Search

In recent years, there has been a lot of research into statistical static timing analysis (SSTA) to compute the critical path delay of a circuit under timing variation. In order to compute the true critical path delay, however, false paths that cannot be sensitized by any input vector must be identified first. Since SSTA is unable to capture the dynamic timing behavior of a circuit, it is completely blind to false paths, and thus it overestimates the circuit timing. In this paper, we propose a new concept of timing analysis approach called statistical dynamic timing analysis (SDTA), which is able to precisely express the statistical behavior of dynamic transitions at the output of gate into a compact form and to directly evaluate and propagate the expressions throughout the circuit, by which the false paths can be cleaned effectively. In addition, to be practical, we propose a couple of techniques that enable a fast computation of the SDTA. We tested the proposed approach on ISCAS benchmarks and carry skip adders under timing variation to show its accuracy in computing the distribution of the true critical path delay of a circuit. In summary, compared to the previous approach of false path-aware statistical timing analysis, our timing analysis technique is able to reduce the accuracy error in the mean and standard deviation of true critical path delay distribution from 9.8% to 1.9% and from 29.4% to -3.4\%, respectively. [ABSTRACT FROM AUTHOR]

Multirate digital signal processing (DSP) algorithms are often modeled with synchronous dataflow graphs (SDFGs). A lower iteration period implies a faster execution of a DSP algorithm. Retiming is a simple but efficient graph transformation technique for performance optimization, which can decrease the iteration period without affecting functionality. In this paper, we deal with two problems: feasible retiming—retiming a SDFG to meet a given iteration period constraint, and optimal retiming—retiming a SDFG to achieve the smallest iteration period. We present a novel algorithm for feasible retiming and based on that one, a new algorithm for optimal retiming, and prove their correctness. Both methods work directly on SDFGs, without explicitly converting them to their equivalent homogeneous SDFGs. Experimental results show that our methods give a significant improvement compared to the earlier methods. [ABSTRACT FROM PUBLISHER]

This paper presents a formal methodology for test generation from formal specifications. Our method can be used for test generation for critical faults in component-based designs. Test generation for critical faults is done entirely using formal specifications and therefore the theory inherently guarantees that a generated test will be applicable to any implementation of the specifications. The theory makes fault analysis possible at an abstract level of design where the complete logic is not specified. [ABSTRACT FROM AUTHOR]

When a multipattern scan-based test is applied at-speed to detect delay defects, it is necessary to change the primary input vectors at-speed. However, tester limitations can make this infeasible. The solution where the primary input vectors are held constant during the test reduces the fault coverage. An alternative solution is to store the primary input sequences of a multipattern test set on-chip and apply them at-speed from an on-chip memory. To support such a solution, this paper describes a procedure for computing a multipattern test set that requires a small number of different primary input sequences. Experimental results for single stuck-at faults and for transition faults show that a multipattern test set that detects all the detectable faults requires a number of primary input sequences that is significantly smaller than the number of tests. [ABSTRACT FROM AUTHOR]

Power grid verification has become an indispensable step to guarantee a functional and robust chip design. Vectorless power grid verification methods, by solving linear programming (LP) problems under current constraints, enable worst-case voltage drop predictions at an early stage of design when the specific waveforms of current drains are unknown. In this paper, a novel power grid verification algorithm based on hierarchical constraints is proposed. By introducing novel power constraints, the proposed algorithm generates more realistic current patterns and provides less pessimistic voltage drop predictions. The model order reduction-based coefficient computation algorithm reduces the complexity of formulating the LP problems from being proportional to steps to being independent of steps. Utilizing the special hierarchical constraint structure, the submodular polyhedron greedy algorithm dramatically reduces the complexity of solving the LP problems from over O(km^{3}) to roughly O(km\log km), where km is the number of variables. Numerical results have shown that the proposed algorithm provides less pessimistic voltage drop prediction while at the same time achieves dramatic speedup. [ABSTRACT FROM PUBLISHER]

This paper addresses the issue of automatically generating reduced order models of very large multidimensional systems. To tackle this problem we introduce an efficient parallel projection based model order reduction framework for parameterized linear systems. The underlying methodology is based on an automated multidimensional sample selection procedure that maximizes effectiveness in the generation of the projection basis. The parallel nature of the algorithm is efficiently exploited using both shared and distributed memory architectures. This leads to a highly scalable, automatic, and reliable parallel reduction scheme, able to handle very large systems depending on multiple parameters. In addition, the framework is general enough to provide a good approximation regardless of the model's representation or underlying nature, as will be demonstrated on a variety of benchmark examples. The method provides the potential to tackle, in an automatic fashion, extremely challenging models that would be otherwise difficult to address with existing sequential approaches. [ABSTRACT FROM PUBLISHER]

Approximate computing is an emerging trend in hardware and software design that leverages upon the inherent tolerance for inaccuracy in applications to optimize their power consumption, latency, and area. Due to the widespread usage of adders in digital hardware designs, numerous approximate adders, offering various error margins and area, latency and power constraints, have been proposed. Probabilistic error analysis of these adders holds a significant step in selecting an appropriate approximate adder for a given application. Traditionally, this analysis has been conducted using Monte-Carlo simulations or analytical analysis, which do not ascertain a sound and complete analysis. In order to overcome these limitations, we propose to use interactive theorem proving for error analysis of approximate adders. For this purpose, we present a higher-order-logic formalization of probability distributions and error related events encountered in approximate adders that comprise of subadder units, based on a probability theory formalization available in the HOL4 theorem prover. We also propose an algorithm for analyzing the probability of error as a metric for accurate comparison for high-speed, low-latency approximate adders with uniformly distributed inputs. For illustration purposes, we present the formal error analysis of three of the most widely acclaimed approximate adders, i.e., error tolerant adder-I, accuracy configurable adder, and generic accuracy configurable adder. [ABSTRACT FROM AUTHOR]

