We introduce Mixture-of-Trees (MoT), a novel framework that integrates sparse expert activation with structured tree-based reasoning for efficient LLM inference. MoT employs a learned gating mechanism to selectively activate only the most relevant expert reasoning trees for each problem, where experts use models of varying capacities based on task complexity. The framework features three key innovations: (1) sparse expert activation through unified gating networks, (2) specialized expert trees that leverage domain-specific expertise while optimizing the quality-efficiency trade-off, and (3) collaborative debate mechanisms for conflicting solutions. Additionally, MoT includes a shared baseline tree with early stopping—activated experts perform lightweight validation and terminate early when confidence is high. Experiments across five benchmarks (GSM8K, MATH, AIME 2024, MMLU, HotpotQA) show that MoT achieves 2-7 percentage point accuracy improvements while reducing LLM calls by 37-40% compared to existing multi-path methods.

Large Language Models (LLMs) are achieving unprecedented performance across diverse tasks, benefiting from autoregressive generation. However, this left-to-right decoding paradigm inherently limits contextual understanding quality. Diffusion-based LLMs (dLLMs) offer a promising alternative by iteratively refining sequences via denoising, enabling stronger bidirectional context modeling and improved generation quality. However, dLLMs face two main challenges: redundant computation and memory overhead in multi-step denoising, and excessive inference cost from over-denoising under fixed-step schedules. To address these issues, we propose dLLM-OPU, an FPGA overlay processor to accelerate dLLMs. Our solution features two key innovations: (1) a Region-Adaptive Caching for Dynamic Column Sparsity Framework that exploits temporal locality for selective recomputation without model retraining, and (2) a Token Entropy-based Early Stopping strategy that dynamically terminates the denoising process based on token-level convergence metrics. We implement these innovations through a specialized sparse processing element (PE) array that maximizes top-k sparsity utilization by minimizing idle cycles via row-column concatenation, complemented by an efficient cache management system that reduces memory access latency and a flexible entropybased decoding unit. Implemented on a U200 FPGA, dLLM-OPU achieves $2.2 \times-5.1 \times$ speedup and $7.6 \times-20.3 \times$ energy efficiency over RTX4090 in LLaDA.

Chiplets are a promising architecture for high-performance AI computing, but their package-level interconnects create a tightly coupled multiphysics problem involving signal delivery, power delivery, and heat dissipation. This challenge is compounded by the need to co-optimize the interposer and substrate, which have divergent design rules and performance sensitivities. To address these challenges, we propose MIP-SPT, a framework for multi-level interconnect planning. We introduce a hierarchical variable sched- uling strategy that decouples interposer and substrate variables, significantly reducing the search space. MIP-SPT then employs a multi-phase Bayesian optimization scheme to fully explore the streamlined design space. Crucially, our framework quantitatively models the effects of multiphysics coupling during planning to achieve rapid design closure. Experimental results show that our work reduces manufacturing cost by 22.4% compared to the baseline single-phase Bayesian optimization under equivalent design con- straints. In addition, it outperforms two existing works, lowering interconnect cost by 23.1% and 18.1%, respectively.

Transformer-based models have shown remarkable proficiency in extensive tasks for natural language processing, which are facing the ever-increasing need of processing long-context inputs. However, the memory footprint of the self-attention mechanism grows quadratically with the context length and becomes the bandwidth and memory bottleneck. Existing accelerators are mainly tailored for short sequences and struggle to handle attention in long-context scenarios. While some works attempt to mitigate this memory overhead with algorithmic optimizations, they suffer from limited hardware efficiency due to the sequential execution of backward-dependent iterations and additional computations. To this end, this paper proposes METAL, an algorithm-architecture co-optimized approach to support long-context inference with minimized memory overhead. First, we propose a hardware-friendly attention algorithm that eliminates the data dependency across inner loops, enabling full pipelining while keeping nonincreasing on-chip memory requirements, regardless of context length. Second, we develop a unified PE array for different dataflows across the transformer block to consistently support the entire inference with efficient data reuse. Moreover, an advanced non-linear operation module is designed to properly match the throughput of PE arrays with maximized resource sharing. Experimental results show that METAL on the Xilinx U200 FPGA outperforms other FPGA accelerators by$1.23-2.89 \times$in normalized throughput and achieves up to$\mathbf{5 1. 0 \%}$BRAM savings across different input sequence lengths.

Advanced integrated circuit (IC) systems increasingly utilize chiplet-based packaging with complex $2.5 \mathrm{D} / 3 \mathrm{D}$ structures and dense Through-Silicon Via (TSV) arrays. While the Finite Element Method (FEM) provides high-fidelity thermal simulation for these systems, its computational efficiency degrades significantly when generating and optimizing meshes for intricate geometries. To address these performance limitations while preserving simulation accuracy, we present NeuralMesh, a novel framework that accelerates thermal analysis of chiplet-based ICs. Our approach integrates deep learning and geometric analysis to optimize mesh generation without the need for iterative refinement steps. NeuralMesh first employs an enhanced segmentation model to predict thermal distributions based on geometric, material, and power parameters. These predictions, combined with key geometric features, guide the optimization of an initial coarse FEM mesh. By eliminating traditional iterative mesh refinement, our framework achieves up to $45.00 \times$ mesh generation speedup while maintaining thermal accuracy within 0.8% of commercial COMSOL simulations. It reduces the number of mesh elements in unimportant areas, which represents a speed improvement of the subsequent thermal simulation. This advancement enables rapid yet precise thermal analysis essential for modern IC package design.

Thermal management in 3D ICs is increasingly challenging due to higher power densities. Traditional PDESolving based methods, while accurate, are too slow for iterative design. Machine learning approaches like FNO provide faster alternatives but suffer from high-frequency information loss and high-fidelity data dependency. We introduce Self-Attention UNet Fourier Neural Operator (SAU-FNO), a novel framework combining self-attention and U-Net with FNO to capture longrange dependencies and model local high-frequency features effectively. Transfer learning is employed to fine-tune low-fidelity data, minimizing the need for extensive high-fidelity datasets and speeding up training. Experiments demonstrate that SAUFNO achieves state-of-the-art thermal prediction accuracy and provides an $842 \times$ speedup over traditional FEM methods, making it an efficient tool for advanced 3D IC thermal simulations.

State-space models (SSMs), such as Mamba, have emerged as a promising alternative to Transformers. However, the recently developed Mamba2, based on state space duality (SSD), is highly memorybound and suffers from limited computation efficiency. This inefficiency arises from its irregular broadcast element-wise multiplications and structured sparse computations. In this work, we propose MambaOPU, an FPGA overlay processor, to accelerate SSD. First, to reduce memory overhead, we introduce a software-hardware co-optimized operator fusion framework. Specifically, operator merging combines adjacent broadcast multiplication and summation operations into a single descriptor, while operator backward shifting embeds segment multiplication into subsequent operations. Both techniques shorten the computation path and improve computation efficiency. Second, to enhance sparse computation efficiency, we skip zero-region computations using a tensor-reorder-and-group algorithm combined with a sparse-predefined data fetcher. Additionally, since Mamba integrates linear operations with SSD, we develop a reconfigurable systolic array to improve data reuse across different computation modes. Extensive experiment results demonstrate that MambaOPU achieves up to $1812 \times$ and $880.79 \times$ higher normalized throughput and up to $12908 \times$ and $24.27 \times$ higher energy efficiency over Intel Xeon Gold 6348 CPU and NVIDIA A100 GPU, respectively.

Transformer-based models have shown huge success in natural language processing (NLP) with increasing model size and attention mechanism. However, this makes Von Neumann architecture based accelerators memory-bound such that the accelerators cannot leverage all the advantages of Transformer-based models. Although computing-in-memory (CIM) processors have emerged to tackle this problem through in-situ computing, the mismatch of computing patterns and low computing precision of CIM make it still challenging to accelerate Transformers. In this paper, we propose C2OPU, a hybrid dual-core processor to accelerate Transformers with hardware and software co-optimization. The dual-core architecture uses CIM arrays to accelerate weight-stationary vector-matrix multiplications, which accounts for the main computation complexity of Transformers. Meanwhile, a coarse-grained reconfigurable architecture (CGRA) is used to address the issues of computing pattern mismatch and low precision of the CIM. In addition, we propose an accuracy-bound workload allocation strategy, which considers non-ideal characteristics in analog computing, to balance throughput and accuracy. Furthermore, C2OPU provides a compiler to automatically determine optimal system configurations when Transformer model changes. Experimental results show that C2OPU achieves an average speedup of 145.41×, 4.73×, 4.70x and 3.85×, and 1.37x compared to CPU, GPU, Science23, Nature23, and VLSI24, respectively, on ten different Transformer models.

The advent of Large Language Models (LLMs) like DeepSeek, empowered by the Mixture-of-Experts (MoE) architecture, has driven significant advancements across diverse applications. However, a critical challenge arises during inference: Only a small fraction of experts are activated, causing severe token allocation imbalances among experts. This inefficiency poses substantial storage and computational burdens on resource-constrained devices, exacerbated by the lack of optimization strategies that integrate expert usage-aware parameter pruning and parallel scheduling, ultimately leading to suboptimal resource utilization. To address these limitations, we propose MoE-OPU, an FPGA-based overlay processor that optimizes parallel MoE inference through three key innovations. First, we introduce N:M sparsity (1:4/2:4/4:8/6:8/8:8) in the MLP layers and mixed-precision quantization (BF16/FP8/INT4) guided by expert activation frequency, reducing the parameter size by up to 2.76× while maintaining model accuracy (only 1.53% average drop after fine-tuning). Second, a lightweight prediction network dynamically predicts next-layer "hot" experts by analyzing historical activation patterns and current hidden states, achieving an average prediction hit rate of 83.4%. Third, a reconfigurable multi-core architecture maximizes the utilization of HBM bandwidth via a systolic array that natively supports sparse and mixed-precision computations, coupled with parallel concatenation to balance compute and memory efficiency. Experimental results on a Xilinx V80 FPGA with the DeepSeek-V2-lite model demonstrate that MoE-OPU outperforms the NVIDIA A100 GPU, delivering a 6.78× higher token throughput. Compared to RTX 4090 and U200 FPGA, MoE-OPU achieves 13.37× and 7.85× improvements, respectively. These advancements highlight the potential of algorithm-hardware co-design for scalable deployment of MoE-based LLMs on edge devices.

Accurate setup/hold time characterization is crucial for modern chip timing closure, but its reliance on potentially millions of SPICE simulations across diverse process-voltage-temperature (PVT) corners creates a major bottleneck, often lasting weeks or months. Existing methods suffer from slow search convergence and inefficient exploration, especially in the multi-corner setting. We introduce SetupKit, a novel framework designed to break this bottleneck using statistical intelligence, circuit analysis and active learning (AL). SetupKit integrates three key innovations: BEIRA, a bias-enhanced interpolation search derived from statistical error modeling to accelerate convergence by overcoming stagnation issues, initial search interval estimation by circuit analysis and AL strategy using Gaussian Process. This AL component intelligently learns PVT-timing correlations, actively guiding the expensive simulations to the most informative corners, thus minimizing redundancy in multi-corner characterization. Evaluated on industrial 22nm standard cells across 16 PVT corners, SetupKit demonstrates a significant 2.4× overall CPU time reduction (from 720 to 290 days on a single core) compared to standard practices, drastically cutting characterization time. SetupKit offers a principled, learning-based approach to library characterization, addressing a critical EDA challenge and paving the way for more intelligent simulation management.

The state of the art analog circuit design applies mainly a full-custom layout methodology. This demands high expertise and heavy manual workload. Additionally, neither can the resulting layout be re-used easily across different designs or different PDKs. Learning from digital standard cells, existing work has proposed stem cells that are abuttable. But stem cells have a fixed area ratio of 2 over same-sized Pcells, limiting its wide application. In this paper we develop a new type of abuttable analog cells (called Acells) for transistors and passive elements. Acells are compatible with digital standard cells and can be abutted in all directions, enabling the use of automatic digital place and route (PnR) engines. We automate Acell generation and show that the average area ratio over same-sized Pcell is 1.49 for 65nm technology and 1.3 for 28nm technology, and is expected to decrease for more advanced technologies. We then use digital PnR to automatically layout a number of analog and mixed-signal (AMS) circuits mainly in 28nm, and show that compared to Pcell-based manual layout, Acell-based layout obtains similar performance and its circuit level layout area is about 2% higher for large scale AMS circuits in our experiments.

As transistor dimensions shrink, process variations significantly impact circuit performance, signifying the need for accurate statistical circuit analysis. In digital circuit timing analysis, the Liberty Variation Format (LVF) has emerged as an industrial leading representation of timing distributions in cell libraries at 22 nm and below. However, LVF characterization relies on the Monte Carlo (MC) method, which requires excessive SPICE simulations of cells with process variations. Similar challenges also exist for uncertainty propagation and quantification in chip manufacturing and the broader scientific communities. To resolve this foundational challenge, this paper presents LVFGen, a novel method that reduces the simulation costs of MC while generate high-accuracy LVF library. LVFGen utilizes an active learning strategy based on variational analysis to identify process variation samples that impact timing distributions more significantly. Compared to the state-of-the-art Quasi-MC method, LVFGen demonstrates an overall 2.27× speedup in LVF library generation within an accuracy level of 5k-sample MC and a 4.06× speedup within a 100k-sample MC accuracy.

High-performance analog and mixed-signal (AMS) circuits are mainly full-custom designed, which is time-consuming and labor-intensive. A significant portion of the effort is experience-driven, which makes the automation of AMS circuit design a formidable challenge. Large language models (LLMs) have emerged as powerful tools for electronic design automation (EDA) applications, fostering advancements in the automatic design process for large-scale AMS circuits. However, the absence of high-quality datasets has led to issues such as model hallucination, which undermines the robustness of automatically generated circuit designs. To address this issue, this article introduces AMSnet-KG, a dataset encompassing various AMS circuit schematics and netlists. We construct a knowledge graph with annotations on detailed functional and performance characteristics. Facilitated by AMSnet-KG, we propose an automated AMS circuit generation framework that utilizes the comprehensive knowledge embedded in LLMs. The flow first formulate a design strategy (e.g., circuit architecture using a number of circuit components) based on required specifications. Next, matched subcircuits are retrieved and assembled into a complete topology, and transistor sizing is obtained through Bayesian optimization. Simulation results of the netlist are automatically fed back to the LLM for further topology refinement, ensuring the circuit design specifications are met. We perform case studies of operational amplifier and comparator design to verify the automatic design flow from specifications to netlists with minimal human effort. The dataset used in this article is available at https://ams-net.github.io/ .

Device models require large numbers of parameters to characterize complex physical effects. Although the latest advancements in machine learning and automated tools have drastically improved efficiency over the classic methods, they still demand a considerable amount of human intervention in the loop to gain accuracy. This drastically limits further automation. Inspired by the success of Multimodal Large Language Models (MLLMs) in addressing tasks across diverse fields, we propose ModelGen, the first in-depth study to leverage MLLMs with RAG (Retrieval-Augmented Generation) to significantly reduce human effort in parameter extraction for compact model. Our contributions include (1) Automated Agentic Workflow Construction that learns to build and refine extraction workflows through iterative optimization, (2) MLLM Judge, a visual scoring mechanism that evaluates fitting quality using actual device characteristic plots rather than simple numerical metrics, and (3) Model-specific RAG for providing relevant domain knowledge during the extraction process. Experimental results demonstrate that ModelGen achieves a 26.8%–33.1% improvement in pass@1,3,5 compared to base LLM methods. The system completes complex model extractions for BSIMs and ASM-HEMT in hours (up to 168× faster) rather than days or weeks, making parameter extraction more accessible to non-experts while maintaining professional engineer-level accuracy.

Linear algebra computations can be greatly accelerated using spatial accelerators on FPGAs. As a standard building block of linear algebra applications, BLAS covers a wide range of compute patterns that vary vastly in data reuse, bottleneck resources, matrix storage layouts, and data types. However, existing implementations of BLAS routines on FPGAs are stuck in the dilemma of productivity and performance. They either require extensive human effort or fail to leverage the properties of routines for acceleration. We introduce Lasa, a framework composed of a programming model and a compiler, designed to address the dilemma by abstracting (for productivity) and specializing (for performance) the architecture of a spatial accelerator. The programming model realizes systolic arrays using uniform recurrence equations and space-time transforms. Streaming tensors, an intuitive dataflow-style abstraction, is proposed to uniformly describe the movement, storage, and transpose of input and output data across the spatial components. According to streaming tensors, a customized memory hierarchy is automatically built on an FPGA by our compiler. The compiler further specializes the architecture with transparent optimizations on FPGAs. Using this framework, we develop a complete BLAS library, demonstrating performance in parity with expert-written HLS code for BLAS level 3 routines, 76%–94% machine peak for level 1 and 2 routines, and 1.6X–13X speedup by leveraging the matrix properties such as symmetry, triangularity, and bandness.

Transformer-based models have achieved extensive success with increasingly large numbers of parameters and computations, for which many multi-core accelerators have been developed. Nevertheless, they suffer from limited throughput due to either low operating frequency or high communication overhead between cores. This article proposes an FPGA-based multi-core overlay processor, named MCoreOPU, to optimize intra-core computation and inter-core communication. First, we boost the operating frequency of the processing element (PE) array to double the rest of the processor to improve the intra-core throughput. Second, we develop on-chip synchronization routers to reduce off-chip memory traffic, where only the partial sum and maximum are communicated between cores rather than entire vectors for layer normalization and softmax. Moreover, we pipeline synchronization to reduce synchronization latency and develop a bypass of the interconnect bus to reduce the off-chip memory access latency. Finally, we optimize the multi-core model allocation and scheduling to minimize the inter-core communications and maximize the intra-core computation efficiency. The MCoreOPU is implemented in 8-bit fixed-point precision with four cores and four DDRs on the Xilinx U200 FPGA, where the PE array runs at 600 MHz while the rest runs at 300 MHz. Experimental results show that the throughput per MAC of MCoreOPU for BERT, ViT, GPT-2, and LLaMA inference is 1.31 \(\times\) –7.18 \(\times\) higher than other FPGA-based accelerators. Compared with the A100 GPU, the throughput per equivalent MAC efficiency is improved by 22.52 \(\times\) –27.12 \(\times\) .

Yield estimation and optimization have become increasingly important for circuit design as technology nodes scale down. Simple yet well-established minimal norm importance sampling (MNIS) still serves as an industrial standard due to its robustness and reliability. In this study, we generalize the classic MNIS and propose Every Failure Is A Lesson (EFIAL) to utilize every failure sample (instead of one in MNIS) to construct the proposal distribution. EFIAL is completely tuning-free and the update computation complexity is only O(M) (M is the number of failure samples) by utilizing the blessing of dimensionality. The idea of EFIAL is then extended to the state-of-the-art (SOTA) pre-sampling method, onion sampling, to significantly boost efficiency, by up to 9.08x (4.68x on average). Extensive evaluations against SOTA yield estimation methods reveal that EFIAL achieves a speedup of up to 13.54x (5.16x on average) and an accuracy improvement of up to 24.91%.

As transistor size continues to scale down, process variation has become an essential factor determining semiconductor yield and economic return. The Liberty Variation Format (LVF) is the current industrial standard that expresses statistical timing behaviors based on single Gaussian model. However, it loses accuracy when the timing distribution is non-Gaussian due to growing process variations. This paper proposes a novel LVF2 distribution model that combines two weighted skewed-normal (SN) distributions, which better captures the multi-Gaussian timing distribution while maintaining backward compatibility with LVF. Experiments using TSMC 22nm standard cells show that, compared to LVF, LVF2 reduces binning error by 7.74X in delay and 9.56X in transition time, and reduces 3σ-yield error by 4.79X and 7.18X in delay and transition time, respectively. The error reduction for path delay is diminished due to Central Limit Theorem (CLT). But it is still 2X for a typical circuit path with 8 Fanout-of-4 (FO4) inverter delays.

Optimal mean shift vector (OMSV)-based importance sampling methods have long been prevalent in yield estimation and optimization as an industry standard. However, most OMSV-based methods are designed heuristically without a rigorous understanding of their limitations. To this end, we propose VIS, the first variational analysis framework for yield problems, enabling a systematic refinement for OMSV. For instance, VIS reveals that the classic OMSV is suboptimal, and the optimal/true OMSV should always stay beyond the failure boundary, which enables a free improvement for all OMSV-based methods immediately. Using VIS, we show a progressive refinement for the classic OMSV including incorporation of full covariance in closed form, adjusting for asymmetric failure distributions, and capturing multiple failure regions, each of which contributes to a progressive improvement of more than 2×. Inheriting the simplicity of OMSV, the proposed method retains simplicity and robustness yet achieves up to 29.03× speedup over the state-of-the-art (SOTA) methods. We also demonstrate how the SOTA yield optimization, ASAIS, can immediately benefit from our True OMSV, delivering a 1.20× and 1.27× improvement in performance and efficiency, respectively, without additional computational overhead.

Compute-in-memory (CIM) architectures based on emerging nonvolatile memories (eNVM) are recognized as promising candidates for the efficient computation of self-attention-based Transformer models, which are bounded by memory-intensive dynamic computations involving large matrices. However, existing CIM-based approaches mostly focused on the acceleration of vector-matrix multiplications (VMM) to obtain Q, K and V matrices for direct or sparse calculations of the vanilla Transformer. By storing large amounts of intermediate results in eNVM, the endurance limit is ignored which contradicts the reality of these technologies. In this work, a hybrid RRAM-SRAM CIM architecture to accelerate Transformers, namely AESHA, is proposed based on the eigen-decomposition of WQWTK and the systolic in-memory attention reconstruction. By utilizing the features of symmetric/skew-symmetric real matrices, AESHA translates dynamic attention computation to RRAM-based sparse feature transformation and SRAM-based systolic attention reconstruction to fully exploit the advantages of both on the architectural level. Experiments on a broad spectrum of benchmarks demonstrate that AESHA delivers superior performance in terms of pipeline optimization and energy efficiency. Specifically, AESHA achieves 2.59×, 2.69×, 2.62×, 2.58×, 3.08× and 7.84× maximum static RRAM memory footprint reduction in BERT-Base, BERT-Large, BigBird, Sanger, ViT-Base and ViT-Large over vanilla computation stack, respectively. It eliminates all runtime write access to the RRAM arrays to circumvent the endurance limit. Additionally, AESHA demonstrates 3170.0×, 95.6×, 4.1×, 19.0×, and 19.2× speedup, and 336.0K×, 12.6K×, 7.3×, 23.1×, and 25.8× energy reduction over CPU, GPU, ReBERT, ReTransformer, and CPSAA, respectively.

Large language models (LLMs) have achieved notable success on many applications with increasingly tremendous parameters and computations. While hardware accelerators on Transformer-based models have been extensively studied, recent work mainly assumes structured model pruning and does not work well for unstructured sparsity that could lead to more parameter and computation reduction. The reason behind is that it is difficult to exploit data reuse from the unstructured sparsity, leaving hardware underutilized. This paper proposes ChatOPU, an FPGA-based overlay processor for LLMs, to support unstructured model pruning with better data reuse. First, we propose a new diagonal dataflow on a systolic array to obtain efficient data reuse for both sparse and dense matrix multiplication. Second, we develop efficient encoding and decoding for the sparse parameters to save off-chip memory traffic. Moreover, we boost the off-chip bandwidth utilization with pinned on-chip KV cache allocation and coalesced access throughout the LLM inference. Experimental results show that ChatOPU on Xilinx U200 FPGA outperforms GPU and other FPGA-based accelerators on token/s by 2.29× and 1.63× on LLMs with unstructured sparsity across different input and output sequence lengths.

Linear algebra can often be significantly expedited by spatial accelerators on FPGAs. As a broadly-adopted linear algebra library, BLAS requires extensive optimizations for routines that vary vastly in data reuse, bottleneck resources, matrix storage layouts, and data types. Existing solutions are stuck in the dilemma of productivity and performance. We introduce Lasa, a framework composed of a programming model and a compiler, that addresses the dilemma by abstracting (for productivity) and specializing (for performance) the architecture of a spatial accelerator. Lasa abstracts a compute and its I/O as two dataflow graphs. A compiler maps the graphs onto systolic arrays and a customized memory heirarchy. The compiler further specializes the architecture transparently. In this framework, we develop 14 key BLAS routines, and demonstrate performance in parity with expert-written HLS code for BLAS level 3 routines, >=80% machine peak performance for level 2 and 1 routines, and 1.6X-7X speed up by taking advantage of matrix properties of symmetry, triangularity and bandness.

Transformer-based models has achieved remarkable success in extensive tasks for natural language processing. To face the variable-length sentences in human language, popular deep learning frameworks rely on zero padding for batch processing, which introduces significant computation and memory overhead. Existing works attempt to eliminate padding redundancy but results in low hardware efficiency due to the mismatch between the variable shape of operations and fixed shape of processing elements (PEs). This paper proposes a reconfigurable systolic array with token packing in three folds to boost hardware efficiency. First, matrix multiplications for different tokens can be packed along the array columns to improve spatial efficiency. Meanwhile, for temporal efficiency, we develop a coarse-grained pipeline for attention, where stages can run on different parts of the array at the same time. We further exploit the masking redundancy in the Transformer decoder with runtime reconfigurable inter-PE connection and buffer switching. Applied to GPT, our FPGA design has achieved 1.16× higher normalized throughput and 1.94× better runtime MAC utilization over the state-of-the-art GPU performance for variable-length input sequences from GLUE and SQuAD dataset.

