Search

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.

IP blocks and large macro cells are becoming more prevalent in the physical layout of a design, actually causing an increase in the available free space. We observe that top-down placement based on recursive bisection with multilevel partitioning performs poorly on these porous designs since it lacks a global view of the ideal placement. However, the strength of analytic placement methods lies in their ability to ascertain this global view. Consequently, we propose an enhancement to cut-based placement called analytic constraint generation (ACG). ACG utilizes an analytic engine to distribute available free space appropriately by determining balance constraints for each partitioning step. For one-dimensional placements, our experiments illustrate the large gap between analytic engines, traditional cut-based placement, and ACG as a design becomes increasingly sparse. We also show that for real industry designs, ACG significantly improves the performance of cut-based placement, particularly timing perspective, as implemented within a state-of-the-art industrial placer.

As technology scales, interconnect-centric design flows become imperative for achieving timing closure. Preplanning buffers and wires in the layout is critical for such flows. Both buffers and wires must be considered simultaneously, since wire routes determine buffer requirements and buffer locations constrain the wire routes. In contrast to recently proposed buffer-block planning approaches, our novel design methodology distributes a set of buffer sites throughout the design. This allows one to use a tile graph to abstract the buffer planning problem and simultaneously address wire planning. We present a four-stage heuristic called resource allocation for buffer and interconnect distribution for resource allocation that includes a new, efficient technique for buffer insertion using a length-based constraint. Extensive experiments validate the effectiveness of this approach.

In high-speed digital VLSI design, bounding the load capacitance at gate outputs is a well-known methodology to improve coupling noise immunity, reduce degradation of signal transition edges, and reduce delay uncertainty due to coupling noise. Bounding load capacitance also improves reliability with respect to hot-carrier oxide breakdown and AC self-heating in interconnects, and guarantees bounded input rise/fall times at buffers and sinks. This paper introduces a new minimum-buffer routing problem (MBRP) formulation which requires that the capacitive load of each buffer, and of the source driver, be upper-bounded by a given constant. Our contributions are as follows: We give linear-time algorithms for optimal buffering of a given routing tree with a single (inverting or noninverting) buffer type. For simultaneous routing and buffering with a single noninverting buffer type, we prove that no algorithm can guarantee a factor smaller than 2 unless P=NP and give an algorithm with approximation factor slightly larger than 2 for typical buffers. For the case of a single inverting buffer type, we give an algorithm with approximation factor slightly larger than 4. We give local-improvement and clustering based MBRP heuristics with improved practical performance, and present a comprehensive experimental study comparing the runtime/quality tradeoffs of the proposed MBRP heuristics on test cases extracted from recent industrial designs.

Clock grid is a mainstream clock network methodology for high performance microprocessor and SOC designs. Clock skew, power usage and robustness to PVT (power, voltage, temperature) are all important metrics for a high quality clock grid design. Tree-driven-grid clock network is a typical clock grid clock network. It includes a clock source, a buffered tree, leaf buffers, a mesh clock grid, local clock buffers, and latches as shown in Fig. 1. For such network, one big challenge is how to connect the leaf level buffers of the global tree to the grid with nonuniform loads under tight slew and skew constraints. The choice of tapping points that connect the leaf buffers to the clock grid are critical to the quality of the clock designs. Good tapping points can minimize the clock skew and reduce power. In this paper, we proposed a new algorithm to select the tapping points to build the global tree as regular and symmetric as possible. From our experimental results, the proposed algorithm can efficiently reduce global clock skew, rising slew, maximum overshoot, reduce power, and avoid local skew violation.

