The increasing reliance on third-party intellectual property (IP) cores in modern integrated circuit (IC) design has introduced significant security vulnerabilities, particularly the risk of Hardware Trojans (HTs). These malicious modifications can compromise system integrity, leading to data leakage, unauthorized access, or functional failures. Traditional detection methods often depend on the availability of a golden chip, which is not always feasible. This paper presents the 2025 ICCAD CAD Contest Problem A, which challenges participants to develop machine learning-based solutions for detecting HTs directly from gate-level netlists without requiring a golden reference. The problem is formulated with defined Trojan behaviors, input/output specifications, and evaluation metrics, including correctness and F1 score. The contest aims to foster innovation in HT detection by leveraging advanced data-driven techniques and scalable analysis frameworks.

Logical equivalence checking (LEC, or EC) is critical to design implementation and for decades has allowed cost-efficient RTL-level functional testing to be the dominant type of verification done on a project. Test once, then formally prove that the subsequent design stages later in the implementation flow are 100% logically equivalent. But over the last 10-15 years, SoCs have grown 100X in complexity, creating new challenges.

Traditionally, logic synthesis/optimization metric would be majorly determined by PPA (power, performance, area). However, as the technology node shrinks and the design process becomes extremely complicated, iterative optimization flow and local re-synthesis might be invoked to optimize for more variant purposes. It is necessary to have a methodology which is not just a simple cost-function-based algorithm but also can optimize and legalize a design according to a more complex cost estimator.

The Prim-Dijkstra (PD ) construction [1] was first presented over 20 years ago as a way to efficiently trade off between shortest-path and minimum-wirelength routing trees. This approach has stood the test of time, having been integrated into leading semiconductor design methodologies and electronic design automation tools. PD optimizes the conflicting objectives of wirelength (WL) and source-sink pathlength (PL) by blending the classic Prim and Dijkstra spanning tree algorithms. However, as this work shows, PD can sometimes demonstrate significant suboptimality for both WL and PL. This quality degradation can be especially costly for advanced nodes because (i) wire delays form a much larger component of total stage delay, i.e., timing-driven routing is critical, and (ii) modern designs are severely power-constrained (e.g., mobile, IoT), which makes low-capacitance wiring important. Consequently, achieving a good timing and power tradeoff for routing is required to build a market-leading product[2]. This work introduces a new problem formulation that incorporates the total detour cost in the objective function to optimize the detour to every sink in the tree, not just the worst detour. We then propose a new PD-II construction which directly improves upon the original PD construction by repairing the tree to simultaneously reduce both WL and PL. The PD-II approach achieves improvement for both objectives, making it a clear win over PD, for virtually zero additional runtime cost. PD-II is a spanning tree algorithm (which is useful for seeding global routing); however, since Steiner trees are needed for timing estimation, this work also includes a post-processing algorithm called DAS to convert PD-II trees into balanced Steiner trees. Experimental results demonstrate that this construction outperforms the recent state-of-the-art academic tool, SALT [36], for high-fanout nets, achieving up to 36.46% PL improvement with similar WL on average for 20K nets of size ≥ 32 terminals from DAC 2012 contest benchmark designs [37].

As very large-scale integration technology shrinks to fewer tracks per standard cell, e.g., from 10 to 7.5-track libraries (and lesser for 7 nm), there has been a rapid increase in the usage of multiple-row cells like two- and three-row flip-flops, buffers, etc., for design closure. Additionally, the usage of multibit flip-flops or flop trays to save power creates large cells that further complicate critical design tasks, such as placement. Detailed placement happens to be a key optimization transform, which is repeatedly invoked during the design closure flow to improve design parameters, such as wirelength, timing, and local wiring congestion. Advanced node designs, with hundreds of thousands of multiple-row cells, require a paradigm change for this critical design closure transform. The traditional approach of fixing multiple-row cells during detailed placement and only optimizing the locations of single-row standard cells can no longer obtain appreciable quality of results. It is imperative to have new techniques that can simultaneously optimize both multiple- and single-row height cell locations during detailed placement. In this paper, we propose a new density-aware detailed placer for heterogeneous-sized netlists. Our approach consists of a chain move scheme that generalizes the movement of heterogeneous-sized cells, a nested dynamic programming-based approach for ordered double-row placement and a network flow-based formulation to solve ordered multiple-row placement for wirelength and density optimization. Experimental results demonstrate the effectiveness of these techniques in wirelength minimization and density smoothing compared with the most recent detailed placers for designs with heterogeneous-sized cells.

