Nowadays integrated circuits (ICs) are underpinning all major information technology innovations including the current trends of artificial intelligence (AI). Modern IC designs often involve analyses of complex phenomena (such as timing, noise, and power etc.) for tens of billions of electronic components, like resistance (R), capacitance (C), transistors and gates, interconnected in various complex structures. Those analyses often need to strike a balance between accuracy and speed as those analyses need to be carried out many times throughout the entire IC design cycles. With the advancement of AI, researchers also start to explore news ways in leveraging AI to improve those analyses. This paper focuses on one of the most important analyses, timing analysis for interconnects. Since IC interconnects can be represented as an RC-tree, a specialized graph as tree, we design a novel tree-based graph neural network, SyncTREE, to speed up the timing analysis by incorporating both the structural and physical properties of electronic circuits. Our major innovations include (1) a two-pass message-passing (bottom-up and top-down) for graph embedding, (2) a tree contrastive loss to guide learning, and (3) a closed formular-based approach to conduct fast timing. Our experiments show that, compared to conventional GNN models, SyncTREE achieves the best timing prediction in terms of both delays and slews, all in reference to the industry golden numerical analyses results on real IC design data.

Deep learning is a promising approach to early DRV (Design Rule Violation) prediction. However, non-deterministic parallel routing hampers model training and degrades prediction accuracy. In this work, we propose a stochastic approach, called LGC-Net, to solve this problem. In this approach, we develop new techniques of Gaussian random field layer and focal likelihood loss function to seamlessly integrate Log Gaussian Cox process with deep learning. This approach provides not only statistical regression results but also classification ones with different thresholds without retraining. Experimental results with noisy training data on industrial designs demonstrate that LGC-Net achieves significantly better accuracy of DRV density prediction than prior arts.

As the semiconductor process technology advances into sub-10-nm regime, cell pin accessibility, which is a complex joint effect from the pin shape and nearby blockages, becomes a main cause for design rule violations (DRVs). Therefore, a machine-learning model for DRV prediction needs to consider both very high-resolution pin shape patterns and low-resolution layout information as input features. A new convolutional neural network technique, J-Net, is introduced for the prediction with mixed resolution features. This is a customized architecture that is flexible for handling various input and output resolution requirements. It can be applied at placement stage without using global routing information. This technique is evaluated on 12 industrial designs at a 7-nm technology node. The results show that the J-Net-based binary classifier can improve the true positive rate by 37%, 40%, and 7%, respectively, compared to extensions of three recent works, with similar false positive rates.

Owing to the inherent fault tolerance of deep neural networks (DNNs), many structural faults in DNN accelerators tend to be functionally benign. In order to identify functionally critical faults, we analyze the functional impact of stuck-at faults in the processing elements of a 128×128 systolic-array accelerator that performs inferencing on the MNIST dataset. We present a 2-tier machine-learning framework that leverages graph convolutional networks (GCNs) for quick assessment of the functional criticality of structural faults. We describe a computationally efficient methodology for data sampling and feature engineering to train the GCN-based framework. The proposed framework achieves up to 90% classification accuracy with negligible misclassification of critical faults.

EDA tools provide a large spectrum of parameters to help designers achieve the maximized PPA of designs. The corresponding enormous solution space, however, hinders designers from navigating towards optimal solutions. In this paper, we propose a multi-stage automatic flow tuning tool, named FlowTuner, for efficient and effective parameter tuning of VLSI design flow. It utilizes both exploitation using transferred parameter knowledge from archival design data and exploration via a multi-stage cooperative co-evolutionary framework. Furthermore, novel flow jump-start and early-stop techniques are developed to reduce the overall runtime for tuning. Experiments on a set of IWLS 2005 benchmark circuits through a commercial tool flow demonstrate that FlowTuner produces considerably better design outcomes in 50 % shorter turnaround time compared to the state-of-the-art flow tuning techniques.

Latch clustering is a critical stage to reduce power consumption at cost of timing disruption during a modern SoC design flow. However, most existing latch clustering researches mitigate timing disruptions by indirectly minimizing latch displacement during clustering, which is inaccurate and insufficient for timing closure in the design flow. Further, most researches do not control the amount of inserted clock buffers during clustering, which is the key factor to provide flexibility for timing and power trade-off. To address the two issues above, this paper presents a novel timing-power co-optimized latch clustering framework: we augment an integer linear programming (ILP) formulation of a facility-location allocation (FLA) problem to (1) directly optimize timing with a path-based timing model and (2) accurately control the number of inserted buffers by the FLA formulation for power optimization. We evaluate the framework with a displacement-optimized clustering approach and a state-of-the-art approach. Experimental results show 46% total negative slack timing overhead reduction, and 21% reduction for total power consumption.

