Abstract
In this paper, we consider the problem of interconnect delay minimization by simultaneous buffer and wire sizing under the Elmore delay model. We first present a polynomial time algorithm SBWS to minimize the delay of an interconnect wire. Previously, no polynomial time algorithm for the problem has been reported in the literature. SBWS is an iterative algorithm with guaranteed convergence to the optimal solution. It runs in quadratic time and uses constant memory for computation. Experimental results show that SBWS is extremely efficient in practice. For example, for an interconnect of 10 000 segments and buffers, the CPU time is only 0.255 s. We then extend our result to handle interconnect trees. We present an algorithm SBWS-T which always gives the optimal solution. Experimental results show that SBWS-T is faster than the greedy wire sizing algorithm [2] in practice.
Original language | English (US) |
---|---|
Pages (from-to) | 1297-1304 |
Number of pages | 8 |
Journal | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |
Volume | 18 |
Issue number | 9 |
DOIs | |
State | Published - 1999 |
Externally published | Yes |
Keywords
- Buffer sizing
- Interconnect
- Performance optimization
- Physical design
- Wire sizing
ASJC Scopus subject areas
- Software
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering