Stochastic computing (SC) is subject to many subtle, interacting, and application-driven error types often not found in conventional binary computing systems. These errors may defy standard methods of analysis and demand the use of black-box simulation to quantify system performance and accuracy. To address this issue, we propose a methodology called Bayesian Analysis of Stochastic Errors (BASE). BASE provides a comprehensive statistical basis for understanding and analyzing SC errors either in mathematical terms or in conjunction with simulation. It also introduces three new viewpoints into SC theory: bias-variance decomposition to distinguish systematic from random errors, Bayesian cost metrics to account for application dependencies, and estimator dominance to compare circuits. We demonstrate BASE’s utility via examples that reveal the intricacies of stochastic circuit errors. We also use BASE to analyze SC’s fundamental building blocks and demonstrate how to analyze circuit error using purely statistical models.

Stochastic computing offers low-power and compact arithmetic for neural network inference, but achieving fault tolerance typically requires long bitstreams that create latency bottlenecks for real-time applications. This work introduces an adaptive-precision framework for fault-tolerant stochastic long short-term memory (SLSTM) networks that dynamically assigns stochastic number lengths based on computational criticality. The proposed Cell-based Gradient Sensitivity Search (CGSS) algorithm identifies the most faultsensitive LSTM cells through gradient-based analysis, enabling targeted allocation of longer bitstreams to critical computations while using shorter, low-latency bitstreams for less sensitive operations. The proposed adaptive-precision SLSTM accelerator validates our approach by achieving up to $3.4 \times$ latency reduction, 40% area savings, and 58% power reduction while maintaining fault tolerance equivalent to fixed highprecision SLSTM designs under higher fault rates. These results demonstrate that criticality-guided adaptive-precision is important for making fault-tolerant stochastic neural networks practically viable in resource-constrained environments.

The continuous wavelet transform (CWT) is essential for analyzing non-stationary signals in edge computing, but traditional implementations are limited by high power demands, particularly in resource-constrained environments. Stochastic computing (SC), which leverages probabilistic bit-streams and compact arithmetic units, provides a promising alternative for ultra-low-power CWT designs. However, such circuits are vulnerable to transient faults and involve careful power-reliability trade-offs. This work presents the first SC-based CWT hardware design aimed at applications with severe resource constraints, including power consumption, accuracy, and fault tolerance. We comprehensively analyzed our design, which features a Sobol-based pseudo-random number source and accumulative parallel counter-based addition. In a fault-free environment, this design achieves an 84% power reduction over non-SC CWTs and a 37% reduction over other SC designs. It also achieves up to 64% area savings and reduces latency by 8×. Under a 30% fault rate, our design improves RMSE by 74% over binary CWTs and 32% over other SC implementations.

Human activity recognition (HAR) is a challenging area of research with widespread applications in human-computer interaction. Recent advances in neural networks (NNs) have greatly improved the methods of HAR feature extraction from wearable sensor data and increased the interest in their classification using NNs. While most prior work has relied on software implementations of NN-based HAR, we investigate for the first time hardware implementations for use in resource-constrained edge devices. Emerging edge and near-sensor systems must avoid costly communication with the cloud and perform complex classification tasks locally. This points to using low-area hardware technology such as stochastic computing (SC) and enhanced feature extraction methods such as wavelet transform (WT). We explore the wavelet-assisted stochastic-enabled neural network (WASENN) design for HAR. The NN types we consider are convolutional neural networks and long short-term memory networks. We study both partial and full versions of WASENN and evaluate their performance and resource utilization on the UCI HAR and WISDM datasets. Our hardware synthesis results show the superiority of the wavelet transform in accuracy and size. They also show that SC reduces area and power by 32% and 74% respectively with little impact on classification accuracy.

Stochastic computing (SC) provides low-area, power-efficient hardware solutions suitable for edge systems, but its scalability poses challenges due to its precision limitations, especially in noisy environments. This paper investigates the fault tolerance of key SC components, such as stochastic number generators (SNGs) and activation functions (AFs), within recurrent and sequential networks like long short-term memory (LSTM) networks. We inject bit-flip faults into a network’s most sensitive inputs, weights and AFs, and study fault propagation across different network layers. Our findings reveal that SC component choices significantly influence fault tolerance. For example, networks using Sobol-based SNGs with tanh AFs exhibited stronger resilience than those with LFSR-based SNGs and ReLU AFs, by maintaining higher accuracy under fault conditions. However, the accuracy of the networks declined significantly under simultaneous faults in inputs, weights and AFs. Additionally, while increasing stochastic number lengths improved fault tolerance, they also increased latency. Nevertheless, the SC networks achieved up to 54% area and 72% power savings, making them ideal for resource-constrained applications. We also found that there is a trade-off between efficiency and fault tolerance: SC designs that focus on resource efficiency may struggle in noisy environments, where fault-tolerant SC designs are more effective. This implies that fault resilience in SC architectures depend heavily on design choices and cannot be assumed inherent across all configurations.

Recent advances in near-sensor computing have prompted the need to design low-cost digital filters for edge devices. Stochastic computing (SC), leveraging its probabilistic bit-streams, has emerged as a compelling alternative to traditional deterministic computing for filter design. This paper examines error tolerance, area and power efficiency, and accuracy loss in SC-based digital filters. Specifically, we investigate the impact of various stochastic number generators and increased filter complexity on both FIR and IIR filters. Our results indicate that in an error-free environment, SC exhibits a 49% area advantage and a 64% power efficiency improvement, albeit with a slight loss of accuracy, compared to traditional binary implementations. Furthermore, when the input bit-streams are subject to a 2% bit-flip error rate, SC FIR and SC IIR filters have a much smaller performance degradation (1.3X and 1.9X, respectively) than comparable binary filters. In summary, this work provides useful insights into the advantages of stochastic computing in digital filter design, showcasing its robust error resilience, significant area and power efficiency gains, and trade-offs in accuracy compared to traditional binary approaches.

Stochastic computing (SC) uses streams of pseudo-random bits to perform low-cost and error-tolerant numerical processing for applications like neural networks and digital filtering. A key operation in these domains is the summation of many hundreds of bit-streams, but existing SC adders are inflexible and unpredictable. Basic mux adders have low area but poor accuracy while other adders like accumulative parallel counters (APCs) have good accuracy but high area. This work introduces parallel sampling adders (PSAs), a novel weighted adder family that offers a favorable area-accuracy trade-off and provides great flexibility to large-scale SC adder design. Our experiments show that PSAs can sometimes achieve the same high accuracy as APCs, but at half the area cost. We also examine the behavior of large-scale SC adders in depth and uncover some surprising results. First, APC accuracy is shown to be sensitive to input correlation despite the common belief that APCs are correlation insensitive. Then, we show that mux-based adders are sometimes more accurate than APCs, which contradicts most prior studies. Explanations for these anomalies are given and a decorrelation scheme is proposed to improve APC accuracy by 4x for a digital filtering application.

Stochastic computing (SC) is a digital design paradigm that foregoes the conventional binary encoding in favor of pseudo-random bitstreams. Stochastic circuits operate on the probability values of bitstreams, and often achieve low power, low area, and fault-tolerant computation. Most SC designs rely on the input bitstreams being independent or uncorrelated to obtain the best results. However, circuits have also been proposed that exploit deliberately correlated bitstreams to improve area or accuracy. In such cases, different sub-circuits may have different correlation requirements. A major barrier to multi-layer or hierarchical stochastic circuit design has been understanding how correlation propagates from a circuit’s inputs to its outputs while meeting the correlation requirements for all its sub-circuits. In this paper, we introduce correlation matrices and extensions to probability transfer matrix (PTM) algebra to analyze complex correlation behavior, thereby alleviating the need for computationally intensive bit-wise simulation. We apply our new correlation analysis to two multi-layer SC image processing and neural network circuits and show that it helps designers to systematically reduce correlation error.

For emerging edge and near-sensor systems to perform hard classification tasks locally, they must avoid costly communication with the cloud. This requires the use of compact classifiers such as recurrent neural networks of the long short term memory (LSTM) type, as well as a low-area hardware technology such as stochastic computing (SC). We study the benefits and costs of applying SC to LSTM design. We consider a design space spanned by fully binary (non-stochastic), fully stochastic, and several hybrid (mixed) LSTM architectures, and design and simulate examples of each. Using standard classification benchmarks, we show that area and power can be reduced up to 47% and 86% respectively with little or no impact on classification accuracy. We demonstrate that fully stochastic LSTMs can deliver acceptable accuracy despite accumulated errors. Our results also suggest that ReLU is preferable to tanh as an activation function in stochastic LSTMs

Human activity recognition (HAR) is a challenging area of research with many applications in human-computer interaction. With advances in artificial neural networks (ANNs), methods of HAR feature extraction from wearable sensor data have greatly improved and have increased interest in their classification using ANNs. Most prior work has only investigated the software implementations of ANN-based HAR. Here, we investigate, for the first time, two novel hardware implementations for use in resource-constrained edge devices. Through architecture exploration, we identify first a hybrid ANN we call DCLSTM incorporating the convolutional and long-short-term memory techniques. The second is a much more compact implementation WCLSTM that uses wavelet transforms (WTs) to enhance feature extraction; it can achieve even better accuracy while being smaller and simpler; it is therefore the better choice for resource-constrained applications. We present hardware implementations of these ANNs and evaluate their performance and resource utilization on the UCI HAR and WISDM datasets. Synthesis results on an FPGA platform show the superiority of the WT-assisted version in accuracy and size. Moreover, our networks achieve a better accuracy than earlier published works.

Stochastic computing (SC) is a low-cost computational paradigm that has promising applications in digital filter design, image processing, and neural networks. Fundamental to these applications is the weighted addition operation, which is most often implemented by a multiplexer (mux) tree. Mux-based adders have very low area but typically require long bitstreams to reach practical accuracy thresholds when the number of summands is large. In this work, we first identify the main contributors to mux adder error. We then demonstrate with analysis and experiment that two new techniques, precise sampling and full correlation, can target and mitigate these error sources. Implementing these techniques in hardware leads to the design of CeMux (Correlation-enhanced Multiplexer), a stochastic mux adder that is significantly more accurate and uses much less area than traditional weighted adders. We compare CeMux to other SC and hybrid designs for an electrocardiogram filtering case study that employs a large digital filter. One major result is that CeMux is shown to be accurate even for large input sizes. CeMux's higher accuracy leads to a latency reduction of 4× to 16× over other designs. Furthermore, CeMux uses about 35% less area than existing designs, and we demonstrate that a small amount of accuracy can be traded for a further 50% reduction in area. Finally, we compare CeMux to a conventional binary design and we show that CeMux can achieve a 50% to 73% area reduction for similar power and latency as the conventional design but at a slightly higher level of error.

A fundamental assumption in stochastic computing (SC) is that bit-streams are generally well-approximated by a Bernoulli process, i.e., a sequence of independent 0-1 choices. We show that this assumption is flawed in unexpected and significant ways for some bit-streams such as those produced by a typical LFSR-based stochastic number generator (SNG). In particular, the Bernoulli assumption leads to a surprising overestimation of output errors and how they vary with input changes. We then propose a more accurate model for such bit-streams based on the hypergeometric distribution and examine its implications for several SC applications. First, we explore the effect of correlation on a mux-based stochastic adder and show that, contrary to what was previously thought, it is not entirely correlation insensitive. Further, inspired by the hypergeometric model, we introduce a new mux tree adder that offers major area savings and accuracy improvement. The effectiveness of this study is validated on a large image processing circuit which achieves an accuracy improvement of 32%, combined with a reduction in overall circuit area.

Understanding accuracy and the tradeoffs it entails is key to evaluating the growing list of stochastic computing (SC) circuit designs. Due to shortcomings of current SC error theory, simulation has become the standard way to estimate a circuit's accuracy. However, simulation can demand large computational resources and lead to uncertain, misleading, or unexplainable results. A soundly based analytic approach is therefore preferable to simulation. In this work, we first show the input value distribution's large influence on circuit accuracy. Then we develop a Bayesian error analysis methodology which uses the input value distribution as a prior to inform better accuracy estimates. This error formulation introduces concepts new to SC such as estimator dominance and points to ways of improving simulation-based accuracy estimates. Orthogonal to the Bayesian ideas, we also show how to use bias-variance decomposition to simplify and aggregate the effects of SC's many error sources. We present techniques that use the beta distribution to model the stochastic number value distribution. Finally, we demonstrate the use of these ideas to improve the accuracy and analysis of an SC-based neural network.

Stochastic computing (SC) is an emerging paradigm for designing circuits to perform complicated computation with simple circuitry. Although SC circuits have small area and critical-path delay, due to the need of many clock cycles to perform computation, they have a large overall latency and energy consumption. One solution to this problem is to further minimize the circuits. In this work, we explore target function approximation to derive an SC circuit with significantly reduced area and delay. We propose two static methods that first construct a set of functions close to the given target function and then select the best synthesized SC circuit realizing one of these functions. We also propose an efficient dynamic method that simultaneously searches for the best approximated target function and the corresponding minimized SC circuit. The experimental results show that on average, our dynamic method dramatically reduces the area, critical-path delay, and area-delay product of the SC circuits by 80%, 59%, and 91%, respectively, over the state-of-the-art Maclaurin polynomial-based method for a given error bound of 2%. The code of our methods is made open-source.

Stochastic computing (SC) with its small area and power footprint is a prime candidate for realizing neural networks (NNs) in heavily resource-restricted devices, such as near-sensor computing systems. Complete SCNNs encompassing all network layers have mostly been simulated in software, or synthesized without consideration of potential area limitations. In this work, we present a full FPGA implementation of a complete SCNN for image classification under tight resource constraints. All computational operations of the NN are performed on FPGA primitives. Furthermore, no DSPs and no onboard CPU is required for the computation. Our system operates at 60MHz and can classify an input image within approximately 6ms. Moreover, our basic SC and memory components can be flexibly combined to cover a large variety of NN structures.

Stochastic circuits (SCs) offer significant area, power and energy benefits at the cost of computational inaccuracies. SCs have received particular attention recently in the context of neural networks (NNs). Many NNs use the maximum function, e.g., in the max-pooling layer of convolutional NNs. Currently, approximate workarounds are often employed for this function. We propose NMax, a new SC design for the maximum function that produces an exact result with latency similar to an approximate circuit. Furthermore, unlike most stochastic functions, NMax is correlation insensitive. We also observe that maximum calculations are subject to application-specific bias and analyze this bias.

Stochastic computing (SC) computes with randomized bit-streams using standard logic circuits. Its defining features are low power, small area, and high fault tolerance; its drawbacks are long run times and inaccuracies due to its inherently random behavior. Consequently, much previous work has focused on improving SC performance by introducing non-random or deterministic data formats and components, often at considerable cost. However, as this paper shows, taking advantage of, or even adding to, a stochastic circuit's randomness can play a major positive role in applications like neural networks (NNs). The amount of such randomness, must however, be carefully controlled to achieve a beneficial effect without corrupting an application's functionality. The paper first discusses the use of mean square deviation (MSD) as a metric for randomness in SC. It then describes a low-cost element to control the MSD levels of stochastic signals. Finally, it examines two applications where SC can provide performance-enhancing randomness at very low cost, while retaining all the other benefits of SC. Specifically, it is shown how to improve the visual quality of black-and-white images via stochastic dithering, a technique that leverages randomness to enhance image details. Further, the paper demonstrates how the randomness of an SC-based layer makes an NN more resilient against adversarial attacks than an NN realized entirely by conventional, non-stochastic designs.

Stochastic computing (SC) is an alternative way to design arithmetic circuits that have lower area and power than circuits employing conventional binary (base-2) computing (BC). Large SC-based systems like neural networks (NNs) or vision systems usually resort to BC, either explicitly or implicitly, for tasks requiring higher accuracy, such as data storage, control functions, or complex arithmetic operations. The resulting hybrid SC-BC features often incorporate unsatisfactory tradeoffs between system latency and accuracy. For example, they may require many costly SC-BC data format converters, which interrupt bit-stream flow and cause significant delay overhead. While improving accuracy has been a major research goal in SC, less attention has been paid to reducing latency. We present a novel design methodology called Maxflow that minimizes the latency of SC operations without reducing accuracy or interrupting data flow more than necessary. Maxflow supports delay-accuracy tradeoffs with little hardware modification. Its effectiveness is demonstrated for a deep NN, where it reduces overall latency substantially with no loss of accuracy compared to previous designs.

