Direct address translation for virtual memory in energy-efficient embedded systems

ABSTRACT

This article presents a methodology for virtual memory support in energy-efficient embedded systems. A holistic approach is proposed, where the combined efforts of compiler, operating system, and hardware architecture achieve a significant system power reductions. The application information extracted and analyzed by the compiler is utilized dynamically by the microarchitecture and the operating system to perform energy-efficient and, for many memory references, time-deterministic address translations. We demonstrate that by using application information regarding virtual memory layout, an efficient and conflict-free translation process can be implemented through the utilization of a small hardware direct translation table (DTT) accessed in an application-specific manner. The set of virtual pages is partitioned into groups, such that for each group only a few of the least significant bits are used as an index to obtain the physical page number. We outline an efficient compile-time algorithm for identifying these groups and allocate their translation entries optimally into the DTT. The introduced hardware is minimal in terms of area, performance, and power overhead, while offering the flexibility of software programmability. This is achieved through a small set of registers and tables, which are made software accessible. We have quantitatively evaluated the proposed methodology on a number of embedded applications, including voice, image, and video processing.

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: ARM Ltd. ARM920T Technical Reference Manual. ARM Ltd.
• 3: 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]
• 4: Baase, S. and Gelder, A. 2000. Computer Algorithms. Addison-Wesley, Boston, MA.
• 5: Chinnakrishnan S. Ballapuram , Hsien-Hsin S. Lee , Milos Prvulovic, Synonymous address compaction for energy reduction in data TLB, Proceedings of the 2005 international symposium on Low power electronics and design, August 08-10, 2005, San Diego, CA, USA [doi>10.1145/1077603.1077689]
• 6: 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]
• 7: Michel Cekleov , Michel Dubois, Virtual-Address Caches Part 1: Problems and Solutions in Uniprocessors, IEEE Micro, v.17 n.5, p.64-71, September 1997 [doi>10.1109/40.621215]
• 8: Massimilano Chiodo , Paolo Giusto , Attila Jurecska , Harry C. Hsieh , Alberto Sangiovanni-Vincentelli , Luciano Lavagno, Hardware-Software Codesign of Embedded Systems, IEEE Micro, v.14 n.4, p.26-36, August 1994 [doi>10.1109/40.296155]
• 9: Peter J. Denning, Virtual memory, ACM Computing Surveys (CSUR), v.28 n.1, p.213-216, March 1996 [doi>10.1145/234313.234403]
• 10: Magnus Ekman , Per Stenström , Fredrik Dahlgren, TLB and snoop energy-reduction using virtual caches in low-power chip-multiprocessors, Proceedings of the 2002 international symposium on Low power electronics and design, August 12-14, 2002, Monterey, California, USA [doi>10.1145/566408.566471]
• 11: Dongrui Fan , Zhimin Tang , Hailin Huang , Guang R. Gao, An energy efficient TLB design methodology, Proceedings of the 2005 international symposium on Low power electronics and design, August 08-10, 2005, San Diego, CA, USA [doi>10.1145/1077603.1077688]
• 12: Krisztián Flautner , Nam Sung Kim , Steve Martin , David Blaauw , Trevor Mudge, Drowsy caches: simple techniques for reducing leakage power, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 13: Poletti Francesco , Paul Marchal , David Atienza , Luca Benini , Francky Catthoor , Jose M. Mendias, An integrated hardware/software approach for run-time scratchpad management, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996634]
• 14: Steve Furber, ARM System-on-Chip Architecture, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 15: Tony Givargis, Zero cost indexing for improved processor cache performance, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.1, p.3-25, January 2006 [doi>10.1145/1124713.1124715]
• 16: M. R. Guthaus , J. S. Ringenberg , D. Ernst , T. M. Austin , T. Mudge , R. B. Brown, MiBench: A free, commercially representative embedded benchmark suite, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop, p.3-14, December 02-02, 2001 [doi>10.1109/WWC.2001.15]
• 17: Heckmann, R., Langenbach, M., Thesing, S., and Wilhelm, R. 2003. The influence of processor architecture on the design and the results of wcet tools. IEEE Proc. 91, 7, 1038--1054.
• 18: J. S. Hu , A. Nadgir , N. Vijaykrishnan , M. J. Irwin , M. Kandemir, Exploiting program hotspots and code sequentiality for instruction cache leakage management, Proceedings of the 2003 international symposium on Low power electronics and design, August 25-27, 2003, Seoul, Korea [doi>10.1145/871506.871606]
• 19: Intel Corporation. Intel XScale microarchitecture. Intel Corporation.
• 20: Bruce Jacob , Trevor Mudge, Virtual Memory: Issues of Implementation, Computer, v.31 n.6, p.33-43, June 1998 [doi>10.1109/2.683005]
• 21: Toni Juan , Tomas Lang , Juan J. Navarro, Reducing TLB power requirements, Proceedings of the 1997 international symposium on Low power electronics and design, p.196-201, August 18-20, 1997, Monterey, California, United States [doi>10.1145/263272.263332]
• 22: I. Kadayif , A. Sivasubramaniam , M. Kandemir , G. Kandiraju , G. Chen, Generating physical addresses directly for saving instruction TLB energy, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 23: M. Kandemir , I. Kadayif , G. Chen, Compiler-directed code restructuring for reducing data TLB energy, 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.1016747]
• 24: Kandemir, M., Ramanujam, J., Irwin, M., Vijaykrishnan, N., Kadayif, I., and Parikh, A. 2004. A compiler-based approach for dynamically managing scratch-pad memories in embedded systems. IEEE Trans Comput.-Aid. Design Integr. Circ. Syst. 23, 2, 243--260.
• 25: Raimund Kirner , Peter Puschner, Transformation of Path Information for WCET Analysis during Compilation, Proceedings of the 13th Euromicro Conference on Real-Time Systems, p.29, June 13-15, 2001
• 26: 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
• 27: Hsien-Hsin S. Lee , Chinnakrishnan S. Ballapuram, Energy efficient D-TLB and data cache using semantic-aware multilateral partitioning, Proceedings of the 2003 international symposium on Low power electronics and design, August 25-27, 2003, Seoul, Korea [doi>10.1145/871506.871583]
• 28: A Banked-Promotion TLB for High Performance and Low Power, Proceedings of the International Conference on Computer Design: VLSI in Computers & Processors, p.118, September 23-26, 2001
• 29: Silvano Martello , Paolo Toth, Knapsack problems: algorithms and computer implementations, John Wiley & Sons, Inc., New York, NY, 1990
• 30: Matthew C. Merten , Andrew R. Trick , Ronald D. Barnes, An Architectural Framework for Runtime Optimization, IEEE Transactions on Computers, v.50 n.6, p.567-589, June 2001 [doi>10.1109/12.931894]
• 31: Montanaro, J., Witek, R., Anne, K., Black, A., Cooper, E., Dobberpuhl, D., Donahue, P., Eno, J., Farell, A., Hoeppner, G., et al. 1996. A 160mhz, 32b 0.5w cmos risc microprocessor. In Proceedings of the International Symposium on Computers and Communication (ISCC'96). IEEE, Los Alamitos, CA, 214--229.
• 32: Xiaogang Qiu , Michel Dubois, Towards Virtually-Addressed Memory Hierarchies, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.51, January 20-24, 2001
• 33: Timothy Sherwood , Erez Perelman , Greg Hamerly , Suleyman Sair , Brad Calder, Discovering and Exploiting Program Phases, IEEE Micro, v.23 n.6, p.84-93, November 2003 [doi>10.1109/MM.2003.1261391]
• 34: Shivakumar, P. and Jouppi, N. 2001. Cacti 3.0: An integrated cache timing, power and area model. Tech. rep., Western Research Lab.
• 35: Matthew Simpson , Bhuvan Middha , Rajeev Barua, Segment protection for embedded systems using run-time checks, Proceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems, September 24-27, 2005, San Francisco, California, USA [doi>10.1145/1086297.1086307]
• 36: Stojanovic, V. and Oklobdzija, V. 1999. Comparative analysis of master-slave latches and flip-flops for high-performance and low-power systems. IEEE J. Solid-State Circ. 34, 4, 536--548.
• 37: 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]
• 38: 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]
• 39: Chuanjun Zhang, Balanced Cache: Reducing Conflict Misses of Direct-Mapped Caches, Proceedings of the 33rd annual international symposium on Computer Architecture, p.155-166, June 17-21, 2006

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

General Terms:
Design, Experimentation, Performance

Keywords:
Low-power embedded systems, address translation, virtual memory