On-chip communication system design starting from a high-level model can facilitate formal verification of system properties, such as safety and deadlock freedom. Yet, analyzing its quality-of-service (QoS) property, in our context, per-flow delay bound, is an open challenge. Based on executable micro-architectural specification (xMAS) which is a formal framework modeling communication fabrics, we first present how to model a classic input-queuing virtual channel router using the xMAS primitives and then a QoS analysis methodology using network calculus (NC). Thanks to the precise semantics of the xMAS primitives, the router can be modeled in different variants, which cannot be otherwise captured by normal ad hoc box diagrams. The analysis methodology consists of three steps: 1) given network and flow knowledge, we first create a well-defined precise xMAS model for a specific application on a concrete on-chip network; 2) the specific xMAS model is then mapped to an NC graph (NCG) following a set of mapping rules; and 3) finally, existing QoS analysis techniques can be applied to analyze the NCG to obtain end-to-end delay bound per flow. We also show how to apply the technique to a typical all-to-one communication pattern on a binary-tree network and conduct an SoC case study, exemplifying the step-by-step analysis procedure and discussing the tightness of the results.

In the past decades, harmonic balance (HB) has been widely used for computing steady-state solutions of nonlinear radio-frequency (RF) and microwave circuits. However, using HB for simulating strongly nonlinear post-layout RF circuits still remains a very challenging task. Although direct solution methods can be adopted to handle moderate to strong nonlinearities in HB analysis, such methods do not scale efficiently with large-scale problems due to excessively long simulation time and prohibitively large memory consumption. In this paper, we present a novel graph sparsification approach for automatically generating preconditioners that can be efficiently applied for simulating strongly nonlinear post-layout RF circuits. Our approach allows to sparsify time-domain circuit modified nodal analysis matrices that can be subsequently leveraged for sparsifying the entire HB Jacobian matrix. We show that the resultant sparsified Jacobian matrix can be used as a robust yet efficient preconditioner in HB analysis. Our experimental results show that when compared with the prior state-of-the-art direct solution method, the proposed solver can more efficiently handle moderate to strong nonlinearities during the HB analysis of RF circuits, achieving up to 20× speedups and 6× memory reductions.

To improve the efficiency of direct solution methods in SPICE-accurate integrated circuit (IC) simulations, preconditioned iterative solution techniques have been widely studied in the past decades. However, it is still an extremely challenging task to develop robust yet efficient general-purpose preconditioning methods that can deal with various types of large-scale IC problems. In this paper, based on recent graph sparsification research we propose circuit-oriented general-purpose support-circuit preconditioning (GPSCP) methods to dramatically improve the sparse matrix solution time and reduce the memory cost during SPICE-accurate IC simulations. By sparsifying the Laplacian matrix extracted from the original circuit network using graph sparsification techniques, general-purpose support circuits can be efficiently leveraged as preconditioners for solving large Jacobian matrices through Krylov-subspace iterations. Additionally, a performance model-guided graph sparsification framework is proposed to help automatically build nearly-optimal GPSCP solvers. Our experiment results for a variety of large-scale IC designs show that the proposed preconditioning techniques can achieve up to 18× runtime speedups and 7× memory reduction in DC and transient simulations when compared to state-of-the-art direct solution methods.

Studying the tightness of analytical delay and backlog bounds is critical for network-on-chip designs, since formal analysis predicts the boundary of communication delay and buffer dimensioning. However, this evaluation process is often a tedious, time-consuming, and manual simulation process whereas many simulation parameters have to be configured before the simulations run. We formulate the tightness evaluation as constrained optimization problems for delay bound and backlog bounds, respectively. The well-defined problems enable a fully automated configuration searching process, which can be guided by a heuristic algorithm with cycle-accurate simulations integrated. This is a fully automated procedure and thus provides a promising path to automatic design space exploration in similar contexts. Experimental results over various topologies and traffic patterns indicate that our method is effective in finding the configuration for best tightness up to 98%, even when up to 50 parameters are configured in a multidimensional discrete search space under complex constraints.

