On multiprocessor synchronization and data transfer

Abstract

Interprocessor communication has been one of the major overheads in parallel processing. Although synchronization and data transfer are two related activities associated with interprocessor communication, most previous approaches dealt only with synchronization. This thesis studies the issues in interprocessor communication. Experimental data on parallelism of application programs using an oracle-guided simulator confirm the importance of interprocessor communication. Direct communication with static message-passing, which integrates synchronization and data transfer, is proposed as a basic mechanism to implement efficient interprocessor communication on distributed shared memory multiprocessors for critical region synchronization, a family of information dissemination algorithms (such as data spreading and dissemination barriers), and Doacross loops. The mechanism is able to remove three major interprocessor communication overheads, namely, processor stall, remote busy-waiting, and remote reads. Algorithms for the critical region synchronization and information dissemination are given with correctness proofs and timing analysis. Compiler algorithms are proposed to transform sequential loops into Doacross loops using the above mechanism. Also included in this thesis is a Doacross synchronization scheme which can handle complex cross-iteration dependences easily, and is suitable for bus-based systems. Experiments on the proposed schemes and the previous schemes by detailed interpretation-driven simulation are used to show the merits of proposed schemes.