Exact inference of marginals in probabilistic graphical models (PGM) is known to be intractable, necessitating the use of approximate methods. Most of the existing variational techniques perform iterative message passing in loopy graphs which is slow to converge for many benchmarks. In this paper, we propose a new algorithm for marginal inference that is based on the incremental build-infer-approximate (IBIA) paradigm. Our algorithm converts the PGM into a sequence of linked clique tree forests (SLCTF) with bounded clique sizes, and then uses a heuristic belief update algorithm to infer the marginals. For the special case of Bayesian networks, we show that if the incremental build step in IBIA uses the topological order of variables then (a) the prior marginals are consistent in all CTFs in the SLCTF and (b) the posterior marginals are consistent once all evidence variables are added to the SLCTF. In our approach, the belief propagation step is non-iterative and the accuracy-complexity trade-off is controlled using user-defined clique size bounds. Results for several benchmark sets from recent UAI competitions show that our method gives either better or comparable accuracy than existing variational and sampling based methods, with smaller runtimes.

A commonly used approach to compute the error rate at the primary outputs (POs) of a circuit is to compare the fault-free and faulty copies of the circuit using XOR gates. This model results in poor accuracies with nonsampling-based methods for reliability estimation. An alternative is to use a single copy of the circuit with a four-valued representation for each net corresponding to the correct and incorrect signals. One problem in this formulation is the accurate propagation of associated probabilities. We use the framework of Bayesian inference (BI) to address this issue. We derive the conditional probability distribution (CPD) corresponding to the four-valued signals and find the output error rate using various approximate BI techniques. With our formulation, we demonstrate that the output error rate scales with the gate error probabilities. It is guaranteed to be zero when the gate error probability is zero, provided approximate BI algorithms based on sum-product belief propagation (BP) are used. Although inaccuracies increase at very low gate error probabilities, it is able to capture the relative reliability of outputs with respect to each other. We also propose a new method for finding the overall circuit error rate as the partition function for a fixed state of POs. This method provides a significant improvement in accuracy when compared with the existing method using OR gates.

In this article, we propose a computationally efficient iterative algorithm for proper orthogonal decomposition (POD) using random sampling based techniques. In this algorithm, additional rows and columns are sampled and a merging technique is used to update the dominant POD modes in each iteration. We derive bounds for the spectral norm of the error introduced by a series of merging operations. We use an existing theorem to get an approximate measure of the quality of subspaces obtained on convergence of the iteration. Results on various datasets indicate that the POD modes and/or the subspaces are approximated with excellent accuracy with a significant runtime improvement over computing the truncated SVD. We also propose a method to compute the POD modes of large matrices that do not fit in the RAM using this iterative sampling and merging algorithms.

Deep Neural Networks (DNNs) are increasingly being used in a variety of applications. However, DNNs have huge computational and memory requirements. One way to reduce these requirements is to sparsify DNNs by using smoothed LASSO (Least Absolute Shrinkage and Selection Operator) functions. In this paper, we show that irrespective of error profile, the sparsity values obtained using various smoothed LASSO functions are similar, provided the maximum error of these functions with respect to the LASSO function is the same. We also propose a layer-wise DNN pruning algorithm, where the layers are pruned based on their individual allocated accuracy loss budget, determined by estimates of the reduction in number of multiply-accumulate operations (in convolutional layers) and weights (in fully connected layers). Further, the structured LASSO variants in both convolutional and fully connected layers are explored within the smoothed LASSO framework and the tradeoffs involved are discussed. The efficacy of proposed algorithm in enhancing the sparsity within the allowed degradation in DNN accuracy and results obtained on structured LASSO variants are shown on MNIST, SVHN, CIFAR-10, and Imagenette datasets and on larger networks such as ResNet-50 and Mobilenet.

Approximate circuit design has gained significance in recent years targeting error-tolerant applications. In the literature, there have been several attempts at optimizing the number of approximate bits of each approximate adder in a system for a given accuracy constraint. For computational efficiency, the error models used in these routines are simple expressions obtained using regression or by assuming inputs or the error is uniformly distributed. In this article, we first demonstrate that for many approximate adders, these assumptions lead to an inaccurate prediction of error statistics for multi-level circuits. We show that mean error and mean square error can be computed accurately if static probabilities of adders at all stages are taken into account. Therefore, in a system with a certain type of approximate adder, any optimization framework needs to take into account not just the functionality of the adder but also its position in the circuit, functionality of its parents, and the number of approximate bits in the parent blocks. We propose a method to derive parameterized error models for various types of approximate adders. We incorporate these models within an optimization framework and demonstrate that the noise power is computed accurately.

