The co-design of neural network architectures and their target chiplet-based hardware systems presents a significant challenge due to the vast and combinatorial design space. Identifying solutions that are Pareto-optimal across competing objectives of task accuracy, system latency, and power consumption requires solutions beyond manual design and brute-force methods. This paper proposes a closed-loop chiplet-aware neural architecture search (Chiplet-NAS) framework to automate the exploration and discover hardware-optimized models for efficient AI inference on 2.5 D chiplet-based systems. The framework integrates a Tree-structured Parzen Estimator (TPE) for sampleefficient search with CLAIRE, a chiplet-based library and fast performance benchmarking tool, to provide direct hardware feedback on latency and energy consumption, along with accuracy optimization. The framework is evaluated by co-designing ResNet-based model architectures with chiplet based hardware systems. Compared to a baseline NAS that optimizes only on the task accuracy, our Chiplet-NAS achieves significant power and performance benefits at the iso-accuracy.

Global placement is essential for high-quality and efficient circuit placement for complex modern VLSI designs. Recent advancements, such as electrostatics-based analytic placement, have improved scalability and solution quality. This work demonstrates that using an accelerated FFT technique, AccFFT, for electric field computation significantly reduces runtime. Experimental results on standard benchmarks show significant improvements when incorporated into the ePlace-MS and Pplace-MS algorithms, e.g., a $5.78 \times$ speedup in FFT computation and a 32% total runtime improvement against ePlace-MS, with 1.0% reduction of scaled half-perimeter wirelength after detailed placement.

Many combinatorial optimization problems map naturally to Ising Hamiltonians, $H({\text{s}}) = - \sum\nolimits_{i,j} {{J_{ij}}} {s_i}{s_j} - \sum\nolimits_i {{h_i}} {s_i}$ , and CMOS ring-oscillator Ising machines solve them in microseconds at milliwatts [1] , [2] . Their key limitation is capacity : the number of spins one solver core can process in a single solve. Because each hardware spin represents one binary Ising variable, capacity directly sets the largest problem solvable in one shot. Our 28 nm five-core COBI chip solves a 45-spin all-to-all subproblem per core in 77.5 µ s, so larger instances require iterative decomposition. This shifts the bottleneck from analog solving to digital orchestration: a CPU-based decomposer needs ∼321 µ s/iter over PCIe, 4× the core solve time, leaving the solver idle 84.9% of the time. We instead co-locate an FPGA decomposer with the chip and derive sizing laws for the required parallelism, achieving 1.93× geomean speedup and > 40× energy reduction vs. an optimized C++ baseline.

Model-Based Diagnosis (MBD) identifies faulty components in complex systems by reasoning over a model of expected behavior and observations. Computing minimal-cardinality diagnoses—those involving the smallest number of faulty components—is NP-hard and becomes challenging for large systems due to the combinatorial growth of possible fault combinations. SAT-based formulations provide a compact representation of diagnostic constraints, allowing the diagnosis problem to be expressed as a combinatorial optimization problem. Since Ising Machines are well suited for solving such problems, this representation offers a natural pathway for mapping MBD to Ising-based computation. In this work, we present MIBID, a framework that maps SAT-based MBD formulations to an Ising model for computing minimal-cardinality diagnoses. The framework also incorporates hardware-aware pre-processing and decomposition to adapt the formulation to the capabilities of an Ising Machine. Experimental results on a manufactured Ising Machine show competitive performance with SAT-based methods for single minimal diagnoses. For multiple-diagnosis tasks, MIBID enumerates up to \(34\%\) and \(43.59\%\) more diagnoses than state-of-the-art under the weak and strong fault models, respectively, thereby providing broader coverage of plausible fault explanations.

Electromigration, a significant lifetime reliability concern in high-performance integrated circuits, is projected to grow even more important in future heterogeneously integrated systems that will service higher current loads. Today, EM checks are primarily based on rule-based methods, but these have known limitations. In recent years, there has been remarkable progress in enabling fast EM computations based on more accurate physics-based models, but such methods have not yet moved from research to practice. This paper overviews physics-based EM models, contrasts them with empirical models, and outlines several open problems that must be solved in order to enable accurate physics-based and circuit-aware EM analysis and optimization in future integrated systems.

The advent of heterogeneous integration (HI) places new demands on EDA tooling. Building large systems requires (1) methods for chiplet disaggregation that map the system to smaller chiplets, working in conjunction with system-technology co-optimization to determine the right design decisions that optimize computation and communication, together with the choice of substrate and chiplet technologies; (2) multiphysics and multiscale analyses that incorporate thermomechanical aspects into performance analysis, ranging from fast machine-learningdriven analyses in early stages to signoff-quality multiphysics-based analysis; (3) physical design techniques for placing and routing chiplets and embedded active/passive elements on and within the substrate, including the design of thermal and power delivery solutions; and (4) underlying infrastructure required to facilitate HI-based design, including the design and characterization of chiplet libraries and the establishment of data formats and standards. This paper overviews these issues and lays out a set of EDA needs for HI designs.

Device sizing is crucial for meeting performance specifications in operational transconductance amplifiers (OTAs), and this work proposes an automated sizing framework based on a transformer model. The approach first leverages the driving-point signal flow graph (DP-SFG) to map an OTA circuit and its specifications into transformer-friendly sequential data. A specialized tokenization approach is applied to the sequential data to expedite the training of the transformer on a diverse range of OTA topologies, under multiple specifications. Under specific performance constraints, the trained transformer model is used to accurately predict DP-SFG parameters in the inference phase. The predicted DP-SFG parameters are then translated to transistor sizes using a precomputed look-up table-based approach inspired by the 9m / I d methodology. In contrast to previous conventional or machine-learning-based methods, the proposed framework achieves significant improvements in both speed and computational efficiency by reducing the need for expensive SPICE simulations within the optimization loop; instead, almost all SPICE simulations are confined to the one-time training phase. The method is validated on a variety of unseen specifications, and the sizing solution demonstrates over 90% success in meeting specifications with just one SPICE simulation for validation, and 100% success with 3–5 additional SPICE simulations.

Traditional logic optimization relies on proxy metrics to approximate post-mapping performance and area, which may not correlate well with post-mapping delay and area. This paper explore a ground-truth-based optimization flow that directly incorporates the post-mapping delay and area during optimization using decision tree-based machine learning models. Results show high prediction accuracy and generalization to unseen designs,

Artificial intelligence has made a significant impact on fields like computer vision, Natural Language Processing (NLP), healthcare, and robotics. However, recent AI models, such as GPT-4 and LLaMAv3, demand significant number of computational resources, pushing monolithic chips to their technological and practical limits. 2.5D chiplet-based heterogeneous architectures have been proposed to address these technological and practical limits. While chiplet optimization for models like Convolutional Neural Networks (CNNs) is well-established, scaling this approach to accommodate diverse AI inference models with different computing primitives, data volumes, and different chiplet sizes is very challenging. A set of hardened IPs and chiplet libraries optimized for a broad range of AI applications is proposed in this work. We derive the set of chiplet configurations that are composable, scalable and reusable by employing an analytical framework trained on a diverse set of AI algorithms. Testing these set of library synthesized configurations on a different set of algorithms, we achieve a$1.99\times-3.99\times$improvement in non-recurring engineering (NRE) chiplet design costs, with minimal performance overhead compared to custom chiplet-based ASIC designs. Similar to soft IPs for SoC development, the library of chiplets improves flexibility, reusability, and efficiency for AI hardware designs.

Power delivery is a significant bottleneck in 2.5D heterogeneously integrated (HI) systems. A key part of the solution lies in the use of voltage regulators that distribute power to the chiplets with low transmission losses, thus ensuring supply levels that meet design specifications. Early HI systems have used manual approaches for placement, but as systems grow more complex and employ heterogeneous chiplets with nonuniform power distributions, the solution becomes nontrivial, and automation is essential. This paper addresses the problem of voltage regulator selection and placement for early-stage power planning in HI systems under DC estimates of chiplet loads. It demonstrates an HI technology using an active silicon interposer with embedded switched-capacitor voltage regulators (SCVRs). The problem is formulated as a 0–1 mixed integer linear program (MILP) and determines the optimal number, location, and types of SCVRs. A key part of the solution is using a macromodeling approach to control the size of the MILP. Experimental results across four test cases—covering both homogeneous and heterogeneous chiplet configurations—demonstrate that the method can efficiently find optimal solutions. The tested scenarios span a wide range of power densities, from 0.8 to 4.0W/mm2, and include total load currents ranging from 800A to 1200A. In all cases, the method achieves high accuracy (average error below 1.7%) and completes the optimization within practical runtimes, ranging from 18.8 to 46.1 minutes.

Machine learning (ML) is transforming electronic design automation (EDA), offering innovative solutions for designing and optimizing integrated circuits (ICs). However, the field faces significant challenges in standardization, accessibility, and reproducibility, limiting the impact of ML-driven EDA (ML EDA) research. To address these barriers, this paper presents a vision for an ML EDA Commons, a collaborative open ecosystem designed to unify the community and drive progress through establishing standards, shared resources, and stakeholder-based governance. The ML EDA Commons focuses on three objectives: (1) Maturing existing EDA infrastructure to support ML EDA research; (2) Establishing standards for benchmarks, metrics, and data quality and formats for consistent evaluation via governance that includes key stakeholders; and (3) Improving accessibility and reproducibility by providing open datasets, tools, models, and workflows with cloud computing resources, to lower barriers to ML EDA research and promote robust research practices via artifact evaluations, canonical evaluators, and integration pipelines. Inspired by successes of ML and MLCommons, the ML EDA Commons aims to catalyze transparency and sustainability in ML EDA research.

Today, NP-complete or NP-hard combinatorial problems are often solved on classical computers, using heuristics with no optimality guarantees or approximation algorithms with loose optimality bounds. Ising computation provides a new paradigm for solving these problems using networks of coupled oscillators. In contrast with traditional Ising machines that use supercooled chips, recent approaches have proposed the use of coupled CMOS ring oscillators, reducing the power dissipation of these systems by several orders of magnitude. This talk will overview the Ising model, discuss the challenges of building CMOS Ising machines, including issues related to layout and timing, and point to directions that are helping deploy these methods to solve ever-larger combinatorial problems.

Beyond edge devicescan function off the power grid and without batteries, making them suitable for deployment in hard-to-reach environments. As the energy budget is extremely tight, energy-hungry long-distance communication required for offloading computation or reporting results to a server becomes a significant limitation. Based on the observation that the energy required for communication decreases with shorter distances, this paper makes a case for the deployment ofsecure beyond edge miniservers. These are strategically positioned, lightweight local servers designed to support beyond edge devices without compromising the privacy of sensitive information. We demonstrate that even for relatively small scale representative computations – which are more likely to fit into the tight power budget of a beyond edge device for local processing – deploying a beyond edge miniserver can lead to higher performance. To this end, we consider representative deployment scenarios of practical importance, including but not limited to agricultural systems or building structures, where beyond edge miniservers enable highly energy-efficient real-time data processing.

The layout area and power consumption of a charge-scaling digital-to-analog converter (DAC) is typically dominated by the capacitor array. For a binary-weighted DAC, since the number of unit capacitors in the array increases exponentially with the number of bits, minimizing the size of the unit capacitor is crucial for controlling the layout area. A split DAC uses many fewer unit capacitors than the binary-weighted DAC, but requires the use of noninteger multiples of a unit capacitance; the choice of unit capacitor remains an important consideration. Smaller capacitors can be susceptible to larger amounts of noise and process mismatch, and can also be affected by mismatch in the parasitics of routing wires that connect the capacitors in the array: the latter is particularly significant in FinFET nodes. Together, these factors can degrade critical DAC performance metrics unless the unit capacitor is sufficiently large. This work proposes a systematic approach for selecting the unit capacitance value in both binary-weighted and split capacitor arrays for charge-scaling DACs. The proposed method selects a value that optimizes the nonlinearity metrics of a DAC, accounting for multiple factors that contribute to mismatch, flicker noise, and thermal noise. Our results demonstrate that by using a systematic methodology to size the unit capacitor, it is possible to overcome shifts due to process variation and noise for 6-bit to 14-bit DACs. Particularly for higher-resolution DACs, it is seen that the minimum unit capacitor value for binary-weighted DACs is lower than for split DACs, but the former incurs much larger area costs since it contains a significantly larger number of unit capacitors.

Today’s performance analysis frameworks for deep learning accelerators suffer from two significant limitations. First, although modern convolutional neural networks (CNNs) consist of many types of layers other than convolution, especially during training, these frameworks largely focus on convolution layers only. Second, these frameworks are generally targeted towards inference and lack support for training operations. This work proposes a novel open-source performance analysis framework, SimDIT, for general ASIC-based systolic hardware accelerator platforms. The modeling effort of SimDIT comprehensively covers convolution and non-convolution operations of both CNN inference and training on a highly parameterizable hardware substrate. SimDIT is integrated with a backend silicon implementation flow and provides detailed end-to-end performance statistics (i.e., data access cost, cycle counts, energy, and power) for executing CNN inference and training workloads. SimDIT-enabled performance analysis reveals that on a 64×64 processing array, non-convolution operations constitute 59.5% of total runtime for ResNet-50 training workload. In addition, by optimally distributing available off-chip DRAM bandwidth and on-chip SRAM resources, SimDIT achieves 18× performance improvement over a generic static resource allocation for ResNet-50 inference.

This work presents an analytical approach for analyzing electromigration (EM) in modern technologies that use copper dual damascene (Cu DD) interconnects. In these technologies, due to design rule and methodology constraints, wires are typically laid out unidirectionally in each metal layer; since EM in Cu DD interconnects do not cross layer boundaries, the problem reduces to one of analyzing EM in multisegment interconnect lines. In contrast with traditional empirical methodologies, our approach is based on physics-based modeling, directly solving the differential equations that model EM-induced stress. This article places a focus on interconnect lines, for reasons described above, and introduces the new concept of boundary reflections of stress flux that ascribes a physical (wave-like) analogy to the transient stress behavior in a finite multisegment line. This framework is used to derive analytical expressions of transient EM stress for lines with any number of segments, which can also be tailored to include the appropriate number of terms for any desired level of accuracy. The approach is applied to both the nucleation phase and the postvoiding phase on large power grid benchmarks. These experiments demonstrate excellent accuracy as compared to accurate numerical solution, as well as linear complexity with the number of segments for evaluating stress at a specified point and time.

Building upon recent advances in analog electronic design automation (EDA), this paper discusses directions for reinforcing the connection between design and EDA, in order to develop solutions that are meaningful to designers. Two aspects, both related to bridging the gap between EDA and designers, are highlighted. The first discusses the use of test structures to generate meaningful characterized data to aid design automation, specifically understanding the impact of random, correlated, and systematic variations on the design of matched structures. Results on a recent test chip that analyzes these variations and their impact on EDA design choices will be presented. The second illustrates a design testcase that applies analog EDA techniques, using the ALIGN layout engine, to design an RF MIMO receiver, and describes how this experience has helped both in advancing the state of analog EDA and in building circuits with enhanced designer productivity.

Due to the inherent error-tolerance of machine learning (ML) algorithms, many parts of the inference computation can be performed with adequate accuracy and low power under relatively low precision. Early approaches have used digital approximate computing methods to explore this space. Recent approaches using analog-based operations achieve power-efficient computation at moderate precision. This work proposes a mixed-signal optimization (MiSO) approach that optimally blends analog and digital computation for ML inference. Based on accuracy and power models, an integer linear programming formulation is used to optimize design metrics of analog/digital implementations. The efficacy of the method is demonstrated on multiple ML architectures.

Computing-in-memory (CIM) architectures that perform logic gate operations directly within memory arrays, in-situ, are particularly effective in addressing memory-induced performance bottlenecks. When paired with nonvolatile memory, energy efficiency in performing bulk bitwise logic operations can reach unprecedented levels. However, unlocking this potential is not possible if functional correctness is compromised. In this paper we present a CIM-specific class of functional errors termed gate flips, where parametric variations make a logic gate behave as another. Through detailed functional and electrical characterization we demonstrate that gate flips stem from a significant subclass of write errors. Accordingly, we introduce an abstract model to enable efficient functional reliability assessment and to guide design decisions in forming universal CIM gate libraries. We also evaluate the impact on the end accuracy of computation using representative benchmarks.

Decades of progress in energy-efficient and low-power design have successfully reduced the operational carbon footprint in the semiconductor industry. However, this has led to increased embodied emissions, arising from design, manufacturing, and packaging. While existing research has developed tools to analyze embodied carbon for traditional monolithic systems, these tools do not apply to near-mainstream heterogeneous integration (HI) technologies. HI systems offer significant potential for sustainable computing by minimizing carbon emissions through two key strategies: “reducing” computation by “reusing” pre-designed chiplet IP blocks and adopting hierarchical approaches to system design. The reuse of chiplets across multiple designs, even spanning multiple generations of ICs, can substantially reduce carbon emissions throughout the lifespan. This paper introduces ECO-CHIP, a carbon analysis tool designed to assess the potential of HI systems toward sustainable computing by considering scaling, chip let, and packaging yields, design complexity, and even overheads associated with advanced packaging techniques. Experimental results from ECO-CHIP demonstrate that HI can reduce embodied carbon emissions by up to 30% compared to traditional monolithic systems. ECO-CHIP is integrated with other chiplet simulators and is applied to chiplet disaggregation considering other metrics such as power, area, and cost. ECO-CHIP suggests that HI can pave the way for sustainable computing practices.

The electronic design automation (EDA) community has recently begun recognizing the potential of generative artificial intelligence (AI) in chip design. However, its full potential is not fully exploited due to the limited availability of publicly accessible datasets crucial for advancing research in EDA. This paper highlights the dual role of generative AI; in particular, it showcases (i) BeGAN, the use of a generative AI strategy to create thousands of realistic benchmarks for power grid synthesis and analysis to advance power-related research, and (ii) EDA Corpus---an expert-curated and generative AI-enhanced dataset to serve research and development of EDA tool assistants. These two case studies emphasize the ability of generative methods to create and utilize datasets to advance research and lower the barriers to entry in EDA.

In FinFET nodes, high transistor power densities in a power amplifier (PA) lead to device self-heating (SH), degrading performance. This study investigates the impact of SH in large PA FinFET arrays. An encoder-decoder network, together with a long short-term memory model, is used for rapid and accurate thermal analysis. This fast analyzer helps better explore design optimizations than conventional computationally-expensive thermal solvers. The work explores methods for mitigating thermal effects in PAs by inserting dummy transistors within the array of active FinFET devices, and shows the impact of duty cycle and frequency on PA performance.

Processing in memory (PiM) represents a promising computing paradigm to enhance performance of numerous dataintensive applications. Variants performing computing directly in emerging nonvolatile memories can deliver very high energy efficiency. PiM architectures directly inherit the vulnerabilities of the underlying memory substrates, but they also are subject to errors due to the computation in place. Numerous well-established error correcting codes (ECC) for memory exist, and are also considered in the PiM context, however, they typically ignore errors that occur throughout computation. In this paper we revisit the error correction design space for nonvolatile PiM, considering both storage/memory and computation-induced errors, surveying several self-checking and homomorphic approaches. We propose several solutions and analyze their complex performance-area-coverage trade-off, using three representative nonvolatile PiM technologies. All of these solutions guarantee single error correction for both, bulk bitwise computations and ordinary memory/storage errors.

Dynamic graph neural networks (DGNNs) play a crucial role in applications that require inferencing on graph-structured data, where the connectivity and features of the graph evolve over time. The proposed platform integrates graph neural network (GNN) and recurrent neural network (RNN) components of DGNNs, providing a unified platform that captures spatial and temporal information. Novel contributions include optimized cache reuse, a novel caching policy, and efficient GNN-RNN pipelining. Average energy efficiency gains of 8393X, 183x, and 87X -- 10X, and inference speedups of 1796X, 77X, and 21x -- 2.4X, over Intel Xeon Gold CPU, NVIDIA V100 GPU, and prior approaches, respectively, are demonstrated across multiple graph datasets and multiple DGNNs.

Traditional electronic design automation (EDA) techniques struggle to fulfill the stringent efficiency and quick turnaround demands of complex integrated systems. Machine learning (ML) strategies for EDA (“ML EDA”) are pivotal in transforming EDA to address these challenges. However, they encounter significant obstacles due to inadequate infrastructure, ranging from datasets to software interfaces. This paper demonstrates a software infrastructure for ML EDA built on two key technologies: (i) OpenROAD’s Python APIs, and (ii) NVIDIA’s CircuitOps, an EDA data representation format tailored for ML, facilitating ML EDA applications. The paper illustrates three ML EDA examples that utilize the established OpenROAD and CircuitOps infrastructure.

Performance modeling is a key bottleneck for analog design automation. Although machine learning-based models have advanced the state-of-the-art, they have so far suffered from huge data preparation cost, very limited reusability, and inadequate accuracy for large circuits. We introduce ML-based macro-modeling techniques to mitigate these problems for linear analog ICs and ADC/DACs. The modeling techniques are based on macro-models, which can be assembled to evaluate circuit system performance, and more appealingly can be reused across different circuit topologies. On representative testcases, our method achieves more than$1700\times $speedup for data preparation and remarkably smaller model errors compared to recent ML approaches. It also attains$3600\times $acceleration over SPICE simulation with very small errors and reduces data preparation time for an ADC design from 40 days to 9.6 h.

The design of active array structures in analog circuits requires careful matching to minimize the impact of variations. This work presents a constructive approach for building these arrays to directly incorporate shifts due to process variations, considering systematic first-order and second order gradients; to account for systematic layout effects, including parasitic mismatch and layout-dependent effects due to stress; and to ensure that the resulting layout delivers high performance. The proposed algorithms are targeted to FinFET technologies and are validated for multiple analog blocks in a commercial 12nm FinFET process. The layouts generated by the proposed method are demonstrated to provide better matching and performance than prior methods.

Due to the unavailability of routing information in design stages prior to detailed routing (DR), the tasks of timing prediction and optimization pose major challenges. Inaccurate timing prediction wastes design effort, hurts circuit performance, and may lead to design failure. This work focuses on timing prediction after clock tree synthesis and placement legalization, which is the earliest opportunity to time and optimize a “complete” netlist. The article first documents that having “oracle knowledge” of the final post-DR parasitics enables post-global routing (GR) optimization to produce improved final timing outcomes. To bridge the gap between GR-based parasitic and timing estimation and post-DR results during post-GR optimization , machine learning (ML)-based models are proposed, including the use of features for macro blockages for accurate predictions for designs with macros. Based on a set of experimental evaluations, it is demonstrated that these models show higher accuracy than GR-based timing estimation. When used during post-GR optimization, the ML-based models show demonstrable improvements in post-DR circuit performance. The methodology is applied to two different tool flows—OpenROAD and a commercial tool flow—and results on an open-source 45nm bulk and a commercial 12nm FinFET enablement show improvements in post-DR timing slack metrics without increasing congestion. The models are demonstrated to be generalizable to designs generated under different clock period constraints and are robust to training data with small levels of noise.

Parameterizable machine learning (ML) accelerators are the product of recent breakthroughs in ML. To fully enable their design space exploration (DSE), we propose a physical-design-driven, learning-based prediction framework for hardware-accelerated deep neural network (DNN) and non-DNN ML algorithms. It adopts a unified approach that combines power, performance, and area (PPA) analysis with frontend performance simulation, thereby achieving a realistic estimation of both backend PPA and system metrics such as runtime and energy. In addition, our framework includes a fully automated DSE technique, which optimizes backend and system metrics through an automated search of architectural and backend parameters. Experimental studies show that our approach consistently predicts backend PPA and system metrics with an average 7% or less prediction error for the ASIC implementation of two deep learning accelerator platforms, VTA and VeriGOOD-ML, in both a commercial 12 nm process and a research-oriented 45 nm process.

Deep learning (DL) accelerators are optimized for standard convolution. However, lightweight convolutional neural networks (CNNs) use depthwise convolution (DwC) in key layers, and the structural difference between DwC and standard convolution leads to significant performance bottleneck in executing lightweight CNNs on such platforms. This work reuses the fast general matrix-vector multiplication (GEMM) core of DL accelerators by mapping DwC to channel-wise parallel matrix-vector multiplications. An analytical framework is developed to guide pre-RTL hardware choices, and new hardware modules and software support are developed for end-to-end evaluation of the solution. This GEMM-based DwC execution strategy offers substantial performance gains for lightweight CNNs: 7× speedup and 1.8× lower off-chip communication for MobileNet-v1 over a conventional DL accelerator, and 74× speedup over a CPU, and even 1.4× speedup over a power-hungry GPU.

Recent advances in auto-generating analog and mixed-signal (AMS) circuits use standard digital tool flows to compose AMS circuits from a combination of digital standard cells and a set of auxiliary cells (auxcells). Until now, generating auxcell layouts for each new PDK was the last manual step in the flow for auto-generating AMS components, which limited the available auxcells and reduced the optimality of the auto-generated AMS designs. To solve this, we propose AuxcellGen, a framework to auto-generate auxcell layouts and performance models. Aux-cellGen generates a parasitic-aware auxcell performance model using a neural network (NN), auto-sizes and optimizes auxcell schematics for a given design target, and auto-generates auxcell layouts. The framework is demonstrated by auto-generating tristate buffer auxcells for PLLs and sense-amplifier auxcells for SRAM across a range of user specifications that are compatible with standard cell and memory bitcell pitch.

The layout area and power consumption of a binary-weighted capacitive digital-to-analog converter (DAC) increases exponentially with the number of bits. To meet linearity targets, unit capacitors should be large enough to limit errors caused by various sources of noise and those due to mismatch. This work proposes a systematic approach for minimizing the unit capacitance value that optimizes the linearity metrics of a DAC, accounting for multiple factors that contribute to mismatch, as well as the impact of flicker and thermal noise.

ML accelerators have largely focused on building general platforms for deep neural networks (DNNs), but less so on shallow machine learning (SML) algorithms. This paper proposes Axiline, a compact, configurable, template-based generator for SML hardware acceleration. Axiline identifies computational kernels as templates that are common to these algorithms and builds a pipelined accelerator for efficient execution. The dataflow graphs of individual ML instances, with different data dimensions, are mapped to the pipeline stages and then optimized by customized algorithms. The approach generates energy-efficient hardware for training and inference of various ML algorithms, as demonstrated with post-layout FPGA and ASIC results.

The analysis of transient stress buildup in on-chip interconnects due to electromigration (EM) requires the solution of partial differential equations (PDEs) with appropriate boundary conditions, but prior approaches have been computationally expensive. This paper uses a stress-electrical equivalence to map the solution of the system of PDEs for a general multisegment interconnect to an RC network. For tree structures, this system is solved in linear time in the frequency domain using model order reduction (MOR) techniques. We present two MOR approaches: one that is not guaranteed to provide a stable approximant due to the presence of the mass-conservation equation, but empirically does so for a large fraction of testcases; and another that is guaranteed-stable. To achieve a guaranteed-stable solution, the approach approximates the RC circuit in a Krylov space and captures the impact of mass conservation in the form of a mass conservation excitation. However, the latter is observed to be slightly less accurate than the first approach when it does provide a solution. The method demonstrates excellent accuracy against a commercial numerical solver, and is scalable, solving transient EM analysis problems on large power grid interconnect benchmarks.

