A quadratic programming approach to simultaneous buffer insertion sizing and wire sizing

In this paper, rye present a completely new approach to the problem of dela y minimization by simultaneous buffer insertion and wire sizing for a wire. We show that the problem can be formulated as a Convex quadratic program, which is known to be solvable in polynomial time. Nevertheless, we explore some special properties of our problem and derive an optimal and very effic ient algorithm modified active set method (MASM) to solve the resulting pro gram. Given m buffers and a set of n discrete choices of wire width, the ru nning time of our algorithm is O(mn(2)) and is independent of the wire leng th in practice, For example, an instance of 100 buffers and 100 choices of wire width can be solved in 0.92 s, In addition, we extend MASM to consider simultaneous buffer insertion, buffer sizing, and wire sizing. The resulti ng algorithm MASM-BS is again optimal and very efficient, For example, with six choices of buffer size and 10 choices of wire width, the optimal solut ion for a 15000 mu m long wire can be found in 0.05 s, Besides, our formula tion is so versatile that it is easy to consider other objectives like wire area or power dissipation, or to add constraints to the solution. Also, wi re capacitance lookup tables, or very general wire capacitance models which can capture area capacitance, fringing capacitance, coupling capacitance, etc, can be used.