Interconnect optimization, including buffer insertion and Steiner tree construction, continues to be a pillar technology that largely determines overall chip performance. Buffer insertion algorithms in published literature are mostly focused on optimizing only the most critical path. This is a sensible approach for the first order effect. As people strive to squeeze out more performance in the post Moore's law era, the timing of near critical paths is worth considering as well. In this work, a p-norm based Figure Of Merit (pFOM) is proposed to account for both the critical and near critical path timing. Accordingly, a pFOM-driven buffer insertion method is developed. Further, the interaction with timing driven Steiner tree is investigated. The proposed techniques are validated in an industrial design flow and the results confirm their advantages.

As technology scaling advances beyond 65 nanometer node, more devices can fit onto a chip, which implies continued growth of design size. The increased wire delay dominance due to finer wire widths makes design closure an increasingly challenging problem. Interconnect synthesis techniques, such as buffer insertion/sizing and wire sizing, have proven to be the critical part of a successful timing closure optimization tool.

Current design methodologies are geared towards meeting different design criteria, such as delay, area or power. However, in order to correctly identify the critical parts of a circuit for optimization, the circuit has to be electrically clean - i.e., slews on each pin have to be within certain limits, a gate cannot drive more than a certain amount of capacitance, etc. Thus far, this requirement has largely been ignored in the literature. Instead, existing methods which optimize delay are used to fix electrical violations. This leads to solutions that are unnecessarily expensive, and still leave violations that remain unfixed. There is therefore a need for an area-efficient strategy that targets the electrical state of a circuit and fixes all violations quickly. This paper explicitly defines "electrical violations" and presents a flexible approach (called EVE, the electrical violation eliminator) for fixing these. Experimental results validate our approach.

The traditional purpose of physical synthesis is to perform timing closure , i.e., to create a placed design that meets its timing specifications while also satisfying electrical, routability, and signal integrity constraints. In modern design flows, physical synthesis tools hardly ever achieve this goal in their first iteration. The design team must iterate by studying the output of the physical synthesis run, then potentially massage the input, e.g., by changing the floorplan, timing assertions, pin locations, logic structures, etc., in order to hopefully achieve a better solution for the next iteration. The complexity of physical synthesis means that systems can take days to run on designs with multimillions of placeable objects, which severely hurts design productivity. This paper discusses some newer techniques that have been deployed within IBM's physical synthesis tool called PDS that significantly improves throughput. In particular, we focus on some of the biggest contributors to runtime, placement, legalization, buffering, and electric correction, and present techniques that generate significant turnaround time improvements

Buffer insertion is an increasingly critical optimization for achieving timing closure, and the number of buffers required increases significantly with technology migration. It is imperative for an automated buffer insertion algorithm to be able to efficiently optimize tens of thousands of nets. One must also be able to effectively navigate the existing layout, including handling large blockages, blockages with holes specifically for buffers, specially allocated buffer blocks, placement porosity, and routing congestion. The algorithm must also be flexible enough to know when to use and when not to use expensive layout resources. Although several previous works have addressed buffer insertion in the presence of blockages, this is the first to present a complete solution that can manage the physical layout environment.

Van Ginneken's algorithm [18] for performing buffer insertion is a classic in the field, since it optimally solves the problem subject to a set of fixed buffer insertion candidate locations for a given Steiner topology. The generation of these candidate locations is typically performed by dividing the routed wires into small uniformly sized pieces [1]. However, certain regions of the layout are generally more attractive to place buffers than others, e.g., sparse regions are preferred to dense ones. This work presents a fast, shortest path based algorithm to identify good candidate buffer insertion locations to be passed to van Ginneken's algorithm. Our experiments show that the buffers inserted significantly improve the overall design density with virtually no impact on either CPU time or buffered net delays.

To achieve timing closure in a placed design, buffer insertion and driver sizing are two of the most effective transforms that can be applied. Since the driver-sizing solution and the buffer-insertion solution affect each other, suboptimal solutions may result if these techniques are applied sequentially instead of simultaneously. We show how to simply extend van Ginneken's buffer-insertion algorithm to simultaneously incorporate driver sizing and introduce the idea of a delay penalty to encapsulate the effect of driver sizing on the previous stage. The delay penalty can be precomputed efficiently via dynamic programming. Experimental results show that using driver sizing with a delay-penalty function obtains designs with superior timing and area characteristics.