Processing-in-Memory (PIM) architectures have gained popularity due to their ability to alleviate the memory wall by performing large numbers of operations within the memory itself. On top of this, nonvolatile memory (NVM) technologies offer highly energy-efficient operations, rendering processing in NVM especially promising. Unfortunately, a major drawback is that NVM has limited endurance. Even when used for standard memory, nonvolatile technologies face limited lifetimes, which is exacerbated by imbalanced usage of memory cells. PIM significantly increases the number of operations the memory is required to perform, making the problem much worse. In this work, we quantitatively analyze the impact of PIM applications on endurance considering representative memory technologies. Our findings indicate that limited endurance can easily block the performance and energy efficiency potential of PIM architectures. Even the best known technologies of today can fall short of meeting practical lifetime expectations. This highlights the importance of research efforts to improve endurance especially at the device technology level. Our study represents the first step in characterizing the very demanding endurance needs of PIM applications to derive a detailed technology level design specification.

Graph neural networks (GNN) are vital for analytics on real-world problems with graph models. This work develops a multicore GNN training accelerator and develops multicore-specific optimizations for superior performance. It uses enhanced multicore-specific dynamic caching to circumvent the costs of irregular DRAM access patterns of graph-structured data. A novel feature vector segmentation approach is used to maximize on-chip data reuse with high on-chip computation per memory access, reducing data access latency, using a machine learning model for optimal performance. The work presents a major advance over prior FPGA/ASIC GNN accelerators by handling significantly larger datasets (with up to 8.6M vertices) on a variety of GNN models. On average, training speedup of 17× and energy efficiency improvement of 322× is achieved over DGL on a GPU; a speedup of 14× with 268× lower energy is shown over GPU-based GNNAdvisor; and 11× and 24× speedups are obtained over ASIC-based Rubik and FPGA-based GraphACT.

Traditional approaches to analyzing electromigration (EM) in on-chip interconnects are largely driven by semi-empirical models. However, such methods are inexact for the typical multisegment lines that are found in modern integrated circuits. This paper overviews recent advances in analyzing EM in on-chip interconnect structures based on physics-based models that use partial differential equations, with appropriate boundary conditions, to capture the impact of electron-wind and back-stress forces within an interconnect, across multiple wire segments. Methods for both steady-state and transient analysis are presented, highlighting approaches that can solve these problems with a computation time that is linear in the number of wire segments in the interconnect.

The ALIGN (Analog Layout, Intelligently Generated from Netlists) project [1, 2] is a joint university-industry effort to push the envelope of automated analog layout through a systematic new approach, novel algorithms, and open-source software [3]. Analog automation research has been active for several decades, but has not found widespread acceptance due to its general inability to meet the needs of the design community. Therefore, unlike digital design, which has a rich history of automation and extensive deployment of design tools, analog design is largely unautomated.

Process variations and the effect of interconnect parasitics can cause significant perturbations in the performance metrics of capacitive digital-to-analog converters (DACs). This article develops fast constructive procedures for common-centroid placement and routing for binary-weighted and split capacitor array topologies of charge-sharing DACs. Our approach particularly targets FinFET technologies with high wire and via parasitics: in these technology nodes, we show that the switching speed of the capacitor array, as measured by the 3-dB frequency, can be severely degraded by these parasitics, and develop techniques to place and route the capacitor array, for both binary-weighted and split DACs, to optimize the switching speed. A balance between 3-dB frequency and DAC INL/DNL is shown by trading off via counts with dispersion. The approach delivers high-quality results with low runtimes.

Analog designs consist of multiple hierarchical functional blocks. Each block can be built using one of several design topologies, where the choice of topology is based on circuit performance requirements. A major challenge in automating analog design is in the identification of these functional blocks, which enables the creation of hierarchical netlist representations. This can facilitate a variety of design automation tasks, such as circuit layout optimization, because the layout is dictated by constraints at each level, such as symmetry requirements, that depend on the topology of the hierarchical block. Traditional graph-based methods find it hard to automatically identify the large number of structural variants of each block. To overcome this limitation, this article leverages recent advances in graph neural networks (GNNs). A variety of GNN strategies is used to identify netlist elements for circuit functional blocks at higher levels of the design hierarchy, where numerous design variants are possible. At lower levels of hierarchy, where the degrees of freedom in circuit topology is limited, structures are identified using graph-based algorithms. The proposed hierarchical recognition scheme enables the identification of layout constraints, such as symmetry and matching, which enable high-quality hierarchical layouts. This method is scalable across a wide range of analog designs. An experimental evaluation shows a high degree of accuracy over a wide range of analog designs, identifying functional blocks, such as low-noise amplifiers, operational transconductance amplifiers, mixers, oscillators, and band-pass filters, in larger circuits.

Graph neural networks (GNNs) analysis engines are vital for real-world problems that use large graph models. Challenges for a GNN hardware platform include the ability to 1) host a variety of GNNs; 2) handle high sparsity in input vertex feature vectors and the graph adjacency matrix and the accompanying random memory access patterns; and 3) maintain load-balanced computation in the face of uneven workloads, induced by high sparsity and power-law vertex degree distributions. This article proposes GNNIE, an accelerator designed to run a broad range of GNNs. It tackles workload imbalance by 1) splitting vertex feature operands into blocks; 2) reordering and redistributing computations; and 3) using a novel flexible MAC architecture. It adopts a graph-specific, degree-aware caching policy that is well suited to real-world graph characteristics. The policy enhances on-chip data reuse and avoids random memory access to DRAM. GNNIE achieves average speedups of$7197\times $over a CPU and$17.81\times $over a GPU over multiple datasets on graph attention networks (GATs), graph convolutional networks (GCNs), GraphSAGE, GINConv, and DiffPool. Compared to prior approaches, GNNIE achieves an average speedup of$5\times $over HyGCN (which cannot implement GATs) for GCN, GraphSAGE, and GINConv. GNNIE achieves an average speedup of$1.3\times $over AWB-GCN (which runs only GCNs), despite using$3.4\times $fewer processing units.

Power delivery network (PDN) analysis and thermal analysis are computationally expensive tasks that are essential for successful integrated circuit (IC) design. Algorithmically, both these analyses have similar computational structure and complexity as they involve the solution to a partial differential equation of the same form. This article converts these analyses into image-to-image and sequence-to-sequence translation tasks, which allows leveraging a class of machine learning models with an encoder-decoder–based generative (EDGe) architecture to address the time-intensive nature of these tasks. For PDN analysis, we propose two networks: (i) IREDGe: a full-chip static and dynamic IR drop predictor and (ii) EMEDGe: electromigration (EM) hotspot classifier based on input power, power grid distribution, and power pad distribution patterns. For thermal analysis, we propose ThermEDGe, a full-chip static and dynamic temperature estimator based on input power distribution patterns for thermal analysis. These networks are transferable across designs synthesized within the same technology and packing solution. The networks predict on-chip IR drop, EM hotspot locations, and temperature in milliseconds with negligibly small errors against commercial tools requiring several hours.

Well island generation and well tap placement is an important problem in analog/mixed-signal (AMS) circuits. Well taps can only prevent latchups within a certain radius of influence within a well island, and hence must be appropriately inserted to cover all devices. However, existing automated AMS layout paradigms typically defer the insertion of well taps and creation of well islands to a post-processing step after placement. This alters the placement, resulting in increased area and wire length, as well as circuit performance degradation. Therefore, there is a strong need for a solution that generates well islands and inserts well taps during placement so the placer can account for well overheads in optimizing placement metrics. In this work, we propose a modular solution using a graph-based optimization scheme that can be used within multiple placement paradigms with minimal intrusion. We demonstrate the integration of this scheme into stochastic, analytical, and designer-driven row-based placement. The method is demonstrated in advanced FinFET technologies. Layouts generated using this scheme show better area, wire length, and performance metrics at the cost of a marginal runtime degradation when compared to the post-processing approach. Using our scheme, there is an average improvement of 3% and 4% and a maximum improvement of 23% and 11% in area and wirelength, respectively, of layouts of various classes of AMS circuits at the cost of 17% average and 29% maximum increase in total runtime.

Analog IC performance has a strong dependence on interconnect RC parasitics, which are significantly affected by wire sizes in recent technologies, where minimum-width wires have high resistance. However, performance-driven wire sizing for analog ICs has received very little research attention. In order to fill this void, we develop several techniques to facilitate an end-to-end automatic wire sizing approach. They include a circuit performance model based on customized graph neural network (GNN) and two optimization techniques: one using Bayesian optimization accelerated by the GNN model, and the other based on TensorFlow training. Experimental results show that our technique can achieve 11% circuit performance improvement or 8.7× speedup compared to a conventional Bayesian optimization method.

This paper presents an overview of common-centroid (CC) layout styles, used in analog designs to overcome the impact of systematic variations. CC layouts must be carefully engineered to minimize the impact of mismatch. Algorithms for CC layout must be aware of routing parasitics, layout-dependent effects (for active devices), and the performance impact of layout choices. The optimal CC layout further depends on factors such as the choice of the unit device and the relative impact of uncorrelated and systematic variations. The paper also examines scenarios where non-CC layouts may be preferable to CC layouts.

Graph neural networks (GNN) inferencing involves weighting vertex feature vectors, followed by aggregating weighted vectors over a vertex neighborhood. High and variable sparsity in the input vertex feature vectors, and high sparsity and power-law degree distributions in the adjacency matrix, can lead to (a) unbalanced loads and (b) inefficient random memory accesses. GNNIE ensures load-balancing by splitting features into blocks, proposing a flexible MAC architecture, and employing load (re)distribution. GNNIE's novel caching scheme bypasses the high costs of random DRAM accesses. GNNIE shows high speedups over CPUs/GPUs; it is faster and runs a broader range of GNNs than existing accelerators.

An analog/mixed-signal designer typically performs circuit optimization, involving intensive SPICE simulations, on a schematic netlist and then sends the optimized netlist to layout. During the layout phase, it is vital to maintain symmetry requirements to avoid performance degradation due to mismatch: these constraints are usually specified using user input or by invoking an external tool. Moreover, to achieve high performance, the layout must avoid large interconnect parasitics on critical nets. Prior works that optimize parasitics during placement work with coarse metrics such as the half-perimeter wire length, but these metrics do not appropriately emphasize performance-critical nets. The novel charge flow (CF) formulation in this work addresses both symmetry detection and parasitic optimization. By leveraging schematic-level simulations, which are available “for free” from the circuit optimization step, the approach (a) alters the objective function to emphasize the reduction of parasitics on performance-critical nets, and (b) identifies symmetric elements/element groups. The effectiveness of the CF-based approach is demonstrated on a variety of circuits within a stochastic placement engine.

The accuracy and linearity of capacitive digital-to-analog converters (DACs) depend on precise capacitor ratios, but these ratios are perturbed by process variations and parasitics. This paper develops fast constructive procedures for common-centroid placement and routing for binary-weighted capacitors in charge-sharing DACs. Parasitics also degrade the switching speed of a capacitor array, particularly in FinFET nodes with severe wire/via resistances. To overcome this, the capacitor array is placed and routed to optimize switching speed, measured by the 3dB frequency. A balance between 3dB frequency and DAC INL/DNL is shown by trading off via counts with dispersion. The approach delivers high-quality results with low runtimes.

Analytical techniques have long been a prevailing approach to digital IC placement due to their advantage in handling large-sized problems. Recently, they have been adopted for analog IC placement, an area where prior methods were mostly based on simulated annealing. However, a comparative study between the two classes of approaches is lacking. Moreover, the effectiveness of different analytical techniques is not clear. This work attempts to shed light on both issues by studying existing methods and developing a new analytical technique. Since prior analytical methods have not addressed circuit performance, a critical concern for automated analog layout, this work also extends the new analytical placer for performance-driven placement. Experiments on various test circuits show that for a conventional performance-oblivious formulation, the proposed analytical technique achieves 55x speedup and 12% wirelength reduction compared to simulated annealing. For performance-driven placement, the proposed technique outperforms simulated annealing in terms of circuit performance, area, and runtime. Moreover, the proposed technique generally provides better solution quality than an alternative analytical technique.

As integrated circuit technologies move below 10 nm, Electromigration (EM) has become an issue of great concern for the longterm reliability due to the stricter performance, thermal and power requirements. The problem of EM becomes even more pronounced in power grids due to the large unidirectional currents flowing in these structures. The attention for EM analysis during the past years has been drawn to accurate physics-based models describing the interplay between the electron wind force and the back stress force, in a single Partial Differential Equation (PDE) involving wire stress. In this paper, we present a fast semi-analytical approach for the solution of the stress PDE at discrete spatial points in multi-segment lines of power grids, which allows the analytical calculation of EM stress independently at any time in these lines. Our method exploits the specific form of the discrete stress coefficient matrix whose eigenvalues and eigenvectors are known beforehand. Thus, a closed-form equation can be constructed with almost linear time complexity without the need of time discretization. This closed-form equation can be subsequently used at any given time in transient stress analysis. Our experimental results, using the industrial IBM power grid benchmarks, demonstrate that our method has excellent accuracy compared to the industrial tool COMSOL while being orders of magnitude times faster.

Well island generation and well tap placement pose an important challenge in automated analog/mixed-signal (AMS) layout. Well taps prevent latchup within a radius of influence in a well island, and must cover all devices. Automated AMS layout flows typically perform well island generation and tap insertion as a postprocessing step after placement. However, this step is intrusive and potentially alters the placement, resulting in increased area, wire length, and performance degradation. This work develops a graph-based optimization that integrates well island generation, well tap insertion, and placement. Its efficacy is demonstrated within a stochastic placement engine. Experimental results show that this approach generates better area, wire length and performance metrics than traditional methods, at the cost of a marginal runtime degradation.

Power delivery network (PDN) design is a nontrivial, time-intensive, and iterative task. Correct PDN design must consider power bumps, currents, blockages, and signal congestion distribution patterns. This work proposes a machine learning-based methodology that employs a set of predefined PDN templates. At the floorplan stage, coarse estimates of current, congestion, macro/blockages, and C4 bump distributions are used to synthesize a grid for early design. At the placement stage, the grid is incrementally refined based on more accurate and fine-grained distributions of current and congestion. At each stage, a convolutional neural network (CNN) selects an appropriate PDN template for each region on the chip, building a safe-by-construction PDN that meets IR drop and electromigration (EM) specifications. The CNN is initially trained using a large synthetically created dataset, following which transfer learning is leveraged to bridge the gap between real-circuit data (with a limited dataset size) and synthetically generated data. On average, the optimization of the PDN frees thousands of routing tracks in congestion-critical regions, when compared to a globally uniform PDN, while staying within the IR drop and EM limits.

Beyond-edge devices can operate outside the reach of the power grid and without batteries. Such devices can be deployed in large numbers in regions that are difficult to access. Using machine learning, these devices can solve complex problems and relay valuable information back to a host. Many such devices deployed in low Earth orbit can even be used as nanosatellites. Due to the harsh and unpredictable nature of the environment, these devices must be highly energy-efficient, be capable of operating intermittently over a wide temperature range, and be tolerant of radiation. Here, we propose a non-volatile processing-in-memory architecture that is extremely energy-efficient, supports minimal overhead checkpointing for intermittent computing, can operate in a wide range of temperatures, and has a natural resilience to radiation.

Computationally expensive temperature and power grid analyses are required during the design cycle to guide IC design. This paper employs encoder-decoder based generative (EDGe) networks to map these analyses to fast and accurate image-to-image and sequence-to-sequence translation tasks. The network takes a power map as input and outputs the temperature or IR drop map. We propose two networks: (i) ThermEDGe: a static and dynamic full-chip temperature estimator and (ii) IREDGe: a full-chip static IR drop predictor based on input power, power grid distribution, and power pad distribution patterns. The models are design-independent and must be trained just once for a particular technology and packaging solution. ThermEDGe and IREDGe are demonstrated to rapidly predict on-chip temperature and IR drop contours in milliseconds (in contrast with commercial tools that require several hours or more) and provide an average error of 0.6% and 0.008% respectively.

Placement algorithms for analog circuits explore numerous layout configurations in their iterative search. To steer these engines towards layouts that meet the electrical constraints on the design, this work develops a fast feasibility predictor to guide the layout engine. The flow first discerns rough bounds on layout parasitics and prunes the feature space. Next, a Latin hypercube sampling technique is used to sample the reduced search space, and the labeled samples are classified by a linear support vector machine (SVM). If necessary, a denser sample set is used for the SVM, or if the constraints are found to be nonlinear, a multilayer perceptron (MLP) is employed. The resulting machine learning model demonstrated to rapidly evaluate candidate placements in a placer, and is used to build layouts for several analog blocks.

Scheduling computations in each layer of a convolutional neural network on a deep learning (DL) accelerator involves a large number of choices, each of which involves a different set of memory reuse and memory access patterns. Since memory transactions are the primary bottleneck in DL acceleration, these choices can strongly impact the energy and throughput of the accelerator. This work proposes an optimization framework, DeepOpt, for general ASIC-based systolic hardware accelerators for layer-specific and hardware-specific scheduling strategy for each layer of a CNN to optimize energy and latency. Optimal hardware allocation significantly reduces execution cost as compared to generic static hardware resource allocation, e.g., improvements of up to 50x in the energy-delay product for VGG-16 and 41x for GoogleNet-v1.

Traditional methodologies for analyzing electromigration (EM) in VLSI circuits first filter immortal wires using Blech’s criterion, and then perform detailed EM analysis on the remaining wires. However, Blech’s criterion was designed for two-terminal wires and does not extend to general structures. This paper demonstrates a first-principles-based solution technique for determining the steady-state stress at all the nodes of a general interconnect structure, and develops an immortality test whose complexity is linear in the number of edges of an interconnect structure. The proposed model is applied to a variety of structures. The method is shown to match well with results from numerical solvers, to be scalable to large structures.

Vectored IR drop analysis is a critical step in chip signoff that checks the power integrity of an on-chip power delivery network. Due to the prohibitive runtimes of dynamic IR drop analysis, the large number of test patterns must be whittled down to a small subset of worst-case IR vectors. Unlike the traditional slow heuristic method that select a few vectors with incomplete coverage, MAVIREC uses machine learning techniques -- 3D convolutions and regression-like layers -- for accurately recommending a larger subset of test patterns that exercise worst-case scenarios. In under 30 minutes, MAVIREC profiles 100K-cycle vectors and provides better coverage than a state-of-the-art industrial flow. Further, MAVIREC's IR drop predictor shows 10x speedup with under 4mV RMSE relative to an industrial flow.

Hierarchical analog layout generators proceed from leaf cells (“primitives”) to progressively larger blocks that are placed and routed. The quality of primitive cell layout is critical for design performance. This paper proposes a methodology that defines and optimizes the performance metrics of primitives during leaf cell layout. It incorporates layout parasitics and layout-dependent effects, providing a set of optimized layout choices for use by the place-and-route engine, as well as wire sizing guidelines for connections outside the cell. For FinFET-based designs of a high-frequency amplifier, a StrongARM comparator, and a fully differential VCO, our approach outperforms existing methods and is competitive with time-intensive manual layout.

Common-centroid (CC) layouts are widely used in analog design to make circuits resilient to variations by matching device characteristics. However, CC layout may involve increased routing complexity and higher parasitics than other alternative layout schemes. This paper critically analyzes the fundamental assumptions behind the use of common-centroid layouts, incorporating considerations related to systematic and random variations as well as the performance impact of common-centroid layout. Based on this study, conclusions are drawn on when CC layout styles can reduce variation, improve performance (even if they do not reduce variation), and when non-CC layouts are preferable.

Embedded/edge computing comes with a very stringent hardware resource (area) budget and a need for extreme energy efficiency. This motivates repurposing, i.e., reconfiguring hardware resources on demand, where the overhead of reconfiguration itself is subject to the very same tight budgets in area and energy efficiency. Numerous applications running on resource constrained environments such as wearable devices and Internet-of-Things incorporate CAM (Content Addressable Memory) as a key computational building block. In this paper we present CAMeleon -- a novel energy-efficient compute substrate which can seamlessly be reconfigured to perform CAM operations in addition to logic and memory functions. CAMeleon has a similar level of latency to conventional CAM designs based on SRAM and emerging memory technologies (such as STT-MTJ, ReRAM and PCM), however, performs CAM operations more energy-efficiently, consumes less area, and can support traditional logic and memory functions beyond CAM operations on demand thanks to its reconfigurability.

Evaluating CAD solutions to physical implementation problems has been extremely challenging due to the unavailability of modern benchmarks in the public domain. This work aims to address this challenge by proposing a process-portable machine learning (ML)-based methodology for synthesizing synthetic power delivery network (PDN) benchmarks that obfuscate intellectual property information. In particular, the proposed approach leverages generative adversarial networks (GAN) and transfer learning techniques to create realistic PDN benchmarks from a small set of available real circuit data. BeGAN generates thousands of PDN benchmarks with significant histogram correlation (p-value ≤ 0.05) demonstrating its realism and an average L1 Norm of more than 7.1 %, highlighting its IP obfuscation capabilities. The original and thousands of ML-generated synthetic PDN benchmarks for four different open-source technologies are released in the public domain to advance research in this field.

This paper introduces VeriGOOD-ML, an automated methodology for generating Verilog with no human in the loop, starting from a high-level description of a machine learning (ML) algorithm in a standard format such as ONNX. The Verilog RTL is then translated through a back-end design flow to GDSII, driven by a design planning approach that is well tailored to the macro-intensive nature of ML platforms. VeriGOOD-ML uses three approaches to build ML hardware: the TABLA platform uses a dataflow architecture that is well suited to non-DNN ML algorithms; the GeneSys platform, with a systolic array and a SIMD array, is optimized for implementing DNNs; and the Axiline approach synthesizes small ML algorithms by hardcoding the structure of the algorithm into hardware, thus trading off flexibility for performance and power. The overall approach explores the design space of platform configurations and Pareto-optimal-PPA back-end implementations to yield designs that represent different tradeoffs at the algorithmic level between area, power, performance, and execution time. The overall methodology, from architecture to back-end design to hardware implementation, is described in this paper, and the results of VeriGOOD-ML are demonstrated on a set of ML benchmarks.

We propose a complete analog mixed-signal circuit design flow from specification to silicon with minimum human-in-the-loop interaction, and verify the flow in a 12nm FinFET CMOS process. The flow consists of three key elements: neural network (NN) modeling of the parameterized circuit component, a search algorithm based on NN models to determine its sizing, and layout automation. To reduce the required training data for NN model creation, we utilize transfer learning to improve the NN accuracy from a relatively small amount of post-layout/silicon data. To prove the concept, we use a voltage-controlled oscillator (VCO) as a test vehicle and demonstrate that our design methodology can accurately model the circuit and generate designs with a wide range of specifications. We show that circuit sizing based on the transfer learned NN model from silicon measurement data yields the most accurate results.

The common-centroid (CC) layout style is widely used to minimize the impact of variations among matched devices in analog blocks such as current mirror banks and differential pairs. This paper presents a constructive, performance-aware CC placement and routing algorithm for transistor arrays. Specifically, the proposed approach maximizes diffusion sharing, incorporates length of diffusion (LOD) based stress-induced performance variations, and mitigates resistive parasitics and electromigration (EM) hotspots, all of which are critical in modern technology nodes. The proposed algorithms are validated using cell- and circuit-level test cases in a commercial 12nm FinFET process. As compared to existing works, the cells generated using the proposed approach are shown to provide better performance in the presence of systematic variations, LOD, layout parasitics, and EM-induced degradation.

Traditional methods that test for electromigration (EM) failure in multisegment interconnects, over the lifespan of an IC, are based on the use of the Blech criterion, followed by Black's equation. Such methods analyze each segment independently, but are well known to be inaccurate due to stress buildup over multiple segments. This paper introduces the new concept of boundary reflections of stress flow that ascribes a physical (wave-like) interpretation to the transient stress behavior in a finite multisegment line. This can provide a framework for deriving analytical expressions of transient EM stress for lines with any number of segments, which can also be tailored to include the appropriate number of terms for any desired level of accuracy. The proposed method is shown to have excellent accuracy, through evaluations against the FEM solver COMSOL, as well as scalability, through its application on large power grid benchmarks.

The quality of layouts generated by automated analog design have traditionally not been able to match those from human designers over a wide range of analog designs. The ALIGN (Analog Layout, Intelligently Generated from Netlists) project [2, 3, 6] aims to build an open-source analog layout engine [1] that overcomes these challenges, using a variety of approaches. An important part of the toolbox is the use of machine learning (ML) methods, combined with traditional methods, and this talk overviews our efforts. The input to ALIGN is a SPICE-like netlist and a set of perfor- mance specifications, and the output is a GDSII layout. ALIGN automatically recognizes hierarchies in the input netlist. To detect variations of known blocks in the netlist, approximate subgraph iso- morphism methods based on graph convolutional networks can be used [5]. Repeated structures in a netlist are typically constrained by layout requirements related to symmetry or matching. In [7], we use a mix of graph methods and ML to detect symmetric and array structures, including the use of neural network based approximate matching through the use of the notion of graph edit distances. Once the circuit is annotated, ALIGN generates the layout, going from the lowest level cells to higher levels of the netlist hierarchy. Based on an abstraction of the process design rules, ALIGN builds parameterized cell layouts for each structure, accounting for the need for common centroid layouts where necessary [11]. These cells then undergo placement and routing that honors the geomet- ric constraints (symmetry, common-centroid). The chief parameter that changes during layout is the set of interconnect RC parasitics: excessively large RCs could result in an inability to meet perfor- mance. These values can be controlled by reducing the distance between blocks, or, in the case of R, by using larger effective wire widths (using multiple parallel connections in FinFET technologies where wire widths are quantized) to reduce the effective resistance. ALIGN has developed several approaches based on ML for this purpose [4, 8, 9] that rapidly predict whether a layout will meet the performance constraints that are imposed at the circuit level, and these can be deployed together with conventional algorithmic methods [10] to rapidly prune out infeasible layouts. This presentation overviews our experience in the use of ML- based methods in conjunction with conventional algorithmic ap- proaches for analog design. We will show (a) results from our efforts so far, (b) appropriate methods for mixing ML methods with tra- ditional algorithmic techniques for solving the larger problem of analog layout, (c) limitations of ML methods, and (d) techniques for overcoming these limitations to deliver workable solutions for analog layout automation.

Spiking Neural Networks (SNNs) represent a biologically inspired computation model capable of emulating neural computation in human brain and brain-like structures. The main promise is very low energy consumption. Classic Von Neumann architecture based SNN accelerators in hardware, however, often fall short of addressing demanding computation and data transfer requirements efficiently at scale. In this article, we propose a promising alternative to overcome scalability limitations, based on a network of in-memory SNN accelerators, which can reduce the energy consumption by up to 150.25= when compared to a representative ASIC solution. The significant reduction in energy comes from two key aspects of the hardware design to minimize data communication overheads: (1) each node represents an in-memory SNN accelerator based on a spintronic Computational RAM array, and (2) a novel, De Bruijn graph based architecture establishes the SNN array connectivity.

This work presents a framework for dynamic energy reduction in hardware accelerators for convolutional neural networks (CNNs). The key idea is based on the early prediction of the features that may be important, with the deactivation of computations related to unimportant features and static bitwidth reduction. The former is applied in late layers of the CNN, while the latter is more effective in the early layers. The procedure includes a methodology for automated threshold tuning to detect feature activation. For various state-of-the-art neural networks, the results show that energy savings of up to about 30% are achievable, after accounting for all implementation overheads, with a small loss in the accuracy.