Studying the delay bound tightness typically takes a practical approach by comparing simulated results against analytic results. However, this is often a manual process whereas many simulation parameters have to be configured before the simulations run. This is a tedious and time-consuming process. We propose a technique to automate this process by using a simulated annealing approach. We formulate the problem as an online optimization problem, and embed a simulated annealing algorithm in the simulation environment to guide the search of configuration parameters which give good tightness results. This is a fully automated procedure and thus provide a promising path to automatic design space exploration in similar contexts. Experiment results of an all-to-one communication network with large searching space and complicated constraints illustrate the effectiveness of our method.

Existing state-of-the-art realizable RC reduction methods may not be suitable for scalable power grid reductions due to the fast growing computational complexity and the large number of ports. In this work, we present a scalable power grid reduction method for reducing large-scale flip-chip power grids based on recent spectral graph sparsification techniques. The first step of the proposed approach aggressively reduces the large power grid blocks into much smaller power grid blocks by properly matching the effective resistances of the original power grid networks. Next, an efficient spectral graph sparsification scheme is introduced to dramatically sparsify the relatively dense power grid blocks that are generated during the previous step. In the last, an effective grid compensation scheme is proposed to further improve the model accuracy of the reduced and sparsified power grid. Since reduction of each power grid block can be performed independently, our method can be easily accelerated on parallel computers, and therefore expected to be capable of handling large power grid designs as well as incremental designs. Extensive experimental results show that our method can scale linearly with power grid sizes and efficiently reduce industrial power grids sizes by 20X without loss of much accuracy in both DC and transient analysis.

In nowadays variation-aware IC designs, cell characterizations and SRAM memory yield analysis require many thousands or even millions of repeated SPICE simulations for relatively small nonlinear circuits. In this work, we present a massively parallel SPICE simulator on GPU, TinySPICE, for efficiently analyzing small nonlinear circuits, such as standard cell designs, SRAMs, etc. In order to gain high accuracy and efficiency, we present GPU-based parametric three-dimensional (3D) LUTs for fast device evaluations. A series of GPU-friendly data structures and algorithm flows have been proposed in TinySPICE to fully utilize the GPU hardware resources, and minimize data communications between the GPU and CPU. Our GPU implementation allows for a large number of small circuit simulations in GPU's shared memory that involves novel circuit linearization and matrix solution techniques, and eliminates most of the GPU device memory accesses during the Newton-Raphson (NR) iterations, which enables extremely high-throughput SPICE simulations on GPU. Compared with CPU-based TinySPICE simulator, GPU-based TinySPICE achieves up to 138X speedups for parametric SRAM yield analysis without loss of accuracy.

In the past decades, harmonic balance (HB) has been widely used for computing steady-state solutions of nonlinear radio-frequency (RF) and microwave circuits. However, using HB for simulating strongly nonlinear RF circuits still remains a very challenging task. Although direct solution methods can be adopted to handle moderate to strong nonlinearities in HB analysis, such methods do not scale efficiently with large-scale problems due to excessively long simulation time and huge memory consumption. In this work, we present a novel graph sparsification approach for generating preconditioners that can be efficiently applied for simulating strongly nonlinear RF circuits. Our approach first sparsifies RF circuit matrices that can be subsequently leveraged for sparsifying the entire HB Jacobian matrix. We show that the resultant sparsified Jacobian matrix can be used as a robust yet efficient preconditioner in HB analysis. Our experimental results show that when compared with existing state-of-the-art direct solvers, the proposed HB solver can more efficiently handle moderate to strong nonlinearities during the HB analysis of RF circuits, achieving more than 10X speedups and 8X memory reductions.

