Software controlled memory layout reorganization for irregular array access patterns

ABSTRACT

Many embedded array-intensive applications have irregular access patterns that are not amenable to static analysis for extraction of access patterns, and thus prevent efficient use of a Scratch Pad Memory (SPM) hierarchy for performance and power improvement. We present a profiling based strategy that generates a memory access trace which can be used to identify data elements with fine granularity that can profitably be placed in the SPMs to maximize performance and energy gains. We developed an entire toolchain that allows incorporation of the code required to profitably move data to SPMs; visualization of the extracted access pattern after profiling; and evaluation/exploration of the generated application code to steer mapping of data to the SPM to yield performance and energy benefits.We present a heuristic approach that efficiently exploits the SPM using the profiler-driven access pattern behaviors. Experimental results on EEMBC and other industrial codes obtained with our framework show that we are able to achieve 36% energy reduction and reduce execution time by up to 22% compared to a cache based system.

REFERENCES

• 1: 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]
• 2: Oren Avissar , Rajeev Barua , Dave Stewart, An optimal memory allocation scheme for scratch-pad-based embedded systems, ACM Transactions on Embedded Computing Systems (TECS), v.1 n.1, p.6-26, November 2002 [doi>10.1145/581888.581891]
• 3: 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]
• 4: D. Burger and T. M. Austin. The SimpleScalar tool set, version 2.0. InTechnical Report 1342, University of Wisconsin-Madison, CS Department, June 1997.
• 5: David F. Bacon , Susan L. Graham , Oliver J. Sharp, Compiler transformations for high-performance computing, ACM Computing Surveys (CSUR), v.26 n.4, p.345-420, Dec. 1994 [doi>10.1145/197405.197406]
• 6: 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
• 7: M. Co, Dee A. B. Weikle, and K. Skadron A Break-Even Formulation for Evaluating Branch Predictor Energy Efficiency. In Proceedings of Complexity-Effective Design, 2005.
• 8: Keith D. Cooper , Timothy J. Harvey, Compiler-controlled memory, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.2-11, October 02-07, 1998, San Jose, California, United States
• 9: 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
• 10: Ariel Felner , Sarit Kraus , Richard E. Korf, KBFS: K-Best-First Search, Annals of Mathematics and Artificial Intelligence, v.39 n.1-2, p.19-39, September 2003 [doi>10.1023/A:1024452529781]
• 11: Dorit S. Hochbaum , David B. Shmoys, A unified approach to approximation algorithms for bottleneck problems, Journal of the ACM (JACM), v.33 n.3, p.533-550, July 1986 [doi>10.1145/5925.5933]
• 12: I. Issenin, and N. Dutt. Data Reuse Driven Memory and Network-on-Chip Co-Synthesis. In Proceedings of IESS, 2007.
• 13: 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]
• 14: 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]
• 15: Ilya Issenin , Erik Brockmeyer , Miguel Miranda , Nikil Dutt, Data Reuse Analysis Technique for Software-Controlled Memory Hierarchies, Proceedings of the conference on Design, automation and test in Europe, p.10202, February 16-20, 2004
• 16: 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]
• 17: 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]
• 18: S. Lin, D. Costello. Error Control Coding: Fundamentals and Applications. Book, Practice Hall, October 1982.
• 19: Kathryn S. McKinley , Steve Carr , Chau-Wen Tseng, Improving data locality with loop transformations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.424-453, July 1996 [doi>10.1145/233561.233564]
• 20: M. Palkovic , M. Miranda , K. Denolf , P. Vos , F. Catthoor, Systematic Address and Control Code Transformations for Performance Optimisation of a MPEG-4 Video Decoder, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.547, January 07-11, 2002
• 21: Yunheung Paek , Jay Hoeflinger , David Padua, Simplification of array access patterns for compiler optimizations, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.60-71, June 17-19, 1998, Montreal, Quebec, Canada
• 22: 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
• 23: S. Steinke , L. Wehmeyer , B. Lee , P. Marwedel, Assigning Program and Data Objects to Scratchpad for Energy Reduction, Proceedings of the conference on Design, automation and test in Europe, p.409, March 04-08, 2002
• 24: P. Shivakumar, N. Jouppi. CACTI 3.0: An Integrated Cache Timing, Power, and Area Model. WRL Technical Report, August 2001.
• 25: Jan Sjödin , Carl von Platen, Storage allocation for embedded processors, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA [doi>10.1145/502217.502221]
• 26: Sumesh Udayakumaran , Rajeev Barua, Compiler-decided dynamic memory allocation for scratch-pad based embedded systems, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951747]
• 27: Manish Verma , Lars Wehmeyer , Peter Marwedel, Dynamic overlay of scratchpad memory for energy minimization, Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 08-10, 2004, Stockholm, Sweden [doi>10.1145/1016720.1016748]
• 28: 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]
• 29: EDN Embedded Microprocessor Benchmark Consortium, www.eembc.org.
• 30: Intel Corporation, http://developer.intel.com/design/intelxscale/index.htm.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Dynamic storage management

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

General Terms:
Languages, Management

Keywords:
data layout, energy consumption, scratch pad memory