Designing an optimal power delivery network (PDN) is a time-intensive task that involves many iterations. This paper proposes a methodology that employs a library of predesigned, stitchable templates, and uses machine learning (ML) to rapidly build a PDN with region-wise uniform pitches based on these templates. Our methodology is applicable at both the floorplan and placement stages of physical implementation. (i) At the floorplan stage, we synthesize an optimized PDN based on early estimates of current and congestion, using a simple multilayer perceptron classifier. (ii) At the placement stage, we incrementally optimize an existing PDN based on more detailed congestion and current distributions, using a convolution neural network. At each stage, the neural network builds a safe-by-construction PDN that meets IR drop and electromigration (EM) specifications. On average, the optimization of the PDN brings an extra 3% of routing resources, which corresponds to a thousands of routing tracks in congestion-critical regions, when compared to a globally uniform PDN, while staying within the IR drop and EM limits.

High resolution Fast Fourier Transform (FFT) is important for various applications while increased memory access and parallelism requirement limits the traditional hardware. In this work, we explore acceleration opportunities for high resolution FFTs in spintronic computational RAM (CRAM) which supports true in-memory processing semantics. We experiment with Spin-Torque-Transfer (STT) and Spin-Hall-Effect (SHE) based CRAMs in implementing CRAFFT, a high resolution FFT accelerator in memory. For one million point fixed-point FFT, we demonstrate that CRAFFT can provide up to 2.57× speedup and 673× energy reduction. We also provide a proof-of-concept extension to floating-point FFT.

Automated subcircuit identification and annotation enables the creation of hierarchical representations of analog netlists, and can facilitate a variety of design automation tasks such as circuit layout and optimization. Subcircuit identification must navigate the numerous alternative structures that can implement any analog function, but traditional graph-based methods cannot easily identify the large number of such structural variants. The novel approach in this paper is based on the use of a trained graph convolutional neural network (GCN) that identifies netlist elements for circuit blocks at upper levels of the design hierarchy. Structures at lower levels of hierarchy are identified using graph-based algorithms. The proposed recognition scheme organically detects layout constraints, such as symmetry and matching, whose identification is essential for high-quality hierarchical layout. The subcircuit identification method demonstrates a high degree of accuracy over a wide range of analog designs, successfully identifies larger circuits that contain subblocks such as OTAs, LNAs, mixers, oscillators, and band-pass filters, and provides hierarchical decompositions of such circuits.

Automating analog layout is a long-standing research problem, with a history that goes back several decades. While digital design is largely automated today, analog layout has been significantly more resistant: automation has not made much headway in industry settings. There are several reasons for this, including:

Analog layout synthesis requires some elements in the circuit netlist to be matched and placed symmetrically. However, the set of symmetries is very circuit-specific and a versatile algorithm, applicable to a broad variety of circuits, has been elusive. This paper presents a general methodology for the automated generation of symmetry constraints, and applies these constraints to guide automated layout synthesis. While prior approaches were restricted to identifying simple symmetries, the proposed method operates hierarchically and uses graph-based algorithms to extract multiple axes of symmetry within a circuit. An important ingredient of the algorithm is its ability to identify arrays of repeated structures. In some circuits, the repeated structures are not perfect replicas and can only be found through approximate graph matching. A fast graph neural network based methodology is developed for this purpose, based on evaluating the graph edit distance. The utility of this algorithm is demonstrated on a variety of circuits, including operational amplifiers, data converters, equalizers, and low-noise amplifiers.

Analog IC placement is typically a manual process that requires strong experience and trial-and-error iterations as it produces a large impact to circuit performance in a complicated manner. Although automatic analog placement has been studied for decades, existing methods are inadequate for achieving performance comparable with manual designs. In this work, a customized graph neural network model is developed for predicting the impact of placement on circuit performance. Knowledge obtained by such a model can be transferred among different topologies of the same circuit type. Simulation results show that the proposed model is superior to a recent CNN-based work in terms of both accuracy and knowledge transfer. It also outperforms a plug-in use of graph attention network. The proposed model is further applied in analog IC placement and achieves performance similar to manual designs.

The problem of analog design automation has vexed several generations of researchers in electronic design automation. At its core, the difficulty of the problem is related to the fact that machinegenerated designs have been unable to match the quality of the human designer. The human designer typically recognizes blocks from a netlist and draws upon her/his experience to translate these blocks into a circuit that is laid out in silicon. The ability to annotate blocks in a schematic or netlist-level description of a circuit is key to this entire process, but it is a process fraught with complexity due to the large number of variants of each circuit type. For example, the number of topologies of operational transconductance amplifiers (OTAs) easily numbers in the hundreds. A designer manages this complexity by dividing this large set of variants into classes (e.g., OTAs may be telescopic, folded cascode, etc.). Even so, the number of minor variations within each class is large. Early approaches to analog design automation attempted to use rule-based methods to capture these variations, but this database of rules required tender care: each new variant might require a new rule. As machine learning (ML) based alternatives have become more viable, alternative forms of solving this problem have begun to be explored.

There is increasing demand to bring machine learning capabilities to low power devices. By integrating the computational power of machine learning with the deployment capabilities of low power devices, a number of new applications become possible. In some applications, such devices will not even have a battery, and must rely solely on energy harvesting techniques. This puts extreme constraints on the hardware, which must be energy efficient and capable of tolerating interruptions due to power outages. Here, we propose an in-memory machine learning accelerator utilizing non-volatile spintronic memory. The combination of processing-in-memory and non-volatility provides a key advantage in that progress is effectively saved after every operation. This enables instant shut down and restart capabilities with minimal overhead. Additionally, the operations are highly energy efficient leading to low power consumption.

Neural networks span a wide range of applications of industrial and commercial significance. Binary neural networks (BNN) are particularly effective in trading accuracy for performance, energy efficiency, or hardware/software complexity. Here, we introduce a spintronic, re-configurable in-memory BNN accelerator, PIMBALL: P rocessing I n M emory B NN A cce L(L) erator, which allows for massively parallel and energy efficient computation. PIMBALL is capable of being used as a standard spintronic memory (STT-MRAM) array and a computational substrate simultaneously. We evaluate PIMBALL using multiple image classifiers and a genomics kernel. Our simulation results show that PIMBALL is more energy efficient than alternative CPU-, GPU-, and FPGA-based implementations while delivering higher throughput.

In the past few years, ever-increasing amounts of image data have been generated by users globally, and these images are routinely stored in cold storage systems in compressed formats. This article investigates the use of approximate storage that leverages the use of cheaper, lower reliability memories that can have higher error rates. Since traditional JPEG-based schemes based on variable-length coding are extremely sensitive to error, the direct use of approximate storage results in severe quality degradation. We propose an error-resilient adaptive-length coding (ALC) scheme that divides all symbols into two classes, based on their frequency of occurrence, where each class has a fixed-length codeword. This provides a balance between the reliability of fixed-length coding schemes, which have a high storage overhead, and the storage-efficiency of Huffman coding schemes, which show high levels of error on low-reliability storage platforms. Further, we use data partitioning to determine which bits are stored in approximate or reliable storage to lower the overall cost of storage. We show that ALC can be used with general non-volatile storage, and can substantially reduce the total cost compared to traditional JPEG-based storage.

Data processing on convolutional neural networks (CNNs) places a heavy burden on energy-constrained mobile platforms. This article optimizes energy on a mobile client by partitioning CNN computations between in situ processing on the client and offloaded computations in the cloud. A new analytical CNN energy model is formulated, capturing all major components of the in situ computation, for ASIC-based deep learning accelerators. The model is benchmarked against measured silicon data. The analytical framework is used to determine the optimal energy partition point between the client and the cloud at runtime. On standard CNN topologies, partitioned computation is demonstrated to provide significant energy savings on the client over a fully cloud-based computation or fully in situ computation. For example, at 80 Mbps effective bit rate and 0.78 W transmission power, the optimal partition for AlexNet [SqueezeNet] saves up to 52.4% [73.4%] energy over a fully cloud-based computation and 27.3% [28.8%] energy over a fully in situ computation.

This work presents a dynamic energy reduction approach for hardware accelerators for convolutional neural networks (CNN). Two methods are used: (1) an adaptive data-dependent scheme to selectively activate a subset of all neurons, by narrowing down the possible activated classes (2) static bitwidth reduction. The former is applied in late layers of the CNN, while the latter is more effective in early layers. Even accounting for the implementation overheads, the results show 20%--25% energy savings with 5--10% accuracy loss.

We describe the planned Alpha release of OpenROAD, an open-source end-to-end silicon compiler. OpenROAD will help realize the goal of "democratization of hardware design", by reducing cost, expertise, schedule and risk barriers that confront system designers today. The development of open-source, self-driving design tools is in and of itself a "moon shot" with numerous technical and cultural challenges. The open-source flow incorporates a compatible open-source set of tools that span logic synthesis, floorplanning, placement, clock tree synthesis, global routing and detailed routing. The flow also incorporates analysis and support tools for static timing analysis, parasitic extraction, power integrity analysis, and cloud deployment. We also note several observed challenges, or "lessons learned", with respect to development of open-source EDA tools and flows.

This paper presents analog layout automation efforts under the ALIGN ("Analog Layout, Intelligently Generated from Netlists") project for fast layout generation using a modular approach based on a mix of algorithmic and machine learning-based tools. The road to rapid turnaround is based on an approach that detects structure and hierarchy in the input netlist and uses a grid based philosophy for layout. The paper provides a view of the current status of the project, challenges in developing open-source code with an academic/industry team, and nuts-and-bolts issues such as working with abstracted PDKs, navigating the "wall" between secured IP and open-source software, and securing access to example designs.

As we approach the limits of CMOS scaling, researchers are developing "beyond-CMOS" technologies to sustain the technological benefits associated with device scaling. Spin-tronic technologies have emerged as a promising beyond-CMOS technology due to their inherent benefits over CMOS such as high integration density, low leakage power, radiation hardness, and non-volatility. These benefits make spintronic devices an attractive successor to CMOS-especially for memory circuits. However, spintronic devices generally suffer from slower switching speeds and higher write energy, which limits their usability. In an effort to close the energy-delay gap between CMOS and spintronics, device concepts such as CoMET (Composite-Input Magnetoelectric-base Logic Technology) have been introduced, which collectively leverage material phenomena such as the spin-Hall effect and the magnetoelectric effect to enable fast, energy efficient device operation. In this work, we propose a non-volatile flip-flop (NVFF) based on CoMET technology that is capable of achieving up to two orders of magnitude less write energy than CMOS. This low write energy (≈2 aJ) makes our CoMET NVFF especially attractive to architectures that require frequent backup operations-e.g., for energy harvesting non-volatile processors.

No abstract available.

Communication overheads in distributed systems constitute a large fraction of the total execution time, and limit the scalability of applications running on these systems. We propose a DCT-based approximate communication scheme that takes advantage of the error resiliency of several widely-used applications, and improves communication efficiency by substantially reducing message lengths. Our scheme is implemented into the Message Passing Interface (MPI) library. When evaluated on several representative MPI applications on a real cluster system, it is seen that the fraction of total execution time devoted to communication reduces from 59% to 23%, even accounting for the computational overhead required for DCT encoding. For many communication-intensive applications, it is shown that our approximate communication scheme effectively speeds up the total execution time without much loss in quality of the result.

Electromigration (EM) is seen as a growing problem in recent and upcoming technology nodes, and affects a wider variety of wires (e.g., power grid, clock/signal nets), circuits (e.g., digital, analog, mixed-signal), and systems (e.g., mobile, server, automotive), touching lower levels of metal than before. Moreover, unlike traditional EM checks that were performed on each wire individually, EM checks must evolve to consider the system-level impact of wire failure. This requires a change in how interconnect design incor- porates this effect. This paper overviews the root causes of EM, its impact on high-performance designs, and techniques for analyzing, working around, and alleviating the effects of EM.

Mixed-criticality system is a popular model for reducing pessimism in real-time scheduling while providing guarantee for critical tasks in presence of unexpected overrun. However, it is controversial due to some drawbacks. First, a single high-criticality job overrun leads to the pessimistic mode for all high-criticality tasks and consequently resource utilization becomes inefficient. Second, all low-criticality tasks are dropped in high-criticality mode, although they are still needed. These two issues have been addressed in several recent works, which are mostly focused on uniprocessor scheduling. In this work, we attempt to tackle these two issues in multiprocessor scheduling for dual-criticality systems. A deferred switching protocol is introduced so that the chance of switching to high-criticality mode is significantly reduced. Moreover, a service preserving technique is developed such that all low-criticality tasks can continue to execute in high-criticality mode. Further, the two techniques are unified into a single framework. Schedulability of these methods is studied so that the Quality-of-Service is improved with guarantee of satisfying all deadline constraints. The effectiveness of the proposed techniques is confirmed through simulations.

The Computational Random Access Memory (CRAM) is a platform that makes a small modification to a standard spintronics-based memory array to organically enable logic operations within the array. CRAM provides a true in-memory computational platform that can perform computations within the memory array, as against other methods that send computational tasks to a separate processor module or a near-memory module at the periphery of the memory array. This paper describes how the CRAM structure can be built and utilized, accounting for considerations at the device, gate, and functional levels. Techniques for constructing fundamental gates are first overviewed, accounting for electrical and noise margin considerations. Next, these logic operations are composed to schedule operations in the array that implement basic arithmetic operations such as addition and multiplication. These methods are then demonstrated on 2D convolution with multibit data, and a binary neural inference engine. The performance of the CRAM is analyzed on near-term and longer-term spintronic device technologies. Significant improvements in energy and execution time for the CRAM-based implementation over a near-memory processing system are demonstrated, and can be attributed to the ability of CRAM to overcome the memory access bottleneck, and to provide high levels of parallelism to the computation.

Approximate computing has emerged as a circuit design technique that can reduce system power without significantly sacrificing the output quality in error-resilient applications. However, there exists only a few approaches for systematically and efficiently determining the error introduced by approximate hardware units. This paper focuses on the development of error analysis techniques for approximate circuits consisting of adders and multipliers, which are the key hardware components used in error-resilient applications. A novel algorithm has been presented, using the Fourier and the Mellin transforms, that efficiently determines the probability distribution of the error introduced by approximation in a circuit, abstracted as a directed acyclic graph. The algorithm is generalized for signed operations through two's complement representation, and its accuracy is demonstrated to be within 1% of Monte Carlo simulations, while being over an order of magnitude faster.

JPEG compression based on the discrete cosine transform is a key building block in low-power multimedia applications. Approximate computation techniques are used to exploit the error tolerance of JPEG. An image-dependent framework is proposed in this paper to design optimized approximate hardware with variable approximate bit-widths for a user-specified error budget. The proposed method can dynamically adjust the extent of approximation in the system depending on the pixel values of the input image, thus leveraging the inherent sparsity of certain images. This novel technique not only improves the power-delay product by 3.4× over the base case, i.e., where the JPEG hardware is accurate but also significantly outperforms the image-independent approximation case, which is solely based on the error tolerance of the JPEG algorithm.

3D-stacked DRAMs can significantly increase cell density and bandwidth while also lowering power consumption. However, 3D structures experience significant thermomechanical stress due to the differential rate of contraction of the constituent materials, which have different coefficients of thermal expansion. This impacts circuit performance. This article develops a procedure that performs a performance analysis of 3D DRAMs, capturing the impact of both layout-aware stress and layout-independent stress on parameters such as latency, leakage power, refresh power, area, and bus delay. The approach first proposes a semianalytical stress analysis method for the entire 3D DRAM structure, capturing the stress induced by through-silicon-vias (TSVs), micro bumps, package bumps, and warpage. Next, this stress is translated to variations in device mobility and threshold voltage, after which analytical models for latency, leakage power, and refresh power are derived. Finally, a complete analysis of performance variations is performed for various 3D DRAM layout configurations to assess the impact of layout-dependent stress. We explore the use of alternative flexible package substrate options to mitigate the performance impact of stress. Specifically, we explore the use of an alternative bendable package substrate made of polyimide to reduce warpage-induced stress, and show that it reduces stress-induced variations and improves the performance metrics for stacked 3D DRAMs.

Conventional hard real-time scheduling is often overly pessimistic due to the worst case execution time estimation. The pessimism can be mitigated by exploiting imprecise computing in applications where occasional small errors are acceptable. This leverage was previously investigated for preemptive scheduling. We study how to make use of imprecise computing in uniprocessor non-preemptive real-time scheduling, which is known to be more difficult than its preemptive counterpart. Several heuristic algorithms are developed for periodic tasks with independent or cumulative errors due to imprecision. Simulation results show that the proposed techniques can significantly improve task schedulability and achieve desired accuracy-schedulability tradeoff. The benefit is further confirmed by a prototyping implementation in Linux system.

In-memory computing is a promising approach to alleviating the processor-memory data transfer bottleneck in computing systems. While spintronics has attracted great interest as a non-volatile memory technology, recent work has shown that its unique properties can also enable in-memory computing. We summarize efforts in this direction, and describe three different designs that enhance STT-MRAM to perform logic, arithmetic, and vector operations and evaluate transcendental functions within memory arrays.

Organic thin-film transistors (OTFTs) are widely used in flexible circuits, such as flexible displays, sensor arrays, and radio frequency identification cards (RFIDs), because these technologies offer features such as better flexibility, lower cost, and easy manufacturability using low-temperature fabrication process. This paper develops a procedure that evaluates the performance of flexible displays. Due to their very nature, flexible displays experience significant mechanical strain/stress in the field due to the deformation caused during daily use. These deformations can impact device and circuit performance, potentially causing a loss in functionality. This paper first models the effects of extrinsic strain due to two fundamental deformations modes, bending and twisting. Next, this strain is translated to variations in device mobility, after which analytical models for error analysis in the flexible display are derived based on the rendered image values in each pixel of the display. Finally, two error correction approaches for flexible displays are proposed, based on voltage compensation and flexible clocking.

This paper presents an approach for analyzing stress in 2-D and 3-D integrated circuits (ICs) due to postmanufacturing thermal mismatch. For both 2D-ICs and 3D-ICs, shallow trench isolation (STI) induces thermal residual stress in active silicon. For 3D-ICs, through-silicon vias (TSVs) act as an additional source of stress. Together, the sources of stress cause changes in the delay and power of the circuit. We develop an analytical model based on inclusion theory in micromechanics to accurately estimate the stresses and strains induced in the active region by surrounding STI in a layout. The TSV-induced stress depends on the location of the transistor with respect to the TSVs. Therefore, these stresses result in placement-dependent variations in the transistor mobilities and threshold voltages of the active devices, and we propagate these effects to circuit-level performance. At the transistor level, the stress state is translated into mobility and threshold voltage variations using piezoresistivity and band deformation potential models, respectively. At the gate level, the computed changes in transistor electrical parameters are used to predict gate-level delay and leakage power changes for single-fingered and multifingered layout styles, which are subsequently used to predict circuit-level delay and leakage power for a given placement.

Approximate computing has applications in areas such as image processing, neural computation, distributed systems, and real-time systems, where the results may be acceptable in the presence of controlled levels of error. The promise of approximate computing is in its ability to render just enough performance to meet quality constraints. However, going from this theoretical promise to a practical implementation requires a clear comprehension of the system requirements and matching them to the design of approximations as the system is implemented. This involves the tasks of (a) identifying the design space of potential approximations, (b) modeling the injected error as a function of the level of approximation, and (c) optimizing the system over the design space to maximize a metric, typically the power savings, under constraints on the maximum allowable degradation. Often, the error may be introduced at a low level of design (e.g., at the level of a full adder) but its impact must be percolated up to system-level error metrics (e.g., PSNR in a compressed image), and a practical approach must devise a coherent and quantifiable way of translating between error/power tradeoffs at all levels of design.

Modern power grids use via arrays to connect wires across metal layers. These arrays are susceptible to electromigration (EM), which creates voids under the vias, potentially causing circuit malfunction. We combine the effect of via redundancy with models that characterize the effect of via array geometry on thermomechanical stress, and determine how the choice of via arrays can affect EM-induced failure in a power grid based on IR-drop threshold based failure criteria.

A wide variety of error tolerant applications supports the use of approximate circuits that achieve power savings by introducing small errors. This paper proposes a fast and novel algorithm for the design of such circuits with the goal of maximizing power savings, constrained by a fixed error budget, through an analytical expression to optimally select the number of bits to be approximated. This algorithm outperforms uniform approximation schemes by over 30% in power savings, with negligible computational overhead.

Many key technologies of our society, including so-called artificial intelligence (AI) and big data, have been enabled by the invention of transistor and its ever-decreasing size and ever-increasing integration at a large scale. However, conventional technologies are confronted with a clear scaling limit. Many recently proposed advanced transistor concepts are also facing an uphill battle in the lab because of necessary performance tradeoffs and limited scaling potential. We argue for a new pathway that could enable exponential scaling for multiple generations. This pathway involves layering multiple technologies that enable new functions beyond those available from conventional and newly proposed transistors. The key principles for this new pathway have been demonstrated through an interdisciplinary team effort at C-SPIN (a STARnet center), where systems designers, device builders, materials scientists and physicists have all worked under one umbrella to overcome key technology barriers. This paper reviews several successful outcomes from this effort on topics such as the spin memory, logic-in-memory, cognitive computing, stochastic and probabilistic computing and reconfigurable information processing.

Many ultra-low power Internet of things (IoT) systems may be powered by energy harvested from ambient sources (e.g., solar radiation, thermal gradients, and WiFi). However, these energy sources can vary significantly in terms of their strengths and on/off patterns. For volatile systems, the intermittent nature of the energy sources necessitates the use of backup/recovery schemes to guarantee computational correctness and forward progress, which incur performance, area and energy overhead. Non-volatile (NV) processors based on spintronic devices, such as Spin-Transfer Torque (STT) memory and All-Spin-Logic (ASL), are more attractive alternatives. These NV devices are capable of achieving forward progress without relying on backup/recovery schemes. This work establishes a general framework for evaluating NV device-based processors for energy harvesting applications. Results demonstrate that NV spintronic processors can achieve significant energy savings (up to 83 x) versus a hybrid CMOS (computation) and STT-RAM (backup) implementation.

3D-stacked wide I/O DRAM can significantly increase cell density and bandwidth while also lowering power consumption. However, 3D structures experience significant thermomechanical stress, which impacts circuit performance. This paper develops a procedure that performs a full performance analysis of 3D DRAMs, including latency, leakage power, refresh power, and area, while incorporating the effects of both layout-aware stress and layout-independent stress. The approach first proposes an analytic stress analysis method for the entire 3D DRAM structure, capturing the stress induced by TSVs, micro bumps, package bumps and warpage. Next, this stress is translated to variations in device mobility and threshold voltage, after which analytical models for latency, leakage power, and refresh power are derived. Finally, a complete analysis of performance variations is performed for various 3D DRAM layout configurations to assess the impact of layout-dependent stress.

Approximate computing is a promising approach for low power IC design and has recently received considerable research attention. To accommodate dynamic levels of approximation, a few accuracy configurable adder designs have been developed in the past. However, these designs tend to incur large area overheads as they rely on either redundant computing or complicated carry prediction. Some of these designs include error detection and correction circuitry, which further increases area. In this work, we investigate a simple accuracy configurable adder design that contains no redundancy or error detection/correction circuitry and uses very simple carry prediction. Simulation results show that our design dominates the latest previous work on accuracy-delay-power tradeoff while using 39% lower area. Moreover, we propose a delay-adaptive self-configuration technique to further improve accuracy-delay-power tradeoff.

Electromigration (EM) is a growing concern in on-chip interconnects, particularly in the computing and automotive domains. EM can cause wire resistances in a circuit to increase, which may result in circuit performance failure within the lifetime of a product. Classical circuit-level EM models have two drawbacks: first, they do not accurately capture the physics of degradation in modern copper dual-damascene (Cu DD) metallization and second, they fail to model the inherent resilience in a circuit that may allow it to continue to function even after some wires fail. This paper overcomes both limitations, and develops a method to analyze the effect of EM on the resistance of wires in a circuit. For a single wire, our probabilistic analysis encapsulates known realities about Cu DD wires, e.g., that some regions of these wires are more susceptible to EM than others, and that void evolution shows statistical behavior. We develop a new criterion for identifying mortal wires based on this analysis. One part of the criterion incorporates the achievement of steady state and provides a result that is slightly tighter than the traditional Blech criterion, while another part is tied to the lifetime of the system. We apply these ideas to the analysis of on-chip power grids and demonstrate the inherent robustness of these grids that maintains supply integrity under some EM failures.

The performance of nanometer-scale circuits is adversely affected by aging induced by bias temperature instability (BTI) and hot carrier injection (HCI). Both BTI and HCI impact transistor electrical parameters at a level that depends on the operating environment and usage of the circuit. This paper presents a novel method, using on-chip sensors based on ring oscillators (ROSCs), to detect the delay shifts in circuits as a result of aging. Our method uses presilicon analysis of the circuit to compute calibration factors that can translate BTI- and HCI-induced delay shifts in the ROSC to those in the circuit of interest. Our simulations show that the delay estimates are within 1% of the true values from presilicon analysis. Further, for post-silicon analysis, a refinement strategy is proposed where sensor measurements can be amalgamated with infrequent online delay measurements on the monitored circuit to partially capture its true workloads. This leads to about 8% lower delay guardbanding overheads compared to the conventional methods as demonstrated using benchmark circuits.

A fast and stochastic analysis methodology for electromigration (EM) assessment of power distribution networks is presented in this paper. We examine the impact of variability on EM time-to-failure (TTF), considering altered current densities due to global/local process variations as well as the fundamental factors that cause the conventional EM TTF distribution. Through the novel variations-aware current density model based on Hermite polynomial chaos, we demonstrate significant margins in EM lifetime when compared with the traditional worst case approach. On the other hand, we show that the traditional approach is altogether incompetent in handling transistor-level local variations leading to significantly optimistic lifetime estimates for lower metal level interconnects of power delivery network. Subsequently, we attempt to bridge the conventional, component-level EM verification method to the system level failures, inspired by the extreme order statistics. We make use of asymptotic order models to determine the TTF for the kth component failure due to EM, and demonstrate application of this approach in developing IR drop aware system-level failure criteria.

The design of logic and memory circuits in emerging spintronics technology offers fertile ground for new ideas and innovations. We first describe methods for optimizing spintronic logic circuits at the level of physical design, including systematic approaches for building standard cell libraries to enable the design of large circuits. Next, we examine issues in the design of spintronic memories and present methods that trade off volatility with error correction to create dense memory arrays.

Today's methodologies for electromigration (EM) identify EM-susceptible wires based on their current density, using the Blech criterion to filter out wires that are EM-immortal. The Blech criterion is agnostic to the product lifetime and temperature conditions: many Blech-mortal wires may never experience EM during the product lifetime. We develop new methods that evaluate the transient evolution of stress, relative to the product lifetime, and present an improved set of simple and practical mortality criteria. On a set of power grid benchmarks, we demonstrate that the actual number of mortal wires may depend strongly on the lifetime and reliability conditions.

Over the years, there has been tremendous progress in developing new methods for modeling and diagnosing reliability at the level of individual transistors and interconnects. The thrust to propagate these models to higher levels of abstraction to predict the reliability of larger circuits is much more recent. This paper addresses the intersection of physics, circuits, and architecture for reliability modeling and optimization that must come together for cross-layer optimization. For various device reliability phenomena, this paper shows how physical models can be leveraged at the circuit level, or circuit models at the architecture level, to deliver composite solutions that comprehend chip-level design goals.

JPEG compression based on the discrete cosine transform (DCT) is a key building block in low-power multimedia applications. We use approximate computing to exploit the error tolerance of JPEG and formulate a novel optimization problem that maximizes power savings under an error budget. We analyze the error propagation sensitivity in the DCT network and use this information to model the impact of introduced errors on the output quality. Simulations show up to 15% reduction in area and delay which corresponds to 40% power savings at iso-delay.

