This paper addresses the challenging problem of retrieval and matching of graph structured objects, and makes two key contributions. First, we demonstrate how Graph Neural Networks (GNN), which have emerged as an effective model for various supervised prediction problems defined on structured data, can be trained to produce embedding of graphs in vector spaces that enables efficient similarity reasoning. Second, we propose a novel Graph Matching Network model that, given a pair of graphs as input, computes a similarity score between them by jointly reasoning on the pair through a new cross-graph attention-based matching mechanism. We demonstrate the effectiveness of our models on different domains including the challenging problem of control-flow graph based function similarity search that plays an important role in the detection of vulnerabilities in software systems. The experimental analysis demonstrates that our models are not only able to exploit structure in the context of similarity learning but they can also outperform domain specific baseline systems that have been carefully hand-engineered for these problems.

Population Based Training (PBT) is a recent approach that jointly optimizes neural network weights and hyperparameters which periodically copies weights of the best performers and mutates hyperparameters during training. Previous PBT implementations have been synchronized glass-box systems. We propose a general, black-box PBT framework that distributes many asynchronous "trials" (a small number of training steps with warm-starting) across a cluster, coordinated by the PBT controller. The black-box design does not make assumptions on model architectures, loss functions or training procedures. Our system supports dynamic hyperparameter schedules to optimize both differentiable and non-differentiable metrics. We apply our system to train a state-of-the-art WaveNet generative model for human voice synthesis. We show that our PBT system achieves better accuracy and faster convergence compared to existing methods, given the same computational resource.

It is challenging to efficiently evaluate the performance bound of high-precision analog circuits with input and parameter variations at nano-scale. With the use of zonotope to model uncertainty of input data pattern (or jitter) and multiple parameters, a reachability-based verification is developed in this paper to compute the worst-case eye-diagram. The proposed zonotope-based reachability analysis can consider both spatial and temporal variations in one-time simulation. Moreover, a nonlinear zonotoped macromodeling is further developed to reduce the computational complexity. Performance bound for I/O links considering the parameter variations are evaluated. In addition, the eye-diagrams are generated by the proposed zonotoped macromodel for performance evaluation considering both temporal and spatial variations. As shown by experiments, the zonotoped macromodel achieves up to 450× speedup compared to the Monte Carlo simulation of the original model within small error under specified macromodel order for high-speed I/O links eye-diagram verification.

Efficient performance modeling of today's analog and mixed-signal circuits is an important yet challenging task, due to the high-dimensional variation space and expensive circuit simulation. In this paper, we propose a novel performance modeling algorithm that is referred to as Bayesian model fusion (BMF) to address this challenge. The key idea of BMF is to borrow the information collected from an early stage (e.g., schematic level) to facilitate efficient performance modeling at a late stage (e.g., post layout). Such a goal is achieved by statistically modeling the performance correlation between early and late stages through Bayesian inference. Furthermore, to make the proposed BMF method of practical utility, four implementation issues, including: 1) prior mapping; 2) missing prior knowledge; 3) fast solver; and 4) prior and hyper-parameter selection, are carefully considered in this paper. Two circuit examples designed in a commercial 32 nm CMOS silicon on insulator process demonstrate that the proposed BMF method achieves up to 9× runtime speed-up over the traditional modeling technique without surrendering any accuracy.

Uncertainty prevails in IC manufacturing and circuit operation. In particular, process variability has a huge impact on circuit performance, especially for mixed-signal/RF circuits, leading to unacceptable yields. Additionally, environmental uncertainties, such as temperature fluctuation and channel variation, further deteriorate performances in field. To combat variability, circuits are often made reconfigurable by adding tunable knobs to recover circuit performance in the post-manufacturing stage. However, as the number of knobs increases, knob tuning becomes challenging due to the huge search space. In fact, knob-tuning policies can have an observable impact on final performance and power consumption. In this paper, we propose mTunes, a method based on the Markov decision process for dynamically choosing the "right" knob tuning sub-routine from a pre-defined set achieving a balance between performance and power constraints. The proposed method has been applied to a reconfigurable RF front-end design, showing 60% improvement in yield compared to static tuning policies.