Double patterning is a widely used technique for sub-22nm. Among various double patterning techniques, Self-Aligned Double Patterning (SADP) is a promising technique for good mask overlay control. Based on SADP, a new set of standard cells (T-cells) are developed using thicker metal wires for stronger drive strength. By applying this kind of gates on critical paths, it helps to improve the design performance. However, a mixed design with T-cells and normal cells (N-cells) requires that T-cells are placed on circuit rows with thicker metal, and the normal cells are on the normal circuit rows. Therefore, a placer is needed to adjust the cells to the matched circuit rows. In this paper, a two-stage min-cost max-flow based legalization flow is presented to adjust N/T gate locations for a legal placement. The experimental results demonstrate the effectiveness and efficiency of our approach.

Interconnect spacing is getting increasingly smaller in advanced technology nodes, which adversely increases the capacitive coupling of adjacent interconnect wires. It makes crosstalk a significant contributor to signal integrity and timing, and it is now imperative to prevent crosstalk-induced noise and delay issues in the earlier stages of VLSI design flow. Nonetheless, since the crosstalk effect depends primarily on the switching of neighboring nets, accurate crosstalk evaluation is only viable at the late stages of design flow with routing information available, e.g., after detailed routing. There have also been previous efforts in early-stage crosstalk prediction, but they mostly rely on time-expensive trial routing. In this work, we propose a machine learning-based routing-free crosstalk prediction framework. Given a placement, we identify routing and net topology-related features, along with electrical and logical features, which affect crosstalk-induced noise and delay. We then employ machine learning techniques to train the crosstalk prediction models, which can be used to identify crosstalk-critical nets in placement stages. Experimental results demonstrate that the proposed method can instantly classify more than 70% of crosstalk-critical nets after placement with a false-positive rate of less than 2%.

As the semiconductor process technology advances into sub-10nm regime, cell pin accessibility, which is a complex joint effect from the pin shape and nearby blockages, becomes a main cause for DRC violations. Therefore, a machine learning model for DRC hotspot prediction needs to consider both very high-resolution pin shape patterns and low-resolution layout information as input features. A new convolutional neural network technique, J-Net, is introduced for the prediction with mixed resolution features. This is a customized architecture that is flexible for handling various input and output resolution requirements. It can be applied at placement stage without using global routing information. This technique is evaluated on 12 industrial designs at 7nm technology node. The results show that it can improve true positive rate by 37%, 40% and 14% respectively, compared to three recent works, with similar false positive rates.

The globalization of IC manufacturing has increased the likelihood for IP providers to suffer financial and reputational loss from IP piracy. Logic locking prevents IP piracy by corrupting the functionality of an IP unless a correct secret key is inserted. However, existing logic-locking techniques can impose significant area overhead and performance impact (delay and power) on designs. In this work, we propose BISTLock, a logic-locking technique that utilizes built-in self-test (BIST) to isolate functional inputs when the circuit is locked. We also propose a set of security metrics and use the proposed metrics to quantify BISTLock's security strength for an open-source AES core. Our experimental results demonstrate that BISTLock is easy to implement and introduces an average of 0.74% area and no power or delay overhead across the set of benchmarks used for evaluation.

As the wide adoption of FinFET technology in mass production, dynamic power becomes the bottleneck to achieving low power. Therefore, clock power reduction is crucial in modern IC design. Register clustering can effectively save clock power because of significantly reducing the number of clock sinks and register pin capacitance, clock routed wirelength, and the number of clock buffers. In this paper, we propose effective mean shift to naturally form clusters according to register distribution without placement disruption. Effective mean shift fulfills the requirements to be a good register clustering algorithm because it needs no prespecified number of clusters, is insensitive to initializations, is robust to outliers, is tolerant of various register distributions, is efficient and scalable, and balances clock power reduction against timing degradation. Experimental results show that our approach outperforms state-of-the-art work on power and timing balancing, as well as efficiency and scalability.

