The emergence of multicore and many-core processors has introduced new opportunities and challenges to electronic design automation research and development. While the availability of increasing parallel computing power holds new promise to address many challenges in computer-aided design (CAD), the leverage of hardware parallelism can only be possible with a new generation of parallel CAD applications. In this paper, we propose a novel hierarchical multialgorithm (MA) parallel circuit simulation approach and its multicore implementation to expedite one of the most fundamental CAD applications: transistor-level transient circuit simulation. In our parallel circuit simulation approach, we create two levels of parallelism. At the higher level of parallelism, we start multiple simulation algorithms in parallel for a given simulation task. Interalgorithm communication is established to enable simulation algorithms to exchange useful information so that they could advance faster than without doing so. At the lower level of parallelism, each algorithm within the MA framework utilizes fine-grained parallel techniques such as parallel device evaluation and parallel matrix solve to fully harness the available hardware resources. By combining the two levels of parallelism, the computing power of the multicore or many-core processor platforms can be fully utilized to achieve superlinear speedup in circuit simulation.

With the increasing popularity of multi-core processors and the promise of future many-core systems, parallel CAD algorithm development has attracted a significant amount of research effort. However, a highly relevant issue, parallel program performance modeling has received little attention in the EDA community. Performance modeling serves the critical role of guiding parallel algorithm design and provides a basis for runtime performance optimization. We propose a systematic composable approach for the performance modeling of a recently developed hierarchical multi-algorithm parallel circuit simulation (HMAPS) approach. The unique integration of inter- and intra-algorithm parallelisms allows a multiplicity of parallelisms to be exploited in HMAPS and also creates interesting modeling challenges in forms of complex performance tradeoffs and large runtime configuration space. We model the performances of key subtask entities as functions of workload and parallelism. We address significant complications introduced by inter-algorithm interactions in terms of memory contention and collaborative simulation behavior via novel penalty and statistical based modeling. The proposed approach is able to accurately predict the parallel performance of a given HMAPS configuration and hence enables the runtime optimization of the parallel simulation code.

Integrating a large number of on-chip voltage regulators holds the promise of solving many power delivery challenges through strong local load regulation and facilitates system-level power management. The quantitative understanding of such complex power delivery networks (PDNs) is hampered by the large network complexity and interactions between passive on-die/package-level circuits and a multitude of nonlinear active regulators. We develop a fast combined GPU-CPU analysis engine encompassing several simulation strategies, optimized for various subcomponents of the network. Using accurate quantitative analysis, we demonstrate the significant performance improvement brought by onchip low-dropout regulators (LDOs) in terms of suppressing high-frequency local voltage droops and avoiding the mid-frequency resonance caused by off-chip inductive parasitics. We perform comprehensive analysis on the tradeoffs among overhead of on-chip LDOs, maximum voltage droop and overall power efficiency. We conduct systematic design optimization by developing a simulation-based nonlinear optimization strategy that determines the optimal number of on-chip LDOs required and on-board input voltage, and the corresponding voltage droop and power efficiency for PDNs with multiple power domains.

The past several years have witnessed a significant interest in developing parallel CAD algorithms and implementations that exploit various multi-core and distributed computing hardware. In addition to fundamental parallel algorithm design, the ability in modeling parallel performance and facilitating runtime optimization is indispensable for achieving good efficiency for complex parallel CAD applications. Under the context of a recently developed hierarchical multi-algorithm parallel circuit simulation (HMAPS) framework, we demonstrate a runtime optimization approach that allows for automatic on-the-fly reconfiguration of the parallel simulation code. We show how the runtime information, collected as parallel simulation proceeds, can be combined with static parallel performance models to enable dynamic adaptation of parallel simulation execution for improved performance and robustness. Our results have shown that the proposed approach not only finds the near-optimal code configuration over a large configuration space, it also outperforms multi-algorithm circuit simulation assisted only with static pre-runtime parallel performance modeling.

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

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

Mesh-based clock distribution network has been employed in many high-performance microprocessor designs due to its favorable properties such as low clock skew and robustness. Such clock distributions are usually highly complex. While the simulation of clock meshes is already time consuming, tuning such networks under tight performance constraints is a more daunting task. In this paper, we address the challenging task of driver size optimization with a goal of skew minimization. The expensive objective function evaluations and difficulty in getting explicit sensitivity information make this problem intractable to standard optimization methods. We propose to explore the recently developed asynchronous parallel pattern search (APPS) method for efficient driver size tuning. While being a search-based method, APPS not only provides the desirable derivative-free optimization capability, but is also amenable to parallelization and possesses appealing theoretically rigorous convergence properties. We show how such a method can lead to powerful parallel sizing optimization of large clock meshes with significant runtime and quality advantages over the traditional sequential quadratic programming (SQP) method. We also show how design-specific properties and speeding-up techniques can be exploited to make the optimization even more efficient while maintaining the convergence of APPS in a practical sense.

