In chip design planning, obtaining reliable performance and power forecasts for various design options is of critical importance. Traditionally, this involves using system-level models, which often lack accuracy, or trial synthesis, which is both labor-intensive and time-consuming. We introduce a new methodology, called Lorecast, which accepts English prompts as input to rapidly generate layout-aware performance and power estimates. To the best of our knowledge, Lorecast is the first approach to enable performance and power forecasting directly from natural language descriptions. This approach bypasses the need for HDL code development and synthesis, making it both fast and user-friendly. Experimental results show that Lorecast achieves accuracy within a few percent of error compared to post-layout analysis, while significantly reducing turnaround time.

Rapid and accurate performance estimation is critical in evaluating novel microarchitectures, as it enables efficient exploration of architectural trade-offs. Unfortunately, traditional simulation techniques, while precise in predicting performance and power, incur tremendous slowdowns versus real machines. Despite prior works having explored machine learning–based performance prediction, the area remains far from sufficiently studied with existing approaches typically requiring large comprehensive datasets, frequent retraining, and heavy memory footprints with limited accuracy. Here, we introduce a new, fast and accurate, early-stage preview framework that uses partial simulation data, and leverages a smaller, faster tree-based machine learning (ML) model to forecast performance metrics such as IPC and Power. By training on a diverse set of configurations, our framework dynamically captures relationships between microarchitectural parameters in large OoO cores versus overall performance and other metrics. Collecting data from as few as 10 sample points taken during warmup, representing only 25 million instructions, our models achieve mean absolute percentage errors of 3-4%, preserving a majority of the model’s predictive accuracy while achieving a 25× speedup (96% reduction in simulation time). By comparison, linear regression techniques from the same point in simulation show an error of 50%. In cache DSE, we improve ranking accuracy by 25× compared to state-of-the-art prediction methods. Our results also show the proposed framework can accurately predict the performance of unseen (untrained) microarchitectural components including new prefetchers and branch predictors.

A major obstacle in analog design automation is that circuit performance is sensitive to layout, yet accurately capturing this impact within layout tools is very expensive. To address this challenge, we propose a performance-driven analog IC placement approach, called VPlace, guided by machine learning. Our approach leverages a novel application of the VQ-VAE technique to improve robustness during the placement stage, in conjunction with a recent machine learning-based macromodeling method. We further demonstrate that data preparation strategies, which directly affect the efficiency of investigating the solution space, play an important role in determining both the accuracy of machine learning models and the resulting circuit performance. Experimental results show that VPlace achieves 22%-26% and 10%-16% performance improvements over an open-source analog layout tool and a prior machine learning–based performance-driven analog placement technique, respectively.

The increasing integration of renewable and distributed energy resources into the power grid makes Electromagnetic Transient (EMT) simulation more critical for ensuring grid stability. Efficient numerical solvers are crucial for the computationally intensive task of simulating electrical distribution networks (EDN). This paper presents an FPGA-based accelerator for solving the linear system derived from EMT simulation of EDNs. It features a reconfigurable datapath that can exploit parallelism in handling dynamic matrix shapes during runtime. FPGA prototyping shows significant speedup over prior works with reduced logic resource usage.

To apply machine learning (ML) techniques for electronic design automation (EDA), training models on diverse datasets is essential for model reliability and generalizability, especially when applied to modern circuits. However, data availability remains a severe issue as circuit data is typically kept confidential within each data provider due to the difficulty of secure data sharing. This problem has impeded the development of ML for EDA in both industry and academia and has never been well addressed. To facilitate model development, enabling secure data sharing among various data providers is needed. To this end, we propose PRICING, a privacy-preserving circuit data sharing framework. This is the first exploration to (1) investigate the secure data sharing problem in EDA and (2) generate protected circuit features that hide important circuit information while preserving sufficient information for a well-known EDA application, lithographic hotspot detection. Our results demonstrate that our approach successfully protects raw circuit features, providing 55% superior protection over existing state-of-the-art techniques in computer vision. Moreover, models trained with our protected data achieve up to 48% higher accuracy than models trained with limited raw data. This shows the effectiveness of PRICING in enhancing model development for EDA.

Generating diverse VLSI layout patterns is essential for various downstream tasks in design for manufacturing, as design rules continually evolve during the development of new technology nodes. However, existing training-based methods for layout pattern generation rely on large datasets. In practical scenarios, especially when developing a new technology node, obtaining such extensive layout data is challenging. Consequently, training models with large datasets becomes impractical, limiting the scalability and adaptability of prior approaches. To this end, we propose PatternPaint, a diffusion-based framework capable of generating legal patterns with limited design-rule-compliant training samples. PatternPaint simplifies complex layout pattern generation into a series of inpainting processes with a template-based denoising scheme. Furthermore, we perform few-shot finetuning on a pretrained image foundation model with only 20 design-rule-compliant samples. Experimental results show that using a sub-3nm technology node (Intel 18A), our model is the only one that can generate legal patterns in complex 2D metal interconnect design rule settings among all previous works and achieves a high diversity score. Additionally, our few-shot finetuning can boost the legality rate by 1.87 X compared to the original pretrained model. As a result, we demonstrate a production-ready approach for layout pattern generation in developing new technology nodes.

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.

Systolic arrays have become a popular hardware architecture for machine learning computing, which is a key driver for the growth of the semiconductor industry. Unlike many other circuits, systolic arrays exhibit distinct 2D regularity, which holds significant potential for improving physical design quality. However, this regularity is largely overlooked in existing physical design methodologies.

Tiled architectures have emerged as a compelling platform for scaling deep neural network (DNN) execution, offering both compute density and communication efficiency.To harness their full potential, effective inter-layer scheduling is crucial for managing operation order, memory behavior, and compute resource coordination.However, current schedulers often fall short due to three persistent issues: incomplete treatment of core design factors, limited flexibility in handling diverse workload structures, and reliance on heuristic search algorithms with poor convergence.In this work, we trace these limitations to the absence of a unified and expressive scheduling representation.We introduce Crane, a framework that addresses these gaps through a hierarchical tableformat abstraction capable of encoding rich scheduling semantics.Crane supports both inference and training workloads, and reformulates scheduling as a mathematically structured optimization problem, enabling more complete and efficient exploration of the scheduling space.Evaluations show that Crane reduces energydelay product by up to 21.01× and improves scheduling speed by at least 2.82× over state-of-the-art baselines.

The growing complexity of CNNs demands both hardware acceleration design and dataflow mapping solutions. The large co-design solution space presents a huge challenge. We introduce an analytical model for assessing CNN hardware design and dataflow solutions, using a matrix-based approach. Our co-optimization method, combining nonlinear programming and parallel local search, excels in addressing the power-performance-area tradeoff. The average relative error of our analytical model compared with Timeloop is as small as 1%. Compared to state-of-the-art methods, our co-optimization achieves solutions with average$3.14\times $shorter inference latency,$\mathbf {68.2\%}$less power consumption, and$\mathbf {74\%}$less area on all testcases. It also provides a$200\times $speedup of optimization runtime.

Cell placement is a step of paramount importance in chip physical design and requests relentless effort for continuous improvement. Recently, designs with two-dimensional (2D) processing element arrays have become popular primarily due to their deep neural network hardware applications. The 2D array regularity is similar to but different from the regularity of conventional datapath designs. To exploit the 2D array regularity, this work develops a new global placement technique, Placement of Arrays with SOft Regularity (PASOR), built upon RePlAce, the state-of-the-art placement framework. Experimental results from various designs show that the proposed approach can reduce global routing wirelength by 11% and 6% compared to RePlAce and a previous work on datapath driven placement, respectively.

Within the rapidly evolving domain of Electronic Design Automation (EDA), Large Language Models (LLMs) have emerged as transformative technologies, offering unprecedented capabilities for optimizing and automating various aspects of electronic design. This survey provides a comprehensive exploration of LLM applications in EDA, focusing on advancements in model architectures, the implications of varying model sizes, and innovative customization techniques that enable tailored analytical insights. By examining the intersection of LLM capabilities and EDA requirements, the article highlights the significant impact these models have on extracting nuanced understandings from complex datasets. Furthermore, it addresses the challenges and opportunities in integrating LLMs into EDA workflows, paving the way for future research and application in this dynamic field. Through this detailed analysis, the survey aims to offer valuable insights to professionals in the EDA industry, AI researchers, and anyone interested in the convergence of advanced AI technologies and electronic design.

Many real-world CNNs exhibit sparsity, a characteristic that has primarily been utilized in manual design processes and has received little attention in existing automatic optimization techniques. To the best of our knowledge, this paper presents the first systematic investigation of automatic dataflow and hardware optimization for sparse CNN computation. A differentiable PPA (Power Performance Area) model incorporating stochastic modeling of sparse CNN workloads is developed to enable fast nonlinear optimization solving and massively parallel local search-based discretization. Experimental results on public domain testcases demonstrate the efficacy of the proposed approach, achieving an average of 5× and 10× better PPA than the previous work for two different sparsity patterns.

Systolic array designs are gaining popularity due to their applications in hardware acceleration for ML computing, such as CNNs and transformers. Increasingly large ML models necessitate very high circuit energy-efficiency, which is highly correlated with minimizing placement wirelength in chip physical design. However, existing placement techniques are mostly general purpose and overlook unique properties of systolic array designs. We propose a mixed-size placement approach, called SysMix, which is tailored for systolic arrays and leverage their partial regularity in hierarchical design methodologies. Experimental results from multiple CNN designs show that SysMix achieves 53% wirelength reduction and 15X speedup compared to a commercial placer and a state-of-the-art academic placer.

Microprocessor validation is a complex task that consumes substantial engineering time. Degradation of the system performance that does not affect its functional correctness, is particularly difficult to address given the lack of a golden reference for performance. This work introduces an automated methodology based on machine learning to assist in localizing performance faults, aiming to speed up the validation process. Our results show that, for the injected performance issues, whose average IPC impact is$> 1{\%}$, our technique is able to help localize the exact microarchitectural unit where the degradation occurs$\sim$75% of the time while achieving a top-3 unit accuracy (out of 11 possible locations) of$> 97{\%}$. The proposed setup requires a few seconds to perform a localization inference, leading to a reduced validation time.

The rise of machine learning (ML) technology inspires a boom of its applications in electronic design automation (EDA) and helps improve the degree of automation in chip designs. However, manually crafting ML models remains a complex and time-consuming process because it requires extensive human expertise and tremendous engineering efforts to carefully extract features and design model architectures. In this work, we leverage automated ML techniques to automate the ML model development for routability prediction, a well-established technique that can help to guide cell placement toward routable solutions. We present an automated feature selection method to identify suitable features for model inputs. We develop a neural architecture search method to search for high-quality neural architectures without human interference. Our search method supports various operations and highly flexible connections, leading to architectures significantly different from all previous human-crafted models. Our experimental results demonstrate that our automatically generated models clearly outperform multiple representative manually crafted solutions with a superior 9.9% improvement. Moreover, compared with human-crafted models, which easily take weeks or months to develop, our efficient automated machine learning framework completes the whole model development process with only 1 day.

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.

Machine learning (ML)-based techniques for electronic design automation (EDA) have boosted the performance of modern integrated circuits (ICs). Such achievement makes ML model to be of importance for the EDA industry. In addition, ML models for EDA are widely considered having high development cost because of the time-consuming and complicated training data generation process. Thus, confidentiality protection for EDA models is a critical issue. However, an adversary could apply model extraction attacks to steal the model in the sense of achieving the comparable performance to the victim's model. As model extraction attacks have posed great threats to other application domains, e.g., computer vision and natural language process, in this paper, we study model extraction attacks for EDA models under two real-world scenarios. It is the first work that (1) introduces model extraction attacks on EDA models and (2) proposes two attack methods against the unlimited and limited query budget scenarios. Our results show that our approach can achieve competitive performance with the well-trained victim model without any performance degradation. Based on the results, we demonstrate that model extraction attacks truly threaten the EDA model privacy and hope to raise concerns about ML security issues in EDA.

Analog integrated circuit (IC) placement is a heavily manual and time-consuming task that has a significant impact on chip quality. Several recent studies apply machine learning (ML) techniques to directly predict the impact of placement on circuit performance or even guide the placement process. However, the significant diversity in analog design topologies can lead to different impacts on performance metrics (e.g., common-mode rejection ratio (CMRR) or offset voltage). Thus, it is unlikely that the same ML model structure will achieve the best performance for all designs and metrics. In addition, customizing ML models for different designs require more tremendous engineering efforts and longer development cycles. In this work, we leverage Neural Architecture Search (NAS) to automatically develop customized neural architectures for different analog circuit designs and metrics. Our proposed NAS methodology supports an unconstrained DAG-based search space containing a wide range of ML operations and topological connections. Our search strategy can efficiently explore this flexible search space and provide every design with the best-customized model to boost the model performance. We make unprejudiced comparisons with the claimed performance of the previous representative work on exactly the same dataset. After fully automated development within only 0.5 days, generated models give 3.61% superior accuracy than the prior art.

Buffering is a prevalent interconnect optimization technique to help timing closure and is often performed after placement. A common buffering approach is to construct a Steiner tree and then buffers are inserted on the tree based on Ginneken-Lillis style algorithm. Such an approach is difficult to scale with large nets. Our work attempts to solve this problem with a generative machine-learning (ML) approach without Steiner tree construction. Our approach can extract and reuse knowledge from high quality samples and therefore has significantly improved scalability. A generative ML framework, BufFormer, is proposed to construct abstract tree topology while simultaneously determining buffer sizes & locations. A baseline method, FLUTE-based Steiner tree construction followed by Ginneken-Lillis style buffer insertion, is implemented to generate training samples. After training, BufFormer can produce solutions for unseen nets highly comparable to baseline results with a correlation coefficient 0.977 in terms of buffer area and 0.934 for driver-sink delays. On average, BufFormer-generated tree achieves similar delays with slightly larger buffer area. And up to 160X speedup can be achieved for large nets when running on a GPU over the baseline on a single CPU thread.

Systolic array designs have regained popularity in recent years, particularly for their applications in accelerating CNN (Convolutional Neural Network) computing in hardware, including on FPGAs. However, existing FPGA layout techniques are primarily designed for general-purpose applications and have not fully leveraged the regularity of systolic arrays to enhance solution quality. This paper presents a new algorithmic approach for systolic array placement on FPGAs. Our approach enables 23% – 25% wirelength reduction for CNN circuits compared to an industrial tool and state-of-the-art academic methods. Moreover, it usually leads to significantly reduced routing resource utilization, accelerated placement runtime and improved timing performance.