Negative bias temperature instability along with the presence of process variations has resulted in time-varying path criticalities. To ensure reliable circuit operation, aging sensors are used at the end of potential critical paths (PCPs) for delay monitoring. Optimization of the number of delay sensors requires accurate computational models for prediction of criticality and selection of PCPs. We identify a path as a PCP if its maximum global criticality over the lifetime exceeds a certain threshold. However, the global criticality of a path could vary nonmonotonically over the lifetime of the device. In this paper, we propose a framework for time-varying statistical static timing analysis (TV-SSTA), wherein the circuit delay is obtained as a collection of time-varying canonicals with breakpoints in time which define the end of validity of one and the start of the next canonical. We show that the global criticality of any path will be maximum either at t = 0 or at these breakpoints. Hence, criticality computation and PCP selection need to be done only at these time points, which typically is less than four. The TV-SSTA is integrated with a previously proposed criticality computation technique to identify the PCPs and the results are validated against Monte Carlo simulations.

Approximate circuit design has gained significance in recent years targeting applications like media processing where full accuracy is not required. In this paper, we propose an approximate adder in which the approximate part of the sum is obtained by finding a single optimal level that minimises the mean error distance. Therefore hardware needed for the approximate part computation can be removed, which effectively results in very low power consumption. We compare the proposed adder with various approximate adders in the literature in terms of power and accuracy metrics. The power savings of our adder is shown to be 17% to 55% more than power savings of the existing approximate adders over a significant range of accuracy values. Further, in an image addition application, this adder is shown to provide the best trade-off between PSNR and power.

Approximate adders are used in applications that are error tolerant to save on power and area. We consider the class of two-part segmented approximate adders, where the upper part of the sum is computed accurately and the lower part of the sum is approximated. In this paper, we model the error of various two-part segmented approximate adders using probabilistic analysis and derive expressions for some basic error metrics used in literature. We compare the results obtained using our expressions for various error metrics with those using Monte Carlo simulations for different input distributions. Further, in an image addition application, we use our expression derived for mean square error and show that it predicts the PSNR correctly.

Due to process variations, every path in the circuit is associated with a probability of being critical and a measure of this probability is the criticality of the path. Identification of critical paths usually proceeds in two steps, namely, generation of a candidate path set followed by computation of path criticality. As criticality computation is expensive, the candidate path set is chosen using simpler metrics. However, these metrics are not directly related to path criticality and, often, the set also contains low criticality paths that do not need to be tested. In this article, we propose a hierarchical technique that directly gives all paths above a global criticality threshold. The circuit is divided into disjoint groups at various levels. We show that the criticality of a group at each level of hierarchy can be computed using criticality of the parent group and the local complementary delay within the group. Low criticality groups are pruned at every level, making the computation efficient. This recursive partitioning and group criticality computation is continued until the group criticality falls below a threshold. Beyond this, the path selection within the group is done using branch-and-bound algorithm with global criticality as the metric. This is possible, since our method for criticality computation is very efficient. Unlike other techniques, path selection and criticality computation are integrated together so that when the path selection is complete, path criticality is also obtained. The proposed algorithm is tested with ISCAS’85, ISCAS’89, and ITC’99 benchmark circuits and the results are verified using Monte Carlo simulation. The experimental results suggest that the proposed method gives better accuracy on average with around 90% reduction in run-time.

In this article, we derive a simple and accurate expression for the change in timing yield due to a change in the gate delay distribution. It is based on analytical bounds that we have derived for the moments of the circuit and path delay. Based on this, we propose computationally efficient algorithms for (1) discrete gate sizing and (2) simultaneous gate sizing and threshold voltage ( V T ) assignment so that the circuit meets a timing yield specification under parameter variations. The use of this analytical yield gradient within a gradient-based timing yield optimization algorithm results in a significant improvement in the runtime as compared to the numerical method, while achieving the same final yield. It also allows us to explore a larger search space in each iteration more efficiently, which is required in the case of simultaneous resizing and V T assignment. We also propose heuristics for resizing/changing the V T of multiple gates in each iteration. This makes it possible to optimize the timing yield for large circuits. Results on ITC ’99 benchmarks show that the proposed multinode resizing algorithm results in a significant improvement in the runtime with a marginal average area penalty and no cost to the final yield achieved.

The use of quadratic gate delay models and arrival times results in improved accuracies for a parameterized block-based statistical static timing analysis (SSTA). However, the computational complexity is significantly higher. As an alternative to this, we propose a canonical model based on skew-normal random variables (SN model). This model is derived from the quadratic canonical models and can consider the skewness in the gate delay distribution as well as the nonlinearity of the MAX operation. Based on conditional expectations, we derive the analytical expressions for the moments of the MAX operator and the tightness probability that can be used along with the SN canonical models. The computational complexity for both timing and criticality analysis is comparable with SSTA using linear models. There is a two to three orders of magnitude improvement in the run time as compared with the quadratic models. Results on ISCAS benchmarks show that the SN models have a lower variance error than the quadratic model, but the error in the third moment is comparable with that of the semiquadratic model.

Statistical timing yield optimization algorithms require computation of yield-gradient for gate resizing in every iteration. Numerical yield-gradients account for the effects of fan-in and fan-out gates, but are computationally expensive. In this paper, we formulate a more accurate analytical expression for the yield-gradient (termed effective yield-gradient) that includes these effects. Based on the statistical properties of the path delay variations, we derive a simplified expression for the effective yield gradient that is accurate and results in an improvement in the run-time. Using these simplified expressions, we also propose an algorithm for resizing multiple gates in an iteration. Results on ITC99 and ISCAS85 benchmarks show that the proposed multi-node resizing algorithm results in 83% improvement in the runtime with an average area penalty of 3% and no cost to the final yield achieved.

