Sarita V. Adve
Mark D. Hill
Abstract
A memory model for a shared memory, multiprocessor commonly and often implicitly assumed by programmers is that of sequential consistency. This model guarantees that all memory accesses will appear to execute atomically and in program order. An alternative model, weak ordering, offers greater performance potential. Weak ordering was first defined by Dubois, Scheurich and Briggs in terms of a set of rules for hardware that have to be made visible to software.
The central hypothesis of this work is that programmers prefer to reason about sequentially consistent memory, rather than having to think about weaker memory, or even write buffers. Following this hypothesis, we re-define weak ordering as a contract between software and hardware. By this contract, software agrees to some formally specified constraints, and hardware agrees to appear sequentially consistent to at least the software that obeys those constraints. We illustrate the power of the new definition with a set of software constraints that forbid data races and an implementation for cache-coherent systems that is not allowed by the old definition.
- AdH89 S. V. ADVE and M. D. HILL. Weak Ordering - A New Definition And Some Implications, Computer Sciences Technical Report #902, University of Wisconsin, Madison, December 1989.Google Scholar
- ASH88 A. AGARWAL. R. SIMONI. M. HOROWITZ and J. HENNESSY, An Evaluation of Directory Schemes for Cache Coherence, 15th Annual International Symposium on Computer Architecture, Honolulu, Hawaii, June 1988.280-289. Google ScholarDigital Library
- ArB86 J. ARCHIBALD and J. BAER, Cache Coherence Protocols: Evaluation Using a Multiprocessor Simulation Model, ACM Transactions on Computer Systems 4. 4 (November 1986). 273- 298. Google ScholarDigital Library
- BeG81 P. A. BERNSTEIN and N. GOODMAN. Concurrency Control in Distributed Systems, Computing Surueys 13.2 (June, 1981). 185221. Google ScholarDigital Library
- BNR89 R. BISIANI. A. NOWATZYK and M. RAMSHANKAR. Coherent Shared Memory on a Distributed Memory Machine, Proc. International Conference on Parallel Processing, August 1989, I-133-141.Google Scholar
- BMW85 W. C. BRANIZEY, K. P. MCAULJFFE and J. WEISS, RP3 Process-Memory Element, International Conference on Parallel Processing, August 1985. 772-781.Google Scholar
- Col84 W. W. COLLIER, Architectures for Systems of Parallel Processes, Technical Report Tech. Rep. 00.3253, IBM Corp., Poughkeepsie, N.Y., 27 January 1984.Google Scholar
- Col90 W. W. COLLIER, Reasoning about Parallel Architectures, Prentice-Hall, Inc., To appear 1990. Google ScholarDigital Library
- DeM88 R. DE LEONE and 0. L. MANGASARIAN, Asynchronous Parallel Successive Over-relaxation for the Symmetric Linear Complementarity Problem, Mathematical Programming 42( 1988). 347-361. Google ScholarDigital Library
- DSB86 M. DUBOIS, C. SCHEURICH and F. A. BRIGGS, Memory Access Buffering in Multiprocessors, Proc. Thirteenth Annual International Symposium on Computer Architecture 14. 2 (June 1986), 434-442. Google ScholarDigital Library
- DSB88 M. DUBOIS, C. SCHEURICH and F. A. BRIGGS, Synchronization, Coherence, and Event Ordering in Multiprocessors, IEEE Computer 21, 2 (February 1988). 9-21. Google ScholarDigital Library
- GVW89 J. R. GOODMAN, M. K. VERNON and P. J. WOEST. Efficient Synchronization Primitives for Large- Scale Cache-Coherent Multiprocessors, Proc. Third International Conference on Architectural Support for Programming Languages and Operating Systems, Boston, April 1989,64-75. Google ScholarDigital Library
- Kro81 D. KROFT, Lockup-Free Instruction Fetch/Perfetch Cache Organization, Proc. Eighth Symposium on Computer Architecture, May 1981, 81-87. Google ScholarDigital Library
- Lam78 L. LAMPORT. Time, Clocks, and the Ordering of Events in a Distributed System, Communications of the ACM 21.7 (July 1978). 558-565. Google ScholarDigital Library
- Lam79 L. LAMPORT. How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs, IEEE Trans. on Computers C-28, 9 (September 1979). 690-691.Google ScholarDigital Library
- Lam86 L. LAMPORT, The Mutual Exclusion Problem, Parts I and II , Journal of the Association of Computing Machinery 33. 2 (April 1986), 313- 348. Google ScholarDigital Library
- NeM89 R. NEIZR and B. MILLER, Detecting Data Races in Parallel Program Executions, Computer Sciences Technical Report #894, University of Wiiconsin. Madison. November 1989.Google Scholar
- Pap86 C. PAPAD-OU, The Theory of Database Concurrency Control, Computer Science Press. Rockville, Maryland 20850.1986. Google ScholarDigital Library
- PBG85 G. F. PZ;ISTER, W. C. BRANTLEY, D. A. GEORGE, S. L. HARVEY, W. J. QXINFELDER K. P. MCAULIFFE, E. A. MELTON, V. A. NORTON and J. WEISS, The IBM Research Parallel Processor Prototype (RP3): Introduction and Architecture, International Cogerence on Parallel Processing, August 1985.764-771.Google Scholar
- RuS84 L. RUDOLPH and Z. SEGALL, Dynamic Decentralized Cache Schemes for MIMD Parallel Processors, Proc. Eleventh International Symposium on Computer Architecture, June 1984, 340-347. Google ScholarDigital Library
- ScD87 C. SCHEURICH and M. D~OIS, Correct Memory Operation of Cache-Based Multiprocessors, Proc. Fourteenth Annual International Symposium on Computer Architecture, Pittsburgh, PA, June 1987,234-243. Google ScholarDigital Library
- ScD88 C. SCHEURICH and M. DUBOIS, Concurrent Miss Resolution in Multiprocessor Caches, Proceedings of the 1988 International Conference on Parallel Processing, University Park PA, August, 1988, I-l 18-125.Google Scholar
- Sch89 C. E. SCHBURICH, Access Ordering and Coherence in Shared Memory Multiprocessors, Ph.D. Thesis, Department of Computer Engineering. Technical Report CENG 89-19. University of Southern California, May 1989. Google ScholarDigital Library
- ShS88 D. SHASHA and M. SNIR. Efficient and Correct Execution of Parallel Programs that Share Memory, ACM Trans. on Programming Languages and Systems 10, 2 (April 1988), 282- 312. Google ScholarDigital Library
Index Terms
- Weak ordering—a new definition
Recommendations
Weak ordering—a new definition
ISCA '90: Proceedings of the 17th annual international symposium on Computer ArchitectureA memory model for a shared memory, multiprocessor commonly and often implicitly assumed by programmers is that of sequential consistency. This model guarantees that all memory accesses will appear to execute atomically and in program order. An ...
A Unified Formalization of Four Shared-Memory Models
The authors present a data-race-free-1, shared-memory model that unifies four earliermodels: weak ordering, release consistency (with sequentially consistent specialoperations), the VAX memory model, and data-race-free-0. Data-race-free-1 unifies ...
Weak ordering—a new definition
ISCA '98: 25 years of the international symposia on Computer architecture (selected papers)
Comments