Show simple item record

dc.contributor.advisorJiménez-Cedeño, Manuel
dc.contributor.authorArce-Nazario, Rafael A.
dc.date.accessioned2019-02-12T15:30:46Z
dc.date.available2019-02-12T15:30:46Z
dc.date.issued2007
dc.identifier.urihttps://hdl.handle.net/20.500.11801/1790
dc.description.abstractDiscrete signal transforms (DSTs) have numerous applications in a wide spectrum of scientific fields. To attain superior performance, the size and composition of these algorithms frequently require implementation to architectures involving more than one dedicated hardware device. Even though hardware implementations of signal processing algorithms are known to be orders of magnitude faster than most other generic computing platforms, they are not commonplace mainly because of the increased complexity involved in partitioning and mapping such algorithms onto distributed hardware platforms. Automated methods and tools to aid in the design and exploration of distributed implementations shall encourage adoption of dedicated hardware platforms for high-performance applications. Traditionally, partitioning to distributed hardware architectures (DHAs) has been done either manually, or at various stages of the design process, predominantly at the behavioral and structural levels. Although these schemes have produced acceptable implementations, they do not necessarily exploit the functional properties of algorithms. Structural level techniques handle the design at an abstraction level too low for the algorithm functionality to be effectively interpreted. Most proposed higher-level strategies target generic partitioning problems through local optimization techniques, which miss out on alternate formulations that become apparent only on a higher level of abstraction. This dissertation presents an automated methodology specifically designed for partitioning DSTs onto DHAs. The methodology takes advantage of DST features at two levels of abstraction: the graph and algorithmic levels. At the algorithmic level, an exploration is conducted in search of equivalent transform formulations that are more suitable for the target topology. At the graph level, a series of DSTspecific structural considerations are made to improve the partitioning heuristic. The developed strategy integrates several algorithms which allow exploring partitioning solutions at both abstraction levels. A Kronecker products algebra (KPA) to dataflow graph conversion (DFG) tool was developed to allow straightforward conversion and structural visualization of KPA expressed formulations. The DFG generated by this tool is partitioned using a k-way deterministic algorithm with structural considerations derived from common DST features. A scheduler estimates latency of the partition solution, constrained by the available computational resources, as determined by an area estimator. Solution cost at the graph level is used to transform the current DST formulation, and thus explore alternative formulations as part of the partition optimization process. Given the exponential size of the space of equivalent formulations, a greedy, polynomialtime exploration heuristic was designed. Results from the application of this methodology to a range of sizes of Discrete Fourier Transforms and Discrete Cosine Transforms evidence the advantages of making the partition methodology DST-aware. Latency and run-time reductions of up to 34% and 99%, respectively were obtained with respect to previously proposed, stochastic high-level partitioning approaches.en_US
dc.language.isoEnglishen_US
dc.subjectHigh level partitioningen_US
dc.subjectDiscrete signal transformsen_US
dc.titleHigh-level partitioning of discrete signal transforms for distributed hardware architectures en_US
dc.typeDissertationen_US
dc.rights.licenseAll rights reserveden_US
dc.rights.holder(c) 2007 Rafael A. Arce Nazarioen_US
dc.contributor.committeeBollman, Dorothy
dc.contributor.committeePalomera, Rogelio
dc.contributor.committeeCouvertier, Isidoro
dc.contributor.committeeRodriguez, Domingo
dc.contributor.representativeRamirez, Nazario
thesis.degree.levelPh.D.en_US
thesis.degree.disciplineComputing and Information Sciences and Engineeringen_US
dc.contributor.collegeCollege of Engineeringen_US
dc.contributor.departmentDepartment of Electrical and Computer Engineeringen_US
dc.description.graduationSemesterSummeren_US
dc.description.graduationYear2007en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

  • Theses & Dissertations
    Items included under this collection are theses, dissertations, and project reports submitted as a requirement for completing a degree at UPR-Mayagüez.

Show simple item record

All rights reserved
Except where otherwise noted, this item's license is described as All Rights Reserved