Vector multiprocessors with arbitrated memory access

ABSTRACT

The high latency of memory accesses is one of the factors that most contribute to reduce the performance of current vector supercomputers. The conflicts that can occur in the memory modules plus the collisions in the interconnection network in the case of multiprocessors make that the execution time of applications increases significantly. In this work we propose a memory access method that for both cases of vector uniprocessors and multiprocessors allows to perform stream accesses with the smallest possible latency in the majority of the cases. The basic idea is to arbitrate the memory access by defining the order in which the memory modules are visited. The stream elements are requested out of order. In addition, the access method also reduces the cost of the interconnection network.

REFERENCES

• 1: R M. Kogge, "The Architecture of Pipelined Computers", McGraw-Hill, New York, 1981.
• 2: E Budnik and D. J. Kuck, "The Organization and Use of Parallel Memories", IEEE Trans. on Computers, vol. 20, no. 12, pp. 1566-1569, 1971.
• 3: J. Frailong, W. Jalby and J. Lenfant, "XOR-schemes: A Flexible Data Organization in Parallel Memories", Int. Conf. on Parallel Processing, pp. 276-283, 1985.
• 4: D.T. Harper III, "Address Transformations to Increase Memory Performance", Int. Conf. on Parallel Processing, pp. 237-241, 1989.
• 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: 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
• 7: 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
• 8: Montse Peiron , Mateo Valero , Eduard Ayguadé, Synchronized access to streams in SIMD vector multiprocessors, Proceedings of the 8th international conference on Supercomputing, p.23-32, July 11-15, 1994, Manchester, England [doi>10.1145/181181.181204]
• 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. Bailey, "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: 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]
• 14: 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]
• 15: 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]
• 16: 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]
• 17: D.A. Calahan, "Characterization of Memory Conflict Loading on the Cray-2", Int. Conf. on Parallel Processing, pp. 299-302, 1988.
• 18: Ingrid Y. Bucher , Margaret L. Simmons, Measurement of memory access contentions in multiple vector processor systems, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.806-817, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.126197]
• 19: 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]
• 20: Mateo Valero , Montse Peiron , Eduard Ayguadé, Memory Access Synchronization in Vector Multiprocessors, Proceedings of the Third Joint International Conference on Vector and Parallel Processing: Parallel Processing, p.414-425, September 06-08, 1994
• 21: Honda Shing , Lionel M. Ni, A conflict-free memory design for multiprocessors, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.46-55, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125868]

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.3 MEMORY STRUCTURES

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

General Terms:
Algorithms, Design, Performance