Memory access scheduling

ABSTRACT

The bandwidth and latency of a memory system are strongly dependent on the manner in which accesses interact with the “3-D” structure of banks, rows, and columns characteristic of contemporary DRAM chips. There is nearly an order of magnitude difference in bandwidth between successive references to different columns within a row and different rows within a bank. This paper introduces memory access scheduling, a technique that improves the performance of a memory system by reordering memory references to exploit locality within the 3-D memory structure. Conservative reordering, in which the first ready reference in a sequence is performed, improves bandwidth by 40% for traces from five media benchmarks. Aggressive reordering, in which operations are scheduled to optimize memory bandwidth, improves bandwidth by 93% for the same set of applications. Memory access scheduling is particularly important for media processors where it enables the processor to make the most efficient use of scarce memory bandwidth.

REFERENCES

• 1: J. Carter , W. Hsieh , L. Stoller , M. Swanson , L. Zhang , E. Brunvand , A. Davis , C.-C. Kuo , R. Kuramkote , M. Parker , L. Schaelicke , T. Tateyama, Impulse: Building a Smarter Memory Controller, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.70, January 09-12, 1999
• 2: Jesus Corbal , Roger Espasa , Mateo Valero, Command Vector Memory Systems: High Performance at Low Cost, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.68, October 12-18, 1998
• 3: Richard Crisp, Direct Rambus Technology: The New Main Memory Standard, IEEE Micro, v.17 n.6, p.18-28, November 1997 [doi>10.1109/40.641593]
• 4: Vinodh Cuppu , Bruce Jacob , Brian Davis , Trevor Mudge, A performance comparison of contemporary DRAM architectures, Proceedings of the 26th annual international symposium on Computer architecture, p.222-233, May 01-04, 1999, Atlanta, Georgia, United States
• 5: Joel S. Emer , Douglas W. Clark, A Characterization of Processor Performance in the vax-11/780, Proceedings of the 11th annual international symposium on Computer architecture, p.301-310, January 1984
• 6: Sung I. Hong , Sally A. McKee , Maximo H. Salinas , Robert H. Klenke , James H. Aylor , Wm. A. Wulf, Access Order and Effective Bandwidth for Streams on a Direct Rambus Memory, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.80, January 09-12, 1999
• 7: 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
• 8: KANADE, TAKEO, KANO, HIROSHI, AND KIMURA, SHIGERU, Development of a Video-Rate Stereo Machine. In Proceedings of the International Robotics and Systems Conference (August 1995), pp. 95-100.
• 9: David Kroft, Lockup-free instruction fetch/prefetch cache organization, Proceedings of the 8th annual symposium on Computer Architecture, p.81-87, May 12-14, 1981, Minneapolis, Minnesota, United States
• 10: Ruby B. Lee , Michael D. Smith, Guest Editors' Introduction: Media Processing: A New Design Target, IEEE Micro, v.16 n.4, p.6-9, August 1996 [doi>10.1109/MM.1996.526920]
• 11: MATTHEW, BINU K., ET AL., Design of a Parallel Vector Access Unit for SDRAM Memory Systems. In Proceedings of the Sixth International Symposium on High-Performance Computer Architecture (January 2000), pp. 39-48.
• 12: S. A. Mckee , W. A. Wulf, Access ordering and memory-conscious cache utilization, Proceedings of the 1st IEEE Symposium on High-Performance Computer Architecture, p.253, January 22-25, 1995
• 13: NEC Corporation. 128M-bit Synchronous DRAM 4-bank, LVTTL Data Sheet. Document No. M12650EJ5VODS00, 5th Edition, Revision K (July 1998).
• 14: David Patterson , Thomas Anderson , Neal Cardwell , Richard Fromm , Kimberly Keeton , Christoforos Kozyrakis , Randi Thomas , Katherine Yelick, A Case for Intelligent RAM, IEEE Micro, v.17 n.2, p.34-44, March 1997 [doi>10.1109/40.592312]
• 15: Parthasarathy Ranganathan , Sarita Adve , Norman P. Jouppi, Performance of image and video processing with general-purpose processors and media ISA extensions, Proceedings of the 26th annual international symposium on Computer architecture, p.124-135, May 01-04, 1999, Atlanta, Georgia, United States
• 16: Scott Rixner , William J. Dally , Ujval J. Kapasi , Brucek Khailany , Abelardo López-Lagunas , Peter R. Mattson , John D. Owens, A bandwidth-efficient architecture for media processing, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.3-13, November 1998, Dallas, Texas, United States
• 17: Ashley Saulsbury , Fong Pong , Andreas Nowatzyk, Missing the memory wall: the case for processor/memory integration, Proceedings of the 23rd annual international symposium on Computer architecture, p.90-101, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 18: WATANABE, TAKEO, ET AL., Access Optimizer to Overcome the "Future Walls of Embedded DRAMs" in the Era of Systems on Silicon. In IEEE International Solid-State Circuits Conference Digest of Technical Papers (February 1999), pp. 370- 371.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

Additional Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
  B.3 MEMORY STRUCTURES

General Terms:
Design, Management, Performance