Electronic Design Automation (EDA) tools are central to Very Large Scale Integration (VLSI) design, where numerous parameters govern the Quality-of-Result (QoR) metrics, including performance, power, and area. The high dimensionality of the parameter space, coupled with complex interactions, makes manual tuning inefficient and hinders the scalability of automated methods. Existing methods typically treat parameters as flat vectors, neglecting the EDA flow’s hierarchical causal structure, where early-stage decisions constrain later downstream stages. To address this, we propose CausalTuner, a causality-aware design space exploration framework for efficient parameter tuning. It employs a hybrid causal attention mechanism to capture stage-wise parameter interactions and embeds them into deep kernel Gaussian processes for accurate and generalizable surrogate modeling. The causal exploration strategies enhance sampling efficiency. Experiments show that CausalTuner outperforms state-of-the-art methods in both final QoR and efficiency.

Full-chip inverse lithography techniques (ILT) represent an advanced methodology for next-generation mask optimization, enhancing sub-wavelength patterning but often facing prohibitive computational costs. State-of-the-art methods rely on iterative first-order optimizers, which exhibit slow convergence, often requiring hundreds of iterations. This inefficiency is compounded by the high overhead of repeated Fast Fourier Transform (FFT) operations and inter-GPU communication per iteration. To overcome this fundamental bottleneck, we propose a scalable second-order optimizer for full-chip ILT. Our approach leverages second-order curvature information via the Hessian matrix to achieve dramatically faster convergence and superior pattern fidelity compared to conventional first-order methods. Crucially, we address the prohibitive cost of exact Hessian computation by employing Hutchinson’s method to efficiently approximate the Hessian diagonal. Combined with exponential moving average (EMA) and gradient modulation techniques, our optimizer achieves significant performance gains. Experimental results demonstrate substantial improvements in both runtime efficiency (reduced iterations) and solution quality (enhanced pattern fidelity) compared to existing first-order ILT methods, paving the way for practical full-chip ILT.

As a critical step in electronic design automation (EDA), global routing provides a guide to subsequent steps and provides valuable feedback to previous steps, including congestion, timing, and power estimation. However, given the complexity of timing and power calculation, it is difficult to estimate the impact on timing and power during the routing process. To address this issue, we propose a gradient-guided framework that computes the ''capacity sensitivity'' and ''resistance sensitivity'' of each segment to estimate their influence on the timing objectives. Integrating these two values as weights to constrain the changes in capacitance and resistance of the wire segments, we develop a timing-driven global router with superior performance. Power is also considered by optimizing the cells' switching power. Tested on ISPD25 Contest benchmarks, we can achieve 14.3% and 18.5% improvements in worst negative slack and total negative slack, respectively, with comparable congestion. With power optimization, we can further improve switching power by 10.6%.

Face-to-face (F2F) stacked three-dimensional (3D) IC is a promising alternative for scaling beyond Moore’s Law. In F2F 3D ICs, dies are connected through bonding terminals whose positions can significantly impact routing performance. Further, there exists resource competition among all the 3D nets due to the constrained bonding terminal number. In advanced technology nodes, traditional bonding terminal planning may also introduce legality challenges of bonding terminals, as the metal pitches can be much smaller than the sizes of bonding terminals. Previous works attempt to insert bonding terminals automatically using existing 2D commercial P&R tools and then consider interdie connection legality, but they fail to take the legality and routing performance into account simultaneously. In this article, we provide a novel bonding terminal assignment formulation for effective routing-aware bonding terminal planning. We explore the generalized assignment formulation and provide the routability guidance in our hybrid bonding terminal assignment problem. Our framework, BTAssign , offers a strict legality guarantee and an iterative solution. We provide two versions of the BTAssign framework, BTAssign-WL [ 1 ] and BTAssign-R, which BTAssign-R extends BTAssign-WL [ 1 ] by considering routability. The experiments are conducted on 18 open source designs with various 3D net densities and the most advanced bonding scale. The results reveal that all the testing cases with different partitioning and placement strategies could gain benefits from our BTAssign framework.

Timing is a critical issue in electronic design automation (EDA). To reduce the delay of a net, an important strategy is to minimize the path lengths from the source to the sinks. However, minimizing the path lengths will inevitably sacrifice the total wirelength. To balance the two objectives, researchers use shallow-light tree (SLT) to model and optimize the problem. In this article, we introduce MALT, a novel approach that uses a neural network to guide the construction of Steiner shallow-light trees. The constructed trees are further refined by a dynamic programming-based branch merging algorithm, which improves the wirelength without sacrificing the path lengths of any sinks. Our experimental results demonstrate that the proposed framework achieves significant improvements over both state-of-the-art traditional SLT generation algorithms and existing machine learning enhanced methods.

The post-exposure bake (PEB) process is a critical step in semiconductor lithography, directly impacting resist profile accuracy and circuit pattern fidelity. Precise modeling of PEB is essential for controlling photoacid diffusion and inhibitor reactions. In this paper, we introduce SDM-PEB, an advanced modeling framework designed to enhance the accuracy of PEB simulations by capturing both intra-layer spatial dependencies and inter-layer depthwise interactions. Leveraging a unique hierarchical feature extractor with overlapped patch merging and efficient self-attention, our approach effectively captures both coarse and fine features at multiple scales. The spatial-depthwise Mamba-based attention unit, centered on a customized selective scan and structured state space model, efficiently captures spatial and depthwise dependencies, enabling precise 3D PEB simulation. Additionally, a PEB focal loss and differential depth divergence regularization term improve the sensitivity to both spatial and depthwise variations, addressing inherent data imbalances in 3D PEB simulations. Our framework is validated with commercial rigorous model, and experimental results demonstrate that the SDM-PEB outperforms previous methods in accuracy and efficiency.

This paper presents a novel curvilinear optical proximity correction (OPC) framework. The proposed approach involves representing mask patterns with control points, which are interconnected through cardinal splines. Mask optimization is achieved by iteratively adjusting these control points, guided by lithography simulation. To ensure compliance with mask rule checking (MRC) criteria, we develop comprehensive methods for checking width, space, area, and curvature. Additionally, to match the performance of inverse lithography techniques (ILT), we design algorithms to fit ILT results and resolve MRC violations. Extensive experiments demonstrate the effectiveness of our methodology, highlighting its potential as a viable OPC/ILT alternative.

The analysis of IR-drop stands as a fundamental step in optimizing the power distribution network (PDN), and subsequently influences the design performance. However, traditional IR-drop analysis using commercial tools proves to be exceedingly time-consuming. Fast and accurate IR-drop analysis is desperately in demand to achieve high performance on timing and power. Recently, machine learning approaches have garnered attention owing to their remarkable speed and extensibility in IC designs. However, prior works for dynamic IR-drop prediction presented limited performance since they did not exploit the time-varying activities. In this paper, we proposed a dual-path model with spatial-temporal transformers to extract the static spatial features and dynamic time-variant activities for dynamic IR drop prediction. Experimental results on the large-scale advanced dataset CircuitNet show that our model significantly outperforms the state-of-the-art works.

Reinforcement learning (RL)-based macro placement has garnered significant interest in both the fields of artificial intelligence and electronic design automation (EDA), due to its excellent potential for achieving better performance, power and area optimization compared to analytical methods. However, existing techniques are restricted in the ASIC and ignore the other hardware architectures like FPGA. Neglecting the intrinsic characters of FPGA structures, conventional RL-based methods for ASICs may result in a large exploration space and low sample efficiency. In this work, we propose TRPlaceFPGA-MP, a two-stage RL-based macro placement framework for Ultrascale FPGAs. Leveraging the columnar architecture, we first train a tiny RL model to determine the candidate columns for each macro in the first stage. With the pruned searching space, a more sophisticated RL model is then trained in the second stage to determine the ultimate positions of the macros. Experimental results on the MLCAD2023 contest benchmark demonstrate that TRPlaceFPGA-MP still maintains superior placement performance compared with Vivado and DreamplaceFPGA-MP. Furthermore, it improves the convergence rate by 2.28 x and accelerates the exploration process by$1.61 x$compared to the one-stage RL approach.

Timing closure is considered across the circuit design flow. Generally, the early stage timing optimization can only focus on improving early timing metrics, e.g., rough timing estimation using linear RC model or prerouting path length, since obtaining sign-off performance needs a time-consuming routing flow. However, there is no consistency guarantee between early stage metrics and sign-off timing performance. Therefore, we utilize the power of deep learning techniques to bridge the gap between the early stage analysis and the sign-off analysis. A well-designed deep learning framework guides the adjustment of Steiner points to enable explicit early stage timing optimization. Cooperating with deep Steiner point adjustment, we propose the routing topology reconstruction to accelerate the convergence and hold a reasonable routing topology. Further, we also introduce Steiner point simplification as a post-processing technique to avoid unnecessary routing constraints. This article demonstrates the ability of the learning-assist framework to perform robust and efficient timing optimization in the early stage with comprehensive and convincing experimental results on real-world designs. With Steiner point adjustment alone, TSteinerPt, can help the state-of-the-art open-source router to obtain 11.2% and 7.1% improvement for the sign-off worst-negative slack and total negative slack, respectively. Under the additional joint optimization with routing topology reconstruction and simplification, TSteinerRec can further save 25.9% optimization duration with a better-sign-off performance.

Model-based optical proximity correction (OPC) with subresolution assist feature (SRAF) generation is a critical standard practice for compensating lithography distortions in the fabrication of integrated circuits at advanced technology nodes. Typical model-based OPC and SRAF algorithms involve the selection of user-controlled rule parameters. Conventionally, these rules are heuristically determined and applied globally throughout the correction regions, which can be time consuming and require expert knowledge of the tool. Additionally, the correlations of rule parameters to the objectives are highly nonlinear. All these factors make designing a high-performance OPC engine for complex metal designs a nontrivial task. This article proposes RuleLearner, a comprehensive mask optimization system designed for SRAF generation and model-based OPC in real industrial scenarios. The proposed framework learns from the guidance of an information-augmented inverse lithography technique engine, which, although expressive for complex designs, is expensive to generate refined masks for a whole set of design clips. Considering the nonlinearity and the tradeoff between local and global performance, the extracted rule value distributions are further optimized with customized natural gradients. The sophisticated SRAF generation, the edge segmentation and movements are then guided by the rule parameter. Experimental results show that RuleLearner can be applied across different complex design patterns and achieve the best lithographic performance and computational efficiency.

In the pursuit of advancing computational lithography, this paper introduces a novel pattern database framework designed to support related tasks. The proposed framework is built upon three core components: an unsupervised metric learning method for robust pattern embedding, a vector database for swift pattern retrieval, and an efficient algorithm dedicated to pattern clustering. These elements synergize to significantly enhance the efficiency and effectiveness of various computational lithography methods. In downstream tasks, our framework provides accurate lithography hotspot detection through pattern retrieval, streamlines inverse lithography technique (ILT) by leveraging solution reusing, and facilitates the exploration of ILT & source parameters based on the pattern clustering results. Collectively, these advancements culminate in a comprehensive improvement in computational lithography, offering a scalable solution for the ever-evolving demands of this field.

Congestion modeling is crucial for enhancing the routability of VLSI placement solutions. The underutilization of netlist information constrains the efficacy of existing layout-based congestion modeling techniques. We devise a novel approach that grafts netlist-based message passing into a layout-based model, thereby achieving a better knowledge fusion between layout and netlist to improve congestion prediction performance. The innovative heterogeneous message-passing paradigm more effectively incorporates routing demand into the model by considering connections between cells, overlaps of nets, and interactions between cells and nets. Leveraging multi-scale features, the proposed model effectively captures connection information across various ranges, addressing the issue of inadequate global information present in existing models. Using contrastive learning and mini-Gnet techniques allows the model to learn and represent features more effectively, boosting its capabilities and achieving superior performance. Extensive experiments demonstrate a notable performance enhancement of the proposed model compared to existing methods.Our code is available at: https://github.com/lanchengzou/congPred.

With the rapid development of semiconductors, the size of transistors is continuously scaling down. The shrinking circuit size poses great challenges to optical proximity correction (OPC) and hotspot detection (HSD). Recent advancements in OPC and HSD commonly employ deep neural networks, achieving impressive performance within a limited runtime. Based on these achievements, we observe that deep-learning-based models of both HSD and OPC require knowledge of layout structure information. Furthermore, these two tasks are closely related to the lithography process during chip manufacturing. Observing such strong relationships, we propose that integrating OPC and HSD into a unified deep learning model will contribute to the performance of both tasks. To bridge the relationship between OPC and HSD, we first pre-train a layout understanding model built on the mask modeling technique, which effectively captures the layout geometric information, and then the pre-trained model can be easily fine-tuned on HSD and OPC with limited data. To fully pre-train the layout understanding model (LUM), we create a large layout dataset using layout generation techniques, solving the data-hungry issues. Experimental results show that the fine-tuned LUM model achieves remarkable performance on both OPC and HSD tasks.

Microarchitecture determines the implementation of a microprocessor. Designing a microarchitecture to achieve better performance, power, and area (PPA) trade-off has been increasingly difficult. Previous data-driven methodologies hold inappropriate assumptions and lack more tightly coupling with expert knowledge. This paper proposes a novel reinforcement learning-based (RL) solution that addresses these limitations. With the integration of microarchitecture scaling graph, PPA preference space embedding, and proposed lightweight environment in RL, experiments using commercial electronic design automation (EDA) tools show that our method achieves an average PPA trade-off improvement of 16.03% than previous state-of-the-art approaches with 4.07× higher efficiency. The solution qualities outperform human implementations by at most 2.03× in the PPA trade-off.

The emerging technologies of 3D integrated circuits (3DICs) unveil a new avenue for expanding the design space into the 3D domain and present the opportunity to overcome the bottleneck of Moore’s Law for the traditional 2DICs. Among various technologies, the face-to-face bonding structure provides high integration density and reliable performance. Most commercial EDA tools, however, do not support 3DIC and cannot give a convincing solution. To exploit the benefits of stacking multiple tiers vertically, placement algorithms for 3DIC are imperatively in need. In this paper, we proposed a design flow that optimizes partitioning and placement quality for 3DICs in a unified way. Experimental results on the ICCAD2022 contest benchmark show that our work outperforms the first-place team by 3.35% in quality with less runtime and terminals used.

Composite Current Source (CCS) timing model plays an important role in modern static timing analysis (STA) because it precisely captures the timing behavior of a design at advanced nodes. However, CCS is extremely time-consuming due to its accurate but complicated timing models. To overcome this challenge, we introduce GCS-Timer, a GPU-accelerated CCS-based timing analysis algorithm. Unlike existing methods that perform model order reduction to trade accuracy for speed, GCS-Timer achieves high accuracy through a fast simulation-based analysis using GPU computing. Experimental results show that GCS-Timer can complete CCS analysis with better accuracy and achieve 3.2X faster runtime compared with a 16-threaded industrial standard timer. The source code is available at https://github.com/cuhk-eda/GCS-Timer.

Resubstitution is a flexible algorithmic framework for circuit restructuring that has been incorporated into many high-effort logic optimization flows. It is thus important to speed up resubstitution in order to obtain high-quality realizations of large-scale designs. This paper proposes a massively parallel AIG resubstitution algorithm targeting GPUs, with effective approaches to addressing cyclic dependencies and restructuring conflicts. Compared with ABC and mockturtle, our algorithm achieves 41.9× and 50.3× acceleration on average without quality degradation. When combining our resubstitution with other GPU algorithms, a GPU-based resyn2rs sequence obtains 46.4× speedup over ABC with 0.8% and 5.8% smaller area and delay respectively.

Layout pattern generation via deep generative models is a promising methodology for building practical large-scale pattern libraries. However, although improving optical proximity correction (OPC) is a major target of existing pattern generation methods, they are not explicitly trained for OPC and integrated into OPC methods. In this paper, we propose EMOGen to enable the co-evolution of layout pattern generation and learning-based OPC methods. With the novel co-evolution methodology, we achieve up to 39% enhancement in OPC and 34% improvement in pattern legalization.

Macro placement significantly influences the performance of the FPGA placement. However, constraints in modern designs like relative placement constraint (RPC) and regional constraint (RC) are often overlooked in existing routability-driven FPGA placers during macro placement. These constraints introduce challenges in optimizing routability during global placement and macro legalization stages. In this paper, we propose a novel macro placer that specifically addresses these constraints while optimizing routability. Our macro placer integrates macro size-aware pseudo nets, RC guided spreading, and multi-stage look-ahead legalization techniques to enhance routability with specified design constraints. Experimental results show that compared with DreamplaceFPGA-MP and the macro placer in Vivado, our proposed approach achieves 6% and 8% total routing score reduction on the MLCAD2023 contest benchmark. Moreover, the place and route time is reduced by 3.5% on average and up to 43% after our macro placer is integrated into Vivado. These compelling results demonstrate the efficiency gains and superior routability optimization achieved through our approach.

Due to the lengthy design cycle, generating legal, diverse and valid layout patterns artificially to expand VLSI layout pattern libraries has become an important problem to solve in order to facilitate modern design-for-manufacturability (DFM) studies. Considering the more realistic demands and to enhance functionality, this work proposes a style-controllable and violation-fixable layout pattern generation framework based on conditional diffusion models named ControLayout, which treats pattern category and complexity as conditions to control the style of generated patterns, and leverages the idea of image masking-inpainting to fix violations adaptively. Experiments reveal its promising performance in controllability and different metrics compared with the state-of-the-art methods.

With minimal compromises on other metrics, eliminating overflow and lowering congestion level of global routing results as much as possible is a crucial topic for reducing violations and hotspots in subsequent design phases. Different from current common practices of using maze routing according to some explicit orders to sequentially re-route particular nets of interest, this paper proposes a collaborative refinement framework that can generate multiple paths simultaneously to enlarge the solution space based on a multi-agent generative model, serving as a flexible post-processing plug-in on existing global routing results to reduce congestion. Experimental results well reveal its effectiveness.

Large-scale multi-FPGA prototyping platforms play an indispensable role in the functional verification of complex IC designs. The process of compiling circuit designs typically entails tasks such as partitioning, global placement and routing using a fixed multi-FPGA network. However, different circuit designs often exhibit varying inter-FPGA communication requirements after compilation. Neglecting this distinction, the use of fixed multi-FPGA networks may impede the performance enhancement of circuit verification. In this study, we investigate dynamic networking for multi-FPGA platforms and propose a comprehensive framework, which integrates simultaneous networking and system-level placement and routing. Based on theoretical analysis, we formulate this dynamic networking problem as an Integer Linear Programming (ILP) problem. Additionally, we introduce two innovative techniques, namely two-level ILP optimization and edge grouping, to expedite the ILP-solving process. Compared to the baselines on Titan23 and ICEEC22 benchmarks, our method achieves remarkable 11% and 47% improvements in system frequency respectively.

Placement is a crucial step in the physical synthesis flow that significantly determines the timing performance of a design. In this paper, we propose a timing-driven global placement framework with a hybrid pin-based weighting scheme that considers both graph and path information and an optimization-friendly RC tree and wirelength model. A calibration method is proposed to further improve the incremental timing. Experiment results show over 37% improvement on TNS and 15% improvement on WNS, with 4.2% less HPWL on the ICCAD 2015 benchmark compared to the state-of-the-art GPU-accelerated differentiable timing-driven placer, while also being around 2x faster.

Face-to-face (F2F) stacked 3D IC is a promising alternative for scaling beyond Moore's Law. In F2F 3D ICs, dies are connected through bonding terminals whose positions can significantly impact routing performance. Further, there exists resource competition among all the 3D nets due to the constrained bonding terminal number. In advanced technology nodes, such 3D integration may also introduce legality challenges of bonding terminals, as the metal pitches can be much smaller than the sizes of bonding terminals. Previous works attempt to insert bonding terminals automatically using existing 2D commercial P&R tools and then consider inter-die connection legality, but they fail to take the legality and routing performance into account simultaneously. In this paper, we explore the formulation of the generalized assignment in the hybrid bonding terminal assignment problem. Our framework, BTAssign, offers a strict legality guarantee and an iterative solution. The experiments are conducted on 18 open-source designs with various 3D net densities and the most advanced bonding scale. The results reveal that BTAssign can achieve improvements in routed wirelength under all testing conditions from 1.0% to 5.0% with a tolerable runtime overhead.

The 2024 International Symposium on Physical Design lifetime achievement award goes to Professor Martin D F Wong for his oustanding contributions in the field.

Neural ordinary differential equations (Neural ODEs) is a family of continuous-depth neural networks where the evolution of hidden states is governed by learnable temporal derivatives. We identify a significant limitation in applying traditional Batch Normalization (BN) to Neural ODEs, due to a fundamental mismatch --- BN was initially designed for discrete neural networks with no temporal dimension, whereas Neural ODEs operate continuously over time. To bridge this gap, we introduce temporal adaptive Batch Normalization (TA-BN), a novel technique that acts as the continuous-time analog to traditional BN. Our empirical findings reveal that TA-BN enables the stacking of more layers within Neural ODEs, enhancing their performance. Moreover, when confined to a model architecture consisting of a single Neural ODE followed by a linear layer, TA-BN achieves 91.1\% test accuracy on CIFAR-10 with 2.2 million parameters, making it the first \texttt{unmixed} Neural ODE architecture to approach MobileNetV2-level parameter efficiency. Extensive numerical experiments on image classification and physical system modeling substantiate the superiority of TA-BN compared to baseline methods.

Source mask optimization (SMO) is vital for mitigating lithography imaging distortions caused by shrinking critical dimensions in integrated circuit fabrication. However, the computational intensity of SMO, involving multiple integrals in Abbe’s theory, hinders its widespread adoption and advancement. In this paper, we present Diff-SMO, a highly efficient and accurate SMO framework with a primary emphasis on enhancing source optimization techniques. Previous research was confined to mask optimization acceleration due to the constraints of the academia lithography model. Diff-SMO extends the scope of optimization by concurrently refining the intricate interplay between the source and mask. We first develop a GPU-accelerated lithography simulator grounded in Abbe’s theory, enabling full GPU acceleration throughout the SMO process. Furthermore, we propose a discrete diffusion model for generating quasi-optimal sources, significantly improving computational efficiency. Our experimental results demonstrate exceptional imaging fidelity, surpassing the state-of-the-art, with over 200 times higher throughput compared to traditional SMO methods.

Placement serves as a fundamental step in VLSI physical design. Recently, GPU-based placer DREAMPlace 1 demonstrated its superiority over CPU-based placers. In this work, we develop an extremely fast GPU-accelerated placer Xplace which considers factors at operator-level optimization. Xplace achieves around 2x speedup with better solution quality compared to DREAMPlace. We also plug a novel Fourier neural network into Xplace as an extension. Besides, we enable Xplace to handle the detailed-routability-driven placement problem and demonstrate its superiority in terms of quality and performance. We believe this work not only proposes an extremely fast and extensible placement framework but also illustrates a possibility of incorporating a neural network component into a GPU-accelerated analytical placer. The source code of Xplace is released on GitHub.

Optical proximity correction (OPC) is a widely used technique to enhance the printability of designs in various foundaries. Recently, there has been a growing interest in using rigorous numerical optimization and machine learning to improve the robustness and efficiency of OPC. Our research focuses on developing a self-adaptive OPC framework that leverages the properties of pattern distribution and repetition in design layouts to optimize the correction process. We observe that different sub-regions in a design layer have varying pattern complexities, and many patterns repeat themselves throughout the layout. By exploiting these properties, we propose a framework that adaptively selects the most suitable OPC solvers from an extensible pool to optimize the correction process for each pattern based on its complexity. This approach allows for a co-optimization of speed and accuracy. Additionally, we introduce a graph-based dynamic pattern library that reuses optimized masks for repeated patterns, further accelerating the OPC flow. Our experimental results demonstrate a significant improvement in both performance and efficiency using our proposed framework.

Inverse lithography technique (ILT) is one of the most widely used resolution enhancement techniques (RETs) to compensate for the diffraction effect in the lithography process. However, ILT suffers from runtime overhead issues with the shrinking size of technology nodes. In this article, our proposed L2O-ILT framework unrolls the iterative ILT optimization algorithm into a learnable neural network with high interpretability, which can generate a high-quality initial mask for fast refinement. Experimental results demonstrate that our method achieves better performance on both mask printability and runtime than the previous methods.

Microarchitecture parameters tuning is critical in the microprocessor design cycle. It is a non-trivial design space exploration (DSE) problem due to the large solution space, cycle-accurate simulators’ modeling inaccuracy, and high simulation runtime for performance evaluations. Previous methods require massive expert efforts to construct interpretable equations or high computing resource demands to train black-box prediction models. This article follows the black-box methods due to better solution qualities than analytical methods in general. We summarize two learned lessons and propose BOOM-Explorer accordingly. First, embedding microarchitecture domain knowledge in the DSE improves the solution quality. Second, BOOM-Explorer makes the microarchitecture DSE for register-transfer-level designs within the limited time budget feasible. We enhance BOOM-Explorer with the diversity-guidance, further improving the algorithm performance. Experimental results with RISC-V Berkeley-Out-of-Order Machine under 7-nm technology show that our proposed methodology achieves an average of 18.75% higher Pareto hypervolume, 35.47% less average distance to reference set, and 65.38% less overall running time compared to previous approaches.

Lithography is fundamental to integrated circuit fabrication, necessitating large computation overhead. The advancement of machine learning (ML)-based lithography models alleviates the trade-offs between manufacturing process expense and capability. However, all previous methods regard the lithography system as an image-to-image black box mapping, utilizing network parameters to learn by rote mappings from massive mask-to-aerial or mask-to-resist image pairs, resulting in poor generalization capability. In this paper, we propose a new ML-based paradigm disassembling the rigorous lithographic model into non-parametric mask operations and learned optical kernels containing determinant source, pupil, and lithography information. By optimizing complex-valued neural fields to perform optical kernel regression from coordinates, our method can accurately restore lithography system using a small-scale training dataset with fewer parameters, demonstrating superior generalization capability as well. Experiments show that our framework can use 31% of parameters while achieving 69× smaller mean squared error with 1.3× higher throughput than the state-of-the-art.

Analytical placement is proven to be effective in global placement. The differentiability of wirelength models is very critical to gradient-based numerical optimization. Most previous works approximate the non-smooth half-perimeter wirelength (HPWL) model with various differentiable functions. In this paper, we propose a new differentiable wirelength model using the Moreau envelope to approximate HPWL. By combining the state-of-the-art electrostatic-based placement algorithm, the experimental results demonstrate that our proposed algorithm can achieve up to 5.4% HPWL improvement and more than 1% on average compared to the most widely-used nonlinear wirelength model.

Timing closure is crucial across the circuit design flow. Since obtaining sign-off performance needs a time-consuming routing flow, all the previous early-stage timing optimization works only focus on improving early timing metrics, e.g., rough timing estimation using linear RC model or pre-routing path-length. However, there is no consistency guarantee between early-stage metrics and sign-off timing performance. To enable explicit early-stage optimization on the sign-off timing metrics, we propose a novel timing optimization framework, TSteiner. This paper demonstrates the ability of the learning framework to perform robust and efficient timing optimization in the early stage with comprehensive and convincing experimental results on real-world designs.

The placement and routing (PnR) flow plays a critical role in physical design. Poor routing congestion is a possible problem causing severe routing detours, which can lead to deteriorated timing performance or even routing failure. Deep-learning-based congestion prediction model is designed to guide the global placement process in previous work. However, the distribution shift problem in this method limits its performance. In this paper, we mitigate the distribution shift problem with a look-ahead mechanism inspired by optical flow prediction and an invariant feature space learning technique. With the proposed method, we can achieve better congestion prediction performance and less-congested placement results.

Path-based Analysis (PBA) is a key process in Static Timing Analysis (STA) to reduce excessive slack pessimism. How-ever, PBA can easily become the major performance bottleneck due to its long execution time. To overcome this bottleneck, recent STA researches have proposed to accelerate PBA algorithms with manycore CPU and GPU parallelisms. However, GPU memory is rather limited when we compute PBA on large industrial designs with millions of gates. In this work, we introduce a new endpoint-oriented partitioning framework that can separate STA graphs and dispatch the PBA workload onto multiple GPUs. Our framework can quickly identify logic overlaps among endpoints and group endpoints based on the size of shared logic. We then recover graph partitions from the grouped endpoints and offload independent PBA workloads to multiple GPUs. Experiments show that our framework can largely accelerate the PBA process on designs with over 10M gates.

Circuit partitioning is a critical step in hardware-assisted functional verification that involves splitting a circuit into multiple partitions and assigning them to specific hardware. However, partitioning a large circuit can require considerable computation resources and time, especially when complex hardware constraints are involved. Moreover, the path delay after partitioning can have a significant impact on verification efficiency, making early path delay prediction crucial for refining the circuit effectively. In this work, we propose a novel circuit partitioning predictor, named CPP, to rapidly and accurately predict the path delay after partitioning. To achieve this, we use circuit coarsening to develop a multi-level path representation and employ a convolutional neural network (CNN) that can capture both local and global path structures for delay prediction. Through extensive experiments on large industrial circuits, we demonstrate the superiority of our prediction framework.

With the size of modern VLSI circuits growing in size to billions of transistors, multi-FPGA systems have been widely applied in circuit emulation and prototyping. To make full advantage of limited FPGA resources and improve the system frequency, designing a flexible multi-FPGA system with a corresponding design compilation flow is an important research problem in both industry and academia. In this work, we propose a practical and scalable partitioning and routing framework, named SPARK, for a multi-FPGA system with an adjustable near-square mesh shape and the minimum number of FPGAs. To resolve the significant constraints on multiple hardware resources for partitioning, SPARK leverages the general hypergraph partitioning tool by combining it with an efficient legalization algorithm to minimize cut size without resource overflow. We also propose novel max_cut-driven maze routing and max_hop-driven refinement algorithms to optimize the max_cut and max_hop in multi-FPGA systems meanwhile and improve the system frequency. Extensive experiments using the largest public circuit benchmarks for FPGA and several small FPGA settings from the industry demonstrate the effectiveness and efficiency of SPARK.

The microarchitecture design of processors faces growing complexity due to expanding design space and time-intensive verification processes. Utilizing historical design task data can improve the search process, but managing distribution discrepancies between different source tasks is essential for enhancing the search method's generalization ability. In light of this, we introduce IT-DSE, a microarchitecture searching framework with the surrogate model pre-trained to absorb knowledge from previous design tasks. The Feature Tokenizer-Transformer (FT-Transformer) serves as a backbone, facilitating feature extraction from source tasks even with varied design spaces. Concurrently, the invariant risk minimization (IRM) paradigm bolsters generalization ability under data distribution discrepancies. Further, IT-DSE exploits a combination of multi-objective Bayesian optimization and a model ensemble to discover Pareto-optimal designs Experimental results indicate that IT-DSE effectively harnesses the knowledge of existing microarchitecture designs and uncovers designs that outperform previous methods in terms of power, performance, and area (PPA).

Congestion modeling is a key point for improving the routability of VLSI placement solutions. The underuti-lization of netlist information limits the performance of ex-isting layout-based congestion modeling methods. Combining the knowledge from netlist and layout, we graft netlist-based message passing on a layout-based model to achieve better congestion prediction performance. The novel heterogeneous message-passing paradigm better embeds the routing demand into the model by considering both connections between cells and overlaps of nets. With the help of multi-scale features, the proposed model can effectively capture connection information across different ranges, overcoming the problem of insufficient global information in existing models. Based on the advancements, the proposed model achieves significant improvement compared with existing methods.

3D heterogeneous integration enables the integration of multiple heterogeneous chiplets into the same package with the effective reduction of package size and interconnection latency. According to the market requirement, chiplets with robust re-usability and effective cost reduction can be selected from a library to form different package products for enlarging total profit. Since die-to-wafer (D2W) bonding enables the chiplets with different sizes to be bonded in a package, it is a more flexible option for 3D heterogeneous integration compared with the conventional wafer-to-wafer (W2W) bonding. However, this promising technique creates new issues, including 1) flexible chiplet bonding enabling more than one chiplet to be bonded with a base chiplet to construct multiple products and 2) degraded bonding leading to the degradation of performance. In this work, a distributed integer-linear-programming-based (ILP-based) method is proposed to efficiently maximize the profits of multiple package products considering the issues of cost-addition 3D heterogeneous integration with D2W bonding. Compared with the baseline, the distributed ILP-based method can achieve the best profits while achieving a 5.96X speedup. To the best of our knowledge, this is the first work to solve the multi-product optimization problem for 3D heterogeneous integration with D2W bonding.

Computational lithography provides algorithmic and mathematical support for resolution enhancement in optical lithography, which is the critical step in semiconductor manufacturing. The time-consuming lithography simulation and mask optimization processes limit the practical application of inverse lithography technology (ILT), a promising solution to the challenges of advanced-node lithography. Although various machine learning methods for ILT have shown promise for reducing the computational burden, this field is in lack of a dataset that can train the models thoroughly and evaluate the performance comprehensively. To boost the development of AI-driven computational lithography, we present the LithoBench dataset, a collection of circuit layout tiles for deep-learning-based lithography simulation and mask optimization. LithoBench consists of more than 120k tiles that are cropped from real circuit designs or synthesized according to the layout topologies of famous ILT testcases. The ground truths are generated by a famous lithography model in academia and an advanced ILT method. Based on the data, we provide a framework to design and evaluate deep neural networks (DNNs) with the data. The framework is used to benchmark state-of-the-art models on lithography simulation and mask optimization. We hope LithoBench can promote the research and development of computational lithography. LithoBench is available at https://anonymous.4open.science/r/lithobench-APPL.

As a key routine in static timing analysis (STA), path-based analysis (PBA) plays a very important role in refining the critical path report by reducing excessive slack pessimism. PBA is also well known for its long execution time, which makes it a hot topic for parallel computing in the STA community. However, nearly all of the parallel PBA algorithms are restricted to CPU architectures, which greatly limits their scalability. To achieve a new performance milestone on PBA, we must leverage the high throughput computing in the graphics processing unit (GPU). Therefore, in this work, we propose a new GPU-accelerated PBA framework which contains compact data structures and highly efficient kernels. By integrating with GPU-accelerated preprocessing steps, our framework can also effectively handle extensive critical path constraints. Besides, we highlight many optimization techniques that can overcome the execution bottleneck and further boost the performance. In experiments, we demonstrate$543\times$speed-up compared to the state-of-the-art PBA algorithm on the design with 1.6 million gates, which outperforms$25\times $–$45\times$over the state-of-the-art parallel PBA algorithm on 40 CPU cores. A fully optimized framework can achieve$3\times$–$5\times$speed-up on top of that.

Multiple patterning lithography decomposition (MPLD) and mask optimization enable the ever-shrinking device feature sizes far below the lithography system limit. Conventional MPLD is solved by mathematical programming or graph-based approaches, where a set of predetermined rules is indispensable to identify the conflicts to be resolved. In this article, we explore rule-free layout decomposition following a simple but sweet principle, let the mask optimizer “teach” the layout decomposer how to generate suitable decompositions. Our flow includes a reinforcement-learning-based layout decomposer and a deep-learning-based mask optimizer. Without any handcrafted rules, our framework can perform competitively and even surpass the state-of-the-art rule-based methods with notable$(7\times \sim 63\times)$turn-around-time speedup.