This article presents an algorithm for integrated timing-driven latch placement and cloning. Given a circuit placement, the proposed algorithm relocates some latches while circuit timing is improved. Some latches are replicated to further improve the timing; the number of replicated latches along with their locations are automatically determined. After latch cloning, each of the replicated latches is set to drive a subset of the fanouts that have been driven by the original single latch. The proposed algorithm is then extended such that relocation and cloning are applied to some latches together with their neighbor logic gates. Experimental results demonstrate that the worst negative slack and the total negative slack are improved by 24% and 59%, respectively, on average of test circuits. The negative impacts on circuit area and power consumption are both marginal, at 0.7% and 1.9% respectively.

In this paper, we present DATC Robust Design Flow (RDF) from logic synthesis to detailed routing. We further include detailed placement and detailed routing tools based on recent EDA research contests. We also demonstrate RDF in a scalable cloud infrastructure. Design methodology and cross-stage optimization research can be conducted via RDF.

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

The continued delay of higher resolution alternatives for lithography, such as EUV, is forcing the continued adoption of multi-patterning solutions in new technology nodes, which include triple and quadruple patterning using several lithography-etch steps. In the design space each pattern of a multi-patterning solution is modeled as a color on a shape. Designers or EDA tools must determine the colors that each shape is assigned so that the relative position of any two shapes of the same color does not violate the design rules. This results in a shapes layout coloring problem which is formulated as the traditional k-coloring problem in a graph. Because color interactions cross cell boundaries, coloring of a flat (as opposed to hierarchical) design becomes necessary, tremendously increasing the size of the input graph. If a color conflict occurs, any attempt to fix it may cause a chain reaction propagating through the whole design space which makes any approach of the type color_greedily - fix_conflicts - loop_back infeasible. Given the situation, it is extremely desirable to have a set of design rules which provably guarantee k-colorability and admit a practical coloring algorithm. In this paper we formulate such sets of design rules for triple and quadruple patterning problems. For these sets of rules we provide proofs of colorability along with the coloring algorithms with the runtime upper bound of O(n·log n). We also show that our sets of design rules are almost tight in the sense that even a very small relaxation of the formulated rules leads to existence of not k-colorable designs.

This paper presents an incremental timing-driven placement tool, named OWARU. It optimizes timing critical paths through a free space-aware path smoothing: the gates on such paths are relocated to free spaces around the smoothed paths, while incremental static timing analysis is involved to accurately assess timing changes due to the relocation. OWARU is extended to accommodate gate sizing and layer assignment to demonstrate the effectiveness of unified physical synthesis optimizations and incremental placement. The goal is to show that OWARU is an ideal platform for timing closure at later stages of a physical design flow. OWARU is applied on a set of test circuits from 14-nm high-performance commercial microprocessors, which originally failed in timing closure. On average, the worst slack is improved by 63.6%, which corresponds to 5.0% of the clock period; total negative slack is improved by 69.1%.

In this paper, we present DATC Robust Design Flow Database covering the stages from logic synthesis to physical design [1]. Based on this database, design flow and cross-stage optimization research can be conducted via various EDA tools developed from academia.

In this paper, we propose ExtraV, a framework for near-storage graph processing. It is based on the novel concept of graph virtualization , which efficiently utilizes a cache-coherent hardware accelerator at the storage side to achieve performance and flexibility at the same time. ExtraV consists of four main components: 1) host processor, 2) main memory, 3) AFU (Accelerator Function Unit) and 4) storage. The AFU, a hardware accelerator, sits between the host processor and storage. Using a coherent interface that allows main memory accesses, it performs graph traversal functions that are common to various algorithms while the program running on the host processor (called the host program) manages the overall execution along with more application-specific tasks. Graph virtualization is a high-level programming model of graph processing that allows designers to focus on algorithm-specific functions. Realized by the accelerator, graph virtualization gives the host programs an illusion that the graph data reside on the main memory in a layout that fits with the memory access behavior of host programs even though the graph data are actually stored in a multi-level, compressed form in storage. We prototyped ExtraV on a Power8 machine with a CAPI-enabled FPGA. Our experiments on a real system prototype offer significant speedup compared to state-of-the-art software only implementations.