Upon the observation of a circuit failure, problematic circuit blocks and parameters need to be localized before they can be fixed or bypassed -- this has traditionally been highly manual and problem-specific. In this paper, we present a bug localization methodology that automatically identifies and ranks potential root-causes probabilistically. We model linear and nonlinear sub-circuits using the corresponding probabilistic graphical models, and formulate the bug localization problem as a statistical inference problem given partially observed data. We infer the posterior distribution of underlying circuit parameters, which provides a statistical measure of whether the bug lies in each sub-circuit. We have verified this methodology on a high-speed I/O link circuit, and have demonstrated its effectiveness of root-causing circuit bugs.

With the use of zonotope to model uncertainty of input data pattern (or jitter), a reachability-based verification is developed in this paper to compute the worst-case eye-diagram. The proposed zonotope-based reachability analysis can consider both spatial and temporal variations in one-time simulation of high-speed I/O links. Moreover, nonlinear zonotoped macromodeling is developed to reduce the verification complexity. As shown by experiments, the zonotoped macromodel achieves up to 450× speedup compared to the Monte Carlo simulation of the original model within small error under specified macromodel order for highspeed I/O links verification.

Moment estimation is one of the most important tasks to appropriately characterize the performance variability of today's nanoscale integrated circuits. In this paper, we propose an efficient algorithm of multi-population moment estimation via Dirichlet Process (MPME-DP) for validation of analog and mixed-signal circuits with extremely small sample size. The key idea is to partition all populations (e.g., different environmental conditions, setup configurations, etc.) into groups. The populations within the same group are similar and their common knowledge can be extracted to improve the accuracy of moment estimation. As will be demonstrated by the silicon measurement data of a high-speed I/O link, MPME-DP reduces the moment estimation error by up to 65% compared to other conventional estimators.

Moment estimation is an important problem during circuit validation, in both presilicon and postsilicon stages. From the estimated moments, the probability of failure and parametric yield can be estimated at each circuit configuration and corner, and these metrics are used for design optimization and making product qualification decisions. The problem is especially difficult if only a very small sample size is allowed for measurement or simulation, as is the case for complex analog/mixed-signal circuits. In this paper, we propose an efficient moment estimation method, called multiple-population moment estimation (MPME), that significantly improves estimation accuracy under small sample size. The key idea is to leverage the data collected under different corners/configurations to improve the accuracy of moment estimation at each individual corner/configuration. Mathematically, we employ the hierarchical Bayesian framework to exploit the underlying correlation in the data. We apply the proposed method to several datasets including postsilicon measurements of a commercial high-speed I/O link, and demonstrate an average error reduction of up to 2×, which can be equivalently translated to significant reduction of validation time and cost.

A critical problem in pre-Silicon and post-Silicon validation of analog/mixed-signal circuits is to estimate the distribution of circuit performances, from which the probability of failure and parametric yield can be estimated at all circuit configurations and corners. With extremely small sample size, traditional estimators are only capable of achieving a very low confidence level, leading to either over-validation or under-validation. In this paper, we propose a multi-population moment estimation method that significantly improves estimation accuracy under small sample size. In fact, the proposed estimator is theoretically guaranteed to outperform usual moment estimators. The key idea is to exploit the fact that simulation and measurement data collected under different circuit configurations and corners can be correlated, and are conditionally independent. We exploit such correlation among different populations by employing a Bayesian framework, i.e., by learning a prior distribution and applying maximum a posteriori estimation using the prior. We apply the proposed method to several datasets including post-silicon measurements of a commercial high-speed I/O link, and demonstrate an average error reduction of up to 2x, which can be equivalently translated to significant reduction of validation time and cost.