General purpose computing on graphical processing units (GPGPU) is a paradigm shift in computing that promises a dramatic increase in performance. GPGPU also brings an unprecedented level of complexity in algorithmic design and software development. In this paper, we present an efficient parallel fault simulator, FSimGP^2, that exploits the high degree of parallelism supported by a state-of-the-art graphic processing unit (GPU) with the NVIDIA compute unified device architecture. A novel 3-D parallel fault simulation technique is proposed to achieve extremely high computation efficiency on the GPU. Global communication is minimized by concentrating as much work as possible on the local device's memory. We present results on a GPU platform from NVIDIA (a GeForce GTX 285 graphics card) that demonstrate a speedup of up to 63\times and 4\times compared to two other GPU-based fault simulators and up to 95\times over a state-of-the-art algorithm on conventional processor architectures. [ABSTRACT FROM AUTHOR]

Photonic technology is becoming an increasingly attractive solution to the problems facing today's electronic chip-scale interconnection networks. Recent progress in silicon photonics research has enabled the demonstration of all the necessary optical building blocks for creating extremely high-bandwidth density and energy-efficient links for on-chip and off-chip communications. From the feasibility and architecture perspective however, photonics represents a dramatic paradigm shift from traditional electronic network designs due to fundamental differences in how electronics and photonics function and behave. As a result of these differences, new modeling and analysis methods must be employed in order to properly realize a functional photonic chip-scale interconnect design. In this paper, we present a methodology for characterizing and modeling fundamental photonic building blocks which can subsequently be combined to form full photonic network architectures. We also describe a set of tools which can be utilized to assess the physical-layer and system-level performance properties of a photonic network. The models and tools are integrated in a novel open-source design and simulation environment. We present a case study of two different photonic networks-on-chip to demonstrate how our improved understanding and modeling of the physical-layer details of photonic communications can be used to better understand the system-level performance impact. [ABSTRACT FROM AUTHOR]

The translation of emerging application concepts that exploit resistive random access memory (ReRAM) into large-scale practical systems requires realistic yet computationally efficient device models. Here, we present a ReRAM model, where device current–voltage characteristics and resistive switching rate are expressed as a function of: 1) bias voltage and 2) initial resistive state (RS). The model versatility is validated on detailed characterization data, for both filamentary valence change memory and nonfilamentary ReRAM technologies, where device resistance is swept across its operating range using multiple input voltage levels. Furthermore, the proposed model embodies a window function which features a simple mathematical form analytically describing RS response under constant bias voltage as extracted from physical device response data. Its Verilog-A implementation captures the ReRAM memory effect without requiring integration of the model state variable, making it suitable for fast and/or large-scale simulations and overall interoperable with current design tools. [ABSTRACT FROM AUTHOR]

Fast and accurate thermal analysis is crucial for determining the propagation of heat and tracking the formation of hotspots in integrated circuits (ICs). Existing academic thermal analysis tools primarily use compact models to accelerate thermal simulations but are limited to linear problems on relatively simple circuit geometries. The Manchester Thermal Analyzer (MTA) is a comprehensive tool that allows for fast and highly accurate linear and nonlinear thermal simulations of complex physical structures including the IC, the package, and the heatsink. The MTA is targeted for 2.5/3-D IC designs but also handles standard planar ICs. The MTA discretizes the heat equation in space using the finite element method and performs the time integration with unconditionally stable implicit time stepping methods. To improve the computational efficiency without sacrificing accuracy, the MTA features adaptive spatiotemporal refinement. The large-scale linear systems that arise during the simulation are solved with fast preconditioned Krylov subspace methods. The MTA supports thermal analysis of realistic integrated systems and surpasses the computational capabilities and performance of existing academic thermal simulators. For example, the simulation of a processor in a package attached to a heat sink, modeled by a computational grid consisting of over 3 million nodes, takes less than 3 min. The MTA is fully parallel and publicly available. [ABSTRACT FROM AUTHOR]

One major issue that hinders the use of performance analysis in industrial design processes is the pessimism inherent to any analysis technique that applies to realistic system models. Indeed, such analyses may conservatively declare unschedulable systems that will in fact never miss any deadlines. We advocate the need to compute not only tight upper bounds on worst-case behaviors but also tight lower bounds. As a first step, we focus on uniprocessor systems executing a set of sporadic or periodic hard real-time task chains. Each task has its own priority, and the chains are scheduled according to the fixed-priority pre-emptive scheduling policy. Computing the worst-case end-to-end latency (WCEL) of each chain is complex because of the intricate relationship between the task priorities. Compared to the state of the art, our analysis provides upper bounds on the WCEL in the more general case of asynchronous task chains, and also provides lower bounds on the WCEL both for synchronous and asynchronous chains. Our computed lower bounds correspond to actual system executions exhibiting a behavior that is as close to the worst case as possible, while all other approaches rely on simulations. Extensive experiments show the relevance of lower bounds on the worst-case behavior for the industrial design of real-time embedded systems. [ABSTRACT FROM AUTHOR]

Deep neural networks have seen tremendous success for different modalities of data including images, videos, and speech. This success has led to their deployment in mobile and embedded systems for real-time applications. However, making repeated inferences using deep networks on embedded systems poses significant challenges due to constrained resources (e.g., energy and computing power). To address these challenges, we develop a principled co-design approach. Building on prior work, we develop a formalism referred as coarse-to-fine networks (C2F Nets) that allow us to employ classifiers of varying complexity to make predictions. We propose a principled optimization algorithm to automatically configure C2F Nets for a specified tradeoff between accuracy and energy consumption for inference. The key idea is to select a classifier on-the-fly whose complexity is proportional to the hardness of the input example: simple classifiers for easy inputs and complex classifiers for hard inputs. We perform comprehensive experimental evaluation using four different C2F Net architectures on multiple real-world image classification tasks. Our results show that optimized C2F Net can reduce the energy delay product by 27% to 60% with no loss in accuracy when compared to the baseline solution, where all predictions are made using the most complex classifier in C2F Net. [ABSTRACT FROM AUTHOR]

