Files in this item



application/pdf9305543.pdf (7MB)Restricted to U of Illinois
(no description provided)PDF


Title:Automatic Data Partitioning on Distributed Memory Multicomputers
Author(s):Gupta, Manish
Doctoral Committee Chair(s):Banerjee, Prithviraj
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computer Science
Abstract:Distributed-memory parallel computers are increasingly being used to provide high levels of performance for scientific applications. Unfortunately, such machines are not very easy to program. A number of research efforts seek to alleviate this problem by developing compilers that take over the task of generating communication. The communication overheads and the extent of parallelism exploited in the resulting target program are determined largely by the manner in which data is partitioned across different processors of the machine. Most of the compilers provide no assistance to the programmer in the crucial task of determining a good data partitioning scheme.
This thesis presents a novel approach, the constraint-based approach, to the problem of automatic data partitioning for numeric programs. In this approach, the compiler identifies some desirable requirements on the distribution of various arrays being referenced in each statement based on performance considerations. These desirable requirements are referred to as constraints. For each constraint, the compiler determines a quality measure that captures its importance with respect to the performance of the program. The quality measure is obtained through static performance estimation, without actually generating the target data-parallel program with explicit communication. Each data distribution decision is taken by combining all the relevant constraints. The compiler attempts to resolve any conflicts between constraints such that the overall execution time of the parallel program is minimized.
This approach has been implemented as part of a compiler called P scARADIGM, that accepts Fortran 77 programs, and specifies the partitioning scheme to be used for each array in the program. We have obtained results on some programs taken from the Linpack and Eispack libraries, and the Perfect Benchmarks. These results are quite promising, and demonstrate the feasibility of automatic data partitioning for a significant class of scientific application programs with regular computations.
Issue Date:1992
Description:160 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1992.
Other Identifier(s):(UMI)AAI9305543
Date Available in IDEALS:2014-12-17
Date Deposited:1992

This item appears in the following Collection(s)

Item Statistics