Article ID: | iaor2012601 |
Volume: | 23 |
Issue: | 2 |
Start Page Number: | 292 |
End Page Number: | 300 |
Publication Date: | Feb 2012 |
Journal: | Journal of Combinatorial Optimization |
Authors: | Wimer Shmuel, Moiseev Konstantin, Kolodny Avinoam |
Keywords: | combinatorial optimization, programming: convex, programming: dynamic |
The lithography used for 32 nanometers and smaller VLSI process technologies restricts the interconnect widths and spaces to a very small set of admissible values. Until recently the sizes of interconnects were allowed to change continuously and the implied power‐delay optimal tradeoff could be formulated as a convex programming problem, for which classical search algorithms are applicable. Once the admissible geometries become discrete, continuous search techniques are inappropriate and new combinatorial optimization solutions are in order. A first step towards such solutions is to study the complexity of the problem, which this paper is aiming at. Though dynamic programming has been shown lately to solve the problem, we show that it is NP‐complete. Two typical VLSI design scenarios are considered. The first trades off power and sum of delays (