Monte Carlo random walk methods are widely used in capacitance extraction for their mesh-free formulation and inherent parallelism. However, modern semiconductor technologies with densely packed structures present significant challenges in unbiasedly sampling transition domains in walk steps with multiple high-contrast dielectric materials. We present DeepRWCap, a machine learning-guided random walk solver that predicts the transition quantities required to guide each step of the walk. These include Poisson kernels, gradient kernels, signs and magnitudes of weight. DeepRWCap employs a two-stage neural architecture that decomposes structured outputs into face-wise distributions and spatial kernels on cube faces. It uses 3D convolutional networks to capture volumetric dielectric interactions and 2D depthwise separable convolutions to model localized kernel behavior. The design incorporates grid-based positional encodings and structural design choices informed by cube symmetries to reduce learning redundancy and improve generalization. Trained on 100,000 procedurally generated dielectric configurations, DeepRWCap achieves a mean relative error of 1.24±0.53% when benchmarked against the commercial Raphael solver on the self-capacitance estimation of 10 industrial designs spanning 12 to 55 nm nodes. Compared to the state-of-the-art stochastic difference method Microwalk, DeepRWCap achieves an average 23% speedup. On complex designs with runtimes over 10s, it reaches an average 49% acceleration.

The escalating scale and complexity of modern circuits demand multi-FPGA emulation platforms that incorporate multi-die architectures. However, most existing routers remain FPGA-level, optimizing wire-length or total Time-Division Multiplexing (TDM) ratios while disregarding die-level load imbalance and path-level slack. They result in suboptimal performance and timing violations. In this paper, we propose a timing-aware co-optimization framework for die-level routing and TDM assignment, explicitly linking physical constraints to critical path timing slack. The proposed flow features a timing-aware load-balanced die-level router with timing path compression and a timing graph-based TDM assignment. Experiments on industrial designs show that the proposed method improves the worst-path slack by 98% over the existing methods.

Parameter tuning for multi-FPGA partitioning algorithms represents a bottleneck in modern chip emulation and verification workflows. Current multilevel partitioning tools require manual configuration of various parameters, where each evaluation can take tens of seconds to minutes, making exhaustive search impractical and expert-driven tuning both time-consuming and suboptimal. To automate this process, we propose a preference-guided Bayesian optimization framework specifically designed for industrial FPGA partitioning parameter tuning under limited evaluation budgets. Our approach maximizes the minimum timing slack by incorporating domain-specific insights: we exploit the strong correlation between cutsize and timing performance through a priority-based ranking scheme that guides a pairwise Gaussian process to learn configuration preferences. Additionally, we introduce a kernel input transformation that properly handles the mixed discrete-continuous parameter space typical in EDA tools. Our method converges faster with fewer evaluations and achieves the best timing slack in 60–70% of cases on industrial circuit benchmarks compared to existing methods including standard Bayesian optimization, quasi-random sampling, and state-of-the-art preference learning techniques. The proposed framework reduces parameter tuning from days of manual effort to hours of automated optimization, offering practitioners a deployment-ready solution that improves both design quality and engineering productivity.

Sparse linear-equation solvers are indispensable to circuit simulation. They provide the mathematical engine that faithfully forecasts the dynamic response of analog circuits. In this invited paper, we present two novel techniques to speed up these solvers. The first is a parallel LU factorization driven by a new task scheduling strategy. Based on the nested dissection approach for matrix reordering, we derive a task assignment/scheduling strategy which largely reduces synchronization and develops more parallelism. Thus, a more efficient parallel sparse LU factorization algorithm (named SubtreeLU) is obtained. It outperforms both PARDISO and CKTSO in computational speed while remaining similar robustness. The second technique is a practical randomized GMRES algorithm. By implementing the Gram-Schmidt process with an extremely efficient random sketched linear-least-squares kernel, we obtain a fast randomized Arnoldi procedure that orthogonormalizes the Krylov subspace basis. Coupled with on-the-fly residual error estimates, this yields a practical randomized GMRES that is provably stable and runs remarkably faster than the standard GMRES on a wide range of circuit and field simulation benchmarks.

Efficient and reliable device simulation remains a critical challenge for modern electronic design automation (EDA), where ill-conditioned sparse linear equation systems are often solved. Traditional linear matrix solvers struggle to balance accuracy, performance, and scalability concurrently in the presence of ill-conditioning. In this work, we propose a parallel solver framework that integrates mixed-precision iterative refinement with GMRES algorithm and novel architecture-aware optimizations on modern CPUs. Our approach leverages vectorization, parallel scheduling, and memory hierarchy optimizations to accelerate Krylov subspace methods while preserving numerical robustness. Comprehensive evaluation on matrices arising from realistic device simulation problems demonstrates that our solver achieves 5.4× speedup on average, compared to the high-precision direct solver baseline, while maintaining solution accuracy within given tolerances. Moreover, the proposed mixed-precision GMRES-IR solver attains further 3.3× parallel speedup with 8 threads, demonstrating its parallel efficiency.

Hypergraph partitioning is a fundamental combinatorial optimization problem with critical applications in VLSI design. While recent deep learning based approaches have shown promise for this problem, they rely on graph neural networks (GNNs) that require transforming hypergraphs into normal graphs, thereby losing the high-order relationships in hypergraph structures. In this work, we propose a novel framework that directly utilizes hypergraph neural networks (HGNNs) to exploit the high-order interactions in hypergraphs. We develop an efficient normalized cut loss computation algorithm optimized for GPU training and apply randomized matrix decomposition techniques to significantly accelerate the eigenvector computation required for node feature extraction without sacrificing quality. To address the scarcity of open-source hypergraph data, we release a comprehensive dataset with 164 VLSI hypergraphs collected from various EDA contests and benchmarks. Extensive experiments on the ISPD98 and ISPD05 benchmarks demonstrate that our method achieves superior partitioning quality compared to state-of-the-art approaches, including multilevel methods (hMETIS), spectral methods (SpecPart, K-SpecPart), and recent deep learning based approaches (MedPart, GenPart). Furthermore, training on our expanded dataset yields additional performance gains, validating the framework’s ability to leverage larger training data effectively.

The accuracy of floating-random-walk (FRW) based capacitance extraction stands only when the recursive FRW transitions are sampled unbiasedly according to surrounding dielectrics. Advanced technology profiles, featuring complicated non-stratified dielectrics, challenge the accuracy of existing FRW transition schemes that approximate dielectrics with stratified or eight-octant patterns. In this work, we propose an algorithm named MicroWalk, enabling accurate FRW transitions for arbitrary dielectrics while keeping high efficiency. It is provably unbiased and equivalent to using transition probabilities solved by finite difference method, but at orders of magnitude lower cost (802× faster). An enhanced 3-D capacitance solver is developed with a hybrid strategy for complicated dielectrics, combining MicroWalk with the special treatment for the first transition cube and the analytical algorithm for stratified cubes. Experiments on real-world structures show that our solver achieves a significant accuracy advantage over existing FRW solvers, while preserving high efficiency.

Many-core neuromorphic integrated circuits (ICs) have the potential advantages of low power consumption, high parallelism, etc. for the edge computing of deep learning. A key problem in the application of many-core neuromorphic IC is how to efficiently deploy the deep neural networks onto the core clusters. Notice that mapping the neural network clusters to physical cores is NP-hard due to the super-exponential growth of the search space. In this work, we propose a novel approach termed the Dimensional Order Search (DOS) based mapping algorithm, which integrates a branch-and-bound strategy to reduce the size of search space to no more than 4!·2!·8!. The DOS further employs a time-sharing protocol that eliminates deadlocks via priority-based channel arbitration. A key strength of DOS lies in its ability to preserve the optimality of mappings with increasing core allocations, backed by asymptotic convergence guarantees. DOS achieves a probability asymptotically approaching unity as core allocation scales. Furthermore, we provide a mathematical proof of the optimality-preserving property of the proposed mapping algorithm. Experimental results on a 160-core TianjicX neuromorphic platform demonstrate that DOS achieves significant improvements in routing efficiency compared to conventional methods. Specifically, DOS reduces mapping time for ResNet-50 by 3.9×, 5.55×, and 10.99× versus genetic algorithms (GA), simulated annealing (SA), and reinforcement learning (RL) approaches respectively. Similar gains are observed for VGG-16 (3.32×/ 5.96×/ 3.44×) and Inception-V3 (3.94×/ 7.37×/ 5.11×) when compared to GA, SA, and RL baselines. Our work bridges the gap between the complexity of theoretical mapping and practical implementations of many cores.

Efficient techniques are proposed for parallel incomplete LU (ILU) factorization and forward/backward substitution, for the sparse matrices with the same sparsity pattern. These parallel algorithms are then used as a preconditioner for the generalized minimal residual (GMRES) algorithm to obtain an ILU-GMRES solver for large-scale circuit simulation. The novelty of the parallel ILU and substitution algorithms includes a subtree-based task scheduling scheme, a nested dissection-based approach for generating task queues, and the task packing and reverse-order execution techniques for forward/backward substitution. Experiments on 43 matrices dumped from circuit simulation show that the 8-thread parallel ILU with threshold (ILUT) factorization and forward/backward substitution with the proposed techniques achieve 4.2 \(\times\) and 3.3 \(\times\) parallel speedups on average, respectively. The proposed parallel ILUT-GMRES solver runs 5.3 \(\times\) , on average, faster than PARDISO on these benchmarks. When integrated into Ngspice, it enables up to 2.3 \(\times\) and 1.7 \(\times\) faster execution of a step of Newton-Raphson iteration than the commercial parallel HSPICE, for the DC analysis and time integration stages, respectively.

Ordered escape routing (OER), which seeks the routing paths from some signal pins to the boundary of a pin array in a given order, is an important research topic for PCB design. Although reinforcement learning based methods for OER have been proposed, the routing capacity between two adjacent pins is assumed to be just one. In this work, we propose MCMC-Escape, a Monte-Carlo tree search (MCTS) based multi-capacity ordered escape router, which includes, in turn, the initial solving approach, the improved Monte-Carlo tree search (improved MCTS) process, and the last routing attempt approach based on wires removing and re-routing. In the improved MCTS, the prior knowledge based pruning strategies and the fine-tuning strategy are proposed to enhance the efficiency of solving multi-capacity OER (MC-OER) problems, while the weight adjusting strategy is proposed to address the path occupancy issues arising from multiple capacity. Experimental results demonstrate that MCMC-Escape can effectively solve large-scale MC-OER problems and outperform existing methods in terms of routing success rate, runtime and wire length. For a set of problems with 50×50 pin array, MCMC-Escape achieves 4X higher success rate of routing with 50% less solving time than MCMCF-Router [ 1 ], while reducing the average total wire length.

Efficient solver for general linear equations is of significance for EDA problems. The generalized minimal residual (GMRES) method, which can solve general linear equations efficiently, is one of the most widely-used fundamental algorithms. Randomized Arnoldi process, which leverages sketched least-squares solver to orthogonalize Krylov subspace basis, has shown potential to promote the effectiveness of Arnoldi process, the core step in GMRES. However, how to make it more efficient, and utilize it to develop a practical GMRES solver is still an open problem. In this work, we aim at obtaining a practically-useful randomized GMRES algorithm (named PRGMRES) for solving general sparse linear equations. Firstly, an efficient estimator of residual error based on a modified randomized Gram-Schmidt process and a double-tolerance scheme are proposed to enable a practical restarted GMRES algorithm which terminates at a solution satisfying the specified accuracy tolerance. Then, a linear-time-complexity sketching algorithm based on Rademacher matrices is proposed to facilitate fast and robust random sketching. After that, incremental solution of the sketched least-squares problems, and the theoretical analysis supporting smaller sketching size are presented. Based on the above proposed techniques and theoretical results, the PRGMRES algorithm, which has stronger theoretically-supported stability and efficiency, is proposed. Numerical experiments on various circuit simulation problems validate the efficiency and effectiveness of the proposed algorithm.

