Efficient and correct execution of parallel programs that share memory
Dennis E. Shasha, Marc Snir · ACM Transactions on Programming Languages and Systems · 1988
In this paper we consider an optimization problem that arises in the execution of parallel programs on shared-memory multiple-instruction-stream, multiple-data-stream (MIMD) computers. A program on such machines consists of many sequential program segments, each executed by a single processor. These segments interact as they access shared variables. Access to memory is asynchronous, and memory accesses are not necessarily executed in the order they were issued. An execution is correct if it is sequentially consistent: It should seem as if all the instructions were executed sequentially, in an order obtained by interleaving the instruction streams of the processors. Sequential consistency can be enforced by delaying each access to shared memory until the previous access of the same processor has terminated. For performance reasons, however, we want to allow several accesses by the same processor to proceed concurrently. Our analysis finds a minimal set of delays that enforces sequential consistency. The analysis extends to interprocessor synchronization constraints and to code where blocks of operations have to execute atomically. We use a conflict graph similar to that used to schedule transactions in distributed databases. Our graph incorporates the order on operations given by the program text, enabling us to do without locks even when database conflict graphs would suggest that locks are necessary. Our work has implications for the design of multiprocessors; it offers new compiler optimization techniques for parallel languages that support shared variables.
Cited by 417 works. doi:10.1145/42190.42277 Open-access PDF
Authors
References
- Time, clocks, and the ordering of events in a distributed system
- Compilers: Principles, Techniques, and Tools
- How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs
- Concurrency Control in Distributed Database Systems
- The NYU Ultracomputer—Designing an MIMD Shared Memory Parallel Computer
- The IBM Research Parallel Processor Prototype (RP3): Introduction and Architecture.
- Automatic translation of FORTRAN programs to vector form
- On interprocess communication
- Advanced compiler optimizations for supercomputers
- Concurrency control in a system for distributed databases (SDD-1)