As a promising candidate for next generation lithography, multiple e-beam lithography (MEBL) is able to improve manufacturing throughput using parallel beam printing. In MEBL, a layout is split into stripes and the layout patterns are cut by stripe boundaries, then all the stripes are printed in parallel. If a via pattern or a vertical long wire is overlapping with a stitch, it may suffer from poor printing quality due to the so called stitch error; then the circuit performance may be degraded. In this paper, we propose a comprehensive study on the stitch aware detailed placement to simultaneously minimize the stitch error and optimize traditional objectives, e.g., wirelength and density. Experimental results show that our algorithms are very effective on modified ICCAD 2014 benchmarks that zero stitch error is guaranteed while the scaled half-perimeter wirelength is very comparable to a state-of-the-art detailed placer.

As VLSI technology shrinks to fewer tracks per standard cell, e.g., from 10-track to 7.5-track libraries (and lesser for 7nm), there has been a rapid increase in the usage of multiple-row cells like two- and three-row flip-flops, buffers, etc., for design closure. Additionally, the usage of multi-bit flip-flops or flop trays to save power creates large cells that further complicate critical design tasks, such as placement. Detailed placement happens to be a key optimization transform, which is repeatedly invoked during the design closure flow to improve design parameters, such as, wirelength, timing, and local wiring congestion. Advanced node designs, with hundreds of thousands of multiple-row cells, require a paradigm change for this critical design closure transform. The traditional approach of fixing multiple-row cells during detailed placement and only optimizing the locations of single-row standard cells can no longer obtain appreciable quality of results. It is imperative to have new techniques that can simultaneously optimize both multiple- and single-row high cell locations during detailed placement. In this paper, we propose a new density-aware detailed placer for heterogeneous-sized netlists. Our approach consists of a chain move scheme that generalizes the movement of heterogeneous-sized cells as well as a nested dynamic programming based approach for wirelength and density optimization. Experimental results demonstrate the effectiveness of these techniques in wirelength minimization and density smoothing compared with the most recent detailed placer for designs with heterogeneous-sized cells.

As the feature size of semiconductor process further scales to sub-16 nm technology node, triple patterning lithography (TPL) has been regarded as one of the most promising lithography candidates along with extreme ultraviolet, electron beam lithography, and directly self-assembly. M1 and contact layers, which are usually deployed within standard cells, are the most critical and complex parts for modern digital designs. Traditional design flow that ignores TPL in early stages may limit the potential to resolve all the TPL conflicts. In this paper, we propose a coherent framework, including standard cell compliance and detailed placement, to enable TPL friendly design. Considering TPL constraints during early design stages, such as standard cell compliance, improves the layout decomposability. With the precoloring solutions of standard cells, we present a TPL aware detailed placement where the layout decomposition and placement can be resolved simultaneously. In addition, we propose a linear dynamic programming to solve TPL aware detailed placement with maximum displacement, which can achieve good trade-off in terms of runtime and performance. Experimental results show that our framework can achieve zero conflict, meanwhile can effectively optimize the stitch number and placement wire-length.

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.

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.

Optical microlithography is the technique of printing a set of shapes on a wafer using light transmitted through a template called a mask. Repeatedly printing and stacking such shapes on top of each other to build electrical circuits allows us to manufacture chips in high volume. However this technique has now reached its fundamental physical limits of resolution. Current 193nm wavelength light is no longer sufficient to reliably transfer patterns which are now in the sub-100nm dimensional range. This has led to increased research in optimizing lithographic masks to pre-compensate for distortions introduced by the lithographic process. This is called mask optimization. In this contest, students are provided with a sample lithographic model which simulates the transfer of a mask pattern on to wafer. The mask is assumed to be a pixelated template, where every pixel can be turned on or off, to indicate where light passes through, or is blocked. Contestants are also provided with models to predict the robustness of their pattern i.e. how much variability is in the transferred pattern. Given these tools, the objective is to minimize the variability in the wafer image, as measured by process variability (PV) bands. This is subject to the constraints of runtime and satisfying pattern fidelity i.e. the transferred pattern should resemble the target pattern. Benchmarks are provided in the form of collections of geometric shapes, each of which provides a challenge in printing at sub-wavelength.