SoC design teams embrace new technologies and methodologies that bring clear value. Given this, future infusion of AI into design closure and signoff is inevitable. Predictive AI models help focus the application of last-mile incremental optimizations (sizing, placement and routing) to achieve timing and noise closure; successful examples range from routing-free crosstalk prediction to timing/power evaluation in early RTL development. Design closure becomes more efficient when “imperfect but fast” ML inferencing is used to filter out potential violations, which can then be passed to golden analysis tools. Learning methods also improve the design process in many ways, ranging from smarter PVT corner selection to predicting the CPU and memory usage of signoff tools. At a higher level, AI will help design teams learn to avoid design trajectories that lead to time-consuming closure and signoff iterations. This talk will provide a broad overview of directions in which AI will inevitably improve the cost and efficiency of signoff in the coming years.

In this paper we present an approximate division scheme for Scaled Population (SP) arithmetic, a technique that improves on the limitations of stochastic computing (SC). SP arithmetic circuits are designed (a) to perform all operations with a constant delay, and (b) they use scaling operations to help reduce errors compared to SC circuits. As part of this work, we also present a method to correlate two SP numbers with a constant delay. We compare our SP divider with SC dividers, as well as fixed-point dividers (in terms of area, power and delay). Our 512-bit SP divider has a delay (power) that is 0.08× (0.06x×) that of the equivalent fixed-point binary divider. Compared to a equivalent SC divider, our power-delay-product is 13× better.

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.

The growing integrated circuit complexity has led to a compelling need for design efficiency improvement through new electronic design automation (EDA) methodologies. In recent years, many unprecedented efficient EDA methods have been enabled by machine learning (ML) techniques. While ML demonstrates its great potential in circuit design, however, the dark side about potential security and model reliability problems, is seldomly discussed. This article gives a comprehensive and impartial summary of all security and reliability concerns we have observed in ML for EDA. Many of them are hidden or neglected by practitioners in this field. In this article, we first provide our taxonomy to define four major types of concerns, then we analyze different application scenarios and special properties in ML for EDA. After that, we present our detailed and impartial analysis of each type of concern with experiments.

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.

The finite element method has wide applications and often presents a computing challenge due to huge problem sizes and slow convergence rate. A leading-edge computing acceleration approach is to leverage wafer-scale engine, which contains more than 800K processing elements. The effectiveness of this approach heavily depends on how to map a finite element computing task onto such enormous hardware space. A mapping method is introduced to partition an object space into computing kernels, which are further placed onto processing elements. This method achieves the best overall result in terms of computing accuracy and communication cost among all the ISPD 2021 contest participants.

Applying machine learning (ML) in design flow is a popular trend in Electronic Design Automation (EDA) with various applications from design quality predictions to optimizations. Despite its promise, which has been demonstrated in both academic researches and industrial tools, its effectiveness largely hinges on the availability of a large amount of high-quality training data. In reality, EDA developers have very limited access to the latest design data, which is owned by design companies and mostly confidential. Although one can commission ML model training to a design company, the data of a single company might be still inadequate or biased, especially for small companies. Such data availability problem is becoming the limiting constraint on future growth of ML for chip design. In this work, we propose an Federated-Learning based approach for well-studied ML applications in EDA. Our approach allows an ML model to be collaboratively trained with data from multiple clients but without explicit access to the data for respecting their data privacy. To further strengthen the results, we co-design a customized ML model FLNet and its personalization under the decentralized training scenario. Experiments on a comprehensive dataset show that collaborative training improves accuracy by 11% compared with individual local models, and our customized model FLNet significantly outperforms the best of previous routability estimators in this collaborative training flow.

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.

Reinforcement learning (RL) is an effective and increasingly popular machine learning approach for optimization and decision-making. However, modern reinforcement learning techniques, such as deep Q-learning, often require neural network inference and training, and therefore are computationally expensive. For example, Twin-Delay Deep Deterministic Policy Gradient (TD3), a state-of-the-art RL technique, uses as many as 6 neural networks. In this work, we study the FPGA-based acceleration of TD3. To address the resource and computational overhead due to inference and training of the multiple neural networks of TD3, we propose TD3lite, an integrated approach consisting of a network sharing technique combined with bitwidth-optimized block floating-point arithmetic. TD3lite is evaluated on several robotic benchmarks with continuous state and action spaces. With only 5.7% learning performance degradation, TD3lite achieves 21 ×and 8 ×speedup compared to CPU and GPU implementations, respectively. Its energy efficiency is 26 ×of the GPU implementation. Moreover, it utilizes ~ 25 - 40% fewer FPGA resources compared to a conventional sinale-precision floating-point representation of TD3.

The continuous growth of CNN complexity not only intensifies the need for hardware acceleration but also presents a huge challenge. That is, the solution space for CNN hardware design and dataflow mapping becomes enormously large besides the fact that it is discrete and lacks a well behaved structure. Most previous works either are stochastic metaheuristics, such as genetic algorithm, which are typically very slow for solving large problems, or rely on expensive sampling, e.g., Gumbel Softmax-based differentiable optimization and Bayesian optimization. We propose an analytical model for evaluating power and performance of CNN hardware design and dataflow solutions. Based on this model, we introduce a co-optimization method consisting of nonlinear programming and parallel local search. A key innovation in this model is its matrix form, which enables the use of deep learning toolkit for highly efficient computations of power/performance values and gradients in the optimization. In handling power-performance tradeoff, our method can lead to better solutions than minimizing a weighted sum of power and latency. The average relative error of our model compared with Timeloop is as small as 1%. Compared to state-of-the-art methods, our approach achieves solutions with up to 1.7 × shorter inference latency, 37.5% less power consumption, and 3 × less area on ResNet 18. Moreover, it provides a 6.2 × speedup of optimization runtime.

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

Deep learning has been widely applied in various VLSI design automation tasks, from layout quality estimation to design optimization. Though deep learning has shown state-of-the-art performance in several applications, recent studies reveal that deep neural networks exhibit intrinsic vulnerability to adversarial perturbations, which pose risks in the ML-aided VLSI design flow. One of the most effective strategies to improve robustness is regularization approaches, which adjust the optimization objective to make the deep neural network generalize better. In this paper, we examine several adversarial defense methods to improve the robustness of ML-based lithography hotspot detectors. We present an innovative design rule checking (DRC)-guided curvature regularization (CURE) approach, which is customized to robustify ML-based lithography hotspot detectors against white-box attacks. Our approach allows for improvements in both the robustness and the accuracy of the model. Experiments show that the model optimized by DRC-guided CURE achieves the highest robustness and accuracy compared with those trained using the baseline defense methods. Compared with the vanilla model, DRC-guided CURE decreases the average attack success rate by 53.9% and increases the average ROC-AUC by 12.1%. Compared with the best of the defense baselines, DRC-guided CURE reduces the average attack success rate by 18.6% and improves the average ROC-AUC by 4.3%.

