Synchronized access to streams in SIMD vector multiprocessors

ABSTRACT

The synchronized and simultaneous access to several vectors that form a single stream is typical in SIMD vector multiprocessors as well as in MIMD superscalar multiprocessors with decoupled access. In this paper we propose a block-interleaved storage scheme and an out-of-order access mechanism that allows conflict-free access to streams with an arbitrary initial address and constant stride between elements. The memory system can have any degree of unmatchness and we consider the use of either a crossbar or a multistage interconnection network. A maximal number of conflict-free families including the most commonly used strides can be obtained. We describe the hardware for address calculation and control and show that their additional costs are minimal compared with the cost of the hardware for in-order access. Finally, we evaluate the applicability of this technique to real loops from some programs of the Perfect Club and SPEC suites.

REFERENCES

• 1: P. Budnik and D.J. Kuck, "The Organization and Use of Parallel Memories", IEEE Trans. on Computers, vol. 20, no. 12 pp. 1566-1569, 1971.
• 2: J. Frailong, W. Jalby and J. Lenfant "XOR-schemes: A Flexible Data Organization Parallel Memories", Int. Conf. on Parallel Processing, pp. 276-283, 1985.
• 3: 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]
• 4: 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
• 5: 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
• 6: Tomás Lang , Mateo Valero , Montse Peiron , Eduard Ayguadé, Conflict-Free Access for Streams in Multimodule Memories, IEEE Transactions on Computers, v.44 n.5, p.634-646, May 1995 [doi>10.1109/12.381949]
• 7: Mateo Valero , Tomás Lang , Eduard Ayguadé, Conflict-free access of vectors with power-of-two strides, Proceedings of the 6th international conference on Supercomputing, p.149-156, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143403]
• 8: Honda Shing, A conflict-free memory design for multiprocessors, Michigan State University, East Lansing, MI, 1992
• 9: David H. Bailey, Vector computer memory bank contention, IEEE Transactions on Computers, v.36 n.3, p.293-298, March 1987 [doi>10.1109/TC.1987.1676901]
• 10: Ingrid Y. Bucher , Donald A. Calahan, Access conflicts in multiprocessor memories queueing models and simulation studies, Proceedings of the 4th international conference on Supercomputing, p.428-438, June 11-15, 1990, Amsterdam, The Netherlands
• 11: D.A. Calahan and D.H. Barley, "Measurement and Analysis of Memory Conflicts on Vector Multiprocessors", Performance Evaluation of Supercomputers, Elsevier Science Publishers, pp. 83-106, 1988
• 12: 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
• 13: Tony Cheung , James E. Smith, A simulation study of the CRAY X-MP memory system, IEEE Transactions on Computers, v.35 n.7, p.613-622, July 1986 [doi>10.1109/TC.1986.1676802]
• 14: W Oed , O Lange, Modelling, measurement, and simulation of memory interference in the CRAY X-MP, Parallel Computing, v.3 n.4, p.343-358, Oct. 1986 [doi>10.1016/0167-8191(86)90015-3]
• 15: D. A. Calahan, Some results in memory conflict analysis, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.775-778, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76351]
• 16: D.A. Calahan, "Characterization of Memory Conflict Loading on the Cray-2" Int. Conf. on Parallel Processing, pp. 299- 302,1988.
• 17: J. E. Smith , W. R. Taylor, Characterizing memory performance in vector multiprocessors, Proceedings of the 6th international conference on Supercomputing, p.35-44, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143379]
• 18: J. E. Smith , W. R. Taylor, Accurate modelling of interconnection networks in vector supercomputers, Proceedings of the 5th international conference on Supercomputing, p.264-273, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109091]
• 19: André Seznec , Jacques Lenfant, Interleaved parallel schemes: improving memory throughput on supercomputers, Proceedings of the 19th annual international symposium on Computer architecture, p.246-255, May 19-21, 1992, Queensland, Australia
• 20: H. Tamura Y. Shinnkai and F. Isobe "The Supercomputer FACOM VP System", Fujisu Techical Journal, 1985.
• 21: 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]
• 22: M. Peiron, M. Valero, E. Ayguade and T. Lang, "Conflict- Free Acess Streams in Multiprocessor Systems" Research Report DAC RR-93/04, 1993.
• 23: D.H. Lawrie "Access and Afignment of Data in an Array Processor", IEEE Trans. on Computers, vol. 24, no. 12, pp. 1145-1155, 1975.
• 24: R. Espasa et al, "Quantitative Analysis of Vector Code", Research Report CEPBA/UPC, 1994.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Single-instruction-stream, multiple-data-stream processors (SIMD)

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Design, Measurement, Performance, Theory

Keywords:
SIMD vector multiprocessors, conflict-free access, interconnection networks, multi-module memories, vectors with constant stride