Award Date

1-1-2007

Degree Type

Thesis

Degree Name

Master of Science (MS)

Department

Computer Science

First Committee Member

Jan B. Pedersen

Number of Pages

55

Abstract

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.

Keywords

Allocation; Buffer; Implementation; Message; Mpi; Passing; System

Controlled Subject

Computer science

File Format

pdf

File Size

1669.12 KB

Degree Grantor

University of Nevada, Las Vegas

Language

English

Permissions

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 digitalscholarship@unlv.edu and include clear identification of the work, preferably with URL.

Rights

IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/

Download


COinS