Methodologies and Algorithms for High-Level Synthesis of Application Specific Processors
Date Issued
2011
Date
2011
Author(s)
Yu, Cheng-Juei
Abstract
Growing design complexity has led designers to generate designs at higher levels of abstraction, such as, the behavior description level. The core task for synthesizing the behavior description is the high-level synthesis (HLS), which contains three main steps to create a hardware architecture of datapath elements, control logic and memory elements: resource allocation, binding and scheduling. Among these tasks, resource scheduling is considered the most important in a HLS process. A part of this thesis is devoted to the study of the problem of resource-constrained scheduling (RCS) and proposes two search algorithms to exactly solve the problem in an effective, systematic way. The proposed algorithms are capable of reducing the computational effort required to obtain the best schedules on a pre-defined datapath by effectively pruning the non-promising search space. The effectiveness of the algorithms against existing approaches over time and space is demonstrated by theorems and related analysis. Furthermore, this thesis also presents methodologies that help convert a given application specified in C programming language into a hardware implementation of a custom processor.
Besides datapaths representing standalone functional blocks the proposed RCS algorithms can schedule effectively, control paths representing calls of functions are also considered. Based on and extended from the concept of hierarchical finite-state machines (HFSMs), a number of built-in HFSM templates are proposed and used as the elementary components of a hardware design. Guidelines on the refinement of a C program are introduced; the refined C functions are compiled into HFSMs that in turn generate synthesizable hardware description language (HDL) code as the final design. A set of HFSMs is viewed as an intermediate representation between C and HDL and can be functionally simulated. Two modeling levels, i.e. cycle-accurate and cycle-approximated, are supported. In the end of this thesis, experimental results on a series of several well known algorithmic benchmarks demonstrate the effectiveness of the proposed algorithms and approaches against existing ones.
Subjects
High-Level Synthesis
Search Algorithms
Design Automation
Resource-Constrained Scheduling
Hierarchical Finite State Machines
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-100-F95921036-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):0b1cbb2ade782bfb081b39c95fea1dad