We empirically assess the implications of fixed terminals for hypergraph partitioning heuristics. Our experimental testbed incorporates a leading-edge multilevel hypergraph partitioner and IBM-internal circuits that have recently been released as part of the ISPD-98 Benchmark Suite. We find that the presence of fixed terminals can make a partitioning instance considerably easier (possibly to the point of being "trivial"); much less effort is needed to stably reach solution qualities that are near best-achievable. Toward development of partitioning heuristics specific to the fixed-terminals regime, we study the pass statistics of flat FM-based partitioning heuristics. Our data suggest that more fixed terminals implies that the improvements within a pass will more likely occur near the beginning of the pass. Restricting the length of passes-which degrades solution quality in the classic (free-hypergraph) context-is relatively safe for the fixed-terminals regime and considerably reduces the run times of our FM-based heuristic implementations. The distinct nature of partitioning in the fixed-terminals regime has deep implications: (1) for the design and use of partitioners in top-down placement; (2) for the context in which VLSI hypergraph partitioning research is pursued; and (3) for the development of new benchmark instances for the research community.

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%.

The graph partitioning problem is to divide the vertices of a graph into disjoint clusters to minimize the total cost of the edges cut by the clusters. A spectral partitioning heuristic uses the graph's eigenvectors to construct a geometric representation of the graph (e.g., linear orderings) which are subsequently partitioned. Our main result shows that when all the eigenvectors are used, graph partitioning reduces to a new vector partitioning problem. This result implies that as many eigenvectors as are practically possible should be used to construct a solution. This philosophy is in contrast to that of the widely used spectral bipartitioning (SB) heuristic (which uses only a single eigenvector) and several previous multi-way partitioning heuristics [8, 11, 17, 27, 38] (which use k eigenvectors to construct k-way partitionings). Our result motivates a simple ordering heuristic that is a multiple-eigenvector extension of SB. This heuristic not only significantly outperforms recursive SB, but can also yield excellent multi-way VLSI circuit partitionings as compared to [1, 11]. Our experiments suggest that the vector partitioning perspective opens the door to new and effective partitioning heuristics. The present paper updates and improves a preliminary version of this work [5].

A linear wirelength objective more effectively captures timing, congestion, and other global placement considerations than a squared wirelength objective. The GORDIAN-L cell placement tool minimizes linear wirelength by first approximating the linear wirelength objective by a modified squared wirelength objective, then executing the following loop-(1) minimize the current objective to yield some approximate solution and (2) use the resulting solution to construct a more accurate objective-until the solution converges. This paper shows how to apply a generalization of an algorithm due to Weiszfeld (1937) to placement with a linear wirelength objective and that the main GORDIAN-L loop is actually a special case of this algorithm. We then propose applying a regularization parameter to the generalized Weiszfeld algorithm to control the tradeoff between convergence and solution accuracy; the GORDIAN-L iteration is equivalent to setting this regularization parameter to zero. We also apply novel numerical methods, such as the primal-Newton and primal-dual Newton iterations, to optimize the linear wirelength objective. Finally, we show both theoretically and empirically that the primal-dual Newton iteration stably attains quadratic convergence, while the generalized Weiszfeld iteration is linear convergent. Hence, primal-dual Newton is a superior choice for implementing a placer such as GORDIAN-L, or for any linear wirelength optimization.

consisting of k clusters, with k > 2. Bottom-up agglomerative approaches are also commonly used to construct partitions, and we discuss these in terms of worst-case performance for metric data sets. Our main contribution derives from a new restricted partition formulation that requires each cluster to be an interval of a given ordering of the objects being clustered. Dynamic programming can optimally split such an ordering into a partition Pk for a large class of objectives that includes min-diameter. We explore a variety of ordering heuristics and show that our algorithm, when combined with an appropriate ordering heuristic, outperforms traditional algorithms on both random and non-random data sets.

To address the routability issue, routing congestion estimators (RCE) become essential in industrial design flow. Recently, several RCEs [1-4] based on global routing engines are developed, but they typically ignore the effects of routing on timing so that the identified routing paths may be overlong and thus impractical. To be aware of the timing issues, our proposed global-routing-based RCE obeys the layer directive and scenic constraints to respectively limit the routing layers and the maximum routing wirelength of the potentially timing-critical nets. To handle the scenic constrains, we propose a novel method based on a relaxation-legalization scheme. Also, because the work in [5] reveals that congestion ratio is a better indicator than overflow to evaluate routability, this work focuses on minimizing the congestion ratio rather than overflows. As will be shown, the problem of minimizing congestion ratio is more complicated than minimizing overflows, so we develop a new rip-up and rerouting scheme to reduce congestion and further to approach a target congestion ratio. Moreover, to fit the demands of practical uses, this work presents a control utility to trade off runtime and quality, which is an essential function to an industrial RCE tool. Experiments reveal that the proposed RCE is faster and more accurate than another industrial global-routing-based RCE.

