Evaluation of compiler generated parallel programs on three multicomputers

ABSTRACT

Distributed memory parallel processors (DMPPs) have no hardware support for a global address space. However, conventional programs written in a sequential imperative language such as Fortran typically manipulate few, large arrays. The Oxygen compiler, developed as part of the K2 project, translates conventional Fortran code, augmented with code and data distribution directives, into C programs including SEND/RECEIVE communication primitives. The compiler directives, which are either supplied by the user, or for simple programs generated automatically, support a global name space through a run-time mechanism called data consistency analysis. We report in this paper the performance of seven parallel programs generated by Oxygen for three DMPPs, namely for a Parsytec Supercluster, an iWARP, and for the Fujitsu AP1000. All machines were configured as 8 x 8 tori.

REFERENCES

• 1: M. Annaratone , M. Fillo , M. Halbherr , R. Rühl , P. Steiner , M. Viredaz, The K2 distributed memory parallel processor: architecture, compiler, and operating system, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.900-909, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.126721]
• 2: P. Beadle , C. Pommerell , M. Annaratone, K9: a simulator of distributed-memory parallel processors, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.765-774, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76350]
• 3: Parsytec. Megaframe- SuperCluster series, technical overview. Technical report, Aachen, 1988
• 4: Shekhar Borkar , Robert Cohn , George Cox , Thomas Gross , H. T. Kung , Monica Lam , Margie Levine , Brian Moore , Wire Moore , Craig Peterson , Jim Susman , Jim Sutton , John Urbanski , Jon Webb, Supporting systolic and memory communication in iWarp, Proceedings of the 17th annual international symposium on Computer Architecture, p.70-81, May 28-31, 1990, Seattle, Washington, United States
• 5: H. Ishihata et al. An architecture of highly parallel computer AP1000. In Pacific R,m Con/erence on Communications, Computers and S,gnal Processing, pages 13-16. IEEE, May 1991.
• 6: R. Rtihl and M. Annaratone. A parallelizing compiler for distributed memory parallel processors. TechmcaI report, Swms Federal Institute of Technology Zurich, Integrated Systems Laboratory, 1991. Also to appear in IEEE Trans. on Par and Dist Syst.
• 7: M Annaratone and R. Rfihl. Balancing interprocessor communication and computation on torus-connected multicomputers running compller-parallelized code. In Proc. SHPCC 92, Withamsburg VA, March 1992. IEEE
• 8: C. Polychronopoulos et al. Parafrase-II: An environment for parallehzing, partitioning, synchronizing, and scheduling programs on multiprocessors. Technical report, University of Illinois, CSRD, 1989.
• 9: Michael Burke , Ron Cytron , Jeanne Ferrante , Wilson Hsieh , Vivek Sarkar , David Shields, Automatic discovery of parallelism: a tool and an experiment (extended abstract), Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems, p.77-84, July 19-21, 1988, New Haven, Connecticut, United States
• 10: S. Hiranandani, K. Kennedy, and C. Tseng. Compiler support for machine-independent parallel programming in Fortran D. Technical Report TR90-149, Rice Umversity, February 1991.
• 11: D. CaIlahan and K. Kennedy Compiling programs for distributed memory multiprocessors. The Journal of Supercomput,ng, Vol 2:151-169, 1988.
• 12: Michael Gerndt, Array distribution in SUPERB, Proceedings of the 3rd international conference on Supercomputing, p.164-174, June 05-09, 1989, Crete, Greece [doi>10.1145/318789.318808]
• 13: C. Koelbel , P. Mehrotra , J. Van Rosendale, Supporting shared data structures on distributed memory architectures, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.177-186, March 14-16, 1990, Seattle, Washington, United States
• 14: A. Rogers , K. Pingali, Process decomposition through locality of reference, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.69-80, June 19-23, 1989, Portland, Oregon, United States
• 15: Joel Saltz , Kathleen Crowley , Ravi Mirchandaney , Harry Berryman, Run-time scheduling and execution of loops on message passing machines, Journal of Parallel and Distributed Computing, v.8 n.4, p.303-312, Apr. 1990 [doi>10.1016/0743-7315(90)90129-D]
• 16: J. Li , M. Chen, Compiling Communication-Efficient Programs for Massively Parallel Machines, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.361-376, July 1991 [doi>10.1109/71.86111]
• 17: Manish Gupta , Prithviraj Banerjee, Compile-Time Estimation of Communication Costs on Multicomputers, Proceedings of the 6th International Parallel Processing Symposium, p.470-475, March 01, 1992
• 18: Vasanth Balasundaram , Geoffrey Fox , Ken Kennedy , Ulrich Kremer, A static performance estimator to guide data partitioning decisions, ACM SIGPLAN Notices, v.26 n.7, p.213-223, July 1991
• 19: Thomas Gross , Monica S. Lam, Compilation for a high-performance systolic array, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.27-38, June 25-27, 1986, Palo Alto, California, United States
• 20: P. S Tseng, M Lain, and H. T Kung. The domain parallel computation model on Warp In Proc. SPIE. SPIE, 1988.
• 21: P.-S. Tseng, A parallelizing compiler for distributed memory parallel computers, Carnegie Mellon University, Pittsburgh, PA, 1989
• 22: Ping-Sheng Tseng, Compiling programs for a linear systolic array, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.311-321, June 1990, White Plains, New York, United States
• 23: William J. Dally, Performance Analysis of k-ary n-cube Interconnection Networks, IEEE Transactions on Computers, v.39 n.6, p.775-785, June 1990 [doi>10.1109/12.53599]
• 24: S. Lennart Johnsson, Communication effect basic linear algebra computations on hypercube architectures, Journal of Parallel and Distributed Computing, v.4 n.2, p.133-172, April 1, 1987 [doi>10.1006/jpdc.1997.1353]
• 25: M Neeracher and R Riihl. Automatic Parallelization of LIN- PACK Routines on Dmtribu~ed Memory Parallel Processors. Techmcal Report 92/7, Sw,ss Federal Institute of Technology Zurich, Integrated Systems Laboratory, 1992
• 26: R. Riihl. Oxygen--A short tutorial Technical Report 91/9, Swiss Federal Institute of Technology Zurich, Integrated Systems Laboratory, 1991.
• 27: C. L. Lawson , R. J. Hanson , D. R. Kincaid , F. T. Krogh, Basic Linear Algebra Subprograms for Fortran Usage, ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.308-323, Sept. 1979 [doi>10.1145/355841.355847]
• 28: R. S. Martin and J H Wilkinson. Similarity reduction of a general matrix to Hessenberg form. In J H Wilkinson and C. Reinsch, editors, Handbook for Automatzc Computatzon. Vol. 2 (L~near Algebra), pages 339-358. Springer-Verlag, New York, 1971.
• 29: B.S. Garbow, J M. Boyle, J.J. Dongarra, and C.B. Moler Matrix E~gensystvm t:~outinas - EISPACK guide Extension. Lecture notes in Computer Science Sprmger-Verlag, 1977.
• 30: G Heiser, C. Pommerell, J. Weis, and W. Fichtner. Three dlmensmnal numerical semiconductor device simulation: Algorithms, architectures, results. IEEE Trans. on CAD, 1991.
• 31: Claude Pommerell , Marco Annaratone , Wolfgang Fichtner, A set of new mapping and coloring heuristics for distributed-memory parallel processors, SIAM Journal on Scientific and Statistical Computing, v.13 n.1, p.194-226, Jan. 1992 [doi>10.1137/0913011]
• 32: Y. Sand. SPARSKIT A basic tool kit for sparse matrix computation Technical Report CSRD Report no. 1029, Umversity of Illinom, CSRD, August 1990.
• 33: Y. Saad, Krylov subspace methods on supercomputers, SIAM Journal on Scientific and Statistical Computing, v.10 n.6, p.1200-1232, Nov. 1989 [doi>10.1137/0910073]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FORTRAN

General Terms:
Algorithms, Design, Languages