System design starting from high level models can facilitate formal verification of system properties, such as safety and deadlock freedom. Yet, analyzing their QoS property, in our context, per-flow delay bound, is an open challenge. Based on xMAS (eXecutable Micro-Architectural Specification), a formal framework modeling communication fabrics, we present a QoS analysis procedure using network calculus. Given network and flow knowledge, we first create a well-defined xMAS model for a specific application on a concrete on-chip network. Then the specific xMAS model can be mapped to its network calculus analysis model for which existing QoS analysis techniques can be applied to compute end-to-end delay bound per flow. We give an example to show the step-by-step analysis procedure and discuss the tightness of the results.

SPICE-accurate simulation of present-day large-scale nonlinear integrated circuit (IC) systems with millions of linear/nonlinear components can be prohibitively expensive, and thus extremely challenging. In this paper, we present a novel support-circuit preconditioning (SCP) technique for tackling large-scale nonlinear circuit simulations by exploiting sparsified graphs of a given circuit network. By extracting support graphs (SGs) from the original linear circuit networks, and combining them with nonlinear devices, support-circuit preconditioner can be efficiently computed using existing matrix solvers, allowing for on-the-fly updates during transient simulations when adopted in Krylov-subspace iterative solvers. Experimental results for a variety of large-scale circuit designs show that the proposed method achieves up to 22X speedups in solving the matrices involved in DC and transient (TR) simulations, and up to 8X reduction in memory usage, when compared with the simulator powered by the state-of-the-art direct solver KLU.

To improve the efficiency of direct solution methods in SPICE-accurate nonlinear circuit simulations, preconditioned iterative solution techniques have been widely studied in the past decades. However, it still has been an extremely challenging task to develop general-purpose preconditioning methods that can deal with various large-scale nonlinear circuit simulations. In this work, a novel circuit-oriented, general-purpose support-circuit preconditioning technique (GPSCP) is proposed to significantly improve the matrix solving time and reduce the memory consumption during large-scale non-linear circuit simulations. We show that by decomposing the system Jacobian matrix at a given solution point into a graph Laplacian matrix as well as a matrix including all voltage and controlled sources, and subsequently sparsifying the graph Laplacian matrix based on support graph theory, the general-purpose support-circuit preconditioning matrix can be efficiently obtained, thereby serving as a very effective and efficient preconditioner in solving the original Jacobian matrix through Krylov-subspace iterations. Additionally, a novel critical node selection method and an energy-based spanning-graph scaling method have been proposed to further improve the quality of ultra-sparsifier support graph. To gain higher computational efficiency during transient circuit analysis, a dynamic support-circuit preconditioner updating approach has also been investigated. Our experimental results for a variety of large-scale nonlinear circuit designs show that the proposed technique can achieve up to 14.0X runtime speedups and 6.7X memory reduction in DC and transient simulations.

To facilitate full chip capacitance extraction, field solvers are typically deployed for characterizing capacitance libraries for various interconnect structures and configurations. In the past decades, various algorithms for accelerating boundary element methods (BEM) have been developed to improve the efficiency of field solvers for capacitance extraction. This paper presents the first massively parallel capacitance extraction algorithm FMMGpu that accelerates the well-known fast multipole methods (FMM) on modern Graphics Processing Units (GPUs). We propose GPU-friendly data structures and SIMD parallel algorithm flows to facilitate the FMM-based 3-D capacitance extraction on GPU. Effective GPU performance modeling methods are also proposed to properly balance the workload of each critical kernel in our FMMGpu implementation, by taking advantage of the latest Fermi GPU's concurrent kernel executions on streaming multiprocessors (SMs). Our experimental results show that FMMGpu brings 22X to 30X speedups in capacitance extractions for various test cases. We also show that even for small test cases that may not well utilize GPU's hardware resources, the proposed cube clustering and workload balancing techniques can bring 20% to 60% extra performance improvements.