Graph convolutional networks (GCNs) have been introduced to effectively process non-Euclidean graph data. However, GCNs incur large amounts of irregularity in computation and memory access, which prevents efficient use of traditional neural network accelerators. Moreover, existing dedicated GCN accelerators demand high memory volumes and are difficult to implement onto resource limited edge devices. In this work, we propose LW-GCN, a lightweight FPGA-based accelerator with a software-hardware co-designed process to tackle irregularity in computation and memory access in GCN inference. LW-GCN decomposes the main GCN operations into Sparse Matrix-Matrix Multiplication (SpMM) and Matrix-Matrix Multiplication (MM). We propose a novel compression format to balance workload across PEs and prevent data hazards. Moreover, we apply data quantization and workload tiling, and map both SpMM and MM of GCN inference onto a uniform architecture on resource limited hardware. Evaluation on GCN and GraphSAGE are performed on Xilinx Kintex-7 FPGA with three popular datasets. Compared to existing CPU, GPU, and state-of-the-art FPGA-based accelerator, LW-GCN reduces latency by up to 60×, 12×, and 1.7× and increases power efficiency by up to 912×, 511×, and 3.87×, respectively. Furthermore, compared with NVIDIA’s latest edge GPU Jetson Xavier NX, LW-GCN achieves speedup and energy savings of 32× and 84×, respectively.

Graph Convolutional Networks (GCNs) have shown great results but come with large computation costs and memory overhead. Recently, sampling-based approaches have been proposed to alter input sizes, which allows large GCN workloads to align to hardware constraints. Motivated by this flexibility, we propose an FPGA-based GCN accelerator, named SkeletonGCN, along with multiple software-hardware co-optimizations to improve training efficiency. We first quantize all feature and adjacency matrices of GCN from FP32 to SINT16. We then simplify the non-linear operations to better fit the FPGA computation, and identify reusable intermediate results to eliminate redundant computation. Moreover, we employ a linear time sparse matrix compression algorithm to further reduce memory bandwidth while allowing efficient decompression on hardware. Finally, we propose a unified hardware architecture to process sparse-dense matrix multiplication (SpMM) and dense matrix multiplication (MM), all on the same group of PEs to increase DSP utilization on FPGA. Evaluation is performed on a Xilinx Alveo U200 board. Compared with existing FPGA-based accelerator on the same network architecture, SkeletonGCN can achieve up to 11.3x speedup while maintaining the same training accuracy. In addition, SkeletonGCN can achieve up to 178x and 13.1x speedup over state-of-art CPU and GPU implementation on popular datasets, respectively.

Morphology of neuron trees is a key indicator to delineate neuronal cell-types, analyze brain development process, and evaluate pathological changes in neurological diseases. Traditional analysis mostly relies on heuristic features and visual inspections. A quantitative, informative, and comprehensive representation of neuron morphology is largely absent but desired. To fill this gap, in this work, we adopt a Tree-LSTM network to encode neuron morphology and introduce a self-supervised learning framework named TreeMoCo to learn features without the need for labels. We test TreeMoCo on 2403 high-quality 3D neuron reconstructions of mouse brains from three different public resources. Our results show that TreeMoCo is effective in both classifying major brain cell-types and identifying sub-types. To our best knowledge, TreeMoCo is the very first to explore learning the representation of neuron tree morphology with contrastive learning. It has a great potential to shed new light on quantitative neuron morphology analysis. Code is available at https://github.com/TencentAILabHealthcare/NeuronRepresentation.

With the ever-increasing applications of the Internet of Things (IoT), e.g., smart homes, smart cities, smart factories, etc., data security and device trustworthiness become the major concerns. Although blockchain contributes to achieve the data traceability and fault tolerance, the huge resource consumption and limited performance severely restrict its deployments in IoT. Moreover, the unique features of IoT, such as mobility, resource constraints, and security vulnerabilities, create even greater difficulties for blockchain running. Observing the lack of blockchain analyzing tools for IoT, we intend to provide a fair means with standard metrics for better understanding IoT-oriented blockchain. In this article, we present BCmaster, a blockchain analyzing and monitoring framework focusing on IoT scenarios. Based on the detailed modeling of blockchain-assisted IoT, we propose a novel metric set named 5-D quantitative metric framework, which can conduct the comprehensive blockchain analysis from five dimensions. Moreover, we design a modular architecture for BCmaster, wherein the interaction requests (IRs)-based data parser ensures a high system compatibility and the synchronous metric visualizer facilitates the real-time blockchain monitoring in IoT. Extensive evaluations in a real IoT environment demonstrate the validity of BCmaster and explore the performance of four IoT-oriented blockchain systems. Last but not least, we discuss the ways to customize IoT-oriented blockchain with the help of BCmaster.

“Curse of dimensionality” has become the major challenge for existing high-sigma yield analysis methods. In this article, we develop a meta-model using Low-Rank Tensor Approximation (LRTA) to substitute expensive SPICE simulation. The polynomial degree of our LRTA model grows linearly with the circuit dimension. This makes it especially promising for high-dimensional circuit problems. Our LRTA meta-model is solved efficiently with a robust greedy algorithm and calibrated iteratively with a bootstrap-assisted adaptive sampling method. We also develop a novel global sensitivity analysis approach to generate a reduced LRTA meta-model which is more compact. It further accelerates the procedure of model calibration and yield estimation. Experiments on memory and analog circuits validate that the proposed LRTA method outperforms other state-of-the-art approaches in terms of accuracy and efficiency.

Low-precision data representation is important to reduce storage size and memory access for convolutional neural networks (CNNs). Yet, existing methods have two major limitations: (1) requiring re-training to maintain accuracy for deep CNNs and (2) needing 16-bit floating-point or 8-bit fixed-point for a good accuracy. In this article, we propose a low-precision (8-bit) floating-point (LPFP) quantization method for FPGA-based acceleration to overcome the above limitations. Without any re-training, LPFP finds an optimal 8-bit data representation with negligible top-1/top-5 accuracy loss (within 0.5%/0.3% in our experiments, respectively, and significantly better than existing methods for deep CNNs). Furthermore, we implement one 8-bit LPFP multiplication by one 4-bit multiply-adder and one 3-bit adder, and therefore implement four 8-bit LPFP multiplications using one DSP48E1 of Xilinx Kintex-7 family or DSP48E2 of Xilinx Ultrascale/Ultrascale+ family, whereas one DSP can implement only two 8-bit fixed-point multiplications. Experiments on six typical CNNs for inference show that on average, we improve throughput by over existing FPGA accelerators. Particularly for VGG16 and YOLO, compared to six recent FPGA accelerators, we improve average throughput by 3.5 and 27.5 and average throughput per DSP by 4.1 and 5 , respectively.

Panoramic X-ray (PX) provides a 2D picture of the patient's mouth in a panoramic view to help dentists observe the invisible disease inside the gum. However, it provides limited 2D information compared with cone-beam computed tomography (CBCT), another dental imaging method that generates a 3D picture of the oral cavity but with more radiation dose and a higher price. Consequently, it is of great interest to reconstruct the 3D structure from a 2D X-ray image, which can greatly explore the application of X-ray imaging in dental surgeries. In this paper, we propose a framework, named Oral-3D, to reconstruct the 3D oral cavity from a single PX image and prior information of the dental arch. Specifically, we first train a generative model to learn the cross-dimension transformation from 2D to 3D. Then we restore the shape of the oral cavity with a deformation module with the dental arch curve, which can be obtained simply by taking a photo of the patient's mouth. To be noted, Oral-3D can restore both the density of bony tissues and the curved mandible surface. Experimental results show that Oral-3D can efficiently and effectively reconstruct the 3D oral structure and show critical information in clinical applications, e.g., tooth pulling and dental implants. To the best of our knowledge, we are the first to explore this domain transformation problem between these two imaging methods.

Convolutional neural networks (CNNs) have achieved extensive success on miscellaneous artificial intelligence applications such as image classification and object detection. A plethora of models emerge with different operators and architectures, gradually shifting attention from accuracy to efficiency in terms of speed and power, since VGG-like architecture from early stage has significant redundancy. Light-weight CNNs are proposed to reduce computation complexity and parameter amount. MobileNets, one typical example of light-weight CNNs, adopt depthwise separable convolution, while others such as SqueezeNet alter model topology to spare computation power.

In recent years, transformer-based models have shown state-of-the-art results for Natural Language Processing (NLP). In particular, the introduction of the BERT language model brought with it breakthroughs in tasks such as question answering and natural language inference, advancing applications that allow humans to interact naturally with embedded devices. FPGA-based overlay processors have been shown as effective solutions for edge image and video processing applications, which mostly rely on low precision linear matrix operations. In contrast, transformer-based NLP techniques employ a variety of higher precision nonlinear operations with significantly higher frequency. We present NPE, an FPGA-based overlay processor that can efficiently execute a variety of NLP models. NPE offers software-like programmability to the end user and, unlike FPGA designs that implement specialized accelerators for each nonlinear function, can be upgraded for future NLP models without requiring reconfiguration. NPE can meet real-time conversational AI latency targets for the BERT language model with 4x lower power than CPUs and 6x lower power than GPUs. We also show NPE uses 3x fewer FPGA resources relative to comparable BERT network-specific accelerators in the literature. NPE provides a cost-effective and power-efficient FPGA-based solution for Natural Language Processing at the edge.

Low precision quantization in convolutional neural network (CNN) inference has been proved effective for reducing computation complexity and bandwidth requirement. Mixed precision CNNs manage to benefit from low precision while maintaining accuracy. In this paper, we propose a Mixed Precision FPGA-based Overlay Processor (MP-OPU) to fully leverage the advantages of mixed precision for both conventional and lightweight CNNs. The micro-architecture of MP-OPU considers sharing of computation core with mixed precision weights and activations to improve computation efficiency. In addition, run-time scheduling of external memory access and data arrangement are optimized to further leverage the advantages of mixed precision data representation. Our experimental results show that MP-OPU reaches 4.92 TOPS peak throughput when implemented on the Xilinx VC709 FPGA (with all DSPs configured to support 2-bit multipliers). Moreover, MP-OPU achieves 12.9 × latency reduction and 2.2 × better throughput/DSP for conventional CNNs while 7.6× latency reduction and 2.9× better throughput/DSP for lightweight CNNs, all on average compared with existing FPGA accelerators/processors, respectively. To the best of our knowledge, this is the first in-depth study on mixed precision FPGA-based overlay processor for both conventional and lightweight CNNs.

Patient’s understanding on forthcoming dental surgeries is required by patient-centered care and helps reduce anxiety. Due to the complexity of dental surgeries and the patient-dentist expertise gap, conventional techniques of patient education are usually not effective for explaining surgical steps. In this paper, we present OralViewer—the first interactive application that enables dentist’s demonstration of dental surgeries in 3D to promote patients’ understanding. OralViewer takes a single 2D panoramic dental X-ray to reconstruct patient-specific 3D teeth structures, which are then assembled with registered gum and jaw bone models for complete oral cavity modeling. During the demonstration, OralViewer enables dentists to show surgery steps with virtual dental instruments that can animate effects on a 3D model in real-time. A technical evaluation shows that our deep learning model achieves a mean Intersection over Union (IoU) of 0.771 for 3D teeth reconstruction. A patient study with 12 participants shows OralViewer can improve patients’ understanding of surgeries. A preliminary expert study with 3 board-certified dentists further verifies the clinical validity of our system.

Dental forensic identification targets to identify persons with dental traces.The task is vital for the investigation of criminal scenes and mass disasters because of the resistance of dental structures and the wide-existence of dental imaging. However, no widely accepted automated solution is available for this labour-costly task. In this work, we pioneer to study deep learning for dental forensic identification based on panoramic radiographs. We construct a comprehensive benchmark with various dental variations that can adequately reflect the difficulties of the task. By considering the task's unique challenges, we propose FoID, a deep learning method featured by: (\textit{i}) clinical-inspired attention localization, (\textit{ii}) domain-specific augmentations that enable instance discriminative learning, and (\textit{iii}) transformer-based self-attention mechanism that dynamically reasons the relative importance of attentions. We show that FoID can outperform traditional approaches by at least \textbf{22.98\%} in terms of Rank-1 accuracy, and outperform strong CNN baselines by at least \textbf{10.50\%} in terms of mean Average Precision (mAP). Moreover, extensive ablation studies verify the effectiveness of each building blocks of FoID. Our work can be a first step towards the automated system for forensic identification among large-scale multi-site databases. Also, the proposed techniques, \textit{e.g.}, self-attention mechanism, can also be meaningful for other identification tasks, \textit{e.g.}, pedestrian re-identification.Related data and codes can be found at \href{https://github.com/liangyuandg/FoID}{https://github.com/liangyuandg/FoID}.

An artificial noise (AN)-aided beamformer specific to correlated main and wiretap channels is designed in this paper. We consider slow-fading multiple-input-single-output wiretap channels with multiple passive single-antenna eavesdroppers in which an independent transmitter side and correlated receiver side are assumed. Additionally, the source has accurate main channel information and statistical wiretap channel information. To reduce the secrecy loss due to receiver-side correlation, this paper proposes a channel-correlation-enabled transmission optimization scheme. In particular, the correlation is viewed as a resource to acquire more knowledge about wiretap channels. Based on this, the statistical distribution of wiretap channels is described more precisely, and an elaborate channel-correlation-enabled AN-aided beamformer is designed. Then, the achievable secrecy rate under transmit power and secrecy outage constraints is derived. Finally, the study is also extended to a specific scenario of multiple-antenna eavesdroppers. Simulation results show that the secrecy rate under transmit power and secrecy outage constraints can be improved under high correlation.

Convolutional networks (ConvNets) have achieved promising accuracy for various anatomical segmentation tasks. Despite the success, these methods can be sensitive to appearance variations that unforeseen from the training distributions. Considering the large variability of scans caused by artifacts, pathologies, and scanning setups, the robustness of ConvNets poses as a major challenge for their clinical applications, yet has not been much explored. In this paper, we propose to mitigate the challenge by enabling ConvNets’ awareness of the underlying anatomical invariances among imaging scans. Specifically, we introduce a fully convolutional Constraint Adoption Module (CAM) that incorporates probabilistic atlas priors as explicit constraints for predictions over a locally connected Conditional Random Field (CFR), which effectively reinforces the anatomical consistency of the labeling outputs. We design the CAM to be flexible for boosting various ConvNet, and compact for co-optimizing with ConvNets for fusion parameters that leads to the optimal performance. We show the advantage of such atlas priors fusion is two-fold with two brain parcellation tasks. First, our models achieve state-of-the-art accuracy among ConvNet-based methods on both datasets, by significantly reducing structural abnormalities of predictions. Second, we can largely boost the robustness of existing ConvNets, proved by: (i) testing on scans with synthetic pathologies, and (ii) training and evaluation on scans of different scanning setups across datasets. Our method is proposing to be easily adopted to existing ConvNets by fine-tuning with CAM plugged in for accuracy and robustness boosts.

Due to a lack of medical resources or oral health awareness, oral diseases are often left unexamined and untreated, affecting a large population worldwide. With the advent of low-cost, sensor-equipped smartphones, mobile apps offer a promising possibility for promoting oral health. However, to the best of our knowledge, no mobile health (mHealth) solutions can directly support a user to self-examine their oral health condition. This paper presents OralCam, the first interactive app that enables end-users' self-examination of five common oral conditions (diseases or early disease signals) by taking smartphone photos of one's oral cavity. OralCam allows a user to annotate additional information (e.g. living habits, pain, and bleeding) to augment the input image, and presents the output hierarchically, probabilistically and with visual explanations to help a laymen user understand examination results. Developed on our in-house dataset that consists of 3,182 oral photos annotated by dental experts, our deep learning based framework achieved an average detection sensitivity of 0.787 over five conditions with high localization accuracy. In a week-long in-the-wild user study (N=18), most participants had no trouble using OralCam and interpreting the examination results. Two expert interviews further validate the feasibility of OralCam for promoting users' awareness of oral health.

Low precision data representation is important to reduce storage size and memory access for convolutional neural networks (CNNs). Yet, existing methods have two major limitations: (1) requiring re-training to maintain accuracy for deep CNNs, and (2) needing 16-bit floating point or 8-bit fixed point for a good accuracy.

Lightweight convolutional neural networks (LW-CNNs) such as MobileNet, ShuffleNet, SqueezeNet, etc., have emerged in the past few years for fast inference on embedded and mobile system. However, lightweight operations limit acceleration potential by GPU due to their memory bounded nature and their parallel mechanisms that are not friendly to SIMD. This calls for more specific accelerators. In this paper, we propose an FPGA-based overlay processor with a corresponding compilation flow for general LW-CNN accelerations, called Light-OPU. Software-hardware co-designed Light-OPU reformulates and decomposes lightweight operations for efficient acceleration. Moreover, our instruction architecture considers sharing of major computation engine between LW operations and conventional convolution operations. This improves the run-time resource efficiency and overall power efficiency. Finally, Light-OPU is software programmable, since loading of compiled codes and kernel weights completes switch of targeted network without FPGA reconfiguration. Our experiments on seven major LW-CNNs show that Light-OPU achieves 5.5x better latency and 3.0x higher power efficiency on average compared with edge GPU NVIDIA Jetson TX2. Furthermore, Light-OPU has 1.3x to 8.4x better power efficiency compared with previous customized FPGA accelerators. To the best of our knowledge, Light-OPU is the first in-depth study on FPGA-based general processor for LW-CNNs acceleration with high performance and power efficiency, which is evaluated using all major LW-CNNs including the newly released MobileNetV3.

Rare-event yield analysis is challenging for high-dimensional circuit cases. In this paper, we propose a non-Gaussian adaptive importance sampling (NGAIS) method. In order to approximate the failure region in high-dimensional space, we model it as a mixture of von Mises-Fisher distributions. We formulate the parameter estimation problem as a maximum likelihood estimation problem, and then solve with expectation-maximization algorithm. Experiments on bit cell, amplifier and SRAM column circuit validate that the proposed NGAIS method outperforms other state-of-the-art approaches in terms of accuracy and efficiency.

This paper studies cooperative-jamming (CJ)-aided beamforming design under Gaussian channel uncertainties to reduce the secrecy loss due to reception correlation. In light of the difficulty of maximizing the outage-probability-constrained secrecy rate, a novel quality-of-service (QoS)-based optimization is considered. By employing the Bernstein-type inequality to approximate the probabilistic constraints, we seek to maximize the target outage signal-to-noise ratio (SNR) at the destination under transmit power and SNR outage constraints. Simulation results verify the designed CJ-aided beamforming substantially enhances the secrecy from a QoS perspective.

Performance failure has become a major threat for various memory and analog circuits. It is challenging to estimate the extremely small failure probability when failed samples are distributed in multiple disjoint regions. In this article, we propose an adaptive importance sampling (AIS) algorithm. AIS has several iterations of sampling region adjustments, while existing methods predecide a static sampling distribution. We design two adaptive frameworks based on resampling and population Metropolis-Hastings (MH) to iteratively search for failure regions. The experimental results of the AIS method exhibit better efficiency and higher accuracy. For SRAM bit cell with single failure region, the AIS method uses 2-$27{\times }$ fewer samples and reaches better accuracy when compared to several recent methods. For a two-stage amplifier circuit with multiple failure regions, the AIS method is $90{\times }$ faster than Monte Carlo and 7-23 ${\times }$ over other methods. For charge pump circuit and $C^{2}MOS$ master-slave latch circuit, the AIS method can reach 6-$18{\times }$ and 4-$6{\times }$ speedup over other methods, respectively.

Field-programmable gate array (FPGA) provides rich parallel computing resources with high energy efficiency, making it ideal for deep convolutional neural network (CNN) acceleration. In recent years, automatic compilers have been developed to generate network-specific FPGA accelerators. However, with more cascading deep CNN algorithms adapted by various complicated tasks, reconfiguration of FPGA devices during runtime becomes unavoidable when network-specific accelerators are employed. Such reconfiguration can be difficult for edge devices. Moreover, network-specific accelerator means regeneration of RTL code and physical implementation whenever the network is updated. This is not easy for CNN end users. In this article, we propose a domain-specific FPGA overlay processor, named OPU to accelerate CNN networks. It offers software-like programmability for CNN end users, as CNN algorithms are automatically compiled into executable codes, which are loaded and executed by OPU without reconfiguration of FPGA for switch or update of CNN networks. Our OPU instructions have complicated functions with variable runtimes but a uniform length. The granularity of instruction is optimized to provide good performance and sufficient flexibility, while reducing complexity to develop microarchitecture and compiler. Experiments show that OPU can achieve an average of 91% runtime multiplication and accumulation unit (MAC) efficiency (RME) among nine different networks. Moreover, for VGG and YOLO networks, OPU outperforms automatically compiled network-specific accelerators in the literature. In addition, OPU shows 5.35× better power efficiency compared with Titan Xp. For a real-time cascaded CNN networks scenario, OPU is 2.9× faster compared with edge computing GPU Jetson Tx2, which has a similar amount of computing resources.

In this article, we design the first full software/ hardware stack, called Uni-OPU, for an efficient uniform hardware acceleration of different types of transposed convolutional (TCONV) networks and conventional convolutional (CONV) networks. Specifically, a software compiler is provided to transform the computation of various TCONV, i.e., zero-inserting-based TCONV (zero-TCONV), nearest-neighbor resizing-based TCONV (NN-TCONV), and CONV layers into the same pattern. The compiler conducts the following optimizations: 1) eliminating up to 98.4% of operations in TCONV by making use of the fixed pattern of TCONV upsampling; 2) decomposing and reformulating TCONV and CONV into streaming parallel vector multiplication with a uniform address generation scheme and data flow pattern; and 3) efficient scheduling and instruction compilation to map networks onto a hardware processor. An instruction-based hardware acceleration processor is developed to efficiently speedup our uniform computation pattern with throughput up to 2.35 TOPS for the TCONV layer, consuming only 2.89 W dynamic power. We evaluate Uni-OPU on a benchmark set composed of six TCONV networks from different application fields. Extensive experimental results indicate that Uni-OPU is able to gain 1.45× to 3.68× superior power efficiency compared with state-of-the-art zero-TCONV accelerators. High acceleration performance is also achieved on NN-TCONV networks, the acceleration of which have not been explored before. In summary, we observe 1.90× and 1.63× latency reduction, as well as 15.04× and 12.43× higher power efficiency on zero-TCONV and NN-TCONV networks compared with Titan Xp GPU on average. To the best of our knowledge, ours is the first in-depth study to completely unify the computation process of zero-TCONV, NN-TCONV, and CONV layers.

"Curse of dimensionality" has become the major challenge for existing high-sigma yield analysis methods. In this paper, we develop a meta-model using Low-Rank Tensor Approximation (LRTA) to substitute expensive SPICE simulation. The polynomial degree of our LRTA model grows linearly with circuit dimension. This makes it especially promising for high-dimensional circuit problems. Our LRTA meta-model is solved efficiently with a robust greedy algorithm, and calibrated iteratively with an adaptive sampling method. Experiments on bit cell and SRAM column validate that proposed LRTA method outperforms other state-of-the-art approaches in terms of accuracy and efficiency.

As the design complexity keep increasing, the 2.5D FPGA with large logic capacity has become popular in modern circuit applications. A 2.5D FPGA consists of multiple dies connected through super long lines (SLLs) on an interposer, where each die contains heterogeneous logic blocks and ASIC-like clocking architectures to achieve better skew and timing. To address the crucial SLL issue and the special clocking architecture, this paper presents the first analytical placement algorithm for the 2.5D FPGA with the objective of minimizing the numbers of inter-die SLL signals and intra-die clocking violations simultaneously. Using a lifting dimension technique, we first formulate the 2.5D global placement problem as a three-dimensional continuous and differential minimization problem, where the SLL-aware block distribution is modeled by 3D Poisson's equation and directly solved to obtain an analytical solution. Then, we further reformulate the minimization problem as a separable optimization problem with linear constraints. Based on the proximal alternating direction method of multipliers (ADMM) optimization method, we efficiently optimize the separable subproblems one by one in an alternating fashion. Finally, clock-aware legalization and detailed placement are applied to legalize and further improve our placement results. Compared with the state-of-the-art work, experimental results show that our algorithm can resolve all clocking constraints and reduce the number of SLL crossing signals by 36.9% with similar wirelength in comparable running time.

Metal fill insertion has become an essential step to reduce dielectric thickness variation and improve pattern uniformity, which is important in mitigating process variations, thereby achieving better manufacturing yield. However, metal fills could induce coupling capacitance, which is not often considered in existing works that typically focus more on pattern density uniformity, incurring significant problems in timing closure. In this paper, we address the timing-aware fill insertion problem that considers the total capacitance and density constraints simultaneously. First, initial metal fill insertion and design-rule-aware legalization are used to quickly obtain an initial fill insertion solution. Second, from critical conductors to powers/grounds in a circuit, we divide conductors into different equivalent paths and then construct a capacitance graph to globally reduce the capacitance of each equivalent path. Third, we present a density-aware coupling capacitance optimization method and a fast Monte Carlo based fill selection to further reduce the coupling capacitance between any pair of conductors. Finally, we present a density-aware fill deletion method to reduce the fill amounts. We evaluate the performance of our algorithm based on the benchmarks of the 2018 CAD Contest at ICCAD and its official contest evaluator. Compared with the first place team of the contest and the state-of-the-art work, experimental results show that our algorithm achieves the lowest total capacitance and the least fill amount for each benchmark.