In order to achieve timing closure on increasingly complex IC designs, buffer insertion needs to be performed on thousands of nets within an integrated physical synthesis system. Modern designs may contain large blocks which severely constrain the buffer locations. Even when there may appear to be space for buffers in the alleys between large blocks, these regions are often densely packed or may be needed later to fix critical paths. Therefore, within physical synthesis, a buffer insertion scheme needs to be aware of the porosity of the existing layout to be able to decide when to insert buffers in dense regions to achieve critical performance improvement and when to utilize the sparser regions of the chip. This work addresses the problem of finding porosity-aware buffering solutions by constructing a "smart Steiner tree" to pass to van Ginneken's topology-based algorithm. This flow allows one to fully integrate the algorithm into a physical synthesis system without paying an exorbitant runtime penalty. We show that significant improvements on timing closure are obtained when this approach is integrated into a physical synthesis system.

In order to achieve timing closure on increasingly complex IC designs, buffer insertion needs to be performed on thousands of nets within an integrated physical synthesis system. Modern designs may contain large blocks which severely constrain the buffer locations. Even when there may appear to be space for buffers in the alleys between large blocks, these regions are often densely packed or may needed later to fix critical paths. Therefore, within physical synthesis, a buffer insertion scheme needs to be aware of the porosity of the existing layout to be able to decide when to insert buffers in dense regions to achieve critical performance improvement and when to utilize the sparser regions of the chip.This work addresses the problem of finding porosity-aware buffering solutions by constructing a "smart Steiner tree" to pass to van Ginneken's topology based algorithm. This flow allows one to fully integrate the algorithm into a physical synthesis system without paying an exorbitant runtime penalty. We show that significant improvements on timing closure are obtained when this approach is integrated into a physical synthesis system.

Buffer insertion is a fundamental technology for very large scale integration interconnect optimization. This work presents the repeater insertion with adaptive tree adjustment (RIATA) heuristic that directly extends van Ginneken's classic algorithm to handle blockages in the layout. Given a Steiner tree containing a Steiner point that overlaps a blockage, a local adjustment is made to the tree topology that enables additional buffer insertion candidates to be considered. This adjustment adapts to the demand on buffer insertion and is incurred only when it facilitates the maximal slack solution. RIATA can be combined with any performance-driven Steiner tree algorithm and permits various solution search schemes to achieve different solution quality and runtime tradeoffs. Experiments on several large nets confirms that high-quality solutions can be obtained through this technique with greater efficiency than simultaneous approaches.

To achieve timing closure in a placed design, buffer insertion and driver sizing are two of the most effective transforms that can be applied. Since the driver sizing solution and the buffer insertion solution affect each other, sub-optimal solutions may result if these techniques are applied sequentially instead of simultaneously. We show how to simply extend van Ginneken's buffer insertion algorithm to simultaneously incorporate driver sizing and introduce the idea of a delay penalty to encapsulate the effect of driver sizing on the previous stage. The delay penalty can be pre-computed efficiently via dynamic programming. Experimental results show that using driver sizing with a delay penalty function obtains designs with superior timing and area characteristics.

Buffer insertion is a fundamental technology for VLSI interconnect optimization. Several existing buffer insertion algorithms have evolved from van Ginneken's classic algorithm. In this work, we extend van Ginneken's algorithm to handle blockages in the layout. Given a Steiner tree containing a Steiner point that overlaps a blockage, a local adjustment is made to the tree topology that enables additional buffer insertion candidates to be considered. This adjustment is adaptive to the demand on buffer insertion and is incurred only when it facilitates the maximal slack solution. This approach can be combined with any performance-driven Steiner tree construction. The overall time complexity has linear dependence on the number of blockages and quadratic dependence on the number of potential buffer locations. Experiments on several large nets confirm that high-quality solutions can be obtained through this technique with little CPU cost.

Buffer insertion has become an increasingly critical optimization in high performance design. The problem of finding a delay-optimal buffered Steiner tree has been an active area of research, and excellent solutions exist for most instances. However, current approaches fail to adequately solve a particular class of real-world “difficult” instances which are characterized by a large number of sinks, variations in sink criticalities, and varying polarity requirements. We propose a new Steiner tree construction called C-Tree for these instance types. When combined with van Ginneken style buffer insertion, C-Tree achieves higher quality solutions with fewer resources compared to traditional approaches.

Interconnect synthesis techniques, such as wire sizing and buffer insertion/sizing, have proven to be critical for reducing interconnect delays in deep submicron design. Consequently, the past few years have seen several works that study buffer insertion, wire sizing, and their simultaneous optimization. For long interconnect, wire tapering, i.e., reducing the wire width as the distance from the driver increases, can yield better solutions than uniform wire sizing. However, despite its obvious benefits, tapering is not widely used in practice since it is difficult to integrate into a coherent routing methodology. This paper studies the benefits of wire sizing with tapering when combined with buffer insertion. We first present a theoretical result that shows wire tapering is at most 3.5% faster than uniform wire sizing when maximal buffer insertion is applied. We then present detailed experiments that support this result. Consequently, we conclude that it is generally not worthwhile to perform tapering for signal nets. Finally, we present a general formulation and optimal polynomial time algorithm for simultaneous wire sizing and buffer insertion that forbids wire tapering, but incorporates layer assignment and wire spacing.

