Multiprocessors should support simple memory consistency models

Many future computers will be shared-memory multiprocessors. These hardware systems must define for software the allowable behavior of memory. A reasonable model is sequential consistency (SC), which makes a shared memory multiprocessor behave like a multi

To Appear in IEEE Computer

Multiprocessors Should Support Simple Memory Consistency Models

Mark D. Hill

Computer Sciences DepartmentUniversity of Wisconsin–Madison

1210 West Dayton St.Madison, WI 53706 USA

doc.xuehai.net

Abstract

Many future computers will be shared-memory multiprocessors.These hardware systems must de ne for software the allowablebehavior of memory. A reasonable model is sequential consis-tency (SC), which makes a shared memory multiprocessor behavelike a multiprogrammed uniprocessor. Since SC appears to limitsome of the optimizations useful for aggressive hardware imple-mentations, researchers and practitioners have de ned severalrelaxed consistency models. Some of these models just relax theordering from writes to reads (processor consistency, IBM 370,Intel Pentium Pro, and Sun TSO), while others aggressively relaxthe order among all normal reads and writes (weak ordering,release consistency, DEC Alpha, IBM PowerPC, and Sun RMO).This paper argues that multiprocessors should implement SCor, in some cases, a model that just relaxes the ordering fromwrites to reads. I argue against using aggressively relaxed modelsbecause, with the advent of speculative execution, these modelsdo not give a suf cient performance boost to justify exposing theircomplexity to the authors of low-level software.

Keywords: multiprocessors, parallel computing, shared mem-ory, memory consistency models.

1 Introduction

Many future computers will contain multiple proces-sors, in part, because the marginal cost of adding a fewadditional processors is so low that only minimal perfor-mance gain is needed to make the additional processorscost-effective [11]. Intel, for example, now makes cardscontaining four Pentium Pro processors that can easily beincorporated into a system. Multiple-processor cards willhelp multiprocessing spread from servers to the desktop.

How will these multiprocessors be programmed? Theevolution that has already begun is likely to continue. First,multiprocessors are used for multiprogramming, whereconventional single-threaded programs are multiplexed onthe processors. Next, performance-critical parts of com-pute-intensive applications will be parallelized by expertprogrammers to use multiple threads sharing data throughshared memory. When one game vendor, for example, par-allelizes and obtains a performance advantage, competitorswill rapidly follow suit. Finally, someday we may be ableto build compilers that can effectively parallelize mostsequential programs or provide tools and abstractions thatallow many people to program in parallel.

What hardware is needed to support threads with sharedmemory? First, the hardware should provide a well-de nedinterface for shared memory. Second, it should provide ahigh-performanceimplementation of the interface.

De ning a shared-memory multiprocessor’s interface tomemory is easier if we rst consider a uniprocessor. A uni-processor executes instructions and memory operations ina dynamic execution order calledprogram order. Simpleprocessors actually execute operations in program orderwhile complex processors only appear to do so. In eithercase, each read must return the value of the last write to thesame address, wherelast is uniquely de ned by programorder. If the uniprocessor is multiprogrammed, two casesexist. If a program executes as a single thread without shar-ing memory, then the programmer’s memory interface isthe same as for a uniprocessor without multiprogramming.The situation is more complex, on the other hand, if a pro-gram has multiple threads sharing memory (or the programshares memory with other running programs or is the oper-ating system). In this case, thelast write to an addresscould be by itself (the same thread) or by another thread(that was context switched onto the processor since thisthread’s last write to the address). In most cases, softwareuses synchronization to make program results meaningful.Programmers can model a multiprogrammed uniproces-sor as a merging of the program order of each executingthread into a single total order of processor execution. Mostprogrammers, for example, would expect the code frag-

第1页下一页