In recent years, an increasing number of papers have focused on the cell selection problem. However, previous papers fail to consider the actual problems of performing cell selection in the after placement and CTS optimization stages of industrial designs. This paper discusses the obstacles found when applying state-of-the-art Lagrangian relaxation-based cell selection in a real industrial flow. Solutions to such obstacles are presented, filling the gap in previous literature.

Timing-constrained power-driven gate sizing has aroused lot of research interest after the recent two discrete gate sizing contests organized by International Symposium on Physical Design. Since then, there are plenty of research papers published and new algorithms are proposed based on the ISPD 2013 contest formulation. However, almost all (new and old) papers in the literature ignore the details of how power-driven gate sizing fits in industrial physical synthesis flows, which limits their practical usage. This paper aims at filling this knowledge gap. We explain our approach to integrate a state-of-the-art Lagrangian Relaxation-based gate sizing into our actual physical synthesis framework, and explain the challenges and issues we observed from the point of view of VLSI design flows.

Advanced technology nodes have engendered new challenges in the design of integrated circuits (ICs), which can only be addressed through innovations in physical design techniques and algorithms. These challenges stem from factors such as increasingly complex manufacturing design rules, cell pin access in technologies utilizing multiple patterning and FinFETs, various types of restrictions and blockages on the routing layers, and complexity of the physical floorplan, for example due to irregular shapes of placeable areas. This issue and the next issue feature the special section on physical design aimed at addressing these challenges.

As VLSI technology continuously scales down, buffered clock tree synthesis (CTS) has become increasingly critical in an attempt to generate a high-performance synchronous chip design. This paper presents a novel obstacle-avoiding CTS approach with slew constraints satisfied and signal polarity corrected. We build a look-up table through NGSPICE simulation to achieve accurate buffer delay and slew, which guarantees that the final skew after NGSPICE simulation is as satisfactory as expected. Aiming at skew optimization under constraints of slew and obstacles, our CTS approach features the clock tree construction stage with the obstacle-aware topology generation algorithm called OBB, balanced insertion of candidate buffer positions and a fast heuristic buffer insertion algorithm. With an overall view on obstacles to explore the global optimization space, our CTS approach effectively overcomes the negative influence on skew brought by the obstacles. Experimental results show the effectiveness of our CTS approach with significantly improved skew and latency by 69.0% and 72.0% on average. In addition, the accuracy of the look-up table is demonstrated through the huge skew reduction by 87.3% on average. Moreover, our OBB heuristic algorithm obtains 53.2% improvement in skew than the classic balanced bipartition algorithm.

The eight papers in this special section highlight several studies on contemporary and emerging issues in physical design.

Routing congestion has become a critical layout challenge in nanoscale circuits since it is a critical factor in determining the routability of a design. An unroutable design is not useful even though it closes on all other design metrics. Fast design closure can only be achieved by accurately evaluating whether a design is routable or not early in the design cycle. Lately, it has become common to use a “light mode” version of a global router to quickly evaluate the routability of a given placement. This approach suffers from three weaknesses: (i) it does not adequately model local routing resources, which can cause incorrect routability predictions that are only detected late, during detailed routing; (ii) the congestion maps obtained by it tend to have isolated hotspots surrounded by noncongested spots, called “noisy hotspots”, which further affects the accuracy in routability evaluation; and (iii) the metrics used to represent congestion may yield numbers that do not provide sufficient intuition to the designer, and moreover, they may often fail to predict the routability accurately. This article presents solutions to these issues. First, we propose three approaches to model local routing resources. Second, we propose a smoothing technique to reduce the number of noisy hotspots and obtain a more accurate routability evaluation result. Finally, we develop a new metric which represents congestion maps with higher fidelity. We apply the proposed techniques to several industrial circuits and demonstrate that one can better predict and evaluate design routability and that congestion mitigation tools can perform much better to improve the design routability.

