Many systematic methods exist for mapping algorithms to processor arrays. The
algorithm is usually specified as a set of recurrence equations, and the processor arrays
are synthesized by finding timing and allocation functions which transform index points
in the recurrences into points in a space-time domain.
The problem of scheduling (i.e. finding the timing function) of recurrence equations
has been studied by a number of researchers. Of particular interest here are Systems of
Affine Recurrence Equations (SAREs). The existing methods are limited to affine (or
linear) schedules over the entire domain of computation. For some algorithms, there are
points in the computation domain where the dependencies point in opposite directions,
and an affine schedule does not exist, although a valid Piecewise Affine Schedule (PAS)
can exist. The objective of this thesis is to examine these schedules and obtain a
systematic method for deriving such schedules for SAREs. PAS can be found by first
partitioning the computation domain and then obtaining a new SARE by renaming the
variables. By partitioning the computation domain, we can obtain additional parallelism
from the dependency graph, and find faster schedules over subspaces of the domain. In
this paper, we describe a procedure for partitioning the domain and to generate a new
SARE by renaming the variables. Some heuristics are introduced for partitioning the
domain based on the properties of dependence vectors. After the partitioning and
renaming, an existing method (due to Mauras et al.) is applied to find the schedules.
Examples of Toeplitz System and Algebraic Path Problem are used to illustrate the results. / Graduation date: 1992
| Identifer | oai:union.ndltd.org:ORGSU/oai:ir.library.oregonstate.edu:1957/37328 |
| Date | 05 March 1992 |
| Creators | Mui, Lap K. |
| Contributors | Kiaei, Sayfe |
| Source Sets | Oregon State University |
| Language | en_US |
| Detected Language | English |
| Type | Thesis/Dissertation |
Page generated in 0.0016 seconds