The task graph cost-optimal scheduling problem consists in scheduling a certain number of interdependent tasks onto a set of heterogeneous processors (characterized by idle and running rates per time unit), minimizing the cost of the entire process. This paper provides a novel formulation for this scheduling puzzle, in which an optimal solution is computed through a sequence of binate covering problems, hinged within a bounded model checking paradigm. In this approach, each covering instance, providing a min-cost trace for a given schedule depth, can be solved with several strategies, resorting to minimum-cost satisfiability solvers or pseudo-Boolean optimization tools. Unfortunately, all direct resolution methods show very low efficiency and scalability. As a consequence, we introduce a specialized method to solve the same sequence of problems, based on a traditional all-solution SAT solver. This approach follows the “circuit cofactoring” strategy, as it exploits a powerful technique to capture a large set of solutions for any new SAT counter-example. The overall method is completed with a branch-and-bound heuristic which evaluates lower and upper bounds of the schedule length, to reduce the state space that has to be visited. Our results show that the proposed strategy significantly improves the blind binate covering schema, and it outperforms general purpose state-of-the-art tools. [ABSTRACT FROM AUTHOR]

Considerable effort has been expended in the electronic design automation community in trying to cope with the statistical timing problem. Most of this effort has been aimed at generalizing the static timing analyzers to the statistical case. On the other hand, detailed transistor-level simulations of the critical paths in a circuit are usually performed at the final stage of performance verification. We describe a transistor-level Monte Carlo (MC) technique which makes final transistor-level timing verification practically feasible. The MC method is used as a golden reference in assessing the accuracy of other timing yield estimation techniques. However, it is generally believed that it can not be used in practice as it requires too many costly transistor-level simulations. We present a novel approach to constructing an improved MC estimator for timing yield which provides the same accuracy as standard MC but at a cost of much fewer transistor-level simulations. This improved estimator is based on a unique combination of a variance reduction technique, importance sampling, and a cheap but approximate gate delay model. The results we present demonstrate that our improved yield estimator achieves the same accuracy as standard MC at a cost reduction reaching several orders of magnitude. [ABSTRACT FROM AUTHOR]

We present a numerical modeling and simulation paradigm for multidomain, multiphysics systems with components modeled both in a lumped and distributed manner. The lumped components are modeled with a system of differential-algebraic equations (DAEs), whereas the possibly nonlinear distributed components that may belong to different physical domains are modeled using partial differential equations (PDEs) with associated boundary conditions. We address a comprehensive suite of problems for nonlinear coupled DAE–PDE systems including 1) transient simulation; 2) periodic steady-state (PSS) analysis formulated as a mixed boundary value problem that is solved with a hierarchical spectral collocation technique based on a joint Fourier–Chebyshev representation, for both forced and autonomous systems; 3) Floquet theory and analysis for coupled linear periodically time-varying DAE–PDE systems; 4) phase noise analysis for multidomain oscillators; and 5) efficient parameter sweeps for PSS and noise analyses based on first-order and pseudo-arclength continuation schemes. All of these techniques, implemented in a prototype simulator, are applied to a substantial case study: a multidomain feedback oscillator composed of distributed and lumped components in two physical domains, namely, a nano-mechanical beam resonator operating in the nonlinear regime, an electrical delay line, an electronic amplifier and a sensor-actuator for the transduction between the two physical domains. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Applying modern data mining in electronic design automation and test has become an area of growing interest in recent years. This paper reviews some of the recent developments in the area. It begins by introducing several key concepts in machine learning and data mining, followed by a review of different learning approaches. Then, the experience of developing a practical data mining application is described, including promises demonstrated through positive results based on industrial settings and challenges explained in the respective application contexts. Future research directions are summarized at the end. [ABSTRACT FROM PUBLISHER]

Parametric yield estimation is a critical task for design and validation of analog and mixed-signal (AMS) circuits. However, the computational cost for yield estimation based on Monte Carlo (MC) analysis is often prohibitively high, especially when multiple circuit performances and/or environmental corners (e.g., voltage and temperature corners) are considered. In this paper, a novel statistical method named correlation-aided yield estimation (C-YES) is proposed to reduce the computational cost for parametric yield estimation. Our proposed approach exploits the fact that multiple circuit performances over different environmental corners are often correlated. Hence, we can accurately predict the performance value at one corner from the simulation results for other performances and/or corners. Based upon this observation, instead of running a large number of MC simulations to cover all performances and corners, an efficient algorithm is developed to select a small set of the most “informative” simulations that should be performed for yield estimation. Our numerical experiments show that for parametric yield estimation with multiple circuit performances and environmental corners, C-YES achieves 6.5– 9.3 \boldsymbol \times runtime speedups over other conventional methods. [ABSTRACT FROM PUBLISHER]

A new design methodology for radiofrequency circuits is presented that includes electromagnetic (EM) simulation of the inductors into the optimization flow. This is achieved by previously generating the Pareto-optimal front (POF) of the inductors using EM simulation. Inductors are selected from the Pareto front and their S -parameter matrix is included in the circuit netlist that is simulated using an RF simulator. Generating the EM-simulated POF of inductors is computationally expensive, but once generated, it can be used for any circuit design. The methodology is illustrated both for a single-objective and a multiobjective optimization of a low noise amplifier. [ABSTRACT FROM AUTHOR]

Post-silicon validation deals with detection and diagnosis of errors that, due to existing limitations in pre-silicon verification, escape to the silicon prototypes and need to be fixed before committing to high-volume manufacturing. Electrical errors, such as those caused by cross-talk or power droops, are particularly difficult to catch during the pre-silicon phase because of the insufficient accuracy of device models, which is often traded-off against simulation time. This challenge is further aggravated by the rising number of voltage domains, especially if subtle errors are excited in unique electrical states. In fact these electrically-induced subtle errors most commonly manifest in the logic domain as bit-flips and, to the best of our knowledge, there are no systematic methods for designing embedded hardware monitors for generic logic blocks that can detect bit-flips with low detection latency. Moreover, unlike pre-silicon verification and manufacturing test that benefit from well-defined and universally accepted coverage metrics, there is no generic metric from which confidence can be implied at the end of post-silicon validation. Toward these goals, we present a method that relies on design invariants (assertions) that are ranked based on their potential to detect bit-flips. We also introduce two metrics bit-flip coverage estimate and flip-flop coverage estimate that can be used to assess the quality of the selected assertions, and, in general, the effectiveness of the post-silicon validation process. [ABSTRACT FROM PUBLISHER]