Based on a simple intuitive notion, in this paper, we propose an efficient post-placement improvement scheme. Based on the given timing slack distribution of a circuit, a corresponding “slack mountain map” can be visualized with peaks representing most violating (negative) slacks and valleys representing non-critical (positive) slacks respectively. Guided by this map, violating paths are eliminated or improved when slack mountains are flattened by applying a local logic perturbation technique (rewiring) iteratively to shift logic resources from critical to non-critical areas. Due to the locality property of the rewiring technique, to better avoid being stuck at local minimums, instead of running rewiring operations from the peak top towards lower areas, we do this local logic shifting starting from “sea areas” (most non-critical) towards peak (most critical) areas. At the end, as the slack map is more flattened, a circuit with slack violations more evenly distributed can be yielded. Comparing to the recent work [1], our experimental results demonstrate that this scheme can obtain a better or comparable delay reduction but with CPU time one order of magnitude smaller.

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.

For the last several technology generations, VLSI designs in new technology nodes have had to confront the challenges associated with reduced scaling in wire delays. The solution from industrial back-end-of-line process has been to add more and more thick metal layers to the wiring stacks. However, existing physical synthesis tools are usually not effective in handling these new thick layers for design closure. To fully leverage these degrees of freedom, it is essential for the design flow to provide better communication among the timer, the router, and different optimization engines. This work proposes a new algorithm, CATALYST, to perform congestion- and timing-aware layer directive assignment. Our flow balances routing resources among metal stacks so that designs benefit from the availability of thick metal layers by achieving improved timing and buffer usage reduction while maintaining routability. Experiments demonstrate the effectiveness of the proposed algorithm.

This work proposes a novel latch placement methodology by computing optimized placement templates with significantly lower local clock tree capacitance at a one-time cost per standard cell library. By directly minimizing local clock tree capacitance, overall chip power is reduced. The proposed methodology first generates optimized placement solutions for a wide range of input configurations. Then, a redundancy removal approach using set-theoretic annotation is proposed demonstrating it is possible to remove over 99% of the templates with no information loss. Finally, a decision tree induction algorithm with novel impurity metric enables extremely fast template selection during the clock optimization stage of a modern physical design flow. The proposed approach reduces the local clock tree capacitance by 20-30% on average roughly equating to between a 1 and 4 watt reduction in total dynamic power on a 100-watt 22-nm microprocessor. Additionally, because of a priori generation, template selection during physical design is extremely fast.

We have newly introduced the expert designer/user session (EDS) to ISPD in 2013, which is tailor-made for designers and users of physical design (PD) tools. Since ISPD is the premium PD-centric symposium, it is a great opportunity for designers, tools developers and PD researchers to interact and learn from each other. The benefit of including EDS in ISPD's program is twofold.

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.

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.

Industry routers are very complex and time consuming, and are becoming more so with the explosion in design rules and design for manufacturability requirements that multiply with each technology node. Global routing is just the first phase of a router and serves the dual purpose of (i) seeding the following phases of a router and (ii) evaluating whether the current design point is routable. Lately, it has become common to use a "light mode" version of the global router, similar to today's academic routers, to quickly evaluate the routability of a given placement. This use model suffers from two primary weaknesses: (i) it does not adequately model the local routing resources, while the model is important to remove opens and shorts and eliminate DRC violations, (ii) the metrics used to represent congestion are non-intuitive and often fail to pinpoint the key issues that need to be addressed. This paper presents solutions to both issues, and empirically demonstrates that incorporating the proposed solutions within a global routing based congestion analyzer yields a more accurate view of design routability.

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.

Placement is considered a fundamental physical design problem in electronic design automation. It has been around so long that it is commonly viewed as a solved problem. However, placement is not just another design automation problem; placement quality is at the heart of design quality in terms of timing closure, routability, area, power and most importantly, time-to-market. Small improvements in placement quality often translate into large improvements further down the design closure stack. This paper makes the case that placement is a "hot topic" in design automation and presents several placement formulations related to routability, clocking, datapath, timing, and constraint management to drive years of research.

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.

Designing a high-quality clock network is very important in very large-scale integrated designs today, as it is the clock network that synchronizes all the elements of a chip, and it is also a major source of power dissipation of a system. Early study by Pham in 2006 shows that about 18.1% of the total clock capacitance was due to this postgrid clock routing (i.e., lower mesh wires plus clock twig wires). In this paper, we proposed a partition-based path expansion algorithm to solve this postgrid clock routing problem effectively. Experimental results on industrial test cases show that our algorithm can improve over the latest work by Shelar on this problem significantly by reducing the wire capacitance by 24.6% and the wirelength by 23.6%.