Adaptive Supply Voltage (ASV) is a power-efficient approach to achieving resilience against process variation and circuit aging. Fine-grained ASV offers further power-efficiency gains, but entails relatively complex control circuit, which has not been well studied yet. This paper presents two control design techniques - one is rule-based control derived from network flow optimization and the other is finite state machine control. For the FSM control, a graph-based algorithm that automates the control vector generation is proposed. To the best of our knowledge, this work is the first dedicated study on fine-grained ASV control. This paper also presents an iterative greedy heuristic for delay sensor deployment in ASV designs. The effectiveness of these techniques is confirmed by experiments performed on ICCAD 2014 benchmark circuits. The results show that our techniques achieve around 20% leakage power reduction compared to coarse-grained ASV, while maintain about the same timing yield.

All-Spin Logic (ASL) devices provide a promising spintronics-based alternative for Boolean logic implementations in the post-Complementary Metal-Oxide Semiconductor (CMOS) era. In principle, any logic functionality can be implemented in ASL. In practice, the performance of an ASL gate is significantly affected by layout choices, but such implications have not been adequately explored in the past. This article proposes a systematic approach for building standard cells in ASL, which are a basic building block in an overall design methodology for implementing large ASL-based circuits. We first propose a new technique to reduce the magnet count for an ASL majority gate but still ensure correct functioning through layout optimization methods. Building on physics-based analysis, we then build a standard cell library with diverse functionality and characterize the library for delay, energy, and area. We perform delay-optimized technology mapping on ISCAS85 benchmark circuits using our library. Our approach results in circuits that are 12.90% faster, consume 26.16% less energy, and are 33.56% more area efficient compared to a standard cell library that does not incorporate layout-based optimization techniques of our work.

Electromigration (EM) in on-chip metal interconnects is a critical reliability-driven failure mechanism in nanometer-scale technologies. This paper addresses the problem of EM on signal interconnects and on Vdd and Vss rails within a standard cell. An approach for modeling and efficient characterization of cell-internal EM is developed, incorporating Joule heating effects. We also present a graph-based algorithm that computes the currents when the pin position is moved avoiding a new characterization for each pin position and consequently considerably reducing the characterization time. We use the cell lifetime analysis to determine the lifetime of large benchmark circuits, and show that these circuit lifetimes can be improved by about 2.5×-161× by avoiding the EM-critical output, Vdd, and Vss pin positions of the cells, using minor layout modifications.

A new methodology for system-on-chip-level logic-IP-internal electromigration verification is presented in this paper, which significantly improves accuracy by comprehending the impact of the parasitic RC loading and voltage-dependent pin capacitance in the library model. It additionally provides an on-the-fly retargeting capability for reliability constraints by allowing arbitrary specifications of lifetimes, temperatures, voltages, and failure rates, as well as interoperability of the IPs across foundries. The characterization part of the methodology is expedited through the intelligent IP-response modeling. The ultimate benefit of the proposed approach is demonstrated on a 28-nm design by providing an on-the-fly specification of retargeted reliability constraints. The results show a high correlation with SPICE and were obtained with an order of magnitude reduction in the verification runtime.

A new methodology for SoC-level logic-IP-internal EM verification is presented, which provides an on-the-fly retargeting capability for reliability constraints. This flexibility is available at the design verification stage, in the form of allowing arbitrary specifications (of lifetimes, temperatures, voltages and failure rates), as well as interoperability of IPs across foundries. The methodology is characterization- and reuse-based, and naturally incorporates complex effects such as clock gating and variable switching rates at different pins. The benefit from such a framework is demonstrated on a 28nm design, with close SPICE-correlation and verification in a retargeted reliability condition.

Approximate computing has been recognized as an effective low power technique for applications with intrinsic error tolerance, such as image processing and machine learning. Existing efforts on this front are mostly focused on approximate circuit design, approximate logic synthesis or processor architecture approximation techniques. This work aims at how to make good use of approximate circuits at system and block level. In particular, approximation aware scheduling, functional unit allocation and binding algorithms are developed for data intensive applications. Simple yet credible error models, which are essential for precision control in the optimizations, are investigated. The algorithms are further extended to include bitwidth optimization in fixed point computations. Experimental results, including those from Verilog simulations, indicate that the proposed techniques facilitate desired energy savings under latency and accuracy constraints.

Source/drain stressors in FinFET-based circuits lose their effectiveness at smaller contacted gate pitches. To improve circuit performance, a dual gate pitch technique is proposed in this work, where standard cells with double the gate pitch are selectively used on the gates of the circuit critical paths, at minimal area and power costs. A stress-aware library characterization is performed for FinFET-based standard cells by obtaining stress distributions using finite element simulations on a subset of structures. The stresses are then employed to create look-up tables for mobility multipliers and threshold voltage shifts, for subsequent performance characterization of FinFET-based standard cells. Finally, a circuit delay optimizer is applied using the dual gate pitch approach and is compared with an alternative gate sizing approach. Using a combination of gate sizing and the dual gate pitch approach, it is shown that the average power delay product improves by 12.9% and 15.9% in 14nm and 10nm technologies, respectively.

Approximate computing has emerged as a circuit design technique that can reduce system power without significantly sacrificing the output quality in error-resilient applications. However, there are few approaches for systematically and efficiently determining the error introduced by approximate hardware units. This paper focuses on the development of error analysis techniques for approximate multipliers, which are a key hardware component used in error-resilient applications, and presents a novel algorithm that efficiently determines the probability distribution of the error introduced by the approximation. The accuracy of the technique is demonstrated to be comparable to Monte Carlo simulations, while being significantly less computationally intensive.

The growing variability in nanoelectronic devices, due to uncertainties from the manufacturing process and environmental conditions (power supply, temperature, aging), requires increasing design guardbands, forcing circuits to work with conservative clock frequencies. Various schemes for clock generation based on ring oscillators and adaptive clocks have been proposed with the goal to mitigate the power and performance losses attributable to variability. However, there has been no systematic analysis to quantify the benefits of such schemes and no sign-off method has been proposed for timing correctness. This paper presents and analyzes a Reactive Clocking scheme with Variability-Tracking Jitter (RClk) that uses variability as an opportunity to reduce power by continuously adjusting the clock frequency to the varying environmental conditions, and thus, reduces guardband margins significantly. Power can be reduced between 20% and 40% at iso-performance and performance can be boosted by similar amounts at iso-power. Additionally, energy savings can be translated to substantial advantages in terms of reliability and thermal management. More importantly, the technology can be adopted with minimal modifications to conventional EDA flows.

Design automation has been one of the main propellers of the semiconductor industry with logic synthesis being one of the core technologies in this field. This article reviews the evolution of logic synthesis until the advent of techniques for automatic pipelining based on elastic timing, either synchronous or asynchronous. The emergence of these techniques can enable a productive interaction with tools that can do microarchitectural exploration of complex designs.

As the end draws near for Moore's law, the search for low-power alternatives to complementary metal-oxide-semiconductor (CMOS) technology is intensifying. Among the various post-CMOS candidates, spintronic devices have gained special attention for their potential to overcome the power and performance limitations of CMOS. In particular, all spin logic (ASL) technology, which performs Boolean operations and transfers the output in the spin domain, has been proposed for enabling new capabilities-such as high density, low device count, and nonvolatility-that were previously impossible with CMOS technology. In this paper, first we provide an overview of the history and the current status of the various spintronic devices being pursued by the research community. Then, we describe how spin-based components are integrated into a computing system and the advantages that result. We use a hypothetical spintronic-based Intel Core i7 as a test vehicle to compare the system-level power requirements of ASL- and CMOS-based systems, taking into consideration the unique demands of spin-based interconnects. We conclude with a brief analysis of current limitations and future directions of spintronic research.

In 3-D ICs, through silicon via (TSV)-induced thermal residual stress impacts several transistor electrical parameters-low-field mobility, saturation velocity, and threshold voltage. These thermal-stress related shifts are coupled with other temperature effects on transistor parameters that are seen even in the absence of TSVs. In this paper, analytical models are developed to holistically represent the effect of thermally-induced variations on circuit timing. A biaxial stress model is built, based on a superposition of 2-D axisymmetric and Boussinesq-type elasticity models. The computed stresses and strains are then employed to evaluate transistor mobility, saturation velocity, and threshold voltage. The electrical variations are translated into gate-level delay and leakage power calculations, which are then elevated to circuit-level analysis to thoroughly evaluate the variations in circuit performance-induced by TSV stress.

This paper presents a method for inferring circuit delay shifts due to bias temperature instability using ring oscillator (ROSC) sensors. This procedure is based on presilicon analysis, postsilicon ROSC measurements, a new aging analysis model called the Upperbound on fMax(UofM), and a look-up table that stores a precomputed degradation ratio that translates delay shifts in the ROSC to those in the circuits. This method not only yields delay estimates within 0.2% of the true values with very low runtime, but is also independent of temperature and supply voltage variations.

STT-MRAMs are prone to data corruption due to inadvertent bit flips. Traditional methods enhance robustness at the cost of area/energy by using larger cell sizes to improve the thermal stability of the MTJ cells. This paper employs multibit error correction with DRAM-style refreshing to mitigate errors and provides a methodology for determining the optimal level of correction. A detailed analysis demonstrates that the reduction in nonvolatility requirements afforded by strong error correction translates to significantly lower area for the memory array compared to simpler ECC schemes, even when accounting for the increased overhead of error correction.

Electromigration (EM) in on-chip metal interconnects is a critical reliability failure mechanism in nanometer-scale technologies. This work addresses the problem of EM on signal interconnects within a standard cell. An approach for modeling and efficient characterization of cell-internal EM is developed, incorporating Joule heating effects, and is used to analyze the lifetime of large benchmark circuits. Further, a method for optimizing the circuit lifetime using minor layout modifications is proposed.

Bias temperature instability (BTI) induced delay shifts in a circuit depend strongly on its operating environment. While sensors can capture some operating parameters, they are ineffective in measuring vital performance shifts due to changes in the workloads and signal probabilities. This paper determines the delay of an aged circuit by amalgamating more frequent measurements on ring-oscillator sensors with infrequent online delay measurements on a monitored circuit to recalibrate the sensors. Our approach reduces the pessimism in predicting circuit delays, thus permitting lower delay guardbanding overheads compared to conventional methods.

NoCs are an integral part of modern multicore processors, they must continuously support high-throughput low-latency on-chip data communication under a stringent energy budget when system size scales up. Heterogeneous multicore systems further push the limit of NoC design by integrating cores with diverse performance requirements onto the same die. Traditional packet-switched NoCs, which have the flexibility of connecting diverse computation and storage devices, are facing great challenges to meet the performance requirements within the energy budget due to latency and energy consumption associated with buffering and routing at each router. In this paper, we take advantage of the diversity in performance requirements of on-chip heterogeneous computing devices by designing, implementing, and evaluating a hybrid-switched network that allows the packet-switched and circuit-switched messages to share the same communication fabric by partitioning the network through time-division multiplexing (TDM). In the proposed hybrid-switched network, circuit-switched paths are established along frequently communicating nodes. Our experiments show that utilizing these paths can improve system performance by reducing communication latency and alleviating network congestion. Furthermore, better energy efficiency is achieved by reducing buffering in routers and in turn enabling aggressive power gating.

Power grid design and analysis is a critical part of modern VLSI chip design and demands tools for accurate modeling and efficient analysis. The process of power grid design is inherently iterative, during which numerous small changes are made to an initial design, either to enhance the design or to fix design constraint violations. Due to the large sizes of power grids in modern chips, updating the solution for these perturbations can be a computationally intensive task. In this work, we first introduce an accurate modeling methodology for power grids that, contrary to conventional models, can result in asymmetrical equations. Next, we propose an efficient and accurate incremental solver that utilizes the backward random walks to identify the region of influence of the perturbation. The solution of the network is then updated for this significantly smaller region only. The proposed algorithm is capable of handling both symmetrical and asymmetrical power grid equations. Moreover, it can handle consecutive perturbations without any degradation in the quality of the solution. Experimental results show speedups of up to 13× for our incremental solver, as compared to a full resolve of the power grid.

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

This paper focuses on hot-carrier effects in modern CMOS technologies and proposes a scalable method for analyzing circuit-level delay degradations in large digital circuits, using methods that take abstractions up from the transistor to the circuit level. We begin with an exposition of our approach for the nominal case. At the transistor level, a multimode energy-driven model for nanometer technologies is employed. At the logic cell level, a methodology that captures the aging of a device as a sum of device age gains per signal transition is described, and the age gain is characterized using SPICE simulation. At the circuit level, the cell-level characterizations are used in conjunction with probabilistic methods to perform fast degradation analysis. Next, we extend the nominal case analysis to include the effect of process variations. Finally, we show the composite effect of these approaches in the presence of other aging variations, notably bias temperature instability, and study the relative impact of each component of aging on the temporal trends of circuit delay degradations. The analysis approaches for nominal and variational cases are both validated by Monte Carlo simulation on various benchmark circuits, and are proved to be accurate, efficient, and scalable.

Although typical digital circuits are designed so that the clock period satisfies worst case path delay constraints, the average input excitation often completes computation in less than a clock cycle. Variable latency units (VLUs) allow for improved throughput by allowing one clock cycle for some computations, and two clock cycles for others, using hold logic to differentiate between the two cases. However, they may experience significant throughput losses due to the effects of process variations. We develop a combined presilicon-postsilicon technique for variation-aware VLU design that ensures high throughputs across all manufactured chips. We achieve this by identifying path clusters at the presilicon stage, such that each element of a path cluster is likely to be similarly critical in a manufactured part. We use sensors to determine which path clusters is critical at the postsilicon stage and then activate the appropriate hold logics. Practically, for a small number of path clusters, significant improvements in throughput are achievable. On a set of 32-nm PTM-based ISCAS89 circuits, our scheme offers 15.1% throughput enhancements with only 3.3% area overhead.

Dynamic voltage and frequency scaling (DVFS) is a powerful technique to reduce power consumption in a chip multiprocessor. To support DVFS in the multicore power delivery network, we integrate on-chip switched-capacitor (SC) dc-dc converters that can work with multiple conversion ratios to provide varying levels of Vdd supplies. We study the application of such SC converters in multicore chips by simulation. Our results show that distributed SC converters can significantly reduce the voltage droop seen by the local core loads by providing better localized power regulation. Considering the fact that the current distribution in a multicore chip is unbalanced, we further develop computer-aided design techniques to automate the design (size) and distribution (number and location) of these SC converters, using the efficiency of the whole power delivery system as the optimization metric. This is a major concern, but has not been addressed at the system level in prior research. We develop models for the power loss of such a system as a function of size and distribution of the SC converters, then propose an approach to optimize the SC converters to maximize the efficiency of the system, while considering all the possible conversion ratios an SC converter can work with. We verify the accuracy of our models for the power loss in the power delivery system, and demonstrate the efficiency of our techniques to optimize the SC converters on both homogenous and heterogenous multicore chips.

Electromigration (EM), a growing problem in on-chip interconnects, can cause wire resistances in a circuit to increase under stress, to the point of creating open circuits. Classical circuit-level EM models have two drawbacks: first, they do not accurately capture the physics of degradation in copper dual-damascene (CuDD) metallization, and second, they fail to model the inherent resilience in a circuit that keeps it functioning even after a wire fails. This work overcomes both limitations. For a single wire, our probabilistic analysis encapsulates known realities about CuDD wires, e.g., that some regions of these wires are more susceptible to EM than others, and that void formation/growth show statistical behavior. We apply these ideas to the analysis of on-chip power grids and demonstrate the inherent robustness of these grids that maintains supply integrity under some EM failures.

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

This paper presents an efficient algorithm for the placement of power supply pads in flip-chip packaging for high-performance VLSI circuits. The placement problem is formulated as a mixed-integer linear program (MILP), subject to the constraints on mean-time-to-failure (MTTF) for the pads and the voltage drop in the power grid. To improve the performance of the optimizer, the pad placement problem is solved based on the divide-and-conquer principle, and the locality properties of the power grid are exploited by modeling the distant nodes and sources coarsely, following the coarsening stage in multi-grid-like approach. An accurate electromigration (EM) model that captures current crowding and Joule heating effects is developed and integrated with our C4 placement approach. The effectiveness of the proposed approach is demonstrated on several designs adapted from publicly released benchmarks.

In nanometer technologies, shallow trench isolation (STI) induces thermal residual stress in active silicon due to post-manufacturing thermal mismatch. The amount of STI around an active region depends on the layout of the design, and the biaxial stress due to STI results in placement-dependent variations in the the transistor mobilities and threshold voltages of the active devices. An analytical model based on inclusion theory in micromechanics is employed to accurately estimate the stresses and the strains induced in the active region by the surrounding STI in the layout. The induced changes in mobility and threshold voltage changes are computed at the transistor level, and then propagated to the gate and circuit levels to predict circuit-level delay and leakage power for a given placement.

This article presents a novel scheme for saving architectural power by mitigating delay degradations in digital circuits due to bias temperature instability (BTI), inspired by the notion of human circadian rhythms. The method works in two alternating phases. In the first, the compute phase, the circuit is awake and active, operating briskly at a greater-than-nominal supply voltage which causes tasks to complete more quickly. In the second, the idle phase, the circuit is power-gated and put to sleep, enabling BTI recovery. Since the wakeful stage works at an elevated supply voltage, it results in greater aging than operation at the nominal supply voltage, but the sleep state involves a recovery that more than compensates for this differential. We demonstrate, both at the circuit and the architectural levels, that at about the same performance, this approach can result in appreciable BTI mitigation, thus reducing the guardbands necessary to protect against aging, which results in power savings over the conventional design.

The process of power network analysis during VLSI chip design is inherently iterative. It is very common for the designer to make many small perturbations to an otherwise complete design, to enhance the design or fix design violations. Considering the size of the modern chips, updating the solution for the changed network can be a computationally intensive task. In this paper we propose an efficient and accurate incremental solver that utilizes the backward random walks to identify the region of influence of the perturbation. The solution of the network is updated for the significantly smaller region only. The proposed algorithm is capable of handling consecutive perturbations without any degradation. The experimental results show speedups of up to 13.7× as compared to a complete solution.

This paper focuses on hot carrier (HC) effects in large scale digital circuits and proposes a scalable method for analyzing circuit-level delay degradations. At the transistor level, a multi-mode energy-driven model for nanometer technologies is employed. At the logic cell level, a methodology that captures the aging of a device as a sum of device age gains per signal transition is described, and the age gain is characterized using SPICE simulation. At the circuit level, the cell-level characterizations are used in conjunction with probabilistic methods to perform fast degradation analysis. The proposed analysis method is validated by Monte Carlo simulation on various benchmark circuits, and is proved to be accurate, efficient and scalable.

This paper presents a novel scheme for mitigating delay degradations in digital circuits due to bias temperature instability (BTI). The method works in two alternating phases. In the first, a greater-than-nominal supply voltage, Vdd,gis used, which causes a task to complete more quickly but causes greater aging than the nominal supply voltage, Vdd,n. In the second, the circuit is power-gated, enabling the BTI recovery phase. We demonstrate, both at the circuit and the architectural levels, that this approach can significantly mitigate aging for a small performance penalty.

Circuit degradation due to bias temperature instability (BTI) can lead to timing failures in digital circuits. We develop variable latency unit (VLU) based BTI-aware designs, with a novel scheme for multioutput hold logic implementation for VLUs. A key observation is the identification and exploitation of specific supersetting patterns in the two-dimensional space of frequency and aging of the circuit. The multioutput hold logic scheme is used in conjunction with an adaptive body bias framework to achieve high performance, allowing the design to be easily incorporated in traditional synthesis flows. As compared to conventional combinational BTI-resilience scheme, our design achieves an area reduction of 9.2%, with a significant throughput enhancement of 30.0%.

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

In the period of extreme CMOS scaling, reliability issues are becoming a critical problem. These problems include issues related to device reliability, in the form of bias temperature instability, hot carrier injection, time-dependent dielectric breakdown of gate oxides, as well as interconnect reliability concerns such as electromigration and TSV stress in 3D integrated circuits. This tutorial surveys these effects, and discusses methods for mitigating them at all levels of design.

In 3D ICs, TSV-induced thermal residual stress impacts transistor mobilities due to the piezoresistive effect. This phenomenon is coupled with other temperature effects on transistor parameters that are seen even in the absence of TSVs. In this paper, analytical models are developed to holistically represent the effect of thermally-induced variations on circuit timing. The analysis is based on a semianalytic formulation that is demonstrated to accurately capture the biaxial nature of TSV stress and its effect on delay.

On-chip switched-capacitor (SC) DC-DC converters have recently been demonstrated in silicon for high-performance applications such as multicore processors. The efficiency of the power delivery system using SC converters is a major concern, but this has not been addressed at the system level in prior research. This work develops models for the efficiency of such a system as a function of size and layout of the SC converters, and proposes an approach to optimize the size and layout of the SC converter to minimize power loss. The efficiency of these techniques is demonstrated on both homogenous and heterogenous multicore chips.

Network-on-Chips (NoCs) in heterogeneous systems containing both CPU and GPU cores must be designed to satisfy the performance requirements of both latency-sensitive CPU traffic and throughput-intensive GPU traffic. DVFS and adaptive routing can potentially improve NoC energy and performance efficiency. We further notice that GPU traffic can sometimes tolerate a slack defined as the number of cycles a packet can be delayed without causing performance penalty. In this work, we take advantage of the slack in GPU packets to route packets through non-minimal path, so that routers can operate at a lower frequency without suffering performance penalty.

Accurate and efficient thermal analysis for a VLSI chip is crucial, both for sign-off reliability verification and for design-time circuit optimization. To determine an accurate temperature profile, it is important to simulate a die together with its thermal mounts: this requires solving Poisson's equation on a nonrectangular 3D domain. This article presents a class of eigendecomposition-based Fast Poisson Solvers (FPS) for chip-level thermal analysis. We start with a solver that solves a rectangular 3D domain with mixed boundary conditions in O( N ⋅ log N ) time, where N is the dimension of the finite difference matrix. Then we reveal, for the first time in the literature, a strong relation between fast Poisson solvers and Green-function-based methods. Finally, we propose an FPS method that leverages the preconditioned conjugate gradient method to solve nonrectangular 3D domains efficiently. We demonstrate this approach on thermal analysis of an industrial microprocessor, showing accurate results verified by a commercial tool, and that it solves a system of dimension 4.54e6 in only 13 conjugate gradient iterations, with a runtime of 65 seconds, a 15X speedup over the popular ICCG solver.

Three-dimensional (3D) silicon integration technologies have provided new opportunities for Network-on-Chip (NoC) architecture design in Systems-on-Chip (SoCs). In this article, we consider the application-specific NoC architecture design problem in a 3D environment. We present an efficient floorplan-aware 3D NoC synthesis algorithm based on simulated allocation (SAL), a stochastic method for traffic flow routing, and accurate power and delay models for NoC components. We demonstrate that this method finds greatly improved solutions compared to a baseline algorithm reflecting prior work. To evaluate the SAL method, we compare its performance with the widely used simulated annealing (SA) method and show that SAL is much faster than SA for this application, while providing solutions of very similar quality. We then extend the approach from a single-path routing to a multipath routing scheme and explore the trade-off between power consumption and runtime for these two schemes. Finally, we study the impact of various factors on the network performance in 3D NoCs, including the TSV count and the number of 3D tiers. Our studies show that link power and delay can be significantly improved when moving from a 2D to a 3D implementation, but the improvement flattens out as the number of 3D tiers goes beyond a certain point.

Gate oxide breakdown is an important reliability issue that has been widely studied at the individual transistor level, but has seen very little work at the circuit level. We first develop an analytic closed-form model for the failure probability (FP) of a large digital circuit due to this phenomenon. The new approach accounts for the fact that not every breakdown leads to circuit failure, and shows a 4.8-6.2× relaxation of the predicted lifetime with respect to the pessimistic area-scaling method for nominal process parameters. Next, we extend the failure analysis to include the effect of process variations, and derive that the circuit FP at a specified time instant has a lognormal distribution due to process variations. Circuits with variations show 19%-24% lifetime degradation against nominal analysis and 4.7-5.9× lifetime relaxation against area-scaling method under variations. Both parts of our work are verified by extensive simulations and proved to be effective, accurate and scalable.

State-of-the-art timing tools are built around the use of current source models (CSMs), which have proven to be fast and accurate in enabling the analysis of large circuits. As circuits become increasingly exposed to process and temperature variations, there is a strong need to augment these models to account for thermal effects and for the impact of adaptive body biasing, a compensatory technique that is used to overcome on-chip variations. However, a straightforward extension of CSMs to incorporate timing analysis at multiple body biases and temperatures results in unreasonably large characterization tables for each cell. We propose a new approach to compactly capture body bias and temperature effects within a mainstream CSM framework. Our approach features a table reduction method for compaction of tables and a fast and novel waveform sensitivity method for timing evaluation under any body bias and temperature condition. On a 45-nm technology, we demonstrate high accuracy, with mean errors of under 4% in both slew and delay as compared to HSPICE. We show a speedup of over five orders of magnitude over HSPICE and a speedup of about$92\times$over conventional CSMs.

Gate oxide breakdown is a major cause of reliability failures in future nanometer-scale CMOS designs. This paper develops an analysis technique that can predict the probability of a functional failure in a large digital circuit due to this phenomenon. Novel features of the method include its ability to account for the inherent resilience in a circuit to a breakdown event, while simultaneously considering the impact of process variations. Based on standard process variation models, at a specified time instant, this procedure determines the circuit failure probability as a lognormal distribution. Experimental results demonstrate this approach is accurate compared with Monte Carlo simulation, and gives 4.7-5.9× better lifetime prediction over existing methods that are based on pessimistic area-scaling models.

A floorplanning has a potential to reduce chip temperature due to the conductive nature of heat. If floorplan optimization, which is usually based on simulated annealing, is employed to reduce temperature, its evaluation should be done extremely fast with high accuracy. A new thermal index, named thermal signature, is proposed. It approximates the temperature calculation, which is done by taking the product of Green's function and power density integrated over space. The correlation coefficient between thermal signature and temperature is shown to be quite high, more than 0.7 in many examples. A floorplanner that uses thermal signature is constructed and assessed using real design examples in 32-nm technology. It produces a floorplan whose maximum temperature is 11.4°C smaller than that of standard floorplan, on average, in reasonable amount of runtime.

The analysis of on-chip power grids requires the solution of large systems of linear algebraic equations with specific properties. Lately, a class of random walk based solvers have been developed that are capable of handling these systems: these are especially useful when only a small part of the original system must be solved. These methods build a probabilistic network that corresponds to the power grid. However, this construction does not fully exploit the properties of the problem and can result in large variances for the random walks, and consequently, large run times. This paper presents an efficient methodology, inspired by the idea of importance sampling, to improve the runtime of random walk based solvers. Experimental results show significant speedups, as compared to naive random walks used by the state-of-the-art random walk solvers.

In recent years, chip multiprocessors (CMP) have emerged as a solution for high-speed computing demands. However, power dissipation in CMPs can be high if numerous cores are simultaneously active. Dynamic voltage and frequency scaling (DVFS) is widely used to reduce the active power, but its effectiveness and cost depends on the granularity at which it is applied. Per-core DVFS allows the greatest flexibility in controlling power, but incurs the expense of an unrealistically large number of on-chip voltage regulators. Per-chip DVFS, where all cores are controlled by a single regulator overcomes this problem at the expense of greatly reduced flexibility. This work considers the problem of building an intermediate solution, clustering the cores of a multicore processor into DVFS domains and implementing DVFS on a per-cluster basis. Based on a typical workload, we propose a scheme to find similarity among the cores and cluster them based on this similarity. We also provide an algorithm to implement DVFS for the clusters, and evaluate the effectiveness of per-cluster DVFS in power reduction.

