The Potential of Computation Regrouping for Improving Locality

ABSTRACT

Improving program locality has become increasingly important on modern computer systems. An effective strategy is to group computations on the same data so that once the data are loaded into cache, the program performs all their operations before the data are evicted. However, computation regrouping is difficult to automate for programs with complex data and control structures. This paper studies the potential of locality improvement through trace-driven computation regrouping. First, it shows that maximizing the locality is different from maximizing the parallelism or maximizing the cache utilization. The problem is NP-hard even without considering data dependences and cache organization. Then the paper describes a tool that performs constrained computation regrouping on program traces. The new tool is unique because it measures the exact control dependences and applies complete memory renaming and re-allocation. Using the tool, the paper measures the potential locality improvement in a set of commonly used benchmark programs written in C.

REFERENCES

• 1: J. R. Allen , Ken Kennedy , Carrie Porterfield , Joe Warren, Conversion of control dependence to data dependence, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.177-189, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567085]
• 2: Ken Kennedy , John R. Allen, Optimizing compilers for modern architectures: a dependence-based approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 3: John Backus, The history of Fortran I, II, and III, History of programming languages I, ACM, New York, NY, 1978 [doi>10.1145/800025.1198345]
• 4: [4] L. A. Belady. A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal, 5(2):78-101, 1966.
• 5: Doug Burger , James R. Goodman , Alain Kägi, Memory bandwidth limitations of future microprocessors, Proceedings of the 23rd annual international symposium on Computer architecture, p.78-89, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 6: David Callahan , John Cocke , Ken Kennedy, Estimating interlock and improving balance for pipelined architectures, Journal of Parallel and Distributed Computing, v.5 n.4, p.334-358, August 1988 [doi>10.1016/0743-7315(88)90002-0]
• 7: Martin Christopher Carlisle, Olden: parallelizing programs with dynamic data structures on distributed-memory machines, Princeton University, Princeton, NJ, 1996
• 8: Steve Carr , Ken Kennedy, Blocking Linear Algebra Codes for Memory Hierarchies, Proceedings of the Fourth SIAM Conference on Parallel Processing for Scientific Computing, p.400-405, December 11-13, 1989
• 9: Michał Cierniak , Wei Li, Unifying data and control transformations for distributed shared-memory machines, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.205-217, June 18-21, 1995, La Jolla, California, United States
• 10: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 11: Chen Ding , Ken Kennedy, Improving cache performance in dynamic applications through data and computation reorganization at run time, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.229-241, May 01-04, 1999, Atlanta, Georgia, United States
• 12: Chen Ding , Ken Kennedy, Improving effective bandwidth through compiler enhancement of global cache reuse, Journal of Parallel and Distributed Computing, v.64 n.1, p.108-134, January 2004 [doi>10.1016/j.jpdc.2003.09.005]
• 13: Chen Ding , Yutao Zhong, Compiler-directed run-time monitoring of program data access, Proceedings of the 2002 workshop on Memory system performance, p.1-12, June 16-16, 2002, Berlin, Germany
• 14: Chen Ding , Yutao Zhong, Predicting whole-program locality through reuse distance analysis, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 15: Changpeng Fang , Steve Carr , Soner Önder , Zhenlin Wang, Reuse-distance-based miss-rate prediction on a per instruction basis, Proceedings of the 2004 workshop on Memory system performance, June 08-08, 2004, Washington, D.C. [doi>10.1145/1065895.1065906]
• 16: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 17: Guang R. Gao , R. Olsen , Vivek Sarkar , Radhika Thekkath, Collective Loop Fusion for Array Contraction, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.281-295, August 03-05, 1992
• 18: 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
• 19: [19] H. Han and C. W. Tseng. Locality optimizations for adaptive irregular scientific codes. Technical report, Department of Computer Science, University of Maryland, College Park, 2000.
• 20: Mark Donald Hill , Alan Jay Smith, Aspects of cache memory and instruction buffer performance, University of California, Berkeley, 1987
• 21: Andrew S. Huang , John Paul Shen, The intrinsic bandwidth requirements of ordinary programs, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.105-114, October 01-04, 1996, Cambridge, Massachusetts, United States
• 22: Ken Kennedy, Fast greedy weighted fusion, Proceedings of the 14th international conference on Supercomputing, p.131-140, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335244]
• 23: [23] K. Kennedy and K. S. McKinley. Typed fusion with applications to parallel and sequential code generation. Technical Report TR93-208, Dept. of Computer Science, Rice University, Aug. 1993. (also available as CRPC-TR94370).
• 24: 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
• 25: Monica S. Lam , Robert P. Wilson, Limits of control flow on parallelism, Proceedings of the 19th annual international symposium on Computer architecture, p.46-57, May 19-21, 1992, Queensland, Australia
• 26: Gabriel Marin , John Mellor-Crummey, Cross-architecture performance predictions for scientific applications using parameterized models, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 27: [27] R. L. Mattson, J. Gecsei, D. Slutz, and I. L. Traiger. Evaluation techniques for storage hierarchies. IBM System Journal, 9(2):78-117, 1970.
• 28: Kathryn S. McKinley , Olivier Temam, Quantifying loop nest locality using SPEC'95 and the perfect benchmarks, ACM Transactions on Computer Systems (TOCS), v.17 n.4, p.288-336, Nov. 1999 [doi>10.1145/329466.329484]
• 29: John Mellor-Crummey , Robert Fowler , David Whalley, Tools for application-oriented performance tuning, Proceedings of the 15th international conference on Supercomputing, p.154-165, June 2001, Sorrento, Italy [doi>10.1145/377792.377826]
• 30: John Mellor-Crummey , David Whalley , Ken Kennedy, Improving Memory Hierarchy Performance for Irregular Applications Using Data and Computation Reorderings, International Journal of Parallel Programming, v.29 n.3, p.217-247, June 2001 [doi>10.1023/A:1011119519789]
• 31: [31] A. Nicolau and J. A. Fisher. Measuring the parallelism available for very long instruction word architecture. IEEE Transactions on Computers, 33(11), 1984.
• 32: Venkata K. Pingali , Sally A. McKee , Wilson C. Hsieh , John B. Carter, Restructuring computations for temporal data cache locality, International Journal of Parallel Programming, v.31 n.4, p.305-338, August 2003 [doi>10.1023/A:1024556711058]
• 33: William Pugh , Evan Rosser, Iteration Space Slicing for Locality, Proceedings of the 12th International Workshop on Languages and Compilers for Parallel Computing, p.164-184, August 04-06, 1999
• 34: [34] X. Shen, Y. Zhong, and C. Ding. Regression-based multi-model prediction of data reuse signature. In Proceedings of the 4th Annual Symposium of the Las Alamos Computer Science Institute, Sante Fe, New Mexico, November 2003.
• 35: Yonghong Song , Zhiyuan Li, New tiling techniques to improve cache temporal locality, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.215-228, May 01-04, 1999, Atlanta, Georgia, United States
• 36: Michelle Mills Strout , Larry Carter , Jeanne Ferrante, Compile-time composition of run-time data and iteration reorderings, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 37: Michelle Mills Strout , Paul D. Hovland, Metrics and models for reordering transformations, Proceedings of the 2004 workshop on Memory system performance, June 08-08, 2004, Washington, D.C. [doi>10.1145/1065895.1065899]
• 38: [38] K. B. Theobald, G. R. Gao, and L. J. Hendren. On the limits of program parallelism and its smoothability. Technical Report ACAPS Memo 40, School of Computer Science, McGill University, June 1992.
• 39: Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada
• 40: David Wonnacott, Achieving Scalable Locality with Time Skewing, International Journal of Parallel Programming, v.30 n.3, p.181-221, June 2002 [doi>10.1023/A:1015460304860]
• 41: Qing Yi , Vikram Adve , Ken Kennedy, Transforming loops to recursion for multi-level memory hierarchies, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.169-181, June 18-21, 2000, Vancouver, British Columbia, Canada
• 42: Xiangyu Zhang , Rajiv Gupta, Cost effective dynamic program slicing, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 43: [43] Y. Zhong, C. Ding, and K. Kennedy. Reuse distance analysis for scientific programs. In Proceedings of Workshop on Languages, Compilers, and Run-time Systems for Scalable Computers, Washington DC, March 2002.
• 44: Yutao Zhong , Steven G. Dropsho , Chen Ding, Miss Rate Prediction across All Program Inputs, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.79, September 27-October 01, 2003