Scheduling system of affine recurrence equations by means of piecewise affine timing functions Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/mw22v9223

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • 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.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using ScandAll PRO 1.8.1 on a Fi-6770A in PDF format. CVista PdfCompressor 5.0 was used for pdf compression and textual OCR.
Replaces
Additional Information
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-02-08T21:10:57Z (GMT) No. of bitstreams: 1 MuiLapK1992.pdf: 1440679 bytes, checksum: 28cb6a82fc99b0f63ba0507b5783e3da (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-03-05T20:44:10Z (GMT) No. of bitstreams: 1 MuiLapK1992.pdf: 1440679 bytes, checksum: 28cb6a82fc99b0f63ba0507b5783e3da (MD5)
  • description.provenance : Submitted by Kaylee Patterson (kdpscanner@gmail.com) on 2013-02-08T20:59:22Z No. of bitstreams: 1 MuiLapK1992.pdf: 1440679 bytes, checksum: 28cb6a82fc99b0f63ba0507b5783e3da (MD5)
  • description.provenance : Made available in DSpace on 2013-03-05T20:44:10Z (GMT). No. of bitstreams: 1 MuiLapK1992.pdf: 1440679 bytes, checksum: 28cb6a82fc99b0f63ba0507b5783e3da (MD5) Previous issue date: 1992-03-05

Relationships

In Administrative Set:
Last modified: 08/20/2017

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items