This article studies the robust deep stereo vision in autonomous driving systems and counteracting adversarial attacks. The autonomous system operation requires real-time processing of measurement data which often contain significant uncertainties and noise. Adversarial attacks have been widely studied to simulate these perturbations in recent years. To counteract the practical attacks in autonomous systems, novel methods based on simulated attacks are proposed in this article. Univariate and multivariate functions are adopted to represent the relationships between the left and right input images and the deep stereo model. A stereo regularizer is proposed to guide the model to learn the implicit relationship between the images and characterize the loss function’s local smoothness. The attacks are generated by maximizing the regularizer term to break the linearity and smoothness. The model then defends the attacks by minimizing the loss and regularization terms. Two techniques are developed in this article. The first technique, SmoothStereo, explores the basic knowledge from the physical world and smoothness, while the second technique, SmoothStereoV2, improves SmoothStereo through leveraging the smooth activation functions during the defense. SmoothStereoV2 can learn and utilize the gradient information concerning the attacks. The gradients of the smooth activation functions can handle attacks for improving the model robustness. Numerical experiments on KITTI datasets demonstrate that the proposed methods offer superior performance. [ABSTRACT FROM AUTHOR]

The ubiquitous application of deep neural networks (DNNs) has led to a rise in demand for artificial intelligence (AI) accelerators. For example, the tensor processing unit from Google–based on a systolic array–and its variants are of considerable interest for DNN inferencing using AI accelerators. This article studies the problem of classifying structural faults in such an accelerator based on their functional criticality. We first analyze pin-level faults in the processing elements (PEs) of a systolic array. Simulation results for the LeNet network with 8-bit fixed-point, 16-bit floating-point (FP), and 32-bit FP data paths applied to the MNIST dataset show that over 93% of the pin-level structural faults in a PE are functionally benign. We present a greedy iterative framework for determining the criticality of stuck-at faults in a PE netlist and analyze the limitations of criticality analysis methods based on repeated fault simulations. We next present a scalable two-tier machine-learning (ML)-based method to assess the functional criticality of stuck-at faults in a computationally efficient manner. We address the problem of minimizing misclassification by utilizing generative adversarial networks (GANs). Two-tier ML/GAN-based criticality assessment leads to less than 1% test escapes during functional criticality evaluation of structural faults. [ABSTRACT FROM AUTHOR]

Memristor-based accelerator (MBA) has demonstrated its capability in accelerating matrix-vector multiplication (MVM) with high performance and energy efficiency. However, it is hard to determine whether and how well an application can benefit from MBAs in a heterogeneous computing architecture. In this article, we propose a simulation framework called MHSim to evaluate the energy efficiency and performance of applications running with both MBAs and CPUs. MHSim provides flexible system-level interfaces and circuit-level simulation models for designers to configure heterogeneous computing architectures. We design a general-purpose MBA which enables floating-point computation models for general matrix-matrix multiplication (GEMM). Our simulation framework can quantify the performance and energy efficiency of different MBA architectures for various applications. We validate our simulation framework with SPICE and evaluate the accuracy and performance of MBAs via several case studies. Experimental results demonstrate that the deviations of energy consumption and latency are only 0.47% and 0.49% on average compared with SPICE-based simulation. [ABSTRACT FROM AUTHOR]

Since Google proposed Transformer in 2017, it has made significant natural language processing (NLP) development. However, the increasing cost is a large amount of calculation and parameters. Previous researchers designed and proposed some accelerator structures for transformer models in field-programmable gate array (FPGA) to deal with NLP tasks efficiently. Now, the development of Transformer has also affected computer vision (CV) and has rapidly surpassed convolution neural networks (CNNs) in various image tasks. And there are apparent differences between the image data used in CV and the sequence data in NLP. The details in the models contained with transformer units in these two fields are also different. The difference in terms of data brings about the problem of the locality. The difference in the model structure brings about the problem of path dependence, which is not noticed in the existing related accelerator design. Therefore, in this work, we propose the ViA, a novel vision transformer (ViT) accelerator architecture based on FPGA, to execute the transformer application efficiently and avoid the cost of these challenges. By analyzing the data structure in the ViT, we design an appropriate partition strategy to reduce the impact of data locality in the image and improve the efficiency of computation and memory access. Meanwhile, by observing the computing flow of the ViT, we use the half-layer mapping and throughput analysis to reduce the impact of path dependence caused by the shortcut mechanism and fully utilize hardware resources to execute the Transformer efficiently. Based on optimization strategies, we design two reuse processing engines with the internal stream, different from the previous overlap or stream design patterns. In the stage of the experiment, we implement the ViA architecture in Xilinx Alveo U50 FPGA and finally achieved ~5.2 times improvement of energy efficiency compared with NVIDIA Tesla V100, and 4–10 times improvement of performance compared with related accelerators based on FPGA, that obtained nearly 309.6 GOP/s computing performance in the peek. [ABSTRACT FROM AUTHOR]

As the artificial intelligence and Internet of Things (AIoT) develop rapidly, the deployment of artificial neural networks in edge computing is becoming significant with great challenge. The binarized convolutional neural network (BCNN) is one of the most widely adopted light-weight ANNs in AIoT, which can achieve the balance of system accuracy and hardware resource consumption, compared to others. To achieve high power and area efficiency in BCNN deployment, many approximate computing (AxC) techniques are integrated to make full use of the resilience of BCNN. As the research focused on the integration of AxC in circuit design, the design of AxC itself is not fully considered when applied to specific applications or domains. Based on circuit-architecture-system co-design, this article proposes an efficient BCNN deployment method, including a quality-circuit co-design method for approximate adder generation, a quality-aware intercompensation approach for addition tree, and a computing quality involved retraining approach for BCNN deployment. Experimental results show that the proposed quality model can achieve 86.43% in average accuracy while evaluating nine types of typical approximate adders. The proposed method is conducted on the applications of keyword spotting of GSCD, MNIST, and CIFAR-10, and we can further rise the approximation degree by 50%–75%, while reducing the accuracy by less than 1%. [ABSTRACT FROM AUTHOR]

