2011 | OriginalPaper | Buchkapitel
Contention-Free Many-to-Many Communication Scheduling for High Performance Clusters
verfasst von : Satyajit Banerjee, Atish Datta Chowdhury, Koushik Sinha, Subhas Kumar Ghosh
Erschienen in: Distributed Computing and Internet Technology
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 requests 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 algorithm 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 factor of 2
H
2Δ− 1
, where |
E
| is the number of edges in the bipartite graph, Δ is the maximum node degree of the bipartite graph and
H
2Δ− 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 eliminate 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 4log(
w
max
) and has a worst case run time of
O
(Δ|
E
|log(
w
max
)), where
w
max
represents the longest communication time in a set of received requests.