Modern NVIDIA GPU architectures offer dot-product instructions (DP2A and DP4A), with the aim of accelerating machine learning and scientific computing applications. These dot-product instructions allow the computation of multiply-and-add instructions in a single clock cycle, effectively achieving higher throughput compared to conventional 32-bit integer units. In this paper, we show that the dot-product instruction can also be used to accelerate matrix-multiplication and polynomial convolution operations, which are widely used in post-quantum lattice-based cryptographic schemes. In particular, we propose a highly optimized implementation of FrodoKEM wherein the matrix-multiplication is accelerated by the dot-product instruction. We also present specially designed data structures that allow an efficient implementation of Saber key-encapsulation mechanism, utilizing the dot-product instruction to speed-up the polynomial convolution. The proposed FrodoKEM implementation achieves$4.37\times $higher throughput than the state-of-the-art implementation on a V100 GPU. This paper also presents the first implementation of Saber on GPU platforms, achieving 124,418, 120,463, and 31,658 key exchanges per second on RTX3080, V100, and T4 GPUs, respectively. Since matrix-multiplication and polynomial convolution operations are the most time-consuming operations in lattice-based cryptographic schemes, we strongly believe that the proposed methods can be beneficial to other KEM and signatures schemes based on lattices.

LU factorization is extensively used in engineering and scientific computations for solution of large set of linear equations. Particularly, circuit simulators rely heavily on sparse version of LU factorization for solution involving circuit matrices. One of the recent advances in this field is exploiting the emerging computing platform of graphics processing units (GPUs) for parallel and sparse LU factorization. In this article, following contributions are made to advance the state of the art in hybrid right-looking algorithm (RLA): 1) a novel GPU kernel based on parallel column and block size optimization (PCBSO) is developed for adaptively allocating the block size while optimizing the number of columns for parallel execution based on the size of their associated submatrices at every level. The proposed approach helps to minimize the resource contention and to improve the computational performance and 2) an algorithm is developed to enable the execution of the new adaptive mode with dynamic parallelism. Also, a comprehensive performance comparison using a set of benchmark circuit examples is presented. The results indicate that, the proposed advancements can improve the results of state-of-the-art right looking sparse LU factorization in GPU by$1.54\times $(Arithmetic Mean).

An efficient approach for modeling of time interval error (TIE) due to noise in power delivery networks (PDNs), for current-mode (CM) driver circuits, is presented. Semianalytical expressions relating the PDN noise and TIE are developed based on midpoint delays of the rising and falling edges of the differential signal. The validating examples with CM driver circuits designed in various technologies comparing both the proposed and conventional approaches demonstrate a significant speedup using the proposed approach.

In this paper, a parallel high-order envelope-following (EF) method is presented. The proposed method exploits the high-order and A-stable Obreshkov formula (ObF) to provide superior accuracy and speedup for the EF technique. Utilizing ObF provides accurate and faster analysis while keeping the same accuracy as the conventional low-order integration methods. In addition, a parallel method that is based on multiple-shooting (MS) techniques is used. Using MS allows partitioning and solving the sensitivity equations in parallel. It is also shown that with proper partitioning scheme, high CPU scalability can be achieved.

With the rapidly increasing demands for high-speed and high-density electronic products, complexity and size of the associated circuits have increased significantly in the recent years. The large size of these circuits poses major challenges for simulation in terms of excessive CPU cost. To address this, a parallel circuit simulation algorithm has been recently developed that allows modern multicore processors to be exploited to realize higher parallel scalability with an increasing number of CPUs. In this paper, several methods have been proposed to improve efficiency and flexibility during the partitioning of analog circuits. The proposed methods reduce the constraints for partitioning, allowing a more efficient set of partitions to be found, which improves scalability when used in a parallel implementation.

This paper presents structural characterization and performance enhancement strategies for the recently proposedA-stable and L-stable high-order integration methods based on the Obreshkov formula. It is demonstrated that although the Jacobian matrix in these methods has a bigger size than the Jacobian matrix in classical low-order methods, it enjoys a special structure that can be used to develop efficient factorization techniques. In addition, the paper proposes a method to reduce the number of Newton-Raphson iterations needed to converge in the large Jacobian domain.

This paper presents a fast algorithm for transient simulation of power grids in very large scale integration systems using waveform relaxation (WR) techniques. Novel partitioning methods and convergence accelerators are developed for fast convergence of WR iterations when applied to power grid networks. Unlike the direct solvers, the new method is highly parallelizable and scales well with the increasing number of CPUs, leading to significant speed-ups. Numerical examples are presented to demonstrate the validity and efficiency of the proposed method.