Random forests (RFs) use a collection of decision trees (DTs) to perform the classification or regression. RFs are adopted in a wide variety of machine learning (ML) applications, and they are finding increasing use also in scenarios at the extreme edge of the Internet of Things (TinyML) where memory constraints are particularly tight. This article addresses the optimization of the computational and storage costs for running DTs on the microcontroller units (MCUs) typically deployed in TinyML scenarios. We introduce three alternative DT kernels optimized for memory- and compute-limited MCUs, providing insight into the key memory-latency tradeoffs on an open-source RISC-V platform. We identify key bottlenecks and demonstrate that SW optimizations enable up to significant memory footprint and latency decrease. Experimental results show that the optimized kernels achieve up to 4.5 $\mu \text{s}$ latency, $4.8\times $ speedup, and 45% storage reduction against the widely-adopted naive DT design. We carry out a detailed performance and energy cost analysis of various optimized DT variants: the best approach requires just 8 instructions and 0.155 pJ per decision. [ABSTRACT FROM AUTHOR]

Federated learning (FL) has been recognized as a promising collaborative on-device machine learning method in the design of Internet of Things (IoT) systems. However, most existing FL methods fail to deal with IoT applications that contain a variety of IoT devices equipped with different types of neural network (NN) models. This is because traditional FL methods assume that local models on devices should have the same architecture as the global model on cloud. To address this problem, we propose a novel framework named PervasiveFL that enables efficient and effective FL among heterogeneous IoT devices. Without modifying original local models, PervasiveFL installs one lightweight NN model named modellet on each device. By using the deep mutual learning (DML) and our entropy-based decision gating (EDG) method, modellets and local models can selectively learn from each other through soft labels using locally captured data. Meanwhile, since modellets are of the same architecture, the learned knowledge by modellets can be shared among devices in a traditional FL manner. In this way, PervasiveFL can be pervasively applied to any heterogeneous IoT system. Comprehensive experimental results on four well-known datasets show that PervasiveFL can not only pervasively enable FL among heterogeneous devices within a large-scale IoT system, but also significantly enhance the inference accuracy of heterogeneous IoT devices with low communication overhead. [ABSTRACT FROM AUTHOR]

This article considers a setting where embedded devices are used to acquire and classify images. Because of limited computing capacity, embedded devices rely on a parsimonious classification model with uneven accuracy. When local classification is deemed inaccurate, devices can decide to offload the image to an edge server with a more accurate but resource-intensive model. Resource constraints, e.g., network bandwidth, however, require regulating such transmissions to avoid congestion and high latency. This article investigates this offloading problem when transmissions regulation is through a token bucket, a mechanism commonly used for such purposes. The goal is to devise a lightweight, online offloading policy that optimizes an application-specific metric (e.g., classification accuracy) under the constraints of the token bucket. This article develops a policy based on a deep $Q$ -network (DQN), and demonstrates both its efficacy and the feasibility of its deployment on embedded devices. Of note is the fact that the policy can handle complex input patterns, including correlation in image arrivals and classification accuracy. The evaluation is carried out by performing image classification over a local testbed using synthetic traces generated from the ImageNet image classification benchmark. Implementation of this work is available at https://github.com/qiujiaming315/edgeml-dqn. [ABSTRACT FROM AUTHOR]

Guaranteeing timing constraints for parallel real-time applications deployed on multicore platforms is challenging, especially for applications containing non-preemptive execution blocks, that suffer from priority inversions. In this article, we propose to model such applications using a sporadic directed acyclic graph (DAG) model where preemption may take place only between the nodes of a DAG task. We present a new method for response-time analysis of such tasks scheduled with the global fixed-priority scheduling policy. We show that our method outperforms the state-of-the-art techniques significantly in terms of resource utilization in experimental evaluations using both benchmark and randomly generated task sets. We also present a method to deal with global EDF scheduling, which is a new technique proposed for response time analysis of sporadic DAG tasks with non-preemptive nodes. [ABSTRACT FROM AUTHOR]

Fully formal verification of perception models is likely to remain challenging in the foreseeable future, and yet these models are being integrated into safety-critical control systems. We present a practical method for reasoning about the safety of such systems. Our method is based on systematically constructing approximations of perception models from system-level safety requirements, data, and program analysis of the modules that are downstream from perception. These approximations have some desirable properties like being low-dimensional, intelligible, and tractable. The closed-loop system, with the approximation substituting the actual perception model, is verified to be safe. Establishing the formal relationship between the actual and the approximate perception models remains well beyond available verification techniques. However, we do provide a useful empirical measure of their closeness called precision. Overall, our method can tradeoff the size of the approximation against precision. We apply the method to two significant case studies: 1) a vision-based lane tracking controller for an autonomous vehicle and 2) a controller for an agricultural robot. We show how the generated approximations for each system can be composed with the downstream modules and be verified using program analysis tools like CBMC. Detailed evaluations of the impacts of size, and the environmental parameters (e.g., lighting, road surface, and plant type) on the precision of the generated approximations suggest that the approach can be useful for realistic control systems. [ABSTRACT FROM AUTHOR]

Side-channel attacks are powerful attacks for retrieving secret data by exploiting physical measurements, such as power consumption or electromagnetic emissions. Masking is a popular countermeasure as it can be proven secure against an attacker model. In practice, software-masked implementations suffer from a security reduction due to a mismatch between the considered leakage sources in the security proof and the real ones, which depend on the microarchitecture. We propose ARMISTICE, a framework for formally verifying the absence of leakage in first-order masked implementations taking into account modeled microarchitectural sources of leakage. As a proof of concept, we present the modeling of an Arm Cortex-M3 core from its RTL description and leakage test vectors, as well as the modeling of the memory of an STM32F1 board, exclusively using leakage test vectors. We show that, with these models, ARMISTICE pinpoints vulnerable instructions in real-world masked implementations and helps the design of masked software implementations which are practically secure. [ABSTRACT FROM AUTHOR]