It is increasingly challenging to analyze present day large-scale power delivery networks (PDNs) due to the drastically growing complexity in power grid design. To achieve greater runtime and memory efficiencies, a variety of preconditioned iterative algorithms has been investigated in the past few decades with promising performance, while incremental power grid analysis also becomes popular to facilitate fast re-simulations of corrected designs. Although existing preconditioned solvers, such as incomplete matrix factor-based preconditioners, usually exhibit high efficiency in memory usage, their convergence behaviors are not always satisfactory. In this work, we present a novel hierarchical support-graph preconditioned iterative algorithm that constructs preconditioners by generating spanning trees in power supply networks for fast power grid analysis. The support-graph preconditioner is efficient for handling complex power grid structures (regular or irregular grids), and can facilitate very fast incremental analysis. Our experimental results on IBM power grid benchmarks show that compared with the best direct or iterative solvers, the proposed support-graph preconditioned iterative solver achieves up to 3.6X speedups for DC analysis, and up to 22X speedups for incremental analysis, while reducing the memory consumption by a factor of four.

Leveraging the power of nowadays graphics processing units for robust power grid simulation remains a challenging task. Existing preconditioned iterative methods that require incomplete matrix factorizations cannot be effectively accelerated on graphics processing unit (GPU) due to its limited hardware resource as well as data parallel computing. This paper presents an efficient GPU-based multigrid preconditioning algorithm for robust power grid analysis. By combining the fast geometric multigrid solver with the robust Krylov-subspace iterative solver, power grid DC and transient analysis can be performed efficiently on GPU without loss of accuracy (largest errors <;0.5 mV). Unlike previous GPU-based algorithms that rely on good power grid regularities, the proposed algorithm can be applied for more general power grid structures. Additionally, we also propose an accuracy-aware GPU performance modeling and optimization framework to automatically obtain the best power grid simulation configurations. Experimental results show that the DC and transient analysis on GPU can achieve more than 25X speedups over the best available CPU-based solvers.

Decoupling capacitor (decap) has been widely used to effectively reduce dynamic power supply noise. Traditional decap budgeting algorithms usually explore the sensitivity-based nonlinear optimizations or conjugate gradient (CG) methods, which can be prohibitively expensive for large-scale decap budgeting problems and cannot be easily parallelized. In this paper, we propose a hierarchical cross-entropy based optimization technique which is more efficient and parallel-friendly. Cross-entropy (CE) is an advanced optimization framework which explores the power of rare event probability theory and importance sampling. To achieve the high efficiency, a sensitivity-guided cross-entropy (SCE) algorithm is introduced which integrates CE with a partitioning-based sampling strategy to effectively reduce the solution space in solving the large-scale decap budgeting problems. Compared to improved CG method and conventional CE method, SCE with Latin hypercube sampling method (SCE-LHS) can provide 2× speedups, while achieving up to 25% improvement on power supply noise. To further improve decap optimization solution quality, SCE with sequential importance sampling (SCE-SIS) method is also studied and implemented. Compared to SCE-LHS, in similar runtime, SCE-SIS can lead to 16.8% further reduction on the total power supply noise.

Decoupling capacitor (decap) placement has been widely adopted as an effective way to suppress dynamic power supply noise. Traditional decap budgeting algorithms usually explore the sensitivity-based nonlinear optimizations or conjugate gradient methods, which can be prohibitively expensive for large-scale decap budgeting problems. We present a hierarchical cross entropy (CE) optimization technique for solving the decap budgeting problem. CE is an advanced optimization framework which explores the power of rare-event probability theory and importance sampling. To achieve high efficiency, a sensitivity-guided cross entropy (SCE) algorithm is proposed which integrates CE with a partitioning-based sampling strategy to effectively reduce the dimensionality in solving the large scale decap budgeting problems. Extensive experiments on industrial power grid benchmarks show that the proposed SCE method converges 2X faster than the prior methods and 10X faster than the standard CE method, while gaining up to 25% improvement on power grid supply noise. Importantly, the proposed SCE algorithm is parallel-friendly since the simulation samples of each SCE iteration can be independently obtained in parallel. We obtain up to 1.9X speedup when running the SCE decap budgeting algorithm on a dual-core-dual-GPU system.