Contests and their benchmarks have become an important driving force to push our EDA domain forward in different areas lately, such as ISPD, TAU, DAC contests. The annual CAD Contest in Taiwan has been held for 13 consecutive years and has successfully boosted the EDA research momentum in Taiwan. To encourage better research development on timely and practical EDA problems across all domains, CAD Contest is internationalized since 2012 under the joint sponsorship of the IEEE CEDA and Ministry of Education (MOE) of Taiwan. 2012 CAD Contest attracted 56 teams from 7 regions, including USA, Japan, Mainland China, Hong Kong, Korea, Italy, and Taiwan. Continuing its great success in 2012, 2013 CAD contest attracts 87 teams from 9 regions, including USA, Canada, Brazil, India, Russia, Japan, Mainland China, Hong Kong and Taiwan, achieving 55% growth. Three contest problems on technology mapping, placement, and mask optimization are announced this year and run by industry experts from Cadence and IBM. Topic chair Hwei-Tseng Wang of Cadence Design Systems manages the first contest problem, concentrating on technology mapping for macro blocks. The implementation of a digital function is more flexible and powerful as technology advances. Therefore, how to fully utilize and reuse macro blocks in a highly optimized design becomes an important issue. However, it is challenging to identify the boundaries of macro blocks in such complex netlists. For the first problem, contestants are required to map and replace a given design by a set of macro blocks as much as possible. Topic chair Myung-Chul Kim of IBM manages the second problem, focusing on the placement finishing step, detailed placement and legalization. Placement, which determines locations of circuit elements, is one of the most crucial steps in the modern IC design flow. Although there are significant improvements on global placement techniques via recent placement contests, the need for high performance detailed placement continues to grow. For the second problem, contestants are required to perform local refinements on a legal design such that the total wirelength, placement/pin density are optimized. Topic chair Shayak Banerjee of IBM manages the third problem, exploring lithography mask optimization. As technology advances, the printed feature size is smaller than the wavelength of the light shining through the mask. The subwavelength gap causes unwanted shape distortions. To compensate these distortions, mask optimization is performed. For the third problem, contestants are required to find the best mask solution for a given pixelated layout. The best mask solution means least EPE violations and minimum process variations over different corners measured by a provided lithography simulation model. This session will include three presentations from the contest organizers for these contest problems and an award ceremony. Each contest organizer (topic chair) will present detailed information about the corresponding contest problem, including problem description, benchmarks, and evaluation. Along with the contest, a new set of industrial benchmarks for each contest problem will be released and facilitate scientific evaluations of related research results. We expect that the benchmark suites will further play a key driving force to push the advancement of related research. Moreover, we also expect that the participants will submit their works to the subsequent top conferences to boost related research and also extend the impacts of this contest.

At advanced technology nodes, highly-optimized placements need careful post-processing to further reduce interconnect length or optimize resource distribution, and therefore, high-performance legalization and detailed placement steps are essential for performance. In the last decade, we observed impressive improvements both in quality and speed of academic placement algorithms, in part enabled by the availability of realistic benchmarks and common evaluation frameworks along the history of ISPD, DAC and ICCAD placement contests. However, most research innovations have heavily relied on improvement and extensions of global placement algorithms [4, 5, 8, 9, 12, 15]. Detailed placement has been often limited to mixing existing methods and local interconnect length recovery, and individual impacts and relative performances of different detailed placement algorithms remain unclear. The goal of the ICCAD-2013 detailed-placement contest is to address these issues. In this contest, we provide (i) a suite of realistic benchmarks derived from industrial ASIC including input legal placements to detailed placers, and (ii) an evaluation framework to specifically measure the impact of detailed placement optimizations. To judge the quality of resulting placements, we consider both Half-Perimeter Wirelength (HPWL) and placement density, and impose maximum cell displacement limitations to the detailed placers. We hope that a set of standardized benchmarks and an evaluation framework will further accelerate research in the area of detailed placement.

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.

