Record Details

Complexity of minimum-delay gate resizing

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Complexity of minimum-delay gate resizing
 
Creator CHAKRABORTY, S
MURGAI, R
 
Description Gate resizing for minimum circuit delay is a fundamental problem in the performance optimization of gate-level circuits. In this paper, we study the complexity of two different minimum-delay gate resizing, problems for combinational circuits composed of single-output gates. The first problem is that of gate resizing for minimum circuit delay under the load-dependent delay model. The second problem is a variant of the first, where we relax the delay model to a load-independent one, but impose load constraints instead, i.e., each gate output is not allowed to drive a capacitive load that exceeds its drive capacity. The goal, as before, is to minimize the delay through the circuit. To the best of our knowledge, there has been no published result on the complexity of these problems. In this paper, we prove that both problems are NP-complete. The proofs are inspired by Murgai's work [6], in which the global fanout optimization problem under a fixed net topology was shown to be NP-complete. These results, along with previously published ones, establish that gate resizing is a hard problem except under the most simplistic assumptions.
 
Publisher IEEE COMPUTER SOC
 
Date 2011-10-24T16:36:56Z
2011-12-15T09:11:41Z
2011-10-24T16:36:56Z
2011-12-15T09:11:41Z
2001
 
Type Proceedings Paper
 
Identifier VLSI DESIGN 2001: FOURTEENTH INTERNATIONAL CONFERENCE ON VLSI DESIGN,425-430
0-7695-0831-6
http://dx.doi.org/10.1109/ICVD.2001.902695
http://dspace.library.iitb.ac.in/xmlui/handle/10054/15471
http://hdl.handle.net/100/2223
 
Source 14th International Conference on VLSI Design,BANGALORE, INDIA,JAN 03-07, 2001
 
Language English