| Abstract: | Parallel algorithms that use shared resources are notoriously difficult to write and verify, especially when properties such as fairness and efficiency are desired. This paper introduces a new synchronization method called the group lock. This method has some of the advantages of strict synchronization methods such as monitors; algorithms written using group lock are quite clear and easy to verify. At the same time, these algorithms generally make better use of parallelism than those written using stricter synchronization methods. In many cases we can obtain worst case time bounds that are constant or logarithmic in the number of processes, thus also insuring bounded fairness. The paper begins with a discussion of related synchronization methods and an introduction to the group lock. This is followed by some examples of applications in algorithms for a readers/writers problem, parallel stacks and queues, implementation of fetch- and-phi routines, and others. Finally, two implementations of group lock are described. A detailed implementation is given for the paracomputer, an idealized MIMD multiprocessor that supports the fetch-and-add synchronization instruction. An implementation is also outlined for general CREW multiprocessors using only reads and writes to shared memory. |
