Incremental component implementation selection: enabling ECO in compositional system synthesis

The component implementation selection problem (CISP) is to select the appropriate implementation for components of a design, such that the timing constraint is met and some global design objective is optimized. CISP is a generic problem that implicitly or explicitly appears in many stages of CAD flow. In this paper, we present a methodology for quick and efficient updating of CISP solutions in face of incremental engineering changes. For a commonly-used formulation, we discuss necessary and sufficient conditions for optimality of a CISP solution based on which, we develop an algorithm that maintains both validity and optimality of a solution subject to incremental changes. We implemented our approach to incrementally update the threshold voltage assignment solution for a netlist going through engineering changes. On average, our method ran over 300 times faster than the "from-scratch" solver, while delivering the same results.