Efficient high-dimensional performance modeling of today's complex analog and mixed-signal (AMS) circuits with large-scale process variations is an important yet challenging task. In this paper, we propose a novel performance modeling algorithm that is referred to as Bayesian Model Fusion (BMF). Our key idea is to borrow the simulation data generated from an early stage (e.g., schematic level) to facilitate efficient high-dimensional performance modeling at a late stage (e.g., post layout) with low computational cost. Such a goal is achieved by statistically modeling the performance correlation between early and late stages through Bayesian inference. Several circuit examples designed in a commercial 32nm CMOS process demonstrate that BMF achieves up to 9x runtime speedup over the traditional modeling technique without surrendering any accuracy.

In this paper, we describe a novel statistical framework, referred to as Bayesian Model Fusion (BMF), that allows us to minimize the simulation and/or measurement cost for both pre-silicon validation and post-silicon tuning of analog and mixed-signal (AMS) circuits with consideration of large-scale process variations. The BMF technique is motivated by the fact that today's AMS design cycle typically spans multiple stages (e.g., schematic design, layout design, first tape-out, second tape-out, etc.). Hence, we can reuse the simulation and/or measurement data collected at an early stage to facilitate efficient validation and tuning of AMS circuits with a minimal amount of data at the late stage. The efficacy of BMF is demonstrated by using several industrial circuit examples.

The design of a communications system is typically most effective only when each of its components can be accurately represented by a discrete, symbolic behavioural abstraction. Such abstractions, in addition to providing valuable design intuition, also enable highly efficient and scalable system-level simulation. However, given a SPICE-level description for a subsystem such as a latch, it is a challenge to come up with a discrete, symbol-level abstraction that accurately captures its continuous-time dynamics. Indeed, the manual construction of such an abstraction requires deep knowledge and understanding of the operation of the module in question; moreover, it is very time-consuming, tedious, error-prone and not easily scalable to larger designs. In recent work [1], we adapted methods from computational learning theory to develop an automated technique, DAE2FSM, that produces binary finite state machine (FSM) abstractions of non-linear analog/mixed-signal (AMS) circuits. In the present paper, we demonstrate the application of the DAE2FSM technique to automatically derive FSM abstractions for a mixed-signal communications circuit component, namely a current mode latch (CML) designed in IBM's 90nm LP process technology. We show that the FSMs learned by DAE2FSM not only capture the essence of the latch's behaviour during normal conditions, but also faithfully mimic its behaviour under adverse operating conditions (e.g., under lowered supply voltages). Moreover, in addition to a stand-alone CML, we also generate FSMs for cascades of two and three latches (such topologies are used in the design of power-efficient, bit-error optimised analog-to-digital converters). In spite of the inherent non-linearity of such systems, and in spite of the pronounced “analog-ness” of the waveforms in question, our FSM abstractions are able to produce discrete-time symbol sequences that closely match the data points obtained by sampling from continuous-time SPICE simulations.

There are increasingly number of analog/mixed-signal circuits in microprocessors and SOCs. A significant portion of mixed-signal circuits are high-speed I/O links, including serial buses such as PCIE and parallel buses such as DDR. Post-silicon validation of I/O links is hard and time-consuming, and can be critical for making a product release qualification decision. In this paper, we try to summarize key challenges in post-silicon I/O validation. We discuss potential research directions and potential solutions to improve efficiency and quality of I/O validation.

Parametric yield estimation is one of the most critical-yet-challenging tasks for designing and verifying nanoscale analog and mixed-signal circuits. In this paper, we propose a novel Bayesian model fusion (BMF) technique for efficient parametric yield estimation. Our key idea is to borrow the simulation data from an early stage (e.g., schematic-level simulation) to efficiently estimate the performance distributions at a late stage (e.g., post-layout simulation). BMF statistically models the correlation between early-stage and late-stage performance distributions by Bayesian inference. In addition, a convex optimization is formulated to solve the unknown late-stage performance distributions both accurately and robustly. Several circuit examples designed in a commercial 32 nm CMOS process demonstrate that the proposed BMF technique achieves up to 3.75X runtime speedup over the traditional kernel estimation method.

