External memory page remapping for embedded multimedia systems

ABSTRACT

As memory speeds and bus capacitances continue to rise, external memory bus power will make up an increasing portion of the total system power budget for system-on-a-chip embedded systems. Both hardware and software approaches can be explored to balance the power/performance tradeoff associated with the external memory.

In this paper we present a hardware-based, programmable external memory page remapping mechanism which can significantly improve performance and decrease the power budget due to external memory bus accesses. Our approach was developed by studying common data access patterns present in embedded multimedia applications. In the paper, we evaluate a mechanism that can perform page remapping of external memory. We also develop an efficient algorithm to map application data and instruction memory into external memory pages. We employ graph-coloring techniques to guide the page mapping procedure. The objective is to avoid page misses by remapping conflicting pages to different memory banks (i.e., by assigning them different colors). Our algorithm can significantly reduce the memory page miss rate by 70-80% on average. For a 4-bank SDRAM memory system, we reduced external memory access time by 12.6%. The proposed algorithm can reduce power consumption in majority of the benchmarks, averaged by 13.2% of power reduction. Combining the effects of both power and delay, our algorithm can benefit significantly to the total energy cost.

REFERENCES

• 1: Analog Devices Inc., Norwood, MA. SDRAM Selection Guidelines and Configuration for ADI Processors, May 2004.
• 2: P. Bose, D. H. Albonesi, and D. Marculescu. Guest editors' introduction: Power and complexity aware design. IEEE Micro, 23(5):8--11, Sep/Oct 2003.
• 3: Mary Brown , Roy M. Jenevein , Nasr Ullah, Memory Access Pattern Analysis, Proceedings of the Workload Characterization: Methodology and Case Studies, p.105, November 29-29, 1998
• 4: S. Byna , Xian-He Sun , W. Gropp , R. Thakur, Predicting memory-access cost based on data-access patterns, Proceedings of the 2004 IEEE International Conference on Cluster Computing, p.327-336, September 20-23, 2004
• 5: Francky Catthoor , Eddy de Greef , Sven Suytack, Custom Memory Management Methodology: Exploration of Memory Organisation for Embedded Multimedia System Design, Kluwer Academic Publishers, Norwell, MA, 1998
• 6: Victor De La Luz , Ismail Kadayif , Mahmut Kandemir , Uger Sezer, Access Pattern Restructuring for Memory Energy, IEEE Transactions on Parallel and Distributed Systems, v.15 n.4, p.289-303, April 2004 [doi>10.1109/TPDS.2004.1271179]
• 7: Amir H. Hashemi , David R. Kaeli , Brad Calder, Efficient procedure mapping using cache line coloring, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.171-182, June 16-18, 1997, Las Vegas, Nevada, United States
• 8: Mahmut Kandemir , J. Ramanujam , Alok Choudhary, Improving Cache Locality by a Combination of Loop and Data Transformations, IEEE Transactions on Computers, v.48 n.2, p.159-167, February 1999 [doi>10.1109/12.752657]
• 9: Alvin R. Lebeck , Xiaobo Fan , Heng Zeng , Carla Ellis, Power aware page allocation, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.105-116, November 2000, Cambridge, Massachusetts, United States
• 10: Junghee Lee , Chanik Park , Soonhoi Ha, Memory access pattern analysis and stream cache design for multimedia applications, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119777]
• 11: 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]
• 12: K. Ning and D. Kaeli. Power aware external bus arbitration for system-on-a-chip embedded systems. In Proceedings of International Conference on High Performance Embedded Architectures and Compilers (HiPEAC05), 2005.
• 13: Karl Pettis , Robert C. Hansen, Profile guided code positioning, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.16-27, June 1990, White Plains, New York, United States
• 14: Vidyadhar Phalke , B. Gopinath, Program Modelling via Inter-Reference Gaps and Applications, Proceedings of the 3rd International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, p.212-216, January 10-18, 1995
• 15: Shai Rubin , Rastislav Bodík , Trishul Chilimbi, An efficient profile-analysis framework for data-layout optimizations, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.140-153, January 16-18, 2002, Portland, Oregon

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Primary memory

General Terms:
Algorithms, Design

Keywords:
embedded systems, memory coloring, memory controllers, memory page remapping