Performance failure has become the major threat to the robustness and reliability of various memory and analog circuits. It is challenging to accurately estimate the extremely small failure probability when failed samples are distributed in multiple disjoint failure regions. In this paper, we develop a novel meta-model based importance sampling (MIS) method. MIS utilizes Gaussian Process meta-model to construct quasi-optimal importance sampling distribution, and performs Markov Chain Monte Carlo (MCMC) simulation to generate new samples from the proposed distribution. By updating our global Importance Sampling estimator in an iterated framework, MIS leads to better efficiency and higher accuracy. For SRAM bit cell with single failure region, MIS uses 4-6X fewer samples and reaches better accuracy when compared to several recent methods. For a two-stage amplifier circuit with multiple failure schemes, MIS is 213X faster than MC without compromising accuracy, while other methods fail to cover all failure regions in our experiment.

Statistical circuit simulation is exhibiting increasing importance for memory circuits under process variation. It is challenging to accurately estimate the extremely low failure probability as it becomes a high-dimensional and multi-failure-region problem. In this paper, we develop an Adaptive Clustering and Sampling (ACS) method. ACS proceeds iteratively to cluster samples and adjust sampling distribution, while most existing approaches pre-decide a static sampling distribution. By adaptively searching in multiple cone-shaped subspaces, ACS obtains better accuracy and efficiency. This result is validated by our experiments. For SRAM bit cell with single failure region, ACS requires 3-5X fewer samples and achieves better accuracy compared with existing approaches. For 576-dimensional SRAM column circuit with multiple failure regions, ACS is 2050X faster than MC without compromising accuracy, while other methods fail to converge to correct failure probability in our experiment.

This paper proposes to employ multiple cooperative jammers to reduce the secrecy loss due to the correlation between main and wiretap channels. We consider slow-fading multiple-input single-output (MISO) wiretap channels with a passive single-antenna eavesdropper, in which an independent transmitter side and correlated receiver side are assumed. Considering that signal processing techniques as well as the blind growth of power at the source play a limited role in reducing the secrecy loss due to the receiver-side correlation, multiple cooperative jammers equipped with multiple antennas are introduced into the system. Owing to spatial diversity, the channel correlation from the different jammers to the destination and the eavesdropper varies. To interfere with the reception at the eavesdropper efficiently and consequently enhance security, some jammers in favorable channel conditions are selected to emit artificial noise (AN) with power optimization. Based on this, the secrecy outage probability is analyzed. The simulation results verify that the proposed scheme of multiple cooperative jammers provides substantial gains in terms of secrecy.

Performance failure has become a growing concern for the robustness and reliability of memory circuits. It is challenging to accurately estimate the extremely small failure probability when failed samples are distributed in multiple disjoint failure regions. In this paper, we develop an adaptive importance sampling (AIS) method. AIS has several iterations of sampling region adjustments, while existing methods pre-decide a static sampling distribution. By iteratively searching for failure regions, AIS may lead to better efficiency and accuracy. This is validated by our experiments. For SRAM cell with single failure region, AIS uses 5-10X fewer samples and reaches better accuracy when compared to several recent methods. For sense amplifier circuit with multiple failure regions, AIS is 4369X faster than MC without compromising accuracy, while other methods fail to cover all failure regions in our experiment.

Recently, a practical quantum annealing device has been commercialized by D-Wave Systems, sparking research interest in developing applications to solve problems that are intractable for classical computer. This paper provides a tutorial for using quantum annealer to solve Boolean satisfiability problem. We explain the computational model of quantum annealer and discuss the detailed mapping technique inspired by FPGA CAD flow, including stages such as logic optimization, placement and routing.

Energy router (ER) based system is a crucial part of the energy transmission and management under the circumstance of energy Internet for green cities. During its design process, a sound formal verification and a performance monitoring scheme are needed to check its reliability and meaningful quantitative properties. In this paper, we provide formal verification solutions for an ER-based system by proposing a continuous-time Markov chain model describing the architecture of the ER-based system. To verify real-world function of the ER-based system, we choose electricity trading to propose a Markov decision process model based on an ER subsystem to describe the trading behavior. To monitor the system performance, we project the energy scheduling process in the ER-based system, and then implement this scheduling process on top of a cloud computing experiment tool. Finally, we perform extensive experiment evaluations to investigate the system reliability properties, quantitative properties, and scheduling behaviors. The experiment verifies the effectiveness of the proposed models and the monitoring scheme.

Recent research has demonstrated promising results in solving constrained satisfaction problem (CSP) using D-Wave quantum annealer. However, the embedding of the CSP suffers drawbacks such as long embedding time in addition to poor quality due to long chains that reduce the ground state probability. To address those issues, we propose an effective embedding technique that reduces the embedding time and minimizes the chain length. We compared to the most recent method published in DAC 2016. Experiments using existing D-Wave 2X quantum annealer show that the proposed embedding technique increases the ground state probability by 29% on average. Furthermore, to demonstrate the efficiency, we embedded large problems onto a predicted C100 D-Wave Chimera architecture. Experimental results show that our approach reduces the run-time by 3.4x on average with reduced longest chain length.

Green energy router (ER) system is a crucial part in the energy transmission and management under the circumstance of Energy Internet and green communication. During its design process a sound formal verification is needed to check its reliability and meaningful quantitative properties. In this paper, we first propose two models describing the architecture of ER system using continuous-time Markov chains. To verify real world function of the ER, we choose electricity trading to propose an Markov decision process model based on an ER subsystem to describe the trading behaviour. Finally, we perform extensive experiment evaluations to investigate the system reliability properties, quantitative properties. The experiment verifies the effectiveness of the proposed models.

Quantum annealing device has shown a great potential in solving discrete problems that are theoretically and empirically hard. Boolean Satisfiability (SAT) problem, determining if there is an assignment of variables that satisfies a given Boolean function, is the first proven NP-complete problem widely used in various domains. Here, we present a novel mapping of the SAT problem to the quadratic unconstrained binary optimization problem (QUBO), and further develop a tool flow embedding the proposed QUBO to the architecture of the commercialized quantum computer D-Wave. By leveraging electronic design automation techniques including synthesis, placement and routing, this is not only the first work providing the detail flow that embeds the QUBO, but also a technique scalable for real world applications and some hard SAT problems with over 6000 variables in QUBO. Based on our results, we discuss the challenges in solving SAT using the current generation of annealing device, and explore the problem solving capability of future quantum annealing computers.

Because layout stage consumes the lion share of FPGA synthesis runtime, pre-layout power estimation can be viewed as an early stage estimation and is needed for power minimization at the early design stage. Consisting two phases of feature selection and model training, data mining is effective for data based modeling, yet it has not been applied in a rigid fashion for FPGA power estimation as the existing algorithms can be viewed as model training using features selected manually. In this paper, we apply machine learning with automatic feature selection to pre- and post- logic synthesis estimations, named pre-synthesis and post-synthesis estimation. Experiments using Lattice Diamond MachXO2 family show that compared to the post-layout power simulation, post-synthesis estimation is 20x faster with 8.62% average error, while pre-synthesis estimation is 600x faster with considerably larger error that still needs further improvement. Furthermore, compared to existing algorithms using manually selected features, our post-synthesis estimation using automatic feature selection reduces error by 2-3 times. Finally, the ranking of features is able to provide insights for power minimization.

Unlike well accepted FPGA emulation for digital circuits, there is no winning emulation solution for analog and mixed-signal (AMS) circuits. This paper presents an analog circuit emulation based on wave digital filters (WDFs), which covers the entire flow of transforming an AMS circuit from SPICE netlist to hardware implementation in FPGA. More specifically, it presents the theoretical support of how to map linear and nonlinear circuit components to WDF. The detail implementation of each WDF component in FPGA is not elaborated due to the page limit. Experiments show that there is a virtually perfect match between FPGA emulation and HSPICE simulations on two small but representative analog circuits, indicating high accuracy of the proposed emulation, and the FPGA-based WDF emulation can process analog signal sampled at as high as 512KHz, which is adequate for a variety of biomedical sensing applications.

Statistical circuit simulation is exhibiting increasing importance for circuit design under process variations. It has been widely used throughout the design of standard cell circuits (SRAM, Flip-Flop, etc.) to maximize yield, i.e. to minimize the failure probability. Existing approaches cannot effectively analyze the failure probability when failed samples are distributed in multiple disjoint regions, nor handle the circuits with a large number of variations. To tackle these challenges, the proposed hyperspherical clustering and sampling (HSCS) approach first identifies multiple failure regions through a reweighted spherical k-means algorithm, which clusters failed samples on a set of hyperspheres, rather than the high dimensional open space. Next, a modified mixture importance sampling is designed to draw samples at those clusters to achieve multiple failure region coverage. The proposed HSCS is evaluated using both mathematical and circuit-based examples. It achieves about 3-order speedup over Monte Carlo with the same level of accuracy, while other importance sampling based approaches either fail to converge or converge to wrong results. Furthermore, HSCS demonstrates excellent robustness by generating consistent results in multiple replications.

For software testing, concolic testing reasons about data symbolically but enumerates program paths. The existing concolic technique enumerates paths sequentially, leading to poor branch coverage in limited time. In this paper, we improve concolic testing by bounded model checking (BMC). During concolic testing, we identify program regions that can be encoded by BMC on the fly so that program paths within these regions are checked simultaneously. We have implemented the new algorithm on top of KLEE and called the new tool LLSPLAT. We have compared LLSPLAT with KLEE using 10 programs from the Windows NT Drivers Simplified and 88 programs from the GNU Coreutils benchmark sets. With 3600 second testing time for each program, LLSPLAT provides on average 13% relative branch coverage improvement on all 10 programs in the Windows drivers set, and on average 16% relative branch coverage improvement on 80 out of 88 programs in the GNU Coreutils set.

In advanced technology node, not only process variations but also aging effects have critical impacts on circuit performance. Most of existing works consider process variations and aging effects separately while building the corresponding behavior models. Because of the time-varied circuit property, parametric yield need to be reanalyzed in each aging time step. This results in expensive simulation cost for reliability analysis due to the huge number of circuit simulation runs. In this paper, an incremental Latin hypercube sampling (LHS) approach is proposed to build the stochastic behavior models for analog/mixed-signal (AMS) circuits while simultaneously considering process variations and aging effects. By reusing previous sampling information, only a few new samples are incrementally updated to build an accurate stochastic model in different time steps, which significantly reduces the number of simulations for aging analysis. Experiments on an operational amplifier and a DAC circuit achieve 242x speedup over traditional reliability analysis method with similar accuracies.

Software simulation of analog and mixed-signal circuits often takes a long computing time. Unlike digital circuits that can be validated by FPGA emulation, there is no winning emulation solution for analog circuits. As the first step to applying wave digital filter (WDF) to emulate post-layout analog circuits, we present how to map linear and nonlinear components in an original circuit to WDFs with exactly same behaviors. To validate, we implement the emulation circuit (i.e., WDFs) in FPGA. To be more specific, each emulation time step is executed as a finite state machine, while all the computing resource, e.g. floating point units (FPU), are shared as a resource pool and used only when it is necessary, which result in a very small resource consumption on FPGA. Virtually perfect match is obtained between the Verilog and SPICE simulations for a number of primitive analog circuits, indicating the high accuracy of the proposed emulation. In terms of runtime, the WDF implementation is about 3-4x faster than HSPICE on a small two-stage differential amplifier circuit. And better speedup can be anticipated when it scales to larger circuits because of the underlying binary tree structure of the WDF implementation.

In Delay Tolerant Networks (DTN), the resource utilization is decreased because of the limited resources and redundant copies. This paper proposes an improved Socially Aware Feedback Mechanism (SAFM). In this mechanism, the historical information of the encountered nodes are utilized to construct social links which indicates the level of social relationship between nodes. In the feedback process, acknowledgements are forwarded to the nodes whose Social Link (SL) is higher than a given threshold α. After getting the acknowledgements, nodes will delete the copies of messages which have been received by the destination nodes, so as to reduce the redundancy. In simulation, the threshold α is obtained to reach the best performance of SAFM. Compared with active and passive receipt approaches in an acceptable range of delay, SAFM improves the delivery probability, decreases the buffer occupancy and reduces the overhead.

Due to the limited resources of DTMSN (Delay Tolerant Mobile Sensor Networks), network congestion becomes a critical problem to resolve. Traditional congestion control methods where the number of copies is restricted to limit data packet forwarding cannot adapt to constantly changing network environment because of fixed number of copies. Fortunately, this problem can be solved through a real-time algorithm by modifying data packet forwarding conditions. However, one of the major challenges of this algorithm is detecting characteristics of the network environment accurately and efficiently. In this paper, an optimized routing algorithm, RVNS (Reduced Variable Neighborhood Search)-based Spray and Wait (SW) is proposed. In this algorithm, nodes will transmit and store the counter record of each other when they meet, based on which, RVNS is introduced to calculate a real-time threshold for the forwarding condition to control packet delivery. Simulation results show that the proposed algorithm increases delivery probability and dramatically reduces the overhead ratio. In some extreme cases, this algorithm can reach an extremely low overhead ratio (ten times lower than that of SW), meaning that the proposed algorithm suits challenged networks well.

Distributed devices in smart grid systems are decentralized and connected to the power grid through different types of equipment transmit, which will produce numerous energy losses when power flows from one bus to another. One of the most efficient approaches to reduce energy losses is to integrate distributed generations (DGs), mostly renewable energy sources. However, the uncertainty of DG may cause instability issues. Additionally, due to the similar consumption habits of customers, the peak load period of power consumption may cause congestion in the power grid and affect the energy delivery. Energy management with DG regulation is considered to be one of the most efficient solutions for solving these instability issues. In this paper, we consider a power system with both distributed generators and customers, and propose a distributed locational marginal pricing (DLMP)-based unified energy management system (uEMS) model, which, unlike previous works, considers both increasing profit benefits for DGs and increasing stability of the distributed power system (DPS). The model contains two parts: 1) a game theory-based loss reduction allocation (LRA); and 2) a load feedback control (LFC) with price elasticity. In the former component, we develop an iterative loss reduction method using DLMP to remunerate DGs for their participation in energy loss reduction. By using iterative LRA to calculate energy loss reduction, the model accurately rewards DG contribution and offers a fair competitive market. Furthermore, the overall profit of all DGs is maximized by utilizing game theory to calculate an optimal LRA scheme for calculating the distributed loss of every DG in each time slot. In the latter component of the model, we propose an LFC submodel with price elasticity, where a DLMP feedback signal is calculated by customer demand to regulate peak-load value. In uEMS, LFC first determines the DLMP signal of a customer bus by a time-shift load optimization (LO) algorithm based on the changes of customer demand, which is fed back to the DLMP of the customer bus at the next slot-time, allowing for peak-load regulation via price elasticity. Results based on the IEEE 37-bus feeder system show that the proposed uEMS model can increase DG benefits and improve system stability.

Memory circuits have become important components in today's IC designs which demands extremely high integration density and reliability under process variations. The most challenging task is how to accurately estimate the extremely small failure probability of memory circuits where the circuit failure is a “rare event”. Classic importance sampling has been widely recognized to be inaccurate and unreliable in high dimensions. To address this issue, we propose a fast statistical analysis to estimate the probability of rare events in high dimensions and prove that the estimation is always bounded. This methodology has been successfully applied to the failure analysis of memory circuits with hundreds of variables, which was considered to be very intractable before. To the best of our knowledge, this is the first work that successfully solves high dimensional “rare event” problems without using expensive Monte Carlo and classic importance sampling methods. Experiments on a 54-dimensional SRAM cell circuit show that the proposed approach achieves 1150x speedup over Monte Carlo without compromising any accuracy. It also outperforms the classification based method (e.g., Statistical Blockade) by 204x and existing importance sampling method (e.g., Spherical Sampling) by 5x. On another 117-dimension circuit, the proposed approach yields 364x speedup over Monte Carlo while existing importance sampling methods completely fail to provide reasonable accuracy.

In this paper, we propose a novel algorithm for structured sparsity reconstruction. This algorithm is based on the iterative reweighted least squares (IRLS) framework, and accelerated by the preconditioned conjugate gradient method. The convergence rate of the proposed algorithm is almost the same as that of the traditional IRLS algorithms, that is, exponentially fast. Moreover, with the devised preconditioner, the computational cost for each iteration is significantly less than that of traditional IRLS algorithms, which makes it feasible for large scale problems. Besides the fast convergence, this algorithm can be flexibly applied to standard sparsity, group sparsity, and overlapping group sparsity problems. Experiments are conducted on a practical application compressive sensing magnetic resonance imaging. Results demonstrate that the proposed algorithm achieves superior performance over 9 state-of-the-art algorithms in terms of both accuracy and computational cost.

Statistical circuit simulation is exhibiting increasing importance for circuit design under process variations. Existing approaches cannot efficiently analyze the failure probability for circuits with a large number of variation, nor handle problems with multiple disjoint failure regions. The proposed rare event microscope (REscope) first reduces the problem dimension by pruning the parameters with little contribution to circuit failure. Furthermore, we applied a nonlinear classifier which is capable of identifying multiple disjoint failure regions. In REscope, only likely-to-fail samples are simulated then matched to a generalized pareto distribution. On a 108-dimension charge pump circuit in PLL design, REscope outperforms the importance sampling and achieves more than 2 orders of magnitude speedup compared to Monte Carlo. Moreover, it accurately estimates failure rate, while the importance sampling totally fails because failure regions are not correctly captured.

Modern petroleum reservoir simulation serves as a primary tool for quantitatively managing reservoir production and planning new fields. It involves repeatedly solving the Jacobian of a set of strong nonlinear partial differential equations governing the mass and energy conduction and conservation. Most of the existing reservoir simulators adopt iterative solver with multiple stages of preconditioners, in which the incomplete LU (ILU) factorization is an outstanding universal smoother. However, it turns out that when the degree of freedom of each grid grows, ILU usually becomes the bottleneck of the solver. Moreover, ILU is difficult to parallelize due to its inherent data dependency. In this paper, we developed a sparse iterative solver with parallelized ILU and triangular solve using block-wise data structure. Compared with the state of art iterative solver on 14 industrial reservoir simulation matrices, the proposed ILU is 5.2x faster (on average) than the state of art iterative solver because of the block-wise data structure, which leads to 2.2x speedup on the total solver runtime. In addition, parallel ILU and triangular solve are developed to further accelerate the solver. To tackle the strong data dependency in ILU and triangular solve, we first partition the algorithm into separated tasks and construct a data flow graph to represent the data dependency. Then, tasks are scheduled in parallel according to the topological order of the data flow graph. On an 8-thread multicore architecture, we achieved another 3.6x speedup on ILU factorization, and 3.3x on triangular solve with good scalability.

Modern SRAM-based field-programmable gate arrays (FPGAs) are prone to single event upsets compared to application-specific integrated circuits. We propose a synthesis-based in-place x-filling algorithm by utilizing don't cares to augment the reliability of FPGA-based designs. Compared to circuit- and architecture-based solutions, our algorithm is in place, and does not incur area, power, performance, and design time overheads. Compared to other synthesis-based algorithms, we take into account widely accepted interconnect architecture. For the 10 largest combinational MCNC benchmark circuits mapped to 6-LUT architecture, our approach achieves up to 37% greater failure rate reduction, and up to 7 × runtime speedup, compared to the best known synthesis-based in-place algorithm, namely the in-place decomposition algorithm.

In this paper, we introduce a new matching method based on a novel locally affine-invariant geometric constraint and linear programming techniques. To model and solve the matching problem in a linear programming formulation, all geometric constraints should be able to be exactly or approximately reformulated into a linear form. This is a major difficulty for this kind of matching algorithm. We propose a novel locally affine-invariant constraint which can be exactly linearized and requires a lot fewer auxiliary variables than other linear programming-based methods do. The key idea behind it is that each point in the template point set can be exactly represented by an affine combination of its neighboring points, whose weights can be solved easily by least squares. Errors of reconstructing each matched point using such weights are used to penalize the disagreement of geometric relationships between the template points and the matched points. The resulting overall objective function can be solved efficiently by linear programming techniques. Our experimental results on both rigid and nonrigid object matching show the effectiveness of the proposed algorithm.

It has become increasingly challenging to model the stochastic behavior of analog/mixed-signal (AMS) circuits under large-scale process variations. In this paper, a novel moment-matching-based method has been proposed to accurately extract the probabilistic behavioral distributions of AMS circuits. This method first utilizes Latin hypercube sampling coupling with a correlation control technique to generate a few samples (e.g., sample size is linear with number of variable parameters) and further analytically evaluate the high-order moments of the circuit behavior with high accuracy. In this way, the arbitrary probabilistic distributions of the circuit behavior can be extracted using moment-matching method. More importantly, the proposed method has been successfully applied to high-dimensional problems with linear complexity. The experiments demonstrate that the proposed method can provide up to 1666X speedup over crude Monte Carlo method for the same accuracy.

Through-silicon-via (TSV) enables vertical connectivity between stacked chips or interposer and is a key technology for 3-D integrated circuits (ICs). While arrays of TSVs are needed in 3-D IC, there only exists a frequency-dependent resistance, inductance, conductance and capacitance circuit model for a pair of TSVs with coupling between them. In this paper, we develop a simple yet accurate circuit model for a multiport TSV network (e.g., coupled TSV array) by decomposing the network into a number of TSV pairs and then applying circuit models for each of them. We call the new model a pair-based model for the multiport TSV network. It is first verified against a commercial electromagnetic solver for up to 20 GHz and subsequently employed for a variety of examples for signal and power integrity analysis.

In this paper, we present HCS - Heterogeneous CRAM Scrubbing - for FPGAs. By utilizing stochastic fault modeling for SEUs in CRAM, we present a quantitative estimate of system MTTF improvement through CRAM scrubbing. HCS then leverages the fact that different SEUs have unequal effects on the circuit system operation, and thus the CRAM bits can be scrubbed at different rates based on the sensitivity of the bits to the circuit system failures. To maximize the improvement on system MTTF for a given circuit system, we present a dynamic programming algorithm which solves the problem efficiently and effectively. Through a detailed case study on system level study by an H.264/AVC decoder implemented on a Xilinx Virtex-5 FPGA, we show an estimation of 60% MTTF improvement by HCS over the existing homogeneous CRAM scrubbing method, while contributing virtually no area, performance and power overhead to the system.

Importance sampling is a popular approach to estimate rare event failures of SRAM cells. We propose to improve importance sampling by probability collectives. First, we use "Kullback-Leibler (KL) distance" to measure the distance between the optimal sampling distribution and the original sampling distribution of variable process parameters. Further, the probability collectives (PC) technique using immediate sampling is adapted to analytically minimize the KL distance and to obtain a sampling distribution as close to the optimal as possible. The proposed algorithm significantly accelerates the convergence of importance sampling. Experiments demonstrate that proposed algorithm is 5200X faster than the Monte Carlo approach and achieves more than $40X$ speedup over other existing state-of-the-art techniques without compromising estimation accuracy.

3-D vision technologies are extensively used in a wide variety of applications. Particularly glasses-based 3-D technology facilities are increasingly becoming affordable to our daily lives. Considering health issues raised by 3-D video technologies, to the best of our knowledge, most of the pilot studies are practiced in a highly-controlled laboratory environment only. In this paper, we present NeuroGlasses, a nonintrusive wearable physiological signal monitoring system to facilitate health analysis and diagnosis of 3-D video watchers. The NeuroGlasses system acquires health-related signals by physiological sensors and provides feedbacks of health-related features. Moreover, the NeuroGlasses system employs signal-specific reconstruction and feature extraction to compensate the distortion of signals caused by variation of the placement of the sensors. We also propose a server-based NeuroGlasses infrastructure where physiological features can be extracted for real-time response or collected on the server side for long term analysis and diagnosis. Through an on-campus pilot study, the experimental results show that NeuroGlasses system can effectively provide physiological information for healthcare purpose. Furthermore, it approves that 3-D vision technology has a significant impact on the physiological signals, such as EEG, which potentially leads to neural diseases.

Performance failure has become a significant threat to the reliability and robustness of analog circuits. In this article, we first develop an efficient non-Monte-Carlo (NMC) transient mismatch analysis, where transient response is represented by stochastic orthogonal polynomial (SOP) expansion under PVT variations and probabilistic distribution of transient response is solved. We further define performance yield and derive stochastic sensitivity for yield within the framework of SOP, and finally develop a gradient-based multiobjective optimization to improve yield while satisfying other performance constraints. Extensive experiments show that compared to Monte Carlo-based yield estimation, our NMC method achieves up to 700 X speedup and maintains 98% accuracy. Furthermore, multiobjective optimization not only improves yield by up to 95.3% with performance constraints, it also provides better efficiency than other existing methods.