Abstraction of circuits is desirable for faster simulation and high-level system verification. In this paper, we present an algorithm that derives a Mealy machine from differential equations of a circuit by learning input-output trajectories. The key idea is adapted from Angluin's DFA (deterministic finite automata) learning algorithm [1] that learns a DFA from another DFA. Several key components of Angluin's algorithm are modified so that it fits in our problem setting, and the modified algorithm also provides a reasonable partitioning of the continuous state space as a by-product. We validate our algorithm on a latch circuit and an integrator circuit, and demonstrate that the resulting FSMs inherit important behaviors of original circuits.

We present a projection-based nonlinear model order reduction method, named model order reduction via quadratic-linear systems (QLMOR). QLMOR employs two novel ideas: 1) we show that nonlinear ordinary differential equations, and more generally differential-algebraic equations (DAEs) with many commonly encountered nonlinear kernels can be re-written equivalently in a special representation, quadratic-linear differential algebraic equations (QLDAEs), and 2) we perform a Volterra analysis to derive the Volterra kernels, and we adapt the moment-matching reduction technique of nonlinear model order reduction method (NORM)to reduce these QLDAEs into QLDAEs of much smaller size. Because of the generality of the QLDAE representation, QLMOR has significantly broader applicability than Taylor-expansion-based methodssince there is no approximation involved in the transformation from original DAEs to QLDAEs. Because the reduced model has only quadratic nonlinearities, its computational complexity is less than that of similar prior methods. In addition, QLMOR, unlike NORM, totally avoids explicit moment calculations, hence it has improved numerical stability properties as well. We compare QLMOR against prior methodson a circuit and a biochemical reaction-like system, and demonstrate that QLMOR-reduced models retain accuracy over a significantly wider range of excitation than Taylor-expansion-based methods. QLMOR, therefore, demonstrates that Volterra-kernel-based nonlinear MOR techniques can in fact have far broader applicability than previously suspected, possibly being competitive with trajectory-based methods (e.g., trajectory piece-wise linear reduced order modeling) and nonlinear-projection-based methods (e.g., maniMOR).

We present a new manifold construction and parameterization algorithm for model reduction approaches based on projection on manifolds. The new algorithm employs two key ideas: (1) we define an ideal manifold for nonlinear model reduction to be the solution of a set of differential equations with the property that the tangent space at any point on the manifold spans the same subspace as the low-order subspace (e.g., Krylov subspace generated by moment-matching techniques) of the linearized system; (2) we propose the concept of normalized integral curve equations, which are repeatedly solved to identify an almost-ideal manifold. The manifold constructed by our algorithm inherits the important property in that it covers important system responses such as DC and AC responses. It also preserves better local distance metrics on the manifold, thanks to the employment of normalized integral curve equations. To gauge the quality of the resulting manifold, we also derive an error bound of the moments of linearized systems, assuming moment-matching techniques are employed to generate low-order subspaces for linearized systems. The algorithm is also more systematic and generalizable to higher dimensions than the ad hoc procedure in. We illustrate the key ideas through a simple 2-D example. We also combine this new manifold construction and parameterization algorithm with maniMOR to generate reduced models for a quadratic nonlinear system and a CMOS circuit. Simulation results are provided, together with comparisons to full models as well as TPWL reduced models.

Oscillations and rhythmic activity are seen in natural and man-made systems. Dynamics of oscillators can be compactly described by phase domain models. Phase equations for periodic, single-frequency oscillators have been developed and utilized in analyzing oscillation phenomena that arise in electronic systems, circadian clocks, and the nervous system. We consider quasi-periodic oscillators and present a general phase model theory and numerical techniques for the construction of phase equations for multi-frequency oscillators. We demonstrate the utility of these phase equations in analyzing oscillators experiencing perturbations.

