Toward a methodology of optimizing programs for high-performance computers

ABSTRACT

This report describes experiences in porting the Perfect Benchmarks programs to the Alliant FX/8 and Cedar machines. Although there is much to learn before we can really say we know how to optimize programs successfully for parallel computers in general and for hierarchical shared-memory architectures in particular, it is hoped that this report will be helpful to those who are beginning to port and transform programs for parallel machines. Perhaps it is even an interesting reference for experts. In addition, this paper summarizes our experience with the programming tools we used and discusses tools that could have helped to increase the productivity of the optimization process. This information is believed to be a useful basis for future tool development projects.

REFERENCES

• BE92: W. Blume , R. Eigenmann, Performance Analysis of Parallelizing Compilers on the Perfect Benchmarks Programs, IEEE Transactions on Parallel and Distributed Systems, v.3 n.6, p.643-656, November 1992 [doi>10.1109/71.180621]
• CKPK90: George Cybenko , Lyle Kipp , Lynn Pointer , David Kuck, Supercomputer performance evaluation and the Perfect Benchmarks, Proceedings of the 4th international conference on Supercomputing, p.254-266, June 11-15, 1990, Amsterdam, The Netherlands
• CY91: Ding-Kai Chen and Pen-Chung Yew. An Empirical Study DOACROSS Loops. Proceedings of Supercomputing'91, Albuquerque NM, pages 630-632, November 18-, 1991.
• DSB89: J. Dongarra, D. Sorensen, and O. Brewer. Tools and methodology for programming parllel processors. In M. H. Wright, editor, Aspects of Computation on Asynchronous Parallel Processors, pages 125-137. Elsevier Science Pubfishers B. V. (North-Holland), 1989.
• EHJ+91: Rudolf Eigenmann, Jay Hoeflinger, Greg Jaxon, Zhiyuan Li, and David Padua. Restructuring For tran Programs for Cedar. Proceedings of ICPP'91, St. Charles, IL, 1:57-66, August 12-16, 1991.
• EHJP92: R. Eigenmann, J. Hoeflinger, G. Jaxon, and D. Padua. The Cedar Fortran Project. Technical Report 1262, Univ. of Illinois at Urbana-Chmpaign Center for Supercomp. R&D, 1992.
• EHLP92: Rudolf Eigenmann, Jay Hoeflinger, Zhiyuan Li, and David Padua. Experience in the Automatic Parallelization of Four Perfect-Benchmarks Programs. Lecture Notes in Computer Science 589, Sprinnger Verlag, NY, pages 65-83, 1992.
• EM91: Perry Emrath and Bret Marslf mdb- Xylem Parallel Debugger User's Guide. Technical report, Univ. of Illinois at Urban-Champaign, Center for Supercomputing Res. & Dev., December 1991. CSRD Report No. 1180.
• EM93: Rudolf Eigenmann and Patrick McClaughry. Practical Tools for Optimizing Parallel Programs. Presented at the 1993 SCS Multiconference, Arlington, VA, March 27- April 1, 1993.
• GJT+91: K. Gallivan, W. Jalby, S. Turner, A. Veidenbaum, and H. Wijshoff. Preliminary Basic Performance Analysis of the Cedar Multiprocessor Memory Systems. Proceedings of ICPP'91, St. Charles, IL, I:71-75, August 12-16, 1991.
• Hoe91: Jay Hoeflinger. Cedar Fortran Programmer's Handbook. Technical report, Univ. of Illinois at Urbana Champaign, Center for Supercomputing Res. & Dev., October 1991. CSRD Report No. 1157.
• ME91: Ulrike Meier , Rudolf Eigenmann, Parallelization and performance of Conjugate Gradient algorithms on the Cedar hierarchical-memory multiprocessor, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.178-188, April 21-24, 1991, Williamsburg, Virginia, United States
• Poi90: Lynn Pointer. Perfect: Performance Evaluation for Cost-Effective Transformations Report 2. Technical report, University of Illinois at Urbana-Champaign, Center for Supercomputing Res & Dev, March 1990. CSRD Report No. 964.
• PP93: Paul M. Petersen , David A. Padua, Static and dynamic evaluation of data dependence analysis, Proceedings of the 7th international conference on Supercomputing, p.107-116, July 19-23, 1993, Tokyo, Japan [doi>10.1145/165939.165961]
• SBSS+92: S. Sharma, R. Bramley P. Sinvahl-Sharma, J. Bruner, and G. Cybenko. P3S: Portable, Parallel Program Performance Evalution System. Technical report, Univ. of Illinois at Urbana-Champaign, Center for Supetcomputing Res. & Dev., September 1992. CSRD Report No. 1170.
• Sta91: CSRD Staff. The Cedar Project. Proceedings of ICPP'91, St. Charles, IL, August 12-16, 1991.
• TJC91: Allan Tuchman , David Jablonowski , George Cybenko, Run-time visualization of program data, Proceedings of the 2nd conference on Visualization '91, October 22-25, 1991, San Diego, California

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.2 SOFTWARE ENGINEERING
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Compilers

General Terms:
Algorithms, Design, Performance