Reliability has become an increasingly important concern for SRAM-based field programmable gate arrays (FPGAs). Targeting SEU (single event upset) in SRAM-based FPGAs, this article first develops an SEU evaluation framework that can quantify the failure sensitivity for each configuration bit during design time. This framework considers detailed fault behavior and logic masking on a post-layout FPGA application and performs logic simulation on various circuit elements for fault evaluation. Applying this framework on MCNC benchmark circuits, we first characterize SEUs with respect to different FPGA circuits and architectures, for example, bidirectional routing and unidirectional routing. We show that in both routing architectures, interconnects not only contribute to the lion's share of the SEU-induced functional failures, but also present higher failure rates per configuration bits than LUTs. Particularly, local interconnect multiplexers in logic blocks have the highest failure rate per configuration bit. Then, we evaluate three recently proposed SEU mitigation algorithms, IPD, IPF, and IPV, which are all logic resynthesis-based with little or no overhead on placement and routing. Different fault mitigating capabilities at the chip level are revealed, and it demonstrates that algorithms with explicit consideration for interconnect significantly mitigate the SEU at the chip level, for example, IPV achieves 61% failure rate reduction on average against IPF with about 15%. In addition, the combination of the three algorithms delivers over 70% failure rate reduction on average at the chip level. The experiments also reveal that in order to improve fault tolerance at the chip level, it is necessary for future fault mitigation algorithms to concern not only LUT or interconnect faults, but also their interactions. We envision that our framework can be used to cast more useful insights for more robust FPGA circuits, architectures, and better synthesis algorithms.

Process variation in nanometer technology is becoming an important issue for cutting-edge FPGAs with a multimillion gate capacity. Considering both die-to-die and within-die variations in effective channel length, threshold voltage, and gate oxide thickness, we first develop closed-form models of chip-level FPGA leakage and timing variations. Experiments show that the mean and standard deviation computed by our models are within 3% from those computed by Monte Carlo simulation. We also observe that the leakage and timing variations can be up to 3X and 1.9X, respectively. We then derive analytical yield models considering both leakage and timing variations, and use such models to evaluate the performance of FPGA device and architecture considering process variations. Compared to the baseline, which uses the VPR architecture and device setup based on the ITRS roadmap, device and architecture tuning improves leakage yield by 10.4%, timing yield by 5.7%, and leakage and timing combined yield by 9.4%. We also observe that LUT size of 4 gives the highest leakage yield, LUT size of 7 gives the highest timing yield, but LUT size of 5 achieves the maximum leakage and timing combined yield. To the best of our knowledge, this is the first in-depth study on FPGA architecture and device coevaluation considering process variation.

The most challenging problem in the current block-based statistical static timing analysis (SSTA) is how to handle the max operation efficiently and accurately. Existing SSTA techniques suffer from limited modeling capability by using a linear delay model with Gaussian distribution, or have scalability problems due to expensive operations involved to handle non-Gaussian variation sources or nonlinear delays. To overcome these limitations, we propose efficient algorithms to handle the max operation in SSTA with both quadratic delay dependency and non-Gaussian variation sources simultaneously. Based on such algorithms, we develop an SSTA flow with quadratic delay model and non-Gaussian variation sources. All the atomic operations, max and add, are calculated efficiently via either closed-form formulas or low dimension (at most 2-D) lookup tables. We prove that the complexity of our algorithm is linear in both variation sources and circuit sizes, hence our algorithm scales well for large designs. Compared to Monte Carlo simulation for non-Gaussian variation sources and nonlinear delay models, our approach predicts the mean, standard deviation and 95% percentile point with less than 2% error, and the skewness with less than 10% error.

This paper presents a parallel and incremental solver for stochastic capacitance extraction. The random geometrical variation is described by stochastic geometrical moments, which lead to a densely augmented system equation. To efficiently extract the capacitance and solve the system equation, a parallel fast-multipole-method (FMM) is developed in the framework of stochastic geometrical moments. This can efficiently estimate the stochastic potential interaction and its matrix-vector product (MVP) with charge. Moreover, a generalized minimal residual (GMRES) method with incremental update is developed to calculate both the nominal value and the variance. Our overall extraction show is called piCAP. A number of experiments show that piCAP efficiently handles a large-scale on-chip capacitance extraction with variations. Specifically, a parallel MVP in piCAP is up 3 × to faster than a serial MVP, and an incremental GMRES in piCAP is up to 15× faster than non-incremental GMRES methods.

Differential signaling has been widely used in high-speed interconnects. Signal integrity issues, such as inter-symbol interference (ISI) and crosstalk between the differential pair, however, still cause significant timing jitter and amplitude noise and heavily limit the performance of the differential link. The pre-emphasis filter is commonly used to reduce ISI but may potentially change the crosstalk behavior. In this paper, we first propose formula-based jitter and noise models considering the combined effect of ISI, crosstalk, and pre-emphasis filter. With the same set of input patterns, experiment shows our models achieve within 5% difference compared with SPICE simulation. By utilizing these formula-based models, we then develop algorithms to directly find out the input patterns for worst-case jitter and worst-case amplitude noise through pseudo-Boolean optimization (PBO) and mathematical programming. In addition, a heuristic algorithm is proposed to further reduce runtime. Experiments show our algorithms obtain more reliable worst-case jitter and noise compared with pseudorandom bit sequences simulation and, meanwhile, reduce runtime by 25× when using a general PBO solver and by 150× when using our proposed heuristic algorithm.

Stochastic device noise has become a significant challenge for high-precision analog/RF circuits, and it is particularly difficult to correctly include both white noise and flicker noise in the traditional transient verification with an efficient numerical solution. In this paper, a Non-Monte-Carlo transient noise analysis is developed. Both white noise and flicker noise are considered in Itô integral based stochastic differential algebraic equation (SDAE), which is solved by one-time calculation of variance using stochastic orthogonal polynomials (SoPs). Our work is the first in literature to provide the SoP-based SDAE solution with application for transient noise analysis. Experiments on a number of different analog circuits demonstrate that the proposed method is up to 488X faster than Monte Carlo method with similar accuracy, and achieves on average 6.8X speedup over the existing non-Monte-Carlo approaches.

The reliability of SRAM-based Field Programmable Gate Array (FPGA) is susceptible to Single Event Upset (SEU) fault. To investigate the fault impact, particular the fault in interconnects on FPGA functionality, this paper proposes a SEU fault analysis framework by evaluating the fault with a unified metric. This metric, termed as criticality, quantifies the sensitivity of FPGA functional failure to the SEU fault on logical and interconnect configuration bits. Considering the post layout information, our framework can characterize the SEU fault with respect to different FPGA architectures and CAD algorithms, such that the sensitivity of FPGA functional failure can be investigated in detail during design phase. The experiment result quantitatively shows that the configuration bits in interconnects dominate those in LUTs, several times both in bit number and criticality contribution. The ratio of their criticalities is even higher when LUT input size increases from 4 to 6. The higher criticality of interconnects than their LUT counterpart is due to their natural sensitivity to functional failure instead of their majority of bits. In addition, it is also shown that, among the three common types of switch boxes, the Subset switch box is less fault tolerant than Wilton and Universal.

Multi-agent simulation (MAS) is a widely used paradigm for modeling and simulating real world complex system, ranging from ant colony foraging to online trading. The performance of existing MAS software, however, suffers when simulating massive-scale multi-agent systems on traditional serial processing processors. In this paper, we propose an FPGA-based framework for massive-scale grid-based MAS. Memory interleaving, parallel tasks partition, and computing pipeline are adopted to improve system throughput. A classical MAS benchmark, Conway's Game of Life, is used as a case study to illustrate how to map grid-based models to our MAS framework. We implemented it on a Xilinx Virtex-5 FPGA board and achieved a speedup of 290x with two million agents, compared to the C implementation.

SRAM-based Field Programmable Gate Arrays (FPGAs) are vulnerable to Single Event Upsets (SEUs). We show that a large portion (40%-60% for the circuits in our experiments) of the total used LUT configuration bits are don't care bits, and propose to decide the logic values of don't care bits such that soft errors are reduced. Our approaches are efficient and do not change LUT level placement and routing. Therefore, they are suitable for design closure. For the ten largest combinational MCNC benchmark circuits mapped for 6-LUTs, our approaches obtain 20% chip level Mean Time To Failure (MTTF) improvements, compared to the baseline mapped by Berkeley ABC mapper. They obtain 3× more chip level MTTF improvements and are 128× faster when compared to the existing best in-place IPD algorithm.

This paper studies the SEU (Single Event Upset) fault for SRAM-based FPGAs. Considering detailed fault behavior on various circuit elements in a post-layout FPGA application, we develop a simulation-based SEU evaluation tool that quantifies fault contribution for each configuration bit. Using this tool and MCNC benchmark circuits, we study the fault characteristics of FPGA circuits and architectures. We show that interconnects not only contribute to the lion share of functional failures, but also have higher failure rate per configuration bit than LUTs. Particularly, multiplexers in local interconnects have the highest failure rate per bit. We find that tuning LUT and cluster sizes helps to reduce the rate (up to 38% in our experiments). In addition, we evaluate two recent fault mitigation algorithms IPD and IPF, which reduce LUT faults by an average of 74% and 15% respectively. But when interconnects are taken into account, the reduction via IPD which considers only LUT faults is merely 6% on chip level. Yet the reduction via IPF which implicitly considers interconnect faults is still around 15%. Therefore, synthesis algorithm should be evaluated with interconnect faults and future algorithms should be developed with consideration of interconnect faults explicitly.

Modern SRAM-based FPGAs (Field Programmable Gate Arrays) use multiplexer-based unidirectional routing, and SRAM configuration cells in these multiplexers contribute to the majority of soft errors in FPGAs. In this paper, we formulate an In-Placed inVersion (IPV) on LUT (Look-Up Table) logic polarities to reduce the Soft Error Rate (SER) at chip level, and reveal a locality and NP-Hardness of the IPV problem. We then develop an exact algorithm based on the binary integer linear programming (ILP) and also a heuristic based on the simulated annealing (SA), both enabled by the locality. We report results for the 10 largest MCNC combinational benchmarks synthesized by ABC and then placed and routed by VPR. The results show that IPV obtains close to 4× chip level SER reduction on average and SA is highly effective by obtaining the same SER reduction as ILP does. A recent work IPD has the largest LUT level SER reduction of 2.7× in literature, but its chip level SER reduction is merely 7% due to the dominance of interconnects. In contrast, SA-based IPV obtains nearly 4× chip level SER reduction and runs 30× faster. Furthermore, combining IPV and IPD leads to a chip level SER reduction of 5.3×. This does not change placement and routing, and does not affect design closure. To the best of our knowledge, our work is the first in-depth study on SER reduction for modern multiplexer-based FPGA routing by in-placed logic re-synthesis.

Stochastic device parameter variations have dramatically increased beyond the scale of 65nm and can significantly lead to large mismatch for analog circuits. To estimate unknown analog circuit behavior in performance space under the given stochastic variations in parameter space, many state-of-art approaches have been developed recently. However, either Gaussian distribution or response surface model (RSM) with analytical formulae has to be assumed when connecting performance space and parameter space. A novel point-estimation based approach has been proposed in this paper to capture arbitrary stochastic distributions for analog circuit behaviors in performance space. First, to evaluate high-order moments of circuit behavior in an accurate fashion, the point-estimation method has been applied with only a few number of simulations. Then, probability density function (PDF) of circuit behavior can be efficiently extracted by the obtained high-order moments. This method is further extended for multiple parameters under linear complexity. Extensive numerical experiments on a number of different circuits have demonstrated that the proposed point-estimation method can provide up to 181X runtime speedup with the same accuracy, when compared with Monte Carlo method. Moreover, it can further achieve up to 15X speedup over the RSM-based method such as APEX with the similar accuracy.

Modeling spatial variation is important for statistical analysis. Most existing works model spatial variation as spatially correlated random variables. We discuss process origins of spatial variability, all of which indicate that spatial variation comes from deterministic across-wafer variation, and purely random spatial variation is not significant. We analytically study the impact of across-wafer variation and show how it gives an appearance of correlation. We have developed a new die-level variation model considering deterministic across-wafer variation and derived the range of conditions under which ignoring spatial variation altogether may be acceptable. Experimental results show that for statistical timing and leakage analysis, our model is within 2% and 5% error from exact simulation result, respectively, while the error of the existing distance-based spatial variation model is up to 6.5% and 17%, respectively. Moreover, our new model is also faster than the spatial variation model for statistical timing analysis and faster for statistical leakage analysis.

Power delivery network (PDN) is a distributed resistance-inductance-capacitance (RLC) network with its dominant resonance frequency in the low-to-middle frequency range. Though high-performance chips' working frequencies are much higher than this resonance frequency in general, chip runtime loading frequency is not. When a chip executes a chunk of instructions repeatedly, the induced current load may have harmonic components close to this resonance frequency, causing excessive power integrity degradation. Existing PDN design solutions are, however, mainly targeted at reducing high-frequency noise and not effective to suppress such resonance noise. In this work, we propose a novel approach to proactively suppress this type of noise. A method based on the high dimension generalized Markov process is developed to predict current load variation. Based on such prediction, a clock frequency actuator design is proposed to proactively select an optimal clock frequency to suppress the resonance. To the best of our knowledge, this is the first in-depth study on proactively reducing instruction loop induced PDN resonance noise at the runtime.

In this paper we study statistics of statistics. Statistical modeling and analysis have become the mainstay of modern design-manufacturing flows. Most analysis techniques assume that the statistical variation models are reliable. However, due to limited number of samples (especially in the case of lot-to-lot variation), calibrated models have low degree of confidence. The problem is further exacerbated when production volumes are low (¿ 65 lots) causing additional loss of confidence in the statistical analysis (since production only sees a small snapshot of the entire distribution). The problem of confidence in statistical analysis is going to be further worsened with advent of 450mm wafers. We mathematically derive the confidence intervals for commonly used statistical measures (mean, variance, percentile corner) and analysis (SPICE corner extraction, statistical timing). Our estimates are within 2% of simulated confidence values. Our experiments (with variability assumptions derived from test silicon data from a 45nm industrial process) indicate that for moderate characterization volumes (10 lots) and low-to-medium production volumes (15 lots), a significant guardband (e.g., 34.7% of standard deviation for single parameter corner, 38.7% of standard deviation for SPICE corner, and 52% of standard deviation for 95%-tile point of circuit delay) is needed to ensure 95% confidence in the results. The guardbands are non-negligible for all cases when either production or characterization volume is not large. We also study the interesting one production lot case which may be common for prototyping as well as for academic designs. The proposed methods require are not runtime-intensive (always within 10s) as they require Monte-Carlo simulations on closed form expressions.

We present a fault-tolerant post-mapping resynthesis for FPGA-based designs that exploits the dual-output feature of modern FPGA architectures to improve the reliability of a mapped circuit against faults. Emerging FPGA architectures, such as 6-LUTs in Xilinx Virtex-5 and 8-input ALMs in Altera Stratix-III, have a secondary LUT output that allows access to non-occupied SRAM bits. We show that this architectural feature can be used to build redundancy for fault masking with limited area and performance overhead. Our algorithm improves reliability of a mapping by performing two basic operations: duplication (in which free configuration bits are used to duplicate a logic function whose value is obtained at the secondary output) and encoding (in which two copies of the same logic function are ANDed or ORed together in the fanout of the duplicated logic). The problem of fault tolerant post-mapping resynthesis is then formulated as the optimal duplication and encoding scheme that ensures the minimal circuit fault rate w.r.t. a stochastic single fault model. We present an ILP formulation of this problem and an efficient algorithm based on generalized network flow. On MCNC benchmarks, experimental results show that for combinational circuits the proposed approach improves mean-time-to-failure(MTTF) by 27% with 4% area overhead, and the proposed approach with explicit area redundancy improves MTTF by 113% with 36% area overhead, compared to the baseline mapping by ABC. This provides a viable fault tolerance solution for non-mission critical applications compared to TMR (triple modular redundancy) which has a 5x–6x area overhead.

In this paper, we present a new object matching algorithm based on linear programming and a novel locally affine-invariant geometric constraint. Previous works have shown possible ways to solve the feature and object matching problem by linear programming techniques. To model and solve the matching problem in a linear formulation, all geometric constraints should be able to be exactly or approximately reformulated into a linear form. This is a major difficulty for this kind of matching algorithms. We propose a novel locally affine-invariant constraint which can be exactly linearized and requires a lot fewer auxiliary variables than the previous work does. The key idea behind it is that each point can be exactly represented by an affine combination of its neighboring points, whose weights can be solved easily by least squares. The resulting overall objective function can then be solved efficiently by linear programming techniques. Our experimental results on both rigid and non-rigid object matching show the advantages of the proposed algorithm.

With technology scaling down to 90nm and below, many yield-driven design and optimization methodologies have been proposed to cope with the prominent process variation and to increase the yield. A critical issue that affects the efficiency of those methods is to estimate the yield when given design parameters under variations. Existing methods either use Monte Carlo method in performance domain where thousands of simulations are required, or use local search in parameter domain where a number of simulations are required to characterize the point on the yield boundary defined by performance constraints. To improve efficiency, in this paper we propose QuickYield, a yield surface boundary determination by surface-point finding and global-search. Experiments on a number of different circuits show that for the same accuracy, QuickYield is up to 519X faster compared with the Monte Carlo approach, and up to 4.7X faster compared with YENSS, the fastest approach reported in literature.

Logic synthesis for soft error mitigation is increasingly important in a wide range of applications of FPGAs. We present R2, an algorithm for rewiring a post-layout LUT-based circuit that reduces the overall criticality of the circuit, where criticality is the fraction of primary inputs that lead to observable errors at the primary outputs if an single event upset inverts a configuration bit. Our algorithm explicitly optimizes the robustness of the interconnect, the dominant component of FPGAs. The key idea of R2 is to exploit Boolean flexibilities in the circuit implementation to replace wires with high criticality with those with lower criticality while preserving the circuit functionality. We estimate criticalities using a Monte Carlo fault simulation. We represent flexibilities using SPFDs (Set of Pairs of Functions to be Distinguished), and use criticality information to choose candidates for rewiring, assigning the maximum flexibility to high criticality wires. Compared to IPR, a recent robust logic optimization, our implementation increases MTTF (Mean Time to Failure) by 24%, showing for the first time, the advantages of exploiting Boolean flexibilities in optimizing for robustness. In addition, R2 achieves 5% and 2% more reduction on the number of wires and LUTs in an FPGA than that obtained by the existing rewiring algorithm for area minimization.

State-of-charge (SOC) measures energy left in a battery, and it is critical for modeling and managing batteries. Developing efficient yet accurate SOC algorithms remains a challenging task. Most existing work uses regression based on a time-variant circuit model, which may be hard to converge and often does not apply to different types of batteries. Knowing open-circuit voltage (OCV) leads to SOC due to the well known mapping between OCV and SOC. In this paper, we propose an efficient yet accurate OCV algorithm that applies to all types of batteries. Using linear system analysis but without a circuit model, we calculate OCV based on the sampled terminal voltage and discharge current of the battery. Experiments show that our algorithm is numerically stable, robust to history dependent error, and obtains SOC with less than 4% error compared to a detailed battery simulation for a variety of batteries. Our OCV algorithm is also efficient, and can be used as a real-time electro-analytical tool revealing what is going on inside the battery.

Reliability analysis for a logic circuit is one of the primary tasks in fault-tolerant logic synthesis. Given a fault model, it quantifies the impact of faults on the full-chip fault rate. We present RALF, an exact algorithm for calculating the reliability of a logic circuit. RALF is based on the compilation of a circuit to deterministic decomposable negation normal form (d-DNNF), a representation for Boolean formulas that can be more succinct than BDDs. Our algorithm can solve a large set of MCNC benchmark circuits within 5 minutes, enabling an optimality study of Monte Carlo simulation, a popular estimation method for reliability analysis, on real benchmark circuits. Our study shows that Monte Carlo simulation with a small set of random vectors generally has a high fidelity for the computation of full-chip fault rates and the criticality of single gates. While we focus on reliability analysis, RALF can also be used to efficiently locate random pattern resistant faults. This can be used to identify where methods other than random simulation should be used for accurate criticality calculations and where to enhance the testability of a circuit.

Boolean matching is one of the most important fundamental algorithms in FPGA synthesis and architecture evaluations. However, existing Boolean matchers for FPGAs, even with numerous improvements, are still not scalable to complex PLBs and large circuits. This paper aims to improve the efficiency of Boolean matching using lookup tables implemented by Bloom filters, which can store terabyte-lookup tables with a desktop PC. The key improvement is to efficiently prune a large set of non-implementable functions use the Bloom filter. Using the area-oriented re-synthesis as an application, the experiments on a broad selection of benchmark sets show that the re-synthesis with our improved Boolean matcher is 18X faster than the one with an optimized SAT-based Boolean matcher, while preserving the quality of the re-synthesizer.

The programmable logic block (PLB) in a modern FPGA features a built-in carry chain (or adder) and a decomposable LUT, where such an LUT may be decomposed into two or more smaller LUTs. Leveraging decomposable LUTs and underutilized carry chains, we propose to decompose a logic function in a PLB into two subfunctions and to combine the subfunctions via a carry chain to make the circuit more robust against single-event upsets(SEUs). Note that such decomposition can be implemented using the decomposable LUT and carry chain in the original PLB without changing the PLB-level placement and routing. Therefore, it is an in-place decomposition (IPD) with no area and timing overhead at the PLB level and has an ideal design closure between logic and physical syntheses. For 10 largest combinational MCNC benchmark circuits with a conservative 20% utilization rate for carry chain, IPD improves MTTF (mean time to failure) by 1.43 and 2.70 times respectively, for PLBs similar to those in Xilinx Virtex-5 and Altera Stratix-IV.

Power integrity gains growing importance for integrated circuits in 45nm technology and beyond. This paper provides a tutorial of modeling and design for beyond the die power integrity. We explain the background of simultaneous switching noise (SSN) and its impacts on circuit designs. We discuss various models of different accuracy and complexity for the board, package and chip, and suggest how to select proper ones for board-package-chip co-simulation and co-design of SSN. We then review different design techniques to suppress SSN, including I/O planning and placement, decoupling capacitor allocation, package layer stacking and power/ground plane stapling.

Software as a Service (SaaS) 1.0 signifcantly lowers the infrastructure and maintenance cost and increases the accessibility of the software by hosting software via the web. Compared with SaaS 1.0, SaaS 2.0 is more flexible since it leverages software tools from both server and client sides with closer interaction between them. The SaaS 2.0 paradigm provides new opportunities and challenges for EDA. In this paper, we take Boolean matching, one of the core sub algorithms in logic synthesis for field programmable gate arrays (FPGAs), as a case study. We investigate the advantages and challenges of implementing a scalable EDA algorithm under SaaS 2.0 paradigm from a technical perspective. We propose SaaS-BM, a new Boolean matching algorithm customized to take full advantage of the cloud while addressing concerns such as security and the internet bandwidth limit. Extensive experiments are performed under a networked environment with concurrent accesses. Integrated into a post-mapping re-synthesis algorithm minimizing area, the proposed SaaS-BM is 863X times faster than state-of-the-art SAT-based Boolean matching with 0.5% area overhead. Compared with a recent Bloom Filter-based Boolean matching algorithm, our proposed SaaS-BM is 53X times faster on large circuits with no area overhead.

This paper presents a technology mapping algorithm for field-programmable gate array architectures with dual supply voltages (Vdds) for power optimization. This is done with the guarantee that the mapping depth of the circuit will not increase compared to the circuit with a single Vdd. This paper also presents an enhanced clustering algorithm that considers dual supply voltages, honoring the dual-Vdd mapping solution. To carry out various comparisons, we first design a single-Vdd mapping algorithm, named SVmap-2, which achieves a 3.8% total power reduction (15.6% dynamic power reduction) over a previously published low-power mapping algorithm, Emap . We then show that our dual-Vdd mapping algorithm, named DVmap-2, can further improve total power savings by 12.8% over SVmap-2, with a 52.7% dynamic power reduction. Compared to the early single-Vdd version SVmap , DVmap-2 is 14.3% better for total power reduction. This is achieved through an ideal selection of the low-Vdd/high-Vdd ratio and the consideration of various voltage changing scenarios during the mapping process.

Off-chip substrate routing for high-density packages is challenging due to requirements such as high density, lack of vertical detour, non-Manhattan routing, and primarily planar routing. The existing substrate routing algorithms often result in a large number of unrouted nets that have to be routed manually. This article develops an effective yet efficient diffusion-driven method D-Router to reduce congestion. Starting with an initial routing, we develop an effective diffusion-based congestion reduction. We iteratively find a congested window and spread out connections to reduce congestion inside the window by a simulated diffusion process based on the duality between congestion and concentration. The window is released after the congestion is eliminated. Compared with the state-of-the-art substrate routing method that leads to 480 nets unrouted for ten industrial designs with a total of 6415 nets, the D-Router reduces the amount of unrouted nets to 104, a reduction to the 4.6 multiple. In addition, the D-Router obtains a similar reduction on unrouted nets but runs up to 94 times faster when compared with a negotiation-based substrate routing.

Parameterized model-order reduction is useful for very large-scale integration VLSI physical design and optimization. In this paper, we propose an efficient yet accurate parameterized model-order reduction method EMPIRE for multiple parameters. It uses implicit moment matching to efficiently handle high-order moments of a large number of parameters. In addition, it can match the moments of different parameters with different accuracy according to their influence on the objective under study, and such influence is measured by the 2-norm of their coefficient matrix in the canonical form. It develops three algorithms to further suppress the size of the reduced model by finding a projection matrix that has a much smaller number of columns than the original one. Experimental results show that compared with the best existing algorithm CORE that uses explicit moment matching for the parameters, EMPIRE reduces waveform error by 47.8 × at a similar runtime.

