A-MPI : supporting MPI on a nondedicated cluster of workstations

by (Daniel Brent), 1970- Weatherly

Distributing data is one of the fundamental problems in implementing efficient distributed-memory parallel programs. The problem becomes more difficult in environments where the participating nodes (processors) are not dedicated to a parallel application. Such environments increase the difficulty of the data distribution problem, which is to determine an assignment of data elements to each node to minimize completion time. We are investigating this problem in the context of explicit message-passing programs. We have designed and implemented an extension to the popular Message Passing Interface (MPI) that efficiently supports adaptive programs by providing the necessary infrastructure to redistribute data dynamically. Our system, called the Adaptive Message Passing Interface (A-MPI), contributes (1) an efficient memory allocation mechanism, (2) techniques for accurately determining system load and computation time, and (3) a heuristic for determining efficient data distributions, including the removal of nodes whose participation degrades the performance of an application. Performance results show that programs that use A-MPI can produce significant improvements over previous load-balancing systems. Index words: Load Balancing, MPI, Data Distribution, Parallel Programming A-MPI: Supporting MPI on a Nondedicated Cluster of Workstations by D. Brent Weatherly B.S., The University of Georgia, 1994 A.B., The University of Georgia, 1995 A Thesis Submitted to the Graduate Faculty of The University of Georgia in Partial Fulfillment of the Requirements for the Degree Master of Science Athens, Georgia 2002 c? 2002 D. Brent Weatherly All Rights Reserved A-MPI: Supporting MPI on a Nondedicated Cluster of Workstations by D. Brent Weatherly Approved: Major Professor: David Lowenthal Committee: John Miller Eileen Kraemer Electronic Version Approved: Gordhan L. Patel Dean of the Graduate School The University of Georgia August 2002