Perfectly nested loops : communication and memory reuse for do-across loops
Date
1995
Authors
Zigman, John N
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The expression of problem solutions in a serial form has distinct advantages over
parallel implementations from the programmer's point of view:
1. The thought process involved in constructing a program solution is more
intuitive.
2. The language itself, (eg FORTRAN), can be standard across a large range
of platforms.
Although often under one paradigm one of the above may be true, both are seldom
true simultaneously. Frequently programs which are used to solve scientific or
engineering problems display a high degree of repetitiveness. This regular and
repetitive nature has a high degree of inherent parallelism.
The extraction and exploitation of parallelism from program structures such
as loop nests has been extensively studied. A set of fundamental transforms
form a basis for extracting parallelism. Some of these techniques are: data space
transforms such as array expansion and scalar expansion, loop transformations
such as skewing, reversal, interchange and tiling. Other methods such as ChainBased
Scheduling rely on these techniques.
In this thesis we examine a perfectly nested set of loops, in which some or all
of those loops are Do-ACROSS loops. The loop nest is partitioned by tiling and
the resulting subsets of iterations are not independent. This gives rise to several
issues: 1. Communication:- what messages must be sent and what they actually contain.
2. Data Distribution:- what data is needed by which processor and what data
must be shared. 3. Memory Reuse:- can memory be reused during execution, if so under what
conditions.
These issues are covered and answered by techniques presented in this thesis.
Description
Keywords
Citation
Collections
Source
Type
Thesis (Masters)
Book Title
Entity type
Access Statement
License Rights
Restricted until
Downloads
File
Description