Recent breakthroughs in Large Language Models (LLMs) and Large Circuit Models (LCMs) have sparked excitement across the electronic design automation (EDA) community, promising a revolution in circuit design and optimization. Yet, this excitement is met with significant skepticism: Are these AI models a genuine revolution in circuit design, or a temporary wave of inflated expectations? This paper serves as a foundational text for the corresponding ICCAD 2025 panel, bringing together perspectives from leading experts in academia and industry. It critically examines the practical capabilities, fundamental limitations, and future prospects of large AI models in hardware design. The paper synthesizes the core arguments surrounding reliability, scalability, and interpretability, framing the debate on whether these models can meaningfully outperform or complement traditional EDA methods. The result is an authoritative overview offering fresh insights into one of today’s most contentious and impactful technology trends.

Despite using a novel model of computation, quantum computers break down programs into elementary gates. Among such gates, entangling gates are the most expensive. In the context of fermionic simulations, we develop a suite of compilation and optimization techniques that massively reduce the entangling-gate counts. We exploit the well-studied non-quantum optimization algorithms to achieve up to 24% savings over the state of the art for several small-molecule simulations, with no loss of accuracy or hidden costs. Our methodologies straightforwardly generalize to wider classes of near-term simulations of the ground state of a fermionic system or real-time simulations probing dynamical properties of a fermionic system.

We address two major obstacles to practical deployment of AI-based models on distributed private data. Whether a model was trained by a federation of cooperating clients or trained centrally, (1) the output scores must be calibrated, and (2) performance metrics must be evaluated --- all without assembling labels in one place. In particular, we show how to perform calibration and compute the standard metrics of precision, recall, accuracy and ROC-AUC in the federated setting under three privacy models ( i ) secure aggregation, ( ii ) distributed differential privacy, ( iii ) local differential privacy. Our theorems and experiments clarify tradeoffs between privacy, accuracy, and data efficiency. They also help decide if a given application has sufficient data to support federated calibration and evaluation.

Physical design is the epicenter where the complexity of circuit system design at the billiontransistor scale meets the complexity of silicon fabrication at the nanometer scale.Such everincreasing complexity makes physical design the most critical and challenging stage in the entire VLSI design flow.Despite a long time of active research and development, traditional algorithmic approaches such as nonlinear optimization have gradually lost steam under the heavy weight of physical design complexity, and are looking desperately for help from all possible directions.Empowered by fast-growing cloud-scale computing power and Internet-scale data, machine learning technologies have made remarkable progress in innovation and broad adoptions across a wide range of application domains.Several seminal works have demonstrated encouraging results targeting various aspects of IC design stages.In particular, researchers have been actively pursuing machine learning methods to tackle key physical design problems covering both digital and analog circuits, such as floorplanning, placement, routing, parasitic extraction and modeling, gate sizing/buffering, post-silicon simulation, and design for manufacturing.This special issue presents a collection of recent advances in machine learning technologies for VLSI physical design, covering key physical design issues including routing and placement, power delivery, gate sizing, interconnect analysis, reliability, manufacturability, and physical security, which are summarized as follows.Placement and Routing .In "IMPRoVED: Integrated Method to Predict Post-Routing Setup Violations in Early Design Stages ," Krishna et al. focus on timing analysis, a critical yet time-consuming problem.They propose a random forest based method equipped with a set of new features, such as post-route buffer-bloat and cell sizing prediction, for fast timing delay and violation estimation.In "Routability Optimization of Extreme Aspect Ratio Design Through Non- Uniform Placement Utilization and Selective F lip-F lop Stacking ," Hyun et al. focus on the routability optimization problem for designs with extreme aspect ratios and high area utilization.They propose a set of techniques, including a CNN-based model to generate a non-uniform placement distribution for routability optimization, a flip-flop selection and stacking method for clock routing resource minimization, and A U-Net model with GAT for congestion estimation.In "Multi-Terminal Pathfinding in Practical VLSI Systems with Deep Neural Networks ," Utyamishev et al. tackle the multiterminal obstacle-avoiding pathfinding problem.They map the problem to an image manipulation task and solve the problem using a conditional generative adversarial network based approach.Gate Sizing .In "DAGSizer: A Directed Graph Convolutional Network Approach to Discrete Gate Sizing of VLSI Graphs ," Cheng et al. tackle the discrete gate sizing problem using a

Ion-trap quantum computers offer a large number of possible qubit couplings, each of which requires individual calibration and can be misconfigured. To enhance the duty cycle of an ion trap, we develop a strategy that diagnoses individual miscalibrated couplings using only log-many tests. This strategy is validated on a commercial ion-trap quantum computer, where we illustrate the process of debugging faulty quantum gates. Our methodology provides a scalable pathway towards fault detections on a larger scale ion-trap quantum computers, confirmed by simulations up to 32 qubits.

Modern software systems and products increasingly rely on machine learning models to make data-driven decisions based on interactions with users, infrastructure and other systems. For broader adoption, this practice must (i) accommodate product engineers without ML backgrounds, (ii) support finegrain product-metric evaluation and (iii) optimize for product goals. To address shortcomings of prior platforms, we introduce general principles for and the architecture of an ML platform, Looper, with simple APIs for decision-making and feedback collection. Looper covers the end-to-end ML lifecycle from collecting training data and model training to deployment and inference, and extends support to personalization, causal evaluation with heterogenous treatment effects, and Bayesian tuning for product goals. During the 2021 production deployment, Looper simultaneously hosted 440-1,000 ML models that made 4-6 million real-time decisions per second. We sum up experiences of platform adopters and describe their learning curve.

Quantum computers promise to solve important problems faster than conventional computers ever could. Underneath is a fundamentally different computational primitive that introduces new challenges for the development of software tools that aid designers of corresponding quantum algorithms. The different computational primitives render classical simulation of quantum circuits particularly challenging. While the logic simulation of conventional circuits is comparatively simple with linear complexity with respect to the number of gates, quantum circuit simulation has to deal with the exponential memory requirements to represent quantum states on non-quantum hardware with respect to the number of qubits. Decision Diagrams (DDs) address this challenge through exploitation of redundancies in matrices and vectors to provide significantly more compact representations in many cases. Moreover, the probabilistic nature of quantum computations enables another angle to tackle the complexity: Quantum algorithms are resistant to some degree against small inaccuracies in the quantum state as these only lead to small changes in the outcome probabilities. We propose to exploit this resistance against (small) errors to gain even more compact decision diagrams. In this work, we investigate the potential of approximation in quantum circuit simulation in detail. To this end, we first present four dedicated schemes that exploit the error resistance and efficiently approximate quantum states represented by decision diagrams. Subsequently, we propose two simulation strategies that utilize those approximations schemes in order to improve the efficiency of DD-based quantum circuit simulation, while, at the same time, allowing the user to control the resulting degradation in accuracy. We empirically show that the proposed approximation schemes reduce the size of decision diagrams substantially and also analytically prove the effect of multiple approximations on the attained accuracy. Eventually, this enables speed-ups of the resulting approximate quantum circuit simulation of up to several orders of magnitudes—again, while controlling the fidelity of the result.

This work outlines how we prioritize original news, a critical indicator of news quality. By examining the landscape and lifecycle of news posts on our social media platform, we identify challenges of building and deploying an originality score. We pursue an approach based on normalized PageRank values and three-step clustering, and refresh the score on an hourly basis to capture the dynamics of online news. We describe a near real-time system architecture, evaluate our methodology, and deploy it to production. Our empirical results validate individual components and show that prioritizing original news increases user engagement with news and improves proprietary cumulative metrics.

Quantum computers promise to solve important problems faster than conventional computers. However, unleashing this power has been challenging. In particular, design automation runs into (1) the probabilistic nature of quantum computation and (2) exponential requirements for computational resources on non-quantum hardware. In quantum circuit simulation, Decision Diagrams (DDs) have previously shown to reduce the required memory in many important cases by exploiting redundancies in the quantum state. In this paper, we show that this reduction can be amplified by exploiting the probabilistic nature of quantum computers to achieve even more compact representations. Specifically, we propose two new DD-based simulation strategies that approximate the quantum states to attain more compact representations, while, at the same time, allowing the user to control the resulting degradation in accuracy. We also analytically prove the effect of multiple approximations on the attained accuracy and empirically show that the resulting simulation scheme enables speed-ups up to several orders of magnitudes.

Recent demonstrations of superconducting quantum computers by Google and IBM and trapped-ion computers from IonQ fueled new research in quantum algorithms, compilation into quantum circuits, and empirical algorithmics. While online access to quantum hardware remains too limited to meet the demand, simulating quantum circuits on conventional computers satisfies many needs. We advance Schrödinger-style simulation of quantum circuits that is useful standalone and as a building block in layered simulation algorithms, both cases are illustrated in our results. Our algorithmic contributions show how to simulate multiple quantum gates at once, how to avoid floating-point multiplies, how to best use data-level and thread-level parallelism as well as CPU cache, and how to leverage these optimizations by reordering circuit gates. While not described previously, these techniques implemented by us supported published high-performance distributed simulations up to 64 qubits. To show additional impact, we benchmark our simulator against Microsoft, IBM and Google simulators on hard circuits from Google.

The computational power of quantum computers poses major challenges to new design tools since representing pure quantum states typically requires exponentially large memory. As shown previously, decision diagrams can reduce these memory requirements by exploiting redundancies. In this work, we demonstrate further reductions by allowing for small inaccuracies in the quantum state representation. Such inaccuracies are legitimate since quantum computers themselves experience gate and measurement errors and since quantum algorithms are somewhat resistant to errors (even without error correction). We develop four dedicated schemes that exploit these observations and effectively approximate quantum states represented by decision diagrams. We empirically show that the proposed schemes reduce the size of decision diagrams by up to several orders of magnitude while controlling the fidelity of approximate quantum state representations.

Quantum computers promise significant speedups in solving problems intractable for conventional computers but, despite recent progress, remain limited in scaling and availability. Therefore, quantum software and hardware development heavily rely on simulation that runs on conventional computers. Most such approaches perform strong simulation in that they explicitly compute amplitudes of quantum states. However, such information is not directly observable from a physical quantum computer because quantum measurements produce random samples from probability distributions defined by those amplitudes. In this work, we focus on weak simulation that aims to produce outputs which are statistically indistinguishable from those of error-free quantum computers. We develop algorithms for weak simulation based on quantum state representation in terms of decision diagrams. We compare them to using state-vector arrays and binary search on prefix sums to perform sampling. Empirical validation shows, for the first time, that this enables mimicking of physical quantum computers of significant scale.

As quantum computers grow more capable, simulating them on conventional hardware becomes more challenging yet more attractive since this helps in design and verification. Some quantum algorithms and circuits are amenable to surprisingly efficient simulation, and this makes hard-to-simulate computations particularly valuable. For such circuits, we develop accurate massively-parallel simulation with dramatic speedups over earlier methods on 42- and 45-qubit circuits. We propose two ways to trade circuit fidelity for computational speedups, so as to match the error rate of any quantum computer. Using Google Cloud, we simulate approximate sampling from the output of a circuit with 7 × 8 qubits and depth 42 with fidelity 0.5% at an estimated cost of $35K.

The world's appetite for analyzing massive amounts of structured and unstructured data has grown dramatically. The computational demands of these abundant-data applications, such as deep learning, far exceed the capabilities of today's computing systems and are unlikely to be met with isolated improvements in transistor or memory technologies, or integrated circuit architectures alone. To achieve unprecedented functionality, speed, and energy efficiency, one must create transformative nanosystems whose architectures are based on the salient properties of the underlying nanotechnologies. Our Nano-Engineered Computing Systems Technology (N3XT) approach makes such nanosystems possible through new computing system architectures leveraging emerging device (logic and memory) nanotechnologies and their dense 3-D integration with fine-grained connectivity to immerse computing in memory and new logic devices (such as carbon nanotube field-effect transistors for implementing high-speed and low-energy logic circuits) as well as high-density nonvolatile memory (such as resistive memory), and amenable to ultradense (monolithic) 3-D integration of thin layers of logic and memory devices that are fabricated at low temperature. In addition, we explore the use of several device and integration technologies in the N3XT beyond the specific ones mentioned earlier that are also used in our main nanosystem prototypes. We also present an efficient resiliency technique to overcome endurance challenges in certain resistive memory technologies. N3XT hardware prototypes demonstrate the practicality of our architectures. We evaluate the benefits of the N3XT using a simulation framework calibrated using experimental measurements. System-level energy-delay product of common implementations of abundant-data workloads improves by three orders of magnitude in the N3XT compared with conventional architectures. These improvements impact a broad range of application workloads and architecture configurations, from embedded systems to the cloud.

Performance of modern multi-chip modules, increasingly implemented as interposer solutions, is limited by system-level interconnects. We propose an effective method for optimal wirelength-driven die placement of interposer-based 3D ICs. Our key ideas are to leverage the constraint-satisfaction problem (CSP) formalism in combination with a branch-and-bound (B&B) algorithm, and to develop several novel techniques for early identification and pruning of unpromising configurations. Such techniques are crucial for addressing the combinatorial explosion when solving the NP-hard placement problem. Experiments on ISPD08 (modified) and MCNC benchmarks demonstrate that our method outperforms prior art: we can optimally place up to eleven rotatable dies, whereas state-of-the-art tools are limited to six dies.

Given the significance of placement in integrated circuit (IC) physical design, extensive research studies performed over the last 50 years addressed numerous aspects of global and detailed placement. The objectives and the constraints dominant in placement have been revised many times over, and continue to evolve. Additionally, the increasing scale of placement instances affects the algorithms of choice for high-performance tools. We survey the history of placement research, the progress leading up to the state of the art, and outstanding challenges.

Generic quantum-circuit simulation appears intractable for conventional computers and may be unnecessary because useful quantum circuits exhibit significant structure that can be exploited during simulation. For example, Gottesman and Knill identified an important subclass, called stabilizer circuits, which can be simulated efficiently using group-theory techniques and insights from quantum physics. Realistic circuits enriched with quantum error-correcting codes and fault-tolerant procedures are dominated by stabilizer subcircuits and contain a relatively small number of non-Clifford components. Therefore, we develop new data structures and algorithms that facilitate parallel simulation of such circuits. Stabilizer frames offer more compact storage than previous approaches but require more sophisticated bookkeeping. Our implementation, called Quipu, simulates certain quantum arithmetic circuits (e.g., reversible ripple-carry adders) in polynomial time and space for equal superpositions of n-qubits. On such instances, known linear-algebraic simulation techniques, such as the (state-of-the-art) BDD-based simulator QuIDDPro, take exponential time. We simulate quantum Fourier transform and quantum fault-tolerant circuits using Quipu, and the results demonstrate that our stabilizer-based technique empirically outperforms QuIDDPro in all cases. While previous high-performance, structure-aware simulations of quantum circuits were difficult to parallellize, we demonstrate that Quipu can be parallelized with a nontrivial computational speedup.