Balanced truncation of descriptor systems requires computation of spectral projectors and solution of the generalized projected Lyapunov equations, both of which have significant complexity. Frequency-weighted balancing methods are more efficient if the response over a specific frequency range is desired. However, a direct extension of these methods to descriptor systems requires the spectral projectors. In this paper, we propose an efficient frequency-weighted balanced truncation algorithm without finding the spectral projectors. Samples of the frequency-domain solution to the system are used to get an accurate estimate of the improper Gramians. The proper Gramians are computed after adjusting for the contribution of the improper subsystem. Low rank factors of these Gramians are used to obtain a basis that includes the contribution of both the proper and improper subsystems. Congruence transform is used to ensure passivity of RLC interconnect models. Results for standard benchmarks show that the method is accurate and efficient.

The statistical nature of gate delays in current day technologies necessitates the use of measures, such as path criticality and node/edge criticality for timing optimization. Node criticalities are typically computed using the complementary path delay. An alternative approach to compute the criticality using the circuit delay has been recently proposed. In this paper, we discuss in detail, the use of circuit delay to compute node criticalities and show that the criticality thus found is not equal to the conventional measure found using complementary path delay. However, there is a monotonic relationship between them and the two measures can be used interchangeably. We derive new bounds for the global criticality and propose a pruning algorithm based on these bounds to improve the accuracy and speed of computation. The use of this pruning technique results in a significant speedup in criticality computations. We obtain an order of magnitude average speedup for ISCAS benchmarks.

Due to the statistical nature of gate delays in current day technologies, measures such as path criticality and node/edge criticality are required for timing optimization. Node criticalities are usually computed using the complementary path delay. In order to speed up computations, it has been recently proposed that the circuit delay be used instead. In this paper, we show that there is a monotonic relationship between the node criticalities computed using the circuit delay and the complementary delay. They are not equal, but they can be used interchangeably. We discuss the sources of error in this computation and propose methods for more accurate computations. We also introduce a measure that is very easy to compute and is an approximate indicator of criticality. Since it is easy to compute, it can also be used effectively for pruning the number of edges involved in criticality computations thus improving the speed of criticality computations. The speedup obtained can be as large as an order of magnitude for some of larger circuits in the ISCAS benchmarks.

For a task mapped to the reconfigurable fabric (RF) of partially reconfigurable hybrid processor architecture, significant speedup can be obtained if multiple processing units (PUs) are used to accelerate the task. In this paper, the authors present the results obtained from a quantitative analysis for a single data-parallel task mapped to the RF of bus-based hybrid processor architecture. The architectural constraints in this case include run-time reconfiguration delay and a shared data bus to main memory

Reconfigurable hybrid processor systems provide a flexible platform for mapping data-parallel applications, while providing considerable speedup over software implementations. However, the overhead for reconfiguration presents a significant deterrent in mapping applications onto reconfigurable hardware. Partial runtime reconfiguration is one approach to reduce the reconfiguration overhead. In this paper, we present a methodology to map data-parallel tasks onto hardware that supports partial reconfiguration. The aim is to obtain the maximum possible speedup, for a given reconfiguration time, bus speed, and computation speed. The proposed approach involves using multiple, identical but independent processing units in the reconfigurable hardware. Under nonzero reconfiguration overhead, we show that there exists an upper limit on the number of processing units that can be employed beyond which further reduction in execution time is not possible. We obtain solutions for the minimum processing time, the corresponding load distribution, and schedule for data transfer. To demonstrate the applicability of the analysis, we present the following: 1) various plots showing the variation of processing time with different parameters; 2) hardware simulations for two examples, viz., 1-D discrete wavelet transform and finite impulse response filter, targeted to Xilinx field-programmable gate arrays (FPGAs); and 3) experimental results for a hardware prototype implemented on a FPGA board

In this paper, we analyze the effect of jitter in track and hold circuits. The output spectrum is obtained in terms of the system function of the track and hold. It is a fairly general model in which the effect of input as well as clock jitter can be included. The clock can have an arbitrary duty cycle, so that the circuit could also approximate a sample and hold. Using this model, it is possible to simulate the effects of jitter in a track and hold using a standard circuit simulator. Three cases are analyzed - long term jitter, correlated jitter with exponential autocorrelation and white noise jitter. These results are verified using Monte Carlo simulations.

A time-domain algorithm for computation of the noise power spectral density (PSD) is proposed in [17]. When applied to periodically varying circuits, this formulation requires efficient methods to obtain the quasi-periodic steady-state solution of a set of linear time-varying ordinary differential equations. We use both the mixed frequency-time technique(MFT) and the shooting Newton method for this computation. We show that, at each frequency for which the spectral density is sought, MFT requires only two integrations over a duration of the clock period. The results are compared with published experimental and computed data.