Modern high-speed links and I/O subsystems often employ sophisticated coding strategies to boost error resilience and achieve multi-Gb/s throughput. The end-to-end analysis of such systems, which involves accurate prediction of worst-case and stochastic eye diagrams, is a challenging problem. Existing techniques such as Peak Distortion Analysis (PDA) typically predict overly pessimistic eye diagrams because they do not take into account the coding strategies employed. Monte-Carlo methods, on the other hand, often predict overly optimistic eye diagrams, and they are also very time-consuming. As an alternative, we present BEE, an accurate and efficient computational technique that applies dynamic programming algorithms to predict realistic worst-case and stochastic eye diagrams in modern high-speed links and I/O subsystems - with neither excessive pessimism nor undue optimism. BEE is able to fully and correctly take into account many features underlying modern communications systems, including arbitrary high-level transmit-side coding schemes and strategies, as well as various low-level non-idealities introduced by the underlying channel(s), such as inter-symbol interference (ISI) and crosstalk, asymmetric rise/fall times, jitter, parameter variability, etc. Furthermore, BEE accurately captures the fact that different received bits typically have widely different eye diagrams when a channel is driven by correlated bitstreams generated by coding strategies. We demonstrate BEE on links involving (7,4)-Hamming and 8b/10b SERDES encoders, featuring channels that give rise to multiple reflections, dispersion, loss, and overshoot/undershoot. BEE successfully predicts actual worst case eye openings in all these real-world systems, which can be twice as large as the eye openings predicted by overly pessimistic methods like PDA. Also, BEE can be an order of magnitude faster (and much more reliable) than Monte-Carlo based eye estimation methods.

We describe the Berkeley Model and Algorithm Prototyping Platform (MAPP), designed to facilitate experimentation with numerical algorithms and models. MAPP is written entirely in MATLAB and is available as open source under the GNU GPL.

We present ABCD-NL, a technique that approximates non-linear analog circuits using purely Boolean models, to high accuracy. Given an analog/mixed-signal (AMS) system (e.g., a SPICE netlist), ABCD-NL produces a Boolean circuit representation (e.g., an And Inverter Graph, Finite State Machine, or Binary Decision Diagram) that captures the I/O behaviour of the given system, to near SPICE-level accuracy, without making any apriori simplifications. The Boolean models produced by ABCD-NL can be used for high-speed simulation and formal verification of AMS designs, by leveraging existing tools developed for Boolean/hybrid systems analysis (e.g., ABC [1]). We apply ABCD-NL to a number of SPICE-level AMS circuits, including data converters, charge pumps, comparators, non-linear signaling/communications sub-systems, etc. Also, we formally verify the throughput of an AMS signaling system - modelled in SPICE using 22nm BSIM4 transistors, Booleanized with high accuracy using ABCD-NL, and property-checked using ABC.

We present ABCD-L, a scalable technique for Analog/Mixed Signal (AMS) modelling/verification that captures the continuous dynamics of Linear Time-Invariant (LTI) systems, using purely Boolean approximations, to any desired level of accuracy. ABCD-L's models can be used in conjunction with existing techniques for Boolean synthesis/verification/fast logic simulation, or with hybrid systems frameworks, to represent LTI dynamics without incurring the penalty of adding continuous variables. Unlike existing state-enumeration approaches like DAE2FSM [1], ABCD-L scales practically linearly with system size. We apply ABCD-L to I/O links composed of RC/RLGC units, capturing important analog effects like inter-symbol interference, overshoot/undershoot, ringing, etc. -- all using purely Boolean models. We also present a continuous-time differential equalizer example, where ABCD-L accurately reproduces key design-relevant AMS metrics, including the eye diagram correction achieved by the circuit. Furthermore, for real-world LTI systems, we demonstrate that ABCD-L can be applied in conjunction with Model Order Reduction (MOR) techniques; we use this to produce accurate Boolean models of an industry-scale power grid network (with 25849 nodes) made available by IBM. We also demonstrate that Boolean simulation using ABCD-L's models offers considerable speed-up over standard circuit simulation using linear multi-step numerical methods.