The increasing IC manufacturing cost encourages a business model where design houses outsource IC fabrication to remote foundries. Despite cost savings, this model exposes design houses to IC piracy as remote foundries can manufacture in excess to sell on the black market. Recent efforts in digital hardware security aim to thwart piracy by using XOR-based chip locking, cryptography, and active metering. To counter direct attacks and lower the exposure of unlocked circuits to the foundry, we introduce a multiplexor-based locking strategy that preserves test response allowing IC testing by an untrusted party before activation. We demonstrate a simple yet effective attack against a locked circuit that does not preserve test response, and validate the effectiveness of our locking strategy on IWLS 2005 benchmarks.

The increasing IC manufacturing cost encourages a business model where design houses outsource IC fabrication to remote foundries. Despite cost savings, this model exposes design houses to IC piracy as remote foundries can manufacture in excess to sell on the black market. Recent efforts in digital hardware security aim to thwart piracy by using XOR-based chip locking, cryptography, and active metering. To counter direct attacks and lower the exposure of unlocked circuits to the foundry, we introduce a multiplexor-based locking strategy that preserves test response allowing IC testing by an untrusted party before activation. We demonstrate a simple yet effective attack against a locked circuit that does not preserve test response, and validate the effectiveness of our locking strategy on IWLS 2005 benchmarks.

Physically Unclonable Functions (PUFs) combat counterfeit ICs by identifying each chip using inherent process variation. PUFs must produce sufficiently many bits, but replicating the same PUF design requires care since process variation and its spatial correlation may change in the next 10 years. Additional challenges arise in system-on-chip and heterogeneous 3D integration of diverse PUFs. Responding to these challenges, we introduce methods for combining PUFs, with provisions for sampling process variation throughout the IC. When multiple sources of entropy are available, our optimization algorithms select sources to maximize joint entropy and minimize physical overhead. Empirical validation uses SPICE simulations for a 45nm technology node.

IC performance, power dissipation, size, and signal integrity are now dominated by interconnects. However, with ever-shrinking standard cells, blind minimization of interconnect during placement causes routing failures. Hence, we develop Coordinated Place-and-Route (CoPR) with (i) a Lightweight Incremental Routing Estimation (LIRE) frequently invoked during placement, (ii) placement techniques that address three types of routing congestion, and (iii) an interface to congestion estimation that supports new types of incrementality. LIRE comprehends routing obstacles and non-uniform routing capacities, and relies on a cache-friendly, fully-incremental routing algorithm. Our implementation extends and improves our winning entry at the ICCAD 2012 Contest.

Physical Unclonable Functions (PUFs) extract unique chip signatures from process variations. They are used in identification, authentication, integrity verification, and anti-counterfeiting tasks. We introduce new PUF techniques that extract bits from pairwise skews between sinks of a clock network. These techniques inherit the stability of clock network, but require a return network to deliver clock pulses to a certain region, where they are compared. Our algorithms select equidistant sinks and route the return network, then derive chip-specific random bits from available data with a moderate overhead. SPICE-based evaluation of clock-PUFs using a 45nm CMOS technology validates the operability, stability, uniqueness, randomness, and their low overhead.

Process and device scaling in late-CMOS technologies highlight leakage power as a critical challenge for the semiconductor industry. Careful gate sizing and Vth-swapping can reduce leakage, but prior optimizations based on convex or dynamic programming (i) are often based on unrealistic assumptions about circuit delay and slew propagation, (ii) fail to handle practical design rules such as transition time or load upper bounds, and (iii) do not scale well to input complexities when full extracted parasitics are available. Seeing substantial opportunities for improvement, we present a multithreaded, stochastic optimization (Trident2.0) for gate sizing and Vthassignment to minimize leakage power subject to capacitance, slew and timing constraints. Scalability and high performance of Trident2.0 are validated on ISPD-2013 Gate Sizing Contest benchmarks.

Combinatorial objects in EDA applications exhibit a great amount of complexity and typically defy polynomial-time algorithms. To achieve acceptable performance, EDA tools seek to exploit various structures found in these objects in practice. In this work, we explore symmetries of Boolean functions and develop a new algorithm based on nested partition refinement, abstract group theory and Boolean satisfiability. We apply our algorithm to solve large-scale Boolean matching.

As quantum information processing gains traction, its simulation becomes increasingly significant for engineering purposes - evaluation, testing and optimization - as well as for theoretical research. Generic quantum-circuit simulation appears intractable for conventional computers. However, Gottesman and Knill identified an important subclass, called stabilizer circuits, which can be simulated efficiently using group-theory techniques. Practical circuits enriched with quantum error-correcting codes and fault-tolerant procedures are dominated by stabilizer subcircuits and contain a relatively small number of non-stabilizer components. Therefore, we develop new group-theory data structures and algorithms to simulate such circuits. Stabilizer frames offer more compact storage than previous approaches but requires more sophisticated bookkeeping. Our implementation, called Quipu, simulates certain quantum arithmetic circuits (e.g., ripple-carry adders) in polynomial time and space for equal superpositions of n-qubits. On such instances, known linear-algebraic simulation techniques, such as the (state-of-the-art) BDD-based simulator QuIDDPro, take exponential time. We simulate various quantum Fourier transform and quantum fault-tolerant circuits with Quipu, and the results demonstrate that our stabilizer-based technique outperforms QuIDDPro in all cases.

We adapt techniques from the constraint programming and satisfiability literatures to expedite the search for graph automorphisms. Specifically, we implement conflict-driven backjumping, several branching heuristics, andrestarts. To support backjumping, we extend high-performance search for graph automorphisms with a novel framework for conflict analysis. Empirically, these techniques improve performance up to several orders of magnitude.

Past improvements in clock frequencies have traditionally been obtained through technology scaling, but most recent technology nodes do not offer such benefits. Instead, parallelism has emerged as the key driver of chip-performance growth. Unfortunately, efficient simultaneous use of on-chip resources is hampered by sequential dependencies, as illustrated by Amdahl's law. Quantifying achievable parallelism in terms of provable mathematical results can help prevent futile programming efforts and guide innovation in computer architecture toward the most significant challenges. To complement Amdahl's law, we focus on stream processing and quantify performance losses due to stochastic runtimes. Using spectral theory of random matrices, we derive new analytical results and validate them by numerical simulations. These results allow us to explore unique benefits of stochasticity and show how and when they outweigh the costs for software streams.

We develop a projected-subgradient primal-dual Lagrange optimization for global placement, that can be instantiated with a variety of interconnect models. It decomposes the original non-convex problem into\more convex"sub-problems. It generalizes the recent SimPL, SimPLR and Ripple algo- rithms and extends them. Empirically, ComPLx outper- forms all published placers in runtime and performance on ISPD 2005 and 2006 benchmarks.

At-speed testing is increasingly important at recent technology nodes due to growing uncertainty in chip manufacturing. However, at-speed fault coverage and test-efficacy suffer when tests are not robust. Since Automatic Test Pattern Generation (ATPG) is typically performed at late design stages, fixing robustness problems found during ATPG can be costly. To address this challenge, we propose a methodology that identifies robustness problems at the Register Transfer Level (RTL) and fixes them. Empirically, this improves final at-speed fault coverage and test-efficacy.

The well-studied gate-sizing optimization is a major contributor to IC power-performance tradeoffs. Viable optimizers must accurately model circuit timing, satisfy a variety of constraints, scale to large circuits, and effectively utilize a large (but finite) number of possible gate configurations, including Vt and Lg. Within the research-oriented infrastructure used in the ISPD 2012 Gate Sizing Contest, we develop a metaheuristic approach to gate sizing that integrates timing and power optimization, and handles several types of constraints. Our solutions are evaluated using a rigorous protocol that computes circuit delay with Synopsys PrimeTime. Our implementation Trident outperforms the best-reported results on all but one of the ISPD 2012 benchmarks. Compared to the 2012 contest winner, we further reduce leakage power by an average of 43%.

In 3D-IC integration and its implied resource optimization, a particularly critical resource is deadspace --- regions between floorplan blocks. Deadspace is required for through-silicon via (TSV) planning and other related design tasks, but the effective use of this limited and highly-contested resource requires effort. While most previous work focuses on a single design issue at a time, we propose a lightweight multiobjective deadspace-optimization methodology that simultaneously optimizes interconnect, IR-drop, clock-tree size and maximal temperature. This methodology repeatedly re-evaluates design quality during early chip planning and uses resulting information to guide further optimization. Experimental results indicate that constructing an appropriate deadspace distribution improves design tradeoffs and is effective in practice.

Given the significance of placement in IC physical design, extensive research studies performed over the last 50 years addressed numerous aspects of global and detailed placement. The objectives and the constraints dominant in placement have been revised many times over, and continue to evolve. Additionally, the increasing scale of placement instances affects the algorithms of choice for high-performance tools. We survey the history of placement research, the progress achieved up to now, and outstanding challenges.

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

We propose a self-contained, flat, quadratic global placer that is simpler than existing placers and easier to integrate into timing-closure flows. It maintains lower-bound and upper-bound placements that converge to a final solution. The upper-bound placement is produced by a novel look-ahead legalization algorithm. Our placer SimPL outperforms mPL6, FastPlace3, NTUPlace3, APlace2, and Capo simultaneously in runtime and solution quality, running 7.10 times faster than mPL6 (when using a single thread) and reducing wirelength by 3% on the ISPD 2005 benchmark suite. More significant improvements are achieved on larger benchmarks. The new algorithm is amenable to parallelism, and we report empirical studies with SSE2 instructions and up to eight parallel threads.

Despite numerous advantages of 3-D integrated circuits (ICs), their commercial success remains limited. In part, this is due to the wide availability of trustworthy intellectual property (IP) blocks developed for 2-D ICs and proven through repeated use. Block-based design reuse is imperative for heterogeneous 3-D ICs where memory, logic, analog, and microelectromechanical systems dies are manufactured at different technology nodes and circuit modules cannot be partitioned among several dies. In this paper, we show how to integrate 2-D IP blocks into 3-D chips without altering their layout. Experiments indicate that the overhead of proposed integration is small, which can help accelerate industry adoption of 3-D integration.

Traditional integrated circuit (IC) design flows optimize clock networks before signal-net routing are limited by the quality of register placement. Existing publications also reflect this bias and focus mostly on clock routing. The few known techniques for register placement exhibit significant limitations and do not account for recent progress in large-scale placement and obstacle-aware clock-network synthesis. In this paper, we integrate clock network synthesis within global placement by optimizing register locations. We propose: 1) obstacle-aware virtual clock-tree synthesis; 2) arboreal clock-net contraction force with virtual-node insertion, which can handle multiple clock domains and gated clocks; and 3) an obstacle-avoidance force (OAF). Our work is validated on large benchmarks with numerous macroblocks. Experimental results indicate that our software implementation, called Lopper, prunes clock-tree branches to reduce their length by 30.0%-36.6% and average total dynamic power consumption by 6.8%-11.6% versus conventional wirelength-driven approaches. SPICE-driven simulations show that our methods improve robustness of clock trees.

Highly-optimized placements may lead to irreparable routing congestion due to inadequate models of modern interconnect stacks and the impact of partial routing obstacles. Additional challenges in routability-driven placement include scalability to large netlists and limiting the complexity of software integration. Addressing these challenges, we develop lookahead routing to give the placer advance, firsthand knowledge of trouble spots, not distorted by crude congestion models. We also extend global placement to (i) spread cells apart in congested areas, and (ii) move cells together in less-congested areas to ensure short, routable interconnects and moderate runtime. While previous work adds isolated steps to global placement, our SIMultaneous PLace-and-Route tool SimPLR integrates a layer- and via-aware global router into a leading-edge, force-directed placer. The complexity of integration is mitigated by careful design of simple yet effective optimizations. On the ISPD 2011 Contest Benchmark Suite, with the official evaluation protocol, SimPLR outperforms every contestant on every benchmark.

Recent improvements in clock-tree and mesh-based topologies maintain a healthy competition between the two. Trees require much smaller capacitance, but meshes are naturally robust against process variation and can accommodate late design changes. Cross-link insertion has been advocated to make trees more robust, but is limited in practice to short distances. In this work we develop a novel non-tree topology that fuses several clock trees to create large-scale redundancy in a clock network. Empirical validation shows that our novel clock-network structure incrementally enhances robustness to satisfy given variation constraints. Our implementation called Contango3.0 produces robust clock networks even for challenging skew limits, without parallel buffering used by other implementations. It also offers a fine trade-off between power and robustness, increasing the capacitance of the initial tree by less than 60%, which results in 2.3× greater power efficiency than mesh structures.

This mini-tutorial covers recent research on clock-network tuning. It starts with SPICE-accurate optimizations used in winning entries at the ISPD 2009 and 2010 clock-network synthesis contests. After comparing clock trees to meshes, it outlines a recent redundant clock-network topology that retains most advantages of clock trees, but improves robustness to PVT variations. It also shows how to incorporate clock-network synthesis into global placement to reduce dynamic power and insertion delay.

Three-dimensional ICs promise to significantly extend the scale of system integration and facilitate new-generation electronics. However, progress in commercial 3D ICs has been slow. In addition to technology-related difficulties, industry experts cite the lack of a commercial 3D EDA tool-chain and design standards, high risk associated with a new technology, and high cost of transition from 2D to 3D ICs. To streamline the transition, we explore design styles that reuse existing 2D Intellectual Property (IP) blocks in 3D ICs. Currently, these design styles severely limit the placement of Through-Silicon Vias (TSVs) and constrain the reuse of existing 2D IP blocks in 3D ICs. To overcome this problem, we develop a methodology for using TSV islands and novel techniques for clustering nets to connect 2D IP blocks through TSV islands. Our empirical validation demonstrates 3D integration of traditional 2D circuit blocks without modifying their layout for this context.

Traditional IC design flows optimize clock networks before signal-net routing and are limited by the quality of register placement. Existing publications also reflect this bias and focus mostly on clock routing. The few known techniques for register placement exhibit significant limitations and do not account for recent progress in large-scale placement and obstacle-aware clock-network synthesis.

With the end of clock-frequency scaling, parallelism has emerged as the key driver of chip-performance growth. Yet, several factors undermine efficient simultaneous use of on-chip resources, which continue scaling with Moore's law. These factors are often due to sequential dependencies, as illustrated by Amdahl's law.