As the scale of integrated circuit (IC) design continues to expand, the multi-FPGA system (MFS) is widely employed for logic emulation and simulation acceleration which ensures the functional correctness of logic circuits. During this process, circuit partitioning becomes a dispensable step. In this work, we address the hypergraph modeling techniques for the MFS-orientated circuit partitioning. Firstly, an efficient adaptive flattening algorithm considering multi-dimensional resource constraints and based on dynamic programming (DP) is proposed. Then, a parallel algorithm for clock modeling is proposed. With them, an efficient tool of hypergraph modeling is developed. Experiments on industrial benchmarks with up to sixty million cells have validated the efficiency and correctness of the proposed techniques. The results also demonstrate the benefit of the adaptive flattening to the subsequent hypergraph partitioning, and the significant acceleration effects of the proposed DP-based adaptive flattening and the parallel clock modeling algorithms.

With the advancement of integrated circuit (IC), the process technology becomes more complicated and the design margin shrinks. Thus, the parasitic extraction is more demanded during IC design. In this invited paper, we survey the research progress on IC capacitance extraction, especially the usage of deep-learning technologies in relevant problems. Firstly, a method based on graph neural network (GNN) for predicting the parasitic capacitances in the pre-layout design stage is presented. It exhibits potential benefit for the optimization of SRAM design. Then, the deep-learning-inspired methods for post-layout capacitance extraction are presented, including CNN-Cap, NAS-Cap and GNN-Cap, etc. They can revamp the accuracy drawback of layout parasitic extraction (LPE) method and the efficiency drawback of 3-D capacitance field solver. Lastly, we briefly review the deep-learning technique for improving the accuracy of the random walk based 3-D capacitance solver for the structures under the advanced process technology.

Graph representation learning is a powerful method to extract features from graph-structured data, such as analog/mixed-signal (AMS) circuits. However, training deep learning models for AMS designs is severely limited by the scarcity of integrated circuit design data. In this work, we present CircuitGPS, a few-shot learning method for parasitic effect prediction in AMS circuits. The circuit netlist is represented as a heterogeneous graph, with the coupling capacitance modeled as a link. CircuitGPS is pre-trained on link prediction and fine-tuned on edge regression. The proposed method starts with a small-hop sampling technique that converts a link or a node into a subgraph. Then, the subgraph embeddings are learned with a hybrid graph Transformer. Additionally, CircuitGPS integrates a low-cost positional encoding that summarizes the positional and structural information of the sampled subgraph. CircuitGPS improves the accuracy of coupling existence by at least 20% and reduces the MAE of capacitance estimation by at least 0.067 compared to existing methods. Our method demonstrates strong inherent scalability, enabling direct application to diverse AMS circuit designs through zero-shot learning. Furthermore, the ablation studies provide valuable insights into graph models for representation learning.

Balanced hypergraph partitioning is a fundamental problem in applications like VLSI design, high-performance computing, etc. Nowadays, large-scale hypergraphs become more common due to the increasing complexity of modern systems. Thus, fast and high-quality deterministic partitioning algorithms are largely in demand. Regarding the quality of partitioning, balance is a critical concern when the number of partitions increases. In this paper, we propose BlasPart, a deterministic parallel algorithm for balanced large-scale hypergraph partitioning. BlasPart leverages a recursive multilevel bisection framework to achieve high-quality partitions while ensuring deterministic outcomes. A level-dependent balance constraint is also proposed to further improve the efficiency and effectiveness of the proposed partitioner. Extensive experiments, with comparisons to the state-of-the-art partitioners (hMETIS, BiPart, and Mt-KaHyParSDet), demonstrate that BlasPart achieves better balance and scalability while maintaining competitive partitioning quality and efficiency. BlasPart runs $3.33 \times$ faster than Mt-KaHyPar-SDet on average for a 4096-way partitioning task on six benchmarks.

The floating random walk (FRW) method is a popular and promising tool for capacitance extraction, but its stochastic nature leads to critical limitations in reproducibility and physics-related reliability. In this work, we present FRW- RR, a parallel FRW solver with enhancements for Reproducible and Reliable capacitance extraction. First, we propose a novel parallel FRW scheme that ensures reproducible results, regardless of the degree of parallelism (DOP) or machine used. We further optimize its parallel efficiency and enhance the numerical stability. Then, to guarantee the physical properties of capacitances and reliability for downstream tasks, we propose a regularization technique based on constrained multi-parameter estimation to postprocess FRW's results. Experiments on actual IC structures demonstrate that, FRW-RR ensures DOP-independent reproducibility (with at least 12 decimal significant digits) and physics-related reliability with negligible overhead. It has remarkable advantages over existing FRW solvers, including the one in [1].

Solving sparse linear systems via LU factorization remains a critical performance bottleneck in SPICE-based circuit simulation. Existing solvers such as NICSLU and CKTSO have introduced various improvements, but they continue to face limitations such as synchronization overheads, conservative dependency estimation, and under-utilization of supernodal structures. In this work, we propose SubtreeLU, a high-performance parallel sparse LU factorization framework tailored for circuit simulation. SubtreeLU introduces a novel scheduling framework that either collapses or partitions the separator tree generated by nested dissection to organize computation into a private-pipeline structure. This enables efficient support for both pivoting and non-pivoting modes. Supernodal methods are integrated to further accelerate numerical updates. Extensive experiments on 46 circuit matrices demonstrate that SubtreeLU consistently outperforms state-of-the-art solvers in terms of accuracy, runtime, and scalability. The proposed SubtreeLU solver is available at https://numbda.cs.tsinghua.edu.cn/download.html.

Graph representation learning on Analog-Mixed Signal (AMS) circuits is crucial for various downstream tasks, e.g., parasitic estimation. However, the scarcity of design data, the unbalanced distribution of labels, and the inherent diversity of circuit implementations pose significant challenges to learning robust and transferable circuit representations. To address these limitations, we propose CircuitGCL, a novel graph contrastive learning framework that integrates representation scattering and label rebalancing to enhance transferability across heterogeneous circuit graphs. CircuitGCL employs a self-supervised strategy to learn topology-invariant node embeddings through hyperspherical representation scattering, eliminating dependency on large-scale data. Simultaneously, balanced mean squared error (BMSE) and balanced softmax cross-entropy (BSCE) losses are introduced to mitigate label distribution disparities between circuits, enabling robust and transferable parasitic estimation. Evaluated on parasitic capacitance estimation (edge-level task) and ground capacitance classification (node-level task) across TSMC 28nm AMS designs, CircuitGCL outperforms all state-of-the-art (SOTA) methods, with the R2improvement of 33.64% ~ 44.20% for edge regression and F1-score gain of 0.9× ~ 2.1× for node classification. Our code is available at https://github.com/ShenShan123/CircuitGCL.

The photolithography process is getting more sophisticated with technology node scaling down and VLSI designs becoming complex. As photomask patterns get finer, mask rule checks (MRCs) are inevitable to avoid discrepancies in the layout and to ensure manufacturability. This paper introduces an efficient mask rule checking approach that utilizes a representative edge sampling scheme. The representative edge sampling scheme selects a subset of edges and points of each polygon that capture its contour, meanwhile greatly reducing the number of edges involved in actual checking. Experimental results demonstrate that the proposed approach achieves significant speedup compared with the state-of-the-art academic tool.

With the advance of very-large-scale-integrated (VLSI) systems, fast and efficient algorithms for solving equations of Laplacian matrices are increasingly significant. Graph spectral sparsification, which aims to produce an ultra-sparse subgraph while preserving properties of original graph, has aroused extensive attention thanks to its distinguished performance. For preconditioning, the effectiveness of sparsifiers produced by graph spectral sparsification algorithms may directly influence the speed of PCG iterations, while the recently proposed algorithm that pursues effective sparsifiers may result in huge time expenditure of sparsifier construction as calculating the sparse approximate inverse of Cholesky factor may be rather time-consuming. In this paper, based on domain decomposition, a parallel algorithm for calculating sparse approximate inverse of Cholesky factor is proposed, where a skill for calculating Schur complement matrix based on partial Cholesky factorization is applied. Based on the proposed parallel algorithm for calculating sparse approximate inverse of Cholesky factor, a fast and effective parallel graph spectral sparsification algorithm is proposed. Extensive experiments reveal that the proposed parallel graph spectral sparsification algorithm shows eminent speedup compared with serial approach. Moreover, for transient analysis of power grids, the proposed algorithm shows significant speedup compared with the state-of-the-art parallel iterative solver based on graph sparsification.

Accurate and efficient transient analysis of power grids (PGs) poses a large challenge of computation for nowadays integrated circuit design. In this work, we propose to leverage the public cloud computing to do PG transient analysis while preserving security. A multi-level distributed parallel LU factorization and forward/backward substitution approach based on nested dissection is then proposed to guarantee accuracy and robustness. Experimental results show that the proposed algorithm can achieve an average 2.06X speedup over NICSLU and 2.85X over conventional domain decomposition method based parallel approach. And, it exhibits good scalability with up to 6.0X parallel speedup on large-scale PGs with 4 cloud computer nodes.

The complicated dielectric profile under advanced process technologies challenges the accuracy of floating random walk (FRW) based capacitance extraction, as the latter pre-computes the surface Green's functions for a finite set of multi-dielectric transition cubes and makes approximations of transition cubes during the FRW process. In this work, we derive analytic surface Green's functions for transition cubes with arbitrary stratified dielectrics and propose a fast algorithm named AGF to compute them. A capacitance solver named FRW-AGF is then proposed to incorporate AGF into the FRW process to accurately model realistic transition cubes. Experimental results show that the proposed AGF is over 100× faster than the state-of-the-art, and FRW-AGF largely improves the accuracy of RWCap4 [3, 16] (making all errors to golden values below 5%) without degrading computational speed and parallel scalability.

Efficient power grid analysis is critical in modern VLSI design. It is computationally challenging because it requires solving large linear equations with millions of unknowns. Iterative solvers are more scalable, but their performance relies on preconditioners. Existing preconditioning approaches suffer from either high construction cost or slow convergence rate, both resulting in unsatisfactory total solution time. In this work, we propose an efficient power grid simulator based on fast randomized Cholesky factorization, named PowerRChol. We first propose a randomized Cholesky factorization algorithm with provable linear-time complexity. Then we propose a randomized factorization oriented matrix reordering approach. Experimental results on large-scale power grids demonstrate the superior efficiency of PowerRChol over existing iterative solvers, showing 1.51X, 1.93X and 3.64X speedups on average over the original RChol [3], feGRASS [11] and AMG [14] based PCG solvers, respectively. For instance, a power grid matrix with 60 million nodes and 260 million nonzeros can be solved (at a 1E-6 accuracy level) in 148 seconds on a single CPU core.

More accurate capacitance extraction is demanded for IC design nowadays. The pattern matching approach and the field solver for capacitance extraction have the drawbacks of in-accuracy and large computational cost, respectively. Recent work [1] proposes a grid-based data representation and a convolutional neural network based capacitance models (called CNN -Cap) for 3- D capacitance extraction. In this work, the techniques of neural architecture search (NAS) is proposed to train better models for 3- D capacitance extraction. Experimental results show that the obtained NAS-Cap model achieves higher accuracy than [1].

To achieve higher system energy efficiency, SRAM in SoCs is often customized. The parasitic effects cause notable discrepancies between pre-layout and post-layout circuit simulations, leading to difficulty in converging design parameters and excessive design iterations. Is it possible to well predict the parasitics based on the pre-layout circuit, so as to perform parasitic-aware pre-layout simulation? In this work, we propose a deep-learning-based 2-stage model to accurately predict these parasitics in pre-layout stages. The model combines a Graph Neural Network (GNN) classifier and Multi-Layer Perceptron (MLP) regressors, effectively managing class imbalance of the net parasitics in SRAM circuits. We also employ Focal Loss to mitigate the impact of abundant internal net samples and integrate subcircuit information into the graph to abstract the hierarchical structure of schematics. Experiments on 4 real SRAM designs show that our approach not only surpasses the state-of-the-art model in parasitic prediction by a maximum of 19X reduction of error but also significantly boosts the simulation process by up to 598X speedup.

