Design Space Exploration for Scheduling and Allocation in High Level Synthesis of Datapaths


Increasing design complexity and shrinking lead times have led to automation of the VLSI design flow at higher levels of abstraction. High-level synthesis (HLS) is that phase in system design which deals with the translation of behavioral descriptions in high-level languages such as C or graphical representations in the form of data flow graphs (DFGs) and control data flow graphs (CDFGs) into an equivalent register transfer level (RTL) netlist. The typical objectives to be optimized during HLS such as delay, area, and power are mutually conflicting thereby necessitating the rapid exploration of the entire design space to identify solutions with different trade-offs among the objectives. This is called design space exploration (DSE). The NP-complete nature of HLS problems requires heuristic approaches which are capable of yielding near optimal solutions. Population-based meta-heuristics such as genetic algorithms (GAs) and particle swarm optimization (PSO) are ideal candidates for DSE since they are capable of generating a population of trade-off solutions in a single run. The application of multi-objective GA and PSO approaches for optimization of power, area, and delay during datapath scheduling and allocation phases of HLS is discussed in this chapter. A novel metric-based approach for estimating the potential of a schedule to yield low-power bindings is also proposed.