We define a new synchronization primitive for parallel asynchronous computations, the parallel operation. The parallel operation (parop) is a special case of the atomic action. A parop is a set of partially ordered independent operations that appears to be executed indivisibly. Depending on the programming model, each operation is either a message to a process or an access to a shared variable. Operations must be independent in the sense that the process issuing a parop must be able to issue all the operations in the parop before any operation in that parop is executed. The operations in a parop appear to be executed in a single indivisible step even though different operations in the parop may be executed at different nodes. We describe a mechanism, local synchrony, that supports a deadlock-free, fair, and highly concurrent implementation of parops in hardware. Using this mechanism, parops can be implemented without locking. Parops can also be pipelined. Local synchrony supports the sequentially consistent execution of pipelined memory accesses. It is compatible with combining and can be adapted to a wide class of network topologies. Since it requires no global clock or other global arbitration, local synchrony is suitable for implementing parops on distributed as well as tightly coupled systems. The use of parops reduces the need for locks in accessing shared memory or distributed objects. The parop also forms a basis for a more general method for coordinating access to shared memory described in a companion paper.
Note: Abstract extracted from PDF file via OCR
All rights reserved (no additional license for public reuse)
Reynolds, Jr, Craig Williams, and Jr Wagner. "Parallel Operations." University of Virginia Dept. of Computer Science Tech Report (1989).
University of Virginia, Department of Computer Science