Recently, there have been a slew of design automation contests and released benchmarks. ISPD place & route contests, DAC placement contests, timing analysis contests at TAU and CAD contests at ICCAD are good examples in the past and more of new contests are planned in the upcoming conferences. These are interesting and important events that stimulate the research of the target problems and advance the cutting edge technologies. Nevertheless, most contests focus only on the point tool problems instead of addressing the design flow or co-optimization among design tools. OpenDesign Flow Database platform is developed to direct attentions to the overall design flow from logic synthesis to physical design optimization [1]. The goals are to provide an academic reference design flow based on past CAD contest results, the database for design benchmarks and point tool libraries, and standard design input/output formats to build a customized design flow by composing point tool libraries.

This paper proposes a powerful new technique called “OWARU”1 that re-places and re-sizes multiple gates simultaneously to improve the most critical paths of a design. In essence, it is an incremental timing-driven placement technique integrated with gate sizing optimization that runs in conjunction with static timing analysis to guarantee a WYSIWYG 2 property. The OWARU technique offers several key advantages over previous techniques such as geometrical path straightening via the Bézier-curve algorithm, free space awareness to guarantee a legal placement solution, and an accurate true timing mode. The Bézier-curve geometric smoothing algorithm is extended with new anchor placement techniques to further improve the path placement. Free space aware placement algorithm is further enhanced with multiple gate optimization. The preliminary results are promising. We applied the OWARU technique at the end of industrial strength physical synthesis optimization on high performance microprocessor designs. The technique was extremely effective in improving the most critical path of the tested designs. On timing critical paths that were not fully closed from the previous physical synthesis optimization, the WS (worst slack) is improved by 5.3% of the total clock period and the TNS (total negative slack) improved by 91.3% on average.

Design automation (DA) research has for over fifty years been performed in academia, semiconductor and system companies, and EDA companies worldwide. This research has been enabling to continued scaling of design productivity and growth of the semiconductor industry. For product companies, funding program managers and individual researchers alike, a highly relevant question is: what DA research, and what DA research outcomes, ultimately have the greatest “impact”? In this paper, we present measurements and analyses of DA research outputs (papers, patents, EDA companies), upon which future metrics of DA research impact might be based. Our studies consider 47000+ conference and journal papers from 1964-2014; the inter-patent citation graph over 759000+ DA-related patents; abstracts of 1150+ U.S. NSF projects over a three-decade span; 36 research needs documents of the Semiconductor Research Corporation from 2000-2013; and market segmentation of hundreds of EDA companies. We identify several interesting correlations, but do not claim to identify causal relationships; indeed, connecting traditional measures of research output to real-world impacts seems quite challenging. We conclude with several directions and targets for future investigation.

The new era of cognitive computing brings forth the grand challenge of developing systems capable of processing massive amounts of noisy multisensory data. This type of intelligent computing poses a set of constraints, including real-time operation, low-power consumption and scalability, which require a radical departure from conventional system design. Brain-inspired architectures offer tremendous promise in this area. To this end, we developed TrueNorth, a 65 mW real-time neurosynaptic processor that implements a non-von Neumann, low-power, highly-parallel, scalable, and defect-tolerant architecture. With 4096 neurosynaptic cores, the TrueNorth chip contains 1 million digital neurons and 256 million synapses tightly interconnected by an event-driven routing infrastructure. The fully digital 5.4 billion transistor implementation leverages existing CMOS scaling trends, while ensuring one-to-one correspondence between hardware and software. With such aggressive design metrics and the TrueNorth architecture breaking path with prevailing architectures, it is clear that conventional computer-aided design (CAD) tools could not be used for the design. As a result, we developed a novel design methodology that includes mixed asynchronous-synchronous circuits and a complete tool flow for building an event-driven, low-power neurosynaptic chip. The TrueNorth chip is fully configurable in terms of connectivity and neural parameters to allow custom configurations for a wide range of cognitive and sensory perception applications. To reduce the system's communication energy, we have adapted existing application-agnostic very large-scale integration CAD placement tools for mapping logical neural networks to the physical neurosynaptic core locations on the TrueNorth chips. With that, we have successfully demonstrated the use of TrueNorth-based systems in multiple applications, including visual object recognition, with higher performance and orders of magnitude lower power consumption than the same algorithms run on von Neumann architectures. The TrueNorth chip and its tool flow serve as building blocks for future cognitive systems, and give designers an opportunity to develop novel brain-inspired architectures and systems based on the knowledge obtained from this paper.