With the prospect of atomic-scale computing, we study cumulative energy profiles of spin-spin interactions in non-ferromagnetic lattices (Ising spin-glasses)-an established topic in solid-state physics that is now becoming relevant to atomic-scale EDA. Recent proposals suggest non-traditional computing devices based on nature's ability to find min-energy states. Spinto utilizes EDA-inspired high-performance algorithms to (i) simulate natural energy minimization in spin systems and (ii) study its potential for solving hard computational problems. Unlike previous work, our algorithms are not limited to planar Ising topologies. In one CPU-day, our branch-and-bound algorithm finds min-energy (ground) states on 100 spins, while our local search approximates ground states on 1,000,000 spins. We use this computational tool to study the significance of hyper-couplings in the context of recently implemented adiabatic quantum computers.

We propose a methodology for Boolean matching under permutations of inputs and outputs (PP-equivalence checking problem) - a key step in incremental logic design that identifies large sections of a netlist that are not affected by a change in specifications. Finding reusable sections of a netlist reduces the amount of work in each design iteration and accelerates design closure. Our approach integrates graph-based, simulation-driven and SAT-based techniques to make Boolean matching feasible for large circuits. Experimental results confirm scalability of our techniques to circuits with hundreds and even thousands of inputs and outputs.

On-chip clock networks are remarkable in their impact on the performance and power of synchronous circuits, in their susceptibility to adverse effects of semiconductor technology scaling, as well as in their strong potential for improvement through better CAD algorithms and tools. Our work offers new algorithms and a methodology for SPICE-accurate optimization of clock networks, coordinated to satisfy slew constraints and achieve best trade-offs between skew, insertion delay, power, as well as tolerance to variations. Our implementation, called Contango, is evaluated on 45nm benchmarks from IBM Research and Texas Instruments with up to 50K sinks.

We propose a self-contained, flat, force-directed algorithm for global placement that is simpler than existing placers and easier to integrate into timing-closure flows. It maintains lower-bound and upper-bound placements that converge to a final solution. The upper-bound placement is produced by a novel rough legalization algorithm. Our placer SimPL outperforms mPL6, NTUPlace3, FastPlace3, APlace2 and Capo simultaneously in runtime and solution quality, running 6.4 times faster than mPL6 and reducing wirelength by 2% on the ISPD 2005 benchmark suite.

Clock networks contribute a significant fraction of dynamic power and can be a limiting factor in high-performance CPUs and SoCs. The need for multi-objective optimization over a large parameter space and the increasing impact of process variation make clock network synthesis particularly challenging. In this work, we develop new modeling techniques and algorithms, as well as a methodology, for clock power optimization subject to tight skew constraints in the presence of process variations. Key contributions include a new time-budgeting step for clock-tree tuning, accurate optimizations that satisfy budgets, modeling and optimization of variational skew. Our implementation, Contango 2.0, outperforms the winners of the ISPD 2010 clock-network synthesis contest on 45nm benchmarks from Intel and IBM.

The impact of physical synthesis on design performance is increasing as process technology scales. Current physical synthesis flows generally perform a series of individual netlist transformations based on local timing conditions. However, such optimizations lack sufficient perspective or scope to achieve timing closure in many cases. To address these issues, we develop an integrated transformation system that performs multiple optimizations simultaneously on larger design partitions than existing approaches. Our system, SPIRE, combines physically-aware register retiming, along with a novel form of cloning and register placement. SPIRE also incorporates a placement-dependent static timing analyzer (STA) with a delay model that accounts for buffering and is suitable for physical synthesis. Empirical results on 45 nm microprocessor designs show 8% improvement in worst-case slack and 69% improvement in total negative slack after an industrial physical synthesis flow was already completed.

To ensure chip manufacturability, all routes must be completed without violations. Furthermore, the chip's power consumption and performance are determined by the length of its routed wires. Therefore, our work focuses on minimizing wirelength. Our key innovations include: (1) a novel branch-free representation (BFR) for routed nets, (2) a trigonometric penalty function (TPF), (3) dynamic adjustment of Lagrange multipliers (DALM), (4) cyclic net locking (CNL), and (5) aggressive lower-bound estimates (ALBE) for A*-search, resulting in faster routing. We complete all routable ISPD 2008 contest benchmarks and re-placed adaptec suite without violation and produce shorter routes.

Traditional digital circuit synthesis flows start from an HDL behavioral definition and assume that circuit functions are almost completely defined, making don't-care conditions rare. However, recent design methodologies do not always satisfy these assumptions. For instance, third-party IP blocks used in a system-on-chip are often overdesigned for the requirements at hand. By focusing only on the input combinations occurring in a specific application, one could resynthesize the system to greatly reduce its area and power consumption. Therefore we extend modern digital synthesis with a novel technique, called SWEDE, that makes use of extensive external don't-cares. In addition, we utilize such don't-cares present implicitly in existing simulation-based verification environments for circuit customization. Experiments indicate that SWEDE scales to large ICs with half-million input vectors and handles practical cases well.

State elements are increasingly vulnerable to soft errors due to their decreasing size, and the fact that latched errors cannot be completely eliminated by electrical or timing masking. Most prior methods of reducing the soft-error rate (SER) involve combinational redesign, which tends to add area and decrease testability, the latter a concern due to the prevalence of manufacturing defects. Our work explores the fundamental relations between the SER of sequential circuits and their testability in scan mode, and appears to be the first to improve both through retiming. Our retiming methodology relocates registers so that 1) registers become less observable with respect to primary outputs, thereby decreasing overall SER, and 2) combinational nodes become more observable with respect to registers (but not with respect to primary outputs), thereby increasing scan-testability. We present experimental results which show an average decrease of 42% in the SER of latches, and an average improvement of 31% random-pattern testability.

Traditional digital circuit synthesis flows start from an HDL behavioral definition and assume that circuit functions are almost completely defined, making don't-care conditions rare. However, recent design methodologies do not always satisfy these assumptions. For instance, third-party IP blocks used in a system-on-chip are often over-designed for the requirements at hand. By focusing only on the input combinations occurring in a specific application, one could resynthesize the system to reduce its area and power consumption. Therefore we extend modern digital synthesis with a novel technique, called SWEDE, that uses external don't-cares present implicitly in existing simulation-based verification environments for circuit customization. Experiments indicate that SWEDE scales to large ICs with half-million input vectors and handles practical cases well.

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.

We explore the use of signatures, i.e., partial truth tables generated via bit-parallel functional simulation, during soft error analysis and logic synthesis. We first present a signature-based CAD framework that incorporates tools for the logic-level Analysis of Soft Error Rate (x) and for Signature-based Design for Reliability (SiDeR). We observe that the soft error rate (SER) of a logic circuit is closely related to various testability parameters, such as signal observability and probability. We show that these parameters can be computed very efficiently (in linear time) by means of signatures. Consequently, AnSER evaluates logic masking two to three orders of magnitude faster than other SER evaluators while maintaining accuracy. AnSER can also compute SER efficiently in sequential circuits by approximating steady-state probabilities and sequential signal observabilities. In the second part of this paper, we incorporate AnSER into logic synthesis design flows aimed at reliable circuit design. SiDeR identifies and exploits redundancy already present in a circuit via signature comparison to decrease SER. We show that SiDeR reduces SER by 40% with only 13% area overhead. We also describe a second signature-based synthesis strategy that employs local rewriting to simultaneously improve area and decrease SER. This technique yields 13% reduction in SER with a 2% area decrease. We show that combining the two synthesis approaches can result in further area-reliability improvements.

Many computational tools have recently begun to benefit from the use of the symmetry inherent in the tasks they solve, and use general-purpose graph symmetry tools to uncover this symmetry. However, existing tools suffer quadratic runtime in the number of symmetries explicitly returned and are of limited use on very large, sparse, symmetric graphs. This paper introduces a new symmetry-discovery algorithm which exploits the sparsity present not only in the input but also the output, i.e., the symmetries themselves. By avoiding quadratic runtime on large graphs, it improves state-of- the-art runtimes from several days to less than a second.

Soft errors, once only of concern in memories, are beginning to affect logic as well. Determining the soft error rate (SER) of a combinational circuit involves three main masking mechanisms: logic, timing and electrical. Most previous papers focus on logic and electrical masking. In this paper we develop static and statistical analysis techniques for timing masking that estimate the error-latching window of each gate. Our SER evaluation algorithms incorporating timing masking are orders of magnitude faster than comparable evaluators and can be used in synthesis and layout. We show that 62 % of gates identified as error-critical using timing masking would not be identifiable by considering only logic masking. Furthermore, hardening the top 10 % of errorcritical gates leads to a 43 % reduction in the SER. We also propose a more subtle solution, gate-relocation for technologies where wire delay dominates gate delay. We decrease the error-latching window of each gate by relocating it in such a way that path lengths to primary outputs are equalized. Our results show a 14 % improvement in SER with no area overhead. 1

Our work addresses protection of hardware IP at the mask level with the goal of preventing unauthorized manufacturing. The proposed protocol based on chip locking and activation is applicable to a broad category of electronic systems with a primary bus. Such designs include (1) numerous IP offerings for USB, PCI, PCI-E, AMBA and other bus standards typically used in system-on-a-chip designs and computer peripherals, (2) SRAM-based FPGAs that are programmed through an input bus, (3) general-purpose and embedded microprocessors, including soft cores, (4) DSPs, (5) network processors, and (6) game consoles. Our key insight is that such designs can be locked by scrambling the central bus by controlled reversible bit-permutations and substitutions. To securely establish a unique code per chip to control bus scrambling, we employ true random number generators and Diffie-Hellman cryptography during activation.

Despite the growing research effort in formal verification, constraint-based random simulation remains an integral part of design validation, especially for large design components where formal techniques do not scale. However, stimulating important aspects of a design to uncover bugs often requires the construction of complex constraints to guide stimulus generation. We propose Toggle, a stimulus generation engine, which features (1) an entropy-based coverage analysis to efficiently find portions of the design inadequately sensitized by simulation and (2) a novel strategy to automatically stimulate these portions through a specialized SAT algorithm that uses small randomized XOR constraints. As our experimental results demonstrate, Toggle requires minimal input from the verification engineer, and significantly improves the coverage qualities of the generated stimuli when compared to plain random simulation.

As semiconductor manufacturing requires greater capital investments, the use of contract foundries has grown dramatically, increasing exposure to mask theft and unauthorized excess production. While only recently studied, IC piracy has now become a major challenge for the electronics and defense industries. We propose a novel comprehensive technique to end piracy of integrated circuits (EPIC). It requires that every chip be activated with an external key, which can only be generated by the holder of IP rights, and cannot be duplicated. EPIC is based on (i) automatically-generated chip IDs, (ii) a novel combinational locking algorithm, and (Hi) innovative use of public-key cryptography. Our evaluation suggests that the overhead of EPIC on circuit delay and power is negligible, and the standard flows for verification and test do not require change. In fact, major required components have already been integrated into several chips in production. We also use formal methods to evaluate combinational locking and computational attacks. A comprehensive protocol analysis concludes that EPIC is surprisingly resistant to various piracy attempts.

Technology scaling reduces gate delays while wire delays may increase. Our work studies the interaction of this phenomenon with technology mapping and its impact on modern EDA flows. In particular, we demonstrate that the use of larger standard cells increases the number of long wires and may undermine circuit delay optimization at 65 nm and below. Experiments with 130 nm, 90 nm, 65 nm, and 45 nm industrial CMOS technology suggest that limiting the use of larger standard cells in technology mapping becomes more effective at 65 nm and 45 nm node, resulting in up to 12% improvement in critical path delay on large benchmark circuits.

Post-silicon validation has recently become a major bottleneck in IC design. Several high profile IC designs have been taped-out with latent bugs, and forced the manufacturers to resort to additional design revisions. Such changes can be applied through metal fix; however, this is impractical without carefully pre-placed spare cells. In this work we perform the first comprehensive analysis of the issues related to spare-cell insertion, including the types of spare cells that should be used as well as their placement. In addition, we propose a new technique to measure the heterogeneity among signals and use it to determine spare-cell density. Finally, we integrate our findings into a novel multi-faceted approach that calculates regional demand for spare cells, identifies the most appropriate cell types, and places such cells into the layout. Our approach enables the use of metal fix at a much smaller delay cost, with a reduction of up to 37% compared to previous solutions

Wire routing, an important step in modern VLSI design, is increasingly responsible for timing closure and manufacturability. The CAD community has witnessed remarkable improvements in speed and quality of global routing algorithms in response to the inaugural ISPD 2007 Global Routing Contest, where prizes were awarded for best results on a new set of large industry benchmarks.

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

Abstract — The relatively poor scaling of interconnect in modern digital circuits necessitates a number of design optimizations, which must typically be iterated several times to meet the specified performance objectives. Such iterations are often due to the difficulty of early delay estimation, especially before placement. Therefore, effective logic restructuring to reduce interconnect delay has been a major challenge in physical synthesis, a phase during which more accurate delay estimates can be finally gathered. In this work, we develop a new approach that enhances modern high-performance logic synthesis techniques with flexibility and accuracy in the physical domain. This approach is based on (1) a novel criterion based on path monotonicity, that identifies those interconnects amenable to optimization through logic restructuring and (2) a synthesis algorithm relying on logic simulation and placement information to identify placed subcircuits that hold promise for interconnect reduction. Experiments indicate that our techniques find optimization opportunities and improve interconnect delay by 11.7 % on average at less than 2% wirelength and area overhead. I.

The treewidth of a graph is a useful combinatorial measure of how close the graph is to a tree. We prove that a quantum circuit with T gates whose underlying graph has a treewidth d can be simulated deterministically in $T^{O(1)}\exp[O(d)]$ time, which, in particular, is polynomial in T if $d=O(\log T)$. Among many implications, we show efficient simulations for log-depth circuits whose gates apply to nearby qubits only, a natural constraint satisfied by most physical implementations. We also show that one-way quantum computation of Raussendorf and Briegel (Phys. Rev. Lett., 86 (2001), pp. 5188–5191), a universal quantum computation scheme with promising physical implementations, can be efficiently simulated by a randomized algorithm if its quantum resource is derived from a small-treewidth graph with a constant maximum degree. (The requirement on the maximum degree was removed in [I. L. Markov and Y. Shi, preprint:quant-ph/0511069].)

In this paper, we propose a resynthesis framework, called COunterexample-guided REsynthesis (CoRe), that automatically corrects errors in digital designs. The framework is based on a simulation-based abstraction technique and performs an error correction through two innovative circuit resynthesis solutions: distinguishing-power search and goal-directed search, which modify the functionality of circuits' internal nodes to match the correct behavior. In addition, we propose a compact encoding of resynthesis information, called the Pairs of Bits to be Distinguished, which is a key enabler for our resynthesis techniques. Compared with previous solutions, CoRe is more powerful for the following reasons: (1) It can fix a broader range of error types because it is not bounded by specific error models; (2) it derives the correct functionality from simulation vectors without requiring golden netlists; and (3) it can be applied with a broad range of verification flows, including formal and simulation-based flows.

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