Hardware Description Language (HDL) is a common entry point for designing digital circuits. Differences in HDL coding styles and design choices may lead to considerably different design quality and performance-power tradeoff. In general, the impact of HDL coding is not clear until logic synthesis or even layout is completed. However, running synthesis merely as a feedback for HDL code is computationally not economical especially in early design phases when the code needs to be frequently modified. Furthermore, in late stages of design convergence burdened with high-impact engineering change orders (ECO's), design iterations become prohibitively expensive. To this end, we propose a machine learning approach to Verilog-based Register-Transfer Level (RTL) design assessment without going through the synthesis process. It would allow designers to quickly evaluate the performance-power tradeoff among different options of RTL designs. Experimental results show that our proposed technique achieves an average of 95% prediction accuracy in terms of post-placement analysis, and is 6 orders of magnitude faster than evaluation by running logic synthesis and placement.

Accurate and efficient on-chip power modeling is crucial to runtime power, energy, and voltage management. Such power monitoring can be achieved by designing and integrating on-chip power meters (OPMs) into the target design. In this work, we propose a new method named DEEP to automatically develop extremely efficient OPM solutions for a given design. DEEP selects OPM inputs from all individual bits in RTL signals. Such bit-level selection provides an unprecedentedly large number of input candidates and supports lower hardware cost, compared with signal-level selection in prior works. In addition, DEEP proposes a powerful two-step OPM input selection method, and it supports reporting both total power and the power of major design components. Experiments on a commercial microprocessor demonstrate that DEEP's OPM solution achieves correlation R > 0.97 in per-cycle power prediction with an unprecedented low area overhead on hardware, i.e., < 0.1% of the microprocessor layout. This reduces the OPM hardware cost by 4 -- 6× compared with the state-of-the-art solution.

Cell placement is such a critical step for chip physical design that it needs many kinds of efforts for improvement. Recently, designs with 2D processing element arrays have become popular primarily due to their deep neural network computing applications. The 2D array regularity is similar to but different from the regularity of conventional datapath designs. To exploit the 2D array regularity, this work develops a new global placement technique built upon RePlAce, the latest state-of-the-art placement framework. Experimental results from various designs show that the proposed technique can reduce half-perimeter wirelength and Steiner tree wirelength by about $6%$ and $12%$, respectively.

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

Net length is a key proxy metric for optimizing timing and power across various stages of a standard digital design flow. However, the bulk of net length information is not available until cell placement, and hence, it is a significant challenge to explicitly consider net length optimization in design stages prior to placement, such as logic synthesis. In addition, the absence of net length information makes accurate preplacement timing estimation extremely difficult. Poor predictability on the timing not only affects timing optimizations but also hampers the accurate evaluation of synthesis solutions. This work addresses these challenges by a preplacement prediction flow with estimators on both net length and timing. We propose a graph attention network (GAT) method with customization, called Net2, to estimate individual net length before cell placement. Its accuracy-oriented version Net2a achieves about 15% better accuracy than several previous works in identifying both long nets and long critical paths. Its fast version Net2f is more than$1000\times $faster than placement while still outperforms previous works and other neural network techniques in terms of various accuracy metrics. Based on net size estimations, we propose the first machine learning-based preplacement timing estimator. Compared with the preplacement timing report from commercial tools, it improves the correlation coefficient in arc delays by 0.08, and reduces the mean absolute error in slack, worst negative slack, and total negative slack estimations by more than 50%.

Data-Flow Integrity (DFI) is a well-known approach to effectively detecting a wide range of software attacks. However, its real-world application has been quite limited so far because of the prohibitive performance overhead it incurs. Moreover, the overhead is enormously difficult to overcome without substantially lowering the DFI criterion. In this work, an analysis is performed to understand the main factors contributing to the overhead. Accordingly, a hardware-assisted parallel approach is proposed to tackle the overhead challenge. Simulations on SPEC CPU 2006 benchmark show that the proposed approach can completely enforce the DFI defined in the original seminal work while reducing performance overhead by 4×, on average.

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.

Net length is a key proxy metric for optimizing timing and power across various stages of a standard digital design flow. However, the bulk of net length information is not available until cell placement, and hence it is a significant challenge to explicitly consider net length optimization in design stages prior to placement, such as logic synthesis. This work addresses this challenge by proposing a graph attention network method with customization, called Net2, to estimate individual net length before cell placement. Its accuracy-oriented version Net2a achieves about 15% better accuracy than several previous works in identifying both long nets and long critical paths. Its fast version Net2f is more than 1000x faster than placement while still outperforms previous works and other neural network techniques in terms of various accuracy metrics.

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.

Processor design validation and debug is a difficult and complex task, which consumes the lion's share of the design process. Design bugs that affect processor performance rather than its functionality are especially difficult to catch, particularly in new microarchitectures. This is because, unlike functional bugs, the correct processor performance of new microarchitectures on complex, long-running benchmarks is typically not deterministically known. Thus, when performance benchmarking new microarchitectures, performance teams may assume that the design is correct when the performance of the new microarchitecture exceeds that of the previous generation, despite significant performance regressions existing in the design. In this work we present a two-stage, machine learning-based methodology that is able to detect the existence of performance bugs in microprocessors. Our results show that our best technique detects 91.5% of microprocessor core performance bugs whose average IPC impact across the studied applications is greater than 1% versus a bug-free design with zero false positives. When evaluated on memory system bugs, our technique achieves 100% detection with zero false positives. Moreover, the detection is automatic, requiring very little performance engineer time.

The rise of machine learning technology inspires a boom of its applications in electronic design automation (EDA) and helps improve the degree of automation in chip designs. However, manually crafted machine learning models require extensive human expertise and tremendous engineering efforts. In this work, we leverage neural architecture search (NAS) to automate the development of high-quality neural architectures for routability prediction, which can help to guide cell placement toward routable solutions. Our search method supports various operations and highly flexible connections, leading to architectures significantly different from all previous human-crafted models. Experimental results on a large dataset demonstrate that our automatically generated neural architectures clearly outperform multiple representative manually crafted solutions. Compared to the best case of manually crafted models, NAS-generated models achieve 5.85% higher Kendall's$T$in predicting the number of nets with DRC violations and 2.12% better area under ROC curve (ROC-AUC) in DRC hotspot detection. Moreover, compared with human-crafted models, which easily take weeks to develop, our efficient NAS approach finishes the whole automatic search process with only 0.3 days.

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

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

Accurate power modeling is crucial for energy-efficient CPU design and runtime management. An ideal power modeling framework needs to be accurate yet fast, achieve high temporal resolution (ideally cycle-accurate) yet with low runtime computational overheads, and easily extensible to diverse designs through automation. Simultaneously satisfying such conflicting objectives is challenging and largely unattained despite significant prior research.

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.

Control-Flow Integrity (CFI) is an effective defense technique against a variety of memory-based cyber attacks. CFI is usually enforced through software methods, which entail considerable performance overhead. Hardware-based CFI techniques can largely avoid performance overhead, but typically rely on code instrumentation, forming a non-trivial hurdle to the application of CFI. Taking advantage of the tradeoff between computing efficiency and flexibility of FPGA, we develop FastCFI, an FPGA-based CFI system that can perform fine-grained and stateful checking without code instrumentation. We also propose an automated Verilog generation technique that facilitates fast deployment of FastCFI, and a compression algorithm for reducing the hardware expense. Experiments on popular benchmarks confirm that FastCFI can detect fine-grained CFI violations over unmodified binaries. When using FastCFI on prevalent benchmarks, we demonstrate its capability to detect fine-grained CFI violations in unmodified binaries, while incurring an average of 0.36% overhead and a maximum of 2.93% overhead.

Design flow parameters are of utmost importance to chip design quality and require a painfully long time to evaluate their effects. In reality, flow parameter tuning is usually performed manually based on designers' experience in an ad hoc manner. In this work, we introduce a machine learning-based automatic parameter tuning methodology that aims to find the best design quality with a limited number of trials. Instead of merely plugging in machine learning engines, we develop clustering and approximate sampling techniques for improving tuning efficiency. The feature extraction in this method can reuse knowledge from prior designs. Furthermore, we leverage a state-of-the-art XGBoost model and propose a novel dynamic tree technique to overcome overfitting. Experimental results on benchmark circuits show that our approach achieves 25% improvement in design quality or 37% reduction in sampling cost compared to random forest method, which is the kernel of a highly cited previous work. Our approach is further validated on two industrial designs. By sampling less than 0.02% of possible parameter sets, it reduces area by 1.83% and 1.43% compared to the best solutions hand-tuned by experienced designers.

IR drop is a fundamental constraint required by almost all chip designs. However, its evaluation usually takes a long time that hinders mitigation techniques for fixing its violations. In this work, we develop a fast dynamic IR drop estimation technique, named PowerNet, based on a convolutional neural network (CNN). It can handle both vector-based and vectorless IR analyses. Moreover, the proposed CNN model is general and transferable to different designs. This is in contrast to most existing machine learning (ML) approaches, where a model is applicable only to a specific design. Experimental results show that PowerNet outperforms the latest ML method by 9% in accuracy for the challenging case of vectorless IR drop and achieves a 30× speedup compared to an accurate IR drop commercial tool. Further, a mitigation tool guided by PowerNet reduces IR drop hotspots by 26% and 31% on two industrial designs, respectively, with very limited modification on their power grids.

Wafer inspection locates defects at early fabrication stages and traditionally focuses on pixel-level defects. However, there are very few solutions that can effectively detect largescale defects. In this work, we leverage Convolutional Neural Networks (CNNs) to automate the wafer inspection process and propose several techniques to preprocess and augment wafer images for enhancing our model's generalization on unseen wafers (e.g., from other fabs). Cross-fab experimental results of both wafer-level and pixel-level detections show that the F1 score increases from 0.09 to 0.77 and the Precision-Recall area under curve (PR AUC) increases from 0.03 to 0.62 using our proposed method.

We propose a new Scaled Population (SP) based arithmetic computation approach that achieves considerable improvements over existing stochastic computing (SC) techniques. First, SP arithmetic introduces scaling operations that significantly reduce the numerical errors as compared to SC. Experiments show accuracy improvements of a single multiplication and addition operation by 6.3× and 4.0×, respectively. Secondly, SP arithmetic erases the inherent serialization associated with stochastic computing, thereby significantly improves the computational delays. We design each of the operations of SP arithmetic to take O(1) gate delays, and eliminate the need of serially iterating over the bits of the population vector. Our SP approach improves the area, delay and power compared with conventional stochastic computing on an FPGA-based implementation. We also apply our SP scheme on a handwritten digit recognition application (MNIST), improving the recognition accuracy by 32.79% compared to SC.

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

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

IR drop constraint is a fundamental requirement enforced in almost all chip designs. However, its evaluation takes a long time, and mitigation techniques for fixing violations may require numerous iterations. As such, fast and accurate IR drop prediction becomes critical for reducing design turnaround time. Recently, machine learning (ML) techniques have been actively studied for fast IR drop estimation due to their promise and success in many fields. These studies target at various design stages with different emphasis, and accordingly, different ML algorithms are adopted and customized. This paper provides a review to the latest progress in ML-based IR drop estimation techniques. It also serves as a vehicle for discussing some general challenges faced by ML applications in electronics design automation (EDA), and demonstrating how to integrate ML models with conventional techniques for the better efficiency of EDA tools.

In this paper we present Scaled Population Subtraction to fill a void in Scaled Population arithmetic. Scaled population (SP) arithmetic is a scheme that is inspired by stochastic computing (SC), a non-conventional approximate computing method that is well known for its simplicity, area efficiency and resilience to bit errors. SP arithmetic reduces the numerical errors compared to SC and also solves the serialization limitation of SC, since it is designed to have a O(1) gate delay. Previously, SP was limited to only addition and multiplication and did not have a way to perform subtraction. This paper introduces the basic SP subtraction idea, followed by a detailed study of several ways that the basic design can be improved to reduce the computational error. Our best SP design significantly improves the error compared to our basic SP subtraction idea (reducing it by 32.3%). We also study the trade-off between design complexity of the SP subtractor against output error. Also, our implementation of the SP subtractor exhibits an improved delay, power and area compared to fixed point realizations with the same size.

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.

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

Analog/RF performance locking techniques insert configurable components to obfuscate the biasing or the design parameters of the secured analog block. The locked circuit meets the specifications only under a specific configuration decided by the correct common key, shared by all chip instances of the same design. Key provisioning enables the design of distinct user keys for individual chip instances. This area has received little research attention, and a naive approach yields large area overhead when increasing the key size. We propose a new approach based on a Schmitt trigger (ST) circuit with configurable hysteresis. The proposed key provisioning is compatible with existing analog locking techniques and has a constant area overhead regardless of key size. This approach is tested with three analog/RF circuits to demonstrate its area scalability and effectiveness on security.

Low power system-on-chips (SoCs) are now at the heart of Internet-of-Things (IoT) devices, which are well-known for their bursty workloads and limited energy storage-usually in the form of tiny batteries. To ensure battery lifetime, dynamic voltage frequency scaling (DVFS) has become an essential technique in such SoC chips. With continuously decreasing supply level, noise margins in these devices are already being squeezed. During DVFS transition, large current that accompanies the clock speed transition runs into or out of clock networks in a few clock cycles, induces large Ldi/dt noise, thereby stressing the power delivery system (PDS). Due to the limited area and cost target, adding additional decoupling capacitance to mitigate such noise is usually challenging. A common approach is to gradually introduce/remove the additional clock cycles to increase/decrease the clock frequency in steps, also known as, clock skipping. However, such a technique may increase DVFS transition time, and still cannot guarantee minimal noise. In this paper, we propose a new noise-aware DVFS sequence optimization technique by formulating a mixed 0/1 programming to resolve the problems of clock skipping sequence optimization. Moreover, the method is also extended to schedule extensive wake-up activities on different clock domains for the same purpose. The experiments show that the optimized sequence is able to significantly mitigate noise within the desired transition time, thereby saving both power and energy.

Similar to digital circuits, analog circuits are also susceptible to supply-chain attacks. There are several analog locking techniques proposed to combat these supply-chain attacks. However, there exists no elaborate evaluation procedure to estimate the resilience offered by these techniques. Evaluating analog defenses requires the usage of non-Boolean variables, such as bias current and gain. Hence, in this work, we evaluate the resilience of the analog-only locks and analog and mixed-signal (AMS) locks using satisfiability modulo theories (SMTs). We demonstrate our attack on five analog locking techniques and three AMS locking techniques. The attack is demonstrated on commonly used circuits, such as bandpass filter (BPF), low-noise amplifier (LNA), and low-dropout (LDO) voltage regulator. Attack results on analog-only locks show that the attacker, knowing the required bias current or voltage range, can determine the key. Likewise, knowing the protected input patterns (PIPs), the attacker can determine the key to unlock the AMS locks. We then extend our attack to break the existing analog camouflaging technique.

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.

One technique to prevent attacks from an untrusted foundry is split manufacturing, where only a part of the layout is sent to the untrusted high-end foundry, and the rest is manufactured at a trusted low-end foundry. The untrusted foundry has front-end-of-line (FEOL) layout and the original circuit netlist and attempts to identify critical components on the layout for Trojan insertion. Although defense methods for this scenario have been developed, the corresponding attack technique is not well explored. For instance, Boolean satisfiability (SAT) based bijective mapping attack is mentioned without detailed research. Hence, the defense methods are mostly evaluated with the k-security metric without actual attacks. We provide the first systematic study, to the best of our knowledge, on attack techniques in this scenario. Besides of implementing SAT-based bijective mapping attack, we develop a new attack technique based on structural pattern matching. Experimental comparison with bijective mapping attack shows that the new attack technique achieves about the same success rate with much faster speed for cases without the k-security defense, and has a much better success rate at the same runtime for cases with k-security defense. The results offer an alternative and practical interpretation for k-security in split manufacturing.

Optimizations at placement stage need to be guided by timing estimation prior to routing. To handle timing uncertainty due to the lack of routing information, people tend to make very pessimistic predictions such that performance specification can be ensured in the worst case. Such pessimism causes over-design that wastes chip resources or design effort. In this work, a machine learning-based pre-routing timing prediction approach is introduced. Experimental results show that it can reach accuracy near post-routing sign-off analysis. Compared to a commercial pre-routing timing estimation tool, it reduces false positive rate by about 2/3 in reporting timing violations.

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.

Although Markov Decision Process (MDP) has wide applications in autonomous systems as a core model in Reinforcement Learning, a key bottleneck is the large memory utilization of the state transition probability matrices. This is particularly problematic for computational platforms with limited memory, or for Bayesian MDP, which requires dozens of such matrices. To mitigate this difficulty, we propose a highly memory-efficient representation for probability matrices using Binary Decision Diagram (BDD) based sampling, and develop a corresponding (Bayesian/classical) MDP solver on a CPU-GPU platform. Simulation results indicate our approach reduces memory by one and two orders of magnitude for Bayesian/classical MDP, respectively.

With the dramatic shrink of feature size and the advance of semiconductor technology nodes, numerous and complicated design rules need to be followed, and a chip design can only be taped-out after passing design rule check (DRC). The high design complexity seriously deteriorates design routability, which can be measured by the number of DRC violations after the detailed routing stage. In addition, a modern large-scaled design typically consists of many huge macros due to the wide use of intellectual properties (IPs). Empirically, the placement of these macros greatly determines routability, while there exists no effective cost metric to directly evaluate a macro placement because of the extremely high complexity and unpredictability of cell placement and routing. In this paper, we propose the first work of routability-driven macro placement with deep learning. A convolutional neural network (CNN)-based routability prediction model is proposed and embedded into a macro placer such that a good macro placement with minimized DRC violations can be derived through a simulated annealing (SA) optimization process. Experimental results show the accuracy of the predictor and the effectiveness of the macro placer.

Similar to digital circuits, analog circuits are also susceptible to supply-chain attacks, such as intellectual property (IP) piracy, counterfeiting, and overproduction. Hence, analog locking techniques have been proposed to combat supply-chain attacks. However, there exists no evaluation procedure to estimate the resilience offered by these defense techniques. Evaluating analog defense techniques requires the usage of non-Boolean variables, such as bias current, bias voltage, and gain. However, it cannot be handled by the Boolean satisfiability (SAT) attack. In this work, we propose an evaluation technique based on satisfiability modulo theories (SMT). We demonstrate our attack on four state-of-the-art analog locking techniques using commonly used circuits, such as bandpass filter (BPF), LC oscillator, quadrature oscillator, and class-D amplifiers. Our results show that the attacker, knowing the required bias current values, can determine the key in polynomial time. We also show that even if he/she has only partial information about the bias currents, the search space can be reduced from exponential to a polynomial number of keys. We then extend our attack to break existing analog camouflaging techniques.

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.

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.

At nanometer manufacturing technology nodes, process variations affect circuit performance significantly. This trend leads to a large timing margin and thus overdesign in the traditional worst-case circuit design flow. To combat this pessimism, post-silicon clock tuning buffers can be deployed to balance timing slacks of consecutive combinational paths in individual chips by tuning clock skews after manufacturing. A challenge of this method is that path delays of each chip with timing failures should be measured to gather the information for clock skew configuration. However, current methods for delay measurement rely on path-wise frequency stepping, which requires much time from expensive testers. In this paper, we propose an efficient delay test framework (EffiTest2) to solve the post-silicon testing problem by testing only representative paths with delay alignment using the already-existing tunable buffers in the circuit. Experimental results demonstrate that EffiTest2 can reduce the number of frequency stepping iterations by more than 94% with only a slight yield loss.

Serverless or functions as a service runtimes have shown significant benefits to efficiency and cost for event-driven cloud applications. Although serverless runtimes are limited to applications requiring lightweight computation and memory, such as machine learning prediction and inference, they have shown improvements on these applications beyond other cloud runtimes. Training deep learning can be both compute and memory intensive. We investigate the use of serverless runtimes while leveraging data parallelism for large models, show the challenges and limitations due to the tightly coupled nature of such models, and propose modifications to the underlying runtime implementations that would mitigate them. For hyperparameter optimization of smaller deep learning models, we show that serverless runtimes can provide significant benefit.

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.

Similar to digital circuits, analog and mixed-signal (AMS) circuits are also susceptible to supply-chain attacks such as piracy, overproduction, and Trojan insertion. However, unlike digital circuits, supply-chain security of AMS circuits is less explored. In this work, we propose to perform "logic locking" on digital section of the AMS circuits. The idea is to make the analog design intentionally suffer from the effects of process variations, which impede the operation of the circuit. Only on applying the correct key, the effect of process variations are mitigated, and the analog circuit performs as desired. We provide the theoretical guarantees of the security of the circuit, and along with simulation results for the band-pass filter, low-noise amplifier, and low-dropout regulator, we also show experimental results of our technique on a band-pass filter.

Early routability prediction helps designers and tools perform preventive measures so that design rule violations can be avoided in a proactive manner. However, it is a huge challenge to have a predictor that is both accurate and fast. In this work, we study how to leverage convolutional neural network to address this challenge. The proposed method, called RouteNet, can either evaluate the overall routability of cell placement solutions without global routing or predict the locations of DRC (Design Rule Checking) hotspots. In both cases, large macros in mixed-size designs are taken into consideration. Experiments on benchmark circuits show that RouteNet can forecast overall routability with accuracy similar to that of global router while using substantially less runtime. For DRC hotspot prediction, RouteNet improves accuracy by 50% compared to global routing. It also significantly outperforms other machine learning approaches such as support vector machine and logistic regression.

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

Split manufacturing can mitigate security vulnerabilities at untrusted foundries by exposing only partial designs. Even so, attackers can make educated guess according to design conventions and thereby recover entire chip designs. In this work, a routing perturbation-based defense method is proposed such that such attacks become very difficult while wirelength/timing overhead is restricted to be very small. Experimental results on benchmark circuits confirm the effectiveness of the proposed techniques. The new techniques also significantly outperform the latest previous work.

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.

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.

Split fabrication is a promising approach to security against attacks by untrusted foundries. While existing split fabrication methods consider the overhead of conventional objectives such as wirelength and timing, they mostly neglect manufacturability - an unavoidable challenge in nanometer technologies. Observing that security and manufacturability can be addressed in a synergistic manner, this work introduces routing techniques that can simultaneously improve both security and manufacturability in terms of either Chemical Mechanical Planarization (CMP) uniformity or Self-Aligned Double Patterning (SADP) compliance. The effectiveness of these techniques is confirmed by experiments on benchmark circuits.

Split fabrication is a promising approach to security against attacks by untrusted foundries. While existing split fabrication methods consider the overhead of conventional objectives such as wirelength and timing, they mostly neglect manufacturability - an unavoidable challenge in nanometer technologies. Observing that security and manufacturability can be addressed in a synergistic manner, this work introduces routing techniques that can simultaneously improve both security and manufacturability in terms of either Chemical Mechanical Planarization (CMP) uniformity or Self-Aligned Double Patterning (SADP) compliance. The effectiveness of these techniques is confirmed by experiments on benchmark circuits.

By splitting the manufacturing of integrated circuits into back-end-of-line (BEOL) and front-end-of-line (FEOL) at different foundries, the vulnerabilities to attacks by a untrusted foundry is considerably alleviated. Most previous works focus on the scenario of only BEOL attacks at untrusted FEOL foundries. In this work, we study a largely unexplored scenario, where FEOL attacks are launched by an untrusted BEOL foundry. A geometric pattern match attack and a machine learningbased attack technique are investigated. Defense techniques against the FEOL attacks are also discussed. The effectiveness of these techniques is demonstrated by experiments on benchmark circuits.

Resource management of modern datacenters needs to consider multiple competing objectives that involve complex system interactions. In this work, Linear Temporal Logic (LTL) is adopted in describing such interactions by leveraging its ability to express complex properties. Further, LTL-based constraints are integrated with reinforcement learning according the recent progress on control synthesis theory. The LTL-constrained reinforcement learning facilitates desired balance among the competing objectives in managing resources for datacenters. The effectiveness of this new approach is demonstrated by two scenarios. In datacenter power management, the LTL-constrained manager reaches the best balance among power, performance and battery stress compared to the previous work and other alternative approaches. In multitenant job scheduling, 200 MapReduce jobs are emulated on the Amazon AWS cloud. The LTL-constrained scheduler achieves the best balance between system performance and fairness compared to several other methods including three Hadoop schedulers.

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.

With a relatively small number of components, analog ICs are much more vulnerable to piracy, and especially reverse engineering, than many digital ICs. However, analog IC security has received much less research attention than digital ICs. We introduce a combinational locking technique using configurable current mirror for analog IC protection. The locking circuit is designed by applying Satisfiability Modulo Theories. With the locking system, only a single key value can make analog IC operate properly while the other key values result in significant performance degradation or malfunction. Moreover, circuit output is not monotone function with respect to key values and thus systematic attack is difficult to be effective. Experimental results demonstrate that this technique can largely thwart analog IC piracy with limited overhead.

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.

Split manufacturing of integrated circuits eliminates vulnerabilities introduced by an untrusted foundry by manufacturing only a part of design at an untrusted high-end foundry and the remaining part at a trusted low-end foundry. Most researchers have focused on attack and defenses for hierarchical designs and/or use a relatively high-end trusted foundry, leading to high cost. We propose an attack and defense for split manufacturing for industry-standard/relevant flattened designs. Our attack uses network-flow model and outperforms previous attacks. We also develop a defense technique using placement perturbation, while considering overhead. The effectiveness of our techniques is demonstrated on benchmark circuits.

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.

The performance growth of conventional VLSI circuits is seriously hampered by various variation effects and the fundamental limit of chip power density. Adaptive circuit design is recognized as a power-efficient approach to tackling the variation challenge. However, it tends to entail large area overhead if not carefully designed. This work studies how to reduce the overhead by forming adaptivity blocks considering both timing and spatial proximity among logic cells. The proximity optimization consists of timing and location aware cell clustering and incremental placement enforcing the clusters. Experiments are performed on the ICCAD 2014 benchmark circuits, which include case of near one million cells. Compared to alternative methods, our approach achieves 1/4 to 3/4 area overhead reduction with an average of 0.6% wirelength overhead, while retains about the same timing yield and power.

With the breakdown of Dennard’s scaling over the past decade, performance growth of modern microprocessor design has largely relied on scaling core count in chip multiprocessors (CMPs). The challenge of chip power density, however, remains and demands new power management solutions. This work investigates a coordinated CMP systemwide Dynamic Voltage and Frequency Scaling (DVFS) policy centered around shared resource utilization. This approach represents a new angle on the problem, differing from the conventional core-workload-driven approaches. The key component of our work is per-core DVFS leveraging a technique similar to TCP Vegas congestion control from networking. This TCP Vegas–based DVFS can potentially identify the synergy between power reduction and performance improvement. Further, this work includes uncore (on-chip interconnect and shared last level cache) and main memory DVFS policies coordinated with the per-core DVFS policy. Full system simulations on PARSEC benchmarks show that our technique reduces total energy dissipation by over 47% across all benchmarks with less than 2.3% performance degradation. Our work also leads to 12% more energy savings compared to a prior work CMP DVFS policy.

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.

Timing analysis is one of the most widely used techniques in digital IC designs. It is increasingly over-loaded by growing circuit sizes and complexities arising from nanometer VLSI technologies. One well-known challenge is process variations, which need to be addressed in timing analysis at least by considering different process corners. Adaptive circuit design, a promising technique for handling variations, further needs statistical static timing analysis (SSTA), which is much more time consuming than variation-oblivious timing analysis. This work explores GPU (Graphic Processing Unit) based parallel computing techniques for accelerating SSTA. Previous works on GPU acceleration are mostly for Monte Carlo based SSTA. By contrast, we focus on SSTA using PCA (Principal Component Analysis), which is intrinsically more efficient. We develop a new batch-based task scheduling algorithm and investigate other speedup techniques such as latency hiding. Experiments are performed on ISPD'13 benchmark suite, which has circuits of over 100K gates. Compared to sequential SSTA, our approach can achieve the identical timing results with average speedup of 22X and 134X on conventional circuits and adaptive circuits, respectively. Our approach is also compared with GPU-based Monte Carlo SSTA and obtains 39X speedup with 0.77% error on timing yield estimation.

The routing of analog integrated circuits (IC) has long been a challenge due to numerous constraints (such as symmetry and topology-matching) that matter for overall circuit performance. Existing automatic analog IC routing algorithms can be broadly categorized into two approaches: sequential approach that heuristically routes one net after another and constructive ILP (Integer Linear Programming). The former approach is usually fast but may miss opportunities of finding good solutions. The constructive ILP provides optimal solutions but can be very time consuming. We propose a simple yet efficient method that combines the advantages of both existing approaches. First, sequential routing is performed to obtain a set of candidate routing paths for each net. Then, an ILP is applied to commit each net to only one of its candidate routes. Experiments on two op-amp designs show that the post-layout performance (such as gain and phase margin) from our method is close to that of manual design. Our method also outperforms a previous work of automated analog IC routing.

Adaptive design is a power-efficient approach to variation resilience in VLSI circuits. However, its implementation, especially that of fine-grained adaptivity, can easily result in large overhead. Although numerous previous works have demonstrated the effectiveness of adaptive design, very few works have emphasized its overhead control. In order to make adaptive design a truly practical approach, we develop a method that systematically optimizes adaptivity assignment with consideration of overhead reduction. At the same time, a variability aware gate implementation selection technique is investigated and applied in conjunction with the adaptivity assignment. Experimental results on benchmark circuits indicate that our approach can greatly decrease adaptivity overhead while satisfy performance and robustness constraints.

Typically in computer systems, performance must be traded-off to achieve energy savings or, conversely, performance gains come with significant energy overhead. Here, we present a novel approach that can achieve synergistic energy-savings and performance gain in chip multiprocessors (CMPs). Our key observation is that per-core dynamic voltage/frequency scaling (DVFS) can be used as a client regulation mechanism for shared resources on-die. Based on this observation, we propose a new DVFS technique inspired by TCP Vegas, a congestion control protocol from the IP-networking domain. Full system simulations on PARSEC benchmarks show that our technique reduces total CMP energy dissipation by over 40% with a small performance improvement.

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

With increasing core counts in Chip Multi-Processor (CMP) designs, the size of the on-chip communication fabric and shared Last-Level Caches (LLC), which we term uncore here, is also growing, consuming as much as 30% of die area and a significant portion of chip power budget. In this work, we focus on improving the uncore energy-efficiency using dynamic voltage and frequency scaling. Previous approaches are mostly restricted to reactive techniques, which may respond poorly to abrupt workload and uncore utility changes. We find, however, there are predictable patterns in uncore utility which point towards the potential of a proactive approach to uncore power management. In this work, we utilize artificial intelligence principles to proactively leverage uncore utility pattern prediction via an Artificial Neural Network (ANN). ANNs, however, require training to produce accurate predictions. Architecting an efficient training mechanism without a priori knowledge of the workload is a major challenge. We propose a novel technique in which a simple Proportional Integral (PI) controller is used as a secondary classifier during ANN training, dynamically pulling the ANN up by its bootstraps to achieve accurate predictions. Both the ANN and the PI controller, then, work in tandem once the ANN training phase is complete. The advantage of using a PI controller to initially train the ANN is a dramatic acceleration of the ANN's initial learning phase. Thus, in a real system, this scenario allows quick power-control adaptation to rapid application phase changes and context switches during execution. We show that the proposed technique produces results comparable to those of pure offline training without a need for prerecorded training sets. Full system simulations using the PARSEC benchmark suite show that the bootstrapped ANN improves the energy-delay product of the uncore system by 27% versus existing state-of-the-art methodologies.

Quality-of-Service (QoS) is a fundamental part of Networks-on-Chip (NoC) design. In application specific NoCs, guaranteed QoS is often obtained by static bandwidth reservation at design-time. The bandwidth allocation inevitably affects power-efficiency, which is crucial yet largely neglected in prior NoC QoS methods. In this work, we develop two algorithmic techniques that concurrently address power-efficiency and QoS. One is path-based integer linear programming (ILP) and the other is a negotiation-based heuristic. Both techniques support multiple user-cases. Simulation results show that our techniques significantly outperform an iterative greedy heuristic and are order of magnitude faster than conventional edge-based ILP.

Networks-on-Chip (NoCs) offer a scalable means of on-chip communication for future many-core chips. This work explores NoC router microarchitectures which leverage traffic pattern biases and imbalances to reduce latency and improve throughput. It introduces STORM, a new, low-latency, fair, highth-roughput NoC router design, customized for the traffic seen in a two-dimensional mesh network employing dimension-order routing. Compared to a baseline NoC router with equivalent buffer resources, STORM offers single cycle operation and reduced cycle time (17% less than the baseline on 45nm CMOS). This design yields a higher overall network saturation throughput (13% higher than the baseline) in an 8x8 2D mesh network for uniform random traffic. STORM also reduces packet latencies under realistic workloads by 36% on average.

As the core count in processor chips grows, so do the on-die, shared resources such as on-chip communication fabric and shared cache, which are of paramount importance for chip performance and power. This paper presents a method for dynamic voltage/frequency scaling of networks-on-chip and last level caches in multicore processor designs, where the shared resources form a single voltage/frequency domain. Several new techniques for monitoring and control are developed, and validated through full system simulations on the PARSEC benchmarks. These techniques reduce energy-delay product by 56% compared to a state-of-the-art prior work.

We propose a novel technique to significantly reduce the leakage energy of last level caches while mitigating any significant performance impact. In general, cache blocks are not ordered by their temporal locality within the sets; hence, simply power gating off a partition of the cache, as done in previous studies, may lead to considerable performance degradation. We propose a solution that migrates the high temporal locality blocks to facilitate power gating, where blocks likely to be used in the future are migrated from the partition being shutdown to the live partition at a negligible performance impact and hardware overhead. Our detailed simulations show energy savings of 66% at low performance degradation of 2.16%.

Networks-on-chip (NoC) has been recognized as a scalable approach to cope with the increasingly large demand for on-chip communication. This work focuses on how to achieve guaranteed service for application-specific NoCs through resource reservation. A graph model is adopted to describe physical and temporal sources of an NoC in a unified manner. Based on the graph model, two resource allocation heuristics are proposed and investigated. One heuristic leverages the idea of chip layout routing and the other utilizes Boolean satisfiability. Results from simulation from various testcases indicate that the proposed methods significantly outperform a state-of-the-art previous work.

This Special Section considers several studies that emphasize cross-domain physical optimization. The first paper applies physical optimization techniques that cut across the discrete and continuous domains; a geometric programming method is applied to solve the classical floorplanning problem. The second paper introduces a subfield scheduling approach that considers both ebeam lithography throughput and the thermal effect in the ebeam writing process. The third paper presents techniques that make the circuit layout compatible with multiple-patterning lithography. The fourth paper describes an integrated design methodology for microfluidic chips that encompasses operation scheduling, chip layout generation, control pin assignment, and wiring solution. The fifth paper crosses the boundaries of datapath design and random logic; it proposes a placement flow that simultaneously places a mixture of random logic and datapath cells found in hybrid designs. The short paper replaces flipflops with pulsed latches, and utilizes the time-borrowing property of pulsed latches and clock gating to achieve power efficiency.

In chip design today and for a foreseeable future, the last-level cache and on-chip interconnect is not only performance critical but also a substantial power consumer. This work focuses on employing dynamic voltage and frequency scaling (DVFS) policies for networks-on-chip (NoC) and shared, distributed last-level caches (LLC). In particular, we consider a practical system architecture where the distributed LLC and the NoC share a voltage/frequency domain that is separate from the core domain. This architecture enables the control of the relative speed between the cores and memory hierarchy without introducing synchronization delays within the NoC. DVFS for this architecture is more complex than individual link/core-based DVFS since it involves spatially distributed monitoring and control. We propose an average memory access time (AMAT)-based monitoring technique and integrate it with DVFS based on PID control theory. Simulations on PARSEC benchmarks yield a 27% energy savings with a negligible impact on system performance.

Process variations and circuit aging continue to be one of the main challenges to the power-efficiency of VLSI circuits, as a considerable power budget must be allocated to cushion timing variations. A design-time allocation implies uniform power consumption on all fabricated instances, even if many instances do not have strong variations. Adaptive design provides a power-efficient approach to variation tolerance, since it uses power only when the variations of a circuit instance are harmful. This paper is an effort toward supply voltage adaptation for variation resilience in VLSI interconnects. The main idea is a boostable repeater design that can transiently and autonomously raise its internal voltage rail to boost switching speed. The boosting can be turned on/off to compensate variations. The boostable repeater design achieves fine-grained voltage adaptation without stand-alone voltage regulators or an additional power grid. Since interconnect is a widely recognized cause of bottleneck in chip performance, and tremendous repeaters are employed on chip designs, boostable repeater has plenty of chances to improve system robustness. Experimental results indicate that our approach significantly outperforms existing techniques, including over-design, conventional adaptive supply voltage system, and online adjustable buffer.

VLSI circuits of the 45-nm technology and beyond are increasingly affected by process variations as well as aging effects. Overcoming the variations inevitably requires additional power expense, which in turn aggravates the power and heat problem. Adaptive supply voltage (ASV) is an arguably power-efficient approach for variation resilience since it attempts to allocate power resources only to where the negative effect of variations is strong. We propose a dual-level ASV (dual-ASV) system for designs containing many timing critical paths. This system can simultaneously provide ASV at both coarse-grained and fine-grained levels, and has limited power routing overhead. The dual-ASV system is compared with conventional ASV through SPICE simulations on benchmark circuits. The results indicate that the dual-ASV system consumes significantly less power and achieves similar performance in the presence of variations.

Track assignment is a critical step between global routing and detailed routing in modern VLSI chip designs. Crosstalk, which is largely decided by wire adjacency, has significant impact on interconnect delay and circuit performance. Therefore, the amount of crosstalk should be restrained in order to satisfy timing constraints. In this work, a novel track assignment algorithm is proposed to reduce crosstalk-induced performance degradation. The problem is formulated as a Traveling Salesman Problem (TSP) and solved by a graph-based heuristic. Experimental results on the ISPD2011 benchmark circuits show that the violations on crosstalk bounds can be reduced by up to 99.56% compared to the conventional non-constraint-based heuristics.

In chip design today and for a foreseeable future, on-chip communication is not only a performance bottleneck but also a substantial power consumer. This work focuses on employing dynamic voltage and frequency scaling (DVFS) policies for networks-on-chip (NoC) and shared, distributed last-level caches (LLC). In particular, we consider a practical system architecture where the distributed LLC and the NoC share a voltage/frequency domain which is separate from the core domain. This architecture enables controlling the relative speed between the cores and memory hierarchy without introducing synchronization delays within the NoC. DVFS for this architecture is more difficult than individual link/core-based DVFS since it involves spatially distributed monitoring and control. We propose an average memory access time (AMAT)-based monitoring technique and integrate it with DVFS based on PID control theory. Simulations on PARSEC benchmarks yield a 33% dynamic energy savings with a negligible impact on system performance.

The eight papers in this special section are extended versions of papers presented at the 2011 International Symposium on Physical Design (ISPD 2011), held in Santa Barbara, CA.

It is becoming increasingly important to design high-performance circuits with as low power as possible. In this paper, we study the gate sizing and device parameter selection problem for today's industrial designs. We first outline the typical practical problems that make it difficult to use traditional algorithms on high-performance industrial designs. Then, we propose a Lagrangian relaxation-based formulation that decouples timing analysis from optimization without a resulting loss in accuracy. We also propose a graph model that accurately captures discrete cell-type characteristics based on library data. We model the relaxed Lagrangian subproblem as a graph problem and propose algorithms to solve it. In our experiments, we demonstrate the importance of using the signoff timing engine to guide the optimization. We also show the benefit of the graph model we propose to solve the discrete optimization problem. Compared to a state-of-the art industrial optimization flow, we show that our algorithms can obtain up to 38% leakage power reductions and better overall timing for real high-performance microprocessor blocks.

It is becoming more and more important to design high performance designs with as low power as possible. In this paper, we study the gate sizing and device technology selection problem for today's industrial designs. We first outline the typical practical problems that make it difficult to use the traditional algorithms on high-performance industrial designs. Then, we propose a Lagrangian Relaxation (LR) based formulation that decouples timing analysis from optimization without resulting in loss of accuracy. We also propose a graph model that accurately captures discrete cell type characteristics based on library data. We model the relaxed Lagrangian subproblem as a discrete graph problem, and propose algorithms to solve it. In our experiments, we demonstrate the importance of using the signoff timing engine to guide the optimization. Compared to a state-of-the art industrial optimization flow, we show that our algorithms can obtain up to 38% leakage power reductions and better overall timing for real high-performance microprocessor blocks.

Multi-core technology becomes a new engine that drives performance growth for both microprocessors and embedded computing. This trend asks chip floorplanners to consider regularity constraint since identical processing/memory cores are preferred to form an array in layout. As chip core count keeps growing, manual floorplanning will be inefficient on the solution space exploration while conventional floorplanning algorithms do not address the regularity constraint. In this work, we investigate how to enforce regularity constraint in a simulated-annealing based floorplanner. We propose a simple and effective technique for encoding the regularity constraint in sequence-pairs. To the best of our knowledge, this is the first work on regularity-constrained floorplanning in the context of multi-core processor designs. Experimental comparison with a semi-automatic method shows that our approach yields an average of 22% less wirelength and mostly smaller area.

In a typical circuit optimization flow, one essential decision is to select the implementation for each gate according to a cell library. An implementation implies specific gate size, threshold voltage, etc. The selection normally needs to handle multiple and often conflicting objectives. An effective approach for multi-objective optimization is Lagrangian relaxation (LR), which has been adopted in continuous gate sizing. When LR is applied to the gate implementation selection, the Lagrangian dual problem is no longer convex like in continuous gate sizing, and conventional sub-gradient method becomes inefficient. In this paper, we propose a projection-based descent method and a new technique of Lagrangian multiplier distribution for solving the Lagrangian dual problem in discrete space. Experimental results demonstrate that our approach leads to significantly better solution quality and faster convergence compared to the sub-gradient method.

Technology mapping and placement have a significant impact on delays in standard cell-based very large scale integrated circuits. Traditionally, these steps are applied separately to optimize the delays, possibly since efficient algorithms that allow the simultaneous exploration of the mapping and placement solution spaces are unknown. In this paper, we present an exact polynomial time algorithm for delay-optimal placement of a tree and extend the same to simultaneous technology mapping and placement for the optimal delay in the tree. We extend the algorithm by employing Lagrangian relaxation technique, which assesses the timing criticality of paths beyond a tree, to optimize the delays in directed acyclic graphs. Experimental results on benchmark circuits in a 70 nm technology show that our algorithms improve timing significantly with remarkably less runtimes compared to a competitive approach of iterative conventional timing-driven mapping and multilevel placement.

The progress of GPU (Graphics Processing Unit) technology opens a new avenue for boosting computing power. This work is an attempt to exploit the GPU for accelerating VLSI circuit optimization. We propose GPU-based parallel computing techniques and apply them on simultaneous gate sizing and threshold voltage assignment, which is a popular method for VLSI performance and power optimization. These techniques include efficient task scheduling and memory organization, all of which are aimed to fully utilize the advantages of GPUs. Compared to conventional sequential computation, our techniques can provide up to 56× (39× on average) speedup without any sacrifice on solution quality.

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.

This work proposes a new problem of identifying large and tangled logic structures in a synthesized netlist. Large groups of cells that are highly interconnected to each other can often create potential routing hotspots that require special placement constraints. They can also indicate problematic clumps of logic that either require resynthesis to reduce wiring demand or specialized datapath placement. At a glance, this formulation appears similar to conventional circuit clustering, but there are two important distinctions. First, we are interested in finding large groups of cells that represent entire logic structures like adders and decoders, as opposed to clusters with only a handful of cells. Second, we seek to pull out only the structures of interest, instead of assigning every cell to a cluster to reduce problem complexity. This work proposes new metrics for detecting structures based on Rent's rule that, unlike traditional cluster metrics, are able to fairly differentiate between large and small groups of cells. Next, we demonstrate how these metrics can be applied to identify structures in a netlist. Finally, our experiments demonstrate the ability to predict and alleviate routing hotspots on a real industry design using our metrics and method.

Manufacturing hotspots are the layout patterns which cause excessive difficulties to manufacturing process. Design rules are effective at handling sizing/spacing induced hotspots, but are inadequate at dealing with topological hotspots. In wire routings, existing approaches often remove the hotspots through iteratively ripping up and rerouting one net at a time guided by litho-simulations. This procedure can be very time-consuming because litho-simulation is typically very slow and the rerouting may result in new hotspots due to its heuristic nature. In this paper, we propose a new approach for improving the efficiency of hotspot removal. In our approach, multiple nets in each hotspot region are simultaneously ripped up and rerouted based on Boolean satisfiability (SAT). The hotspot patterns, which are described and stored in a pre-built library, are forbidden to appear in the reroute through SAT constraints. Since multiple nets are simultaneously processed and SAT can guarantee to find a feasible solution if it exists, our approach can greatly accelerate the convergence on manufacturability. Experimental results on benchmark circuits show that our approach can remove over 90% of the hotspots in less than one minute on circuits with more than 20K nets and hundreds of hotspots.

Networks-on-chip (NoC) is emerging as a promising communication structure, which is scalable with respect to chip complexity. Meanwhile, latest chip designs are increasingly leveraging multiple voltage-frequency domains for energy-efficiency improvement. In this work, we propose a simultaneous task and voltage scheduling algorithm for energy minimization in NoC based designs. The energy-latency tradeoff is handled by Lagrangian relaxation. The core algorithm is a clustering based approach which not only assigns voltage levels and starting time to each task (or Processing Element) but also naturally finds voltage-frequency clusters. Compared to a recent previous work, which performs task scheduling and voltage assignment sequentially, our method leads to an average of 20% energy reduction.

Clock mesh is widely used in microprocessor designs for achieving low clock skew and high variation tolerance. Clock mesh optimization is a very difficult problem because it has highly-connected structure and requires accurate delay models which are computationally expensive. Existing methods on clock network optimization are either restricted to clock trees, which are easy to be separated into smaller problems, or naive heuristics based on crude delay models. In this paper, we propose a clock mesh sizing algorithm which is aimed to minimize mesh wire area with consideration of clock skew constraints. This algorithm is a systematic solution search through rigorous Sequential Quadratic Programming (SQP). The SQP is guided by an efficient adjoint sensitivity analysis which has near-SPICE-level accuracy and faster-than-SPICE speed. Experimental results on various benchmark circuits indicate that our algorithm leads to significant wire area reduction while maintaining low clock skew.

Gate sizing and threshold voltage (Vt) assignment are popular techniques for circuit timing and power optimization. Existing methods, by and large, are either sensitivity-driven heuristics or based on discretizing continuous optimization solutions. Sensitivity-driven heuristics are easily trapped in local optima and the discretization may be subject to remarkable errors. In this paper, we propose a systematic combinatorial approach for simultaneous gate sizing and Vtassignment. The core idea of this approach is joint relaxation and restriction, which employs consistency relaxation and coupled bi-directional solution search. The process of joint relaxation and restriction is conducted iteratively to systematically improve solutions. Our algorithm is compared with a state-of-the-art previous work on benchmark circuits. The results from our algorithm can lead to about 22% less power dissipation subject to the same timing constraints.

Clock meshes possess inherent low clock skews and excellent immunity to process-voltage-temperature variations, and have increasingly found their way to high-performance integrated circuit designs. However, analysis of such massively coupled networks is significantly hindered by the sheer size of the network and tight coupling between non-tree interconnects and large numbers of clock drivers. While the SPICE simulation of large clock meshes is often intractable, standard interconnect model order reduction algorithms also fail due to the large number of input/output ports introduced by clock drivers. The presented approach is motivated by the key observation of the steady-state operation of the clock networks while its efficiency is facilitated by exploringnewclock-mesh specific harmonic-weighted model order reduction algorithm and locality analysis via port sliding. The scalability of the analysis is significantly improved by eliminating the need for computing infeasible multi-port passive reduced order interconnect models with large port count and decomposing the overall task into very tractable and naturally parallelizable model generation and fast Fourier transform/inverse-fast Fourier transform operations, all on a per driver or per sink basis. We demonstrate the application of our approach by feasibly analyzing large clock meshes with excellent accuracy.

The gap between VLSI technology and fabrication technology leads to strong refractive effects in lithography. Consequently, it is a huge challenge to reliably print layout features on wafers. The quality and robustness of lithography directly depend on layout patterns. It becomes imperative to consider the manufacturability issue during layout design such that the burden of lithography process can be alleviated. In this paper, three algorithms, namely, cell flipping algorithm, single row optimization approach and multiple row optimization approach, are proposed to tune any existing cell placement to be lithography friendly. These algorithms are based on dynamic programming and graph theoretic approaches, and can provide different tradeoff between critical dimension (CD) variation reduction and wirelength increase. Using lithography simulations, our experimental results demonstrate that over 15% CD variation reduction can be obtained in post-OPC stage by the new approaches while only less than 1% additional wire is introduced.

Clock network is a vulnerable victim of variations as well as a main power consumer in many integrated circuits. Recently, link-based non-tree clock network attracts people's attention due to its appealing tradeoff between variation tolerance and power overhead. In this work, we investigate how to optimize such clock networks through buffer and wire sizing. A two-stage hybrid optimization approach is proposed. It considers the realistic constraint of discrete buffer/wire sizes and is based on accurate delay models. In order to provide reliable and efficient guidance for the optimization, we suggest to apply support vector machine (SVM)-based machine learning as a surrogate for expensive circuit-level simulation. Experimental results on benchmark circuits show that our sizing method can reduce clock skew by 45% on average with very small increase on power dissipation.

Clock gating is one of the most effective techniques to reduce clock tree power. Although it has already been studied considerably, most of the previous works are restricted to either register transfer level (RTL) or clock tree synthesis stage. Clock gating design at RTL is coarse and it pays no attention to the physical information, therefore, it often results in large wirelength overhead. While if clock gating is considered only at clock tree synthesis, the optimization space is largely limited due to the fixing of registers. To fully use the logical and physical information between registers, we propose a new flow for low-power gated clock tree design in this work. It mainly includes three parts: gated clock tree aware register placement, gated clock tree construction, and incremental placement. Compared with the previous works on clock gating, our algorithm reduces the clock tree power with much fewer gating logics, therefore, the overhead to the placement is also reduced.

Clock mesh has been widely used to distribute the clock signal across the chip. Clock mesh is driven by a top-level tree and a set of mesh buffers. We present fast and efficient combinatorial algorithms to simultaneously identify the candidate locations as well as sizes of the buffers driving the clock mesh. We show that such a sizing offers a better solution than inserting buffers of uniform size across the mesh. Due to the high redundancy, a mesh architecture offers high tolerance toward variations in clock skew. However, such a redundancy comes at the expense of mesh wire length and power dissipation. Based on survivable network theory, we formulate the problem to reduce the clock mesh by retaining only those edges that are critical to maintain redundancy. Such a formulation offers designer the option to tradeoff between power and tolerance to process variations. We present efficient postprocessing techniques to reduce the size of the mesh buffers after mesh reduction. Experimental results indicate that our techniques can result inpower savings up to 28% with less than 3.3% delay penalty. We also present driver models that can help in simulating the clock mesh. Such models achieve near-HSPICE accuracy with significant speedup in run time.

The progress of GPU (Graphics Processing Unit) technology opens a new avenue for boosting computing power. This work is an attempt to exploit GPU for accelerating VLSI circuit optimization. We propose GPU-based parallel computing techniques and apply them on simultaneous gate sizing and threshold voltage assignment, which is often employed in practice for performance and power optimization. These techniques are aimed to fully utilize the benefits of GPU through efficient task scheduling and memory organization. Compared to conventional sequential computation, our techniques can provide up to 56x speedup without any sacrifice on solution quality.

Current lithography techniques use a light wavelength of 193nm to print sub-65nm features. This introduces process variations which cause mismatches between desired and actual wafer feature sizes. However, the circuit layout can be modified in a manner which can make it more lithography-friendly. These modifications are implemented as a series of perturbation iterations on the initial layout generated by the CAD tool. The iterations are performed based on estimates of the highest feature variations which are calculated offline for standard cell pairs and stored in a Look-up table (LUT). The iterations are directed by a Simulated Annealing algorithm. In the process we observe the impact of the iterations performed on the initial solution in terms of wirelength, vias and routing congestion. The procedure is validated on ISCAS85 benchmark circuits and a reduction of greater than 20% in the number of instances with the highest cell boundary feature variations is observed. The wirelength and the number of vias showed an increase of roughly 2.2-8.8% and 1.2-7.8% respectively for different circuits.

Gate sizing and threshold voltage (Vt) assignment are popular tech-niques for circuit timing and power optimization. Existing meth-ods, by and large, are either sensitivity-driven heuristics or based on rounding continuous optimization solutions. Sensitivity-driven heuristics are easily trapped in local optimum and the rounding is subject to remarkable errors. In this paper, we propose a system-atic combinatorial approach for simultaneous gate sizing and Vt assignment. The core ideas of this approach include consistency relaxation and coupled bi-directional search. Our algorithm is com-pared with a state-of-the-art previous work on benchmark circuits. The results from our algorithm can lead to about 24 % less power dissipation subject to the same timing constraints.

With increasing time-to-market pressure and shortening semiconductor product cycles, more and more chips are being designed with library-based methodologies. In spite of this shift, the problem of discrete gate sizing has received significantly less attention than its continuous counterpart. On the other hand, cell sizes of many realistic libraries are sparse, for example, geometrically spaced, which makes the nearest rounding approach inapplicable as large timing violations may be introduced. Therefore, it is highly desirable to design an effective algorithm to handle this discrete gate-sizing problem. Such an algorithm is proposed in this paper. The algorithm is a continuous-solution-guided dynamic-programming-like approach. A set of novel techniques, such as locality-sensitive-hashing-based solution pruning, is also proposed to accelerate the algorithm. Our experimental results demonstrate that 1) the nearest rounding approach often leads to large timing violations and 2) compared to the well-known Coudert's approach, the new algorithm saves up to 21% in area cost while still satisfying the timing constraint.