Bayesian optimization (BO) is popular for a analog circuit sizing problem recently. However, BO can only work well in small-scale circuit. Scaling BO to common circuit optimization (typically dimension > 10) is difficult due to the curse of dimensionality. In this article, we proposed a new BO algorithm (cBO), which can scale BO to more larger scale circuit and improve the optimization result. First, according to the fact that a specification of the analog integrated circuit is mainly determined by a few transistors, dropout strategy is adopted in our algorithm. At each iteration, only a subset of selected variables to be optimized. A variables selection strategy based on mutual information analysis and a new fill-in strategy are proposed. Second, the $g_{m}/I_{D}$ methodology-based optimization strategy is proposed. Optimization variables are not width and the length of transistors, but $g_{m}/I_{D}$ , $I_{D}$ and length. $g_{m}$ , $I_{D}$ and $g_{m}/I_{D}$ have a direct relationship to circuit performance. This is equivalent to search in circuit feature space, which could achieve better performance and handle constraints more easily. Four commonly used circuits, including low dropout regulator, two stage amplifiers, Bandgap voltage reference (VR), and VR are used for validation. Compared with other high-dimensional BO, common BO, and commercial tools (Cadence ADE_GXL), the proposed algorithm is found to produce the best optimization result and best stability. And, the ablation study shows the effectiveness and efficiency of two ingredients of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Deep neural networks (DNNs) achieved great cognitive performance at the expense of a considerable computation workload. To relieve the computational burden, many optimization works are developed to reduce the model redundancy by identifying and removing insignificant model components, such as weight sparsity and filter pruning methods. However, these works only evaluate model components’ static significance with parameter information, ignoring their dynamic interaction with external inputs. Specifically, due to the difference in per-input features, the model components’ significance can dynamically change and, thus, the static methods can only achieve suboptimal performance. Focusing on this aspect, we propose a dynamic DNN optimization framework in this work. Based on the neural network attention mechanism, we propose a comprehensive dynamic optimization framework, including 1) testing-phase dynamic feature map pruning; 2) training-phase optimization by training with targeted dropout; and 3) deployment-phase one-for-all (OFA) model adaptability enhancement. By providing a holistic dynamic testing, training, and deployment co-optimization framework, our work has the following benefits: first, it can accurately identify and aggressively remove per-input feature redundancy by considering the model-input interaction and involving the channel/column-wise pruning flexibility; meanwhile, the training-testing co-optimization favors the dynamic pruning and helps maintain the model accuracy even with a very high feature pruning ratio. Finally, the deployment enhancement provides one unified OFA model to support full-spectrum feature sparsity ratios. The unified model can be dynamically reconfigured to meet different resource budgets without any retraining cost, and thus provide significant deployment flexibility. Extensive experiments show that our method could bring 37.4%–54.5% floating-point operations reduction with negligible accuracy drop on various test benchmarks. Meanwhile, the OFA deployment optimization enables us to use one model to support at most ten different resource constraints without any retraining cost. [ABSTRACT FROM AUTHOR]

The real-time coscheduling problem, where tasks may have multiple phases executing on different types of processors, is known to be hard. The (already hard) self-suspending task scheduling simplifies the coscheduling problem by assuming that the latency a task may experience on the other type of processors is naturally bounded, which is unfortunately not true in practice. In this article, we present a novel analysis technique, namely, the vertical view analysis, for analyzing the schedulability of coscheduling sporadic tasks under global earliest-deadline-first (GEDF) on a heterogeneous multiprocessor consisting of two types of processors. We derive both hard (no deadline miss) and soft (bounded response times) real-time utilization-based tests. To the best of our knowledge, these results are the first-of-its-kind for the coscheduling problem and may allow real-time schedulability analysis to be carried out on more practical scenarios under heterogeneous computing. [ABSTRACT FROM AUTHOR]

Applications with adaptability are widely available on the edge devices with energy harvesting capabilities. For their runtime quality optimization, however, current approaches cannot tackle the variations of quality modeling and harvested energy simultaneously. Therefore, in this article, we are the first to propose a deep reinforcement learning (DRL)-based dynamic voltage frequency scaling (DVFS) method that optimizes the application execution quality of energy harvesting edge devices to mitigate the variations. First, we propose a baseline DRL formulation that novelly migrates the objective of quality maximization into a reward function and constructs a DRL quality agent. Second, we devise a long short-term memory (LSTM)-based selector that performs DRL quality agent selection based on the energy harvesting history. Third, we further propose two optimization methods to alleviate the nonnegligible overhead of DRL computations: 1) an improved thinking-while-moving concurrent DRL scheme to compromise the “state drifting” issue during the DRL decision process and 2) a variable interstate duration decision scheme that compromises the DVFS overhead incurred in each action taken. The experiments take an adaptive stereo matching application as a case study. The results show that the proposed DRL-based DVFS method on average achieves 17.9% runtime reduction and 22.05% quality improvement compared to state-of-the-art solutions. [ABSTRACT FROM AUTHOR]

In recent years, convolutional neural networks (CNNs) have achieved significant advancements in various fields. However, the computation and storage overheads of CNNs are overwhelming for Internet-of-Things devices. Both network pruning algorithms and hardware accelerators have been introduced to empower CNN inference at the edge. Network pruning algorithms reduce the size and computational cost of CNNs by regularizing unimportant weights to zeros. However, existing works lack intrakernel structured types to tradeoff between sparsity and hardware efficiency, and the index storage for irregularly pruned networks is significant. Hardware accelerators leverage the sparsity of pruned CNNs to improve energy efficiency. However, their process element (PE) utilization rate is low because of uneven sparsity among input convolutional kernels. To overcome these problems, we propose PACA: a Pattern pruning Algorithm and Channel-fused high PE utilization Accelerator for CNNs. It includes three parts: a pattern pruning algorithm to explore the intrakernel sparsity type and reduce the index storage, a channel-fused hardware architecture to reduce the PEs’ idle rate and improve the performance, and a heuristic and taboo search-based smart fusion scheduler to analyze the idle PE problem and schedule the channel fusion in hardware. To demonstrate the effectiveness of PACA, we have implemented the software parts by Python and the hardware architecture by RTL codes. Experimental results on various datasets show that compared with an existing work, PACA can reduce the index storage overhead by $3.47\times $ – $5.63\times $ with 3.85–9.12 average patterns, and it can improve the hardware performance by $2.01\times $ – $5.53\times $ because of PEs’ idle rate reduction. [ABSTRACT FROM AUTHOR]