As technology scales and frequencies increase, a new hybrid design style emerges, wherein designs contain a mixture of random logic and datapath standard-cell components. This paper demonstrates that conventional half-perimeter wirelength driven placers underperform in terms of regularity and Steiner wirelength (StWL) for such hybrid designs. In addition, the quality gap between manual and automatic placement is more pronounced as the designs become more datapath oriented. To effectively handle hybrid designs, this paper proposes a new unified placement flow that simultaneously places random logic and datapath cells. This flow is built on the top of a leading academic force-directed placer and significantly improves the quality of datapath placement while leveraging the speed and flexibility of existing random-logic placement algorithms. It consists of a suite of novel global and detailed placement techniques, collectively called structure-aware placement techniques (SAPT). These techniques effectively integrate alignment constraints into placement, thereby overcoming the deficiencies of existing random-logic placers when handling designs with embedded datapaths. Compared to other state-of-the-art placers, SAPT improves total StWL by more than 28% and total routing overflow by over six times on the ISPD 2011 datapath benchmark suite. In addition, it improves total StWL by 5.8% on industrial hybrid designs.

We propose a new yield estimation algorithm which estimates the acceptability region as the union of spherical cones. The algorithm works by dividing the input parameter space into approximately equi-probable cones, efficiently estimating the refined weight contributions for each cone, then combining the results to get the total yield. The algorithm is broadly similar to the worst-case-distances method, but is more generally applicable for cases with -for example- multiple failure regions. The algorithm is quite accurate, and offers several orders (>100x) of magnitude of speedup compared to traditional Monte Carlo. The paper includes example applications to difficult high-yield circuits like SRAM.

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.

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.

Contests and their benchmarks have become an important driving force to push our EDA domain forward in different areas lately, such as ISPD, TAU, DAC contests. To encourage better research development on timely and practical EDA problems across all domains, a new international CAD Contest is held this year under the joint sponsorship of the IEEE CEDA and Ministry of Education (MOE) of Taiwan. Three contest problems on functional ECO, placement, and litho hotspot identification are announced this year and run by industry experts from Cadence, IBM and Mentor Graphics.

Although power grid analysis has been an active research area for a number of years, increasing chip size has exposed new challenges in this traditional topic. The simulation of these large scale networks is becoming a dominant step in the design verification flow and it often requires the very largest computer available to the design team. To spur academic research in this vital verification step, the IBM Austin Research Laboratory, with support from the ACM TAU Workshop, has successfully organized two annual TAU Power Grid Simulation Contests, and over twenty university teams across the world have participated. For 2012, the contest is focused on dynamic analysis and parallel implementation.

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.

As technology scales and frequency increases, a new design style is emerging, referred to as hybrid designs, which contain a mixture of random logic and datapath standard cell components. This work begins by demonstrating that conventional Half-Perimeter Wire Length (HPWL)-driven placers under-perform in terms of regularity and Steiner Wire Length (StWL) for such hybrid designs, and the quality gap between manual placement and automatic placers is more pronounced as the designs become more datapath-oriented. Then, a new unified placement flow that simultaneously handles random logic and datapath standard cells is proposed that significantly improves the placement quality of the datapath while leveraging the speed of modern state-of-the-art placement algorithms. The placement flow is built on top of a leading academic force-directed placer. It consists of a series of novel global and detailed placement techniques, collectively called Structure Aware Placement Techniques (SAPT). The techniques effectively integrate alignment constraints into placement, overcoming the deficiencies of the HPWL objective. Experimental results comparing our placement flow with six state-of-the-art placers on the ISPD 2011 Datapath Benchmark Suite show at least a 32% improvement in total StWL with over a 6x improvement in total routing overflow. In addition, the flow demonstrates an 8.25% improvement in total StWL on industrial hybrid designs.