Maze routing is usually the most time-consuming step in global routing and detailed routing. A commonly used maze routing method is to start from one pin and iteratively connect the current route to the closest unconnected pin. This method reduces the maze routing problem to multiple multisource–multidestination shortest path problems. The shortest path problem in VLSI routing has: 1) rectilinear routing directions and 2) preferably small via usage. By utilizing these two characteristics, we propose a novel parallel algorithm called GAMER to accelerate the multisource–multidestination shortest path problem for VLSI routing. GAMER decomposes the shortest path search into alternating vertical and horizontal$sweep$operations, and two parallel algorithms are proposed to accelerate a$sweep$operation from$O(n^{2})$to$O(\log _{2}{n})$on a grid graph of$n\times n$. Several techniques of applying GAMER on irregular routing regions are also introduced. Experiments are conducted by integrating GAMER into the state-of-the-art academic global router CUGR. CUGR adopts a two-level maze routing scheme, including coarse-grained routing and fine-grained routing, and they can be accelerated by$19.85\times $and$2.59\times $, respectively, with GAMER, achieving an overall speedup of$2.7\times $without quality degradation.

In the lithography process, subresolution assist features (SRAFs), as an essential resolution enhancement technique (RET), is applied to improve the pattern fidelity and enlarge the process window. In this article, we propose a robust constraint-aware SRAF generation method based on continuous transmission mask (CTM). The intensity distribution on the CTM is extracted to guide the SRAF generation. The SRAF insertion also honors the design rules, which is formulated as integer programming with quadratic constraints and solved by a fast yet efficient algorithm. A fast probe-based SRAF evolution method is proposed to determine the shapes of SRAFs. The effectiveness and efficiency are demonstrated based on the experimental results.

Over the past few years, super-resolution (SR) processing has achieved astonishing progress along with the development of deep learning. Nevertheless, the rigorous requirement for real-time inference, especially for video tasks, leaves a harsh challenge for both the model architecture design and the hardware-level implementation. In this article, we propose a hardware-aware acceleration on embedded GPU devices as a full-stack SR deployment framework. The most critical stage with dictionary learning applied in SR flow was analyzed in details and optimized with a tailored dictionary slimming strategy. Moreover, we also delve into the programming architecture of hardware while analyzing the model structure to optimize the computation kernels to reduce inference latency and maximize the throughput given restricted computing power. In addition, we further accelerate the model with 8-bit integer inference by quantizing the weights in the compressed model. An adaptive 8-bit quantization flow for SR task enables the quantized model to achieve a comparable result with the full-precision baselines. With the help of our approaches, the computation and communication bottlenecks in the deep dictionary learning-based SR models can be overcome effectively. The experiments on both edge embedded device NVIDIA NX and 2080Ti prove that our framework exceeds the performance of state-of-the-art NVIDIA TensorRT significantly and can achieve real-time performance.

Modern very large-scale integration (VLSI) design requires the implementation of integrated circuits using electronic design automation (EDA) tools. Due to the complexity of EDA algorithms, there are numerous tool parameters that have imperative impacts on the chip design quality. Manual selection of parameter values is excessively laborious and constrained by experts’ experience. Due to the high complexity and lack of parallelization, most existing parameter tuning methods cannot make sufficient exploration in a large search space. In this article, we boost the efficiency and performance of parameter tuning with random embedding and multi-objective trust-region Bayesian optimization. Random embedding can effectively cut down the number of variables in the search process and thus reduce the runtime of Bayesian optimization. Multi-objective trust-region Bayesian optimization allows the algorithm to explore diverse solutions with excellent parallelism. Due to the ability to do more exploration in limited runtime, the proposed framework can achieve better performance than existing methods in our experiments.

Design Rule Checking (DRC) is a critical step in integrated circuit design. DRC requires formatted scripts as the input to design rule checkers. However, these scripts are manually generated in the foundry, which is tedious and error prone for generation of thousands of rules in advanced technology nodes. To mitigate this issue, we propose the first DRC script generation framework, leveraging a deep learning-based key information extractor to automatically identify essential arguments from rules and a script translator to organize the extracted arguments into executable DRC scripts. We further enhance the performance of the extractor with three specific design rule generation techniques and a multi-task learning-based rule classification module. Experimental results demonstrate that the framework can generate a single rule script in 5.46 ms on average, with the extractor achieving 91.1% precision and 91.8% recall on the key information extraction. Compared with the manual generation, our framework can significantly reduce the turnaround time and speed up process design closure.

Logic rewriting is an important part in logic optimization. It rewrites a circuit by replacing local subgraphs with logically equivalent ones, so that the area and the delay of the circuit can be optimized. This paper introduces a parallel AIG rewriting algorithm with a new concept of logical cuts. Experiments show that this algorithm implemented with one GPU can be on average 32X faster than the logic rewriting in the logic synthesis tool ABC on large benchmarks. Compared with other logic rewriting acceleration works, ours has the best quality and the shortest running time.

Placement serves as a fundamental step in VLSI physical design. Recently, GPU-based global placer DREAMPlace[1] demonstrated its superiority over CPU-based global placers. In this work, we develop an extremely fast GPU accelerated global placer Xplace which achieves around 2x speedup with better solution quality compared to DREAMPlace. We also plug a novel Fourier neural network into Xplace as an extension to further improve the solution quality. We believe this work not only proposes a new, fast, extensible placement framework but also illustrates a possibility to incorporate a neural network component into a GPU accelerated analytical placer.

The finite element method (FEM) is a well-known technique for approximately solving partial differential equations and it finds application in various engineering disciplines. The recently introduced wafer-scale engine (WSE) has shown the potential to accelerate FEM by up to 10,000×. However, accelerating FEM to the full potential of a WSE is non-trivial. Thus, in this work, we propose a partitioning algorithm to partition a 3D finite element model into tiles. The tiles can be thought of as a special netlist and are placed onto the 2D array of a WSE by our placement algorithm. Compared to the best-known approach, our partitioning has around 5% higher accuracy, and our placement algorithm can produce around 11% shorter wirelength (L1.5-normalized) on average.

Inverse lithography technology (ILT) is one of the promising resolution enhancement techniques (RETs) in modern design-for-manufacturing closure, however, it suffers from huge computational overhead and unaffordable mask writing time. In this paper, we propose A2-ILT, a GPU-accelerated ILT framework with spatial attention mechanism. Based on the previous GPU-accelerated ILT flow, we significantly improve the ILT quality by introducing spatial attention map and on-the-fly mask rectilinearization, and strengthen the robustness by Reinforcement-Learning deployment. Experimental results show that, comparing to the state-of-the-art solutions, A2-ILT achieves 5.06% and 11.60% reduction in printing error and process variation band with a lower mask complexity and superior runtime performance.

Global routing is an essential step in physical design. Recently there are works on accelerating global routers using GPU. However, they only focus on certain stages of global routing, and have limited overall speedup. In this paper, we present a superfast full-scale GPU-accelerated global router and introduce useful parallelization techniques for routing. Experiments show that our 3D router achieves both good quality and short runtime compared to other state-of-the-art academic global routers.

As the demand for semiconductor products increases and the integrated circuits (IC) processes become more and more complex, wafer failure pattern classification is gaining more attention from manufacturers and researchers to improve yield. To further cope with the real-world scenario that there are only very limited labeled data and without any unlabeled data in the early manufacturing stage of new products, this work proposes an efficient human-like staged learning framework for wafer failure pattern classification named WaferHSL. Inspired by human's knowledge acquisition process, a mutually reinforcing task fusion scheme is designed for guiding the deep learning model to simultaneously establish the knowledge of spatial relationships, geometry properties and semantics. Furthermore, a progressive stage controller is deployed to partition and control the learning process, so as to enable humanlike progressive advancement in the model. Experimental results show that with only 10% labeled samples and no unlabeled samples, WaferHSL can achieve better results than previous SOTA methods trained with 60% labeled samples and a large number of unlabeled samples, while the improvement is even more significant when using the same size of labeled training set.

Placement and routing are two crucial steps in the physical design of integrated circuits (ICs). To close the gap between placement and routing, the routing with cell movement problem has attracted great attention recently. In this problem, a certain number of cells can be moved to new positions and the nets can be rerouted to improve the total wire length. In this work, we advance the study on this problem by proposing a two-level layer-aware scheme, named ATLAS. A coarse-level cluster-based cell movement is first performed to optimize via usage and provides a better starting point for the next fine-level single cell movement. To further encourage routing on the upper metal layers, we utilize a set of adjusted layer weights to increase the routing cost on lower layers. Experimental results on the ICCAD 2020 contest benchmarks show that ATLAS achieves much more wire length reduction compared with the state-of-the-art routing with cell movement engine. Furthermore, applied on the ICCAD 2021 contest benchmarks, ATLAS outperforms the first place team of the contest with much better solution quality while being 3× faster.

Optical proximity correction (OPC) is a widely-used resolution enhancement technique (RET) for printability optimization. Recently, rigorous numerical optimization and fast machine learning are the research focus of OPC in both academia and industry, each of which complements the other in terms of robustness or efficiency. We inspect the pattern distribution on a design layer and find that different sub-regions have different pattern complexity. Besides, we also find that many patterns repetitively appear in the design layout, and these patterns may possibly share optimized masks. We exploit these properties and propose a self-adaptive OPC framework to improve efficiency. Firstly we choose different OPC solvers adaptively for patterns of different complexity from an extensible solver pool to reach a speed/accuracy co-optimization. Apart from that, we prove the feasibility of reusing optimized masks for repeated patterns and hence, build a graph-based dynamic pattern library reusing stored masks to further speed up the OPC flow. Experimental results show that our framework achieves substantial improvement in both performance and efficiency.

Path-based Analysis (PBA) is an important step in the design closure flow for reducing slack pessimism. However, PBA is extremely time-consuming. Recent years have seen many parallel PBA algorithms, but most of them are architecturally constrained by the CPU parallelism and do not scale beyond a few threads. To overcome this challenge, we propose in this paper a new fast and accurate PBA algorithm by harnessing the power of graphics processing unit (GPU). We introduce GPU-efficient data structures, high-performance kernels, and efficient CPU-GPU task decomposition strateiges, to accelerate PBA to a new performance milestone. Experimental results show that our method can speed up the state-of-the-art algorithm by $543\times$ on a design of 1.6 million gates with exact accuracy. At the extreme, our method of 1 CPU and 1 GPU outperforms the state-of-the-art algorithm of 40 CPUs by $25-45\times$.

The microarchitecture design of a processor has been increasingly difficult due to the large design space and time-consuming verification flow. Previously, researchers rely on prior knowledge and cycle-accurate simulators to analyze the performance of different microarchitecture designs but lack sufficient discussions on methodologies to strike a good balance between power and performance. This work proposes an automatic framework to explore microarchitecture designs of the RISC-V Berkeley Out-of-Order Machine (BOOM), termed as BOOM-Explorer, achieving a good trade-off on power and performance. Firstly, the framework utilizes an advanced microarchitecture-aware active learning (MicroAL) algorithm to generate a diverse and representative initial design set. Secondly, a Gaussian process model with deep kernel learning functions (DKL-GP) is built to characterize the design space. Thirdly, correlated multi-objective Bayesian optimization is leveraged to explore Pareto-optimal designs. Experimental results show that BOOM-Explorer can search for designs that dominate previous arts and designs developed by senior engineers in terms of power and performance within a much shorter time.

Path-based Analysis (PBA) is a pivotal step in Static Timing Analysis (STA) for reducing slack pessimism and improving quality of results. Optimization flows often invoke PBA repeatedly with different critical path constraints to verify correct timing behavior under certain logic cone. However, PBA is extremely time consuming and state-of-the-art PBA algorithms are hardly scaled beyond a few CPU threads under constrained search space. In order to achieve new performance milestone, in this work, we propose a new GPU-accelerated PBA algorithm which can handle extensive path constraints and quickly report arbitrary number of critical paths in constrained search space. Experimental results show that our algorithm can generated identical path report and achieve up to 102x speed up on a million-gate design compared to the state-of-the-art algorithm.

Maze routing is usually the most time-consuming step in global routing or detailed routing. One possible way to accelerate it is to use parallel computing. Net-level parallelism is commonly used but it is affected greatly by the dependency between nets. There are few GPU-friendly parallel maze routers, which can be nontrivial to design. In this paper, we propose a pathfinding-level parallel 3D routing scheme. We implemented it in CUDA and applied it to the coarsened maze routing stage of an open source global router CUGR. Compared with CUGR on the ICCAD 2019 global routing contest benchmark suite, we achieve an average of 16 x speedup in the coarsened maze routing stage without loss of quality.

Placement and routing (P&R) are two important stages in the physical design flow. After circuit components are assigned locations by a placer, routing will take place to make the connections. Defined as two separate problems, placement and routing aim to optimize different objectives. For instance, placement usually focuses on optimizing the half-perimeter wire length (HPWL) and estimated congestion while routing will try to minimize the routed wire length and the number of overflows. The misalignment between the objectives will inevitably lead to a significant degradation in solution quality. Therefore, in this paper, we present Starfish, an efficient P&R co-optimization engine that bridges the gap between placement and routing. To incrementally optimize the routed wire length, Starfish conducts cell movements and reconnects broken nets by A*-based partial rerouting. Experimental results on the ICCAD 2020 contest benchmark suites [1] show that our co-optimizer outperforms all the contestants with better solution quality and much shorter runtime.

Recent years have witnessed impressive progress in super-resolution (SR) processing. However, its real-time inference requirement sets a challenge not only for the model design but also for the on-chip implementation. In this paper, we implement a full-stack SR acceleration framework on embedded GPU devices. The special dictionary learning algorithm used in SR models was analyzed in detail and accelerated via a novel dictionary selective strategy. Besides, the hardware programming architecture together with the model structure is analyzed to guide the optimal design of computation kernels to minimize the inference latency under the resource constraints. With these novel techniques, the communication and computation bottlenecks in the deep dictionary learning-based SR models are tackled perfectly. The experiments on the edge embedded NVIDIA NX and 2080Ti show that our method outperforms the state-of-the-art NVIDIA TensorRT significantly and can achieve real-time performance.

As the complexity of circuit designs continues growing, multi-FPGA systems are becoming more and more popular for logic emulation and rapid prototyping. In a multi-FPGA system, different FPGAs are connected by limited physical wires, in other words, one FPGA usually has direct connections with only a few FPGAs. During the circuit partitioning stage, assigning two directly connected nodes to two FPGAs without physical links would significantly increase the delay and degrade the overall performance. However, some well-known partitioners, like hMETIS and PaToH, mainly focus on cut size minimization without considering such topology constraints of FPGAs, which limits their practical usage. In this paper, we propose a multi-level topology-driven partitioning framework, named as TopoPart, to deal with topology constraints in a multi-FPGA system. In particular, we firstly devise a candidate FPGA propagation algorithm in the coarsening phase to guarantee the later stages free of topology violations. In the last refinement phase, cut size is iteratively optimized maintaining both topology and resource constraints. Compared with the proposed baseline, our partitioning algorithm achieves zero topology violation while giving less cut size.

With the rapid development of semiconductors and the continuous scaling-down of circuit feature size, hotspot detection has become much more challenging and crucial as a critical step in the physical verification flow. In recent years, advanced deep learning techniques have spawned many frameworks for hotspot detection. However, most existing hotspot detectors can only detect defects arising in the central region of small clips, making the whole detection process time-consuming on large layouts. Some advanced hotspot detectors can detect multiple hotspots in a large area but need to propose potential defect regions, and a refinement step is required to locate the hotspot precisely. To simplify the procedure of multi-stage detectors, an end - to-end single-stage hotspot detector is proposed to identify hotspots on large scales without refining potential regions. Besides, multiple tasks are developed to learn various pattern topological features. Also, a feature aggregation module based on Transformer Encoder is designed to globally capture the relationship between different features, further enhancing the feature representation ability. Experimental results show that our proposed framework achieves higher accuracy over prior methods with faster inference speed.

Since the first release in 2015, OpenTimer v1 has been used in many industrial and academic projects for analyzing the timing of custom designs. After four-year research and developments, we have announced OpenTimer v2-a major release that efficiently supports: 1) a new task-based parallel incremental timing analysis engine to break through the performance bottleneck of existing loop-based methods; 2) a new application programming interface (API) concept to exploit high degrees of parallelisms; and 3) an enhanced support for industry-standard design formats to improve user experience. Compared with OpenTimer v1, we rearchitect v2 with a modern C++ programming language and advanced parallel computing techniques to largely improve the tool performance and usability. For a particular example, OpenTimer v2 achieved up to 5.33× speedup over v1 in incremental timing, and scaled higher with increasing cores. Our contributions include both technical innovations and engineering knowledge that are open and accessible to promote timing research in the community.

This article introduces Cpp-Taskflow, a high-performance parallel task programming system, to streamline the building of large and complex parallel applications. Cpp-Taskflow leverages the power of modern C++ and task-based approaches to enable efficient implementations of parallel decomposition strategies. Our programming model can quickly handle not only traditional loop-level parallelism but also irregular patterns, such as graph algorithms and dynamic control flows. Compared with existing libraries, Cpp-Taskflow is more cost efficient in performance scaling and software integration. We have evaluated Cpp-Taskflow on both micro-benchmarks and large-scale design automation problems of million-scale tasking. In a particular timing analysis workload, Cpp-Taskflow outperformed OpenMP by 2× faster using 2× fewer lines of code. We have also shown Cpp-Taskflow achieved up to 47.81% speed-up with 28.5% less code over the industrial-strength library, Intel Threading Building Blocks, on a detailed placement problem.

In this paper, we introduce a fast and efficient critical path generation algorithm considering extensive path constraints on a Static Timing Analysis (STA) graph. Critical path generation is a key routine in the inner loop of path-based analysis and timing-driven synthesis flows. Our algorithm can report arbitrary numbers of critical paths on a logic cone constrained by a sequence of from/through/to pins under different min/max modes and rise/fall transitions. Our algorithm is general, efficient, and provably good. Experimental results have showed that our algorithm produces reports that matches a golden reference generated by an industrial signoff timer. Our results also correlate to a commercial timer yet achieving more than an order of magnitude speed-up.

Automatic heuristic design through reinforcement learning opens a promising direction for solving computationally difficult problems. Unlike most previous works that aimed at solution construction, we explore the possibility of acquiring local search heuristics through massive search experiments. To illustrate the applicability, an agent is trained to perform a walk in the search space by selecting a candidate neighbor solution at each step. Specifically, we target the floorplanning problem, where a neighbor solution is generated through perturbing the sequence pair encoding of a floorplan. Experimental results demonstrate the efficacy of the acquired heuristics as well as the potential of automatic heuristic design.

Work-stealing is a key component of many parallel task graph libraries such as Intel Threading Building Blocks (TBB) FlowGraph, Microsoft Task Parallel Library (TPL) Batch .Net, Cpp-Taskflow, and Nabbit. However, designing a correct and effective work-stealing scheduler is a notoriously difficult job, due to subtle implementation details of concurrency controls and decentralized coordination between threads. This problem becomes even more challenging when striving for optimal thread usage in handling parallel workloads with complex task graphs. As a result, we introduce in this paper an effective work-stealing scheduler for execution of task dependency graphs. Our scheduler adopts a simple and efficient strategy to adapt the number of working threads to available task parallelism at any time during the graph execution. Our strategy is provably good in preventing resource underutilization and simultaneously minimizing resource waste when tasks are scarce. We have evaluated our scheduler on both micro-benchmarks and a real-world circuit timing analysis workload, and demonstrated promising results over existing methods in terms of runtime, energy efficiency, and throughput.

Rectangular grid graph (RGG) and diagonal grid graph (DGG) are induced subgraphs of a rectangular or diagonal grid, respectively. Their k-coloring problem has direct applications in printing contact/via layouts by multipatterning lithography (MPL). However, the problem in general is computationally difficult for k 2, while it remains an open question on grid graphs due to their regularity and sparsity. On the other hand, directed self-assembly (DSA) technique can work with MPL to optimize the graph by grouping neighboring vertices such that k can be reduced, but the problem of deploying the grouping for coloring is even more intractable. In this paper, we study both of the k-coloring problems, with and without DSA grouping, on RGG and DGG. Without grouping, a complete k-coloring analysis is conducted and particularly the NP-completeness of 3-coloring on a diagonal grid is proved. When considering grouping, we present a 3-coloring solution and prove the NP-completeness to solve the problem of k = 2.

Open source has started energizing both industrial and academic research and development in electronic design automation (EDA) systems. By moving to open source, we can speed up our effort and work with others who are working toward the same goals, while reducing costs and improving end products. However, building an open-source project is much more than placing the codebase on the web. In this paper, we will talk about essential building blocks to create an impactful open-source project, including source repository, project landing page, documentation, and continuous integration. We will also cover the use of web-based frameworks to design a showcase project to bring community's attention. We will then share our experience in developing an open-source timing analyzer (OpenTimer) and a parallel task programming library (Cpp-Taskflow), both of which are being used in many industrial and academic EDA research projects.

As the design complexities continue to grow, the need to efficiently analyze circuit timing with billions of transistors is quickly becoming the major bottleneck to the overall chip design flow. In this work we introduce a distributed timer that (1) has scalable performance, (2) can be seamless integrable to existing EDA applications, (3) enables transparent resource management, (4) has robust fault-tolerant control. We evaluate the distributed timer using a set of large industry benchmarks on a cluster with 24 nodes. The results show that the proposed timer achieves full accuracy over all designs with high performance and good scalability.

In this paper we introduce Cpp-Taskflow, a new C++ tasking library to help developers quickly write parallel programs using task dependency graphs. Cpp-Taskflow leverages the power of modern C++ and task-based approaches to enable efficient implementations of parallel decomposition strategies. Our programming model can quickly handle not only traditional loop-level parallelism, but also irregular patterns such as graph algorithms, incremental flows, and dynamic data structures. Compared with existing libraries, Cpp-Taskflow is more cost efficient in performance scaling and software integration. We have evaluated Cpp-Taskflow on both micro-benchmarks and real-world applications with million-scale tasking. In a machine learning example, Cpp-Taskflow achieved 1.5-2.7× less coding complexity and 14-38% speed-up over two industrial-strength libraries OpenMP Tasking and Intel Threading Building Blocks (TBB).

In this paper we present Cpp-Taskflow, a C++ parallel programming library that enables users to quickly develop parallel applications using the task dependency graph model. Developers formulate their application as a task dependency graph and Cpp-Taskflow will manage the task execution and concurrency control.The task graph model is expressive and composable. It can express both regular and irregular parallel patterns, and developers can quickly compose large programs from small parallel modules. Cpp-Taskflow has an intuitive and unified API set. Users only need to learn the APIs to build and dispatch a task graph and no complex parallel programming concept is required. We have conducted experiments using both micro-benchmarks and real-world applications and Cpp-Taskflow outperforms state-of-the-art parallel programming libraries in both runtime and coding effort. Cpp-Taskflow is open-source and has been used in both industry and academic projects. From our users' feedback, we believe Cpp-Taskflow can benefit the industry and research community greatly through its ease-of-programming and inspire new research directions in multimedia system/software design.

Recent years have seen rapid growth in data-driven distributed systems, such as Hadoop MapReduce, Spark, and Dryad. However, the counterparts for high-performance or compute-intensive applications including large-scale optimizations, modeling, and simulations are still nascent. In this paper, we introduce DtCraft, a modern C++ based distributed execution engine to streamline the development of high-performance parallel applications. Users need no understanding of distributed computing and can focus on high-level developments, leaving difficult details, such as concurrency controls, workload distribution, and fault tolerance handled by our system transparently. We have evaluated DtCraft on both micro-benchmarks and large-scale optimization problems, and shown the promising performance from single multicore machines to clusters of computers. In a particular semiconductor design problem, we achieved 30× speedup with 40 nodes and 15× less development efforts over hand-crafted implementation.

Rectangular and diagonal grid graphs are induced subgraphs of a rectangular or diagonal grid respectively. Their k-coloring problem has direct applications in printing contact/via layouts by multi-patterning lithography (MPL). However, the problem in general is computationally difficult for k>2, while it remains an open question on grid graphs due to their regularity and sparsity. In this paper, we conduct a complete analysis of the k-coloring problems on rectangular and diagonal grid graphs, and particularly the NP-completeness of 3-coloring on a diagonal grid graph is proved. In practice, we propose an exact 3-coloring algorithm. Experiments are conducted to verify its effectiveness and performance. Extensions and other results are also discussed.

Large-scale hierarchical and incremental timing analysis has driven the need for highly compressed timing macro-models. A small timing macro-model for accelerating hierarchical timing is desired because the size of incremental changes dramatically increases as the macro-models are widely used in the large design process. In fact, it takes days for an incremental timing analysis on millions of gates with thousands of incremental changes. To date, the timing macro-models generated by timing macro-modeling algorithms from all the previous works are not compact enough. In this work, we provide four essential techniques in our timing macro-modeling algorithm, which are able to generate highly compressed timing macro-models for hierarchical and incremental timing analysis. In addition, our timing macro-model maintain high accuracy and the efficiency in generating our macro-models. Our algorithm generates timing macro-models where the model sizes are 9% better in the number of nodes and 19% better in the number of edges than the original circuit. Our work outperforms the state of arts significantly in both model size and the runtime in macro-model usage.

This paper presents a generic approach of exploiting GPU parallelism to speed up the essential computations in VLSI nonlinear analytical placement. We consider the computation of wirelength and density which are widely used as cost and constraint in nonlinear analytical placement. For wirelength gradient computing, we utilize the sparse characteristic of circuit graph to transform the compute-intensive portions into sparse matrix multiplications, which effectively optimizes the memory access pattern and mitigates the imbalance workload. For density, we introduce a computation flattening technique to achieve load balancing among threads and a High-Precision representation is integrated into our approach to guarantee the reproducibility. We have evaluated our method on a set of contest benchmarks from industry. The experimental results demonstrate our GPU method achieves a better performance over both the CPU methods and the straightforward GPU implementation.

The ever-increasing design complexities have overwhelmed what is offered by existing EDA tools. As a result, the recent EDA industry is driving the need for distributed computing to leverage large-scale compute-intensive problems, in particular, power grid analysis. In this paper, we introduce a distributed power grid analysis framework based on the stream graph model. We show that the stream graph model has better programmability over the MPI and enables flexible domain decomposition without limited by hardware resource. In addition, we design an efficient scheduling policy for this particular workload to maximize the cluster utilization to improve the performance. The experimental results demonstrated the promising performance of our framework that scales from single multi-core machines to a distributed computer cluster.

In this paper we present DtCraft, a distributed execution engine that enables a new powerful programming model to streamline cluster computing. Applications are described in a set of data-parallel streams, leaving difficult execution details and concurrency controls handled by our system kernel transparently. Compared with existing systems, DtCraft is unique in (1) an efficient stream-oriented programming paradigm using modern C++17, (2) an in-context resource controller and task executor based on Linux container technology, and (3) ease of development from prototyping machines to production cloud environments. These capabilities power industry applications and create new research directions in machine learning, stream processing, and distributed multimedia systems.

The Internet of Things (IoT) and cloud computing rely on strong confidence in security of confidential or highly privacy sensitive data. Therefore, side-channel leakage is an important threat, but countermeasures require expert-level security knowledge for efficient application, limiting adoption. This work addresses this need by presenting the first High-Level Synthesis (HLS) flow with primary focus on side-channel leakage reduction. Minimal security annotation to the high-level C-code is sufficient to perform automatic analysis of security critical operations with corresponding insertion of countermeasures. Additionally, imbalanced branches are detected and corrected. For practicality, the flow can meet both resource and information leakage constraints. The presented flow is extensively evaluated on established HLS benchmarks and a general IoT benchmark. Under identical resource constraints, leakage is reduced between 32% and 72% compared to the reference. Under leakage target, the constraints are achieved with 31% to 81% less resource overhead.

The ever-increasing design complexity is driving the need of fast and accurate macro-modeling algorithms to accelerate the hierarchical timing. We introduce LibAbs, an effective macro-modeling algorithm that efficiently supports high accuracy, high compression rate, and multi-threading. LibAbs applies tree-based graph reduction techniques to reduce the model size with comparable accuracy values to the flat model under multi-threaded environment. LibAbs outperforms existing tools including top winners from TAU 2016 macro-modeling contest in terms of model size, accuracy, and runtime on industry benchmarks. The in-context usage of our abstracted model has also demonstrated promising performance for timing-driven optimizations in large hierarchical designs.

Recent years have seen rapid growth in data-driven distributed systems such as Hadoop MapReduce, Spark, and Dryad. However, the counterparts for high-performance or compute-intensive applications including large-scale optimizations, modeling, and simulations are still nascent. In this paper, we introduce DtCraft, a modern C+,+,17-based distributed execution engine that efficiently supports a new powerful programming model for building high-performance parallel applications. Users need no understanding of distributed computing and can focus on high-level developments, leaving difficult details such as concurrency controls, workload distribution, and fault tolerance handled by our system transparently. We have evaluated DtCraft on both micro-benchmarks and large-scale optimization problems, and shown promising performance on computer clusters. In a particular semicondictor design problem, we achieved 30 x speedup with 40 nodes and 15 × less development efforts over hand-crafted implementation.

Multiple patterning lithography has been widely adopted for today's circuit manufacturing. However, increasing the number of masks will make the manufacturing process more expensive. More importantly, towards 7 nm technology node, the accumulated overlay in multiple patterning will cause unacceptable edge placement error (EPE). Recently, directed self-assembly (DSA) has been shown to be an effective lithography technology that can pattern contact/via/cuts with high throughput and low cost. DSA is currently aiming at 7 nm technology, where the guiding template generation needs either double patterning EUV or multiple patterning DUV process. By incorporating DSA into the multiple patterning process, it is possible to reduce the number of masks and achieve a cost effective solution. In this paper, we study the decomposition problem for contact layer in row-based standard cell layout with DSA-MP complementary lithography. We explore several heuristic-based approaches, and propose an algorithm that decomposes a standard cell row optimally in polynomial-time. Our experiments show that our algorithm guarantees to find a minimum cost solution if one exists, while the heuristic cannot or only finds a sub-optimal solution. Our results show that the DSA-MP complementary approach is very promising for the future advanced nodes.

Given ever-increasing circuit complexities, recent trends are driving the requirement for distributed timing analysis (DTA) in electronic design automation (EDA) tools. However, DTA has received little research attention so far and remains a critical problem. In this paper, we introduce a DTA framework for large designs. Our framework supports (1) general design partitions in distributed file systems, (2) non-blocking IO with event-driven loop for effective communication and computation overlap, and (3) an efficient messaging interface between application and network layers. The effectiveness and scalability of our framework has been evaluated on large hierarchical industry designs over a cluster with hundreds of machines.

Emerging technologies such as the Internet of Things (IoT) heavily rely on hardware security for data and privacy protection. However, constantly increasing integration complexity requires automatic synthesis to maintain the pace of innovation. We introduce the first High-Level Synthesis (HLS) flow that produces a security enhanced hardware design to directly prevent Hardware Trojan Horse (HTH) injection by a malicious foundry. Through analysis of entropy loss and criticality decay, the presented algorithms implement highly efficient resource-targeted information dispersion to counter HTH insertion. The flow is evaluated on existing HLS benchmarks and a new IoT-specific benchmark and shows significant resource savings.

In this talk, we will give a brief survey of automatic floorplan design techniques in the early days of EDA. We will focus on presenting the pioneering contributions of Prof. Ralph Otten in the field.

The recent TAU computer-aided design (CAD) contest has aimed to seek novel ideas for accurate and fast common path pessimism removal (CPPR). Unnecessary pessimism forces the static timing analysis tool to report worse violation than the true timing properties owned by physical circuits, thereby misleading signoff timing into a lower clock frequency at which circuits can operate than actual silicon implementations. Therefore, we introduce in this paper UI-Timer 1.0, a powerful CPPR algorithm which achieves high accuracy and ultrafast runtime. Unlike existing approaches which are dominated by explicit path search, UI-Timer 1.0 proves that by implicit path representation the amount of search effort can be significantly reduced. Our timer is superior in both space and time saving, from which memory storage and important timing quantities are available in constant space and constant time per path during the search. Experimental results on industrial benchmarks released from TAU 2014 CAD contest have justified that UI-Timer 1.0 achieved the best result in terms of accuracy and runtime over existing CPPR algorithms.

Physically unclonable functions (PUFs) provide a device-unique challenge-response mapping and are employed for authentication and encryption purposes. Unpredictability and reliability are the core requirements of PUFs: unpredictability implies that an adversary cannot sufficiently predict future responses from previous observations. Reliability is important as it increases the reproducibility of PUF responses and hence allows validation of expected responses. However, advanced machine-learning algorithms have been shown to be a significant threat to the practical validity of PUFs, as they are able to accurately model PUF behavior. The most effective technique was shown to be the XOR-based combination of multiple PUFs, but as this approach drastically reduces reliability, it does not scale well against software-based machine-learning attacks. In this paper, we analyze threats to PUF security and propose PolyPUF, a scalable and secure architecture to introduce polymorphic PUF behavior. This architecture significantly increases model-building resistivity while maintaining reliability. An extensive experimental evaluation and comparison demonstrate that the PolyPUF architecture can secure various PUF configurations and is the only evaluated approach to withstand highly complex neural network machine-learning attacks. Furthermore, we show that PolyPUF consumes less energy and has less implementation overhead in comparison to lightweight reference architectures.

Electron beam lithography (EBL) is a very promising candidate for integrated circuit (IC) fabrication beyond the 10 nm technology node. To address its throughput issue, the Character Projection (CP) technique has been proposed, and its stencil planning can be optimized with aware of overlapping characters. However, the top level 2D stencil planning problem has been proved to be an NP-hard problem. As its most essential step, the 1D row ordering is believed hard as well, and no polynomial time optimal solution has been provided so far. In this paper, we propose a polynomial time optimal algorithm to solve the row ordering problem, which serves as the major subroutine for the entire stencil planning problem. Proof and experimental results are also provided to verify the correctness and efficiency of our algorithm.

Triple patterning lithography (TPL) has been recognized as one of the most promising techniques for 14/10nm technology node. In this paper, we applied triple patterning lithography on standard cell based designs, and proposed a novel algorithm to solve the problem. The algorithm guarantees to find a legal TPL decomposition with optimal number of stitches if one exists. A graph model is proposed to reduce the number of vertices in the solution graph, and a fast approach is developed to achieve simultaneous runtime and memory improvement. An efficient approach to limit the number of stitches is also proposed, which greatly reduces the total number of stitch candidates and enables an incremental implementation of the algorithm. Experimental results shows that the proposed algorithm is very efficient, which achieves 39.1% runtime improvement and 18.4% memory reduction compared with the state-of-the-art TPL algorithm on the same problem.