Abstract—To efficiently analyze the large-scale interconnect dominant circuits with inductive couplings (mutual inductances), this paper introduces a new state matrix, called VNA, to stamp inverse-inductance elements by replacing inductive-branch current with flux. The state matrix under VNA is diagonal-dominant, sparse, and passive. To further explore the sparsity and hierarchy at the block level, a new matrix-stretching method is introduced to reorder coupled fluxes into a decoupled state matrix with a bordered block diagonal (BBD) structure. A corresponding block-structure-preserved model-order reduction, called BVOR, is developed to preserve the sparsity and hierarchy of the BBD matrix at the block level. This enables us to efficiently build and simulate the macromodel within a SPICE-like circuit simulator. Experiments show that our method achieves up to 7 faster modeling building time, up to 33 faster simulation time, and as much as 67 smaller waveform error compared to SAPOR [a second-order reduction based on nodal analysis (NA)] and PACT (a first-order 2 2 structured reduction based on modified NA). Index Terms—Circuit simulation, high-speed interconnect model, model-order reduction. I.

Majority of practical multivariate statistical analyses and optimizations model interdependence among random variables in terms of the linear correlation among them. Though linear correlation is simple to use and evaluate, in several cases non-linear dependence between random variables may be too strong to ignore. In this paper, We propose polynomial correlation coefficients as simple measure of multivariable non-linear dependence and show that need for modeling non-linear dependence strongly depends on the end function that is to be evaluated from the random variables. Then, we calculate the errors in estimation which result from assuming independence of components generated by linear de-correlation techniques such as PCA and ICA. The experimental result shows that the error predicted by our method is within 1% error compared to the real simulation. In order to deal with non-linear dependence, we further develop a target function driven component analysis algorithm (FCA) to minimize the error caused by ignoring high order dependence and apply such technique to statistical leakage power analysis and SRAM cell noise margin variation analysis. Experimental results show that the proposed FCA method is more accurate compared to the traditional PCA or ICA.

Power delivery network (PDN) is a distributed RLC network with its dominant resonance frequency in the low-to-middle frequency range. Though high-performance chips' working frequencies are much higher than this resonance frequency in general, chip runtime loading frequency is not. When a chip executes a chunk of instructions repeatedly, the induced current load may have harmonic components close to this resonance frequency, causing excessive power integrity degradation. Existing PDN design solutions are, however, mainly targeted at reducing high-frequency noise and not effective to suppress such resonance noise. In this work, we propose a novel approach to proactively suppress this type of noise. A method based on a high dimension generalized Markov process is developed to predict current load variation. Based on such prediction, a clock frequency actuator design is proposed to proactively select an optimal clock frequency to suppress the resonance. To the best of our knowledge, this is the first in-depth study on proactively reducing runtime instruction execution induced PDN resonance noise.

Power distribution networks (PDNs) are designed and analyzed iteratively. Random walk is among the most efficient methods for PDN analysis. We develop in this paper an incremental and on-demand random walk to reduce iterative analysis time. During each iteration, we map the design changes as positive or negative random walks for observed nodes. To update PDN analysis result, we only need to apply these extra positive or negative walks, instead of doing all walks from scratch. We show that different execution orders for these walks do not affect accuracy but do affect the runtime because of the cancellation between positive and negative walks. Considering this cancellation effect, we optimize the walk order by solving a min-energy electromagnetic particles placement problem and, as a result, further reduce the runtime to about 8times compared to the worst order. Experiments show that, compared to random walk from scratch, our algorithm has similar accuracy but reduces the iterative analysis time by up to 18times for on-chip PDN sizing, and by up to 13times for package ball assignment with substrate routing. In addition, our incremental random walk has a linear time complexity with respect to the number of observed nodes and is more suitable for on-demand analysis, compared to random walk from scratch and its big warm-up cost.

Modeling spatial variation is important for statistical analysis. Most existing works model spatial variation as spatially correlated random variables. We discuss process origins of spatial variability, all of which indicate that spatial variation comes from deterministic across-wafer variation, and purely random spatial variation is not significant. We analytically study the impact of across-wafer variation and show how it gives an appearance of correlation. We have developed a new dielevel variation model considering deterministic across-wafer variation and derived the range of conditions under which ignoring spatial variation altogether may be acceptable. Experimental results show that our model is within 1% error from exact simulation result while the error of the existing distance-based spatial variation model is up to 8%. Moreover, our new model is also 10X faster than the spatial variation model for Monte-Carlo analysis.

It is unknown how to include stochastic process variation into fast-multipole-method (FMM) for a full chip capacitance extraction. This paper presents a parallel FMM extraction using stochastic polynomial expanded geometrical moments. It utilizes multi-processors to evaluate in parallel for the stochastic potential interaction and its matrix-vector product (MVP) with charge. Moreover, a generalized minimal residual (GMRES) method with deflation is modified to incrementally consider the nominal value and the variance. The overall extraction flow is called piCAP. Experiments show that the parallel MVP in piCAP is up to 3X faster than the serial MVP, and the incremental GMRES in pi-CAP is up to 15X faster than non-incremental GMRES methods.

We describe In-Place Reconfiguration (IPR) for LUT-based FPGAs, an algorithm that maximizes identical configuration bits for complementary inputs of a LUT thereby reducing the propagation of faults seen at a pair of complementary inputs. Based on IPR, we develop a fault-tolerant logic resynthesis algorithm which decreases the circuit fault rate while preserving functionality and topology of the LUT-based logic network. Since the topology is preserved, the resynthesis algorithm can be applied post-layout and without changes in physical design. Compared to the state-of-the-art academic technology mapper Berkeley ABC, IPR reduces the relative fault rate by 48% and increases MTTF by 1.94x with the same area and performance, and IPR combined with a previous fault-tolerant logic resynthesis algorithm (ROSE) reduces the relative fault rate by 49% and increases MTTF by 2.40x with 19% less area but same performance. The above improvement assumes a stochastic single fault and more improvement is expected for multi-fault models.

Joint design time and post-silicon optimization for analog circuits has been an open problem in literature because of the complex nature of analog circuit modeling and optimization. In this paper we formulate the co-optimization problem for digitally tuned analog circuits to optimize the parametric yield, subject to power and area constraints. A general optimization framework combing the branch-and-bound algorithm and gradient ascent method is proposed. We demonstrate our framework with two examples in high-speed serial link, the transmitter design and the phase-locked-loop (PLL) design. Simulation results show that compared with the design heuristic from analog designers' perspective, joint design-time and post-silicon optimization can improve the yield by up to 47% for transmitter design and up to 56% for PLL design under the same area and power constraints. To the best of the authors' knowledge, this is the first in-depth study on yield-driven analog circuit design technique that optimizes post-silicon tuning together with the design-time optimization.

O-chip substrate routing for high density packages is chal-lenging, and the existing substrate routing algorithms often result in a large number of unrouted nets that have to be routed manually. This paper develops an eective yet e-cient diusion-driven method D-Router to improve routabil-ity by a simulated diusion process based on the duality between congestion and concentration. Compared with a recently published A*-based algorithm used in a state of the art commercial tool and with similar routability and run-time as the negotiation based routing, D-Router reduces the number of unrouted nets by 4.6x with up to 94x runtime reduction.

Nominal power estimation is quick but gives minimal information. Statistical power analysis can provide information on yield, chip robustness, etc., but current methods are unnecessarily slow and complex. This is primarily because existing leakage-power models, which model leakage power as lognormal distribution and calculate chip leakage power based on Wilkinson's approach, are not directly additive. Hence, for each incremental change of the circuit, the covariances between each pair of circuit elements need to be recalculated, which is inefficient. In this paper, we proposed a simple additive polynomial leakage-variation model. With additivity, we can calculate chip leakage power and leakage power after incremental change very efficiently. Experimental results show that our method is five times faster than the existing Wilkinson's approach while having no accuracy loss in mean estimation and about 1% accuracy loss in standard-deviation and 99%-percentile-point estimations.

For nanometer manufacturing, process variation causes significant uncertainty for circuit performance verification. Statistical static timing analysis (SSTA) is thus developed to estimate timing distribution under process variation. Most existing SSTA techniques have difficulty in handling the non-Gaussian variation distribution and nonlinear dependence of delay on variation sources. To address this problem, we first propose a new method to approximate the max operation of two non-Gaussian random variables through second-order polynomial fitting. With such approximation, we then present new non-Gaussian SSTA algorithms for three delay models: quadratic model, quadratic model without crossing terms (semiquadratic model), and linear model. All the atomic operations (max and sum) of our algorithms are performed by closed-form formulas; hence, they scale well for large designs. Experimental results show that compared to the Monte Carlo simulation, our approach predicts the mean, standard deviation, skewness, and 95% percentile point within 1%, 1%, 6%, and 1% error, respectively.

Small gates, such as AND2, XOR2, and MUX2, have been mixed with lookup tables (LUTs) inside programmable logic blocks (PLBs) to reduce area and power and increase performance in FPGAs. However, it is unclear whether incorporating macrogates with wide inputs inside PLBs is beneficial. In this paper, we first develop a methodology to extract a small set logic functions that are able to implement a large portion of functions for given FPGA applications, and propose a heterogeneous PLB with one LUT and one macrogate for the selected logic functions. Furthermore, we develop a synthesis flow for such heterogeneous PLBs, including a cut-based delay and area optimized technology mapping, a mixed binary integer and linear programming-based postmapping area recovery to balance the utilization of macrogates and LUTs, and a SAT-based PLB architecture-aware packing. Experiments using over 70 industrial benchmark applications show that we can extract four six-input logic functions to cover more than 50% functions of these applications, and the proposed synthesis flow reduces area by 5% compared to an alternative flow without the postmapping area recovery when both have the optimal logic depth. Compared to the PLB with mixed LUT-4 and small macrogates (XOR2 and MUX2), the PLB with mixed LUT-4 and four-input macrogate reduces logic depth by 6% (and up to 42%) for the aforementioned applications.

Off-chip substrate routing for high-density packages is on the critical path for time to market. Compared with on-chip routers, existing commercial tools for off-chip routing have lower routability and often result in a large number of unrouted nets for manual routing. In this paper, we explain why planar routing is still required with multiple routing layers for substrate routing and then propose a flexible via-staggering technique to improve routability. In addition, we develop an efficient yet effective substrate routing algorithm, applying dynamic pushing to tackle the net ordering problem and reordering and rerouting to further reduce wire length and congestion. Compared with an industrial design tool that leaves 936 nets unrouted for nine industrial designs with a total of 6100 nets, our algorithm reduces the unrouted nets to 212, a 4.5-times net number reduction, which translates to design time reduction.

The existing work on via allocation in 3D ICs ignores power/ground vias' ability to simultaneously reduce voltage bounce and remove heat. This article develops the first in-depth study on the allocation of power/ground vias in 3D ICs with simultaneous consideration of power and thermal integrity. By identifying principal ports and parameters, effective electrical and thermal macromodels are employed to provide dynamic power and thermal integrity as well as sensitivity with respect to via density. With the use of sensitivity, an efficient via allocation simultaneously driven by power and thermal integrity is developed. Experiments show that, compared to sequential power and thermal optimization using static integrity, sequential optimization using the dynamic integrity reduces nonsignal vias by up to 18%, and simultaneous optimization using dynamic integrity further reduces nonsignal vias by up to 45.5%.

In the nanometer manufacturing region, process variation causes significant uncertainty for circuit performance verification. Statistical static timing analysis (SSTA) is thus developed to estimate timing distribution under process variation. However, most of the existing SSTA techniques have difficulty in handling the non-Gaussian variation distribution and non-linear dependency of delay on variation sources. To solve such a problem, in this paper, we first propose a new method to approximate the max operation of two non-Gaussian random variables through second-order polynomial fitting. We then present new non-Gaussian SSTA algorithms under two types of variational delay models: quadratic model and semi-quadratic model (i.e., quadratic model without crossing terms). All atomic operations (such as max and sum) of our algorithms are performed by closed-form formulas, hence they scale well for large designs. Experimental results show that compared to the Monte-Carlo simulation, our approach predicts the mean, standard deviation, and skewness within 1%, 1%, and 5% error, respectively. Our approach is more accurate and also 20x faster than the most recent method for non-Gaussian and nonlinear SSTA.

The time-varying workload for multimedia applications poses a great challenge for the efficient performance of dynamic voltage scaling (DVS) algorithms. While many DVS algorithms have been proposed for real-time applications, there does not yet exist a systematic method for evaluating the optimality of such DVS algorithms. In this paper, we propose an offline linear programming (LP) method to determine the minimum energy consumption for processing multimedia tasks under stringent delay deadlines. Based on this lower bound, we evaluate the efficiency of various existing DVS algorithms. Furthermore, we modify the LP formulation to construct an online robust sequential linear programming DVS algorithm for real-time multimedia processing. Simulation results from decoding over a wide range of video sequences shows that on average, our online algorithm consumes less than 1% more energy than the optimal lower bound while dropping only 0.1% of all scheduled decoding jobs, while the existing best algorithm consumes roughly 3% more energy at the same miss rate.

We propose a new resynthesis algorithm for FPGA area reduction. In contrast to existing resynthesis techniques, which consider only single-output Boolean functions and the combinational portion of a circuit, we consider multi-output functions and retiming, and develop effective algorithms that incorporate recent improvements to SAT-based Boolean matching. Our experimental results show that with the optimal logic depth, the resynthesis considering multi-output functions reduces area by up to 0.4% compared to the one considering single-output functions, and the sequential resynthesis reduces area by up to 10% compared to combinational resynthesis when both consider multi-output functions. Furthermore, our proposed resynthesis algorithm reduces area by up to 16% compared to the best existing academic technology mapper, Berkeley ABC.

Compared with on-chip routers, the existing commercial tools for off-chip routing have a much lower routability and often result in a large number of unrouted nets for manual routing. In this paper, we develop an effective, yet efficient, substrate routing algorithm, applying dynamic pushing to alleviate the net ordering problem and reordering and rerouting for further wire length and congestion reduction. Compared with an industrial design tool that leaves 936 nets unrouted for nine industrial designs with a total of 6100 nets, our algorithm reduces the unrouted nets to 212, a 4.5-times net number reduction and practically more design time reduction.

This paper develops a trace-based framework to enable concurrent process and FPGA architecture co-development. Based on process parameters and traces for FPGA applications, the framework calculates the chip level performance and power distribution and soft error rate (SER) with consideration of process variations and device aging. As examples to utilize the framework, the paper further applies heterogeneous gate lengths to logic and interconnects for energy reduction, and studies the interaction between device aging, process variation and SER

We present FPGA logic synthesis algorithms for stochastic fault rate reduction in the presence of both permanent and transient defects. We develop an algorithm for fault tolerant Boolean matching (FTBM), which exploits the flexibility of the LUT configuration to maximize the stochastic yield rate for a logic function. Using FTBM, we propose a robust resynthesis algorithm (ROSE) which maximizes stochastic yield rate for an entire circuit. Finally, we show that existing PLB (programmable logic block) templates for area-aware Boolean matching and logic resynthesis are not effective for fault tolerance, and propose a new robust template with path re-convergence. Compared to the state-of-the-art academic technology mapper Berkeley ABC, ROSE using the proposed robust PLB template reduces the fault rate by 25% with 1% fewer LUTs, and increases MTBF (mean time between failures) by 31%, while preserving the optimal logic depth.

This paper presents a fast and accurate solution, namely Fashion, to routability-driven global routing problem. Fashion is based on two efficient yet effective techniques: 1) dynamic pattern routing (DPR) and 2) movable-segment-driven DPR. These two techniques enable Fashion to explore large solution space to achieve high routability with low time complexity. Compared with BoxRouter, Fashion has a shorter wire length and reduces overflow and runtime by 5 and 15 times, respectively. Compared with FastRoute, Fashion has similar runtime but 90% smaller overflow and 1.9% shorter wire length. Fashion is significantly better than Labyrinth and Fengshui in terms of overflow, wire length, and runtime.

Boolean matching is one of the enabling techniques for technology mapping and logic resynthesis of field-programmable gate arrays (FPGAs). Boolean satisfiability (SAT)-based Boolean matching (SAT-BM) has been proposed, but computational complexity prohibits its practical deployment. In this paper, we leverage symmetries present in both Boolean functions and target FPGA architectures to prune the solution space, and we also propose some techniques to reduce the replication runtime for SAT instance generation using the incremental SAT reasoning engine. Experiment shows that our SAT-BM reduces runtime by 226times compared with the original SAT-BM algorithm, making SAT-BM more practical.

This paper solves the variation-aware decoupling capacitance (decap) budgeting problem. Unlike previous works which only consider worst case design, for the first time, we consider the input of both process variation and operation variation for decap budgeting. A novel stochastic current model is proposed that efficiently and accurately captures temporal correlation between clock cycles, logic-induced correlation between ports, and current variation due to process variation with spatial correlation. An iterative alternative programming algorithm that is applicable to a variety of current models is then developed. Compared with the baseline model which assumes maximum current peaks at all ports, the model considering temporal correlation reduces noise by up to 5times, and the model considering both temporal and logic-induced correlations reduces noise by up to 17times. Compared with using deterministic process parameters, considering process variation (in particular Leffvariation) reduces the mean noise by up to 4times and 3sigma noise by up to 13times when both applying the current model with temporal and logic-induced correlations. Note that stochastic optimization has been used mainly for process variation in the literature, but this paper convincingly demonstrate that stochastic optimization considering operation variation is effective to reduce overdesign introduced by worst case design for power integrity. Such stochastic optimization has a wide scope of applications to design problems. To the best of our knowledge, this is the first in-depth study on decap insertion for power network design considering current correlations including process variation.

