Record Details

One To Mant And Many To Many Collective Communication Operations On Grids

Electronic Theses of Indian Institute of Science

View Archive Info
 
 
Field Value
 
Title One To Mant And Many To Many Collective Communication Operations On Grids
 
Creator Gupta, Rakhi
 
Subject Collective Communication Operations
Grid System (Electrical Communication Engineering)
Message Passing Interface
Grid Networks
Grids
MPI
Allgather - Algorithms
One-To-Many Collective Communication
Many-To-Many Collective Communication
Computer Science
 
Description Collective Communication Operations are widely used in MPI applications and play an important role in their performance. Hence, various projects have focused on optimization of collective communications for various kinds of parallel computing environments including LAN settings, heterogeneous networks and most recently Grid systems. The distinguishing factor of Grids from all the other environments is heterogeneity of hosts and network, and dynamically changing resource characteristics including load and availability.
The first part of the thesis develops a solution for MPI broadcast (one-to-many) on Grids. Some current strategies take into consideration static information about network topology for determining an efficient broadcast tree for Grids. Some other strategies take into account only transient network characteristics. We combined both these strategies and cluster the network dynamically on the basis of link bandwidths. Given a set of network parameters we use Simulated Annealing (SA) to obtain the best schedule. Also, we can time tune individual. SAs, to adapt the solution finding process, on the basis of estimated available times before next broadcast invocations in the application. We also developed software architecture for updation of schedules. We compared our algorithm with the earlier approaches under loaded network conditions, and obtained average performance improvement of 20%.
The second part of the thesis extends the work for MPI all gather (many-to-many) operation. Current popular techniques consider strict hierarchical schemes for this operation, wherein from each cluster a representative (or coordinator) node is chosen, and inter cluster communication is done through these representative nodes. This is non optimal as inter cluster communication is usually on high capacity links that can sustain more than one transfer with the same through- put. We developed a cluster based and incremental heuristic algorithm for allgather on Grids.
We compared the time taken by allgather schedules determined by this algorithm with current popular implementations. We also compared our algorithm with a strategy where allgather is constructed from a set of broadcast trees. We obtained average performance improvement of 67% over existing strategies.
 
Contributor Vadhiyar, Sathish S
 
Date 2008-01-16T09:47:38Z
2008-01-16T09:47:38Z
2008-01-16T09:47:38Z
2006-12
 
Type Thesis
 
Identifier http://hdl.handle.net/2005/345
 
Language en_US
 
Rights I grant Indian Institute of Science the right to archive and to make available my thesis or dissertation in whole or in part in all forms of media, now hereafter known. I retain all proprietary rights, such as patent rights. I also retain the right to use in future works (such as articles or books) all or part of this thesis or dissertation.