Abstract
Buffer insertion is an efficient technique in interconnect optimization. This paper presents a graph based algorithm for optimal buffer insertion under accurate delay models. In our algorithm, a signal is accurately represented by a finite ramp which is characterized by two parameters, shift time and transition time. Any accurate delay model, such as delay models based on the transmission line model and SPICE simulations, can be incorporated into our algorithm. The algorithm determines the optimal number of buffers and their locations on a wire such that some optimization objective is satisfied. Two typical examples of such optimization objectives are minimizing the 50% threshold delay and minimizing the transition time. Both can be easily determined in our algorithm. We show that the buffer insertion problem can be reduced to a shortest path problem. The algorithm can be easily extended for simultaneous buffer insertion and wire-sizing, and complexity is still polynomial. The algorithm can also be extended to deal with problems such as buffer insertion subject to transition time constraints at any position along the wire.
Original language | English |
---|---|
Title of host publication | Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE 2001 |
Editors | Wolfgang Nebel, Ahmed Jerraya |
Publisher | IEEE |
Pages | 535-539 |
Number of pages | 5 |
DOIs | |
Publication status | Published - Mar 2001 |
Event | 2001 Design, Automation and Test in Europe Conference and Exhibition, DATE 2001 - Munich, Germany Duration: 13 Mar 2001 → 16 Mar 2001 https://past.date-conference.com/proceedings-archive/2001/YEAR.HTM (Conference proceedings) |
Publication series
Name | Proceedings of Design, Automation and Test in Europe Conference and Exhibition, DATE |
---|---|
ISSN (Print) | 1530-1591 |
Conference
Conference | 2001 Design, Automation and Test in Europe Conference and Exhibition, DATE 2001 |
---|---|
Country/Territory | Germany |
City | Munich |
Period | 13/03/01 → 16/03/01 |
Internet address |
|
Scopus Subject Areas
- General Engineering