Models and parallel programming abstractions for synchronization and communication

Abstract

An approach based on algebraic treatment of programs and advanced transition system operational semantics is described for efficient synchronization  and communication of parallel coarse-grained distributed/shared memory programs. The approach combines compile/run time data flow analysis and buffering techniques and improves communication and synchronization features for these programs. This is accomplished in two ways: 1) construction of a number of semantic models  of data exchanges of increasing power for asynchronous communication in distributed environment, and 2) exploiting user-based specification of shared memory access order, known a priori, by means of synchronization facilities orthogonal to computation part of parallel programs that are more expressive and efficient than barrier-like facilities. Two new programming abstractions, exchange environs and forcing expressions, aimed at reducing communication and synchronization overhead, are elaborated from the theory. The program models constructed give more theoretical insight into the nature of parallelism of computation and communication and have immediate practical influence on parallel programming. Particularly automatic resolution of some classes of communication deadlocks is allowed and enhancement of data parallel paradigm of computation can be provided.