Buffer insertion is an effective technique to reduce interconnect delay. In this paper, we give a simple$O(mn)$time algorithm for optimal buffer insertion, where$m$is the number of sinks and$n$is the number of buffer positions. When$m$is small, our algorithm is a significant improvement over the recent$O(n\log^{2}n)$time algorithm by Shi and Li, and the$O(n^{2})$time algorithm of van Ginneken. For$b$buffer types, our algorithms runs in$O(b^{2}n+bmn)$time, an improvement of the recent$O(bn^{2})$algorithm by Li and Shi. The improvement is made possible by an innovative linked list that can perform addition of a wire, addition of a buffer in amortized$O(1)$time, and smart design of pointers. We then present the extension of our algorithm for the buffer cost minimization problem, which improves the previous best algorithm. On industrial test cases, the new algorithms is faster than previous best algorithms by an order of magnitude.

Benchmark suite is an immensely useful tool in performing research since it allows for rapid and clear comparison between different approaches to solving CAD problems. Technology scaling with decrease in supply voltage, increase in power density and frequency will continue to impose strong challenges in designing of robust power delivery networks. An accurate analysis of power delivery networks has become an absolute necessity. A critical issue in power grid analysis is the large size of the power grid network. At the 45-nm technology node, the typical size of the power grid network is in the range of hundreds of million nodes. In this paper, we review the TAU 2011 Power Grid Simulation Contest. This contest was held to seek new efficient methods for solving very large power grid networks. Accuracy, run-time and memory were used as metrics to evaluate the solutions and consequently, prizes were awarded to the top three teams. The benchmarks in [1] are expanded to include larger networks that were created from real industry designs. These are made public along with the score from various teams that participated in the contest. These new benchmarks would aid in furthering academic research to address the increasing demands in the analysis of very large power grid networks.

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.

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.

Local routing congestion is becoming increasingly important as complex design rules make local pin access the bottleneck for modern designs and routers. Since congestion analysis based on global routing does not model these effects, routability-driven placement and physical synthesis fail to alleviate local congestion. This work models routing congestion at the placement level in order to apply local congestion mitigation. We propose a local congestion metric that computes a “routing-difficulty” score for every cell in the design library. To disperse local congestion, we apply a suite of detailed placement techniques called MILOR (Movement, cell Inflation and Legalization, and Optimization within a Row). Experimental results show that our techniques can significantly improve routing quality on real industry designs from 65, 45, and 32 nanometer technologies.

Traditionally, the goal of physical synthesis has been to produce a physical realization of the input netlist that meets its timing constraints with minimum area. However, design routability has emerged from a secondary objective to perhaps the primary objective, in no small part due to the myriad of rules and constraints that emerge with each successive technology. This work overviews the complexities with modeling congestion during physical synthesis and discusses how optimizations may be able to provide some relief.

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.

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.

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.

As VLSI technology moves to the 65nm node and beyond, interconnect delay greatly limits the circuit performance. As a critical component in interconnect synthesis, layer assignment manifests enormous potential in drastically reducing wire delay. This is due the fact that wires on thick metals are much less resistive than those on thin metals. Nevertheless, it is not desired to assign all wires to thick metals and the right strategy is to only use minimal thick-metal routing resources for meeting the timing constraints. This timing driven minimum cost layer assignment problem is NP-Complete, and a fast algorithm with provable approximation bound is highly desired.

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 VLSI technology enters the nanoscale regime, interconnect delay becomes the bottleneck of circuit performance. Compared to gate delays, wires are becoming increasingly resistive which makes it more difficult to propagate signals across the chip. However, more advanced technologies (65 nm and 45 nm) provide relief as the number of metal layers continues to increase. The wires on the upper metal layers are much less resistive and can be used to drive further and faster than on thin metals. This provides an entirely new dimension to the traditional wire sizing problem, namely, layer assignment for efficient timing closure. Assigning all wires to thick metals improves timing, however, routability of the design may be hurt. The challenge is to assign minimal amount of wires to thick metals to meet timing constraints. In this paper, the minimum cost layer assignment problem is proven to be NP-Complete. As a theoretical solution for NP-complete problems, a polynomial time approximation scheme is proposed. The new algorithm can approximate the optimal layer assignment solution by a factor of 1 + isin in O(mlog logmldrn3/isin2) time for 0 < isin < 1, where n is the number of nodes in the tree and m is the number of routing layers. This work presents the first theoretical advance for the timing-driven minimum cost layer assignment problem. In addition to its theoretical guarantee, the new algorithm is highly practical. Our experiments on 500 test cases demonstrate that the new algorithm can run 2times faster than the optimal dynamic programming algorithm with only 2% additional wire.

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.

