Conflict-free access of vectors with power-of-two strides

ABSTRACT

An address mapping and an access order is presented for conflict-free access to vectors with any initial address and power-of-two strides. We show that for this conflict-free access it is necessary that the memory be unmatched and present an implementation for M=2T, where M is the number of modules and T the module latency. Moreover, the implementation allows the masking of the latency of the address calculation, of the mapper, and of the bus arbiter.

REFERENCES

• 1: P. Budnik and D. J. Kuck, "The Organization and Use of Parallel Memories", IEEE Transactions on Computers, vol. C-20, no. 12, pp. 1566-1569, 1971.
• 2: C.-L. Chen , C.-K. Liao, Analysis of vector access performance on skewed interleaved memory, Proceedings of the 16th annual international symposium on Computer architecture, p.387-394, April 1989, Jerusalem, Israel
• 3: J. Frailong, W. Jalby and J. Lenfant, "10OR-schemes: A Flexible Data Organization in Parallel Memories", International Conference on Parallel Processing, pp. 276-283, 1985.
• 4: D.T. Harper III and Y. Costa, "Analytical Estimation of Vector Access Performance in Parallel Memory Architectures", Internal Report, Dept. of Electrical Engineering. The University of Texas at Dallas, 1991.
• 5: D. T. Harper, III , J. R. Jump, Performance evaluation of vector accesses in parallel memories using a skewed storage scheme, Proceedings of the 13th annual international symposium on Computer architecture, p.324-328, June 02-05, 1986, Tokyo, Japan
• 6: David T. Harper, III , Darel A. Linebarger, Conflict-Free Vector Access Using a Dynamic Storage Scheme, IEEE Transactions on Computers, v.40 n.3, p.276-283, March 1991 [doi>10.1109/12.76404]
• 7: D. T. Harper, III, Block, Multistride Vector, and FFT Accesses in Parallel Memory Systems, IEEE Transactions on Parallel and Distributed Systems, v.2 n.1, p.43-51, January 1991 [doi>10.1109/71.80188]
• 8: D.H. Lawrie, "Access and Alignment of Data in an Array Processor", IEEE Transactions on Computers, vol. C-24, no. 12, pp. 1145-1155, Dec. 1975.
• 9: A. Norton and E. Melton, "A Class of Boolean Linear Transformations for Conflict-Free Power-of-Two Stride Access", international Conference on Parallel Processing, pp. 247-254, 1987.
• 10: 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
• 11: B. R. Rau, M. S. Schlansker and D. W. L. Yen, "The CydraTM 5 Stride-Insensitive Memory System", International Conference on Parallel Processing, pp. 242-246, 1989.
• 12: 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
• 13: 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
• 14: S. Weiss, An aperiodic storage scheme to reduce memory conflicts in vector processors, Proceedings of the 16th annual international symposium on Computer architecture, p.380-386, April 1989, Jerusalem, Israel
• 15: H.A.G. Wijshoff and J. van Leeuwen, "The Structure of Periodic Storage Schemes for Parallel Memories", IEEE Transactions on Computers, vol. C-34, pp. 501-505, June 1985.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Array and vector processors

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION

  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

General Terms:
Design

Keywords:
conflict-free access, multi-module memories, out-of-order access, power-of-two strides, storage schemes, vector processors