Efficient Scheduling of Complete Exchange on Clusters

In this paper, we focus on the practical issues of designing efficient complete exchange algorithms on a commodity cluster interconnected by a non-blocking crossbar switch. Four complete exchange algorithms, including, shift exchange, pairwise exchange, group shuffle exchange and synchronous shuffle exchange algorithms are studied and tested on a cluster platform. These algorithms feature their own communication schedule to avoid node and switch contention so as to fully utilize the available bandwidth. Both the analytical and measured results show that the synchronous shue exchange algorithm can achieve the best performance. It can reach 97 % of the available bandwidth in our tests; while the group shuffle exchange performs almost as good as the synchronous shuffle exchange algorithm but scales better under the Head-Of-Line phenomenon. Performance studies of the four algorithms on both input-buffered and shared-buffered switches are also reported