Mutli-objective trade-off exploration for Cyclo-Static and Synchronous Dataflow graphs

dc.contributor.advisorGerstlauer, Andreas, 1970-en
dc.contributor.committeeMemberJohn, Lizy K.en
dc.creatorSinha, Ashmitaen
dc.date.accessioned2012-10-30T19:14:11Zen
dc.date.available2012-10-30T19:14:11Zen
dc.date.issued2012-08en
dc.date.submittedAugust 2012en
dc.date.updated2012-10-30T19:14:22Zen
dc.descriptiontexten
dc.description.abstractMany digital signal processing and real-time streaming systems are modeled using dataflow graphs, such as Synchronous Dataflow (SDF) and Cyclo-static Dataflow (CSDF) graphs that allow static analysis and optimization techniques. However, mapping of such descriptions into tightly constrained real-time implementations requires optimization of resource sharing, buffering and scheduling across a multi-dimensional latency-throughput-area objective space. This requires techniques that can find the Pareto-optimal set of implementations for the designer to choose from. In this work, we address the problem of multi-objective mapping and scheduling of SDF and CSDF graphs onto heterogeneous multi-processor platforms. Building on previous work, this thesis extends existing two-stage hybrid heuristics that combine an evolutionary algorithm with an integer linear programming (ILP) model to jointly optimize throughput, area and latency for SDF graphs. The primary contributions of this work include: (1) extension of the ILP model to support CSDFGs with additional buffer size optimizations; (2) a further optimization in the ILP-based scheduling model to achieve a runtime speedup of almost a factor of 10 compared to the existing SDFG formulation; (3) a list scheduling heuristic that replaces the ILP model in the hybrid heuristic to generate Pareto-optimal solutions at significantly decreased runtime while maintaining near-optimality of the solutions within an acceptable gap of 10% when compared to its ILP counterparts. The list scheduling heuristic presented in this work is based on existing modulo scheduling approaches for software pipelining in the compiler domain, but has been extended by introducing a new concept of mobility-based rescheduling before resorting to backtracking. It has been proved in this work that if mobility-based rescheduling is performed, the number of required backtrackings and hence overall complexity and runtime is less.en
dc.description.departmentElectrical and Computer Engineeringen
dc.format.mimetypeapplication/pdfen
dc.identifier.slug2152/ETD-UT-2012-08-5995en
dc.identifier.urihttp://hdl.handle.net/2152/ETD-UT-2012-08-5995en
dc.language.isoengen
dc.subjectSynchronous Dataflow graph (SDF)en
dc.subjectCyclo-Static Dataflow graph (CSDF)en
dc.subjectInteger Linear Programming (ILP)en
dc.subjectList schedulingen
dc.subjectMappingen
dc.subjectThroughputen
dc.subjectLatencyen
dc.subjectBufferen
dc.subjectAreaen
dc.titleMutli-objective trade-off exploration for Cyclo-Static and Synchronous Dataflow graphsen
dc.type.genrethesisen
thesis.degree.departmentElectrical and Computer Engineeringen
thesis.degree.disciplineElectrical and Computer Engineeringen
thesis.degree.grantorUniversity of Texas at Austinen
thesis.degree.levelMastersen
thesis.degree.nameMaster of Science in Engineeringen

Access full-text files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
SINHA-THESIS.pdf
Size:
1.97 MB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.12 KB
Format:
Plain Text
Description: