APEX: access pattern based memory architecture exploration

ABSTRACT

Memory accesses represent a major bottleneck in embedded systems power and performance. Traditionally, designers tried to alleviate this problem by relying on a simple cache hierarchy, or a limited use of special purpose memory modules such as stream buffers. Although real-life applications contain a large number of memory references to a diverse set of data structures, a significant percentage of all memory accesses in the application are generated from a few memory instructions that exhibit predictable, well-known access patterns; this creates an opportunity for memory customization, targeting the needs of these access patterns. We present APEX, an approach that extracts, analyzes and clusters the most active access patterns in the application, and aggressively customizes the memory architecture to match the needs of the application, exploring a wide range of cost, performance and power designs. We use a heuristic to prune the design space, guiding the exploration towards the best cost/gain ratios. We present experiments on a set of large real-life benchmarks, showing significant performance improvements for varied cost and power characteristics, allowing the designer to best target the system goals.

REFERENCES

• 1: Smita Bakshi , Daniel D. Gajski, A memory selection algorithm for high-performance pipelines, Proceedings of the conference on European design automation, p.124-129, September 18-22, 1995, Brighton, England
• 2: 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
• 3: Tzi cker Chiueh.Sunder:A programmable hardware prefetch architecture for numerical loops.In Conference on High Performance Networking and Computing 1994.
• 4: Robert F. Cmelik , David Keppel, Shade: A Fast Instruction Set Simulator for Execution Profiling, Sun Microsystems, Inc., Mountain View, CA, 1993
• 5: P. Grun , N. Dutt , A. Nicolau, Access pattern based local memory customization for low power embedded systems, Proceedings of the conference on Design, automation and test in Europe, p.778-784, March 2001, Munich, Germany
• 6: P.Grun,N.Dutt,and A.Nicolau.Exploring memory architecture through access pattern analysis and clustering. Technical report,University of California,Irvine,2001.
• 7: Patrick Hicks , Matthew Walnock , Robert Michael Owens, Analysis of power consumption in memory hierarchies, Proceedings of the 1997 international symposium on Low power electronics and design, p.239-242, August 18-20, 1997, Monterey, California, United States [doi>10.1145/263272.263342]
• 8: Joseph Hummel , Alexandru Nicolau , Laurie J. Hendren, A Language for Conveying the Aliasing Properties of Dynamic, Pointer-Based Data Structures, Proceedings of the 8th International Symposium on Parallel Processing, p.208-216, April 01, 1994
• 9: Norman P. Jouppi, Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, Proceedings of the 17th annual international symposium on Computer Architecture, p.364-373, May 28-31, 1990, Seattle, Washington, United States
• 10: C.Kulkarni.Cache optimization for Multimedia Applications PhD thesis,IMEC,2001.
• 11: Prabhat Mishra , Peter Grun , Nikil Dutt , Alex Nicolau, Processor-Memory Co-Exploration driven by a Memory-Aware Architecture Description Language, Proceedings of the The 14th International Conference on VLSI Design (VLSID '01), p.70, January 03-07, 2001
• 12: S. Palacharla , R. E. Kessler, Evaluating stream buffers as a secondary cache replacement, Proceedings of the 21ST annual international symposium on Computer architecture, p.24-33, April 18-21, 1994, Chicago, Illinois, United States
• 13: Preeti Ranjan Panda , Alexandru Nicolau , Nikil Dutt, Memory Issues in Embedded Systems-on-Chip: Optimizations and Exploration, Kluwer Academic Publishers, Norwell, MA, 1998
• 14: Ian Parsons , Ron Unrau , Jonathan Schaeffer , Duane Szafron, PI/OT: parallel I/O templates, Parallel Computing, v.23 n.4-5, p.543-570, June 1, 1997 [doi>10.1016/S0167-8191(97)00013-6]
• 15: R. H. Patterson , G. A. Gibson , E. Ginting , D. Stodolsky , J. Zelenka, Informed prefetching and caching, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.79-95, December 03-06, 1995, Copper Mountain, Colorado, United States
• 16: S.Przybylski.Sorting out the new DRAMs.In Hot Chips Tutorial Stanford,CA,1997.
• 17: G.Reinman and N.Jouppi.An integrated cache timing and power model.In Summer Internship Report, COMPAQ Western Research Lab, Palo-Alto 1999.
• 18: Amir Roth , Andreas Moshovos , Gurindar S. Sohi, Dependence based prefetching for linked data structures, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.115-126, October 02-07, 1998, San Jose, California, United States
• 19: Synopsys Design Compiler.www.synopsys.com
• 20: Alexander V. Veidenbaum , Weiyu Tang , Rajesh Gupta , Alexandru Nicolau , Xiaomei Ji, Adapting cache line size to application behavior, Proceedings of the 13th international conference on Supercomputing, p.145-154, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305188]
• 21: N. Vijaykrishnan , M. Kandemir , M. J. Irwin , H. S. Kim , W. Ye, Energy-driven integrated hardware-software optimizations using SimplePower, Proceedings of the 27th annual international symposium on Computer architecture, p.95-106, June 2000, Vancouver, British Columbia, Canada
• 22: Sven Wuytack , Francky Catthoor , Gjalt de Jong , Bill Lin , Hugo de Man, Flow Graph Balancing for Minimizing the Required Memory Bandwidth, Proceedings of the 9th international symposium on System synthesis, p.127, November 06-08, 1996

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: System architectures; Instruction set design (e.g., RISC, CISC, VLIW)

General Terms:
Design, Experimentation, Performance