Go backward to 2.1 A First Example Go up to 2 Examples Go forward to 2.3 Distributed Factorization (Divide and Conquer)

2.2 Distributed Factorization of Integers

The following program demonstrates how to compute the factorizations of a list of integers using the features of Distributed Maple. We may use this program in the context of a session as follows:

      deneb!1> maple
          |\^/|     Maple V Release 4 (Johannes Kepler University Linz)
      ._|\|   |/|_. Copyright (c) 1981-1996 by Waterloo Maple Inc. All rights
       \  MAPLE  /  reserved. Maple and Maple V are registered trademarks of
       <____ ____>  Waterloo Maple Inc.
            |       Type ? for help.
      > read `dist.maple`;
      Distributed Maple V1.0 (c) 1998 Wolfgang Schreiner (RISC-Linz)
      See http://www.risc.uni-linz.ac.at/software/distmaple
      > dist[initialize]([[deneb,solaris], [iris,irix]]):
      connecting deneb...
      connecting iris...
      > main(20,2^90):
      > dist[terminate]():
      > quit:

The program itself is shown below:

# -----------------------------------------------------------------------
#
# distributed Maple
# distributed integer factorizations
#
# -----------------------------------------------------------------------

# -----------------------------------------------------------------------
# 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
  dist[all](`readlib(ifactors);`);

  # 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, tasks, results, i, t, r;

  # length of list
  length := nops(numbers);

  # generate list of tasks
  tasks := [];
  for i from 1 to length do
    t := dist[start](ifactors, numbers[i]);
    tasks := [op(tasks), t];
  od;

  # wait for result values
  results := [];
  for i from 1 to length do
    r := dist[wait](tasks[i]);
    results := [op(results), r];
  od;

  # return results
  RETURN(results);
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:

The main function of this program executes the procedure dist[all] which evaluates its argument string (denoting a command) on each Maple kernel connected to the session; thus on each kernel the Maple library ifactors is loaded. The core function dfactors creates a list of tasks each of which computes ifactors(numbers[i]) for some i. The program then traverses the list waiting for each result in turn and constructs a corresponding list of results.

Above example demonstrates the simple strategy of data parallelism where each element of a central input data structure is processed in parallel and the task results are joined to form the desired output structure. Above example only uses one-level parallelism where each task computes a sequential function; however, as shown in the following section, a task may itself create other tasks.