SPM management using Markov chain based data access prediction

ABSTRACT

Leveraging the power of scratchpad memories (SPMs) available in most embedded systems today is crucial to extract maximum performance from application programs. While regular accesses like scalar values and array expressions with affine subscript functions have been tractable for compiler analysis (to be prefetched into SPM), irregular accesses like pointer accesses and indexed array accesses have not been easily amenable for compiler analysis. This paper presents an SPM management technique using Markov chain based data access prediction for such irregular accesses. Our approach takes advantage of inherent, but hidden reuse in data accesses made by irregular references. We have implemented our proposed approach using an optimizing compiler. In this paper, we also present a thorough comparison of our different dynamic prediction schemes with other SPM management schemes. SPM management using our approaches produces 12.7% to 28.5% improvements in performance across a range of applications with both regular and irregular access patterns, with an average improvement of 20.8%.

REFERENCES

• 1: Ilya Issenin , Erik Brockmeyer , Bart Durinck , Nikil Dutt, Multiprocessor system-on-chip data reuse analysis for exploring customized memory hierarchies, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1146925]
• 2: M. Kandemir , A. Choudhary, Compiler-directed scratch pad memory hierarchy design and management, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514077]
• 3: M. Kandemir , J. Ramanujam , J. Irwin , N. Vijaykrishnan , I. Kadayif , A. Parikh, Dynamic management of scratch-pad memory space, Proceedings of the 38th conference on Design automation, p.690-695, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379049]
• 4: Lian Li , Lin Gao , Jingling Xue, Memory Coloring: A Compiler Approach for Scratchpad Memory Management, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.329-338, September 17-21, 2005 [doi>10.1109/PACT.2005.27]
• 5: Nghi Nguyen , Angel Dominguez , Rajeev Barua, Scratch-pad memory allocation without compiler support for java applications, Proceedings of the 2007 international conference on Compilers, architecture, and synthesis for embedded systems, September 30-October 03, 2007, Salzburg, Austria [doi>10.1145/1289881.1289899]
• 6: Manish Verma , Stefan Steinke , Peter Marwedel, Data partitioning for maximal scratchpad usage, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119788]
• 7: Preeti Ranjan Panda , Nikil D. Dutt , Alexandru Nicolau, Efficient Utilization of Scratch-Pad Memory in Embedded Processor Applications, Proceedings of the 1997 European conference on Design and Test, p.7, March 17-20, 1997
• 8: Rajeshwari Banakar , Stefan Steinke , Bo-Sik Lee , M. Balakrishnan , Peter Marwedel, Scratchpad memory: design alternative for cache on-chip memory in embedded systems, Proceedings of the tenth international symposium on Hardware/software codesign, May 06-08, 2002, Estes Park, Colorado [doi>10.1145/774789.774805]
• 9: Bernhard Egger , Jaejin Lee , Heonshik Shin, Scratchpad memory management for portable systems with a memory management unit, Proceedings of the 6th ACM & IEEE International conference on Embedded software, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176887.1176933]
• 10: Bernhard Egger , Chihun Kim , Choonki Jang , Yoonsung Nam , Jaejin Lee , Sang Lyul Min, A dynamic code placement technique for scratchpad memory using postpass optimization, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176760.1176788]
• 11: Isabelle Puaut , Christophe Pais, Scratchpad memories vs locked caches in hard real-time systems: a quantitative comparison, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
• 12: Olga Golubeva , Mirko Loghi , Massimo Poncino , Enrico Macii, Architectural leakage-aware management of partitioned scratchpad memories, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
• 13: Angel Dominguez , Sumesh Udayakumaran , Rajeev Barua, Heap data allocation to scratch-pad memory in embedded systems, Journal of Embedded Computing, v.1 n.4, p.521-540, December 2005
• 14: N. Nguyenet al. "Memory allocation for embedded systems with a compile-time-unknown scratch-pad size," in CASES, 2005.
• 15: M. J. Absar , F. Catthoor, Compiler-Based Approach for Exploiting Scratch-Pad in Presence of Irregular Array Access, Proceedings of the conference on Design, Automation and Test in Europe, p.1162-1167, March 07-11, 2005 [doi>10.1109/DATE.2005.97]
• 16: G. Chen , O. Ozturk , M. Kandemir , M. Karakoy, Dynamic scratch-pad memory management for irregular array access patterns, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 17: Doosan Cho , Ilya Issenin , Nikil Dutt , Jonghee W. Yoon , Yunheung Paek, Software controlled memory layout reorganization for irregular array access patterns, Proceedings of the 2007 international conference on Compilers, architecture, and synthesis for embedded systems, September 30-October 03, 2007, Salzburg, Austria [doi>10.1145/1289881.1289915]
• 18: Ilya Issenin , Nikil Dutt, Data reuse driven energy-aware MPSoC co-synthesis of memory and communication architecture for streaming applications, Proceedings of the 4th international conference on Hardware/software codesign and system synthesis, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176254.1176326]
• 19: 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
• 20: V. Srinivasan et al. "A static filter for reducing prefetch traffic," in CSE-TR-400-99, UMich, 1999.
• 21: Mary W. Hall , Jennifer M. Anderson , Saman P. Amarasinghe , Brian R. Murphy , Shih-Wei Liao , Edouard Bugnion , Monica S. Lam, Maximizing Multiprocessor Performance with the SUIF Compiler, Computer, v.29 n.12, p.84-89, December 1996 [doi>10.1109/2.546613]
• 22: Todd Austin , Eric Larson , Dan Ernst, SimpleScalar: An Infrastructure for Computer System Modeling, Computer, v.35 n.2, p.59-67, February 2002 [doi>10.1109/2.982917]