Energy distribution networks refer to that part of the electricity network that delivers power to homes and business. It is reported that significant amounts of energy are being wasted simply due to inefficiencies in this network. Further, this domain is rapidly changing with new types of loads such as electric vehicles or the spread of new types of energy sources such as photo-voltaic and wind. In this paper, we demonstrate a comprehensive design automation capability for energy distribution networks leading to much more flexible yet effective system. The new system's capabilities include power load distribution and transfers, equipment upgrading, geospatial-aware network optimization, outage identification, contingency planning and loss analysis/reduction. These features are enabled by advanced simulation, analysis and optimization engines that are adapted from those available in the traditional VLSI design automation area. The paper will conclude with potential future research directions that require further innovations in energy distribution networks.

Fast changing power distribution systems request a dynamic system configuration capability of reacting to volatile consumption demands in an economical way. Load balancing in power distribution systems is an essential technique for smart grid that enables reliable electricity delivery to end customers. This paper is the first work focusing on load balancing using switch reconfiguration, tie-line addition, and wire upgrade simultaneously, while existing works adopt only one of the three techniques to configure the power distribution system. We observe that the new load balancing problem induces a new challenge, dynamic topology rotation, which cannot be handled by existing solutions. To overcome this challenge, we first consider bidirectional power flows and formulate the load balancing problem as a mixed-integer quadratically constrained quadratic program (MIQCQP). To reduce the computational complexity, it is further transformed into a mixed-integer linear program (MILP) without loss of optimality. Experimental results show that, on real power distribution networks, our approach produces optimal solutions that are unlikely to be found in ad-hoc heuristics methods.

Smart Grid refers to the technology that uses computer-based remote control and automation on electricity delivery systems. In recent years, the industry is going through rather dramatic transformations thanks to the quite significant scale of shifts in energy policy, technology and consumer focus. The current situation is dire however. It was reported that the United States loses $150 billion per year due to power interruptions for example and the energy companies lag behind in adopting these new trends. Hence, there are urgent urges for them to act on a number of critical challenges and opportunities in order to build and manage the electric power systems in more efficient manners. In this presentation, we first provide a brief introduction of energy distribution system design and show how much energy distribution problem resembles that of EDA optimization. Then, we claim that there exist ample opportunities for the traditional VLSI design automation techniques to play a critical role in this relatively new domain of problems. As a proof of concept, a few real world power distribution problems are formulated and solved via advanced simulation, analysis and optimization techniques that are adapted from the EDA field. Finally the potential future research directions are discussed where further innovations are possible via EDA-like thinking process.

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.

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.

A pulsed-latch can be modeled as a fast flip-flop. This allows conventional flip-flop designs to be migrated to pulsed-latch versions by simple replacement to reduce the clocking power. A key step in the migration process is to insert pulsers, which generate clock pulse to drive local latches; the number of pulsers as well as the wirelength of clock routing must be minimized to reduce the clocking power. We formulate a pulser insertion problem to find a set of latch groups where each group shares a pulser and its load constraint is satisfied; both an ILP formulation and a heuristic algorithm are presented to solve the problem. Experimental results of circuits implemented with 32-nm CMOS technology show that the clocking power of pulsed-latch designs obtained by our approach is 5.9% less than that of greedy approach; this is 44.7% less than that of flip-flop designs. We also consider the problem of pulsed-register where a pulser is integrated with multiple latches. A concept of logical distance is explored during our clustering algorithm to minimize the overhead of signal wirelength when converting flip-flops to pulsed-registers. Compared with flip-flop circuits, signal wirelength is increased by 6.3%, which is 1.4% smaller than without considering logical distance, while reducing the clocking power by 24%.

The last few years have seen significant advances in the quality of placement algorithms. This is in part due to the availability of large, challenging testcases by way of the ISPD-2005 [17] and ISPD-2006 [16] placement contests. These contests primarily evaluated the placers based on the half-perimeter wire length metric. Although wire length is an important metric, it still does not address a fundamental requirement for placement algorithms, namely, the ability to produce routable placements.

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