We extend the concept of timing/phase macromodels, previously established rigorously only for oscillators, to apply to general systems, both non-oscillatory and oscillatory. We do so by first establishing a solid foundation for the timing/phase response of any nonlinear dynamical system, then deriving a timing/phase macromodel via nonlinear perturbation analysis. The macromodel that emerges is a scalar, nonlinear time-varying equation that accurately characterizes the system's phase/timing responses. We establish strong links of this technique with projection frameworks for model order reduction. We then present numerical methods to compute the phase model. The computation involves a full Floquet decomposition — we discuss numerical issues that arise if direct computation of the monodromy matrix is used for Floquet analysis, and propose an alternative method that are numerically superior. The new method has elegant connections to the Jacobian matrix in harmonic balance method (readily available in most RF simulators). We validate the technique on several highly nonlinear systems, including an inverter chain and a firing neuron. We demonstrate that the new scalar nonlinear phase model captures phase responses under various types of input perturbations, achieving accuracies considerably superior to those of reduced models obtained using LTI/LPTV MOR methods. Thus, we establish a powerful new way to extract timing models of combinatorial/sequential systems and memory (e.g., SRAMs/DRAMs), synchronization systems based on oscillator enslaving (e.g., PLLs, injection-locked oscillators, CDR systems, neural processing, energy grids), signal-processing blocks (e.g., ADCs/DACs, FIR/IIR filters), etc.

We present a new projection-based nonlinear model order reduction method, named QLMOR (MOR via quadratic-linear systems). QL-MOR employs two novel ideas: (1) we show that DAEs (differential-algebraic equations) with many commonly-encountered nonlinear kernels can be re-written equivalently into a special format, QL-DAEs (quadratic-linear differential algebraic equations, i.e., DAEs that are quadratic in their state variables and linear in their inputs); (2) we adapt the moment-matching reduction technique of NORM[1] to reduce these QLDAEs into QLDAEs of much smaller size. Because of the generality of the QLDAE form, QLMOR has significantly broader applicability than Taylor-expansion based methods [2, 3, 1]. Importantly, QLMOR, unlike NORM, totally avoids explicit moment calculations (AiB terms), hence it has improved numerical stability properties as well. Because the reduced model has only quadratic nonlinearities (i.e., no cubic and higher-order terms), its computational complexity is less than that of similar prior methods[2, 3, 1]. We also prove that QLMOR-reduced models preserve local passivity, and provide an upper bound on the size of the QLDAEs derived from a polynomial system. We compare QLMOR against prior methods [2, 3, 1] on a circuit and a biochemical reaction-like system, and demonstrate that QLMOR-reduced models retain accuracy over a significantly wider range of excitation than Taylor-expansion based methods [2, 3, 1]. Indeed, QLMOR is able to reduce systems that Taylor-expansion based methods fail to reduce due to passivity loss and impracti-cally high computational costs. QLMOR therefore demonstrates that Volterra-kernel based nonlinear MOR techniques can in fact have far broader applicability than previously suspected, possibly being competitive with trajectory-based methods (e.g., TPWL [4]) and nonlinear-projection based methods (e.g., maniMOR [5]).

Failures and yield problems due to parameter variations have become a significant issue for sub-90-nm technologies. As a result, CAD algorithms and tools that provide designers the ability to estimate the effects of variability quickly and accurately are being urgently sought. The need for such tools is particularly acute for static RAM (SRAM) cells and integrated oscillators, for such circuits require expensive and high-accuracy simulation during design. We present a novel technique for fast computation of parametric yield. The technique is based on efficient, adaptive geometric calculation of probabilistic hypervolumes subtended by the boundary separating pass/fail regions in parameter space. A key feature of the method is that it is far more efficient than Monte-Carlo, while at the same time achieving better accuracy in typical applications. The method works equally well with parameters specified as corners, or with full statistical distributions; importantly, it scales well when many parameters are varied. We apply the method to an SRAM cell and a ring oscillator and provide extensive comparisons against full Monte-Carlo, demonstrating speedups of 100–1000×.

Previous model order reduction methods fit into the framework of identifying the low-order linear subspace and using the linear projection to project the full state space into the low-order subspace. Despite its simplicity, the macromodel might automatically include redundancies.