Synchronization Primitives for Parallel Processing

In the parallel computing environment, there exists few standards upon which parallel processing machines and models are built. This thesis develops a set of synchronization primitives that can be used as a synchronization standard. These primitives have been designed to meet the needs of the synchronization mechanisms used in common parallel processing models. The primitives are motivated by those used in HEP (Jordan 1985), the NYU Ultracomputer (Gottlieb 1983}, the Cedar (Zhu and Yew 1984), Dijkstra\u27s P and V operators (Dijkstra 1968), I-structures (Arvind 1987), and Futures (Halstead 1985). Based on these concepts a set of twenty-one synchronization primitives have been designed. These primitives rely upon a one bit tag that records the state of the memory location. The primitives consist of a read, a write and an add, that act dependent or independent of the tag bit. The operations are atomic and can either set or clear the tag bit. A typical operation is a dependent read and clear. A simulator has been created that these primitives have been tested on