Lower Bound Estimation of Hardware Resources for Scheduling in High-Level Synthesis

In high-level synthesis of VLSI circuits, good lower bound predictioncan efficiently narrow down the large space of possible designs.Previous approaches predict the lower bound by relaxing or evenignoring the precedence constraints of the data flow graph (DFG), andresult in inaccuracy of the lower bound. The loop folding andconditional branch were also not considered. In this paper, a newstepwise refinement algorithm is proposed, which takes consideration ofprecedence constraints of the DFG to estimate the lower bound ofhardware resources under time constraints. Processing techniques tohandle multi-cycle, chaining, pipelining, as well as loop folding andmutual exclusion among conditional branches are also incorporated inthe algorithm. Experimental results show that the algorithm can producea very tight and close to optimal lower bound in reasonable computationtime.