Combined compile-time and runtime-driven, pro-active data movement in software DSM systems

ABSTRACT

Scientific applications contain program sections that exhibit repetitive data accesses. This paper proposes combined compile-time/runtime data reference analysis techniques that exploit repetitive data access behavior in both regular and irregular program sections. We present a new compiler algorithm to detect such repetitive data references and an API to an underlying software distributed shared memory (software DSM) system to orchestrate the learning and pro-active reuse of communication patterns. We evaluate the combined compile-time/runtime system on a selection of OpenMP applications, exhibiting both regular and irregular data reference patterns, resulting in average performance improvement of 28.1% on 8 processors.

REFERENCES

• 1: 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]
• 2: 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]
• 3: S.-J. M. Ayon, Basumallik, and R. Eigenmann. Supporting realistic openmp applications on a commodity cluster of workstations. In International Workshop on OpenMP Applications and Tools (WOMPAT'03), pages 170--179, June 2003.
• 4: Ricardo Bianchini , Raquel Pinto , Claudio L. Amorim, Data prefetching for software DSMs, Proceedings of the 12th international conference on Supercomputing, p.385-392, July 1998, Melbourne, Australia [doi>10.1145/277830.277925]
• 5: John B. Carter , John K. Bennett , Willy Zwaenepoel, Techniques for reducing consistency-related communication in distributed shared-memory systems, ACM Transactions on Computer Systems (TOCS), v.13 n.3, p.205-243, Aug. 1995 [doi>10.1145/210126.210127]
• 6: Sandhya Dwarkadas , Alan L. Cox , Willy Zwaenepoel, An integrated compile-time/run-time software distributed shared memory system, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.186-197, October 01-04, 1996, Cambridge, Massachusetts, United States
• 7: Thomas Fahringer , Bernhard Scholz, Symbolic evaluation for parallelizing compilers, Proceedings of the 11th international conference on Supercomputing, p.261-268, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263648]
• 8: Manish Gupta , Prithviraj Banerjee, A methodology for high-level synthesis of communication on multicomputers, Proceedings of the 6th international conference on Supercomputing, p.357-367, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143433]
• 9: 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]
• 10: H. Han , C.-W. Tseng, Improving Compiler and Run-Time Support for Adaptive Irregular Codes, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.393, October 12-18, 1998
• 11: Seema Hiranandani , Ken Kennedy , Chau-Wen Tseng, Compiler optimizations for Fortran D on MIMD distributed-memory machines, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.86-100, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125886]
• 12: Update Protocols and Iterative Scientific Applications, Proceedings of the 12th. International Parallel Processing Symposium on International Parallel Processing Symposium, p.675, March 30-April 03, 1998
• 13: Pete Keleher , Alan L. Cox , Willy Zwaenepoel, Lazy release consistency for software distributed shared memory, Proceedings of the 19th annual international symposium on Computer architecture, p.13-21, May 19-21, 1992, Queensland, Australia
• 14: Peter J. Keleher , Chau-Wen Tseng, Enhancing Software DSM for Compiler-Parallelized Applications, Proceedings of the 11th International Symposium on Parallel Processing, p.490-499, April 01-05, 1997
• 15: 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
• 16: Seung Jai Min , Seon Wook Kim , Michael Voss , Sang Ik Lee , Rudolf Eigenmann, Portable Compilers for OpenMP, Proceedings of the International Workshop on OpenMP Applications and Tools: OpenMP Shared Memory Parallel Programming, p.11-19, July 30-31, 2001
• 17: Guhan Viswanathan , James R. Larus, Compiler-directed shared-memory communication for iterative parallel applications, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.10-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States [doi>10.1145/369028.369047]
• 18: Jiajing Zhu , Jay Hoeflinger , David Padua, A synthesis of memory mechanisms for distributed architectures, Proceedings of the 15th international conference on Supercomputing, p.13-22, June 2001, Sorrento, Italy [doi>10.1145/377792.377799]