This paper presents the first in-depth study on dual-Vddbuffer insertion for power minimization under delay constraint. Compared with delay-optimal singleVddbuffer insertion, the dual-Vddbuffer insertion reduces power by 16%. Such power reduction increases when the delay specification is relaxed. Whereas the van Ginneken algorithm can be extended to handle the new problem formulation optimally, its time complexity increases from quadratic time (O(|B|n2)) to pseudopolynomial time (O(|B|n3cmax2log(ncmax)), where |B| is the size of buffer library,nis the number of buffer stations, andcmaxis proportional to the number of all possible subtrees of the net. To improve the time complexity, we propose an approximation technique by sampling subsolutions (i.e., options) and apply predictive min-delay and prebuffer slack pruning rules from a related work. Experiments show that sampling is most effective to reduce run time, whereas the two pruning rules further improve efficiency and accuracy loss due to sampling. We show that our proposed algorithm has linear time complexity with respect to the tree size. It runs over 1000 times faster at a cost of less than 2% delay and power increase over the extended van Ginneken algorithm.

Field programmable dual-Vdd interconnects are effective in reducing FPGA power. We formulate the dual-Vdd-aware slack budgeting problem as a linear program (LP) and a min-cost network flow problem, respectively. Both algorithms reduce interconnect power by 50% on average compared to single-Vdd interconnects, but the network-flow-based algorithm runs 11x faster on MCNC benchmarks. Furthermore, we develop simultaneous retiming and slack budgeting (SRSB) with flip-flop layout constraints in dual-Vdd FPGAs based on mixed integer linear programming, and speed-up the algorithm by LP relaxation and local legalization. Compared to retiming followed by slack budgeting, SRSB reduces interconnect power by up to 28.8%.

Process variation and prerouting interconnect delay uncertainty affect timing and power for modern VLSI designs in nanometer technologies. This paper presents the first in-depth study on stochastic physical synthesis algorithms leveraging statistical static timing analysis (SSTA) with process variation and prerouting interconnect delay uncertainty for field-programmable gate arrays (FPGAs). Evaluated by SSTA using the placed and routed circuits, the stochastic clustering, placement, and routing reduce the mean delay by 5.0%, 4.0%, and 1.4%, respectively, and reduce the standard deviation of delay by 6.4%, 6.1%, and 1.4%, respectively for MCNC designs. The majority of improvements come from modeling interconnect delay uncertainty for clustering and from considering process variation for placement, while routing has less improvement on delay. In addition, we study the interaction between each individual design stage. When applying all stochastic algorithms concurrently, the mean delay and standard deviation are reduced by 6.2% and 7.5%, respectively. On the other hand, stochastic clustering with deterministic placement and routing is a good flow with little change to the entire flow, but the mean delay is reduced by 5.0%, the standard deviation is reduced by 6.4%, and the runtime is slightly reduced compared to the deterministic flow. Finally, while its improvement over timing is small, stochastic routing is able to reduce the total wire length by 4.5% and to reduce the overall runtime by 4.2% compared to deterministic routing.

The existing 3-D thermal-via allocation methods are based on the steady-state thermal analysis and may lead to excessive number of thermal vias. This paper develops an accurate and efficient thermal-via allocation considering the temporally and spatially variant thermal-power. The transient temperature is calculated by macromodel with a one-time structured and parameterized model reduction, which also generates temperature sensitivity with respect to thermal-via density. The proposed thermal-via allocation minimizes the time-integral of temperature violation, and is solved by a sequential quadratic programming algorithm with use of sensitivities from the macromodel. Compared to the existing method using the steady-state thermal analysis, our method in experiments is 126$\times$faster to obtain temperature, and reduces the number of thermal vias by 2.04$\times$under the same temperature bound.

This paper presents a fast and accurate global routing algorithm, DpRouter, based on two efficient techniques: (1) dynamic pattern routing (Dpr), and (2) segment movement. These two techniques enable DpRouter to explore large solution space to achieve better routability with low time complexity. Compared with the state-of-the-arts, experimental results show that we consistently obtain better routing quality in terms of both congestion and wire length, while simultaneously achieving a more than 30x runtime speedup. We envision that this algorithm can be further leveraged in other routing applications, such as FPGA routing.

Existing statistical static timing analysis (SSTA) techniques suffer from limited modeling capability by using a linear delay model with Gaussian distribution, or have scalability problems due to expensive operations involved to handle non-Gaussian variation sources or non-linear delays. To overcome these limitations, we propose a novel SSTA technique to handle both nonlinear delay dependency and non-Gaussian variation sources simultaneously. We develop efficient algorithms to perform all statistical atomic operations (such as max and add) efficiently via either closed-form formulas or one-dimensional lookup tables. The resulting timing quantity provably preserves the correlation with variation sources to the third-order. We prove that the complexity of our algorithm is linear in both variation sources and circuit sizes, hence our algorithm scales well for large designs. Compared to Monte Carlo simulation for non-Gaussian variation sources and nonlinear delay models, our approach predicts all timing characteristics of circuit delay with less than 2% error.

Off-chip decoupling capacitor (decap) allocation is a demanding task during package and chip codesign. Existing approaches can not handle large numbers of I/O counts and large numbers of legal decap positions. In this paper, we propose a fast decoupling capacitor allocation method. By applying a spectral clustering, a small amount of principal I/Os can be found. Accordingly, the large power supply network is partitioned into several blocks each with only one principal I/O. This enables a localized macromodeling for each block by a triangular-structured reduction. In addition, to systemically consider a large legal position map in a manageable fashion, the map of legal positions is decomposed into multiple rings, which are further parameterized in each block. The decaps are then allocated according to the sensitivity obtained from the parameterized macro-model for each block. Compared to the PRIMA-based macromodeling, experiments show that our method (TBS2) is 25X faster and has 3.04X smaller error. Moreover, our decap allocation reduces the optimization time by 97X, and reduces decap cost by up to 16% to meet the same power-integrty target.

Field programmable dual-Vdd interconnects are effective to reduce FPGA power. However, the deterministic Vdd assignment leverages timing slack exhaustively and significantly increases the number of near-critical paths, which results in a degraded timing yield with process variation. In this paper, we present two statistical Vdd assignment algorithms. The first greedy algorithm is based on sensitivity while the second one is based on timing slack budgeting. Both minimize chip-level interconnect power without degrading timing yield. Evaluated with MCNC circuits, the statistical algorithms reduce interconnect power by 40% compared to the single- Vdd FPGA with power gating. In contrast, the deterministic algorithm reduces interconnect power by 51% but degrades timing yield from 97.7% to 87.5%

Process variation and pre-routing interconnect delay uncertainty affect timing and power for modern VLSI designs in nanometer technologies. This paper presents the first in-depth study on stochastic physical synthesis algorithms leveraging statistical static timing analysis (SSTA) with process variation and pre-routing interconnect delay uncertainty for FPGAs. Evaluated by SSTA with the placed and routed layout and measured at the same clock frequency, the stochastic clustering, placement and routing reduce the yield loss from 50 failed parts per 10 thousand parts (pp10K) for the deterministic flow to 9, 12 and 35pp10K respectively for MCNC designs. The majority of improvements are achieved during clustering and placement while routing stage has much less gain. The gain mainly comes from modeling interconnect delay uncertainty for clustering and from considering process variation for placement. When applying all stochastic algorithms concurrently, the yield loss is reduced to 5pp10K (a 10 X reduction) with the mean delay reduced by 6.2% and the standard deviation reduced by 7.5%. On the other hand, stochastic clustering with deterministic placement and routing is a good flow with little change to the entire flow, but the yield loss is reduced from 50pp10K to 9pp10K, the mean delay is reduced by 5.0%, the standard deviation is reduced by 6.4%, and the runtime is slightly reduced compared to the deterministic flow. Finally, while its improvement over timing is small, stochastic routing is able to reduce the total wire length for the same routing channel width by 4.5% and to reduce runtime by 4.2% compared to deterministic routing.

This paper studies microprocessor floorplanning considering thermal and throughput optimization. We first develop a stochastic heat diffusion model taking into account the application dependent power load for thermal analysis. Then, we design the floorplanning algorithm based on this model. Experimental results show that, compared with the deterministic heat diffusion model, our model obtains up to 3.2degC reduction of the on-chip peak temperature, 1.25% reduction of the area, and 1.125times better CPI (cycles per instruction) performance, respectively. Compared with temperature aware floorplanning in the HOTSPOT tool set that ignores interconnect pipelining, our algorithm is up to 27times faster, reduces the peak temperature by up to 3degC, and also reduces CPI significantly with a negligible area overhead.

Small gates, such as AND2, XOR2 and MUX2, have been mixed with lookup tables (LUTs) inside the. programmable logic block (PLB) to reduce area and power and increase performance in FP-GAs. However, it is unclear whether incorporating macro-gates with wide inputs inside PLBs is beneficial. In this paper, we first propose a methodology to extract a small set of logic functions that are able to implement a large portion of functions for given FPGA applications. Assuming that the extracted logic functions are implemented by macro-gates in PLBs, we then develop a complete synthesis flow for such heterogeneous PLBs with mixed LUTs and macro-gates. The flow includes a cut-based delay and area optimized technology mapping, a mixed binary integer and linear programming based area recovery algorithm to balance the resource utilization of macro-gates and LUTs for area-efficient packing, and a SAT-based packing. We finally evaluate the proposed heterogeneous FPGA using the newly developed flow and show that mixing LUT and macro-gates, both with 6 inputs, improves performance by 16.5% and reduces logic area by 30% compared to using merely 6-input LUTs.

The Boolean matching problem is a key procedure in technology mapping for heterogeneous field programmable gate arrays (FPGA), and SAT-based Boolean matching (SAT-BM) provides a highly flexible solution for various FPGA architectures. However, the computational complexity of state-of-the-art SAT-BM prohibits its application practically. In this paper we propose an efficient SAT-BM algorithm by exploring function and architectural symmetries. While the most recent work obtained up to 13times speedup, we achieve up to 200times speedup, when both are compared to the original SAT-BM algorithm.

Late CMOS scaling reduces device reliability, and existing work has studied the permanent SER (soft error rate) for configuration memory in FPGA extensively. In this paper, we show that continuous CMOS scaling dramatically increases the significance of FPGA chip-level transient soft errors in circuit elements other than configuration memory, and transient SER can no longer be ignored. We then develop an efficient, yet accurate, transient SER evaluation method, called trace based methodology, considering logic, electrical and latch-window maskings. By collecting traces on logic probability and sensitivity and re-using these traces for different device settings, we finally perform device and architecture concurrent optimization considering hundreds of device and architecture combinations. Compared to the commonly used FPGA architecture and device settings, device and architecture concurrent optimization can reduce the transient SER by 2.8X and reduce the product of energy, delay and transient SER by 1.8X,

This paper solves the variation-aware on-chip decoupling capacitance (decap) budgeting problem. Unlike previous work assuming the worst-case current load, we develop a novel stochastic current model, which efficiently and accurately captures operation variation such as temporal correlation between clock cycles and logic-induced correlation between ports. The models also considers current variation due to process variation with spatial correlation. We then propose an iterative alternative programming algorithm to solve the decap budgeting problem under the stochastic current model. Experiments using industrial examples show that compared with the baseline model which assumes maximum currents at all ports and under the same decap area constraint, the model considering temporal correlation reduces the noise by up to 5times, and the model considering both temporal and logic-induced correlations reduces the noise by up to 17times. Compared with the model using deterministic process parameters, considering process variation tLej f variation in this paper reduces the mean noise by up to 4times and the 3 sigma noise by up to 13times. While the existing stochastic optimization has been used mainly for process variation purpose, this paper to the best of our knowledge is the first in-depth study on stochastic optimization taking into account both operation and process variations for power network design. We convincingly show that considering operation variation is highly beneficial for power integrity optimization and this should be researched for optimizing signal and thermal integrity as well.

In physical design and optimization for VLSI/ULSI, parameterized model order reduction can be used to handle large design objectives. In this paper we propose an efficient yet accurate parameterized model order reduction method EMPIRE for physical design with multiple parameters. It is the first practical algorithm using implicit moment matching to handle high order moments of very large number of parameters. In addition, it can match the moments of different parameters with different accuracy according to their influence on the objective under study. Experiment results show that compared with the best existing algorithm CORE which uses explicit moment matching for the parameters, EMPIRE results in 47.8X improved accuracy at a similar runtime.

The existing temperature-aware clock embedding assumes a time-invariant temperature gradient. However, it is not solved how to find the worst-case temperature gradient leading to the worst case skew. In this paper, we develop a PErturbation based Clock Optimization (PECO) considering the timevariant temperature gradient. For a given clock topology, we minimize the worst case skew without asking for the worst case temperature map. We decide the merging point level by level based on the sensitivity of the skew with respect to the change of merging point. Such sensitivity is calculated using a parameterized model, which is compressed by a singularvalue-decomposition (SVD) and K-means based clustering considering the temperature correlation. The experimental results show that our algorithm reduces worst-case skew by up to 5X compared to the existing zero skew based ZST/DME method with small (up to 1%) wirelength overhead.

With high integration density of today's electronic system and reduced noise margins, maintaining high power integrity becomes more challenging for high performance design. Inserting decoupling capacitors is one important and effective solution to improve the power integrity. The existing decoupling capacitor optimization approaches meet constraints on input impedance. In this paper, we show that impedance metric leads to large overdesign and then develop a noise-driven optimization algorithm for decoupling capacitors in packages for power integrity. We use the simulated annealing algorithm to minimize the total cost of decoupling capacitors under the constraints of a worst case noise bound. The key enabler for efficient optimization is an incremental worst case noise computation based on fast Fourier transform over incremental impedance matrix evaluation. Compared to the existing impedance-based approaches, our algorithm reduces the decoupling capacitor cost by 3times and is also more than 10times faster even with explicit noise computation

Device optimization considering supply voltage Vdd and threshold voltage Vt has little chip-area increase but a great impact on power and performance in the nanometer technology. This paper studies simultaneous evaluation of device and architecture optimization for field-programmable gate arrays (FPGAs). We first develop an efficient yet accurate timing and power evaluation method called a trace-based model. By collecting trace information from a cycle-accurate simulation of placed and routed FPGA benchmark circuits and reusing the trace for different Vdds and Vts, we enable device and architecture cooptimization considering hundreds of device and architecture combinations. Compared to the baseline FPGA architecture, which uses the Versatile Place and Route architecture model and the same lookup table and cluster sizes as those used by the Xilinx Virtex-II, Vdd suggested by the International Technology Roadmap for Semiconductor, Vt optimized with respect to the preceding architecture, and Vdd architecture and device cooptimization can reduce the energy-delay product (ED) by 20.5% and the chip area by 23.3%. Furthermore, considering the power gating of unused logic blocks and interconnect switches (in this case, sleep transistor size is a parameter of device tuning), our co-optimization reduces ED by 55.0% and the chip area by 8.2% compared to the baseline FPGA architecture. To the best of our knowledge, this is the first in-depth study in the literature on architecture and device cooptimization for FPGAs.

Abstract—This paper presents extensions of the dynamicprogramming (DP) framework to consider buffer insertion and wire-sizing under effects of process variation. We study the effectiveness of this approach to reduce timing impact caused by chemical–mechanical planarization (CMP)-induced systematic variation and random Leffprocess variation in devices. We first present a quantitative study on the impact of CMP to interconnect parasitics. We then introduce a simple extension to handle CMP effects in the buffer insertion and wire sizing problem by simultaneously considering fill insertion (SBWF).We also tackle the same problem but with random Leffprocess variation (vSBWF) by incorporating statistical timing into the DP framework. We develop an efficient yet accurate heuristic pruning rule to approximate the computationally expensive statistical problem. Experiments under conservative assumption on process variation show that SBWF algorithm obtains 1.6% timing improvement over the variationunaware solution. Moreover, our statistical vSBWF algorithm results in 43.1% yield improvement on average. We also show that our approaches have polynomial time complexity with respect to the net-size. The proposed extensions on the DP framework is orthogonal to other power/area-constrained problems under the same framework, which has been extensively studied in the literature.

Power reduction is of growing importance for field-programmable gate arrays (FPGAs). In this paper, we apply programmable supply voltage (Vdd) to reduce FPGA power. We first design FPGA logic fabrics using dual-Vdd levels and show that field-programmable power supply is required to obtain a satisfactory power-versus-performance tradeoff. We further design FPGA interconnect fabrics for fine-grained Vdd programmability with minimal increase of the number of configuration static-random-access-memory cells. With a simple yet practical computer-aided design flow to leverage the field-programmable dual-Vdd logic and interconnect fabrics, we carry out a highly quantitative study using placed and routed benchmark circuits, and delay, power, and area models obtained from detailed circuit designs. Compared to single-Vdd FPGAs with the Vdd level suggested by the International Technology Roadmap for Semiconductors for 100-nm technology, field-programmable dual-Vdd FPGAs reduce the total power by 47.61% and the energy-delay product by 27.36%

In this paper, a novel method to efficiently reduce the terminal number of general linear-interconnect circuits with a large number of input or output terminals considering delay uncertainty is proposed. Our new algorithm is motivated by the fact that terminal reduction can lead to a more compact order-reduced model and the observation that very large-scale integration interconnect circuits have many similar terminals in terms of their timing and delay metrics due to their closeness in structure or due to the mathematical discretization using meshing in finite-difference or finite-element scheme during the extraction process. The new method, called TermMerg ( Proc. ICCAD, p. 821, 2005), is based on the moments of the circuits as the metrics for the timing or delay. It then employs a singular-value-decomposition (SVD) method to determine the best number of clusters based on the low-rank approximation. After this, the -means clustering algorithm is used to cluster the moments of the terminals into the different clusters. The proposed method can work with any passive-model order reduction and ensure the passive models. In contrast, we show that singular value decomposition model order reduction (SVDMOR) does not generate passive models in general. Passivity enforcement in SVDMOR will significantly hamper the terminal-reduction effectiveness. Experimental results on a number of real industry interconnect circuits demonstrate the effectiveness of the proposed method and show also that the proposed method is more accurate than SVDMOR when the used moment matrix does not give good terminal correlations.

We propose a provably transitive-closure ordering rule with theoretical foundations to prune suboptimal design solutions in the presence of process variations. As an example, this probabilistic ordering rule is applied to develop an efficient variational buffering algorithm. Compared to the conventional deterministic approach, variational buffering improves the parametric timing yield by 15.7% on average. This transitive-closure ordering rule may be leveraged to solve other computer-aided-design problems considering process variation effects

The increased variability of process parameters makes it important yet challenging to extract the statistical characteristics and spatial correlation of process variation. Recent progress in statistical static-timing analysis also makes the extraction important for modern chip designs. Existing approaches extract either only a deterministic component of spatial variation or these approaches do not consider the actual difficulties in computing a valid spatial-correlation function, ignoring the fact that not every function and matrix can be used to describe the spatial correlation. Applying mathematical theories from random fields and convex analysis, we develop: 1) a robust technique to extract a valid spatial-correlation function by solving a constrained nonlinear optimization problem and 2) a robust technique to extract a valid spatial-correlation matrix by employing a modified alternative-projection algorithm. Our novel techniques guarantee to extract a valid spatial-correlation function and matrix from measurement data, even if those measurements are affected by unavoidable random noises. Experiment results, obtained from data generated by a Monte Carlo model, confirm the accuracy and robustness of our techniques and show that we are able to recover the correlation function and matrix with very high accuracy even in the presence of significant random noises

This article develops circuit-simulated routing algorithms. We model the routing graph by an RC network with terminals as inputs, and show that the faster an output reaches its peak, the higher the possibility for the corresponding Hanan or escape node to become a Steiner point. This enables us to select Steiner points and then apply any minimum spanning tree algorithm to obtain obstacle-free or obstacle-aware Steiner routing. Compared with existing algorithms, our algorithms have significant gain on either wirelength or runtime for obstacle-free routing, and on both wirelength and runtime for obstacle-aware routing.

Microarchitecture configurations and floorplanning are keys to boost throughput, and they are strongly related. In this paper, we propose a new method to optimize them simultaneously. We first concentrate on floorplanning under given microarchitecture configurations. In addition to the objectives of conventional floorplanning methods, we minimize the throughput degradation caused by pipelined global interconnects based on efficient yet accurate models for microarchitecture throughput over pipeline stages of global interconnects. Our results show that an accurate trajectory piecewise-linear (TPWL) model incurs more offline setup time to obtain 13% better throughput than a rough access ratio-based model, and both models lead to much better throughput (up to 64% higher) compared with conventional floorplanning methods. We then build a unified throughput model parameterized for pipelined global interconnects and microarchitecture configurations based on the TPWL method and apply this model to efficiently explore over one million microarchitecture configurations and corresponding floorplan variations. We obtain microarchitecture configurations and floorplans with throughput 26.9% better than manually chosen microarchitecture followed by automatic floorplanning in a very recent paper.

Routing tree construction is a fundamental problem in modern VLSI design. In this paper we propose CDCTree, an Obstacle-Avoiding Rectilinear Steiner Minimum Tree (OARSMT) heuristic algorithm to construct an OARSMT. CDCTree is based on the current driven circuit (CDC) model mapped from an escape graph. The circuit structure comes from the topology of the escape graph, with each edge replaced by a resistor indicating the wirelength of that edge. By performing DC analysis on the circuit and selecting the edges according to the current distribution to construct an OARSMT, the wirelength of the resulting tree is short. The algorithm has been implemented and tested on cases of different scales and with different shapes of obstacles. Experiments show that CDCTree can achieve shorter wirelength than the existing best algorithm, An-OARSMan, when the terminal number of a net is less than 50.

System-on-chip and system-in-package result in increased number of I/O cells and complicated constraints for both chip designs and package designs. This renders the traditional manually tuned and chip-centered I/O designs suboptimal in terms of both turn around time and design quality. In this paper, we formally introduce a set of design constraints suitable for chip-package co-design. We formulate a constraint-driven I/O planning and placement problem, and solve it by a multi-step algorithm based upon integer linear programming. Experiment results using real industry designs show that the proposed algorithm can effectively find a large scale I/O placement solution and satisfy all given design constraints in less than 10 minutes. In contrast, the state-of-the-art without considering those design constraints simply cannot meet all design constraints by relying solely upon the conventional iterative approach

Field programmable dual-Vdd interconnects are effective to reduce FPGA power.Assuming uniform length interconnects,existing work has developed time slack budgeting to minimize power based on estimating the lower bound of power reduction using dual-Vdd for given time slack.In this paper,we show that such lower bound estimation cannot be extended to mixed length interconnects that are used in modern FPGAs.We develop a technique to estimate power reduction using dual-Vdd for mixed length interconnects, and apply linear programming (LP)to solve slack budgeting to minimize power for mixed length interconnects.Experiments show 53%power reduction on average compared to single-Vdd interconnects.Furthermore,this paper presents a simultaneous retiming and slack budgeting algorithm to reduce power in dual-Vdd FPGAs considering placement and.ip-.op binding constraints.The algorithm is based on mixed integer and linear programming (MILP)and achieves up to 20%power reduction compared to retiming followed by slack budgeting.We propose a runtime e fficient flow to apply simultaneous retiming and slack budgeting only when it is necessary.To the best of our knowledge,this paper is the first in-depth study of simultaneous retiming and slack budgeting for dual-Vdd programmable FPGA power reduction while considering layout constraints.

Steiner routing is a fundamental yet NP-hard problem in VLSI design and other research fields. In this paper, we propose to model the routing graph by an RC network with routing terminals as input ports and Hanan nodes as output ports. We show that the faster an output reaches its peak, the higher the possibility for the correspondent Hanan node to be a Steiner point. Iteratively adding one or multiple selected Steiner points to build and improve Steiner trees leads to 1-cktSteiner and Blocked-cktSteiner (in short, B-cktSteiner) algorithms, respectively. When there are no routing obstacles, 1-cktSteiner obtains similar wirelength compared with the best existing algorithm FastSteiner. Both are less than 1% worse than the exact solution, but 1-cktSteiner is up to 11.3X faster than FastSteiner. Compared with the fastest existing heuristic FLUTE, B-cktSteiner has similar runtime but up to 1.9% shorter wirelength. Different from FastSteiner and FLUTE which are only applicable to non-obstacle cases, 1-cktSteiner and B-cktSteiner can be applied to routing with obstacles with minimal runtime increase. Compared with the best existing obstacle-avoiding algorithm An-OARSMan, 1-cktSteiner has similar runtime and reduces wirelength by 6.12%, and B-cktSteiner has an average speedup of 352X with a similar wirelength.

In this paper, a Triangularization Based Structure preserving (TBS) model order reduction is proposed to verify power integrity of on-chip structured power grid. The power grid is represented by interconnected basic blocks according to current density, and basic blocks are further clustered into compact blocks, each with a unique pole distribution. Then, the system is transformed into a triangular system, where compact blocks are in its diagonal andthe system poles are determined only by the diagonal blocks. Finally, projection matrices are constructed and applied for compact blocks separately. The resulting macromodel has more matched poles and is more accurate than the one using flat projection. It is also sparse and enables a two-level analysis for simulation time reduction. Compared to existing approaches, TBS in experiments achieves up to 133X and 109X speedup in macromodel buildingand simulation respectively, and reduces waveform error by 33X.

Both custom IC and FPGA designs in the nanometer regime suffer from process variations. But different from custom ICs, FPGAs, programmability offers a unique design freedom to leverage process variation and improve circuit performance. We propose the following variation aware chip-wise placement flow in this paper. First, we obtain the variation map for each chip by synthesizing the test circuits for each chip as a preprocessing step before detailed placement. Then we use the trace-based method to estimate the performance gain achievable by chipwise placement. Such estimation provides a lower bound of the performance gain without detailed placement. Finally, if the gain is significant, a variation aware chipwise placement is used to place the circuits according to the variation map for each chip. Our experimental results show that, compared to the existing FPGA placement, variation aware chipwise placement improves circuit performance by up to 19.3% for the tested variation maps.

Process variation affecting timing and power is an important issue for modern integrated circuits in nanometer technologies. FPGAs are similar to ASICs in their susceptibility to these issues, but face unique challenges in that critical paths are unknown at test time. This paper presents the first in-depth study on applying statistical timing analysis with cross-chip and on-chip variations to speed-binning and guard-banding in FPGAs. Considering the uniqueness of reprogrammability in FPGAs, we quantify the effects of timing-model with guard-banding and speed-binning on statistical performance and timing yield. We also develop a new variation aware placement, which is the first statistical algorithm for FPGA layout and reduces yield loss by 3.4x with guard-banding and 25x with speed-binning for MCNC and QUIP designs.

The existing work on via-stapling in 3D integrated circuits optimizes power and thermal integrity separately and uses steadystate thermal analysis. This paper presents the first in-depth study on simultaneous power and thermal integrity driven viastapling in 3D design. The transient temperature and supply voltage violations are calculated by a structured and parameterized model reduction, which also generates parameterized temperature and voltage violation sensitivities with respect to the via pattern and density. Using parameterized sensitivities, an efficient yet effective greedy optimization is presented to optimize power and thermal integrity simultaneously. Experiments with two active device layers show that compared to sequential power and thermal optimization using steady-state thermal analysis, sequential optimization using transient thermal analysis reduces non-signal vias by on average 11.5%, and simultaneous optimization using transient thermal analysis reduces non-signal vias by on average 34%. The via reduction would be higher for the 3D design with more device layers.

Most existing RCL-1 circuit reductions stamp inverse inductance L-1 elements by a second-order nodal analysis (NA). The NA formulation uses nodal voltage variables and describes inductance by nodal susceptance. This leads to a singular matrix stamping in general. We introduce a new circuit stamping for RCL-1 circuits using branch vector potentials. The new circuit stamping results in a first-order circuit matrix that is semi-positive definite and non-singular. We call this as vectorpotential based nodal analysis (VNA). It enables an accurate and passive reduction. In addition, to preserve the structure of state matrices such as sparsity and hierarchy, we represent the flat VNA matrix in a bordered-block diagonal (BBD) form. This enables us to build and simulate the macromodel efficiently. In experiments performed on several test cases, our method achieves up to 15X faster modeling building time, up to 33X faster simulation time, and as much as 67X smaller waveform error compared to SAPOR, the best existing second order RCL-1 reduction method.

To reduce FPGA power, a linear programming (LP) based time slack allocation algorithm, EdTLC-LP, has been proposed recently for Vdd-programmable interconnects without using Vdd-level converters for mixed wire lengths. However, it takes a long time to solve the LP problem for time slack allocation. In this paper, we develop EdTLC-NW, a slack allocation algorithm based on min-cost network flow to reduce runtime. Compared to single Vdd FPGA with power-gating, EdTLC-LP and EdTLC-NW reduce interconnect power by 52.71% and 52.52%, respectively. EdTLC-NW achieves as good results as EdTLC-LP but runs 8X faster on average. Furthermore, the speedup increases for larger circuits and EdTLC-NW is 20X faster for the largest circuit.

This paper proposes a power-efficient PWM DC/DC converter design with a novel zero voltage switching (ZVS) control technique. The ZVS control is realized by an inner feedback loop which is implemented by simple digital circuitry between the input and output of the power transistors and achieves real-time zero voltage switching (ZVS) for various loading and device parameters with power efficiencies over 90.0%. In addition, an outer feedback loop is used to ensure that the output precisely tracks a reference voltage level. We have also built the relationship between the output voltage ripple and the speed of the voltage comparators which has shown to introduce new low-frequency signals to the loops and cause significant output voltage ripples. Experiment results show that the output ripple could be reduced by 4x by carefully handling the generation and propagation of these low frequency signals.

All existing methods for thermal-via allocation are based on a steady-state thermal analysis and may lead to excessive number of thermal vias. This paper develops an accurate and efficient thermal-via allocation considering temporally and spatially variant thermal-power. The transient temperature is calculated using macromodel by a structured and parameterized model reduction, which generates temperature sensitivity with respect to thermal-via density. By defining a thermal-violation integral based on the transient temperature, a nonlinear optimization problem is formulated to allocate thermal-vias and minimize thermal violation integral. This optimization problem is transformed into a sequence of subproblems by Lagrangian relaxation, and each subproblem is solved by quadratic programming using sensitives from the macromodel. Experiments show that compared to the existing method using steady-state thermal analysis, our method is 126X faster to obtain the temperature profile, and reduces the number of thermal vias by 2.04X under the same temperature bound.

The existing decoupling capacitance optimization approaches meet constraints on input impedance for package. In this paper, we show that using impedance as constraints leads to large overdesign and then develop a noise driven optimization algorithm for decoupling capacitors in packages for power integrity. Our algorithm uses the simulated annealing algorithm to minimize the total cost of decoupling capacitors under the constraints of a worst case noise. The key enabler for efficient optimization is an incremental worst-case noise computation based on FFT over incremental impedance matrix evaluation. Compared to the existing impedance based approaches, our algorithm reduces the decoupling capacitor cost by 3x and is also more than 10x faster even with explicit noise computation.

Power integrity analysis of in-package and on-chip power supply needs to consider a large number of ports and handle magnetic coupling that is better represented by susceptance. The existing moment matching methods are not able to accurately model both large number of ports and susceptance. In this paper, we propose a generalized Second-order Arnoldi method for reducing Multiple Source Linear Network (SAMSON) with susceptance. We employ a right-hand-side excitation current vector to replace the port incident matrix such that an MIMO (Multiple-input-multiple-output) system is transformed into an equivalent superposed SIMO (Single-input-multiple-output) system to avoid accuracy loss in block moment matching, and develop a generalized second-order Arnoldi method based orthonormalization to accurately handle susceptance and non-impulse current sources. Compared with existing EKS and IEKS approaches able to consider non-impulse sources but not susceptance, SAMSON is slightly faster and is more accurate in high frequency range and at dc. With same model order, SAMSON reduces time domain waveform error by 33X compared to EKS/IEKS and by 47X compared with the best block moment matching method applicable to susceptance.

A comprehensive probabilistic methodology is proposed to solve the buer insertion problem with the consideration of process variations. In contrast to a recent work, we point out, for the rst time, that the correlation between the required arrival time and the downstream loading ca-pacitance must be considered in order to solve the problem \\correctly". We develop an ecient bottom-up recursive al-gorithm to calculate the joint probability density function that accurately captures the above correlation, and propose eective pruning rules to exclude probabilistically inferior solutions. We verify our buer insertion using timing anal-ysis with both device and interconnect variations, and show that compared to the conventional buer insertion algorithm using nominal device and interconnect parameters, our new buer insertion methodology can reduce the probability of timing violation by up to 30%. 1.

Increased variability of process parameters and recent progress in statistical static timing analysis make extraction of statistical characteristics of process variation and spatial correlation an important yet challenging problem in modern chip designs. Unfortunately, existing approaches either focus on extraction of only a deterministic component of spatial variation or do not consider actual difficulties in computing a valid spatial correlation function and matrix, simply ignoring the fact that not every function and matrix can be used to describe the spatial correlation. Based upon the mathematical theory of random fields and convex analysis, in this paper, we develop (1) a robust technique to extract a valid spatial correlation function by solving a constrained nonlinear optimization problem; and (2) a robust technique to extract a valid spatial correlation matrix by employing a modified alternative projection algorithm.Our novel techniques guarantee to extract a valid spatial correlation function and matrix that are closest to measurement data, even if those measurements are affected by unavoidable random noises. Experiment results based upon a Monte-Carlo model confirm the accuracy and robustness of our techniques, and show that we are able to recover the correlation function and matrix with very high accuracy even in the presence of significant random noises.