Negative bias temperature instability (NBTI) in pMOS transistors has become a major reliability concern in present-day digital circuit design. Further, with the recent introduction of Hf-based high-k dielectrics for gate leakage reduction, positive bias temperature instability (PBTI), the dual effect in nMOS transistors, has also reached significant levels. Consequently, designs are required to build in substantial guardbands in order to guarantee reliable operation over the lifetime of a chip, and these involve large area and power overheads. In this paper, we begin by proposing the use of adaptive body bias (ABB) and adaptive supply voltage (ASV) to maintain optimal performance of an aged circuit, and demonstrate its advantages over a guard banding technique such as synthesis. We then present a hybrid approach, utilizing the merits of both ABB and synthesis, to ensure that the resultant circuit meets the performance constraints over its lifetime, and has a minimal area and power overhead, as compared with a nominally designed circuit.

It is common for a designer to consider making several small changes to a power grid, corresponding to ¿what if¿ scenarios, in an attempt to improve its performance. To evaluate the effects of each incremental change, the circuit must go through incremental analysis. This paper presents a computationally efficient and accurate method for fast and accurate incremental analysis using random walks to identify a region of influence (RoI) of a change, so that this RoI can then be analyzed by any other solver. Our experimental results demonstrate the accuracy and computational efficiency of this method.

With the increasing use of adaptive body biases in high-performance designs, it has become necessary to build timing models that can include these effects. State-of-the-art timing tools use current source models (CSMs), which have proven to be fast and accurate. However, a straightforward extension of CSMs to incorporate multiple body biases results in unreasonably large characterization tables for each cell. We propose a new approach to compactly capture body bias effects within a mainstream CSM framework. Our approach features a table reduction method for compact storage, and a fast and novel waveform sensitivity method for timing evaluation. On a 45 nm technology, we demonstrate high accuracy, with worst-case errors of under 5% in both slew and delay as compared to HSPICE. We show a speedup of over five orders of magnitude over HSPICE and almost 70× over conventional CSMs.

At 65nm and below, Rapid Thermal Annealing (RTA) makes a significant contribution to manufacturing process variations, degrading the parametric yield. RTA-induced variability strongly depends on circuit layout patterns, particularly the distribution of the density of the Shallow Trench Isolation (STI) regions. In this work, we investigate a two-step approach to reduce the impact of RTA-induced variations. We first solve a floorplanning problem that aims to reduce the RTA variations by evening out the STI density distribution. Next, we insert dummy polysilicon fills to further improve the uniformity of the STI density. Experimental results show that our floorplanner can reduce the global RTA variations by 39% and the local variations by 29% on average with low overhead compared to a traditional floorplanner, and the proposed dummy fill algorithm can further reduce the RTA variations to negligible amounts. Moreover, when inserting dummy fills, for the layouts obtained by our floorplanner, on average, 24% fewer dummy polysilicon fills are inserted, as compared to the results from a traditional floorplanner.

Three-dimensional (3D) silicon integration technologies have provided new opportunities for Network-on-Chip (NoC) architecture design in Systems-on-Chip (SoCs). In this paper, we consider the application-specific NoC architecture design problem in a 3D environment. We present an efficient floorplan-aware 3D NoC synthesis algorithm, based on simulated allocation, a stochastic method for traffic flow routing, and accurate power and delay models for NoC components. We demonstrate that this method finds greatly improved topologies for various design objectives such as NoC power (average savings of 34%), network latency (average reduction of 35%) and chip temperature (average reduction of 20%).

Accurate and efficient thermal analysis for a VLSI chip is crucial, both for sign-off reliability verification and for design-time circuit optimization. To determine an accurate temperature profile, it is important to simulate a die together with its thermal mounts: this requires solving Poisson's equation on a non-rectangular 3D domain. This paper presents a class of eigendecomposition-based fast Poisson solvers (FPS) for chiplevel thermal analysis. We start with a solver that solves a rectangular 3D domain with mixed boundary conditions in O(NlogN) time, where N is the dimension of the finite-difference matrix. Then we reveal, for the first time in the literature, a strong relation between fast Poisson solvers and Green-function-based methods. Finally, we propose an FPS method that leverages the preconditioned conjugate gradient method to solve non-rectangular 3D domains efficiently. We demonstrate that this approach solves a system of dimension 5.33e6 in only 11 Conjugate Gradient iterations, with a runtime of 171 seconds, a 6X speedup over the popular ICCG solver.

Three-dimensional (3D) technologies have the potential to provide major benefits to integrated circuit design. An advanced 3D chip consists of multiple tiers of two-dimensional (2D) circuitry, stacked vertically over each other, with very small intertier distances. Such technologies offer numerous benefits over conventional 2D designs. First, by stacking multiple 2D tiers, it is possible to increase the number of transistors within a package: in other words, 3D offers increased integration using an approach that is orthogonal to device scaling. Second, the small intertier distances imply that the histogram of wire length distributions is significantly altered, enabling critical wires to be made very short. Third, 3D offers opportunities for integrating heterogeneous technologies into a single chip, enabling much more versatility in the types of chips we can build.Fundamentally, the shift from 2D to 3D is topological, and holds numerous physical design challenges. In addition, several effects that were critical in 2D are further accentuated in 3D. For example, the increased current required by a 3D stack, as compared to a 2D chip with the same footprint, brings forth twin problems: how do we get the current in (i.e., perform reliable power delivery), and how do we get the heat out (i.e., perform thermal management)? Solutions to problems such as these can come from the architectural level and go down to much finer granularities. This talk overviews prior work in the area, and surveys the challenges and opportunities ahead.

This paper presents a router that minimizes the amount of dummy fill necessary to satisfy the requirements for chemical-mechanical polishing (CMP). The algorithm uses a greedy strategy and effective cost functions to control the maximal effective pattern density during routing. On a standard set of benchmark circuits, our CMP-aware router can reduce the required dummy fill by 22.0% on average, and up to 41.5%, as compared to the CMP-unaware case. In comparison with another CMP-aware routing approach, our algorithm is demonstrated to reduce the amount of dummy fill by 14.1% on average, and up to 23.6%, over the benchmarks.

In nanoscale technologies that experience large levels of process variation, post-silicon adaptation is an important step in circuit design. These adaptation techniques are often based on measurements of a replica of the nominal critical path, whose variations are intended to reflect those of the entire circuit after manufacturing. For realistic circuits, where the number of critical paths can be large, the notion of using a single critical path is too simplistic. This paper overcomes this problem by introducing the idea of synthesizing a representative critical path (RCP), which captures these complexities of the variations. We first prove that the requirement on the RCP is that it should be highly correlated with the circuit delay. Next, we present three novel algorithms to automatically build the RCP. Our experimental results demonstrate that over a number of samples of manufactured circuits, the delay of the RCP captures the worst case delay of the manufactured circuit. The average prediction error of all circuits is shown to be below 2.8% for all three approaches. For both our approach and the critical path replica method, it is essential to guard-band the prediction to ensure pessimism: on average our approach requires a guard band 31% smaller than for the critical path replica method.

Negative bias temperature instability (NBTI) in PMOS transistors has become a major reliability concern in present-day digital circuit design. Further, with the recent usage of Hf-based high-k dielectrics for gate leakage reduction, positive bias temperature instability (PBTI), the dual effect in NMOS transistors has also reached significant levels. Consequently, designers are required to build in substantial guard-bands into their designs, leading to large area and power overheads, in order to guarantee reliable operation over the lifetime of a chip. We propose a guard-banding technique based on adaptive body bias (ABB) and adaptive supply voltage (ASV), to recover the performance of an aged circuit, and compare its merits over previous approaches.

The enhanced packing densities facilitated by 3D integrated circuit technology also has an unwanted side-effect, in the form of increasing the amount of current per unit footprint of the chip, as compared to a 2D design. This has ramifications on two critical issues: firstly, it means that more heat is generated per unit footprint, potentially leading to thermal problems, and secondly, more current must be supplied per package pin, leading to possible power delivery bottlenecks. This paper presents an overview of the challenges and solutions in the domain of addressing these two issues in 3D integrated circuits.

In three-dimensional (3D) chips, the amount of supply current per package pin is significantly more than in two-dimensional (2D) designs. Therefore, the power supply noise problem, already a major issue in 2D, is even more severe in 3D. CMOS decoupling capacitors (decaps) have been used effectively for controlling power grid noise in the past, but with technology scaling, they have grown increasingly leaky. As an alternative, metal-insulator-metal (MIM) decaps, with high capacitance densities and low leakage current densities, have been proposed. In this paper, we explore the tradeoffs between using MIM decaps and traditional CMOS decaps, and propose a congestion-aware 3D power supply network optimization algorithm to optimize this tradeoff. The algorithm applies a sequence-of-linear-programs based method to find the optimum tradeoff between MIM and CMOS decaps. Experimental results show that power grid noise can be more effectively optimized after the introduction of MIM decaps, with lower leakage power and little increase in the routing congestion, as compared to a solution using CMOS decaps only.

Several approaches to post-silicon adaptation require feedback from a replica of the nominal critical path, whose variations are intended to reflect those of the entire circuit after manufacturing. For realistic circuits, where the number of critical paths can be large, the notion of using a single critical path is too simplistic. This paper overcomes this problem by introducing the idea of synthesizing a representative critical path (RCP), which captures these complexities of the variations. We first prove that the requirement on the RCP is that it should be highly correlated with the circuit delay. Next, we present two novel algorithms to automatically build the RCP. Our experimental results demonstrate that over a number of samples of manufactured circuits, the delay of the RCP captures the worst case delay of the manufactured circuit. The average prediction error of all circuits is shown to be below 2.8% for both approaches. For both our approach and the critical path replica method, it is essential to guard-band the prediction to ensure pessimism: our approach requires a guard band 30% smaller than for the critical path replica method.

Due to increased variability trends in nanoscale integrated circuits, statistical circuit analysis and optimization has become essential. While statistical timing analysis has an important role to play in this process, it is equally important to develop die-specific delay prediction techniques using postsilicon measurements. We present a novel method for postsilicon delay analysis. We gather data from a small number of on-chip test structures, and combine this information with presilicon statistical timing analysis to obtain narrow die-specific timing probability density function (PDF). Experimental results show that for the benchmark suite being considered, taking all parameter variations into consideration, our approach can obtain a PDF whose standard deviation is 79.0% smaller, on average, than the statistical timing analysis result. The accuracy of the method defined by our metric is 99.6% compared to Monte Carlo simulation. The approach is scalable to smaller test structure overheads and can still produce acceptable results.

With ever-shrinking device geometries, process variations play an increased role in determining the delay of a digital circuit. Under such variations, a gate may lie on the critical path of a manufactured die with a certain probability, called the criticality probability. In this paper, we present a new technique to compute the statistical criticality information in a digital circuit under process variations by linearly traversing the edges in its timing graph and dividing it into ldquozones.rdquo We investigate the sources of error in using tightness probabilities for criticality computation with Clark's statistical maximum formulation. The errors are dealt with using a new clustering-based pruning algorithm which greatly reduces the size of circuit-level cutsets improving both accuracy and runtime over the current state of the art. On large benchmark circuits, our clustering algorithm gives about a 250times speedup compared with a pairwise pruning strategy with similar accuracy in results. Coupled with a localized sampling technique, errors are reduced to around 5% of Monte Carlo simulations with large speedups in runtime.

Due to recent advances in microfluidics technology, digital microfluidic biochips and their associated computer-aided-design problems have gained much attention, most of which has been devoted to direct-addressing biochips. In this paper, we solve the droplet routing problem under the more scalable cross-referencing biochip paradigm. We propose the first droplet routing algorithm that directly solves the problem of routing. We first present an optimal basic integer-linear-programming (ILP) formulation. Due to its complexity, we also propose a progressive-ILP scheme to determine the locations of droplets at each time step. Simulation results demonstrate the efficiency and effectiveness of our algorithm.

Since process and environmental variations can no longer be ignored in high-performance microprocessor designs, it is necessary to develop techniques for computing the sensitivities of the timing slacks to parameter variations. This additional slack information enables designers to examine paths that have large sensitivities to various parameters: such paths are not robust, even though they may have large nominal slacks and may hence be ignored in traditional timing analysis. We present a framework for block-based timing analysis, where the parameters are specified as ranges -- rather than statistical distributions which are hard to know in practice. We show that our approach -- which scales well with the number of processors -- is accurate at all values of the parameters within the specified bounds, and not just at the worst-case corner. This allows the designers to quantify the robustness of the design at any design point. We validate our approach on circuit blocks extracted from a commercial 45nm microprocessor.

Faced with continually coping with Moore's Law, computer-aided design (CAD) for integrated circuits is used to facing challenges in our ever-evolving design problem. Increasing device complexity is a perennial challenge and has led to several discontinuities in design methodology. Over the last decade deep submicron physical effects have significantly complicated the design process and required new efforts in design for manufacturability. With the emergence of multicore and manycore microprocessor systems we face a new type of challenge: Not only will our design object (the microprocessor systems themselves) take another leap in complexity, but for the first time in our industry's history we will need to fundamentally change the way we design and implement our software solutions as well. In this panel a broad set of representatives at the front lines of addressing this challenge will outline how they plan to respond. Representative questions to the panelists include:

Due to recent advances in microfluidics technology, digital microfluidic biochips and their associated CAD problems have gained much attention, most of which has been devoted to direct-addressing biochips. In this paper, we solve the droplet routing problem under the more scalable cross-referencing biochip paradigm, which uses row/column addressing scheme to activate electrodes. We propose the first droplet routing algorithm that directly solves the problem of routing in cross-referencing biochips. The main challenge of this type of biochips is the electrode interference which prevents simultaneous movement of multiple droplets. We first present a basic integer linear programming (ILP) formulation to optimally solve the droplet routing problem. Due to its complexity, we also propose a progressive ILP scheme to determine the locations of droplets at each time step. Experimental results demonstrate the efficiency and effectiveness of our progressive ILP scheme on a set of practical bioassays.

With aggressive reductions in feature sizes and the integration of multiple functionalities on the same die, bottlenecks due to I/O pin limitations have become a critical issue in today's VLSI designs, especially for 3D IC technologies. To alleviate the pin limitation problem, a stacked-Vdd circuit paradigm has recently been proposed in the literature. However, for a circuit designed using this paradigm, a significant amount of power may be wasted if modules are not carefully assigned to different Vdd domains. In this article, we present a partition-based algorithm for efficiently assigning modules at the floorplanning level, so as to reuse currents between Vdd domains and minimize the power wasted during the operation of the circuit. Experimental results on both 3D and 2D ICs show that compared with assigning modules to different Vdd domains using enumeration and simulated annealing, our algorithm can generate circuits with competitive power and IR noise performance, while being orders of magnitude faster.

Technology mapping is a crucial step in the synthesis of digital designs and can be used to obtain mapped circuits that are optimized for delay or area. Current tree-based mapping algorithms break the circuit into individual trees and map these optimally. However, these solutions are not globally optimal. This paper presents a new approach to delay-optimal mapping based on the principle of logical effort. This algorithm maps individual trees such that the solution of the entire circuit is optimal. In traditional technology mapping, the best match for a gate depends on the load being driven, which is not known at the matching stage. Current algorithms handle this situation by generating matches for all loads and selecting the best match at a later stage. This strategy works for fan-out-free circuits but breaks down at multiple fan-out points where each fan-out has to be sized correctly, depending on its criticality. This can have a significant impact on the selection of matches as well but has not been adequately addressed in the published literature. We refer to the correct sizing of branches of multiple fan-out points as the load-distribution problem, which is formally defined and solved in the context of technology mapping in this paper. The effect of the new logical effort-based mapping algorithm, combined with correct sizing of individual branches of a multiple fan-out point, leads to implementations that are closer to the global optimum. On the average, benchmark circuits mapped using our approach are 39.45% faster and 32.77% smaller than those obtained using SIS.

We present an efficient optimization scheme for gate sizing in the presence of process variations. Our method is a worst case design scheme; however, it reduces the pessimism involved in traditional worst case methods by incorporating the effect of spatial correlations in the optimization procedure. The pessimism reduction is achieved by employing a bounded model for the parameter variations in the form of anuncertaintyellipsoid, which captures the spatial correlation information between the physical parameters. The use of the uncertainty ellipsoid, along with the assumption that the random variables corresponding to the varying parameters follow a multivariate Gaussian distribution, enables us to size the circuits for a specified timing yield. Using a posynomial delay model, the delay constraints are modified to incorporate uncertainty in the transistor widths and effective channel lengths due to the process variations. The resulting optimization problem is relaxed to a geometric program and is efficiently solved using convex optimization tools. The effectiveness of our robust gate sizing scheme is demonstrated by applying the optimization on the ISCAS'85 benchmark circuits and testing the optimized circuits by performing Monte Carlo simulations to model the process variations. Experimental results show that the timing yield of the robustly optimized circuits improves manifold over the traditional deterministically sized circuits. For the same transistor area, the circuits sized by our robust optimization approach have, on average, 12% fewer timing violations as compared to the gate sizing solutions that are obtained via the traditional deterministically based guard-banding method.

We propose a scalable efficient parameterized block-based statistical static timing analysis (SSTA) algorithm incorporating both Gaussian and non-Gaussian parameter distributions, capturing spatial correlations using a grid-based model. As a preprocessing step, we employ an independent component analysis to transform the set of correlated non-Gaussian parameters to a basis set of parameters that are statistically independent. Given the moments of the variational parameters, we use a Pade acute-approximation-based moment-matching scheme to generate the distributions of the random variables representing the signal arrival times and preserve correlation information by propagating arrival times in a canonical form. Our SSTA procedure is able to generate the circuit delay distributions with reasonably small prediction errors. For the ISCAS89 benchmark circuits, as compared to Monte Carlo simulations, we obtain average errors of 0.99%, 2.05%, 2.33%, and 2.36%, respectively, in the mean, standard deviation, and 5% and 95% quantile points of the circuit delay. Experimental results show that our procedure can handle as many as 256 correlated non-Gaussian variables in about 5 min of runtime. For a circuit with |G| gates and a layout with g spatial correlation grids, the complexity of our approach is O(g|G|) .

This paper presents a statistical leakage estimation method for FinFET devices considering the unique width quantization property. Monte Carlo simulations show that the conventional approach underestimates the average leakage current of FinFET devices by as much as 43% while the proposed approach gives a precise estimation with an error less than 5%. Design example on subthreshold circuits shows the effectiveness of the proposed method.

Subthreshold circuit designs have been demonstrated to be a successful alternative when ultra-low power consumption is paramount. However, the characteristics of MOS transistors in the subthreshold region are significantly different from those in strong inversion. This presents new challenges in design optimization, particularly in complex gates with stacks of transistors. In this paper, we present a framework for choosing the optimal transistor stack sizing factors in terms of current drivability for subthreshold designs. We derive a closed-form solution for the correct sizing of transistors in a stack, both in relation to other transistors in the stack, and to a single device with equivalent current drivability. Simulation results show that our framework provides a performance benefit ranging up to more than 10% in certain critical paths.

With continued scaling into the sub-90-nm regime, the role of process, voltage, and temperature (PVT) variations on the performance of VLSI circuits has become extremely important. These variations can cause the delay and the leakage of the chip to vary significantly from their expected values, thereby affecting the yield. Circuit designers have proposed the use of threshold voltage modulation techniques to pull back the chip to the nominal operational region. One such scheme, known as adaptive body bias (ABB), has become extremely effective in ensuring optimal performance or leakage savings. Our work provides a means to efficiently compute the body bias voltages required for ensuring high performance operation in gigascale systems. We provide a computer-aided design (CAD) perspective for determining the exact amount of bias voltages that can compensate both temperature and process variations. Mathematical models for delay and leakage based on minimal tester measurements are built, and a nonlinear optimization problem is formulated to ensure highest frequency operation under all conditions, and thereby minimize the overall circuit leakage. Three different algorithms are presented and their accuracies and runtimes are compared. The algorithms have been applied to a wide range of process and temperature corners, for a 65- and 45-nm technology node-based process. A suitable implementation mechanism has also been outlined.

Thermal problems and limitations on interlayer via densities are important design constraints on three-dimensional integrated circuits (3D ICs), and need to be considered during global and detailed placement. Analytical and partitioning-based techniques are developed to explore the tradeoff between wirelength, interlayer via counts, and thermal effects. This method allows wirelengths to be minimized for any desired interlayer via density and temperatures to be reduced while minimizing deleterious effects on wirelength and interlayer via counts. Wirelength reductions within 2% of the optimal can be achieved using 46% fewer interlayer vias. Temperatures can be reduced by about 20% with only 1% higher wirelengths and 10% more interlayer vias.

Statistical behavior of device leakage and threshold voltage shows a strong width dependency under microscopic random dopant fluctuation. Leakage estimation using the conventional square-root method shows a discrepancy as large as 45% compared to the real case because it fails to model the effective VT shift in the subthreshold region. This paper presents a width-dependent statistical leakage model with an estimation error less than 5%. Design examples on SRAMs and domino circuits demonstrate the significance of the proposed model.

Negative Bias Temperature Instability (NBTI) in PMOS transistors has become a major reliability concern in nanometer scale design, causing the temporal degradation of the threshold voltage of the PMOS transistors, and the delay of digital circuits. A novel method to characterize the delay of every gate in the standard cell library, as a function of the signal probability of each of its inputs, is developed. Accordingly, a technology mapping technique that incorporates the NBTI stress and recovery effects, in order to ensure optimal performance of the circuit, during its entire life-time, is presented. Our technique, demonstrated over 65nm benchmarks shows an average of 10% area recovery, and 12% power savings, as against a pessimistic method that assumes constant stress on all PMOS transistors in the design.

Due to increased variability trends in nanoscale integrated circuits, statistical circuit analysis has become essential. We present a novel method for post-silicon analysis that gathers data from a small number of on-chip test structures, and combines this information with pre-silicon statistical timing analysis to obtain narrow, die-specific, timing PDFs. Experimental results show that for the benchmark suite being considered, taking all parameter variations into consideration, our approach can get a PDF with the standard deviation 83.5% smaller on average than the SSTA result. The approach is scalable to smaller test structure overheads.

This paper proposes a library-free technology mapping algorithm to reduce delay in combinational circuits. The algorithm reduces the overall number of series transistors through the longest path, considering that each cell network has to obey to a maximum admitted chain. The number of series transistors is computed in a Boolean way, reducing the structural bias. The mapping algorithm is performed on a Directed Acyclic Graph (DAG) description of the circuit. Preliminary results for delay were obtained through SPICE simulations. When compared to the SIS technology mapping, the proposed method shows significant delay reductions, considering circuits mapped with different libraries.

Unlike conventional electronic circuits, where transistors are placed in a single plane, three-dimensional (3D) integrated circuits utilize multiple tiers of active devices, placed one above another. Recent advances in processing technologies have brought these technologies into the realm of achievable reality, and today, several academic, corporate and government labs run fabrication processes for building 3D integrated circuits. The move to the third dimension immediately provides increased packing densities per unit footprint, and provides a path for maintaining Moore's law rates of growth at the system level, even as questions are being raised about the sustainability of device-level scaling. 3D circuits offer numerous other advantages as well, including the potential for reduced interconnect lengths, and the ability to easily integrate heterogeneous technologies on multiple tiers into a single package.This new paradigm brings forth a number of novel and interesting challenges, and raises the necessity for novel design and CAD techniques. A direct translation of a 2D design to 3D can lead to a suboptimal implementation that does not fully exploit the power of 3D, and 3D-specific approaches are essential. At the most fundamental level, 3D circuit design is a physical design problem; therefore, new methods for floorplanning, placement and routing must be developed within this paradigm. These techniques must work within the additional degrees of freedom as well as the new constraints imposed by this technology, such as restrictions on interlayer vias, as well as circuit limitations due to increased packing densities, particularly those related to the challenges of heat removal and power delivery.

Retiming, c-slow retiming and recycling are different transformations for the performance optimization of sequential circuits. For retiming and c-slow retiming, different models that provide exact solutions have already been proposed. An exact model for recycling was yet unknown. This paper presents a general formulation that covers the combination of the three schemes for performance optimization. It provides an exact model based on integer linear programming that resorts to the structural theory of marked graphs. A set of experiments has been designed to show the benefits in performance obtained by combining retiming and recycling. The results also show the applicability of the method in large circuits.

We present a new linear time technique to compute criticality information in a timing graph by dividing it into “zones”. Errors in using tightness probabilities for criticality computation are dealt with using a new clustering based pruning algorithm which greatly reduces the size of circuitlevel cutsets. Our clustering algorithm gives a 150X speedup compared to a pairwise pruning strategy in addition to ordering edges in a cutset to reduce errors due to Clark’s MAX formulation. The clustering based pruning strategy coupled with a localized sampling technique reduces errors to within 5% of Monte Carlo simulations with large speedups in runtime.

This paper addresses the module assignment problem in pinlimited designs under the stacked-Vdd circuit paradigm. A partition-based algorithm is presented for efficiently assigning modules at the floorplanning level so as to reuse currents between the Vdd domains, and minimize the power wasted during the operation of the circuit. Experimental results on a DLX architecture show that compared with assigning modules to different Vdd rails using a bin-packing technique, the circuit generated by our algorithm has 32% lower wasted power, on average. In addition, experiments on a 3D IC example show that our module assignment approach is equally effective in reducing the power waste in 3D ICs.

No abstract available.

Recounts the career of Dr. Margarida F. Jacome, a Professor with the Department of Electrical and Computer Engineering, University of Texas (UT), Austin. Also includes recollections from her colleagues and students.

Due to technology scaling trends, the accurate and efficient calculations of the temperature distribution corresponding to a specific circuit layout and power density distribution will become indispensable in the design of high-performance very large scale integrated circuits. In this paper, we present three highly efficient thermal simulation algorithms for calculating the on-chip temperature distribution in a multilayered substrate structure. All three algorithms are based on the concept of the Green function and utilize the technique of discrete cosine transform. However, the application areas of the algorithms are different. The first algorithm is suitable for localized analysis in thermal problems, whereas the second algorithm targets full-chip temperature profiling. The third algorithm, which combines the advantages of the first two algorithms, can be used to perform thermal simulations where the accuracy requirement differs from place to place over the same chip. Experimental results show that all three algorithms can achieve relative errors of around 1% compared with that of a commercial computational fluid dynamic software package for thermal analysis, whereas their efficiencies are orders of magnitude higher than that of the direct application of the Green function method.

In this article, we present a method to analyze the total leakage current of a circuit under process variations, considering interdie and intradie variations as well as the effect of the spatial correlations of intradie variations. The approach considers both the subthreshold and gate tunneling leakage power, as well as their interactions. With process variations, each leakage component is approximated by a lognormal distribution, and the total chip leakage is computed as a sum of the correlated lognormals. Since the lognormals to be summed are large in number and have complicated correlation structures due to both spatial correlations and the correlation among different leakage mechanisms, we propose an efficient method to reduce the number of correlated lognormals for summation to a manageable quantity. We do so by identifying dominant states of leakage currents and taking advantage of the spatial correlation model and input states at the gates. An improved approach utilizing the principal components computed from spatially correlated process parameters is also proposed to further improve runtime efficiency. We show that the proposed methods are effective in predicting the probability distribution of total chip leakage, and that ignoring spatial correlations can underestimate the standard deviation of full-chip leakage power.

