EWA: efficient wiring-sizing algorithm for signal nets and clock nets

摘要

The wire sizing problem under inequality Elmore delay constraints is known to be posynomial, hence convex under an exponential variable transformation. Due to their efficiency and ease of implementation, one-wire-at-a-time downhill improvement heuristics are often applied to solve such problems. Unfortunately, when there are complex boundary constraints, the solutions from such heuristics can be far away from the global minimum. There are formal methods for solving convex programs, but they are too costly in terms of runtime for some applications. Some optimization techniques can be quite efficient but they solve less desirable formulations, such as minimum weighted sum of area and critical path delays. This paper proposes an efficient wire-sizing algorithm (EWA) that is able to trade solution accuracy for time efficiency while providing an upper bound on the distance from the optimal solution. EWA solves the practical problem of minimizing the total wiring area or the capacitance of an interconnect RC tree subject to hard constraints on the Elmore delay. The implementation is simple and efficiency is comparable to the available heuristics. No restrictions are placed on the circuit or wire widths. Furthermore, it is shown that the optimal wire width assignment for a minimum wiring area objective satisfies all the delay constraints as equalities when minimum wire width constraints are not active. It follows that EWA can be applied for problems with equality delay constraints such as clock trees. Moreover, this and other properties are general enough to permit extensions to higher order delay models and can be used to enhance other optimization methods.