Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(10)
Approximate Algorithm
Best Approximation
Bipartite Graph
Cluster Computing
Communication Scheduling
Data Center
Data Transfer
Harmonic Number
High Performance
Scheduling Algorithm
Subscribe
Academic
Publications
ContentionFree ManytoMany Communication Scheduling for High Performance Clusters
ContentionFree ManytoMany Communication Scheduling for High Performance Clusters,10.1007/9783642190568_10,Satyajit Banerjee,Atish Datta Chowdhu
Edit
ContentionFree ManytoMany Communication Scheduling for High Performance Clusters
BibTex

RIS

RefWorks
Download
Satyajit Banerjee
,
Atish Datta Chowdhury
,
Koushik Sinha
,
Subhas Kumar Ghosh
In the context of generating efficient, contention free schedules for internode communication through a switch fabric in
cluster computing
or
data center
type environments, alltoall 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 manytomany 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, Elog(E))) and guarantees an approximation factor of 2H 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(E2) 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(ΔElog(w max )), where w max represents the longest communication time in a set of received requests.
Conference:
Distributed Computing and Internet Technology  ICDCIT
, pp. 150161, 2011
DOI:
10.1007/9783642190568_10
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
More »
References
(13)
Bandwidth Efficient AlltoAll Broadcast on Switched Clusters
(
Citations: 14
)
Ahmad Faraj
,
Pitch Patarasuk
,
Xin Yuan
Conference:
Cluster Computing  CLUSTER
, pp. 110, 2005
Efficient ManytoMany RealTime Communication Using an Intelligent Ethernet Switch
(
Citations: 2
)
Xing Fan
,
Magnus Jonsson
,
Hoai Hoang
Conference:
International Symposium on Parallel Architectures, Algorithms and Networks  ISPAN
, pp. 280287, 2004
ContentionAware Communication Schedule for HighSpeed Communication
(
Citations: 9
)
Anthony T. C. Tam
,
Choli Wang
Journal:
Cluster Computing  CLUSTER
, vol. 6, no. 4, pp. 339353, 2003
Optimal AlltoAll Personalized Exchange in SelfRoutable Multistage Networks
(
Citations: 25
)
Yuanyuan Yang
,
Jianchao Wang
Journal:
IEEE Transactions on Parallel and Distributed Systems  TPDS
, vol. 11, no. 3, pp. 261274, 2000
Switch Scheduling via Randomized Edge Coloring
(
Citations: 7
)
Gagan Aggarwal
,
Rajeev Motwani
,
Devavrat Shah
,
An Zhu
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 502512, 2003