Directed Self-Assembly (DSA) is a promising technique for contacts/vias patterning in 7 nm technology nodes. In DSA process, groups of contact holes/vias are generated by the self-assembly process guided by the `guiding templates'. The guiding templates are patterned by conventional optical lithography process such as 193 nm immersion lithography. As a result, the patterning fidelity and variation in the template shapes is very likely to affect the final contact holes/vias. While feasible in principle, rigorous DSA process simulation is unacceptably slow for full chip verification in practice. This paper proposes a machine learning based verification that can predict the pitch size of the contact holes and the hole centers. Given a set of training data that consists of simulated template and contact hole patterns, our method is able to learn a highly accurate predictive model for pitch size and hole location. To build a statistical model for prediction, we utilize computer vision techniques to extract various geometric and image features. We conduct extensive experiments to explore the effectiveness of the proposed features, and compare several machine learning algorithms to achieve an effective and efficient prediction. The experimental results show that compared to the minutes or even hours of simulation time in rigorous methods, our best prediction model achieves very promising results (RMSE = 0.135 pitch grid) with less than one second of training and predicting runtime overhead.

Recently, block copolymer directed self-assembly (DSA) has demonstrated great advantages in patterning contacts/vias for the 7 nm technology node and beyond. The high throughput and low process cost of DSA makes it the most promising candidate in patterning tight pitched dense patterns for the next generation lithography. Since DSA is very sensitive to the shapes and distributions of the guiding templates, it is necessary to develop new EDA algorithms and tools to address the patterning rules and constraints of the process. This paper presents a set of DSA-aware optimization techniques targeting the most urgent problems for DSA technology, including layout optimization and template pattern verification.

We introduce in this paper, OpenTimer, an open-source timing analysis tool that efficiently supports (1) both block-based and path-based timing propagations, (2) common path pessimism removal (CPPR), and (3) incremental processing. OpenTimer works on industry formats (e.g., .v, .spef, .lib, .sdc) and is designed to be parallel and portable. To further facilitate integration between timing and other electronic design automation (EDA) applications such as timing-driven placement and routing, OpenTimer provides user-friendly application programming interface (API) for inactive analysis. Experimental results on industry benchmarks released from TAU 2015 timing analysis contest have demonstrated remarkable results achieved by OpenTimer, especially in its order-of-magnitude speedup over existing timers.

Path-based timing analysis (PBA) is a pivotal step to achieve accurate timing signoff. A core primitive extracts a large set of paths subject to path-specific or less-pessimistic timing update. However, this process in nature demands a very high computational complexity and thus has been a major bottleneck in accelerating timing closure. Therefore, we introduce in this paper a fast and scalable PBA framework with MapReduce - a recent programming paradigm invented by Google for big-data processing. Inspired by the spirit of MapReduce, we formulate our problem into tasks that are associated with keys and values and perform massively-parallel map and reduce operations on a distributed system. Experimental results demonstrated that our approach can easily analyze million nodes in a single minute.

In this talk, we will give a brief survey of circuit placement techniques in the early days of EDA. We will present the main contributions by Prof. Kurt Antreich on circuit placement, focusing on the classical works GORDIAN and DOMINO.

Physically Unclonable Functions (PUFs) are used to provide identification, authentication and secret key generation based on unique and unpredictable physical characteristics. Carbon Nanotube Field Effect Transistors (CNFETs) were shown to have excellent electrical and unique physical characteristics and are promising candidates to replace silicon transistors in future Very Large Scale Integration (VLSI) designs. We present Carbon Nanotube PUF (CNPUF), the first PUF design that takes advantage of unique CNFET characteristics. CNPUF achieves higher reliability against environmental variations and increased resistance against modeling attacks. Furthermore, CNPUF has a considerable power and energy reduction in comparison to previous ultra-low power PUF designs of 89.6% and 98%, respectively. Additionally, CNPUF allows power-security tradeoff.

IR-drop values of power grid can be reduced through inserting on-chip low-dropout voltage regulators (LDO). In this paper, we explore the optimization of LDOs to meet the IR-drop constraint, where the maximum IR-drop value is less than 10% of power supply. With Cholesky direct solver and SPICE, we propose a method to simulate power grid with LDOs. Based on the simulation method, we develop an efficient flow to optimize the number and locations of the LDOs. Effectiveness of the proposed method is verified by the experimental results. To the best of our knowledge, this is the first work optimizing the number and locations of LDOs to meet the IR-drop constraint.

Timing closure, which is to meet the design's timing constraints, is a key problem in the physical design flow. During the timing optimization process, buffers can be used to speedup the circuit or serve as delay elements. In this paper, we study the hold-violation removal problem for today's industrial designs. Discrete buffers, accurate timing models/analysis, and complex timing constraints make the problem difficult and time-consuming to solve. In this paper, we first present a linear programming-based methodology to model the setup and hold-time constraints. Then based on the solution to the linear programming, buffers are inserted as delay elements to solve hold violations. In the experiment, our approach is tested on industrial designs, then runs with the industrial optimization flow, and better results in terms of hold violations and runtime are reported.

Directed Self-Assembly (DSA) is a promising technique for contacts/vias patterning, where groups of contacts/vias are patterned by guiding templates. As the templates are patterned by traditional lithography, their shapes may vary due to the process variations, which will ultimately affect the contacts/vias even for the same type of template. Due to the complexity of the DSA process, rigorous process simulation is unacceptably slow for full chip verification. This paper formulate several critical problems in DSA verification, and proposes a design automation methodology that consists of a data preparation and a model learning stage. We present a novel DSA model with Point Correspondence and Segment Distance features for robust learning. Following the methodology, we propose an effective machine learning (ML) based method for DSA hotspot detection. The results of our initial experiments have already demonstrated the high-efficiency of our ML-based approach with over 85% detection accuracy. Compared to the minutes or even hours of simulation time in rigorous method, the methodology in this paper validates the research potential along this direction.

FinFET transistors have great advantages over traditional planar MOSFET transistors in high performance and low power applications. Major foundries are adopting the Fin-FET technology for CMOS semiconductor device fabrication in the 16 nm technology node and beyond. Edge device degradation is among the major challenges for the FinFET process. To avoid such degradation, dummy gates are needed on device edges, and the dummy gates have to be tied to power rails in order not to introduce unconnected parasitic transistors. This requires that each dummy gate must abut at least one source node after standard cell placement. If the drain nodes at two adjacent cell boundaries abut each other, additional source nodes must be inserted in between for dummy gate power tying, which costs more placement area. Usually there is some flexibility during detailed placement to horizontally flip the cells or switch the positions of adjacent cells, which has little impact on the global placement objectives, such as timing conditions and net congestion. This paper proposes a detailed placement optimization strategy for the standard cell based designs. By flipping a subset of cells in a standard cell row and switching pairs of adjacent cells, the number of drain to drain abutments between adjacent cell boundaries can be optimally minimized, which saves additional source node insertion and reduces the length of the standard cell row. In addition, the proposed graph model can be easily modified to consider more complicated design rules. The experimental results show that the optimization of 100k cells is completed within 0.1 second, verifying the efficiency of the proposed algorithm.

Common-path-pessimism removal (CPPR) is a pivotal step to achieve accurate timing signoff. Unnecessary pessimism might arise quality-of-result (QoR) concerns such as reporting worse violations than the true timing properties owned by the physical circuit. In other words, signoff timing report will conclude a lower clock frequency at which circuits can operate than actual silicon implementations. Therefore, we introduce in this paper a fast path-based timing analysis for CPPR. Unlike existing approaches which are dominated by explicit path search, we perform implicit path representation which yields significantly smaller search space and faster runtime. Specifically, our algorithm is superior in both space and time saving, from which the memory storage and important timing quantities are available in constant space and constant time per path during the search. Experimental results on industrial benchmarks released from TAU 2014 timing analysis contest have shown that our algorithm won the first place and achieved the best result in terms of accuracy and runtime over all participating teams.

The recent TAU computer-aided design (CAD) contest has aimed to seek novel ideas for accurate and fast clock network pessimism removal (CNPR). Unnecessary pessimism forces the static-timing analysis (STA) tool to report worse violation than the true timing properties owned by physical circuits, thereby misleading signoff timing into a lower clock frequency at which circuits can operate than actual silicon implementations. Therefore, we introduce in this paper UI-Timer, a powerful CNPR algorithm which achieves exact accuracy and ultra-fast runtime. Unlike existing approaches which are dominated by explicit path search, UI-Timer proves that by implicit path representation the amount of search effort can be significantly reduced. Our timer is superior in both space and time saving, from which memory storage and important timing quantities are available in constant space and constant time per path during the search. Experimental results on industrial benchmarks released from TAU 2014 CAD contest have justified that UI-Timer achieved the best result in terms of accuracy and runtime over all participating timers.

Triple patterning lithography (TPL) has been recognized as one of the most promising techniques for 14/10nm technology node. There are various concerns for TPL decompositions. For standard cell based designs, assigning the same pattern for the same type of cells is a desired property for TPL decomposition. It is more robust for process variations and gives the chip similar physical and electrical characteristics as well as more reliable and predictable performance. Assigning the same type of pattern for the same type of cell is called a constrained pattern assignment (CPA) problem. In this paper, we integrated the flow of detailed placement and TPL decompositions with CPA coloring constraints. We focused on refining a layout to make it CPA-friendly during the detailed placement stage while minimizing the area and HPWL (half perimeter wire length) overhead. A weighted partial MAX SAT approach is proposed which guarantees to obtain a CPA-friendly detailed placement result while minimizing the area overhead. An efficient graph model is also proposed to compute the locations of the cells with optimal HPWL. Our formulation is very efficient and achieves a 79.4% area overhead reduction compared with the approach of fixing cell colors beforehand. Better HPWL are also achieved consistently over all benchmarks.

Due to the absence of defect-free blanks in extreme ultraviolet (EUV) lithography, defect mitigation is necessary before mass production. One effective defect mitigation approach is to cover defects by device features, such that the defects will no longer be printable. Normally die size is much smaller than the exposure field on the blank, such that one blank can accommodate multiple copies of a die, each of which can be placed independently within the exposure field. For thorough utilization of blank area, the number of valid dies that are not impacted by any defects should be maximized. To do so, all relocation positions to place a single valid die on a defective blank must be determined first [1]. To the best of our knowledge, no existing work can find all relocation positions throughout the whole blank in a reasonable amount of time. In this paper, we develop an efficient algorithm to solve this problem. The time complexity of our algorithm is linear in the number of features in the die. Experimental results with full die layouts generated from a standard cell library validate the efficiency of our algorithm. Comparing to the algorithm in [2] which runs more than one week without termination, our algorithm only takes several hours to find all relocation positions for a die with millions of features.

Modern PCBs have to be routed manually since no EDA tools can successfully route these complex boards. An auto-router for PCBs would improve design productivity tremendously since each board takes about 2 months to route manually. This paper focuses on a major step in PCB routing called bus planning. In the bus planning problem, we need to simultaneously solve the bus decomposition, escape routing, layer assignment and global bus routing. This problem was partially addressed by Kong et al. in [3] where they only focused on the layer assignment and global bus routing, assuming bus decomposition and escape routing are given. In this paper, we present an ILP-based solution to the entire bus planning problem. We apply our bus planner to an industrial PCB (with over 7000 nets and 12 signal layers) which was previously successfully routed manually, and compare with a state-of-the-art industrial internal tool where the layer assignment and global bus routing are based on the algorithm in [3]. Our bus planner successfully routed 97.4% of all the nets. This is a huge improvement over the industrial tool which could only achieve 84.7% routing completion for this board.

Recently staggered pin arrays are introduced for modern designs with high pin density. Although some studies have been done on escape routing for hexagonal arrays, the hexagonal array is only a special kind of staggered pin array. There exist other kinds of staggered pin arrays in current industrial designs, and the existing works cannot be extended to solve them. In this paper, we study the escape routing problem on staggered pin arrays. Network flow models are proposed to correctly model the capacity constraints of staggered pin arrays. Our models are guaranteed to find an escape routing satisfying the capacity constraints if there exists one. The correctness of these models lead to an optimal algorithm.

Self-aligned double patterning (SADP) lithography is a leading technology for 10nm node Metal layer fabrication. In order to achieve successful decomposition, SADP-compliant design becomes a necessity. Spacer-Is-Dielectric (SID) is the most popular flavor of SADP with higher flexibility in design. This paper makes a careful study on the challenges for SID-compliant detailed routing and proposes a graph model to capture the decomposition violations and SID intrinsic residue issues. Then a negotiated congestion based scheme is adopted to solve the overall routing problem. The proposed SID-compliant detailed routing algorithm simultaneously assigns colors to the routed wires, which provides valuable information guiding SID decomposition. In addition, if one pin has multiple candidate locations, the optimal one will be automatically determined during detailed routing. The decomposability of the conflict-free routing layers produced by our detailed router is verified by a commercial SADP decomposition tool.

At the 10 nm technology node, the contact layers of integrated circuits (IC) designs are too dense to be printed by single exposure using 193 nm immersion (193i) lithography. Among all the emerging patterning approaches, block copolymer directed self-assembly (DSA) is a promising candidate with high throughput and low cost for sub-20 nm features. Traditionally, the study of DSA has focused on achieving periodic regular patterns over large area. Realizing that long range order is not needed for patterning irregularly distributed contact holes, we use topographical guiding templates to alter the natural symmetry of block copolymer and achieve controlled irregular DSA patterns. However, DSA patterning must satisfy the overlay accuracy requirements while the guiding templates also need to be printable by conventional lithography. This presents a unique opportunity of DSA patterning and layout design co-optimization for improving the manufacturability of DSA. This paper discusses the DSA-aware contact layer optimization problem for 10 nm 1D standard cell library. For the first time we propose a cost function for each DSA template based on its overlay accuracy performance. Then given a standard cell library, we simultaneously optimize the layouts of every cell, such that the contact layer of any cell in the library can be fully patterned by a set of guiding templates, and the total cost of the templates is minimal. This optimization problem is first proved to be NP-hard and formulated as a Weighted Partial Maximum Satisfiability (MAXSAT) problem, which can be optimally solved with a public SAT solver. Then we propose a bounded approximation algorithm that solves the problem much more efficiently. The experimental results demonstrate that our approach is remarkably promising in practice and validate the proposed optimization problem.

Triple patterning lithography (TPL) has been recognized as one of the most promising candidates for 14/10nm technology node. Apart from obtaining legal TPL decompositions, various concerns have been raised by the designers, among them consistently assigning the same pattern for the same type of standard cells and balancing the usage of the three masks are two most critical ones. In this paper, a hybrid approach (SAT followed by a sliding-window approach) is proposed targeting at these two problems. To assign the same pattern for the same type of standard cell, we pre-color the boundary polygons of each type of cell by solving a small SAT problem. Following that we propose a sliding-window based approach to compute a locally balanced decomposition. Our algorithm guarantees to find a feasible solution if one exists. Experimental results verify that the problem can be solved very efficiently with the proposed algorithm. Superior locally balanced decompositions are achieved compared with the previous approach in.

Aerial image simulation is a fundamental problem in advanced lithography for chip fabrication. Since it requires a huge number of mathematical computations, an efficient yet accurate implementation becomes a necessity. In the literature, GPU or FPGA has demonstrated its potential for accelerating aerial image simulation. However, the comparisons of GPU or FPGA to CPU were not done thoroughly. In particular, careful tunings for the CPU-based method were missing in the previous works, while the recent CPU architectures have significant modifications toward high performance computing capabilities. In this paper, we present and discuss several algorithms for the aerial image simulation on multi-core SIMD CPU. Our fastest method achieves up to 73X speedup over the baseline serial approach and outperforms the state-of-the-art GPU-based approach by up to 2X speedup on a single hex-core SIMD CPU. We show that the performance on the multi-core SIMD CPU is promising, and that careful CPU tunings are necessary in order to exploit its computing capabilities.

Self-aligned double patterning is one of the most promising double patterning techniques for sub-20nm nodes. As in any multiple patterning techniques, layout decomposition is the most important problem. In SADP decomposition, overlay is among the most primary concerns. Most of the existing works target at minimizing the overall overlay, while others totally forbid the overlay. On the other hand, most of the works either rely on exponential time methods, or apply heuristic that cannot guarantee to find a solution. In this paper, we consider the SADP decomposition problem in row-based standard cell layout, where the overlay violations are minimized. Although SADP decomposition has been shown to be NP-hard in general, we showed that it can be solved in polynomial time when the layout is row-based standard cells. We propose a polynomial time optimal algorithm that finds a decomposition with minimum overlay violations. The efficiency of our method is further demonstrated by the experimental results.

Double patterning lithography (DPL) technologies have become a must for today's sub-32 nm technology nodes. Currently, there are two leading DPL technologies: self-aligned double patterning (SADP) and litho-etch-litho-etch (LELE). Among them, SADP has the significant advantage over LELE in its ability to avoid overlay, making it the likely DPL candidate for the next technology node of 14 nm. In any DPL technology, layout decomposition is the key problem. While the layout decomposition problem for LELE has been well studied in the literature, only a few attempts have been made to address the SADP layout decomposition problem. In this paper, we present a polynomial time exact (optimal) algorithm to determine if a given layout has SADP decompositions that do not have any overlay at specified critical edges. The previous approaches tried to minimize the total overlay of a given layout, which may be a problematic objective. Furthermore, all previous exact algorithms were computationally expensive exponential time algorithms based on SAT or ILP. Other previous algorithms for the problem were heuristics without having any guarantee that an overlay-free solution can be found even if one exists.

Conventional CMOS devices are facing an increasing number of challenges as their feature sizes scale down. Graphene nanoribbon (GNR) based devices are shown to be a promising replacement of traditional CMOS at future technology nodes. However, all previous works on GNRs focus at the device level. In order to integrate these devices into electronic systems, routing becomes a key issue. In this article, the GNR routing problem is studied for the first time. We formulate the GNR routing problem as a minimum hybrid-cost shortest path problem on triangular mesh (“hybrid” means that we need to consider both the length and the bending of the routing path). We show that by graph expansion, this minimum hybrid-cost shortest path problem can be solved by applying the conventional shortest path algorithm on the expanded graph. Experimental results show that our GNR routing algorithm effectively handles the hybrid cost.

Since some of major IC industry participants are moving to the highly regular 1D gridded designs to enable scaling to sub-20nm nodes, how to manufacture the randomly distributed cuts with reasonable throughput and process variation becomes a big challenge. With the help of hybrid lithography, people can apply different types of processes for one single layer manufacturing such that the advantages from different technologies can be combined together to further benefit manufacturing. In this paper, targeting cut printing difficulties and hybrid lithography with electron beam (E-Beam) and 193 nm immersion (193i) processes, we propose a novel algorithm to optimally assign cuts to 193i or E-Beam processes with proper modifications on cut distribution, in order to maximize the overall throughput. To validate our method, we construct our algorithm based on the forbidden patterns obtained from the optical simulation; then we formulate the redistribution problem into a well defined ILP problem and finally call a reliable solver to solve the whole problem. Experimental results show that the throughput is dramatically improved by the cut redistribution. Besides that, for sparser layers, the EBL process can be totaly saved, which largely reduces the fabrication cost.

R-tree is an important spatial data structure used in EDA as well as other fields. Although there has been a huge literature of parallel R-tree query, as far as we know, our work is the first successful one to parallelize R-tree query on the GPU. We also propose the first R-tree construction method on the GPU. Unlike the other parallel construction methods, our method does not depend on a partition algorithm and guarantees the same quality as the sequential construction. Experiments show that more than 30× speedup on R-tree query and more than 20× speedup on R-tree construction are achieved.

Blank defect mitigation is a critical step for extreme ultraviolet (EUV) lithography. Targeting the defective blank, a layout relocation method, to shift and rotate the whole layout pattern to a proper position, has been proved to be an effective way to reduce defect impact. Yet, there is still no published work about how to find the best pattern location to minimize the impact from the buried defects with reasonable defect model and considerable process variation control. In this paper, we successfully present an algorithm that can optimally solve this pattern relocation problem. Experimental results validate our method, and the relocation results with full scale layouts generated from Nangate Open Cell Library has shown great advantages with competitive runtimes compared to the existing commercial tool.

As technology continues to scale to 14nm node, Double Patterning Lithography (DPL) is pushed to near its limit. Triple Patterning Lithography (TPL) is a considerable and natural extension along the paradigm of DPL. With an extra mask to accommodate the features, TPL can be used to eliminate the unresolvable conflicts and minimize the number of stitches, which are pervasive in DPL process, and thus smoothen the layout decomposition step. Considering TPL during routing stage explores a larger solution space and can further improve the layout decomposability. In this paper, we propose the first triple patterning aware detailed routing scheme, and compare its performance with the double patterning version in 14nm node. Experimental results show that, using TPL, the conflicts can be resolved much more easily and the stitches can be significantly reduced in contrast to DPL.

As minimum feature size keeps shrinking, and the next generation lithography (e.g, EUV) further delays, double patterning lithography (DPL) has been widely recognized as a feasible lithography solution in 20nm technology node. However, as technology continues to scale to 14/10nm, DPL begins to show its limitations and usually generates too many undesirable stitches. Triple patterning lithography (TPL) is a natural extension of DPL to conquer the difficulties and achieve a stitch-free layout decomposition. In this paper, we study the standard cell based row-structure layout decomposition problem in TPL. Although the general TPL layout decomposition problem is NP-hard, in this paper we will show that for standard cell based TPL layout decomposition problem, it is polynomial time solvable. We propose a polynomial time algorithm to solve the problem optimally and our approach has the capability to find all stitch-free decompositions. Color balancing is also considered to ensure a balanced triple patterning decomposition. To speed up the algorithm, we further propose a hierarchical algorithm for standard cell based layout, which can reduce the run time by 34.5% on average without sacrificing the optimality. We also extend our algorithm to allow stitches for complex circuit designs, and our algorithm guarantees to find optimal solutions with minimum number of stitches.

In this paper, we propose PGT_SOLVER - an effecient solver for power grid transient analysis. It is based on direct solver. The conductance matrix is SPD and is generated by modifying the matrix for DC analysis. Modified sparse vector technique is proposed to obtain solutions of interested nodes by performing partial forward and backward substitutions. Smart mapping technique is presented to obtain correct solutions without reordering the right-hand-side vector. Moreover, memorized supernode technique is utilized to speed up the substitution process. A effortless but effective parallel strategy with multiple threads is introduced to further accelerate the simulation. This software won the 1st place at "TAU 2012 Power Grid Simulation Contest". Experimental results on several industrial benchmarks show that this solver can get solutions fast without introducing any error. The memory consumption is also very affordable.

Due to the rapid advances of integrated circuit technology, the size of power distribution network (power grid) is becoming larger and larger. There are usually multi-million nodes on a power grid. Analyzing these huge power grids has become very expensive in terms of both time and memory. This paper presents an efficient parallel implementation of the Additive Schwarz Method (ASM) for IR-drop analysis of large-scale power grid. Based on distributed memory system, a new data storage method is proposed to overcome memory bottleneck of traditional methods. Techniques including overlapping in multiple layer and irregular power grid, via detection and grouping are utilized to accelerate the simulation. Moreover, a new communication strategy exhibiting minimum communication overhead is proposed. The proposed method is very accurate in the final solution, with the maximum error less than 0.1mv. Experimental results on industrial medium size benchmarks show that the proposed method achieves more than 110X speedup over a state-of-the-art direct LU solver. The proposed approach can easily solve very large-scale benchmarks, while LU solver fails to obtain the solution because of system memory limitation. It is the first time reported in literature that IR-drop analysis of power grid with over 190M nodes is successfully solved within 5 minutes.

Blank defect mitigation is crucial for extreme ultraviolet (EUV) lithography. One of the existing options is to relocate patterns to avoid defect impact. However, when the defect number increases, only pattern shift in X-Y directions becomes far from enough, requiring the reticle holder rotate a small angle to provide a third exploring dimension. This non-trivial extension from 2D to 3D exploration requests efficient runtime as well as enough accuracy to handle different defect sizes and locations on the different features. In this paper, we present the first work with a detailed algorithm to find the optimal shift and rotation for layout patterns on blanks. Compared to the straightforward method, which is to check every pair of defect and feature at every possible relocation position, our proposed algorithm can significantly reduce the runtime complexity to scale linearly with the size of the full solution space. The experimental results validate our method and show a largely increased success rate of defect mitigation by shift and rotation.

Simulated annealing was first introduced in 1983 as a generic stochastic algorithmic approach to solve optimization problems. Prof. C. L. Liu and his students H. W. Leong and D. F. Wong were among the earliest EDA researchers who applied simulated annealing to EDA. They solved a wide range of EDA problems with successes and reported their results in a series of papers at premier EDA conferences such DAC and ICCAD. Liu, Leong, and Wong later summarized their works in a research monograph entitled Simulated Annealing for VLSI Design, published in 1988 by Kluwer Academic Publishers. In the Preface of their book, the authors wrote "We hope that our experiences with the techniques we employed, some of which indeed bear certain similarities for different problems, could be useful as hints and guides for other researchers in applying the method to the solutions of other problems". Indeed, there were "similarities in techniques" among Liu's works that had influenced the design of simulated annealing EDA algorithms in the past 20 some years. To better understand Liu's contributions in simulated annealing, one should note that a typical simulated annealing algorithm uses a solution space and a cost function that come directly with the problem. Although computation time may be high, the algorithm is straightforward to design, making simulated annealing an attractive option for difficult problems where clever algorithms are hard to come by. On the contrary, Liu's simulated annealing algorithms have a completely different style: They resemble clever algorithms that attempt to solve difficult problems in polynomial time, and they often have a strong algorithmic flavor with a significant effort spent on optimizing the solution space and cost function. In this talk, we will discuss Prof. Liu's pioneering contributions in simulated annealing for EDA.

Double patterning lithography (DPL) technologies have become a must for today's sub-32nm technology nodes. There are two leading DPL technologies: self-aligned double patterning (SADP) and litho-etch-litho-etch (LELE). Among these two DPL technologies, SADP has the significant advantage over LELE in its ability to avoid overlay, making it the likely DPL candidate for the next technology node of 14nm. In any DPL technology, layout decomposition is the key problem. While the layout decomposition problem for LELE has been well-studied in the literature, only few attempts have been made to address the SADP layout decomposition problem. In this paper, we present the first polynomial time exact (optimal) algorithm to determine if a given layout has an overlay-free SADP decomposition. All previous exact algorithms were computationally expensive exponential time algorithms based on SAT or ILP. Other previous algorithms for the problem were heuristics without having any guarantee that an overlay-free solution can be found even if one exists.

In this paper, we introduce and study the rectangle escape problem (REP), which is motivated by printed circuit board (PCB) bus escape routing. Given a rectangular regionRand a setSof rectangles withinR, the REP is to choose a direction for each rectangle to escape to the boundary ofR, such that the resultant maximum density overRis minimized. We prove that the REP is NP-complete, and show that it can be formulated as an integer linear programming (ILP). A provably good approximation algorithm for the REP is developed by applying linear programming (LP) relaxation and a special rounding technique to the ILP. In addition, an iterative refinement procedure is proposed as a postprocessing step to further improve the results. Our approximation algorithm is also shown to work for more general versions of REP: weighted REP and simultaneous REP. Our approach is tested on a set of industrial PCB bus escape routing problems. Experimental results show that the optimal solution can be obtained within several seconds for each of the test cases.

Escape routing for packages and printed circuit boards (PCBs) has been studied extensively in the past. Network flow is pervasively used to model this problem. However, none of the previous works correctly models the diagonal capacity, which is essential for 45° routing in most packages and PCBs. As a result, existing algorithms may either produce routing solutions that violate the diagonal capacity or fail to output a legal routing even though there exists one. In this paper, we propose a new network flow model that guarantees the correctness when diagonal capacity is taken into consideration. This model leads to the first optimal algorithm for escape routing. We also extend our model to handle missing pins.

In this paper, we introduce and study the Rectangle Escape Problem (REP), which is motivated by PCB bus escape routing. Given a rectangular region R and a set S of rectangles within R, the REP is to choose a direction for each rectangle to escape to the boundary of R, such that the resultant maximum density over R is minimized. We prove that the REP is NP-Complete, and show that it can be formulated as an Integer Linear Program (ILP). A provably good approximation algorithm for the REP is developed by applying Linear Programming (LP) relaxation and a special rounding technique to the ILP. This approximation algorithm is also shown to work for a more general version of REP with weights (weighted REP). In addition, an iterative refinement procedure is proposed as a postprocessing step to further improve the results. Our approach is tested on a set of industrial PCB bus escape routing problems. Experimental results show that the optimal solution can be obtained within 3 seconds for each of the test cases.

Conventional CMOS devices are facing an increasing number of challenges as their feature sizes scale down. Graphene nanoribbon (GNR) based devices are shown to be a promising replacement of traditional CMOS at future technology nodes. However, all previous works on GNRs focus at the device level. In order to integrate these devices into electronic systems, routing becomes a key issue. In this paper, the GNR routing problem is studied for the first time. We formulate the GNR routing problem as a minimum hybrid-cost shortest path problem on triangular mesh (“hybrid” means that we need to consider both the length and the bending of the routing path). In order to model this hybrid-cost problem, we apply graph expansion and introduce a shortest red-black path problem on the expanded graph. We then propose an algorithm that solves the shortest red-black path problem optimally. This algorithm is then used in a negotiated congestion based routing scheme. Experimental results show that our GNR routing algorithm effectively handles the hybrid cost.

Double patterning lithography (DPL) is the enabling technology for printing in sub-32nm nodes. In the EDA literature, researchers have been focusing on double-exposure double-patterning (DEDP) DPL for printing arbitrary 2D features where the layout decomposition problem for double exposure is an interesting graph coloring problem. But due to overlay errors, it is very difficult for DEDP to print even 1D features. A more promising DPL technology is self-aligned double patterning (SADP) for 1D design. SADP first prints dense lines and then trims away the portions not on the design by a cut mask. The complexity of cut mask is very high, adding to the skyrocketing manufacturing cost. In this paper we present a mask cost reduction method with circuit performance consideration for SADP. This is the first paper to focus on the mask cost reduction issue for SADP from a design perspective. We simplify the polygons on the cut mask, by formulating the problem as a constrained shortest path problem. Experimental results show that with a set of layouts in 28nm technology, we can largely reduce the complexity of cut polygons, with little impact on performance.

Bus escape routing is a critical problem in modern PCB design. Due to the huge pin count and high density of the pin array, it usually requires multiple layers to route the buses without any conflict. How to assign the escape routing of buses to different layers becomes an important issue. In addition, some buses are required to be assigned on consecutive layers, which adds more difficulties to the layer assignment problem. In this paper, we propose a branch-and-bound based algorithm that optimally solves the layer assignment problem of bus escape routing. Our algorithm guarantees to produce a feasible layer assignment of the buses with a minimum number of layers. We applied our algorithm on industrial data and the experimental results validate our approach.

Self-aligned double patterning (SADP) lithography is a promising technology which can reduce the overlay and print 2D features for sub-32nm process. Yet, how to decompose a layout to minimize the overlay and perform hot spot detection is still an open problem. In this paper, we present an algorithm that can optimally solve the SADP decomposition problem. For a decomposable layout, our algorithm guarantees to find a decomposition solution that minimizes overlay. For a non-decomposable layout our algorithm guarantees to find all hot spots. Experimental results validate our method, and decomposition results for Nangate Open Cell Library and larger testcases are also provided with competitive runtimes.

Aerial image simulation is a fundamental problem for modern VLSI design. It requires a huge amount of numerical computation. The recent advancement of general purpose GPU computing provides an excellent opportunity to parallelize the aerial image simulation and achieve great speedup. In this paper, we present and discuss two GPU-based aerial image simulation algorithms. We show through experiments that the fastest algorithm we propose can achieve 50X to 60X speedup over the CPU based serial algorithm. The error of our approach is shown to be insignificant.

With the thermal effect, improper analog placements may degrade circuit performance because the thermal impact from power devices can affect electrical characteristics of the thermally-sensitive devices. There is not much previous work that considers the desired placement configuration between power and thermally-sensitive devices for a better thermal profile to reduce the thermally-induced mismatches. This paper first introduces the properties of a desired thermal profile for better thermal matching of the matched devices. It then presents a thermal-driven analog placement methodology to achieve the desired thermal profile and to consider the best device matching under the thermal profile while satisfying the symmetry and the common-centroid constraints. Experimental results based on real analog circuits show that the proposed approach can achieve the best analog circuit performance/accuracy with the least impact due to the thermal gradient, among existing works.

Simultaneous escape routing on dense circuit boards is a very challenging task and a great amount of manual effort is still needed in order to achieve high routability. In this paper, we present a new simultaneous escape routing algorithm which is based upon a novel boundary routing approach. Our algorithm can solve complicated escape problems in a very short time. For a set of industrial escape problems, our algorithm successfully solved all of them while Cadence Allegro PCB router was only able to complete the routing of half of the problems. In addition, we propose a clustering strategy targeting at large escape routing problems. Experimental results show that this clustering strategy can significantly cut down the runtime of our router when solving large problems.

Dynamic power consumption in CMOS circuits is usually estimated based on the number of signal transitions. However, when considering glitches, this is not accurate because narrow glitches consume less power than wide glitches. Glitch width and transition density modeling is further complicated by the effect of process variation. This paper presents a fast and accurate dynamic power estimation method that considers the detailed effect of process variation. First, we extend the probabilistic modeling approach to handle timing variations. Then the power consumption of a logic gate is computed based on the transition waveforms of its inputs. Both mean values and standard deviations of the dynamic power are estimated with high confidence based on accurate device characterization data. Compared with SPICE-based Monte Carlo simulations for small circuits, our power estimator reports power results within 3% error for the mean and 5% error for the standard deviation with six orders of magnitude speedup. For medium and large benchmarks, it is impossible to run Monte Carlo simulations with enough samples due to very long runtime, while our estimator can finish within minutes.

In PCB designs, pin positions greatly affect routability of the design. State-of-the-art pin assignment algorithms are guided by simple (heuristic) metrics to estimate routability and thus have no guarantee to obtain a routable solution. In this paper, we present a novel approach to obtain a pin assignment solution that guarantees routability. We show that the problem of simultaneous pin assignment and escape routing can be solved optimally in polynomial time. We then focus on the pin assignment and escape routing for the terminals in a bus, and present algorithmic enhancements as well as discuss the tradeoffs between single-layer and multi-layer implementations. We tested our approach on a state-of-the-art industrial board with 80 buses (over 7000 nets). The pin assignment and escape routing solutions for all the 80 buses are successfully obtainted in less than 5 minutes of CPU time.

Before VLSI design starts, it is strategically important to do product planning for targeted market segments that need specific applications, and to optimally reuse at different levels to save design and silicon costs with shorter time-to-market schedule. Conventional ASIC or SoC design floorplan usually targets for one single product; and, high efforts in re-floorplan and re-convergence for different products are still required if there is no pre-design stage multi-product planning. Therefore, the problem of designing floorplans at product or market planning stage that simultaneously optimizes multiple products, or Multi-product Floorplanning, is introduced. To the best of our knowledge, this is the first work in literature that addresses this newly emerged and financially important problem. We start with the necessary number of basic functional blocks to accommodate all the products, and pack them using a simulated annealing (SA) based floorplanner that can easily incorporate other costs (e.g., product finance weights). Given a candidate floorplan, we provide both an O(n3) exact algorithm and a O(n) greedy heuristic to identify the Minimum Feasible Region for each product, where n is the number of basic blocks in this floorplan. These identification procedures are integrated into the SA framework to generate a floorplan that favors the configurable multi-product design. The effectiveness of our approach is validated by promising results on several data sets derived from industrial test cases.

When VLSI technology scales down to sub-40nm process node, systematic variation introduced by the lithography is a persistent challenge to the manufacturability. The limitation of the resolution enhancement technologies (RETs) forces people to adopt a regular cell design methodology. In this paper, targeted on 1D cell design, we use simulation data to analyze the relationship between the line-end gap distribution and printability. Based on the gap distribution preferences, an optimal algorithm is provided to efficiently extend the line ends and insert dummies, which will significantly improve the gap distribution and help printability. Experimental results on 45nm and 32nm processes show that significant improvement can be obtained on edge placement error (EPE).

The maximum disjoint subset (MDS) of rectangles is a subset of non-overlapping rectangles with the maximum total weight. The problem of finding the MDS of general rectangles has been proven to be NP-complete in [6]. In this paper, we focus on the problem of finding the MDS of boundary rectangles, which is an open problem and is closely related to some difficult problems in PCB routing. We propose a polynomial time algorithm to optimally solve the MDS problem of boundary rectangles. Then we show that this algorithm can be applied to find the optimal solution of the bus escape routing problem.

Breadth-first search (BFS) has wide applications in electronic design automation (EDA) as well as in other fields. Researchers have tried to accelerate BFS on the GPU, but the two published works are both asymptotically slower than the fastest CPU implementation. In this paper, we present a new GPU implementation of BFS that uses a hierarchical queue management technique and a three-layer kernel arrangement strategy. It guarantees the same computational complexity as the fastest sequential version and can achieve up to 10 times speedup.

The increasing complexity of electronic systems has made PCB layout a difficult problem. A large amount of research efforts are dedicated to the study of this problem. In this paper, we provide an overview of recent research results on the PCB layout problem. We focus on the escape routing problem and the length-matching routing problem, which are the two most important problems in PCB layout. Other relevant works are also briefly introduced.

As an important step in PCB design, the escape routing problem has been extensively studied in literature. However, few studies have been done on the escape routing of differential pairs. In this paper, we study the differential pair escape routing problem and propose two algorithms. The first one computes the optimal routing for a single differential pair while the second one is able to simultaneously route multiple differential pairs considering both routability and wire length. We then propose a two-stage routing scheme based on the two algorithms. Experimental results show that our routing scheme efficiently and effectively solves the differential pair escape routing test cases we obtained from industry.

As advances in process technology continue to scale down transistors, low power design is becoming more critical. Clock gating is a dynamic power saving technique that can freeze some flip-flops and prevent portion of the circuit from unneeded switching. In this paper, we consider fine-grained clock gating through pipelining, in which control signals from one pipeline stage are used to freeze some logic in the next pipeline stage. We present a novel BDD-based decomposition algorithm to restructure the circuit and expose possible control signals that would maximize power saving. We then use ILP formulation to select the optimal set of control signals for the circuit. We show that the constraint matrix is totally unimodular, and solve this selection problem optimally using linear programming. Comparing to a previous work, we get similar and 9% better dynamic power saving for small and medium circuits, respectively. For the largest MCNC circuits, which the previous technique cannot handle, we get an average of 19% dynamic power saving with 9.3% area overhead comparing to the original, non-restructured circuits.

Simultaneous escape routing on dense circuit boards is a very challenging task and great amount of manual effort is still needed in order to achieve high routability. In this paper, we present a new simultaneous escape routing algorithm which is based upon a novel boundary routing approach. Our algorithm can solve complicated escape problems in very short time. For a set of industrial escape problems, our algorithm successfully solved all of them while Cadence Allegro PCB router was only able to complete the routing of half of the problems.

This paper presents a novel approach to reduce dynamic power in field-programmable gate arrays (FPGAs) by reducing glitches during routing. It finds alternative routes for early-arriving signals so that signal arrival times at look-up tables are aligned. We developed an efficient algorithm to find routes with target delays and then built a glitch-aware router aiming at reducing dynamic power. To the best of our knowledge, this is the first glitch-aware routing algorithm for FPGAs. Experiments show that an average of 27% reduction in glitch power is achieved, which translates into an 11% reduction in dynamic power, compared to the glitch-unaware versatile place and route's router.

Routing for high-speed boards is largely a time-consuming manual task today. The ordered escape routing problem is one of the key problems in board-level routing, and Boolean satisfiability (SAT) based approach [1] is the only solution to this problem so far. In this paper, we first solve the major deficiency of the original SAT formulation so that the escape problem is completely resolved. Then we propose two techniques to extend SAT approach for large-scale problems. Experimental results on industrial benchmarks show that our methods perform well in terms of both speed and routability.

In this paper, we present a novel flip-chip routing algorithm for package-board co-design. Unlike the previous works that can consider only either free- or pre-assignment routing, our router is the first work in the literature that can handle both the free-and pre-assignment routing. Based on the computational geometry techniques (e.g., the Delaunay triangulation and the Voronoi diagram), the router applies a unified network-flow formulation to perform congestion estimation for the pre-assignment routing. According to the congestion map, the network-flow formulation can also consider the free-assignment nets during the routing for the pre-assignment ones. Then, the router modifies the network-flow formulation to optimally assign and route the free-assignment nets, considering the routed pre-assignment nets. With the package and board co-design flow, we can achieve 100% routing completion. Experimental results based on industry designs demonstrate the high-quality of our algorithm.

Since no commercial PCB routing tools can solve the routing problem for today's complex PCBs, these circuit boards have to be routed manually, taking about 2 months of time per board. Bus planning is one of the most time-consuming steps of PCB routing. It consists of assigning buses to multiple layers of the PCB and routing them in a planar fashion on each layer. Routing congestion between on-board components and the min-max length bounds of the buses must also be considered during routing. In this paper, we present the first automatic bus planner. We tested our system on a state-of-the-art industrial circuit board with over 7000 nets and 12 signal layers. All the nets on this board were already manually routed. Our bus planner is able to achieve 100% routing completion using the layer assignment extracted from manual design. For simultaneous layer assignment and bus routing, we are able to successfully route 98.5% of the nets. The remaining 1.5% can be routed either manually or by using vias. The runtime of our bus planner is less than 3 hours on a 3 Ghz workstation.

With the thermal effect, improper analog placements may degrade circuit performance because the thermal impact from power devices can affect electrical characteristics of the thermally-sensitive devices. There is not much previous work that considers the desired placement configuration between power and thermally-sensitive devices for a better thermal profile to reduce the thermally-induced mismatches. In this paper, we first introduce the properties of a desired thermal profile for better thermal matching of the matched devices. We then propose a thermal-driven analog placement methodology to achieve the desired thermal profile and to consider the best device matching under the thermal profile while satisfying the symmetry and the common-centroid constraints. Experimental results based on real analog circuits show that our approach can achieve the best analog circuit performance/accuracy with the least impact due to the thermal gradient, among existing works.

Escape routing for packages and PCBs has been studied extensively in the past. Network flow is pervasively used to model this problem. However, none of the previous works correctly models the diagonal capacity, which is essential for 45° routing in most packages and PCBs. As a result, existing algorithms may either produce routing solutions that violate the diagonal capacity or fail to output a legal routing even though there exists one. In this paper, we propose a new network flow model that guarantees the correctness when diagonal capacity is taken into consideration. This model leads to the first optimal algorithm for escape routing. We also extend our model to handle missing pins.

Escape routing is a critical problem in PCB design. In IC-CAD'07, a layer assignment algorithm was proposed for escape routing of buses. The algorithm is optimal for single layer design in the sense that it determines if a set of buses can all be escaped on one layer. If they cannot, the algorithm is able to select a maximum subset of the buses that can be escaped on one layer. This, in turn, leads to a heuristic for the layer assignment problem with multiple layers, which is to repeatedly assign a maximum subset of the unassigned buses to a new layer. In this work, we present an algorithm that solves the multi-layer layer assignment problem optimally. Our algorithm guarantees to produce a layer assignment with minimum number of layers. We applied our algorithm on industrial data and obtained encouraging results.

Glitches (spurious transitions) are common in electronic circuits. In this paper we present a novel approach to reduce dynamic power in FPGAs by reducing glitches during the routing step. This approach involves finding alternative routes for early-arriving signals, so that signal arrival times at LUTs are aligned and no glitches are generated. This approach does not require additional circuitry to balance signals as done in previous work, but uses the available programmable routing resources instead. We develop an efficient algorithm to find routes with target delays. Based on this algorithm, we then build a glitch-aware router, named GlitchReroute, aiming at reducing dynamic power. To the best of our knowledge, this is the first glitch-aware routing algorithm for FPGAs. Experiments show that an average of 23% reduction in glitch power is achieved, which translates into a 9.8% reduction in dynamic power, compared to the glitch-unaware VPR router.

Wire shaping for delay/power minimization has been extensively studied. Due to the perceived high design and manufacturing costs for using non-uniform wire shapes, wire shaping is generally considered to be impractical. In this paper, we present a practical wire shaping methodology. Non-uniform wire shapes are directly implemented on silicon wafer instead of in GDSII during design. We present novel enhancements to existing OPC technology to accurately print non-uniform wire shapes. Experimental results show that the post-OPC mask complexities of uniform wire and non-uniform wire are comparable. With minimal impact on the design and manufacturing flows and minimal additional design and manufacturing costs, we demonstrate that wire shaping can help to obtain substantial reduction of interconnect dynamic power without affecting timing closure. Our wire shaping methodology is an excellent example of Manufacturing for Design.

Global routing is an important step in the physical design process. In this paper, we propose a new global routing algorithm Archer, which resolves some of the most common problems with the state-of-the-art global routers. It is known that concurrent global routing algorithms are typically too expensive to be applied on today's large designs, which may contain up to a million nets. On the other hand, iterative rip-up and reroute (RNR)-based algorithms are susceptible to getting stuck in local optimal solutions. In this paper, we propose an RNR-based global routing algorithm that guides the routing iterations out of local optima through effective usage of congestion histories. We also focus on the problem of how to enable a smooth tradeoff between seemingly conflicting objectives of overflow and wirelength minimization. Furthermore, we propose a Lagrangian relaxation-based bounded-length min-cost topology improvement algorithm that enables Steiner trees to change dynamically for the purpose of congestion optimization. Our experiments on public benchmarks show the effectiveness of Archer compared to other state-of-the-art global routers.

Design for low power has become a key requirement in today's System-on-a-Chip design, particularly for mobile applications. Multi-Vdd (MSV) is an effective method to reduce both leakage and dynamic powers. In a MSV design, cells of different supply voltages are often grouped into a small number of voltage islands, in order to avoid complex power-supply system and excessive amount of level shifters. In 2005, Wuetalproposed an elegant algorithm for voltage-island grouping based on the physical proximity of the critical cells in a postplacement voltage assignment and, in 2006, proposed an efficient algorithm for voltage assignment which not only meets timing but also forms good proximity of the critical cells. However, due to insufficient slack, a few isolated critical cells (calledoutliers) may still exist in the resulting voltage assignment, causing disproportionately expensive penalty to the final voltage-island grouping. In this paper, we propose a novel approach to improve the voltage assignment by automatic outlier detection followed by incremental placement. The outlier detection is based on a modified algorithm for the facility-location problem and proper parameter setting. We also propose a novel partial-sort technique which speeds up this algorithm significantly (up to 3times in our experiments). The incremental placement is guided by setting proper constraints on the paths containing the detected outliers, such that the outliers can be eliminated later. Our experiments on industry designs show that our algorithm leads to 12%-54% improvement in the final voltage-island grouping, with quick turn-around time.

Length-constrained routing is a very important issue for printed circuit board (PCB) routing. Previous length-constrained routers all have assumptions on the routing topology, whereas practical designs may be free of any topological constraint. In this paper, we propose a routing scheme that deals with general topology. Unlike previous works, our approach does not impose any restriction on the routing topology. Moreover, our routing scheme is gridless. Its performance does not depend on the routing grid size of the input while the routers in the papers of Ozdal and Wong and Kubo do. This is a big advantage because modern PCB routing configurations usually imply huge routing grids. The novelty of this work is that we view the length-constrained routing problem as an area assignment problem and use a placement structure, which is the bounded-sliceline grid, to help transform the area assignment problem into a mathematical programming problem. We then use an iterative approach to solve this mathematical programming problem. Experimental results show that our routing scheme can handle practical designs that previous routers cannot handle. For designs that they could handle, our router runs much faster. For example, in one of our data, we obtain the result in 88 s while the Lagrangian relaxation based router by Ozdal and Wong takes more than one day.

Previous works on PCB bus routing assume matched pin ordering on both sides. But in practice, the pin ordering might be mismatched and the nets become twisted. In this article, we propose a preprocessing step to untangle such twisted nets. We also introduce a practical routing style, which we call single-detour routing , to simplify the untangling problem. We then present a necessary and sufficient condition for the existence of single-detour routing solutions. Furthermore, we present a dynamic-programming-based algorithm to solve the single-detour untangling problem with consideration of wire capacity between adjacent pins. Our algorithm produces an optimal single-detour routing solution that rematches the pin ordering. By integrating our algorithm into the bus router in a previous length-matching router, we show that many routing problems that cannot be solved previously can now be solved with insignificant increase in runtime.

Routing for high-speed boards is largely a time-consuming manual task today. In this work we consider the ordered escape routing problem which is a key problem in board-level routing. All existing approaches to this problem cannot guarantee to find a routing solution even if one exists. We present an algorithm to exactly solve this problem based on Boolean satisfiability. Experimental results on escape routing problems from industry show that our algorithm performs well.

Application-Specific Instruction-set Processors (ASIP) can improve execution speed by using custom instructions. Several ASIP design automation flows have been proposed recently. In this paper, we investigate two techniques to improve these flows, so that ASIP can be efficiently applied to simple computer architectures in embedded applications. Firstly, we efficiently generate custom instructions with multi-cycle IO (which allows multi-outputs), thus removing the constraint imposed by the ports of the register file. Secondly, we allow identical portions of different custom instructions to be shared, thus allowing more custom instructions under the same area constraint. To handle the greatly increased exploration space, we propose several heuristics to keep the problem tractable. Experimental results show that we can achieve 3x speedup in some cases

Length-matching routing is a very important issue for PCB routing. Previous length-matching routers [1]–[3] all have assumptions on the routing topology whereas practical designs may be free of any topological constraint. In this paper, we propose a router that deals with general topology. Unlike previous routers, our router does not impose any restriction on the routing topology. Moreover, our router is gridless. Its performance does not depend on the routing grid size of the input while routers in [1]–[3] do. This is a big advantage because modern PCB routing configurations usually imply huge routing grids. The novelty of this work is that we view the lengthmatching routing problem as an area assignment problem and use a placement structure, Bounded-Sliceline Grid (BSG) [4], to help solving the problem. Experimental results show that our router can handle practical designs that previous routers can’t handle. For designs that they could handle, our router runs much faster. For example, in one of our data, we obtain the result in 88 seconds while the router in [3] takes more than one day.

In this paper, we target field-programmable gate array (FPGA) performance optimization using a novel binary decision diagram (BDD)-based synthesis paradigm. Most previous works have focused on BDD size reduction during logic synthesis. In this paper, we concentrate on delay reduction and conclude that there is a large optimization margin through BDD synthesis for FPGA performance optimization. Our contributions are threefold: 1) we propose a gain-based clustering and partial collapsing algorithm to prepare the initial design for BDD synthesis for better delay; 2) we use a technique called linear expansion for BDD decomposition, which, in turn, enables a dynamic programming algorithm to efficiently search through the optimization space for the BDD of each node in the clustered circuit; and 3) we consider special decomposition scenarios coupled with linear expansion for further improvement on the quality of results. Experimental results show that we can achieve a 30% performance gain with a 22% area overhead on the average compared to a previous state-of-the-art BDD-based FPGA synthesis tool, namely, BDS-pga. Compared to DAOmap, we can achieve a 33% performance gain with only an 8% area overhead. Compared to the ABC mapper, we can achieve a 20% performance gain with only an 8% area overhead.

Shrinking transistor sizes, increasing circuit complexities, and high clock frequencies bring new board-routing challenges that cannot be handled effectively by traditional routing algorithms. Many high-end designs in the industry today require manual routing efforts, which increases the design-cycle times considerably. In this paper, we propose an escape-routing algorithm to route nets within multiple dense components simultaneously so that the number of crossings in the intermediate area is minimized. We also show how to handle high-speed-design constraints within the framework of this algorithm. Experimental comparisons with a recently proposed algorithm show that our algorithm reduces the via requirements of industrial test cases on average by 39%.

As the device shapes keep shrinking, the designs are more sensitive to manufacturing processes. In order to improve performance predictability and yield, mask-layout uniformity/evenness is highly desired, and it is usually measured by the feature densities within defined feasible ranges determined by the manufacturing-process design rules. To address the density-control problem, one fundamental problem is how to calculate density accurately and efficiently. In this paper, we propose a fast exact algorithm to identify the maximum/minimum density for a given layout. Compared with the existing exact algorithms, our algorithm reduces the running time from days/long hours to a few minutes/seconds. Moreover, it is even faster than the existing approximate algorithms in the literature.

In modern very large scale integration manufacturing processes, dummy fills are widely used to adjust local metal density in order to improve layout uniformity and yield optimization. However, the introduction of a large amount of dummy features also affects wire electrical properties. In this paper, we propose the first coupling-constrained dummy-fill analysis algorithm which identifies feasible locations for dummy fills such that the fill-induced coupling capacitance can be bounded within the given coupling threshold of each wire segment. A speedup approach is presented based on the cache concept. The algorithm also makes efforts to maximize ground dummy fills, which are more robust and predictable. The output of the algorithm can be treated as the upper bound for dummy-fill insertion, and it can be easily adopted in density models to guide dummy-fill insertion without disturbing the existing design.

The Input vector control (IVC) technique is based on the observation that the leakage current in a CMOS logic gate depends on gate input state, and a good input vector is able to minimize leakage when the circuit is in sleep mode. The gate replacement technique is a very effective method to further reduce the leakage current. In this article, we propose a fast heuristic algorithm to find a low-leakage input vector with simultaneous gate replacement. Results on MCNC91 benchmark circuits show that our algorithm produces 14% better leakage current reduction with several orders of magnitude speedup in runtime for large circuits compared to the previous state-of-the-art algorithm. In particular, the average runtime for the ten largest combinational circuits has been dramatically reduced from 1879 seconds to 0.34 seconds.

As the circuit densities and transistor counts are increasing, the package routing problem is becoming more and more challenging. In this article, we study an important routing problem encountered in typical high-end MCM designs: routing within dense pin clusters. Pin clusters are often formed by pins that belong to the same functional unit or the same data bus, and can become bottlenecks in terms of overall routability. Typically, these clusters have irregular shapes, which can be approximated with rectilinear convex boundaries. Since such boundaries have often irregular shapes, a traditional escape routing algorithm may give unroutable solutions. In this article, we study how the positions of escape terminals on a convex boundary affect the overall routability. For this purpose, we propose a set of necessary and sufficient conditions to model routability outside a rectilinear convex boundary. Given an escape routing solution, we propose an optimal algorithm to select the maximal subset of nets that are routable outside the boundary. After that, we focus on an integrated approach to consider routability constraints (outside the boundary) during the actual escape routing algorithm. Here, we propose an optimal algorithm to find the best escape routing solution that satisfies all routability constraints. Our experiments demonstrate that we can reduce the number of layers by 17% on the average, by using this integrated methodology.

Multi-Vdd is an effective method to reduce both leakage and dynamic power. A key challenge in a multi-Vdd design is to control the complexity of the power-supply system and limit the demand for level shifters. This can be tackled by grouping cells of different supply voltages into a small number of voltage islands. Recently, an elegant algorithm was proposed for generating voltage islands that balance the power-versus-design-cost tradeoff under performance requirement, according to the placement proximity of the critical cells. One prerequisite of this algorithm is an initial voltage assignment at the standard-cell level that meets timing. In this article, we present a novel method to produce quality voltage assignment which not only meets timing but also forms good proximity of the critical cells to provide a smooth input to the aforementioned voltage island generation. Our algorithm is based on effective delay budgeting and efficient computation of physical proximity by Voronoi diagram. Our extensive experiments on real industrial designs show that our algorithm leads to 25%--75% improvement in the voltage island generation in terms of the number of voltage islands generated, with computation time only linear to design size.

As integrated circuits manufacturing technology is advancing into 65nm and 45nm nodes, extensive resolution enhancement techniques (RETs) are needed to correctly manufacture a chip design. The widely used RET called off-axis illumination (OAI) introduces forbidden pitches which lead to very complex design rules. It has been observed that imposing uniformity on layout designs can substantially improve printability under OAI. For metal layers, uniformity can be achieved simply by inserting dummy metal wire segments at all free spaces. Simulation results indeed show significant improvement in printability with such a dummy metal insertion approach. To minimize mask cost, it is advantageous to use dummy metal segments that are of the same size as regular metal wires due to their simple geometry. But these dummy wires are printable and hence increase coupling capacitances and potentially affect yield. The alternative is to use a set of parallel sub-resolution thin wires (which is not printed) to replace a printable dummy wire segment. These invisible dummy metal segments do not increase coupling capacitances but bring a higher lithography cost, which includes mask cost and RET/process expense. This paper presents a strategy for dummy metal insertion that can optimally trade off lithography cost and coupling capacitance. In particular, we present an optimal algorithm that can minimize lithography cost subject to any given coupling capacitance bound. Moreover, this dummy metal insertion achieves a highly uniform density because of the locality of coupling capacitance, which automatically ameliorates chemical mechanical polish (CMP) problem.

Model based optical proximity correction (OPC) has become necessary at 90nm technology node and beyond. Cell-wise OPC is an attractive technique to reduce the mask data size as well as the prohibitive runtime of full-chip OPC. As feature dimensions have gotten smaller, the radius of influence for edge features has extended further into neighboring cells such that it is no longer sufficient to perform cellwise OPC independent of neighboring cells, especially for the critical layers. The methodology described in this work accounts for features in neighboring cells and allows a cellwise approach to be applied to cells with a printed gate length of 45nm with the projection that it can also be applied to future technology nodes. OPC-ready cells are generated at library creation (independent of placement) using a boundary-based technique. Each cell has a tractable number of OPC-ready versions due to an intelligent characterization of standard cell layout features. Total number of cells with boundaries in the OPC-ready library only increases linearly with the number of cells in the original library. Results are very promising: the average edge placement error (EPE) for all metal1 features in 100 layouts is 0.731nm which is less than 1 % of metal1 width, creating similar levels of lithographic accuracy while obviating any of the drawbacks inherent in layout specific full-chip model-based OPC. For even small circuits, there were runtime reductions of up to 100times and a potential 35times decrease in mask data size.

Power grid networks in VLSI circuits are required to provide adequate input supply to ensure reliable performance. In this paper, we propose algorithms to find the placement of power pads that minimize not only the worst voltage drop but also the voltage deviation across the power grid. Our algorithm uses simulated annealing to minimize the total cost of voltage drops. The key enabler for efficient optimization is a fast localized node-based iterative method to compute the voltages after each movement of pads. Experimental results show that our algorithm demonstrates good runtime characteristics for power grids with large numbers of pad candidates in multi-million-size circuits. For a 16-million-node power grid with 646 thousand pad candidates, our algorithm took 72 minutes to improve the worst voltage drop from 0.398V to 0.196V and reduce the deviation of voltages on the power grid from 0.134V to 0.0241V.

Due to the extremely large sizes of power grids, IR drop analysis has become a computationally challenging problem both in terms of runtime and memory usage. It has been shown in (Zhong and Wong, 2005) that first-order iterative algorithms based on node-by-node and row-by-row traversals of the power grid have both accuracy and runtime advantages over the well-known random-walk method. In this paper, we propose second-order iterative algorithms that can significantly reduce the runtime. The new algorithms are extremely fast, and we prove that they guarantee converge to the exact solutions. Experimental results show that our algorithms outperform the random-walk algorithm in (Qian et al., 2003) and algorithms in (Zhong and Wong, 2005), For a 25-million node problem, while the random-walk algorithm takes 2 days with maximum error of 6.1 mV, the fastest algorithm in (Zhong and Wong, 2005) takes 50 minutes, and our second-order row-based algorithm takes 32 minutes to get an exact solution. Moreover, we can get a solution with maximum error 2 mV in 10 minutes.

In 90-nm technology, dynamic power is still the largest power source in FPGAs [1], and signal glitches contribute a large portion of the dynamic power consumption. Previous power- aware technology mapping algorithms for FPGAs have not taken into account the glitch power reduction. In this paper, we present a dynamic power estimation model and a new technology mapping algorithm considering glitches. To the best of our knowledge, this is the first work that explicitly reduces glitch power during technology mapping for FPGAs. Experiments show that our algorithm, named GlitchMap, is able to reduce dynamic power by 18.7% compared to a previous state-of-the-art power-aware algorithm, EMap [2].

In this paper, we target FPGA performance optimization using a novel BDD (binary decision graph)-based synthesis approach. Most of previous works have focused on BDD size reduction during logic synthesis. In this work, we concentrate on delay reduction and conclude that there is a large optimization margin through BDD synthesis for FPGA performance optimization. Our contributions are threefold: (1) we propose a gain-based clustering and partial collapsing algorithm to prepare the initial design for BDD synthesis for better delay; (2) we use a technique named linear expansion for BDD decomposition, which in turn enables a dynamic programming algorithm to efficiently search through the optimization space for the BDD of each node in the clustered circuit; (3) we consider special decomposition scenarios coupled with linear expansion for further improvement on quality of results. Experimental results show that we can achieve a 95% gain in terms of network depths, and a 20% gain in terms of routed delay, with a 22% area overhead on average compared to a previous state-of-art BDD-based FPGA synthesis tool, BDS-pga.

Design for low power has become a key requirement in today's SoC design, especially for mobile applications. Multi-Vdd is an effective method to reduce both leakage and dynamic power. In a multi-Vdd design, cells of different supply voltages are often grouped into a small number of voltage islands, in order to avoid complex power supply system and excessive amount of level shifters. Recently, [9] proposed an elegant algorithm for voltage island grouping based on the physical proximity of the critical cells in a post-placement voltage assignment, and [10] proposed an efficient algorithm for voltage assignment which not only meets timing but also forms good proximity of the critical cells. However, due to insufficient slack, a few isolated critical cells (called outliers) may still exist in the resulting voltage assignment, causing disproportionately expensive penalty to the final voltage island grouping. In this paper, we propose a novel approach to improve the voltage assignment by automatic outlier detection followed by incremental placement. The outlier detection is based on a modified algorithm for the facility location problem. The incremental placement is guided by setting proper constraints on the paths containing the detected outliers, such that the outliers can be eliminated later. Our experiments on industry designs show that our algorithm leads to 12% -- 54% improvement in the final voltage island grouping, with quick turn around time.

Modern FPGA chips contain multiple dedicated clocking networks, because nearly all real designs contain multiple clock domains. In this paper, we present an FPGA technology mapping algorithm targeting designs with multi-clock domains such as those containing multi-clocks, multi-cycle paths, and false paths. We use timing constraints to handle these unique clocking issues. We work on timing constraint graphs and process multiple arrival/required times for each node in the gate-level netlist. We also recognize and process constraint conflicts efficiently. Our algorithm produces a mapped circuit with the optimal mapping depth under timing constraints. To the best of our knowledge, this is the first FPGA mapping algorithm working with multi-clock domains. Experiments show that our algorithm is able to improve circuit performance by 16.8% on average after placement and routing for a set of benchmarks with multi-cycle paths, comparing to a previously published depth-optimal algorithm that does not consider multi-cycle paths.

The PCB routing problem has become so difficult that no commercial CAD software can provide an automatic solution for high-end boards. Existing algorithms for escape routing, an important step in PCB routing, are net-centric. Directly applying these algorithms will result in mixing nets of different buses together. But in practice, it is preferred to bundle together nets in a bus. Thus the bus-centric escape routing problem can be naturally divided into two subproblems: (1) finding a subset of buses that can be routed on the same layer without net mixings and crossings, which we refer to as the bus sequencing problem, and (2) finding the escape routing solutions for each chosen bus, which can be solved by a net-centric escape router. In this paper, we solve the bus sequencing problem. We introduce a new optimization problem called the longest common interval Sequence (LCIS) problem and model the bus sequencing problem as an LCIS problem. By using dynamic programming and balanced search tree data structure, we present an LCIS algorithm which can find an optimal solution in O(n log n) time. We also show that O(n log n) is a lower-bound for this problem and thus the time complexity of our algorithm is also the best possible.

Global routing is an important step in the physical design process. In this paper, we propose a new global routing algorithm Archer, which resolves some of the most common problems with the state-of- the-art global routers. It is known that concurrent global rou- ting algorithms are typically too expensive to be applied on today’s large designs, which may contain up to a million nets. On the other hand, iterative rip-up and reroute (RNR) based algorithms are sus- ceptible to getting stuck in local optimal solutions. In this paper, we propose an RNR-based global routing algorithm that guides the routing iterations out of local optima through effective usage of con- gestion histories. We also focus on the problem of how to enable a smooth trade-off between seemingly conflicting objectives of over- flow and wirelength minimization. Furthermore, we propose a Lagrangian relaxation based bounded-length min-cost topology improvement algorithm that enables Steiner trees to change dynamically for the purpose of congestion optimization. Our experiments show that Archer obtains congestion-free solutions for all circuits in the standard ISPD98 benchmarks, which is the best result published so far. Furthermore, it produces better results than the best results reported in the ISPD-07 Global Routing Contest in terms of routability. Compared to FastRoute [18, 19], which is the state-of- the-art RNR-based global routing algorithm, Archer improves routability by 30%, and reduces the wirelengths by 32% on the av- erage on ISPD07 benchmarks.

Previous works [1], [2] on PCB bus routing assume matched pin ordering for both sides. But in practice, the pin ordering might be mismatched and the nets become twisted. In this paper, we propose a preprocessing step to untangle such twisted nets. We also present an algorithm to solve this untangling problem. Our algorithm produces an optimal singledetour routing scheme that rematches the pin ordering. By integrating our preprocessing step into the bus router in [2], we show that many routing problems that cannot be solved previously can now be solved with insignificant increase in runtime.

As the device shapes keep shrinking, the designs are more sensitive to manufacturing processes. In order to improve performance predictability and yield, mask layout uniformity/evenness is highly desired, and it is usually measured by the feature density with defined feasible range in manufacture process design rules. To address the density control problem, one fundamental problem is how to calculate density accurately and efficiently. In this paper, we propose a fast exact algorithm to identify the maximum density for a given layout. Compared with the existing exact algorithms, our algorithm reduces the running time from days/hours to a few minutes/seconds. And it is even faster than the existing approximate algorithms in literature.

In modern VLSI manufacturing processes, dummy fills are widely used to adjust local metal density in order to improve layout uniformity and yield optimization. However, the introduction of a large amount of dummy features also affects wire electrical properties. In this paper, we propose the first Coupling constrained Dummy Fill (CDF) analysis algorithm which identifies feasible locations for dummy fills such that the fill induced coupling capacitance can be bounded within the given coupling threshold of each wire segment. The algorithm also makes efforts to maximize ground dummy fills, which are more robust and predictable. The output of the algorithm can be treated as the upper bound for dummy fill insertion, and it can be easily adopted in density models to guide dummy fill insertion without disturbing the existing design.

High power consumption not only leads to short battery life for hand-held devices but also causes on-chip thermal and reliability problems in general. As power consumption is proportional to the square of supply voltage, reducing supply voltage can significantly reduce power consumption. Multi-supply voltage (MSV) has previously been introduced to provide finer grain power and performance tradeoff. In this paper, we propose a methodology on top of a set of algorithms to exploit nontrivial voltage island boundaries for optimal power versus design-cost tradeoff under performance requirement. Our algorithms are efficient, robust, and error-bounded and can be flexibly tuned to optimize for various design objectives (e.g., minimal power within a given number of voltage islands, or minimal fragmentation in voltage islands within a given power bound) depending on the design requirement. Our experiment on real industry designs shows a tenfold improvement of our method over current logical-boundary-based industry approach.

Graph algorithms are widely used in VLSI CAD. Traditional graph algorithms can handle graphs with deterministic edge weights. As VLSI technology continues to scale into nanometer designs, we need to use probability distributions for edge weights in order to model uncertainty due to parameter variations. In this paper, we consider the statistical shortest path (SSP) problem. Given a graph G, the edge weights of G are random variables. For each path P in G, let L/sub P/ be its length, which is the sum of all edge weights on P. Clearly L/sub P/ is a random variable and we let /spl mu//sub P/, and /spl omega//sub P//sup 3/ be its mean and variance, respectively. In the SSP problem, our goal is to find a path P connecting two given vertices to minimize the cost function /spl mu//sub p/, + /spl Phi/ (/spl omega//sub P//sup 2/) where /spl Phi/ is an arbitrary function. (For example, if /spl Phi/ (/spl times/) /spl equiv/ the cost function is /spl mu//sub P/, + 3/spl omega//sub P/.) To minimize uncertainty in the final result, it is meaningful to look for paths with bounded variance, i.e., /spl omega//sub P//sup 2/ /spl les/ B for a given fixed bound B. In this paper, we present an exact algorithm to solve the SSP problem in O(B(V + E)) time where V and E are the numbers of vertices and edges, respectively, in G. Our algorithm is superior to previous algorithms for SSP problem because we can handle: 1) general graphs (unlike previous works applicable only to directed acyclic graphs), 2) arbitrary edge-weight distributions (unlike previous algorithms designed only for specific distributions such as Gaussian), and 3) general cost function (none of the previous algorithms can even handle the cost function /spl mu//sub P/, + 3/spl omega//sub P/. Finally, we discuss applications of the SSP problem to maze routing, buffer insertions, and timing analysis under parameter variations.

This paper presents a fundamental result on buffer sizing. Given an interconnection wire with n buffers evenly spaced along the wire, we would like to size all buffers such that the Elmore delay is minimized. It is well known that the problem can be solved by an iterative algorithm which sizes one buffer at a time. However, no closed form solution has ever been reported. In this paper, we derive a closed form buffer sizing function f(x) where f(x) gives the optimal buffer size for the buffer at position x. We show that f(x) can be expressed in terms of the Weierstrass elliptic function p(x) and its derivative p'(x).

Input vector control (IVC) technique is based on the observation that the leakage current in a CMOS logic gate depends on the gate input state, and a good input vector is able to minimize the leakage when the circuit is in the sleep mode. The gate replacement technique is a very effective method to further reduce the leakage current. In this paper, we propose a fast algorithm to find a low leakage input vector with simultaneous gate replacement. Results on MCNC91 benchmark circuits show that our algorithm produces $14 %$ better leakage current reduction with several orders of magnitude speedup in runtime for large circuits compared to the previous state-of-the-art algorithm. In particular, the average runtime for the ten largest combinational circuits has been dramatically reduced from 1879 seconds to 0.34 seconds.

Multi-Vdd is an effective method to reduce both leakage and dynamic power. A key challenge in a multi-Vdd design is to limit the design cost and the demand for level shifters. This can be tackled by grouping cells of different supply voltages into a small number of voltage islands. Recently, an elegant algorithm [7] is proposed for generating voltage islands that balance the power versus design cost tradeoff under performance requirement, according to the placement proximity of the critical cells. One prerequisite of [7] is an initial voltage assignment at the standard cell level that meets timing. In this paper, we present a novel method to produce quality voltage assignment to [7], which not only meets timing but also forms good proximity of the critical cells to provide [7] with a smooth input. The algorithm is based on effective delay budgeting and efficient computation of physical proximity by Voronoi diagram. Our extensive experiments on real industrial designs show that our algorithm leads to 25% - 75% improvement in the voltage island generation, with the computation time only linear to the design size.

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

Input-output (I/O) placement has always been a concern in modern integrated circuit design. Due to flip-chip technology, I/O can be placed throughout the whole chip without long wires from the periphery of the chip. However, because of I/O placement constraints in design cost (DC) and performance, I/O buffer planning becomes a pressing problem. During the early stages of circuits and package co-design, I/O layout should be evaluated to optimize DC and to avoid product failures. The objective of this brief is to improve the existing/initial standard cell placement by I/O clustering, considering DC reduction and signal integrity preservation. The authors formulate it as a minimum cost flow problem that minimizes alphaW+betaD, where W is the I/O wirelength of the placement and D is the total voltage drop in the power network and, at the same time, reduces the number of I/O buffer blocks. The experimental results on some Microelectronics Center of North Carolina benchmarks show that the author's method averagely achieves better timing performance and over 32% DC reduction when compared with a conventional rule-of-thumb design that is popularly used by circuit designers

Modern field-programmable gate arrays (FPGAs) have multimillions of gates and future generations of FPGAs will be even more complex. This means that floorplanning tools will soon be extremely important for the physical design of FPGAs. Due to the heterogeneous logic and routing resources of an FPGA, FPGA floorplanning is very different from the traditional floorplanning for application-specific integrated circuits. This paper presents the first FPGA-floorplanning algorithm targeted for FPGAs with heterogeneous resources (e.g., Xilinx's Spartan3 chips consisting of columns of configurable logic blocks, RAM blocks, and multiplier blocks). This algorithm can generate floorplans for Xilinx's XC3S5000 architecture (largest of the Spartan3 family) in a few minutes

As the clock frequencies used in industrial applications increase, the timing requirements on routing problems become tighter, and current routing tools cannot successfully handle these constraints any more. In this paper, the authors focus on the high-performance single-layer bus routing problem, where the objective is to match the lengths of all nets belonging to each bus. An effective approach to solve this problem is to allocate extra routing resources around short nets during routing, and use those resources for length extension afterwards. First, a provably optimal algorithm for routing nets with minimum-area maximum-length constraints is proposed. Then, this algorithm is extended to the case where minimum constraints are given as exact length bounds, and it is also proven that this algorithm is near-optimal. Both algorithms proposed are shown to be scalable for large circuits, since the respective time complexities are O(A) and O(AlogA), where A is the area of the intermediate region between chips.

As die sizes are shrinking, and circuit complexities are increasing, the printed circuit board routing problem becomes more and more challenging. Traditional routing algorithms cannot handle these challenges effectively, and many high-end designs in the industry require manual routing efforts. This paper proposes a problem decomposition that distinguishes routing under dense components from routing in the intermediate area. In particular, it proposes an effective methodology to find the escape routing solution for multiple components simultaneously such that the number of crossings in the intermediate area is minimized. For this, the problem is modeled as a longest path with forbidden pairs problem, and two algorithms are proposed for it. The first is an exact polynomial-time algorithm that is guaranteed to find the maximal planar routing solution on one layer. The second is a randomized algorithm that has good scalability characteristics for large circuits. Then, these algorithms are used to assign the maximal subset of planar nets to each layer, and then the remaining nets are distributed at the end. This paper demonstrates the effectiveness of these algorithms through experiments on industrial circuits.

As the clock frequencies used in industrial applications increase, the timing requirements imposed on routing problems become tighter. Therefore, it becomes important to route the nets within tight minimum and maximum length bounds. Although the problem of routing nets to satisfy maximum length constraints is a well-studied problem, there exists no sophisticated algorithm in literature that ensures that minimum length constraints are also satisfied. In this paper, the authors propose a novel algorithm that effectively incorporates the min–max length constraints into the routing problem. The approach is to use a Lagrangian-relaxation (LR) framework to allocate extra routing resources around nets simultaneously during routing them. The authors also propose a graph model that ensures that all the allocated routing resources can be used effectively for extending lengths. Their routing algorithm automatically prioritizes resource allocation for shorter nets and length minimization for longer nets so that all nets can satisfy their min–max length constraints. This paper demonstrates that this algorithm is effective even in the cases where length constraints are tight, and the spacing between adjacent nets is small.

Existing floorplanning algorithms compact blocks to the left and bottom. Although the compaction obtains an optimal area, it may not be good for meeting other objectives such as minimizing the total wire length, which is the first-order objective. It is not known in the literature how to place blocks to obtain an optimal wire length. This paper first shows that the problem can be formulated by linear programming. Thereafter, instead of using the general, but slow, linear programming, this paper proposes an efficient minimum-cost flow-based approach to solve it. This approach guarantees to obtain the minimum total wire length in polynomial time and meanwhile keep the minimum area by distributing white space smarter for a given floorplan topology. This paper also shows that the approach can be easily extended to handle constraints such as fixed frame (fixed area), input-output (IO) pins, preplaced blocks, boundary blocks, range placement, alignment and abutment, rectilinear blocks, soft blocks, one-dimensional cluster placement, and bounded net delay, without loss of optimality. Practically, the algorithm is so efficient that it finishes in less than 0.4 s for all Microelectronics Center of North Carolina (MCNC) benchmarks of block placement. It is also very effective. Experimental results show that the wire length of very compact floorplans can even be improved by 4.2%. Thus, it provides an ideal way for postfloorplanning refinement

Engineering change order changes are almost inevitable in the late stages of a design process. Based on an existing design, incremental change is favored since it can avoid considerable efforts of redoing the whole process and can minimize the disturbance on the existing converged design. The coupling-capacitance violation elimination (CVE) problem is addressed. Due to the changes in the multiple layer routing design, the total coupling capacitance on some signal wire segments on a layer may be larger than their allowable bounds after postlayout timing/noise analysis. The target is to find a new routing solution without coupling-capacitance violations under certain constraints, which helps to keep the new design close to the original one. This paper proposes a two-stage algorithm to solve CVE problems, and present optimization strategies to speed up the execution. Experimental results demonstrate the efficiency and effectiveness of this algorithm

The increasing clock frequencies in high-end industrial circuits bring new routing challenges that cannot be handled by traditional algorithms. An important design automation problem for high-speed boards today is routing nets within tight minimum and maximum length bounds. In this article, we propose an algorithm for routing bus structures between components on two layers such that all length constraints are satisfied. This algorithm handles length extension simultaneously during the actual routing process so that maximum resource utilization is achieved during length extension. Our approach here is to process one track at a time, and choose the best subset of nets to be routed on each track. The algorithm we propose for single-track routing is guaranteed to find the optimal subset of nets together with the optimal solution with length extension on one track. The experimental comparison with a recently proposed technique shows the effectiveness of this algorithm both in terms of solution quality and run-time.

In this paper we present a floorplanning algorithm for 3-D ICs. The problem can be formulated as that of packing a given set of 3-D rectangular blocks while minimizing a suitable cost function. Our algorithm is based on a generalization of the classical 2-D slicing floorplans to 3-D slicing floorplans. A new encoding scheme of slicing floorplans (2-D/3-D) and its associated set of moves form the basis of the new simulated annealing based algorithm. The bestknown algorithm for packing 3-D rectangular blocks is based on simulated annealing using sequence-triple floorplan representation. Experimental results show that our algorithm produces packing results on average 3% better than the sequence-triple-based algorithm under the same annealing parameters, and our algorithm runs much faster (17 times for problems containing 100 blocks) than the sequence-triple. Moreover, our algorithm can be extended to consider various types of placement constraints and thermal distribution while the existing sequence-triple-based algorithm does not have such capabilities. Finally, when specializing to 2-D problems, our algorithm is a new 2-D slicing floorplanning algorithm. We are excited to report the surprising results that our new 2-D floorplanner has produced slicing floorplans for the two largest MCNC benchmarks ami33 and ami49 which have the smallest areas (among all slicing/nonslicing floorplanning algorithms) ever reported in the literature.

In this paper, we propose a new multi-objective multilevel K-way partitioning which is aware of resource utilization distribution, assuming the resource utilization for a partitioned block is proportional to the logic occupation and the interconnections required for the block. A new quality of the partitioning solution, crowdedness, is defined as a virtual complexity metric where the physical size and the local connectivity of a partitioned block are considered simultaneously in the form of a weighted sum. The partitioning solutions driven by overall cut quality minimization tend to have wide variances of local interconnections for different blocks. The difference of block sizes, combining with the variance of the interconnections, potentially leads to the significant imbalance of the crowdedness (equivalently, resource utilization), even though the feasibility imposed by a block-size constraint is satisfied.Using the crowdedness metric, we explore the new partitioning solution space where the local interconnections are adaptively adjusted according to the block sizes, still under the same objective of overall interconnections minimization. By the carefully designed prioritized cell move policy, the proposed crowdedness-based partitioning achieves near-optimal solutions in terms of resource utilization distribution, while the overall interconnection quality also is improved but the feasibility is barely violated. The proposed approach is practically beneficial to multi-FPGA applications, in which excessive interconnections for a FPGA generate additional logics inside of the FPGA.

Existing floorplanning algorithms compact blocks to the left and bottom. Although the compaction obtains an optimal area, it may not be good to meet other objectives such as minimizing total wire length which is the first-order objective. It is not known in the literature how to place blocks to obtain an optimal wire length. In this paper, we first show that the problem can be formulated as linear programming. Thereafter, instead of using the general but slow linear programming, we propose an efficient min-cost flow based approach to solve it. Our approach guarantees to obtain the minimum of total wire length in polynomial time and meanwhile keep the minimum area by distributing white space smarter for a given floorplan topology. We also show that the approach can be easily extended to handle constraints such as fixed-frame (fixed area), IO pins, pre-placed blocks, boundary blocks, range placement, alignment and abutment, rectilinear blocks, soft blocks, one-dimensional cluster placement, and bounded net delay, without loss of optimality. Practically, the algorithm is so efficient in that it finishes in less than 0.4 seconds for all MCNC benchmarks of block placement. It is also very effective. Experimental results show we can improve 4.2% of wire length even on very compact floorplans. Thus it provides an ideal way of post-floorplanning (refine floorplanning).

Redundant via insertion is a good solution to reduce the yield loss by via failure. However, the existing methods are all post-layout optimizations that insert redundant via after detailed routing. In this paper, we propose the first routing algorithm that considers feasibility of redundant via insertion in the detailed routing stage. Our routing problem is formulated as maze routing with redundant via constraints. The problem is transformed to a multiple constraint shortest path problem, and solved by Lagrangian relaxation technique. Experimental results show that our algorithm can find routing layout with much higher rate of redundant via than conventional maze routing.

By putting different chips on the same mask, shuttle mask (or multiple project wafer) provides an economical solution for low volume designs and design prototypes to share the rising mask cost. A challenging floorplanning problem is to optimally pack these chips according to objectives and constraints related to cost and manufacturability. In this paper, we study the problem of CMP aware shuttle mask floorplanning, which is formulated as a rectangle packing problem with objectives of area and post-CMP topography variation minimization. We propose a 3-step procedure to solve the problem. First, we use the low-pass filter oxide CMP model to guide the simulated annealing search to minimize the topography variation. The result is then further improved by sliding each chip in its enclosing rectangle. Finally, we calculate the optimal amount of dummy feature needed with a linear programming method. Our experiment show excellent results on real industry data.

Energy optimization for high-capacitance on-chip buses has become a critical problem in VLSI design, especially for embedded or SoC systems. Coupling effects between bus wires make this issue even more urgent. Coding schemes have been proposed to reduce the energy dissipation. However, the circuits overhead increases significantly when the coding schemes consider the inter-wire capacitances. In this paper, we present a novel method for energy optimization in memory address bus (MAB). The data on application specified MAB has different characters to the data bus, which has high repetition vectors and unevenly distributed switch activity. Thus a combined method is proposed to optimize the energy consumption by both self capacitance and inter-wire capacitance. First, we lower the switch activity by an efficient coding scheme. Based on the statistical data, a modified bus-invert coding scheme can intelligently divide bus lines into groups and apply bus-invert coding. It brings ultra-low area or timing penalty because of the simple circuit structure. Then the energy consumption of coupling capacitances is optimized by net reordering technique. Implemented with table-look-up technique, a fast simulated annealing algorithm is proposed to solve the net reordering problem. The experimental results show that our combined method is very efficient to reduce the energy consumption in memory address bus for varieties of applications.

This paper considers the buffer insertion problem under process variations. With continued technology scaling, it is necessary to model the physical parameters to be random variables. One approach to the buffer insertion problem under variations is to use the mean values of these parameters and solve the problem using traditional buffer insertion techniques for delay minimization. Another approach is to find a buffer insertion solution using a new method that can handle the probability distributions. Thus, the performance can be optimized with some yield constraint. In this paper, we present both analytical and experimental results to show that the two approaches give almost identical solutions. In other words, the more expensive statistical methods are not needed for the buffer insertion in delay minimization problem.

Shrinking transistor sizes, increasing circuit complexities, and high clock frequencies bring new board routing challenges that cannot be handled effectively by traditional routing algorithms. Many high-end designs in the industry today require manual routing efforts, which increases the design cycle times considerably. In this paper, we propose an escape routing algorithm to route nets within multiple dense components simultaneously so that the number of crossings in the intermediate area is minimized. We also show how to handle high-speed design constraints within the framework of this algorithm. Experimental comparisons with a recently proposed algorithm (Ozdal and Wong, 2004) show that our algorithm reduces the via requirements of industrial test cases on average by 39%.

Optimal routing algorithms for pin clusters in high-density multichip modules As the circuit densities and transistor counts are increasing, the package routing problem is becoming more and more challenging. In this paper, we study an important routing problem encountered in typical high-end MCM designs: routing within dense pin clusters. Pin clusters are often formed by pins that belong to the same functional unit or the same data bus, and can become bottlenecks in terms of overall routability. Topically, these clusters have irregular shapes, which can be approximated with rectilinear convex boundaries. Since such boundaries have often irregular shapes, a traditional escape routing algorithm may give unroutable solutions. In this paper, we study how the positions of escape terminals on a convex boundary affect the overall routability. For this purpose, we propose a set of necessary and sufficient conditions to model routability outside a rectilinear convex boundary. Given an escape routing solution, we propose an optimal algorithm to select the maximal subset of nets that are routable outside the boundary. After that, we focus on an integrated approach to consider routability constraints (outside the boundary) during the actual escape routing algorithm. Here, we propose an optimal algorithm to find the best escape routing solution that satisfies all routability constraints. Our experiments demonstrate that we can reduce the number of layers by 17% on the average, by using this integrated methodology.

High power consumption not only leads to short battery life for handheld devices, but also causes on-chip thermal and reliability problems in general. As power consumption is proportional to the square of supply voltage, reducing supply voltage can significantly reduce power consumption. Multi-supply voltage (MSV) has previously been introduced to provide finer-grain power and performance trade-off. In this work we propose a methodology on top of a set of algorithms to exploit non-trivial voltage island boundaries for optimal power versus design cost trade-off under performance requirement. Our algorithms are efficient, robust and error-bounded, and can be flexibly tuned to optimize for various design objectives (e.g., minimal power within a given number of voltage islands, or minimal fragmentation in voltage islands within a given power bound) depending on the design requirement. Our experiment on real industry designs shows a ten-fold improvement of our method over current logical-boundary based industry approach.

Due to the extremely large size of power grids, IR drop analysis has become a computationally challenging problem both in terms of runtime and memory usage. Although IR drop analysis can be naturally formulated as the problem of solving a linear system, the system is too large to be solved by existing linear solvers. In this paper, we present two iterative algorithms based on node-by-node traversals and row-by-row traversals of the power grid, respectively. Our algorithms are extremely fast and guarantee convergence to the exact solutions. In fact, they can be considered as efficient implementations of the classical successive over relaxation iterative method for solving linear systems. Our methods take full advantage of the special structure of the power grid. Experimental results show that our algorithms out-perform the random-walk-based algorithm which is the best known method today. For a 16-million node problem, our row-based algorithm took 26.47 minutes while the random-walk-based algorithm took 19.6 hours. Our row-based algorithm produced an exact solution while the random walk produced a solution with maximum error of 5.7 mV.

With today's advanced integrated circuit manufacturing technology in deep submicron (DSM) environment, we can integrate entire electronic systems on a single system on a chip. However, without careful power supply planning in layout, the design of chips will suffer from local hot spots, insufficient power supply, and signal integrity problems. Postfloorplanning or postroute methodologies in solving power delivery and signal integrity problems have been applied but they will cause a long turnaround time, which adds costly delays to time-to-market. In this paper, we study the problem of simultaneous power supply planning and noise avoidance as early as in the floorplanning stage. We show that the problem of simultaneous power supply planning and noise avoidance can be formulated as a constrained maximum flow problem and present an efficient yet effective heuristic to handle the problem. Experimental results are encouraging. With a slight increase of total wirelength, we achieve almost no static IR (voltage)-drop requirement violation in meeting the current and power demand requirement imposed by the circuit blocks compared with a traditional floorplanner and 45.7% of improvement on a /spl Delta/I noise constraint violation compared with the approach that only considers power supply planning.

The buffer block methodology has become increasingly popular as more and more buffers are needed in deep-submicron design, and it leads to many challenging problems in physical design. In this article, we present a polynomial-time exact algorithm for integrated pin assignment and buffer planning for all two-pin nets from one macro block (source block) to all other blocks of a given buffer block plan, while minimizing the total cost α ˙ W + β ˙ R for any positive α and β where W is the total wirelength, and R is the number of buffers. By applying this algorithm iteratively (each time, pick one block as the source block), it provides a polynomial-time algorithm for pin assignment and buffer planning for nets among multiple macro blocks. Experimental results demonstrate its efficiency and effectiveness.

As the technology migrates into the deep submicron manufacturing(DSM) era, the critical dimension of the circuits is getting smaller than the lithographic wavelength. The unavoidable light diffraction phenomena in the sub-wavelength technologies have become one of the major factors in the yield rate. Optical proximity correction (OPC) is one of the methods adopted to compensate for the light diffraction effect as a post layout process.However, the process is time-consuming and the results are still limited by the original layout quality. In this paper, we propose a maze routing method that considers the optical effect in the routing algorithm. By utilizing the symmetrical property of the optical system, the light diffraction is efficiently calculated and stored in tables. The costs that guide the router to minimize the optical interferences are obtained from these look-up tables. The problem is first formulated as a constrained maze routing problem, then it is shown to be a multiple constrained shortest path problem. Based on the Lagrangian relaxation method, an effective algorithm is designed to solve the problem.

Complementary bus architecture is used to achieve higher speed and lower power in VLSI chips. However, in deep submicron circuit design, the effects of crosstalk become more and more serious, especially in the bus structure where wires are placed close to each other. Complementary bus architecture with twisted wires can reduce the coupling noise. But in current chip design flow, engineering change order (ECO) happens commonly to meet improvement requirement. Layout changes due to ECO introduce obstacles to the twists, which could reduce the number of twists and increase the coupling noise. In this paper, an ECO algorithm for generating twisted complementary architecture is proposed based on the shortest path algorithm. Our algorithm guarantees to give the minimum number of twists along the bus wires under noise constraints. Experimental results show that the twist patterns generated by our algorithm can effectively reduce the capacitive coupling noises.

Modern FPGAs have multi-millions of gates and future generations of FPGA will be even more complex. This means floorplanning tools will soon be extremely important for the physical design of FPGAs. Due to the heterogeneous logic and routing resources on an FPGA, FPGA floorplanning is very different from the traditional floorplanning for ASICs. This work presents the first FPGA floorplanning algorithm targeted for FPGAs with heterogeneous resources (e.g., Xilinx's Spartan3 chips consisting of columns of CLBs, RAM blocks, and multiplier blocks). Our algorithm can generate floor-plans for Xilinx's XC3S5000 architecture (largest of the Spartan3 family) in a few minutes.

As die sizes are shrinking, and circuit complexities are increasing, the PCB routing problem becomes more and more challenging. Traditional routing algorithms can not handle these challenges effectively, and many high-end designs in the industry require manual routing efforts. In this paper, we propose a problem decomposition that distinguishes routing within dense components from routing in the intermediate area. In particular, we propose an effective methodology to find the escape routing solution for multiple components simultaneously such that the number of crossings in the intermediate area is minimized. For this, we model the problem as a longest path with forbidden pairs (LPFP) problem, and propose two algorithms for it. The first is an exact polynomial-time algorithm that is guaranteed to find the maximal planar routing solution on one layer. The second is a randomized algorithm that has good scalability characteristics for large circuits. Then we use these algorithms to assign the maximal subset of planar nets to each layer, and then distribute the remaining nets at the end. We demonstrate the effectiveness of these algorithms through experiments on industrial circuits.

As the clock frequencies used in industrial applications increase, the timing requirements on routing problems become tighter, and current routing tools can not successfully handle these constraints any more. We focus on the high-performance single-layer bus routing problem, where the objective is to match the lengths of all nets belonging to each bus. An effective approach to solve this problem is to allocate extra routing resources around short nets during routing; and use those resources for length extension afterwards. We first propose a provably optimal algorithm for routing nets with min-area max-length constraints. Then, we extend this algorithm to the case where minimum constraints are given as exact length bounds. We also prove that this algorithm is optimal within a constant factor. Both algorithms proposed are also shown to be scalable for large circuits, since the respective time complexities are O(A) and O(A log A), where A is the area of the intermediate region between chips.

I/O placement has always been a concern in modern IC design. Due to flip-chip technology, I/O can be placed throughout the whole chip without long wires from the periphery of the chip. However, because of I/O placement constraints in design cost and performance, I/O buffer planning becomes a pressing problem. During the early stages of circuits and packaging co-design, I/O layout should be evaluated to optimize design cost and to avoid product failures. In this paper, our objective is to better an existing/initial standard cell placement by I/O clustering, considering design cost reduction and signal integrity preservation. We formulate it as a minimum cost flow problem minimizing /spl alpha/W+/spl beta/D, where W is the I/O wirelength of the placement and D is the total voltage drop in the power network. The experimental results on some MCNC benchmarks show that our method achieves better timing performance and averagely over 30% design cost reduction when compared with the conventional design rule of thumb popularly used by circuit designers.

The increasing clock frequencies in high-end industrial circuits bring new routing challenges that cannot be handled by traditional algorithms. An important design automation problem for high-speed boards today is routing nets within tight minimum and maximum length bounds. In this paper, we propose an algorithm for routing bus structures between components on two layers such that all length constraints are satisfied. This algorithm handles length extension simultaneously during the actual routing process so that maximum resource utilization is achieved during length extension. Our approach here is to process one track at a time, and choose the best subset of nets to be routed on each track. The algorithm we propose for single-track routing is guaranteed to find the optimal subset of nets together with the optimal solution with length extension on one track. The experimental comparison with a recently proposed technique shows the effectiveness of this algorithm both in terms of solution quality and run-time.

With the dramatic increase in mask costs, multi-project wafers have became an attractive choice for low-volume chip fabrication. By using the same set of masks to fabricate a number of different chips, the mask-set cost is amortized among different chip providers, leading to significant cost reduction especially for chip prototyping. In this paper, we present a new algorithm for reticle floorplanning with wafer yield guarantees. The previous approach of Kahng et al. considers optimizing both the reticle area and the wafer yield, leading to suboptimal solutions with no yield bounds. By contrast, we consider the yield as a constraint and optimize the area accordingly. We characterize yield constraints and provide a mechanism through which yield can be incorporated into an optimal-area packer. The incorporation of yield constraints prunes large parts of the search space of the optimal-area packer, leading to runtime-efficient optimal-area floorplans with guaranteed yields. Empirical results demonstrate that our approach dominates previous results, i.e., we give floorplans that consume less area and have higher die yields. For the 10 benchmarks, we achieve a yield improvement of 14% with an area reduction of 2%.

ECO changes are almost inevitable in late stages of a design process. Based on an existing design, incremental change is favored since it can avoid considerable efforts of re-doing the whole process and can minimize the disturbance on the existing converged design. In this paper, we address the CVE (Crosstalk Violation Elimination) problem. Due to the changes in a multiple layer routing design, the total capacitive crosstalk on some signal wire segments on a layer may be larger than their allowable bounds after post-layout timing/noise analysis. The target is to find a new routing solution without crosstalk violations under certain constraints which help to keep the new design close to the original one. We propose a two-stage algorithm to solve CVE problems, and present optimization strategies to speed up the execution. Experimental results demonstrate the efficiency and effectiveness of our algorithm.

The antenna problem is a phenomenon of plasma-induced gate-oxide degradation. It directly affects manufacturability of very large scale integration (VLSI) circuits, especially in deep submicron technology using high-density plasma. Diode insertion is a very effective way to solve this problem. Ideally, diodes are inserted directly under the wires that violate antenna rules. But in today's high-density VLSI layouts, there is simply not enough room for "under-the-wire" diode insertion for all wires. Thus, it is necessary to insert many diodes at legal "off-wire" locations and extend the antenna-rule violating wires to connect to their respective diodes. Previously, only simple heuristic algorithms were available for this diode insertion and routing problem. In this paper, we show that the diode insertion and routing problem for an arbitrary given number of routing layers can be optimally solved in polynomial time. Our algorithm guarantees finding a feasible diode insertion and routing solution whenever one exists. Moreover, we can guarantee to find a feasible solution to minimize a cost function of the form /spl alpha//spl times/L+/spl beta//spl times/N, where L is the total length of extension wires and N is the total number of vias on the extension wires. Experimental results show that our algorithm is very efficient.

In this paper, we present an integrated approach for floorplanning and bus planning, i.e., bus-driven floorplanning (BDF). We are given a set of circuit blocks and the bus specifications (i.e., the net list of blocks for the buses). A feasible BDF solution is a placement of all circuit blocks such that each bus can be realized as a rectangular strip (horizontal or vertical) going through all the blocks connected by the bus. The objective is to determine a feasible BDF solution that minimizes the floorplan area and the total bus area. Our approach is based upon the sequence-pair floorplan representation. After a careful analysis of the relationship between bus ordering and block ordering in the floorplan represented by a sequence pair, we derive feasibility conditions on sequence pairs that give feasible BDF solutions. Experimental results demonstrate the efficiency and effectiveness of our algorithm.

Abstract — With today’s advanced integrated circuits (ICs) manufacturing technology in deep submicron (DSM) environ-ment, we can integrate entire electronic systems on a single chip (SoC). However, without careful power supply planning in lay-out, the design of chips will suffer from mostly signal integrity problems including IR-drop, I noise, and IC reliability. Post-route methodologies in solving signal integrity problem have been applied but they will cause a long turn-around time, which adds costly delays to time-to-market. In this paper, we study the prob-lem of power supply noise avoidance as early as in floorplanning stage. We show that the noise avoidance in power supply planning problem can be formulated as a constrained maximum flow prob-lem and present an efficient yet effective heuristic to handle the problem. Experimental results are encouraging. With slight in-crease of total wirelength, we achieve almost no IR-drop require-ment violation and 46.6 % of improvement on I noise constraint violation compared with a previous approach. I.

problem has become one of the dominant factors in determining system reliability. This problem is caused by high current density flowing in the metal interconnect. Therefore, current evaluation is a crucial concern in IC design. SPICE level circuit simulators are excellent for doing current calculation, however, their running time are too expensive to be used repeatedly in design synthesis loops. In this paper, we propose an efficient approach for the interconnect current calculation. This method is based on moment matching but does not need high order moments. It only needs traversing the RC tree once to get the mean current value of every segment, traversing the tree once more is enough for the RMS current calculation, and two more traversals is sufficient for the peak current calculation. We apply our method to a larger number of interconnects getting close-to-SPICE accuracy at significantly faster runtimes. In particular, applying the method to 17,387 wire segments in the clock tree of a commercial IC, we obtained that the average deviation error of mean current is 0.0569%, average RMS current error is 0.703 % and average peak current error is 6.552%. It took 28 hours for HSPICE to get current value of all the wire segments and it only took our method 156 seconds. I.

In order to adequately account for nanometer effects during timing analysis, archaic standard cell models must be replaced. Simplifying assumptions used during characterization, such as nearly linear voltage inputs or lumped-capacitance loads, are no longer valid. Signal integrity analysis further complicates the characterization process because the typical voltage waveform used during characterization does not contain a noise component. This paper introduces two new technologies for standard cell and interconnect timing analysis: Blade and Razor. Blade is a novel cell model and runtime engine based on current flow. Razor is the accompanying interconnect model. Both Blade and Razor produce and consume arbitrary voltage waveforms with near-SPICE accuracy at speeds tens of thousands of times faster than SPICE.

The routing channels of an FPGA consist of wire segments of various types providing the tradeoff between performance and routability. In the routing architectures of recently developed FPGAs (e.g., Virtex-II), there are more versatile wire types and richer connections between them than those of the older generations of FPGAs (e.g. XC4000). To fully exploit the potential of the new routing architectures, it is beneficial to perform wire type assignment for all channels as an intermediate stage between global routing and detailed routing. In this paper, we present a wire-type assignment algorithm that is based on iteratively applying min-cost max-flow technique to simultaneously route many nets. At each stage of the network flow computation, we have guaranteed optimal result in terms of routability and delay cost. We use the routing architecture of the Virtex-II FPGAs from Xilinx as a target architecture in our experiments. Experimental results show that our algorithm outperforms the traditional sequential net-by-net approach.

Delay evaluation is always a crucial concern in the VLSI design and it becomes increasingly more critical in the nowadays deep-submicron technology. To obtain an accurate delay value, the gate modeling is a key issue. As the VLSI feature size scaling down and meanwhile operating frequency increasing, the modeling work becomes more difficult than ever for high-performance digital ICs. Nevertheless, most conventional techniques of gate modeling are based on the switch-resistor model;(i.e., a voltage source concatenating a driving resistance), which can only capture the gate characteristic in its switching region. Hence, these modeling techniques have to decouple the gate with its interconnects and compute a piecewise linear function for the driving source in the iterative computation of effective capacitance [1, 3, 4]. Since the driving source of the model is dependent on gate load, when the design modification affects the load, the gate has to be modeled again almost from the beginning for a new timing analysis. The efficiency will be deteriorated in synthesis loops due to this. In this paper, we present an explicit gate delay model, which is not sensitive to gate load and can be pre-computed before timing analysis and synthesis. Thus, the repetition of modeling work is totally unnecessary even when the gate load keeps on changing in the performance optimization procedure. The efficiency is certainly improved in the synthesis/optimization loops. The advantage is attributed to using a second-order circuit as the model base. This two-pole approach also certifies the model to yield an accurate result to match the non-linear output of gate.

In this paper, we present a new multilevel circuit partitioning algorithm (dhml) which is guided by design hierarchy. In addition to flat netlist hypergraph, we use user design hierarchy as a hint for partitioning. This design hierarchy already has some implications on connectivity between logical blocks in the design. Using design hierarchy in partitioning is nontrivial since the hierarchical elements in design hierarchy do not necessarily have strong internal connectivity; hence, we need to determine whether it is preferable to break up or preserve the hierarchical elements. In order to identify and select the hierarchical elements with strong connectivity, their Rent exponents are used. Then, the selected hierarchical elements serve as effective clustering scopes during the multilevel coarsening phase. The scopes are dynamically updated (enlarged) while building up a clustering tree so that the clustering tree resembles the densely connected portions of the design hierarchy. We tested our algorithm on a set of large industrial designs in which the largest one has 1.8 million cells, 2.8 million nets, and 11 levels of hierarchy. By exploiting design hierarchy, our algorithm produces higher quality partitioning results than the state-of-the-art multilevel partitioner hMetis. Furthermore, experimental results show that dhml yields significantly more stable solutions, which is helpful in practice to reduce the number of runs to obtain the best result.

The authors address the problem of simultaneous routing and buffer insertion. Recently the authors considered simultaneous maze routing and buffer insertion under the Elmore delay model. Their algorithms can take into account both routing obstacles and restrictions on buffer locations. It is well known that the Elmore delay is only a first-order approximation of signal delay and hence could be very inaccurate. Moreover, constraints cannot be imposed on the transition times of the output signal waveform at the sink or at the buffers on the route. The authors extend the algorithm in so that accurate delay models (e.g., transmission line model, delay lookup table from SPICE, etc.) can be used. They show that the problem of finding a minimum-delay buffered routing path can be formulated as a shortest path problem in a specially constructed weighted graph. By including only the vertices with qualifying transition times in the graph, they guarantee that all transition time constraints are satisfied. Their algorithm can be easily extended to handle buffer sizing and wire sizing. It can be applied iteratively to improve any given routing tree solution. Experimental results show that their algorithm performs well.

As interconnection delay plays an important role in determining circuit performance in field programmable gate arrays (FPGAs), timing-driven FPGA routing has received much attention recently. In this paper, we present a new timing-driven routing algorithm for FPGAs. The algorithm minimizes critical path delay for a given placed circuit using the Lagrangian relaxation technique. Lagrangian multipliers used to relax timing constraints are updated by subgradient method over iterations. Incorporated into the cost function, these multipliers guide the router to construct a routing tree for each net. During routing, the congestion constraints on each routing resource are also handled to route circuits successfully. Experimental results on benchmark circuits show that our approach outperforms the state-of-the-art versatile place and route router.

Macroblock pin assignment and routing are important tasks in physical design. Existing algorithms for these problems can be classified into two categories: 1) a two-step approach where pin assignment is followed by routing and 2) a net-by-net approach where pin assignment and routing for a single net are performed simultaneously. However, none of the existing algorithms is "exact" in the sense that they may fail to route all of the nets even though a feasible solution exists. This remains to be true even if only two-pin nets with fixed pins between two blocks are concerned. In this paper, we consider the problem of two-pin net connections from one macroblock to all of the other blocks, and present the first polynomial-time exact algorithm for simultaneous pin assignment and routing for all of the two-pin nets between one block (source block) and all of the other blocks. In addition to finding a feasible solution whenever one exists, it guarantees to find a pin-assignment/routing solution with minimum cost /spl alpha//spl middot/W+/spl beta//spl middot/V, where W is the total wire length and V is the total number of vias. Our algorithm has various applications. 1) It is suitable in engineering change order (ECO) situations where the existing solution is modified incrementally. 2) Given any pin assignment and routing solution obtained by any existing method, our algorithm can be used to increase the number of routed nets and reduce the routing cost. Furthermore, it provides an efficient algorithm for the pin assignment and routing problem of all of the blocks. The method is applicable to both global and detailed routing with arbitrary routing obstacles on multiple layers. Experimental results demonstrate its efficiency and effectiveness.

Switch modules are the most important component of the routing resources in FPGAs/FPICs. Previous works have shown that switch modules with higher routability result in better area performance for practical applications. We consider in this paper an FPGA/FPIC switch-module analysis problem: the inputs consist of a switch-module description and the number of nets required to be routed through the switch module; the question is to determine if there exists a feasible routing for the routing requirements on the switch module. As a fundamental problem for the analysis of switch modules, this problem is applicable to the design and routability evaluation of FPGA/FPIC switch modules and FPGA/FPIC routing. We present a network-flow-based approximation algorithm for this problem. Based on mathematical analyses, we show that this algorithm has provably good performance with the bounds 5 and 5/4 away from the optima for two types of switch modules, respectively. Extensive experiments show that this algorithm is highly accurate and runs very efficiently.

In this paper, we present a floorplanning algorithm based on sequence pair representation. Our floorplanner has the following important features: 1) It is explicitly designed for fixed-frame floorplanning, which is different from traditional well-researched min-area floorplanning. Moreover, we also show that it can be adapted to minimize total area. 2) It addresses the problem of handling alignment constraint which arises in bus structure. 3) It deals with performance constraint such as bounded net delay, while many existing floorplanners just minimize total wire length. 4) More importantly, even with all these constraints the algorithm is very fast in that it evaluates the feasibility of a sequence pair and translates to a floorplan in O(n log log n) time typically where n is the number of blocks and the number of constrained blocks is O(n), which is significantly faster than the O(n3) method operating on constraint graph. Our algorithm is based on computing the longest common subsequence of a pair of weighted sequences. Experimental results on MCNC benchmark for block placement show the promise of the method.

The buffer block methodology has become increasingly popular as more and more buffers are needed in deep-submicron design, and it leads to many challenging problems in physical design. In this paper, we present a polynomial-time exact algorithm for integrated pin assignment and buffer planning for all two-pin nets from one macro block (source block) to all other blocks of a given buffer block plan as well as minimizing the total cost α ċ W + Β ċ R for any positive α and Β where W is the total wire length and R is the number of buffers. By applying this algorithm iteratively (each time pick one block as the source block), it provides a polynomial-time algorithm for pin assignment and buffer planning for nets among multiple macro blocks. Experimental results demonstrate its efficiency and effectiveness.

In this paper we address the problem of simultaneous routing and buffer insertion. Simultaneous maze routing and buffer insertion under the Elmore delay model have been reported in the literature previously. Such algorithms can take into account both routing obstacles and restrictions on buffer locations. It is well known that Elmore delay is only a first-order approximation of signal delay and hence could be very inaccurate. Moreover, we cannot impose constraints on the transition times of the output signal waveform at the sink or at the buffers on the route. In this paper we extend previously reported algorithm so that accurate delay models (e.g., transmission line model, delay look-up table from SPICE, etc.) can be used We show that the problem of finding a minimum-delay buffered routing path can be formulated as a shortest path problem in a specially constructed weighted graph. By including only the vertices with qualifying transition times in the graph, we guarantee that all transition time constraints are satisfied. Our algorithm can be easily extended to handle buffer sizing and wire sizing. It can be applied iteratively to improve any given routing tree solution. Experimental results show that our algorithm performs well.

Antenna problem is a phenomenon of plasma induced gate oxide degradation. It directly affects manufacturability of VLSI circuits, especially in deep-submicron technology using high density plasma. Diode insertion is a very effective way to solve this problem Ideally diodes are inserted directly under the wires that violate antenna rules. But in today's high-density VLSI layouts, there is simply not enough room for "under-the-wire" diode insertion for all wires. Thus it is necessary to insert many diodes at legal "off-wire" locations and extend the antenna-rule violating wires to connect to their respective diodes. Previously only simple heuristic algorithms were available for this diode insertion and routing problem. In this paper we show that the diode insertion and routing problem for an arbitrary given number of routing layers can be optimally solved in polynomial time. Our algorithm guarantees to find a feasible diode insertion and routing solution whenever one exists. Moreover we can guarantee to find a feasible solution to minimize a cost function of the form /spl alpha/ /spl middot/ L + /spl beta/ /spl middot/ N where L is the total length of extension wires and N is the total number of Was on the extension wires. Experimental results show that our algorithm is very efficient.

In reconfigurable computing, circuits implemented on multi-FPGA systems have to be incrementally modified. Since reconfiguring an FPGA is time-consuming, the time for reconfiguration depends on the number of FPGAs to be reconfigured. Our objective is to reduce the number of such FPGAs. In this paper, we consider the specific problem of incrementally reconfiguring a multi-FPGA system that utilizes the direct interconnection architecture, where routing connections between FPGAs are to neighbors that are near. This problem can be divided into a net addition problem and a net deletion problem. We show that the net addition problem is a generalization of the NP-complete Steiner tree problem. Our algorithm for this problem is based on an adaptation of the Klein-Ravi approximation algorithm for the node-weighted Steiner tree problem. As for the net deletion problem, we prove that it is NP-complete but the problem is solvable in polynomial time for tree topologies. Based on the algorithm for trees, we design an effective heuristic algorithm for the general net deletion problem. Finally, we present an algorithm for solving the incremental reconfiguration problem which handles both placement of new gates and inter-FPGA routing.

As the VLSI technology scaling down, the electromigration problem becomes one of the major concerns in high-performance IC design for both power network and signal interconnects. For a uniform width metal interconnect, the current flows through the driving point is much larger than that flows through the fan-out point since much of current bypasses to the ground through the parasitic capacitance. This causes the lifetime of driving point to be quite shorter than that of fan-out point due to electromigration. In order to avoid breakdown at the driving point, wire sizing is an effective solution. Thus we present a wire shape, of which the current density as well as the lifetime is uniform along the wire. SPICE simulation results show the uniformity of current density of this wire shape. Under the same current density bound, we demonstrate that chip area and power consumption are significantly reduced for this wire shape compared to the uniform width wire. The wire shape functions we derived are continuous. However, it is not necessary to ultra-accurately reproduce the continuous shape on the silicon, since we can round the continuous shape to the nearest available litho width and this will not degrade the uniformity of current density.

Electron projection lithography (EPL) is a leading candidate for next generation lithography (NGL) in VLSI production. The membrane mask used in EPL is divided into sub-fields by struts for structural support. A layout must be partitioned into these sub-fields on mask and then stitched back together by the EPL tool on wafer. To minimize possible stitching errors, partitioning of a mask layout should minimize cuts of layout features in the overlapping area between two adjacent sub-fields. This paper presents the first formulation of the mask layout partitioning problem for EPL as a graph problem. The graph formulation is optimally solved with a shortest path approach. Two other techniques are also presented to speed up computation. Experimental runs on data from a real industry design show excellent results.

Design ECO commonly happens in industry due to constraints or target changes from manufacturing, marketing, reliability, or performance. At each step, designers usually want to modify the existing solution incrementally and keep the design as close as possible to the existing one. In this paper, we address the PSO (Power rail - Signal wire Overlap) problem which solves overlaps between power rails and signal wires due to the changes in power rail design on the top layer of a multiple layer routing region. PSO problems are frequently caused by changes from power delivery system or package design. The new routing solution satisfies the following constraints: 1) Keep the routing of power rails in the new design unchanged. 2) Only the routing of the top two layers is changed. 3) Horizontal (vertical) signal wire segments on the top layer can only move up/down (left/right). At the same time, the new routing solution keeps the routing pattern unchanged. This requires: a) If one end point of a horizontal (vertical) wire segment on the top layer is a fixed pin, this segment can not move. b) If vertical (horizontal) projections of two horizontal (vertical) signal wire segments have overlaps, then the up/down (left/right) relationship should not be changed. c) If two horizontal (vertical) segments belonging to different nets are on the same track, their left/right (up/down) relationship should not be changed as long as the two segments still exist in the new solution. 4) For each signal wire segment, the deviation (i.e., the difference between its new position and the old one) should not exceed the user-defined allowable deviation bound. Different bounds can be set on different segments. We propose two algorithms to solve the PSO problem. Both algorithms guarantee to find a feasible solution as long as one exists. One is faster, while the other makes effort to minimize the total deviation as well as the max deviation. According to time and quality requirements, users can choose an appropriate algorithm to solve the problem. For a set of industrial test circuits, we were able to remove all overlaps between power rails and signal wires with minimal wire deviation.

In this paper, we present a new multilevel circuit partitioning algorithm (dhml) which is guided by design hierarchy. In addition to flat netlist hypergraph, we use user design hierarchy as a hint for partitioning because it already has some implications on connectivity information between logical blocks in the design. Using design hierarchy in partitioning is nontrivial since hierarchical elements in design hierarchy does not necessarily have strong internal connectivity, hence we need to determine whether it is preferable to break up or preserve the hierarchical elements. In order to identify and select the hierarchical elements with strong connectivity, Rent exponent is used. Then, the selected hierarchical elements are used as effective clustering scopes during multilevel coarsening phase. The scopes are dynamically updated (enlarged) while building up a clustering tree so that the clustering tree resembles the densely connected portions of the design hierarchy.We tested our algorithm on a set of large industrial designs in which the largest one has 1.8 million cells, 2.8 million nets, and 11 levels of hierarchy. By exploiting design hierarchy, our algorithm produces higher quality partitioning results than the state-of-the-art multilevel partitioner hMetis [7]. Furthermore, experimental results show that dhml yields significantly more stable solutions, which is helpful in practice to reduce the number of runs to obtain the best result.

As interconnection delay plays an important role in determining circuit performance in FPGAs, timing-driven FPGA routing has received much attention recently. In this paper, we present a new timing-driven routing algorithm for FPGAs. The algorithm finds a routing with minimum critical path delay for a given placed circuit using the Lagrangian relaxation technique. Lagrangian multipliers used to relax timing constraints are updated by subgradient method over iterations. Incorporated into the cost function, these multipliers guide the router to construct routing tree for each net. During routing, the exclusivity constraints on each routing resources are also taken care of to route circuits successfully. Experimental results on benchmark circuits show that our approach outperforms the state-of-the-art VPR router.

The authors propose an elegant formulation of the Maze Routing with Buffer Insertion and Wiresizing problem as a graph-theoretic shortest path problem. This formulation provides time and space performance improvements over previously proposed dynamic programming based techniques. Routing constraints such as wiring obstacles and restrictions on buffer locations and types are easily incorporated in the formulation. They construct a buffer planning (BP)-graph such that the length of every path in this graph is equal to the Elmore delay. Therefore, finding the minimum Elmore delay path becomes a finite shortest path problem. The buffer choices and insertion locations are represented as the vertices in the BP-graph. The interconnect wires are sized by constructing a look-up table for buffer-to-buffer wiresizing solutions. The authors also provide a technique that is able to tremendously improve the runtime. Experiments show improvements over previously proposed methods.

Manufacturability of a design that is processed with shallow-trench isolation (STI) depends on the uniformity of the chemical-mechanical polishing (CMP) step in STI. The CMP step in STI is a dual-material polish for which all previous studies on dummy-feature placement for single-material polish by Kahng et al. (1999), Tian et al. (2000), and Chen et al. (2000) are not applicable. Based on recent semiphysical models of polish-pad bending by Ouma et al (1998), local polish-pad compression by Grillaert (1999) and Smith (1999), and different polish rates for materials present in a dual-material polish by Grillaert (1999) and Tugbawa et al. (1999), this paper derives a time-dependent relation between post-CMP topography and layout pattern density for CMP in STI. Using the dependencies derived, the first formulation of dummy-feature placement for CMP in STI is given as a nonlinear-programming problem. An iterative approach is proposed to solve the dummy-feature placement problem. Computational experience on four layouts from Motorola is given.

In this paper, we present a fast and accurate delay estimation method for buffered interconnects. The interconnect wire is modeled by the transmission line model which is more accurate and efficient than lumped circuit model. For the interconnect wire, we specify the wire shape to be of the form f(x) = ae-bx. Note that if we let b = 0, our work is reduced to uniform wire case. By using first three poles in the transfer function, we derive analytical expressions for calculating delay at any threshold voltage under a finite ramp input. The expressions involved in calculating coefficients in the transfer function are also analytical. We use k-factor equations to estimate delays for buffers. Since the k-factor equations require a loading capacitance for delay computation, we use the effective capacitance technique introduced in [17] to calculate the effective capacitance for each interconnect wire which is connected to a buffer. Therefore, our delay calculation for buffered interconnects is analytical and thus very efficient. Our experiments show that signal waveforms estimated by our method are very close to SPICE's results.

Interconnect design has emerged as one of the major challenges facing chip designers as VLSI manufacturing progresses and gate sizes scale down. Dynamic programming(DP) is an efficient and robust technique for finding optimal solutions to interconnect optimization problems in VLSI design. However, DP's huge memory requirement often limits its effectiveness and sometimes, due to limited storage resources, even makes it impossible to solve a problem of practical size. Since interconnect optimization is often a subprocess embedded in an upper level design procedure, a memory and time efficient implementation of DP can be very favorable to circuit designers. In this paper, we develop a new memory-efficient dynamic programming approach to interconnect optimization problems. Our method utilizes selective storage and recomputation technique. This memory and time efficient algorithm speeds up the dynamic programming method without compromising solution quality. Experiments show tremendous saving, both in storage and time, over traditional dynamic programming algorithms. Our novel approach can also be generalized for other VLSI applications using DP algorithms.

One of the most challenging issues in today's high-performance VLSI design is to ensure high-quality power supply to each individual circuit blocks. Reduced power supply voltage can result in slower cell switching, or even circuit failure. Nevertheless, most floorplanning methodologies have ignored power supply considerations. Thus, the resulting floorplan may suffer from local hot spots and insufficient power supply for certain circuit blocks. In this paper, we present an optimal power supply planning algorithm based on network flow to shorten the current paths from power bumps to local power supply wirings. We have incorporated our algorithm into a floorplanning algorithm for integrated floorplanning and power supply planning. Experimental results are encouraging.

In this paper we present FAST-SP which is a fast block placement algorithm based on the sequence-pair placement representation. FAST-SP has two significant improvements over previous sequence-pair based placement algorithms: 1) FAST-SP translates each sequence pair to its corresponding block placement in O(n log log n) time based on a fast longest common subsequence computation. This is much faster than the traditional O(n2) method by first constructing horizontal and vertical constraint graphs and then performing longest path computations. As a result, FAST-SP can examine more sequence pairs and obtain a better placement solution in less runtime. 2) FAST-SP can handle placement constraints such as pre-placed constraint, range constraint, and boundary constraint. No previous sequence-pair based algorithms can handle range constraint and boundary constraint. Fast evaluation in O(n log log n) time is still valid in the presence of placement constraints and a novel cost function which unifies the evaluation of feasible and infeasible sequence pairs is used. We have implemented FAST-SP and obtained excellent experimental results. For all MCNC benchmark block placement problems, we have obtained the best results ever reported in the literature (including those reported by algorithms based on O-tree and B*-tree) with significantly less runtime. For example, the best known result for ami49 (36.8 mm2) was obtained by a B*-tree based algorithm using 4752 seconds, and FAST-SP obtained a better result (36.5 mm2) in 31 seconds.

Buffer insertion is an efficient technique in interconnect optimization. This paper presents a graph based algorithm for optimal buffer insertion under accurate delay models. In our algorithm, a signal is accurately represented by a finite ramp which is characterized by two parameters, shift time and transition time. Any accurate delay model, such as delay models based on the transmission line model and SPICE simulations, can be incorporated into our algorithm. The algorithm determines the optimal number of buffers and their locations on a wire such that some optimization objective is satisfied. Two typical examples of such optimization objectives are minimizing the 50% threshold delay and minimizing the transition time. Both can be easily determined in our algorithm. We show that the buffer insertion problem can be reduced to a shortest path problem. The algorithm can be easily extended for simultaneous buffer insertion and wire-sizing, and complexity is still polynomial. The algorithm can also be extended to deal with problems such as buffer insertion subject to transition time constraints at any position along the wire.

Slicing tree has been an effective tool for VLSI floorplan design. Floorplanners using slicing tree representation take full advantage of shape and orientation flexibility of circuit modules to find highly compact slicing floorplans. However, slicing floorplans are commonly believed to suffer from poor utilization of space when all modules are hard. For this reason, a large body of literature has recently been devoted to various new representations of non-slicing floorplans to improve space utilization. In this paper, we prove that by using slicing tree representation and compaction, all maximally compact placements of modules can be generated. In conclusion, slicing tree is a complete floorplan representation for all non-slicing floorplans as well.

This paper describes LRoute, a novel router for the popular and scalable hierarchical Complex Programmable Logic Devices (CPLDs). CPLD routing has constraints on routing topologies due to architectural limitations and performance considerations. These constraints make the problem quite different from FPGA routing and render the routing problem more complicated. Extensions of popular FPGA routers like the maze router performs poorly on such CPLDs. There is also little published work on CPLD routing. LRoute uses a different paradigm based on the Lagrangian Relaxation framework in the theory of mathematical programming. It respects the topology constraints imposed and routes a circuit with minimum delay. We tested this router on a set of industry problems that commercial software failed to route. Our router was able to route all of them very quickly.

#%$& (' ) * + , . /'0* 1 2 * 34 657 8* 2 8* 9 /':; : 6 * ?6@8AB *1 1 0* %* C= 8 0 ?D':1 ? E3F * +G'H ?D'0* IJ ?6@ K'0? ?L > M 2 4 0NO ? 8 (P> Q -A : A )7R-SJ$& *F+='T'Q?U'V : > M 2 4 0N * A : AXW-S0YM$(A2!> , [Z \* :MC= 8 '0?D:6* + F M ?D'0* / ]'0 ?D':^3F+ (+] E* % Z 'K' ?D'0 :H > `_ 2 [ . 0NTC 8 ?U'0 )a* + K [ /':% > M 2 -NT * M+ 'M K' 8* * _b 8* 9C 8 ?U'0 D :c *(''-? ?6@]IJ @d Z>_ 2 IJ Ae#1 0 VIJ /)F* + 1 D 9'0?D \*9 G \@ \* K'V* D H3f' @;* ? IJ .* + ` : \* d ? g (+c K'0: * M -N4 > `_ 2 [ h 0NO [* T ^'M: IJ 9C= 8 ?D'LAi H* + F ='0 2 /) 34 E 8*T' ?D E@8 [*h [57 * IJ E D /'.* :6 ('K'0* 4 0I 8*r Q 8* AOx 0 '.y y0_b ?D 8 (Pcz/R0Y,_b [*F ? ) 3X , / / K 8* hNu { 0I W0y`+ 4* `? F* +='0 ^R-SM D > * A 1. INTRODUCTION n| * +H},qr! a* -?D -:-@H 8* :Q* + E 1 c ! #%$ [ (' )r I> E'V . /'0? / c /3F * 9 K'-? ? E ~ = % ?D'/ c'V* '0 ^ IJ h ':9 /Z * @8Af#1 '83F+ ? )73F 6* + * + /'0 0No h ~ ) fNu [* D f'V h 8* :0 ('0* / K >* T D tAih? ? * + E : [ G},qr! , +>@ /'0?4 [_ : %v6z/S>) „0wAak /34 IJ /)J3F 6* +`* & 0 X+> / a -N7* + 'i -N 8* [*f H \*('0 = 'V ( _b ? ?2 0 4Np ?D?6_b \*  : H'0Nu* [ F 6 _ * L ='V * * : ) 8* *r ?D':F L* _b : A # '8@cC= 8 '-? : 0 6* + )i ? = :% ? D D : '= G _ ? : )7+ '/IJ E 2 2 / ^ ='\*k /' Mv6z-z )Oz  )tW>)2‘>)7’>) RVw)> *a* + @` D ` 0*&*('0PJ F >* [ *& ?D'0 :E D 8* Q'>* Z *9v W/wA € ;v WVw)&ƒX+ d *M'-? A1 8* :0 ('0* C= 8 0 ?D':%'0 = “ D >*M 8* [*. ?U'0 D : Ac!> D IJ [ @d3F 6 :% I-'-? ='V_ * 9 \* K X'Q ?D [_ :[* @`: ? ='-?2 * /)1v W/w7 /'9 ?6@ 8 f > ('V* _b ~ / * ? \* , A : ATz S S-SM [* [$a *X3F ? ?7 -* 2 “ D >*Q* -?DI 9 ?D 6* +]IJ [ @c?D'V : K * ? \* 1 -A : A z/S0Y” [* [$(A,x * + 0 )ˆv WVwa 'K+ \* M:-?D ='0?o * [ * K /m8 8* D'-? ?6@^ * M:-? ='0?O >* [ * )7* + Q 2 [ Np K'0 -NO3F+ [+1 2 f 1* + , 0 ( : -NO * f* . 2 , * / tA c [Z \* :]C 8 ?D'0 :;'0? : 6* + . ?D'V* / Š'_ '-? :h3F+ [+ / r* T Z '&'F?D'0 :4 > . 2 [ r 0N C 8 ?D'0 ) * + f /':E . 2 o -N7 [* i+ 'i K' 4 >* [ * _b >* C= 8 0 ?D': *(''-? ?6@ IJ @. Z 2 IJ Ao € `* + i ='0 2 /) 34 c >*1'‰ D ? %@J * 57 * IJ c D /'G* ˆ :6 c 8* Š'Œ :-? ˆ */A•…X Nu ‰::|* + G * ) . ?6* _* '-?o * E'0 M * 9*€3X -_* ='0? [* A …X = / _ :M+8@ 2 [ :('+ _* -_b:0 ('+%* ('\Np 0 K'0* . / d* % I K* + K \* ('8*.Np 0 _ ? 6*Q D ‰'^ ?D 8 (P2A l4+ E *, / * %* (+ Um8 . ,IJ @% [57 * IJ A.! 2 M34 '0 h: IJ H' ? ‹3F 6* +1R-S ? 8 [P> f'0 = 9W-S0YŽ [* AiTNu* [ f * / * t)834 , 'K+='/IJ h'0*f \*,zVW-R-SQ * h p3F+ [+9 X* + h /'3F+ `34 F+ 'VI f * i 2 *€3X K'-? ? ='6 i -Nt ? 8 (P> [$(Aal4+ Q'H :6 * )-Np 0 F', _ ? •3F * +Œy y ? 8 [P> '0 = ŠzVRVY† * )&* + HC 8 ?U'0 D :G'0?D:-_ 6* +  D cv WVwr* 8 -PH 0 k* +='0 ^W0y.+ f* M 1 H* + , 0 D:='-? * ? \*/)& ** 8 Pc? M* + '‰R0S% > * '0Nu* [ ` [*M / * LA #1 '83F+ ? )k3X c 8*H'] %'('V* c:-?D ='0?, * [ HNu 3F 6 :^ I '0?D '0* d D * + E ='0 2 /A nG . qL'-:('0 :U'0 G ?D'0Z>_ 'V* .* (+ Dm> &* h \@ \* K'0* /'-? ?6@Q * X: ? '-? D 8* * ) * @ :,* E D ~ 4* + f K'0Z . ŽI> D -?D'0* 9'-: '\*&* + 4 * _ :k Ail4+ D q'%: IJ ‰C 8 ?U'0 LA‰l4+ H 7 'V* H 0N,qL'-:('0 :U'0 b2 b5

Buffer insertion and wire sizing are critical in deep submicron VLSI design. This paper studies the problem of constructing routing trees with simultaneous buffer insertion and wire sizing in the presence of routing and buffer obstacles. No previous algorithms consider all these factors simultaneously. Previous dynamic programming based algorithm is first extended to solve the problem. However, with the size of routing graph increasing and with wire sizing taken into account, the time and space requirement increases enormously. Then a new approach is proposed to formulate the problem as a series of graph problems. The routing tree solution is obtained by finding shortest paths in a series of graphs. In the new approach, wire sizing can be handled almost without any additional time and space requirement, Moreover, the time and space requirement is only polynomial in terms of the size of routing graph. Our algorithm differs from traditional dynamic programming, and is capable of addressing the problem of inverter insertion and sink polarity. Both theoretical and experimental results show that the graph-based algorithm outperforms the DP-based algorithm by a large margin. We also propose a hierarchical approach to construct routing tree for a large number of sinks.

Macro-block pin assignment and routing are important tasks in physical design planning. Existing algorithms for these problems can be classified into two categories: 1) a two-step approach where pin assignment is followed by routing, and 2) a net-by-net approach where pin assignment and routing for a single net are performed simultaneously. None of the existing algorithms is "exact" in the sense that the algorithm may fail to route all nets even though a feasible solution exists. This remains to be true even if only 2-pin nets between two blocks are concerned. In this paper, we present the first polynomial-time exact algorithm for simultaneous pin assignment and routing for 2-pin nets from one block (source block) to all other blocks. In addition to finding a feasible solution whenever one exists, it guarantees to find a pin-assignment/routing solution with minimum cost /spl alpha//spl middot/W + /spl beta//spl middot/V, where W is the total wirelength and V is the total number of vias. Our algorithm has various applications and is applicable to both global and detailed routing with arbitrary routing obstacles on multiple layers. Experimental results demonstrate its efficiency and effectiveness.

Manufacturability of a design that is processed with shallow trench isolation (STI) depends on the uniformity of the chemical-mechanical polishing (CMP) step in STI. The CMP step in STI is a dual-material polish, for which all previous studies on dummy feature placement for single-material polish [3, 11, 1] are not applicable. Based on recent semi-physical models of polish pad bending [5], local polish pad compression [2, 10], and different polish rates for materials present in a dual-material polish [2, 13], this paper derives a time-dependent relation between post-CMP topography and layout pattern density for CMP in STI. Using the dependencies derived, the first formulation of dummy feature placement for CMP in STI is given as a nonlinear programming problem. An iterative approach is proposed to solve the dummy feature placement problem. Computational experience on four layouts from Motorola is given.

Process technology advances have made multimillion gate field programmable gate arrays (FPGAs) a reality. A key issue that needs to be solved in order for the large-scale FPGAs to realize their full potential lies in the design of their segmentation architectures. Channel segmentation designs have been studied to some degree in much of the literature; the previous methods are based on experimental studies, stochastic models, or analytical analysis. In this paper, we address a new direction for studying segmentation architectures. Our method is based on graph-theoretic formulation. We first formulate a problem of finding the optimal segmentation architecture for two input routing instances and present a polynomial-time optimal algorithm to solve the problem. Based on the solution to the problem, we develop an effective and efficient multi-level matching-based algorithm for general channel segmentation designs. Experimental results show that our method significantly outperforms the previous work. For example, our method achieves average improvements of 18.2% and 8.9% in routability in comparison with other work.

Murata et al. (1996) introduced an elegant representation of block placement called sequence pair. All block-placement algorithms that are based on sequence pairs use simulated annealing where the generation and evaluation of a large number of sequence pairs is required. Therefore, a fast algorithm is needed to evaluate each generated sequence pair, i.e., to translate the sequence pair to its corresponding block placement. This paper presents a new approach to evaluate a sequence pair based on computing longest common subsequence in a pair of weighted sequences. We present a very simple and efficient O(n/sup 2/) algorithm to solve the sequence pair evaluation problem. We also show that using a more sophisticated data structure, the algorithm can be implemented to run in O (n log log n) time. Both implementations of our algorithm are significantly faster than the previous O(n/sup 2/) graph-based algorithm. For example, we achieve 60 /spl times/ speedup over the previous algorithm when input size n = 128. As a result, we can examine a million sequence pairs within one minute for typical input size of placement problems. For all MCNC benchmark block-placement problems, we have obtained the best results ever reported in the literature (including those reported by algorithms based on O tree and B* tree) with significantly less runtime. For example, the best known result for ami49 (36.8 mm/sup 2/) was obtained by a B*-tree-based algorithm using 4752 s and we obtained a better result (36.5 mm/sup 2/) in 31 s.

Chemical-mechanical polishing (CMP) is an enabling technique used in deep-submicrometer VLSI manufacturing to achieve long range oxide planarization. Post-CMP oxide topography is highly related to local pattern density in the layout. To change local pattern density and, thus, ensure post-CMP planarization, dummy features are placed in the layout. Based on models that accurately describe the relation between local pattern density and post-CMP planarization by Stine et al. (1997), Ouma et al. (1998), and Yu et al. (1999), a two-step procedure of global density assignment followed by local insertion is proposed to solve the dummy feature placement problem in the fixed-dissection regime with both single-layer and multiple-layer considerations. Two experiments conducted with real design layouts gave excellent results by reducing simulated post-CMP topography variation from 767 /spl Aring/ to 152 /spl Aring/ in the single-layer formulation and by avoiding cumulative effect in the multiple-layer formulation. The simulation result from single-layer formulation compares very favorably both to the rule-based approach widely used in industry and to the algorithm by Kahng et al (1999). The multiple-layer formulation has no previously published work.

In floorplanning, it is common that a designer wants to have certain modules abutting with one another in the final packing. The problem of controlling the relative positions of an arbitrary number of modules in floorplan design is nontrivial. Slicing floorplan has an advantageous feature in which the topological structure of the packing can be found without knowing the module dimensions. This feature is good for handling placement constraints in general. In this paper, we make use of it to solve the abutment problem in the presence of L- and T-shaped modules. This is done by a procedure which explores the topological structure of the packing and finds the neighborhood relationship between every pair of modules in linear time. Our main contribution is a method that can handle abutment constraints in the presence of L- or T-shaped modules in such a way that the shape flexibility of the soft modules can still be fully exploited to obtain a tight packing. We tested our floorplanner with some benchmark data and the results are promising.

In this paper, we consider the delay minimization problem of an interconnect wire by simultaneously considering buffer insertion, buffer sizing and wire sizing. We consider three cases, namely using no buffer (i.e., wire sizing alone), using a given number of buffers, and using the optimal number of buffers. We provide elegant closed form optimal solutions for all three problems. These closed form solutions are useful in early stages of the VLSI design flow such as logic synthesis and floorplanning.

We propose an elegant formulation of the Maze Routing with Buffer Insertion and Wiresizing pr oblem as a graph-the oretic shortest path problem. This formulation provides time and space performance improvements over previously proposed dynamic-programming based techniques. R outing c onstr aints such as wiring obstacles and restrictions on buffer locations and types are easily inc orporated in the formulation. Furthermore, efficient softwar e routines solving shortest path problems in existing graph applic ation libraries can be applied. We construct a BP-Graph such that the length of every path in this graph is e qual to the Elmore delay. Therefore, finding the minimum Elmore delay path becomes a finite shortest path problem. The buffer choices and insertion locations are repr esente d as the vertices in the BP-Graph. The inter connect wir es are sized by constructing a look-up table for buffer-to-buffer wir esizing solutions. We also provide a technique that is able to tremendously improve the runtime. Experiments show improvements over previously proposed methods.

Chemical-mechanical polishing (CMP) is an enabling technique used in deep-submicron VLSI manufacturing to achieve uniformity in long range oxide planarization [1]. Post-CMP oxide topography is highly related to local spatial pattern density in layout. To change local pattern density, and thus ensure post-CMP planarization, dummy features are placed in layout. Based on models that accurately describe the relation between local pattern density and post-CMP planarization [7; 5; 9], a two-step procedure of global density assignment followed by local insertion is proposed to solve the dummy feature placement problem in the fixed-dissection regime with both single-layer and multiple-layer considerations. Two experiments, conducted with real design data, gave excellent results by reducing post-CMP topography variation from 767Å to 152Å in the single-layer formulation and by avoiding cumulative effect in the multiple-layer formulation. The result from single-layer formulation compares very favorably both to the rule-based approach widely used in industry and to the algorithm in [3]. The multiple-layer formulation has no previously published work.

With the remarkable growth of portable application and the increasing frequency and integration density, power is being given comparable weight to speed and area in IC designs. For the problem of low power decomposition of an XOR gate, if the implementation technology is static CMOS logic, previous research gave an O(n) log (n) time algorithm which assumes that the inputs have both polarities available. But that approach can not be used in dynamic logic. In this paper, we analyze the properties of optimal XOR decompositions in dynamic logic. Based on these optimality properties, we design an optimal algorithm to solve the low power XOR decomposition problem in dynamic logic. We also point out that the previous solution for static logic is not optimal, and give an optimal algorithm which does not even change the input polarities.

In this paper, we consider continuous wire-sizing optimization for delay minimization and ringing control. The optimization is based on a fast and accurate delay estimation method under a finite ramp input, where an analytical expression is also derived to estimate overshoot/undershoot voltage. In this paper we specify the wire shape to be of the form f(x)=ae/sup -bx/, since previous studies under the Elmore delay model suggest that exponential wire shape is effective for delay minimization. The relevant transmission line equations are solved by using the Picard-Carson method. The transient response in the time domain is derived as a function of a and b. The coefficients a and b are then determined such that either the actual delay (50% delay) is minimized, or the wiring area is minimized subject to a delay bound. At the same time, the overshoot/undershoot voltage is bounded to prevent false switching. Our method for delay estimation is very efficient. In all the experiments we performed, it is far more accurate than the Elmore delay model and the estimated delay values are very close to SPICE's results. We also find that in determining the optimal shape which minimizes delay, the Elmore delay model performs as good as our method in terms of the minimum actual delay it achieves, i.e. the Elmore delay model has high fidelity. However, in determining the optimal shape which minimizes area subject to a delay bound the Elmore delay model performs much worse than our method. We also find that the constraint for overshoot/undershoot control does affect optimization results for both delay and area minimization objectives.

We address the problem of inserting repeaters, selected from a library, at feasible locations in a placed and routed network to meet user-specified delay constraints for deep submicron (DSM) technology. We use minimal repeater area by taking advantage of slacks available in the network. Specifically, we transform the problem into an unconstrained optimization problem and solve it by iterative local refinement. We show that the optimal repeater locations and sizes that locally minimize the objective function in the unconstrained problem can be efficiently computed. We have implemented our algorithm and tested it on a set of benchmarks; experimental results are promising.

Murata et al. (1996) introduced an elegant representation of block placement called sequence pair. All block placement algorithms which are based on sequence pairs use simulated annealing where the generation and evaluation of a large number of sequence pairs is required. Therefore, a fast algorithm is needed to evaluate each generated sequence pair, i.e. to translate the sequence pair to its corresponding block placement. This paper presents a new approach to evaluate a sequence pair based on comparing longest common subsequence in a pair of weighted sequences. We present a very simple and efficient O(n/sup 2/) algorithm to solve the sequence pair evaluation problem. We also show that using a more sophisticated data structure, the algorithm can be implemented to run in O(n log n) time. Both implementations of our algorithm are significantly faster than the previous O(n/sup 2/) graph-based algorithm. For example, we achieve 60/spl times/ speedup over the previous algorithm when input size n=128.

We propose an integrated clock tree construction algorithm which performs simultaneous routing, wire sizing and buffer insertion.In existing approaches, wire sizing and clock buffer insertion are typically applied sequentially after a clock tree is generated and routed, i.e., they are done as post-processing steps.None of the known methods can perform clock routing while simultaneously considering wire sizing and buffer insertion.We introduce wire widths and levels of buffers inserted as variables in forming merging segments in the proposed Integrated Deferred-Merge Embedding (IDME) algorithm.As a result, more zero-skew merging locations are made possible and the clock trees generated are zero-skew by construction.Our experiments show that by taking the advantage offered by wire sizing, we are able to minimize phase delay as well as to reduce wire length and use less buffers.

The problem of planning the locations of large number of buffers is of utmost importance in deep submicron VLSI design.Recently, Cong et al in [1] proposed an algorithm to directly address this problem.Given a placement of circuit blocks, a key step in [1] is to use the free space between the circuit blocks for inserting as many buffers as possible.This step is very important because if all buffers can be inserted into existing spaces, no expansion of chip area would be needed.An effective greedy heuristic was used in [1] for this step.In this paper, we give a polynomial-time optimal algorithm for solving the problem of inserting maximum number of buffers into the free space between the circuit blocks.In the case where the "costs" of placing a buffer at different locations are different, we can guarantee to insert maximum number of buffers with minimum total cost.Our algorithm is based on efficient min-cost network-flow computations.

This issue of IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems is devoted to papers that appear in The International Symposium on Physical Design 1999 (ISPD-99) held April 12-14, in Monterey, CA. The symposium provided a high-quality forum for the exchange of ideas and results in critical areas related to the physical design of VLSI systems. This annual symposium evolved from the ACM/SIGDA Physical Design Workshops held during the years 1987-1996 with the first ISPD held in 1997. Its scope included all aspects of physical design, from interactions with behavior- and logic-level synthesis, to back-end performance analysis and verification. We invited all ISPD-99 authors to submit their papers for consideration in the special issue. The submitted papers were divided between the guest editors to avoid potential conflicts of interest. Finally, a total of nine regular-length papers and two short papers were accepted into this special issue. These papers cover a wide range of current physical design topics, including partitioning, floorplanning, placement, routing, interconnect modeling, and design for manufacturability. The accepted papers meet the usual high standard of the IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems.

In floorplanning, it is important to allow users to specify placement constraints. Floorplanning with preplaced constraint was considered recently in Murata et al. (1997) and Young and Wong (1998). In this paper, we address a more general kind of placement constraint called range constraint in which a module must be placed within a given rectangular region in the floorplan. This is a more general formulation of the placement constraint problem and any preplaced constraint can be written as a range constraint. We extend the Wong-Liu algorithm (1986) to handle range constraint. Our main contribution is a novel shape curve computation which takes range constraint into consideration. Experimental results show that the extended floorplanner performs very well and, in particular, it out-performs the floorplanner proposed by Young and Wong (1998) when specialized to handle preplaced modules.

During the routing of global interconnects, macro blocks form useful routing regions which allow wires to go through but forbid buffers to be inserted. They give restrictions on buffer locations. In this paper, we take these buffer location restrictions into consideration and solve the simultaneous maze routing and buffer insertion problem. Given a block placement defining buffer location restrictions and a pair of pins (a source and a sink), we give a polynomial time exact algorithm to find a buffered route from the source to the sink with minimum Elmore delay.

In this paper we present a timing-driven router for symmetrical array-based FPGAs. The routing resources in the FPGAs consist of segments of various lengths. Researchers have shown that the number of segments, instead of wirelength, used by a net is the most critical factor in controlling routing delay in an FPGA. Thus, the traditional measure of routing delay on the basis of geometric distance of a signal is not accurate. To consider wirelength and delay simultaneously, we study a model of timing-driven routing rees, arising from the special properties of FPGA routing architectures. Based on the solutions to the routing-tree problem, we present a routing algorithm that is able to utilize various routing segments with global considerations to meet timing constraints. Experimental results show that our approach is very effective in reducing timing violations.

In this paper, by using calculus of variations, we determine the optimal shape for a wire under the Elmore delay model. Coupling capacitance has been taken into consideration explicitly by treating it as another source of grounded capacitance. Given two wires in parallel, one has uniform width and the other has non-uniform width whose shape is described by a function f(x). Let T/sub D/ be the delay through the non-uniform wire. We determine f(x) such that T/sub D/ is minimized. We also extend our study to the case where a non-uniform wire has two neighboring wires. Our study shows that the optimal shape function satisfies an integral equation. Numerical methods are employed to solve the corresponding differential equation and carry out the integration. We provide an efficient algorithm to find the optimal solution. Experiments show that it only takes several iterations to get the optimal results by using our algorithm. Our experiments also show that the wire delay T/sub D/ is a convex function of the wire width at the driver end.

In floorplanning of VLSI design, it is useful if users are allowed to specify some placement constraints in the packing. One particular kind of placement constraints is to pack some modules on one of the four sides: on the left, on the right, at the bottom or at the top of the final floorplan. These are called boundary constraints. In this paper, we enhanced a well-known slicing floorplanner to handle these boundary constraints. Our main contribution is a necessary and sufficient characterization of the Polish expression, a representation of the intermediate solution in a simulated annealing process, so that we can check these constraints efficiently and can fix the expression in case the constraints are violated. We tested our algorithm on some benchmark data and the performance is good.

Since Asymptotic Waveform Evaluation (AWE) was introduced in [5], many interconnect model order reduction methods via Pad& approximation have been proposed.Although the stability and precision of model reduction methods have been greatly improved, the following important question has not been answered: "What is the error bound in the time domain?".This problem is mainly caused by the "gap" between the frequency domain and the time domain, i.e. a good approximated transfer function in the frequency domain may not be a good approximation in the time domain.All of the existing methods approximate the transfer function directly in the frequency domain and hence can not provide error bounds in the time domain.In this paper, we present new moment matching methods which can provide guaranteed error bounds in the time domain.Our methods are based on the classic work by Teasdale in [l] which performs Pade approximation in a transformed domain by the bilinear conformal transformation s = E.

Article Free Access Share on Simultaneous routing and buffer insertion with restrictions on buffer locations Authors: Hai Zhou Department of Computer Sciences, University of Texas, Austin, TX Department of Computer Sciences, University of Texas, Austin, TXView Profile , D. F. Wong Department of Computer Sciences, University of Texas, Austin, TX Department of Computer Sciences, University of Texas, Austin, TXView Profile , I-Min Liu Department of Electrical and Computer Engineering, University of Texas, Austin, TX Department of Electrical and Computer Engineering, University of Texas, Austin, TXView Profile , Adnan Aziz Department of Electrical and Computer Engineering, University of Texas, Austin, TX Department of Electrical and Computer Engineering, University of Texas, Austin, TXView Profile Authors Info & Claims DAC '99: Proceedings of the 36th annual ACM/IEEE Design Automation ConferenceJune 1999 Pages 96–99https://doi.org/10.1145/309847.309885Published:01 June 1999Publication History 44citation315DownloadsMetricsTotal Citations44Total Downloads315Last 12 Months43Last 6 weeks8 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Dynamically reconfigurable FPGAs have the potential to dramatically improve logic density by time-sharing a physical FPGA device.This paper presents a network-flow baaed partitioning algorithm for dynamically reconfigurable FP-GAS based on the architecture in [2].Experiments show that our approach outperforms the enhanced force-directed scheduling method in [2] in terms of communication cost.

VLSI fabrication has entered the deep sub-micron era and communication between different components has significantly increased. Interconnect delay has become the dominant factor in total circuit delay. As a result, it is necessary to start interconnect planning as early as possible. We propose a method to combine interconnect planning with floorplanning. Our approach is based on the Wong-Liu (1986) floorplaning algorithm. When the positions, orientations, and shapes of the cells are decided, the pin positions and routing of the interconnects are decided as well. We use a multi-stage simulated annealing approach in which different interconnect planning methods are used in different ranges of temperature to reduce running time. A temperature adjustment scheme is designed to give smooth transitions between different stages of simulated annealing. Experimental results show that our approach performs well.

Presents an optimal algorithm to solve the schedule compression problem, which is an open problem proposed by S. Trimberger (1998) for time-multiplexed FPGA partitioning. Time-multiplexed FPGAs have the potential to dramatically improve logic density by time-sharing logic. Schedule compression is an important step in partitioning for time-multiplexed FPGAs and can greatly influence the quality of the partitioning solution. We exactly solve the schedule compression problem by converting it to a constrained min-max path problem. We further extend our algorithm to minimize the communication cost during schedule compression. Experiments show that our optimal algorithm outperforms the existing heuristics and runs very efficiently.

We consider technology mapping of combinational circuits onto complex configurable logic blocks (CLBs) with two levels of LUTs. We show that if the CLB has b bases, a tree network with n nodes can be mapped in O(C/spl middot/n/sup 2b-1/) time, where C is a function dependent on b. b is fired for a given CLB architecture. In particular this algorithm runs in O (n/sup 5/) time when mapping a circuit of n nodes onto the Xilinx XC4000. To the best of our knowledge, this is the first optimal polynomial time algorithm for mapping any nontrivial network onto such a complex CLB architecture. By simplifying the computation, we obtained an O(n/sup 3/) algorithm. The mapping results are comparable to the best NP-hard MILP approach, but our algorithm runs in polynomial time and is much faster in practice. The larger MCNC benchmark circuits were mapped in a few minutes. Our algorithm also maps to CLBs with independent, heterogeneous LUTs as a special case.

We propose a novel buffer insertion algorithm for handling more general networks, whose underlying topology is a directed acyclic graph rather than just a RC tree. The algorithm finds a global buffering which minimizes buffer area while meeting the timing constraints. We use Lagrangian relaxation to translate the timing constraints to a cost in the objective function, and simplify the resulting objective function using the special structure of the problem we are solving. The core of the algorithm is a local refinement procedure, which iteratively computes the optimal buffering for each edge so as to minimize a weighted area and delay objective. The resulting procedure is fast, and takes full advantage of the slack available on noncritical paths.

In floorplanning, it is important to allow users to specify placement constraints.Floorplanning with pm-placed constraint is considered recently in [3, 131.In this paper, we address a more general placement constraint called range constraint, in which a module must be placed within a given rectangular region in the floorplan.This is a more general formulation because any pre-placed constraint can be written as a range constraint.We extend the Wong-Liu algorithm [ll] to handle range constraint.Our main contribution is a novel shape curve computation which takes range constraint into consideration.Experimental results show that the extended floorplanner performs very well and, in particular, it out-performs the floorplauner in [13] when specialized to handle pm-placed modules.

The structural tree-based mapping algorithm is an efficient and popular technique for technology mapping. In order to make good use of this mapping technique in FTGA design, it is desirable to design FPGA logic modules based on Boolan functions which can be represented by a tree of gates (i.e., series-parallel or SP functions). Thakur and Wong [1996a; 1996b] studied this issue and they demonstrated the advantages of designing logic modules as universal SP functions, that is, SP functions which can implement all SP functions with a certain number of inputs. The number of variables in the universal function corresponds to the number of inputs to the FPGA module, so it is desirable to have as few variables as possible in the constructed functions. The universal SP functions presented in Thakur and Wong [1996a; 1966b] were designed manually. Recently, there is an algorithm that can generate these functions automatically [Young and Wong 1997], but the number of variables in the generated functions grows exponentially. In this paper, we present an algorithm to generate, for each n > 0, a universal SP function f n for implementing all SP functions with n inputs or less. The number of variables in f n is less than n 2.376 and the constructions are the smallest possible when n is small ( n ≤ 7). We also derived a nontrival lower bound on the sizes of the optimal universal SP functions (Ω( n log n )).

This paper considers simultaneous gate and wire sizing for general very large scale integrated (VLSI) circuits under the Elmore delay model. We present a fast and exact algorithm which can minimize total area subject to maximum delay bound. The algorithm can be easily modified to give exact algorithms for optimizing several other objectives (e.g., minimizing maximum delay or minimizing total area subject to arrival time specifications at all inputs and outputs). No previous algorithm for simultaneous gate and wire sizing can guarantee exact solutions for general circuits. Our algorithm is an iterative one with a guarantee on convergence to global optimal solutions. It is based on Lagrangian relaxation and "one-gate/wire-at-a-time" greedy optimizations, and is extremely economical and fast. For example, we can optimize a circuit with 27648 gates and wires in 11.53 min using under 23 Mbytes memory on a PC with a 333-MHz Pentium II processor.

The greedy wire-sizing algorithm (GWSA) has been experimentally shown to be very efficient, but no mathematical analysis on its convergence rate has ever been reported. In this paper, we consider GWSA for continuous wire sizing. We prove that GWSA converges linearly to the optimal solution, which implies that the run time of GWSA is linear with respect to the number of wire segments for any fixed precision of the solution. Moreover, we also prove that this is true for any starting solution. This is a surprising result because previously it was believed that in order to guarantee convergence, GWSA had to start from a solution in which every wire segment is set to the minimum (or maximum) possible width. Our result implies that GWSA can use a good starting solution to achieve faster convergence. We demonstrate this point by showing that the minimization of maximum delay and the minimization of area subject to maximum delay bound using Lagrangian relaxation can be sped up by more than 50%.

In this paper, we present a completely new approach to the problem of delay minimization by simultaneous buffer insertion and wire sizing for a wire. We show that the problem can be formulated as a convex quadratic program, which is known to be solvable in polynomial time. Nevertheless, we explore some special properties of our problem and derive an optimal and very efficient algorithm, modified active set method (MASM), to solve the resulting program. Given m buffers and a set of m discrete choices of wire width, the running time of our algorithm is O(mn/sup 2/) and is independent of the wire length in practice. For example, an instance of 100 buffers and 100 choices of wire width can be solved in 0.92 s. In addition, we extend MASM to consider simultaneous buffer insertion, buffer sizing, and wire sizing. The resulting algorithm MASM-BS is again optimal and very efficient. For example, with six choices of buffer size and 10 choices of wire width, the optimal solution for a 15000 /spl mu/m long wire can be found in 0.05 s. Besides, our formulation is so versatile that it is easy to consider other objectives like wire area or power dissipation, or to add constraints to the solution. Also, wire capacitance lookup tables, or very general wire capacitance models which can capture area capacitance, fringing capacitance, coupling capacitance, etc. can be used.

In this paper, we consider the problem of interconnect delay minimization by simultaneous buffer and wire sizing under the Elmore delay model. We first present a polynomial time algorithm SBWS to minimize the delay of an interconnect wire. Previously, no polynomial time algorithm for the problem has been reported in the literature. SBWS is an iterative algorithm with guaranteed convergence to the optimal solution. It runs in quadratic time and uses constant memory for computation. Experimental results show that SBWS is extremely efficient in practice. For example, for an interconnect of 10000 segments and buffers, the CPU time is only 0.255 s. We then extend our result to handle interconnect trees. We present an algorithm SBWS-T which always gives the optimal solution. Experimental results show that SBWS-T is faster than the greedy wire sizing algorithm in practice.

In this paper, we determine the optimal shape function for a bidirectional wire under the Elmore delay model. Given a bidirectional wire of length L, let f(x) be the width of the wire at position x, 0/spl les/x/spl les/L. Let T/sub DR/ be the right-to-left delay. Let T/sub DL/ be the left-to-right delay. Let T/sub BD/=/spl alpha/T/sub D/R+/spl beta/T/sub DL/ be the total weighted delay where /spl alpha//spl ges/0 and /spl beta//spl ges/0 are given weights such that /spl alpha/+/spl beta/=1. We determine f(x) so that T/sub BD/ is minimized. Our study shows that, /spl alpha/=/spl beta/, the optimal shape function is f(x)=c, for some constant c; if /spl alpha//spl ne//spl beta/, the optimal shape function can be expressed in terms of the Lambert's W function as f(x)=-c/sub f//2c/sub 0/((1/W(-ae/sup -bx/))+1), where c/sub f/ is the unit length fringing capacitance, c/sub 0/ is the unit area capacitance, a and b are constants in terms of the given circuit parameters. If /spl alpha/=0 or /spl beta/=0, our result gives the optimal shape function for a unidirectional wire.

Because of the inaccuracy of the Elmore delay model and its inability to handle inductance, it is necessary to use a more accurate delay model in wire-sizing optimization. This paper presents continuous wire-sizing optimization by using a three pole based delay model. Our work is focused on exponential wire shape f(x)=ae/sup -bx/, i.e, we determine a and b such that either delay or area is minimized. Fringing capacitance and inductance, which have been neglected in previous work on wire sizing, are taken into consideration in the delay model. Expressions involved in calculating all three poles are derived with the help of the Picard-Carson method. Since these expressions are all analytical, the delay calculation is very efficient. In our experiments, the delay model is found to be far more accurate than the Elmore delay model. We also observe that in determining the optimal shape that minimizes delay, the Elmore delay model performs as well as our delay model. However, in determining the optimal shape that minimizes area subject to a delay bound, the Elmore delay model performs much worse than our delay model.

In floorplanning of very large scale integration design, it is useful if users are allowed to specify some placement constraints in the packing. One particular kind of placement constraints is to pack some modules on one of the four sides: on the left, on the right, at the bottom, or at the top of the final floorplan. These are called boundary constraints. In this paper, we enhanced a well-known slicing floorplan algorithm to handle these boundary constraints. Our main contribution is a necessary and sufficient characterization of the Polish expression, a representation of the intermediate solutions in the simulated annealing process, so that we can check these constraints efficiently and can fix the expression in case the constraints are violated. We tested our algorithm on some benchmark data and the performance is good.

Due to the scaling down of device geometry and increasing of frequency in deep submicron designs, crosstalk between interconnection wires has become an important issue in very large scale integration (VLSI) layout design. In this paper, we consider crosstalk avoidance during global routing. We present a global routing algorithm based on a new Steiner tree formulation and the Lagrangian relaxation technique. We also give theoretical results on the complexity of the problem.

The logic blocks (CLBs) of a lookup table (LUT) based FPGA consist of one or more LUTs, possibly of different sizes. In this paper, we focus on technology mapping for CLBs with several independent LUTs of two different sizes (called ICLBs). The Actel ES6500 family is an example of a class of commercially available ICLBs. Given a tree network with n nodes, the only previously known approach for minimum area tree-based mapping to ICLBs was a heuristic with running time Θ(nd+1, where d is the maximum indegree of any node. We give an O(n3) time exact algorithm for mapping a given tree network, an improvement over this heuristic in terms of run time and the solution quality. For general networks, an effective strategy is to break it into trees and combine them. We also give an O(n3) exact algorithm for combining the optimal solutions to these trees, under the condition that LUTs do not go across trees. The method can be extended to solve mapping onto CLBs that can be configured into different ICLBs, (e.g. Xilinx' XC4000E).

Due to the scaling down of device geometry and increasing frequency in deep sub-micron designs, crosstalk between interconnection wires has become an important issue in VLSI layout design. In this paper, we consider crosstalk avoidance during global routing. W e present a global routing algorithm based on a new Steiner tree formulation and the Lagrangian relaxation technique. W e also give theoretical results on the complexity of the problem.

An interconnect joining a source and a sink is divided into fixed-length uniform-width wire segments, and some adjacent segments have buffers in between. The problem we considered is to simultaneously size the buffers and the segments so that the Elmore delay from the source to the sink is minimized. Previously, no polynomial time algorithm for the problem has been reported in the literature. In this paper, we present a polynomial time algorithm SBWS for the simultaneous buffer and wire sizing problem. SBWS is an iterative algorithm with guaranteed convergence to the optimal solution. It runs in quadratic time and uses constant memory for computation. Also, experimental results show that SBWS is extremely efficient in practice. For example, for an interconnect of 10 000 segments and buffers, the CPU time is only 0.127 s.

In this paper, we present an algorithm for circuit partitioning with complex resource constraints in large FPGAs. Traditional partitioning methods estimate the capacity of an FPGA device by counting the number of logic blocks, however this is not accurate with the increasing capacity and diverse resource types in the new FPGA architectures. We propose a network flow based method to optimally check whether a circuit or a sub-circuit is feasible for a set of available heterogeneous resources. The feasibility checking procedure is integrated in the FM-based algorithm for circuit partitioning. Incremental flow technique is employed for efficient implementations. Experimental results on the MCNC benchmark circuits show that our partitioning algorithm not only yields good results, but also is efficient. Our algorithm for partitioning with complex resource constraints is applicable for both multiple FPGA designs (e.g. logic emulation systems) and partitioning-based placement algorithms for a single large hierarchical FPGA (e.g. Actel's ES6500 FPGA family).

No abstract available.

Process technology advances will soon make the one-miilion gate FPGA a reality.A key issue that needs to be solved for the large-scale FPGAs to realize their full potential lies in the design of their segmentation architectures [10].Onedimensional segmentation designs have been studied to some degree in much of the literature; most of the previously proposed methods are based on stochastic or analytical analysis.In this paper, we address a new direction for studying segmentation architwtures.Our method is based on graph-theoretic formulation.tire first formulate a net matching problem and present a polynomial-time optimal algorithm to solve the problem.Based on the solution to the problem, we develop an effective and eficient matching-based a!gonthm for FPGA segmentation designs.Eqem.mental results show that our method significantly outperforms previous work. For uample,our method achieves averagw of 18.2% and 8.9% improvements m routability, compared with the work in [lJ] and the most recent work in [7], respectively.More importantly, our approaches are vey flm.ble and can Teadi[y utend to higherorder segmentation designs (e.g., two-or three-dimensional segmentation design, etc), which aTe crucial to the design of large-scale FPGAs.

This paper considers simultaneous gate and wire sizing for general VUI circuits under the E[more delay model.JVepresent a fast and met algorithm which can minimize total area subject to mmimurn delay bound.The algorithm can be easily modl~ed to give ~wct algorithms for optimizing several other objectives (e.g.minimizing maximum delay or minimizing total area subject to arrival time specl~cations at all inputs and outputs).No previous algorithm for simultaneous gate and wire sizing can guarantee met solutions for general circuits.Our algorithm is an iterative one with a guarantee on convergence to global Oph.malsolutions.It is based on hgransian relmtion and "one-gatdwire-at-a-time" local optimi~tions, and is mtremely economical and fast.For example, we can optimize a circuit with 27,648 gates and wires in about 36 minutes using under 23 MB metnory on an IBM RS/6000 worhtation.

Article Shaping a VLSI wire to minimize delay using transmission line model Share on Authors: Youxin Gao Department of Computer Sciences, University of Texas at Austin, Austin, Texas Department of Computer Sciences, University of Texas at Austin, Austin, TexasView Profile , D. F. Wong Department of Computer Sciences, University of Texas at Austin, Austin, Texas Department of Computer Sciences, University of Texas at Austin, Austin, TexasView Profile Authors Info & Claims ICCAD '98: Proceedings of the 1998 IEEE/ACM international conference on Computer-aided designNovember 1998 Pages 611–616https://doi.org/10.1145/288548.289096Published:01 November 1998 22citation222DownloadsMetricsTotal Citations22Total Downloads222Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Time-multiplexed FPGAs have the potential to dramatically improve logic density by time-sharing logic, and have become an active research for reconfigurable computing. The partitioning problem for time-multiplexed FPGAs is different from the traditional partitioning problem in that the nodes have precedence constraints among them, and the widely used iterative improvement partitioning methods such as K&L, FM [14,15] are no longer applicable. All previous approaches [1,2,3] used list scheduling heuristics. In this paper, we present a network flow based algorithm for multi-way precedence constrained partitioning, which can handle the precedence constraints while minimizing the netcut size. The experimental results on the MCNC benchmark circuits show that our algorithm out-performs list scheduling by a big margin, with an average improvement of over 50% for bipartitioning and 20% for multi-way partitioning. 1 Introduction One of the major benefits provided by FPGAs is the ability of ru...

Existing floorplanuers that use shcing floorplans are efficient in runtime and yet can pack modties tightly.Ho~vever,none of them can handle pre-placed modules.In this paper, }ve est end a ~ve~-kno~vnslicing floorplanner [10] to handle preplaced modules.Our main contribution is a novel shape curve computation procedure \vhich can take the positions of the pre-placed moddes into consideration.The shape curve computation procedure is used repeatedly during the floorplanning process to f~y exTloit the shape flexibility of the modules to give a tight packing.Expenmentd results sho~v that the extended floorplanner performs very ~ve~.

Existing approaches to hardware/software co-design separate partitioning and scheduling as two steps. Since partitioning solutions affect scheduling results and vice versa, the existing sequential approach leads to sub-optimal results. In this paper, we explore an integrated hardware/software partitioning and scheduling strategy, where the partitioning process uses the information provided by the scheduling solution as a guide. We present an efficient algorithm for partitioning and scheduling the tasks for execution on the given software (2 CPUs) and hardware (k ASICs or FPGAs) resources with the objective of minimizing the total execution time and the hardware cost. Our algorithm has produced good results for all the task graphs in our experiments.

Previously, two algorithms for the board-level routing problem in FPGA-based logic emulators that use crossbars for interconnection were proposed. However, the performance issue was not considered in the previous algorithms. And they cannot handle routing constraints that may arise from certain timing requirement. So, in this paper we propose a performance-driven routing algorithm for the board-level routing problem that can handle additional routing constraints and reduce the delay of the routing solutions.

In this paper, we present a timing-driven global router for symmetrical-array-based FPGAs. The routing resources in the symmetrical-array-based FPGAs consist of segments of various lengths. Researchers have shown that the number of segments, instead of wirelength, used by a net is the most critical factor in controlling routing delay in an FPGA. Thus, traditional measure of routing delay based on the geometric distance of a signal is not accurate. To consider wirelength and delay simultaneously, we study a model of timing-driven routing trees, arising from the special properties of FPGA routing architectures. We explore the complexity of the routing-tree problem and present efficient and effective approximation algorithms for the problem. Based on the solutions to the routing-tree problem, we present a global-routing algorithm which is able to utilize various routing segments with global consideration to meet the timing constraints. Experimental results on benchmark circuits show that our approach is promising.

In interconnect optimization by wire-sizing, minimizing weighted sink delay has been shown to be the key problem. Wire-sizing with many important objectives such as minimizing total area subject to delay bounds or minimizing maximum delay can all be reduced to solving a sequence of weighted sink delay problems by Lagrangian relaxation [1, 3]. GWSA, first introduced in [10] for discrete wire-sizing and later extended in [2] to continuous wire-sizing, is a greedy wire-sizing algorithm for the weighted sink delay problem. Although GWSA has been experimentally shown to be very efficient, no mathematical analysis on its convergence rate has ever been reported. In this paper, we consider GWSA for continuous wire sizing. We prove that GWSA converges linearly to the optimal solution, which implies that the run time of GWSA is linear with respect to the number of wire segments for any fixed precision of the solution. Moreover, we also prove that this is true for any starting solution. This is a surprising result because previously it was believed that in order to guarantee convergence, GWSA had to start from a solution in which every wire segment is set to the minimum (or maximum) possible width. Our result implies that GWSA can use a good starting solution to achieve faster convergence. We demonstrate this point by showing that the minimization of maximum delay using Lagrangian relaxation can be speed up by 57.7%.

In this paper, we consider the thermal placement problem for gate arrays. We introduce a new combinatorial optimization problem, matrix synthesis problem (MSP), to model the thermal placement problem. Given a list of mn nonnegative real numbers and an integer t, MSP constructs a m/spl times/n matrix out of the given numbers such that the maximum sum among all t/spl times/t submatrices is minimized. We show that MSP is NP-complete and present several provably good approximation algorithms for the problem. We also demonstrate that our thermal placement strategy is flexible enough to allow simultaneous consideration of other objectives such as wiring.

Network flow is an excellent approach to finding min-cuts because of the celebrated max-flow min-cut theorem. For a long time, however, it was perceived as computationally expensive and deemed impractical for circuit partitioning. Recently, the algorithm FBB successfully applied network flow to two-way balanced partitioning. It for the first time demonstrated that network flow was a viable approach to circuit partitioning. In this paper, we present FBB-MW, which is an extension of FBB, to solve the problem of multiway partitioning with area and pin constraints. Experimental results show that FBB-MW outperforms previous approaches for multiple field programmable gate array partitioning. In particular, although FBB-MW does not employ logic replication and logic resynthesis, it still outperforms some other algorithms, which allow replication and resynthesis for optimization.

Previous results show that node replication can be used to reduce the number of cut edges substantially in a partitioned circuit. The node replication approach is particularly useful for fully utilizing pin-limited devices such as multiple field-programmable gate array. Hwang and El Gamal [1992, 1995] formulated the min-cut replication problem, which is to determine min-cut replication sets for the components of a k-way partition such that the cut size of the partition is minimized after the replication. They gave an optimal algorithm for finding min-cut replication sets for a k-way partitioned digraph. However their optimal min-cut replication algorithm does not guarantee min-cut replication sets of minimum sizes. Furthermore, their algorithm is not optimal for hypergraphs. In this paper, we optimally solve the min-area min-cut replication problem on digraphs, which is to find min-cut replication sets with the minimum sizes. More important, we give an optimal solution to the hypergraph min-area min-cut replication problem using a much smaller flow network model. We implemented our algorithms in a package called Hyper-MAMC, and interfaced Hyper-MAMC to the TAPIR package. We compared the replication results by Hyper-MAMC with those obtained by MC-Rep in the TAPIR package on the exact same initial partitions of a set of MCNC Partition93 benchmark circuits. On average, Hyper-MAMC produces 57.3% fewer cut nets and runs much faster than MC-Rep.

In segmented channel routing of row-based FPGA's, the routability and interconnection delays depend on the choice of upper bounds on the number of programmable switches allocated for routing net segments in the channel. Traditionally, the upper bounds for the net segments in the same channel are set uniformly. In this paper, we present algorithms for determining the upper bounds for all of the net segments of a net simultaneously, so that the predefined source-to-sink delay bound on the net is satisfied and the routability of the net is maximized. The upper bounds on net segments in a channel determined by the algorithms in general are nonuniform. Experimental results show that the algorithms can significantly improve routability and reduce delay bound violation as compared with the traditional, uniform upper bound approach.

With the increasing density of VLSI circuits, the interconnection wires are being packed even closer. This has increased the effect of interaction among these wires on circuit performance and hence, the importance of controlling crosstalk. In this article, we consider river routing with crosstalk constraints. Given the positions of the pins in a single-layer routing channel and the maximum tolerable crosstalk between each pair of neighboring nets, we give a polynomial time algorithm to decide whether there is a feasible river routing solution and produce one with minimum crosstalk when it is feasible.

In this paper, we consider non-uniform wire-sizing under theElmore delay model.Given a wire segment of length L, letf(x) be the width of the wire at position x, 0 ≤ x ≤ L.It was shown in [Optimal Wire-sizing formula under the Elmore delay model, Shaping a distributed-RC line to minimize Elmore delay] that the optimal wire-sizing functionwhich minimizes delay is an exponential tapering functionf(x) = ae{-bx}, where a > 0 and b > 0 are constants.Unfortunately, [Optimal Wire-sizing formula under the Elmore delay model, Shaping a distributed-RC line to minimize Elmore delay] did not consider fringing capacitancewhich is at least comparable in size to area capacitance indeep submicron designs.As a result, exponential taperingis no longer the optimal strategy.In this paper, we showthat the optimal wire-sizing function, taking fringing capacitanceinto consideration, is f(x) = \frac{{ - c_f }}{{2c_0 }}(\frac{1}{{W(\frac{{ - c_f }}{{ae^{ - bx} }})}} + 1) whereW(x) = \sum\nolimits_{n = 1}^\infty{\frac{{( - n)^{n - 1} }}{{n!}}} x^n is the Lambert's W function, c{f}and c{0} are the respective fringing capacitance and area capacitanceof wire per unit square, a > 0 and b> 0 are constants.The optimal wire-sizing function degenerates into an exponentialtapering function as c}{f} = 0, and degenerates into asquare-root tapering function (f(x)=\sqrt {b - ax}, where a > 0and b > 0) as c{f} → √.Our experimental results show thatthe optimal wire-sizing function can significantly reduce theinterconnection delay of exponentially tapered wires.In thecase where lower and upper bounds on the wire widths aregiven, the optimal wire-sizing function is a truncated versionof the above function.Finally, our optimal wire-sizing functioncan be iteratively applied to optimally size all the wiresegments in a routing tree for objectives such as minimizingweighted sink delay, minimizing maximum sink delay, orminimizing area subject to delay bounds at the sinks.

Cell characterization data is used by synthesis and timing verificationtools to compile and validate a cell netlist which meets timingconstraints imposed by the designer. Characterization tablescontain data for multiple, simple equations representing a cell's behaviorand are an alternative to the single, monolithic characteristicequation. Data in the table is fit to a function whose form isfixed by the application, and the cellýs response is interpolated fromthe function. Tables can potentially increase accuracy, but large tablescan cause a program to use dramatically more memory and runmuch slower. The optimization of characterization tables, in whichaccuracy is maintained but table size is significantly reduced, is importantif large programs, such as synthesis, are to complete accuratelyand in a reasonable runtime. In this paper we address someof the issues involved in characterizing cells and optimizing characterizationtables quickly and accurately. Experimental results fromthe use of these techniques within AMD for a Synopsys cell libraryis also presented.

We present a completely new approach to the problem of delay minimization by simultaneous buffer insertion and wire sizing for a wire. We show that the problem can be formulated as a convex quadratic program, which is known to be solvable in polynomial time. Nevertheless, we explore some special properties of our problem and derive on optimal and very efficient algorithm to solve the resulting program. Given m buffers and a set of n discrete choices of wire width, the running time of our algorithm is O(mn/sup 2/) and is independent of the wire length in practice. For example, an instance of 100 buffers and 100 choices of wire width can be solved in 3 seconds. Besides, our formulation is so versatile that it is easy to consider other objectives like wire area or power dissipation, or to add constraints to the solution. Also, wire capacitance lookup tables, or very general wire capacitance models which can capture area capacitance, fringing capacitance, coupling capacitance, etc. can be used.

We determine the optimal shape function for a bi-directional wire under the Elmore delay model. Given a bi-directional wire of length L, let f(x) be the width of the wire at position x, 0/spl les/x/spl les/L. Let T/sub DR/ be the right-to-left delay. Let T/sub DL/ be the left-to-right delay. Let T/sub BD/=/spl alpha/T/sub DR/+/spl beta/T/sub DL/ be the total weighted delay where /spl alpha//spl ges/0 and /spl beta//spl ges/0 are given weights such that /spl alpha/+/spl beta/=1. We determine f(x) so that T/sub BD/ is minimized. Our study shows that, if /spl alpha/=/spl beta/, the optimal shape function is f(x)=c, for some constant c; if /spl alpha//spl ne//spl beta/, the optimal shape function can be expressed in terms of the Lambert's W function as f(x)=-(c/sub f/)/(2c/sub 0/)(1/(W(-ae/sup -bx/)+1)), where c/sub f/ is the unit length fringing capacitance, c/sub 0/ is the unit area capacitance, a and b are constants in terms of the given circuit parameters. If /spl alpha/=0 or /spl beta/=0, our result gives the optimal shape function for a uni-directional wire.

With the remarkable growth of portable application and the increasing frequency and integration density, power is being given comparable weight to speed and area in IC designs. In technology mapping, how decomposition is done can have a significant impact on the power dissipation of the final implementation. In the literature, only heuristic algorithms are given for the low power gate decomposition problem. We prove many properties an optimal decomposition tree must have. Based on these optimality properties, we design an efficient exact algorithm to solve the low power gate decomposition problem. Moreover the exact algorithm can be easily modified to a heuristic algorithm which performs much better than the known heuristics.

The channel segmentation design problem for symmetrical FPGAs is the problem of designing segmented tracks in the interconnection channels that provides good net routability and delay performance at the same time. In this paper, we show how to separate the problem into the segmentation design problems of the vertical and horizontal channels by a statistical analysis of the net distribution on a symmetrical FPGA. And we propose an effective approach for segmented channel design when the allowed number of tracks in a channel is fixed and limited.

Buffers in clock trees introduce two additional sources of skew: the first source of skew is the effect of process variations on buffer delays. The second source of skew is the imbalance in buffer loading. We propose a buffered clock tree synthesis methodology whereby we first apply a clustering algorithm to obtain clusters of approximately equal capacitance loading. We drive each of these clusters with identical buffers. A sensitivity based approach is then used for equalizing the Elmore delay from the buffer output to all of the clock nodes. The skew due to load imbalance is minimized concurrently by matching a higher-order model of the load by wire sizing and wire lengthening. We demonstrate how this algorithm can be used recursively to generate low-skew buffered clock trees.

The structural tree-based mapping algorithm is an efficient and popular technique for technology mapping. In order to make good use of this mapping technique, it is desirable to design FPGA logic modules based on Boolean functions which can be represented by a tree of gates (i.e. series-parallel or SP functions). The authors previously studied this issue and demonstrated the advantages of designing logic modules as universal SP functions, i.e. SP functions which can implement all SP functions with a certain number of inputs. However, the universal SP functions presented earlier were designed manually and an automatic generation of universal SP functions was left as an open problem. They present an algorithm to generate, for each n>0, a universal SP function for implementing all n-input SP functions. They also present an efficient Boolean matching algorithm for matching functions to the universal SP functions that we constructed. As it is important to have alternative universal SP functions from which logic-module designers can choose a design taking other criteria (e.g. area, delay, or power) into consideration, they developed an algorithm to generate alternative universal SP functions. In particular, they have found all universal SP functions for n-input SP functions, when n/spl les/6.

With the increasing density of VLSI circuits, interconnection wires are getting packed even closer. This has increased the effect of interaction between wires on circuit performance and hence, the importance of controlling crosstalk. Maze routing is a robust and general approach which can be used in many situations including multi-layer interconnections. In this paper we consider crosstalk avoidance in maze routing. The crosstalk-constrained maze routing problem is first formulated. Then we show it is equivalent to the multi-constrained shortest path problem and is strongly NP-complete. Based on the Lagrangian relaxation technique, an effective heuristic algorithm is designed to solve the problem.

In this paper, we consider the thermal placement problem for gate arrays.We introduce a new combinatorial optimization problem MSP (Matrix Synthesis Problem) to model the thermal placement problem.Given a list of mn non-negative real numbers and an integer t, MSP constructs a m x n matrix out of the given numbers such that the maximum sum among all t x t sub-matrices is minimized.We show that MSP is NP-complete and present several provably good approximation algorithms for the problem.We also demonstrate that our thermal placement strategy is flexible enough to allow simultaneous consideration of other objectives such as wiring.1.

In this paper, we consider the delay minimization problem of a wire by simultaneously considering buffer insertion, buffer sizing and wire sizing. We consider three versions of the problem, namely using no buffer, using a given number of buffers, and using optimal number of buffers. We provide elegant closed form optimal solutions for all these versions.

Network flow is an excellent approach to finding min-cuts because of the celebrated max-flow min-cut theorem.However, for a long time, it was perceived as computationally expensive and deemed impractical for circuit partitioning.Only until recently, FBB [l] successfully applied network flow to two-way balanced partitioning and for the first time demonstrated that network fow was a viable approach to circuit partitioning.In this paper, we present FBB-MW, which is an extension of FBB, to solve the problem of multi-way partitioning with area and pin constraints.Experimental results show that FBB-MW outperforms the FM-based MW-part program in the TAPIR package[lO].1. *This work was partially

Given a set of modules with flexibility in shape, we show that there exists a slicing floorplan F such that area(F ) minf(1 + 1 b p rc ); 5 4 ; (1 + ff)gA total where A total is the total area of all the modules, Amax is the maximum module area, ff = q 2Amax rA total and r 2 is the shape flexibility of each module. Our result shows that slicing floorplans can provably pack modules tightly. 1. INTRODUCTION Floorplan design plays an important role in the design of VLSI circuits in today's deep submicron technology. A slicing floorplan is a floorplan which can be obtained by recursively dividing a rectangle into two parts with either a vertical line or a horizontal line. Since slicing floorplans have very simple solution representations (e.g. slicing tree [4], Polish expression [6] etc.), it is easier to design efficient strategies to search for optimal slicing floorplans. As a result, slicing floorplans are used in many existing floorplanning systems [4, 3, 6, 5]. The only ...

In this paper, we present an algorithm for selecting implementations for rectangular modules given a placement of the modules in multiple rows. A module is a rectangle with pins located on the top and the bottom edges. An implementation of a module is specified by its dimension and a placement of the pins along the top and bottom edges of the module. Our algorithm accepts as input a placement of the modules and a set of possible implementations of each module, and selects an implementation for each module to minimize the total height of the layout. The time complexity of our algorithm is O(NrK/sup r/+K/sup 2/P), where K is the maximum number of implementations for each module, r is the number of rows, N is the total number of modules, and P is the number of pins in the channel. Our algorithm can be applied to the CMOS transistor placement, and has been implemented in the custom cell synthesis system of MCC. We have tested the algorithm on cells selected from the MCNC benchmarks and industry. Reductions of up to 19% in layout area were obtained.

In this paper, we consider a board-level routing problem which is applicable to field-programmable gate arrays (FPGA)-based logic emulation systems such as the Realizer System and the Enterprise Emulation System manufactured by Quickturn Design Systems. For the case where all nets are two-terminal nets, we present an O(n/sup 2/)-time optimal algorithm where n is the number of nets. Our algorithm guarantees 100% routing completion if the number of interchip signal pins on each FPGA chip in the logic emulation system is less than or equal to the number of I/O pins on the chip. Our algorithm is based on iterative computation of Euler circuits in graphs. We also prove that the routing problem with multiterminal nets is NP-complete. Also we suggest one way to handle multiterminal nets using some additional resources.

Logic replication has been shown to be very effective in reducing the number of cut nets in partitioned circuits. Liu et al. (see IEEE Trans. Computer-Aided Design, vol. 14, p. 623-30, May 1995) considered the circuit partitioning problem with logic replication for separating two given nodes and presented an algorithm to determine a partitioning of the minimum possible cut size. In general, there are many possible partitioning solutions with the minimum cut size and the difference in the required amount of replication by these solutions can be significant. Since there is a size constraint on each component of the partitioning in practice, it is desirable to also minimize the amount of replication. In this paper, we present a network-flow based algorithm to determine an optimum replication min-cut partitioning that requires minimum replication. We show that the algorithm can be generalized to separate two given subsets of nodes giving an optimum partitioning of the minimum possible cut size using the least possible amount of replication. We also show that our algorithm can be used to improve the solutions produced by any existing size-constrained replication min-cut partitioning algorithm by reducing the cut size and shrinking the replication set.

Abstract — We consider a switch module routing problem for symmetrical-array field-programmable gate arrays (FPGA’s). This problem was first introduced in [21]. They used it to evaluate the routability properties of switch modules which they proposed. Only an approximation algorithm for the problem was proposed by them. We give an optimal algorithm for the problem based on integer linear programming (ILP). Experiments show that this formulation leads to fast and efficient solutions to practical-sized problems. We then propose a precomputation that eliminates the need to use ILP on-line. We also identify special cases of this problem that reduce to problems for whom efficient algorithms are known. Thus, the switch module routing problem can be solved in polynomial time for these special cases. Using our solution to the switch module routing problem, we propose a new metric to estimate the congestion in each switch module in the FPGA. We demonstrate the use of this metric in a global router. A comparison with a global router guided by the density of the routing channels shows that our metric leads to far superior global and detailed routing solutions. Index Terms—Field-programmable gate array, global routing. I.

We consider the problem of circuit partitioning for multiple-chip implementations. One motivation for studying this problem is the current need for good partitioning tools for implementing a circuit on multiple field programmable gate array (FPGA) chips. We allow duplication of logic gates as it could be used to reduce circuit delay. Circuit partitioning with duplication of logic gates is also called circuit clustering. In this paper, we present a circuit clustering algorithm that minimizes circuit delay subject to both area and pin constraints on each chip, using the general delay model. We develop a repeated network cut technique for finding a cluster that is bounded by both area and pin constraints. Our algorithm achieves optimal delay under either the area constraint only or the pin constraint only. Under both area and pin constraints, our algorithm achieves optimal delay in most cases. We outline the condition under which the nonoptimality occurs, and we show that the condition rarely occurs in practice. We tested our algorithm on a set of benchmark circuits, and consistently obtained optimal or near-optimal delays.

Unlike traditional ASIC technologies, the geometric structures of clock trees in a field-programmable gate array (FPGA) are usually fixed and cannot be changed for different circuit designs. Furthermore, the clock pins are connected to the clock trees via programmable switches. As a result, the load capacitances of a clock tree may be changed, depending on the utilization and distribution of logic modules in an FPGA. It is possible to minimize clock skew by carefully distributing the load capacitances or, equivalently, the logic modules used for the circuit design implementation. In this paper we present an algorithm for selecting logic modules used for circuit placement such that the clock skew is minimized. The algorithm can be applied to a variety of clock tree architectures, including those used in the major commercial FPGA's. The algorithm can also be extended to handle buffered clock trees and multiple clock trees Experimental results show that the algorithm can reduce clock skews significantly as compared with the traditional placement algorithms which do not consider clock skew minimization.

We consider a board-level routing problem applicable to FPGA-based logic emulation systems such as the Realizer System [Varghese et al. 1993] and the Enterprise Emulation System [Maliniak 1992] manufactured by Quickturn Design Systems. Optimal algorithms have been proposed for the case where all nets are two-terminal nets [Chan and Schlag 1993; Mak and Wong 1995]. We show how multiterminal nets can be handled by decomposition into two-terminal nets. We show that the multiterminal net decomposition problem can be modeled as a bounded-degree hypergraph-to-graph transformation problem where hyperedges are transformed to spanning trees. A network flow-based algorithm that solves both problems is proposed. It determines if there is a feasible decomposition and gives one whenever such a decomposition exists.

Delay, power, skew, area, and sensitivity are the most important concerns in current clock-tree design.We present in this paper an algorithm for simultaneously optimizing the above objectives by sizing wires and buers in clock trees.Our algorithm, based o n L agrangian relaxation method, can optimally minimize delay, power, and area simultaneously with very low skew and sensitivity.With linear storage overall and linear runtime per iteration, our algorithm is extremely economical, fast, and accurate; for example, our algorithm can solve a 6201-wire-segment clock-tree p r oblem using about 1-minute runtime and 1.3-MB memory and still achieve pico-second precision on an IBM RS/6000 workstation.

In this paper, we consider non-uniform wire-sizing.Given a wire s e gment of length L, let f(x) be the width of the wire at position x, 0 x L .We show that the optimal wiresizing function that minimizes the Elmore delay through the wire i s f ( x ) = ae bx , where a > 0 and b > 0 are c onstants that can be c omputed i n O (1) time.In the case where lower bound (L > 0 ) and upper bound (U > 0 ) on the wire widths are given, we show that the optimal wire-sizing function f(x) is a truncated version of ae bx that can also be determined i n O (1) time.Our wire-sizing formula can be iteratively applied to optimally size the wire s e gments in a routing tree.

Technology mapping requires the unmapped logic network to be represented in terms of base functions, usually two-input NORs and inverters.Technology decomposition is the step that transforms arbitrary networks to this form.Typically, such decomposition schemes ignore the fact that certain circuit elements can be mapped more eciently by treating them separately during decomposition.Multiplexers are one such category of circuit elements.They appear very naturally in circuits, in the form of datapath elements and as a result of synthesis of CASE statements in HDL speci cations of control logic.Mapping them using multiplexers in technology libraries has many advantages.In this paper, we give an algorithm for optimally decomposing multiplexers, so as to minimize the delay of the network, and demonstrate its eectiveness in improving the quality of mapped circuits.

No abstract available.

No abstract available.

We consider non-uniform wire-sizing for general routing trees under the Elmore delay model. Three minimization objectives are studied: (1) total weighted sink-delays; (2) total area subject to sink-delay bounds; and (3) maximum sink delay. We first present an algorithm NWSA-wd for minimizing total weighted sink-delays based on iteratively applying the wire-sizing formula in [1]. We show that NWSA-wd always converges to an optimal wire-sizing solution. Based on NWSA-wd and the Lagrangian relaxation technique, we obtained two algorithms NWSA-db and NWSA-md which can optimally solve the other two minimization objectives. Experimental results show that our algorithms are efficient both in terms of runtime and storage. For example, NWSA-wd, with linear runtime and storage, can solve a 6201-wire segment routing-tree problem using about 1.5-second runtime and 1.3-MB memory on an IBM RS/6000 workstation.

Logic replication has been shown to be very effective in reducing the number of cut nets in partitioned circuits. L.T. Liu et al. (1995) considered the circuit partitioning problem with logic replication for separating two given nodes and presented an algorithm to determine a partitioning of the minimum possible cut size. In general, there are many possible partitioning solutions with the minimum cut size and the difference of their required amounts of replication can be significant. Since there is a size constraint on each component of the partitioning in practice, it is desirable to also minimize the amount of replication. In this paper, we present a network-flow based algorithm to determine an optimum replication min-cut partitioning that requires minimum replication. We show that the algorithm can be generalized to separate two given subsets of nodes and determine an optimum partitioning of the minimum possible cut size using the least possible amount of replication. We also show that our algorithm can be used to improve the solutions produced by any heuristic replication min-cut partitioning algorithm by reducing the cut size and shrinking the replication set.

With the increasing density of VLSI circuits, the interconnection wires are getting packed even closer. This has increased the effect of interaction between these wires on circuit performance and hence, the importance of controlling crosstalk. We consider river routing with crosstalk constraints. Given the positions of the pins in a single-layer routing channel and the maximum tolerable crosstalk between each pair of nets, we give a polynomial time algorithm to decide whether there is a feasible river routing solution and produce one with minimum crosstalk whenever the problem is feasible.

In high level synthesis, after the binding stage, multiplexor network is generated to connect the outputs of modules (functional-units/registers) to the inputs of modules. In this paper we present an algorithm to generate a 2-to-1 multiplexor network with minimum number of multiplexors. Our algorithm is based on iteratively solving minimum vertex cover problems. Experimental results show that our approach obtains 8 to 25% improvement over a direct multiplexor-forest approach.

We present a general multilayer area router for performing detailed routing in integrated circuits. This router is based on a novel grid construction scheme which considers the differing design rules of the routing layers and produces more wiring tracks than a uniform grid scheme. Our router is very general and flexible and is designed to handle all the physical constraints of a CMOS custom cell layout problem for an arbitrary number of routing layers. The router has been incorporated into the Custom Cell Synthesizer project at MCC. It has produced better results than uniform gridded routers and improved the capability of the system by providing routing flexibility and supporting features needed to handle a wide range of design styles in generating CMOS custom cells.

Design-rule checking, whose efficiency depends greatly on the speed in finding an object's neighbors, is an indispensable component of any VLSI design process. Given a design, the objects it contains are usually represented by their smallest enclosing rectangles, and neighbor search is defined as the operation to find, among the collection of rectangles, the ones that are within the specified distance of a rectangle. Commonly, the rectangles are stored in a tree structure, and a region query that searches the tree starting at its root is used to find a rectangle's neighbors. In this paper, we introduce the hinted quad tree, or HQT, that supports neighbor searches directly without always starting a search at the root of the tree. We show that HQT achieves the highest neighbor-search performance among the data structures compared and uses a reasonable amount of storage.

We consider the problem of bipartitioning a circuit into two balanced components that minimizes the number of crossing nets. Previously, Kernighan and Lin type (K&L) heuristics, simulated annealing approach, and analytical methods were given to solve the problem. However, network flow (max-flow min-cut) techniques were overlooked as viable heuristics to min-cut balanced bipartition due to their high complexity. In this paper we propose a balanced bipartition heuristic based on repeated max-flow min-cut techniques, and give an efficient implementation that has the same asymptotic time complexity as that of one max-flow computation. We implemented our heuristic algorithm in a package called FBB. The experimental results demonstrate that FBB outperforms K&L heuristics and analytical methods in terms of the number of crossing nets, and our efficient implementation makes it possible to partition large circuit netlists with reasonable runtime. For example, the average elapsed time for bipartitioning a circuit S35932 of almost 20 K gates is less than 20 min on a SPARC10 with 32 MB memory.

A switch module M with W terminals on each side is said to be universal if every set of nets satisfying the dimensional constraint (i.e., the number of nets on each side of M is at most W ) is simultaneously rout able through M . In this article, we present a class of universal switch modules. Each of our switch modules has 6 W switches and switch-module flexibility three (i.e, F s =3). We prove that no switch module with less than 6 W switches can be universal. We also compare our switch modules with those used in the Xilinx XC4000 family FPGAs and the antisymmetric switch modules (with F S =3) suggested by Rose and Brown [1991]. Although these two kinds of switch modules also have F S =3 and 6 W switches, we show that they are not universal. Based on combinatorial counting techniques, we show that each of our universal switch modules can accommodate up to 25% more routing instances, compared with the XC4000-type switch module of the same size. Experimental results demonstrate that our universal switch modules improve routability at the chip level. Finally, our work also provides a theoretical insight into the important observation by Rose and Brown [1991] (based on extensive experiments) that F S =3 is often sufficient to provide high routability.

The need for a two-way interaction between logic synthesis and FPGA logic module design has been stressed recently. Having a logic module that can implement many functions is a good idea only if one can also give a synthesis strategy that makes efficient use of this functionality. Traditionally, technology mapping algorithms have been developed after the logic architecture has been designed. We follow a dual approach, by focusing on a specific technology mapping algorithm, namely, the structural tree-based mapping algorithm, and designing a logic module that can be mapped efficiently by this algorithm. It is known that the tree-based mapping algorithm makes optimal use of a library of functions, each of which can be represented by a tree of AND, OR, and NOT gates (series-parallel or SP functions). We show how to design a SP function with a minimum number of inputs that can implement all possible SP functions with a specified number of inputs. For instances, we demonstrate a seven-input SP function that can implement all four-input SP functions. Mapping results show that, on an average, the number blocks of this function needed to map benchmark circuits are 12% less than those for Actel's ACT1 logic modules. Our logic modules show a 4% improvement over ACT1, if the block count is scaled to take into account the number of transistors needed to implement different logic modules.

In this paper, we consider a board-level routing problem which is applicable to FPGA-based logic emulation systems such as the Realizer system [5] and the Enterprise Emulation System [3] manufactured by Quickturn Systems. For the case where all nets are two-terminal nets, we present an O(n 2 )-time optimal algorithm where n is the number of nets. Our algorithm guarantees 100% routing completion if the number of inter-chip signal pins on each FPGA chip in the logic emulation system is less than or equal to the number of I/O pins on the chip. Our algorithm is based on iteratively finding Euler circuits in graphs. We also prove that the routing problem with multiterminal nets is NP-complete. 1 Introduction Introduced in the mid-1980's, FPGAs [1,2] combine the programmability of programmable logic devices and the scalable interconnection structure of traditional gate arrays. This combination results in programmable devices with much higher logic density. Compared with tradition...

FPGA technologies employ replicated programmable logic blocks. These can be look-up tables or more complex macro-cells. In this paper, we give a method to design macro-cell logic modules, based on an extension of classical work on designing Universal Logic Modules (ULM ). Specifically, we give a technique to design a class of logic modules that specialize to a large number of functions under complementations and permutations of inputs, bridging of inputs and assignment of 0/1 to inputs. Thus, a lot of functions can be implemented using a single logic module. The significance of our work lies in our ability to generate a large set of such logic modules. A choice can be made from this set based on design criteria. We demonstrate the technique by generating a set of 471 8-input functions that have a much higher coverage than the 8-input cells employed by Actel's FPGAs. Our functions can specialize to up to 23 times the number of functions that Actel functions can. We also show t...

Pad assignment with signal integrity optimization is very important for high-speed VLSI design. In this paper, an efficient method is proposed to effectively minimize both simultaneous switching noise and crosstalk that are inevitably caused by package inductance and capacitance during the design of high-speed/high-bandwidth circuits. Due to its efficiency, our algorithm can be incorporated into existing circuit floorplanning and placement schemes for the co-design of VLSI and packaging. For a set of industrial circuits/packages tested in our experiment, on the average, our method achieves a 16.8% reduction of total electrical noise when compared with the conventional design rule of thumb popularly used by circuit designers.

We consider a board-level routing problem applicable to FPGA-based logic emulation systems such as the Realizer System (Varghese et al., (1993)) and the Enterprise Emulation System (Maliniak (1992)) manufactured by Quickturn Systems. Optimal algorithms have been proposed for the case where all nets are two-terminal nets. In this paper, we show how multi-terminal nets can be handled by decomposition into two-terminal nets. We show that the multi-terminal net decomposition problem can be modelled as a bounded-degree hypergraph-to-graph transformation problem where hyper-edges are transformed to spanning trees. A network flow-based algorithm that solves both problems is proposed. It determines if there is a feasible decomposition and gives one whenever such a decomposition exists.

Hwang and El Gamal (1992, 1995) formulated the min-cut replication problem, which is to determine min-cut replication sets for the components of a k-way partition such that the cut size of the partition is minimized after the replication. They gave an optimal algorithm for finding min-cut replication sets for a k-way partitioned digraph. However, their optimal min-cut replication algorithm does not guarantee min-cut replication sets of minimum sizes. Furthermore, their algorithm is not optimal for hypergraphs. In this paper, we optimally solve the min-area min-cut replication problem on digraphs, which is to find min-cut replication sets with the minimum sizes. More importantly, we give an optimal solution to the hypergraph min-area min-cut replication problem using a much smaller flow network model. We implemented our algorithms in a package called Hyper-MAMC, and interfaced Hyper-MAMC to the TAPIR package. On average, Hyper-MAMC produces 57.3% fewer cut nets and runs much faster than MO-Rep in the TAPIR package, on the same initial partitions of a set of MCNC Partition93 benchmark circuits.

Unlike traditional ASIC routing, the feasibility of routing in FPGAs is constrained not only by the available space within a routing region, but also by the routing capacity of a switch block. Recent work has established the switch-block capacity as a superior congestion-control metric for FPGA global routing. However, the work has two deficiencies: (1) its algorithm for computing the switch-block capacity is not efficient, and (2) it, as well as the other recent works only modeled one type of routing segments-single-length lines. To remedy the deficiencies, we present in this paper efficient algorithms for obtaining the switch-block capacity and a graph modeling for routing on the new generation FPGAs with a versatile set of segment lengths. Experiments show that our algorithms dramatically reduce the run times for obtaining the switch-block capacities. Experiments with a global router based on the switch-block and channel densities for congestion control show a significant improvement in the area performance, compared with one based on the traditional congestion metric.

Switch modules are the most important component of the routing resources in FPGAs and FPICs. The quality of switch modules greatly affects FPGA/FPIC routing solutions. The switch-module design problem was studied by K. Zhu et al. (1993). In order to analyze the routability of designed switch modules, a heuristic algorithm based on network-flow techniques was proposed. In this paper, we mathematically show that the network-flow based algorithm has provably good performance with the bounds 5 and 5/4 away from the optima for two types of switch modules, respectively. Based on the analyses, we developed a new method for designing switch modules. Experimental results show that our designed switch modules significantly improve routability, compared with those by K. Zhu et al. Extensive experiments also show that the network-flow based algorithm is highly accurate and runs very efficiently.

A placement scheme that considers both electrical performance requirements and thermal behavior for the high-performance multichip modules is described in this paper. Practical thermal models are used for placement of high-speed chips in multichip module packages under two different cooling environments: conduction cooling and convection cooling. Placement methods are modified to optimize conventional electrical performance and chip junction temperatures.

We address the technology mapping problem for lookup table FPGAs. The area minimization problem for mapping K-bounded networks, consisting of nodes with at most K inputs using K-input lookup tables is known to be NP-complete for K/spl ges/5. The complexity was unknown for K=2, 3, and 4. The corresponding delay minimization problem (under the constant delay model) was solved in polynomial time by the flow-map algorithm, for arbitrary values of K. We study the class of K-bounded networks, where all nodes have exactly K inputs. We call such networks K-exact. We give a characterization of mapping solutions for such networks. This leads to a polynomial time algorithm for computing the simultaneous area and delay minimum mapping for such networks using K-input lookup tables. We also show that the flow-map algorithm minimizes the area of the mapped network as well, for K-exact networks. We then show that for K=2 the mapping solution for a 2-bounded network, minimizing the area and delay simultaneously, can be easily obtained from that of a 2-exact network derived from it by eliminating single input nodes. Thus the area minimization problem for 2-input lookup tables can be solved in polynomial time, resolving an open problem.

In this paper, a floorplanner for low power designs is presented. Our objective is to optimize total power consumption and area during the selection and placement of circuit modules. Furthermore, our method considers the reduction of power line noises, thermal reliability problems, and performance requirements.

With the increasing density of VLSI circuits, the interconnection wires are getting packed even closer. This has increased the effect of interaction between these wires on circuit performance and hence, the importance of controlling crosstalk. We consider the gridded channel routing problem where, specifically, the channel has 3 routing layers in the VHV configuration. Given a horizontal track assignment for the nets, we present an optimal algorithm for minimizing the crosstalk between vertical wiring segments in the channel by finding an optimal vertical layer assignment for them. We show an algorithm that minimizes total crosstalk between between wires on the same V layer on adjacent columns of the grid in O(/spl nu/ log /spl nu/) time using O(/spl nu/) memory, where the channel has /spl nu/ columns. We then extend this algorithm to consider crosstalk between wires in non-adjacent columns and between wires on different layers.

Existing over-the-cell channel routers assume that the orientations of the cells are fixed. In practice, it is quite common that each cell can be horizontally flipped. This pin rearrangement flexibility should be used by over-the-cell routers to further reduce channel routing area. Given a placement of cells in multiple rows with pin terminals at the top and bottom edges of the cells and each cell can be flipped. The objective is to select an orientation for each cell and a set of net segments to be routed over the cells such that the final routing area is minimized. In this paper, we assume the HCVD cell model, i.e., power/ground buses run through the middle of each cell row horizontally and one layer is available for over-the-cell routing. For this model, it suffices to focus on over-the-cell routing for each individual cell row. We present a branch-and-bound optimal algorithm to maximize the total weight of the net segments to be routed in both upper and Lower over-the-cell regions. With minor modifications, our algorithm is applicable to simultaneously consider pin assignment and over-the-cell routing. The proposed algorithm has been implemented and tested on a set of industrial examples. Reduction in total channel densities of up to 37% was obtained using a reasonable amount of CPU time.>

In this paper we consider two channel pin assignment problems which take circuit performance into account. The first one is the module implementation selection problem. We are given a net span bound for each critical net and each module has several possible placements of its pins. Our objective is to minimize channel density while satisfying net span constraints. We proved that this problem is NP-complete. For the case when each module has at most 2 pin placements, the problem can be transformed to the 2-SAT problem and hence is polynomial time solvable. We present a heuristic based on this algorithm to solve the general case. The second problem we consider is the module shifting problem. We are given a set of modules whose relative ordering is fixed on each side of the channel but their exact positions are not fixed. We present a polynomial time algorithm to test the feasibility of satisfying the net span constraints by shifting the modules. The algorithm is based on formulating the problem as a special integer linear programming problem which is solvable in polynomial time. We also extend our algorithms to handle multiple channels.>

This paper addresses the problem of circuit clustering for delay minimization, subject to area capacity constraints. We use the general delay model, for which only heuristic solutions were known. We present an optimum polynomial-time algorithm for combinational circuits under this model. Our algorithm can be generalized to solve the problem under any monotone clustering constraint.

We study in this paper the net assignment problem subject to the capacity constraint, selection constraint and routing constraint. Given two adjacent channels separated by a cell row, and a set of nets in each of the two channels, this problem is to assign to the cell row a subset of nets in each channel such that without violating any given constraint, the sum of the remaining densities of the two channels is minimized. The capacity constraint requires the density caused by the nets, which are assigned to the cell row, to be no more than a user-specified number k, where k is no more than the number of tracks available for routing over that cell row. The selection constraint specifies in each channel the subset of nets which are candidates to be assigned to the cell row. The routing constraint requires each net to be either completely assigned to the cell row or to stay in its channel. This problem can find its application in modeling a practical over-the-cell routing problem in which the whole region over the cell row is two-layer routable for the nets in the two adjacent channels. We present an optimal algorithm to solve this problem and provide experimental results to support our algorithm.

In segmented channel routing of row-based FPGAs, the routability and interconnection delays depend on the choice of the upper bounds on the number of programmable switches used in routing net segments in the channel.Traditionally, the upper bounds for the net segments in the same channel are set uniformly.In this paper, we present algorithms for determining the upper bounds for all net segments of a net simultaneously, so that the prede ned source-to-sink delay bound on the net is satis ed and the routability o f t h e net is maximized.The upper bounds on net segments in a channel thus in general are non-uniform.Preliminary experimental results show that the algorithms can signi cantly improve routability and reduce delay bound violation as compared with the traditional approach.

Unlike traditional ASIC technologies, the geometrical structures of clock trees in an FPGA are usually xed and cannot be changed for dierent circuit designs.Moreover, the clock pins are connected to the clock trees via programmable switches.As a result, the load capacitances of a clock tree may b e c hanged, depending on the utilization and distribution of logic modules in an FPGA.It is possible to minimize clock s k ew by distributing the load capacitances, or equivalently the logic modules used by the circuit design, carefully according to the circuit design.In this paper we present an algorithm for selecting logic modules used for circuit placement such that the clock s k ew is minimized.The algorithm can be applied to a variety of clock tree architectures, including those used in major commercial FPGAs.Furthermore, the algorithm can be extended to handle buered clock trees and multi-phase clock trees.Experimental results show that the algorithm can reduce clock s k ews signi cantly as compared with the traditional placement algorithms which do not consider clock s k ew minimization.

In this paper, we present a layer assignment method for high-performance multi-chip module environments. In contrast with treating global routing and layer assignment separately, our method assigns nets to layers while considering preferable global routing topologies simultaneously. We take transmission line effects into account to avoid noise in high-speed circuit packages. The problem is formulated as a quadratic Boolean programming problem and an algorithm is presented to solve the problem after linearization. Our method is applied to a set of benchmark circuits to demonstrate the effectiveness.

We consider the problem of minimizing the number of logic modules for Actel 2 or Actel 3 sequential circuits. We make use of the fact that if a flip-flop is the only destination of its driving combinational block, then both the flip-flop and the combinational block can be put in a sequential module. Retiming technique is applied to minimize the number of resistors that can not be merged with combinational blocks. We formulate the problem as an integer linear program. We show that the constraint matrix of the integer program is totally unimodular. As a result, we can solve our logic module minimization problem optimally by solving the linear relaxation of the integer program.>

Existing over-the-cell channel routers assume that the orientations of the cells are fixed. In practice, it is quite common that each cell can be horizontally flipped. This pin rearrangement flexibility should be used by over-the-cell routers to further reduce channel routing area. Given a placement of cells in multiple rows with pin terminals at the top and bottom edges and each cell can be flipped. The objective is to select an orientation for each cell and a set of net segments to be routed over the cells such that the final routing area is minimized. We present an optimal algorithm to maximize the total weights of the net segments to be routed in over-the-cell routing regions.>

We study in this paper the problem of minimizing channel density by simultaneously shifting the blocks that form the two sides of a channel and the terminals on the boundary of each block. Several special cases of this problem have been investigated, but no optimal algorithm was known for the general case. We present an optimal algorithm for solving this problem. For long channels, we also propose effective heuristic techniques to speed up our algorithm. Extensions as well as applications of our algorithms to detailed routing in building-block layout design are also discussed.>

Rosenberg compared linked lists, quad trees with bkector lists, and W trees, and

Article Free Access Share on Optimal clustering for delay minimization Authors: Rajmohan Rajaraman View Profile , D. F. Wong View Profile Authors Info & Claims DAC '93: Proceedings of the 30th international Design Automation ConferenceJuly 1993 Pages 309–314https://doi.org/10.1145/157485.164907Published:01 July 1993Publication History 43citation446DownloadsMetricsTotal Citations43Total Downloads446Last 12 Months35Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We address the problem of designing switch modules for FPGAs and FPICs to maximize routability under area and delay constraints. The switch module design problem is closely related to two-dimensional segmentation design for FPGAs and FPICs. We study the properties of switch modules and present an algorithm for switch module design. We also present an algorithm to analyze the routability of a given switch module.

Given a building-block layout of rectangular modules, the routing area is to be decomposed into straight and L-shaped channels and routed in a certain order. Since straight channels are easier to route and channel routers usually produce near-optimal results, it is desirable to minimize the number of L-shaped channels used in such a decomposition. An algorithm for minimizing the number of L-shaped channels used in the routing area decomposition is presented. The algorithm is based on a careful study of the structure of layouts of rectangular modules and a transformation of the original problem to a graph theoretical problem. For examples of up to 136 channels, the algorithm took less than one tenth of a second on a SUN SPARC station 1 to finish the computation and obtained up to 29% reduction in the mumber of L-shaped channels over the results produced by the algorithm of W.M. Dai et al. (1985).>

Considers in this paper the problem of shifting vias to obtain more compactable channel routing solutions. Let S be a grid-based two-layer channel routing solution. Let v/sub c/, w/sub c/ be the number of grid points on column c that are occupied by vias, horizontal wires in S, respectively. The authors define the expected height of columns c in S to be h/sub c/=Av/sub c/+Bw/sub c/+C, where A, B, C are some design rule dependent constants. A column in S is said to be a critical column if it has maximum expected height among all columns in S. Let H/sub S/=max/sub c/h/sub c/ be the expected height of the critical column(s) of S. H/sub S/ is an estimation of the height of S after compaction. The authors show that the problem of shifting vias to minimize H/sub S/ can be solved optimally in polynomial time.>

The channel segmentation design problem for row-based field-programmable gate arrays (FPGAs) is to design a segmented channel to maximize the probability of successful routing. An algorithm which takes an arbitrary net distribution and an integer K (specifying the maximum number of segments allowed in routing a net) as inputs, and automatically generates a segmented channel which is most suitable for K-segment channel routing is presented. The algorithm was tested extensively over various net distributions. An algorithm for segmented channel routing based on reducing the problem to the maximum independent set problem for undirected graphs is also presented.>

A linear-time optimal algorithm for minimizing the density of a channel (with exits) by permuting the terminals on the two sides of the channel is presented. It compares favorably with the near-optimal algorithm of J. Cong and K.-Y. Khoo (1991) that runs in superlinear time. The present algorithm has important applications in hierarchical layout design of integrated circuits. In addition, it is shown that the problem of minimizing wire length by permuting terminals is NP-hard in the strong sense.>

A VLSI two-layer channel router designed to find solutions which minimize both wiring area and number of vias simultaneously is presented. The method, called topological channel routing, analyzes the topological relationship of wires before the wires are mapped onto the channel. A unique layout design rule called an interleaving mesh is used. The interleaving mesh prohibits long wires on one layer from overlapping with wires on the other layer, and thus has smaller crosstalk of signals because of smaller capacitive couplings between those wires on different layers. Experimental results show that the algorithm generates very good solutions. For example, a height of 41 for Deutsch's Difficult Example without any parallel overlaps of wires has been obtained and simultaneously, with a via count of 186, which is one of the best results ever reported in the literature.>

An optimal algorithm for the floorplan area optimization problem is presented. The algorithm is based on an extension of the technique of L. Stockmeyer (1983). Experimental results indicate that the authors' algorithm is efficient and capable of successfully handling large floor plans. The algorithm is compared with the branch-and-bound optimal algorithm of S. Wimer et al. (ibid., vol.8, no.2, p.139-45, 1989). The running time of the present algorithm is substantially less than that of the Wimer algorithm. For several examples where the Wimer algorithm ran for days and did not terminate, the present algorithm produced optimal solutions in a few seconds.>