GLOBAL SYNCHRONIZATION ALGORITHMS FOR THE INTEL IPSC/860

In a distributed memory multicomputer that has no global clock, global processor synchronization can only be achieved through software. Global synchronization is used in many applications, including tridiagonal systems solvers, CFD codes, and sequence comparison algorithms. For the Intel iPSC/860 in particular, global synchronization can also be used to ensure the most effective use of the communication network. Two global synchronization algorithms are considered for the iPSC/860: The gsync primitive provided by Intel and the RDS algorithm. Based on the communication model presented here, it is shown that gsync sometimes leaves the processors more poorly synchronized than they were to begin with. It is also shown that interrupts from the node operating system can cause gsync to contend for communication ports with the application code. The RDS algorithm does not have these shortcomings and costs only slightly more than the other algorithms. Measurements of the cost of message shift operations preceded by global synchronization confirm that the RDS algorithm always synchronizes the nodes more precisely than gsync.