In hardware implementations of many signal processing functions, timing errors on different circuit signals may have largely different importance with respect to the overall signal processing performance. This motivates us to apply the concept ofunequalerrortoleranceto enable the use of voltage overscaling at minimal signal processing performance degradation. Realization of unequal error tolerance involves two main issues, including how to quantify the importance of each circuit signal and how to incorporate the importance quantification into signal processing circuit design. We developed techniques to tackle these two issues and applied them to two types of trellis decoders including Viterbi decoder for convolutional code decoding and max-log-maximum a posteriori (MAP) decoder for turbo code decoding. Simulation results demonstrated promising energy saving potentials of the proposed design solution on both trellis decoding computation and memory storage at small decoding performance degradation.

Power/ground noise is a major source of VLSI circuit timing variations. This work aims to reduce clock network induced power noise by assigning different signal polarities (opposite switchings) to clock buffers in an existing buffered clock tree. Three assignment algorithms are proposed: 1) partitioning; 2) 2-coloring on minimum spanning tree; and 3) recursive min-matching. A post-processing of clock buffer sizing is performed to achieve desired clock skew. SPICE based experimental results indicate that our techniques could reduce the average peak current and average delay variations by 50% and 51%, respectively.

In nanometer regime, IC designs have to consider the impact of process variations, which is often indicated by manufacturing/parametric yield. This paper investigates a yield model — the probability that the values of multiple manufacturing/circuit parameters meet certain target. This model can be applied to predict CMP (Chemical-Mechanical Planarization) yield. We focus on the difficult cases which have large number of partially correlated variations. In order to predict the yield for these difficult cases efficiently, we propose two techniques: (1) application of Orthogonal Principle Component Analysis (OPCA); (2) hierarchical adaptive quadrisection (HAQ). Systematic variations are also included in our model. Compared to previous work, the OPCA based method can reduce the error on yield estimation from 17.1%–21.1% to 1.3%–2.8% with 4.6× speedup. The HAQ technique can reduce the error to 4.1% – 5.6% with 6 × –9.4× speedup.