A methodology to create and develop electrical compact models for memristive devices is presented. It comprises a six-step algorithm that uses experimental data of memristive devices in order to obtain a compact model suitable for circuit-level simulations. The model methodology makes use of the definition of the intrinsic variables of memristive systems, to obtain the state map that describes the system, from which the mathematical expressions of the model are obtained. In order to illustrate the usage of the algorithm, a compact memristive model is developed by using experimental data from a TiO2-based resistive switching (RS) device. The resulting mathematical model is compared to the experimental data by computing the mean absolute percentage error (MAPE) between both, which results in 11%, and reduces to 6% after a piecewise approach. The circuit-level representation is implemented using a SPICE macromodel and a Verilog-A module, from which the memristive behavior is also properly reproduced. [ABSTRACT FROM AUTHOR]

Logic diagnosis to support yield improvement requires the collection of fail data. The full fail data for a faulty unit consist of the tests and observable outputs where the faulty unit produces faulty values. The volume of fail data that needs to be collected can be excessive. A recent solution is to use only pass/fail data for as many tests as possible. With pass/fail data for a test, the full fail data is replaced with a single bit that indicates whether the faulty unit passed or failed the test. However, with conventional scan-based tests, some tests require the full fail data to preserve the diagnostic quality of the test set. This article observes that the use of scan-based tests under bounded transparent-scan increases the diagnostic quality achievable using only pass/fail data. The article describes a test generation procedure for bounded transparent scan that uses only pass/fail data, and targets the same diagnostic quality as a conventional scan-based test set with full fail data. The experimental results demonstrate that, for many of the benchmark circuits considered, a bounded transparent-scan test set with pass/fail data matches the diagnostic quality of a conventional scan-based test set with full fail data. [ABSTRACT FROM AUTHOR]

In order to perform accurate parasitic extraction, foundries must provide the cross section profile of devices, and IP vendors must provide sufficient layout information. However, foundries and IP vendors are increasingly reluctant to reveal such sensitive information, especially for advanced devices. Therefore, the industry is faced with the following challenges: 1) foundries/IP vendors need to protect their trade secrets; 2) electronic design automation vendors need to integrate foundry data into extraction tools; and 3) IC designers need to have the accurate parasitic data. In this paper, we propose an innovative and practical solution to these challenges, by building a macro model around any region in 2-D/3-D on a circuit where foundries or IP vendors wish to hide information, yet the macro model allows accurate capacitance extraction inside and outside of the region. We first give algorithms to construct the macro model. Then, we describe how existing extraction algorithms can interface with the macro model to perform extraction for the entire circuit at the same accuracy as if complete information was given. The macro model can be used in finite difference method/finite element method and floating random walk, due to an equivalence theorem we proved. Finally, we propose the concept of equivalent profile and describe how to find one based on the macro model. Experimental results show the macro model can be efficiently constructed and used to produce accurate capacitance extraction. [ABSTRACT FROM AUTHOR]

We present deflection routing network on chip simulator (DNOC), a network-on-chip simulator. DNOC is primarily a deflection routing simulator, it simulates custom network topologies with detailed deflection router models, and a basic virtual channel router. DNOC can generate various statistics, such as network latency and power. We evaluate the simulator in three typical use cases. In stand-alone simulation, synthetic traffic generators are used to offer load to the network. In synchronous co-simulation, the simulator is integrated as a module within a larger system simulator with synchronization every simulated cycle. In the faster model-based co-simulation mode, a latency model is built, and retuned periodically at longer time intervals. We demonstrate co-simulation by running applications from the Rodinia and SPLASH-2 benchmark sets on mesh variants. DNOC is also able to run on multicore processors, speeding up the simulation of large networks. [ABSTRACT FROM AUTHOR]

The random telegraph noise (RTN) is becoming more serious in advanced technologies. Due to the unpredictability of the physical phenomenon, RTN is a good randomness source for true random number generators (TRNG). In this paper, we build fundamental randomness models for TRNGs based on single trap- and multiple traps-induced RTN. We theoretically derive the autocorrelation coefficient, bias, and bit rate for RTN-based TRNGs. Two representative RTN-based TRNG schemes are simulated to verify the proposed randomness models. An oscillator-based TRNG is also studied based on the theoretical randomness model of multiple traps-induced RTN. We also provide basic guidelines for designing RTN-based TRNGs. [ABSTRACT FROM PUBLISHER]

This paper proposes a technique, GALAXY, to speed up multicircuit simulation, where each circuit under simulation is identical in schematic but different in some parameters. GALAXY is based on the successive chord method, where the inverse Jacobian matrix ( J ^-1 ) is reused to simulate many circuits whose solutions are similar. GALAXY also speeds up single-circuit simulation by reusing J ^-1 between consecutive time steps. Compared with a traditional Newton–Raphson (NR) simulator, on average, GALAXY reduces runtime of single-circuit and multicircuit simulation by 44% and 71%, without loss of accuracy. The number of NR iterations is reduced by 78%. [ABSTRACT FROM PUBLISHER]