We present a novel power-aware yield enhancement design methodology and reconfiguration scheme for deep submicron SRAM designs. We show that with the continued trend of raising array supply to counter process variations, it is more effective to use a per-element selectable virtual power-supply scenario as opposed to single array supply with traditional redundancy schemes. The element can be a bank, a sub-array, or an independent row/column, and the element's virtual supply value is determined based on fail bitmaps. The technique can also be used in conjunction with traditional redundancy schemes to further improve the efficiency. The supply and redundancy assignments can be obtained by relying on memory reconfiguration algorithms. For this, we propose a greedy yet accurate algorithm that runs in O(nlogn) as opposed to average case O(n2) traditional algorithms. The methodology leads to significant power savings ranging from 20% to 50% for 65nm technology. We expect the savings to increase in future technologies as leakage powers dominate. To the best of our knowledge, this is the first time such a methodology is applied to SRAM designs.

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

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.

Even with the wide adaptation of resolution enhancement techniques in sub-wavelength lithography, the geometry of the fabricated interconnect is still quite different from the drawn one. Existing layout parasitic extraction (LPE) tools assume perfect geometry, thus introducing significant error in the extracted parasitic models, which in turn cases significant error in timing verification and signal integrity analysis. Our simulation shows that the RC parasitics extracted from perfect GDS-II geometry can be as much as 20% different from those extracted from the post litho/etching simulation geometry. This paper presents a new LPE methodology and related fast algorithms for interconnect parasitic extraction under photolithographic effects. Our methodology is compatible with the existing design flow. Experimental results show that the proposed methods are accurate and efficient.

In modern VLSI circuits, metal conductors are separated by multiple planar, conformal or embedded dielectric media. Previous algorithms based on Boundary Element Method (BEM) are inefficient to extract interconnect capacitance due to the complex dielectric structures. In this paper, we present a new algorithm that combines multilayer Green's function with the equivalent charge method to efficiently deal with the complex dielectrics. The multilayer Green's function is efficient to model layered dielectric media, while the equivalent charge method is powerful to model non-planar complex dielectric. Our method can also model ground plane and reflective boundary wall. From experimental results, the new method is significantly faster than previous methods in realistic conditions, i.e., 70X speedup and 99% memory saving compared with FastCap and 2X speedup and 80% memory saving compared with PHiCap for complex dielectric structure with similar accuracy.

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.

Most existing methods for interconnect wire sizing are designed for RC trees. With the increasing popularity of the non-tree topology in clock networks and multiple link networks, wire sizing for non-tree networks becomes an important problem. In this paper, we propose the first systematic method to size the wires of general non-tree RC networks. Our method consists of three steps: 1) decompose a non-tree RC network into a tree RC network such that the Elmore delay at every sink remains unchanged; 2) size wires of the tree; and 3) merge the wires back to the original non-tree network. All three steps can be implemented in low-order polynomial time. Using this method, previous wiresizing techniques for tree topology for various objectives, such as minimizing the maximum delay, minimizing the total area or power, and reducing skew variability under process variations, can be applied to non-tree topologies. For certain types of networks, such as the tree+link network, our method gives the optimal solution, provided the tree wire sizing is optimal. Compared with the previous best wire-sizing method for non-tree circuits we can achieve 2% to 17% Elmore delay reduction with 14% to 30% total wire area reduction. Compared with unsized minimum width networks, our delay is 25% less and the skew is 34% less, under SPICE simulation. For the tree+link network, we can achieve significant delay reduction and zero skew in nominal case, while get up to 66% skew variation reduction.