Traditionally, clock network layout is performed after cell placement. Such methodology is facing a serious problem in nanometer IC designs where people tend to use huge clock buffers for robustness against variations. That is, clock buffers are often placed far from ideal locations to avoid overlap with logic cells. As a result, both power dissipation and timing are degraded. In order to solve this problem, we propose a low power clock buffer planning methodology which is integrated with cell placement. A Bin- Divided Grouping algorithm is developed to construct virtual buffer tree, which can explicitly model the clock buffers in placement. The virtual buffer tree is dynamically updated during the placement to reflect the changes of latch locations. To reduce power dissipation, latch clumping is incorporated with the clock buffer planning. The experimental results show that our method can reduce clock power significantly by 21% on average.

Clock gating is a popular technique for reducing power dissipation in clock network. Although there have been numerous research efforts on clock gating, the previous approaches still have a significant weakness. That is, they usually construct a gated clock tree after cell placement, i.e., cell placement is performed without considering clock gating and may generate a solution unfriendly to subsequent gated clock tree construction. As a result, the control gates inserted in the tree construction is very likely to cause cell overlap. Even though the overlap can be eventually removed in placement legalization, remarkable wirelength/power overhead is incurred. In this paper, we propose a gate planning technique which is integrated with a partition-based cell placer. During cell placement, the planning judiciously inserts clock gates based on power estimation. In addition, pseudo edges are inserted between clock gates and registers in order to reduce clock wirelength and enable long shut-off periods. At the end, when a relatively detailed placement is obtained, a post-processing is performed to degrade the inefficient clock gates to clock buffers. We compared our approach with recent previous works on ISCAS89 benchmark circuits. Our method reduces the clock tree wirelength and power by 22.06% and 40.80%, respectively, with a very limited increase on signal nets wirelength and power compared with the conventional (register-oblivious) placement. The results also indicate that our algorithm outperforms the clock-gating-oblivious placement [9] on power reduction and performance improvement.

