Performance of barrier synchronization methods in a multi-access network

Barrier synchronization is a commonly used primitive in parallel processing, but has traditionally been implemented only on hardware multiprocessors. With the growing interest in concurrent computing on general purpose networks, it is worthwhile investigating methods for implementing barriers in such environments. We present different algorithms for barrier synchronization on the widely prevalent multi-access bus network, and derive analytical performance metrics for each of the proposed schemes, which are then compared against simulation results. Our findings indicate that algorithms originally developed for dedicated interconnection networks perform fairly well in shared bus networks with some modifications, and interestingly that the best performance is obtained with a dimensional exchange algorithm