Co-design of interleaved memory systems

ABSTRACT

Memory interleaving is a cost-efficient approach to increase bandwidth. Improving data access locality and reducing memory access conflicts are two important aspects to achieve high efficiency for interleaved memory. In this paper, we introduce a design framework that integrates these two optimizations, in order to find out minimal memory banks and channels required in the embedded system under performance restriction. Several important techniques, loop and data layout transformations for data access locality, extracting data streams, conflict cache miss reduction as well as data placement and optimally reordered access for interleaved memories, are incorporated in the design framework. Experiments show that our co-design method results in substantially less hardware requirement compared to the implementations without optimization.

REFERENCES

• 1: CRAY X-MP Series Mainframe Reference Manual. Cray Research Inc. HR-0032, Nov. 1982
• 2: http ://www.rambus.com/
• 3: R. Raghavan , J. P. Hayes, Reducing Interference Among Vector Accesses in Interleaved Memories, IEEE Transactions on Computers, v.42 n.4, p.471-483, April 1993 [doi>10.1109/12.214693]
• 4: Steven Robbins , Kay A. Robbins, Buffered Banks in Multiprocessor Systems, IEEE Transactions on Computers, v.44 n.4, p.518-530, April 1995 [doi>10.1109/12.376167]
• 5: Wilfried Oed , O. Lange, On the effective bandwidth of interleaved memories in vector processor systems, IEEE Transactions on Computers, v.34 n.10, p.949-957, Oct. 1985
• 6: 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
• 7: A. M. del Corral , J. M. Llaberia, Minimizing Conflicts Between Vector Streams in Interleaved Memory Systems, IEEE Transactions on Computers, v.48 n.4, p.449-456, April 1999 [doi>10.1109/12.762540]
• 8: De-Lei Lee, Memory access reordering in vector processors, Proceedings of the 1st IEEE Symposium on High-Performance Computer Architecture, p.380, January 22-25, 1995
• 9: D. H. Lawrie, "Access and alignment of data in an array processor", IEEE Trans. Comput., Vol. C-24, pp. 1145-1155, Dec. 1975
• 10: B. Ramakrishna Rau, Pseudo-randomly interleaved memory, Proceedings of the 18th annual international symposium on Computer architecture, p.74-83, May 27-30, 1991, Toronto, Ontario, Canada
• 11: L. Kurian, B. Choi, P.T. Hulina, L.D. Coroor, "Module partitioning and interleaved data placement schemes to reduce conflicts in interleaved memories", Proc. Int'l Conf. Parallel Processing, Vol. 1, pp. 212-219, 1994
• 12: http://www.ee.princeton.edu/^-hualin/seminar.ppt
• 13: Michał Cierniak , Wei Li, Unifying data and control transformations for distributed shared-memory machines, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.205-217, June 18-21, 1995, La Jolla, California, United States
• 14: 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]
• 15: Somnath Ghosh , Margaret Martonosi, Cache miss equations: compiler analysis framework for tuning memory behavior, 1999
• 16: M. D. Hill , A. J. Smith, Evaluating Associativity in CPU Caches, IEEE Transactions on Computers, v.38 n.12, p.1612-1630, December 1989 [doi>10.1109/12.40842]
• 17: http://www.mpeg.org/MPEG/MSSG/

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

General Terms:
Design, Experimentation, Performance

Keywords:
data access locality, extracted data stream, in-dimension-stride vector, interleaved memory systems, memory access conflict, optimally reordered access