To overcome the limitations of traditional interconnects, multichannel interconnects that transmit signals via high-frequency carriers have recently been proposed and realized for intrachip and interchip communication. To efficiently design such transmission-line-based interconnects, this paper derives a closed-form model for signal-to-noise ratio (SNR) considering multiple ports and branches, and proposes efficient figures of merit (FOMs) to minimize signal distortion. Experiments show that the SNR model is accurate compared to SPICE simulation and the signal distortion FOMs are effective. Using the proposed models, this paper further automatically synthesizes coplanar waveguides (CPWs) for radio-frequency (RF) interconnects with capacitive couplers. The authors minimize the total interconnect area under the constraints of SNR and signal distortion. Compared to the published manual designs, the synthesized solutions can reduce up to 80% area. Furthermore, the optimized solutions vary greatly with respect to number of ports, frequency bands, topologies, and terminations, and therefore automatic synthesis is effective and necessary

To reduce field-programmable gate array power, Vdd programmability has been recently proposed to select the Vdd level for interconnects and power-gate unused interconnects. However, Vdd-level converters used in the existing Vdd-programmable method consume a large amount of leakage. This paper proposes two ways to avoid using level converters in interconnects, namely; 1) tree-based level converter insertion (TLC) and 2) dual-Vdd tree-based level converter insertion (dTLC). TLC enforces that there is only one Vdd level within each routing tree, while dTLC can have different Vdd levels within a routing tree, but no VddL switch drives VddH switches. Dual-Vdd assignment algorithms were developed considering chip-level time slack allocation for maximum power reduction. The algorithms include TLC-S and dTLC-S, two power sensitivity-based algorithms with implicit time slack allocation, and dTLC-LP, a linear programming (LP)-based algorithm with explicit time slack allocation. All allocate time slack first to interconnects with higher power sensitivity and assign low Vdd to them for more power reduction. Experiments show that dTLC-LP obtains the lowest power consumption. Compared to dTLC-LP, dTLC-S obtains a slightly higher power consumption but runs three times faster. Compared to the existing segment-based level converter insertion for dual Vdd, dTLC-LP reduces interconnect power by 52.90% without performance loss for Microelectronics Center of North Carolina benchmark circuits

This paper presents a novel compact passive modeling technique for high-performance RF passive and interconnect circuits modeled as high-order resistor-inductor-capacitor-mutual inductance circuits. The new method is based on a recently proposed general s-domain hierarchical modeling and analysis method and vector potential equivalent circuit model for self and mutual inductances. Theoretically, this paper shows that s-domain hierarchical reduction is equivalent to implicit moment matching at around s=0 and that the existing hierarchical reduction method by one-point expansion is numerically stable for general tree-structured circuits. It is also shown that hierarchical reduction preserves the reciprocity of passive circuit matrices. Practically, a hierarchical multipoint reduction scheme to obtain accurate-order reduced admittance matrices of general passive circuits is proposed. A novel explicit waveform-matching algorithm is proposed for searching dominant poles and residues from different expansion points based on the unique hierarchical reduction framework. To enforce passivity, state-space-based optimization is applied to the model order reduced admittance matrix. Then, a general multiport network realization method to realize the passivity-enforced reduced admittance based on the relaxed one-port network synthesis technique using Foster's canonical form is proposed. The resulting modeling algorithm can generate the multiport passive SPICE-compatible model for any linear passive network with easily controlled model accuracy and complexity. Experimental results on an RF spiral inductor and a number of high-speed transmission line circuits are presented. In comparison with other approaches, the proposed reduction is as accurate as passive reduced-order interconnect macromodeling algorithm in the high-frequency domain due to the enhanced multipoint expansion, but leads to smaller realized circuit models. In addition, under the same reduction ratio, realized models by the new method have less error compared with reduced circuits by time-constant-based reduction techniques in time domain.

This paper presents a novel global routing algorithm, AT-PO-GR, to minimize the routing area under both congestion, timing, and RLC crosstalk constraints. The proposed algorithm is consisted of three key parts: (1) timing and congestion optimization; (2) crosstalk budgeting and estimation; and (3) crosstalk elimination and local refinement. Compared with the recent work introduced in [9] and [10], the proposed algorithm can achieve smaller routing area and fewer shields under the same design constraints, yet use less running time.

Power has become an increasingly important design constraint for FPGAs in nanometer technologies, and global interconnects should be the focus of FPGA power reduction as they consume more power than logic cells. We design area-efficient circuits for programmable fine-grained power-gating of individual unused interconnect switches, and reduce interconnect leakage power dramatically because the interconnect switches have an intrinsically low utilization rate for the purpose of programmability. The low leakage interconnect via power-gating reduces total power by 38.18% for the FPGA in 100nm technology. Furthermore, it enables interconnect dynamic power reduction. We design a routing channel containing abundant or duplicated routing tracks with pre-determined high and low Vdd, and develop routing algorithm using low Vdd for non-critical routing to reduce dynamic power. The track-duplicated routing channel has small leakage power and increase the FPGA power reduction to 45.00%.

This paper proposes a novel wideband modeling technique for high-performance RF passives and linear(ized) analog circuits. The new method is based on a recently proposed sdomain hierarchical modeling and analysis method [27]. Theoretically, we show that the s-domain hierarchical reduction is equivalent to implicit moment matching around s = 0, and that the existing hierarchical reduction method by one-point expansion is numerically stable for general tree-structured circuits. Practically, we propose a hierarchical multi-point reduction scheme for high-fidelity, wideband modeling of general passive or active linear circuits. A novel explicit waveform matching algorithm is proposed for searching the dominant poles and residues from different expansion points based on the unique hierarchical reduction framework. Experimental results with large analog circuits, on-chip spiral inductors are presented to validate the proposed method.

We extend an existing probabilistic congestion model to consider shielding for crosstalk reduction. We then develop a multilevel router to study the impact of various congestion models on routing congestion by using large industrial design examples. We show that (1) when shielding is applied as a post-routing optimization for crosstalk reduction, the existing probabilistic model, when compared to a deterministic routing-order dependent congestion model, reduces routing congestion by 17.1% on average under the given routing area constraints, or reduces routing area by 9.4% on average under the given routing congestion constraints; (2) our extended probabilistic congestion model considering shielding enables shielding reservation and minimization for routing and achieves routing congestion (or area) reduction by 47.7% (or 31.0%) on average under the given routing area (or congestion) constraints, when compared to the above deterministic congestion model not able to estimate shielding and therefore not able to minimize shielding during routing.

We develop a realizable circuit reduction to generate the interconnect macro-model for parasitic estimation in wideband applications. The inductance is represented by VPEC (vector potential equivalent circuit) model, which not only enables the passive sparsification but also gives correct low-frequency response, whereas the recent circuit reduction intrinsically has inaccurate value and low-frequency response due to nodal-susceptance formulation. Applying hierarchical circuit-reduction enhanced by multi-point expansions, we can obtain an accurate high-order impedance function to capture the high-frequency response. The impedance function is further enforced passivity by convex programming, and realized by a Foster's synthesis. Experiments show that our method is as accurate as PRIMA in high frequency range, but leads to a realized circuit model with up to 10X times less complexity and up to 8X smaller simulation time. In addition, under the same reduction ratio, its error margin is less than that for the time-constant based reduction in both time-domain and frequency-domain simulations.

Device optimization considering supply voltage Vdd and threshold voltage Vt tuning does not increase chip area but has a great impact on power and performance in the nanometer technology. This paper studies the simultaneous evaluation of device and architecture optimization for FPGA. We first develop an efficient yet accurate timing and power evaluation method, called trace-based model. By collecting trace information from cycle-accurate simulation of placed and routed FPGA benchmark circuits and re-using the trace for different Vdd and Vt, we enable the device and architecture co-optimization for hundreds of combinations. Compared to the baseline FPGA which has the architecture same as the commercial FPGA used by Xilinx, and has Vdd suggested by ITRS but Vt optimized by our device optimization, architecture and device co-optimization can reduce energy-delay product by 20.5% without any chip area increase compared to the conventional FPGA architecture. Furthermore, considering power-gating of unused logic blocks and interconnect switches, our co-optimization method reduces energy-delay product by 54.7% and chip area by 8.3%. To the best of our knowledge, this is the first in-depth study on architecture and device co-optimization for FPGAs.

To reduce power, Vdd programmability has been proposed recently to select Vdd-level for interconnects and to powergate unused interconnects. However, Vdd-level converters used in the Vdd-programmable method consume a large amount of leakage. In this paper, we develop chip-level dual-Vdd assignment algorithms to guarantee that no low-Vdd interconnect switch drives high-Vdd interconnect switches. This removes the need of Vdd-level converters and reduces interconnect leakage and interconnect device area by 91.78% and 25.48%, respectively. The assignment algorithms include power sensitivity based heuristics with implicit time slack allocation and a linear programming (LP) based method with explicit time slack allocation. Both first allocate time slack to interconnects with higher transition density and assign low-Vdd to them for more power reduction. Compared to the aforementioned Vdd-programmable method using Vdd-level converters, the LP based algorithm reduces interconnect power by 65.13% without performance loss for the MCNC benchmark circuits. Compared to the LP based algorithm, the sensitivity based heuristics can obtain slightly smaller power reduction but run 4X faster.

This paper presents the first in-depth study on applying dual VDD buffers to buffer insertion and multi-sink buffered tree construction for power minimization under delay constraint. To tackle the problem of dramatic complexity increment due to simultaneous delay and power consideration and increased buffer choices, we develop a sampling-based sub-solutions (i.e. options) propagation method and a balanced search tree-based data structure for option pruning. We obtain 17x speedup with little loss of optimality compared to the exact option propagation. Moreover, compared to buffer insertion with single VDD buffers, dual-VDD buffers reduce power by 23% at the minimum delay specification. In addition, compared to the delay-optimal tree using single VDD buffers, our power-optimal buffered tree reduces power by 7% and 18% at the minimum delay specification when single VDD and dual VDD buffers are used respectively.

Context-aware applications pose new challenges, including a need for new computational models, uncertainty management, and efficient optimization under uncertainty. Uncertainty can arise at two levels: multiple and single tasks. When a mobile user changes environments, the context changes resulting in the possibility of the user requesting tasks which are specific for the new environment. However as the user moves these requested tasks may no longer be context relevant. Additionally, the runtime of each task is often highly dependent on the input data. We introduce an hierarchical multi-resolution statistical task model that captures relevant aspects at the task and intertask levels, and captures not only uncertainty, but also introduces the notion of utility for the user. We have developed a system of nonparametric statistical techniques for modeling the runtime of a specific task. This model is a framework where we define problems of design and optimization of statistical soft real-time systems (SSRTS). The main algorithmic novelty is a cumulative potential-based task scheduling heuristic for maximizing utility. The heuristic conducts global optimization and induces low runtime overhead. We demonstrate the effectiveness of the scheduling heuristic using a Trimaran-based evaluation platform.

A comprehensive probabilistic methodology is proposed to solve the buffer insertion problem with the consideration of process variations. In contrast to a recent work, we point out, for the first time, that the correlation between the required arrival time and the downstream loading capacitance must be considered in order to solve the problem "correctly". We develop an efficient bottom-up recursive algorithm to calculate the joint probability density function that accurately captures the above correlation, and propose effective pruning rules to exclude probabilistically inferior solutions. We verify our buffer insertion using timing analysis with both device and interconnect variations, and show that compared to the conventional buffer insertion algorithm using nominal device and interconnect parameters, our new buffer insertion methodology can reduce the probability of timing violation by up to 30%.

Vdd-programmable FPGAs have been proposed recently to reduce FPGA power, where Vdd levels can be customized for different circuit elements and unused circuit elements can be power-gated. In this paper, we first develop an accurate FPGA power model and then design novel Vdd-programmable interconnect switches with minimum number of configuration SRAM cells. Applying our power model to placed and routed benchmark circuits, we evaluate Vdd-programmable FPGA architecture using the new switches. The best architecture in our study uses Vdd-programmable logic blocks and Vdd-gateable interconnects. Compared to the baseline architecture similar to the leading commercial architecture, the best architecture reduces the minimal energy-delay product by 44.14% with 48% area overhead and 3% SRAM cell increase. Our evaluation results also show that LUT size 4 always gives the lowest energy consumption while LUT size 7 always leads to the highest performance for all evaluated architectures.

This paper proposes a novel method to efficiently reduce the terminal number of general linear interconnect circuits with a large number of input and/or output terminals considering delay variations. Our new algorithm is motivated by the fact that VLSI interconnect circuits have many similar terminals in terms of their timing and delay metrics due to their closeness in structure or due to mathematic approximation using meshing in finite difference or finite element scheme during the extraction process. By allowing some delay tolerance or variations, we can reduce many similar terminals and keep a small number of representative terminals. After terminal reduction, traditional model order reduction methods can achieve more compact models and improve simulation efficiency. The new method, TermMerg, is based on the moments of the circuits as the metrics for the timing or delay. It then employs singular value decomposition (SVD) method to determine the optimum number of clusters based on the low-rank approximation. After this, the K-means clustering algorithm is used to cluster the moments of the terminals into different clusters. Experimental results on a number of real industry interconnect circuits demonstrate the effectiveness of the proposed method.

Process variations in nanometer technologies are becoming an important issue for cutting-edge FPGAs with a multi-million gate capacity. Considering both die-to-die and within-die variations in effective channel length, threshold voltage, and gate oxide thickness, we first develop closed-form models of leakage and timing variations at the FPGA chip level. Experiments show that our models are within 3% from Monte Carlo simulation, and the leakage and delay variations can be up to 3/spl times/ and 1.9/spl times/, respectively. We then derive analytical yield models considering both leakage and timing variations, and use such models to evaluate FPGA device and architecture under process variations. Compared to the architecture similar to a commercial FPGA and device setting from ITRS roadmap, device tuning alone improves leakage yield by 39% and architecture and device co-optimization increases leakage yield by 73%. We also show that LUT size 4 gives the highest leakage yield, LUT size 7 gives the highest timing yield, but LUT size 5 achieves the maximum combined leakage and timing yield. To the best of our knowledge, this is the first in-depth study on FPGA device and architecture co-evaluation considering process variations.

This work first presents an analytical repeater insertion method which optimizes power under delay constraint for a single net. This method finds the optimal repeater insertion lengths, repeater sizes, and Vdd and Vth levels for a net with a delay target, and it reduces more than 50 % power over a previous work which does not consider Vdd and Vth optimization. This work further presents the power saving when multiple Vdd and Vth levels are used in repeater insertion at the full-chip level. Compared to the case with single Vdd and Vth suggested by ITRS, optimized dual Vdd and dual Vth reduce overall global interconnect power by 47%, 28% and 13 % for 130nm, 90nm and 65nm technology nodes, respectively, but extra Vdd or Vth levels only give marginal improvement. We also show that an optimized single Vth reduce interconnect power almost as effective as dual-Vth does, in contrast to the need of dual Vth for logic circuits.

In this session, we will first present an overview of new challenges in commercial FPGA architecture design with an emphasis on the circuit and architecture issues for power at current and upcoming process nodes. Today’s 90nm FPGAs utilize techniques such as programmable shut-down of unused resources at the architectural level and multiple threshold voltages and gate-oxides at the circuit level. At 65nm and 45nm new techniques will need to target not only power mitigation but process variation in power and timing and their impact on yield and manufacturability.

Abstract—This paper presents extensions of the dynamic-programming (DP) framework to consider buffer insertion and wire-sizing under effects of process variation. We study the effectiveness of this approach to reduce timing impact caused by chemical–mechanical planarization (CMP)-induced systematic variation and random Leff process variation in devices. We first present a quantitative study on the impact of CMP to interconnect parasitics. We then introduce a simple extension to handle CMP effects in the buffer insertion and wire sizing problem by simulta-neously considering fill insertion (SBWF). We also tackle the same problem but with random Leff process variation (vSBWF) by in-corporating statistical timing into the DP framework. We develop an efficient yet accurate heuristic pruning rule to approximate the computationally expensive statistical problem. Experiments under conservative assumption on process variation show that SBWF algorithm obtains 1.6 % timing improvement over the variation-unaware solution. Moreover, our statistical vSBWF algorithm results in 43.1 % yield improvement on average. We also show that our approaches have polynomial time complexity with respect to the net-size. The proposed extensions on the DP framework is orthogonal to other power/area-constrained problems under the same framework, which has been extensively studied in the literature. Index Terms—Buffering, dummy fill insertion, fill patterns, interconnect optimization, process variation, random Leff variation, systematic CMP variation, wire sizing. I.

Transmission line effects become increasingly significant for on-chip high-speed interconnects. Efficient and accurate transmission line models are required for analysis and synthesis of such interconnects. In this paper, we first present an efficient model for the far-end response of a single transmission line considering ramp input and capacitive loading. Our model divides the time axis into a number of regions according to the time of flight and the input rising time, and then approximates the far-end response by piecewise linear (PWL) waveform in each region. We name the resulting model as the PWL model. Experiments show that the waveform from the PWL model differs from the SPICE simulation result with the average voltage difference less than 0.9% V/sub dd/, and the PWL model is at least 1000/spl times/ faster than SPICE simulation. We further apply the PWL model to calculate the delay, rising time, and oscillation amplitude of the coplanar waveguide structure, and achieve less than 10% average error compared to SPICE simulation. Combining the PWL model and decoupling technique, we analyze the far-end response of bus structures and obtain waveform almost perfectly matching the SPICE simulation result.

Considering a RLC interconnect model, we determine switching patterns and switching times of multiple aggressors to generate the worst case crosstalk noise (WCN) for a quiet or a noisy victim. We consider the routing direction as it has a significant impact under the RLC model. When there are no timing window constraints, we show that the commonly used superposition algorithm results in 15% underestimation on average, and propose a new SS + AS algorithm that has virtually the same complexity as the superposition algorithm but has a much improved accuracy. On average, the SS + AS algorithm only underestimates WCN by 3% compared to time-consuming simulated annealing and genetic algorithm. We also show that applying a RC model to the high-speed interconnects in the International Technology Roadmap for Semiconductors 0.10 /spl mu/m technology virtually always underestimates WCN, and the underestimation can be up to 80%. Furthermore, we extend our algorithm to consider aggressor switching and victim sampling windows. We show that the extended SS + AS algorithm well approximates WCN with 2% underestimation on average. Although the RC model usually severely underestimates WCN with timing window constraints, it does overestimate when both the aggressor switching and the victim sampling windows are small enough. We conclude that the RLC model is needed for accurate modeling of WCN in design in the multigigahertz region.

This paper studies power modeling for field programmable gate arrays (FPGAs) and investigates FPGA power characteristics in nanometer technologies. Considering both dynamic and leakage power, a mixed-level power model that combines switch-level models for interconnects and macromodels for look-up tables (LUTs) is developed. Gate-level netlists back-annotated with postlayout capacitances and delays are generated and cycle-accurate power simulation is performed using the mixed-level power model. The resulting power analysis framework is named as fpgaEVA-LP2. Experiments show that fpgaEVA-LP2 achieves high fidelity compared to SPICE simulation, and the absolute error is merely 8% on average. fpgaEVA-LP2 can be used to examine the power impact of FPGA circuits, architectures, and CAD algorithms, and it is used to study the power characteristics of existing FPGA architectures in this paper. It is shown that interconnect power is dominant and leakage power is significant in nanometer technologies. In addition, tuning cluster and LUT sizes lead to 1.7/spl times/ energy difference and 0.8/spl times/ delay difference between the resulting min-energy and min-delay FPGA architectures, and FPGA area and power are reduced at the same time by tuning the cluster and LUT sizes. The existing commercial architectures are similar to the min-energy (and min-area at the same time) architecture according to this study. Therefore, innovative FPGA circuits, architectures, and CAD algorithms, for example, considering programmable power supply voltage, are needed to further reduce FPGA power.

Performance and power are two primary design issues for systems ranging from server computers to handhelds. Performance is affected by both temperature and supply voltage because of the temperature and voltage dependence of circuit delay. Furthermore, as semiconductor technology scales down, leakage power's exponential dependence on temperature and supply voltage becomes significant. Therefore, future design studies call for temperature and voltage aware performance and power modeling. In this paper, we study microarchitecture-level temperature and voltage aware performance and power modeling. We present a leakage power model with temperature and voltage scaling, and show that leakage and total energy vary by 38% and 24%, respectively, between 65/spl deg/C and 110/spl deg/C. We study thermal runaway induced by the interdependence between temperature and leakage power, and demonstrate that without temperature-aware modeling, underestimation of leakage power may lead to the failure of thermal controls, and overestimation of leakage power may result in excessive performance penalties of up to 5.24%. All of these studies underscore the necessity of temperature-aware power modeling. Furthermore, we study optimal voltage scaling for best performance with dynamic power and thermal management under different packaging options. We show that dynamic power and thermal management allows designs to target at the common-case thermal scenario among benchmarks and improves performance by 6.59% compared to designs targeted at the worst case thermal scenario without dynamic power and thermal management. Additionally, the optimal V/sub dd/ for the best performance may not be the largest V/sub dd/ allowed by the given packaging platform, and that advanced cooling techniques can improve throughput significantly.

To reduce the model complexity for inductive interconnects, the vector potential equivalent circuit (VPEC) model was introduced recently and a localized VPEC model was developed based on geometry integration. In this paper, the authors show that the localized VPEC model is not accurate for interconnects with nontrivial sizes. They derive an accurate VPEC model by inverting the inductance matrix under the partial element equivalent circuit (PEEC) model and prove that the effective resistance matrix under the resulting full VPEC model is passive and strictly diagonal dominant. This diagonal dominance enables truncating small-valued off-diagonal elements to obtain a sparsified VPEC model named truncated VPEC (tVPEC) model with guaranteed passivity. To avoid inverting the entire inductance matrix, the authors further present another sparsified VPEC model with preserved passivity, the windowed VPEC (wVPEC) model, based on inverting a number of inductance submatrices. Both full and sparsified VPEC models are SPICE compatible. Experiments show that the full VPEC model is as accurate as the full PEEC model but consumes less simulation time than the full PEEC model does. Moreover, the sparsified VPEC model is orders of magnitude (1000/spl times/) faster and produces a waveform with small errors (3%) compared to the full PEEC model, and wVPEC uses less (up to 90/spl times/) model building time yet is more accurate compared to the tVPEC model.

In this paper, we study microarchitecture-level leakage energy reduction by power gating. We consider the virtual power/ground rails clamp (VRC) and multithreshold CMOS (MTCMOS) techniques and apply VRC to memory-based units for data retention and MTCMOS to the other units. We propose a systematic methodology for leakage reduction at the microarchitecture level, in which profiling of idle period distribution and ideal power gating analysis are used to select a target component for realistic power gating. We show that the ideal leakage energy reduction can be up to 30% of the total energy for the modern high-performance very long instruction word processors we study and that the secondary level (L2) cache contributes most to the reduction. We further improve the existing adaptive cache decay method for leakage reduction by using VRC for data retention and name it VRC decay . Applied to L2 cache, the VRC decay, on average, increases performance by 5.6% and reduces system energy by 24.1%, compared to the adaptive cache decay without data retention.

Field programmable gate arrays (FPGAs) with supply voltage (Vdd) programmability have been proposed recently to reduce FPGA power, where the Vdd-level can be customized for FPGA circuit elements and unused circuit elements can be power-gated. In this paper, we first design novel Vdd-programmable and Vdd-gateable interconnect switches with minimal number of configuration SRAM cells. We then evaluate Vdd-programmable FPGA architectures using the new switches. The best architecture in our study uses Vdd-programmable logic blocks and Vdd-gateable interconnects. Compared to the baseline architecture similar to the leading commercial architecture, our best architecture reduces the minimal energy-delay product by 54.39% with 17% more area and 3% more configuration SRAM cells. Our evaluation results also show that LUT size 4 gives the lowest energy consumption, and LUT size 7 leads to the highest performance, both for all evaluated architectures.

In this paper, we study an extended global routing problem with RLC crosstalk constraints. Considering simultaneous shield insertion and net ordering, we propose a multiphase algorithm to synthesize a global routing solution with track assignment to satisfy the RLC crosstalk constraint at each sink. The key algorithm phase is global routing synthesis with shield reservation and minimization based on prerouting shield estimation. Experiments using large industrial benchmarks show that compared to the best alternative with postrouting shield insertion and net ordering, the proposed algorithm with shield reservation and minimization reduces the congestion by 18.4% with a smaller runtime. To the best of our knowledge, this is the first in-depth study on global routing synthesis with RLC crosstalk constraints.

The high leakage devices in nanometer technologies as well as the low activity rates in system-on-a-chip (SOC) contribute to the growing significance of leakage power at the system level. We first present system-level leakage-power modeling and characteristics and discuss ways to reduce leakage for caches. Considering the interdependence between leakage power and temperature, we then discuss thermal runaway and dynamic power and thermal management (DPTM) to reduce power and prevent thermal violations. We show that a thermal-independent leakage model may hide actual failures of DPTM. Finally, we present voltage scaling considering DPTM for different packaging options. We show that the optimal Vdd for the best throughput may be smaller than the largest Vdd allowed by the given packaging platform, and that advanced cooling techniques can improve throughput significantly.

