Master of Science (MS)
First Committee Member
Jan B. Pedersen
Number of Pages
Message passing applications that perform asynchronous communication need sufficient buffer space to hold all undelivered messages, or else the applications may deadlock. Determining the minimum amount of buffer space an application needs is called the Buffer Allocation Problem, and has been shown to be intractable [BPW]. However, an epoch based polynomial-time algorithm that approximates the Buffer Allocation Problem has been proposed by Pedersen et al. [PBS]. The algorithm partitions application executions into epochs and intersperses barrier synchronizations between them, thus limiting the number of message buffers necessary to ensure deadlock-freedom; In this thesis, we describe an implementation of the epoch based algorithm. Our implementation analyzes and performs barrier synchronizations for MPI (Message Passing Interface) applications. We use a modified version of MPI to gather information about the messages sent during the execution, and then use a standalone Java program to analyze the protocol (communication structure) and build a graph which serves as the foundation for the computation of barrier synchronizations. We then pass this information to MPI, making it available for automatic barrier synchronization. Finally, we present the results of an empirical study of various applications implemented to test our approximation algorithm.
Allocation; Buffer; Implementation; Message; Mpi; Passing; System
University of Nevada, Las Vegas
If you are the rightful copyright holder of this dissertation or thesis and wish to have the full text removed from Digital Scholarship@UNLV, please submit a request to firstname.lastname@example.org and include clear identification of the work, preferably with URL.
Sampson, Jeffrey, "Buffer allocation in message passing systems: An implementation for Mpi" (2007). UNLV Retrospective Theses & Dissertations. 2265.