Memory consistency and event ordering in scalable shared-memory multiprocessors

ABSTRACT

Scalable shared-memory multiprocessors distribute memory among the processors and use scalable interconnection networks to provide high bandwidth and low latency communication. In addition, memory accesses are cached, buffered, and pipelined to bridge the gap between the slow shared memory and the fast processors. Unless carefully controlled, such architectural optimizations can cause memory accesses to be executed in an order different from what the programmer expects. The set of allowable memory access orderings forms the memory consistency model or event ordering model for an architecture. This paper introduces a new model of memory consistency, called release consistency, that allows for more buffering and pipelining than previously proposed models. A framework for classifying shared accesses and reasoning about event ordering is developed. The release consistency model is shown to be equivalent to the sequential consistency model for parallel programs with sufficient synchronization. Possible performance gains from the less strict constraints of the release consistency model are explored. Finally, practical implementation issues are discussed, concentrating on issues relevant to scalable architectures.

REFERENCES

• 1: Sarita Adve and Mark Hill. Personal communication. March 1990.
• 2: Forest Basket& Tom Jermoluk, and Doug Solomon. The 4D-MP graphics superworkstation: Computing + graphics = 40 MIPS + 40 MFLOPS and 100,000 lighted polygons per second. In Proceedings of the 33rd IEEE Computer Society International Conference - COMPCON 88, pages 468471, February 1988.
• 3: W. C. Brantley, K. P. McAuliffe, and J. Weiss. RP3 processor-memory element. In Proceedings of the 1985 International Conference on Paralle{ Processing, pages 782-789, 1985.
• 4: M. Dubois , C. Scheurich , F. Briggs, Memory access buffering in multiprocessors, Proceedings of the 13th annual international symposium on Computer architecture, p.434-442, June 02-05, 1986, Tokyo, Japan
• 5: James R. Goodman. Cache consistlency and sequential consistency. Technical Report no. 61, SC1 Committee, March 1989.
• 6: Anoop Gupta , Milind Tambe , Dirk Kalp , Charles Forgy , Allen Newell, Parallel implementation of OPS5 on the encore multiprocessor: results and analysis, International Journal of Parallel Programming, v.17 n.2, p.95-124, April 1988 [doi>10.1007/BF01383952]
• 7: Leslie Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers, C-28(9):241-248, September 1979.
• 8: Daniel Lenoski , James Laudon , Kourosh Gharachorloo , Anoop Gupta , John Hennessy, The directory-based cache coherence protocol for the DASH multiprocessor, Proceedings of the 17th annual international symposium on Computer Architecture, p.148-159, May 28-31, 1990, Seattle, Washington, United States
• 9: G. F. Pfister, W. C. Brantley, D. A. George, S. L. Harvey, W. J. Kleinfelder, K. P. McAuliffe. E. A. Melton, V. A. Norton, and J. Weiss. The Il3M research parallel processor prototype (RP3): Introduction and architecture. In Proceedings of the 1985 International Conference on Parallel Processing, pages 764-771, 1985.
• 10: C. Scheurich , M. Dubois, Correct memory operation of cache-based multiprocessors, Proceedings of the 14th annual international symposium on Computer architecture, p.234-243, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30377]
• 11: C. E. Scheurich, Access ordering and coherence in shared memory multiprocessors, University of Southern California, Los Angeles, CA, 1989
• 12: G. E. Schmidt. The Butterfly parallel processor. In Proceedings of the Second Znternational Conference on Supercomputing, pages 362-365, 1987.
• 13: Dennis Shasha , Marc Snir, Efficient and correct execution of parallel programs that share memory, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.2, p.282-312, April 1988 [doi>10.1145/42190.42277]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS

General Terms:
Design, Management, Theory