Routability is a mandatory metric for modern large-scale mixed-size circuit placement which typically needs to handle hundreds of large macros and millions of small standard cells. However, most existing academic mixed-size placers either focus on wirelength minimization alone, or do not consider the impact of movable macros on routing. To remedy these insufficiencies, this paper formulates design-hierarchy information as a novel fence force in an analytical placement framework. Unlike a state-of-the-art routability-driven placer that simply removes net bounding boxes during placement, this paper utilizes two different optimization forces, the global fence force and the local spreading force, to determine the positions of both standard cells and macros. We utilize design-hierarchy information to determine block distributions globally, and locally we add additional spreading forces to preserve sufficient free space among blocks by a net-topology estimation. With the interactions between these two forces, our placer can well balance routability and wirelength. Experimental results show that our placer can achieve the best routability and routing time among all published works.

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.

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.

The five regular papers and three short papers in this special section were carefully selected from the 2009 Association for Computing Machinery International Symposium on Physical Design (ISPD) Technical Program.

Dramatic progress has been made in algorithms for placement and routing over the last 5 years, with improvements in both speed and quality. Combining placement and routing into a joint optimization has also been proposed. However, it remains unclear if the benefits would be significant enough to justify major changes in commercial tools. CRISP addresses this challenge and is the first tool to demonstrate tangible benefits of combined place-and-route optimization including fewer global routing detours, reduced detailed routing violations and runtime, and even shrinking the floorplan of a commercial design. We employ fast global routing to choose standard cells to temporarily inflate and iteratively spread for congestion reduction. Spreading only in congested regions, we enable die area reduction by facilitating routing with high area utilization.

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.

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

The eight papers in this special section are extended papers that were presented at the International Symposium on Physical Design (ISPD), held in Portland, Oregon, om April 2008.

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.

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

This paper describes a simple and effective quadratic placement algorithm called RQL. We show that a good quadratic placement, followed by local wirelength-driven spreading can produce excellent results on large-scale industrial ASIC designs. As opposed to the current top performing academic placers [4, 7, 11], RQL does not embed a linearization technique within the solver. Instead, it only requires a simpler, pure quadratic objective function in the spirit of [8, 10, 23]. Experimental results show that RQL outperforms all available academic placers on the ISPD-2005 placement contest benchmarks. In particular, RQL obtains an average wire-length improvement of 2.8%, 3.2%, 5.4%, 8.5%, and 14.6% versus mPL6 [5], NTUPlace3 [7], Kraftwerk [20], APlace2.0 [11], and Capo10.2 [18], respectively. In addition, RQL is three, seven, and ten times faster than mpL6, Capo10.2, and APlace2.0, respectively. On the ISPD-2006 placement contest benchmarks, on average, RQL obtains the best scaled wirelength among all available academic placers.

In 2005 and 2006, ISPD successfully hosted two placement contests and released a total of 16 benchmark circuits. These benchmarks are all derived from real industrial circuits and present modern physical design challenges such as scalability, variety of floorplans, movable macro handling, and congestion mitigation. Since their release, the ISPD placement benchmarks have been extensively used by the physical design community. Indeed, we have observed significant progress in placement and floorplanning in the last few years. Much of this success can be credited to the fact that the placement community finally has large, well-defined benchmark circuits available that allow for fair comparisons among different algorithms. In this presentation, we report the most recent results on ISPD placement benchmarks and review how much progress each placement tool has achieved.

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

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

Statistical Static Timing Analysis has received wide attention recently and emerged as a viable technique for manufacturability analysis. To be useful, however, it is important that the error introduced in SSTA be significantly smaller than the manufacturing variations being modeled. Achieving such accuracy requires careful attention to the delay models and to the algorithms applied. In this paper, we propose a new sparse-matrix based framework for accurate path-based SSTA, motivated by the observation that the number of timing paths in practice is sub-quadratic based on a study of industrial circuits and the ISCAS89 benchmarks. Our sparse-matrix based formulation has the following advantages: (a) It places no restrictions on process parameter distributions; (b) It embeds accurate polynomial-based delay model which takes into account slope propagation naturally; (c) It takes advantage of the matrix sparsity and high performance linear algebra for efficient implementation. Our experimental results are very promising.