Logic verification becomes more and more important for the design of large-scale digital integrated circuits (ICs). This makes FPGA-based hardware emulation an imperative step in the design flow, and how to effectively partition and map the circuit netlist into the multi-FPGA system (MFS) for emulation is of concern. In this paper, we present EasyPart, an effective and comprehensive hypergraph partitioner for the FPGA-based hardware emulation. EasyPart can handle the practical constraints in the MFS for logic emulation and includes novel techniques for pursuing minimum hop during topology-driven partitioning and treating the interconnection constraints. We have evaluated EasyPart against state-of-the-art partitioners on public benchmarks. The results show that EasyPart can reduce the cutsize with a comparable or shorter runtime. EasyPart is capable of finding non-hop solutions with better robustness and performance compared to previous work. It also achieves significant improvements in terms of time division multiplexing (TDM) ratio and maximum hop when tested on industrial cases.

A key factor affecting the computational time of floating random walk (FRW) based capacitance extraction is the variance of underlying Monte Carlo (MC) sample of capacitance. For achieving a fixed accuracy of result, the number of walks executed is proportional to the variance of this underlying random variable. In this work, we study the way to reduce the variance of random variable in FRW method through some theoretical analysis. An FRW method with symmetric multiple-shooting (SMS) walks is proposed, which stems out Ns symmetric sub-walk paths from a same sample point on Gaussian surface (with Ns being 2, 4, 8 or 16). Theoretical analysis reveals that the method with SMS walks could reduce the number of walks compared to the FRW method with important sampling (IS) approach under some assumption, and thus runs faster even considering the increase of hops within a walk. Its benefits also include the reduction of sampling points on Gaussian surface, which shows large benefit when the sampling on a complex Gaussian surface is very costly. Numerical experiments on the parallel-plate structure have validated the correctness of the theoretical analysis on the variances. With test cases from IC and FPD design, the proposed method with SMS walks is compared with the method with IS approach and the method with both IS and stratified sampling (SS) approach. The results show that the proposed method with SMS walks runs in similar speed or much faster than the FRW method using the IS+SS scheme, with up to 10.1× speedup.

Transient simulation of large power grids (PGs) can be extremely challenging because linear equation systems with millions of unknowns need to be solved at each time step. The iterative equation solvers can be more scalable and efficient than direct solvers, thanks to the preconditioning approaches. Recently, randomized Cholesky factorization (RChol) was proposed, showing promising performance in preconditioning symmetric diagonally dominant M-matrices (SDDMs). However, it does not allow to include more fill-ins, making it less flexible and less efficient in problems like PG transient simulation. In this work, a randomized Cholesky factorization with a threshold based multisampling strategy (RCholT) is proposed. RCholT allows to control the sparsity of preconditioners by a user-defined threshold and can construct more effective preconditioners than RChol. As the result, the RCholT based transient simulator is 1.7X faster than the RChol based one and 2.3X faster than the graph sparsification based one on SDDM and PG benchmarks.

Ordered escape routing (OER), which means that the pins need to be routed to the boundary of a pin array in a given order, is an important research topic in PCB design. Although OER has been widely investigated, most works assume that the routing capacity between two adjacent pins is just 1 and the structure of the pin array is a grid pin array. In this article, we focus on multi-capacity ordered escape routing (MC-OER) both in grid pin arrays and staggered pin arrays, which means that multiple wires are allowed to pass through between two adjacent pins. We first propose a multi-capacity multi-commodity flow (MC-MCF) model for the MC-OER problem. To accelerate the routing process, MCMCF-Router is proposed. In MCMCF-Router, a wiring resources driven partition strategy is proposed to reduce the problem size, followed by the approach based on routing conflicts. These approaches largely accelerate the MC-MCF model based method and increase the routability with minimal sacrifice on wire length. Experiments on various cases (with up to 525 pins) show that the proposed method achieves 100% routability within reasonable time (<810 seconds). Compared to the state-of-the-art works for single-capacity OER problems, MCMCF-Router performs similarly well or better.

Aiming to provide a faster and convenient truncated SVD algorithm for large sparse matrices from real applications (i.e., for computing a few of the largest singular values and the corresponding singular vectors), a dynamically shifted power iteration technique is applied to improve the accuracy of the randomized SVD method. This results in a d yn a mic sh ifts-based randomized SVD (dashSVD) algorithm, which also collaborates with the skills for handling sparse matrices. An accuracy-control mechanism is included in the dashSVD algorithm to approximately monitor the per vector error bound of computed singular vectors with negligible overhead. Experiments on real-world data validate that the dashSVD algorithm largely improves the accuracy of a randomized SVD algorithm or attains the same accuracy with fewer passes over the matrix, and provides an efficient accuracy-control mechanism to the randomized SVD computation, while demonstrating the advantages on runtime and parallel efficiency. A bound of the approximation error of the randomized SVD with the shifted power iteration is also proved.

Floating metals are special conductors introduced into conductor structures by design for manufacturing (DFM). They bring difficulty to accurate capacitance simulation. In this work, we aim to accelerate the floating random walk (FRW) based capacitance simulation for structures with considerable amounts of general floating metals. We first discuss how the existing modified FRW is affected by the integral surfaces of floating metals and propose an improved placement of integral surface. Then, we propose a hybrid approach called incomplete network reduction to avoid random transitions trapped by floating metals. Experiments on structures from IC and FPD design, which involves multiple floating metals and single or multiple master conductors, have shown the effectiveness of the proposed techniques. The proposed techniques reduce the computational time of capacitance calculation, while preserving the accuracy.

A series of fixed-structure sparse linear equations are solved in a circuit simulation process. We propose a parallel incomplete LU (ILU) preconditioned GMRES solver for those equations. A new subtree-based scheduling algorithm for ILU factorization and forward/backward substitution is adopted to overcome the load-balancing and data locality problem of the conventional levelization-based scheduling. Experimental results show that the proposed scheduling algorithm can achieve up to 2.6X speedup for ILU factorization and 3.1X speedup for forward/backward substitution compared to the levelization-based scheduling. The proposed ILU-GMRES solver achieves around 4X parallel speedup with 8 threads, which is up to 2.1X faster than that based on the levelization-based scheme. The proposed parallel solver also shows remarkable advantage over existing methods (including HSPICE) on transient simulation of linear and nonlinear circuits.

Effective resistance, which originates from the field of circuits analysis, is an important graph distance in spectral graph theory. It has found numerous applications in various areas, such as graph data mining, spectral graph sparsification, circuits simulation, etc. However, computing effective resistances accurately can be intractable and we still lack efficient methods for estimating effective resistances on large graphs. In this work, we propose an efficient algorithm to compute effective resistances on general weighted graphs, based on a sparse approximate inverse technique. Compared with a recent competitor, the proposed algorithm shows several hundreds of speedups and also one to two orders of magnitude improvement in the accuracy of results. Incorporating the proposed algorithm with the graph sparsification based power grid (PG) reduction framework, we develop a fast PG reduction method, which achieves an average 6.4X speedup in the reduction time without loss of reduction accuracy. In the applications of power grid transient analysis and DC incremental analysis, the proposed method enables 1.7X and 2.5X speedup of overall time compared to using the PG reduction based on accurate effective resistances, without increase in the error of solution.

Efficient and lossless digital waveform compression is essentially important for large-scale IC design. In this paper, a compression and storage scheme with detailed-encoding is proposed for compressing the digital waveform including signal transition and auxiliary information. The proposed scheme encodes different values according to their detailed characteristics and utilizes a modified look-up table to reduce the memory cost for storing signal aliases. It is also integrated into a block-by-block compressing procedure which facilitates the secondary lossless compression, pipeline computation and variable-length coding techniques for fast conversion from the output of simulator to the compressed file. Experiments are carried out with 8 digital waveform files from industrial cases. The results show that the proposed method enables 402X average (and up to 1561X) compression ratio with respect to the original VCD format. Compared to the existing compression method for digital waveform, it costs similar or less time while achieving up to 2.56X more compression with about 20% reduction of memory usage averagely.

Efficient and accurate waveform compression is critical for analog circuit simulation. In this work, we propose a waveform compression scheme which supports asynchronous waveforms, while improving the compression ratio (CR) and reducing memory usage based on the techniques of multi-model prediction, residual quantization and random-accessible secondary compression. Experimental results show that the proposed method can achieve up to 7.90X and 35.29X CR for industrial synchronous waveforms and asynchronous waveforms respectively, while keeping absolute error within 10-6 and relative error within 10-3. In comparison with existing work that only supports synchronous waveforms, the CR is improved by 1.23X and the memory usage is reduced by 8.4X on average.

Analyzing large power grids directly is computationally expensive. To tackle this issue, various power grid reduction methods, which aim to reduce original power grid to a smaller one while preserving voltage responses at port nodes as much as possible, have been proposed. In the past decade, node elimination based methods incorporated with graph sparsification have shown good performance in the reduction of modern large-scale power grids. The resulting sparsified reduced power grids enable more efficient transient analysis than simulating original power grids directly, with tolerable simulation accuracy. However, due to the large number of ports, the efficiency gained from these elimination-plus-sparsification methods can be still limited. In this work, we propose an effective node aggregation scheme to further reduce the sparsified reduced grids generated by elimination-plus-sparsification methods without increasing simulation errors. We first propose an accuracy-aware multilevel node aggregation framework with an effective scheme to determine aggregation levels automatically, which ensures simulation accuracy does not deteriorate. Then, an aggregation error induced spectral node similarity metric is proposed based on rigorous proof. Experimental results show that the proposed method can reduce the sparsified reduced grids to much smaller sizes with simulation accuracy even improved. It enables a further 3.0X speedup of transient simulation on average. Compared with the transient analysis of original power grids, the proposed method achieves an average 12.4X speedup with average voltage error below 1 mV and maximum error below 6 mV for all test cases with 1.8 V supply voltage. Finally, we demonstrate the advantages of the proposed method over other power grid reduction methods [1], [2] in terms of accuracy, model size and time for reduction.

With the rapid development of electronic payment, risks in large-scale financial transaction networks are persistently arising. One important problem is how to use the transaction data to detect sellers who do fraudulent trades on the online platform. This paper analyzes three attributes of the transaction flow: money (what), time (when), region (where), and summarizes corresponding characteristics among fraudulent sellers. Based on this, we propose an unsupervised anomaly detection algorithm: W3Detector. It processes the raw data with a new sequence discretization method and uses statistical tools to convert data indicators into information value. With the minimum description length principle, we finally filter out the suspicious sellers. The algorithm is not affected by factors such as unit or range of the attributes, and is highly flexible and scalable. After running on three real-world transaction datasets collected from WeChat Pay, W3Detector has show significantly better performance than the baseline methods of anomaly detection, with weighted accuraccy (WACC) increased by 1.13X and F-score increased by 0.105 on average, and the recall value over 60%.

Deep neural networks (DNNs) are vulnerable to adversarial examples. And, the adversarial examples have transferability, which means that an adversarial example for a DNN model can fool another model with a non-trivial probability. This gave birth to the transfer-based attack where the adversarial examples generated by a ate model are used to conduct blackbox attacks. There are some work on generating the adversarial examples from a given surrogate model with better transferability. However, training a special surrogate model to generate adversarial examples with better transferability is relatively under-explored. This paper proposes a method for training a surrogate model with dark knowledge to boost the transferability of the adversarial examples generated by the surrogate model. This trained surrogate model is named dark surrogate model (DSM). The proposed method for training a DSM consists of two key components: a teacher model extracting dark knowledge, and the mixing augmentation skill enhancing dark knowledge of training data. We conducted extensive experiments to show that the proposed method can substantially improve the adversarial transferability of surrogate models across different architectures of surrogate models and optimizers for generating adversarial examples, and it can be applied to other scenarios of transfer-based attack that contain dark knowledge, like face verification. Our code is publicly available at https://github.com/ydc123/DarkSurrogate-Model.

It is desirable to adaptively determine the number of dimensions (rank) for PCA according to a given tolerance of low-rank approximation error. In this work, we aim to develop a fast algorithm solving this adaptive PCA problem. We propose to replace the QR factorization in randQB_EI algorithm with matrix multiplication and inversion of small matrices, and propose a new error indicator to incrementally evaluate approximation error in Frobenius norm. Combining the shifted power iteration technique for better accuracy, we finally build up an algorithm named farPCA. Experimental results show that farPCA is much faster than the baseline methods (randQB_EI, randUBV and svds) in practical setting of multi-thread computing, while producing nearly optimal results of adpative PCA.

