Portable programming within a message-passing model: the FFT as an example

ABSTRACT

This paper describes a portable programming environment for MIMD concurrent processors based on an object-oriented, message-passing paradigm. The basis of this environment is the Virtual Machine Loosely Synchronous Communication System (VMLSCS) which is designed to be used for loosely synchronous problems. VMLSCS is structured to make efficient use of hierarchical memory, and permits communication and calculation to be overlapped on certain concurrent processors. As an example, the use of VMLSCS in performing both one-dimensional and multi-dimensional fast Fourier transforms (FFTs) on concurrent multiprocessors is described. It is shown that all necessary interprocessor communication can be performed by a single routine, vm_index. Thus the construction of a portable concurrent FFT rests on the implementation of vm_index on the target machines. In the multi-dimensional algorithm a strip decomposition is applied to each of the directions in turn so that each of the FFTs performed in a particular direction are done in one processor. This allows fast sequential one-dimensional FFTs to be exploited. The implementation of vm_index on both homogeneous and inhomogeneous hypercubes, and shared memory multiprocessors is discussed.

REFERENCES

• Angus 88: Ian G. Angus , Geoffrey C. Fox , Jai Sam Kim , David W. Walker, Solving problems on concurrent processors: vol. 2, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• Baillie 88: C.F. Baillie, "CrOS on the BBN Butterfly," Caltech Concurrent Computation Program Technical Bulletin, 11:13, Sept. 1987.
• Briggs 87: William L. Briggs , Leslie B. Hart , Roland A. Sweet , Abbie O'Gallagher, Multiprocessor FFT methods, SIAM Journal on Scientific and Statistical Computing, v.8 n.1, p.27-42, January 2, 1987 [doi>10.1137/0908011]
• Clapp 88: Russelil M. Clapp and Trevor Mudge, "Ada on a Hypercube," this Volume, 1988.
• Cooley 65: J.W. Cooley and J. W. Tukey, "An Algorithm for the Machine Calculation of Complex Fourier Series," Math. Comp., 19:297, 1965.
• Dally 88a: William J. Dally and Andrew A. Chien, "Object-Oriented Concurrent Programming in CST," this Volume, 1988.
• Dally 88b: William J. Dally, "Fine-Grain Message-Passing Concurrent Computers," this Volume, 1988.
• Felten 88: Edward W. Felten and Steve W. Otto, "Coherent Parallel C," this Volume, 1988.
• Fox 88a: Geoffrey C. Fox , Mark A. Johnson , Gregory A. Lyzenga , Steve W. Otto , John K. Salmon , David W. Walker, Solving problems on concurrent processors. Vol. 1: General techniques and regular problems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• Fox 88b: G.C. Fox, "What Have We Learned from Using Real Parallel Machines to Solve Real Problems?'' this Volume. Also available as CaJtech report CSP 522, 1988.
• Fox 88c: G.C. Fox and D. W. Walker, "A Portable Programming Environment for Multiprocessors," to be presented at the 12th IMACS World Congress on Scientific Computation, July 18-22, 1988, Paris, )France.
• Griffiths 88: M. Griffiths, "Ada Tasking on the Sequent Balance," this Volume. Also available as Caltech report CsP 577, 1988.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computation of transforms (e.g., fast Fourier transform)

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

General Terms:
Algorithms, Performance, Theory