Hypergraph partitioning for automatic memory hierarchy management

ABSTRACT

In this paper, we present a mechanism for automatic management of the memory hierarchy, including secondary storage, in the context of a global address space parallel programming framework. The programmer specifies the parallelism and locality in the computation. The scheduling of the computation into stages, together with the movement of the associated data between secondary storage and global memory, and between global memory and local memory, is automatically managed. A novel formulation of hypergraph partitioning is used to model the optimization problem of minimizing disk I/O. Experimental evaluation of the proposed approach using a sub-computation from the quantum chemistry domain shows a reduction in the disk I/O cost by up to a factor of 11, and a reduction in turnaround time by up to 49%, as compared to alternative approaches used in state-of-the-art quantum chemistry codes.

REFERENCES

• 1: Nawaaz Ahmed , Nikolay Mateev , Keshav Pingali, Synthesizing transformations for locality enhancement of imperfectly-nested loop nests, Proceedings of the 14th international conference on Supercomputing, p.141-152, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335245]
• 2: Gerald Baumgartner , David E. Bernholdt , Daniel Cociorva , Robert Harrison , So Hirata , Chi-Chung Lam , Marcel Nooijen , Russell Pitzer , J. Ramanujam , P. Sadayappan, A high-level approach to synthesis of high-performance codes for quantum chemistry, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-10, November 16, 2002, Baltimore, Maryland
• 3: Umit Catalyurek , Cevdet Aykanat, Decomposing Irregularly Sparse Matrices for Parallel Matrix-Vector Multiplication, Proceedings of the Third International Workshop on Parallel Algorithms for Irregularly Structured Problems, p.75-86, August 19-21, 1996
• 4: Umit Catalyurek , Cevdet Aykanat, Hypergraph-Partitioning-Based Decomposition for Parallel Sparse-Matrix Vector Multiplication, IEEE Transactions on Parallel and Distributed Systems, v.10 n.7, p.673-693, July 1999 [doi>10.1109/71.780863 ]
• 5: Chang, C., Kurc, T., Sussman, A., Çatalyürek, U. V., And Saltz, J. 2001. A hypergraph-based workload partitioning strategy for parallel data aggregation. In Proceedings of the Eleventh SIAM Conference on Parallel Processing for Scientific Computing, SIAM.
• 6: Crawford, T., And III, H. S. 2000. An Introduction to Coupled Cluster Theory for Computational Chemists. In Reviews in Computational Chemistry, K. Lipkowitz and D. Boyd, Ed., vol. 14. John Wiley & Sons, Ltd., 33--136.
• 7: Iain S. Duff , Michele Marrone , Giuseppe Radicati , Carlo Vittoli, Level 3 basic linear algebra subprograms for sparse matrices: a user-level interface, ACM Transactions on Mathematical Software (TOMS), v.23 n.3, p.379-401, Sept. 1997 [doi>10.1145/275323.275327]
• 8: Hendrickson, B., And Leland, R. 1994. The Chaco user's guide: Version 2.0. Tech. Rep. SAND94-2692, Sandia National Laboratories.
• 9: High Performance Computational Chemistry Group. 2004. NWChem, A Computational Chemistry Package for Parallel Computers, Version 4.6. Pacific Northwest National Laboratory.
• 10: Laxmikant V. Kale , Sanjeev Krishnan, CHARM++: a portable concurrent object oriented system based on C++, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.91-108, September 26-October 01, 1993, Washington, D.C., United States
• 11: George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: application in VLSI domain, Proceedings of the 34th annual conference on Design automation, p.526-529, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266273]
• 12: Gaurav Khanna , Nagavijayalakshmi Vydyanathan , T. Kurc , U. Catalyurek , P. Wyckoff , J. Saltz , P. Sadayappan, A hypergraph partitioning based approach for scheduling of tasks with batch-shared I/O, Proceedings of the Fifth IEEE International Symposium on Cluster Computing and the Grid (CCGrid'05) - Volume 2, p.792-799, May 09-12, 2005
• 13: Induprakas Kodukula , Nawaaz Ahmed , Keshav Pingali, Data-centric multi-level blocking, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.346-357, June 16-18, 1997, Las Vegas, Nevada, United States
• 14: Krishnamoorthy, S., Catalyurek, U., Nieplocha, J., Rountev, A., And Sadayappan, P. 2006. An extensible global address space frame-work with decoupled task and data abstractions. In Proc. IPDPS Workshop on Next Generation Software.
• 15: Krishnan, S., Krishnamoorthy, S., Baumgartner, G., Cociorva, D., Lam, C., Sadayappan, P., Ramanujam, J., Bernholdt, D., And Choppella, V. 2003. Data Locality Optimization for Synthesis of Efficient Out-of-Core Algorithms. In Proc. 10th Annual International Conference on High Performance Computing (HiPC), Springer Verlag, 406--417.
• 16: Krishnan, S., Krishnamoorthy, S., Baumgartner, G., Lam, C.-C., Ramanujam, J., Sadayappan, P., And Choppella, V. 2004. Efficient synthesis of out-of-core algorithms for tensor contractions using a nonlinear optimization solver. In The 18th International Parallel and Distributed Processing Symposium.
• 17: Amy W. Lim , Monica S. Lam, Maximizing parallelism and minimizing synchronization with affine partitions, Parallel Computing, v.24 n.3-4, p.445-475, May, 1998 [doi>10.1016/S0167-8191(98)00021-0 ]
• 18: Amy W. Lim , Shih-Wei Liao , Monica S. Lam, Blocking and array contraction across arbitrarily nested loops using affine partitioning, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.103-112, June 2001, Snowbird, Utah, United States
• 19: Juan J. Navarro , Toni Juan , Tomás Lang, MOB forms: a class of multilevel block algorithms for dense linear algebra operations, Proceedings of the 8th international conference on Supercomputing, p.354-363, July 11-15, 1994, Manchester, England [doi>10.1145/181181.181561]
• 20: Keith H. Randall , Charles E. Leiserson, Cilk: efficient multithreaded computing, 1998
• 21: Swarup Kumar Sahoo , Sriram Krishnamoorthy , Rajkiran Panuganti , P. Sadayappan, Integrated Loop Optimizations for Data Locality Enhancement of Tensor Contraction Expressions, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.13, November 12-18, 2005 [doi>10.1109/SC.2005.35]
• 22: Joel Saltz , Ravi Ponnusamy , Shamik D. Sharma , Bongki Moon , Yuan-Shin Hwang , Mustafa Uysal , Raja Das, A manual for the CHAOS runtime library, University of Maryland at College Park, College Park, MD, 1995
• 23: Sinha, A., And Kalé, L. 1993. A load balancing strategy for prioritized execution of tasks. In Seventh International Parallel Processing Symposium, 230--237.
• 24: Tuminaro, R. S., Heroux, M., Hutchinson, S. A., And Shadid, J. N. 1999. Official Aztec user's guide: Version 2.1. Tech. rep., Sandia National Laboratories.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Storage hierarchies

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies
      D.4.4 Communications Management
          Subjects: Input/output

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Hypergraphs
      G.2.3 Applications

General Terms:
Algorithms, Design, Management