mirage   mirage   mirage

Mapping of recursive algorithms onto multi-rate arrays

DSpace/Manakin Repository

Show simple item record

dc.contributor.advisor Kiaei, Sayfe
dc.creator Zheng, Yue-Peng
dc.date.accessioned 2012-11-08T19:13:12Z
dc.date.available 2012-11-08T19:13:12Z
dc.date.copyright 1994-05-27
dc.date.issued 1994-05-27
dc.identifier.uri http://hdl.handle.net/1957/34997
dc.description Graduation date: 1995 en_US
dc.description.abstract In this dissertation, multi-rate array (MRA) architecture and its synthesis are proposed and developed. Using multi-coordinate systems (MCS), a unified theory for mapping algorithms from their original algorithmic specifications onto multi-rate arrays is developed. A multi-rate array is a grid of processors in which each interconnection may have its own clock rate; operations with different complexities run at their own clock rate, thus increasing the throughput and efficiency. A class of algorithms named directional affine recurrence equations (DARE) is defined. The dependence space of a DARE can be decomposed into uniform and non-uniform subspaces. When projected along the non-uniform subspace, the resultant array structure is regular. Limitations and restrictions of this approach are investigated and a procedure for mapping DARE onto MRA is developed. To generalize this approach, synthesis theory is developed with initial specification as affine direct input output (ADIO) which aims at removing redundancies from algorithms. Most ADIO specifications are the original algorithmic specifications. A multi-coordinate systems (MCS) is used to present an algorithm's dependence structures. In a MCS system, the index spaces of the variables in an algorithm are defined relative to their own coordinate systems. Most traditionally considered irregular algorithms present regular dependence structures under MCS technique. Procedures are provided for transforming algorithms from original algorithmic specifications to their regular specifications. Multi-rate schedules and multi-rate timing functions are studied. The solution for multi-rate timing functions can be formulated as linear programming problems. Procedures are provided for mapping ADIOs onto multi-rate VLSI systems. Examples are provided to illustrate the synthesis of MRAs from DAREs and ADIOs. The first major contribution of this dissertation is the development of the concrete, executable MRA architectures. The second is the introduction of MCS system and its application in the development of the theory for synthesizing MRAs from original algorithmic specifications. en_US
dc.language.iso en_US en_US
dc.subject.lcsh Integrated circuits -- Very large scale integration en_US
dc.subject.lcsh Recursive functions en_US
dc.title Mapping of recursive algorithms onto multi-rate arrays en_US
dc.type Thesis/Dissertation en_US
dc.degree.name Doctor of Philosophy (Ph. D.) in Electrical and Computer Engineering en_US
dc.degree.level Doctoral en_US
dc.degree.discipline Engineering en_US
dc.degree.grantor Oregon State University en_US
dc.description.digitization File scanned at 300 ppi (Monochrome, 256 Grayscale) using Capture Perfect 3.0 on a Canon DR-9050C in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR. en_US
dc.description.peerreview no en_us

This item appears in the following Collection(s)

Show simple item record

Search ScholarsArchive@OSU

Advanced Search


My Account