Recently, microprocessor industry is headed in the direction of multi-core designs in order to continue the chip performance growth. We investigate buffer insertion, which is a critical timing optimization technique, in the context of an industrial multi-core processor design methodology. Different from the conventional formulation, buffer insertion in this case requires a single solution to accommodate different scenarios. If the conventional buffer insertion is performed for each scenario separately, there may be different solutions corresponding to these scenarios. A naive approach is to select one scenario's solution that is most critical among all scenarios and apply it to all the scenarios. However, a good solution for one scenario maybe a poor one for another scenario. We propose algorithmic techniques for solving these multi-scenario buffer insertion problems. Compared to the naive approach, our algorithm can improve slack by 102ps on average for maxslack solutions. For min-cost solutions, our algorithm causes no timing violation while the naive approach results in 35% timing violations. Moreover, the computation speed of our algorithm is faster

Clock network is a vulnerable victim of variations as well as a main power consumer in many integrated circuits. Recently, link-based non-tree clock network attracts people’s attention due to its appealing tradeoff between variation tolerance and power overhead. In this work, we investigate how to optimize such clock networks through buffer and wire sizing. A two-stage hybrid optimization approach is proposed. It considers the realistic constraint of discrete buffer/wire sizes and is based on accurate delay models. In order to provide reliable and efficient guidance for the optimization, we suggest to apply SVM (Support Vector Machine) based machine learning as a surrogate for expensive circuit-level simulation. Experimental results on benchmark circuits show that our sizing method can reduce clock skew by 43 % on average with very small increase on power dissipation.

Clock gating is one of the most effective techniques to reduce clock network power dissipation. Although it has already been studied considerably, most of the previous works are restricted to either logic level or clock routing stage. Due to the restriction, clock gating often meets the trouble of wirelength overhead and frequent control signal switching, both of which degrade its effectiveness. Furthermore, previous design flows which insert gate logics after placement introduce a lot of overlaps, especially when there are lots of gate logics inserted. In this work, we propose a new design flow for low power gated clock network construction, in order to minimize the clock wirelength and the activity of control signals, and to eliminate the overlaps incurred by the gate logics. Our method begins with a coarse placement followed by soft register clustering. Then, we perform clock tree topology construction and zero skew clock routing to further reduce the power and the clock skew. Last, the gated clock network is fed back to the placer for incremental placement. Experimental results on ISCAS89 benchmarks demonstrate that our method outperforms previous algorithm of activity aware register placement in clock wirelength and clock power reduction with signal nets wirelength and signal nets power increase within 5% and 3%, respectively

Recently, the microprocessor industry is headed in the direction of multicore designs in order to continue the chip performance growth. We investigate buffer insertion, which is a critical timing optimization technique, in the context of an industrial multicore processor design methodology. Different from the conventional formulation, buffer insertion in this case requires a single solution to accommodate different scenarios, since each core has its own parameters. If conventional buffer insertion is performed for each scenario separately, there may be a different solution corresponding to each of these scenarios. A straightforward approach is to judiciously select a solution from one scenario and apply it to all the scenarios. However, a good solution for one scenario may be a poor one for another. We propose several algorithmic techniques for solving these multiscenario buffer insertion problems. Compared with a straightforward extension of the conventional buffer insertion, our algorithm can improve slack by 20-280 ps for max-slack solutions. For min-cost solutions, our algorithm causes no timing violation, while the extended conventional buffering results in 35% timing violations. Moreover, the computation speed of our algorithm is faster.

Advances in very large-scale integration technology make clock skew more susceptible to process variations. Notwithstanding efficient exact zero-skew algorithms, clock skew still limits post-manufacturing performance. Process-induced skew presents an ever-growing limitation for high-speed large-area clock networks. To achieve multigigahertz operation for high-end designs, clock networks must be constructed to tolerate variations in various interconnect parameters. This paper proposes a statistical centering-based clock routing algorithm that is built upon deferred merging embedding that greatly improves skew tolerance to interconnect variations. The algorithm achieves the improvement by the following ways: (1) choosing the best center measure which is dynamically based on the first three moments of the skew distribution and (2) designing for all sink pairs in the subtrees simultaneously. In addition, a variation-aware abstract topology generation algorithm is proposed in this paper. Experiments on benchmark circuits demonstrate that the proposed method reduces the number of skew violations by 12%-37%.

This paper presents a class of power grid analysis and optimization techniques, all of which are based on the algebraic-multigrid (AMG) method. First, a new AMG-based reduction scheme is proposed to improve the efficiency of reducing the problem size for power grid analysis and optimization. Next, with the proposed reduction technique, a fast transient-analysis method is developed and extended to an accurate solver with error control mechanism. After that, the scope of this method is further broadened for handling the analysis of the modified grid. Finally, a fast decap-allocation (DA) scheme based on AMG is suggested. Experimental results show that these techniques not only achieve a significant speedup over reported industrial methods but also enhance the quality of solutions. By using the proposed techniques, transient analysis with 200 time steps on a 1.6-M-node power grid can be completed in less than 5 min; dc analysis on the same circuit can reach an accuracy of in about 141 s. Our DA can process a circuit with up to one million nodes in about 11 min.

Nanometer VLSI systems demand robust clock distribution network design for increased process and operating condition variabilities. In this paper, we propose minimum clock distribution network augmentation for guaranteed skew yield. We present theoretical analysis results on an inserted link in a clock network, which scales down local skew and skew variation, but may not guarantee global skew and skew variation reduction in general. We propose a global minimum clock network augmentation algorithm, which inserts links simultaneously between all nearest sink pairs, apply rule-based link removal, and perform link consolidation by Steiner minimum tree construction for wirelength reduction with guaranteed clock skew yield. Our experimental results show that our proposed algorithm achieves dominant clock network augmentation solutions, e.g., an average of 16% clock skew yield improvement, 9% maximum skew reduction, and 25% reduction of clock skew variation standard deviation with identical wirelength compared with previous best clock network link insertion methods [11].

Abstract—With increasing time-to-market pressure and short-ening semiconductor product cycles, more and more chips are being designed with library-based methodologies. In spite of this shift, the problem of discrete gate sizing has received significantly less attention than its continuous counterpart. On the other hand, cell sizes of many realistic libraries are sparse, for example, geo-metrically spaced, which makes the nearest rounding approach inapplicable as large timing violations may be introduced. There-fore, it is highly desirable to design an effective algorithm to handle this discrete gate-sizing problem. Such an algorithm is pro-posed in this paper. The algorithm is a continuous-solution-guided dynamic-programming-like approach. A set of novel techniques, such as locality-sensitive-hashing-based solution pruning, is also proposed to accelerate the algorithm. Our experimental results demonstrate that 1) the nearest rounding approach often leads to large timing violations and 2) compared to the well-known Coudert’s approach, the new algorithm saves up to 21 % in area cost while still satisfying the timing constraint. Index Terms—Discretization, dynamic programming (DP), gate sizing, pruning, sparse cell library. I.

VLSI design is increasingly sensitive to variations which often degrade the parametric yield. Post-silicon tuning techniques can compensate for specific variations on the die and thus significantly improve the yield. Previous works on adaptivity optimization for post-silicon tuning focus on either logic signal tuning or clock signal tuning. This paper proposes the first unified adaptivity optimization on logical and clock signal tuning, which enables us to significantly save resource. In addition, it does not need any assumption on variation distributions. Our unified optimization is based on a novel linear programming formulation which can be efficiently solved by an advanced robust linear programming technique. Due to the discrete nature of the problem, the continuous solution obtained from linear programming is then efficiently discretized. This procedure involves binary search accelerated dynamic programming, batch based optimization, and Latin Hypercube sampling based fast simulation. Our experimental results demonstrate that up to 50% area cost reduction can be obtained by the unified optimization compared to optimization on logic or clock alone. In addition, the proposed discretization approach significantly outperforms the alternatives in terms of solution quality and runtime.

Clock meshes posses inherent low clock skews and excellent immunity to PVT variations, and have increasingly found their way to high-performance IC designs. However, analysis of such massively coupled networks is significantly hindered by the sheer size of the network and tight coupling between non-tree interconnects and large numbers of clock drivers. The presented Harmonic-weighted model order reduction algorithm is motivated by the key observation of the steady-state operation of the clock networks, and its efficiency is facilitated by the locality analysis via port sliding. The scalability of the analysis is significantly improved by eliminating the need of computing infeasible multi-port passive reduced order interconnect models with large port count. And the overall task is decomposed into tractable and naturally parallelizable model generation and FFT/Inverse-FFT operations, all on a per driver or per sink basis.

Rotary traveling-wave oscillator (RTWO) is a recently pro- posed transmission-line approach for multi-gigahertz rate clock generation. RTWO has the characteristics of both conventional LC tank oscillator and ring oscillator. Thus, it is difficult to be analyzed by a general-purpose method. This paper presents a systematic and efficient method for RTWO modeling and optimization. Equations for frequency, power dissipation, die area, loop gain and phase noise are formulated in posynomial forms. The resulting optimization problem is relaxed to be a Geometric Programming (GP) and can be efficiently solved with a convex optimization solver. A novel scheme to control the rotation direction is also suggested for skew control. Experimental results show that our method can rapidly compute the globally optimal trade-off and reduce the power by up to 85% for a 11.8 GHz RTWO design. Compared to a recently reported low-power methodology, the proposed design scheme can save about 50% of die area and achieve lower power dissipation as well as faster rise/fall time.

