New approach to simultaneous buffer insertion and wire sizing

Chris C.N. Chu, D. F. Wong

Research output: Contribution to journalConference articlepeer-review

Abstract

In this paper, we present a completely new approach to the problem of delay minimization by simultaneous buffer insertion and wire sizing for a wire. We show that the problem can be formulated as a convex quadratic program, which is known to be solvable in polynomial time. Nevertheless, we explore some special properties of our problem and derive an optimal and very efficient algorithm to solve the resulting program. Given m buffers and a set of n discrete choices of wire width, the running time of our algorithm is O(mn2) and is independent of the wire length in practice. For example, an instance of 100 buffers and 100 choices of wire width can be solved in 3 seconds. Besides, our formulation is so versatile that it is easy to consider other objectives like wire area or power dissipation, or to add constraints to the solution. Also, wire capacitance lookup tables, or very general wire capacitance models which can capture area capacitance, fringing capacitance, coupling capacitance, etc. can be used.

Original languageEnglish (US)
Pages (from-to)614-621
Number of pages8
JournalIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers
StatePublished - Dec 1 1997
Externally publishedYes
EventProceedings of the 1997 IEEE/ACM International Conference on Computer-Aided Design, ICCAD - San Jose, CA, USA
Duration: Nov 9 1997Nov 13 1997

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'New approach to simultaneous buffer insertion and wire sizing'. Together they form a unique fingerprint.

Cite this