A parallel solver for steady state analysis of nonlinear circuits is presented. The solver uses the Message Passing Interface specification for communications and is suitable for steady state simulation of very large nonlinear circuits. Performance of the solver is investigated on symmetric multiprocessing, non-uniform memory access, and distributed memory computer systems. Impact of memory subsystem constraints on the solver efficiency is evaluated.

This paper describes a new$A$- and$L$-stable integration method for simulating the time-domain transient response of nonlinear circuits. The proposed method, which is based on the Obreshkov formula, can be made of arbitrary high order while maintaining the$A$-stability property. The new method allows for the adoption of higher order integration methods for the transient analysis of electronic circuits while enabling them to take larger step sizes without violating the stability, leading to faster simulations. The method can be run in an$L$-stable mode to handle circuits with extremely stiff equations. Necessary theoretical foundations, implementation details, error-control mechanisms, and computational results are presented.

Computation of passive and compact macromodels of distributed interconnects has gained considerable importance during the recent years. Method of characteristics (MoC) is widely used for macromodeling of transmission lines, however, it may not be guaranteed passive. This paper presents a new algorithm for passivity enforcement of MoC-based macromodels of multiconductor transmission lines. The algorithm is based on the first-order perturbation of the related delay differential equations and can handle single as well as coupled interconnects. Necessary theoretical foundations and validating numerical results are presented.

This paper presents a robust method for guaranteed passive macromodeling of high-speed interconnects characterized by multiconductor transmission lines with frequency-dependent per-unit-length (FD-PUL) parameters, using integrated-congruence-transformation-based model-order-reduction techniques. For this purpose, a new formulation is developed to directly incorporate state-space equations corresponding to the positive-real (PR) rational functions representing the frequency dependence of PUL parameters, in Telegrapher's equations. The proposed formulation overcomes the need for explicit lumped-circuit realization with all positive elements for PR rational functions of FD-PUL parameters. Proof of passivity and numerical examples are presented to validate the theory.

The large number of ports in an interconnect struc- ture is a critical limiting factor when applying model-order reduction. This is due to the fact that the size of the reduced model grows rapidly with increasing the number of ports, lead- ing to large and dense circuit matrices. To address this problem, a novel method based on transverse partitioning and waveform relaxation is proposed for passive model-order reduction of massively coupled large multiport interconnects. The new method effectively replaces the tightly coupled multiport reduced model with decoupled 2-port subcircuits. In addition to preserving the advantages of model-order reduction, the compu- tational complexity of the new method grows only linearly with the number of lines.

This paper describes a new algorithm for the analysis of high-speed interconnects characterized by frequency-dependent per-unit-length parameter matrices. The proposed technique is based on using the idea of integrated congruence transform to construct a reduced-order system for the interconnect. The reduced-order system offers simple time-domain ordinary differential equations that can be embedded into conventional circuit simulators. The proposed algorithm provides a new approach to perform implicit moment matching on a system described by a mixed set of linear differential algebraic equations. This feature offers a high accuracy in the reduced system over a wide frequency range. The passivity of the reduced-order system is guaranteed. Numerical results demonstrate the validity of the proposed technique.

With the ever increasing signal speeds, signal integrity issues of high-speed VLSI designs are presenting increasingly difficult challenges for state-of-the-art modeling and simulation tools. Consequently, characterization and passive macromodeling of high-speed modules such as interconnects, vias, and packages based on tabulated data are becoming important. This paper presents a fast algorithm for passivity verification and enforcement of large order macromodels of scattering parameter based multiport subnetworks. Numerous examples tested on this algorithm demonstrate a significant speed-up compared to the existing algorithms in the literature

This paper presents a new algorithm for computing the sensitivity of steady-state responses of nonlinear circuits with respect to an arbitrary network parameter. The proposed algorithm is based on circuit-reduction techniques obtained through nonlinear-projection approaches. The main idea in the proposed sensitivity-computation algorithm is based on projecting the adjoint system of equations onto a subspace of smaller dimension. Continuation methods are then applied on the reduced system to trace the solution trajectory of the adjoint system in the reduced space. We show that once the steady-state solution has been obtained using nonlinear order reduction, the computational cost required to compute sensitivity is only a limited number of forward/backward substitutions. Numerical examples are presented to demonstrate the accuracy and efficiency of the proposed algorithm.

Time-domain macromodeling of high speed interconnects characterized by distributed transmission lines has generated immense interest during the recent years. It has been demonstrated that, preserving passivity of the macromodel is essential to guarantee a stable global transient simulation. In this paper, a SPICE compatible closed-form passive macromodel for distributed transmission lines is presented. The proposed method enables representation of the distributed stamp in terms of simple delay and resistive elements. The new method while guaranteeing the passivity of the macromodel, provides significant speedup, and enables easy implementation. Necessary formulation and validation examples are given.