The relatively poor scaling of interconnect in modern digital circuits necessitates a number of design optimizations, which must typically be iterated several times to meet the specified performance objectives. Such iterations are often due to the difficulty of early delay estimation, particularly before placement. Therefore, effective logic restructuring to reduce interconnect delay has been a major challenge in physical synthesis, a phase during which more accurate delay estimates can be finally gathered. In this paper, we develop a new approach that enhances modern high-performance logic synthesis techniques with flexibility and accuracy in the physical domain. This approach is based on the following: 1) a novel criterion based on path monotonicity, which identifies those interconnects that are amenable to optimization through logic restructuring, and 2) a synthesis algorithm relying on logic simulation and placement information to identify placed subcircuits that hold promise for interconnect reduction. Experiments indicate that our techniques find optimization opportunities and improve interconnect delay by 11.7% on average at less than 2% wirelength and area overhead.

In this paper, we describe significant improvements to core routing technologies and outperform the best results from the International Symposium on Physical Design 2007 Global Routing Contest and the International Conference on Computer-Aided Design 2007 in terms of route completion and total wirelength.

We propose the probabilistic transfer matrix (PTM) framework to capture nondeterministic behavior in logic circuits. PTMs provide a concise description of both normal and faulty behavior, and are well-suited to reliability and error susceptibility calculations. A few simple composition rules based on connectivity can be used to recursively build larger PTMs (representing entire logic circuits) from smaller gate PTMs. PTMs for gates in series are combined using matrix multiplication, and PTMs for gates in parallel are combined using the tensor product operation. PTMs can accurately calculate joint output probabilities in the presence of reconvergent fanout and inseparable joint input distributions. To improve computational efficiency, we encode PTMs as algebraic decision diagrams (ADDs). We also develop equivalent ADD algorithms for newly defined matrix operations such as eliminate_variables and eliminate_redundant_variables , which aid in the numerical computation of circuit PTMs. We use PTMs to evaluate circuit reliability and derive polynomial approximations for circuit error probabilities in terms of gate error probabilities. PTMs can also analyze the effects of logic and electrical masking on error mitigation. We show that ignoring logic masking can overestimate errors by an order of magnitude. We incorporate electrical masking by computing error attenuation probabilities, based on analytical models, into an extended PTM framework for reliability computation. We further define a susceptibility measure to identify gates whose errors are not well masked. We show that hardening a few gates can significantly improve circuit reliability.

In this work, we propose a new and efficient approach to the floorplan repair problem, where violated design constraints are satisfied by applying small changes to an existing rough floorplan. Such a floorplan can be produced by a human designer, a scalable placement algorithm, or result from engineering adjustments to an existing floorplan. In such cases, overlapping modules must be separated, and others may need to be repositioned to satisfy additional requirements. Our algorithmic framework uses an expressive graph-based encoding of constraints which can reflect fixed-outline, region, proximity and alignment constraints. By tracking the implications of existing constraints, we resolve violations by imposing gradual modifications to the floorplan, in an attempt to preserve the characteristics of its initial design. Empirically, our approach is effective at removing overlaps and repairing violations that may occur when design constraints are acquired and imposed dynamically.

Physical synthesis is a relatively young field in electronic design automation. Many published optimizations for physical synthesis end up hurting the final result, often by neglecting important physical aspects of the layout, such as long wires or routing congestion. In this work we propose SafeResynth, a safe resynthesis technique, which provides immediately-measurable delay improvement without altering the design's functionality. It can enhance circuit timing without detrimental effects on route length and congestion. When applied to IWLS'05 benchmarks, SafeResynth improves circuit delay by 11% on average after routing, while increasing route length and via count by less than 0.2%. Our resynthesis can also be used in an unsafe mode, akin to more traditional physical synthesis algorithms popular in commercial tools. Applied together, our safe and unsafe transformations achieve 24% average delay improvement for seven large benchmarks from the OpenCores suite. The relative contribution of safe and unsafe techniques varies depending on the amount of whitespace in the layout.

In this work we propose a new error-correction framework, called CoRe, which uses counterexamples, or bug traces, generated in verification to automatically correct errors in digital designs. CoRe is powered by two innovative resynthesis techniques, goal-directed search (GDS) and entropy-guided search (EGS), which modify the functionality of internal circuit's nodes to match the desired specification. We evaluate our solution to designs and errors arising during combinational equivalence-checking, as well as simulation-based verification of digital systems. Compared with previously proposed techniques, CoRe is more powerful in that: (1) it can fix a broader range of error types because it does not rely on specific error models; (2) it derives the correct functionality from simulation vectors, hence not requiring golden netlists; and (3) it can be applied to a range of verification flows, including formal and simulation-based.

SAT sweeping is the process of merging two or more functionally equivalent nodes in a circuit by selecting one of them to represent all the other equivalent nodes. This provides significant advantages in synthesis by reducing circuit size and provides additional flexibility in technology mapping, which could be crucial in post-synthesis optimizations. Furthermore, it is also critical in verification because it can reduce the complexity of the netlist to be analyzed in equivalence checking. Most algorithms available so far for this goal do not exploit observability don't cares (ODCs) for node merging since nodes equivalent up to ODCs do not form an equivalence relation. Although a few recently proposed solutions can exploit ODCs by overcoming this limitation, they constrain their analysis to just a few levels of surrounding logic to avoid prohibitive runtime. We develop an ODC-based node merging algorithm that performs efficient global ODC analysis (considering the entire netlist) through simulation and SAT. Our contributions which enable global ODC-based optimizations are: (1) a fast ODC-aware simulator and (2) an incremental verification strategy that limits computational complexity. In addition, our technique operates on arbitrarily mapped netlists, allowing for powerful post-synthesis optimizations. We show that global ODC analysis discovers on average 25% more (and up to 60%) node-merging opportunities than current state-of-the-art solutions based on local ODC analysis.

In a realistic design flow, circuit and system optimizations must interact with physical aspects of the design. For example, improvements in timing and power may require replacing large modules with variants that have different power/delay trade-off, shape and connectivity. New logic may be added late in the design flow, subject to interconnect optimization, To support such flexibility in design flows we develop a robust system for performing engineering change orders (ECOs). In contrast with existing stand-alone tools that offer poor interfaces to the design flow and cannot handle a full range of modern VLSI layouts, our ECO-system reliably handles fixed objects and movable macros in instances with widely varying amounts of whitespace. It detects geometric regions and sections of the netlist that require modification and applies an adequate amount of change in each case. Given a reasonable initial placement, it applies minimal changes, but is capable of re-placing large regions to handle pathological cases. ECO-system can be used in the range from high-level synthesis, to physical synthesis and detail placement.

Modern IC designs have reached unparalleled levels of complexity, resulting in more and more bugs discovered after design tape-out However, so far only very few EDA tools for post-silicon debugging have been reported in the literature. In this work we develop a methodology and new algorithms to automate this debugging process. Key innovations in our technique include support for the physical constraints specific to post-silicon debugging and the ability to repair functional errors through subtle modifications of an existing layout. In addition, our proposed post-silicon debugging methodology (FogClear) can repair some electrical errors while preserving functional correctness. Thus, by automating this traditionally manual debugging process, our contributions promise to reduce engineers’ debugging effort. As our empirical results show, we can automatically repair more than 70% of our benchmark designs.

While circuit density and power efficiency increase with each major advance in IC technology, reliability with respect to soft errors tends to decrease. Current solutions to this problem such as TMR require high area and power overhead. In this work, soft-error reliability is improved with minimal area overhead by careful, localized circuit restructuring. The key idea is to increase logic masking of errors by taking advantage of conditions already present in the circuit, such as observability don't-cares. We describe two circuit modification techniques to improve reliability: don't-care-based resynthesis and local rewriting. A key feature of these techniques is fast, on-the-fly estimation of soft error rate (SER) using our reliability evaluator AnSER. This tool is compared against prior SER evaluators and found to run orders of magnitude faster. We show empirically that our reliability-driven synthesis methods can reduce SER by 29-40% with only 5-13% area overhead.

In this work we describe significant improvements to core routing technologies and outperform the best results from the ISPD '07 global routing contest, as well as previous literature, in terms of route completion, runtime and total wirelength. In particular, our router, FGR, improves upon wirelengths produced by BoxRouter and MaizeRouter in March 2007 by 9.9% and 8.4%. respectively. Additionally, we reveal the mathematical basis of negotiated-congestion routing. offer comprehensive analysis of existing routing techniques and discuss several applications at the nanometer scale.

Among the post-CMOS technologies currently under investigation, quantum computing (QC) holds a special place. QC offers not only extremely small size and low power, but also exponential speed-ups for important simulation and optimization problems. It also poses new CAD problems that are similar to. but more challenging, than the related problems in classical (non-quantum) CAD. such as determining if two states or circuits are functionally equivalent. While differences in classical states are easy to detect, quantum states, which are represented by complex-valued vectors, exhibit subtle differences leading to several notions of equivalence. This provides flexibility in optimizing quantum circuits, but leads to difficult new equivalence-checking issues for simulation and synthesis. We identify several different equivalence-checking problems and present algorithms for practical benchmarks, including quantum communication and search circuits, which are shown to be very fast and robust for hundreds of qubits.

Optimized solvers for the Boolean satisfiability (SAT) problem have many applications in areas such as hardware and software verification, FPGA routing, planning, and so forth. Further uses are complicated by the need to express "counting constraints" in conjunctive normal form (CNF). Expressing such constraints by pure CNF leads to more complex SAT instances. Alternatively, those constraints can be handled by integer linear programming (ILP), but generic ILP solvers may ignore the Boolean nature of 0-1 variables. Therefore, specialized 0-1 ILP solvers extend SAT solvers to handle these so-called "pseudo-Boolean" (PB) constraints. This work provides an update on the on-going competition between generic ILP techniques and specialized 0-1 ILP techniques. To make a fair comparison, we generalize recent ideas for fast SAT-solving to more general 0-1 ILP problems that may include counting constraints and optimization. This generalization is embodied in our PB constraint solver and optimizer PBS, which is compared with state-of-the-art CNF and generic ILP solvers. Another aspect of our comparison is the evaluation on 0-1 ILP benchmarks that originate in electronic design automation (EDA) but that cannot be directly solved by an SAT solver. Specifically, we solve instances of the max-SAT and max-ONEs optimization problems, which seek to maximize the number of satisfied clauses and the "true" values over all satisfying assignments, respectively. Those problems have straightforward applications to SAT-based routing and are additionally important due to reductions from max-cut, max-clique, and min vertex cover. Our experimental results show that specialized 0-1 techniques implemented in PBS tend to outperform generic ILP techniques on Boolean optimization problems, as well as on general EDA SAT problems.

Finding the cause of a bug can be one of the most time-consuming activities in design verification. This is particularly true in the case of bugs discovered in the context of a random-simulation-based methodology, where bug traces, or counterexamples, may be several hundred thousand cycles long. In this paper, BUg TRAce MINimization (Butramin), which is a bug trace minimizer, is proposed. Butramin considers a bug trace produced by a random simulator or semiformal verification software and produces an equivalent trace of shorter length. Butramin applies a range of minimization techniques, deploying both simulation-based and formal methods, with the objective of producing highly reduced traces that still expose the original bug. Butramin was evaluated on a range of designs, including the publicly available picoJava microprocessor, and bug traces up to one million cycles long. Experiments show that in most cases, Butramin is able to reduce traces to a very small fraction of their initial sizes, in terms of cycle length and signals involved. The minimized traces can greatly facilitate bug analysis and reduce regression runtime

We demonstrate that Steiner-tree wirelength (StWL) correlates with routed wirelength (rWL) much better than the more common half-perimeter wirelength (HPWL) objective. Therefore, we develop a technique to optimize StWL in global and detail placement without a significant runtime penalty. This new optimization, along with congestion-driven whitespace distribution, improves overall Place-and-Route results, making the use of HPWL unnecessary. Additionally, our empirical results provide ample evidence that the fidelity of net-length estimates is more important than their accuracy in Place-and-Route. The new data structures that make our min-cut algorithms fast can also be useful in multilevel analytical placement. Our placement algorithm Rigorous Optimization Of Steiner-Trees Eases Routing (ROOSTER) outperforms the best published results for Dragon, Capo, FengShui, mPL-R/WSA, and APlace in terms of rWL by 10.7%, 5.6%, 9.3%, 5.5%, and 4.2%, respectively. Via counts, which are especially important at 90 nm and below, are improved by 15.6% over mPL-R/WSA and 11.9% over APlace

In a realistic design flow, circuit and system optimizations must interact with physical aspects of the design. For example, improvements in timing and power may require the replacement of large modules with variants that have different power/delay tradeoff, shape, and connectivity. New logic may be added late in the design flow, which is subject to interconnect optimization. To support such flexibility in design flows, we develop a robust system in performing Engineering Change Orders (ECOs). In contrast with the existing stand-alone tools that offer poor interfaces to the design flow and cannot handle a full range of modern very large scale integration layouts, our ECO-system reliably handles fixed objects and movable macros in instances with widely varying amounts of whitespace. It detects geometric regions and sections of the netlist that require modification and applies an adequate amount of change in each case. Given a reasonable initial placement, it applies minimal changes but is capable of replacing large regions to handle pathological cases. The ECO-system can be used in the range from high-level synthesis to physical synthesis and detail placement.

We propose two new algorithms for rewiring: a postplacement optimization that reconnects pins of a given netlist without changing the logic function and gate locations. In the first algorithm, we extract small subcircuits consisting of several gates from the design and reconnect pins according to the symmetries of the subcircuits. To enhance the power of symmetry detection, we also propose a graph-based symmetry detector that can identify permutational and phase-shift symmetries on multiple input and output wires, as well as hybrid symmetries, creating abundant opportunities for rewiring. Our second algorithm, called long-range rewiring, is based on reconnecting equivalent pins and can augment the first approach for further optimization. We apply our techniques for wirelength optimization and observe that they provide wirelength reduction comparable to that achieved by detailed placement.

The proliferation of OpenAccess is opening promising new research opportunities to academic communities. The benefits of adopting an OpenAccess based approach to EDA research are growing, and we review a number of them. Among them is the ability to learn about a domain while writing software for it, increased ease of code reuse, high-quality benchmarks, and enhanced industry adoption.