When VLSI technology scales toward 45nm, the lithography wavelength stays at 193nm. This large gap results in strong refractive effects in lithography. Consequently, it is a huge challenge to reliably print layout features on wafers and the printing is more susceptible to lithographic process variations. Although resolution enhancement techniques can mitigate this manufacturability problem, their capabilities are overstretched by the continuous shrinking of VLSI feature size. On the other hand,the quality and robustness of lithography directly depend on layout patterns. Therefore, it becomes imperative to consider the manufacturability issue during layout design such that the burden of lithography process can be alleviated.

As a prevalent constraint, sharp slew rate is often required in circuit design, which causes a huge demand for buffering resources. This problem requires ultrafast buffering techniques to handle large volume of nets while also minimizing buffering cost. This problem is intensively studied in this paper. First, a highly efficient algorithm based on dynamic programming is proposed to optimally solve slew buffering with discrete buffer locations. Second, a new algorithm using the maximum matching technique is developed to handle the difficult cases in which no assumption is made on buffer input slew. Third, an adaptive buffer selection approach is proposed to efficiently handle slew buffering with continuous buffer locations. Fourth, buffer blockage avoidance is handled, which makes the algorithms ready for practical use. Experiments on industrial netlists demonstrate that our algorithms are very effective and highly efficient: we achieve about 90x speedup and save up to 20% buffer area over the commonly used van Ginneken style buffering. The new algorithms also significantly outperform previous works that indirectly address the slew buffering problem.

We study in this paper the problem of jumper insertion on general routing (Steiner/spanning) trees with obstacles for antenna avoidance/fixing at the routing and/or postlayout stages. We formulate the jumper insertion for antenna avoidance/fixing as a tree-cutting problem and present the first optimal algorithm for the general tree-cutting problem. We show that the tree-cutting problem exhibits the properties of optimal substructures and greedy choices. With these properties, we present an O((V+D)lgD)-time optimal jumper-insertion algorithm that uses the least number of jumpers to avoid/fix the antenna violations on a Steiner/spanning tree with V vertices and D obstacles. Experimental results show the superior effectiveness and efficiency of our algorithm

Along with the progress of very-large-scale-integration technology, buffer insertion plays an increasingly critical role on affecting circuit design and performance. Traditional buffer insertion algorithms are mostly net based and therefore often result in suboptimal delay or unnecessary buffer expense due to the lack of global view. In this paper, we propose a novel path-based-buffer-insertion (PBBI) scheme which can overcome the weakness of the net-based approaches. We also discuss some potential difficulties of the PBBI approach and propose solutions to them. A fast estimation on buffered delay is employed to improve the solution quality. Gate sizing is also considered at the same time. Experimental results show that our method can efficiently reduce buffer/gate cost significantly (by 71% on average) when compared to traditional net-based approaches. To the best of our knowledge, this is the first work on path based buffer insertion and simultaneous gate sizing.

As the VLSI feature size has already decreased below lithographic wavelength, the printability problem, due to strong diffraction effects, poses a serious threat to the progress of VLSI technology. A circuit layout with poor printability implies that it is difficult to make the printed features on wafers follow designed shapes without distortions. The development of resolution enhancement techniques (RET) can alleviate the printability problem but cannot reverse the trend of deterioration. Moreover, over-usage of RET may dramatically increase photo-mask cost and increase the cycle time for volume production. Thus, there is a strong demand to consider the subwavelength printability problem in circuit layout designs. However, layout printability optimization should not degrade circuit timing performance. In this paper, we introduce a wire sizing and spacing method to improve wire printability with minimal adverse impact on interconnect timing performance. A new printability model is proposed to handle partially coherent illuminations. The complex printability and timing optimization problem is solved in a two-phase approach. The difficulty of the printability optimization due to its multimodal nature is handled with a sensitivity-based heuristic. A coupling aware timing driven continuous wire sizing algorithm is also provided. Lithographic simulation results show that our approach can improve the printability in term of edge placement error (EPE) by 20%-40% without violating timing, wire width, and spacing constraints.

Conventionally, the topology of signal net routing is almost always restricted to Steiner trees, either unbuffered or buffered. However, introducing redundant paths into the topology (which leads to non-tree) may significantly improve timing performance as well as tolerance to open faults and variations. These advantages are particularly appealing for timing critical net routings in nanoscale VLSI designs where interconnect delay is a performance bottleneck and variation effects are increasingly remarkable. We propose Steiner network construction heuristics which can generate either tree or non-tree with different slack-wirelength tradeoff, and handle both long path and short path constraints. We also propose heuristics for simultaneous Steiner network construction and buffering, which may provide further improvement in slack and resistance to variations. Furthermore, incremental non-tree delay update techniques are developed to facilitate fast Steiner network evaluations. Extensive experiments in different scenarios show that our heuristics usually improve timing slack by hundreds of pico seconds compared to traditional approaches. When process variations are considered, our heuristics can significantly improve timing yield because of nominal slack improvement and delay variability reduction.

The clock distribution network is a key component of any synchronous VLSI design. High power dissipation and pressure volume temperature-induced variations in clock skew have started playing an increasingly important role in limiting the performance of the clock network. Rotary clocking is a novel technique which employs unterminated rings formed by differential transmission lines to save power and reduce skew variability. Despite its appealing advantages, rotary clocking requires flip-flop locations to match predesigned clock skew on rotary clock rings. This requirement poses a difficult chicken-and-egg problem which prevents its wide application. In this paper, we propose an integrated placement and skew scheduling methodology to break this hurdle, making rotary clocking compatible with practical design flows. A network flow based flip-flop assignment algorithm and a cost-driven skew optimization algorithm are developed. We also present an integer linear programming formulation that minimizes maximum capacitance loaded at any of the rotary rings, thereby maximizing the operating frequency. Experimental results on benchmark circuits show that our method can reduce the tapping cost (measured as the total length of the wire segments connecting the rotary rings to the clock sinks) for rotary clocking by 33%-53%

As VLSI technology scales toward 65nm and beyond, both timing and power performance of integrated circuits are increasingly affected by process variations. In practice, people often treat systematic components of the variations, which are generally traceable according to process models, in the same way as random variations in process corner based methodologies. Consequently, the process corner models are unnecessarily pessimistic. In this paper, we propose a new cell characterization methodology which captures lithography induced gate length variations. A new technique of dummy poly insertion is suggested to shield inter-cell optical interferences. This technique together with standard cells characterized using our methodology will let current design flows comprehend the variations almost without any changes. Experimental results on industrial designs indicate that our methodology can averagely reduce timing variation window by 8%-25%, power variation window by 55 % when compared to a worst case approach. For an industrial low power design, over 300ps reduction on the path delay variation is obtained by using cells characterized according to our methodology.

As a prevalent constraint, sharp slew rate is often required in circuit design which causes a huge demand for buffering resources. This problem requires ultra-fast buffering techniques to handle large volume of nets, while also minimizing buffering cost. This problem is intensively studied in this paper. First, a highly efficient algorithm based on dynamic programming is proposed to optimally solve slew buffering with discrete buffer locations. Second, a new algorithm is developed to handle the difficult cases in which no assumption is made on buffer input slew. Third, an adaptive buffer selection approach is proposed to efficiently handle slew buffering with continuous buffer locations. Experiments on industrial netlists demonstrate that our algorithms are very effective and highly efficient: we achieve > 100X speed up and save up to 40% buffer area over the commonly-used van Ginneken style buffering.

Conventionally, signal net routing is almost always implemented asSteiner trees. However, non-tree topology is often superior on timing performance as well as tolerance to open faults and variations. These advantages are particularly appealing for timing critical net routings in nano-scale VLSI designs where interconnect delay is a performance bottleneck and variation effects are increasingly remarkable. We propose Steiner network construction heuristics which can generate either tree or non-tree with different slack-wirelength tradeoff, and handle both long path and short path constraints. Incremental non-tree delay update techniques are developed to facilitate fast Steiner network evaluations. Extensive experiments in different scenarios show that our heuristics usually improve timing slack by hundreds of pico seconds compared to traditional tree approaches.

In clock network synthesis, sometimes skew constraints are required only within certain groups of clock sinks and do not exist between different groups. This is the so-called associative skew clock routing problem. Although the number of constraints is reduced, the problem becomes more difficult to solve due to the enlarged solution space. The perhaps only previous work used a very primitive delay model and cannot handle difficult instances in which sink groups are intermingled. We reuse existing techniques to solve this problem, including the difficult instances, based on a more accurate and popular delay model. Experimental results show that our algorithm can reduce the total clock routing wirelength by 12% on average compared to greedy-DME which is one of the best zero skew routing algorithms

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

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

Power/ground noise is a major source of VLSI circuit timing variations. This work aims to reduce clock network induced power noise by assigning different signal polarities (opposite switchings) to clock buffers in an existing buffered clock tree. Three assignment algorithms are proposed: (1) partitioning, (2) 2-coloring on minimum spanning tree and (3) recursive min-matching. A post-processing of clock buffer sizing is performed to achieve desired clock skew. SPICE based experimental results indicate that our techniques could reduce the average peak current and average delay variations by 44% and 54% respectively.

We present a fast and efficient combinatorial algorithm to simultaneously identify the candidate locations as well as the sizes of the buffers driving a clock mesh. Due to the high redundancy, a mesh architecture offers high tolerance towards variation in the clock skew. However, such a redundancy comes at the expense of mesh wire length and power dissipation. Based on survivable network theory, we formulate the problem to reduce the clock mesh by retaining only those edges that are critical to maintain redundancy. Such a formulation offers designer the option to trade-off between power and tolerance to process variations. Experimental results indicate that our techniques can result in power savings up to 28% with less than 4% delay penalty.

Decap (decoupling capacitor) is an effective technique for suppressing power supply noise. Nevertheless, over-usage of decap usually causes excessive power dissipation. Therefore, the total decap area needs to be minimized subject to power supply noise constraints. This is a complicated nonlinear optimization problem that may have as many as millions of variables. We propose an algebraic multigrid (AMG) based method to handle the high complexity. An error compensation scheme is developed to compensate the accuracy loss during the AMG reduction. A charge based back-mapping method and a few other techniques are suggested to further improve the computation efficiency. Our method is flexible to use and can be easily integrated with other existing decap allocation works. When compared to several previous works, the results from our method are usually the closest to the optimum. Our method also runs fast and can solve circuits with up to 1 million nodes in about 11 minutes. In addition, it has better scalability than the previous works.

As a promising approach to mitigate the challenge of interconnect limit, X-architecture allows routings along diagonal directions in addition to rectilinear directions. It can reduce routing wire length and vias number compared with conventional Manhattan routing. Although Steiner minimum tree and signal routing algorithms have been developed for X-architecture, clock routing has not been addressed to the best of our knowledge. However, wire length reduction is even more compelling for clock net, as wire is a major power consumer and power supply noise generator. In addition, X-architecture is very effective for interconnect delay and clock skew optimization. In this paper, we investigate the layout embedding technique for clock routing in X-architecture and integrate it with the deferred-merge embedding (DME) algorithm. To alleviate the inaccuracy of the Elmore delay (ED) model, a more accurate fitted Elmore delay (FED) model is employed. Experimental results on benchmarks exhibit encouraging results.

Advances in VLSI technology make clock skew more susceptible to process variations. Notwithstanding efficient zero skew routing algorithms, clock skew still limits post-manufacturing performance. Process-induced skew presents an ever-growing limitation for high speed, large area clock networks. To achieve multi-GHz operation for high-end designs, clock networks must be constructed to tolerate variations in various interconnect parameters. We propose statistical centering based clock routing algorithm built upon DME that greatly improves skew tolerance to interconnect variations. The algorithm achieves the improvement by: i) choosing the best center measure which is dynamically based on the first three moments of the skew distribution, and ii) designing for all sink pairs in the subtrees simultaneously. In addition, a variation aware abstract topology generation algorithm is proposed in this paper. Experiments on benchmark circuits demonstrate the efficiency of the proposed method in reducing the number of skew violations by 12%-37%.

We study in this paper the problem of jumper insertion on general routing (Steiner/spanning) trees with obstacles for antenna avoidance/fixing at the routing and/or post-layout stages. We formulate the jumper insertion for antenna avoidance/fixing as a tree-cutting problem and present the firstoptimal algorithm for the general tree-cutting problem. We show that the tree-cutting problem exhibits the properties of optimal substructures and greedy choices. With these properties, we present an O((V+D) lg D)-time optimal jumper insertion algorithm that uses the least number of jumpers to avoid/fix the antenna violations on a Steiner/spanning tree with V vertices and D obstacles. Experimental results show the superior effectiveness and efficiency of our algorithm.

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.

Increasingly significant variational effects present a great challenge for delivering desired clock skew reliably. Nontree clock network has been recognized as a promising approach to overcome the variation problem. Existing nontree clock routing methods are restricted to a few simple or regular structures, and often consume excessive amounts of wirelength. This paper suggests to construct a low-cost nontree clock network by inserting crosslinks in a given clock tree. The effects of the link insertion on clock skew variability are analyzed. Based on the analysis, this paper proposes two link insertion schemes that can quickly convert a clock tree to a nontree with significantly lower skew variability and very limited wirelength increase. In these schemes, the complicated nontree delay computation is circumvented. Further, they can be applied to the recently popular nonzero skew routing easily. The effectiveness of the proposed techniques has been validated through SPICE-based Monte Carlo simulations.

Under modern very large-scale integrated technology, process variations greatly affect circuit performance, especially clock skew, which is very timing sensitive. Unwanted skew due to process variation forms a bottleneck, preventing further improvement on clock frequency. Impact from intrachip interconnect variation is becoming remarkable and is difficult to be modeled efficiently due to its distributive nature. Through wire shaping analysis, the authors establish an analytical bound for the unwanted skew due to wire width variation, which is a nonnegligible factor among interconnect variations. Experimental results on benchmark circuits show that this bound is safer, tighter, and computationally faster than similar existing approach.

The sustained progress of very-large-scale-integration (VLSI) technology has dramatically increased the likelihood of the antenna problem in the manufacturing process and calls for corresponding considerations in the routing stage. In this paper, the authors propose a technique that can handle the antenna problem during the layer-assignment (LA) stage, which is an important step between global routing and detailed routing. The antenna-avoidance problem is modeled as a tree-partitioning problem with a linear-time-optimal-algorithm solution. This algorithm is customized to guide antenna avoidance in the LA stage. A linear-time optimal jumper-insertion algorithm is also derived. Experimental results on benchmark circuits show that the proposed techniques can lead to an average of 76% antenna-violation reduction and 99% via-violation reduction.