The impact of considering design hierarchy during physical synthesis remains a fairly under-researched area. This is especially true for large-scale circuit placement. This is in large part due to the non-availability of realistic public designs with the design hierarchy information. Additionally, modern designs are fairly complex with numerous placement blockages, non-uniform wiring stacks, partial and/or complete routing blockages, etc. This significantly complicates both, the placement and routing steps of physical synthesis. The aim of the ICCAD-2012 contest is to evaluate the impact of considering design hierarchy on the wire length and routability of placement. This is addressed by way of the following: (a) release industrial-strength place-and-route benchmarks that contain the design hierarchy information, (b) present an accurate congestion analysis framework to evaluate and compare the routability of various placement algorithms. We hope that a set of challenging benchmarks containing the design hierarchy information, along with a standardized evaluation framework, will further advance research in design hierarchy aware routability-driven placement.

Existing routability-driven placers mostly employ rudimentary and often crude congestion models that fail to account for the complexities in modern designs, e.g., the impact of non-uniform wiring stacks, layer directives, partial and/or complete routing blockages, etc. In addition, they are hampered by congestion metrics that do not accurately score or represent design congestion. This is in large part due to the non-availability of public designs depicting industrial wiring stacks and other complexities affecting design routability. The aim of the DAC 2012 routability-driven placement contest is to address these issues, by way of the following: (a) release challenging benchmark designs that are derived from modern industrial ASICs, and contain information to perform both placement and routing, (b) present a new congestion metric, as well as an accurate congestion analysis framework to evaluate and compare the routability of various placement algorithms. We hope that a set of challenging benchmarks, along with a standard, publicly available evaluation framework will further advance research in routability-driven placement.

Physical synthesis has emerged as one of the most important tools in design closure, which starts with the logic synthesis step and generates a new optimized netlist and its layout for the final signoff process. As stated in [1], "it is a wrapper around traditional place and route, whereby synthesis-based optimization are interwoven with placement and routing." A traditional physical synthesis tool generally focuses on design closure with Steiner wire model. It optimizes timing/area/power with the assumption that each net can be routed with optimal Steiner tree. However, advanced design rules, more IP and hierarchical design styles for super-large billion-gate designs, serious buffering problems from interconnect scaling and metal layer stacks make routing a much more challenging problem [2]. This paper discusses a series of techniques that may relieve this problem, and guide the physical design closure system to produce not only easier to route designs, but also better timing quality. Open challenges are also overviewed at the end.

This paper presents WRIP - a Wirelength-driven Rewiring-based Incremental Placement which effectively reduces wirelength of the optimized placement of industrial large-scale standard cell designs. WRIP uses a powerful logic synthesis technique called logic rewiring which restructures the local circuits while preserving the logic functionality and reduces the wirelength under an accurate estimation of the half perimeter wirelength (HPWL) metric. We integrated WRIP into an industrial EDA tool and tested it upon several real designs with hundreds of thousands of movable objects. Tested on circuits which has been fully optimized by the state-of-the-art industrial placement tool, our experiments showed that on average WRIP reduces wirelength by 2.25% after placement and 2.45% after global routing in HPWL and Steiner WL model respectively. The runtime of WRIP is only about half an hour for the largest tested ASIC circuit. This is the first attempt to fully integrate powerful logic synthesis into industrial placement tools with real-life effectiveness and efficiency.

We propose a new multilevel framework for large-scale placement called MAPLE that respects utilization constraints, handles movable macros and guides the transition between global and detailed placement. In this framework, optimization is adaptive to current placement conditions through a new density metric. As a baseline, we leverage a recently developed at quadratic optimization that is comparable to prior multilevel frameworks in quality and runtime. A novel component called Progressive Local Refinement (ProLR) helps mitigate disruptions in wirelength that we observed in leading placers. Our placer MAPLE outperforms published empirical results --- RQL, SimPL, mPL6, NTUPlace3, FastPlace3, Kraftwerk and APlace3 -- across the ISPD 2005 and ISPD 2006 benchmarks, in terms of official metrics of the respective contests.