Floorplanning algorithms have traditionally underperformed experienced designers, even when relatively simple interconnect metrics are concerned. However, the sheer scale of modern systems on chip makes an all-manual design flow infeasible. In this paper, we propose a new efficient automated approach to the floorplan repair problem, where a set of violated design constraints are satisfied by applying small changes to an existing rough floorplan. Such a floorplan can be produced by a human designer, by a scalable placement algorithm, or result from engineering adjustments to a pre-existing floorplan. In all cases, overlapping modules must be separated, and in some instances, modules may need to be repositioned to satisfy other requirements.The algorithmic framework we propose is built upon an expressive graph-based encoding of constraints. While capable of representing floorplans with or without overlapping modules, it can also support the outline of the core area, fixed module locations, region constraints, proximity and alignment constraints, etc. Instead of applying randomized local search in the hope of satisfying these constraints, we track all implications of imposed constraints and resolve violations by invoking gradual modifications to the floorplan.The primary focus of this paper is on a particularly efficient conflict-directed algorithm for floorplan repair and legalization. It is shown to completely eliminate overlaps from layouts produced by Capo 9.4, Feng Shui 5.1 and APlace 2.01 on IBM-HB benchmarks with hard blocks, typically requiring negligible runtime and increasing interconnect length by only several percent. Furthermore, we are able to generate legal solutions for these instances that surpass previously reported results in wirelength by an average of roughly 7%.

A central problem in built-in self test (BIST) is how to efficiently generate a small set of test vectors that detect all targeted faults. We propose a novel solution that uses linear algebraic concepts to partition the vector space of tests into subspaces (clusters). A subspace is defined by a compact set of basis vectors. We give an algorithm to compute sets of basis vectors defining the clusters. We also describe a low-cost logic circuit based on Gray codes that reproduces the subspaces from these basis vectors. Experimental results are presented which show that this approach reduces on-chip hardware overhead and test application time, while also guaranteeing full fault coverage

Physical Design of modern systems on chip is extremely challenging. Such digital integrated circuits often contain tens of millions of logic gates, intellectual property blocks, embedded memories and custom RTL blocks. At current and future technology nodes, their power and performance are impacted, more than ever, by the placement of their modules. However, our experiments show that traditional techniques for placement and floorplanning, and existing academic tools cannot reliably solve the placement task. To study this problem, we identify particularly difficult industrial instances and reproduce the failures of existing tools by modifying public-domain netlists. Furthermore, we propose algorithms that facilitate floorplacement of these difficult instances. Empirically, our techniques consistently produced legal placements, and on instances where comparison is possible, reduced wirelength by 3.5% over Capo 9.4 and 14.5 % over PATOMA 1.0 — the pre-existing tools that most frequently produced legal placements in our experiments.

We show how to optimize Steiner-tree Wirelength (StWL) in global and detail placement without a significant runtime penalty, making the use of Half-Perimeter Wirelength unnecessary. Given that StWL correlates with Routed Wirelength (rWL) much better than HPWL, our new optimization improves the overall Place-and-Route results. We also develop congestion-driven whitespace distribution during global placement. Comparing to the state of the art where whitespace is redistributed after global placement, we demonstrate that cell-shifting techniques often increase via counts.Our placer ROOSTER outperforms best published results for Dragon, Capo, FengShui, mPL-R/WSA and APlace in terms of routed wirelength by 10.7%, 5.6%, 9.3%, 5.5% and 4.2% respectively. Via counts, especially important at 90nm and below, are improved by 15.6% over mPL-R/WSA and 11.9% over APlace.

In this invited note we outline several algorithms and features appearing in Capo 10, free open-source software for congestion-driven standard cell placement, mixed-size placement and floorplanning. Capo scales on par with industry placers and has been successfully used with a broad range of netlists. It can also satisfy lower bounds on local whitespace, using several techniques for global, detail and macro placement.

Code optimization and high level synthesis can be posed as constraint satisfaction and optimization problems, such as graph coloring used in register allocation. Graph coloring is also used to model more traditional CSPs relevant to AI, such as planning, time-tabling and scheduling. Provably optimal solutions may be desirable for commercial and defense applications. Additionally, for applications such as register allocation and code optimization, naturally-occurring instances of graph coloring are often small and can be solved optimally. A recent wave of improvements in algorithms for Boolean satisfiability (SAT) and 0-1 Integer Linear Programming (ILP) suggests generic problem-reduction methods, rather than problem-specific heuristics, because (1) heuristics may be upset by new constraints, (2) heuristics tend to ignore structure, and (3) many relevant problems are provably inapproximable. Problem reductions often lead to highly symmetric SAT instances, and symmetries are known to slow down SAT solvers. In this work, we compare several avenues for symmetry breaking, in particular when certain kinds of symmetry are present in all generated instances. Our focus on reducing CSPs to SAT allows us to leverage recent dramatic improvement in SAT solvers and automatically benefit from future progress. We can use a variety of black-box SAT solvers without modifying their source code because our symmetry-breaking techniques are static, i.e., we detect symmetries and add symmetry breaking predicates (SBPs) during pre-processing. An important result of our work is that among the types of instance-independent SBPs we studied and their combinations, the simplest and least complete constructions are the most effective. Our experiments also clearly indicate that instance-independent symmetries should mostly be processed together with instance-specific symmetries rather than at the specification level, contrary to what has been suggested in the literature.

Reversible logic is motivated by low-power design, quantum circuits, and nanotechnology. We develop a compact representation of small reversible circuits to generate and store optimal circuits for all 40,320 three-input reversible functions, and millions of four-input circuits. This allows implementing a function optimally in constant time for use in the peephole optimization of larger circuits produced by existing techniques, and guarantees that every three-bit subcircuit is optimal. To generate subcircuits, we use a graph-based data structure and algorithms for circuit restructuring. Finally, we demonstrate a suboptimal circuit for which peephole optimization fails.

Identifying and breaking the symmetries of conjunctive normal form (CNF) formulae has been shown to lead to significant reductions in search times. Symmetries in the search space are broken by adding appropriate symmetry-breaking predicates (SBPs) to an SAT instance in CNF. The SBPs prune the search space by acting as a filter that confines the search to nonsymmetric regions of the space without affecting the satisfiability of the CNF formula. For symmetry breaking to be effective in practice, the computational overhead of generating and manipulating SBPs must be significantly less than the runtime savings they yield due to search space pruning. In this paper, we describe a more systematic and efficient construction of SBPs. In particular, we use the cycle structure of symmetry generators, which typically involve very few variables, to drastically reduce the size of SBPs. Furthermore, our new SBP construction grows linearly with the number of relevant variables as opposed to the previous quadratic constructions. Our empirical data suggest that these improvements reduce search runtimes by one to two orders of magnitude on a wide variety of benchmarks with symmetries.

Large macro blocks, predesigned datapaths, embedded memories, and analog blocks are increasingly used in application-specific integrated circuit (ASIC) designs. However, robust algorithms for large-scale placement of such designs have only recently been considered in the literature. Large macros can be handled by traditional floorplanning, but are harder to account for in min-cut and analytical placement. On the other hand, traditional floorplanning techniques do not scale to large numbers of objects, especially in terms of solution quality. The authors propose to integrate min-cut placement with fixed-outline floorplanning to solve the more general placement problem, which includes cell placement, floorplanning, mixed-size placement, and achieving routability. At every step of min-cut placement, either partitioning or wirelength-driven fixed-outline floorplanning is invoked. If the latter fails, the authors undo an earlier partitioning decision, merge adjacent placement regions, and refloorplan the larger region to find a legal placement for the macros. Empirically, this framework improves the scalability and quality of results for traditional wirelength-driven floorplanning. It has been validated on recent designs with embedded memories and accounts for routability. Additionally, the authors propose that free-shape rectilinear floorplanning can be used with rough module-area estimates before logic synthesis

The pressure of fundamental limits on classical computation and the promise of exponential speedups from quantum effects have recently brought quantum circuits (Proc. R. Soc. Lond. A, Math. Phys. Sci., vol. 425, p. 73, 1989) to the attention of the electronic design automation community (Proc. 40th ACM/IEEE Design Automation Conf., 2003), (Phys. Rev. A, At. Mol. Opt. Phy., vol. 68, p. 012318, 2003), (Proc. 41st Design Automation Conf., 2004), (Proc. 39th Design Automation Conf., 2002), (Proc. Design, Automation, and Test Eur., 2004), (Phys. Rev. A, At. Mol. Opt. Phy., vol. 69, p. 062321, 2004), (IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 22, p. 710, 2003). Efficient quantum-logic circuits that perform two tasks are discussed: 1) implementing generic quantum computations, and 2) initializing quantum registers. In contrast to conventional computing, the latter task is nontrivial because the state space of an n-qubit register is not finite and contains exponential superpositions of classical bitstrings. The proposed circuits are asymptotically optimal for respective tasks and improve earlier published results by at least a factor of 2. The circuits for generic quantum computation constructed by the algorithms are the most efficient known today in terms of the number of most expensive gates [quantum controlled-NOTs (CNOTs)]. They are based on an analog of the Shannon decomposition of Boolean functions and a new circuit block, called quantum multiplexor (QMUX), which generalizes several known constructions. A theoretical lower bound implies that the circuits cannot be improved by more than a factor of 2. It is additionally shown how to accommodate the severe architectural limitation of using only nearest neighbor gates, which is representative of current implementation technologies. This increases the number of gates by almost an order of magnitude, but preserves the asymptotic optimality of gate counts.

With impressive progress in Boolean Satisfiability (SAT) solving and several extensions to pseudo-Boolean (PB) constraints, many applications that use SAT, such as high-performance formal verification techniques are still restricted to checking satisfiability of certain conditions. However, there is also frequently a need to express a preference for certain solutions. Extending SAT-solving to Boolean optimization allows the use of objective functions to describe a desirable solution. Although recent work in 0-1 Integer Linear Programming (ILP) offers extensions that can optimize a linear objective function, this is often achieved by solving a series of SAT or ILP decision problems. Our work articulates some pitfalls of this approach. An objective function may complicate the use of any symmetry that might be present in the given constraints, even when the constraints are unsatisfiable and the objective function is irrelevant. We propose several new techniques that treat objective functions differently from CNF/PB constraints and accelerate Boolean optimization in many practical cases. We also develop an adaptive flow that analyzes a given Boolean optimization problem and picks the symmetry-breaking technique that is best suited to the problem characteristics. Empirically, we show that for non-trivial objective functions that destroy constraint symmetries, the benefit of static symmetry-breaking is lost but dynamic symmetry-breaking accelerates problem-solving in many cases. We also introduce a new objective function, Localized Bit Selection (LBS), that can be used to specify a preference for bit values in formal verification applications.

The pressure of fundamental limits on classical computation and the promise of exponential speedups from quantum effects have recently brought quantum circuits to the attention of the EDA community [10, 17, 4, 16, 9]. We discuss efficient circuits to initialize quantum registers and implement generic quantum computations. Our techniques yield circuits that are twice as small as the best previously published technique. Moreover, a theoretical lower bound shows that our new circuits can be improved by at most a factor of two. Further, the circuits grow by at most a factor of nine under severe architectural restrictions.

Soft errors are an increasingly serious problem for logic circuits. To estimate the effects of soft errors on such circuits, we develop a general computational framework based on probabilistic transfer matrices (PTMs). In particular, we apply them to evaluate circuit reliability in the presence of soft errors, which involves combining the PTMs of gates to form an overall circuit PTM. Information, such as output probabilities, the overall probability of error, and signal observability, can then be extracted from the circuit PTM. We employ algebraic decision diagrams (ADDs) to improve the efficiency of PTM operations. A particularly challenging technical problem, solved in our work, is to extend simultaneously tensor products and matrix multiplication in terms of ADDs to non-square matrices. Our PTM-based method enables accurate evaluation of reliability for moderately large circuits and can be extended by circuit partitioning. To demonstrate the power of the PTM approach, we apply it to several problems in fault-tolerant design and reliability improvement.

Recent work on differential power analysis shows that even mathematically-secure cryptographic protocols may be vulnerable at the physical implementation level. By measuring energy consumed by a working digital circuit, one can glean enough information to break encryption. Thwarting such attacks requires a new approach to logic and physical design. In this work, we seek to equalize switching activity of a circuit over all possible inputs and input transitions by adding redundant gates and increasing the overall number of signal transitions. We introduce uniformly-switching (U-S) logic, and present a doubling construction that equalizes power dissipation without requiring drastic changes in CAD tools.

Transient faults are becoming an increasingly serious concern for logic circuits. They can be caused by thermal neutrons, present at all altitudes, and by other types of ionizing radiation, especially in aerospace applications and nuclear engineering. In this paper we examine issues related to detection of transient errors. The difficulty in testing for transient errors is that they are not always present. Test vectors need to be repeated a number of times in order to detect a fault. We show how to compute a measure for the detectability of transient faults with respect to specific test vectors. This is done using a matrix-based gate-fault model known as the probabilistic transfer matrix model. Using this detectability measure we derive methods to generate multisets of tests to verify probability distributions of faults and detect abnormalities in circuit behavior. Applications of this method include detection of increased atmospheric radiation in terms of its impact on circuits, and testing for process variation that increases the susceptibility of a circuit to transient errors.

Finding the cause of a bug can be one of the most time-consuming activities in design verification. This is particularly true in the case of bugs discovered in the context of a random simulation- based methodology, where bug traces, or counter-examples, may contain several hundred thousand cycles. In this work we propose Butramin, a bug trace minimizer. Butramin considers a bug trace produced by a random simulator or a semi-formal verification software and produces an equivalent trace of shorter length. Butramin applies a range of minimization techniques, deploying both simulation-based and formal methods, with the objective of producing highly reduced traces that still expose the original bug. We evaluated Butramin on a range of designs, including the publicly available picoJava microprocessor. Our experiments show that in most cases Butramin is able to reduce traces to a small fraction of their initial size, in terms of cycle length and signals involved.

Separate optimizations of logic and layout have been thoroughly studied in the past and are well documented for common benchmarks. However, to be competitive, modern circuit optimizations must use physical and logic information simultaneously. In this work, we propose new algorithms for rewiring and rebuffering - a post-placement optimization that reconnects pins of a given netlist without changing the logic function and gate locations. These techniques are compatible with separate layout and logic optimizations, and appear independent of them. In particular, when the new optimization is applied before or after detailed placement, it approximately doubles the improvement in wirelength. Our contributions are based on exhaustive search for functional symmetries in sub-circuits consisting of several gates. Our graph-based symmetry finding is more comprehensive than previously known algorithms - it detects permutational and phase-shift symmetries on multiple input and output wires, as well as hybrid symmetries, creating more opportunities for rewiring and rebuffering.

