Efficient and correct execution of parallel programs that share memory
- 1 April 1988
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 10 (2), 282-312
- https://doi.org/10.1145/42190.42277
Abstract
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.Keywords
This publication has 8 references indexed in Scilit:
- Advanced compiler optimizations for supercomputersCommunications of the ACM, 1986
- On interprocess communicationDistributed Computing, 1986
- The NYU Ultracomputer—Designing an MIMD Shared Memory Parallel ComputerIEEE Transactions on Computers, 1983
- On describing the behavior and implementation of distributed systemsTheoretical Computer Science, 1981
- Concurrency Control in Distributed Database SystemsACM Computing Surveys, 1981
- Concurrency control in a system for distributed databases (SDD-1)ACM Transactions on Database Systems, 1980
- How to Make a Multiprocessor Computer That Correctly Executes Multiprocess ProgramsIEEE Transactions on Computers, 1979
- Time, clocks, and the ordering of events in a distributed systemCommunications of the ACM, 1978