First Advisor

Michael A. Driscoll

Date of Publication

3-18-1992

Document Type

Thesis

Degree Name

Master of Science (M.S.) in Electrical and Computer Engineering

Department

Electrical Engineering

Language

English

Subjects

Parallel processing (Electronic computers) -- Evaluation, Computer algorithms

DOI

10.15760/etd.6418

Physical Description

1 online resource (2, xi, 71 p.)

Abstract

Mapping an application program to a parallel architecture can be described as a multidimensional optimization problem. To simplify the problem, we divide the overall mapping process into three sequential substeps: partitioning, allocating, and scheduling, with each step using a few details of the program and architecture description. Due to the difficulty in accurately describing the program and architecture and the fact that each substep uses incomplete information, inaccuracy is pervasive in the real-world mapping process. We hypothesize that the inaccuracy and the use of suboptimal, heuristic mapping methods may greatly affect the mapping or submapping performance and lead to a non-optimal solution. We do not discard the typical approach used by most researchers in which total execution time or speedup is the criterion to evaluate the quality of the mapping. However, we improve on this approach by including the effects of inaccuracy. We believe that, due to the presence of inaccuracy in the mapping process, investigating the impact of inaccuracy on the mapping quality is crucial to achieving good mappings. The motivation of this work is to identify the various inaccuracies during the mapping procedure and explore the sensitivity of mapping quality to the inaccurate parameters. To conduct the sensitivity examination, the Global Cluster partitioning algorithm and some models were used. The models use some program and architecture characteristics, or lower-level meters, to characterize the mapping solution space. The algorithm searches the solution space and makes the decision based on the information provided by the models. The experiments were implemented on a UNIX LAN of Sun workstations for different data flow graphs. The graphs use three parallel programming paradigms: fine grained, coarse-grained, and pipelined styles, to represent some high-level application programs: vector inner product calculation, matrix multiplication, and Gaussian elimination respectively. The experimental results show that varying system behavior affects the accuracy of lower-level meters, and the quality of the mapping algorithm is very sensitive to the inaccuracies.

Rights

In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/ This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).

Comments

If you are the rightful copyright holder of this dissertation or thesis and wish to have it removed from the Open Access Collection, please submit a request to pdxscholar@pdx.edu and include clear identification of the work, preferably with URL

Persistent Identifier

https://archives.pdx.edu/ds/psu/26414

Download

Share

COinS