Deep neural networks (DNNs) have been shown to be vulnerable to adversarial examples. Moreover, the transferability of the adversarial examples has received broad attention in recent years, which means that adversarial examples crafted by a surrogate model can also attack unknown models. This phenomenon gave birth to the transfer-based adversarial attacks, which aim to improve the transferability of the generated adversarial examples. In this paper, we propose to improve the transferability of adversarial examples in the transfer-based attack via masking unimportant parameters (MUP). The key idea in MUP is to refine the pretrained surrogate models to boost the transfer-based attack. Based on this idea, a Taylor expansion-based metric is used to evaluate the parameter importance score and the unimportant parameters are masked during the generation of adversarial examples. This process is simple, yet can be naturally combined with various existing gradient-based optimizers for generating adversarial examples, thus further improving the transferability of the generated adversarial examples. Extensive experiments are conducted to validate the effectiveness of the proposed MUP-based methods.

With the increase in the complexity of VLSI chips, power grid analysis has become a challenging task, because linear equations of extremely large size need to be solved. Recent graph sparsification-based solvers have shown promising performance for power grid analysis. However, existing graph sparsification algorithms are implemented in serial computing, while factorization and backward/forward substitution of the sparsifier’s Laplacian matrix are hard to parallelize. On the other hand, partition-based iterative methods which are inherently parallel lack a direct control of the relative condition number of the preconditioner and consume more memory. In this work, we propose a novel parallel iterative solver called pGRASS-Solver. We first propose a practically efficient parallel graph sparsification algorithm. Then, the domain decomposition method (DDM) is utilized to solve the sparsifier’s Laplacian matrix. To further improve the efficiency, a variant of DDM which employs partial Cholesky factorization and Schur complement matrix sparsification is proposed. Thus, we obtain an efficient parallel preconditioner, which not only leads to fast convergence but also enjoys ease of parallelization. Numerous experiments are conducted to illustrate the superior efficiency of the proposed pGRASS-Solver for large-scale power grid analysis, showing an average$6.8\times $speedup over a recent parallel iterative solver (Wang et al. 2017). Moreover, it solves a real-world power grid matrix with 0.36 billion nodes and 8.7 billion nonzeros within 20 min on a 16-core machine, which is$10.9\times $faster than the best result of sequential graph sparsification-based solver (Liu et al. 2022).

We study large-scale network embedding with the goal of generating high-quality embeddings for networks with more than 1 billion vertices and 100 billion edges. Recent attempts LightNE and NetSMF propose to sparsify and factorize the (dense) NetMF matrix for embedding large networks, where NetMF is a theoretically-grounded network embedding method. However, there is a trade-off between their embeddings’ quality and scalability due to their expensive memory requirements, making embeddings less effective under real-world memory constraints. Therefore, we present the SketchNE model, a scalable, effective, and memory-efficient network embedding solution developed for a single machine with CPU only. The main idea of SketchNE is to avoid the explicit construction and factorization of the NetMF matrix either sparsely or densely when producing the embeddings through the proposed sparse-sign randomized single-pass SVD algorithm. We conduct extensive experiments on nine datasets of various sizes for vertex classification and link prediction, demonstrating the consistent outperformance of SketchNE over state-of-the-art baselines in terms of both effectiveness and efficiency. SketchNE costs only1.0 hoursto embed the Hyperlink2012 network with3.5 billionvertices and225 billionedges on a CPU-only single machine with embedding superiority (e.g., a282%relative HITS@10 gain over LightNE).

We proposeLightNE 2.0, a cost-effective, scalable, automated, and high-quality network embedding system that scales to graphs with hundreds of billions of edges on a single machine. In contrast to the mainstream belief that distributed architecture and GPUs are needed for large-scale network embedding with good quality, we prove that we can achieve higher quality, better scalability, lower cost, and faster runtime with shared-memory, CPU-only architecture.LightNE 2.0combines two theoretically grounded embedding methods NetSMF and ProNE. We introduce the following techniques to network embedding for the first time: (1) a newly proposed downsampling method to reduce the sample complexity of NetSMF while preserving its theoretical advantages; (2) a high-performance parallel graph processing stack GBBS to achieve high memory efficiency and scalability; (3) sparse parallel hash table to aggregate and maintain the matrix sparsifier in memory; (4) a fast randomized singular value decomposition (SVD) enhanced by power iteration and fast orthonormalization to improve vanilla randomized SVD in terms of both efficiency and effectiveness; (5) Intel MKL for proposed fast randomized SVD and spectral propagation; and (6) a fast and lightweight AutoML library FLAML for automated hyperparameter tuning. Experimental results show thatLightNE 2.0can be up to 84× faster than GraphVite, 30× faster than PBG and 9× faster than NetSMF while delivering better performance.LightNE 2.0can embed very large graph with 1.7 billion nodes and 124 billion edges in half an hour on a CPU server, while other baselines cannot handle very large graphs of this scale.

Designing high-performance adders and multiplier components for diverse specifications and constraints is of practical concern. However, selecting the best architecture for adder or multiplier, which largely affects the performance of synthesized circuits, is difficult. To tackle this difficulty, a machine-learning-driven approach is proposed for automatic architectural selection of adders and multipliers. It trains a machine learning model for classification through learning a number of existing design schemes and their performance data. Experimental results show that the proposed approach based on a multi-perception neural network achieves as high as 94% prediction accuracy with negligible inference time. On a CPU server, the proposed approach runs about 4× faster than a brute-force approach trying four candidate architectures and consumes 10%~20% less runtime than the DesignWare datapath generator for obtaining the optimal adder/multiplier circuit. The adder (multiplier) generated with the proposed approach achieves performance metrics close to the optimal and has 1.6% (5.2%) less area and 2.2% (7.1%) more worst negative slack averagely than that generated with the DesignWare datapath generator. Our experiment also shows that the proposed approach is not sensitive to the size of training subset.

Accurate capacitance extraction is becoming more important for designing integrated circuits under advanced process technology. The pattern matching-based full-chip extraction methodology delivers fast computational speed but suffers from large error and tedious efforts on building capacitance models of the increasing structure patterns. In this work, we propose an effective method for building convolutional neural network (CNN)-based capacitance models (called CNN-Cap) for two-dimensional (2-D) and three -dimensional (3-D) interconnect structures. With a novel grid-based data representation, the proposed method is able to model 2-D pattern structure and 3-D window structure with a variable number of conductors to largely reduce the number of patterns or increase the accuracy. Based on the ability of ResNet architecture on capturing spatial information and the proposed training skills, the obtained CNN-Cap exhibits much better performance over the multilayer perception neural network-based capacitance model while being more versatile. Extensive experiments on a 55 nm and a 15 nm process technologies have demonstrated that the error of total capacitance produced with 2-D CNN-Cap is always within 1.3%, and the error of produced coupling capacitance is less than 10% in over 99.5% probability. For 3-D structures, CNN-Cap predicts the total capacitance with less than 5% error in 99% probability and with a maximum error of 7.7%. For the tested 2-D and 3-D structures, the CNN-Cap run on a GPU server is more than 4,000× and 12,000×, respectively, faster than the conventional field solver Raphael, while consuming negligible memory.

Spectral graph sparsification aims to find ultra-sparse subgraphs which can preserve spectral properties of original graphs. In this paper, a new spectral criticality metric based on trace reduction is first introduced for identifying spectrally important off-subgraph edges. Then, a physics-inspired truncation strategy and an approach using approximate inverse of Cholesky factor are proposed to compute the approximate trace reduction efficiently. Combining them with the iterative densification scheme in [8] and the strategy of excluding spectrally similar off-subgraph edges in [13], we develop a highly effective graph sparsification algorithm. The proposed method has been validated with various kinds of graphs. Experimental results show that it always produces sparsifiers with remarkably better quality than the state-of-the-art GRASS [8] in same computational cost, enabling more than 40% time reduction for preconditioned iterative equation solver on average. In the applications of power grid transient analysis and spectral graph partitioning, the derived iterative solver shows 3.3X or more advantages on runtime and memory cost, over the approach based on direct sparse solver.

The element-wise functions of a matrix are widely used in machine learning. For the applications with large matrices, efficiently computing the matrix-vector multiplication of matrix element-wise function without explicitly constructed matrix is very desired. In this work, we aim to develop an efficient low-rank approximation of the element-wise function of matrix with the time/memory cost linear to the matrix dimension. We first propose a sparse-sign streaming randomized SVD (ssrSVD) algorithm based on a streaming singular value decomposition (SVD) algorithm and the sparse-sign random projection for the approximation of element-wise function of general asymmetric matrix. For symmetric positive semi-definite (SPSD) matrix, for which the existing Nyström [1] and FastSPSD [2] method do not perform well if the matrix's singular value decays slowly, we propose a theoretically proved shift skill to improve the approximation accuracy. Combining with the ssrSVD, we obtain the sparse-sign streaming SPSD matrix approximation with shift (S3SPSD) algorithm. Experiments are carried out to evaluate the proposed algorithms' performance in approximating element-wise functions of matrix. With the color transfer task based on the Sinkhorn algorithm, the ssrSVD algorithm largely reduces the approximation error (up to$10^{5}\times$) compared with the state-of-the-art baselines, and results in high-quality color transfer result. For the kernel matrix approximation, the proposed S3SPSD algorithm also consistently outperforms the state-of-the-art baselines. Experimental results finally validate the linear time complexity of the proposed algorithms.

Graph spectral sparsification aims to find a ultrasparse subgraph which can preserve the spectral properties of the original graph. The subgraph can be leveraged to construct a preconditioner to speed up the solution of the original graph’s Laplacian matrix. In this work, we propose feGRASS, a fast and effective graph spectral sparsification approach for the problem of large-scale power grid analysis and other problems with similar graphs. The proposed approach is based on two novel concepts: 1) effective edge weight and 2) spectral edge similarity. The former takes advantage of node degrees and breadth-first-search (BFS) distances, which leads to a scalable algorithm for generating low-stretch spanning trees (LSSTs). Then, the latter concept is leveraged during the recovery of spectrally critical off-tree edges to produce spectrally similar subgraphs. Compared with the most recent competitor[1], the proposed approach is much faster for producing high-quality spectral sparsifiers. Extensive experimental results have been demonstrated to illustrate the superior efficiency of a preconditioned conjugate gradient (PCG) algorithm based on the proposed approach, for solving large power grid problems and many other real-world graph Laplacians. For instance, a power grid matrix with 60 million unknowns and 260 million nonzeros can be solved (at a 1E-3 accuracy level) within 196 s and 12 PCG iterations, on a single CPU core.

Precharacterizing the transition cubes containing stratified dielectrics is inevitable for the floating random walk (FRW)-based capacitance extraction. Each multilayer-dielectric transition cube is characterized by a pair of Green’s function table (GFT) and weight value table (WVT), and all these GFTs and WVTs usually have large volume and constitute the major memory cost of the FRW algorithm. In this work, we explore the geometric symmetry of the multilayer-dielectric transition cube to enable volume reduction and fast generation of the GFT and WVT. For a general transition cube with stratified dielectrics and the one with four equal-thickness dielectrics, two schemes are proposed to reduce the volume of GFT and WVT by$8\times $and over$10\times $, respectively. Accordingly, an approach for fast generation of the reduced GFT/WVT is proposed, which is proved to produce the same result as the original GFT/WVT values. And, an improved FRW algorithm is proposed to utilize the reduced GFTs/WVTs without the sacrifice of runtime or accuracy. Both theoretical analysis and numerical experiments are conducted to demonstrate the remarkable volume reduction of precharacterization data (GFTs/WVTs). The fast GFT/WVT generation approach and the improved FRW algorithm are also validated with numerical experiments, showing over$10\times $speedup of the precharacterization process, and accurate and memory-efficient capacitance extraction as well.