Buffer insertion is an effective technique to reduce interconnect delay. In this paper, we give a simple O(mn) time algorithm for optimal buffer insertion, where m is the number of sinks and n is the number of buffer positions. This is the first linear time buffer insertion algorithm for nets with constant number of sinks. When m is small, it is a significant improvement over our recent O(nlog/sup 2/n) time algorithm, and the O(n/sup 2/) time algorithm of van Ginneken. For b buffer types, the new algorithm runs in O(b/sup 2/n + bmn) time, an improvement of our recent O(bn/sup 2/) algorithm. The improvement is made possible by a clever bookkeeping method and an innovative linked list data structure that can perform addition of a wire, and addition of a buffer in amortized O(1) time. On industrial test cases, the new algorithm is faster than previous best algorithms by an order of magnitude.

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.

Most existing buffer insertion algorithms, such as van Ginneken's algorithm, consider only individual nets. As a result, these algorithms tend to over buffer when applied to combinational circuits, since it is difficult to decide how many buffers to insert in each net. Recently, Sze, et al. [1] proposed a path-based algorithm for buffer insertion in combinational circuits. However their algorithm is inefficient for large circuits when there are many critical paths.In this paper, we present a new buffer insertion algorithm for combinational circuits such that the timing requirements are met and the buffer cost is minimized. Our algorithm iteratively inserts buffers in the circuit to improve the circuit delay. The core of this algorithm is simple but effective technique that guides the search for a good buffering solution. Experimental results on ISCAS85 circuits show that our new algorithm on average uses 36% less buffers and runs 3 times faster than Sze's algorithm.

Most existing buffering algorithms neglect the impact of inductance on circuit performance, which causes large error in circuit analysis and optimization. Even for the approaches considering inductance effects, their delay models are too simplistic to catch the actual performance. As delay-length dependence is approaching linear with inductance effect [1], fewer buffers are needed to reduce RLC delay. This motivates this work to propose a new algorithm for RLC buffer insertion. In this paper, a new buffer insertion algorithm considering inductance for intermediate and global interconnect is proposed, based on downstream impedance instead of traditional downstream capacitance. A new pruning technique that provides tremendous speedup and a new frequency estimation method that is very accurate in delay computation are also proposed. Experiments on industrial netlists demonstrate that our new algorithm reduces the number of buffers up to 34.4% over the traditional van Ginneken’s algorithm that ignores inductance. Our impedance delay estimation is very accurate compared to SPICE simulations, with only 10 % error while the delay model used in the previous RLC algorithm has 20 % error [2]. The accurate delay model not only reduces the number of buffers, but also brings high fidelity to the buffer solutions. Incorporating slew constraints, the algorithm is accelerated by about 4 × with only slight degradation in solution quality. 1.

Buffer insertion is a popular technique to reduce the interconnect delay. The classic buffer insertion algorithm of van Ginneken has a time complexity of O(n/sup 2/), where n is the number of buffer positions. Lillis, Cheng, and Lin extended van Ginneken's algorithm to allow b buffer types in O(b/sup 2/n/sup 2/) time. For modern design libraries that contain hundreds of buffers, it is a serious challenge to balance the speed and performance of the buffer insertion algorithm. In this paper, we present a new algorithm that computes the optimal buffer insertion in O(bn/sup 2/) time. The reduction is achieved by the observation that the (Q,C) pairs of the candidates that generate the new candidates must form a convex hull. On industrial test cases, the new algorithm is faster than the previous best buffer insertion algorithms by orders of magnitude. Since van Ginneken's algorithm with multiple buffer types are used by most existing algorithms on buffer insertion and buffer sizing, our new algorithm improves the performance of all these algorithms.

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.

Buffer insertion is a popular technique to reduce interconnect delay. The classic buffer insertion algorithm of L.P.P.P. van Ginneken (see ISCAS, p.865-8, 1990) has time complexity O(n/sup 2/), where n is the number of buffer positions. J. Lillis et al. (see IEEE Trans. Solid-Slate Circuits, vol.31, no.3, p.437-47, 1996) extended van Ginneken's algorithm to allow b buffer types in time O(b/sup 2/n/sup 2/). For modern design libraries that contain hundreds of buffers, it is a serious challenge to balance the speed and performance of the buffer insertion algorithm. We present a new algorithm that computes the optimal buffer insertion in O(bn/sup 2/) time. The reduction is achieved by the observation that the (Q, C) pairs of the candidates that generate the new candidates must form a convex hull. On industrial test cases, the new algorithm is faster than the previous best buffer insertion algorithms by orders of magnitude.