Timing optimization is a critical component of deep submicrometer design and buffer insertion is an essential technique for achieving timing closure. This work studies buffer insertion under the constraint that the buffers either: (1) avoid blockages or (2) are contained within preassigned buffer bay regions. We propose a general Steiner-tree formulation to drive this application and present a maze-routing-based heuristic that either avoids blockages or finds buffer bays. We show that the combination of our Steiner-tree optimization with leading-edge buffer-insertion techniques leads to effective solutions on industry designs.

Buffer insertion has become a critical optimization technique in high performance design. Perhaps the most prevalent buffer insertion technique is Van Ginneken's dynamic programming algorithm. Although very effective, the algorithm has time complexity that is quadratic in terms of the input buffer library size. Consequently, to achieve an efficient algorithm, it is critical that the buffer library used by the tool be relatively small, containing a subset of the most effective buffers. We propose a new algorithm for selecting a buffer library from all the buffers available in the technology, thereby permitting efficient buffer insertion. We show that the smaller buffer libraries constructed by our algorithm result in little loss in solution quality while speeding up the buffer insertion algorithm by orders of magnitude.

Article Free Access Share on Buffer insertion with accurate gate and interconnect delay computation Authors: Charles J. Alpert IBM Austin Research Laboratory, Austin, TX IBM Austin Research Laboratory, Austin, TXView Profile , Anirudh Devgan IBM Austin Research Laboratory, Austin, TX IBM Austin Research Laboratory, Austin, TXView Profile , Stephen T. Quay IBM Server Group, Austin, TX IBM Server Group, Austin, TXView Profile Authors Info & Claims DAC '99: Proceedings of the 36th annual ACM/IEEE Design Automation ConferenceJune 1999 Pages 479–484https://doi.org/10.1145/309847.309983Published:01 June 1999Publication History 46citation557DownloadsMetricsTotal Citations46Total Downloads557Last 12 Months38Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Wire sizing and buffer insertion/sizing are critical optimizations in deep submicron design. The past years have seen several studies of buffer insertion, wire sizing, and their simultaneous optimization. When wiring long interconnect, tapering, i.e., reducing the wire width as the distance from the driver increases, has proven effective. However tapering is not widely utilized in industry since it is difficult to integrate into a complete routing methodology. The article examines the benefits of wire sizing with tapering when combined with buffer insertion. We perform several experiments with actual IBM technologies. Results indicate that wire tapering reduces delay typically by less than 5% compared to uniform wire sizing, when buffers can be inserted. Consequently, we suggest that it may not be worthwhile to maintain a routing methodology that supports wire tapering.

Interconnect-driven optimization is an increasingly important step in high-performance design. Algorithms for buffer insertion have been successfully utilized to reduce delay in global interconnect paths; however, existing techniques only optimize delay and timing slack, With the continually increasing ratio of coupling capacitance to total capacitance and the use of aggressive dynamic logic circuit families, noise analysis and avoidance is becoming a major design bottleneck. Hence, timing and noise must be simultaneously optimized to achieve maximum performance. This paper presents comprehensive buffer insertion techniques for noise and delay optimization. Three algorithms are presented, the first for noise avoidance for single sink trees, the second for avoidance for multiple sink trees, and the last for simultaneous noise and delay optimization. We prove the optimality of each algorithm (under various assumptions) and present other theoretical results as well. We ran experiments on a high-performance microprocessor design and show that our approach fixes all noise violations, Our approach was separately verified by a detailed, simulation-based noise analysis tool. Further, we show that optimizing delay alone cannot fix all of the noise violations and that the performance penalty induced by optimizing both delay and noise as opposed to only delay is less than 2%.

Buffer insertion has successfully been applied to reduce delay in global interconnect paths; however, existing techniques only optimize delay and timing slack. With the increasing ratio of coupling to total capacitance and the use of aggressive dynamic logic circuit families, noise is becoming a major design bottleneck. We present comprehensive buffer insertion techniques for noise and delay optimization. Our experiments on a microprocessor design show that our approach fixes all noise violations that were identified by a detailed, simulation-based noise analysis tool. Further, we show that the performance penalty induced by optimizing both delay and noise as opposed to only delay is 2%.