Communication optimizations for parallel computing using data access information

ABSTRACT

Given the large communication overheads characteristic of modern parallel machines, optimizations that eliminate, hide or parallelize communication may improve the performance of parallel computations. This paper describes our experience automatically applying communication optimizations in the context of Jade, a portable, implicitly parallel programming language designed for exploiting task-level concurrency. Jade programmers start with a program written in a standard serial, imperative language, then use Jade constructs to declare how parts of the program access data. The Jade implementation uses this data access information to automatically extract the concurrency and apply communication optimizations. Jade implementations exist for both shared memory and message passing machines; each Jade implementation applies communication optimizations appropriate for the machine on which it runs. We present performance results for several Jade applications running on both a shared memory machine (the Stanford DASH machine) and a message passing machine (the Intel iPSC/860). We use these results to characterize the overall performance impact of the communication optimizations. For our application set replicating data for concurrent read access and improving the locality of the computation by placing tasks close to the data that they access are the most important optimizations. Broadcasting widely accessed data has a significant performance impact on one application; other optimizations such as concurrently fetching remote data and overlapping computation with communication have no effect.

REFERENCES

• 1: Saman P. Amarasinghe , Monica S. Lam, Communication optimization and code generation for distributed memory machines, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.126-138, June 21-25, 1993, Albuquerque, New Mexico, United States
• 2: Henri E. Bal , M. Frans Kaashoek , Andrew S. Tanenbaum, Orca: A Language for Parallel Programming of Distributed Systems, IEEE Transactions on Software Engineering, v.18 n.3, p.190-205, March 1992 [doi>10.1109/32.126768]
• 3: Rudolf Berrendorf , Jukka Helin, Evaluating the basic performance of the Intel iPSC/860 parallel computer, Concurrency: Practice and Experience, v.4 n.3, p.223-240, May 1992 [doi>10.1002/cpe.4330040303]
• 4: Martin C. Carlisle , Anne Rogers, Software caching and computation migration in Olden, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.29-38, July 19-21, 1995, Santa Barbara, California, United States
• 5: John B. Carter , John K. Bennett , Willy Zwaenepoel, Implementation and performance of Munin, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.152-164, October 13-16, 1991, Pacific Grove, California, United States
• 6: Rohit Chandra , Anoop Gupta , John L. Hennessy, Data locality and load balancing in COOL, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.249-259, May 19-22, 1993, San Diego, California, United States
• 7: I. S. Duff , Roger G. Grimes , John G. Lewis, Sparse matrix test problems, ACM Transactions on Mathematical Software (TOMS), v.15 n.1, p.1-14, March 1989 [doi>10.1145/62038.62043]
• 8: Babak Falsafi , Alvin R. Lebeck , Steven K. Reinhardt , Ioannis Schoinas , Mark D. Hill , James R. Larus , Anne Rogers , David A. Wood, Application-specific protocols for user-level shared memory, Proceedings of the 1994 conference on Supercomputing, p.380-389, December 1994, Washington, D.C., United States
• 9: Robert J. Fowler , Leonidas I. Kontothanassis, Improving Processor and Cache Locality in Fine-Grain Parallel Computations using Object-Affinity Scheduling and Continuation Passing, University of Rochester, Rochester, NY, 1992
• 10: Robert H. Halstead, Jr., MULTILISP: a language for concurrent symbolic computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.501-538, Oct. 1985 [doi>10.1145/4472.4478]
• 11: J. Harris, S. Lazaratos, and R. Michelena. Tomographic string inversion. In 60th Annual International Meeting, Society of Exploration and Geophysics, Extended Abstracts, pages 82--85, 1990.
• 12: M. D. Hill , J. R. Larus , D. A. Wood, Tempest: a substrate for portable parallel programs, Proceedings of the 40th IEEE Computer Society International Conference, p.327, March 05-09, 1995
• 13: Wilson C. Hsieh , Paul Wang , William E. Weihl, Computation migration: enhancing locality for distributed-memory parallel systems, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.239-248, May 19-22, 1993, San Diego, California, United States
• 14: Daniel Edward Lenoski, The design and analysis of DASH: a scalable directory-based multiprocessor, Stanford University, Stanford, CA, 1992
• 15: Todd Mowry , Anoop Gupta, Tolerating latency through software-controlled prefetching in shared-memory multiprocessors, Journal of Parallel and Distributed Computing, v.12 n.2, p.87-106, June 1991 [doi>10.1016/0743-7315(91)90014-Z]
• 16: Todd C. Mowry , Monica S. Lam , Anoop Gupta, Design and evaluation of a compiler algorithm for prefetching, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.62-73, October 12-15, 1992, Boston, Massachusetts, United States
• 17: Martin C. Rinard, The design, implementation and evaluation of Jade: a portable, implicitly parallel programming language, Stanford University, Stanford, CA, 1994
• 18: Martin C. Rinard , Monica S. Lam, Semantic foundations of Jade, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.105-118, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143189]
• 19: M. C. Rinard , D. J. Scales , M. S. Lam, Heterogeneous parallel programming in Jade, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.245-256, November 16-20, 1992, Minneapolis, Minnesota, United States
• 20: Martin C. Rinard , Daniel J. Scales , Monica S. Lam, Jade: A High-Level, Machine-Independent Language for Parallel Programming, Computer, v.26 n.6, p.28-38, June 1993 [doi>10.1109/2.214440]
• 21: Edward Eric Rothberg, Exploiting the memory hierarchy in sequential and parallel sparse Cholesky factorization, Stanford University, Stanford, CA, 1993
• 22: D. Scales and M. S. Lam. The design and evaluation of a shared object system for distributed memory machines. In Proceedings of the First Usenix Symposium on Operating Systems Design and Implementation, November 1994.
• 23: Jaswinder Pal Singh , Wolf-Dietrich Weber , Anoop Gupta, SPLASH: Stanford parallel applications for shared-memory, ACM SIGARCH Computer Architecture News, v.20 n.1, p.5-44, March 1992 [doi>10.1145/130823.130824]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

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

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Languages, Performance