Compiler driven data layout optimization for regular/irregular array access patterns

ABSTRACT

Embedded multimedia applications consist of regular and irregular memory access patterns. Particularly, irregular pattern 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 energy improvements. To resolve this, we present a compiler strategy to optimize data layout in regular/irregular multimedia applications running on embedded multiprocessor environments. The goal is to maximize the amount of accesses to the SPM over the entire system which leads to a reduction in the energy consumption of the system. This is achieved by optimizing data placement of application-wide reused data so that it resides in the SPMs of processing elements. Specifically, our scheme is based on a profiling that generates a memory access footprint. The memory access footprint is used to identify data elements with fine granularity that can profitably be placed in the SPMs to maximize performance and energy gains. We present a heuristic approach that efficiently exploits the SPMs using memory access footprint. Our experimental results show that our approach is able to reduce energy consumption by 30% and improve performance by 18% over cache based memory subsystems for various multimedia applications.

REFERENCES

• 1: 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]
• 2: 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]
• 3: 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]
• 4: 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]
• 5: 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]
• 6: 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]
• 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: 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]
• 9: 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
• 10: 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]
• 11: 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
• 12: Ilya Issenin , Erik Brockmeyer , Miguel Miranda , Nikil Dutt, DRDU: A data reuse analysis technique for efficient scratch-pad memory management, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.12 n.2, p.15-es, April 2007 [doi>10.1145/1230800.1230807]
• 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: 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]
• 15: Samy Meftali , Ferid Gharsalli , Frederic Rousseau , Ahmed A. Jerraya, An optimal memory allocation for application-specific multiprocessor system-on-chip, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500006]
• 16: M. Kandemir and N. Dutt, Memory Systems and Compiler Support for MPSoC Architectures. Morgan Kaufmann, 2005.
• 17: 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]
• 18: 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]
• 19: 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]
• 20: 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
• 21: "Arm advanced micro bus architecture (amba)," ARM. {Online}. Available: http://www.arm.com/products/solutions/AMBAHomePage.html
• 22: "Sonics, integration architectures." {Online}. Available: http://www.sonicsinc.com
• 23: Michael Gschwind , H. Peter Hofstee , Brian Flachs , Martin Hopkins , Yukio Watanabe , Takeshi Yamazaki, Synergistic Processing in Cell's Multicore Architecture, IEEE Micro, v.26 n.2, p.10-24, March 2006 [doi>10.1109/MM.2006.41]
• 24: W. J. S. H. Yongjoo Kim, Seongnam Kwon and Y. Paek, "An openmp translator with retargetable parallel programming model for mpsoc," in Proc. of Intl. Conf. on Ubiquitous Information Technologies and Applications, 2007.
• 25: Youfeng Wu, Efficient discovery of regular stride patterns in irregular programs and its use in compiler prefetching, ACM SIGPLAN Notices, v.37 n.5, May 2002
• 26: 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]
• 27: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 28: D. C. Burger and T. M. Austin, "The simplescalar tool set, version 2.0," Tech. Rep. CS-TR-1997-1342, 1997.
• 29: P. Shivakumar and N. P. Jouppi, "Cacti 3.0: An integrated cache timing, power, and area model."
• 30: "128 mbit micron mobile sdram data sheet." Micron Technology Incorporated. {Online}. Available: http://www.micron.com
• 31: Luca Benini , Alberto Macii , Enrico Macii , Massimo Poncino, Increasing Energy Efficiency of Embedded Systems by Application-Specific Memory Hierarchy Generation, IEEE Design & Test, v.17 n.2, p.74-85, April 2000 [doi>10.1109/54.844336]

INDEX TERMS

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

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

Keywords:
compiler, data placement, energy consumption, memory hierarchy