The complexity of VLSI power‐delay optimization by interconnect resizing

The complexity of VLSI power‐delay optimization by interconnect resizing

0.00 Avg rating0 Votes
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: , ,
Keywords: combinatorial optimization, programming: convex, programming: dynamic
Abstract:

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 (L 1), and is shown to be NP‐complete by reduction of PARTITION. The second considers power and max delays (L ), and is shown to be NP‐complete by reduction of SUBSET_SUM.

Reviews

Required fields are marked *. Your email address will not be published.