Compiler-assisted demand paging for embedded systems with flash memory

ABSTRACT

In this paper, we propose a novel, application specific demand paging mechanism for low-end embedded systems with flash memory as secondary storage. These systems are not equipped with virtual memory. A small memory space called an execution buffer is allocated to page an application. An application-specific page manager manages the buffer. The manager is generated by a compiler post-pass and combined with the application image. Our compiler post-pass analyzes the ELF executable image of an application and transforms function call/return instructions into calls to the page manager. As a result, each function of the code can be loaded into memory on demand at run time. To minimize the overhead of demand paging, code clustering algorithms are also presented. We evaluate our techniques with five embedded applications. We show that our approach can reduce the code memory size by 33% on average with reasonable performance degradation (8-20%) and energy consumption (10% more on average) for low-end embedded systems.

REFERENCES

• 1: Andrew W. Appel, Modern compiler implementation in Java, Cambridge University Press, New York, NY, 1997
• 2: ARM. ARM Developer Suite Version 1.2: ARM Debug Target Guide. ARM Limited, 2001.
• 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: Samsung~Electronics Co. NAND Flash Memory and SmartMedia Data Book. 2002.
• 5: 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]
• 6: Matthew R. Guthaus, Jeffrey S. Ringenberg, Dan Ernst, Todd M. Austin, Trevor Mudge, and Richard B. Brown. MiBench: A Free, Aommercially Representative Embedded Benchmark Suite. In Proceedings of the 4th Annual Workshop on Workload Characterization, December 1998.
• 7: Prabhat Jain , Srinivas Devadas , Daniel Engels , Larry Rudolph, Software-assisted cache replacement mechanisms for embedded systems, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 8: 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
• 9: M-Systems. Two Technologies Compared: NOR vs. NAND. White Paper, 91-SR-012-04-8L, Rev 1.1, July 2003.
• 10: Preeti Ranjan Panda , Alexandru Nicolau , Nikil Dutt, Memory Issues in Embedded Systems-on-Chip: Optimizations and Exploration, Kluwer Academic Publishers, Norwell, MA, 1998
• 11: Chanik Park , Jeong-Uk Kang , Seon-Yeong Park , Jin-Soo Kim, Energy-aware demand paging on NAND flash-based embedded storages, Proceedings of the 2004 international symposium on Low power electronics and design, August 09-11, 2004, Newport Beach, California, USA [doi>10.1145/1013235.1013317]
• 12: Chanik Park , Jaeyu Seo , Sunghwan Bae , Hyojun Kim , Shinhan Kim , Bumsoo Kim, A low-cost memory architecture with NAND XIP for mobile embedded systems, Proceedings of the 1st IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, October 01-03, 2003, Newport Beach, CA, USA [doi>10.1145/944645.944684]
• 13: Samsung Electronics Co. http://www.samsung.com/products/semiconductor/asic. 2004.
• 14: Abraham Silberschatz , Peter Galvin , Greg Gagne, Applied Operating System Concepts, John Wiley & Sons, Inc., New York, NY, 2001
• 15: Tajana Simunic , Luca Benini , Peter Glynn , Giovanni De Micheli, Dynamic power management for portable systems, Proceedings of the 6th annual international conference on Mobile computing and networking, p.11-19, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345914]
• 16: Tajana . Šimunić , Luca Benini , Giovanni De Micheli, Energy-efficient design of battery-powered embedded systems, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.1, p.15-28, Feb. 2001 [doi>10.1109/92.920814]
• 17: 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
• 18: Hiroyuki Tomiyama , Hiroto Yasuura, Code placement techniques for cache miss rate reduction, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.4, p.410-429, Oct. 1997 [doi>10.1145/268424.268469]
• 19: Toshiba America Electronic Components, Inc. Cost Savings with NAND Shadowing Reference Design with Motorola MPC8260 and Toshiba CompactFlash. 2002.
• 20: Manish Verma , Lars Wehmeyer , Peter Marwedel, Cache-Aware Scratchpad Allocation Algorithm, Proceedings of the conference on Design, automation and test in Europe, p.21264, February 16-20, 2004

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation; Optimization; Compilers
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Virtual memory; Secondary storage; Storage hierarchies

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance

Keywords:
SRAM, clustering, compilers, embedded systems, flash memory, heterogeneous memory, paging, post-pass optimization