Performance driven data cache prefetching in a dynamic software optimization system

ABSTRACT

Software or hardware data cache prefetching is an efficient way to hide cache miss latency. However effectiveness of the issued prefetches have to be monitored in order to maximize their positive impact while minimizing their negative impact on performance. In previous proposed dynamic frameworks, the monitoring scheme is either achieved using processor performance counters or using specific hardware. In this work, we propose a prefetching strategy which does not use any specific hardware component or processor performance counter. Our dynamic framework wants to be portable on any modern processor architecture providing at least a prefetch instruction. Opportunity and effectiveness of prefetching loads is simply guided by the time spent to effectively obtain the data. Every load of a program is monitored periodically and can be either associated to a dynamically inserted prefetch instruction or not. It can be associated to a prefetch instruction at some disjoint periods of the whole program run as soon as it is efficient. Our framework has been implemented for Itanium-2 machines. It involves several dynamic instrumentations of the binary code whose overhead is limited to only 4% on average. On a large set of benchmarks, our system is able to speed up some programs by 2%--143%.

REFERENCES

• 1: The Olden benchmark suite. http://www.cs.princeton.edu/~mcc/olden.html.
• 2: Pointer-intensive benchmark suite. http://www.cs.wisc.edu/~austin/ptr-dist.html.
• 3: Vasanth Bala , Evelyn Duesterwald , Sanjeev Banerjia, Dynamo: a transparent dynamic optimization system, ACM SIGPLAN Notices, v.35 n.5, p.1-12, May 2000
• 4: Derek Bruening , Timothy Garnett , Saman Amarasinghe, An infrastructure for adaptive dynamic optimization, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 5: 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
• 6: Michał Cierniak , Guei-Yuan Lueh , James M. Stichnoth, Practicing JUDO: Java under dynamic optimizations, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.13-26, June 18-21, 2000, Vancouver, British Columbia, Canada
• 7: A. Das, R. Fu, A. Zhai, and W.-C. Hsu. Issues and support for dynamic register allocation. In Asia-Pacific Computer Systems Architecture Conference, pages 351--358, 2006.
• 8: Giuseppe Desoli , Nikolay Mateev , Evelyn Duesterwald , Paolo Faraboschi , Joseph A. Fisher, DELI: a new run-time control point, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 9: Philip G. Emma , Allan Hartstein , Thomas R. Puzak , Vijayalakshmi Srinivasan, Exploring the limits of prefetching, IBM Journal of Research and Development, v.49 n.1, p.127-144, January 2005
• 10: Ando Ki , Alan E. Knowles, Adaptive data prefetching using cache information, Proceedings of the 11th international conference on Supercomputing, p.204-212, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263633]
• 11: 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
• 12: J. Lu, H. Chen, P.-C. Yew, and W.-C. Hsu. Design and implementation of a lightweight dynamic optimization system. J. Instruction-Level Parallelism, 6, 2004.
• 13: Chi-Keung Luk , Robert Muth , Harish Patil , Robert Cohn , Geoff Lowney, Ispike: A Post-link Optimizer for the Intel®Itanium®Architecture, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.15, March 20-24, 2004, Palo Alto, California
• 14: SPEC CPU2000. http://www.spec.org/cpu2000/.
• 15: S. Srinath, O. M. H. Kim,, and Y. N. Patt. Feedback directed prefetching: Improving the performance and bandwidth-efficiency of hardware prefetchers. In Proc. of the 13th Int. Symp. on High-Performance Computer Architecture (HPCA), Feb. 2007.
• 16: A. Srivastava, A. Edwards, and H. Vo. Vulcan: Binary Transformation in a Distributed Environment. Technical Report MSR-TR-2001-50, 2001.
• 17: Toshio Suganuma , Toshiaki Yasue , Motohiro Kawahito , Hideaki Komatsu , Toshio Nakatani, Design and evaluation of dynamic optimizations for a Java just-in-time compiler, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.4, p.732-785, July 2005 [doi>10.1145/1075382.1075386]
• 18: Steven P. Vanderwiel , David J. Lilja, Data prefetch mechanisms, ACM Computing Surveys (CSUR), v.32 n.2, p.174-199, June 2000 [doi>10.1145/358923.358939]
• 19: Weifeng Zhang , Brad Calder , Dean M. Tullsen, An Event-Driven Multithreaded Dynamic Optimization Framework, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.87-98, September 17-21, 2005 [doi>10.1109/PACT.2005.7]
• 20: Weifeng Zhang , Brad Calder , Dean M. Tullsen, A Self-Repairing Prefetcher in an Event-Driven Dynamic Optimization Framework, Proceedings of the International Symposium on Code Generation and Optimization, p.50-64, March 26-29, 2006 [doi>10.1109/CGO.2006.4]
• 21: Q. Zhao, R. Rabbah, S. Amarasinghe, L. Rudolph, and W.-F. Wong. Ubiquitous memory introspection. In CGO '07: Proceedings of the International Symposium on Code Generation and Optimization, Washington, DC, USA, March 2007. IEEE Computer Society.
• 22: Qin Zhao , Rodric Rabbah , Weng-Fai Wong, Dynamic memory optimization using pool allocation and prefetching, ACM SIGARCH Computer Architecture News, v.33 n.5, December 2005 [doi>10.1145/1127577.1127584]

INDEX TERMS

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

General Terms:
Performance

Keywords:
binary instrumentation, data cache prefetching, dynamic optimization