Despite remarkable progress in the area of global routing, the burdens imposed by modern physical synthesis flows are far greater than those expected or anticipated by available (academic) routing engines. As interconnects dominate the path delay, physical synthesis such as buffer insertion and gate sizing has to integrate with layer assignment. Layer directives - commonly generated during wire synthesis to meet tight frequency targets - play a critical role in reducing interconnect delay of smaller technology nodes. Unfortunately, they are not presently understood or honored by leading global routers, nor do existing techniques trivially extend toward their resolution. The shortcomings contribute to a dangerous blindspot in optimization and timing closure, leading to unroutable and/or underperforming designs. In this paper, we aim to resolve the layer compliance problem in routing congestion evaluation and global routing, which is very critical for timing closure with physical synthesis. We propose a method of progressive projection to account for wire tags and layer directives, in which classes of nets are successively applied and locked while performing partial aggregation. The method effectively models the resource contention of layer constraints by faithfully accumulating capacity of bounded layer ranges, enabling three-dimensional assignment to subsequently achieve complete directive compliance. The approach is general, and can piggyback on existing interfaces used to communicate with popular academic engines. Empirical results on the IC-CAD 2009 benchmarks demonstrate that our approach successfully routes many designs that are otherwise unroutable with existing techniques and naïve approaches.

Buered clock tree synthesis (CTS) is increasingly critical as VLSI technology continually scales down. Many researches have been done on this topic due to its key role in CTS, but current approaches either lack the obstacle-avoiding functionality or lead to large clock latency and/or skew. This paper presents a new obstacle-avoiding CTS approach with separate clock tree construction and buer insertion stages based on an integral view to explore the global optimization space. Aiming at skew optimization under constraints of slew and obstacles, our CTS approach features the clock tree construction stage with the obstacle-aware topology generation algorithm called OBB, balanced insertion of candidate buer positions, and a fast heuristic buer insertion algorithm. Experimental results show the eectiveness of our CTS approach with significantly improved skew and latency than [6] by 46% and 63% on average, and 15.3% reduction in skew than [5]. Our OBB heuristic obtains 36% improvement in skew than the classic balanced bipartition algorithm (BB) in [10].

Summary form only given. The clock distribution network presents one of the most important design challenges in high-performance synchronous VLSI designs. However, automation in clock network synthesis is usually limited to local clock domains for two main reasons. (1) Global clock is too important for designers to take the risk of adopting a fully automated clocking flow. (2) Unlike in other EDA areas (such as synthesis/placement/routing), clock synthesis tools are highly tied to clock network topologies, ground/power planning, clock gating, macro floorplanning, clocking methodologies, etc. It is thus very difficult to implement a set of generic clock synthesis tools for design productivity considerations. That being said, industrial clocking methodologies usually resort to overdesigning because clock synthesis is just too critical to fail.

Clock distribution in VLSI designs is of crucial importance and it is also a major source of power dissipation of a system. For today's high performance microprocessors, clock signals are usually distributed by a global clock grid covering the whole chip, followed by post-grid routing that connects clock loads to the clock grid. Early study [2] shows that about 18.1% of the total clock capacitance dissipation was due to this post-grid clock routing (i.e., lower mesh wires plus clock twig wires). This post-grid clock routing problem is thus an important one but not many previous works have addressed it. In this paper, we try to solve this problem of connecting clock ports to the clock grid through reserved tracks on multiple metal layers, with delay and slew constraints. Note that a set of routing tracks are reserved for this grid-to-ports clock wires in practice because of the conventional modular design style of high-performance microprocessors. We propose a new expansion algorithm based on the heap data structure to solve the problem effectively. Experimental results on industrial test cases show that our algorithm can improve over the latest work on this problem [1] significantly by reducing the capacitance by 24.6% and the wire length by 23.6%. We also validate our results using hspice simulation. Finally, our approach is very efficient and for larger test cases with about 2000 ports, the runtime is in seconds.

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.