How can we track synchronized behavior in a stream of time-stamped tuples, such as mobile devices installing and uninstalling applications in the lockstep, to boost their ranks in the app store? We model such tuples as entries in a streaming tensor, which augments attribute sizes in its modes over time. Synchronized behavior tends to form dense blocks (i.e.~subtensors) in such a tensor, signaling anomalous behavior, or interesting communities. However, existing dense block detection methods are either based on a static tensor, or lack an efficient algorithm in a streaming setting. Therefore, we propose a fast streaming algorithm, AUGSPLICING, which can detect the top dense blocks by incrementally splicing the previous detection with the incoming ones in new tuples, avoiding re-runs over all the history data at every tracking time step. AUGSPLICING is based on a splicing condition that guides the algorithm (Section 4). Compared to the state-of-the-art methods, our method is (1) effective to detect fraudulent behavior in installing data of real-world apps and find a synchronized group of students with interesting features in campus Wi-Fi data; (2) robust with splicing theory for dense block detection; (3) streaming and faster than the existing streaming algorithm, with closely comparable accuracy.

In this work, we present effective quantization approaches for compressing the deep neural networks (DNNs). A key ingredient is a novel dynamic programming (DP) based algorithm to obtain the optimal solution of scalar K-means clustering. Based on the approaches with regularization and quantization function, two weight quantization approaches called DPR and DPQ for compressing normal DNNs are proposed respectively. Experiments show that they produce models with higher inference accuracy than recently proposed counterparts while achieving same or larger compression. They are also extended for compressing robust DNNs, and the relevant experiments show 16X compression of the robust ResNet-18 model with less than 3% accuracy drop on both natural and adversarial examples.

As the feature size scales down, the process technology becomes more complicated and the design margin shrinks, accurate parasitic extraction during IC design is largely demanded. In this invited paper, we survey the recent advancements on parasitic extraction techniques, especially those enhancing the floating random walk based capacitance solver and incorporating machine learning methods. The work dealing with process variation are also addressed. After that, we briefly discuss the challenges for capacitance extraction under advanced process technologies, including manufacture-aware geometry variations and middle-end-of-line (MEOL) parasitic extraction, etc.

Due to the rapid advance of the integrated circuit technology, power grid analysis usually imposes a severe computational challenge, where linear equations with millions or even billions of unknowns need to be solved. Recent graph spectral sparsification techniques have shown promising performance in accelerating power grid analysis. However, previous graph sparsification based iterative solvers are restricted by difficulty of parallelization. Existing graph sparsification algorithms are implemented under the assumption of serial computing, while factorization and backward/forward substitution of the spar-sifier's Laplacian matrix are also hard to parallelize. On the other hand, partition based iterative methods which can be easily parallelized lack a direct control of the relative condition number of the preconditioner and consume more memory. In this work, we propose a novel parallel iterative solver for scalable power grid analysis by integrating graph sparsification techniques and partition based methods. We first propose a practically-efficient parallel graph sparsification algorithm. Then, domain decomposition method is leveraged to solve the sparsifier's Laplacian matrix. An efficient graph sparsification based parallel preconditioner is obtained, which not only leads to fast convergence but also enjoys ease of parallelization. Extensive experiments are carried out to demonstrate the superior efficiency of the proposed solver for large-scale power grid analysis, showing 5.2X speedup averagely over the state-of-the-art parallel iterative solver. Moreover, it solves a real-world power grid matrix with 0.36 billion nodes and 8.7 billion nonzeros within 23 minutes on a 16-core machine, which is 9.5X faster than the best result of sequential graph sparsification based solver.

Accurate capacitance extraction is becoming more important for designing integrated circuits under advanced process technology. The pattern matching based full-chip extraction methodology delivers fast computational speed, but suffers from large error, and tedious efforts on building capacitance models of the increasing structure patterns. In this work, we propose an effective method for building convolutional neural network (CNN) based capacitance models (called CNN-Cap) for two-dimensional (2-D) structures in full-chip capacitance extraction. With a novel grid-based data representation, the proposed method is able to model the pattern with a variable number of conductors, so as to largely reduce the number of patterns. Based on the ability of ResNet architecture on capturing spatial information and the proposed training skills, the obtained CNN-Cap exhibits much better performance over the multilayer perception neural network based capacitance model while being more versatile. Extensive experiments on a 55nm and a 15nm process technologies have demonstrated that the error of total capacitance produced with CNN-Cap is always within 1.3% and the error of produced coupling capacitance is less than 10% in over 99.5% probability. CNN-Cap runs more than 4000X faster than 2-D field solver on a GPU server, while it consumes negligible memory compared to the look-up table based capacitance model.

Efficient and accurate waveform compression is essentially important for the application of analog circuit transition simulation nowadays. In this article, an analog waveform compression scheme is proposed which includes two compressed formats for representing small and large signal values, respectively. The compressed formats and the corresponding compression/decompression approaches ensure that both the absolute and relative errors of each signal value restored from the compression are within specified criteria. The formats are integrated in a block-by-block compressing procedure which facilitates a secondary lossless compression and a three-stage pipeline scheme for fast conversion from the simulator's output to the compressed hard-disk file. Theoretical analysis is presented to prove the accuracy-ensured property of our approach. Two schemes are also proposed to incorporate the prediction method. They achieve larger compression ratio for some cases while preserving the accuracy and runtime efficiency. Experiments are carried out with voltage waveforms from industrial circuits. The results validate the accuracy and the efficiency of the proposed techniques. The obtained compression ratio is 2.6X larger than existing work without overhead, even though the latter induces much larger error. Compared with the original double-precision floating number format, the proposed approach achieves the compression ratio of 26 averagely and up to 70, while keeping the relative error less than 10-3and absolute error less than 10-5. And with the pipelined computation, the proposed compression approach hardly increases time cost to the transient simulation.

Electromigration (EM) becomes one of the most challenging reliability issues for current and future ICs in 10-nm technology and below. In this article, a novel method is proposed for the EM hydrostatic stress analysis on 2-D multibranch interconnect trees, which is the foundation of the EM reliability assessment for large-scale on-chip interconnect networks, such as on-chip power grid networks. The proposed method, which is based on an eigenfunction technique, could efficiently calculate the hydrostatic stress evolution for multibranch interconnect trees stressed with different current densities and nonuniformly distributed thermal effects. The proposed method solves the partial differential equations of transient EM stress more efficiently since it does not require any discretization either spatially or temporally, which is in contrast to numerical methods, such as the finite difference method and finite element method. The accuracy of the proposed transient analysis approach is validated against the analytical solution and commercial tools. The convergence of the proposed method is demonstrated by numerical experiments on practical power/ground networks, showing that only a small number of eigenfunction terms are necessary for the accurate solution. Thanks to its analytical nature, the proposed method is also utilized in efficient EM analysis techniques, such as searching for the void nucleation time by a modified bisection algorithm. The numerical results show that the proposed method is 10X-100X faster than the finite difference method and scales better for larger interconnect trees.

Capacitance extraction and power grid (PG) analysis for IC design involve large-scale numerical simulation problems. As the process technology becomes more complicated and design margin is shrinking, the capacitance field solver and power-grid matrix solver with high accuracy and capability for handing large and complex structure are highly demanded. In this invited paper, we present recent application of statistical and AI methods in these two fields. The Markov-chain model and relevant analysis are presented for developing an efficient technique for handling conformal dielectrics in the floating random walk based capacitance extraction. Then, two approaches reducing the computational cost of a domain decomposition based power-grid solver are presented. One employs supervised machine learning while the other is inspired by the A*-search algorithm.

In this paper, two techniques are proposed to enhance the floating random walk (FRW) based capacitance solver for handling non-stratified dielectrics in very large-scale integrated (VLSI) circuits. They follow an existing approach which employs approximate eight-octant transition cubes while simulating the structure with conformal dielectrics. Firstly, the symmetry property of the transition probabilities of the eight-octant cube is revealed and utilized to derive an on-the-fly sampling scheme during the FRW procedure. This avoids the pre-characterization, saves substantial memory, and improves computational accuracy for extracting the structure with non-stratified dielectrics. Then, the space management technique is extended to improve the runtime efficiency for simulating structures with thousands of non-stratified dielectrics. Numerical experiments are carried out to validate the proposed techniques and show their effectiveness for handling structures with conformal dielectrics and air bubbles. Moreover, the extended space management brings up to 1441X speedup for handling structures with from several thousand to nearly one million non-stratified dielectrics.

A model-based collaborative filtering (CF) approach utilizing fast adaptive randomized singular value decomposition (SVD) is proposed for the matrix completion problem in recommender system. Firstly, a fast adaptive PCA framework is presented which combines the fixed-precision randomized matrix factorization algorithm [1] and accelerating skills for handling large sparse data. Then, a novel termination mechanism for the adaptive PCA is proposed to automatically determine a number of latent factors for achieving the near optimal prediction accuracy during the subsequent model-based CF. The resulted CF approach has good accuracy while inheriting high runtime efficiency. Experiments on real data show that, the proposed adaptive PCA is up to 2.7X and 6.7X faster than the original fixed-precision SVD approach [1] and svds in Matlab repsectively, while preserving accuracy. The proposed model-based CF approach is able to efficiently process the MovieLens data with 20M ratings and exhibits more than 10X speedup over the regularized matrix factorization based approach [2] and the fast singular value thresholding approach [3] with comparable or better accuracy. Compared with the deep-learning-based CF approach, the proposed approach is much more computationally efficient, with just marginal performance loss.

The idea of macromodel was recently proposed for encrypting sensitive structures and accelerating the floating random walk (FRW)-based capacitance extraction. In the existing work, boundary element method (BEM) is employed to generate the macromodel, which might cause large error due to the violation of macromodel's properties. To overcome this issue, we propose a modified finite difference method (FDM) with second-order electric field intensity formulas for generating the macromodel. It ensures the macromodel's properties and thus largely improves the reliability of the macromodel-aware FRW algorithm. The numerical experiments with 3-D structures have validated our theoretic analysis, and have shown the proposed technique reliably brings more accurate capacitance results than the BEM and conventional FDM.

A novel technique is proposed to deal with conformal dielectrics for extracting capacitances with floating random walk (FRW) method. It is based on the observation that the transition probabilities for the eight-octant cube exhibit a kind of symmetry and are closely related to those of a single-dielectric transition cube. We first theoretically proved this observation, and then proposed an approach generating the transition probabilities without any precalculation and memory cost. This enables on-the-fly sampling on eight-octant transition cubes and derives an improved FRW algorithm for capacitance extraction with conformal dielectrics. Compared with the existing approach, the proposed improved algorithm saves substantial memory cost and is more accurate. The numerical results have validated the theoretic analysis and demonstrated the benefits of the proposed capacitance solver for handling conformal dielectrics.

We propose a new tensor completion method based on tensor trains. The to-be-completed tensor is modeled as a low-rank tensor train, where we use the known tensor entries and their coordinates to update the tensor train. A novel tensor train initialization procedure is proposed specifically for image and video completion, which is demonstrated to ensure fast convergence of the completion algorithm. The tensor train framework is also shown to easily accommodate Total Variation and Tikhonov regularization due to their low-rank tensor train representations. Image and video inpainting experiments verify the superiority of the proposed scheme in terms of both speed and scalability, where a speedup of up to 155× is observed compared to state-of-the-art tensor completion methods at a similar accuracy. Moreover, we demonstrate the proposed scheme is especially advantageous over existing algorithms when only tiny portions (say, 1%) of the to-be-completed images/videos are known.

A machine-learning-driven approach for matrix ordering is proposed for power grid analysis based on domain decomposition. It utilizes support vector machine or artificial neural network to learn a classifier to automatically choose the optimal ordering algorithm, thereby reducing the expense of solving the subdomain equations. Based on the feature selection considering sparse matrix properties, the proposed method achieves superior efficiency in runtime and memory usage over conventional methods, as demonstrated by industrial test cases.

Capacitance extraction or simulation has become a challenging problem in the computer-aided design of integrated circuits (ICs), flat panel display, etc. Due to its scalability and reliability, the parallel floating random walk (FRW) based capacitance solver is widely used. In practice, the parallel FRW algorithms involve an issue of reproducibility and may consume a lot of time in the scenario requesting high accuracy. To relieve these issues, techniques are developed in this paper to enhance the reproducibility and reusability of the parallel FRW based simulation. With them we ensure that same result is reproduced while rerunning the parallel FRW solver with same setting. A "jump start" feature is also implemented to reduce the total runtime of simulating same structure with multiple accuracy criteria. Experiments on shared-memory and distributed-memory platforms have validated the effectiveness of the presented techniques. Compared with a synchronization based approach ensuring the reproducibility, the proposed technique with static workload allocation can brings 4.8X more parallel speedup while sacrificing nothing.