We discuss a new minimum density objective for spanning and Steiner tree constructions. This formulation is motivated by the minimum-area layout objective, which is best achieved through balancing the usage of horizontal and vertical routing resources. We present two efficient heuristics for constructing low-density spanning trees and prove that their outputs are on average within small constants of optimal with respect to both tree cost and density. Our proof techniques suggest a non-uniform lower bound schema which can afford tighter estimates of solution quality for a given problem instance. Furthermore, the minimum density objective can be transparently combined with a number of previous interconnection objectives (e.g., minimizing tree radius or skew) without affecting solution quality with respect to these previous metrics. Extensive simulation results suggest that applications to VLSI global routing are promising.

The last few years have seen significant advances in the quality of placement algorithms. This is in part due to the availability of large, challenging testcases by way of the ISPD-2005 [17] and ISPD-2006 [16] placement contests. These contests primarily evaluated the placers based on the half-perimeter wire length metric. Although wire length is an important metric, it still does not address a fundamental requirement for placement algorithms, namely, the ability to produce routable placements.This paper describes the ISPD-2011 routability-driven placement contest, and a new benchmark suite that is being released in conjunction with the contest. All designs in the new benchmark suite are derived from industrial ASIC designs, and can be used to perform both placement and global routing. By way of the contest and the associated benchmark suite, we hope to provide a standard, publicly available framework to help advance research in the area of routability-driven placement.

This work proposes a new problem of identifying large and tangled logic structures in a synthesized netlist. Large groups of cells that are highly interconnected to each other can often create potential routing hotspots that require special placement constraints. They can also indicate problematic clumps of logic that either require resynthesis to reduce wiring demand or specialized datapath placement. At a glance, this formulation appears similar to conventional circuit clustering, but there are two important distinctions. First, we are interested in finding large groups of cells that represent entire logic structures like adders and decoders, as opposed to clusters with only a handful of cells. Second, we seek to pull out only the structures of interest, instead of assigning every cell to a cluster to reduce problem complexity. This work proposes new metrics for detecting structures based on Rent's rule that, unlike traditional cluster metrics, are able to fairly differentiate between large and small groups of cells. Next, we demonstrate how these metrics can be applied to identify structures in a netlist. Finally, our experiments demonstrate the ability to predict and alleviate routing hotspots on a real industry design using our metrics and method.

Timing-driven placement is a critical step in nanometer-scale physical synthesis. To improve design timing on a global scale, net-weight based global timing-driven placement is a commonly used technique. This paper shows that such an approach can improve timing, but often degrades wire length and routability. Another problem with existing timing-driven placers is inconsistencies in the definition of timing closure. Approaches using linear programming are forced to make assumptions about the timing models that simplify the problem. To truly do timing-driven placement, the placer must be able to make queries to a real timing analyzer with incremental capabilities. This paper describes an incremental timing-driven placer called ITOP. Using accurate timing from an industrial static timer, ITOP integrates incremental timing closure optimizations like buffering and repowering within placement to improve design timing without degrading wire length and routability.Experimental results on a set of optimized industrial circuit netlists show that ITOP significantly outperforms conventional net-weight based timing-driven placement. In particular, on average, it obtains an improvement of over 47.45%, 9.88% and 5% in the worst slack, total negative slack and wire length as compared to the conventional flow.