There have been significant prior efforts to quantify performance of academic placement algorithms, primarily by creating artificial test cases that attempt to mimic real designs, such as the PEKO benchmark containing known optimas [5]. The idea was to create benchmarks with a known optimal solution and then measure how far existing placers were from the known optimal. Since the benchmarks do not necessarily correspond to properties of real VLSI netlists, the conclusions were met with some skepticism. This work presents two custom constructed datapath designs that perform common logic functions with hand-designed layouts for each. The new generation of academic placers is then compared against them to see how the placers performed for these design styles. Experiments show that all academic placers have wirelengths significantly greater then the manual solution; solutions range from 1.75 to 4.88 times greater wirelengths. These testcases will be released publically to stimulate research into automatically solving structured datapath placement problems.

The move to low-k1 lithography makes it increasingly difficult to print feature sizes which are a small fraction of the wavelength of light. Manufacturing processes currently treat a target layout as a fixed requirement for lithography. However, in reality layout features may vary within certain bounds without violating design constraints. The knowledge of such tolerances, coupled with models for process variability, can help improve the manufacturability of layout features while still meeting design requirements. In this paper, we propose a methodology to convert electrical slack in a design to shape slack or tolerances on individual layout shapes using a two-phase approach. In the first step, we redistribute delay slack to generate delay bounds on individual cells using linear programming. In the second phase, which is solved as a quadratic program, we convert these delay bounds to shape tolerances to maximize the process window of each shape. The shape tolerances produced by our methodology can be used within a process-window optical proximity correction (PWOPC) flow to reduce delay errors arising from variations in the lithographic process. Our experiments on 45 nm SOI cells using accurate process models show that the use of our shape slack generation in conjunction with PWOPC reduces delay errors from 3.6% to 1.4%, on average, compared to the simplistic way of tolerance band generation.

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.

In the talk, the details of ISPD 2010 high performance clock network synthesis contest will be introduced. Compared to first clock network synthesis contest in 2009, the rules have been revised to better reflect the real problems from the industry. Instead of clock latency range upon two simulations with different supply voltage settings, the total clock power (modeled by capacitance) is set to be the major judging criteria. However, a valid clock distribution network solution must have local clock skew under a preset limit. Only local clock skew constraints will be enforced because (1) early mode timing violations are often limited in local regions, and (2) local timing violations often directly lead to congestion problems which are very hard to fix. Moreover, delay variation will be formulated in the contest and simplified Monte Carlo simulation will be used to evaluate valid solutions. More importantly, a new set of benchmarks will be announced and used to decide the winner of the contest. These test-cases are all directly derived from real industrial microprocessor and high-performance ASIC designs and they have over 1000 clock sinks. More than ten academic clock synthesis tools have participated in the contest and the final results will be announced during this talk.

Clock network synthesis (CNS) is one of the most important design challenges in high performance synchronized VLSI designs. However, without appropriate problem examples and real-world objectives, research can become less relevant to industrial design flows. To address the need of the research community, we organize a clock network synthesis contest and a set of benchmark suite is released. Since the full-specification physical and electrical requirements of a leading-edge processor clock distribution would be cumbersome and impractical for this contest, we make the problem formulation familiar to the academia; that is to synthesize, buffer, and tune a clock distribution. However, the objective function has been modified to appropriately include the increasing importance of robustness to variation, in addition to the typical performance and power metrics. The paper briefly describes the ISPD clock network synthesis contest and the benchmark suite.

The purpose of global placement is to find non-overlapping locations for cells, typically while minimizing a wirelength objective. Because of this objective, however, when more timing information about the design is known, some cells will inevitably be sub-optimally placed from a timing perspective. In this paper, we present two new techniques to incrementally improve placements by moving cells to their optimal timing locations. We call our approach Pyramids, since it uses pyramid-shaped delay surfaces to solve for the optimal location, rather than running a more expensive linear programming solver. We show how to apply these techniques to timing-driven detailed placement and also for more accurate late-stage incremental timing correction. Experimental results validate the effectiveness of Pyramids by showing significantly improved timing after an industrial placement algorithm. Furthermore, compared to the linear programming solvers, the speedup of Pyramids solver is 373x vs. CLP and 448x vs. GLPK.

This paper describes the ISPD global routing benchmark suite and related contests. Total 16 global routing benchmarks are produced from the ISPD placement contest benchmark suite using a variety of publicly available academic placement tools. The representative characteristics of the ISPD global routing benchmark suite include multiple metal layers with layer assignment requirement, wire and via width/space modeling, and macro porosity modeling. The benchmarks have routable nets from 200 thousand 1.6 million. While primarily intended for global routing, they can be certainly extended for detailed routing or routing congestion estimation. In conjunction with the previous ISPD placement contest benchmark suite, the new global routing benchmarks will present realistic and challenging physical design problems of modern complex IC designs