How can one quickly answer the most and top popular objects at any time, given a large log stream in a system of billions of users? It is equivalent to find the mode and top-frequent elements in a dynamic array corresponding to the log stream. However, most existing work either restrain the dynamic array within a sliding window, or do not take advantages of only one element can be added or removed in a log stream. Therefore, we propose a profiling algorithm, named S-Profile, which is of $O(1)$ time complexity for every updating of the dynamic array, and optimal in terms of computational complexity. With the profiling results, answering the queries on the statistics of dynamic array becomes trivial and fast. With the experiments of various settings of dynamic arrays, our accurate S-Profile algorithm outperforms the well-known methods, showing at least 2X speedup to the heap based approach and 13X or larger speedup to the balanced tree based approach.

Deep neural networks (DNNs) have achieved significant success in a variety of real world applications, i.e., image classification. However, tons of parameters in the networks restrict the efficiency of neural networks due to the large model size and the intensive computation. To address this issue, various approximation techniques have been investigated, which seek for a light weighted network with little performance degradation in exchange of smaller model size or faster inference. Both low-rankness and sparsity are appealing properties for the network approximation. In this paper we propose a unified framework to compress the convolutional neural networks (CNNs) by combining these two properties, while taking the nonlinear activation into consideration. Each layer in the network is approximated by the sum of a structured sparse component and a low-rank component, which is formulated as an optimization problem. Then, an extended version of alternating direction method of multipliers (ADMM) with guaranteed convergence is presented to solve the relaxed optimization problem. Experiments are carried out on VGG-16, AlexNet and GoogLeNet with large image classification datasets. The results outperform previous work in terms of accuracy degradation, compression rate and speedup ratio. The proposed method is able to remarkably compress the model (with up to 4.9X reduction of parameters) at a cost of little loss or without loss on accuracy.

Principal component analysis (PCA) is widely used for dimension reduction and embedding of real data in social network analysis, information retrieval, and natural language processing, etc. In this work we propose a fast randomized PCA algorithm for processing large sparse data. The algorithm has similar accuracy to the basic randomized SVD (rPCA) algorithm (Halko et al., 2011), but is largely optimized for sparse data. It also has good flexibility to trade off runtime against accuracy for practical usage. Experiments on real data show that the proposed algorithm is up to 9.1X faster than the basic rPCA algorithm without accuracy loss, and is up to 20X faster than the \texttt{svds} in Matlab with little error. The algorithm computes the first 100 principal components of a large information retrieval data with 12,869,521 persons and 323,899 keywords in less than 400 seconds on a 24-core machine, while all conventional methods fail due to the out-of-memory issue.

Due to the advantages on scalability and reliability, the floating random walk (FRW) algorithm has been widely adopted for calculating the capacitances among three-dimensional (3-D) conductors. This is evidenced by the industrial practice of interconnect capacitance extraction during the design of high-performance very large-scale integrated (VLSI) circuits. In this work, the FRW algorithm is enhanced through the distributed parallel computing. With an efficient and adaptive task allocation scheme, the communication among different computer nodes is largely reduced. A distributed algorithm for accelerating the space management is also proposed. They have been implemented with Message Passing Interface (MPI) and applied to the high-precision capacitance simulation for touchscreen design and the interconnect capacitance extraction of VLSI circuits. Experiments on a computer cluster show that the proposed techniques achieve up to 114X speedup while using 120 cores, and build up the space management structure for a VLSI case including two million conductor blocks in just 22 seconds (37X parallel speedup on 60 cores).

Matrix completion is a widely used technique for image inpainting and personalized recommender system, etc. In this work, we focus on accelerating the matrix completion using faster randomized singular value decomposition (rSVD). Firstly, two fast randomized algorithms (rSVD-PI and rSVDBKI) are proposed for handling sparse matrix. They make use of an eigSVD procedure and several accelerating skills. Then, with the rSVD-BKI algorithm and a new subspace recycling technique, we accelerate the singular value thresholding (SVT) method in [1] to realize faster matrix completion. Experiments show that the proposed rSVD algorithms can be 6× faster than the basic rSVD algorithm [2] while keeping same accuracy. For image inpainting and movie-rating estimation problems (including up to 2 × 107ratings), the proposed accelerated SVT algorithm consumes 15× and 8× less CPU time than the methods using svds and lansvd respectively, without loss of accuracy.

Long Short-Term Memory (LSTM) network and Gated Recurrent Units (GRU) network are two widely-used gated Recurrent Neural Network (RNN) architectures. Both of them usually have a huge model size and require a long time to be trained. In this paper, we first propose a singular value decomposition (SVD) based approach for fast training of LSTM. Then, the factorized model and SVD based training approach are proposed for the GRU network, which adaptively choose the rank parameter for the matrix factorization model and reduce the training time and parameters of the gated RNNs. Experiments are carried out on the image classification and sentiment classification tasks using datasets MNIST and IMDB, respectively. The results show that the proposed LSTM-SVD approach achieves up to 3.9X speedup compared with training the original LSTM model, without loss of accuracy. The approaches for training the GRU network also have about 2X speedup. And, with the factorized models the quantity of RNN cell parameters can be significantly reduced by more than 10X.

Accurate capacitance calculation for structures including floating metals is of great interest to both the modeling of interconnect wires and the verification of on-chip capacitors in the design of integrated circuit. The former problem involves regular-shape or cuboid floating dummy fills, and has been addressed with an existing fast algorithm based on floating random walk (FRW) method. The latter problem involves floating metals in more general and complex shape, and is crucial for the design of high-density metal-insulator-metal (MIM) capacitor which endures higher voltage. How to efficiently handle these general-shape floating metals becomes a challenge. In this paper, we first investigate the mechanism of the existing FRW-based approach for handling floating dummies, and then propose an approach based on the central difference formula for handling the general-shape floating metals. The proposed approach has comparable cost to the existing work, but is much more reliable and accurate. Experiments on the structures with floating dummies and MIM capacitor structures have validated the effectiveness and advantage of the proposed approach.

Principal component analysis (PCA) is a fundamental dimension reduction tool in statistics and machine learning. For large and high-dimensional data, computing the PCA (i.e., the top singular vectors of the data matrix) becomes a challenging task. In this work, a single-pass randomized algorithm is proposed to compute PCA with only one pass over the data. It is suitable for processing extremely large and high-dimensional data stored in slow memory (hard disk) or the data generated in a streaming fashion. Experiments with synthetic and real data validate the algorithm's accuracy, which has orders of magnitude smaller error than an existing single-pass algorithm. For a set of high-dimensional data stored as a 150 GB file, the algorithm is able to compute the first 50 principal components in just 24 minutes on a typical 24-core computer, with less than 1 GB memory cost.

In this paper, two techniques based on Q -learning and action dependent heuristic dynamic programming (ADHDP) are demonstrated for the demand-side management of domestic electric water heaters (DEWHs). The problem is modeled as a dynamic programming problem, with the state space defined by the temperature of output water, the instantaneous hot water consumption rate, and the estimated grid load. According to simulation, Q-learning and ADHDP reduce the cost of energy consumed by DEWHs by approximately 26% and 21%, respectively. The simulation results also indicate that these techniques will minimize the energy consumed during load peak periods. As a result, the customers saved about $466 and $367 annually by using Q-learning and ADHDP techniques to control their DEWHs (100 gallons tank size) operation, which is better than the cost reduction that resulted from using the state-of-the-art ($246) control technique under the same simulation parameters. To the best of the authors' knowledge, this is the first work that uses the approximate dynamic programming techniques to solve the DEWH's load management problem.

The non-Manhattan conductor geometry existing in some capacitance extraction problems brings difficulty to the floating random walk (FRW) method using cubic transition domains. In this paper, techniques are proposed to enhance the FRW method for handling the structures with non-Manhattan conductors. Based on the aligned-box distances and corresponding calculating approaches, the techniques for generating the Gaussian surface and constructing axis-aligned transition cubes are proposed. A practical strategy is then proposed to judge the domination relationship of non-Manhattan conductor blocks for building the space management structure with candidate list. Finally, the strategy using rotated transition cube and related space management technique are proposed to make further acceleration. Experiments on 3-D interconnect structures including from 8 to 1000 non-Manhattan blocks show that the proposed method is from 2.9× to 96× faster than a simple extension of the original FRW method. The proposed method is also up to 39× faster than a boundary element method-based solver. Additional experiments are carried out to further validate the accuracy and efficiency of the proposed techniques, and to demonstrate their suitability for large and multi-dielectric structures.

In this paper, a random walk based solver is presented which calculates the capacitances for verifying the touchscreen design. To suit the complicated conductor geometries in touchscreen structures, we extend the floating random walk (FRW) method for handling non-Manhattan conductors. A unified dielectric pre-characterization scheme is proposed to suit arbitrary dielectric profiles while keeping high accuracy. The algorithm is finally implemented on a computer cluster, which enables massively parallel computing. Numerical experiments validate the accuracy of proposed techniques and the up to 67X parallel speedup. While comparing with other schemes, the unified dielectric pre-characterization scheme achieves the highest accuracy while costing the least memory usage.

We design an algorithmic framework using matrix exponentials for time-domain simulation of power delivery network (PDN). Our framework can reuse factorized matrices to simulate the large-scale linear PDN system with variable stepsizes. In contrast, current conventional PDN simulation solvers have to use fixed step-size approach in order to reuse factorized matrices generated by the expensive matrix decomposition. Based on the proposed exponential integration framework, we design a PDN solver R-MATEX with the flexible time-stepping capability. The key operation of matrix exponential and vector product is computed by the rational Krylov subspace method. To further improve the runtime, we also propose a distributed computing framework DR-MATEX. DR-MATEX reduces Krylov subspace generations caused by frequent breakpoints from a large number of current sources during simulation. By virtue of the superposition property of linear system and scaling invariance property of Krylov subspace, DR-MATEX can divide the whole simulation task into subtasks based on the alignments of breakpoints among those sources. The subtasks are processed in parallel at different computing nodes without any communication during the computation of transient simulation. The final result is obtained by summing up the partial results among all the computing nodes after they finish the assigned subtasks. Therefore, our computation model belongs to the category known as embarrassingly parallel model. Experimental results show R-MATEX and DR-MATEX can achieve up to around 14.4× and 98.0× runtime speedups over traditional trapezoidal integration-based solver with fixed time-step approach.

We propose an efficient algorithmic framework for time-domain circuit simulation using exponential integrators. This work addresses several critical issues exposed by previous matrix exponential based circuit simulation research, and makes it capable of simulating stiff nonlinear circuit system at a large scale. In this framework, the system's nonlinearity is treated with exponential Rosenbrock-Euler formulation. The matrix exponential and vector product is computed using invert Krylov subspace method. Our proposed method has several distinguished advantages over conventional formulations (e.g., the well-known backward Euler with Newton-Raphson method). The matrix factorization is performed only for the conductance/resistance matrix G, without being performed for the combinations of the capacitance/inductance matrix C and matrix G, which are used in traditional implicit formulations. Furthermore, due to the explicit nature of our formulation, we do not need to repeat LU decompositions when adjusting the length of time steps for error controls. Our algorithm is better suited to solving tightly coupled post-layout circuits in the pursuit for full-chip simulation. Our experimental results validate the advantages of our framework.

3-D integrated circuits (3-D ICs) make use of the vertical dimension for smaller footprint, higher speed, lower power consumption, and better timing performance. In 3-D ICs, the inter-tier-via (ITV) is a critical enabling technique because it forms vertical signal and power paths. Accordingly, it is imperative to accurately and efficiently extract the electrostatic capacitances of ITVs using field solvers. Unfortunately, the cylindrical via shape presents major challenges to most of the existing methods. To address this issue, we develop a novel floating random walk (FRW) method by rotating the transition cube to suit the cylindrical surface, devising a special space management technique, and proposing accelerating techniques for structures with large-sized through-silicon-vias. Experiments on typical ITV structures suggest that the proposed techniques is up to hundreds times faster than a simple FRW approach and the boundary element method-based algorithms, without loss of accuracy. In addition, compared with extracting the square-approximation structures, the proposed techniques can reduce the error by 10×. Large and multidielectric structures have also been tested to demonstrate the versatility of the proposed techniques.