Research in floorplanning and block-packing has generated a variety of data structures to represent spatial configurations of circuit modules. Much of this work focuses on the geometry of module shapes and seeks tighter packing, as well as improvements in the asymptotic worst-case complexity of algorithms for standard tasks. In this work we consider the implications of interconnect optimization on the value of floorplan representations and establish a framework for comparing different representations. By analyzing performance bottlenecks in block packing and properties of floorplan representations, we show that many of the mathematical results in floorplanning do not translate into better VLSI layouts. This is confirmed by extensive empirical data for stand-alone floorplanners and integrated applications.

In this invited note we describe Capo, an open-source software tool for cell placement, mixed-size placement and floorplanning with emphasis on routability. Capo is among the fastest academic placers and scales to millions of movable objects. This note surveys the overall structure of Capo, discusses recent improvements and describes ongoing research.

Physical design EDA research in academia has historically been based on infrastructure developed independently by individual contributors. This has led to fragmentation in the community, where interaction, data interchange and comparison of results between tools are difficult. We discuss our early experience with the OpenAccess Gear system, an open source software initiative intended to provide pieces of the critical integration and analysis infrastructure that are taken for granted in proprietary tools, but often wholly absent in research tools. Built on top of the widely available OpenAccess database, OA Gear provides components such as industrial-strength static timing analysis and extensible layout and netlist visualization. We discuss preliminary results from two on-going research efforts that have adopted OA Gear as their infrastructure: retrofitting the University of Michigan Capo placer into this environment, and the addition of a timing-driven capability to the Carnegie Mellon Warp placer.

While recent literature on circuit layout addresses large-scale standard-cell placement, the authors typically assume that all macros are fixed. Floorplanning techniques are very good at handling macros, but do not scale to hundreds of thousands of placeable objects. Therefore we combine floorplanning techniques with placement techniques to solve the more general placement problem. Our work shows how to place macros consistently with large numbers of small standard cells. Proposed techniques can also be used to guide circuit designers who prefer to place macros by hand.We address the computational difficulty of layout problems involving large macros and numerous small logic cells at the same time. Proposed algorithms are evaluated in the context of wirelength minimization because a computational method that is not scalable in optimizing wirelength is unlikely to be successful for more complex objectives (congestion, delay, power, etc.)We propose several different design flows to place mixed-size placement instances. The first flow relies on an arbitrary black-box standard-cell placer to obtain an initial placement and then removes possible overlaps using a fixed-outline floorplanner. This results in valid placements for macros, which are considered fixed. Remaining standard cells are then placed by another call to the standard-cell placer. In the second flow a standard-cell placer generates an initial placement and a force-directed placer is used in the engineering change order (ECO) mode to generate an overlap-free placement. Empirical evaluation on ibm benchmarks shows that in most cases our proposed flows compare favorably with previously published mixed-size placers, Kraftwerk, and the mixed-size floor-placer proposed at the 2003 Conference on Design, Automation, and Test in Europe (DATE 2003), and are competitive with mPG-MS.

Instances of the Boolean satisfiability problem (SAT) arise in many areas of circuit design and verification. These instances are typically constructed from some human-designed artifact, and thus are likely to possess much inherent symmetry and sparsity. Previous work[4] has shown that exploiting symmetries results in vastly reduced SAT solver run times, often with the search for the symmetries themselves dominating the total SAT solving time. Our contribution is twofold. First, we dissect the algorithms behind the venerable NAUTY[9] package, particularly the partition refinement procedure responsible for the majority of search space pruning as well as the majority of run time overhead. Second, we present a new symmetry-detection tool, SAUCY, which outperforms NAUTY by several orders of magnitude on the large, structured CNF formulas generated from typical EDA problems.

This paper describes a new algorithm for extracting unsatisfiable subformulas from a given unsatisfiable CNF formula. Such unsatisfiable cores can be very helpful in diagnosing the causes of infeasibility in large systems. Our algorithm is unique in that it adapts the learning process of a modern SAT solver to identify unsatisfiable subformulas rather than search for satisfying assignments. Compared to existing approaches, this method can be viewed as a bottom-up core extraction procedure which can be very competitive when the core sizes are much smaller than the original formula size. Repeated runs of the algorithm with different branching orders yield different cores. We present experimental results on a suite of large automotive benchmarks showing the performance of the algorithm and highlighting its ability to locate not just one but several cores.

In this work we improve top-down min-cut placers in the context of timing closure. Using the concept of boosting factors, we adjust net weights according to net spans, so as to reduce the quadratic wirelength. Our method is generic and does not involve any timing analysis during or prior to placement. In essence, we skew the netlength distribution produced by a min-cut placer so as to decrease the number of long nets, with minimal impact on the overall wirelength. Empirically this approach does not significantly affect runtime, but reduces the worst negative slack and total negative slack of industrial benchmarks by up to 70% compared to Capo and a leading industrial placer.

Code optimization and high level synthesis can be posed as constraint satisfaction and optimization problems, such as graph coloring used in register allocation. Naturally-occurring instances of such problems are often small and can be solved optimally. A recent wave of improvements in algorithms for Boolean satisfiability (SAT) and 0-1 ILP suggests generic problem-reduction methods, rather than problem-specific heuristics, because: (1) heuristics are easily upset by new constraints; (2) heuristics tend to ignore structure; and (3) many relevant problems are provably inapproximable. The NP-spec project offers a language to specify NP-problems and automatic reductions to SAT. Problem reductions often lead to highly symmetric SAT instances, and symmetries are known to slow down SAT solvers. In this work, we compare several avenues for symmetry-breaking, in particular when certain kinds of symmetry are present in all generated instances. Our surprising conclusion is that instance-independent symmetries should often be processed together with instance-specific symmetries rather than earlier, at the specification level.

We show how to implement an arbitrary two-qubit unitary operation using any of several quantum gate libraries with small a priori upper bounds on gate counts. In analogy to library-less logic synthesis, we consider circuits and gates in terms of the underlying model of quantum computation, and do not assume any particular technology. As increasing the number of qubits can be prohibitively expensive, we assume throughout that no extra qubits are available for temporary storage. Using quantum circuit identities, we improve an earlier lower bound of 17 elementary gates by Bullock and Markov to 18, and their upper bound of 23 elementary gates to 18. We also improve upon the generic circuit with six CNOT gates by Zhang et al. (our circuit uses three), and that by Vidal and Dawson with 11 basic gates (we use 10). We study the performance of our synthesis procedures on two-qubit operators that are useful in quantum algorithms and communication protocols. With additional work, we find small circuits and improve upon previously known circuits in some cases.

Simulating quantum computation on a classical computer is a difficult problem. The matrices representing quantum gates, and vectors modeling qubit states grow exponentially with the number of qubits. It has been shown experimentally that the QuIDD (Quantum Information Decision Diagram) datastructure greatly facilitates simulations using memory and runtime that are polynomial in the number of qubits. In this paper, we present a complexity analysis which formally describes this class of matrices and vectors. We also present an improved implementation of QuIDDs which can simulate Grover's algorithm for quantum search with the asymptotic runtime complexity of an ideal quantum computer up to negligible overhead.

We propose a new floorplanner BloBB based on multi-level branch-and-bound. It is competitive with annealers in terms of runtime and solution quality. We empirically quantify the gap between optimal slicing and non-slicing floorplans by comparing optimal packings and best seen results. Optimal slicing and non-slicing packings for apte, xerox and hp are reported. We also discover that the soft versions of all MCNC benchmarks, except for apte, and all GSRC benchmarks can be packed with zero dead-space.Additionally, realistic floorplans often have blocks with similar dimensions, if design blocks, such as memories, are reused. We show that this greatly reduces the complexity of black-packing.

Cell overlaps in the results of global placement are guaranteed to prevent successful routing. However, common techniques for fixing these problems may endanger routing in a different way --- through increased wirelength and congestion. We evaluate several such techniques with routability of row-based placements in mind, and propose new ones that, in conjunction with our detail placer, improve overall routability and routed wirelength. Our generic two-phase approach for resolving illegal placements calls for (i) balancing the numbers of cells in rows, (ii) removing overlaps within rows through a generic dynamic programming procedure. Relevant objectives include minimum total perturbation, minimum wirelength increase and minimum maximum movement. Additionally, we trace cell overlaps in min-cut placement to vertical cuts and show that, if bisection cut directions are varied, overlaps anti-correlate with improved wirelength.Empirical validation is performed using placers Capo and Cadence QPlace, followed by various legalizers and detail placers, with subsequent routing by Cadence WarpRoute. We use a number of IBMv2 benchmarks with routing information. Our legalizer reduces both Capo and QPlace placements' wirelength by up to 4% compared to results of Capo legalized by Cadence's QPlace in the ECO mode.

In the last 20 years, mainstream research in VLSI placement has been driven by formal optimization and the ad hoc requirement that downstream tools, particularly routers, work. Progress is currently measured by improving routed wirelength and place-and-route run-time on large benchmarks. However, these results now appear questionable as (i) major placers were shown to be tuned to particular benchmark suites, and (ii) some reported improvements could not be replicated on full-fledged industrial circuits.Instead of blind wirelength minimization, our work seeks a better understanding of what a good placer should produce and what existing placers actually produce. We abstract away details from various circuit patterns into separate "constructive benchmarks" and perform a detailed study of leading placers. Unlike the randomized PEKO benchmarks, ours are highly structured and easy to visualize. We know all of their wirelength-optimal solutions, and in many cases there is only one per benchmark. By comparing actual solutions to optimal ones, we reason about the underlying placer algorithms and their possible improvements.In a new development, we show that the (wirelength) sub-optimality ratio of several existing placers quickly grows with the size of the netlist. Some of the reasons for such poor performance are obvious from our visualizations. While it seems easy to coerce a given placer to improve wirelength on any particular constructive benchmark, improving the overall performance is more difficult. We improve the performance of Capo placer on several constructive benchmarks and a proprietary 72K-cell circuit from IBM, without wirelength penalty on commonly used benchmarks.

Large macro blocks, pre-designed datapaths, embedded memories and analog blocks are increasingly used in ASIC designs. However, robust algorithms for large-scale placement of such designs have only recently been considered in the literature, and improvements by over 10% per paper are still common. Large macros can be handled by traditional floorplanning, but are harder to account for in min-cut and analytical placement. On the other hand, traditional floorplanning techniques do not scale to large numbers of objects, especially in terms of solution quality. We propose to integrate min-cut placement with fixed-outline floor-planning to solve the more general placement problem, which includes cell placement, floorplanning, mixed-size placement and achieving routability. At every step of min-cut placement, either partitioning or wirelength-driven, fixed-outline floorplanning is invoked. If the latter fails, we undo an earlier partitioning decision, merge adjacent placement regions and re-floorplan the larger region to find a legal placement for the macros. Empirically, this framework improves the scalability and quality of results for traditional wirelength-driven floorplanning. It has been validated on recent designs with embedded memories and accounts for routability. Additionally, we propose that free-shape rectilinear floorplanning can be used with rough module-area estimates before synthesis.

Over the last five years, the large scale integrated circuit placement community achieved great strides in the understanding of placement problems, developed new high-performance algorithms, and achieved impressive empirical results. These advances have been supported by a nontrivial benchmarking infrastructure, and future achievements are set to draw on benchmarking as well. In this paper, we review motivations for benchmarking, especially for commercial electronic design automation, analyze available benchmarks, and point out major pitfalls in benchmarking. Our empirical data offers perhaps the first comprehensive evaluation of several leading large-scale placers on multiple benchmark families. We outline major outstanding problems and discuss the future of placement benchmarking. Furthermore, we attempt to extrapolate our experience to circuit layout tasks beyond placement.

Applications of reversible circuits can be found in the fields of low-power computation, cryptography, communications, digital signal processing, and the emerging field of quantum computation. Furthermore, prototype circuits for low-power applications are already being fabricated in CMOS. Regardless of the eventual technology adopted, testing is sure to be an important component in any robust implementation. We consider the test-set generation problem. Reversibility affects the testing problem in fundamental ways, making it significantly simpler than for the irreversible case. For example, we show that any test set that detects all single stuck-at faults in a reversible circuit also detects all multiple stuck-at faults. We present efficient test-set constructions for the standard stuck-at fault model, as well as the usually intractable cell-fault model. We also give a practical test-set generation algorithm, based on an integer linear programming formulation, that yields test sets approximately half the size of those produced by conventional automatic test pattern generation.

Aggressive process scaling and increasing clock rates have made crosstalk noise an important issue in VLSI design. Switching on long, adjacent bus wires can lead to timing violations and logic faults. At the same time, system-level interconnects have also become more susceptible to other less predictable forms of interference such as noise induced by power grid fluctuations, electromagnetic interference, and alpha-particle radiation. Previous work has treated these systematic and nonsystematic forms of noise separately. We propose to make system-level interconnects more robust using encoding that simultaneously addresses error-correction requirements and crosstalk noise avoidance. This is more efficient than satisfying these requirements separately. We give algorithms for obtaining optimal encodings and present a practical class of codes called boundary-shift codes. We evaluate the overhead of our method, and make comparisons to using error-correction with simple shielding.

Simulating quantum computation on a classical computer is a difficult problem. The matrices representing quantum gates, and vectors modeling qubit states grow exponentially with an increase in the number of qubits. However, by using a new data structure called the Quantum Information Decision Diagram (QuIDD) that exploits the structure of quantum operators, many of these matrices and vectors can be represented in a form that grows polynomially. Using QuIDDs, we implemented a general-purpose quantum computing simulator in C++ called QuIDDPro and tested it on Grover's algorithm. Our QuIDD technique asymptotically outperforms other known simulation techniques.

Boolean satisfiability (SAT) solvers have experienced dramatic improvements in their performance and scalability over the last several years [5, 7] and are now routinely used in diverse EDA applications. Nevertheless, a number of practical SAT instances remain difficult to solve [9] and continue to defy even the best available SAT solvers [5, 7]. Recent work pointed out that symmetries in the Boolean search space are often to blame. A theoretical framework for detecting and breaking such symmetries was introduced in [2]. This framework was subsequently extended, refined, and empirically shown to yield significant speed-ups for a large number of benchmark classes in [1].Symmetries in the search space are broken by adding appropriate symmetry-breaking predicates (SBPs) to a SAT instance in conjunctive normal form (CNF). The SBPs prune the search space by acting as a filter that confines the search to non-symmetric regions of the space without affecting the satisfiability of the CNF formula. For symmetry breaking to be effective in practice, the computational overhead of generating and manipulating the SBPs must be significantly less than the run time savings they yield due to search space pruning. In this paper we present several new constructions of SBPs that improve on previous work. Specifically, we give a linear-sized CNF formula that selects lex-leaders (among others) for single permutations. We also show how that formula can be simplified by taking advantage of the sparsity of permutations. We test these improvements against earlier constructions and show that they yield smaller SBPs and lead to run time reductions on many benchmarks.

