Algorithms for high-level synthesis: resource utilization-based approach
Miodrag Potkonjak · 1992
This thesis presents a new high level synthesis system, HYPER. HYPER uses a single, global quality measure, called the resource utilization measure, to drive the design space exploration process. This unique approach effectively merges the allocation, assignment, scheduling, transformations, and estimation with hierarchy handling in an unified manner. Three HYPER parts are discussed: estimations, hierarchical graph allocation, assignment and scheduling and transformations. New transformation environment has been developed. Several new transformations (including retiming and associativity, software pipelining and software retiming, commutativity, and very fast implementation of recursive programs), based on a novel learning while searching and anti-voter rejectionless techniques, are introduced. The effectiveness of the proposed algorithms is demonstrated in multiple ways: using standard benchmarks examples, with the aid of statistical analysis and through a comparison with estimated minimal bounds. Sharp minimal bounds based on a discrete relaxation technique are used.