This talk introduces the new suite of ISPD 2006 placement benchmarks. These circuits are all directly derived from real industrial ASIC designs and represent today's mixed-size physical design constraints in terms of size and complexity. Compared to ISPD 2005 placement benchmarks, ISPD 2006 suite has more movable macros and the wider range of design utilizations. The ISPD 2006 Placement Contest is being held with these new benchmarks. This year, a more sophisticated scoring function will be deployed to measure the quality of placement solutions. The metric function takes into account HPWL (half-perimeter-bounding-box-wirelength), runtime and density target constraints. The purpose of adding runtime to the scoring function is to gently encourage faster placement performance. The purpose of the density target constraint is to encourage more routable placements. Further, this also allows more space for buffering, gate sizing and other synthesis transformations that might happen after the placement. Thus, this year's contest forces the placers to become more realistic than last year's, which focused solely on wirelength minimization. A total ten academic placement tools participated in the contest and the final results will be announced during this talk.

Placement is a critical component of today's physical-synthesis flow with tremendous impact on the final performance of very large scale integration (VLSI) designs. Unfortunately, it accounts for a significant portion of the overall physical-synthesis runtime. With the complexity and the netlist size of today's VLSI design growing rapidly, clustering for placement can provide an attractive solution to manage affordable placement runtimes. However, such clustering has to be carefully devised to avoid any adverse impact on the final placement solution quality. This paper presents how to apply clustering and unclustering strategies to an analytic top-down placer to achieve large speedups without sacrificing (and sometimes even enhancing) the solution quality. The authors' new bottom-up clustering technique, called the best choice (BC), operates directly on a circuit hypergraph and repeatedly clusters the globally best pair of objects. Clustering score manipulation using a priority-queue (PQ) data structure enables identification of the best pair of objects whenever clustering is performed. To improve the runtime of PQ-based BC clustering, the authors proposed a lazy-update technique for faster updates of the clustering score with almost no loss of the solution quality. A number of effective methods for clustering score calculation, balancing cluster sizes, handling of fixed blocks, and area-based unclustering strategy are discussed. The effectiveness of the resulting hierarchical analytic placement algorithm is tested on several large-scale industrial benchmarks with mixed-size fixed blocks. Experimental results are promising. Compared to the flat analytic placement runs, the hierarchical mode is 2.1 times faster, on the average, with a 1.4% wire-length improvement.

To achieve timing closure, one often has to run through several iterations of physical synthesis flows, for which placement is a critical step. During these iterations, one hopes to consistently move towards design convergence. A placement algorithm that is "stable" will consistently drive towards similar solutions, even with changes in the input netlist and placement parameters. Indeed, the stability of the algorithm is arguably as important a characteristic as the wirelength it achieves. However, currently there is no way to actually quantify the stability of a placement algorithm. This work seeks to address the issue by proposing metrics that measure the stability of a placement algorithm. Our experimental results examine the stability of three different placement algorithms with our proposed metrics and convincingly illustrate that some algorithms are quantifiably more stable than others. We believe that this opens the door to applying different standards for evaluating placement algorithms in terms of their effectiveness for achieving timing closure.

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

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

A hybrid two-dimensional position sensing system is designed with microelectromechanical systems (MEMS) for padless mouse applications. The X/Y-axis acceleration of the user's hand movements is measured by two MEMS accelerometer devices. These acceleration values are pulsewidth modulated and converted into (X, Y) coordinates on the screen by integral operations on a microprocessor. The overall system consists of four major components: 1) MEMS accelerometers; 2) CMOS analog readout circuitry; 3) an acceleration magnitude extraction module; and 4) a 16-b RISC microprocessor. Mechanical and analog simulation shows that the designed mouse system can detect acceleration as small as 5.3 mg (g=9.8 m/s/sup 2/) with 100-kHz sampling frequency for low power consumption.

We present empirical analyses of two Boolean satisfiability (SAT) formulations of FPGA (field programmable gate array) detailed routing constraints. Boolean SAT-based routing transforms a routing problem into a Boolean SAT instance by rendering geometric routing constraints as an atomic Boolean function. The generated Boolean function is satisfiable if and only if the corresponding routing is possible. Two different Boolean SAT-based routing models are analyzed: the track-based and the route-based routing constraint model. The track-based routing model transforms a routing task into a net-to-track assignment problem, whereas the route-based routing model reduces it into a routability-checking problem with explicitly enumerated set of detailed routes for nets. In both models, routing constraints are represented as CNF Boolean satisfiability clauses. Through comparative experiments, we demonstrate that the route-based formulation yields an easier-to-evaluate and more scalable routability Boolean function than the track-based method. This is empirical evidence that a smart/efficient Boolean formulation can achieve significant performance improvement in real-world applications.

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

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