Stochastic circuits (SCs) offer considerable area- and power-consumption benefits in various applications at the expense of computational inaccuracies. Unlike conventional logic synthesis, managing accuracy is a central problem in SC design. It is usually tackled in ad hoc fashion by multiple trial-and-error simulations that vary relevant parameters like the stochastic number length n . We present, for the first time, a systematic design approach to controlling the accuracy of SCs and balancing it against other design parameters. We express the (in)accuracy of a circuit processing n -bit stochastic numbers by the numerical deviation of the computed value from the expected result, in conjunction with a confidence level. Using the theory of Monte Carlo simulation, we derive expressions for the stochastic number length required for a desired level of accuracy or vice versa. We discuss the integration of the theory into a design framework that is applicable to both combinational and sequential SCs. We show that for combinational SCs, accuracy is independent of the circuit’s size or complexity, a surprising result. We also show how the analysis can identify subtle errors in both combinational and sequential designs. Finally, we apply the proposed methods to a case study on filtering noisy EKG signals.

Stochastic computing (SC) is an unconventional method of computation that treats data as probabilities. Typically, each bit of an N-bit stochastic number (SN) Xis randomly chosen to be 1 with some probability pX, and X is generated and processed by conventional logic circuits. For instance, a single AND gate performs multiplication. The value X of an SN is measured by the density of 1 s in it, an information-coding scheme also found in biological neural systems. SC has uses in massively parallel systems and is very tolerant of soft errors. Its drawbacks include low accuracy, slow processing, and complex design needs. Its ability to efficiently perform tasks like communication decoding and neural network inference has rekindled interest in the field. Many challenges remain to be overcome, however, before SC becomes widespread. In this paper, we discuss the evolution of SC, mostly focusing on recent developments. We highlight the main challenges and discuss potential methods of overcoming them.

Recent advances in neural networks (NNs) exhibit unprecedented success at transforming large, unstructured data streams into compact higher-level semantic information for tasks such as handwriting recognition, image classification, and speech recognition. Ideally, systems would employ near-sensor computation to execute these tasks at sensor endpoints to maximize data reduction and minimize data movement. However, near-sensor computing presents its own set of challenges such as operating power constraints, energy budgets, and communication bandwidth capacities. In this paper, we propose a stochastic-binary hybrid design which splits the computation between the stochastic and binary domains for near-sensor NN applications. In addition, our design uses a new stochastic adder and multiplier that are significantly more accurate than existing adders and multipliers. We also show that retraining the binary portion of the NN computation can compensate for precision losses introduced by shorter stochastic bit-streams, allowing faster run times at minimal accuracy losses. Our evaluation shows that our hybrid stochastic-binary design can achieve 9.8x energy efficiency savings, and application-level accuracies within 0.05% compared to conventional all-binary designs.

Stochastic circuits (SCs) offer tremendous areaand power-consumption benefits at the expense of computational inaccuracies. Managing accuracy is a central problem in SC design and has no counterpart in conventional circuit synthesis. It raises a basic question: how to build a systematic design flow for stochastic circuits? We present, for the first time, a systematic design approach to control the accuracy of SCs and balance it against other design parameters. We express the (in)accuracy of a circuit processing n-bit stochastic numbers by the numerical deviation of the computed value from the expected result, in conjunction with a confidence level. Using the theory of Monte Carlo simulation, we derive expressions for the stochastic number length required for a desired level of accuracy, or vice versa. We discuss the integration of the theory into a design framework that is applicable to both combinational and sequential SCs. We show that for combinational SCs, accuracy is independent of the circuit's size or complexity, a surprising result. We also show how the analysis can identify subtle errors in both combinational and sequential designs.

Stochastic circuits (SCs) offer tremendous area and power-consumption benefits at the expense of computational inaccuracies. They require random num-ber sources (RNSs) to implement stochastic number generators (SNGs) for all of their inputs. It is common for an SC to have a large number of primary and auxiliary inputs. Often the associated SNGs take up as much as 80% of the entire circuit area, so sharing RNSs is a very important goal in stochastic computing. Such sharing often leads to large correlation errors that have to be resolved via costly decorrelation methods. Linear feed-back shift registers (LFSRs) are typically used as RNSs. However, we show that their deterministic and linear behavior can interfere with commonly used decorrelation methods, causing systematic computation errors, and limiting the possibilities of sharing LFSRs between SNGs. We therefore propose a novel pseudo-random number generator SBoNG for stochastic circuits that combines an LFSR with a non-linear S-box function. An SBoNG does not interfere with decorrelation and can be shared effi-ciently by multiple SNGs. Consequently, SBoNGs scale very well in SCs with large numbers of inputs.

Interest in stochastic computing (SC) has been growing due to the need for low-cost circuitry in areas like image processing and machine learning. While combinational stochastic circuits are relatively easy to design, their limitations such as having few implementable functions and inaccuracies due to correlation, call for sequential components and design methods. The theory underlying sequential stochastic circuits is not fully understood, however. Almost all existing sequential SC circuits fall into the up/down-counter-based (UCB) class. In this paper, we identify and investigate a new SC circuit class: shift-register-based (SRB). We focus on the properties of SRB circuits and demonstrate their central role in stochastic computing. This leads to an algorithm MOUSE for sequential design optimization. By exploiting sequential stochastic equivalence, MOUSE can reduce SRB circuit cost without compromising performance or accuracy.

Stochastic computing (SC) is an unconventional computing paradigm that operates on stochastic bit streams. It has gained attention recently because of the very low area and power needs of its computing core. SC relies on stochastic number generators (SNGs) to map input binary numbers to stochastic bit streams. A conventional SNG comprises a random number source (RNS), typically an LFSR, and a comparator. It needs far more area and power than the SC core, offsetting the latter's main advantages. To mitigate this problem, SNGs employing emerging nanoscale devices such as memristors and spintronic devices have been proposed. However, these devices tend to have large errors in their output probabilities due to unpredictable variations in their fabrication processes and noise in their control signals. We present a novel method of exploiting such devices to design a highly accurate SNG. It is built around an RNS that generates uniformly distributed random numbers under ideal (nominal) conditions. It also has a novel error-cancelling probability conversion circuit (ECPCC) that guarantees very high accuracy in the output probability under realistic conditions when the RNS is subject to errors. An ECPCC can also be used to generate maximally correlated stochastic streams, a useful property for some applications.

As we approach the limits of traditional Moore’s-Law scaling, alternative computing techniques that consume energy more efficiently become attractive. Stochastic computing (SC), as a re-emerging computing technique, is a low-cost and error-tolerant alternative to conventional binary circuits in several important applications such as image processing and communications. SC allows a natural accuracy-energy tradeoff that has been exploited in the past. This article presents an accuracy-energy tradeoff technique for SC circuits that reduces their energy consumption with virtually no accuracy loss. To this end, we employ voltage or frequency scaling, which normally reduce energy consumption at the cost of timing errors. Then we show that due to their inherent error tolerance, SC circuits operate satisfactorily without significant accuracy loss even with aggressive scaling. This significantly improves their energy efficiency. In contrast, conventional binary circuits quickly fail as the supply voltage decreases. To find the most energy-efficient operating point of an SC circuit, we propose an error estimation method that allows us to quickly explore the circuit’s design space. The error estimation method is based on Markov chain and least-squares regression. Furthermore, we investigate opportunities to optimize SC circuits under such aggressive scaling. We find that logical and physical design techniques can be combined to significantly expand the already-powerful accuracy-energy tradeoff possibilities of SC. In particular, we demonstrate that careful adjustment of path delays can lead to significant error reduction under voltage and frequency scaling. We perform buffer insertion and route detouring to achieve more balanced path delays. These techniques differ from conventional path-balancing techniques whose goal is to minimize power consumption by resizing the non-critical paths. The goal of our path-balancing approach is to increase error cancellation chances in voltage-/frequency-scaled SC circuits. Our circuit optimization comprehends the tradeoff between power overheads due to inserted buffers and wires versus the energy reduction from supply voltage downscaling enabled by more balanced path delays. Simulation results show that our optimized SC circuits can tolerate aggressive voltage scaling with no significant signal-to-noise ratio (SNR) degradation. In one example, a 40% supply voltage reduction (1V to 0.6V) on the SC circuit leads to 66% energy saving (20.7pJ to 6.9pJ) and makes it more efficient than its conventional binary counterpart. In the same example, a 100% frequency boosting (400ps to 200ps) of the optimized circuits leads to no significant SNR degradation. We also show that process variation and temperature variation have limited impact on optimized SC circuits. The error change is less than 5% when temperature changes by 100°C or process condition changes from worst case to best case.

Stochastic computing (SC) performs arithmetic on randomized bit-streams called stochastic numbers (SNs) using standard logic circuits. SC has many appealing features such as error tolerance, low power, and low area cost. However, it suffers from severe accuracy loss due to correlation or insufficient randomness. SNs can be decorrelated by regenerating them from independent random sources. This is the preferred decorrelation method mentioned in the literature, but it often entails huge area and delay overhead. An attractive alternative is isolation-based decorrelation, which is the focus of this research. Isolation works by inserting delays (isolators) into a stochastic circuit to eliminate undesirable interactions among its SNs. Surprisingly, although it has far lower cost than regeneration, isolation has not been studied systematically before, hindering its practical use. The paper first examines the basic characteristics of SC isolation. We show that unless carefully used, it can result in excessive isolator numbers or unexpectedly corrupt a circuit's function. We therefore formally characterize the behavior of an isolation-decorrelated circuit, and derive conditions for correct deployment of isolators. We then describe the first isolator placement algorithm designed to minimize the number of isolators. Finally, we present supporting data obtained from simulation experiments on representative circuits.

Stochastic computing (SC) uses standard logic to process pseudo-random bit-streams denoting probabilities. It implements arithmetic operations by extremely simple and low-power hardware. Despite major new applications, SC's theory and design requirements are poorly understood. We observe that the Boolean functions used in SC take the form f(X) = f(Xv;Xc), where Xv and Xc are inputs with variable and constant probabilities, respectively. Different functions can be equivalent in the sense of implying the same stochastic behavior. We define stochastic equivalence classes (SECs), and investigate their properties and applications. Suitably interpreted, SECs describe all realizable arithmetic functions of interest. While conventional synthesis focuses on finding the best circuit to implement a known function, stochastic circuit optimization first requires finding the best function. We present an SEC-based approach to this problem, which demonstrates the computational richness of SC and leads to significant cost reductions compared to prior designs.

We give a short overview of stochastic computing (SC) and its uses. SC computes with randomized bit-streams that loosely resemble the neural spike trains of the brain. Its key feature is the use of low-cost and low-power logic elements to implement complex numerical operations in a highly error-tolerant fashion. These advantages must be weighed against SC's inherently slow computing speed and low precision. Although studied sporadically since its invention in the 1960s, SC has regained interest recently as potentially suited to some emerging nanotechnologies, and to applications such as ECC decoding and biomedical image processing. However, a number of major challenges must be overcome if this potential is to be fully realized.

Matrix multiplication is a high-cost operation that can benefit from efficient hardware implementation. Approximate computing offers a promising way to lower the hardware costs and to speed up the computation by leveraging the error tolerance of applications like image processing. This work proposes a novel approximate matrix-vector multiplier which features low area and high speed. Moreover, its accuracy is dynamically reconfigurable, allowing the user to trade small errors for increased speed. Compared to previous designs, our approach reduces the area cost up to 70% with a 5% average error. With a more relaxed 10% error constraint, it achieves a speedup of 2x. We apply the proposed design to color transformation, a basic operation in face-detection algorithms. The approximate transformed images exhibit only a small decrease in detection accuracy.

Stochastic computing (SC) employs conventional logic circuits to implement analog-style arithmetic functions acting on digital bit-streams. It exploits the advantages of analog computation -powerful basic operations, high operating speed, and error tolerance- in important applications such as sensory image processing and neuromorphic systems. At the same time, SC exhibits the analog drawbacks of low precision and complex underlying behavior. Although studied since the 1960s, many of SC"s fundamental properties are not well known or well understood. This paper presents, in a uniform manner and notation, what is known about the relations between the logical and stochastic behavior of stochastic circuits. It also considers how correlation among input bit-streams and the presence of memory elements influences stochastic behavior. Some related research challenges posed by SC are also discussed.

Stochastic computing (SC) acts on data encoded by bit-streams, and is an attractive, low-cost and error-tolerant alternative to conventional binary circuits in some important applications such as image processing and communications. We study the use of energy reduction techniques such as voltage or frequency scaling in SC circuits. We show that due to their inherent error-tolerance, SC circuits operate satisfactorily without significant accuracy loss even with aggressive scaling that improves their energy efficiency by orders of magnitude. To find the minimum-energy operating point of an SC circuit, we propose a Markov chain model that allows us to quickly explore the space of operating points. We also investigate opportunities to optimize SC circuits under such aggressive scaling. We find that logical and physical design techniques can be used to significantly expand the already powerful accuracy-energy tradeoff possibilities in SC circuits. Our simulation results show that our optimized SC circuits can tolerate aggressive voltage scaling with no significant SNR degradation after 40% supply voltage reduction (1V to 0.6V), leading to 66% energy saving (20.7pJ to 6.9pJ). Similarly, a 100% frequency boosting (400ps to 200ps) of the optimized circuits leads to no significant SNR degradation for several representative circuits.

Stochastic computing (SC) is an approximate computing technique that processes data in the form of long pseudorandom bit-streams which can be interpreted as probabilities. Its key advantages are low-complexity hardware and high-error tolerance. SC has recently been finding application in several important areas, including image processing, artificial neural networks, and low-density parity check decoding. Despite a long history, SC still lacks a comprehensive design methodology, so existing designs tend to be either ad hoc or based on specialized design methods. In this paper, we demonstrate a fundamental relation between stochastic circuits and spectral transforms. Based on this, we propose a general, transform-based approach to the analysis and synthesis of SC circuits. We implemented this approach in a program spectral transform use in stochastic circuit synthesis (STRAUSS), which also includes a method of optimizing stochastic number-generation circuitry. Finally, we show that the area cost of the circuits generated by STRAUSS is significantly smaller than that of previous work.

Stochastic computing (SC) is a low-cost design technique that has great promise in applications such as image processing. SC enables arithmetic operations to be performed on stochastic bit-streams using ultra-small and low-power circuitry. However, accurate computations tend to require long run-times due to the random fluctuations inherent in stochastic numbers (SNs). We present novel techniques for SN generation that lead to better accuracy/run-time trade-offs. First, we analyze a property called progressive precision (PP) which allows computational accuracy to grow systematically with run-time. Second, borrowing from Monte Carlo methods, we show that SC performance can be greatly improved by replacing the usual pseudo-random number sources by low-discrepancy (LD) sequences that are predictably progressive. Finally, we evaluate the use of LD stochastic numbers in SC, and show they can produce significantly faster and more accurate results than existing stochastic designs.

Stochastic computing (SC) is a re-emerging technique to process probability data encoded in digital bit-streams. Its main advantage is that arithmetic operations can be implemented by extremely small and low-power logic circuits. This makes SC suitable for signal-processing applications involving matrix operations whose VLSI implementation is very costly. Previous SC approaches only address basic matrix operations with relatively low accuracy needs. We explore the use of SC to implement a representative complex matrix operation, namely eigenvector computation. We apply it to a training task for visual face recognition, and show that our SC design has performance comparable to its conventional binary counterpart, while being able to trade computation time for accuracy.

Stochastic computing (SC) is an approximate computing technique that represents data by probabilistic bit-streams called stochastic numbers (SNs). Arithmetic operations can be implemented at very low cost by means of SC. To achieve acceptable accuracy, interacting SNs must usually be statistically independent or uncorrelated. Correlation is poorly understood, however, and is a key problem in SC because of its impact on accuracy and the high cost of correlation-reducing logic. In this paper we analyze and quantify the role of correlation in stochastic circuit design. We use an algebraic framework based on probabilistic transfer matrices (PTMs) to analyze correlation-induced errors. We compare two systematic correlation-reducing methods, regeneration and isolation. Regeneration introduces new (pseudo) random sources to re-randomize SNs, while isolation uses delays (D flip-flops) to derive multiple independent SNs from a single random source. We present bounds on accuracy loss due to isolator insertion and compare its hardware cost to that of regeneration. We conclude that the isolation method can offer significant cost advantages in reducing correlation errors.

Real-time image-processing applications impose severe design constraints in terms of area and power. Examples of interest include retinal implants for vision restoration and on-the-fly feature extraction. This work addresses the design of image-processing circuits using stochastic computing techniques. We show how stochastic circuits can be integrated at the pixel level with image sensors, thus supporting efficient real-time (pre)processing of images. We present the design of several representative circuits, which demonstrate that stochastic designs can be significantly smaller, faster, more power-efficient, and more noise-tolerant than conventional ones. Furthermore, the stochastic designs naturally produce images with progressive quality improvement.