Under manufacturing process variation, a path through a net is called longest if there exists a process condition under which the path has the maximum delay among all paths through the net. There are often multiple longest paths for each net, due to different process conditions. In addition, a local defect, such as resistive open or a resistive bridge, increases the delay of the affected net. To detect delay faults due to local defects and process variation, it is necessary to test all longest paths through each net. Previous approaches to this problem were inefficient because of the large number of paths that are not longest. This paper presents an efficient method to generate the set of longest paths for delay test under process variation. To capture both structural and process correlation between path delays, we use linear delay functions to express path delays under process variation. A novel technique is proposed to prune paths that are not longest, resulting in a significant reduction in the number of paths. In experiments on International Symposium on Circuits and Systems (ISCAS) circuits, our number of longest paths is 1-6% of the previous best approach, with 300/spl times/ less running time.

The classic buffer insertion algorithm of van Ginneken has time and space complexity O(n/sup 2/), where n is the number of possible buffer positions. For more than a decade, van Ginneken's algorithm has been the foundation of buffer insertion. In this paper, we present a new algorithm that computes the same optimal buffer insertion, but runs much faster. For 2-pin nets, our time complexity is O(nlogn) and space complexity is O(n). For multipin nets, our time complexity is O(nlog/sup 2/n) and space complexity is O(nlogn). The speedup is achieved by four novel techniques: predictive pruning, candidate tree, fast redundancy check, and fast merging. On industrial test cases, the new algorithms is 2-80 times faster than van Ginneken's algorithm and uses 1/4-1/500 of the memory. Since van Ginneken's algorithm and its variations are used by most existing algorithms on buffer insertion and buffer sizing, our new algorithm significantly improves the performance of all these algorithms. The predictive pruning technique has been applied to buffer cost minimization (Shi et al., 2004), and significantly improved the running time.

To detect the smallest delay faults at a fault site, the longest path(s) through it must be tested at full speed. Existing test generation tools are inefficient in automatically identifying the longest testable paths due to the high computational complexity. In this work a test generation methodology for scan-based synchronous sequential circuits is presented, under two at-speed test strategies used in industry. The two strategies are compared and the test generation efficiency is evaluated on ISCAS89 benchmark circuits and industrial designs. Experiments show that testing transition faults through the longest paths can be done in reasonable test set size.

The path delay fault model is the most realistic model for delay faults. Testing all the paths in a circuit achieves 100% delay fault coverage according to traditional path delay fault coverage metrics. These metrics result in unrealistically low fault coverage if only a subset of paths is tested, and the real test quality is not reflected. For example, the traditional path delay fault coverage of any practical test for circuit c6288 is close to 0 because this circuit has an exponential number of paths. In this paper, a statistical and realistic path delay fault coverage metric is presented. Then the quality of several existing test sets (path selection methods) is evaluated in terms of local and global delay faults using this metric, in comparison with the transition fault and traditional path delay fault coverage metrics.

The classic algorithm for optimal buffer insertion due to van Ginneken has time and space complexity O(n2), where n is the number of possible buffer positions.

Delay faults are an increasingly important test challenge. Traditional open and bridge fault models are incomplete because only the functional fault or a subset of delay fault are modeled. In this paper, we propose a circuit level model for resistive open and bridge faults. All possible fault behaviors are illustrated and a general resistive bridge delay calculation method is proposed. The new models are practical and easy to use. Fault simulation results show that the new models help the delay test to catch more bridge faults.

Delay faults are an increasingly important test challenge. Modeling bridge faults as delay faults helps delay tests to detect more bridge faults. Traditional bridge fault models are incomplete because these models only model the logic faults or these models are not efficient to use in delay tests for large circuits. In this article, we propose a physically realistic yet economical resistive bridge fault model to model delay faults as well as logic faults. An accurate yet simple delay calculation method is proposed. We also enumerate all possible fault behaviors and present the relationship between input patterns and output behaviors, which is useful in ATPG. Our fault simulation results show the benefit of at-speed tests.