In a complete physical synthesis flow, optimization transforms, that can improve the timing on critical paths that are already well-optimized by a series of powerful transforms (timing driven placement, buffering and gate sizing) are invaluable. Finding such a transform is quite challenging, to say nothing of efficiency. This work explores innovative cloning (gate duplication) techniques to improve timing-closure in a physical synthesis environment.With a buffer-aware interconnect timing model, new polynomial-time optimal algorithms are proposed for timing-driven cloning, including both finding optimal sink partitions (identifying the fan-outs) for the original and the duplicated gates, as well as physical locations for both gates. In particular, we present an O(m)-time optimal algorithm to minimize the worst slack if the original gate is movable, and an O(m log m) algorithm if the original gate is fixed, where $m$ is the number of fan-outs. To the best of our knowledge, this work is the first one considering the timing-driven cloning problem under a buffer-aware interconnect delay model.For a hundred testcases in 45nm technology node, we demonstrate significant timing improvement due to our cloning techniques as compared to other existing timing-optimization transforms. Extensions to other factors, such as wirelength, FOM and placement obstacles are further discussed.

As VLSI technology enters the nanoscale regime, interconnect delay has become the bottleneck of the circuit timing. As one of the most powerful techniques for interconnect optimization, buffer insertion is indispensable in the physical synthesis flow. Buffering is known to be NP-complete and existing works either explore dynamic programming to compute optimal solution in the worst-case exponential time or design efficient heuristics without performance guarantee. Even if buffer insertion is one of the most studied problems in physical design, whether there is an efficient algorithm with provably good performance still remains unknown. This work settles this open problem. In the paper, the first fully polynomial time approximation scheme for the timing driven minimum cost buffer insertion problem is designed. The new algorithm can approximate the optimal buffering solution within a factor of 1 + e running in O(m2n2b/e3 + n3b2/e) time for any 0 ≪ e ≪ 1, where n is the number of candidate buffer locations, m is the number of sinks in the tree, and b is the number of buffers in the buffer library. In addition to its theoretical guarantee, our experiments on 1000 industrial nets demonstrate that compared to the commonly-used dynamic programming algorithm, the new algorithm well approximates the optimal solution, with only 0.57% additional buffers and 4.6× speedup. This clearly demonstrates the practical value of the new algorithm.

In high-frequency microprocessor design, placement plays a significantly different role from that in large ASICs. Not only does it have to find a good global placement solution, placement needs tighter interaction with physical optimizations to improve every picosecond possible. This paper will introduce practical placement techniques that integrate buffering and gate sizing to maximize timing improvement in a standard-cell library based high-performance design flow. Combined with accurate timing models and analysis, these incremental placement techniques simultaneously consider multiple optimization options and make timing-optimal changes under the given timing model. These techniques are equipped with a “Do-no-harm” policy that makes them applicable in incremental optimization frameworks to reform critical subcircuits.

The physical design flow of any project depends upon the size of the design, the technology, the number of designers, the clock frequency, and the time to do the design. As technology advances and design-styles change, physical design flows are constantly reinvented as traditional phases are removed and new ones are added to accommodate changes in technology. Includes a personal perspective from Ralph Otten as he looks back on the major technical milestones in the history of physical design automation. Explore State-of-the-Art Techniques and TrendsHandbook of Algorithms for Physical Design Automation provides a detailed overview of VLSI physical design automation, emphasizing state-of-the-art techniques, trends and improvements that have emerged during the previous decade. After a brief introduction to the modern physical design problem, basic algorithmic techniques, and partitioning, the book discusses significant advances in floorplanning representations and describes recent formulations of the floorplanning problem. The text also addresses issues of placement, net layout and optimization, routing multiple signal nets, manufacturability, physical synthesis, special nets, and designing for specialized technologies. Highly-Focused Information for Next Generation Design Problems Although several books on this topic are currently available, most are either too broad or out of date. Alternatively, proceedings and journal articles are valuable resources for researchers in this area, but the material is widely dispersed in the literature. This handbook pulls together a broad variety of perspectives on the most challenging problems in the field, and focuses on emerging problems and research results.

A fundamental problem in timing-driven physical synthesis is the reduction of critical paths in a design. In this work, we propose a powerful new technique that moves (and can also resize) multiple cells simultaneously to smooth critical paths, thereby reducing delay and improving worst negative slack or a figure-of-merit. Our approach offers several key advantages over previous formulations, including the accurate modeling of objectives and constraints in the true timing model, and a guarantee of legality for all cell locations.

