Simultaneous buffer and wire sizing for performance and power optimization
Published 12 August 1996
Jason Cong, Cheng‐Kok Koh, Kwok-Shing Leung
Citations66
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
In this paper, we study the simultaneous buffer and wire sizing (SBWS) problem for delay and power dissipation minimization. We prove the BS/WS relation for optimal SBWS solutions. This relation leads to a polynomial time algorithm for computing the lower and upper bounds of the optimal SBWS solutions, which enables an efficient optimal algorithm for computing optimal SBWS solutions. We have applied the SBWS algorithms to the clock nets in a spread spectrum IF transceiver chip and HSPICE simulations show that our algorithms can reduce skew and power by a factor of 3.5X and 2.6X, respectively, when compared to the manual layout of the clock nets in the original chip.
Keywords
Computer ScienceEngineering
Journal of Applied PhysicsThe Transient Response of Damped Linear Networks with Particular Regard to Wideband Amplifiers
1,778 Citations1948W. C. Elmore
It is found possible to define delay time and rise time in such a way that these quantities can be computed very simply from the Laplace system function of the network.
CERN Document Server (European Organization for Nuclear Research)Principles Of Cmos Vlsi Design A Systems Perspective
1,569 Citations1985Neil Weste, Kamran Eshraghian
CMOS Circuit and Logic Design: The Complemenatry CMOS Inverter-DC Characteristics and Design Strategies.
Buffer placement in distributed RC-tree networks for minimal Elmore delay
558 Citations2002L. P. P. P. van Ginneken
An algorithm is presented for choosing the buffer positions for a wiring tree such that the Elmore delay is minimal, and an extension of the basic algorithm allows minimization of the number of buffers as a secondary objective.
Zero-skew clock routing trees with minimum wirelength
222 Citations2003Kenneth D. Boese, Andrew B. Kahng
The deferred-merge embedding (DME) algorithm is presented, which embeds any given connection topology into the Manhattan plane to create a clock tree with zero skew while minimizing total wirelength in linear time.
IEEE Transactions on Computer-Aided Design of Integrated Circuits and SystemsProvably good performance-driven global routing
202 Citations1992Jason Cong, Andrew B. Kahng +3 more
A provably good performance-driven global routing algorithm for both cell-based and building-block design based on a new bounded-radius minimum routing tree formulation, based on an analog of Prim's minimum spanning tree construction.
Performance-driven interconnect design based on distributed RC delay model
195 Citations1993Jason Cong, Kwok-Shing Leung +1 more
It is shown that interconnect topology optimization can be achieved by computing optimal generalized rectilinear Steiner arborescences and an efficient algorithm is presented which yields optimal or near-optimal solutions.
IEEE Transactions on Computer-Aided Design of Integrated Circuits and SystemsOptimal wiresizing under Elmore delay model
151 Citations1995Jason Cong, Kwok-Shing Leung
A polynomial-time optimal wiresizing algorithm for arbitrary interconnect tree structures under Elmore delay model is developed that reduces interconnect delay by up to 51% when compared to the uniform-width solution of the same routing topology.
IEEE Transactions on Very Large Scale Integration (VLSI) SystemsSimultaneous driver and wire sizing for performance and power optimization
127 Citations1994Jason Cong, Cheng‐Kok Koh
RC interconnect optimization under the Elmore delay model
124 Citations1994Sachin S. Sapatnekar
An efficient solution to the wire sizing problem (WSP) using the Elmore delay model is proposed, and it is shown experimentally that the second formulation provides significantly better engineering solutions.
Design Automation ConferenceZero skew clock net routing
119 Citations1992T.-H. Chao, Jan-Ming Ho +1 more
Design Automation ConferenceSwitch-Level Delay Models for Digital MOS VLSI
106 Citations1984John K. Ousterhout
International Conference on Computer Aided DesignOptimal wire sizing and buffer insertion for low power and a generalized delay model
103 Citations1995John Lillis, Chung‐Kuan Cheng +1 more
High-performance routing trees with identified critical sinks
85 Citations1993Kenneth D. Boese, Andrew B. Kahng +1 more
This work modify traditional Steiner constructions and produce routing trees with significantly lower critical-sink delays compared with existing performance-driven methods, and proposes a new class of Elmore routing tree (ERT) constructions, which iteratively add tree edges to minimize Elmore delay.
Minimum-cost bounded-skew clock routing
75 Citations2002Jason Cong, Cheng‐Kok Koh
A new clock routing algorithm which minimizes total wirelength under any given path-length skew bound, named BST/DME, which can produce a set of routing solutions with skew and wirelength trade-off.
1993 IEEE International Symposium on Circuits and SystemsA direct combination of the Prim and Dijkstra constructions for improved performance-driven global routing
66 Citations2002Charles J. Alpert, T. C. Hu +2 more
A new tree construction is proposed for performance-driven global routing which directly trades off between Prim's minimum spanning tree algorithm and Dijkstra's shortest path tree algorithm, achieving routing trees which satisfy a given routing tree radius bound while using less wire than previous methods.
Performance-driven Steiner tree algorithm for global routing
62 Citations1993Xianlong Hong, Tianxiong Xue +3 more
Two performance-driven Steiner tree algorithms for global routing are presented which consider the minimization of timing delay during the tree construction as the goal and are based on nonlinear optimization method and heuristic approach.
Power optimal buffered clock tree design
52 Citations1995Ashok Vittal, Malgorzata Marek-Sadowska
It is shown that the power minimization problem is NP-hard and a greedy heuristic for power-optimal clock network design is proposed that utilizes the opportunities provided by buffer insertion.
Bounded-skew clock and Steiner routing under Elmore delay
48 Citations1995Jason Cong, Andrew B. Kahng +2 more
Fast performance-driven optimization for buffered clock trees based on Lagrangian relaxation
46 Citations1996Chung-Ping Chen, Yao‐Wen Chang +1 more
Critical net routing
38 Citations2002James P. Cohoon, L.J. Randall
A novel interconnection form, the maximum performance tree (MPT), that better approximates an interconnection with optimal circuit performance is proposed and a heuristic approach is presented that quickly generates MPTs.
Simultaneous gate and interconnect sizing for circuit-level delay optimization
24 Citations1995Noel Menezes, S. Pullela +1 more
This work presents an iterative sensitivity-based approach to simultaneous gate and interconnect sizing in terms of a gate delay model which captures the interaction between the driver and the RC interconnect load and efficiently calculates the path delay sensitivities to size the components along a path.
A 12.7 Mchip/s all-digital BPSK direct sequence spread-spectrum IF transceiver in 1.2 μm CMOS
13 Citations2002C. Chien, P.T. Yang +3 more
The SSRX chip receiver presented in this paper is designed for low SNR loss by using a coherent architecture, allowing applications ranging from voice to data transmission.
International Conference on Computer Aided DesignOptimal wiresizing for interconnects with multiple sources
12 Citations1995Jason Cong, Lei He