The Shapley value---probably the most important normative payoff division scheme in coalitional games---has recently been advocated as a useful measure of centrality in networks. However, although this approach has a variety of real-world applications (including social and organisational networks, biological networks and communication networks), its computational properties have not been widely studied. To date, the only practicable approach to compute Shapley value-based centrality has been via Monte Carlo simulations which are computationally expensive and not guaranteed to give an exact answer. Against this background, this paper presents the first study of the computational aspects of the Shapley value for network centralities. Specifically, we develop exact analytical formulae for Shapley value-based centrality in both weighted and unweighted networks and develop efficient (polynomial time) and exact algorithms based on them. We empirically evaluate these algorithms on two real-life examples (an infrastructure network representing the topology of the Western States Power Grid and a collaboration network from the field of astrophysics) and demonstrate that they deliver significant speedups over the Monte Carlo approach. For instance, in the case of unweighted networks our algorithms are able to return the exact solution about 1600 times faster than the Monte Carlo approximation, even if we allow for a generous 10% error margin for the latter method.

With aggressive technology scaling and heightened variability, circuits such as SRAMs and DRAMs have become vulnerable to random telegraph noise (RTN). The bias dependence (i.e., non-stationarity), bi-directional coupling, and high inter-device variability of RTN present significant challenges to understanding its circuit-level effects. In this paper, we present two computer-aided design (CAD) tools, SAMURAI and MUSTARD, for accurately estimating the impact of non-stationary RTN on SRAMs and DRAMs. While traditional (stationary) analysis is often overly pessimistic (e.g., it overestimates RTN-induced SRAM failure rates), the predictions made by SAMURAI and MUSTARD are more reliable by virtue of non-stationary analysis.

We abstract the I/O functionality of continuous-time dynamical systems (e.g., SPICE netlists with combinational and sequential logic) as Finite State Machines (FSMs). This enables efficient simulation of large designs implemented with less-than-perfect devices and components, and also opens the door to formal verification of transistor-level designs against higher-level specifications. In particular, our automatically generated FSMs faithfully capture the behaviour of latches, flip-flops, and circuits constructed from them. Among other technical advances, we generalize an existing (binary-only) FSM-learning approach to arbitrary I/O alphabets, which empowers it to learn high-fidelity abstractions of multi-level-discretized, multi-input/multi-output systems. Our approach, when applied to correctly functioning latches and flip-flops, is able to learn compact, multi-input FSM abstractions whose predictions closely match SPICE simulations. In addition, we have also applied our technique to produce multi-level-discretized FSM representations of digital systems that nevertheless exhibit "analogish" traits, such as an over-clocked, error-prone D-flip-flop. For such circuits, the automatically learned FSM abstraction includes additional states that characterise "failure modes" of the circuit for specific input sequences (these failure modes are also confirmed by SPICE simulations). Finally, we demonstrate that our technique is also applicable to larger and more complex multi-input, multi-output systems; for example, we are able to automatically derive an accurate FSM abstraction of a 280-transistor (BSIM4), 0-to-5 increment/decrement counter.

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.

With aggressive technology scaling and heightened variability, SRAMs and DRAMs have become vulnerable to Random Telegraph Noise (RTN). The bias-dependent, random temporal nature of RTN presents significant challenges to understanding its effects on circuits. In this paper, we propose MUSTARD, a technique and tool for predicting the impact of RTN on SRAMs/DRAMs in the presence of variability. MUSTARD enables accurate, non-stationary, two-way-coupled, discrete stochastic RTN simulation seamlessly integrated with deterministic, continuous circuit simulation. Using MUSTARD, we are able to predict experimentally observed RTN-induced failures in SRAMs, and generate statistical characterisations of bit errors in SRAMs and DRAMs. We also present MUSTARD-generated results showing the effect of RTN on DRAM retention times.

In latest CMOS technologies, Random Telegraph Noise (RTN) has emerged as an important challenge for SRAM design. Due to rapidly shrinking device sizes and heightened variability, analytical approaches are no longer applicable for characterising the circuit-level impact of non-stationary RTN. Accordingly, this paper presents SAMURAI, a computational method for accurate, trap-level, non-stationary analysis of RTN in SRAMs. The core of SAMURAI is a technique called Markov Uniformisation, which extends stochastic simulation ideas from the biological community and applies them to generate realistic traces of non-stationary RTN in SRAM cells. To the best of our knowledge, SAMURAI is the first computational approach that employs detailed trap-level stochastic RTN generation models to obtain accurate traces of non-stationary RTN at the circuit level. We have also developed a methodology that integrates SAMURAI and SPICE to achieve a simulation-driven approach to RTN characterisation in SRAM cells under (a) arbitrary trap populations, and (b) arbitrarily time-varying bias conditions. Our implementation of this methodology demonstrates that SAMURAI is capable of accurately predicting non-stationary RTN effects such as write errors in SRAM cells.