Evaluating uniform expressions within two steps of minimum parallel time

ABSTRACT

Consider an array of Processing Elements [PEs], connected by a 2-dimensional grid network, and holding at most one operand of an expression in each PE. Suppose that each PE is allowed, in any one parallel step, to receive one item of data from any of its four immediate neighbors, and to transmit one datum, as well. How can an associative operator, such as addition, combine all the operands, using as little time for communciation as possible? An expression using such a single operator is termed a uniform expression. When the total number of communication links used is the measure of goodness, this problem becomes a Steiner Tree problem, in the Manhattan Distance metric. When the measure is minimizing the parallel time to completion, a method for solving this problem is given which is optimal to within an additive constant of two time-steps. The method has applications when the operands are matrices, spread over an array of PEs, as well. Some lower bounds for this problem, in more general networks, are also proven.

REFERENCES

• 1: Mark Bromley , Steven Heller , Tim McNerney , Guy L. Steele, Jr., Fortran at ten gigaflops: the connection machine convolution compiler, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.145-156, June 24-28, 1991, Toronto, Ontario, Canada
• 2: DREYFUS, S., AND WAGNER, R. 1972. The Steiner problem in graphs. Networks, 1, 195-207.
• 3: John R. Gilbert , Robert Schreiber, Optimal expression evaluation for data parallel architectures, Journal of Parallel and Distributed Computing, v.13 n.1, p.58-64, Sept. 1991 [doi>10.1016/0743-7315(91)90109-M]
• 4: S. Lennart Johnsson , Ching-Tien Ho, Optimum Broadcasting and Personalized Communication in Hypercubes, IEEE Transactions on Computers, v.38 n.9, p.1249-1268, September 1989 [doi>10.1109/12.29465]
• 5: Robert A. van de Geijn, On global combine operations, Journal of Parallel and Distributed Computing, v.22 n.2, p.324-328, Aug. 1994 [doi>10.1006/jpdc.1994.1091]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms

Keywords:
communication cost, communication time, parallel reduction, processor grid