Physical synthesis tools are responsible for achieving timing closure. Starting with 130nm designs, multiple cycles are required to cross the chip, making latch placement critical to success. We present a new physical synthesis optimization for latch placement called RUMBLE (Rip Up and Move Boxes with Linear Evaluation) that uses a linear timing model to optimize timing by simultaneously re-placing multiple gates. RUMBLE runs incrementally and in conjunction with static timing analysis to improve the timing for critical paths that have already been optimized by placement, gate sizing, and buffering. Experimental results validate the effectiveness of the approach: our techniques improve slack by 41.3% of cycle time on average for a large commercial ASIC design

Physical-synthesis tools are responsible for achieving timing closure. Starting with 130-nm designs, multiple cycles are required to cross the chip, making latch placement critical to success. We present a new physical-synthesis optimization for latch placement called Rip Up and Move Boxes with Linear Evaluation (RUMBLE) that uses a linear timing model to optimize timing by simultaneously replacing multiple gates. RUMBLE runs incrementally and in conjunction with static timing analysis to improve the timing for critical paths that have already been optimized by placement, gate sizing, and buffering. Experimental results validate the effectiveness of the approach: Our techniques improve slack by 41.3% of cycle time on average for a large commercial ASIC design.

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

As a prevalent constraint, sharp slew rate is often required in circuit design, which causes a huge demand for buffering resources. This problem requires ultrafast 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 using the maximum matching technique 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. Fourth, buffer blockage avoidance is handled, which makes the algorithms ready for practical use. Experiments on industrial netlists demonstrate that our algorithms are very effective and highly efficient: we achieve about 90x speedup and save up to 20% buffer area over the commonly used van Ginneken style buffering. The new algorithms also significantly outperform previous works that indirectly address the slew buffering problem.

Along with the progress of very-large-scale-integration 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 suboptimal delay or unnecessary buffer expense due to the lack of global view. In this paper, we propose a novel path-based-buffer-insertion (PBBI) scheme which can overcome the weakness of the net-based approaches. We also discuss some potential difficulties of the PBBI 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.

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 performancedriven 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 timingdriven 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 > 100X speed up and save up to 40% buffer area over the commonly-used van Ginneken style buffering.

The clock distribution network is a key component on any synchronous VLSI design. As technology moves into the nanometer era, innovative clocking techniques are required to solve the power dissipation and variability issues. Rotary clocking is a novel technique which employs unterminated rings formed by differential transmission lines to save power and reduce skew variability. Despite its appealing advantages, rotary clocking requires latch locations to match pre-designed clock skew on rotary clock rings. This requirement is a difficult chicken-and-egg problem which prevents its wide application. In this work, we proposed an integrated placement and skew scheduling methodology to break this hurdle, making rotary clocking compatible with practical design flows. A network flow based latch assignment algorithm and a cost-driven skew optimization algorithm are developed. Experiments show that our method can generate chip placements which satisfy the unique requirements of rotary clocks, without sacrificing design quality. By enabling concurrent clock network and placement design, our method can also be applied in other clocking methodologies as well

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.

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

In modern VLSI designs, the increasingly severe power problem requests to minimize clock routing wirelength so that both power consumption and power supply noise can be alleviated. In contrast to most of traditional works that handle this problem only in clock routing, we propose to navigate standard cell register placement to locations that enable further less clock routing wirelength and power. To minimize adverse impacts to conventional cell placement goals such as signal net wirelength and critical path delay, the register placement is carried out in the context of a quadratic placement. The proposed technique is particularly effective for the recently popular prescribed skew clock routing. Experiments on benchmark circuits show encouraging results.

The synthesis of clock network in the presence of process variation is becoming a vital design issue towards the performance of digital circuits. In this paper, we propose a clock tree design algorithm which is driven by the tolerance towards process variations. We consider tolerance to process variation in various stages of clock tree synthesis which include clock skew scheduling, abstract tree generation and layout embedding. The primary objective of this work is to minimize the maximum skew violation and a layout embedding technique specifically targeting this objective is detailed. Experimental results indicate the our proposed procedure leads to significant reduction in maximum skew violation due to process variation with negligible change in wire length.

