Contention-free Many-to-many Communication Scheduling for High Performance Clusters

Abstract. In the context of generating efficient, contention free schedules for inter-node communication through a switch fabric in cluster computing or data center type environments, all-to-all scheduling with equal sized data transfer re-quests has been studied in the literature [1, 3, 4]. In this paper, we propose a communication scheduling module (CSM) towards generating contention free communication schedules for many-to-many communication with arbitrary sized data. Towards this end, we propose three approximation algorithms- PST, LDT and SDT. From time to time, the CSM first generates a bipartite graph from the set of received requests, then determines which of these three algorithms gives the best approximation factor on this graph and finally executes that al-gorithm to generate a contention free schedule. Algorithm PST has a worst case run time of O(max (∆|E|, |E | log (|E|))) and guarantees an approximation fac-tor of 2H2∆−1, where |E | is the number of edges in the bipartite graph, ∆ is the maximum node degree of the bipartite graph and H2∆−1 is the (2 ∆ − 1)-th harmonic number. LDT runs in O(|E|2) and has an approximation factor of 2(1 + τ), where τ is a constant defined as a guard band or pause time to elim-inate the possibility of contention (in an apparently contention free schedule) caused by system jitter and synchronization inaccuracies between the nodes. SDT gives an approximation factor of 4 log (wmax) and has a worst case run time of O(∆|E | log (wmax)), where wmax represents the longest communication time in a set of received requests