An efficient profile-analysis framework for data-layout optimizations

ABSTRACT

Data-layout optimizations rearrange fields within objects, objects within objects, and objects within the heap, with the goal of increasing spatial locality. While the importance of data-layout optimizations has been growing, their deployment has been limited, partly because they lack a unifying framework. We propose a parameterizable framework for data-layout optimization of general-purpose applications. Acknowledging that finding an optimal layout is not only NP-hard, but also poorly approximable, our framework finds a good layout by searching the space of possible layouts, with the help of profile feedback. The search process iteratively prototypes candidate data layouts, evaluating them by "simulating" the program on a representative trace of memory accesses. To make the search process practical, we develop space-reduction heuristics and optimize the expensive simulation via memoization. Equipped with this iterative approach, we can synthesize layouts that outperform existing non-iterative heuristics, tune application-specific memory allocators, as well as compose multiple data-layout optimizations.

REFERENCES

• 1: Martin Alt , Christian Ferdinand , Florian Martin , Reinhard Wilhelm, Cache Behavior Prediction by Abstract Interpretation, Proceedings of the Third International Symposium on Static Analysis, p.52-66, September 24-26, 1996
• 2: David A. Barrett , Benjamin G. Zorn, Using lifetime predictors to improve memory allocation performance, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.187-196, June 21-25, 1993, Albuquerque, New Mexico, United States
• 3: Brad Calder , Chandra Krintz , Simmi John , Todd Austin, Cache-conscious data placement, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.139-149, October 02-07, 1998, San Jose, California, United States
• 4: Steve Carr , Kathryn S. McKinley , Chau-Wen Tseng, Compiler optimizations for improving data locality, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.252-262, October 05-07, 1994, San Jose, California, United States
• 5: Siddhartha Chatterjee , Erin Parker , Philip J. Hanlon , Alvin R. Lebeck, Exact analysis of the cache behavior of nested loops, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.286-297, June 2001, Snowbird, Utah, United States
• 6: 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
• 7: Trishul M. Chilimbi , Bob Davidson , James R. Larus, Cache-conscious structure definition, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.13-24, May 01-04, 1999, Atlanta, Georgia, United States
• 8: Trishul M. Chilimbi , Mark D. Hill , James R. Larus, Cache-conscious structure layout, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.1-12, May 01-04, 1999, Atlanta, Georgia, United States
• 9: Trishul M. Chilimbi , James R. Larus, Using generational garbage collection to implement cache-conscious data placement, Proceedings of the 1st international symposium on Memory management, p.37-48, October 17-19, 1998, Vancouver, British Columbia, Canada
• 10: Peter J. Denning , Stuart C. Schwartz, Properties of the working-set model, Communications of the ACM, v.15 n.3, p.191-198, March 1972 [doi>10.1145/361268.361281]
• 11: Julian Dolby , Andrew Chien, An automatic object inlining optimization and its evaluation, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.345-357, June 18-21, 2000, Vancouver, British Columbia, Canada
• 12: Shantanu Dutt, New faster Kernighan-Lin-type graph-partitioning algorithms, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.370-377, November 07-11, 1993, Santa Clara, California, United States
• 13: FERDINAND,C.,AND WILHELM, R. Fast and efficient cache behavior prediction.
• 14: Dennis Gannon , William Jalby , Kyle Gallivan, Strategies for cache and local memory management by global program transformation, Journal of Parallel and Distributed Computing, v.5 n.5, p.587-616, October 1988 [doi>10.1016/0743-7315(88)90014-7]
• 15: Thomas Kistler , Michael Franz, Automated data-member layout of heap objects to improve memory-hierarchy performance, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.3, p.490-505, May 2000 [doi>10.1145/353926.353937]
• 16: Anthony LaMarca , Richard Ladner, The influence of caches on the performance of heaps, Journal of Experimental Algorithmics (JEA), 1, p.4-es, 1996 [doi>10.1145/235141.235145]
• 17: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 18: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 19: David A. Patterson , John L. Hennessy, Computer organization & design: the hardware/software interface, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 20: Erez Petrank , Dror Rawitz, The hardness of cache conscious data placement, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.101-112, January 16-18, 2002, Portland, Oregon
• 21: Shai Rubin , David Bernstein , Michael Rodeh, Virtual Cache Line: A New Technique to Improve Cache Exploitation for Recursive Data Structures, Proceedings of the 8th International Conference on Compiler Construction, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS'99, p.259-273, March 22-28, 1999
• 22: Mooly Sagiv , Thomas Reps , Reinhard Wilhelm, Parametric shape analysis via 3-valued logic, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.105-118, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292552]
• 23: Matthew L. Seidl , Benjamin G. Zorn, Segregating heap objects by reference behavior and lifetime, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.12-23, October 02-07, 1998, San Jose, California, United States
• 24: D. N. Truong , F. Bodin , A. Seznec, Improving Cache Behavior of Dynamically Allocated Data Structures, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.322, October 12-18, 1998
• 25: VAN DER WAL, R. Programmer's toolchest: Source-code profilers for Win32. Dr. Dobb's Journal of Software Tools 23,3 (Mar. 1998), 78, 80, 82-88.
• 26: 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