Manish Verma
ABSTRACT
The memory subsystem accounts for a significant portion of the aggregate energy budget of contemporary embedded systems. Moreover, there exists a large potential for optimizing the energy consumption of the memory subsystem. Consequently, novel memories as well as novel algorithms for their efficient utilization are being designed. Scratchpads are known to perform better than caches in terms of power, performance, area and predictability. However, unlike caches they depend upon software allocation techniques for their utilization. In this paper, we present an allocation technique which analyzes the application and inserts instructions to dynamically copy both code segments and variables onto the scratchpad at runtime. We demonstrate that the problem of dynamically overlaying scratchpad is an extension of the Global Register Allocation problem. The overlay problem is solved optimally using ILP formulation techniques. Our approach improves upon the only previously known allocation technique for statically allocating both variables and code segments onto the scratchpad. Experiments report an average reduction of 34% and 18% in the energy consumption and the runtime of the applications, respectively. A minimal increase in code size is also reported.
- A. W. Appel and L. George. Optimal spilling for cisc machines with few registers. In Proc. of the Conference on Programming Language Design and Implementation (PLDI), pages 243--253, Snowbird, Utah, USA, 2001. Google Scholar
Digital Library
- ARM. Advanced RISC Machines Ltd. http://www.arm.com.Google Scholar
- O. Avissar, R. Barua, and D. Stewart. An Optimal Memory Allocation Scheme for Scratch-Pad-Based Embedded Systems. IEEE Transactions on Embedded Computing Systems, 1(1):6--26, November 2002. Google ScholarDigital Library
- R. Banakar, S. Steinke, B.-S. Lee, M. Balakrishnan, and P. Marwedel. Scratchpad Memory: A Design Alternative for Cache On-chip Memory in Embedded Systems. In Proc. of 10th International Symposium on Hardware/Software Codesign, Colorado, USA, May 2002. Google ScholarDigital Library
- G. J. Chaitin. Register allocation & spilling via graph coloring. In Proc. of the 1982 SIGPLAN Symposium on Compiler Construction, pages 98--101, Boston, Massachusetts, USA, 1982. Google ScholarDigital Library
- CPLEX. CPLEX limited. http://www.cplex.com.Google Scholar
- M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide To the Theory of NP-Completeness. Freeman, New York, USA, 1979. Google ScholarDigital Library
- D. W. Goodwin and K. D. Wilken. Optimal and Near-optimal Global Register Allocation Using 0-1 Integer Programming. Software-Practice and Experience, 26(8):929--965, August 1996. Google ScholarDigital Library
- J. L. Hennessy and D. A. Patterson. Computer Architecture : A Quantitative Approach; second edition. Morgan Kaufmann, 1996. Google ScholarDigital Library
- M. Kandemir, I. Kadayif, and U. Sezer. Exploiting Scratch-Pad Memory Using Presburger Formulas. In Proc. of the 14th International Symposium on System Synthesis (ISSS), pages 7--12, Montreal, P.Q., Canada, 2001. Google ScholarDigital Library
- T. Kong and K. D. Wilken. Precise register allocation for irregular architectures. In Proc. of the 31st annual ACM/IEEE International Symposium on Microarchitecture, Dallas, TX, USA, 1998. Google ScholarDigital Library
- MediabenchII. Benchmark Suite for Multimedia and Communication Systems. http://cares.icsl.ucla.edu/MediaBenchII/.Google Scholar
- S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, San Francisco, California, 1. edition, 1997. Google ScholarDigital Library
- P. R. Panda, N. D. Dutt, and A. Nicolau. Memory Issues in Embedded Systems-On-Chip. Kluwer Academic Publishers, Norwell, MA, 1999. Google ScholarDigital Library
- S. Steinke, N. Grunwald, L. Wehmeyer, R. Banakar, M. Balakrishnan, and P. Marwedel. Reducing Energy Consumption by Dynamic Copying of Instructions onto Onchip Memory. In Proc. of the 15th International Symposium on System Synthesis (ISSS), Kyoto Japan, October 2002. Google ScholarDigital Library
- S. Steinke, M. Knauer, L. Wehmeyer, and P. Marwedel. An Accurate and Fine Grain Instruction-Level Energy Model Supporting Software Optimizations. In Proc. of International Workshop on Power And Timing Modeling, Optimization and Simulation PATMOS, Yverdon-Les-Bains, Switzerland, Sep. 2001.Google Scholar
- S. Steinke, L. Wehmeyer, B. S. Lee, and P. Marwedel. Assigning program and data objects to scratchpad for energy reduction. In Proc. of Design Automation and Test in Europe (DATE), Paris France, March 2002. Google ScholarDigital Library
- H. Tomiyama and H. Yasuura. Optimal code placement of embedded software for instruction caches. In Proc. of the 9th European Design and Test Conference, Paris France, March 1996. ET&TC. Google ScholarDigital Library
- M. Verma, S. Steinke, and P. Marwedel. Data Partitioning for Maximal Scratchpad Usage. In Proc. of the Asia and South Pacific Design Automation Conference (ASPDAC), page 77, January 2003. Google ScholarDigital Library
- M. Verma, L. Wehmeyer, and P. Marwedel. Cache-aware Scratchpad Allocation Algorihm. In Proc. of Design, Automation and Test in Europe (DATE), February 2004. Google ScholarDigital Library
Index Terms
- Dynamic overlay of scratchpad memory for energy minimization
Recommendations
Scratchpad memory management for portable systems with a memory management unit
EMSOFT '06: Proceedings of the 6th ACM & IEEE International conference on Embedded softwareIn this paper,we present a dynamic scratchpad memory allocation strategy targeting a horizontally partitioned memory subsystem for contemporary embedded processors. The memory subsystem is equipped with a memory management unit (MMU), and physically ...
Dynamic Overlay of Scratchpad Memory for Energy Minimization
CODES+ISSS '04: Proceedings of the international conference on Hardware/Software Codesign and System Synthesis: 2004The memory subsystem accounts for a significant portion of the aggregate energy budget of contemporary embedded systems. Moreover, there exists a large potential for optimizing the energy consumption of the memory subsystem. Consequently, novel memories ...
Dynamic scratchpad memory management for code in portable systems with an MMU
In this work, we present a dynamic memory allocation technique for a novel, horizontally partitioned memory subsystem targeting contemporary embedded processors with a memory management unit (MMU). We propose to replace the on-chip instruction cache ...
Comments