In this brief, we propose an efficient parallel finite difference-based thermal simulation algorithm for 3-D-integrated circuits (ICs) using generalized minimum residual method (GMRES) solver on CPU-graphic processing unit (GPU) platforms. First, the new method starts from basic physics-based heat equations to model 3-D-ICs with intertier liquid cooling microchannels and directly solves the resulting partial differential equations. Second, we develop a new parallel GPU-GMRES solver to compute the resulting thermal systems on a CPU-GPU platform. We also explore different preconditioners (implicit and explicit) and study their performances on thermal circuits and other types of matrices. Experimental results show the proposed GPU-GMRES solver can deliver orders of magnitudes speedup over the parallel LU-based solver and up to 4× speedup over CPU-GMRES for both dc and transient thermal analyzes on a number of thermal circuits and other published problems.

In this work, a hybrid random walk method is proposed for the thermal analysis of integrated circuits. Preserving the advantage of generic random walk method (GRW), i.e. the suitability for simulating local hot-spots, the proposed techniques largely reduce its runtime for accurate high-resolution simulation, and is suitable for the realistic pyramid-shape IC model. This is achieved by combining the GRW and the floating random walk techniques, and a novel usage of rectangular cuboid transition domain. The techniques to handle the Neumann boundary and convective boundary in thermal simulation are also discussed. Numerical experiments on several IC test cases validate the efficiency and accuracy of the proposed techniques, and demonstrate more than 100X speedup over the GRW method.

To enable the capacitance extraction of chip-scale large VLSI layout using the floating random walk (FRW) algorithm, two techniques are proposed. The first one is a virtual Gaussian surface sampling technique. It makes efficient random sampling on the Gaussian surface for complex nets with vias, and optimizes the sampling scheme to reduce the time of random walk. The other one is a parallelized, improved construction approach for Octree based space management structure. It can be over 5000X faster than the existing approach and provides same convenience to the FRW procedure. Numerical experiments on large cases with up to half million conductors validate the proposed techniques, and demonstrate a fast FRW solver for chip-scale extraction task.

Three-dimensional integrated circuits (3D ICs) make use of the vertical dimension for smaller footprint, higher speed, lower power consumption, and better timing performance. In 3D ICs, the inter-tier-via (ITV) is a critical enabling technique because it forms vertical signal and power paths. Accordingly, it is imperative to accurately and efficiently extract the electrostatic capacitances of ITVs using field solvers. Unfortunately, the cylindrical via shape presents major challenges to most of the existing methods. To address this issue, we develop a novel floating random walk (FRW) method by rotating the transition cube to suit the cylindrical surface and devising a special space management technique. Experiments on typical ITV structures suggest that the proposed techniques can accelerate the existing FRW and boundary element method (BEM) based algorithms by up to 20X and 180X, respectively, without loss of accuracy. In addition, compared with the naïve square approximation approach, our techniques can reduce the error by 10X. Large and multi-dielectric structures have been tested to demonstrate the versatility of the proposed techniques.

The floating random walk (FRW) algorithm is an important field-solver algorithm for capacitance extraction, which has several merits compared with other boundary element method (BEM) based algorithms. In this paper, the FRW algorithm is accelerated with the modern graphics processing units (GPUs). We propose an iterative GPU-based FRW algorithm flow and the technique using an inverse cumulative probability array (ICPA), to reduce the divergence among walks and the global-memory accessing. A variant FRW scheme is proposed to utilize the benefit of ICPA, so that it accelerates the extraction of multi-dielectric structures. The technique for extracting multiple nets concurrently is also discussed. Numerical results show that our GPU-based FRW brings over 20X speedup for various test cases with 0.5% convergence criterion over the CPU counterpart. For the extraction of multiple nets, our GPU-based FRW outperforms the CPU counterpart by up to 59X.

For accurate thermal simulation of integrated circuits (ICs), heat sink components in chip package must be considered. In this letter, techniques based on the domain decomposition method (DDM) are presented for the 3-D thermal simulation of nonrectangular IC thermal model including heat sink and heat spreader. A relaxed nonoverlapping DDM algorithm is employed to convert the problem to subproblems on rectangular subdomains. Then, a nonconformal discretization strategy is proposed to reduce the problem complexity with negligible error. Numerical experiments on several 2-D and 3-D IC test cases demonstrate that the relaxed nonoverlapping DDM is faster than the other preconditioned conjugate gradient algorithms with same mesh grid. The nonconformal discretization achieves further 10× reduction of runtime and memory usage.

A floating random walk (FRW) solver, called RWCap, is presented for the capacitance extraction of very-large-scale integration (VLSI) interconnects. An approach, including the numerical characterization of the cross-interface transition probability and weight value, is proposed to accelerate the extraction of structures with multiple dielectric layers. A comprehensive variance reduction scheme based on the importance sampling and stratified sampling is proposed to improve the convergence rate of the FRW algorithm. Finally, the space management technique using an octree data structure and the parallel computing technique are presented to further improve the efficiency. Numerical experiments are carried out with the test cases generated under the 180 and 45-nm process technologies. They demonstrate that the proposed multidielectric FRW algorithm achieves up to 160× speedup over the FRW algorithm using spherical transition domains to cross dielectric interface, with very small memory overhead. The variance reduction techniques further bring 3× or more speedup without memory overhead and the loss of accuracy. The RWCap also outperforms other existing FRW algorithm and fast boundary element method solvers in terms of computational time or scalability. The experiments on an 8-core CPU machine show that the parallel RWCap is over 6× faster than its serial-computing version.

In the capacitance extraction with the floating random walk (FRW) algorithm, the space management approach is required to facilitate finding the nearest conductor. The Octree and grid-based spatial structures have been used to decompose the whole domain into cells and to store information of local conductors. In this letter, the techniques with the distance limit of cell and only searching in cell's neighbor region are proposed to accelerate the construction of the spatial structures. A fast inquiry technique is proposed to fasten the nearest conductor query. We also propose a grid-Octree hybrid structure, which has advantages over existing structures. Experiments on large very large scale integration structures with up to 484441 conductors have validated the efficiency of the proposed techniques. The improved FRW algorithm is faster than RWCap for thousands times while extracting a single net, and several to tens times while extracting 100 nets.

The floating random walk (FRW) algorithm has several advantages for extracting 3D interconnect capacitance. However, for multi-layer dielectrics in VLSI technology, the efficiency of FRW algorithm would be degraded due to frequent stop of walks at dielectric interface and constraint of first-hop length especially in thin dielectrics. In this paper, we tackle these problems with the numerical characterization of Green's function for cross-interface transition probabilities and the corresponding weight value. We also present a space management technique with Octree data structure to reduce the time of each hop and parallelize the whole FRW by multi-threaded programming. Numerical results show large speedup brought by the proposed techniques for structures under the VLSI technology with thin dielectric layers.

In this paper, we present a variational electromagnetic-semiconductor coupled solver to assess the impacts of process variations on the 3D integrated circuit (3D IC) on-chip structures. The solver employs the finite volume method (FVM) to handle a system of equation considering both the full-wave electromagnetic effects and semiconductor effects. With a smart geometrical variation model for the FVM discretization, the solver is able to handle both small-size or large-size variations. Moreover, a weighted principle factor analysis (wPFA) technique is presented to reduce the random variables in both electromagnetic and semiconductor regions, and the spectral stochastic collocation method (SSCM) is used to generate the quadratic statistical model. Numerical results validate the accuracy and efficiency of this solver in dealing with process variations in hybrid material through-silicon via (TSV) structures.

In this paper, a new geometric variation model, referred to as the improved continuous surface variation (ICSV) model, is proposed to accurately imitate the random variation of on-chip interconnects. In addition, a new statistical capacitance solver is implemented to incorporate the ICSV model, the HPC and weighted PFA techniques. The solver also employs a parallel computing technique to greatly improve its efficiency. Experiments show that on a typical 65nm-technology structure, ICSV model has significant advantage over other existing models, and the new solver is at least 10X faster than the MC simulation with 10000 samples. The parallel solver achieves 7X further speedup on an 8-core machine. We conclude this paper with several criteria to discuss the trade-off between different geometric models and statistical methods for different scenarios.

In this paper, we propose an efficient approach to minimize the noise on power networks via the allocation of decoupling capacitors (decap) and controlled equivalent series resistors (ESR). The controlled-ESR is introduced to reduce the on-chip power voltage fluctuation, including both voltage drop and overshoot. We formulate an optimization problem of noise minimization with the constraint of decap budget. A revised sensitivity calculation method is derived to consider both voltage drop and overshoot. The sequential quadratic programming (SQP) algorithm is adopted to solve the optimization problem where the revised sensitivity is regarded as the gradient. Experimental results show that considering voltage drop without overshoot leads to underestimating noise by 4.8%. We also demonstrate that the controlled-ESR is able to reduce the noise by 25% with the same decap budget.

In this paper, we propose a novel statistical capacitance extraction method for interconnect conductors considering process variations. The new method is called statCap, where orthogonal polynomials are used to represent the statistical processes in a deterministic way. We first show how the variational potential coefficient matrix is represented in a first-order form using Taylor expansion and orthogonal decomposition. Then, an augmented potential coefficient matrix, which consists of the coefficients of the polynomials, is derived. After this, corresponding augmented system is solved to obtain the variational capacitance values in the orthogonal polynomial form. Finally, we present a method to extend statCap to the second-order form to give more accurate results without loss of efficiency compared to the linear models. We show the derivation of the analytic second-order orthogonal polynomials for the variational capacitance integral equations. Experimental results show that statCap is two orders of magnitude faster than the recently proposed statistical capacitance extraction method based on the spectral stochastic collocation approach and many orders of magnitude faster than the Monte Carlo method for several practical conductor structures.

With the popularity of multiple power domain (MPD) design, the multi-domain power network noise analysis and minimization is becoming important. This paper describes an efficient heuristic algorithm to arrange the power-up sequence in a multi-domain power network in order to minimize the noise. We present a formulation of this problem and show it is NP-complete. Therefore, we propose a simulated annealing (SA) based algorithm with preprocessing. Experimental results show that the proposed algorithm can minimize the noise close to the minimal values. In terms of efficiency, the SA algorithm is more than hundreds of times faster than the enumerating method and the running time scales well for these cases with the number of domains. In addition, we discuss the trade off between power-up efficiency and noise.

In this paper we present a continuous surface model to describe the interconnect geometric variation, which improves the currently used model for better accuracy while not increasing the number of variables. Based on it, efficient techniques are presented for chip-level capacitance extraction considering the window technique. The sparse-grid-based Hermite polynomial chaos combined with a novel weighted principle factor analysis is employed for intra-window extraction. Then, the inter-window capacitance covariance is calculated through matrix pseudo inverse. Numerical results validate the accuracy and efficiency of the proposed method, which is more than 50 times faster than the Monte-Carlo simulation with 10000 samples.

This work proposes reliability aware through silicon via (TSV) planning for the 3D stacked silicon integrated circuits (ICs). The 3D power distribution network is modeled and extracted in frequency domain which includes the impact of skin effect. The worst case power noise of the 3D power delivery networks (PDN) with local TSV failures resulting from fabrication process or circuit operation is identified in both frequency and time domain. From the experimental results, it is observed that a single TSV failure could increase the maximum voltage variation up to 70% which should be considered in nanoscale ICs. The parameters of the 3D PDN are designed such that the power distribution is reliable under local TSV failures. The spatial distribution of the power noise, reliability and block out area is analyzed to enhance the reliability of the 3D PDN under local TSV failure.

In this paper, an efficient framework is proposed to analyze the worst case of voltage variation of power network considering multidomain clock gating. First, a frequency-domain-based simulation method is proposed to obtain the time-domain voltage response. With the vector fitting technique, the frequency-domain responses are approximated by a partial fraction expression, which can be easily converted to a time-domain waveform. Then, an algorithm is proposed to find the worst-case voltage variation and corresponding clock gating patterns, through superimposing the voltage responses caused by all domains working separately. The major computation of the whole framework is solving the frequency-domain equation system, whose complexity is about$O(N^{\alpha}D\log f_{\max})$, where$\alpha$is between one and two if using an iterative solver from the PETSc library.$N$is the node number,$f_{\max}$is the upper bound of frequency, and$D$is the number of clock domains. Numerical results show that the proposed simulation method is up to several hundred times faster than commercial fast simulators, like HSPICE and MSPICE. In addition, the proposed method is able to analyze large-scale power networks that the commercial tools are not able to afford.

