A novel instruction scratchpad memory optimization method based on concomitance metric

ABSTRACT

Scratchpad memory has been introduced as a replacement for cache memory as it improves the performance of certain embedded systems. Additionally, it has also been demonstrated that scratchpad memory can significantly reduce the energy consumption of the memory hierarchy of embedded systems. This is significant, as the memory hierarchy consumes a substantial proportion of the total energy of an embedded system. This paper deals with optimization of the instruction memory scratchpad based on a novel methodology that uses a metric which we call the concomitance. This metric is used to find basic blocks which are executed frequently and in close proximity in time. Once such blocks are found, they are copied into the scratchpad memory at appropriate times; this is achieved using a special instruction inserted into the code at appropriate places. For a set of benchmarks taken from Mediabench, our scratchpad system consumed just 59% (avg) of the energy of the cache system, and 73% (avg) of the energy of the state of the art scratchpad system, while improving the overall performance. Compared to the state of the art method, the number of instructions copied into the scratchpad memory from the main memory is reduced by 88%.

REFERENCES

• 1: J. Montanaro et al., "A 160MHz, 32b, 0.5W CMOS RISC microprocessor," JSSC, vol.31 (11), pp. 1703--1712, 1996.
• 2: 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]
• 3: 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]
• 4: 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
• 5: 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]
• 6: 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]
• 7: Federico Angiolini , Luca Benini , Alberto Caprara, Polynomial-time algorithm for on-chip scratchpad memory partitioning, 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.951751]
• 8: 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]
• 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: Stefan Steinke , Nils Grunwald , Lars Wehmeyer , Rajeshwari Banakar , M. Balakrishnan , Peter Marwedel, Reducing energy consumption by dynamic copying of instructions onto onchip memory, Proceedings of the 15th international symposium on System Synthesis, October 02-04, 2002, Kyoto, Japan [doi>10.1145/581199.581247]
• 11: Andhi Janapsatya , Sri Parameswaran , A. Ignjatovic, Hardware/software managed scratchpad memory for embedded system, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.370-377, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382603]
• 12: G. Ramalingam, On loops, dominators, and dominance frontier, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.233-241, June 18-21, 2000, Vancouver, British Columbia, Canada
• 13: Paul Havlak, Nesting of reducible and irreducible loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.4, p.557-567, July 1997 [doi>10.1145/262004.262005]
• 14: Vugranam C. Sreedhar , Guang R. Gao , Yong-Fong Lee, Identifying loops using DJ graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.6, p.649-658, Nov. 1996 [doi>10.1145/236114.236115]
• 15: B. Steensgaard, "Sequentializing Program Dependence Graphs for Irreducible Programs," Technical Report MSR_TR-93-14, Microsoft Research, Redmond, Washington, October 1993.
• 16: Nikolas Gloy , Michael D. Smith, Procedure placement using temporal-ordering information, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.5, p.977-1027, Sept. 1999 [doi>10.1145/330249.330254]
• 17: Peter Grun , Nikil Dutt , Alex Nicolau, Access pattern-based memory and connectivity architecture exploration, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.1, p.33-73, February 2003 [doi>10.1145/605459.605462]
• 18: Anand Ramachandran , Margarida F. Jacome, Xtream-Fit: an energy-delay efficient data memory subsystem for embedded media processing, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775869]
• 19: 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]
• 20: Mahmut Kandemir , Ismail Kadayif , Ugur Sezer, Exploiting scratch-pad memory using Presburger formulas, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500004]
• 21: Sri Parameswaran , Jörg Henkel, I-CoPES: fast instruction code placement for embedded systems to improve performance and energy efficiency, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 22: Pohua P. Chang , Scott A. Mahlke , William Y. Chen , Nancy J. Warter , Wen-mei W. Hwu, IMPACT: an architectural framework for multiple-instruction-issue processors, ACM SIGARCH Computer Architecture News, v.19 n.3, p.266-275, May 1991
• 23: S. McFarling, Program optimization for instruction caches, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.183-191, April 03-06, 1989, Boston, Massachusetts, United States
• 24: Scott McFarling, Procedure merging with instruction caches, ACM SIGPLAN Notices, v.26 n.6, p.71-79, June 1991
• 25: Preeti Ranjan Panda , Nikil D. Dutt , Alexandru Nicolau, Memory Organization for Improved Data Cache Performance in Embedded Processors, Proceedings of the 9th international symposium on System synthesis, p.90, November 06-08, 1996
• 26: P. Panda and et.al., "A Data Alignment Technique for Improving Cache Performance," ICCD, 1997.
• 27: Hiroyuki Tomiyama , Hiroto Yasuura, Optimal Code Placement of Embedded Software for Instruction Caches, Proceedings of the 1996 European conference on Design and Test, p.96, March 11-14, 1996
• 28: S. Bartolini and C. A. Prete, "A cache-aware program transformation technique suitable for embedded systems," Information and Software Technology 44(13), 2002.
• 29: D. Burger and T. M. Austin, "The SimpleScalar Tool Set, Version 2.0," TR-CS-1342, University of Wisconsin-madison, June 1997.
• 30: J. Edler and M. D. Hill, "Dinero IV Trace-Driven Uniprocessor Cache Simulator," http://www.cs.wisc.edu/markhill/DineroIV/.
• 31: David Brooks , Vivek Tiwari , Margaret Martonosi, Wattch: a framework for architectural-level power analysis and optimizations, Proceedings of the 27th annual international symposium on Computer architecture, p.83-94, June 2000, Vancouver, British Columbia, Canada
• 32: P. Shivakumar and N. P. Jouppi, "Cacti 3.0: An Integrated Cache Timing, Power, and Area Model," Technical Report 2001/2, Compaq Computer Corporation, August, 2001. 2001.
• 33: IBM Microelectronics Division, "Embedded DRAM SA-27E," http://ibm.com/chips, 2002.
• 34: 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

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Memory technologies

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids
  B.m MISCELLANEOUS
      Subjects: Design management

General Terms:
Design, Performance