As VLSI technologies scale down, interconnect performance is greatly affected by crosstalk noise due to the decreasing wire separation and increased wire aspect ratio, and crosstalk has become a major bottleneck for design closure. The effectiveness of traditional buffering and spacing techniques for noise reduction is constrained by the limited available resources on chip. In this paper, we present a method for incorporating crosstalk reduction criteria into global routing under a broad power supply network paradigm. This method utilizes power/ground wires as shields between signal wires to reduce capacitive coupling, while considering the constraints imposed by limited routing and buffering resources. An iterative procedure is employed to route signal wires, assign supply shields, and insert buffers so that both buffer/routing capacity and signal integrity goals are met. In each iteration, shield assignment and buffer insertion are considered simultaneously via a dynamic programming-like approach. Our noise calculations are based on Devgan's metric, and our work demonstrates, for the first time, that this metric shows good fidelity on average. An effective noise margin inflation technique is also proposed to compensate for the pessimism of Devgan's metric. Experimental results on testcases with up to about 10000 nets point towards an asymptotic runtime that increases linearly with the number of nets. Our algorithm achieves noise reduction improvements of up to 53% and 28%, respectively, compared to methods considering only buffer insertion or only shield insertion after buffer planning.

Process variations and temperature variations can cause both the frequency and the leakage of the chip to vary significantly from their expected values, thereby decreasing the yield. Adaptive body bias (ABB) can be used to pull back the chip to the nominal operational region. We propose the use of this technique to counter temperature variations along with process variations. We present a CAD perspective for achieving process and temperature compensation using bidirectional ABB. Mathematical models are used to determine the exact amount of body bias required optimizing the delay and leakage, and an algorithmic flow that can be adopted for gigascale LSI systems is provided.

Fixed-die floorplanning is an important problem in the modern physical design process. An effective floorplanning algorithm is crucial to improving both the quality and the time-to-market of the design. In this paper, we present an analytical floorplanning algorithm that can be used to efficiently pack soft modules into a fixed die. The locations and sizing of the modules are simultaneously optimized so that a minimum total wire length is achieved. Experiments on the MCNC and GSRC benchmarks show that our algorithm can achieve above a 90% success rate with a 10% white space constraint in the fixed die, and the efficiency is much higher than that of the simulated annealing based algorithms for benchmarks containing a large number of modules.

With technology scaling, on-chip power densities are growing steadily, leading to the point where temperature has become an important consideration in the design of electrical circuits. This paper overviews several methods for the analysis and optimization of thermal effects in integrated circuits. Thermal analysis may be carried out efficiently through the use of finite difference methods, finite element methods, or Green function based methods, each of which provides different accuracy-computation tradeoffs, and the paper begins by surveying these. Next, we overview a restricted set of thermal optimization methods, specifically, placement techniques for thermal heat-spreading, and then we conclude by summarizing a set of future directions in electrothermal design.

3D integrated circuits (3D ICs) provide an attractive solution for improving circuit performance. Such solutions must be embedded in an electrothermally-conscious design methodology, since 3D ICs generate a significant amount of heat per unit volume. In this paper, we propose a temperature-aware 3D global routing algorithm with insertion of "thermal vias" and "thermal wires" to lower the effective thermal resistance of the material, thereby reducing chip temperature. Since thermal vias and thermal wires take up lateral routing space, our algorithm utilizes sensitivity analysis to judiciously allocate their usage, and iteratively resolve contention between routing and thermal vias and thermal wires. Experimental results show that our routing algorithm can effectively reduce the peak temperature and alleviate routing congestion.

Subthreshold circuit designs have been demonstrated to be a successful alternative when ultra-low power consumption is paramount. However, the characteristics of MOS transistors in the subthreshold regime are significantly different from those in strong-inversion. This presents new challenges in design optimization, particularly in complex gates with stacks of transistors. In this paper, we demonstrate a new optimal sizing scheme for subthreshold designs which takes these issues into account. We derive a closed-form solution for the correct sizing of transistors in a stack, both in relation to other transistors in the stack, and to a single transistor with equivalent current drivability. Experimental results show that our framework provides a performance improvement of up to 13.5% over the conventional logical effort method on ISCAS benchmark circuits, while one component circuit demonstrated an improvement of 33.1%.

We propose a scalable and efficient parameterized block-based statistical static timing analysis algorithm incorporating both Gaussian and non-Gaussian parameter distributions, capturing spatial correlations using a grid-based model. As a preprocessing step, we employ independent component analysis to transform the set of correlated non-Gaussian parameters to a basis set of parameters that are statistically independent, and principal components analysis to orthogonalize the Gaussian parameters. The procedure requires minimal input information: given the moments of the variational parameters, we use a Padé approximation-based moment matching scheme to generate the distributions of the random variables representing the signal arrival times, and preserve correlation information by propagating arrival times in a canonical form. For the ISCAS89 benchmark circuits, as compared to Monte Carlo simulations, we obtain average errors of 0.99% and 2.05%, respectively, in the mean and standard deviation of the circuit delay. For a circuit with G gates and a layout with g spatial correlation grids,the complexity of our approach is O(g G).

transistors has become a significant reliability concern in present day digital circuit design. With continued scaling, the effect of NBTI has rapidly grown in prominence, forcing designers to resort to a pessimistic design style using guard-banding. Since NBTI is strongly dependent on the time for which the PMOS device is stressed, different gates in a combinational circuit experience varying extents of delay degradation. This has necessitated a mechanism of quantizing the gate-delay degradation, to pave the way for improved design strategies. Our work addresses this issue by providing a procedure for determining the amount of delay degradation of a circuit due to NBTI. An analytical model for NBTI is derived using the framework of the Reaction-Diffusion model, and a mathematical proof for the widely observed phenomenon of frequency independence is provided. Simulations on ISCAS benchmarks under a 70nm technology show that NBTI causes a delay degradation of about 8 % in combinational logic based circuits after 10 years (� s). I.

Operating temperatures have become an important concern in high performance microprocessors. Floorplanning or block-level placement offers excellent potential for thermal optimization through better heat spreading between the blocks, but these optimizations can also impact the throughput of a microarchitecture, measured in terms of the number of instructions per cycle (IPC). In nanometer technologies, global buses can have multicycle delays that depend on the positions of the blocks, and it is important for a floorplanner to be microarchitecturally-aware to be sure that thermal and IPC considerations are appropriately balanced. This paper proposes a methodology for thermally-aware microarchitecture floorplanning. The approach models the interactions between the IPC and the temperature distribution, and incorporates both factors in the floorplanning cost function. Our approach uses transient modeling and optimizes both the peak and the average temperatures, and employs a design of experiments (DOE) based strategy, which effectively captures the huge exponential search space with a small number of cycle-accurate simulations. A comparison with a technique based on previous work indicates that the proposed approach results in good reductions both in the average and the peak temperatures for a range of SPEC benchmarks.

Due to the long simulation times of the reference input sets, microarchitects resort to alternative techniques to speed up cycle-accurate simulations. However, the reduction in the runtimes comes with an associated loss of accuracy in replicating the characteristics of the reference sets. In addition, the effect of these inaccuracies on the overall performance can vary across different microarchitecture optimizations or enhancements. In this work, we study and compare two such techniques, reduced input sets and statistical sampling, in the context of microarchitecture-aware floorplanning, a physical design stage, where the objective is to find an IPC-optimal global placement of the blocks of a microprocessor. The variation in the IPC results due the insertion of additional flip-flops on some across-chip wires of the processor that have multicycle delays in nanometer technology nodes. The objective of IPC-aware floorplanning is to minimize the amount of pipelining required by the system buses that are critical in determining the system performance. Our results indicate that, although the two techniques exhibit contrasting behavior in quantifying the criticality of bus latencies, the ensuing floorplanning optimization process results in almost identical performance improvements for both reduced input sets and sampling. The reason behind this is that, for discrete optimization problems such as IPC-aware floorplanning, a reasonably accurate relative ordering of performance bottlenecks is sufficient, absolute accuracy is not necessary.

Dramatic rises in the power consumption and integration density of contemporary systems-on-chip (SoCs) have led to the need for careful attention to chip-level thermal integrity. High temperatures or uneven temperature distributions may result not only in reliability issues, but also timing failures, due to the temperature-dependent nature of chip time-to-failure and delay, respectively. To resolve these issues, high-quality, accurate thermal modeling and analysis, and thermally oriented placement optimizations, are essential prior to tapeout. This paper first presents an overview of thermal modeling and simulation methods, such as finite-difference time domain, finite element, model reduction, random walk, and Green-function based algorithms, that are appropriate for use in placement algorithms. Next, two-dimensional and three-dimensional thermal-aware placement algorithms such as matrix-synthesis, simulated annealing, partition-driven, and force directed are presented. Finally, future trends and challenges are described

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

As thermal problems become more evident, new physical design paradigms and tools are needed to alleviate them. Incorporating thermal vias into integrated circuits (ICs) is a promising way of mitigating thermal issues by lowering the effective-thermal resistance of the chip. However, thermal vias take up valuable routing space, and therefore, algorithms are needed to minimize their usage while placing them in areas where they would make the greatest impact. With the developing technology of three-dimensional integrated circuits (3-D ICs), thermal problems are expected to be more prominent, and thermal vias can have a larger impact on them than in traditional two-dimensional integrated circuits (2-D ICs). In this paper, thermal vias are assigned to specific areas of a 3-D IC and used to adjust their effective-thermal conductivities. The method, which uses finite-element analysis (FEA) to calculate temperatures quickly during each iteration, makes iterative adjustments to these thermal conductivities in order to achieve a desired thermal objective and is general enough to handle a number of different thermal objectives such as achieving a desired maximum operating temperature. With this method, 49% fewer thermal vias are needed to obtain a 47% reduction in the maximum temperatures, and 57% fewer thermal vias are needed to obtain a 68% reduction in the maximum thermal gradients than would be needed using a uniform distribution of thermal vias to obtain these same thermal improvements. Similar results were seen for other thermal objectives, and the method efficiently achieves its thermal objective while minimizing the thermal-via utilization.

Routing congestion has become a serious concern in today's very-large-scale-integration designs. To address this, the authors propose a technology mapping algorithm that minimizes routing congestion under delay constraints in this paper. The algorithm employs a dynamic-programming framework in the matching phase to generate probabilistic congestion maps for all the matches. These congestion maps are then utilized to minimize routing congestion during the covering, which preserves the delay optimality of the solution using the notion of slack. Experimental results on benchmark circuits in a 100-nm technology show that the algorithm can improve track overflows significantly as compared to conventional technology mapping while satisfying delay constraints.

This paper presents an efficient heuristic algorithm, which employs successive partitioning and grid-refinement scheme, for designing the power distribution network of a chip. In an iterative procedure, the chip area is recursively bipartitioned, and the wire pitches and the wire widths of the power grid in the partitions are repeatedly adjusted to meet the voltage drop and current-density specifications. By using the macromodels of the power grid constructed in the previous levels of partitioning, the scheme ensures that a small global power grid system is simulated in each iteration. The idea is based on the notion that due to the locality properties of the power grid, the effects of distant nodes and sources can be modeled more coarsely than the nearby elements, and include practical methods that enhance the convergence of the iterative conjugate-gradient-based solution engine that is used in each step. Finally, a postprocessing step at the end of the optimization is employed to maximize the alignment of wires in adjacent partitions. The effectiveness of the scheme is demonstrated by designing various power grids with real circuit parameters and realistic input current values. The proposed algorithm is able to design power grids comprising thousands of wires and more than a million electrical nodes in about 6 to 14 min. When compared to a multigrid-based power grid design scheme, it is found to save about 5% to 10% of wire area, and on an average is 12% faster.

Temperature-related effects are critical in determining both the performance and reliability of VLSI circuits. Accurate and efficient estimation of the temperature distribution corresponding to a specific circuit layout is indispensable in physical design automation tools. In this paper, we propose a highly accurate fast algorithm for computing the on-chip temperature distribution due to power sources located on the top surface of the chip. The method is a combination of several computational techniques including the Green function method, the discrete cosine transform (DCT), and the table look-up technique. The high accuracy of the algorithm comes from the fully analytical nature of the Green function method, and the high efficiency is due to the application of the fast Fourier transform (FFT) technique to compute the DCT and later obtaining the temperature field for any power source distribution using the pre-calculated look-up table. Experimental results have demonstrated that our method has a relative error of below 1% compared with commercial computational fluid dynamic (CFD) softwares for thermal analysis, while the efficiency of our method is orders of magnitude higher than the direct application of the Green function method.

Structured ASICs present an attractive alternative to reducing design costs and turnaround times in nanometer designs. As with conventional ASICs, such designs require global wires to be buffered. However via-programmable designs must prefabricate and preplace buffers in the layout. This paper proposes a novel and accurate statistical estimation technique for distributing prefabricated buffers through a layout. It employs Rent's rule to estimate the buffer distribution required for the layout, so that an appropriate structured ASIC may be selected for the design. Experimental results show that the estimation for a uniform buffer distribution is accurate and economic.

In this paper, we present a method for analyzing the leakage current, and hence the leakage power, of a circuit under process parameter variations that can include spatial correlations due to intra-chip variation. A lognormal distribution is used to approximate the leakage current of each gate and the total chip leakage is determined by summing up the lognormals. In this work, Both subthreshold leakage and gate tunneling leakage are considered. The proposed method is shown to be effective in predicting the CDF/PDF of the total chip leakage. The average errors for mean and sigma values are -1.3% and -4.1%

We demonstrate how to use placement to ameliorate the predicted repeater explosion problem caused by poor interconnect scaling. We achieve repeater count reduction by dynamically modifying net weights in a context-sensitive manner during global placement and coarse legalization. Our scheme, which models layer assignment as well as valid inter-repeater distance ranges, can decrease the repeater counts significantly with minimal impact on wirelength.

Since across-chip interconnect delays can exceed a clock cycle in nanometer technologies, it has become essential in high performance designs to add flip-flops on wires with multi-cycle delays. Although such a wire pipelining strategy allows higher operating frequencies, it can reduce the delivered performance of a microarchitecture, since the extra flip-flops inserted may increase the operation latencies and stall cycles. Moreover, the addition of latencies on some wires can have a large impact on the overall performance while other wires are relatively insensitive to additional latencies. This varying sensitivity suggests the need for a throughput-aware strategy for pipelining the interconnects that interacts closely with the physical design step, which determines the lengths of these multicycle wires. We use a statistical design of experiments strategy based on a multifactorial design, which intelligently uses a limited number of simulations to rank the importance of the wires. When applied at the floorplanning level, our results show improvements both in the overall system performance and in the total wire length when compared with an existing technique.

We present an efficient optimization scheme for gate sizing in the presence of process variations. Using a posynomial delay model, the delay constraints are modified to incorporate uncertainty in the transistor widths and effective channel lengths due to the process variations. An uncertainty ellipsoid method is used to model the random parameter variations. Spatial correlations of intra-die width and channel length variations are incorporated in the optimization procedure. The resulting optimization problem is relaxed to be a Geometric Program and is efficiently solved using convex optimization tools. The effectiveness of our robust gate sizing scheme is demonstrated by applying the optimization on the ISCAS ’85 benchmark circuits and testing the optimized circuits by performing Monte Carlo simulations to model the process variations. By varying the size of the uncertainty ellipsoids, a trade-off between area and robustness is explored. Experimental results show that the timing yield of the robustly optimized circuits improves manifold over the traditional deterministically sized circuits. As compared to the worst-case design, the robust gate sizing solution having the same area, has fewer timing violations.

This paper presents a novel method for false path detection using satisfiability. It is based on circuit node properties that are related to non-testable stuck-at faults as well as to false path detection. When compared to traditional satisfiability methods that generate sat instances associated to paths, the proposed method is more efficient. This efficiency derives from the fact that most digital circuits have a number of nodes that is smaller than the number of paths.

This paper presents a new hybrid linear equation solver for quadratic placement. The new solver is a combination of stochastic solver and iterative solver: it is proven in this paper that an approximate LDL factorization can be obtained from random walks, and used as a preconditioner for conjugate gradient solver. Testing on real-life placement benchmarks shows a speedup of up to 7.1 times over traditional Incomplete Cholesky preconditioned Conjugate Gradient (ICCG).

Thermal simulation has become increasingly important in chip design, especially in the nanometer regime, where the on-chip hot spots severely degrade the performance and reliability of the circuit and increase the leakage power. In this paper, we present a highly efficient and accurate thermal simulation algorithm that is capable of performing full-chip temperature calculations at the cell level. The algorithm is a combination of several important numerical techniques including the Green function method, the discrete cosine transform (DCT), and the frequency domain computations. Experimental results show that our algorithm can achieve orders of magnitude speedup compared with previous Green function based algorithms while maintaining the same accuracy.

This paper addresses the question of how many serial switches are necessary to implement a given logic function as a switch network. This issue is important because it affects directly the resistance that will be charging/discharging output loads, thus affecting cell and circuit performance. We derive exact lower bounds to easily evaluate the number of serial switches needed and demonstrate that complementary series/parallel (CSP) and pass transistor logic (PTL) topologies exceed the lower bounds for many practical examples. We also propose a design methodology that produces cells with minimum number of transistors in series and evaluate the benefits obtained in circuit delay.

As thermal problems become more evident, new physical design paradigms and tools are needed to alleviate them. Incorporating thermal vias into integrated circuits (ICs) is a promising way of mitigating thermal issues by lowering the thermal resistance of the chip itself. However, thermal vias take up valuable routing space, and therefore, algorithms are needed to minimize their usage while placing them in areas where they would make the greatest impact. With the developing technology of three-dimensional integrated circuits (3D ICs), thermal problems are expected to be more prominent, and thermal vias can have a larger impact on them than in traditional 2D ICs. In this paper, thermal vias are assigned to specific areas of a 3D IC and used to adjust their effective thermal conductivities. The thermal via placement method makes iterative adjustments to these thermal conductivities in order to achieve a desired maximum temperature objective. Finite element analysis (FEA) is used in formulating the method and in calculating temperatures quickly during each iteration. As a result, the method efficiently achieves its thermal objective while minimizing the thermal via utilization.

Routing congestion has become a serious concern in today's VLSI designs. In this paper, we propose a technology mapping algorithm that minimizes routing congestion under delay constraints. The algorithm employs a dynamic programming framework in the matching phase to generate probabilistic congestion maps for all the matches. These congestion maps are then utilized to minimize routing congestion during the covering, which preserves the delay-optimality of the solution using the notion of slack. Experimental results on benchmark circuits in a 100 nm technology show that the algorithm can improve track overflows by 44%, on an average, as compared to the conventional technology mapping while satisfying delay constraints.

This paper presents an efficient heuristic algorithm to design a power distribution network of a chip by employing a successive partitioning and grid refinement scheme. In an iterative procedure, the chip area is recursively bipartitioned, and the wire pitches and the wire widths of the power grid in the partitions are repeatedly adjusted to meet the voltage drop and current density specifications. By using the macromodels of the power grid constructed in the previous levels of partitioning, the scheme ensures that a small global power grid system is simulated in each iteration. A post-processing step at the end of the optimization is employed to maximize the alignment of wires in adjacent partitions. The effectiveness of the scheme is demonstrated by designing various power grids with real circuit parameters and realistic input current values. The proposed algorithm is able to design power grids comprising thousands of wires and more than a million electrical nodes in about 7-16 minutes. The proposed design scheme as compared to a multigrid-based power grid design scheme saves about 7%-12% of wire area.

Process variations are of increasing concern in today's technologies, and they can significantly affect circuit performance. An efficient statistical timing analysis algorithm that predicts the probability distribution of the circuit delay considering both inter-die and intra-die variations, while accounting for the effects of spatial correlations of intra-die parameter variations, is presented. The procedure uses a first-order Taylor series expansion to approximate the gate and interconnect delays. Next, principal component analysis (PCA) techniques are employed to transform the set of correlated parameters into an uncorrelated set. The statistical timing computation is then easily performed with a program evaluation and review technique (PERT)-like circuit graph traversal. The run time of this algorithm is linear in the number of gates and interconnects, as well as the number of varying parameters and grid partitions that are used to model spatial correlations. The accuracy of the method is verified with Monte Carlo (MC) simulation. On average, for the 100 nm technology, the errors of mean and standard deviation (SD) values computed by the proposed method are 1.06% and -4.34%, respectively, and the errors of predicting the 99% and 1% confidence point are -2.46% and -0.99%, respectively. A testcase with about 17 800 gates was solved in about 500 s, with high accuracy as compared to an MC simulation that required more than 15 h.

High-performance integrated circuits are now reaching the 100-plus watt regime, and power delivery and power grid signal integrity have become critical. Analyzing the performance of the power delivery system requires knowledge of the current drawn by the functional blocks that comprise a typical hierarchical design. However, current designs are of such complexity that it is difficult for a designer to determine what a realistic worst-case switching pattern for the various blocks would be in order to maximize noise at a specific location. This paper uses information about the power dissipation of a chip to derive an upper bound on the worst-case voltage drop at an early stage of design. An exact integer linear programming (ILP) method is first developed, followed by an effective heuristic to speed up the exact method. A circuit of 43 K nodes is analyzed within 70 s, and the worst-case scenarios found correlate well with the results from an ILP solver.

This paper presents a class of power grid analyzers based on a random-walk technique. A generic algorithm is first demonstrated for dc analysis, with linear runtime and the desirable property of localizing computation. Next, by combining this generic analyzer with a divide-and-conquer strategy, a single-level hierarchical method is built and extended to multilevel and "virtual-layer" hierarchy. Experimental results show that these algorithms not only achieve speedups over the generic random-walk method, but also are more robust in solving various types of industrial circuits. Finally, capacitors and inductors are incorporated into the framework, and it is shown that transient analysis can be carried out efficiently. For example, dc analysis of a 71 K-node power grid with C4 pads takes 4.16 s; a 348 K-node wire-bond dc power grid is solved in 93.64 s; transient analysis of a 642 K-node power grid takes 2.1 s per timestep.

Due to increasing design complexities, routing congestion has become a critical problem in very large scale integration designs. This paper introduces a distributed metric to predict routing congestion and applies it to technology mapping that targets area and delay optimization. Our technology mapping algorithms are guided by a probabilistic congestion map for the subject graph to identify the congested regions, where congestion-optimal matches are favored. Experimental results on a set of benchmark circuits in a 90-nm technology show that congestion-aware mapping results in a reduction of 37%, on an average, in track overflows with marginal gate-area penalty as compared to conventional area-oriented technology mapping. For delay-oriented mapping, our algorithm improves track overflows by 20%, on an average, in addition to preserving or improving the delay, as compared to the conventional method.

This paper presents an efficient method for optimizing the design of power/ground (P/G) networks by using locally regular, globally irregular grids. The procedure divides the power grid chip area into rectangular subgrids or tiles. Treating the entire power grid to be composed of many tiles connected to each other enables the use of a hierarchical circuit analysis approach to identify the tiles containing the nodes having the greatest drops. Starting from an initial configuration with an equal number of wires in each of the rectangular tiles, wires are added in the tiles using an iterative sensitivity based optimizer. A novel and efficient table lookup scheme is employed to provide gradient information to the optimizer. Incorporating a congestion penalty term in the cost function ensures that regularity in the grid structure does not aggravate congestion. Experimental results on test circuits of practical chip sizes show that the proposed P/G network topology, after optimization, saves 12%-23% of the chip-wiring area over other commonly used topologies.

Digital designs can be mapped to different implementations using diverse approaches, with varying cost criteria. Post-processing transforms, such as transistor sizing, can significantly improve circuit performance by optimizing critical paths to meet timing specifications. However, most transistor sizing tools have high execution times, and the possible delay gains due to sizing, and the associated costs are not known prior to sizing. In this paper, we present two metrics for comparing different implementations-the minimum achievable delay and the cost of achieving a target delay-and show how these can be estimated without running a sizing tool. Using these fast and accurate performance estimators, a designer can determine the tradeoffs between multiple functionally identical implementations, and size only the selected implementation.

We address the problem of synthesizing pass transistor logic (PTL), with the specific objective of delay reduction, through binary decision diagram (BDD) decomposition. The decomposition is performed by mapping the BDD to a network flow graph, and then applying the max-flow min-cut technique to bipartition the BDD optimally under a cost function that measures the delay and area of the decomposed implementations. Experimental results obtained by running our algorithm on the set of ISCAS'85 benchmarks show a 31% improvement in delay and a 30% improvement in area, on an average, as compared to static CMOS implementations for XOR intensive circuits, while in case of arithmetic logic unit and control circuits that are NAND intensive, improvements over static CMOS are small and inconsistent.

Gate oxide tunneling current (I/sub gate/) is comparable to subthreshold leakage current in CMOS circuits when the equivalent physical oxide thickness (T/sub ox/) is below 15 /spl Aring/. Increasing the value of T/sub ox/ reduces the leakage at the expense of increased delay, and hence a practical tradeoff between delay and leakage can be achieved by assigning one of two permissible T/sub ox/ values to each transistor. In this paper, we propose an algorithm for dual-T/sub ox/ assignment to optimize the total leakage power under delay constraints and generate a leakage/delay tradeoff curve. As compared to the case where all transistors are set to low T/sub ox/, our approach achieves an average leakage reduction of 86% under 100 nm models and 81% under 70 nm models. We also propose a transistor and pin reordering technique that has minimal layout impact to further reduce the total leakage current up to 12% and I/sub gate/ up to 27% without incurring any delay penalty.

As across-chip interconnect delays can exceed a clock cycle, wire pipelining becomes essential in high performance designs. Although it allows higher clock frequencies, it may change the microarchitecture altogether because of the arbitrary increase in the latencies of the paths and cycles of the circuit. This paper proposes a method to regain the functionality of a wire-pipelined circuit. In this approach, increased cycle latencies are compensated by slowing down the issue rate of the inputs. Our method finds the optimal value of the slowdown required for a circuit as it directly affects the throughput of the circuit. We also incorporate area minimization in our formulation to minimize the number of extra flip-flops added to the circuit. The formulation is tested on circuits derived from ISCAS benchmarks and the results suggest that wire pipelining increases the overall throughput in most of the cases.

Gate oxide tunneling current (Igate) will become the dominant component of leakage in CMOS circuits as the physical oxide thickness (Tox) goes below 15AA. Increasing the value of Tox reduces the leakage at the expense of an increase in delay, and a practical tradeoff between delay and leakage can be achieved by assigning one of the two permissible Tox values to each transistor. In this paper, we propose an algorithm for dual Tox assignment to optimize the total leakage power under delay constraints, and generate a leakage/delay tradeoff curve. As compared to the case where all transistors are set to low Tox, our approach achieves an average leakage reduction of 83% under 100nm models.

Digital designs can be mapped to different implementations using diverse approaches, with varying cost criteria. Post-processing transforms, such as transistor sizing can drastically improve circuit performance, by optimizing critical paths to meet timing specifications. However, most transistor sizing tools have high execution times, and the attainable circuit delay can be determined only after running the tool. In this paper, we present an approach for fast transistor sizing that can enable a designer to choose one among several functionally identical implementations. Our algorithm computes the minimum achievable delay of a circuit with a maximum average error of 5.5% in less than a second for even the largest benchmarks.

The optimization of integrated spiral inductors has great practical importance. Previous optimization methods used in this field are either too slow or depend on very simplified assumptions in the device modeling which result in the algorithm only applicable to low-frequency cases. In this paper, we propose using the sequential quadratic programming (SQP) approach to optimize the on-chip spiral inductors. A physical model based on first principles is used in the back-end device-parameter extraction engine which makes the algorithm suitable to the optimization at any frequency range. In addition, compared with enumeration, which is used in many inductance optimization packages, our experiments show that the SQP algorithm can achieve at least an order of magnitude speedup while maintaining the same quality of the optimized design.

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