As technology scaling advances to the 45 and 32 nanometer nodes, more devices can fit onto a chip, which impliescontinued rapid design size growth. Naturally, it becomes increasingly challenging to achieve design closure on these enormous chips with tight performance and power constraints. Physical synthesis has emerged as a critical and powerful component of modern design methodologies to conquer such challenges. Starting from logic-level net list, physical synthesis creates a legally placed design while attempting to satisfy timing, power, and electrical constraints simultaneously. This paper briefly outlines the core components of physical synthesis timing closure and discusses some recent techniques that improve the solution quality and throughput of the physical synthesis process.

Fast and accurate routing congestion estimation is essential for optimizations such as floorplanning, placement, buffering, and physical synthesis that need to avoid routing congestion. Using a probabilistic technique instead of a global router has the advantage of speed and easy updating. Previously proposed probabilistic models (Lou, et al., 2001) (Westra et al., 2004) do not account for wiring that may already be fixed in the design, e.g., due to macro blocks or power rails. These "partial wiring blockages" certainly influence the global router, so they should also influence a probabilistic routing prediction algorithm. This work proposes a probabilistic congestion prediction metric that extends the work of (Westra et al., 2004) to model partial wiring blockages. The authors also show a new fast algorithm to efficiently generate the congestion map and demonstrate the effectiveness of our methods on real routing problems

Physical synthesis optimizations and engineering change orders typically change the locations of cells, resize cells or add more cells to the design after global placement. Unfortunately, those changes usually lead to wirelength increases; thus another pass of optimizations to further improve wirelength, timing and routing congestion characteristics is required. Simple wirelength-driven detailed placement techniques could be useful in this scenario. While such techniques can help to reduce wirelength, ones without careful timing constraint considerations might degrade the timing characteristics (worst negative slack, total negative slack, etc) and/or introduce more electrical violations (exceeding maximum output load constraints and maximum input slew constraints). In this paper, we propose a new detailed placement paradigm, which use a set of pin-based timing and electrical constraints in detailed placement to prevent it from degrading timing or violating electrical constraints while reducing wire-length, thus dubbed as Hippocrates: FIRST-DO-NO-HARM optimizations. Our experimental results show great promises. By honoring these constraints, our detailed placement technique not only reduces total wirelength (TWL), but also significantly improves timing, achieving 37% better total negative slack (TNS).

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.

Traditionally, rectilinear Steiner minimum trees (RSMT) are widely used for routing estimation in design optimizations like floorplanning and physical synthesis. Since it optimizes wirelength, an RSMT may take a "non-direct" route to a sink, which may give the designer an unnecessarily pessimistic view of the delay to the sink. Previous works have addressed this issue through performance-driven constructions, minimum Steiner arborescence, and critical sink based Steiner constructions. Physical synthesis and routing flows have been reticent to adapt universal timing-driven Steiner constructions out of fear that they are too expensive (in terms of routing resource and capacitance). This paper studies several different performance-driven Steiner tree constructions in order to show which ones have superior performance. A key result is that they add at most 2%-4% extra capacitance, and are thus a promising avenue for today's increasingly aggressive performance-driven P&R flows. We demonstrate using a production P&R flow that timing-driven Steiner topologies can be easily embedded into an incremental routing subflow to obtain significantly improved timing (3.6% and 5.1% improvements in cycle time for two industry testcases) at practically no cost of wirelength or routability.

As a prevalent constraint, sharp slew rate is often required in circuit design which causes a huge demand for buffering resources. This problem requires ultra-fast buffering techniques to handle large volume of nets, while also minimizing buffering cost. This problem is intensively studied in this paper. First, a highly efficient algorithm based on dynamic programming is proposed to optimally solve slew buffering with discrete buffer locations. Second, a new algorithm is developed to handle the difficult cases in which no assumption is made on buffer input slew. Third, an adaptive buffer selection approach is proposed to efficiently handle slew buffering with continuous buffer locations. Experiments on industrial netlists demonstrate that our algorithms are very effective and highly efficient: we achieve > 100/spl times/ speed up and save up to 40% buffer area over the commonly-used van Ginneken style buffering.