Quantum circuits currently constitute a dominant model for quantum computation [14]. Our work addresses the problem of constructing quantum circuits to implement an arbitrary given quantum computation, in the special case of two qubits. We pursue circuits without ancilla qubits and as small a number of elementary quantum gates [1, 9] as possible. Our lower bound for worst-case optimal two-qubit circuits calls for at least 17 gates: 15 one-qubit rotations and 2 CNOTs. To this end, we constructively prove a worstcase upper bound of 23 elementary gates, of which at most 4 (CNOTs) entail multi-qubit interactions. Our analysis shows that previously known synthesis algorithms, although more general, entail much larger quantum circuits than ours in the special case of two qubits. One such algorithm [4] has a worst case of 61 gates of which 18 may be CNOTs. Our techniques rely on the KAK decomposition from Lie theory as well as the polar and spectral (symmetric Shur) matrix decompositions from numerical analysis. They are related to the canonical decomposition of a two-qubit gate with respect to the "magic basis" of phase-shifted Bell states [11, 12]. We extend this decomposition in terms of elementary gates for quantum computation.

The MINCE heuristic for variable-ordering [1] can successfully reduce the size of BDDs and accelerate SAT-solving. Applications to reachability analysis have also been successful [12]. The main drawback of MINCE is its implementation complexity - the authors used a pre-existing min-cut placer [6] that is several times larger than any existing SAT solver. Tweaking MINCE is difficult.In this work we propose a replacement heuristic, FORCE which is easy to implement from scratch and tweak. It is dramatically faster than MINCE in practice. While FORCE may produce seemingly inferior variable orderings, the difference with MINCE orderings does not affect subsequent SAT-solving.

Over the last five years the VLSI Placement community achieved great strides in the understanding of placement problems, developed new high-performance algorithms, and achieved impressive empirical results. These advances have been supported by non-trivial benchmarking infrastructure, and future achievements are set to draw on benchmarking as well. In this paper we review motivations for benchmarking, especially for commercial EDA, analyze available benchmarks, and point out major pitfalls in benchmarking. We outline major outstanding problems and discuss the future of placement benchmarking. Furthermore, we attempt to extrapolate our experience to circuit layout tasks beyond placement.

Irreversible computation necessarily results in energy dissipation due to information loss. While small in comparison to the power consumption of today's VLSI circuits, if current trends continue this will be a critical issue in the near future. Reversible circuits offer an alternative that, in principle, allows computation with arbitrarily small energy dissipation. Furthermore, reversible circuits are essential components of quantum logic. We consider the problem of testing these circuits, and in particular generating efficient test sets. The reversibility property significantly simplifies the problem, which is generally hard for the irreversible case. We discuss conditions for a test set to be complete, give a number of practical constructions, and consider test sets for worst-case circuits. In addition, we formulate the problem of finding minimal test sets into an integer linear program (ILP) with binary variables. While this ILP method is infeasible for large circuits, we show that combining it with a circuit decomposition approach yields a practical alternative.

Research in algorithms for Boolean satisfiability (SAT) and their implementations (Goldberg and Novikov, 2002), (Moskewicz et al., 2001), (Silva and Sakallah, 1999) has recently outpaced benchmarking efforts. Most of the classic DIMACS benchmarks (ftp:dimacs.rutgers.edu/pub/challenge/sat/benchmarks/cnf ) can now be solved in seconds on commodity PCs. More recent benchmarks (Velev and Bryant, 2001) take longer to solve due to their large size, but are still solved in minutes. Yet, relatively small and difficult SAT instances must exist if P /spl ne/ NP. To this end, our paper articulates SAT instances that are unusually difficult for their size, including satisfiable instances derived from very large scale integration (VLSI) routing problems. With an efficient implementation to solve the graph automorphism problem (McKay, 1990), (Soicher, 1993) (Spitznagel, 1994), we show that in structured SAT instances, difficulty may be associated with large numbers of symmetries. We point out that a previously published symmetry extraction mechanism (Crawford et al., 1996) based on a reduction to the graph automorphism problem often produces many spurious symmetries. Our paper contributes two new reductions to graph automorphism, which extract all correct symmetries found previously (Crawford et al., 1996) as well as phase-shift symmetries not found earlier. The correctness of our reductions is rigorously proven, and they are evaluated empirically. We also formulate an improved construction of symmetry-breaking clauses in terms of permutation cycles and propose to use only generators of symmetries in this process. These ideas are implemented in a fully automated flow that first extracts symmetries from a given SAT instance, preprocesses it by adding symmetry-breaking clauses, and then calls a state-of-the-art backtrack SAT solver. Significant speed-ups are shown on many benchmarks versus direct application of the solver. In an attempt to further improve the practicality of our approach, we propose a scheme for fast "opportunistic" symmetry extraction and also show that considerations of symmetry may lead to more efficient reductions to SAT in the VLSI routing domain.

Increased transistor density in modern commercial ICs typically originates in new manufacturing and defect prevention technologies. Additionally, better utilization of such low-level transistor density may result from improved software that makes fewer assumptions about physical layout in order to reliably automate the design process. In particular, recent layouts tend to have large amounts of whitespace, which is not handled properly by older tools. We observe that a major computational difficulty arises in partitioning-driven top-down placement when regions of a chip lack whitespace. This tightens balance constraints for min-cut partitioning and hampers move-based local-search heuristics such as Fiduccia-Mattheyses. However, the local lack of whitespace is often caused by very unbalanced distribution of whitespace during previous partitioning, and this concern is emphasized in chips with large overall whitespace. This paper focuses on accurate computation of tolerances to ensure smooth operation of common move-based iterative partitioners, while avoiding cell overlaps. We propose a mathematical model of hierarchical whitespace allocation in placement, which results in a simple computation of partitioning tolerance purely from relative whitespace in the block and the number of rows in the block. Partitioning tolerance slowly increases as the placer descends to lower levels, and relative whitespace in all blocks is limited from below (unless partitioners return "illegal" solutions), thus preventing cell overlaps. This facilitates good use of whitespace when it is scarce and prevents very dense regions when large amounts of whitespace are available. Our approach improves the use of the available whitespace during global placement, thus leading to smaller whitespace requirements. Existing techniques, particularly those based on simulated annealing, can be applied after global placement to bias whitespace with respect to particular concerns, such as routing congestion, heat dissipation, crosstalk noise and DSM yield improvement.

Reversible or information-lossless circuits have applications in digital signal processing, communication, computer graphics, and cryptography. They are also a fundamental requirement in the emerging field of quantum computation. We investigate the synthesis of reversible circuits that employ a minimum number of gates and contain no redundant input-output line-pairs (temporary storage channels). We prove constructively that every even permutation can be implemented without temporary storage using NOT, CNOT, and TOFFOLI gates. We describe an algorithm for the synthesis of optimal circuits and study the reversible functions on three wires, reporting the distribution of circuit sizes. We also study canonical circuit decompositions where gates of the same kind are grouped together. Finally, in an application important to quantum computing, we synthesize oracle circuits for Grover's search algorithm, and show a significant improvement over a previously proposed synthesis algorithm.

Classical floorplanning minimizes a linear combination of area and wirelength. When simulated annealing is used, e.g., with the sequence pair representation, the typical choice of moves is fairly straightforward. In this paper, we study the fixed-outline floorplan formulation that is more relevant to hierarchical design style and is justified for very large ASICs and SoCs. We empirically show that instances of the fixed-outline floorplan problem are significantly harder than related instances of classical floorplan problems. We suggest new objective functions to drive simulated annealing and new types of moves that better guide local search in the new context. Wirelength improvements and optimization of aspect ratios of soft blocks are explicitly addressed by these techniques. Our proposed moves are based on the notion of floorplan slack. The proposed slack computation can be implemented with all existing algorithms to evaluate sequence pairs, of which we use the simplest, yet semantically indistinguishable from the fastest reported . A similar slack computation is possible with many other floorplan representations. In all cases the computation time approximately doubles. Our empirical evaluation is based on a new floorplanner implementation Parquet-1 that can operate in both outline-free and fixed-outline modes. We use Parquet-1 to floorplan a design, with approximately 32000 cells, in 37 min using a top-down, hierarchical paradigm.

A priori interconnect prediction and technology extrapolation are closely intertwined. Interconnect predictions are at the core of technology extrapolation models of achievable system power, area density, and speed. Technology extrapolation, in turn, informs a priori interconnect prediction via models of interconnect technology and interconnect optimizations. In this paper, we address the linkage between a priori interconnect prediction and technology extrapolation in two ways. First, we describe how rapid changes in technology, as well as rapid evolution of prediction methods, require a dynamic and flexible framework for technology extrapolation. We then develop a new tool, the GSRC technology extrapolation system (GTX), which allows capture of such knowledge and rapid development of new studies. Second, we identify several "nontraditional" facets of interconnect prediction and quantify their impact on key technology extrapolations. In particular, we explore the effects of interconnect design optimizations such as shield insertion, repeater sizing and repeater staggering, as well as modeling choices for RLC interconnects.

Research in algorithms for Boolean satisfiability and their implementations [23, 6] has recently outpaced benchmarking efforts. Most of the classic DIMACS benchmarks [10] can be solved in seconds on commodity PCs. More recent benchmarks take longer to solve because of their large size, but are still solved in minutes [25]. Yet, small and difficult SAT instances must exist because Boolean satisfiability is NP-complete.We propose an improved construction of symmetry-breaking clauses [9] and apply it to achieve significant speed-ups over current state-of-the-art in Boolean satisfiability. Our techniques are formulated as pre-processing and can be applied to any SAT solver without changing its source code. We also show that considerations of symmetry may lead to more efficient reductions to SAT in the routing domain.Our work articulates SAT instances that are unusually difficult for their size, including satisfiable instances derived from routing problems. Using an efficient implementation to solve the graph automorphism problem [18, 20, 22], we show that in structured SAT instances difficulty may be associated with large numbers of symmetries.

Optimized solvers for the Boolean Satisfiability (SAT) problem have many applications in areas such as hardware and software verification, FPGA routing, planning, etc. Further uses are complicated by the need to express "counting constraints" in conjunctive normal form (CNF). Expressing such constraints by pure CNF leads to more complex SAT instances. Alternatively, those constraints can be handled by Integer Linear Programming (ILP), but generic ILP solvers may ignore the Boolean nature of 0--1 variables. Therefore specialized 0--1 ILP solvers extend SAT solvers to handle these so-called "pseudo-Boolean" constraints.This work provides an update on the on-going competition between generic ILP techniques and specialized 0--1 ILP techniques. To make a fair comparison, we generalize recent ideas for fast SAT-solving to more general 0--1 ILP problems that may include counting constraints and optimization. Another aspect of our comparison is evaluation on 0--1 ILP benchmarks that originate in Electronic Design Automation (EDA), but that cannot be directly solved by a SAT solver. Specifically, we solve instances of the Max-SAT and Max-ONEs optimization problems which seek to maximize the number of satisfied clauses and the "true" values over all satisfying assignments, respectively. Those problems have straightforward applications to SAT-based routing and are additionally important due to reductions from Max-Cut, Max-Clique, and Min Vertex Cover. Our experimental results show that specialized 0--1 techniques tend to outperform generic ILP techniques on Boolean optimization problems as well as on general EDA SAT problems.

Reversible or information-lossless circuits have applications in digital signal processing, communication, computer graphics and cryptography. They are also a fundamental requirement in the emerging field of quantum computation. We investigate the synthesis of reversible circuits that employ a minimum number of gates and contain no redundant input-output line-pairs (temporary storage channels). We prove constructively that every even permutation can be implemented without temporary storage using NOT, CNOT and TOFFOLI gates. We describe an algorithm for the synthesis of optimal circuits and study the reversible functions on three wires, reporting distributions of circuit sizes. Finally, in an application important to quantum computing, we synthesize oracle circuits for Grover's search algorithm, and show a significant improvement over a previously proposed synthesis algorithm.

Boolean functions are fundamental to synthesis and verification of digital logic, and compact representations of Boolean functions have great practical significance. Popular representations, such as CNF, DNF, circuits and ROBDDs [4], offer different advantages and are preferred for different tasks. Conversion between those representations is common, especially when one is used to represent the input and another speeds up relevant algorithms. Our work addresses the construction of ROBDDs that represent outputs of a given Boolean circuit. It is used in synthesis and verification. Earlier works (Fujita, Fujisawa, and Kawato, 1988. Malik et al., 1988.) proposed ordering circuit inputs and gates by graph traversals. We contribute orderings based on circuit partitioning and placement, leveraging the progress in recursive bisection and multi-level min-cut partitioning achieved in late 1990s. Our empirical results show that the proposed orderings based on circuit partitioning and placement are more successful than straightforward DFS and BFS, as well as related heuristics.

While a number of recent works address large-scale standard-cell placement, they typically assume that all macros are fixed. Floorplanning techniques are very good at handling macros, but do not scale to hundreds of thousands of placeable objects. Therefore we combine floorplanning techniques with placement techniques in a design flow that solves the more general placement problem. Our work shows how to place macros consistently with large numbers of small standard cells. Our techniques can also be used to guide circuit designers who prefer to place macros by hand.

At the 250nm technology node, interconnect delays account for over 40% of worst delays [12]. Transition to 130nm and below increases this figure, and hence the relative importance of timing-driven placement for VLSI. Our work introduces a novel minimization of maximal path delay that improves upon previously known algorithms for timing-driven placement. Our placement algorithms have provable properties and are fast in practice. Empirical validation is based on extending a scalable min-cut placer with proven quality in wirelength- and congestion-driven placement [4]. The CPU overhead of the timing-driven capability is within 50%. We placed industrial circuits and evaluated the resulting layouts with a commercial static timing analyzer.

The increasing popularity of SAT and BDD techniques in verification and synthesis encourages the search for additional speed-ups. Since typical SAT and BDD algorithms are exponential in the worst-case, the structure of real-world instances is a natural source of improvements. While SAT and BDD techniques are often presented as mutually exclusive alternatives, our work points out that both can be improved via the use of the same structural properties of instances. Our proposed methods are based on efficient problem partitioning and can be easily applied as pre-processing with arbitrary SAT solvers and BDD packages without source code modifications. Our contribution is validated on the ISCAS circuits and the DIMACS benchmarks. Empirically, our technique often outperforms existing techniques by a factor of two or more. Our results motivate search for stronger dynamic ordering heuristics and combined static/dynamic techniques.