Power optimization is of growing importance for FPGAs in nanometer technologies. Considering dual-Vdd technique, we show that configurable power supply is required to obtain a satisfactory performance and power tradeo#. We design FPGA circuits and logic fabrics using configurable dualVdd and develop the corresponding CAD flow to leverage such circuits and logic fabrics. We then carry out a highly quantitative study using area, delay and power models obtained from detailed circuit design and SPICE simulation in 100nm technology. Compared to single-Vdd FPGAs with optimized Vdd level for the same target clock frequency, configurable dual-Vdd FPGAs with full and partial supply programmability for logic blocks reduce logic power by 35.46% and 28.62% respectively and reduce total FPGA power by 14.29% and 9.04% respectively. To the best of our knowledge, it is the first in-depth study on FPGAs with configurable dual-Vdd for power reduction.

Interconnect pipelining has a great impact on system performance, but has not been considered by automatic floorplanning. Considering interconnect pipelining, we study the floorplanning optimization problem to minimize system CPI (cycles per instruction) and in turn maximize system performance. We develop an efficient tablebased model called trajectory piece-wise linear (TPWL) model to estimate CPI with interconnect pipelining. Experiments show that the TPWL model differs from cycle-accurate simulations by less than 3.0%. We integrate this model with a simulated-annealing based floorplan optimization to obtain CPI-aware floorplanning. Compared to the conventional floorplanning to minimize area and wire length, our CPI-aware floorplanning can reduce CPI by up to 28.6% with a small area overhead of 5.69% under 100nm technology and obtain better results under 70nm technology. To the best of our knowledge, this paper is the first in-depth study on floorplanning optimization with consideration of interconnect pipelining.

Conventional physical design flow separates the design of power network and signal network. Such a separated approach results in slow design convergence for wire-limited deep sub-micron designs. We present a novel design methodology that simultaneously considers global signal routing and power network design under integrity constraints. The key part to this approach is a simple yet accurate power net estimation formula that decides the minimum number of power nets needed to satisfy both power and signal integrity constraints prior to detailed layout. The proposed design methodology is a one-pass solution to the co-design of power and signal networks in the sense that no iteration between them is required in order to meet design closure. Experiment results using large industrial benchmarks show that compared to the state-of-the-art alternative design approach, the proposed method can reduce the power network area by 19.4% on average under the same signal and power integrity constraints with better routing quality, but use less runtime.

In this paper we study the technology mapping problem of FPGA architectures with dual supply voltages (Vdds) for power optimization. This is done with the guarantee that the mapping depth of the circuit will not increase compared to the circuit with a single Vdd. We first design a single-Vdd mapping algorithm that achieves better power results than the latest published low-power mapping algorithms. We then show that our dual-Vdd mapping algorithm can further improve power savings by up to 11.6% over the single-Vdd mapper. In addition, we investigate the best low-Vdd/high-Vdd ratio for the largest power reduction among several dual-Vdd combinations. To our knowledge, this is the first work on dual-Vdd mapping for FPGA architectures.

Traditional FPGAs use uniform supply voltage Vdd and uniform threshold voltage Vt. We propose to use pre-defined dual-Vdd and dual-Vt fabrics to reduce FPGA power. We design FPGA circuits with dual-Vdd/dual-Vt to effectively reduce both dynamic power and leakage power, and define dual-Vdd/dual-Vt FPGA fabrics based on the profiling of benchmark circuits. We further develop CAD algorithms including power-sensitivity based voltage assignment and simulated-annealing based placement to leverage such fabrics. Compared to the conventional fabric using uniform Vdd/Vt at the same target clock frequency, our new fabric using dual Vt achieves 9% to 20% power reduction. However, the pre-defined FPGA fabric using both dual Vdd and dual Vt only achieves on average 2% extra power reduction. It is because that the pre-designed dual-Vdd layout pattern introduces non-negligible performance penalty. Therefore, programmability of supply voltage is needed to achieve significant power saving for dual-Vdd FPGAs. To our best knowledge, it is the first in-depth study on applying both dual-Vdd and dual-Vt to FPGA considering circuits, fabrics and CAD algorithms.

Power is an increasingly important design constraint for FPGAs in nanometer technologies. Because interconnect power is dominant in FPGAs, we design Vdd-programmable interconnect fabric to reduce FPGA interconnect power. There are three Vdd states for interconnect switches: high Vdd, low Vdd and power-gating. We develop a simple design flow to apply high Vdd to critical paths and low Vdd to non-critical paths and to power gate unused interconnect switches. We carry out a highly quantitative study by placing and routing benchmark circuits in 100 nm technology to illustrate the power saving. Compared to single-Vdd FPGAs with optimized but nonprogrammable Vdd level for the same target clock frequency, our new FPGA fabric on average reduces interconnect power by 56.51% and total FPGA power by 50.55%. Due to the highly low utilization rate of routing switches, majority of the power reduction is achieved by power gating unused routing buffers. In contrast, recent work that considers Vdd programmability only for logic fabric reduces total FPGA power merely by 14.29%. To the best of our knowledge, it is the first in-depth study on Vdd programmability for FPGA interconnect power reduction.

Considering the voltage drop constraint over a distributed model for power/ground (P/G) network, we study the following two problems for physical synthesis of sleep transistors: the min-area sleep transistor insertion (and sizing) (T IS) problem with respect to a fixed P/G network, and the simultaneous sleep transistor insertion and P/G network sizing (T IPGS) problem to minimize the weighted area of sleep transistors and P/G network. We show that there may exist multiple sleep transistor insertion solutions that all lead to a same minimum area in the T IS and T IPGS problems. We develop optimal algorithms to T IS and T IPGS problems by modeling the circuit as a single current source, and then extend to the case modeling the circuit as distributed current sources. Compared with the best known approach, our algorithms achieve area reduction by up to 44.1% and 61.3% for T IS and T IPGS, respectively.

Existing layout-optimization methods for both capacitive and inductive (RLC) crosstalk reduction assume a set of interconnects with a priori given crosstalk bounds in a routing region. RLC crosstalk budgeting is critical for effectively applying these methods at the full-chip level. In this paper, we formulate a full-chip routing optimization problem with RLC crosstalk budgeting, and solve this problem with a multiphase algorithm. In phase I, we solve an optimal RLC crosstalk budgeting based on linear programming to partition crosstalk bounds at sinks into bounds for net segments in routing regions. In phase II, we perform simultaneous shield insertion and net ordering to meet the partitioned crosstalk bounds in each region. In phase III, we carry out a local refinement procedure to reduce the total number of shields. Compared with the best alternative approach in experiments, the proposed algorithm reduces the total routing area by up to 5.71% and uses less runtime. To the best of our knowledge, this work is the first in-depth study on full-chip routing optimization with RLC crosstalk budgeting.

In this article, we first show that existing net ordering formulations to minimize noise are no longer sufficient with the presence of inductive noise, and shield insertion is needed to minimize inductive noise. Using a K eff model as the figure of merit for inductive coupling, we then formulate two simultaneous shield insertion and net ordering (SINO) problems: the optimal SINO/NF problem to find a minimal area SINO solution that is free of capacitive and inductive noise, and the optimal SINO/NB problem to find a minimal area SINO solution that is free of capacitive noise and is under the given inductive noise bound. We reveal that both optimal SINO problems are NP-hard, and propose effective approximate algorithms for the two problems. Experiments show that our SINO/NB algorithm uses from 51% to 82% fewer shields compared to uniform shield insertion and net ordering (US + NO), and uses from 4% to 47% fewer shields compared to separated net ordering and shield insertion (NO + SI). Furthermore, the SINO/NB solutions under practical noise bounds use from 38% to 61% fewer shields compared to SINO/NF solutions, and use up to 36% fewer shields compared to the theoretical lower bound for optimal SINO/NF solutions. Moreover, we show that the K eff model has a high fidelity versus the noise voltage computed using accurate RLC circuit models and SPICE simulations. To the best of our knowledge, it is the first work that presents an in-depth study on the automatic layout optimization of multiple nets to minimize both capacitive and inductive noise.

Sleep transistors are effective to reduce leakage power during standby modes. The cluster-based design was proposed to save sleep transistor area by clustering gates to minimize the simultaneous switching current per cluster and inserting a sleep transistor per cluster. In this paper, we propose a novel distributed sleep transistor network (DSTN), and show that DSTN is intrinsically better than the cluster-based design in terms of the sleep transistor area and circuit performance. We reveal properties of optimal DSTN designs, and then develop an efficient algorithm for gate level DSTN synthesis. The algorithm obtains DSTN designs with up to 70.7% sleep transistor area reduction compared to cluster-based designs. Furthermore, we present custom layout designs to verify the area reduction by DSTN.

Considering RLC interconnect model and multiple switching aggressors, we study switching pattern generation and switching time alignment that leads to worst-case crosstalk noise for a quiet victim or a noisy one. We assume that aggressors can have arbitrary switching patterns and can switch at arbitrary times. We show that the commonly used superposition algorithm results in 15% underestimation on average, and propose a new algorithm that has virtually the same complexity as the superposition algorithm but approximates the exhaustive search very well with only 4% underestimation on average. Further, we show that applying RC model to GHz+ interconnects in IRTS 0.10 μm technology underestimates crosstalk noise by up to 80%, and convincingly conclude that RLC model is necessary to analyze such interconnects.

Sleep transistors are effective to reduce dynamic and leakage power. The cluster-based design was proposed to reduce the sleep transistor area by clustering gates to minimize the simultaneous switching current per cluster and then inserting a sleep transistor per cluster. In the paper, we propose a novel distributed sleep transistor network (DSTN), and show that DSTN is intrinsically better than the cluster-based design in terms of the sleep transistor area and circuit performance. We reveal properties of optimal DSTN designs, and then develop an efficient algorithm for gate level DSTN synthesis. The algorithm obtains DSTN designs with up to 70.7% sleep transistor area reduction compared to cluster-based designs. Furthermore, we present custom layout designs to verify the area reduction by DSTN.

The geometry-integration based vector potential equivalent circuit (VPEC) was introduced to obtain a localized circuit model for inductive interconnects in [1]. In this paper, we show that the method in [1] is accurate only for the two body problem. We derive N-body VPEC models based on geometry integration and inversion of inductance matrix under the PEEC model, respectively. Both VPEC models are derived from first principles and are accurate compared to the full PEEC model. The resulting circuit matrix G can be analyzed directly by existing simulation tools such as SPICE, and the simulation time of VPEC model is 47X less than that for PEEC model for a bus structure with 256 wires. It is also passive and strictly diagonal dominant, which leads to efficient circuit sparsification methods such as numerical and geometry based sparsifications. Compared to the full PEEC model, the sparsified VPEC models are orders of magnitude faster and produce waveforms with very small error.

This paper presents a flexible FPGA architecture evaluation framework, named fpgaEVA-LP, for power efficiency analysis of LUT-based FPGA architectures. Our work has several contributions: (i) We develop a mixed-level FPGA power model that combines switch-level models for interconnects and macromodels for LUTs; (ii) We develop a tool that automatically generates a back-annotated gate-level netlist with post-layout extracted capacitances and delays; (iii) We develop a cycle-accurate power simulator based on our power model. It carries out gate-level simulation under real delay model and is able to capture glitch power; (iv) Using the framework fpgaEVA-LP, we study the power efficiency of FPGAs, in 0.10um technology, under various settings of architecture parameters such as LUT sizes, cluster sizes and wire segmentation schemes and reach several important conclusions. We also present the detailed power consumption distribution among different FPGA components and shed light on the potential opportunities of power optimization for future FPGA designs (e.g., ≤: 0.10um technology).

In this paper, we present power models with clock and temperature scaling, and develop the first of its type coupled thermal and power simulation with temperature-dependent leakage power model at micro-architecture level. We show that leakage energy and total energy can be different by up to 2.5X and 2X for temperatures between 90°C and 130°C, respectively. Given such big energy variations, no power model at microarchitecture level is accurate without considering temperature dependent leakage models.

Conventional global routing minimizes total wire length and congestion. Experiments using large industrial benchmark circuits show that up to 24% of nets in such routing solutions may have RLC crosstalk violations at 3GHz clock. We develop an extremely efficient length-scaled Keff (LSK) model that has a high fidelity for long-range RLC crosstalk. We formulate an extended global routing problem (denoted as GSINO) to consider simultaneous shield insertion and net ordering with RLC crosstalk constraints, then propose an effective three-phase GSINO algorithm. The GSINO algorithm completely eliminates the RLC crosstalk violations, and has small area and wire length overhead compared to conventional routing.

In this paper we present an efficient decoupling model for on-chip interconnect analysis. This model decouples multiple RLC transmission lines into independent lines with separate drivers and receivers. Based on this model we propose an efficient algorithm to solve the far end responses of multiple RLC lines. Experiments show good matching between our decoupling model and SPICE simulation. Based on the model, we further develop an Nmax algorithm to quickly determine the noise amplitudes of far end responses. Experiments show that Nmax algorithm gives conservative but reasonably accurate results compared to SPICE simulation.

In this paper, we study leakage power reduction using power gating in the forms of the Virtual power/ground Rails Clamp (VRC) and Multi-threshold CMOS (MTCMOS) techniques. We apply power gating to two circuit types: memory-based units and datapath components. Using a microarchitecture-level power simulator, as well as power and timing models derived from detailed circuit designs, we further study leakage power modeling and reduction at the system level for modern high-performance VLIW processors. We show that the leakage power can be over 40% of the total power for such processors. Moreover, we propose time-out scheduling of VRC to reduce power up to 85.65% for L2 cache. This power savings results in close to 1/3 total power dissipation for the VLIW processors we study.

Existing layout optimization methods often assume a set of interconnects with given RLC crosstalk bounds in a routing region. RLC crosstalk bound partitioning is critical for effectively applying these methods at the full-chip level. In this paper, we develop an optimal crosstalk budgeting scheme based on linear programming (LP) formulation, and apply it to shield insertion and net ordering at the full-chip level. Experiment results show that compared to the best alternative approach, the LP based method reduces the total routing area by up to 7.61% and also uses less runtime. To the best of our knowledge, this is the first in-depth work that studies the RLC crosstalk budgeting problem.

In this paper, we present a new decoupled model for two coupled transmission lines with consideration of the inductive effect. It maps two coupled lines into two completely isolated lines with separated drivers and receivers, and has no loss of accuracy during the decoupling procedure. Further, we derive a closed-form time domain response for an isolated transmission line using a one-segment RLC II model. Combining the two models, we have an analytical time-domain solution to two coupled transmission lines. The model gives satisfied results for up to 5000 um-long lines when compared to SPICE simulation over an accurate distributed RLC circuit model, and can be used to model on-chip wires in the layout design, logic synthesis and high level design.

For multiple coupled RLC nets, we formulate the min-area simultaneous shield insertion and net ordering SINO/NB-ν problem to satisfy the given noise bound. We develop an efficient and conservative model to compute the peak noise, and apply the noise model to a simulated-annealing (SA) based algorithm for the SINO/NB-ν problem. Extensive and accurate experiments show that the SA-based algorithm is efficient, and always achieves solutions satisfying the given noise bound. It uses up to 71\% and 30\% fewer shields when compared to a greedy based shield insertion algorithm and a separated shield insertion and net ordering algorithm, respectively. To the best of our knowledge, it is the first work that presents an in-depth study on the min-area SINO problem under an explicit noise constraint.

In this paper, we propose an e#cient table-based model for frequency-dependent on-chip inductance, and apply it to compute mutual inductance between random wires and loop inductance for cascade wires, respectively. Our inductance computation achieves around 5% error when compared to the numerical solution, and matches frequency-dependent impact very well. We also apply the inductance model to generate RLC circuit models for on-chip interconnects, and present a complexitye #cient normalized RLC circuit model for multiple parallel wires.

It has been shown recently that simultaneous shield insertion and net ordering (called SINO/R as only random shields are used) provides an area-efficient solution to reduce the RLC noise. In this paper, we first develop simple formulae with errors less than 10% to estimate the number of shields in the min-area SINO/R solution. In order to accommodate pre-routed P/G wires that also serve as shields, we then formulate two new SINO problems: SINO/SPR and SINO/UPG, and propose effective and efficient two-phase algorithms to solve them. Compared to the existing dense wiring fabric scheme, the resulting SINO/SPR and SINO/UPG schemes maintain the regularity of the P/G structure, have negligible penalty on noise and delay variation, and reduce the total routing area by up to 42% and 36%, respectively. Further, we develop various pre-layout estimation formulae for shielding areas and optimal P/G structures under different routing styles. These formulae can be readily used to guide global routing and high-level design decisions.

The formiila-based I<,JJ model is a figiire of merit for the inductive coirpling, and has been used to solve the simrrltaneoris shield insertion and net ordering (SINO) and simisltaneoris signal and power routing (SPR) problems. In this papec we first show ihat the Iivf,f model has a high fidelity compared to the SPICE-computed noise rinder an accurate KLC circuit model. We then develop.simple yet accurate Jormrilae to estimate numbers of shields needed by optimal SINO solitlions rinder the liejj model. Extensive e.yeriments show that our pre-routing estimation has errors less lhan 10 % compared to solutions given by detailed SIN0 algorithms. These.fimnrslae can fie irsed eJfecliveIy as a pre-routing congestion estimation jor layorit planning and synthesis. 1.

As semiconductor technology scales down, the leakage power will soon become comparable to the dynamic power. To reduce both dynamic and leakage power, power gating in addition to clock gating should be used because clock gating saves only dynamic power. The knowledge of maximum current is needed to design high-performance and reliable circuits using power gating. However, all existing techniques for maximum current estimation are not applicable to power gating. In this paper, we study the maximum current estimation problem considering power gating. We develop two algorithms based on automatic test pattern generation (ATPG), and apply them to ISCAS'85 benchmarks. Experiments show that our new estimation algorithms can finish the largest benchmark circuit within ten seconds, and achieve up to 87% larger current when compared to an existing ATPG-based estimation algorithm that is able to obtain maximum current estimation 6% less than the theoretical maximum current without considering power gating. This implies that power gating may lead to a larger maximum current when compared to the normal maximum switching current, and open a new avenue for maximum current estimation as well as circuit reliability research.

This paper studies interconnect sizing and space (ISS) problem with consideration of coupling capacitance for performance optimization of single or multiple critical nets. We introduce the formulation of symmetric and asymmetric wire sizing. We develop efficient bound computation algorithms for ISS optimization and prove their optimality under general interconnect resistance and capacitance models. Our experiments show that our algorithms are very effective and obtain significant performance improvement compared to previous wire-sizing/spacing algorithms.

In this paper we present an efficient yet accurate inductance extraction methodology and also apply it to clocktree RLC extraction. We first show that without loss of accuracy, the inductance extraction problem of n traces with or without ground planes can be reduced to a number of one-trace and two-trace subproblems. We then solve one-trace and two-trace subproblems via a table-based approach. We finally validate the linear cascading assumption that enables us to apply our inductance extraction approach to clocktree RLC extraction and optimization.

In this paper, we first show that existing net ordering formulations to minimize noise are no longer valid with presence of inductive noise, and shield insertion is needed to minimize inductive noise.We then formulate two simultaneous shield insertion and net ordering (SINO) problems: the optimal SINO/NF problem to find a min-area SINO solution that is free of capacitive and inductive noise, and the optimal SINO/NB problem to find a min-area SINO solution that is free of capacitive noise and is under the given inductive noise bound.We reveal that both optimal SINO problems are NP-hard, and propose effective approximate algorithms for the two problems.Experiments show that our SINO/NB algorithm uses from 15% to 57% fewer shield wires when compared to separated net ordering and shield insertion procedure.Furthermore, under practical noise bounds, the SINO/NB solutions use from 44% to 67% fewer shield wires when compared to SINO/NF solutions, and use 10% to 40% fewer shield wires when compared to the theoretical lower bound for optimal SINO/NF solutions.Additionally, all our algorithms are extremely efficient to finish all examples in a few seconds.To the best of our knowledge, it is the first work that presents an indepth study on the simultaneous shield insertion and net ordering problem to minimize both capacitive and inductive noise.

In this paper we formulate three classes of optimization problems: the simple, monotonically constrained, and bounded Cong-He (CH)-programs. We reveal the dominance property under the local refinement (LR) operation for the simple CH-program, as well as the general dominance property under the pseudo-LR operation for the monotonically constrained CH-program and the extended-LR operation for the bounded CH-program. These properties enable a very efficient polynomial-time algorithm, using different types of LR operations to compute tight lower and upper bounds of the exact solution to any CH-program. We show that the algorithm is capable of solving many layout optimization problems in deep submicron iterative circuit and/or high-performance multichip module (MCM) and printed circuit board (PCB) designs. In particular, we apply the algorithm to the simultaneous transistor and interconnect sizing problem, and to the global interconnect sizing and spacing problem considering the coupling capacitance for multiple nets. We use tables precomputed from SPICE simulations and numerical capacitance extractions to model device delay and interconnect capacitance, so that our device and interconnect models are much more accurate than many used in previous interconnect optimization algorithms. Experiments show that the bound-computation algorithm can efficiently handle such complex models, and obtain solutions close to the global optimum in most cases. We believe that the CH-program formulations and the bound-computation algorithm can also be applied to other optimization problems in the computer-aided design field.

In this paper, we formulate a new class of optimization problem, named the general CH-posynomial program, and reveal the general dominance property. We propose an efficient algorithm based on the extended local refinement operation to compute lower and upper bounds of the exact solution to the general CH-posynomial program. We apply the algorithm to solve the simultaneous transistor and interconnect sizing (STIS) problem under the table-based device model, and the global interconnect sizing and spacing (GISS) problem with consideration of the crosstalk capacitance. Experiment results show that our algorithm can handle many device and interconnect modeling issues in deep submicron designs and is very efficient.

This paper addresses post-routing capacitance extraction duringperformance-driven layout. We first show how basic driversin process technology (planarization and minimum metal densityrequirements) actually simplify the extraction problem; wedo this by proposing and validating five "foundations" throughdetailed experiments with representative 0.18μm process parametersand a 3-D field solver.We then present a simple yetaccurate 2 1/2-D extraction methodology directly based on thefoundations.This methodology has been productized and isbeing shipped with the Cadence Silicon Ensemble 5.0 product.We conclude that the 2 1/2-D approach has sufficient accuracyfor current and near-term process generations.

The paper presents an efficient approach to perform global interconnect sizing and spacing (GISS) for multiple nets to minimize interconnect delays with consideration of coupling capacitance, in addition to area and fringing capacitances. We introduce the formulation of symmetric and asymmetric wire sizing and spacing. We prove two important results on the symmetric and asymmetric effective fringing properties which lead to a very effective bound computation algorithm to compute the upper and lower bounds of the optimal wire sizing and spacing solution for all nets under consideration. Our experiments show that in most cases the upper and lower bounds meet quickly after a few iterations and we actually obtain the optimal solution. To our knowledge, this is the first in depth study of global wire sizing and spacing for multiple nets with consideration of coupling capacitance. Experimental results show that our GISS solutions lead to substantially better delay reduction than existing single net wire sizing solutions without consideration of coupling capacitance.

In this paper, we study the simultaneous transistor and interconnect sizing (STIS) problem. We define a class of optimization problems as CH-posynomial programs and reveal a general dominance property for all CH-posynomial programs. We show that the STIS problems under a number of transistor delay models are CH-posynomial programs and propose an efficient and near-optimal STIS algorithm based on the dominance property. When used to solve the simultaneous driver/buffer and wire sizing problem for real designs, it reduces the maximum delay by up to 16.1%, and more significantly, reduces the power consumption by a factor of 1.63/spl times/, when compared with the original designs. When used to solve the transistor sizing problem, it achieves a smooth area-delay trade-off. Moreover, the algorithm optimizes a clock net of 367 drivers/buffers and 59304 /spl mu/m-long wire in 120 seconds, and a 32-bit adder with 1026 transistors in 66 seconds on a SPARC-5 workstation.

In this paper, we study the optimal wiresizing problem for nets with multiple sources under the RC tree model and the Elmore delay model. We decompose the routing tree for a multisource net into the source subtree (SST) and a set of loading subtrees (LSTs), and show that the optimal wiresizing solution satisfies a number of interesting properties, including: LST separability, the LST monotone property, the SST local monotone property, and the dominance property. Furthermore, we study the optimal wiresizing problem using a variable segment-division rather than an a priori fixed segment-division as in all previous works and reveal the bundled refinement property. These properties lead to efficient algorithms to compute the optimal solutions. We have tested our algorithm on nets extracted from the multilayer layout for a high-performance Intel microprocessor. Accurate SPICE simulation shows that our methods reduce the average delay by up to 23.5% and the maximum delay by up to 37.8%, respectively, for the submicron CMOS technology when compared to the minimal wire width solution. In addition, the algorithm based on the variable segment-division yields a speedup of over 100× time and does not lose any accuracy, when compared with the algorithm based on the a priori fixed segment-division.

The optimal wiresizing problem for nets with multiple sources is studied under the distributed Elmore delay model. We decompose such a net into a source subtree (SST) and a set of loading subtrees (LSTs), and show the optimal wiresizing solution satisfies a number of interesting properties, including: the LST separability, the LST monotone property, the SST local monotone property and the general dominance property. Furthermore, we study the optimal wiresizing problem using a variable grid and reveal the bundled refinement property. These properties lead to efficient algorithms to compute the lower and upper bounds of the optimal solutions. Experiment results on nets from an Intel processor layout show an interconnect delay reduction of up to 35.9% when compared to the minimum-width solution. In addition, the algorithm based on a variable grid yields a speedup of two orders of magnitude without loss of accuracy, when compared with the fixed grid based methods.