We propose a new approach to library-based technology mapping, based on the method of logical effort. Our algorithm is close to optimal for fanout-free circuits, and is extended to solve the load-distribution problem for circuits with fanout. On average, benchmark circuits mapped using our approach are 25.39% faster than the solutions obtained from SIS.

This work presents a chip-level charged device model (CDM) electrostatic discharge (ESD) simulation method. The chip-level simulation is formulated as a DC analysis problem. A network reduction algorithm based on random walks is proposed for rapid analysis, and to support incremental design. A benchmark with a 2.3M-node V/sub DD/ net and 1000 I/O pads is checked in 13 minutes, and 10 re-simulations for incremental changes take a total of 9 minutes.

Gate oxide tunneling current (I/sub gate/) is emerging as a key roadblock for device scaling in nanometer-scale CMOS circuits. A practical means to reduce I/sub gate/ is to leverage dual T/sub ox/ processes where non-critical transistors are assigned a thicker T/sub ox/. In this paper, we generate a leakage/delay tradeoff curve for dual T/sub ox/ circuits, and propose a transistor and pin reordering technique that has a minimal layout impact to further reduce the total leakage current up to 18% and I/sub gate/ up to 26% without incurring any delay penalty.

We present a method for incorporating crosstalk reduction criteria into global routing under an innovative power supply architecture, while considering the constraints imposed by limited routing and buffering resources. An iterative procedure is employed to route the signal wires, assign supply shields, and insert buffers so that both buffer/routing capacity and signal integrity goals are met. In each iteration, shield assignment and buffer insertion are considered simultaneously via a dynamic programming-like approach. Our noise calculations are based on Devgan's noise metric, and our work shows, for the first time, that this metric shows good fidelity on average. Experimental results on testcases with up to about 10,000 nets point towards an asymptotic run time that increases linearly with the number of nets. Our algorithm achieves noise reduction improvements of up to 53% and 28%, respectively, compared to methods considering only buffer insertion, or only shield insertion after buffer planning.

High performance integrated circuits are now reaching the 100-plus watt regime, and power delivery and power grid signal integrity have become critical. Analyzing the performance of the power delivery system requires knowledge of the the current drawn by the functional blocks that comprise a typical hierarchical design. However, current designs are of such complexity that it is difficult for a designer to determine what a realistic worst-case switching pattern for the various blocks would be in order to maximize noise at a specific location. This paper uses information about the power dissipation of a chip to derive an upper bound on the worst-case voltage drop at an early stage of design. An exact ILP method is first developed, followed by an effective heuristic to speed up the exact method. A circuit of 43K nodes is analyzed within 70 seconds, and the worst-case scenarios found correlate well with the results from an ILP solver.

Due to increasing design complexity, routing congestion has become a critical problem in VLSI designs. This paper introduces a distributed metric to predict routing congestion for a premapped netlist and applies it to technology mapping that targets area optimization. Our technology mapping algorithm is guided by a probabilistic congestion map for the subject graph to identify the congested regions. Experimental results on the benchmark circuits in a 90nm technology show that congestion-aware mapping results in a reduction of 37%, on an average, in track overflows as compared to conventional technology mapping.

This paper presents an efficient method for optimizing the design of power/ground (P/G) networks by using locally regular, globally irregular grids. The procedure divides the power grid chip area into rectangular sub-grids or tiles. Treating the entire power grid to be composed of many tiles connected to each other enables the use of a hierarchical circuit analysis approach to identify the tiles containing the nodes having the greatest drops. Starting from an initial equal number of wires in each of the rectangular tiles, wires are added in the tiles using an iterative sensitivity based optimizer. A novel and efficient table lookup scheme is employed to provide gradient information to the optimizer. Experimental results on test circuits of practical chip sizes show that the proposed P/G network topology after optimization saves 16% to 28% of the chip wiring area over other commonly used topologies.

We present an early-stage global wire-design methodology that simultaneously considers the performance needs for both signal lines and power grids under congestion considerations. An iterative procedure is employed in which the global routing is performed according to a congestion map that includes the resource utilization of the power grid, followed by a step in which the power grid is adjusted to relax the congestion in crowded regions. This adjustment is in the form of wire removal in noncritical regions, followed by a wire-sizing step that overcomes the voltage noise after wire removal and a wire-width resizing that meets the maximum current-density constraint. Experimental results show that the overall routability can be significantly improved while the power-grid noise is maintained within both the voltage-drop and current-density constraints.

This article describes a polynomial time algorithm for min-area retiming for edge-triggered circuits to handle both setup and hold constraints. Given a circuit G and a target clock period c , our algorithm either outputs a retimed version of G satisfying setup and hold constraints or reports that such a solution is not possible, in O (∣V∣ 3 log ∣ V ∣ log (∣ V ∣ C )) steps, where ∣ V ∣ corresponds to number of gates in the circuit and C is equal to the number of registers in the circuit. This is the first polynomial-time algorithm ever reported for min-area retiming with constraints on both long and short-paths. An alternative problem formulation that takes practical issues into consideration and lowers the problem complexity is also developed. Both the problem formulations have many parallels with the original formulation of long path only retiming by Leiserson and Saxe and all the speed improvements that have been obtained on that problem statement are also demonstrated in simulation for the approach presented here. Finally, a basis is provided for deriving efficient heuristics for addressing both long-path and short-path requirements by combining the techniques of retiming and min-delay padding.

This paper presents a power grid analyzer based on a random walk technique. A linear-time algorithm is first demonstrated for DC analysis, and is then extended to perform transient analysis. The method has the desirable property of localizing computation, so that it shows massive benefits over conventional methods when only a small part of the grid is to be analyzed (for example, when the effects of small changes to the grid are to be examined). Even for the full analysis of the grid, experimental results show that the method is faster than existing approaches and has an acceptable error margin. This method has been applied to test circuits of up to 2.3M nodes. For example, for a circuit with 70K nodes, the solution time for a single node was 0.42 sec and the complete solution was obtained in 17.6 sec.

As the technology node progresses, thermal problems are becoming more prominent especially in the developing technology of three-dimensional (3D) integrated circuits. The thermal placement method presented in this paper uses an iterative force-directed approach in which thermal forces direct cells away from areas of high temperature. Finite element analysis (FEA) is used to calculate temperatures efficiently during each iteration. Benchmark circuits produce thermal placements with both lower temperatures and thermal gradients while wirelength is minimally affected.

Analyzing the effect of crosstalk on delay is critical for high performance circuits. The major bottleneck in performing crosstalk-induced delay analysis is the high computational cost of simulating the coupled interconnect and the nonlinear drivers. We propose an efficient iterative algorithm that avoids time-consuming nonlinear driver simulations and performs node-specific crosstalk delay analysis. The proposed algorithm has been tested over circuits in two deep submicron technologies with varying driver sizes, interconnect parasitics, signal transition times and it has been found to predict the worst-case delay to within 10% of the actual delay.

The thermal problem has been emerged as one of the key issues for next-generation IC design. In this paper, we propose a scheme to achieve better thermal distribution for partitiondriven standard cell placement. The proposed heuristic uses a multigrid-like method that simplifies the thermal equation at each level of partitioning and makes it possible to incorporate temperature considerations directly as placement constraints, thus leading to better thermal distribution. Our experimental results verify the e#ectiveness of our scheme. We also describe an algorithm to derive a compact thermal model with a complexity of O(mn + m ), where m is the number of the mesh nodes on the substrate surface and n is the number of all internal mesh nodes.

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

In this paper, a precorrected-fast-Fourier-transform (FFT) approach for fast and highly accurate simulation of circuits with on-chip inductance is proposed. This work is motivated by the fact that circuit analysis and optimization methods based on the partial element equivalent circuit model require the solution of a subproblem in which a dense inductance matrix must be multiplied by a given vector, an operation with a high computational cost. The grid representation enables the use of the discrete FFT for fast magnetic vector potential calculation. The precorrected-FFT method has been applied to accurately simulate large industrial circuits with up to 121 000 inductors and over 7 billion mutual inductive couplings in about 20 min. Techniques for trading off CPU time with accuracy using different approximation orders and grid constructions are also illustrated. Comparisons with a block-diagonal sparsification method are used to illustrate the accuracy and effectiveness of this method. In terms of accuracy, memory, and speed, it is shown that the precorrected-FFT method is an excellent approach for simulating on-chip inductance in a large circuit.

This paper presents an efficient method for optimizing power/ground (P/G) networks by widening wires and adding decoupling capacitors (decaps). It proposes a structured skeleton that is intermediate to the conventional method that uses full meshes, which are hard to analyze efficiently, and tree-structured networks, which provide poor performance. As an example, we consider a P/G network structure modeled as an overlying mesh with underlying trees originating from the mesh, which eases the task of analysis with acceptable performance sacrifices. A fast and efficient event-driven P/G network simulator is proposed, which hierarchically simulates the P/G network with an adaptation of PRIMA to handle nonzero initial conditions. An adjoint network that incorporates the variable topology of the original P/G network, as elements switch in and out of the network, is constructed to calculate the transient adjoint sensitivity over multiple intervals. The gradients of the most critical node with respect to each wire width and decap are used by a sensitivity-based heuristic optimizer that minimizes a weighted sum of the wire and the decap area. Experimental results show that this procedure can be used to efficiently optimize large networks.

With technology scaling, the trend for high-performance integrated circuits is toward ever higher operating frequency, lower power supply voltages, and higher power dissipation. This causes a dramatic increase in the currents being delivered through the on-chip power grid and is recognized in the 2001 International Technology Roadmap for Semiconductors as one of the difficult challenges. The addition of decoupling capacitances (decaps) is arguably the most powerful degree of freedom that a designer has for power-grid noise abatement and is becoming more important as technology scales. In this paper, we propose and demonstrate an algorithm for the automated placement and sizing of decaps in application specific integrated circuit (ASIC)-like circuits. The problem is formulated as one of nonlinear optimization and is solved using a sensitivity-based quadratic programming (QP) solver. The adjoint sensitivity method is applied to calculate the first-order sensitivities. We propose a fast convolution technique based on piecewise linear (PWL) compressions of the original and adjoint waveforms. Experimental results show that power grid noise can be significantly reduced after a judicious optimization of decap placement, with little change in the total chip area.

We present a technology mapping algorithm for implementing a random logic gate network in domino logic. The target technology of implementation is silicon-on-insulator (SOI). SOI devices exhibit an effect known as parasitic bipolar effect (PBE), which can lead to incorrect logic values in the circuit. Our algorithm solves the technology mapping problem by permitting several transformations during the mapping process in order to avoid PBE, such as transistor reordering, altering the way that transistors are organized into gates, and adding pMOS discharge transistors. We minimize the total cost of implementation, which includes discharge transistors required for correct functioning. Our algorithm generates solutions that reduce the number of discharge transistors required by 53% and reduces the size of the final solution by 6.3% on average. We compare our results with a modification of a current technology mapping algorithm for bulk CMOS domino logic that reduces the cost of the final solution and find that our algorithm outperforms this method.

We present a global wire design methodology that simultaneously considers the performance needs for both signal lines and power grids under congestion considerations. An iterative procedure is employed in which the global routing is performed according to a congestion map that includes the resource utilization of the power grid, followed by a step in which the power grid is adjusted to relax the congestion in crowded regions. This adjustment is in the form of wire removal in noncritical regions, followed by a wire sizing step that overcomes the effects of wire removal. Experimental results show that the overall routability can be significantly improved while the power grid noise is maintained within the voltage droop constraint.

The simulation of on-chip inductance using PEEC-based circuit analysis methods often requires the solution of a subproblem where an extracted inductance matrix must be multiplied by a current vector, an operation with a high computational cost. This paper presents a highly accurate technique, based on a precorrected-FFT approach, that speeds up this calculation. Instead of computing the inductance matrix explicitly, the method exploits the properties of the inductance calculation procedure while implicitly considering the effects of all of the inductors in the layout. An optimized implementation of the method has been applied to accurately simulate large industrial circuits with up to 121,000 inductors and nearly 7 billion mutual inductive couplings in about 20 minutes. Techniques for trading off the CPU time with the accuracy using different approximation orders and grid constructions are also illustrated. Comparisons with a block diagonal sparsification method in terms of accuracy, memory and speed demonstrate that our method is an excellent approach for simulating on-chip inductance in a large circuit.

This paper presents a novel enumerative approach, with provable and efficient pruning techniques, for dual threshold voltage (Vt) assignment at the transistor level. Since the use of low Vt may entail a substantial increase in leakage power, we formulate the problem as one of combined optimization for leakage-delay tradeoffs under Vt optimization and sizing. Based on an analysis of the effects of these two transforms on the delay and leakage, we justify a two-step procedure for performing this optimization. Results are presented on the ISCAS85 benchmark suite favorably comparing our approach with an existing sensitivity-based optimizer.

Practical approaches for on-chip inductance extraction to obtain a sparse, stable and accurate inverse inductance matrix K are proposed. The novelty of our work is in using circuit characteristics to define the concept of resistance-dominant and inductance-dominant lines. This notion is used to progressively refine a set of clusters that are inductively tightly-coupled. For reasonable designs, the more exact algorithm yields a sparsification of 97% for delay and oscillation magnitude errors of 10% and 15%, respectively, while the more approximate algorithm achieves up to 99% sparsification. An offshoot of this work is K-PRIMA, an extension of PRIMA to handle K matrices with guaranteed passivity.

With technology scaling, the trend for high performance integrated circuits is towards ever higher operating frequency, lower power supply voltages and higher power dissipation. This causes a dramatic increase in the currents being delivered through the on-chip power grid and is recognized in the International Technology Roadmap for Semiconductors as one of the difficult challenges. The addition of decoupling capacitances (decaps) is arguably the most powerful degree of freedom that a designer has for power-grid noise abatement and is becoming more important as technology scales. In this paper, we propose and demonstrate an algorithm for the automated placement and sizing of decaps in ASIC-like circuits. The adjoint sensitivity method is applied to calculate the first-order sensitivity of the power grid noise with respect to every decap. We propose a fast convolution technique based on piecewise linear (PWL) compressions of the original and adjoint waveforms. Experimental results show that power grid noise can be significantly reduced after a judicious optimization of decap placement, with little change of the total chip area.

Proposed in this paper is a new approach for VLSI interconnect global routing that can optimize both congestion and delay, which are often competing objectives. The authors' approach provides a general framework that may use any single-net routing algorithm and any delay model in global routing. It is based on the observation that there are several routing topology flexibilities that can be exploited for congestion reduction under timing constraints. These flexibilities are expressed through the concepts of a soft edge and a slideable Steiner node. Starting with an initial solution where timing-driven routing is performed on each net without regard to congestion constraints, this algorithm hierarchically bisects a routing region and assigns soft edges to the cell boundaries along the bisector line. The assignment is achieved through a network flow formulation so that the amount of timing slack used to reduce congestions; is adaptive to the congestion distributions. Finally, a timing-constrained rip-up-and-reroute process is performed to alleviate the residual congestions. Experimental results on benchmark circuits are quite promising and the run time is between 0.02 s and 0.15 s per two-pin net.

This paper presents MINFLOTRANSIT, a new transistor sizing tool for fast sizing of combinational circuits with minimal cost. MINFLOTRANSIT is an iterative relaxation-based tool that has two alternating phases. For a circuit with |V| transistors and |E| wires, the first phase (D-phase) is based on minimum cost network flow, which in our application, has a worst case complexity of O(|V/spl par/E| log(log(|V|))). The second phase (W-phase) has a worst case complexity of O(|V/spl par/E|). In practice, during our simulations both the D-phase and W-phase show a near linear run-time dependence on the size of the circuit, comparable to TILOS. Simulation results show excellent run-time behavior for MINFLOTRANSIT on all the ISCAS85 benchmark circuits. For reasonable delay targets, MINFLOTRANSIT shows up to 16.5% area savings (in relatively large circuits) over a circuit sized using a TILOS-like algorithm. In our opinion, the primary contribution of this paper is to take advantage of the structure of the transistor sizing problem and devise an iterative relaxation based gradient descent approach (D-phase) that has excellent convergence properties.

Careful design and verification of the power distribution network of a chip are of critical importance to ensure its reliable performance. With the increasing number of transistors on a chip, the size of the power network has grown so large as to make the verification task very challenging. The available computational power and memory resources impose limitations on the size of networks that can be analyzed using currently known techniques. Many of today's designs have power networks that are too large to be analyzed in the traditional way as flat networks. In this paper, we propose a hierarchical analysis technique to overcome the aforesaid capacity limitation. We present a new technique for analyzing a power grid using macromodels that are created for a set of partitions of the grid. Efficient numerical techniques for the computation and sparsification of the port admittance matrices of the macromodels are presented. A novel sparsification technique using a 0-1 integer linear programming formulation is proposed to achieve superior sparsification for a specified error. The run-time and memory efficiency of the proposed method are illustrated on industrial designs. It is shown that even for a 60 million-node power grid, our approach allows for an efficient analysis, whereas previous approaches have been unable to handle power grids of such size.

We present an efficient algorithm for technology mapping of domino logic to a parameterized library. The algorithm is optimal for mapping trees consisting of two-input AND/OR nodes, and has a computation time that is polynomial in terms of constraint size. The mapping method is then extended to DAG covering that permits the implicit duplication of logic nodes. Our synthesis procedure maps the complementary logic cones independently when AND/OR logic is to be implemented, and together using dual-monotonic gates in the case of XOR/XNOR logic. The mapping procedure solves the output phase assignment problem as a preprocessing step. Based on a key observation that the output phase assignment could reduce the implementation cost due to the possible large cost difference between two polarities, a 0--1 integer linear programming formulation was designed to minimize the implementation cost. Our experimental results show the effectiveness of the proposed techniques.

Proposes two practical approaches for on-chip inductance extraction to obtain a highly sparsified and accurate inverse inductance matrix K. Both approaches differ from previous methods in that they use circuit characteristics to obtain a sparse, stable and symmetric K, using the concept of resistance-dominant and inductance-dominant lines. Specifically, they begin by finding inductance-dominant lines and forming initial clusters, followed by heuristically enlarging and/or combining these clusters, with the goal of including only the important inductance terms in the sparsified K matrix. Algorithm 1 permits the influence of the magnetic field of aggressor lines to reach the edge of the chip, while Algorithm 2 works under the simplified assumptions that the supply lines have zero /spl Sigma//sub j/L/sub ij/(dI/sub j//dt) drops (but have nonzero parasitic Rs and Cs) and that currents cannot return through supply lines beyond a user-defined distance. For reasonable designs, Algorithm 1 delivers a sparsification of 97% for delay and oscillation magnitude errors of 10% and 15%, respectively, as compared to Algorithm 2 where the sparsification can reach 99% for the same delay error.

Clock networks account for a significant fraction of the power dissipation of a chip and are critical to performance. This paper presents theory and algorithms for building a low-power clock tree by distributing the clock signal at a lower voltage and translating it to a higher voltage at the utilization points. Two low-power schemes are used: reduced swing and multiple-supply voltages. We analyze the issue of tree construction and present conclusions relevant to various technology generations according to the NTRS. Our experimental results show that power savings of an average of 45% are possible for a 0.25 /spl mu/m technology using multiple supply voltages, and about 32% using a single external supply voltage.

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

We present a technology mapping algorithm for implementing a random logic gate network in domino logic. The target technology of implementation is Silicon on Insulator (SOI). SOI devices exhibit an effect known as Parasitic Bipolar Effect (PBE), which can lead to incorrect logic values in the circuit. Our algorithm solves the technology mapping problem by permitting several transformations during the mapping process in order to avoid the PBE, such as transistor reordering, altering the way transistors are organized into gates, and adding pmos discharge transistors. We minimize the total cost of implementation, which includes the discharge transistors required for correct functioning. Our algorithm generates solutions that reduce the number of discharge transistors needed by 44.23%, and reduces the size of the final solution by 11.66% on average.

In this paper, a new structural matching algorithm for technology mapping is proposed. The algorithm is based on a key observation that the matches for a node in a subject Boolean network are related to the matches for its children. The structural relationships between the library cells are modeled using a lookup table. The proposed method is fast, has low memory usage, and is easy to implement. Experimental results show speedups of 20x over Matsunaga's fast mapping approach, and orders of magnitude over SIS, with the same or slightly better results, and much lower memory utilization.

In this paper, we address the problem of performance oriented synthesis of pass transistor logic (PTL) circuits using a binary decision diagram (BDD) decomposition technique. We transform the BDD decomposition problem into a recursive bipartitioning problem and solve the latter using a max-flow min-cut technique. We use the area and delay cost of the PTL implementation of the logic function to guide the bipartitioning scheme. Using recursive bipartitioning and a one-hot multiplexer circuit, we show that our PTL implementation has logarithmic delay in the number of inputs, under certain assumptions. The experimental results on benchmark circuits are promising, since they show the significant delay reductions with small or no area overheads as compared to previous approaches.

This paper hierarchically constructs a hybrid mesh/tree clock network structure consisting of overlying zero-skew clock meshes, with underlying zero-skew clock trees originating from the mesh nodes. We propose a mesh construction procedure, which guarantees zero skew under the Elmore delay model, using a simple and efficient linear programming formulation. Buffers are inserted to reduce the transition time (or rise time). As a post-processing step, wire width optimization under an accurate higher-order delay metric is performed to further minimize the transition time and propagation delay/skew. Experimental results show that the hybrid mesh/tree construction scheme can provide smaller propagation delay and transition time than a comparable clock tree.

We propose a method for VLSI interconnect global routing that can optimize routing congestion, delay and number of bends, which are often competing objectives. Routing flexibilities under timing constraints are obtained and exploited to reduce congestion subject to timing constraints. The wire routes are determined through gradual refinement according to probabilistic estimation on congestions so that the congestion is minimized while the number of bends on wires are limited. The experiments on both random generated circuits and benchmark circuits confirm the effectiveness of this method.

Buffer insertion has become an increasingly critical optimization in high performance design. The problem of finding a delay-optimal buffered Steiner tree has been an active area of research, and excellent solutions exist for most instances. However, current approaches fail to adequately solve a particular class of real-world “difficult” instances which are characterized by a large number of sinks, variations in sink criticalities, and varying polarity requirements. We propose a new Steiner tree construction called C-Tree for these instance types. When combined with van Ginneken style buffer insertion, C-Tree achieves higher quality solutions with fewer resources compared to traditional approaches.

Timing optimization is a critical component of deep submicrometer design and buffer insertion is an essential technique for achieving timing closure. This work studies buffer insertion under the constraint that the buffers either: (1) avoid blockages or (2) are contained within preassigned buffer bay regions. We propose a general Steiner-tree formulation to drive this application and present a maze-routing-based heuristic that either avoids blockages or finds buffer bays. We show that the combination of our Steiner-tree optimization with leading-edge buffer-insertion techniques leads to effective solutions on industry designs.

With the reducing distances between wires in deep submicrometer technologies, coupling capacitances are becoming significant as their magnitude becomes comparable to the area capacitance and fringing capacitance of a wire. This causes an increasing susceptibility to failure due to inadvertent noise and leads to a requirement for accurate noise estimation. An incorrect estimation of the noise could lead either to circuit malfunction in case of underestimation or to wasted design resources due to overestimation. This paper presents a new time-efficient method for the precise estimation of crosstalk noise. While existing fast noise estimation metrics may overestimate the coupling noise by several orders of magnitude, the proposed metric computes the coupling noise with a good accuracy as compared to SPICE.

Two new techniques for mapping circuits are proposed in this paper. The first method, called the odd-level transistor replacement (OTR) method, has a goal that is similar to that of technology mapping, but without the restriction of a fixed library size and maps a circuit to a virtual library of complex static CMOS gates. The second technique, the static CMOS/pass transistor logic (PTL) method, uses a mix of static CMOS and PTL to realize the circuit and utilizes the relation between PTL and binary decision diagrams. The methods are very efficient and can handle all of the ISCAS'85 benchmark circuits in minutes. A comparison of the results with traditional technology mapping using SIS on different libraries shows an average delay reduction above 18% for OTR, and an average delay reduction above 35% for the static CMOS/PTL method, with significant savings in the area.

This paper derives a methodology for developing accurate convex delay models to be used for transistor sizing. A new rich class of convex functions to model gate delay is presented and the circuit delay under such a model is shown to be equivalent to a convex function. The richness of these functions is exploited to accurately model gate delay for modern designs. The delay model is incorporated into a transistor sizing algorithm based on TILOS. The models were characterized by using a set of grid points and then validated using a disjoint data set. The models were found to be within about 10% of SPICE for nearly all of the gate types considered. Also presented are the experimental results of sizing various test circuits.

This paper presents MINFLOTRANSIT, a new transistor sizing tool for fast sizing of combinational circuits with minimal cost. MINFLOTRANSIT is an iterative relaxation based tool that has two alternating phases. For a circuit with |V| transistors and |E| wires, the first phase (D-phase)) is based on minimum cost network flow, which in our application, has a worst-case complexity of O(|V||E|log(log(|V|))). The second phase W-phase has a worst case complexity of O(|V||E|). In practice, during our simulations both the D-phase and W-phase show a near linear run-time dependence on the size of the circuit, comparable to TILOS. Simulation results show excellent run-time behavior for MINFLOTRANSIT on all the ISCAS85 benchmark circuits. For reasonable delay targets MINFLOTRANSIT shows up to 16.5% area savings over a circuit sized using a TILOS-like algorithm.

Careful design and verification of the power distribution network of a chip are of critical importance to ensure its reliable performance. With the increasing number of transistors on a chip, the size of the power network has grown so large as to make the verification task very challenging. The available computational power and memory resources impose limitations on the size of networks that can be analyzed using currently known techniques. Many of today's designs have power networks that are too large to be analyzed in the traditional way as flat networks. In this paper, we propose a hierarchical analysis technique to overcome the aforesaid capacity limitation. We present a new technique for analyzing a power grid using macromodels that are created for a set of partitions of the grid. Efficient numerical techniques for the computation and sparsification of the port admittance matrices of the macromodels are presented. A novel sparsification technique using a 0-1 integer linear programming formulation is proposed to achieve superior sparsification for a specified error. The run-time and memory efficiency of the proposed method are illustrated through the analysis of case studies of several multi-million node power grids, extracted from real microprocessor and DSP designs.

In this paper we propose a new approach for VLSI interconnect global routing that can optimize both congestion and delay, which are often competing objectives. Our approach provides a general framework that may use any single-net routing algorithm and any delay model in global routing. It is based on the observation that there are several routing topology flexibilities under timing constraints. These flexibilities are exploited for congestion reduction through a network flow based hierarchical bisection and assignment process. Experimental results on benchmark circuits are quite promising.

This paper presents an efficient method for optimizing power/ground (P/G) networks by widening wires and adding decoupling capacitors (decaps). It proposes a structured skeleton that is intermediate to the conventional method that uses full meshes (which are hard to analyze efficiently), and tree-structured networks (which provide poor performance). As an example, we consider a P/G network structure modeled as an overlying mesh with underlying trees originating from the mesh, which eases the task of analysis with acceptable performance sacrifices. A fast and efficient event-driven P/G network simulator is proposed, which hierarchically simulates the P/G network with an adaptation of PRIMA to handle non-zero initial conditions. An adjoint network that incorporates the variable topology of the original P/G network, as elements switch in and out of the network, is constructed to calculate the transient adjoint sensitivity over multiple intervals. The gradients of the most critical node with respect to each wire width and decap are used by a sensitivity-based heuristic optimizer that minimizes a weighted sum of the wire and the decap area. Experimental results show that this procedure can be used to efficiently optimize large networks.