The sustained miniaturization of VLSI feature size presents great challenges to sub-wavelength photolithography and requests usage of many Resolution Enhancement Techniques (RET). The difficulty and feasibility of deploying the RET such as Alternating Phase Shifting Mask (Alt-PSM) depend heavily on circuit layout. In this paper, we propose a Boolean satisfiability (SAT) based library cell layout method that can achieve Alt-PSM compliance and composability in a constructive manner. Compared to previously reported post processing approach, our method often leads to further cell area efficiency improvement.

In ultra-deep submicron VLSI circuits, clock network is a major source of power consumption and power supply noise. Therefore, it is very important to minimize clock network size. Traditional design methodologies usually let the clock router to undertake the task of clock network minimization independently. Since a clock routing is carried out based on register locations, register placement actually has fundamental influence to a clock network size. In this paper, we propose a new clock network design methodology that Incorporates register placement optimization. Given a cell placement result, incremental modifications are performed according to clock skew specifications. The incremental placement change moves registers toward preferred locations that may enable a small clock network size. At the same time, the side-effect to logic cell placement and wire connections is controlled. Experimental results on benchmark circuits show that the proposed methodology can reduce clock network size considerably with limited impact on signal net wirelength and critical path delay.

are requiring buffers to be inserted on interconnects of even moderate length for both critical paths and fixing electrical violations. Consequently, buffer insertion is needed on tens of thousands of nets during physical synthesis optimization. Even the fast implementation of van Ginneken’s algorithm requires several hours to perform this task. This work seeks to speed up the van Ginneken style algorithms by an order of magnitude while achieving similar results. To this end, we present three approximation techniques in order to speed up the algorithm: (1) aggressive pre-buffer slack pruning, (2) squeeze pruning, and (3) library lookup. Experimental results from industrial designs show that using these techniques together yields solutions in 9 to 25 times faster than van Ginneken style algorithms, while only sacrificing less than 3 % delay penalty. I.

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

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

As VLSI technology enters the ultra-deep submicron era, wire coupling capacitance starts to dominate self capacitance and can no longer be neglected in timing driven routing. In this paper, a coupling aware timing driven track routing heuristic is proposed. Given a global routing solution and timing constraint for each net, major trunks of wire segments are assigned to routing tracks such that the minimum timing slack among all nets is maximized. Delay penalties from both coupling capacitance and wire detour are considered in a unified graph model. The core problem is formulated and solved as a Sequential Ordering Problem (SOP). Routing blockages are handled in a post processing procedure. The experimental results on benchmark circuits show that the effect of coupling capacitance on timing is significant and the proposed heuristic results in greater improvement on coupling aware timing compared with other approaches.

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

Along with the progress of VLSI technology, buffer insertion plays an increasingly critical role on affecting circuit design and performance. Traditional buffer insertion algorithms are mostly net based and therefore often result in sub-optimal delay or unnecessary buffer expense due to the lack of global view. In this paper, we propose a novel path based buffer insertion scheme which can overcome the weakness of the net based approaches. We also discuss some potential difficulties of the path based buffer insertion approach and propose solutions to them. A fast estimation on buffered delay is employed to improve the solution quality. Gate sizing is also considered at the same time. Experimental results show that our method can efficiently reduce buffer/gate cost significantly (by 71% on average) when compared to traditional net based approaches. To the best of our knowledge, this is the first work on path based buffer insertion and simultaneous gate sizing.

Clock skew is becoming increasingly difficult to control due to variations. Link based non-tree clock distribution is a cost-effective technique for reducing clock skew variations. However, previous works based on this technique were limited to unbuffered clock networks and neglected spatial correlations in the experimental validation. In this work, we overcome these shortcomings and make the link based non-tree approach feasible for realistic designs. The short circuit risk and multi-driver delay issues in buffered non-tree clock networks are investigated. Our approach is validated with SPICE based Monte Carlo simulations, considering spatial correlations among variations. The experimental results show that our approach can reduce the maximal skew by 47%, improve the skew yield from 15% to 73% on average with a decrease on the total wire and buffer capacitance.

Increasingly prominent variational effects impose imminent threat to the progress of VLSI technology. This work explores redundancy, which is a well-known fault tolerance technique, for variation tolerance. It is observed that delay variability can be reduced by making redundant paths distributed or less correlated. Based on this observation, a gate splitting methodology is proposed for achieving distributed redundancy. We show how to avoid short circuit and estimate delay in dual-driver nets which are caused by gate splitting. A spin-off gate placement heuristic is developed to minimize redundancy cost. Monte Carlo simulation results on benchmark circuits show that our method can improve timing yield from 59% to 72% with only 03% increase on cell area and 2.2% increase on wirelength on average.

In the nanometer VLSI technology, the variation effects like manufacturing variation, power supply noise, temperature etc. become very significant. As one of the most vital nets in any synchronous VLSI chip, the Clock Distribution Network (CDN) is especially sensitive to these variations. Recently proposed link-based non-tree [1] addresses this problem by constructing a non-tree that is significantly more tolerant to variations when compared to a clock tree. Although the two algorithms proposed in [1] are effective in reducing the skew variability, they have a few drawbacks including high complexity, lengthy links and uneven link distribution across the clock network. In this paper, we propose two new algorithms that can overcome these disadvantages. The effectiveness of the proposed algorithms has been validated using HSPICE based Monte Carlo simulations. Experimental results show that the new algorithms are able to achieve the same or better skew reduction with an average of 5% wire length increase when compared to the 15% wire length increase of the existing algorithms in [1]. Moreover, the new algorithms scale extremely well to big clock networks, i.e., the bigger the clock network, the less overall link cost (less than 2% for the biggest benchmark we have).

The sustained progress of VLSI technology has altered the landscape of routing which is a major physical design stage. For timing driven routings, traditional approaches which consider only wire self capacitance become inadequate since the wire delay is affected more by coupling capacitance in ultra-deep submicron designs. Furthermore, the technology scaling dramatically increases the likelihood of the antenna problem in manufacturing and requests corresponding considerations in the routing stage. In this paper, we propose techniques that can be applied to handle the coupling aware timing and the antenna problem simultaneously during layer assignment which is an important step between global routing and detailed routing. An improved probabilistic coupling capacitance model is suggested for coupling aware timing optimization without performing track assignment. The antenna avoidance problem is modeled as a tree partitioning problem with a linear time optimal algorithm solution. This algorithm is customized to guide antenna avoidance in layer assignment. A linear time optimal jumper insertion algorithm is also derived. Experimental results on benchmark circuits show that the proposed techniques can lead to an average of 270ps timing slack improvement validated by track assignment, 76% antenna violation reduction and 99% via violation reduction.

In ultra-deep submicron very large-scale integration (VLSI) designs, clock network layout plays an increasingly important role on determining circuit quality indicated by timing, power consumption, cost, power-supply noise, and tolerance to process variations. In this brief, a new merging scheme is proposed for prescribed nonzero skew routings which are useful in reducing clock cycle time, suppressing power-supply noise, and improving tolerance to process variations. This technique is simple and easy to implement for practical applications. Experimental results on benchmark circuits with both buffered and unbuffered routings exhibit large improvement on wirelength and buffer cost compared with other existing works.

Buffer insertion is an increasingly critical optimization for achieving timing closure, and the number of buffers required increases significantly with technology migration. It is imperative for an automated buffer insertion algorithm to be able to efficiently optimize tens of thousands of nets. One must also be able to effectively navigate the existing layout, including handling large blockages, blockages with holes specifically for buffers, specially allocated buffer blocks, placement porosity, and routing congestion. The algorithm must also be flexible enough to know when to use and when not to use expensive layout resources. Although several previous works have addressed buffer insertion in the presence of blockages, this is the first to present a complete solution that can manage the physical layout environment.

Increasingly significant variational effects present a great challenge for delivering desired clock skew reliably. Non-tree clock network has been recognized as a promising approach to overcome the variation problem. Existing non-tree clock routing methods are restricted to a few simple or regular structures, and often consume excessive amount of wire-length. In this paper, we suggest to construct a low cost non-tree clock network by inserting cross links in a given clock tree. The effects of the link insertion on clock skew variability are analyzed. Based on the analysis, we propose two link insertion schemes that can quickly convert a clock tree to a non-tree with significantly lower skew variability and very limited wirelength increase. In these schemes, the complicated non-tree delay computation is circumvented. Further, they can be applied to the recently popular non-zero skew routing easily. Experimental results on benchmark circuits show that this approach can achieve significant skew variability reduction with less than 2 increase of wirelength.

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.

The present research presents procedures for exploitation of level sensitive latches in wire pipelining. The user gives a Steiner tree, having a signal source and set of destination or sinks, and the location in rectangular plane, capacitive load and required arrival time at each of the destinations. The user also defines a library of non-clocked (buffer) elements and clocked elements (flip-flop and latch), also known as synchronous elements. The first procedure performs concurrent repeater and synchronous element insertion in a bottom-up manner to find the minimum latency that may be achieved between the source and the destinations. The second procedure takes additional input (required latency) for each destination, derived from previous procedure, and finds the repeater and synchronous element assignments for all internal nodes of the Steiner tree, which minimize overall area used. These procedures utilize the latency and area advantages of latch based pipelining over flip-flop based pipelining. The second procedure suggests two methods to tackle the challenges that exist in a latch based design. The deferred delay padding technique is introduced, which removes the short path violations for latches with minimal extra cost.

To achieve timing closure in a placed design, buffer insertion and driver sizing are two of the most effective transforms that can be applied. Since the driver-sizing solution and the buffer-insertion solution affect each other, suboptimal solutions may result if these techniques are applied sequentially instead of simultaneously. We show how to simply extend van Ginneken's buffer-insertion algorithm to simultaneously incorporate driver sizing and introduce the idea of a delay penalty to encapsulate the effect of driver sizing on the previous stage. The delay penalty can be precomputed efficiently via dynamic programming. Experimental results show that using driver sizing with a delay-penalty function obtains designs with superior timing and area characteristics.

In order to achieve timing closure on increasingly complex IC designs, buffer insertion needs to be performed on thousands of nets within an integrated physical synthesis system. Modern designs may contain large blocks which severely constrain the buffer locations. Even when there may appear to be space for buffers in the alleys between large blocks, these regions are often densely packed or may be needed later to fix critical paths. Therefore, within physical synthesis, a buffer insertion scheme needs to be aware of the porosity of the existing layout to be able to decide when to insert buffers in dense regions to achieve critical performance improvement and when to utilize the sparser regions of the chip. This work addresses the problem of finding porosity-aware buffering solutions by constructing a "smart Steiner tree" to pass to van Ginneken's topology-based algorithm. This flow allows one to fully integrate the algorithm into a physical synthesis system without paying an exorbitant runtime penalty. We show that significant improvements on timing closure are obtained when this approach is integrated into a physical synthesis system.

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.

In order to achieve multi-GHz operation frequency for VLSI design, clock networks need to be designed in a very elaborated manner and be able to deliver prescribed useful skews rather than merely zero-skew. Although traditional zero-skew clock muting methods can be extended directly to prescribed skews, they tend to result in excessive wirelength as the differences among delay-targets for clock sinks are neglected. In this paper, we propose the maximum delay-target and minimum merging-cost merging scheme for prescribed-skew clock routing. This scheme is simple yet surprisingly effective on wirelength reduction. Experimental results on benchmark circuits show that our merging scheme yields 53%-61% wirelength reduction compared to traditional clock routing methods.

In order to achieve timing closure on increasingly complex IC designs, buffer insertion needs to be performed on thousands of nets within an integrated physical synthesis system. Modern designs may contain large blocks which severely constrain the buffer locations. Even when there may appear to be space for buffers in the alleys between large blocks, these regions are often densely packed or may needed later to fix critical paths. Therefore, within physical synthesis, a buffer insertion scheme needs to be aware of the porosity of the existing layout to be able to decide when to insert buffers in dense regions to achieve critical performance improvement and when to utilize the sparser regions of the chip.This work addresses the problem of finding porosity-aware buffering solutions by constructing a "smart Steiner tree" to pass to van Ginneken's topology based algorithm. This flow allows one to fully integrate the algorithm into a physical synthesis system without paying an exorbitant runtime penalty. We show that significant improvements on timing closure are obtained when this approach is integrated into a physical synthesis system.

Fast progress on VLSI technology makes clock skew more susceptible to process variations. We propose DME/BST based algorithms for clock tree routing to improve skew tolerance to process variations. The worst case skew due to process variations is estimated and employed to guide the decision making during the routing. Our method can be applied to general non-zero skew requirements. Minimizing total wirelength is considered as a secondary objective at the same time. Experimental results on benchmark circuits demonstrate great improvement on process variation tolerance through our algorithms.

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.

Buffer insertion is a fundamental technology for very large scale integration interconnect optimization. This work presents the repeater insertion with adaptive tree adjustment (RIATA) heuristic that directly extends van Ginneken's classic algorithm to handle blockages in the layout. Given a Steiner tree containing a Steiner point that overlaps a blockage, a local adjustment is made to the tree topology that enables additional buffer insertion candidates to be considered. This adjustment adapts to the demand on buffer insertion and is incurred only when it facilitates the maximal slack solution. RIATA can be combined with any performance-driven Steiner tree algorithm and permits various solution search schemes to achieve different solution quality and runtime tradeoffs. Experiments on several large nets confirms that high-quality solutions can be obtained through this technique with greater efficiency than simultaneous approaches.

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.

To achieve timing closure in a placed design, buffer insertion and driver sizing are two of the most effective transforms that can be applied. Since the driver sizing solution and the buffer insertion solution affect each other, sub-optimal solutions may result if these techniques are applied sequentially instead of simultaneously. We show how to simply extend van Ginneken's buffer insertion algorithm to simultaneously incorporate driver sizing and introduce the idea of a delay penalty to encapsulate the effect of driver sizing on the previous stage. The delay penalty can be pre-computed efficiently via dynamic programming. Experimental results show that using driver sizing with a delay penalty function obtains designs with superior timing and area characteristics.

Buffer insertion is a fundamental technology for VLSI interconnect optimization. Several existing buffer insertion algorithms have evolved from van Ginneken's classic algorithm. In this work, we extend van Ginneken's algorithm to handle blockages in the layout. Given a Steiner tree containing a Steiner point that overlaps a blockage, a local adjustment is made to the tree topology that enables additional buffer insertion candidates to be considered. This adjustment is adaptive to the demand on buffer insertion and is incurred only when it facilitates the maximal slack solution. This approach can be combined with any performance-driven Steiner tree construction. The overall time complexity has linear dependence on the number of blockages and quadratic dependence on the number of potential buffer locations. Experiments on several large nets confirm that high-quality solutions can be obtained through this technique with little CPU cost.

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.

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

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.

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.

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

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.