Graphic processing units (GPUs) are composed of a group of single-instruction multiple data (SIMD) streaming multiprocessors (SMs). GPUs are able to efficiently execute highly data parallel tasks through SIMD execution on the SMs. However, if those threads take diverging control paths, all divergent paths are executed serially. In the worst case, every thread takes a different control path and the highly parallel architecture is used serially by each thread. This control flow divergence problem is well known in GPU development; code transformation, memory access redirection, and data layout reorganization are commonly used to reduce the impact of divergence. These techniques attempt to eliminate divergence by grouping together threads or data to ensure identical behavior. However, prior efforts using these techniques do not model the performance impact of any particular divergence or consider that complete elimination of divergence may not be possible. Thus, we perform analysis of the performance impact of divergence and potential thread regrouping algorithms that eliminate divergence or minimize the impact of remaining divergence. Finally, we develop a divergence optimization framework that analyzes and transforms the kernel at compile-time and regroups the threads at runtime. For the compute-bound applications, our proposed metrics achieve performance estimation accuracy within 6.2% of measured performance. Using these metrics, we develop thread regrouping algorithms, which consider the impact of divergence, and speed up these applications by 2.2 \times on average on NVIDIA GTX480. [ABSTRACT FROM PUBLISHER]

Synchronous dataflow graphs (SDFGs) are widely used to represent digital signal processing algorithms and streaming media applications. This paper presents several methods for binding and scheduling SDFGs on a multiprocessor platform. Exploring the state space generated by a self-timed execution (STE) of an SDFG, we present an exact method for static rate-optimal scheduling of SDFGs via implicit retiming and unfolding. By modeling a constraint as an extra enabling condition for the STE, we get a constrained STE which implies a schedule under the constraint. We present a general framework for scheduling SDFGs under constraints on the number of processors, buffer sizes, auto-concurrency, or combinations of them. Exploring the state space generated by the constrained STE, we can check whether a retiming, which leads to a rate-optimal schedule under the processor (or memory) constraint, exists. Combining this with a binary search strategy, we present heuristic methods to find a proper retiming and a static scheduling that schedules the retimed SDFG with optimal rate and with as few processors (or as little storage space) as possible. None of the methods explicitly converts an SDFG to its equivalent homogenous SDFG, the size of which may be tremendously larger than the original SDFG. We perform experiments on several models of real applications and hundreds of synthetic SDFGs. The results show that the exact method outperforms existing methods significantly; our heuristics reduce the resources used and are computationally efficient. [ABSTRACT FROM AUTHOR]

The design of cyber-physical systems (CPSs) faces various new challenges that are unheard of in the design of classical real-time systems. Power optimization is one of the major design goals that is witnessing such new challenges. The presence of interaction between the cyber and physical components of a CPS leads to dependence between the time delay of a computational task and the amount of workload in the next iteration. We demonstrate that it is essential to take this delay-workload dependence into consideration in order to achieve low power consumption. In this paper, we identify this new challenge, and present the first formal and comprehensive model to enable rigorous investigations on this topic. We propose a simple power management policy, and show that this policy achieves a best possible notion of optimality. In fact, we show that the optimal power consumption is attained in a “steady-state” operation and a simple policy of finding and entering this steady state suffices, which can be quite surprising considering the added complexity of this problem. Finally, we validated the efficiency of our policy with experiments. [ABSTRACT FROM AUTHOR]

In this paper, we propose SVR-NoC, a network-on-chip (NoC) latency model using support vector regression (SVR). More specifically, based on the application communication information and the NoC routing algorithm, the channel and source queue waiting times are first estimated using an analytical queuing model with two equivalent queues. To improve the prediction accuracy, the queuing theory-based delay estimations are included as features in the learning process. We then propose a learning framework that relies on SVR to collect training data and predict the traffic flow latency. The proposed learning methods can be used to analyze various traffic scenarios for the target NoC platform. Experimental results on both synthetic and real-application traffic demonstrate on average less than 12% prediction error in network saturation load, as well as more than $100\times $ speedup compared to cycle-accurate simulations can be achieved. [ABSTRACT FROM PUBLISHER]

In computer architecture research and development, simulation is a powerful way of acquiring and predicting processor behaviors. While architectural simulation has been extensively utilized for computer performance evaluation, design space exploration, and computer architecture assessment, it still suffers from the high computational costs in practice. Specifically, the total simulation time is determined by the simulator’s raw speed and the total number of simulated instructions. The simulator’s speed can be improved by enhanced simulation infrastructures (e.g., simulators with high-level abstraction, parallel simulators, and hardware-assisted simulators). Orthogonal to these work, recent studies also managed to significantly reduce the total number of simulated instructions with a slight loss of accuracy. Interestingly, we observe that most of these work are built upon statistical techniques. This survey presents a comprehensive review to such studies and proposes a taxonomy based on the sources of reduction. In addition to identifying the similarities and differences of state-of-the-art approaches, we further discuss insights gained from these studies as well as implications for future research. [ABSTRACT FROM PUBLISHER]

Test set quality benefits from tests that detect large numbers of faults. However, test compaction procedures target decreasing numbers of faults as they generate more tests and drop faults from consideration. This paper describes a procedure that balances the numbers of faults that tests in a given test set detect in order to improve its quality. In the first step of an iteration, the procedure moves tests from the beginning to the end of the test set. This allows fault simulation with fault dropping to create target faults for tests that were generated with small numbers of target faults. In the second step, the procedure constructs a new test set where tests with small numbers of detected faults are modified to detect additional faults. Experimental results are presented to demonstrate the ability of the procedure to improve the quality of a test set for single stuck-at faults as measured by its bridging fault coverage, and the numbers of detections of single stuck-at faults. [ABSTRACT FROM PUBLISHER]

Compact modeling of phase-locked loop (PLL) frequency synthesizer is proposed to reduce transient phase noise and jitter simulation time. Conventional small-signal noise assumption based frequency-domain simulation approach produces inaccurate results for nonlinear PLLs. Accurate analysis of nonlinear PLL are possible through time-domain, or transient noise simulation but time-domain simulation is computation-intensive and time-consuming. This paper presents a practical solution for transient phase noise and jitter analysis using compact modeling techniques. It features an autoregressive moving average process modeled voltage-controlled oscillator with fractional calculus and wavelet transform for phase noise decomposition and reconstruction, thereby reducing the phase noise and jitter simulation time to 25.8% of the transistor-level simulation with 0.4 dB @ 1 MHz phase noise error and 0.3 ps long-term jitter error for a 2 GHz PLL frequency synthesizer in a 65 nm CMOS process. [ABSTRACT FROM PUBLISHER]