With the continually increasing operating frequencies, complex high-speed interconnect and package modules require characterization based on measured/simulated data. Several algorithms were recently suggested for macromodeling such types of data to enable unified transient analysis in the presence of external network elements. One of the critical issues involved here is the passivity violations associated with the computed macromodel. To address this issue, a new passivity enforcement algorithm is presented in this paper. The proposed method adopts a global approach for passivity enforcement by ensuring that the passivity correction at a certain region does not introduce new passivity violations at other parts of the frequency spectrum. It also provides an error estimate for the response of the passivity corrected macromodel.

With the rapid developments in very large-scale integration (VLSI) technology, design and computer-aided design (CAD) techniques, at both the chip and package level, the operating frequencies are fast reaching the vicinity of gigahertz and switching times are getting to the subnanosecond levels. The ever increasing quest for high-speed applications is placing higher demands on interconnect performance and highlighted the previously negligible effects of interconnects such as ringing, signal delay, distortion, reflections, and crosstalk. In this review paper various high-speed interconnect effects are briefly discussed. In addition, recent advances in transmission line macromodeling techniques are presented. Also, simulation of high-speed interconnects using model-reduction-based algorithms is discussed in detail.

In the above paper,1 we wish to call the attention of the reader-ship to an error that appears on p. 721. Fig. 27 should have appeared as follows: We regret any confusion this may have caused.

Signal integrity analysis has become imperative for high-speed designs. In this paper, we present a new technique to advance Krylov-space based passive model-reduction algorithms to include lossy coupled transmission lines described by Telegrapher's equations. In the proposed scheme, transmission line subnetworks are treated with closed-form stamps obtained using matrix-exponential Padé, where the coefficients describing the model are computed a priori and analytically. In addition, a technique is given to ensure that the contribution of these stamps to the modified nodal analysis (MNA) formulation leads to guaranteed passive macromodel.

Accurate simulation of large interconnect networks has become a necessity to address signal integrity issues in high-speed designs. Recently, several model-reduction techniques based on Krylov-space methods have been proposed for efficient simulation of large linear networks, However, these methods treat the distributed networks in terms of their lumped representations. In order to overcome this difficulty, a new technique based on congruent transformation is presented in this paper to directly include distributed systems described by Telegrapher's partial differential equations,.

Accurate simulation of large interconnect networks has become a necessity to address signal-integrity issues in current high-speed very-large-scale-integration designs. To accurately characterize a dispersive system of interconnects at higher frequencies, a full-wave analysis is required. However, conventional circuit simulation of interconnects with full-wave models is extremely CPU expensive. Recently published moment-matching techniques provide a generalized approach to lumped/distributed circuit response approximations. However, these techniques are based on quasi-transverse electromagnetic mode (TEM) assumption and have no mechanism to handle full-wave models. In this paper, we present a new method to extend model-reduction techniques for simulation of full-wave models. The following three new results are presented in this paper: 1) a generalized method to combine modal results from a full-wave analysis into circuit simulators; 2) a new algorithm for moment generation involving full-wave models; 3) deviations associated with quasi-TEM approximations compared to full-wave models at higher frequencies. The proposed algorithm yields a speed up of 1 to 2 orders of magnitude for a comparable accuracy with conventional techniques. In addition, the proposed method can be used for a mixed simulation involving distributed models with frequency dependent/independent RLCG parameters, full-wave interconnect models and measured subnetworks along with nonlinear terminations.

This paper describes a new moment-generation algorithm for efficient simulation of linear subnetworks characterized by measured or tabulated data using moment-matching techniques. The subnetwork moments are computed by performing an integration in time-domain on the measured data. The proposed technique is more accurate as it relies on integration as compared to the previously published approaches which depend on the differentiation of measured data in frequency-domain for computation of moments. Using the new moment-generation technique, the CFH (Complex Frequency Hopping) algorithm has been extended to handle measured subnetworks. Also a generalized stencil for measured data for inclusion in circuit simulators and to facilitate efficient moment-generation has been presented. Examples and comparison with conventional simulations are provided. The method is accurate while it is faster than the conventional approach by 1 to 2 orders of magnitude.

In order to accurately characterize dispersive system of VLSI interconnects at higher frequencies, full wave analysis which takes into account all possible field components and satisfies all boundary conditions is required. However, conventional circuit simulation of interconnects with full wave models is extremely CPU expensive. This paper presents a new method to extend the moment matching technique, complex frequency hopping, to the case of interconnects modeled with full wave analysis. Formulation of circuit equations is modified to incorporate interconnect stencil from full wave analysis. A new algorithm for the moment generation for interconnect networks with full wave models has been developed. Full wave analysis has been carried out with the efficient 'spectral domain approach'. Results have shown that the proposed method is accurate while it yields a speed up of one to three orders of magnitude over conventional simulation techniques.