DOC PREVIEW
Berkeley COMPSCI 258 - Memory Consistency and Event Ordering in Scalable Shared-Memory Multiprocessors

This preview shows page 1-2-3-4 out of 12 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Memory Consistency and Event Ordering in Scalable Shared-Memory Multiprocessors Kourosh Gharachorloo, Daniel Lenoski, James Laudon, Phillip Gibbons, Anoop Gupta, and John Hennessy Computer Systems Laboratory Stanford University, CA 94305 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 opti- mizations can cause memory accesses to be executed in an order different from what the programmer expects. The set of allow- able 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 order- ing 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 architec- tures. 1 Introduction Serial computers present a simple and intuitive model of the memory system to the programmer. A load operation returns the last value written to a given memory location. Likewise, a store operation binds the value that will be returned by sub- sequent loads until the next store to the same location. This simple model lends itself to efficient implementations uniprocessors use caches, write buffers, interleaved main mem- ory, and exploit pipelining techniques. The accesses may even be issued and completed out of order as long as the hardware and compiler ensure that data and control dependences are re- spected. For multiprocessors, however, neither the memory system model nor the implementation is as straightforward. The mem- ory system model is more complex because the definitions of “last value written”, “subsequent loads”, and “next store” be- come unclear when there are multiple processors reading and writing a location. Furthermore, the order in which shared mem- ory operations are done by one process may be used by other processes to achieve implicit synchronization. For example, a process may set a flag variable to indicate that a data structure it was manipulating earlier is now in a consistent state. Con- sistency models place specific requirements on the order that shared memory accesses (events) from one process may be ob- served by other processes in the machine. More generally, the consistency model specifies what event orderings are legal when several processes are accessing a common set of locations. Several memory consistency models have been proposed in the literature: examples include sequential consistency 171, pro- cessor consistency [5], and weak consistency [4J. The sequen- tial consistency model [7] requires the execution of a parallel program to appear as some interleaving of the execution of the parallel processes on a sequential machine. While conceptually simple, the sequential consistency model imposes severe restric- tions on the outstanding accesses that a process may have and effectively prohibits many hardware optimizations that could increase performance. Other models attempt to relax the con- straints on the allowable event orderings, while still providing a reasonable programming model for the programmer. Architectural optimizations that reduce memory latency are. especially important for scalable multiprocessor architectures. As a result of the distributed memory and general interconnec- tion networks used by such multiprocessors [8, 9, 121, requests issued by a processor to distinct memory modules may execute out of order. Caching of data further complicates the ordering of accesses by introducing multiple copies of the same location. While memory accesses are atomic in systems with a single copy of data (a new data value becomes visible to all proces- sors at the same time), such atomicity may not be present in cache-based systems. The lack of atomicity introduces extra complexity in implementing consistency models. A system w- chitect must balance the design by providing a memory consis- tency model that allows for high performance implementations and is acceptable to the programmer. In this paper, we present a new consistency model called release consistency, which extends the weak consistency model [4] by utilizing additional information about shared ac- cesses. Section 2 presents a brief overview of previously pro- posed consistency models. The motivation and framework for release consistency is presented in Section 3. Section 4 con- siders equivalences among the several models given proper in- formation about shared accesses. Section 5 discusses potential performance gains for the models with relaxed constraints. Fi- nally, Section 6 discusses implementation issues, focusing on issues relevant to scalable architectures. CH2887-8/90/0000/0015$01.00 0 1990 IEEE 152 Previously Proposed Memory Consis- tency Models In this section, we present event ordering requirements for sup- porting the sequential, processor, and we& consistency models. Although the models discussed in this section have already been presented in the literature,, we discuss them here for purposes of completeness, uniformity in terminology, and later compari- son. Readers familiar with the first three models and the event ordering terminology may wish to skip to Section 3. To facilitate the description of different event


View Full Document

Berkeley COMPSCI 258 - Memory Consistency and Event Ordering in Scalable Shared-Memory Multiprocessors

Documents in this Course
Load more
Download Memory Consistency and Event Ordering in Scalable Shared-Memory Multiprocessors
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Memory Consistency and Event Ordering in Scalable Shared-Memory Multiprocessors and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Memory Consistency and Event Ordering in Scalable Shared-Memory Multiprocessors 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?