The Viterbi algorithm is widely used to decode convolutional codes. We present an unconventional approach to Viterbi decoder design based on stochastic computing (SC) which represents data by random bit-streams that can be interpreted as probabilities. Stochastic circuits allow many decoding functions to be implemented by simple hardware; e.g., multi-bit multiplication can be realized by an AND gate. SC is also highly error-tolerant since a soft error (bit-flip) has little impact on a SC number's value. It also allows decoding precision to be traded for decoding speed. We design two SC-based Viterbi decoders and also a hybrid binary-SC design; the latter uses SC for arithmetic calculations, but not for storing numbers. The proposed designs are compared with a binary (non-SC) decoder using a standard (7, 1/2) convolutional code. The SC designs are found to be more tolerant of soft errors in the decoder than the binary design, and more capable of supporting some useful trade-offs among area cost, data rate, precision, and bit-error rate.

Stochastic computing (SC) is a re-emerging computing paradigm which enables ultra-low power and massive parallelism in important applications like real-time image processing. It is characterized by its use of pseudo-random numbers implemented by 0-1 sequences called stochastic numbers (SNs) and interpreted as probabilities. Accuracy is usually assumed to depend on the interacting SNs being highly independent or uncorrelated in a loosely specified way. This paper introduces a new and rigorous SC correlation (SCC) measure for SNs, and shows that, contrary to intuition, correlation can be exploited as a resource in SC design. We propose a general framework for analyzing and designing combinational circuits with correlated inputs, and demonstrate that such circuits can be significantly more efficient and more accurate than traditional SC circuits. We also provide a method of analyzing stochastic sequential circuits, which tend to have inherently correlated state variables and have proven very hard to analyze.

Stochastic computing (SC) was proposed in the 1960s as a low-cost alternative to conventional binary computing. It is unique in that it represents and processes information in the form of digitized probabilities. SC employs very low-complexity arithmetic units which was a primary design concern in the past. Despite this advantage and also its inherent error tolerance, SC was seen as impractical because of very long computation times and relatively low accuracy. However, current technology trends tend to increase uncertainty in circuit behavior and imply a need to better understand, and perhaps exploit, probability in computation. This article surveys SC from a modern perspective where the small size, error resilience, and probabilistic features of SC may compete successfully with conventional methodologies in certain applications. First, we survey the literature and review the key concepts of stochastic number representation and circuit structure. We then describe the design of SC-based circuits and evaluate their advantages and disadvantages. Finally, we give examples of the potential applications of SC and discuss some practical problems that are yet to be solved.

A new approach to detecting and diagnosing faults in quantum circuits is introduced. In order to account for the probabilistic nature of quantum circuits, collections of test experiments, called binary tomographic tests (BTTs), are generated. A BTT can identify a fault with respect to some user-defined confidence threshold τ. We present an algorithm to generate BTTs that either detect, or ensure the absence of, all modeled faults in a given circuit. We also present an adaptive diagnostic method to locate quantum faults. While classical circuits, even probabilistic ones, only handle ordinary probabilities, quantum circuits deal with quantum states, which have phase as an extra probabilistic parameter. The tomographic testing methods introduced previously for probabilistic circuits are unable to detect differences in phase, and therefore leave many quantum faults undetected. In contrast, we develop a design-for-test method which is specifically intended to detect faults that only affect the phase of a quantum state. We give experimental results for benchmark and random circuits which show high coverage of quantum faults by BTTs, and good resolution in the case of the adaptive diagnosis method.

Monte Carlo (MC) simulation plays a key role in EDA as the gold standard against which heuristics are measured. It is also an important stand-alone technique for statistics-based tasks like power estimation and reliability analysis. Accurate simulation requires large sample sets and long runtimes, which can be hard to achieve with conventional MC. We propose an approach called Reduced-Ordered Monte Carlo (ROMC), which improves simulation efficiency, while still producing accurate results. ROMC takes advantage of the (partial) redundancy inherent in digital signals. It prioritizes input signals based on their observability at the outputs, and combines inputs based on a compatibility property that enables them to share samples. Experimental results are presented which demonstrate that the ROMC methodology can decrease simulation runtime by several orders of magnitude.

Stochastic computing (SC) processes data in the form of long pseudo-random bit-streams denoting probabilities. Its key advantages are simple computational elements and high soft-error tolerance. Recent technology developments have revealed important new SC applications such as image processing and LDPC decoding. Despite its long history, SC still lacks a comprehensive design methodology; existing methods tend to be ad hoc and limited to a few arithmetic functions. We demonstrate a fundamental relation between stochastic circuits and spectral transforms. Based on this, we propose a transform approach to the analysis and synthesis of SC circuits. We illustrate the approach for a variety of basic combinational SC design problems, and show that the area cost associated with stochastic number generation can be significantly reduced.

Electronic systems on a chip increasingly suffer from component variation, voltage noise, thermal hotspots, and other subtle physical phenomena. Systems with reconfigurability have unique opportunities for adapting to such effects. Required, however, are low-cost, fine-grained methods for sensing physical parameters. This article presents powerful, novel approaches to online sensing, including methods for designing compact reconfigurable sensors, low-cost threshold detection, and several enhanced measurement procedures. Together, the approaches help enable systems to autonomously uncover a wealth of physical information. A highly efficient counter and improved ring oscillator are introduced, enabling an entire sensor node in just 8 Virtex-5 LUTs. We describe how variations can be measured in delay, temperature, switching-induced IR drop, and leakage-induced IR drop. We demonstrate the proposed approach with an experimental system based on a Virtex-5, instrumented with over 100 sensors at an overhead of only 1.3%. Results from thermally controlled experiments provide some surprising insights and illustrate the utility of the approach. Online sensing can help open the door to physically adaptive computing, including fine-grained power, reliability, and health management schemes for systems on a chip.

We present a novel trigonometry-based probability calculation (TPC) method for analyzing circuit behavior and reliability in the presence of errors that occur with extremely low probability. Signal and error probabilities are represented by trigonometric functions controlled by their corresponding angles. By combining trigonometric identities and Taylor expansions, the effect of an error at a particular gate is simulated as a rotation. In addition, the correlations among signals caused by reconvergence are carefully handled. The TPC method is shown to be more scalable and accurate than prior approaches, especially for very low-probability errors. We measure the performance of TPC by applying it to the ISCAS and LGSyn-91 benchmark circuits. Experimental results show that TPC achieves near-linear runtime complexity even with the largest circuits, while the accuracy gradually increases with decreasing error probabilities.

Wafer testing via direct-contact probe cards has long been an effective and relatively low-cost method for testing integrated circuit (IC) chips prior to packaging. However, the physical contact occurring between the wafer and automatic test equipment (ATE) has significant costs due to contact point deformation and the need for abrasive cleaning. In this paper, we investigate a non-contact testing technique that wirelessly couples an IC wafer and ATE, and serves as an alternative to conventional probe-card testing. We derive several analytical models for a capacitive testing channel. Electromagnetic field simulations results are presented that support the proposed channel models. We conclude that capacitance-based wireless testing is feasible for testing ICs in the 1-GHz range.

Some emerging technologies for building computers depend on components and signals whose behavior, under normal or fault conditions, is probabilistic. Examples include stochastic and quantum computing circuits, and conventional nano electronic circuits subject to design, manufacturing or environmental errors. Problems common to these technologies are testing and validation, which require determining whether observed non-deterministic behavior is within acceptable limits. Traditional solution methods rely on the determinism of operations performed by the circuit under test, and are not applicable to probabilistic circuits, where signals are often described by probability distributions. We introduce a generic methodology for testing probabilistic circuits by approximating signal probability distributions using tomograms, which aggregate the outcomes of multiple, repeated test measurements. While the name comes from quantum computation, tomography is applicable to both quantum and non-quantum probabilistic circuits, as we demonstrate. Our methodology makes use of fault or error models that allow handling of large and complex circuits. We report the first experimental results on the tomographic testing of quantum and stochastic circuits.

Transient or soft errors caused by various environmental effects are a growing concern in micro and nanoelectronics. We present a general framework for modeling and mitigating the logical effects of such errors in digital circuits. We observe that some errors have time-bounded effects; the system's output is corrupted for a few clock cycles, after which it recovers automatically. Since such erroneous behavior can be tolerated by some applications, i.e., it is noncritical at the system level, we define the critical soft error rate (CSER) as a more realistic alternative to the conventional SER measure. A simplified technology-independent fault model, the single transient fault (STF), is proposed for efficiently estimating the error probabilities associated with individual nodes in both combinational and sequential logic. STFs can be used to compute various other useful metrics for the faults and errors of interest, and the required computations can leverage the large body of existing methods and tools designed for (permanent) stuck-at faults. As an application of the proposed methodology, we introduce a systematic strategy for hardening logic circuits against transient faults. The goal is to achieve a desired level of CSER at minimum cost by selecting a subset of nodes for hardening against STFs. Exact and approximate algorithms to solve the node selection problem are presented. The effectiveness of this approach is demonstrated by experiments with the ISCAS-85 and -89 benchmark suites, as well as some large (multimillion-gate) industrial circuits.

Electronic systems increasingly suffer from component variation, thermal hotspots, uneven wearout, and other subtle physical phenomena. Systems based on FPGAs have unique opportunities for adapting to such effects. Required, however, is a low-cost, fine-grained method for sensing physical parameters. This paper presents an approach to on-line sensing that includes a compact multi-use sensor implemented in reconfigurable logic, methods for instrumenting an application, and enhanced measurement procedures. The sensor utilizes a highly-efficient counter and improved ring oscillator, and requires just 8 LUTs. We describe how to measure variations in delay, static power, dynamic power, and temperature. We demonstrate the proposed approach with an experimental system based on a Virtex-5. The system is instrumented with over 100 sensors with a total overhead of only 1.3%. Results from thermally-controlled experiments provide some surprising insights and illustrate the power of the approach. On-line sensing can help open the door to physically-adaptive computing, including fine-grained power, reliability, and health management schemes for FPGA-based systems.

Random physical variations and noise are growing challenges for advanced electronic systems. Field programmable systems can, in principle, adapt to these phenomena, but two main problems must be addressed: how to efficiently characterize random variations and how to perform subsequent optimization. This paper addresses both of these questions. First, an approach to self-test is presented that uses on-chip noise emulation to quickly characterize some of the hidden variations in latches. Our noise-injection experiments demonstrate that there can be significant spreads in latch reliability even with current 65nm field-programmable gate arrays (FPGAs). We detected coefficients of variation as high as 77%. Second, we propose an approach to self-optimization using local resource swapping. Experiments on two FPGAs show improvements in mean-time-between-failures (MTBF) of up to 60%.

We present a new methodology for fast and accurate simulation of signal probabilities in sequential logic. It can be used for analyzing soft error effects at the logic level, estimating circuit reliability, and the like. Experimental results for large benchmarks show that signal error probabilities can be estimated over many cycles with high accuracy.

State elements are increasingly vulnerable to soft errors due to their decreasing size, and the fact that latched errors cannot be completely eliminated by electrical or timing masking. Most prior methods of reducing the soft-error rate (SER) involve combinational redesign, which tends to add area and decrease testability, the latter a concern due to the prevalence of manufacturing defects. Our work explores the fundamental relations between the SER of sequential circuits and their testability in scan mode, and appears to be the first to improve both through retiming. Our retiming methodology relocates registers so that 1) registers become less observable with respect to primary outputs, thereby decreasing overall SER, and 2) combinational nodes become more observable with respect to registers (but not with respect to primary outputs), thereby increasing scan-testability. We present experimental results which show an average decrease of 42% in the SER of latches, and an average improvement of 31% random-pattern testability.

The traditionally wired interfaces of many electronic systems are in many applications being replaced by wireless interfaces. Testing of electronic systems (both integrated circuits and printed circuit boards) still requires physical electrical contact through probe needles and/or sockets. This paper addresses the state-of-the-art, options, and hurdles-still-to-take of contactless testing, which would resolve many test challenges due to shrinking size and pitch of pads and pins and inaccessibility of advanced assembly techniques as System-in-Package (SiP) and 3D stacked ICs.

The amount of physical variation among electronic components on a die is increasing rapidly. There is a need for a better understanding of variations in transient fault susceptibility, and for methods of on-line adaptation to such variations. We address three key research questions in this area. First, we investigate accelerated characterization of individual latch susceptibilities. We find that on the order of 10 upsets per latch must be observed for variations to be adequately characterized. Second, we propose a method of on-line hardware reconfiguration using incremental place-and-route on FPGAs. Surprisingly, we find that highly localized place-and-route changes (e.g. restricted to groups of 8 flip-flops) are sufficient for realizing most of the possible benefits. Lastly, we quantify potential improvements in system-level soft error rates via Monte Carlo simulation experiments. The study highlights both what is required for and what can be gained by on-line adaptation.

We explore the use of signatures, i.e., partial truth tables generated via bit-parallel functional simulation, during soft error analysis and logic synthesis. We first present a signature-based CAD framework that incorporates tools for the logic-level Analysis of Soft Error Rate (x) and for Signature-based Design for Reliability (SiDeR). We observe that the soft error rate (SER) of a logic circuit is closely related to various testability parameters, such as signal observability and probability. We show that these parameters can be computed very efficiently (in linear time) by means of signatures. Consequently, AnSER evaluates logic masking two to three orders of magnitude faster than other SER evaluators while maintaining accuracy. AnSER can also compute SER efficiently in sequential circuits by approximating steady-state probabilities and sequential signal observabilities. In the second part of this paper, we incorporate AnSER into logic synthesis design flows aimed at reliable circuit design. SiDeR identifies and exploits redundancy already present in a circuit via signature comparison to decrease SER. We show that SiDeR reduces SER by 40% with only 13% area overhead. We also describe a second signature-based synthesis strategy that employs local rewriting to simultaneously improve area and decrease SER. This technique yields 13% reduction in SER with a 2% area decrease. We show that combining the two synthesis approaches can result in further area-reliability improvements.

Soft errors, once only of concern in memories, are beginning to affect logic as well. Determining the soft error rate (SER) of a combinational circuit involves three main masking mechanisms: logic, timing and electrical. Most previous papers focus on logic and electrical masking. In this paper we develop static and statistical analysis techniques for timing masking that estimate the error-latching window of each gate. Our SER evaluation algorithms incorporating timing masking are orders of magnitude faster than comparable evaluators and can be used in synthesis and layout. We show that 62 % of gates identified as error-critical using timing masking would not be identifiable by considering only logic masking. Furthermore, hardening the top 10 % of errorcritical gates leads to a 43 % reduction in the SER. We also propose a more subtle solution, gate-relocation for technologies where wire delay dominates gate delay. We decrease the error-latching window of each gate by relocating it in such a way that path lengths to primary outputs are equalized. Our results show a 14 % improvement in SER with no area overhead. 1

Energy conservation is a key issue in ad hoc wireless network operation. Placing relay nodes (routers) at appropriate locations can substantially lower the power requirements of communicating nodes, thereby reducing overall energy needs. We investigate router placement (RP) for energy-constrained wireless networks, and present RP algorithms that aim to minimize total energy consumption. We consider the RP problem for multi-hop wireless networks, and develop an efficient heuristic solution for them. We model multiple-router placement as a clustering optimization problem in which routers and nodes are treated as clusterheads and cluster members, respectively. We also devise a heuristic that discovers the central area of a multi-hop network, and solves the RP problem with multi-hop connectivity. Simulation results confirm that our RP methods reduce the energy consumption of wireless networks by up to 55% compared with grid networks.

We propose the probabilistic transfer matrix (PTM) framework to capture nondeterministic behavior in logic circuits. PTMs provide a concise description of both normal and faulty behavior, and are well-suited to reliability and error susceptibility calculations. A few simple composition rules based on connectivity can be used to recursively build larger PTMs (representing entire logic circuits) from smaller gate PTMs. PTMs for gates in series are combined using matrix multiplication, and PTMs for gates in parallel are combined using the tensor product operation. PTMs can accurately calculate joint output probabilities in the presence of reconvergent fanout and inseparable joint input distributions. To improve computational efficiency, we encode PTMs as algebraic decision diagrams (ADDs). We also develop equivalent ADD algorithms for newly defined matrix operations such as eliminate_variables and eliminate_redundant_variables , which aid in the numerical computation of circuit PTMs. We use PTMs to evaluate circuit reliability and derive polynomial approximations for circuit error probabilities in terms of gate error probabilities. PTMs can also analyze the effects of logic and electrical masking on error mitigation. We show that ignoring logic masking can overestimate errors by an order of magnitude. We incorporate electrical masking by computing error attenuation probabilities, based on analytical models, into an extended PTM framework for reliability computation. We further define a susceptibility measure to identify gates whose errors are not well masked. We show that hardening a few gates can significantly improve circuit reliability.