Boolean-based routing methods transform the geometric FPGA routing task into a large but atomic Boolean function with the property that any assignment of input variables that satisfies the function specifies a valid routing solution. We present a new search-based satisfiability (SAT) FPGA detailed routing formulation that handles all channels in an FPGA simultaneously. The formulation has the virtue that it considers all nets concurrently allowing higher degrees of freedom for each net, in contrast to the classical one-net-at-a-time approaches and is able to prove the unroutability of a given circuit by demonstrating the absence of a satisfying assignment to the routing Boolean function. To demonstrate the effectiveness of this method, we first present comparative experimental results between integer linear programming (ILP)-based routing, which is an alternative concurrent method, and SAT-based routing. We also present the. first comparisons of search-based Boolean SAT routing results to other conventional routers and offer the first evidence that SAT methods can actually demonstrate the unroutability of a layout. Preliminary experimental results suggest that our approach compares very favorably with both the ILP-based approach and conventional FPGA routers.

A hybrid two-dimensional position sensing system is designed for mouse applications. The system measures the acceleration of hand-movements which are converted into two-dimensional location coor-dinates. The system consists of four major components: 1) MEMS accelerometers, 2) CMOS analog read-out circuitry, 3) an accelera-tion magnitude extraction module, and 4) a 16-bit RISC micropro-cessor. Mechanical and analog circuit simulation shows that the designed padless mouse system can detect accelerations as small as 5.3 mg and operate up to 18MHz.

Incremental redesign is an increasingly essential step in any complex design. Late changes or corrections in functional specifications (so-called "engineering change orders" or ECOs) force us to search for a minimal perturbation that achieves the desired repair. In reconfigurable design scenarios, these incremental repairs may be in response to physical faults: the goal is to "design around" the fault. For FPGAs, incremental rerouting is an essential component of this repair problem. We have developed a new incremental rerouting algorithm for FPGAs using techniques from Boolean Satisfiability (SAT). In this application, these techniques have the twin virtues that they (1) represent all possible routing (and rerouting) constraints simultaneously and exactly, and (2) search for rerouting solutions by perturbing all nets concurrently. Preliminary results are promising. For several FPGA benchmarks, we were able to reroute fault reconfigurations that perturb up to 5.74% of all nets for a small number of fault sets (one to four faults) with only 1.55 track overhead per channel on average, with CPU time 0.76 to 4.91 seconds/fault.

A Boolean-based router expresses the routing constraints as a Bool?ean function which is satisfiable if and only if the layout is routable. Compared to traditional routers, Boolean-based routers offer two unique features: (1) simultaneous embedding of all nets regardless of net ordering, and (2) ability to demonstrate routing infeasibility by proving the unsatisfiability of the generated routing constraint Boolean function. In this paper, we introduce a new Boolean-based FPGA detailed routing formulation that yields an easy-to-evaluate and more scalable routability Boolean function than the previous methods. The routability constraints are expressed in terms of a set of route variables each of which designating a specific detailed route for a given net. Experimental results clearly show the superi?ority of this formulation over an earlier formulation that expressed the constraints in terms of track variables.

lier BDD-based methods.Boolean-based routing transforms the geometric FPGA routing task into a single, large Boolean equation with the property that any assignment of input variables that "satisfies" the equation (that renders equation identically "1") specifies a valid routing.The formulation has the virtue that it considers all nets simultaneously, and the absence of a satisfying assignment implies that the layout is unroutable.Initial Boolean-based approaches to routing used Binary Decision Diagrams (BDDs) to represent and solve the layout problem.BDDs, however, limit the size and complexity of the FPGAs that can be routed, leading these approaches to concentrate only on individual FPGA channels.In this paper, we present a new search-based Satisfiability (SAT) formulation that can handle entire FPGAs, routing all nets concurrently.The approach relies on a recently developed SAT engine (GRASP) that uses systematic search with conflict-directed non-chronological backtracking, capable of handling very large SAT instances.We present the first comparisons of search-based SAT routing results to other routers, and offer the first evidence that SAT methods can actually demonstrate the unroutability of a layout.Preliminary experimental results suggest that this approach to FPGA routing is more viable than ear-1.1