While the emergence of multi-core shared-memory machines offers a promising computing solution to ever complex chip design problems, new parallel CAD methodologies must be developed to gain the full benefit of these increasingly parallel computing systems. We present a parallel transient simulation methodology and its multi-threaded implementation for general analog and digital ICs. Our new approach, Waveform Pipelining (abbreviated as WavePipe), exploits coarsegrained application-level parallelism by simultaneously computing circuit solutions at multiple adjacent time points in a way resembling hardware pipelining. There are two embodiments in WavePipe: backward and forward pipelining schemes. While the former creates independent computing tasks that contribute to a larger future time step by moving backwards in time, the latter performs predictive computing along the forward direction of the time axis. Unlike existing relaxation methods, WavePipe facilitates parallel circuit simulation without jeopardying convergence and accuracy. As a coarse-grained parallel approach, WavePipe not only requires low parallel programming effort, more importantly, it creates new avenues to fully utilize increasingly parallel hardware by going beyond conventional finer grained parallel device model evaluation and matrix solutions.

The emergence of multi-core and many-core processors has introduced new opportunities and challenges to EDA research and development. While the availability of increasing parallel computing power holds new promise to address many computing challenges in CAD, the leverage of hardware parallelism can only be possible with a new generation of parallel CAD applications. In this paper, we propose a novel multi-algorithm parallel circuit simulation approach (MAPS) and its multi-core implementation to expedite one of the most fundamental CAD applications: transistor-level transient circuit simulation. MAPS starts multiple simulation algorithms in parallel for a given simulation task. By properly synchronizing these algorithms on-the-fly, we exploit the diversity in simulation algorithms to achieve possibly superlinear overall speedup in transient simulation. In addition, our unique multi-algorithm framework allows unique safe exploration of simulation methods that are conventionally discarded due to convergence concerns. As a coarse grained parallel simulation approach, the implementation of MAPS demands a minimum of parallel programming effort and allows for reuse of existing serial simulation codes.

Leakage power is becoming an increasingly important component of total chip power consumption for nanometer IC designs. Minimization of leakage power unavoidably enforces the consideration of the key sources of process variations, namely transistor channel length and threshold variations, since both have a significant impact on timing and leakage power. However, the statistical nature of chip performances often requires the use of expensive statistical analysis and optimization techniques in a leakage minimization task, contributing to high computational complexity. Further, the commonly used discrete cell libraries bring specific difficulty for design optimization and render pure continuous sizing and VT optimization algorithm suboptimal. In this paper, we present a fast yet effective approach to statistical leakage power reduction via gate sizing and multiple VT assignment. The proposed technique achieves the runtime efficiency via the use of the novel concept of equi-slack shells and performs fast leakage power reduction on the basis of shells while maintaining the timing yield. When combined with a finer grained gate-based post tuning step, the presented technique achieves Superior runtime efficiency while offering significant leakage power reduction.

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

Interconnects constitute a dominant source of circuit delay for modern chip designs. The variations of critical dimensions in modern VLSI technologies lead to variability in interconnect performance that must be fully accounted for in timing verification. However, handling a multitude of inter-die/intra-die variations and assessing their impacts on circuit performance can dramatically complicate the timing analysis. In this paper, a practical interconnect delay and slew analysis technique is presented to facilitate efficient evaluation of wire performance variability. By harnessing a collection of computationally efficient procedures and closed-form formulas, process variations are directly mapped into the variability of the output delay and slew. An efficient method based on sensitivity analysis is implemented to calculate driving point models under variations for gate-level timing analysis. The proposed adjoint technique not only provides statistical performance variations of the interconnect network under analysis, but also produces delay and slew expressions parameterized in the underlying process variations in a quadratic parametric form. As such, it can be harnessed to enable statistical timing analysis while considering important statistical correlations. Our experimental results have indicated that the presented analysis is accurate regardless of location of sink nodes and it is also robust over a wide range of process variations.

Interconnects constitute a dominant source of circuit delay for modern chip designs. The variations of critical dimensions in modern VLSI technologies lead to variability in interconnect performance that must be fully accounted for in timing verification. However, handling a multitude of inter-die/intra-die variations and assessing their impacts on circuit performance can dramatically complicate the timing analysis. In this paper, a practical interconnect delay and slew analysis technique is presented to facilitate efficient evaluation of wire performance variability. By harnessing a collection of computationally efficient procedures and closed-form formulas, process and input signal variations are directly mapped into the variability of the output delay and slew. Since our approach produces delay and slew expressions parameterized in the underlying process variations, it can be harnessed to enable statistical timing analysis while considering important statistical correlations. Our experimental results have indicated that the presented analysis is accurate regardless of location of sink nodes and it is also robust over a wide range of process variations.