A global communication optimization technique based on data-flow analysis and linear algebra

ABSTRACT

Reducing communication overhead is extremely important in distributed-memory message-passing architectures. In this article, we present a technique to improve communication that considers data access patterns of the entire program. Our approach is based on a combination of traditional data-flow analysis and a linear algebra framework, and it works on structured programs with conditional statements and nested loops but without arbitrary goto statements.The distinctive features of the solution are the accuracy in keeping communication set information, support for general alignments and distributions including block-cyclic distribu-tions, and the ability to simulate some of the previous approaches with suitable modifications. We also show how optimizations such as message vectorization, message coalescing, and redundancy elimination are supported by our framework. Experimental results on several benchmarks show that our technique is effective in reducing the number of messages (anaverage of 32% reduction), the volume of the data communicated (an average of 37%reduction), and the execution time (an average of 26% reduction).

REFERENCES

• 1: Gagan Agrawal , Joel Saltz, Interprocedural data flow based optimizations for distributed memory compilation, Software—Practice & Experience, v.27 n.5, p.519-545, May 1997 [doi>10.1002/(SICI)1097-024X(199705)27:5<519::AID-SPE95>3.3.CO;2-F]
• 2: ADVE, V., MELLOR-CRUMMEY, J., AND SETHI, A. 1997. An integer set framework for HPF analysis and code generation. Technical Report TR97-275, Computer Science Dept., Rice University.
• 3: Vikram Adve , John Mellor-Crummey, Advanced code generation for high performance Fortran, Compiler optimizations for scalable parallel systems: languages, compilation techniques, and run time systems, Springer-Verlag New York, Inc., New York, NY, 2001
• 4: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 5: F. E. Allen , J. Cocke, A program data flow analysis procedure, Communications of the ACM, v.19 n.3, p.137, March 1976 [doi>10.1145/360018.360025]
• 6: 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
• 7: Corinne Ancourt , Fabien Coelho , Francois Irigoin , Ronan Keryell, A linear algebra framework for static High Performance Fortran code distribution, Scientific Programming, v.6 n.1, p.3-27, Spring 1997
• 8: BALASUNDARAM, V., FOX, G., KENNEDY, K., AND K_REMER, U. 1990. An interactive environment for data partitioning and distribution. In 5th Distributed Memory Computing Conference, Charleston, SC.
• 9: Utpal K. Banerjee, Loop Parallelization, Kluwer Academic Publishers, Norwell, MA, 1994
• 10: Prithviraj Banerjee , John A. Chandy , Manish Gupta , Eugene W. Hodges IV , John G. Holm , Antonio Lain , Daniel J. Palermo , Shankar Ramaswamy , Ernesto Su, The Paradigm Compiler for Distributed-Memory Multicomputers, Computer, v.28 n.10, p.37-47, October 1995 [doi>10.1109/2.467577]
• 11: Zeki Bozkus , Alok N. Choudhary , Geoffrey Fox , Tomasz Haupt , Sanjay Ranka, A Compilation Approach for Fortran 90D/ HPF Compilers, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.200-215, August 12-14, 1993
• 12: David Callahan , Ken Kennedy, Analysis of interprocedural side effects in a parallel programming environment, Journal of Parallel and Distributed Computing, v.5 n.5, p.517-550, October 1988 [doi>10.1016/0743-7315(88)90011-1]
• 13: Soumen Chakrabarti , Manish Gupta , Jong-Deok Choi, Global communication analysis and optimization, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.68-78, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 14: Siddhartha Chatterjee , John R. Gilbert , Fred J. E. Long , Robert Schreiber , Shang-Hua Teng, Generating local addresses and communication sets for data-parallel programs, Journal of Parallel and Distributed Computing, v.26 n.1, p.72-84, April 1, 1995 [doi>10.1006/jpdc.1995.1049]
• 15: Béatrice Creusillet , François Irigoin, Interprocedural Array Region Analyses, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, p.46-60, August 10-12, 1995
• 16: Ian Foster, Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 17: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 18: GONG, C., GUPTA, R., AND MELHEM, R. 1993. Compilation techniques for optimizing communication on distributed-memory systems. In Proc. International Conference on Parallel Processing, Volume II, pages 39-46, St. Charles, IL.
• 19: Elana D. Granston , Alexander V. Veidenbaum, Detecting redundant accesses to array data, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.854-865, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.126714]
• 20: T. Gross , P. Steenkiste, Structured dataflow analysis for arrays and its use in an optimizing complier, Software—Practice & Experience, v.20 n.2, p.133-155, February 1990 [doi>10.1002/spe.4380200203]
• 21: M. Gupta , P. Banerjee, Demonstration of Automatic Data Partitioning Techniques for Parallelizing Compilers on Multicomputers, IEEE Transactions on Parallel and Distributed Systems, v.3 n.2, p.179-193, March 1992 [doi>10.1109/71.127259]
• 22: Manish Gupta , Sam Midkiff , Edith Schonberg , Ven Seshadri , David Shields , Ko-Yang Wang , Wai-Mee Ching , Ton Ngo, An HPF compiler for the IBM SP2, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.71-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224422]
• 23: Manish Gupta , Edith Schonberg , Harini Srinivasan, A Unified Data-Flow Framework for Optimizing Communication, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.266-282, August 08-10, 1994
• 24: S. K. S. Gupta , S. D. Kaushik , C.-H. Huang , P. Sadayappan, Compiling array expressions for efficient execution on distributed-memory machines, Journal of Parallel and Distributed Computing, v.32 n.2, p.155-172, Feb. 1, 1996 [doi>10.1006/jpdc.1996.0011]
• 25: M. W. Hall , S. Hiranandani , K. Kennedy , C.-W. Tseng, Interprocedural compilation of Fortran D for MIMD distributed-memory machines, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.522-534, November 16-20, 1992, Minneapolis, Minnesota, United States
• 26: Mary W. Hall , Brian R. Murphy , Saman P. Amarasinghe , Shih-Wei Liao , Monica S. Lam, Interprocedural Analysis for Parallelization, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, p.61-80, August 10-12, 1995
• 27: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 28: Seema Hiranandani , Ken Kennedy , Chau-Wen Tseng, Compiling Fortran D for MIMD distributed-memory machines, Communications of the ACM, v.35 n.8, p.66-80, Aug. 1992 [doi>10.1145/135226.135230]
• 29: Wayne Kelly , Vadim Maslov , William Pugh , Evan Rosser , Tatiana Shpeisman , David Wonnacott, The Omega Library interface guide, University of Maryland at College Park, College Park, MD, 1995
• 30: Ken Kennedy , Nenad Nedeljkovic, Combining dependence and data-flow analyses to optimize communication, Proceedings of the 9th International Symposium on Parallel Processing, p.340-346, April 25-28, 1995
• 31: KENNEDY, K. AND SETHI, A. 1995. A constrained-based communication placement framework, Technical Report CRPC-TR95515-S, CRPC, Rice University.
• 32: K. Kennedy , A. Sethi, A communication placement framework with unified dependence and data-flow analysis, Proceedings of the Third International Conference on High-Performance Computing (HiPC '96), p.201, December 19-22, 1996
• 33: Ken Kennedy , Ajay Sethi, Resource-Based Communication Placement Analysis, Proceedings of the 9th International Workshop on Languages and Compilers for Parallel Computing, p.369-388, August 08-10, 1996
• 34: Ken Kennedy , Nenad Nedeljkovic , Ajay Sethi, A linear-time algorithm for computing the memory access sequence in data-parallel programs, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.102-111, July 19-21, 1995, Santa Barbara, California, United States
• 35: KENNEDY, K., NEDELJKOVIC, N., AND SETHI, A. 1996. Communication generation for cyclic(k) distributions. In Languages, Compilers, and Run-Time Systems for Scalable Computers, B. Szymanski and B. Sinharoy (Eds.), Chapter 14, Kluwer Academic Publishers.
• 36: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Optimal code motion: theory and practice, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1117-1155, July 1994 [doi>10.1145/183432.183443]
• 37: Charles H. Koelbel , David B. Loveman , Robert S. Schreiber , Guy L. Steele, Jr. , Mary E. Zosel, The high performance Fortran handbook, MIT Press, Cambridge, MA, 1994
• 38: PALERMO, D. g., Su, E., CHANDY, g. A., AND BANERJEE, P. 1994. Communication optimizations used in the PARADIGM compiler for distributed-memory multicomputers. In Proc. International Conference on Parallel Processing.
• 39: POLYCHRONOPOULOS, C., GIRKAR, M. B., HAGHIGHAT, M. R., LEE, C. L., LEUNG, B. P., AND SCHOUTEN, D.A. 1989. Parafrase-2: An environment for parallelizing, partitioning, synchronizing, and scheduling programs on multiprocessors. In Proc. the International Conference on Parallel Processing, St. Charles IL, August 1989, pages II 39-48.
• 40: William Pugh, A practical algorithm for exact array dependence analysis, Communications of the ACM, v.35 n.8, p.102-114, Aug. 1992 [doi>10.1145/135226.135233]
• 41: Ernesto Su , Antonio Lain , Shankar Ramaswamy , Daniel J. Palermo , Eugene W. Hodges, IV , Prithviraj Banerjee, Advanced compilation techniques in the PARADIGM compiler for distributed-memory multicomputers, Proceedings of the 9th international conference on Supercomputing, p.424-433, July 03-07, 1995, Barcelona, Spain [doi>10.1145/224538.224650]
• 42: Ernesto Su , Daniel J. Palermo , Prithviraj Banerjee, Processor Tagged Descriptors: A Data Structure for Compiling for Distributed-Memory Multicomputers, Proceedings of the IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques, p.123-132, August 24-26, 1994
• 43: TARJAN, R. E. 1974. Testing flow graph reducibility. Journal of Computer and System Sciences, 9:355-365.
• 44: Ashwath Thirumalai , J. Ramanujam, Efficient computation of address sequences in data parallel programs using closed forms for basis vectors, Journal of Parallel and Distributed Computing, v.38 n.2, p.188-203, Nov. 1, 1996 [doi>10.1006/jpdc.1996.0140]
• 45: VAN HANXLEDEN, R. AND KENNEDY, K. 1993. A code placement framework and its application to communication generation. Technical Report CRPC-TR93337-S, CRPC, Rice University.
• 46: Reinhard von Hanxleden , Ken Kennedy, GIVE-N-TAKE—a balanced code placement framework, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.107-120, June 20-24, 1994, Orlando, Florida, United States
• 47: VENKATACHAR, A., RAMANUJAM, J., AND THIRUMALAI, A. 1997. Communication generation for block-cyclic distributions. Parallel Processing Letters, 7, 2, 195-202, June.
• 48: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 49: Xin Yuan , Rajiv Gupta , Rami G. Melhem, An Array Data Flow Analysis Based Communication Optimizer, Proceedings of the 10th International Workshop on Languages and Compilers for Parallel Computing, p.246-260, August 07-09, 1997
• 50: YUAN, X., GUPTA, R., AND MELHEM, R. 1997b. Demand-driven data flow analysis for communication optimization. Parallel Processing Letters, 7, 4, 359-370, December.
• 51: M. Gerndt, Updating distributed variables in local computations, Concurrency: Practice and Experience, v.2 n.3, p.171-193, Sep. 1990 [doi>10.1002/cpe.4330020303]
• 52: Hans Zima , Barbara Chapman, Supercompilers for parallel and vector computers, ACM Press, New York, NY, 1990

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.6 Programming Environments
          Subjects: Integrated environments

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Frameworks
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Languages

Keywords:
communication optimizations, data-flow analysis, distributed-memory machines, global optimizations, message vectorization, parallelism