Algorithmic foundations for a parallel vector access memory system

ABSTRACT

This paper presents mathematical foundations for the design of a memory controller subcomponent that helps to bridge the processor/memory performance gap for applications with strided access patterns. The Parallel Vector Access (PVA) unit exploits the regularity of vectors or streams to access them efficiently in parallel on a multi-bank SDRAM memory system. The PVA unit performs scatter/gather operations so that only the elements accessed by the application are transmitted across the system bus. Vector operations are broadcast in parallel to all memory banks, each of which implements an efficient algorithm to determine which vector elements it holds. Earlier performance evaluations have demonstrated that our PVA implementation loads elements up to 32.8 times faster than a conventional memory system and 3.3 times faster than a pipelined vector unit, without hurting the performance of normal cache-line fills. Here we present the underlying PVA algorithms for both word interleaved and cache-line inter-leaved memory systems.

REFERENCES

• 1: Todd M. Austin , Dionisios N. Pnevmatikatos , Gurindar S. Sohi, Streamlining data cache access with fast address calculation, Proceedings of the 22nd annual international symposium on Computer architecture, p.369-380, June 22-24, 1995, S. Margherita Ligure, Italy
• 2: Michael Bekerman , Stephan Jourdan , Ronny Ronen , Gilad Kirshenboim , Lihu Rappoport , Adi Yoaz , Uri Weiser, Correlated load-address predictors, Proceedings of the 26th annual international symposium on Computer architecture, p.54-63, May 01-04, 1999, Atlanta, Georgia, United States
• 3: 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
• 4: Siddhartha Chatterjee , John R. Gilbert , Fred J. E. Long , Robert Schreiber , Shang-Hua Teng, Generating local addresses and communication sets for data-parallel programs, Journal of Parallel and Distributed Computing, v.26 n.1, p.72-84, April 1, 1995 [doi>10.1006/jpdc.1995.1049]
• 5: 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
• 6: J. Corbal, R. Espasa, and M. Valero. Command vector memory systems: High performance at low cost. Technical Report UPC-DAC- 1999-5, Universitat Politecnica de Catalunya, Jan. 1999.
• 7: Cray Research, Inc. CRAY T3D System Architecture Overview, hr-04033 edition, Sept. 1993.
• 8: A. M. del Corral , José M. Llabería, Access order to avoid inter-vector-conflicts in complex memory systems, Proceedings of the 9th International Symposium on Parallel Processing, p.404-410, April 25-28, 1995
• 9: José González , Antonio González, Speculative execution via address prediction and data prefetching, Proceedings of the 11th international conference on Supercomputing, p.196-203, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263631]
• 10: W.-C. Hsu , J. E. Smith, Performance of cached DRAM organizations in vector supercomputers, Proceedings of the 20th annual international symposium on Computer architecture, p.327-336, May 16-19, 1993, San Diego, California, United States
• 11: B. Mathew. Parallel vector access: A technique for improving memory system performance. Master's thesis, University of Utah Department of Computer Science, Jan. 2000.
• 12: B. Mathew, S. McKee, J. Carter, and A. Davis. Design of a parallel vector access unit for sdram memories. In Proceedings of the Sixth Annual Symposium on High Performance Computer Architecture, pages 39-48, Jan. 2000.
• 13: Sally A. McKee , Assaji Aluwihare , Benjamin H. Clark , Robert H. Klenke , Trevor C. Landon , Christopher W. Oliver , Maximo H. Salinas , Adam E. Szymkowiak , Kenneth L. Wright , Wm. A. Wulf , James H. Aylor, Design and evaluation of dynamic access ordering hardware, Proceedings of the 10th international conference on Supercomputing, p.125-132, May 25-28, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237578.237594]
• 14: Steven Andrew Moyer, Access ordering and effective memory bandwidth, University of Virginia, Charlottesville, VA, 1993
• 15: Montse Peiron , Mateo Valero , Eduard Ayguadé , Tomás Lang, Vector multiprocessors with arbitrated memory access, Proceedings of the 22nd annual international symposium on Computer architecture, p.243-252, June 22-24, 1995, S. Margherita Ligure, Italy
• 16: Rambus, Inc. RMC2 Data Sheet Advance Information. http://www.rambus.com/developer/downloads/rmc2_ overview.pdf, August 1999.
• 17: Reinhard C. Schumann, Design of the 21174 memory controller for DIGITAL Personal Workstations, Digital Technical Journal, v.9 n.2, p.57-70, 1997
• 18: Mateo Valero , Tomás Lang , José M. Llabería , Montse Peiron , Eduard Ayguadé , Juan J. Navarra, Increasing the number of strides for conflict-free vector access, Proceedings of the 19th annual international symposium on Computer architecture, p.372-381, May 19-21, 1992, Queensland, Australia
• 19: Lixin Zhang , John B. Carter , Wilson C. Hsieh , Sally A. McKee, Memory System Support for Image Processing, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.98, October 12-16, 1999

INDEX TERMS

Primary Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.2 Input/Output Devices
          Subjects: Channels and controllers

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Control theory

General Terms:
Algorithms, Design, Performance, Theory, Verification