The "quadratic placement" methodology is rooted in [Module Placement Based on Resistive Network Optimization, Proud: A Sea-Of-Gate Placement Algorithm, A Combined Force and Cut Algorithm for Hierarchical VLSI Layout]and is reputedly used in many commercial and in-house tools forplacement of standard-cell and gate-array designs. The methodologyiterates between two basic steps: solving sparse systems oflinear equations, and repartitioning. This work dissects the implementationand motivations for quadratic placement. We firstshow that (i) Krylov subspace engines for solving sparse systemsof linear equations are more effective than the traditional successiveover-relaxation (SOR) engine [A Unified Approach to Partitioning and Placement] and (ii) order convergence criteriacan maintain solution quality while using substantially fewersolver iterations. We then discuss the motivations and relevanceof the quadratic placement approach, in the context of past and futurealgorithmic technology, performance requirements, and designmethodology. We provide evidence that the use of numerical linearsystems solvers with quadratic wirelength objective may be due tothe pre-1990's weakness of min-cut partitioners, i.e., numerical engineswere needed to provide helpful hints to min-cut partitioners.Finally, we note emerging methodology drivers in deep-submicrondesign that may require new placement approaches to the placement problem.

Buffer insertion is an important technique used to achieve timing closure in high performance VLSI designs. As the number of buffers in ASIC designs has increased with process scaling, the power con-sumption of buffers has become a critical concern. In this paper, we present an efficient algorithm that performs van Ginneken style buffer insertion on RC trees and minimizes the total power con-sumption under a given delay constraint. Our algorithm is based on a formulation that uses a buffer library consisting of continuous buffer sizes. We construct solution candidates in the form of surfaces in the 3-D delay, capacitance and power (DCP) space and show the mecha-nisms to propagate and merge them in the interconnect tree. Instead of a single minimal power solution, the algorithm produces an entire DCP surface from which a suitable solution point can be selected. We also present a post-processing step where buffers with continu-ous (non-standard) sizes are snapped to discrete size values corre-sponding to the buffers in a given library. The proposed algorithm has a worst-case runtime complexity that is polynomial (quadratic) in the number of possible buffer locations. We implemented and tested our proposed algorithm on a number of large benchmark nets and observed that our method produces a speedup in runtime of 5-6X in comparison with previous power aware buffer insertion methods.

Without the MCNC and ISPD98 benchmarks, it would arguably not have been possible for the academic community to make consistent advances in physical design over the last decade. While still being used extensively in placement and floorplanning research, those benchmarks can no longer be considered representative of today's (and tomorrow's) physical design challenges. In order to drive physical design research over the next few years, a new benchmark suit is being released in conjunction with the ISPD2005 placement contest. These benchmarks are directly derived from industrial ASIC designs, with circuit sizes ranging from 210 thousand to 2.1 million placeable objects. Unlike the ISPD98 benchmarks, the physical structure of these designs is completely preserved, giving realistic challenging designs for today's placement tools. Hopefully, these benchmarks will help accelerate new physical design research in the placement, floor-planning, and routing.

Placement is a critical component of today's physical synthesis flow with tremendous impact on the final performance of VLSI designs. However, it accounts for a significant portion of the over-all physical synthesis runtime. With complexity and netlist size of today's VLSI design growing rapidly, clustering for placement can provide an attractive solution to manage affordable placement runtime. Such clustering, however, has to be carefully devised to avoid any adverse impact on the final placement solution quality. In this paper we present a new bottom-up clustering technique, called best-choice, targeted for large-scale placement problems. Our best-choice clustering technique operates directly on a circuit hypergraph and repeatedly clusters the globally best pair of objects. Clustering score manipulation using a priority-queue data structure enables us to identify the best pair of objects whenever clustering is performed. To improve the runtime of priority-queue-based best-choice clustering, we propose a lazy-update technique for faster updates of clustering score with almost no loss of solution quality. We also discuss a number of effective methods for clustering score calculation, balancing cluster sizes, and handling of fixed blocks. The effectiveness of our best-choice clustering methodology is demonstrated by extensive comparisons against other standard clustering techniques such as Edge-Coarsening [12] and First-Choice [13]. All clustering methods are implemented within an industrial placer CPLACE [1] and tested on several industrial benchmarks in a semi-persistent clustering context.

