Dynamic memory optimization using pool allocation and prefetching

ABSTRACT

Heap memory allocation plays an important role in modern applications. Conventional heap allocators, however, generally ignore the underlying memory hierarchy of the system, favoring instead a low runtime overhead and fast response times. Unfortunately, with little concern for the memory hierarchy, the data layout may exhibit poor spatial locality, and degrade cache performance. In this paper, we describe a dynamic heap allocation scheme called pool allocation. The strategy aims to improve cache performance by inspecting memory allocation requests, and allocating memory from appropriate heap pools as dictated by the requesting context. The advantages are two fold. First, by pooling together data with a common context, we expect to improve spatial locality, as data fetched to the caches will contain fewer items from different contexts. If the allocation patterns are closely matched to the traversal patterns, the end result is faster memory performance. Second, by pooling heap objects, we expect access patterns to exhibit more regularity, thus creating more opportunities for data prefetching. Our dynamic memory optimizer exploits the increased regularity to insert prefetch instructions at runtime. The optimizations are implemented in DynamoRIO, a dynamic optimization framework. We evaluate the work using various bench-marks, and measure a 17% speedup over gcc −03 on an Athlon MP, and a 13% speedup on a Pentium 4.

REFERENCES

• 1: S. G. Abraham and B. R. Rau. Predicting load latencies using cache profiling. Technical Report HPL-94-110, Hewlett Packard Labs, Dec 1994.
• 2: Derek L. Bruening , Saman Amarasinghe, Efficient, transparent, and comprehensive runtime code manipulation, Massachusetts Institute of Technology, Cambridge, MA, 2004
• 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: David Callahan , Ken Kennedy , Allan Porterfield, Software prefetching, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.40-52, April 08-11, 1991, Santa Clara, California, United States
• 5: M. Charney and A. Reeves. Generalized correlation-based hardware prefetching. Technical Report EE-CEG-95-1, Cornell University, Feb. 1995.
• 6: 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
• 7: Trishul M. Chilimbi , Martin Hirzel, Dynamic hot data stream prefetching for general-purpose programs, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 8: John W. C. Fu , Janak H. Patel , Bob L. Janssens, Stride directed prefetching in scalar processors, Proceedings of the 25th annual international symposium on Microarchitecture, p.102-110, December 01-04, 1992, Portland, Oregon, United States
• 9: Doug Joseph , Dirk Grunwald, Prefetching Using Markov Predictors, IEEE Transactions on Computers, v.48 n.2, p.121-133, February 1999 [doi>10.1109/12.752653]
• 10: 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]
• 11: Alexander C. Klaiber , Henry M. Levy, An architecture for software-controlled data prefetching, Proceedings of the 18th annual international symposium on Computer architecture, p.43-53, May 27-30, 1991, Toronto, Ontario, Canada
• 12: Chris Lattner , Vikram Adve, Automatic pool allocation: improving performance by controlling data structure layout in the heap, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 13: Jiwei Lu , Howard Chen , Rao Fu , Wei-Chung Hsu , Bobbie Othmer , Pen-Chung Yew , Dong-Yuan Chen, The Performance of Runtime Data Cache Prefetching in a Dynamic Optimization System, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.180, December 03-05, 2003
• 14: Todd C. Mowry , Monica S. Lam , Anoop Gupta, Design and evaluation of a compiler algorithm for prefetching, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.62-73, October 12-15, 1992, Boston, Massachusetts, United States
• 15: Toshihiro Ozawa , Yasunori Kimura , Shin'ichiro Nishizaki, Cache miss heuristics and preloading techniques for general-purpose programs, Proceedings of the 28th annual international symposium on Microarchitecture, p.243-248, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 16: Preeti Ranjan Panda , Nikil D. Dutt , Alexandru Nicolau, Memory data organization for improved cache performance in embedded processor applications, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.4, p.384-409, Oct. 1997 [doi>10.1145/268424.268464]
• 17: Rodric M. Rabbah , Hariharan Sandanagobalane , Mongkol Ekpanyapong , Weng-Fai Wong, Compiler orchestrated prefetching via speculation and predication, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 18: Rodric M. Rabbah , Krishna V. Palem, Data remapping for design space optimization of embedded memory systems, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.2, p.186-218, May 2003 [doi>10.1145/643470.643474]
• 19: Timothy Sherwood , Suleyman Sair , Brad Calder, Predictor-directed stream buffers, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.42-53, December 2000, Monterey, California, United States [doi>10.1145/360128.360135]
• 20: 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
• 21: Youfeng Wu, Efficient discovery of regular stride patterns in irregular programs and its use in compiler prefetching, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

General Terms:
Design, Performance