In this paper two problems on domino logic synthesis are addressed. A mapping method that maps the complementary logic cones independently when AND/OR logic is to be implemented and together using dual-monotonic gates in the case of XOR/XNOR logic, is proposed. The results show up to 28.9% improvement in area and always show the same or better performance in delay over existing approaches. Then a 0-1 integer programming formulation is provided for the output phase assignment problem for domino logic. It considers the cost difference between two polarities and enables a standard linear programming package to be used to solve the problem. The results show up to 41.0% improvement in area.

For a four-layer datapath routing environment, we present an algorithm that considers all the nets simultaneously. Routing probabilities are calculated for potential routing regions and consolidated into a congestion metric. This is followed by an iterative diversion technique where the region with the maximum congestion metric is repetitively relaxed until the track probabilities crystallize into integer values of 1 and 0. We have run the algorithm on large test cases and achieved significant routability within a small number of available tracks. 1.

To improve the performance of critical nets where both timing and wire resources are stringent, we integrate buffer insertion and driver sizing separately with non-Hanan optimization and propose two algorithms: simultaneous buffer insertion and non-Hanan optimization (BINO) and full-plane AWE routing with driver sizing (FAR-DS). For BINO, we consider the realistic situation that buffer locations are restricted to a limited set of available spaces after cell placement. The objective of BINO is to minimize a weighted sum of wire and buffer costs subject to timing constraints. To achieve this objective, we suggest a greedy algorithm that considers two operations independently: iterative buffer insertion and iterative buffer deletion. Both are conducted simultaneously with non-Hanan optimization until the improvement is exhausted. For FAR-DS, we investigate the curvature property of the sink delay as a function of both connection location and driver stage ratio in a two-dimensional (2-D) space. The objective of FAR-DS is to minimize a weighted sum of wire and driver cost while ensuring that the timing constraints are satisfied. Based on the curvature property, we search for the optimal solution in the continuous 2-D space. In both BINO and FAR-DS, a fourth-order AWE delay model is employed to assure the quality of optimization. Experiments of BINO and FAR-DS on both integrated circuit and MCM technologies showed significant cost reductions compared with SERT and MVERT in addition to making the interconnect to satisfy timing constraints.

This paper derives a methodology for developing accurate convex delay models to be used for transistor sizing. A new rich class of convex functions to model gate delay is presented and the circuit delay under such a model is shown to be equivalent to a convex function. The richness of these functions is exploited to accurately model gate delay for modern designs. Since the delay under this model is a convex function, optimal sizing algorithms based on convex programming techniques are applied with the new delay model. Experimental results demonstrating the accuracy of proposed model are presented along with results of sizing various test circuits.

Crosstalk is generally recognized as a major problem in integrated circuit design. This paper presents a novel approach to the efficient measurement of the effect of crosstalk on the delay of a net using an algorithm whose worst case complexity is polynomial-time in the number of nets. The cost of the algorithm is seen to be O(n log n) in practice, where n is the number of nets, and it is amenable to being incorporated into the inner loop of a timing optimizer. To illustrate this, the method is applied to reduce the effects of crosstalk in channel routing, where it is seen to give an average improvement of 23% in the delay in a channel as compared to the worst case, as measured by SPICE.

Domino logic is a circuit family that is well-suited to implementing high-speed circuits. Synthesis of domino circuits is more complex than static logic synthesis due to the noninverting nature of the logic and the complex timing relationships associated with the clock scheme. In this paper, we address several problems along a domino synthesis flow. We mainly consider the problem of partitioning a circuit into static and domino regions under timing constraints. The algorithm is extended to develop a method for partitioning domino logic into two phases, with inverters permitted between the two phases, and then to a flow for general two-phase static-domino partitioning. We also address a timing verification and sizing optimization tool for circuits containing mixed domino and static logic.

The problem of power-delay tradeoffs in transistor sizing is examined using a nonlinear optimization formulation. Both the dynamic and the short-circuit power are considered, and a new modeling technique is used to calculate the short-circuit power. The notion of transition density is used, with an enhancement that considers the effect of gate delays on the transition density. When the short-cuircuit power is neglected, the minimum power circuit is idential to the minimum area circuit. However, under our more realistic models, our experimental results on several circuits show that the minimum power circuit is not necessarily the same as the minimum area circuit.

We propose a Full-plane AWE Routing with Driver Sizing (FAR-DS) algorithm for performance driven routing in deep sub-micron technology.We employ a fourth order AWE delay model in the full plane, including both Hanan and non-Hanan points.Optimizing the driver size simultaneously extends our work into a twodimensional space, enabling us to achieve the desired balance between wire and driver cost reduction, while satisfying the timing constraints.Compared to SERT, experimental results showed that our algorithm can provide an average reduction of 23% in the wire cost and 50% in the driver cost under stringent timing constraints.This work is supported in

This paper presents a new solution for combining technology mapping with placement, coupling the two into one phase. The original aspects of our work are the use of libraryless mapping and a state-space search mechanism that is used to find the best solution. Several heuristics are presented for speeding up the search. Comparisons with a more conventional approach show that these strategies provide improvements of about 20%, with reasonable CPU times, on benchmark circuits.

This paper describes a polynomial time algorithm for min-area retiming for edge-triggered circuits to handle both setup and hold constraints. Given a circuit G and a target clock period c, our algorithm either outputs a retimed version of G satisfying setup and hold constraints or reports that such a solution is not possible, in O(|V/sup 3/|log|V|log(|V|C)) steps, where |V| corresponds to number of gates in the circuit and C is equal to the number of registers in the circuit. This is the first polynomial time algorithm ever reported for min-area retiming with constraints on both long and short-paths. An alternative problem formulation that takes practical issues in to consideration and lowers the problem complexity is also developed. Both the problem formulations have many parallels with the original formulation of long-path only retiming by Leiserson and Saxe and all the speed improvements that have been obtained on that technique are likely to be valid for improving the performance of the technique described in this paper.

Domino logic is a high-performance circuit configuration that is usually embedded in a static logic environment and tightly coupled with the clocking scheme. In this paper the timing-driven partitioning algorithms that partition a logic network between (1) static and domino implementations, and (2) the phases of a two-phase clock, are provided In addition, an efficient static mapping algorithm is described.

With the reducing distances between wires in deep sub-micron technologies, coupling capacitances are becoming significant as their magnitude becomes comparable to the area capacitance and fringing capacitance of a wire. This causes an increasing susceptibility to failure due to inadvertent noise, and leads to a requirement for accurate noise estimation. An incorrect estimation of the noise could lead either to circuit malfunction in the case of under-estimation, or to wasted design resources due to overestimation. This paper presents a new time-efficient method for the precise estimation of crosstalk noise. While existing fast noise estimation metrics may overestimate the coupling noise by several orders of magnitude, the proposed metric computes the coupling noise with a good accuracy as compared to SPICE.

Clock networks account for a significant fraction of the power dissipation of a chip and are critical to the performance. This paper presents theory and algorithms for building a low power clock tree. Two low power schemes are used: a reduced swing scheme and one using multiple supply voltages. We analyze the issue of tree construction and present conclusions relevant to various technology generations according to the National Technology Roadmap of Semiconductors (NTRS). Our experimental results show that the power could be saved an average of 45% for a 0.25 /spl mu/m technology using multiple supply voltages, and 31% using reduced swing buffers.

We present a simultaneous Buffer Insertion and Non-Hanan Optimization (BINO) algorithm to improve the performance of VLSI interconnect. This algorithm aims to address the realistic situation where both the interconnect resources and timing constraints are stringent and the wire topology is to be optimized using available spaces for buffer insertions after cell placement. These spaces are fixed relative to the changing routing tree during non-Hanan optimization. The objective here is to minimize weighted sum of wire and buffer cost subject to timing constraints. In BINO, buffer insertion and non-Hanan optimization are conducted simultaneously and iteratively in a greedy fashion till the improvements are exhausted. To assure the accuracy of timing evaluation, the fourth order AWE model is employed. Experimental results on both ,18µm IC and MCM technology showed significant cost reductions.

This work presents a Steiner tree construction procedure, maximum delay violation Elmore routing tree, to meet specified sink arrival time constraints. It is shown that the optimal tree requires the use of non-Hanan points. The procedure works in two phases: a minimum-delay Steiner Elmore routing tree is first constructed using a minor variant of the Steiner Elmore routing tree procedure, after which the tree is iteratively modified, using an efficient search method, to reduce its length. The search method exploits the piecewise concavity of the delay function to arrive at a solution efficiently. Experimental results show that this procedure works particularly well for technologies where the interconnect resistance dominates, and significant cost savings are shown to be generated.

Retiming is a powerful technique for optimizing sequential circuits. The transparent nature of level sensitive latches enables level-clocked circuits to operate faster and require fewer memory elements than edge-triggered circuits. However, this transparency makes the operation of level-clocked circuits very complex, and optimization of level-clocked circuits is a difficult task. This work presents efficient algorithms for retiming large level-clocked circuits. To provide us with a simpler view of the operation of level-clocked circuits, we present the relationship between retiming and clock skew optimization. We then utilize this relationship to develop efficient retiming algorithms for period and area optimization. For period optimization, we present an algorithm which produces near-optimal results, but is significantly faster than the traditional algorithms. In this approach, we first calculate the best possible clock period and the amount of motion required for each latch. The latches are then relocated in an attempt to achieve this period. Area, as measured by the number of latches in the circuit can be optimized by solving a linear program. We apply efficient pruning techniques to reduce the size of this linear program, while preserving optimality. Since generating the linear program is a major part of the computational requirements of minarea retiming, we present techniques for efficient generation of the reduced linear program. This enables us to perform area optimization of large circuits clocked by symmetric multiphase clocks in very reasonable time, without sacrificing optimality. We present results on circuits with up to 56000 gates, performing period optimization in under 20 s and area optimization in under 1.5 h.

Delay-constrained area optimization is an important step in synthesis of VLSI circuits. Minimum area (minarea) retiming is a powerful technique to solve this problem. The minarea retiming problem has been formulated as a linear program; in this work we present techniques for reducing the size of this linear program and efficient techniques for generating it. This results in an efficient minarea retiming method for large level-clocked circuits (with tens of thousands of gates).

Domino logic is a popular con#guration for implementing high-speed circuits. An algorithm for domino logic mapping, under a parameterized library style, is presented here. Practical design methods, such as the use of multioutput domino and wide domino gates, are incorporated within the technology mapping framework. The technique can handle large circuits with small computational overheads, and shows improvements of up to about 37# over existing methods.

A new design methodology for mapping circuits is discussed in this paper. It proposes two new techniques for mapping circuits. The first method, known as the odd-level transistor replacement (OTR) method, has a goal that is similar to that of technology mapping, but without the restriction of a fixed library size. The second technique, the Static/PTL method, uses a mix of static CMOS and pass transistor logic (PTL) to realize the circuit, using the relation between PTL and binary decision diagrams. The methods are very efficient and can handle all of the ISCAS85 benchmark circuits in minutes. A comparison of the results with traditional technology mapping using SIS on different libraries shows an average delay reduction about 40% for OTR, and an average delay reduction above 50% for the Static/PTL method.

This work presents a Steiner tree construction procedure, MVERT, to meet specified sink arrival time constraints. It is shown that the optimal tree requires the use of non-Hanan points. The procedure works in two phases: a minimum-delay Steiner tree is first constructed, after which the tree is iterativ ely modified, using an efficient binary search method, to reduce its length. Experimental results show that this procedure w orks particularly well for tec hnologies where the interconnect resistance dominates, and significant cost savings are generated.

An algorithm for unifying the techniques of gate sizing and clock skew optimization for acyclic pipelines is presented in this paper. In the design of circuits under very tight timing specifications, the area overhead of gate sizing can be considerable. The procedure described herein utilizes the idea of cycle borrowing using clock skew optimization to relax the stringency of the timing specification on the critical stages of the pipeline. The theoretical basis for the procedure is developed, a new algorithm for timing analysis of acyclic pipeline circuits with deliberate skew is presented, and a sensitivity-based optimizer is used to solve the sizing+skew problem. Our experimental results verify that the procedure of cycle borrowing using sizing+skew results in a better overall area-delay tradeoff as compared to using sizing alone.

This work presents strategies to insert buffers in a circuit, combined with gate sizing, to achieve better power delay and area-delay tradeoffs. The purpose of this work is to examine how combining a sizing algorithm with buffer insertion will help us achieve better area delay or power-delay tradeoffs, and to determine where and when to insert buffers in a circuit, The delay model incorporates placement-based information and the effect of input slew rates on gate delays. The results obtained by using the new method are significantly better than the results given by merely using a TILOS-like gate sizing algorithm alone, as is illustrated by several area delay tradeoff curves shown in this paper.

Retiming, introduced by Leiserson and Saxe (1983, 1991), is a powerful transformation of circuits that preserves functionality and improves performance. The ASTRA algorithm proposed an alternative view of retiming using the equivalence between retiming and clock skew optimization and also presented a fast algorithm for minimum period (minperiod) retiming. Since minperiod retiming may significantly increase the number of flip-flops in the circuit, minimum area (minarea) retiming is an important problem. Minarea retiming is a much harder problem than minperiod retiming, and previous techniques were not capable of handling large circuits in a reasonable time. This work defines the relationship between the Leiserson-Saxe and the ASTRA approaches and utilizes it for efficient minarea retiming of large circuits. The new algorithm, Minaret, uses the same basis as the Leiserson-Saxe approach. The underlying philosophy of the ASTRA approach is incorporated to reduce the number of variables and constraints generated in the problem. This allows minarea retiming of circuits with over 56 000 gates in under 15 min.

The concept of improving the timing behavior of a circuit by relocatingflip-flops is called retiming and was first presented by Leisersonand Saxe. The ASTRA algorithm proposed an alternativeview of retiming using the equivalence between retiming and clockskew optimization. This work defines the relationship betweenthe Leiserson-Saxe and the ASTRA approaches and utilizes it tosolve the problem of retiming for minimum area. The new algorithm,Minaret, uses the linear programming formulation of theLeiserson-Saxe approach. The underlying philosophy of the ASTRAapproach is incorporated to reduce the number of variablesand constraints in the linear program. This reduction in the sizeof the linear program makes Minaret space and time efficient, enablingminimum area retiming of circuits with over 56,000 gates inunder 15 minutes.

Traditional minimum area retiming algorithms attempt to achieve their prescribed objective with no regard to maintaining the initial state of the system. This issue is important for circuits such as controllers, and our work addresses this problem. The procedure described generates bounds on the retiming variables that guarantee an equivalent initial state after retiming. A number of possible sets of bounds can be derived, and each set is used to solve a minimum area retiming problem that is set up as a 0/1 mixed integer linear program, using a new technique that models the maximal sharing of flip-flops at latch outputs. The best solution is found through enumeration of these sets, terminated on the achievement of a calculated lower bound. Experimental results show that after a small number of enumerations, optimal or near-optimal results are achievable.

A method for concurrent transistor sizing and buffer insertion is proposed. The method considers the tradeoff between upsizing transistors and inserting buffers and chooses the solution with the lowest possible power and area cost. The method operates by analyzing the feasible region of the cost-delay curves of the unbuffered and buffered circuits. As such the feasible region of circuits optimized by our method is extended to encompass the envelop of cost-delay curves which represent the union of the feasible regions of all buffered and unbuffered versions of the circuit. The method is e#cient and tunable in that optimality can be traded for compute time and the method can in theory produce near optimal results.

Distributed Memory Multicomputers (DMMs), such as the IBM SP-2, the Intel Paragon, and the Thinking Machines CM-5, offer significant advantages over shared memory multiprocessors in terms of cost and scalability. Unfortunately, the utilization of all the available computational power in these machines involves a tremendous programming effort on the part of users, which creates a need for sophisticated compiler and run-time support for distributed memory machines. In this paper, we explore a new compiler optimization for regular scientific applications-the simultaneous exploitation of task and data parallelism. Our optimization is implemented as part of the PARADIGM HPF compiler framework we have developed. The intuitive idea behind the optimization is the use of task parallelism to control the degree of data parallelism of individual tasks. The reason this provides increased performance is that data parallelism provides diminishing returns as the number of processors used is increased. By controlling the number of processors used for each data parallel task in an application and by concurrently executing these tasks, we make program execution more efficient and, therefore, faster.

While designing interconnect for MCMs, one must take into consideration the distributed RLC effects, due to which signals may display nonmonotonic behavior and substantial ringing. This paper considers the problem of designing clock trees for MCMs. A fully distributed RLC model is utilized for AWE-based analysis and synthesis, and appropriate measures are taken to ensure adequate signal damping and for buffer insertion to satisfy constraints on the clock signal slew rate. Experimental results, verified by SPICE simulations, show that this method can be used to build clock trees with near-zero skews.

A new approach for fast retiming of level-clocked circuits is presented. The method relies on the relation between clock skew and retiming, and computes the optimal skew solution to translate it to a retiming. Since clock skew optimization operates on the latches (rather than the gates as in conventional retiming), it is much faster because of a smaller problem size; the translation to the retiming solution is computationally cheap. The minimum period retiming for each of the ISCAS89 circuits was obtained within minutes by this algorithm.

The problem of designing individual macrocells for a library for low power and high speed is addressed here, and a new technique for optimization using posynomial approximating functions is devised. In the design of each macrocell, optimality in design is critical and highly accurate techniques for measuring the performance are required during optimization. This paper presents methods for accurately estimating the worst-case contribution of the power and delay of a cell to a circuit. The program uses circuit-level simulation to calculate the power dissipation and delay of the cell with the highest accuracy. A rationale for using arbitrary degree posynomial modeling functions for area, delay, and power modeling is presented. The problem is then formulated as a convex programming problem, and a rigorous optimization technique is used to arrive at the optimal macrocell.

An efficient solution to the wire sizing problem using the Elmore delay model is proposed. Two formulations of the problem are put forth. In the first, the minimum interconnect delay is sought, while in the latter, we minimize the net delay under delay constraints at the leaf nodes; previous approaches solve only the former problem. Theoretical results on these problems are proved, and two algorithms are presented. One is a sensitivity-based heuristic, while the other is a rigorous convex optimization problem. It is shown experimentally that the sensitivity-based heuristic gives near-optimal results with reasonable runtimes. A smooth area-delay tradeoff is shown, and results are presented to illustrate the fact that sizing for minimum delay is not a good engineering goal. Instead, a delay goal of even 15% over the minimum provides significantly better engineering solutions.

The introduction of clock skew at an edge-triggered flip-flop has an effect that is similar to the movement of the flip-flop across combinational logic module boundaries, and these are continuous and discrete optimizations with the same effect. While this fact has been recognized before, this paper, for the first time, utilizes this information to find an optimal retiming. The clock period is guaranteed to be at most one gate delay larger than the optimal clock period found using skew alone; note that since skew is a continuous optimization, it is possible that the optimal period may not be achievable. The method views the circuit hierarchically, first solving the clock skew problem at one level above the gate level, and then using local transformations at the gate level to perform retiming for the optimal clock period. The solution is thus divided into two phases. In Phase A, the clock skew optimization problem is solved with the objective of minimizing the clock period, while ensuring that the difference between the maximum and the minimum skew is minimized. Next, in Phase B, retiming is employed and some flip-flops are relocated across gates in an attempt to set the values of all skews to be as close to zero as possible.

The introduction of clock s k ew at an edge-triggered ipop has an eect that is similar to the movement of the ip-op across combinational logic module boundaries, and these are continuous and discrete optimizations with the same eect.While this fact has been recognized before, this work, for the rst time, utilizes this information to nd a minimum/speci ed period retiming eciently.The clock period is guaranteed to be at most one gate delay larger than a tight l o w er bound on the optimal clock period; this bound is achievable using a combination of intentional skew and retiming.All ISCAS89 circuits can be retimed in a few minutes by this algorithm.1 \astra" ( ): (Sanskrit) a sophisticated weapon.

The problem of sizing gates for power-delay tradeoffs is of great interest to designers. In this work, the theoretical basis for gate sizing under delay and power considerations is presented, and results on a practical implementation are presented. The dynamic power as well as the short-circuit power are modeled, using notions of delay and transition density, and the optimization problem is formulated using notions of convex programming. Previous approaches have not modeled the short circuit power, and our experimental results show that the incorporation of this leads to counter-intuitive results where the minimum power circuit is not necessarily the minimum-sized circuit.

An algorithm for unifying the techniques of gate sizing and clock skew optimization for acyclic pipelines is presented. In the design of circuits under very tight timing specifications, the area overhead of gate sizing can be considerable. The procedure utilizes the idea of cycle-borrowing using clock skew optimization to relax the stringency of the timing specification on the critical stages of the pipeline. Experimental results verify that cycle-borrowing using sizing+skew results in a better overall area-delay tradeoff than with sizing alone.

The problem of designing individual macrocells for a library with power and speed considerations is addressed here. A new technique for optimization using posynomial approximating functions is devised. In the design of each macrocell, optimality in design is critical and highly accurate techniques for measuring the performance are required during optimization. This paper presents methods for accurately estimating the worst-case contribution of the power and delay of a cell to a circuit. The program uses circuit-level simulation to calculate the power dissipation and delay of the cell with the highest accuracy. A rationale for using arbitrary degree posynomial modeling functions for area, delay and power modeling is presented. The problem is then formulated as a convex programming problem, and a rigorous optimization technique is used to arrive at the optimal macrocell.

A standard cell library typically contains several versions of any given gate type, each of which has a different gate size. We consider the problem of choosing optimal gate sizes from the library to minimize a cost function (such as total circuit area) while meeting the timing constraints imposed on the circuit. After presenting an efficient algorithm for combinational circuits, we examine the problem of minimizing the area of a synchronous sequential circuit for a given clock period specification. This is done by appropriately selecting a size for each gate in the circuit from a standard-cell library, and by adjusting the delays between the central clock distribution node and individual flip-flops. Experimental results show that by formulating gate size selection together with the clock skew optimization as a single optimization problem, it is not only possible to reduce the optimized circuit area, but also to achieve faster clocking frequencies. Finally, we address the problem of making this work applicable to very large synchronous sequential circuits by partitioning these circuits to reduce the computational complexity.>

An e cient solution to the wire sizing problem (WSP) using the Elmore delay model is proposed. Two formulations of the problem are put forth: in the rst, the minimum interconnect delay is sought, while in the second, we minimize the net delay under delay constraints at the leaf nodes; previous approaches solve only the former problem. Theoretical results on these problems are proved, and a sensitivity-based algorithm is devised. It is shown experimentally that the second formulation provides signi cantly better engineering solutions. 1

Compilers have focused on the exploitation of one of functional or data parallelism in the past. The PARADIGM compiler project at the University of Illinois is among the first to incorporate techniques for simultaneous exploitation of both. The work in this paper describes the techniques used in the PARADIGM compiler and analyzes the optimality of these techniques. It is the first of its kind to use realistic cost models and includes data transfer costs which all previous researchers have neglected. Preliminary results on the CM-5 show the efficacy of our methods and the significant advantages of using functional and data parallelism together for execution of real applications.

This paper addresses the problem of minimizing the clock period of a circuit by optimizing the clock skews. We incorporate uncertainty factors and present a formulation that ensures that the optimization will be safe. In a paper by J.P. Fishburn (see IEEE Trans. on Computers, vol. 39, no. 7, p. 945-951, 1990) the problem of clock period optimization is formulated as a linear program. We first propose an efficient graph-based solution that takes advantage of the structure of the problem. We also show that the results obtained by Fishburn may result in exceedingly large skews, and propose a method to reduce these skews without sacrificing the optimality of the clock period. Experimental results on several ISCAS89 benchmark circuits are provided.>

A new high-performance CMOS macromodule layout synthesis system is presented. The layout is based on a new flexible logic cell array platform and channelless routing with compaction, utilizing three layers of metallic interconnects. The flexible cells are placed into rows whose heights can be customized to minimize the total area, while meeting the user-specified aspect ratio of the macromodule. The triple metal layer channelless routing problem with irregular boundaries is mapped to the composite problem of channelless two-layer routing and segment squeezing with layer conversion. To meet the user-specified specifications on circuit delays, in addition to well-established placement and routing, a rigorous transistor sizing program, which employs convex programming techniques, is used to find the minimum active area that satisfies all the delay specifications. The optimal transistor sizes are then implemented in the flexible cell and a new layout is generated. This process is iterated until the layout meets all the timing requirements.>

A new technique for design centering and polytope approximation of the feasible region for a design are presented. In the first phase, the feasible region is approximated by a convex polytope, using a method based on a theorem on convex sets. As a natural consequence of this approach, a good approximation to the design center is obtained. In the next phase, the exact design center is estimated using one of two techniques that we present in this paper. The first inscribes the largest Hessian ellipsoid, which is known to be a good approximation to the shape of the polytope, within the polytope. This represents an improvement over previous methods, such as simplicial approximation, where a hypersphere or a crudely estimated ellipsoid is inscribed within the approximating polytope. However, when the probability density functions of the design parameters are known, the design center does not necessarily correspond to the center of the largest inscribed ellipsoid. Hence, a second technique is developed that incorporates the probability distributions of the parameters, under the assumption that their variation is modeled by Gaussian probability distributions. The problem is formulated as a convex programming problem and an efficient algorithm is used to calculate the design center, using fast and efficient Monte Carlo methods to estimate the yield gradient. An example is provided to illustrate how ellipsoid-based methods fail to incorporate the probability density functions and is solved using the convex programming-based algorithm.>

This paper examines the problem of minimizing the area of a synchronous sequential circuit for a given clock period specification under the standard-cell paradigm. This is effected by appropriately selecting a size for each gate in the circuit from a standard-cell library, and by adjusting the delays between the central clock distribution node and individual flip-flops. Traditional methods treat these two problems separately, which may lead to very sub-optimal solutions in some cases. Experimental results show that by considering the two problems together, it is not only possible to reduce the optimized circuit area, but also to achieve faster clocking frequencies. We also address the problem of making this work applicable to very large synchronous sequential circuits by partitioning these circuits to reduce the computational complexity.

Two new geometrical algorithms for design centering are presented. In each case, the feasible region is first approximated by a convex polytope. The first algorithm inscribes the largest Hessian ellipsoid within the approximating polytope. The second assumes Gaussian parameter distributions, formulates the problem as a convex programming problem, and uses an efficient algorithm to perform the optimization.

A general sequential circuit consists of a number of combinational stages that lie between latches. For the circuit to meet a given clocking specification, it is necessary for each combinational stage to satisfy a certain delay requirement. Roughly speaking, increasing the sizes of some transistors in a stage reduces the delay, with the penalty of increased area. The problem of transistor sizing is to minimize the area of a combinational stage, subject to its delay being less than a given specification. Although this problem has been recognized as a convex programming problem, most existing approaches do not take full advantage of this fact, and often give nonoptimal results. An efficient convex optimization algorithm has been used here. This algorithm is guaranteed to find the exact solution to the convex programming problem. We have also improved upon existing methods for computing the circuit delay as an Elmore time constant, to achieve higher accuracy, CMOS circuit examples, including a combinational circuit with 832 transistors are presented to demonstrate the efficacy of the new algorithm.>

The transistor sizing problem of minimizing the circuit area, subject to the circuit delay being less than a given specification, is formulated as a convex programming problem. An efficient convex programming algorithm is then used to obtain the exact solution. Experimental results on a variety of circuits show that, for a given delay specification this approach is able to produce circuits with significantly smaller area when compared with TILOS.>