In this paper, we describe the algorithms implemented in MBEM, a program for wideband impedance extraction of complicated 3-D structures. MBEM is based on a mixed boundary element method (BEM), which reduces the number of unknowns from about 7N in FastImp to 4N, for MQS analysis. Efficient techniques are proposed to handle the extra matrix multiplication, form post-process matrices, and solve the final linear equation system. The inaccuracy of calculation using FastImp at low frequency is also analyzed, which shows the mixed BEM eliminates it completely. Experiments on several typical 3-D structures validate the advantage of MBEM over FastImp, on both accuracy and efficiency.

A low power passive equalizer using RL terminator is proposed and optimized in this work. The equalizer includes an inductor in series with the resistive terminator, which boosts high frequency components and therefore improves the interconnect bandwidth with little overhead on power consumption. An analytic estimation method for eye-opening and jitter based on tritonic step response is also introduced in this work, which enables the optimization procedure. Our experimental results show that our estimation method is accurate and a board level transmission line of 50cm wire length can achieve 15Gb/s data rate. With 15GHz frequency input, the power consumption of the equalizer is less than 2.5mW, and the total power is 5mW.

An efficient method is proposed to consider the process variations with spatial correlation, for chip-level capacitance extraction based on the window technique. In each window, an efficient technique of Hermite polynomial collocation (HPC) is presented to extract the statistical capacitance. The capacitance covariances between windows are then calculated to reflect the spatial correlation. The proposed method is practical for chip-level extraction task, and the experiments on full-path extraction exhibit its high accuracy and efficiency.

This paper proposes an efficient method to find the worst case of voltage violation by multi-domain clock gating in an on-chip power network. We first present a voltage response in an arbitrary multi-domain clock gating pattern, using a superposition technique. Then, an integer linear programming (ILP) formulation is proposed to identify the worst-case gating pattern and the maximum variation area. The ILP based method is significantly faster than a conventional method based on enumeration. The experimental results are also compared with a case where peak voltage variation is induced, which shows the latter technique largely underestimated the overall variation effect.

In this paper, we propose a novel statistical capacitance extraction method for interconnects considering process variations. The new method, called statCap, is based on the spectral stochastic method where orthogonal polynomials are used to represent the statistical processes in a deterministic way. We first show how the variational potential coefficient matrix is represented in a first-order form using Taylor expansion and orthogonal decomposition. Then an augmented potential coefficient matrix, which consists of the coefficients of the polynomials, is derived. After that, corresponding augmented system is solved to obtain the variational capacitance values in the orthogonal polynomial form. Experimental results show that our method is two orders of magnitude faster than the recently proposed statistical capacitance extraction method based on the spectral stochastic collocation approach and many orders of magnitude faster than the Monte Carlo method for several practical interconnect structures.

This paper introduces an accumulative prediction method to predict the eye diagram for high speed signaling systems. We use the step responses of pull-up and pull-down to extract the worst-case eye diagram, including the eye height and jitter. Furthermore, the method produces the input patterns of the worst-case intersymbol interference. The algorithm handles signals of either symmetric or asymmetric rise/fall time. Experimental results demonstrate the accuracy and efficiency of the proposed method.

An efficient method based on a direct boundary element method is proposed for extracting frequency-dependent substrate coupling parameters. A frequency-independent real-valued linear equation system is first solved. Then, the solution is transformed into frequency-dependent parameters at a specified frequency with the Sherman-Morrison-Woodbury formula. The first step is performed only once for a given structure, and the method is very efficient for extraction with multiple frequencies. The proposed method is compared with the Green's function-based method and the approach in our earlier paper for typical substrate structures. Numerical results demonstrate its accuracy, efficiency, and versatility.

The couplings via realistic lossy substrates can be modeled as frequency-dependent coupling parameters. The fast extraction at multiple frequencies can be accomplished in two sequent steps. The first is to extract the coupling resistance using a direct boundary element method (DBEM). The second is to revise the resistance into the parameter at the frequency in an exact and rapid way. The first step is time-consuming, while it runs only one time; the second repeats at each frequency, but is much easier. For more frequency calculation, this method is more advanced. Numerical experiments illustrate that this method has high accuracy, and it can be hundreds of times faster than an advanced Green's function based method. Substrates with arbitrary doping profiles can also be easily handled, which is partly verified by experiment.

In this paper, we investigate thermal via (T-via) planning during three-dimensional (3-D) floorplanning. First, we consider the temperature constrained T-via planning (TVP) problem on a given 3-D floorplan. Second, we integrate dynamic TVP into 3-D floorplanning process. Our main contribution and results can be summarized as follows. We solve the temperature constrained TVP problem by solving a sequence of simplified interlayer and intralayer TVP subproblems. Each subproblem is formulated as convex programming problem and we derive nearly optimal solution for detailed T-via distribution. Based on the TVP solution, we implement the integrated TVP and 3-D floorplanning algorithm in a two-stage approach. Before floorplanning, blocks are assigned into different layers by solving a sequence of knapsack problems. During floorplanning, T-vias are allocated with white space redistribution to optimize T-via insertion. Experimental results show that our TVP approach can reduce T-vias by 12% compared with a recent published work (J. Cong and Y. Zhang, "Thermal via planning for 3-D ICs," in Proc. Int. Conf. Comput.-Aided Des., Nov. 2005, pp.745-752). Compared with the postfloorplanning optimization approach, integrating TVP into floorplanning process can reduce T-vias by 16% with 21% runtime overhead

It is important to model substrate couplings for SoC/mixed-signal circuit designs. After introducing the continuation equation of full current in lossy substrates, we present a new direct boundary element method (DBEM), which can handle the substrates with arbitrary doping profiles. Three techniques can speed up the DBEM remarkably, which include reusing coefficient matrices for multiple-frequency calculation, condensing the linear system, and sparsifying coefficient matrix. Numerical experiments illustrate that DBEM has high accuracy and high efficiency, and is versatile for arbitrary doping profiles.

A complete multiple reciprocity method (CMRM), usually for the eigenvalue analysis of Helmholtz equation, is introduced to the BEM for frequency-dependent inductance extraction. Several approaches are proposed to resolve the problem of "ill-conditioned" series encountered when applying the CMRM practically. Using the BEM combined with CMRM, the major operations of calculating the numerical integrals for a frequency point become reusable, so that inductance extraction for a frequency range is greatly accelerated. Numerical results verify the accuracy and efficiency of the proposed method

As shown in literatures, partial reluctance based circuit analysis is efficient in capturing on-chip inductance effect, because the partial reluctance exhibits much better locality than partial inductance. However, most previous works on reluctance extraction did not take high frequency effect into account and were not efficient enough for 3D complex structure. In this paper, a new reluctance extraction algorithm is proposed considering the high frequency effect. Numerical experiments demonstrate that our algorithm can handle complex 3D interconnect structures while exhibiting high accuracy and a speed-up ratio of several tens to hundreds over FastHenry.

It is important to model the substrate coupling for mixed-signal or RF circuit designs. In this paper, a direct boundary element method (DBEM) and related efficient techniques are presented to calculate the coupling resistances for three-dimensional substrate structure. First, a nonuniform meshing scheme is presented to reduce boundary elements while preserving accuracy. Then, the unknowns on top medium surface are removed from the discretized linear system of DBEM with a matrix reduction technique. The third technique is applying the quasi-multiple medium idea (W. Yu, Z. Wang, and J. Gu, "Fast capacitance extraction of actual 3-D VLSI interconnects using quasi-multiple medium accelerated BEM," IEEE Trans. Microwave Theory Tech., vol. 51, no. 1, pp. 109-199, Jan. 2003), which greatly reduces the expense of matrix reduction and makes the final coefficient matrix much sparser. With these proposed techniques, the linear equation system is largely condensed and sparsified and then solved with a preconditioned generalized minimum residual solver for multiple right-hand sides to get the whole resistance matrix. Numerical experiments on typical substrates with various doping profiles show the high accuracy of the DBEM-based method. The authors also compared the DBEM method with the Green's function methods accelerated by discrete cosine transform or eigendecomposition techniques. The results show that the DBEM-based method is several times or tens of times faster than the other two. At the same time, the DBEM method has no difficulty in handling substrates with more complex than stratified doping profiles, which is a large advantage over the existing methods

Inserting dummy (area fill) metals is necessary to reduce the pattern-dependent variation of dielectric thickness in the chemical-mechanical polishing (CMP) process. Such floating dummy metals affect interconnect capacitance and, therefore, signal delay and crosstalk significantly. To take the floating dummies into account, an efficient method for three-dimensional (3-D) capacitance extraction based on boundary element method is proposed. By introducing a floating condition into the direct boundary integral equation (BIE) and adopting an efficient preconditioning technique, and the quasi-multiple medium (QMM) acceleration, the method achieves very high computational speed. For some typical structures of area fill, the presented algorithm has shown over 1000/spl times/ speedup over the industry-standard Raphael while preserving high accuracy. Compared with the recently proposed PASCAL in the work of Park et al. (2000), the proposed method also has about ten times speedup. Since the dummies are not regarded as normal electrodes in capacitance extraction, the proposed method is much more efficient than the conventional method, especially in cases with a large number of floating dummies.

It is important to model the substrate coupling for mixed-signal circuit designs today. This paper presents the direct boundary element method (BEM) for substrate resistance calculation, where only the boundary of substrate region is discretized. Firstly, an efficient scheme for non-uniform element partition is proposed. Secondly, a new technique is presented which can reduce the scale of produced linear system and then accelerate the equation solving, especially for the multiple right-hand sides problem like substrate resistance extraction. Experiments show that the proposed method has shown high efficiency compared with existing methods while preserving high accuracy.

It is important to model the substrate coupling for mixed-signal circuit designs today. This paper presents an improved direct boundary element method (DBEM) for substrate resistance calculation, where only the boundary of substrate volumes is discretized and only the free-space Green function is used. At first, we discard some inessential unknowns to compress the linear system without accuracy loss. Then we make the coefficient matrix sparser. In this way, solving the linear system is greatly accelerated. Experiments on various substrates validate that DBEM is several to tens of times faster than DCT-accelerated Green's function methods and the eigendecomposition method, while preserving high accuracy. Besides, another experiment shows that this method is versatile for irregular substrates.

The computational time and memory of three-dimensional (3-D) capacitance extraction have been greatly reduced by using a quasimultiple medium (QMM) technology, because it enlarges the matrix sparsity produced by the direct boundary element method (BEM). An approach to automatically determining the QMM cutting pair number and a preconditioning technique are proposed to enhance the QMM-based capacitance extraction. With these two enhancements, the capacitance extraction can achieve much higher speed and adaptability. Experimental results show over 10X speed-up and memory saving over the multipole approach with comparable accuracy.

In this paper, the quasi-multiple medium (QMM) method based on the direct boundary element method (BEM) is used to extract the capacitance of three-dimensional (3-D) VLSI interconnects with multiple dielectrics. Each dielectric in 3-D VLSI parasitic capacitor is cut into several fictitious mediums, so it produces much fewer non-zero entries to the total coefficients matrix. As a result, the QMM algorithm can greatly reduce the CPU time and memory space used in the capacitance extraction. To characterize the efficiency of QMM algorithm, we discuss accuracy, storage and timing statistics in comparison with the analogous information from non-QMM algorithm.

The Line Spectrum Pair (LSP) based on the principle of linear predictive coding (LPC) plays a very important role in the speech synthesis; it has many interesting properties. Several famous speech compression / decompression algorithms, including the famous code excited linear predictive coding (CELP), are based on the LSP analysis, where the information loss or predicting errors are often very small due to the LSP’s characteristics. Unfortunately till now there is not a satisfying kind of distance measure available for LSP so that this kind of features can be used for speech recognition applications. In this paper, the principle of LSP analysis is studied at first, and then several distance measures for LSP are proposed which can describe very well the difference between two groups of different LSP parameters. Experimental results are also given to show the efficiency of the proposed distance measures. 1.