Optimizing irregular shared-memory applications for clusters

ABSTRACT

Irregular applications pose challenges in optimizing communication, due to the difficulty of analyzing irregular data accesses accurately and efficiently. This challenge is especially big when translating irregular shared-memory applications to message-passing form for clusters. The lack of effective irregular data analysis in the translation system results in unnecessary or redundant communication, which limits application scalability. In this paper, we present a Lean Distributed Shared Memory (LDSM) system, which features a fast and accurate irregular data access (IDA) analysis. The analysis uses a region-based diff method and makes use of a runtime library that is optimized for irregular applications. We describe three optimizations that improve the LDSM system performance. A parallel array reduction transformation reduces overheads in the analysis. A packed communication optimization and a differential communication optimization effectively eliminate unnecessary and redundant messages. We evaluate the performance of the optimized LDSM system on a set of representative irregular benchmarks. The optimized LDSM executes irregular applications on average 45% faster than the hand-tuned MPI applications.

REFERENCES

• 1: Gagan Agrawal , Joel Saltz, Interprocedural compilation of irregular applications for distributed memory machines, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.48-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224336]
• 2: Cristiana Amza , Alan L. Cox , Sandhya Dwarkadas , Pete Keleher , Honghui Lu , Ramakrishnan Rajamony , Weimin Yu , Willy Zwaenepoel, TreadMarks: Shared Memory Computing on Networks of Workstations, Computer, v.29 n.2, p.18-28, February 1996 [doi>10.1109/2.485843]
• 3: J. Balart, M. Gonzalez, X. Martorell, E. Ayguade, and J. Labarta. Runtime Address Space Computation for SDSM Systems. In The 19th International Workshop on Languages and Compilers for Parallel Computing (LCPC 2006), pages 330--344, 2006.
• 4: Ayon Basumallik , Rudolf Eigenmann, Towards automatic translation of OpenMP to MPI, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088174]
• 5: Ayon Basumallik , Rudolf Eigenmann, Optimizing irregular shared-memory applications for distributed-memory systems, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1122990]
• 6: Tim Brecht , Harjinder Sandhu, The region trap library: handling traps on application-defined regions of memory, Proceedings of the annual conference on USENIX Annual Technical Conference, p.7-7, June 06-11, 1999, Monterey, California
• 7: B. R. Brooks, R. E. Bruccoleri, B. D. Olafson, D. J. States, S. Swaminathan, and M. Karplus. Charmm: A program for macromolecular energy, minimization, and dynamics calculations. Journal of Computational Chemistry, 4(2):187--217, 1983.
• 8: Wei-Yu Chen , Dan Bonachea , Costin Iancu , Katherine Yelick, Automatic nonblocking communication for partitioned global address space programs, Proceedings of the 21st annual international conference on Supercomputing, June 17-21, 2007, Seattle, Washington [doi>10.1145/1274971.1274995]
• 9: Raja Das , Paul Havlak , Joel Saltz , Ken Kennedy, Index array flattening through program transformation, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.70-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224420]
• 10: T. El-Ghazawi, W. Carlson, and J. Draper. UPC Language Specifications, v1.1.1, 2003.
• 11: Message P Forum, MPI: A Message-Passing Interface Standard, University of Tennessee, Knoxville, TN, 1994
• 12: Paul N. Hilfinger , Dan Bonachea , David Gay , Susan Graham , Ben Liblit , Geoff Pike , Katherine Yelick, Titanium Language Reference Manual, University of California at Berkeley, Berkeley, CA, 2001
• 13: Y. Hwang, B. Moon, S. Sharma, R. Das, and J. Saltz. Runtime Support to Parallelize Adaptive Irregular Programs, 1994.
• 14: Jian Ke , Martin Burtscher , Evan Speight, Runtime Compression of MPI Messanes to Improve the Performance and Scalability of Parallel Applications, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.59, November 06-12, 2004 [doi>10.1109/SC.2004.52]
• 15: C. Koelbel , P. Mehrotra, Compiling Global Name-Space Parallel Loops for Distributed Execution, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.440-451, October 1991 [doi>10.1109/71.97901]
• 16: Honghui Lu , Alan L. Cox , Sandhya Dwarkadas , Ramakrishnan Rajamony , Willy Zwaenepoel, Compiler and software distributed shared memory support for irregular applications, Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.48-56, June 18-21, 1997, Las Vegas, Nevada, United States
• 17: Seung-Jai Min , Ayon Basumallik , Rudolf Eigenmann, Optimizing OpenMP programs on software distributed shared memory systems, International Journal of Parallel Programming, v.31 n.3, p.225-249, June 2003 [doi>10.1023/A:1023090719310]
• 18: Seung-Jai Min , Rudolf Eigenmann, Combined compile-time and runtime-driven, pro-active data movement in software DSM systems, Proceedings of the 7th workshop on Workshop on languages, compilers, and run-time support for scalable systems, p.1-6, October 22-23, 2004, Houston, Texas [doi>10.1145/1066650.1066661]
• 19: R. Mirchandaney , J. H. Saltz , R. M. Smith , D. M. Nico , K. Crowley, Principles of runtime support for parallel processors, Proceedings of the 2nd international conference on Supercomputing, p.140-152, June 1988, St. Malo, France [doi>10.1145/55364.55378]
• 20: B. Moon, M. Uysal, and J. Saltz. Index Translation Schemes for Adaptive Computations on Distributed Memory Multicomputers. Technical Report CS-TR-3428, 1995.
• 21: Robert W. Numrich , John Reid, Co-array Fortran for parallel programming, ACM SIGPLAN Fortran Forum, v.17 n.2, p.1-31, Aug. 1998 [doi>10.1145/289918.289920]
• 22: OpenMP Forum. OpenMP: A Proposed Industry Standard API for Shared Memory Programming. Technical report, October 1997.
• 23: Bill Pottenger , Rudolf Eigenmann, Idiom recognition in the Polaris parallelizing compiler, Proceedings of the 9th international conference on Supercomputing, p.444-448, July 03-07, 1995, Barcelona, Spain [doi>10.1145/224538.224655]
• 24: J. Saltz, R. Ponnusamy, S. D. Sharma, B. Moon, Y.-S. Hwang, M. Uysal, and R. Das. A Manual for the CHAOS Runtime Library. Technical Report CS-TR-3437, 1995.
• 25: Shamik D. Sharma , Ravi Ponnusamy , Bongki Moon , Yuan Shin Hwang , Raja Das , Joel Saltz, Run-time and compile-time support for adaptive irregular problems, Proceedings of the 1994 ACM/IEEE conference on Supercomputing, November 14-18, 1994, Washington, D.C. [doi>10.1145/602770.602793]
• 26: Jimmy Su , Katherine Yelick, Automatic Support for Irregular Computations in a High-Level Language, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, p.53.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.118]
• 27: Manuel Ujaldon , Shamik D. Sharma , Joel H. Saltz , Emilio L. Zapata, Run-Time Techniques for Parallelizing Sparse Matrix Problems, Proceedings of the Second International Workshop on Parallel Algorithms for Irregularly Structured Problems, p.43-57, September 04-06, 1995
• 28: Reinhard von Hanxleden , Ken Kennedy, GIVE-N-TAKE—a balanced code placement framework, ACM SIGPLAN Notices, v.29 n.6, p.107-120, June 1994
• 29: Matthew J. Zekauskas , Wayne A. Sawdon , Brian N. Bershad, Software write detection for a distributed shared memory, Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation, p.8-es, November 14-17, 1994, Monterey, California

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Run-time environments

General Terms:
Languages, Performance

Keywords:
MPI, compiler analysis, irregular data accesses, openMP, performance, runtime technique