Ph.D. Theses

Design Space Exploration in High-Level Synthesis

By Stephen A. Blythe
Advisor: Robert Walker
July 29, 1997

The process of design space exploration in high-level synthesis refers to the derivation of the area vs. latency curve for a specified behavioral description and given library of hardware modules. Deriving the curve that represents the design space can be reduced to finding the design space's Pareto points -- those points that represent locally optimal scheduling solutions in the design space. The work presented here extends traditional design space exploration through careful incorporation of several design issues into the design space exploration problem.

The Pareto points in any design space can be found through successive invocations of a scheduler. Since an accurate characterization of the design space is desired, optimal scheduling results are required. In order to schedule optimally, careful consideration is given to bounding techniques and the development of an efficient ILP based scheduler. One of the design issues that is frequently considered during scheduling is the process of chaining. This process is analyzed and incorporated into the methodology of this thesis.

Other design issues also have a significant impact on the design space. One such issue that is frequently oversimplified is the determination of the system clock length. This problem is introduced as an added dimension to the scheduling problem and then incorporated into the design space exploration problem. Appropriately choosing hardware modules from the given library, a process known as module selection, is another important subproblem that the work outlined here adds into the design space exploration problem. After choosing the appropriate modules, the scheduler must also determine the appropriate way to utilize these module in resulting designs, a process known as type mapping. This thesis presents work that incorporates type mapping directly into the scheduler to solve this problem.

Simply exhaustively scheduling for every possible constraint in a design space to find its Pareto points, while correct, would prove extremely time consuming. Instead, this thesis proposes various methodologies for solving the design space exploration problem with efficiency in mind, and discusses why one methodology might work better than another. Furthermore, a discussion of how the complexity of the clock length determination, module selection, and type mapping subproblems effects the design space exploration methodologies is given.

Return to main PhD Theses page