Transient errors have become a major concern due to advances in technology scaling. Existing detection techniques for these errors, such as dual modular redundancy (DMR), have very high area overhead as they typically target all possible faults. In this paper, we analyze the effect of transient faults on sequential circuit behavior. We introduce the notion of transition errors (TEs) to capture the critical errors caused by both transient and permanent faults. We also present an error-monitoring scheme aimed specifically at TEs. Finally we describe experiments using the MCNC synthesis benchmark suite which show that, using the proposed monitoring scheme, all TEs can be detected with about 36% area overhead, which is significantly less than alternative approaches like DMR.

While circuit density and power efficiency increase with each major advance in IC technology, reliability with respect to soft errors tends to decrease. Current solutions to this problem such as TMR require high area and power overhead. In this work, soft-error reliability is improved with minimal area overhead by careful, localized circuit restructuring. The key idea is to increase logic masking of errors by taking advantage of conditions already present in the circuit, such as observability don't-cares. We describe two circuit modification techniques to improve reliability: don't-care-based resynthesis and local rewriting. A key feature of these techniques is fast, on-the-fly estimation of soft error rate (SER) using our reliability evaluator AnSER. This tool is compared against prior SER evaluators and found to run orders of magnitude faster. We show empirically that our reliability-driven synthesis methods can reduce SER by 29-40% with only 5-13% area overhead.

Among the post-CMOS technologies currently under investigation, quantum computing (QC) holds a special place. QC offers not only extremely small size and low power, but also exponential speed-ups for important simulation and optimization problems. It also poses new CAD problems that are similar to. but more challenging, than the related problems in classical (non-quantum) CAD. such as determining if two states or circuits are functionally equivalent. While differences in classical states are easy to detect, quantum states, which are represented by complex-valued vectors, exhibit subtle differences leading to several notions of equivalence. This provides flexibility in optimizing quantum circuits, but leads to difficult new equivalence-checking issues for simulation and synthesis. We identify several different equivalence-checking problems and present algorithms for practical benchmarks, including quantum communication and search circuits, which are shown to be very fast and robust for hundreds of qubits.

We propose a power-aware link maintenance (PALM) algorithm for mobile ad hoc networks (MANETs) that simultaneously performs transmission power control and route connectivity maintenance. Unlike most topology control algorithms, PALM manages the transmission power of active nodes only, and thus eliminates energy and channel resource waste due to unnecessary beaconing. The basic idea of PALM is that by recording the received signal strength on packets, each node continuously estimates the required transmission power, and adapts to location changes due to mobility. We also introduce some efficient local link repair schemes. When a route change is needed due to node movement, overhearing nodes participate in data forwarding, and locally repair the route before disconnection without the need to propagate route error messages. Through these operations, PALM prevents frequent link breaks due to node mobility, reduces the occurrence of rerouting, and significantly improves network performance. Experimental results with the ns simulator confirm that PALM effectively conserves communication energy with modest overhead.

Transient or soft errors are an increasing problem in mainstream microelectronics. We propose a framework for modeling transient-error tolerance (TET) in logic circuits. We classify transient errors as critical or non-critical according to their impact on circuit behavior, such as their ability to disturb the internal state for specified periods of time. We introduce a metric called the critical soft-error rate (CSER) as an alternative to conventional SER, and present some analysis strategies based on CSER. This approach employs a new single transient fault (STF) model, which is defined in terms of a temporary stuck-at fault and its associated circuit state. Although basically technology-independent, STFs can be extended with low-level physical attributes. With STFs, we can estimate the transient error probability perrof a circuit's nodes, as well as various measures of error susceptibility and TET. We demonstrate the use of STFs with combinational and sequential circuits, including several types of adders. We also present a systematic hardening strategy that uses perras a guide to improving TET.

A central problem in built-in self test (BIST) is how to efficiently generate a small set of test vectors that detect all targeted faults. We propose a novel solution that uses linear algebraic concepts to partition the vector space of tests into subspaces (clusters). A subspace is defined by a compact set of basis vectors. We give an algorithm to compute sets of basis vectors defining the clusters. We also describe a low-cost logic circuit based on Gray codes that reproduces the subspaces from these basis vectors. Experimental results are presented which show that this approach reduces on-chip hardware overhead and test application time, while also guaranteeing full fault coverage

Reversible logic is motivated by low-power design, quantum circuits, and nanotechnology. We develop a compact representation of small reversible circuits to generate and store optimal circuits for all 40,320 three-input reversible functions, and millions of four-input circuits. This allows implementing a function optimally in constant time for use in the peephole optimization of larger circuits produced by existing techniques, and guarantees that every three-bit subcircuit is optimal. To generate subcircuits, we use a graph-based data structure and algorithms for circuit restructuring. Finally, we demonstrate a suboptimal circuit for which peephole optimization fails.

Leakage power consumption is an increasingly serious problem in very large-scale integration circuits, especially for portable applications. Two novel approaches to leakage power minimization in static complementary metal–oxide–semiconductor circuits that employ input vector control (IVC) are investigated. The authors model leakage effects by means of pseudo-Boolean functions. These functions are linearized and incorporated into an exact (optimal) integer linear programming (ILP) model, called virtual-gate ILP, which analyzes leakage variation with respect to a circuit's input vectors. A heuristic mixed-integer linear programming (MLP) method is also proposed, which has several advantages: it is faster, its accuracy can be quickly estimated, and tradeoffs between runtime and optimality can easily be made. Furthermore, the MLP model also provides a way to estimate a lower bound on circuit leakage current. The proposed methods are used to generate an extensive set of experimental results on leakage reduction. It is shown that average leakage currents are usually 1.25 times the minimum, confirming the effectiveness of IVC. The heuristic MLP approach is shown to be approximately 13.6 times faster than the exact ILP method, whereas finding input vectors whose power consumption is only a few percent above the optimum. In addition, the lower bound estimated by the MLP model is also within a few percent of the optimal value.

Circuits containing functional blocks (modules) whose implementation details are not available pose major problems for delay fault testing. High-level testing methods are needed, but they often generate excessively large test sets to ensure good realization-independent fault coverage. This paper extends high-level delay fault models to large modular logic circuits by demonstrating that a hierarchical approach to delay test generation for modular circuits is feasible. Module implementation and input pattern pair requirements for robust delay testing are proposed along with a new fault model, the module path delay fault (MPDF) model. A test generation program called Module PATH delay test generator for MPDFs is presented, which exploits binary decision diagrams to increase its efficiency. Experimental results evaluating the proposed technique are presented, which show that it achieves a significant reduction in test set size compared to nonhierarchical approaches.

Quantum computing is a recently developed approach to information processing, which is based on quantum mechanics rather than classical physics. Information is represented by quantum bits (qubits) that correspond to microscopic states such as photon polarization. Up to 2n n-bit words can be stored simultaneously in n qubits, implying a type of massive parallelism. Powerful forms of quantum interaction such as interference and entanglement exist which have no counterparts in classical computer science. Some important and hitherto intractable problems such as prime factorization of large numbers can be solved efficiently using quantum methods. In practice, however, quantum computing devices and circuits are extremely difficult to design and build, since they are nanoscale in size and operate at very low energy levels. Consequently, they have many more failure modes than classical (non-quantum) circuits. For example, quantum signal states are inherently unstable and tend to decay rapidly due to interaction with the environment (decoherence). Quantum gate operations are defined by continuous parameters that allow small errors to arise and propagate to other gates. Furthermore, state measurement is probabilistic and the measurement process itself affects the state being measured. This talk will review the history and development of quantum circuits, with emphasis on their failure modes and testing requirements. It will be seen that quantum circuits are highly testable for classical faults. However, they are also subject to various complex, nonclassical failure modes, which are still not well understood. Some methods for error correction and recovery that have been developed specifically for quantum circuits will also be reviewed.

Reversibility is of interest in achieving extremely low power dissipation; it is also an inherent design requirement of quantum computation. Logical fault models for conventional circuits such as stuck-at models are not wellsuited to quantum circuits. We derive a family of logical fault models for reversible circuits composed of k- CNOT (k-input controlled-NOT) gates and implementable by many technologies. The models are extensions of the previously proposed single missing-gate fault (MGF) model, and include multiple and partial MGFs. We study the basic detection requirements of the new fault types and derive bounds on the size of their test sets. We also present optimal test sets computed via integer linear programming for various benchmark circuits. These results indicate that, although the test sets are generally very small, partial MGFs may need significantly larger test sets than single MGFs.

Minimizing power consumption is one of the most important objectives in IC design. Resizing gates and assigning different Vt's are common ways to meet power and timing budgets. We propose an automatic implementation of both these techniques using a mixedinteger linear programming model called MLP-exact, which minimizes a circuit's total active-mode power consumption. Unlike previous linear programming methods which only consider local optimality, MLP-exact, can find a true global optimum. An efficient, non-optimal way to solve the MLP model, called MLP-fast,, is also described. We present a set of benchmark experiments which show that MLP-fast, is much faster than MLP-exact,, while obtaining designs with only slightly higher power consumption. Furthermore, the designs generated by MLP-fast, consume 30% less power than those obtained by conventional, sensitivity-based methods.

Soft errors are an increasingly serious problem for logic circuits. To estimate the effects of soft errors on such circuits, we develop a general computational framework based on probabilistic transfer matrices (PTMs). In particular, we apply them to evaluate circuit reliability in the presence of soft errors, which involves combining the PTMs of gates to form an overall circuit PTM. Information, such as output probabilities, the overall probability of error, and signal observability, can then be extracted from the circuit PTM. We employ algebraic decision diagrams (ADDs) to improve the efficiency of PTM operations. A particularly challenging technical problem, solved in our work, is to extend simultaneously tensor products and matrix multiplication in terms of ADDs to non-square matrices. Our PTM-based method enables accurate evaluation of reliability for moderately large circuits and can be extended by circuit partitioning. To demonstrate the power of the PTM approach, we apply it to several problems in fault-tolerant design and reliability improvement.

Transient faults are becoming an increasingly serious concern for logic circuits. They can be caused by thermal neutrons, present at all altitudes, and by other types of ionizing radiation, especially in aerospace applications and nuclear engineering. In this paper we examine issues related to detection of transient errors. The difficulty in testing for transient errors is that they are not always present. Test vectors need to be repeated a number of times in order to detect a fault. We show how to compute a measure for the detectability of transient faults with respect to specific test vectors. This is done using a matrix-based gate-fault model known as the probabilistic transfer matrix model. Using this detectability measure we derive methods to generate multisets of tests to verify probability distributions of faults and detect abnormalities in circuit behavior. Applications of this method include detection of increased atmospheric radiation in terms of its impact on circuits, and testing for process variation that increases the susceptibility of a circuit to transient errors.

Technology trends are increasing the frequency of serious transient (soft) faults in digital systems. For example, ICs are becoming more susceptible to cosmic radiation, and are being embedded in applications with dynamic noisy environments. We propose a generic framework for representing such faults and characterizing them on-line. We formally define the impact of a transient fault in terms of three basic parameters: frequency, observability and severity. We distinguish fault modes in systems whose noise environment changes dynamically. Based on these ideas, the problem of designing on-line architectures for transient fault characterization is formulated and analyzed for several optimization goals. Finally, experiments are described that determine transient fault impact and the corresponding tests for various simulated fault modes of the ISCAS-89 benchmark circuits.

The performance of mobile ad hoc networks is highly sensitive to changes in node-to-node connections (communication links) caused by node movement. Link instability of this kind has proven very difficult to analyze mathematically so previous work has relied heavily on simulation. We present a mathematically tractable model of node motion, the constant velocity model, and use it to derive a precise relation between mobility and connection stability. Our analysis also allows determination of the appropriate frame length for successful and efficient single-hop communication. We further investigate connection stability in multi-hop communication, and uncover some underlying properties of previously proposed mobility metrics. In particular, we demonstrate that link duration has a strong invariant relationship with the stability of multi-hop connections for a wide range of mobility models, and thus is an excellent mobility metric.

We present an exact solution to the technology mapping problem for field-programmable gate arrays (FPGAs), where the objective is to minimize the number of lookup tables (LUTs) required to map a logic circuit. The key idea is to compactly formulate the mapping problem as a mixed-integer linear-programming (MILP) problem, which can then be solved by any off-the-shelf MILP solver. MILP problem formulations are systematically developed for various classes of circuits with increasing complexities-trees, monotone circuits, and general nonmonotone circuits, where the monotonicity of a circuit implies that the number of signals increases monotonically as the circuit is traversed from primary outputs to primary inputs. Several circuit properties related to reconvergent paths and monotone signal sets are determined, which provide insight into the mapping problem for LUTs. Our experiments show that optimal mappings for circuits with several hundred gates can be obtained very quickly by solving their MILP formulations exactly. For larger circuits, we present two powerful heuristic approximation methods based on partitioning the circuit or simplifying its structure. We show that these approximations yield near-optimal solutions for several benchmark circuits.

Advanced automotive control applications such as steer-by-wire are typically implemented as distributed systems comprising many embedded processors, sensors, and actuators interacting via a communication bus. They have severe cost constraints, but demand a high level of safety and performance. Motivated by the need for timely diagnosis of faulty actuators in such systems, we present a method to achieve distributed failure diagnosis under deadline and resource constraints. Actuators are diagnosed in distributed fashion by processors to provide a global view of their fault status. The integration of software-based tests for actuator diagnosis within the overall control application is studied. These tests are implemented using analytical redundancy and execute concurrently with the control tasks. The test scheduling problem is then formulated and solved to guarantee actuator diagnosis within designer-specified deadlines while meeting control performance goals. As a secondary objective, the scheduling algorithm also reduces the number of processors required for diagnosis. We demonstrate the practicality of the proposed diagnosis approach by applying it to a steer-by-wire example to identify failed actuators in timely fashion.

Logical reversibility occurs in low-power applications and is an essential feature of quantum circuits. Of special interest are reversible circuits constructed from a class of reversible elements called k-CNOT (controllable NOT) gates. We review the characteristics of k-CNOT circuits and observe that traditional fault models like the stuck-at model may not accurately represent their faulty behavior or test requirements. A new fault model, the missing gate fault (MGF) model, is proposed to better represent the physical failure modes of quantum technologies. It is shown that MGFs are highly testable, and that all MGFs in an N-gate k-CNOT circuit can be detected with from one to [N/2] test vectors. A design-for-test (DFT) method to make an arbitrary circuit fully testable for MGFs using a single test vector is described. Finally, we present simulation results to determine (near) optimal test sets and DFT configurations for some benchmark circuits.

Simulating quantum computation on a classical computer is a difficult problem. The matrices representing quantum gates, and vectors modeling qubit states grow exponentially with the number of qubits. It has been shown experimentally that the QuIDD (Quantum Information Decision Diagram) datastructure greatly facilitates simulations using memory and runtime that are polynomial in the number of qubits. In this paper, we present a complexity analysis which formally describes this class of matrices and vectors. We also present an improved implementation of QuIDDs which can simulate Grover's algorithm for quantum search with the asymptotic runtime complexity of an ideal quantum computer up to negligible overhead.

Transmitting messages in mobile wireless networks typically involves on-demand route discovery implemented via network-wide broadcast. Due to the dynamic nature of the network topology the life-time of a route is very short, so a source frequently requires a new route to an old destination. Simultaneous discovery of multiple routes can reduce the overhead due to repeated route discovery broadcasts. Previously proposed multipath protocols do not guarantee discovery of alternative paths if they exist. We propose a multiple route discovery algorithm (ALTDSR) that finds a (multihop) primary path between a source and a destination, and a set of alternative paths. We introduce dominator relationships between primary and non-primary path nodes. Using dominators, we characterize alternative paths that bypass an intermediate node on the primary path. We develop algorithms that guarantee finding a set of alternative paths to tolerate any single node fault on the primary path, if such a set of alternative paths exists. We present simulation results which show that under high mobility conditions, ALTDSR delivers substantially more packets (around 75% more) than dynamic source routing (DSR) with moderate increase in routing overhead.

We present two approaches to leakage power minimization in static CMOS circuits by means of input vector control (IVC). We model leakage effects using pseudo-Boolean functions. These are incorporated into an optimal integer linear programming model called VG-ILP that analyzes leakage variation with respect to a circuit's input vectors. A heuristic mixed-integer linear programming (MLP) method is also presented which has several advantages: it is faster, its accuracy can be quickly estimated, and trade-offs between runtime and optimality can easily be made. The proposed methods are used to generate a large set of experimental results on leakage reduction. It is shown that average leakage currents are usually 1.25 times the minimum, confirming the effectiveness of IVC. The heuristic MLP approach is much faster than exact ILP, while finding input vectors whose power consumption is only a few percent from the optimum.

