Locality phase prediction

ABSTRACT

As computer memory hierarchy becomes adaptive, its performance increasingly depends on forecasting the dynamic program locality. This paper presents a method that predicts the locality phases of a program by a combination of locality profiling and run-time prediction. By profiling a training input, it identifies locality phases by sifting through all accesses to all data elements using variable-distance sampling, wavelet filtering, and optimal phase partitioning. It then constructs a phase hierarchy through grammar compression. Finally, it inserts phase markers into the program using binary rewriting. When the instrumented program runs, it uses the first few executions of a phase to predict all its later executions.Compared with existing methods based on program code and execution intervals, locality phase prediction is unique because it uses locality profiles, and it marks phase boundaries in program code. The second half of the paper presents a comprehensive evaluation. It measures the accuracy and the coverage of the new technique and compares it with best known run-time methods. It measures its benefit in adaptive cache resizing and memory remapping. Finally, it compares the automatic analysis with manual phase marking. The results show that locality phase prediction is well suited for identifying large, recurring phases in complex programs.

REFERENCES

• 1: 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]
• 2: Rajeev Balasubramonian , David Albonesi , Alper Buyuktosunoglu , Sandhya Dwarkadas, Memory hierarchy reconfiguration for energy and performance in general-purpose processor architectures, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.245-257, December 2000, Monterey, California, United States [doi>10.1145/360128.360153]
• 3: Rajeev Balasubramonian , Sandhya Dwarkadas , David H. Albonesi, Dynamically managing the communication-parallelism trade-off in future clustered processors, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 4: A. P. Batson , A. W. Madison, Measurements of major locality phases in symbolic reference strings, Proceedings of the 1976 ACM SIGMETRICS conference on Computer performance modeling measurement and evaluation, p.75-84, March 29-31, 1976, Cambridge, Massachusetts, United States [doi>10.1145/800200.806184]
• 5: Trishul M. Chilimbi, Efficient representations and abstractions for quantifying and exploiting data reference locality, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.191-202, June 2001, Snowbird, Utah, United States
• 6: Raja Das , Mustafa Uysal , Joel Saltz , Yuan-Shin Hwang, Communication optimizations for irregular scientific computations on distributed memory architectures, Journal of Parallel and Distributed Computing, v.22 n.3, p.462-478, Sept. 1994 [doi>10.1006/jpdc.1994.1104]
• 7: Ingrid Daubechies, Ten lectures on wavelets, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 8: P.J. Denning. Working sets past and present. IEEE Transactions on Software Engineering, SE-6(1), January 1980.
• 9: Ashutosh S. Dhodapkar , James E. Smith, Managing multi-configuration hardware via dynamic working set analysis, Proceedings of the 29th annual international symposium on Computer architecture, p.233, May 25-29, 2002, Anchorage, Alaska
• 10: Ashutosh S. Dhodapkar , James E. Smith, Comparing Program Phase Detection Techniques, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.217, December 03-05, 2003
• 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 , 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
• 13: Evelyn Duesterwald , Calin Cascaval , Sandhya Dwarkadas, Characterizing and Predicting Program Behavior and its Variability, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.220, September 27-October 01, 2003
• 14: 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]
• 15: Hwansoo Han , Chau-Wen Tseng, Improving Locality for Adaptive Irregular Scientific Codes, Proceedings of the 13th International Workshop on Languages and Compilers for Parallel Computing-Revised Papers, p.173-188, August 10-12, 2000
• 16: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 17: Chung-Hsing Hsu , Ulrich Kremer, The design, implementation, and evaluation of a compiler algorithm for CPU energy reduction, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 18: Russ Joseph , Zhigang Hu , Margaret Martonosi, Wavelet Analysis for Microprocessor Design: Experiences with Wavelet-Based dI/dt Characterization, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.36, February 14-18, 2004 [doi>10.1109/HPCA.2004.10027]
• 19: James R. Larus, Whole program paths, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.259-269, May 01-04, 1999, Atlanta, Georgia, United States
• 20: Chi-Keung Luk , Todd C. Mowry, Memory forwarding: enabling aggressive layout optimizations by guaranteeing the safety of data relocation, Proceedings of the 26th annual international symposium on Computer architecture, p.88-99, May 01-04, 1999, Atlanta, Georgia, United States
• 21: Michael C. Huang , Jose Renau , Josep Torrellas, Positional adaptation of processors: application to energy reduction, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 22: Grigorios Magklis , Michael L. Scott , Greg Semeraro , David H. Albonesi , Steven Dropsho, Profile-based dynamic voltage and frequency scaling for a multiple clock domain microprocessor, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 23: 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
• 24: R. L. Mattson, J. Gecsei, D. Slutz, and I. L. Traiger. Evaluation techniques for storage hierarchies. IBM System Journal, 9(2):78--117, 1970.
• 25: 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]
• 26: C. G. Nevill-Manning and I. H. Witten. Identifying hierarchical structure in sequences: a linear-time algorithm. Journal of Artificial Intelligence Research, 7:67--82, 1997.
• 27: 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]
• 28: 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.
• 29: Timothy Sherwood , Erez Perelman , Brad Calder, Basic Block Distribution Analysis to Find Periodic Behavior and Simulation Points in Applications, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.3-14, September 08-12, 2001
• 30: Timothy Sherwood , Suleyman Sair , Brad Calder, Phase tracking and prediction, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 31: Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.196-205, June 20-24, 1994, Orlando, Florida, United States
• 32: 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
• 33: Rabin A. Sugumar , Santosh G. Abraham, Efficient simulation of caches under optimal replacement with applications to miss characterization, Proceedings of the 1993 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.24-35, May 10-14, 1993, Santa Clara, California, United States
• 34: Lixin Zhang , John B. Carter, Efficient remapping mechanisms for an adaptable memory system, 2002
• 35: Lixin Zhang , Zhen Fang , Mide Parker , Binu K. Mathew , Lambert Schaelicke , John B. Carter , Wilson C. Hsieh , Sally A. McKee, The Impulse Memory Controller, IEEE Transactions on Computers, v.50 n.11, p.1117-1132, November 2001 [doi>10.1109/12.966490]
• 36: Yutao Zhong , Maksim Orlovich , Xipeng Shen , Chen Ding, Array regrouping and structure splitting using whole-program reference affinity, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA

INDEX TERMS

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

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

General Terms:
Algorithms, Measurement, Performance

Keywords:
dynamic optimization, locality analysis and optimization, phase hierarchy, program phase analysis and prediction, reconfigurable architecture