The progress of VLSI technology is facing two limiting factors: power and variation. Minimizing clock network size can lead to reduced power consumption, less power supply noise, less number of clock buffers and therefore less vulnerability to variations. Previous works on clock network minimization are mostly focused on clock routing and the improvements are often limited by the input register placement. In this work, we propose to navigate registers in cell placement for further clock network size reduction. To solve the conflict between clock network minimization and traditional placement goals, we suggest the following techniques in a quadratic placement framework: (1) Manhattan ring based register guidance; (2) center of gravity constraints for registers; (3) pseudo pin and net; (4) register cluster contraction. These techniques work for both zero skew and prescribed skew designs in both wirelength driven and timing driven placement. Experimental results show that our method can reduce clock net wirelength by 16%~33% with no more than 0.5% increase on signal net wirelength compared with conventional approaches.

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.

Closed formed 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 (1998) is extended to show how one can model the blocks into a simple delay estimation technique that applies both to two-pin and to multi-pin 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. Our experiments show that our approach accurately predicts delay when compared to constructing a realizable buffer insertion with multiple buffer types.

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 this paper, an effective algorithm is presented for multilevel circuit clustering for delay minimization, and is applicable to hierarchical field programmable gate arrays. With a novel graph contraction technique, which allows some crucial delay information of a lower-level clustering to be maintained in the contracted graph, our algorithm recursively divides the lower-level clustering into the next higher-level one in a way that each recursive clustering step is accomplished by applying a modified single-level circuit clustering algorithm based on . We test our algorithm on the two-level clustering problem and compare it with the latest algorithm in . Experimental results show that our algorithm achieves, on average, 12% more delay reduction when compared to the best results (from TLC with full node-duplication) in . In fact, our algorithm is the first one for the general multilevel circuit clustering problem with more than two levels.

Abstract | In this paper, an eective algorithm is pre-sented for performance driven multi-level clustering for com-binational circuits, and is applicable to hierarchical FPGAs. With a novel graph contraction technique, which allows some crucial delay information of a lower-level clustering to be maintained in the contracted graph, our algorithm recur-sively divides the lower-level clustering into the next higher-level one in a way that each recursive clustering step is ac-complished by applying a modied single-level circuit clus-tering algorithm based on [1]. We test our algorithm on the two-level clustering problem and compare it with the latest algorithm in [2]. Experimental results show that our algorithm achieves, on average, 12 % more delay reduction when compared to the best results (from TLC with full node-duplication) in [2]. In fact, our algorithm is the rst one for the general multi-level circuit clustering problem with more than two levels. I.

This paper considers the area-constrained clustering of combinational circuits for delay minimization under a more general delay model, which practically takes variable interconnect delay into account. Our delay model is particularly applicable when allowing the back-annotation of actual delay information to drive the clustering process. We present a vertex grouping technique and integrate it with the algorithm (Rajaraman and Wong, 1995) such that our algorithm can be proved to solve the problem optimally in polynomial time.

In this paper, we present a competent algorithm to the alternative wiring problem by exploring the relationship between dominators of a target wire. Alternative wiring refers to the process of adding a redundant connection to a circuit such that a target connection will become redundant and can be removed from the circuit. The well-known ATPG-based alternative wiring scheme. Redundancy Addition and Removal for Multi-level Boolean Optimization (RAMBO), has shown its effectiveness in solving the problem in the last decade. The deficiency of RAMBO lies in its long execution time for redundancy identification among a large set of candidate alternative wires in the circuit. Implication-tree Based Alternative Wiring Logic Transformation Algorithm (IBAW) improves the speed of RAMBO by introducing an implication-tree structure for source node identification. Our approach of investigating the dominator relationship suggest that a large subset of unnecessary redundancy checks can be further avoided in order to improve the efficiency. Experiments were performed on MCNC benchmark circuits and results are compared to those of RAMBO and IBAW. Results show that our proposed algorithm improves IBAW with a 2.3 times speedup. Moreover, our implementation runs 8.8 times faster than RAMBO while solution quality is still maintained.