Closed-form expressions for buffered interconnect delay approximation have been around for some time. However, previous approaches assume that buffers are free to be placed anywhere. In practice, designs frequently have large blocks that make the ideal buffer-insertion solution unrealizable. The theory of Otten (ACM/IEEE Intl. Symp. Physical Design, p. 104, 1998) is extended to show how one can model the blocks into a simple delay-estimation technique that applies to both two-pin and multipin nets. Even though the formula uses one buffer type, it shows remarkable accuracy in predicting delay when compared to an optimal realizable buffer-insertion solution. Potential applications include wire planning, timing analysis during floorplanning, or global routing. The authors' experiments show that their approach accurately predicts delay when compared to constructing a realizable buffer insertion with multiple buffer types

Along with the progress of VLSI technology, buffer insertion plays an increasingly critical role on affecting circuit design and performance. Traditional buffer insertion algorithms are mostly net based and therefore often result in sub-optimal delay or unnecessary buffer expense due to the lack of global view. In this paper, we propose a novel path based buffer insertion scheme which can overcome the weakness of the net based approaches. We also discuss some potential difficulties of the path based buffer insertion approach and propose solutions to them. A fast estimation on buffered delay is employed to improve the solution quality. Gate sizing is also considered at the same time. Experimental results show that our method can efficiently reduce buffer/gate cost significantly (by 71 % on average) when compared to traditional net based approaches. To the best of our knowledge, this is the first work on path based buffer insertion and simultaneous gate sizing.

As technology scales to 0.13 micron and below, designs are requiring buffers to be inserted on interconnects of even moderate length for both critical paths and fixing electrical violations. Consequently, buffer insertion is needed on tens of thousands of nets during physical synthesis optimization. Even the fast implementation of van Ginneken's algorithm requires several hours to perform this task. This work seeks to speed up the van Ginneken style algorithms by an order of magnitude while achieving similar results. To this end, we present three approximation techniques in order to speed up the algorithm: (1) aggressive pre-buffer slack pruning, (2) squeeze pruning, and (3) library lookup. Experimental results from industrial designs show that using these techniques together yields solutions in 9 to 25 times faster than van Ginneken style algorithms, while only sacrificing less than 3% delay penalty.

Placement migration is the movement of cells within an existing placement to address a variety of post-placement design closure issues, such as timing, routing congestion, signal integrity, and heat distribution. To fix a design problem, one would like to perturb the design as little as possible while preserving the integrity of the original placement. This work presents a new diffusion-based placement method based on a discrete approximation to a closed-form solution of the continuous diffusion equation. It has the advantage of smooth spreading, which helps preserve neighborhood characteristics of the original placement. Applying this technique to placement legalization demonstrates significant improvements in wire length and timing compared to other commonly used techniques.

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.

IP blocks and large macro cells are increasingly prevalent in physical design, actually causing an increase in the available free space for the dust logic. We observe that top-down placement, based on recursive bisection with multilevel partitioning, performs poorly on these porous designs. However, analytic solvers have the ability to find the natural distribution of cells in the layout. Consequently, we propose an enhancement to cut-based placement called analytic constraint generation (ACG). ACG utilizes an analytic engine to set constraints for the multi-level partitioner. We show that for real industry designs, ACG significantly improves the performance of cut-based placement, as implemented within a state-of-the-art industrial placer.

For optimizations like physical synthesis and static timing analysis, efficient interconnect delay and slew computation is critical. Since one cannot often afford to run AWE[12], constant time solutions are required. This work presents the first complete solution to closed form formulae for both delay and slew. Our metrics are derived from matching circuit moments to the lognormal distribution. From a single table, one can easily implement the metrics for delay and slew for both step and ramp inputs. Experiments validate the effectiveness of the metrics for nets from a real industrial design.