Go backward to 2.2 Distributed Factorization of Integers Go up to 2 Examples Go forward to 2.4 Shared Data Objects

2.3 Distributed Factorization (Divide and Conquer)

The following program solves the same problem as that one shown in the previous section; however it implements a divide and conquer algorithms to recursively decompose the input list into halves that are processed in parallel:

# -----------------------------------------------------------------------
#
# distributed Maple
# distributed integer factorizations (recursive version)
#
# -----------------------------------------------------------------------

# -----------------------------------------------------------------------
# return a list of `length` elements each of which is a pair [i, f] where 
# `i` <= `size` is a random integer and `f` is the factorization of `i`
# -----------------------------------------------------------------------
main := proc(length, size)
  local
    numbers, results, ti;
 
  # let machines load factorization library and this file
  dist[all](`readlib(ifactors);`);
  dist[all](`read ``/home/distmaple/examples/ifactor2.maple``;`);

  # generate list of numbers
  numbers := rands(length, size);

  # compute result
  results := dfactors(numbers);

  # return list of argument/result pairs
  RETURN ([seq([numbers[i], results[i]], i = 1..length)]);
end:

# -----------------------------------------------------------------------
# return list of facorizations of `numbers` list
# -----------------------------------------------------------------------
dfactors := proc(numbers)
  local
    length, m, i, numbers1, numbers2, task1, result1, result2;

  # recursion base
  length := nops(numbers);
  if length = 0 then
    RETURN ([]);
  elif length = 1 then
    RETURN ([ifactors(numbers[1])]);
  fi;

  # divide problem
  m := trunc(length/2);
  numbers1 := [ seq(numbers[i], i=1..m) ];
  numbers2 := [ seq(numbers[i], i=m+1..length) ];

  # conquer in parallel
  task1 := dist[start](dfactors, numbers1);
  result2 := dfactors(numbers2);

  # combine results
  result1 := dist[wait](task1);
  RETURN ([op(result1), op(result2)]);
end:

# -----------------------------------------------------------------------
# return a list of `length` random numbers less than `size`
# -----------------------------------------------------------------------
rands := proc(length, size)
  local
    r, i, n, numbers;

  # random number generator
  r := rand(size);

  # generate list
  numbers := [];
  for i from 1 to length do
    n := r();
    numbers := [op(numbers), n];
  od;

  # return list
  RETURN (numbers);
end:

Since each of the tasks (executed on any Maple kernel connected to the session) needs to call the function dfactors, we call dist[all] to let each Maple kernel read the Maple file from a path in the global file system. The computation itself is pursued by splitting one recursive call of dfactors(numbers1) as a separate task, computing dfactors(numbers2) in the current task, waiting for the result of the first task, and then joining both results to the final result.

Above program demonstrates the application of nested parallelism where each task in turn may create additional tasks if the input is not simple enough to be solved directly.