We study the fixed-outline floorplan formulation that is more relevant to hierarchical design style and is justified for very large ASICs and SOCs. We empirically show that the fixed-outline floorplan problem instances are significantly harder than the well-researched instances without fixed outline. Furthermore, we suggest new objective functions to drive simulated annealing and new types of moves that better guide local search in the new context. Our empirical evaluation is based on a new floorplanner implementation Parquet-1 that can operate in both outline free and fixed-outline modes. Our proposed moves are based on the notion of floorplan slack. The proposed slack computation can be implemented with all existing algorithms to evaluate sequence pairs, of which we use the simplest, yet semantically indistinguishable from the fastest reported. A similar slack computation is possible with many other floorplan representations. In all cases, the slowdown is by a constant factor - roughly 2x.

Digital system designs are the product of valuable effort and know-how. Their embodiments, from software and hardware description language program down to device-level netlist and mask data, represent carefully guarded intellectual property (IP). Hence, design methodologies based on IP reuse require new mechanisms to protect the rights of IP producers and owners. This paper establishes principles of watermarking-based IP protection, where a watermark is a mechanism for identification that is: (1) nearly invisible to human and machine inspection; (2) difficult to remove; and (3) permanently embedded as an integral part of the design. Watermarking addresses IP protection by tracing unauthorized reuse and making untraceable unauthorized reuse as difficult as recreating given pieces of IP from scratch. We survey related work in cryptography and design methodology, then develop desiderata, metrics, and concrete protocols for constraint-based watermarking at various stages of the very large scale integration (VLSI) design process. In particular, we propose a new preprocessing approach that embeds watermarks as constraints into the input of a black-box design tool and a new postprocessing approach that embeds watermarks as constraints into the output of a black-box design tool. To demonstrate that our protocols can be transparently integrated into existing design flows, we use a testbed of commercial tools for VLSI physical design and embed watermarks into real-world industrial designs. We show that the implementation overhead is low-both in terms of central processing unit time and such standard physical design metrics as wirelength, layout area, number of vias, and routing congestion. We empirically show that the placement and routing applications considered in our methods achieve strong proofs of authorship and are resistant to tampering and do not adversely influence timing.

Multilevel Fiduccia-Mattheyses (MLFM) hypergraph partitioning [3,22,24] is a fundamental optimization in VLSI CAD physical design.The leading implementation, hMetis [23], has since 1997 pro veditself substantially superior in both runtime and solution quality t o e v en v ery recent w orks (e.g., [13,17,25]).In this work, we present t w o sets of results: (i) new techniques for at FM-based hypergraph partitioning (which is the core of multilev el implementations), and (ii) a new multilev el implementation that oers leadingedge performance.Our new techniques for at partitioning con rm the conjecture from [10], suggesting that specialized partitioning heuristics may be able to actively exploit xed nodes in partitioning instances arising in the driving top-down placement con text.Our FM varian t is competitive with traditional FM on instances without terminals [1] and considerably superior on instances with xed nodes (i.e., arising during top-down placement [8]).Our multilev el FM variant a v oids sev eral complex heuristics and non-trivial tunings that often lead to complex implementations; it ac hiev es trade-os bet w een solution quality and run time that are comparable or better than those achiev ed by hMetis-1.5.3 (the latest available version).F ollowing [6], we attempt to provide algorithm descriptions that are as detailed and unambiguous as possible, to allow replicabilit y and speed impro vements in future research.

Global placement ofhypergraphs is critical in the top-down placement of large timing-driven designs [10, 16]. Placement quality is evaluated in terms of the half-perimeter wirelength (HPWL) of hyperedges in the original circuit hypergraph provided timing constraints are met. Analytical placers are instrumental in handling non-linear timing models [9, 3], but have twoimportant drawbacks: (a) corresponding optimization algorithms are typically slower than top-down methods driven by multi-level mincut partitioning [2], and (b) hyperedges must be represented with net

Technology extrapolation — the calibration and prediction of achievable design in future technology generations — drives the evolution of VLSI system architectures, design methodologies, and design tools. This paper describes initial experiences with development and use of GTX, the MARCO GSRC Technology Extrapolation system. GTX provides a robust, portable framework for interactive specification and comparison of modeling choices, e.g., for predicting system cycle time, die size and power dissipation. We use GTX to reveal surprising levels of uncertainty (modeling and parameter sensitivity) in widely-cited cycle-time models that drive recent roadmaps. We also describe new SOI and bulk device models that have been developed for GTX, as well as studies of power dissipation and delay uncertainty under various implementation assumptions for global interconnects.

This work focuses on congestion-driven placement of standard cells into rows in the fixed-die context. We summarize the state-of-the-art after two decades of research in recursive bisection placement and implement a new placer, called Capo, to empirically study the achievable limits of the approach. From among recently proposed improvements to recursive bisection, Capo incorporates a leading-edge multilevel min-cut partitioner [7], techniques for partitioning with small tolerance [8], optimal min-cut partitioners and end-case min-wirelength placers [5], previously unpublished partitioning tolerance computations, and block splitting heuristics. On the other hand, our “good enough” implementation does not use “overlapping” [17], multi-way partitioners [17, 20], analytical placement, or congestion estimation [24, 35]. In order to run on recent industrial placement instances, Capo must take into account fixed macros, power stripes and rows with different allowed cell orientations. Capo reads industry-standard LEF/DEF, as well as formats of the GSRC bookshelf for VLSI CAD algorithms [6], to enable comparisons on available placement instances in the fixed-die regime.

This panel focuses on how new Web-based frameworks can enable academic research and development in VLSI CAD. Open-source initiatives, portals for research communities or for the EDA community at large, algorithm benchmarking support, etc. are a few of the possibilities. Each of the three panelists will describe the current status of efforts toward building new Web-based infrastructure for CAD research. The approaches and “mission statements” illustrate the literally unbounded potential for such frameworks to transform how CAD R&D is performed.

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

We study alternatives to classic Fiduccia-Mattheyses (FM)-based partitioning algorithms in the context of end-case processing for top-down standard-cell placement. While the divide step in the top-down divide and conquer is usually performed heuristically, we observe that optimal solutions can be found for many sufficiently small partitioning instances. Our main motivation is that small partitioning instances frequently contain multiple cells that are larger than the prescribed partitioning tolerance, and that cannot be moved iteratively while preserving the legality of a solution. To sample the suboptimality of FM-based partitioning algorithms, we focus on optimal partitioning and placement algorithms based on either enumeration or branch-and-bound that are invoked for instances below prescribed size thresholds, e.g., <10 cells for placement and <30 cells for partitioning. Such partitioners transparently handle tight balance constraints and uneven cell sizes while typically achieving 40% smaller cuts than best of several FM starts for instances between ten and 50 movable nodes and average degree 2-3. Our branch-and-bound codes incorporate various efficiency improvements, using results for hypergraphs (1993) and a graph-specific algorithm (1996). We achieve considerable speed-ups over single FM starts on such instances on average. Enumeration-based partitioners relying on Gray codes, while easier to implement and taking less time for elementary operations, can only compete with branch-and-bound on very small instances, where optimal placers achieve reasonable performance as well. In the context of a top-down global placer, the right combination of optimal partitioners and placers can achieve up to an average of 10% wirelength reduction and 50% CPU time savings for a set of industry testcases. Our results show that run-time versus quality tradeoffs may be different for small problem instances than for common large benchmarks, resulting in different comparisons of optimization algorithms. We therefore suggest that alternative algorithms be considered and, as an example, present detailed comparisons with the flow-based balanced partitioner heuristic.

We present approximations to non-smooth continuous functions by differentiable functions which are parameterized by a scalar /spl beta/>0 and have convenient limit behavior as /spl beta//spl rarr/0. For standard numerical methods, this translates into a tradeoff between solution quality and speed. We show the utility of our approximations for wirelength and delay estimations used by analytical placers for VLSI layout. Our approximations lead to more "solvable" problems.

Article Hypergraph partitioning for VLSI CAD: methodology for heuristic development, experimentation and reporting Share on Authors: Andrew E. Caldwell UCLA Computer Science Department, Los Angeles, CA UCLA Computer Science Department, Los Angeles, CAView Profile , Andrew B. Kahng UCLA Computer Science Department, Los Angeles, CA UCLA Computer Science Department, Los Angeles, CAView Profile , Andrew A. Kennings Cypress Semiconductor, Beaverton, OR Cypress Semiconductor, Beaverton, ORView Profile , Igor L. Markov UCLA Computer Science Department, Los Angeles, CA UCLA Computer Science Department, Los Angeles, CAView Profile Authors Info & Claims DAC '99: Proceedings of the 36th annual ACM/IEEE Design Automation ConferenceJune 1999 Pages 349–354https://doi.org/10.1145/309847.309955Online:01 June 1999Publication History 20citation418DownloadsMetricsTotal Citations20Total Downloads418Last 12 Months8Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

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

The presence of jixed terminals in hypergraph partitioning instances arising in top-down standard-cell placement makes such instances qualitatively different from the free hypergruphs that have driven the past two decades of VLSI CAD partitioning research.In this paper we empirically show that with fixed terminals in the instance, less effort is needed to stably reach a given solution quality.We then develop new benchmark formats that flexibly capture the presence of terminals and any geometric embedding information associated with the partitioning instance.Our new formats not only allow modeling of top-down placement, but also enable study of placement-specific partitioning objectives, e.g., based on net bounding boxes and Steiner tree estimators.Finally, we develop a new suite of partitioning benchmarks with fixed terminals, based on the actual placement data from the IBM-internal circuits released in the ISPD-98 Benchmark Suite [ 1, 21.A set of partitioning results is presented with nmtime regimes appropriate to the placement use model, as a baseline for future efforts in the research community.

Article Optimal partitioners and end-case placers for standard-cell layout Share on Authors: A. E. Caldwell UCLA Computer Science Dept., Los Angeles, CA UCLA Computer Science Dept., Los Angeles, CAView Profile , A. B. Kahng UCLA Computer Science Dept., Los Angeles, CA UCLA Computer Science Dept., Los Angeles, CAView Profile , I. L. Markov UCLA Computer Science Dept., Los Angeles, CA UCLA Computer Science Dept., Los Angeles, CAView Profile Authors Info & Claims ISPD '99: Proceedings of the 1999 international symposium on Physical designApril 1999 Pages 90–96https://doi.org/10.1145/299996.300032Published:12 April 1999 31citation350DownloadsMetricsTotal Citations31Total Downloads350Last 12 Months7Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Wirelength estimation in very large scale integration layout is fundamental to any predetailed routing estimate of timing or routability. In this paper, we develop efficient wirelength estimation techniques appropriate for wirelength estimation during top-down floorplanning and placement of cell-based designs. Our methods give accurate, linear-time approaches, typically with sublinear time complexity for dynamic updating of estimates (e.g., for annealing placement). Our techniques offer advantages not only for early on-line wirelength estimation during top-down placement, but also for a posteriori estimation of routed wirelength given a final placement. In developing these new estimators, we have made several contributions, including (1) insight into the contrast between region-based and bounding box-based rectilinear Steiner minimal tree (RStMT) estimation techniques; (2) empirical assessment of the correlations between pin placements of a multipin net that is contained in a block; and (3) new wirelength estimates that are functions of a block's complexity (number of cell instances) and aspect ratio.

Digital system designs are the product of valuable effort and knowhow. Their embodiments, from software and HDL program down to device-level netlist and mask data, represent carefully guarded intellectual property (IP). Hence, design methodologies based on IP reuse require new mechanisms to protect the rights of IP producers and owners. This paper establishes principles of watermarkingbased IP protection, where a watermark is a mechanism for identification that is (i) nearly invisible to human and machine inspection, (ii) difficult to remove, and (iii) permanently embedded as an integral part of the design. We survey related work in cryptography and design methodology, then develop desiderata, metrics and example approaches -- centering on constraint-based techniques -- for watermarking at various stages of the VLSI design process. 1 Introduction The advance of processing technology has led to a rapid increase in IC design complexity. The economic drivers are compelling: only by put...

Increasingly popular reuse-based design paradigms create a pressing need for authorship enforcement techniques that protect the intellectual property rights of designers. We develop the first intellectual property protection protocols for embedding design watermarks at the physical design level. We demonstrate that these protocols are tarnsparent with respect to existing industrial tools and design flows, and that they can embed watermarks into real-world industrial designs with very low implementation overhead (as measured by such standard metrics as wirelength, layout area, number of vias, routing congestion and CPU time). On several industrial test cases, we obtain extremely strong, tamper-resistant proofs of authorship for placement and routing solutions.

Wirelength estimation in VLSI layout is fundamental to any pre-detailed routing estimate of timing or routability. In this paper, we develop new wirelength estimation techniques appropriate for top-down floor-planning and placement synthesis of row-based VLSI layouts. Our methods include accurate, linear-time approaches, often with sublinear time complexity for dynamic updating of estimates (e.g., for annealing placement). The new techniques offer advantages not only for early on-line wirelength estimation during top-down placement, but also for a posteriori estimation of routed wirelength given a final placement. In developing these new estimators, we have made several theoretical contributions. Notably, we have resolved the long-standing discrepancy between region-based and bounding box-based RSMT estimation techniques; this leads to new estimates that are functions of instance size n and aspect ratio AR.

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

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

Article Faster minimization of linear wirelength for global placement Share on Authors: Charles J. Alpert IBM Austin Research Laboratory, Austin, TX IBM Austin Research Laboratory, Austin, TXView Profile , Tony F. Chan UCLA Mathematics Department, Los Angeles, CA UCLA Mathematics Department, Los Angeles, CAView Profile , Dennis J.-H. Huang UCLA Computer Science Department, Los Angeles, CA UCLA Computer Science Department, Los Angeles, CAView Profile , Andrew B. Kahng UCLA Computer Science Department, Los Angeles, CA and Cadence Design Systems, Inc., San Jose, CA UCLA Computer Science Department, Los Angeles, CA and Cadence Design Systems, Inc., San Jose, CAView Profile , Igor L. Markov UCLA Mathematics Department, Los Angeles, CA UCLA Mathematics Department, Los Angeles, CAView Profile , Pep Mulet UCLA Mathematics Department, Los Angeles, CA UCLA Mathematics Department, Los Angeles, CAView Profile , Kenneth Yan UCLA Computer Science Department, Los Angeles, CA UCLA Computer Science Department, Los Angeles, CAView Profile Authors Info & Claims ISPD '97: Proceedings of the 1997 international symposium on Physical designApril 1997 Pages 4–11https://doi.org/10.1145/267665.267670Online:01 April 1997Publication History 17citation150DownloadsMetricsTotal Citations17Total Downloads150Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access