IISc Logo    Title

etd AT Indian Institute of Science >
Centres under the Director (formely kown as Division of Information Sciences) >
Supercomputer Education and Research Centre (serc) >

Please use this identifier to cite or link to this item: http://hdl.handle.net/2005/345

Title: One To Mant And Many To Many Collective Communication Operations On Grids
Authors: Gupta, Rakhi
Advisors: Vadhiyar, Sathish S
Keywords: Collective Communication Operations
Grid System (Electrical Communication Engineering)
Message Passing Interface
Grid Networks
Allgather - Algorithms
One-To-Many Collective Communication
Many-To-Many Collective Communication
Submitted Date: Dec-2006
Abstract: 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.
URI: http://etd.iisc.ernet.in/handle/2005/345
Appears in Collections:Supercomputer Education and Research Centre (serc)

Files in This Item:

File Description SizeFormat
G20932.pdf599.78 kBAdobe PDFView/Open

Items in etd@IISc are protected by copyright, with all rights reserved, unless otherwise indicated.


etd@IISc is a joint service of SERC & IISc Library ||
|| Powered by DSpace || Compliant to OAI-PMH V 2.0 and ETD-MS V 1.01