Leakage current is a key factor in IC power consumption even in the active operating mode. We investigate the simultaneous optimization of gate size and threshold voltage to reduce leakage power. We assume a standard-cell-based design flow where the available cell sizes and threshold voltages (V/sub t/'s) are given, and model the optimization as a mixed-integer linear programming (MLP) problem. In addition to the exact model, two faster approximate MLP models are proposed, along with CAD tools that generate the models automatically. We present experimental results which show that optimal designs derived from the exact MLP model can achieve the same performance as all-low-V/sub t/ unit-size designs, but with only one third the leakage power. The approximate MLP models can be solved about 25 times faster than the optimal model with negligible errors. All the proposed models can be extended to take dynamic power and multiple supply voltages into consideration.

Applications of reversible circuits can be found in the fields of low-power computation, cryptography, communications, digital signal processing, and the emerging field of quantum computation. Furthermore, prototype circuits for low-power applications are already being fabricated in CMOS. Regardless of the eventual technology adopted, testing is sure to be an important component in any robust implementation. We consider the test-set generation problem. Reversibility affects the testing problem in fundamental ways, making it significantly simpler than for the irreversible case. For example, we show that any test set that detects all single stuck-at faults in a reversible circuit also detects all multiple stuck-at faults. We present efficient test-set constructions for the standard stuck-at fault model, as well as the usually intractable cell-fault model. We also give a practical test-set generation algorithm, based on an integer linear programming formulation, that yields test sets approximately half the size of those produced by conventional automatic test pattern generation.

Simulating quantum computation on a classical computer is a difficult problem. The matrices representing quantum gates, and vectors modeling qubit states grow exponentially with an increase in the number of qubits. However, by using a new data structure called the Quantum Information Decision Diagram (QuIDD) that exploits the structure of quantum operators, many of these matrices and vectors can be represented in a form that grows polynomially. Using QuIDDs, we implemented a general-purpose quantum computing simulator in C++ called QuIDDPro and tested it on Grover's algorithm. Our QuIDD technique asymptotically outperforms other known simulation techniques.

Over the last decade a new way to compute has been defined which, unlike conventional methods, is based on quantum mechanics rather than classical physics. This fundamental change in paradigm can, in principle, solve some important and hitherto intractable problems such as prime factorization of large numbers. This tutorial presentation will review the basics of quantum computation and the design of circuits to implement quantum algorithms. The starting point is the notion of a quantum bit or qubit. Because of the superposition property of quantum states, n qubits can store 2n numbers simultaneously, implying a type of massive parallelism. Furthermore, quantum states allow powerful forms of interaction such as entanglement that have no classical counterparts. Qubits are fragile, however, and are altered by measurement; hence quantum circuits must follow very different rules from classical ones. The differences between quantum and classical logic circuits will be discussed and illustrated. Finally, the physical implementation of quantum devices will be considered, along with the prospects for practical quantum computers.

A control flow fault occurs when a processor fetches and executes an incorrect next instruction. Executable assertions, i.e., special instructions that check some invariant properties of a program, provide a powerful and low-cost method for on-line detection of hardware-induced control flow faults. We propose a technique called ACFC (Assertions for Control Flow Checking) that assigns an execution parity to a basic block, and uses the parity bit to detect faults. Using a graph model of a program, we classify control flow faults into skip, re-execute and multi-path faults. We derive some necessary conditions for these faults to manifest themselves as execution parity errors. To force a control flow fault to excite a parity error, the target program is instrumented with additional instructions. Special assertions are inserted to detect such parity errors. We have a developed a preprocessor that takes a C program as input and inserts ACFC assertions automatically. We have implemented a software-based fault injection tool SFIG which takes advantage of the GNU debugger. Fault injection experiments show that ACFC incurs less performance overhead (around 47%) and memory overhead (around 30%) than previous techniques, with no significant loss in fault coverage.

The power consumption of a sequential circuit can be reduced by decomposing it into subcircuits which can be turned off when inactive. Power can also be reduced by careful state encoding. Modeling a given circuit as a finite-state machine, we formulate its decomposition into submachines as an integer linear programming (ILP) problem, and automatically generate the ILP model with power minimization as the objective. A simple, but powerful state encoding method is used for the submachines to further reduce power consumption. We present experimental results which show that circuits designed by our approach consume 30% to 90% less power than conventional circuits.

Irreversible computation necessarily results in energy dissipation due to information loss. While small in comparison to the power consumption of today's VLSI circuits, if current trends continue this will be a critical issue in the near future. Reversible circuits offer an alternative that, in principle, allows computation with arbitrarily small energy dissipation. Furthermore, reversible circuits are essential components of quantum logic. We consider the problem of testing these circuits, and in particular generating efficient test sets. The reversibility property significantly simplifies the problem, which is generally hard for the irreversible case. We discuss conditions for a test set to be complete, give a number of practical constructions, and consider test sets for worst-case circuits. In addition, we formulate the problem of finding minimal test sets into an integer linear program (ILP) with binary variables. While this ILP method is infeasible for large circuits, we show that combining it with a circuit decomposition approach yields a practical alternative.

Reversible or information-lossless circuits have applications in digital signal processing, communication, computer graphics, and cryptography. They are also a fundamental requirement in the emerging field of quantum computation. We investigate the synthesis of reversible circuits that employ a minimum number of gates and contain no redundant input-output line-pairs (temporary storage channels). We prove constructively that every even permutation can be implemented without temporary storage using NOT, CNOT, and TOFFOLI gates. We describe an algorithm for the synthesis of optimal circuits and study the reversible functions on three wires, reporting the distribution of circuit sizes. We also study canonical circuit decompositions where gates of the same kind are grouped together. Finally, in an application important to quantum computing, we synthesize oracle circuits for Grover's search algorithm, and show a significant improvement over a previously proposed synthesis algorithm.

A review of traditional IC failure analysis techniques strongly indicates the need for fault models that directly analyze the function of circuit primitives. The input pattern (IP) fault model is a functional fault model that allows for both complete and partial functional verification of every circuit module, independent of the design level. We describe the IP fault model and provide a method for analyzing IP faults using standard single stuck-line- (SSL-) based fault simulators and test generation tools. The method is used to generate test sets that target the IP faults of the ISCAS85 benchmark circuits and a carry-lookahead adder. Improved IP fault coverage for the benchmarks and the adder is obtained by adding a small number of test patterns to tests that target only SSL faults. We also conducted fault simulation experiments that show IP test patterns are effective in detecting nontargeted faults such as bridging and transistor stuck-on faults. Finally, we discuss the notion of IP redundancy and show how large amounts of this redundancy exist in the benchmarks and in SSL-irredundant adder circuits.

Advanced automotive control applications such as steer and brake-by-wire are typically implemented as distributed systems comprising many embedded processors, sensors, and actuators interconnected via a communication bus. They have severe cost constraints but demand a high level of safety and performance. Motivated by the need for timely diagnosis of faulty actuators in such systems, we present a general method to implement failure diagnosis under deadline and resource constraints. Actuators are diagnosed in distributed fashion by processors to provide a global view of their fault status. The diagnostic tests are implemented in software using analytical redundancy and execute concurrently with the control tasks. The proposed method solves the test scheduling problem using a static list-based approach which guarantees actuator diagnosis within designer-specified deadlines while meeting control performance goals. As a secondary objective, it also minimizes the number of required processors. We present simulation results evaluating the effectiveness of the proposed method under various design constraints.

Reversible or information-lossless circuits have applications in digital signal processing, communication, computer graphics and cryptography. They are also a fundamental requirement in the emerging field of quantum computation. We investigate the synthesis of reversible circuits that employ a minimum number of gates and contain no redundant input-output line-pairs (temporary storage channels). We prove constructively that every even permutation can be implemented without temporary storage using NOT, CNOT and TOFFOLI gates. We describe an algorithm for the synthesis of optimal circuits and study the reversible functions on three wires, reporting distributions of circuit sizes. Finally, in an application important to quantum computing, we synthesize oracle circuits for Grover's search algorithm, and show a significant improvement over a previously proposed synthesis algorithm.

We present a general technology-mapping methodology (TULIP) for field-programmable gate arrays (FPGAs) that can yield optimal results, and is applicable to any FPGA with a logic block composed of lookup tables (LUTs). We introduce the concept of a virtual switch to model the internal connections of a logic block with multiple LUTs; each configuration of virtual switches is called a multiple-LUT block (MLB). A logic block can be precisely defined by a small but complete set of representative configurations called an MLB basis. The MLB bases for various commercial FPGA families are demonstrated. Given a logic block represented by its MLB basis, technology mapping is precisely formulated as a graph-covering problem, which is transformed into a mixed integer-linear programming (MILP) optimization problem in order to achieve our optimality and generality objectives. The MILP model is solved using a general-purpose MILP solver tool. The results of using TULIP for mapping some ISCAS-85 benchmark circuits to a variety of logic blocks are presented. Circuits of a few hundred gates can be mapped directly in a few minutes. To map larger circuits to complex logic blocks, some approximation techniques are proposed based on partitioning the input circuit and simplifying the MLB basis. We show that these approximations result in close-to-optimal mappings of the benchmark circuits.

To address the problem of accurate timing characterization, this paper proposes a method that fully exploits mode dependency. It is based on the premise that circuit delays are determined largely by a set of control inputs for which the number of useful combinations, i.e., modes, is small for most practical circuits. We take the mode-dependent characterization approach further and enhance it so that the delays of the I/O paths between the control inputs and outputs are calculated more accurately. We prove that, with a careful choice of propagation conditions, our method can generate timing models with very tight path delays that are guaranteed to give correct results. Experimental results using real-life circuits show that cir-cuit delays can vary significantly among different modes for both control and data input delays, and capturing this variation can have a significant impact on the overall system timing.

Conventional automatic test-pattern generation (ATPG) cannot effectively handle designs employing blocks whose implementation details are either unknown, unavailable, or subject to change. Realization-independent block testing for cores (RIBTEC), a novel ATPG program for such designs, is described, which employs a functional (behavioral) fault model based on a class of nonexhaustive "universal" test sets. Given a circuit's high-level block structure, RIBTEC constructs a universal test set (UTS) for each block from its functional description in such a way that realization independence of the blocks is ensured. Experimental results are presented for representative datapath circuits, which demonstrate that RIBTEC achieves very high fault coverage and an exceptionally high level of realization independence. We also show that RIBTEC can be applied to designs containing a class of small intellectual property (IP) circuits (cores).

In deep submicrometer integrated circuit design, there is a growing need to quickly and accurately characterize the timing of large circuit blocks. Accurate timing characterization requires making available as much timing information as possible at each step of the design process. Conventional fast characterization methods typically employ topological analysis, which can be inaccurate because of its inability to eliminate false paths. To address this problem, a new method for creating accurate timing models of circuit blocks by making efficient use of their functionality is introduced. The proposed mode-dependent characterization (ModeChar) method is based on calculating a distinct timing model for each mode of circuit operation and reflects the way practical circuits function. ModeChar produces a mode-dependent timing model that contains delay information for a given set of circuit modes. It is shown that circuit delays are never underestimated by the mode-dependent models. The concept of mode dependency is taken further by extending it to sequential circuits. Given a sequential circuit, a compact set of constraints is derived for each circuit mode that captures all the timing constraints that must be satisfied for correct operation of the circuit. Experimental results are presented that demonstrate the effectiveness of ModeChar in eliminating many false paths that would otherwise result in performance penalties. In addition, our experiments indicate that delays can vary considerably among circuit modes, making conventional topological analysis overly pessimistic. To make the mode-dependent models more compact, an efficient algorithm far coalescing delay information is also introduced.

Predesigned blocks called intellectual property (IP) cores are increasingly used for complex system-on-a-chip (SoC) designs. The implementation details of IP cores are often unknown or unavailable, so delay testing of such designs is difficult. We propose a method that can test paths traversing both IP cores and user-defined blocks, an increasingly important but little-studied problem. It models representative paths in IP circuits using an efficient form of binary decision diagram (BDD) and generates test vectors from the BDD model. We also present a partitioning technique, which reduces the BDD size by orders of magnitude and makes the proposed method practical for large designs. Experimental results are presented that show that it robustly tests selected paths without using extra logic and, at the same time, protects the intellectual contents of IP cores.

ESIM is a simulation tool that integrates logic fault and design error simulation for logic circuits. It targets several design error and fault models, and uses a novel mix of simulation algorithms based on parallel-pattern evaluation, multiple error activation, single fault propagation, and critical path tracing. Several experiments are discussed to demonstrate the power of ESIM.

A novel technique, CLIP , is presented for the automatic generation of optimal layouts of CMOS cells in the two-dimensional (2D) style. CLIP is based on integer-linear programming ( ILP ) and solves both the width and height minimization problems for 2D cells. Width minimization is formulated in a precise form that combines all factors influencing the 2D cell width—transistor placement, diffusion sharing, and vertical interrow connections—in a common problem space; this space is then searched in a systematic manner by the branch-and-bound algorithms used by ILP solvers. For height minimization, cell height is modeled accurately in terms of the horizontal wire routing density, and a minimum-height layout is found from among all layouts of minimum width. For exact width minimization alone, CLIP 's run times are in seconds for large circuits with 30 or more transistors. For both height and width optimization, CLIP is practical for circuits with up to 20 transistors. To extend CLIP to larger circuits, hierarchical methods are necessary. Since CLIP is optimum under the modeling assumptions, its layouts are significantly better than those generated by other, heuristic, layout tools.

A design methodology for implementing fast, easily testable arithmetic-logic units (ALUs) is presented. Here, we describe a set of fast adder designs, which are testable with a test set that has either /spl theta/(N) complexity (Lin-testable) or /spl theta/(1) complexity (C-testable), where N is the input operand size of the ALU. The various levels of testability are achieved by exploiting some inherent properties of carry-lookahead addition. The Lintestable and C-testable ALU designs require only one extra input, regardless of the size of the ALU. The area overhead for a high-speed 64-bit Lintestable ALU is only 0.5%.

This paper addresses test generation for design verification of pipelined microprocessors. We describe a highlevel model for testing pipelined microprocessors, which exposes high-level knowledge that is useful for verification test generation. We present a three-part test generation algorithm that uses this knowledge: The core part of the algorithm conducts a branch-and-bound search in a transformed state space of the controller. The decision variables of the search represent the essential interaction between concurrent instructions in the pipeline. The size of this transformed search space can be significantly smaller than the original state space of the controller. The second part of the algorithm selects justification and propagation paths in the datapath, which guide the search in the control space. The third part uses discrete relaxation to determine appropriate data values. We have implemented the proposed algorithm and used it to generate verification tests for design errors in the datapath of a representative pipelined microprocessor. I.

Delay testing of designs that contain intellectual property (IF) cores is challenging. We propose a method that can test paths traversing both IP cores and user-defined blocks. It employs a highly efficient BDD-based path modeling method and an associated ATPG technique. Experimental results show that it robustly tests selected paths without using extra logic, and, at the same time, protects the intellectual property.

Static off-line scheduling ensures predictability of worst-case behavior and high resource utilization for safety-critical applications but lacks the flexibility needed to deal with run-time fault-tolerance. We present a temporal redundancy-based recovery technique that tolerates transient task failures in statically scheduled distributed embedded systems where tasks have timing, resource, and precedence constraints. Task failures are handled using precomputed contingency schedules that introduce adaptive fault tolerance into table-driven dispatchers. Failures are masked using the spare capacity on the affected processor and the recovery scheme requires no hardware overhead. Our approach combines the benefits of static scheduling with the run-time flexibility needed for fault tolerance in low-cost embedded systems. We present a method to obtain contingency schedules and prove its correctness. We also evaluate the effectiveness of the proposed method through simulation.

Conventional methods cannot effectively verify path delays of designs employing IP circuits (cores) whose implementation details are hidden. A delay fault ATPG method for such designs is proposed that employs a scan technique called selectively transparent scan (STS). Experimental results are presented which show that the STS method can robustly test paths of a specified delay range in core-based circuits, and substantially reduce test length.

Folding, a key requirement in high-performance cell layout, implies breaking a large transistor into smaller, equal-sized transistors (legs) that are connected in parallel and placed contiguously with diffusion sharing.We present a novel technique FCLZP that integrates folding into the generation of optimal layouts of CMOS cells in the twodimensional (2-D) style.FCLZP is based on integer linear programming (ILP) and precisely formulatm cell width minimization as a O-1 optimization problem.Folding is incorporated into the O-1 ILP model by variables that represent the degrees of freedom that folding introduces into cell layout.FCLZP yields optimal resul@ for three reasons: (1) it implicitly explores all possible transistor placements; (2) it considers all diffusion sharing possibilities among folded transistors; and (3) when paired P and N transistors have unequal numbers of legs, it considers all their relative positions.FCLZP is shown to be practical for relatively large circuits with up to 30 transistors.We then extend FCLZP to accommodate and-stack clustering, a requirement in most practical designs due to its benefiti on circuit performance.This reduces run times dramatically, making FCLZP viable for much larger circuits.It also demonstrates the versatility of FCLZP'S ILP-based approach in easily accommodating additional design constraints. INTRODUCTIONCell layout synthesis falls in the category of constrained optimization \vhose goal is to find a solution that optimizes some cost function under a set of constraints.The cost function can be the cell area, its delay, or a combination of these.The constraints include bounds on \vidth or height, aspect ratio, number of diffusion rolvs, or the maximum size of transistors.Since cell layout optimization is NP-hard [3], any exact algorithm can, in the }vorst case, have an Ped

Conventional ATPG cannot effectively handle designs employing IP circuits (cores) whose implementation details are either unknown, unavailable, or subject to change. A new ATPG program RIBTEC for such designs is described that employs a functional (behavioral) fault model based on a class of non-exhaustive "universal" test sets. Given a circuit's high-level block structure, RIBTEC constructs a universal test set for each block from its functional description in such a way that realization-independence of the blocks is ensured. Experimental results are presented for representative datapath circuits, which show that RIBTEC achieves very high fault coverage and an exceptionally high level of realization independence.

Many built-in self-testing (BIST) schemes compress the test responses from a k-output circuit to q signature streams, where q/spl Lt/k, a process termed space compaction. The effectiveness of such a compaction method can be measured by its compaction ratio c=k/q. A high compaction ratio can introduce aliasing, which occurs when a faulty test response maps to the fault-free signature. We investigate the problem of designing zero-aliasing space compaction circuits with maximum compaction ratio c/sub max/. We introduce a graph representation of test responses to study the space compaction process and relate space compactor design to a graph coloring problem. Given a circuit under test, a fault model, and a test set, we determine q/sub min/, which yields c/sub max/=k/q/sub min/. This provides a fundamental bound on the cost of signature-based BIST. We show that q/sub min//spl les/2 for all the ISCAS 85 benchmark circuits. We develop a systematic design procedure for the synthesis of space compaction circuits and apply it to a number of ISCAS 85 circuits. Finally, we describe multistep compaction, which allows zero aliasing to be achieved with any q, even when q/sub min/>1.

A design verification methodology for microprocessor hardware based on modeling design errors and generating simulation vectors for the modeled errors via physical fault testing techniques is presented. We have systematically collected design error data from a number of microprocessor design projects. The error data is used to derive error models suitable for design verification testing. A class of basic error models is identified and shown to yield tests that provide good coverage of common error types. To improve coverage for more complex errors, a new class of conditional error models is introduced. An experiment to evaluate the effectiveness of our methodology is presented. Single actual design errors are injected into a correct design, and it is determined if the methodology will generate a test that detects the actual errors. The experiment has been conducted for two microprocessor designs and the results indicate that very high coverage of actual design errors can be obtained with test sets that are complete for a small number of synthetic error models.

We present a parity-based space compaction technique that eliminates aliasing for any given fault model. The test responses from a circuit under test with a large number of primary outputs are merged into a narrow signature stream using a multiple-output parity tree. The functions realized by the different outputs of the compactor are determined by a procedure that targets the desired fault model. Experimental results for the ISCAS-85 benchmarks show that zero aliasing of single stuck-line faults can be achieved with a two output parity tree compactor. Our findings corroborate recent results on the fundamental limits of space compaction.

We present a novel technique CLIP for optimizing both theheight and width of CMOS cell layouts in the two-dimensional (2-D) style. CLIP is based on integer-linear programming (ILP) and proceeds in two stages: First, an ILP model is used to determine a 2-D layout of minimum width W cell . Then, another model generatesa 2-D layout that has width W cell and requires a minimumnumber of routing tracks. Run times are in seconds for circuitswith up to 16 transistors. For larger circuits, we extend CLIP to ahierarchical method HCLIP that places series-connected transistorscontiguously. This reduces run times by up to three orders ofmagnitude, and still yields optimal results in over 80% of cases.

We present a general approach to the FPGA technology mapping problem that applies to any logic block composed of lookup tables (LUTs) and can yield optimal solutions. The connections between LUTs of a logic block are modeled by virtual switches, which define a set of multiple-LUT blocks (MLBs) called an MLB-basis. We identify the MLB-bases for various commercial logic blocks. Given a n MLB-basis, we formulate FPGA mapping as a mixed integer linear programming (MILP) problem to achieve both the generality and the optimality objectives. We solve the MILP models using a general-purpose MILP solver, and present the results of mapping some ISCAS.85 benchmark circuits with a variety of commercial FPGAs. Circuits of a few hundred gates can be mapped in reasonable time using the MILP approach directly. Larger circuits can be handled by partitioning them prior to technology mapping. We show that optimal or provably near-optimal solutions can be obtained for the large ISCAS.85 benchmark circuits using partitions defined by their high-level functions.

Recent work in IC failure analysis strongly indicates the need for fault models that directly analyze the function of circuit primitives. The input pattern (IP) fault model is a functional fault model that allows for both complete and partial functional verification of every circuit module, independent of the design level. We describe the IP fault model and provide a method for analyzing IP faults using standard SSL-based fault simulators and test generation tools. The method is used to generate test sets that target the IP faults of the ISCAS85 benchmark circuits and a carry-lookahead adder. Improved IP fault coverage for the benchmarks and the adder is obtained by adding a small number of test patterns to tests that target only SSL faults. We also conducted fault simulation experiments that show IP test patterns are effective in detecting non-targeted faults such as bridging and transistor stuck-on faults. Finally, we discuss the notion of IP redundancy and show how large amounts of this redundancy exist in the benchmarks and in SSL-irredundant adder circuits.

A multiprocessor system is fault-tolerant (FT) if it preserves a fault-free subsystem of a predetermined interconnection structure when faults appear. We present a new method for designing FT multiprocessors that can efficiently tolerate both processor and interconnection faults. The approach is general, in that it can be applied to any multiprocessor topology. Shared buses serve as the main interconnection mechanism to minimize the switching logic needed for reconfiguration. We employ processor-bus-link (PBL) graphs to model multiprocessors with either dedicated or shared buses. Both processors and buses are represented as nodes so that bus faults can be considered explicitly and tolerated efficiently by spare buses instead of by spare processors. A minimum number of spare processors and buses are used to reduce hardware overhead. The node covering concept and the maximum-weight spanning tree algorithm are then employed to construct FT systems that have lower interconnection cost than most previous designs. We also present a cost-effective implementation method which is suitable for both static and dynamic reconfiguration techniques. The FT systems obtained have the advantages of no critical single point of failure, low redundancy, local replacement, and simple circuitry for fast reconfiguration.

The accumulator-based compaction (ABC) technique uses an accumulator to generate a composite fault signature for a circuit under test. The error coverage for this method has been previously analyzed using Markov chains. We describe an alternative technique for calculating the error coverage of ABC using the asymmetric error model. This technique relies on the central limit theorem of statistics and can be applied to other count-based compaction schemes. Our analysis shows that ABC provides very high coverage of asymmetric errors. Experiments on the actual fault coverage for the ISCAS 85 benchmark circuits show that extremely high postcompaction fault coverage (close to 100%) is obtained with ABC. They also indicate that the use of a rotate-carry adder does not always improve the fault coverage; in some cases, the fault coverage is actually reduced.

Accurate and efficient computation of delays is a central problem in computer-aided design of complex VLSI circuits. Delays are determined by events (signal transitions) propagated from the inputs of a circuit to its outputs, so precise characterization of event propagation is required for accurate delay computation. Although many different propagation conditions (PCs) have been proposed for delay computation, their properties and relationships have been far from clear. We present a systematic analysis of delay computation based on a series of waveform models that capture signal behavior rigorously at different levels of details. The most general model, called the exact of W0 model, specifies each event occurring in a circuit signal. A novel method is presented that generates approximate waveforms by progressively eliminating signal values from the exact model. For each waveform model, we drive the PCs that correctly capture the requirements under which an event propagates along a path. The waveform models and their PCs are shown to form a well-defined hierarchy, which provides a means to trade accuracy for computational effort. The relationships among the derived PCs and existing ones are analyzed in depth. It is proven that though many PCs, such as the popular floating mode condition, produce a correct upper bound on the circuit delay, they can fail to recognize event propagation in some instances. This analysis further enables us to derive new and useful PCs. We describe such a PC, called safe static. Experimental results demonstrate that safe static provides an excellent accuracy/efficiency tradeoff.

We present an efficient approach to characterizing the fault tolerance of multiprocessor systems that employ multiple shared buses for interprocessor communication. Of concern is connective fault tolerance, which is defined as the ability to maintain communication between any two fault-free processors in the presence of faulty processors, buses, or processor-bus links. We introduce a model called processor-bus-link (PBL) graphs to represent a multiple-bus system's interconnection structure. The model is more general than previously proposed models, and has the advantages of simple representation, broad application, and the ability to model partial bus failures. The PBL graph implies a set of component adjacency graphs that highlights various connectivity features of the system. Using these graphs, we propose a method for analyzing the maximum number of faults a multiple-bus system can tolerate, and for identifying every minimum set of faulty components that disconnects the processors of the system. We also analyze the connective fault tolerance of several proposed multiple-bus systems to illustrate the application of our method.

We address the problem of CMOS cell width minimization in the general two-dimensional (2-D) layout style and propose a novel technique based on integer linear programming (ILP) to solve it exactly. We formulate a 0-1 ILP model whose solution minimizes cell width along with the routing complexity across the diffusion rows. We present experimental results that evaluate the performance of two ILP solvers that have very different solution methods, and assess the effect of the number of rows on cell width. Runtimes for optimal layouts are in seconds for cells with up to 20 transistors. For larger cells, we propose a practical circuit pre-processing scheme that dramatically reduces the run time with little or no loss in optimality.

We present a novel timing analysis method ACD that computes an approximate value for the delay of datapath circuits. Based on the conditional delay matrix (CDM) formalism we introduced earlier the ACD method exploits the fact that most datapath signals are directed by a small set of control inputs. The signal propagation conditions are restricted to a set of predefined central inputs, which results in significant reductions in the size of the conditions as well as computation time. We have implemented ACD and experimented with reverse-engineered high-level versions of the ISCAS-85 benchmarks. Our results demonstrate up to three orders of magnitude speedup in computation time over exact methods, with little or no loss in accuracy.

The design and implementation of a fast, easily testable arithmetic-logic unit (ALU) is described. It is built around an adder design which is level-testable (L-testable), implying that the number of test patterns required to detect all functional faults in modules grows logarithmically with the size of the ALU. L-testability is achieved by exploiting some inherent properties of carry-lookahead addition. The resulting ALU design requires only two extra inputs, regardless of the size of the ALU. For an 8-bit implementation that has little impact on performance, the area overhead is shown to be less than 9%.

A graph G* is a k-node fault-tolerant supergraph of a graph G, denoted k-NFT (G), if every graph obtained by removing k nodes from G* contains G. A k-NFT (G) graph G* is said to be optimal if it contains n + k nodes, where n is the number of nodes of G and G* has the minimum number of edges among all (n + k)-node k-NFT supergraphs of G. We survey prior results on the design of optimal k-NFT supergraphs of various useful forms of G; this work covers cycles and various types of trees. We also introduce the concept of exact node fault tolerance, which requires that every graph obtained by removing k nodes from G* be isomorphic to G, and explore its basic properties. We conclude with a discussion of some unsolved and partially solved problems. © 1996 John Wiley & Sons, Inc.

We study the structure of fault-tolerant multiprocessor systems that allow one or more communication links to fail. Spare links are employed to tolerate link failures; no redundant processing units are required. Such a multiprocessor is modeled by a graph G whose nodes and edges correspond to the processing units and the links, respectively. G is a k-edge fault-tolerant design of a basic graph H, denoted k-EFT(H), if every graph obtained by removing any k edges from G embeds H. If G contains the fewest edges among all k-EFT designs of H, then G is said to be optimally k-EFT with respect to H. We introduce the concept of critical edges and graphs and derive some of their properties that are generally useful in designing optimal EFT supergraphs. We investigate the theory of edge fault tolerance for tree-structured networks, in particular, nonhomogeneous trees and stars. For both cases, we obtain optimal k-EFT designs for all k. © 1996 John Wiley & Sons, Inc.

The testing properties of a class of regular circuits called convergent trees are investigated. Convergent trees include such practical circuits as comparators, multiplexers, and carry-lookahead adders. The conditions for the testability of these tree circuits are derived for a functional fault model. The notion of L-testability is introduced, where the number of tests for a p-level tree is directly proportional to p, rather than exponential in p. Convergent trees that are C-testable (testable with a fixed number of tests, regardless of the tree's size) are also characterized. Two design techniques are also introduced that modify arbitrary tree modules in order to achieve Land C-testability. Finally, we apply these techniques to the design of a large carry-lookahead adder.

Built-in self-testing requires test response streams from many observation points to be merged (space compaction) and compressed (time compaction) into a short signature. The compaction circuits should be transparent to error propagation in order to minimize aliasing, which occurs when a faulty response maps to the fault-free signature. We investigate the use of multiplexed parity trees (MPTs) for zero-aliasing space compaction. MPTs combine the error propagation properties of multiplexers and parity trees, and ensure zero aliasing via multistep compaction. We present two design techniques based on MPTs-output selection and fanout insertion-that eliminate aliasing for both deterministic and pseudorandom test sets. Our experiments with the ISCAS benchmark circuits show that zero aliasing can be achieved with small test sets and moderate hardware overhead. We also demonstrate that a very high percentage of single stuck-line faults in the compaction circuit are detected by the test patterns applied to the circuit under test.

We present a simulation-based method for combinational design verification that aims at complete coverage of specified design errors using conventional ATPG tools. The error models used in prior research are examined and reduced to four types: gate substitution errors (GSEs), gate count errors (GCEs), input count errors (ICEs), and wrong input errors (WIEs). Conditions are derived for a gate to be completely testable for GSEs. These conditions lend to small rest sets for GSEs. Near-minimal test sets are also derived for GCEs. We analyze redundancy in design errors and relate this to single stuck-line (SSL) redundancy. We show how to map all the foregoing error types into SSL faults, and describe an extensive set of experiments to evaluate the proposed method. Our experiments demonstrate that high coverage of the modeled design errors can be achieved with small test sets.

We show that the FPGA technology mapping problem can be efficiently implemented as a mixed integer linear programming (MILP) problem which generates truly optimal mappings. The MILP approach can handle a wide variety of FPGA logic block architectures. We present a compact MILP formulation for logic blocks based on lookup tables (LUTs) or multiplexes. We also show that the MILP formulation can be easily modified to optimize area delay, or a combination of both. We demonstrate that moderately large benchmark circuits can be mapped in a reasonable time using the MILP approach directly. For larger circuits, we propose a technique of partitioning a circuit prior to mapping, which drastically reduces the computation time with little or no loss in optimality.

We present a novel method to perform timing analysis of hierarchical circuits. It is based on the representation of circuit modules by conditional delay matrices (CDMs) which combine module delays with event propagation conditions. The CDM model is independent of module complexity and allows automatic identification of false paths. We exploit hierarchy information to perform efficient delay computation. The effectiveness of the method is demonstrated on a high-level model of the ISCAS-85 circuit c6288, which is difficult to analyze using traditional approaches. The method has been implemented in a symbolic timing analysis program called CAT. The application of CAT to carry-skip adders shows that hierarchical timing analysis is faster by an order of magnitude than gate-level analysis.

Many built-in self-testing (BIST) schemes compress the test responses from a k-output circuit to q signature streams, where q/spl Lt/k, a process termed space compaction. The effectiveness of a compaction method can be measured by its compaction ratio c=k/q. However, a high compaction ratio can introduce aliasing, which occurs when a faulty test response maps to the fault-free signature. We investigate the problem of designing zero-aliasing space compaction circuits with maximum compaction ratio c/sub max/. We introduce a graph representation of test responses to study the space compaction process and relate space compactor design to a graph coloring problem. For a given circuit tender test, a given fault model, and a given test set, we determine q/sub min/, which yields c/sub max/=k/q/sub min/. This provides a fundamental bound on the cost of signature based BIST. We develop a systematic design procedure for the synthesis of space compaction circuits and apply it to a number of ISCAS-85 benchmark circuits.

A high-level test generation algorithm SWIFT is proposed which incorporates a symbolic scheduling procedure, derived from high-level synthesis applications, to resolve decision conflicts during test generation. SWIFT uses the induced fault model to generate functional tests that guarantee detection of low-level structural faults. When applied to functional models of representative 74 X-series, ISCAS-85 and ISCAS-89 circuits. SWIFT produces test sequences that cover all gate-level stuck-at-faults. Surprisingly, although they are derived from a high-level functional description of the circuit under test, most of these test sequences are of provably minimal or near-minimal size.

A high-level fault modeling and testing philosophy is proposed which is aimed at ensuring full detection of low level, physical faults, as well as the industry-standard single stuck-line (SSL) faults. A set of independent functional faults and the corresponding functional tests are derived (induced) from the circuit under test; of particular interest are SSL-induced functional faults or SIFs. We present, for the first time, complete functional circuit models and tests for representative 74X-series and ISCAS-85 benchmark circuits, and apply the proposed methodology to them. These examples demonstrate that functional testing can, with far less effort than conventional method, produce test sets that provide complete coverage of SSL faults in practical circuits. Surprisingly, these test sets are also provably of minimal or near-minimal size.

We present a new test response compression method called cumulative balance testing (CBT) that extends both balance testing and accumulator compression testing. CBT uses an accumulated balance signature, and it guarantees very high error coverage (over 99%) for various error models. We demonstrate that the single stuck-line (SSL) fault coverage of CBT for many of the ISCAS 85 combinational benchmark circuits is 100%, and for all but one circuit, the fault coverage is over 99.5%. To make processor circuits self-testing, any existing accumulators and counters can be exploited to implement CBT. Its ease of implementation, provably high error coverage, and exceptionally high SSL fault coverage, even with reduced (nonexhaustive) test sets, make CBT suitable for the built-in self testing of processor circuits that require a guaranteed level of test confidence.>

We pr esent design for balance testability (DFBT), a systematic signature-based method for enhancing the testability of logic circuits.DFBT employs balance testing and guarantees 100% coverage of single stuckline faults, as well as many multiple stuck-line and bridging faults.The logic overhead of DFBT is modest|only one extr a I/O pin and a small number of extra gates|and the original cir cuit need not be altered.We illustr ate DFBT by applying it to representative logic circuits.

A system is structurally fault-tolerant (SFT) if it preserves a fault-free subsystem of a pre-determined interconnection structure when faults appear. We present a systematic approach to designing SFT VLSI-based systems that use shared buses as the main communication mechanism. To represent the target systems, we introduce a processor-bus-link (PBL) graph in which processing elements (PEs) and buses are both modeled as nodes. PE and bus faults correspond to the removal of nodes from the PBL graph. The node covering concept and the minimum-weight spanning arborescence algorithm are then applied to the design of SFT systems that can tolerate both PE and bus faults. The designs obtained have fewer spare communication ports than prior designs, no critical single point of failure, and simple circuitry for reconfiguration.>

A major obstacle to achieving high fault coverage in built-in self testing (BIST) methods that employ response compression is aliasing, which occurs when a faulty circuit's signature maps to the fault-free signature. Another problem with many compression methods is that they are inefficient for multiple-output circuits. We present data showing that in most cases, faults are sensitized to an odd number of outputs, even when reduced test sets are used. This suggests that odd-parity detection alone provides very high fault coverage. We then introduce several systematic design techniques that guarantee zero-aliasing compression for single stuck-line faults in multiple-output circuits. We present the results of applying this approach to the ISCAS combinational benchmark circuits using both reduced and pseudorandom test sets. Our experiments show that very high fault coverage (up to 100%) can be achieved with small test sets and low hardware overhead.

Aliasing, which is the mapping of a faulty circuit's signature onto the fault-free signature, is a major problem in signature analysis. The authors present a new design technique (ALFRED) for zero aliasing based on the concept of sequence detection. For a test sequence of length n, the length of the signature in ALFRED is Theta (log n). The authors reduce the circuit complexity by adopting a shift-register-like structure that minimizes the logical dependencies of all but one of the flip-flops. They relate the theory of balanced functions to ALFRED, and demonstrate the feasibility of the approach by using it to design a signature analyzer for a carry-lookahead adder.>

Abstract A graph or multigraph G* is k‐edge fault‐tolerant with respect to a graph G, denoted k‐EFT(G), if every graph obtained by removing any k edges from G* contains G. We observe that for k sufficiently large a k‐EFT(G) graph must be a multigraph, and we present some basic conditions that such multigraphs must meet. We then study the problem of constructing k‐EFT(G) graphs that are optimal in that they contain the minimum number of edges among all k‐EFT(G) graphs. Families of optimal k‐EFT(G) graphs, where G is the n‐node path or cycle, are presented for all k and n. We also give an optimal 1‐EFT design for the n‐dimensional hypercube. © 1993 by John Wiley & Sons, Inc.

Memory interference occurs when two or more concurrent data requests are addressed to the same main memory bank. In vector superconductors, this problem is serious due to the periodic interaction among vectors accesses, and can significantly reduce memory bandwidth and overall system performance. Two techniques can be used to reduce the effects of memory interference. First, vector data can be placed in the main memory such that, when accessed concurrently, the vectors do not interfere with one another. Second, buffers can be used at the memory banks to hold conflicting requests and to allow vector streams to continue to access other banks. Conditions for arbitrary numbers of vector streams to access an interleaved memory system without conflict are derived. It is shown that when three or more vector streams must be accessed concurrently, vector data placement to avoid conflicts becomes increasingly difficult, and that bank buffers can be effective under these conditions in increasing the effective memory bandwidth.>

Methods for modeling and implementing various practical aspects of fault-tolerant multiprocessor systems largely neglected in prior research are examined. The node-covering design approach is generalized to accommodate systems whose structure and failure mechanisms are represented by arbitrary graphs. Several new types of covering graphs are defined, which lead to various useful design tradeoffs. A new technique for incremental design is presented, using a class of switch implementations that reduce a system's interconnection costs. The reduction of other cost factors is also addressed, and methods are presented for VLSI layout area minimization, fast and distributed reconfiguration, efficient transfer of state information for software recovery, and the efficient use of local spares.>

A fault-tolerant communication scheme that facilitates near-optimal routing and broadcasting in hypercube computers subject to node failures is described. The concept of an unsafe node is introduced to identify fault-free nodes that may cause communication difficulties. It is shown that by only using 'feasible' paths that try to avoid unsafe nodes, routing and broadcasting can be substantially simplified. A computationally efficient routing algorithm that uses local information is presented. It can route a message via a path of length no greater than p+2, where p is the minimum distance from the source to the destination, provided that not all nonfaulty nodes in the hypercube are unsafe. Broadcasting can be achieved under the same fault conditions with only one more time unit than the fault-free case. The problems posed by deadlock in faulty hypercubes are discussed, and deadlock-free implementations of the proposed communication schemes are presented.>

The relationship between switch-level circuit models and the linear electric circuits from which they are abstracted is investigated. This is important in determining the accuracy and consistency of switch-level simulation programs. A precise definition of magnitude or strength classes is presented, which leads to exact bounds on the accuracy of resistance and voltage calculations with magnitude classes relative to the corresponding linear calculations. The results indicate that the potential of switch-level simulators to provide accurate results is far less than was previously thought.>

A formal methodology is presented for the layout of a single CMOS functional cell and an array of such cells, which addresses height minimization as well as the ustrrd width minimization.Exact layout algorithms are presented which are the fust to minimim width and height for all cells of practical size, and are computationatly feasible for these circuits.We present the results of a comprehensive set of experiments in which we generated layouts for all practicat-sized circuits.We compare our optimat layouts to published designs, most of which are based on nonoptirnat heuristics.We show that not onty do our optimat algorithms yield si~lcant area savings, they also incur little penatty in amputation time.

Test generation performance can be improved significantly over conventional techniques by combining precomputed module tests to form a test for a complete circuit. We introduce a theory of propagation for modules and circuits which can be used for hierarchical test generation and design for testability. The propagation characteristics of a module - whether it can be sensitized to propagate some or all possible fault effects on an input bus - are represented by structures called ambiguity sets. Algebraic operations are performed on ambiguity sets to determine the propagation characteristics of multi-module circuits. We show how this propagation theory is used in test generation and also to aid in designing circuits suitable for high-level test generation.

A precise characterization of the subcube allocation problem and a general methodology to solve it are presented. Subcube allocation and coalescing algorithms that have the goal of minimizing fragmentation are developed. The concept of a maximal set of subcubes (MSS), which is useful in making allocations that result in a tightly packed hypercube, is introduced. The problems of allocating subcubes and of forming an MSS are formulated as decision problems and shown to be NP-hard. It is proved analytically that the buddy strategy is optimal under restricted conditions, and it is shown using simulation that its performance is actually poor under more realistic conditions. A heuristic procedure for efficiently coalescing a released cube with the existing free cubes is suggested. This coalescing approach is coupled with a simple best-fit allocation scheme to form the basis of a class of MSS-based strategies that give a substantial performance (hit ratio) improvement over the buddy strategy. Simulation results comparing several different allocation and coalescing strategies, which show that the MSS-based schemes provide a marked performance improvement over previous techniques, are presented.>

The authors analyze and identify a basic deficiency of a class of random interleaving schemes (LINEAR), which use linear transformation techniques to achieve randomization. Since all bank addresses generated by these methods are random, constrained only by the bijective property, more conflicts tend to occur than in the more common MODULO method. Also LINEAR lacks the capability of MODULO to move several conflicting vector streams to a conflict-free steady state. To correct these deficiencies, a new class of random interleaving schemes called RANDOM-H that hash only the higher-order address bits is proposed. Unlike LINEAR, the RANDOM-H schemes randomize selectively, while retaining some of the advantages of MODULO. It is shown that RANDOM-H has a higher probability of accessing a vector without conflict than LINEAR. An an example of RANDOM-H, a method called MASH is presented that combines module interleaving with a multiplicative hashing function for randomization.>

A general approach to designing tree structured multiprocessors with optimal or near-optimal fault tolerance properties is developed. A multiprocessor architecture with a static interconnection network is represented by a graph whose nodes are processors and whose edges are interprocessor communication links. The design of k-fault-tolerant (FT) trees for arbitrary k is considered, with the primary goal of minimizing the number of spare nodes and edges. Also presented are strategies for reconfiguring a k-FT supergraph of a tree T around faults to obtain a fault-free tree isomorphic to T. A systematic methodology is presented for designing k-FT nonhomogeneous symmetry d-ary trees based on a concept termed node covering. The designs are shown to be optimal when k>

Recent work has shown that test generation complexity and test set size can be reduced by high-level analysis that exploits the natural design hierarchy found in digital circuits. A design modification approach aimed at facilitating high-level testing by enhancing circuit regularity is proposed. This approach can improve the testability of a broad class of useful array- and tree-like circuits, including counters, decoders, and arithmetic logic units (ALUs). This is demonstrated for the specific case of decoders and decoding trees, where the test set size is reduced from O(2/sup n/) to O(n). A systematic design technique called level separation (LS) is presented for generalized tree circuits, which are useful for fast implementation of arithmetic functions like addition and multiplication. Design for testability (DFT) and hierarchical test generation are shown to reduce the test size from O(n) to O(log/sub 2/ n) for such circuits. A case study of a 16-b four-function ALU is presented to illustrate the utility of the LS method.>

A general theory for designing minimum-area layouts of static series-parallel CMOS functional cells (also called complex gates) in a standard cell layout style is presented. T. Uehara and W.M. vanCleemput. (1981) originally formulated this as the graph optimization problem of finding the minimum number of dual trails that cover a multigraph model of M of a cell. The present theory provides a formalism for the analysis of series-parallel graphs and identifies the mathematical structures that underlie the layout problem. It also leads to two efficient algorithms for designing minimum area functional cell layouts. The first algorithm, TrailTrace, accepts an ordering of M that is fixed, typically for performance reasons, and produces the minimum area layout for that ordering. Its time complexity is linear in the number of transistors in the cell. The second algorithm, R-TrailTrace, reorders M and produces the best layout area that can be achieved for any reordering that preserves the cell's functionality.>

A novel test generation technique for large circuits with high fault coverage requirements is described. The technique is particularly appropriate for circuits designed by silicon compilers. Circuit modules and signals are described at a high descriptive level. Test data for modules are described by predefined stimulus/response packages that are processed symbolically using techniques derived from artificial intelligence. The packages contain sequences of stimulus and response vectors which are propagated as units. Since many test vectors are processed simultaneously, a substantial increase in test generation speed can be achieved. A prototype test generator which uses the technique to generate tests for acyclic circuits has been implemented. Preliminary results from this program suggest that for circuits composed of datapath elements, speed improvements of three orders of magnitude over conventional techniques may be possible.>

The relationship between switch-level circuit models and the linear electric circuits from which they are abstracted were investigated. This is important in determining the accuracy and consistency of switch-level simulation programs. A precise new definition of magnitude or strength classes is presented, which leads to exact bounds on the accuracy of resistance and voltage calculations with magnitude classes relative to the corresponding linear calculations. The applicability to switch-level networks of standard solution methods for linear networks, including Gaussian elimination and Jacobi iteration, is also examined. The results indicate that the potential of switch-level simulators to provide accurate results is far less than previously thought.>

The architecture and applications of the class of highly parallel distributed-memory multiprocessors based on the hypercube interconnection structure are surveyed. The history of hypercube computers from their conceptual origins in the 1960s to the recent introduction of commercial machines is briefly reviewed. The properties of hypercube graphs relevant to their use in supercomputers, including connectivity, routing, and embedding, are examined. The hardware and software characteristics of current hypercubes are discussed, with emphasis on the unique aspects of their operating systems and programming languages. A sample C program is presented to illustrate the single-code, multiple-data programming style typical of distributed-memory machines in general, and hypercube applications in particular. Two contrasting hypercube applications are presented and analyzed: image processing and branch-and-bound optimization. Current trends are discussed.>

The performance of three commercial vector computers, the Cray X-MP/48, IBM 3090/400, and Alliant FX/8, for simulating logic circuits at gate level is compared. Experiments that assume zero- and unit-delay models demonstrate that certain key architectural features, especially, the presence of a scalar cache, have an adverse impact on the potential speedup. Consequently, the achievable speedup due to vectorization of simulation code, while still substantial, is less than expected. The results indicate that concurrent operation of multiple CPUs in vector mode in machines such as the Alliant FX/8 might be the most cost-effective speedup technique for logic simulation on current vector processors.>

A novel test-generation technique for large circuits with high fault-coverage requirements is described. Circuit modules and signals are represented at a high descriptive level. Test data for modules are represented by predefined stimulus/response packages which are processed symbolically using techniques derived from artificial intelligence. Since many test vectors are processed simultaneously, a substantial increase in test generation speed can be achieved. Preliminary results from a programmed implementation of the proposed test-generation technique are presented.>

A figure of merit called normalized-area, is introduced for the purpose of evaluating layouts for VLSI networks. This measure is distinctly different from the existing VLSI measures in two major aspects: (1) it expresses the utilization of the layout area by revealing the constant factor hidden in its asymptotic area-complexity; and (2) it distinguishes between node and wire sizes. Normalized-area is valuable in evaluating alternative layouts for a given structure as well as in analyzing the area utilization of a particular layout for that structure in an absolute sense. An analysis of the normalized-area of the layout schemes for regular structures proposed in the literature shows that most of these schemes are infeasible in practice. Array realizations for several well-known regular structures are used to demonstrate the usefulness of the normalized-area measure. Some practical guidelines for placement and routing to achieve good area utilization in a VLSI chip are presented.>

A novel circuit design methodology is developed for comprehensive offline self-testing of nearly regular VLSI circuits. It is based on four major design techniques: circuit partitioning, regularization to produce identical subcircuits (modules), parallel testing of modules, and fault detection by direct comparison of response streams from the modules. A generalization of I-testing called sequential I-testing (SI-testing) is described, which allows identical response streams to be produced at different times and be subsequently synchronized for comparison purposes. The concepts of k-regular and nearly k-regular circuits are introduced, which generalize regular circuits (iterative logic arrays) to array-like circuits that contain several cell-types and are moderately irregular. A heuristic circuit partitioning and regularization method for nearly-regular circuits is described.>

An optimal non-exhaustive method of minimizing the layout area of complementary series-parallel CMOS functional cells in the standard-cell style is presented. This generalizes earlier work of Uehara and van Cleemput which is heuristic and nonoptimal. A complete graph-theoretical framework for CMOS cell layout is developed and illustrated. The approach demonstrates a new class of graph-based algebras which characterize this layout problem.

The multiple-valued logics obtained by introducing uncertainty and energy considerations into classical switching theory are studied in this paper. First, the nature of uncertain or unknown signals is examined, and two general uncertainty types called U-values and P-values are identified. It is shown that multiple-valued logics composed of U/P-values can be systematically derived from 2-valued Boolean algebra. These are useful for timing and hazard analysis, and provide a rigorous framework for designing gate-level logic simulation programs. Next, signals of the form (v, s) are considered where v and s denote logic level and strength, respectively, and the product vs corresponds to energy flow or power. It is shown that these signals form a type of lattice called a pseudo-Boolean algebra. Such algebras characterize the behavior of digital circuits at a level (the switch level) intermediate between the conventional analog and logical levels. They provide the mathematical basis for an efficient new class of switch-level simulation programs used in MOS VLSI design.

A new class of switch-level logic circuits intended for modeling digital MOS VLSI circuits is presented. These circuits, which are called pseudo-Boolean, are composed of a single (voltage) source, connectors, switches, attenuators, and wells. The latter two devices are digital versions of resistors and capacitors, respectively, and may assume an arbitrary but finite number of different sizes. Signals are bidirectional, and are assigned a finite set of values of the form (v, s) where v corresponds to voltage level and s corresponds to electrical current or charge level (logical strength). It is shown that these signal values and the associated logical operations form a generalization of Boolean algebra called pseudo-Boolean or Heyting algebra. The analysis of pseudo- Boolean circuits using discrete counterparts of Kirchoff's current law and the superposition principle is discussed, as well as the application of pseudo-Boolean techniques to digital simulation.

A new methodology for the layout design of several classes of useful VLSI structures is proposed. The approach produces a structured layout for commonly found computation structures, using regular elements called layout slices. Algorithms for optimal array realization are described that offer several significant advantages over existing layout schemes. Any network that can be decomposed into instances of these structures can therefore be realized using layout slices. Algorithms for the array realization of a class of arbitrary networks are also described. Several well-known structures such as trees, carry-save adders and cube-connected cycles can be realized using the proposed array layout methodology, not only with optimal area but also with several features necessary for practical implementation, e.g., access to key nodes, high area utilization and global signal routing. The proposed methodology is illustrated with actual layouts of useful circuits.

A methodology for characterizing dynamic distributed recovery in fault-tolerant multiprocessor systems is developed using graph theory. Distributed recovery, which is intended for systems with no central supervisor, depends on the cooperation of a set of processors to execute the recovery function, since each processor is assumed to have only a limited amount of information about the system as a whole. Facility graphs, whose nodes denote the system components (processors), and whose edges denote interconnection between components, are used to represent multiprocessor systems, and error conditions. A general distributed recovery strategy R, which allows global recovery to be achieved via a sequence of local actions, is given. R recovers the system in several steps in which different nodes successively act as the local supervisor. R is specialized for two important classes of systems: loop networks and tree networks. For each of these cases, fault-tolerant designs and their associated distributed recovery strategies, which allow recovery from up to k faults within a specified number of steps, are presented.

Multiple-valued logics have long been used, often in intuitive fashion, for simulating transients, errors, unknown states, variable-strength signals, etc., in binary digital circuits. This paper presents a rigorous algebraic method for analyzing such logics, and for systematically constructing new ones. Starting with a basis such as 2-valued Boolean algebra, new algebras suitable for a broad range of practical simulation tasks are obtained systematically via a small set of expansion operations. This approach is applied in detail to the construction of families of simulation algebras for gate-level logic circuits; switch-level simulation is also considered. It is concluded that current simulation programs frequently lack essential logic values, and occasionally have superfluous ones. Some major discrepancies in the number of distinct logic values claimed by commercial simulators are also explained.

A β-network is an interconnection network composed of 2 ×2 crossbar switches called β-elements. This paper presents an analysis of the fault-tolerance of β-networks. A fault model is specified which allows β-elements to be stuck in either of their two normal states. A new connectivity property called dynamic full access (DFA) is introduced which serves as the criterion for fault tolerance. A fault is called critical if it destroys the DFA property; otherwise, it is noncritical. A minimal critical fault (MCF) is a critical fault none of whose proper subsets constitutes a critical fault. Two graph-theoretical characterizations of the minimal critical faults and the noncritical faults of a β-network are presented. Some applications of the theory developed here are discussed.

A new fault modeling technique aimed at efficient simulation and test generation for complex digital MOS IC's is described. It is based on connector-switch-attenuator (CSA) analysis, which employs purely digital models of switching transistors, resistive/capacitive elements, and their associated signals. The use of CSA networks to model the digital behavior, both static and dynamic, of MOS circuits is reviewed. It is shown that most physical failure modes in such circuits, including short-circuit, open-circuit, and delay faults, can be modeled more efficiently by CSA models than by conventional approaches. A generalized single stuck-line (GSSL) fault model is suggested as a uniform and practical method for fault representation.

Bit-sliced microprocessors are representative of an important class of LSI components that can be interconnected in a regular way to construct many useful types of digital systems. This paper develops an analytic test generation methodology for bit-sliced systems. A formal model C for a 1-bit bit-sliced microprocessor is defined which has the main features of many commercially available microprocessors. Using a functional fault model instead of the usual stuck-line fault model, a technique is presented for deriving a complete and near-minimal sequence of tests for C. The basic cell C is extended to form two more general cells Ck and Ck. n. Ck is a k-bit version of C, while Ck, n is Ck with an n × k-bit scratchpad RAM. The internal structure of C4,16 closely resembles that of the AMD 2901 processor slice. Test sequences for these cells are derived in much the same way as for C. It is shown that the test sequence for a single cell (C, Ck, or Ck, n) can easily be extended to a test sequence for an array of N identical cells with no increase in the number of tests required. It is observed that for test generation purposes, bit-sliced microprocessors can be viewed as C-testable iterative logic arrays, which require a constant number of test patterns independent of array size. Some new results on test generation for C-testable systems are presented, as well as a method for modifying iterative logic arrays to make them C-testable.

Bit-sliced systems are formed by interconnecting identical slices or cells to form a one-dimensional iterative logic array (ILA). This paper presents several design techniques for constructing easily testable bit-sliced systems. Properties of ILA's that simplify their testing are examined. C-testable ILA's, which require a constant number of test patterns independent of the array size, are characterized, and a method for making an arbitrary ILA C-testable is presented. A new testability concept for arrays called I-testability is introduced. I-testability ensures that identical test responses can be obtained from every cell in an ILA, and thus simplifies response verification. I-testable ILA's are characterized, as well as CI-testable arrays, which are simultaneously C- and I-testable. A method of making an arbitrary ILA CI-testable is presented. The application of C- and I-testing to the design of bit-sliced (micro-) computers is investigated. For this purpose a family of easily testable processor slices is described. The design of a self-testing CPU based on I-testing is discussed, and compared with a more conventional self-testing design.

Several proposals have been made for using a class of connecting networks called β-networks in multicomputer systems, such as systems containing large numbers of microprocessors. A β-network is a network of 2 × 2 crossbar switches called β-elements. This paper presents an analysis of the fault tolerance of β-networks intended for multicomputer applications. A fault model is used which allows β-elements to be stuck in either of their two normal states. A new connectivity property called dynamic full access (DFA) is introduced which serves as the criterion for fault tolerance. A β-network is said to have the DFA property if each of its inputs can be connected to any of its outputs in a finite number of passes through the network. A fault is called critical if it destroys the DFA property. Two graph-theoretical characterizations of the critical faults of a β-network are presented. It is shown that there is a one-to-one correspondence between minimal critical faults and the cutsets of the circuit adjacency graphs derived from the β-network. It is further shown that a fault is critical if and only if it is incompatible with all Eulerian circuits associated with the β-network. Some applications of the theory are discussed.

The design of combinational logic networks is considered in which equivalent or indistinguishable stuck-type faults are confined to a small region of the network. A general type of fault equivalence called S-equivalence is introduced, which defines fault equivalence with respect to an arbitrary set of modules S. A network N is called totally fault locatable with respect to module set S, denoted TFLS, if all specified faults in N are S-equivalent. Some general structural properties of TFLS networks are derived. The problem of designing TFLS networks is investigated for S = {AND, OR, NAND, NOR, NOT} denoted AON, and S = {AON, EXCLUSIVE- OR} denoted AONE. All equivalent fault classes in TFLAON and TFLAONE networks can be identified by inspection. It is shown that every function has a TFLAONE network, that is, a realization where all equivalence classes can be identified by inspection, containing at most one control point or extra input. A method for constructing a TFLAONE realization of an arbitrary function is presented using at most one control point.

The properties of combinational logic functions and networks that influence equivalence among stuck-type faults are investigated. It is shown that the equivalence of certain types of faults depends only on the function being realized. For instance, the fault classes among primary input/output faults are of this type. It is shown that every irredundant realization of the two-variable EXCLUSIVE-OR function has a unique set of ten fault classes. A fault class F in a module M contained in a network N is called intrinsic, if F can be determined from M alone, i. e., F is independent of N. Using the concepts of intrinsic equivalence and inversion parity, conditions for the equivalence and nonequivalence of two fault classes are obtained. These results are applied to the problem of equivalence identification in two-level logic networks where they provide a substantial reduction in the amount of computation required.

The design of minimum-length test sequences for pattern sensitivity in random-access memory (RAM) arrays is examined. The single pattern-sensitive fault (SPSF) model is used in which operations addressed to at most one memory cell are allowed to be faulty at any time. The influence of an SPSF affecting cell Ci is restricted to a fixed set of cells called the neighborhood of Ci. A new method is presented for efficiently generating the sequence of writes required in an SPSF test. This method yields optimal sequences for a useful class of neighborhoods called tiling neighborhoods. It is observed that RAM neighborhoods can be interpreted as polyominoes. A general procedure is given for constructing an SPSF test containing the minimum number of writes but a nonminimum number of reads. The difficult problem of minimizing the number of reads in an SPSF test is investigated for the 2-cell memory M2. A test of length 36 for M2 is derived which is optimal under certain reasonable restrictions. It is demonstrated that minimum-length SPSF tests can be inherently asymmetric.

The problem of generating minimum-length transition count (TC) tests is examined for combinational logic circuits whose behavior can be defined by an n-row fault table. Methods are presented for generating TC tests of length n+2 and 2n-1 for fault detection and fault location, respectively. It is shown that these tests are optimal with respect to the class of n-row fault tables in the sense that there exist n-row fault tables that cannot be covered by shorter TC tests. The practical significance of these tests is discussed.

The problem of measuring the structural complexity of logic networks is examined. A complexity measure π(N) is proposed which is the total number of input-output paths in an acyclic network N. π(N) is easily computed by representing network structure in matrix form. It is shown that simple upper bounds on the number of tests required by a combinational network N can be derived from π(N). These bounds are fairly tight when N contains little or no fan-out. The path complexity of combinational functions is defined and briefly discussed.

Two techniques are discussed for partitioning logic circuits to maximize the resolution of stuck-line faults. One technique exploits the inherent fault resolution of the circuit by attempting to force equivalent faults into the same module. The other involves inserting control points to separate members of equivalent fault classes, a technique called fault class splitting. Some new methods for identifying equivalent faults are also presented.

A solution to the problem of counting the number of fanout-free Boolean functions of n variables is presented. The relevant properties of fanout-free functions and circuits are summarized. The AND and OR ranks of a fanout-free function are defined. Recursive formulas for determining the number of distinct functions of specified rank are derived. Based on these, expressions are obtained for @@@@ D ( n ), @@@@ ND ( n ), and @@@@( n ), which denote the number of degenerate, nondegenerate, and all n -variable fanout-free functions, respectively. Simple nonrecursive bounds on the various @@@@ functions are also computed and are used to determine some asymptotic properties of the @@@@ functions. It is shown that for large n almost all fanout-free functions are nondegenerate, and that almost all unate functions are not fanout-free. The relationship between the fanout-free function enumeration problem and other function enumeration problems in switching theory is discussed.

Logic circuits are usually tested by applying a sequence of input patterns S to the circuit under test and comparing the observed response sequence R bit by bit to the expected response Ro. The transition count (TC) of R, denoted c(R), is the number of times the signals forming R change value. In TC testing c(R) is recorded rather than R. A fault is detected if the observed TC c(R) differs from the correct TC c(Ro). This paper presents a formal analysis of TC testing. It is shown that the degree of detectability and distinguishability of faults obtainable by TC testing is less than that obtainable by conventional testing. t is argued that the TC tests should be constructed to maximize or minimize c(Ro). General methods are presented for constructing complete TC tests to detect both single and multiple stuck-line faults in combinational circuits. Optimal or near-optimal test sequences are derived for one-and two-level circuits. The use of TC testing for fault location is examined, and it is concluded that TC tests are relatively inefficient for this purpose.

An approach to fault-tolerant design is described in which a computing system S and an algorithm A to be executed by S are both defined by graphs whose nodes represent computing facilities. A is executable by S if A is isomorphic to a subgraph of S.A k-fault is the removal of k nodes (facilities) from S.S is a k-fault tolerant (k-FT) realization of A if A can be executed by S with any k-fault present in S. The problem of designing optimal k-FT systems is considered where A is equated to a 0-FT system. Techniques are described for designing optimal k-FT realizations of single-loop systems; these techniques are related to results in Hamiltonian graph theory. The design of optimal k-FT realizations of certain types of tree systems is also examined. The advantages and disadvantages of the graph model are discussed.

The constraints imposed by various types of irredundancy on the structure of combinational logic networks are investigated. It is shown that the usual notion of irredundancy, here called a-irredundancy, places bounds on the maximum number of inputs to certain types of network structures. A network is called b-redundant if it contains a cascade of single-input gates that can be reduced to either an inverter or a single line. Let Nab(Z) denote all realizations of Z that are both a- and b-irredundant. If N ∈ Nab(Z), then the number of gates in any fan-out-free subnetwork of N is bounded. It is shown that a solution to some important design optimization problems can be found in Nab(Z). It is conjectured that Nāb(Z) is finite and some results supporting this conjecture are presented. For example, it is impossible to construct an arbitrarily long cascade of networks that perform the identity transformation without introducing a- or b-redundancy. A more general type of redundancy, c-redundancy, is defined which includes both a- and b-redundancy as special cases. The class of c-irredundant realizations of Z is finite.

The problem of determining the amount of fanout required to reahze a switching function m investigated.The significance of fanout in switching networks is discussed Fanout-free functions are introduced and their propertms examined.Two relations, adjacency and masking, are defined on the variables X of a functlonf(X), and these relations are used to characterize fanoutfree functions A quantity r(f) called the input fanout index of f is defined for arbitrary switching functions; r (f) represents the minimum number of input variables that require fanout in any reahzation of ff It is shown that r(f) can be determined from the pmme lmphcants and prime imphcates of f using two additmnal relations on X, the conjugate property and compatibility An algorithm is presented for finding a reahzatlon of f in whmh only T(f) variables fan out.Some other measures of fanout are briefly considered.

Some formal models for pattern-sensitive faults (PSF's) in random-access memories are presented. The problem of detecting unrestricted PSF's is that of constructing a checking sequence for the memory. An efficient procedure for constructing such a checking sequence is presented. A local PSF is defined as a PSF where the faulty behavior of a memory cell Cidepends on a fixed group of cells called the neighborhood of Ci. Neighborhoods are divided into two classes, open and closed. Test generation methods are described for local PSF's defined on both open and closed neighborhoods. The detection of PSF's when only one memory cell is faulty (single PSF's) is also discussed.

This paper considers the use of control logic to reduce the number of tests required by a logic network and to simplify test generation. The properties of EXCLUSIVE-OR (EOR) circuits as control elements are examined. Systematic procedures are presented for modifying any combinational or sequential network so that the resulting network requires only five tests. These tests can easily be generated using a set of predefined test patterns of length five. The design of diagnosable networks using a limited amount of control logic is also discussed.

The problem of selecting test points to reduce the number of tests for fault detection in combinational logic networks is examined. A method is presented for labeling the lines of a network. Procedures are described for obtaining a minimal labeling, i.e., one corresponding to a minimal set of tests, for fanout-free circuits and for a restricted class of circuits with fanout. Using these procedures, a branch-and-bound algorithm is developed for selecting an optimal (or near-optimal) set of q test points in fanout-free networks. Some difficulties associated with test point placement in general networks are pointed out. It is shown that the labeling approach is also applicable to the problem of selecting and placing control logic.

A network model colled the normal NAND model is introduced for the study of fault diagnosis in combinational logic circuits. It is shown that every network can be transformed into an equivalent normal NAND network from which all the information pertaining to the diagnosis of the original network con be obtained. The use of this model greatly simplifies fault analysis and test generation.

This paper considers the design of combinational logic circuits which require a minimal or near-minimal number of tests. Bounds on the number of tests required by various network structures are considered. It is shown that for an n-input fanout-free network, the number of single and multiple fault detection test lies between 2 √n and n + 1, while the number of fault locations tests lies between 2 √n and 2n.