The complexity of VLSI power-delay optimization by interconnect resizing

Konstantin Moiseev, Avinoam Kolodny and Shmuel Wimer ()
Additional contact information
Konstantin Moiseev: Technion, Israel Institute of Technology
Avinoam Kolodny: Technion, Israel Institute of Technology
Shmuel Wimer: Bar-Ilan University

Journal of Combinatorial Optimization, 2012, vol. 23, issue 2, No 9, 292-300

Abstract: 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.

Keywords: Power-delay optimization; VLSI interconnects; NP-completeness (search for similar items in EconPapers)
Date: 2012
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-010-9355-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:23:y:2012:i:2:d:10.1007_s10878-010-9355-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-010-9355-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().