Stochastic computing (SC) has emerged as an efficient low-power alternative for deploying neural networks (NNs) in resource-limited scenarios, such as the Internet of Things (IoT). By encoding values as serial bitstreams, SC significantly reduces energy dissipation compared to conventional floating-point (FP) designs; however, further improvement of layer-wise mixed-precision implementation for SC remains unexplored. This paper introduces Adjustable Sequence Length (ASL), a novel scheme that applies mixedprecision concepts specifically to SC NNs. By introducing an operator-norm – based theoretical model, this paper shows that truncation noise can cumulatively propagate through the layers by the estimated amplification factors. An extended sensitivity analysis is presented, using Random Forest (RF) regression to evaluate multi-layer truncation effects and validate the alignment of theoretical predictions with practical network behaviors. To accommodate different application scenarios, this paper proposes two truncation strategies (coarse-grained and fine-grained), which apply diverse sequence length configurations at each layer. Evaluations on a pipelined SC MLP synthesized at 32 nm demonstrate that ASL can reduce energy and latency overheads by up to over 60% with negligible accuracy loss. It confirms the feasibility of the ASL scheme for IoT applications and highlights the distinct advantages of mixed-precision truncation in SC designs.

Multipliers, particularly those with small bit widths, are essential for modern neural network (NN) applications. In addition, multiple-precision multipliers are in high demand for efficient NN accelerators; therefore, recursive multipliers used in low-precision fusion schemes are gaining increasing attention. In this work, we design exact recursive multipliers based on customized approximate full adders (AFAs) for low-power purposes. Initially, the partial products (PPs) encoded by 2×2 multiplications are analyzed, which reveals the correlations among adjacent PPs. Based on these correlations, we propose 4×4 recursive multiplier architectures where certain full adders (FAs) can be simplified without affecting the correctness of the multiplication. Manually and synthesis tool-based FA simplifications are performed separately. The obtained 4×4 multipliers are then used to construct 8×8 multipliers based on a low-power recursive architecture. Finally, the proposed signed and unsigned 4×4 and 8×8 multipliers are evaluated using a 28nm CMOS technology. Compared with DesignWare (DW) multipliers, the proposed signed and unsigned 4×4 multipliers achieve power reductions of 16.5% and 11.6%, respectively, without compromising area or delay; alternatively, the delay can be reduced by 20.9% and 39.4%, respectively, without compromising power or area. For signed and unsigned 8×8 multipliers, the maximum power reductions are 9.7% and 13.7%, respectively, albeit with a trade-off in area.

The utilization of Large Language Models (LLMs) requires dependable operation in the presence of errors in the hardware (caused by for example radiation) as this has become a pressing concern. At the same time, the scale and complexity of LLMs limit the overhead that can be added to detect errors. Therefore, there is a need for low-cost error detection schemes. Concurrent Error Detection (CED) uses the properties of a system to detect errors, so it is an appealing approach. In this paper, we present a new methodology and scheme for error detection in LLMs: Concurrent Linguistic Error Detection (CLED). Its main principle is that the output of LLMs should be valid and generate coherent text; therefore, when the text is not valid or differs significantly from the normal text, it is likely that there is an error. Hence, errors can potentially be detected by checking the linguistic features of the text generated by LLMs. This has the following main advantages: 1) low overhead as the checks are simple and 2) general applicability, so regardless of the LLM implementation details because the text correctness is not related to the LLM algorithms or implementations. The proposed CLED has been evaluated on two LLMs: T5 and OPUS-MT. The results show that with a 1% overhead, CLED can detect more than 87% of the errors, making it suitable to improve LLM dependability at low cost.

A basic operation in big data analysis is to find the cardinality estimate; to estimate the cardinality at high speed and with a low memory requirement, data sketches that provide approximate estimates, are usually used. The K Minimum Value (KMV) sketch is one of the most popular options; however, soft errors on memories in KMV may substantially degrade performance. This paper is the first to consider the impact of soft errors on the KMV sketch and to compare it with HyperLogLog (HLL), another widely used sketch for cardinality estimate. Initially, the operation of KMV in the presence of soft errors (so its dependability) in the memory is studied by a theoretical analysis and simulation by error injection. The evaluation results show that errors during the construction phase of KMV may cause large deviations in the estimate results. Subsequently, based on the algorithmic features of the KMV sketch, two protection schemes are proposed. The first scheme is based on using a single parity check (SPC) to detect errors and reduce their impact on the cardinality estimate; the second scheme is based on the incremental property of the memory list in KMV. The presented evaluation shows that both schemes can dramatically improve the performance of KMV, and the SPC scheme performs better even though it requires more memory footprint and overheads in the checking operation. Finally, it is shown that soft errors on the unprotected KMV produce larger worst-case errors than in HLL, but the average impact of errors is lower; also, the protected KMV using the proposed schemes are more dependable than HLL with existing protection techniques.

Reduced precision redundancy (RPR) has been widely used as an alternative to triple modular redundancy to enhance reliable computing with tolerance to errors and faults; however, it still has stringent requirements for power and area as well as complex decision hardware. Recent works have focused on reduced precision redundancy by approximation (RPA) to attain lower delay, smaller power dissipation, and smaller area because RPA operates using only logic operations (so no arithmetic unit is involved as decision hardware). The proposed RPA-based designs can tolerate up to two erroneous modules, so adding a further data word to the decision process compared to previous three-module based RPA designs found in the technical literature. The proposed designs consist of four modules, two exact data words and two approximate data words (denoted as 2E2A), where E (A) stands for exact (approximate) data words. The probability of generating an output exact data word by RPA under one and both data parts of erroneous modules is analytically found; simulation results are also provided. The difference between simulated and analytical probabilities is at most 7.3%. Figures of merits (such as delay, power dissipation, and area) of the proposed designs are assessed by simulation and compared with RPR and the three-module RPA. The proposed designs incur a similar delay as a three-module RPA; power dissipation and area (due to the additional module) can be adjusted by increasing the number of approximate bits while still retaining a two-module error tolerance. This article also presents its application to image processing, and arithmetic (i.e., the addition operation); the results show that the proposed schemes are very efficient.

Large language models (LLMs) have shown impressive performance in a wide range of tasks such as answering questions or summarizing text. However, running LLMs on edge devices is challenging as they require large amounts of energy due to their memory and computation needs. In LLMs most of the memory is needed to store the model parameters which number keeps increasing from one LLM generation to the next. In the last several years, significant efforts have been made to compress and prune parameters, but this is not enough to reduce their memory needs as the number of parameters grows exponentially. In this work, to reduce energy dissipation, rather than trying to reduce the amount of memory used by LLMs, we study the use of approximate memories to store the LLM parameters. Approximate memories can significantly reduce the energy dissipation at the cost of introducing errors in some of the memory bits. Therefore, the impact of errors on LLMs must be understood. To that end, we have performed error injection on different compressed versions of a classic LLM: Bidirectional Encoder Representations from Transformers (BERT). The results show that in some cases compressed BERTs operate reliably at high bit error rates. This makes possible the use of approximate memories with a negligible impact on the LLM performance and a significant reduction in energy dissipation.

The implementation of Machine Learning (ML) in Internet of Things (IoT) devices poses significant operational challenges due to limited energy and computation resources. In recent years, significant efforts have been made to implement simplified ML models that can achieve reasonable performance while reducing computation and energy, for example by pruning weights in neural networks, or using reduced precision for the parameters and arithmetic operations. However, this type of approach is limited by the performance of the ML implementation, i.e., by the loss for example in accuracy due to the model simplification. In this paper, we present Adaptive Resolution Inference (ARI), a novel approach that enables to evaluate new trade-offs between energy dissipation and model performance in ML implementations. The main principle of the proposed approach is to run inferences with reduced precision (quantization) and use the margin over the decision threshold to determine if either the result is reliable, or the inference must run with the full model. The rationale is that quantization only introduces small deviations in the inference scores, such that if the scores have a sufficient margin over the decision threshold, it is very unlikely that the full model would have a different result. Therefore, we can run the quantized model first, and only when the scores do not have a sufficient margin, the full model is run. This enables most inferences to run with the reduced precision model and only a small fraction requires the full model, so significantly reducing computation and energy while not affecting model performance. The proposed ARI approach is presented, analyzed in detail, and evaluated using different datasets both for floating-point and stochastic computing implementations. The results show that ARI can significantly reduce the energy for inference in different configurations with savings between 40% and 85%.

Approximate multipliers (AMs) have widely been investigated to pursue high-performance and energy-efficient hardware designs for error-tolerant applications, such as neural networks (NNs). The computing accuracy of an AM has been evaluated by using statistical error features; however, it is difficult to estimate the quality of a specific application using AMs. Thus, it is a great challenge to select or design appropriate AMs for an accuracy-constrained application. This paper proposes an application-oriented error evaluation framework for AMs with the aim of exploring the correlation between statistical error features of AMs and the accuracy degradation in AM-based NN applications. Specifically, based on the Dropout Feature Ranking technique, statistical error features of AMs are extensively studied and ranked by their importance to the accuracy of AM-based NN applications. The three most informative features are obtained to construct error models to predict the accuracy loss of AM-based NN applications. The constructed classification models show a probability higher than 96% for correctly classifying the AMs into three categories in accordance with the induced accuracy loss in AM-based NN applications. Furthermore, regression models can predict the accuracy of NN applications using an AM with a deviation as low as 6%. These results show that the proposed error evaluation framework can guide an efficient selection of AMs for NN applications by using just several AM error features, instead of running time-consuming and complicated hardware simulation. The obtained statistical error features can also provide a guidance for the design or generation of application-oriented AMs. Moreover, the proposed framework is applicable for quickly analyzing and selecting other approximate circuits for error-tolerant applications.

The security of probabilistic data structures is increasingly important due to their wide adoption in many computing systems and applications. In particular, the security of approximate membership check filters such as Bloom or cuckoo filters has been recently studied showing how an attacker can degrade the filter performance in some settings. In this paper, we consider for the first time the security of another popular approximate membership check filter, the Quotient Filter (QF). Our analysis and simulations show that quotient filters are vulnerable to both white and black box attackers that can cause insertion failures and degrade the filter performance very significantly. An interesting finding is that quotient filters are vulnerable to a new type of attack, not applicable to Bloom or cuckoo filters, that can degrade the speed of queries dramatically. The paper also briefly discusses and evaluates potential countermeasures to detect and protect against those attacks.

Sparse Convolutional Neural Network (CNN) training is well known to be time-consuming due to significant off-chip memory traffic. To effectively deploy sparse training, existing accelerators store matrices in a compressed format to eliminate memory accesses for zeros; hence, accelerators are designed to process compressed matrices to avoid zero computations. We have observed that the compression rate is greatly affected by the sparsity in the matrices with different formats. Given the varying levels of sparsity in activations, weights, errors, and gradients matrices throughout the sparse training process, it becomes impractical to achieve consistently high compression rates using a singular compression method for the entire duration of the training. Moreover, random zeros in the matrices result in irregular computation patterns, further increasing execution time. To address these issues, we propose a balanced sparse matrix convolution accelerator design for efficient CNN training. Specifically, a dual matrix compression technique is developed that seamlessly combines two widely used sparse matrix compression formats with a control algorithm for lower memory traffic during training. Based on this compression technique, a two-level workload balancing technique is then designed to further reduce the execution time and energy consumption. Finally, an accelerator is implemented to support the proposed techniques. The cycle-accurate simulation results show that the proposed accelerator reduces the execution time by 34% and the energy consumption by 24% on average compared to existing sparse training accelerators.

As probabilistic data structures are widely adopted in computing systems, their privacy is a major issue. Recent works have shown that even though the values stored in these structures look random, information can be extracted from them in some settings. In this paper, we consider the privacy of adaptive cuckoo filters, a probabilistic data structure that implements approximate membership checking. The main novelty and benefit of these filters are that they can adapt to removing false-positives. Unfortunately, our analysis shows that adaptation can dramatically reduce the privacy of the filters, allowing an attacker to extract the set of elements stored in the filter. Indeed, in some settings, the attacker can identify 100% of the elements stored in the filter. This means that the protection of the privacy of adaptive cuckoo filters should be considered. To that end, we propose preprocessing reduction (PR), a scheme that prevents an attacker from extracting the set of elements stored in the filter at the cost of increasing the false-positive probability of the filter. In many settings, the impact on false-positives will be negligible. For example, in a case study with 32-bit universes, the increase in the false-positive probability was smaller than 8% in all the configurations tested. Interestingly, PR is applicable not only to adaptive filters but also to approximate membership check filters in general and thus can be used to protect, for example, Bloom filters.

The complexity of machine learning (ML) systems increases each year. As these systems are widely utilized, ensuring their reliable operation is becoming a design requirement. Traditional error detection mechanisms introduce circuit or time redundancy that significantly impacts system performance. An alternative is the use of concurrent error detection (CED) schemes that operate in parallel with the system and exploit their properties to detect errors. CED is attractive for large ML systems because it can potentially reduce the cost of error detection. In this article, we introduce concurrent classifier error detection (CCED), a scheme to implement CED in ML systems using a concurrent ML classifier to detect errors. CCED identifies a set of check signals in the main ML system and feed them to the concurrent ML classifier that is trained to detect errors. The proposed CCED scheme has been implemented and evaluated on two widely used large-scale ML models: Contrastive language-image pretraining (CLIP) used for image classification and bidirectional encoder representations from transformers (BERT) used for natural language applications. The results show that more than 95% of the errors are detected when using a simple Random Forest classifier that is orders of magnitude simpler than CLIP or BERT.

This paper proposes new designs for Reduced Precision Redundancy (RPR) systems using Approximation (RPAs). Reduced redundancy is accomplished by utilizing approximate modules, hence requiring substantially different designs for the decision hardware for generating an output. The proposed schemes deal with a single erroneous data word generated by a module (in the presence of single and multiple bit errors) using three modules as inputs to the decision hardware of the RPA. Different from RPRs found in the technical literature, the proposed RPAs operate using only logic operations (so no involved as decision hardware). The probability of providing an exact data word at the output of the RPA under the above error conditions is analytically found; the provided simulation results show that the difference between simulated and analytical probabilities is at most 5%. Circuit based metrics (such as delay, power dissipation, and area) of the proposed designs are simulated and compared with RPR; the proposed designs outperform RPR in all metrics.

Feature-embedding triplet networks (TNs) with three symmetric subchannels are very promising for similarity-measuring applications. This paper proposes a novel separately constrained triple loss (SCTL) function that applies to TNs for classification. Through minimizing the intra-class distance and maximizing the inter-class distance, SCTL eliminates possible false solutions and provides insight into the dependency of training based on these two terms. Based on this dependency, the strategy of selecting hyperparameters in SCTL is also analyzed to further improve performance. The effectiveness of the proposed SCTL is evaluated based on TNs with multi-layer perceptrons; the results show that compared to all existing loss functions, the use of SCTL offers the best classification accuracy for the TNs, while incurring in negligible hardware overhead (e.g., only a 0.0002% area overhead of the subnetworks).

Approximate computing is considered an innovative paradigm with wide applications to high performance and low power systems. These applications have relaxed requirements for accuracy, so they can tolerate errors in results and achieve high performance. In approximate computing, multipliers have been widely studied, but squarers (as similar schemes) have not received much attention. In this paper, an accurate squarer is designed based on a Radix-8 Booth-folding square algorithm to reduce the number of partial products and the depth of the partial product array. Several approximate squarers (R8AS1, R8AS2 and R8AS3) are proposed based on the exact squarer to reduce power and delay. Two approximate partial product generators are also designed to simplify the Radix-8 Booth square encoder in R8AS1 and R8AS2. In addition, approximate compressors with compensation are used in the partial product compression stage to reduce additional area and power consumption in R8AS3. Synthesis results for power, area, and delay at 28 nm CMOS technology are presented. Compared with designs in the technical literature with the same accuracy, the proposed 16-bit designs reduce the PDP by 37%; in general, the PDP is decreased by up to 51%. Finally, the proposed approximate squarers are implemented in a square-law detector as a communication application and achieve an SNR close to 30 dB. Also, the three proposed approximate squarers are applied to the k-means clustering algorithm for machine learning to accomplish high performance in classification.

Approximate membership check filters are increasingly used to speed up data processing in many applications. Also, privacy is becoming a key design objective for many systems and thus, the privacy of filters needs to be carefully considered. Previous works have shown that an attacker that knows the implementation details of the filter and has access to its content, may be able to extract some information about the elements stored in the filter. This attack is, however, specific to Bloom filters and requires that the universe of elements must be small. In this article, we show that in many practical settings, an attacker that has only a black-box access to the filter, can extract information about the elements stored in the filter regardless of the specific filter type and the universe size. This is possible based on the key observation that in many applications, the elements stored in the filter are not randomly chosen, but they are concentrated in one or more parts of the universe of elements. To identify these parts, the positive probability can be measured on different parts of the universe; the parts having significantly larger values than the average positive probability for the filter are the ones on which the filter elements are concentrated. This approach is formalized and applied to several case studies showing the process by which the attacker can get additional information about the elements stored for the filters in a wide range of scenarios.

This article considers memory errors in a Siamese Network (SN) through an extensive analysis and proposes two schemes (using a weight filter and a code) to provide efficient hardware solutions for error tolerance. Initially the impact of memory errors on the weights of the SN (stored as floating-point (FP) numbers) is analyzed; this shows that the degradation is mostly caused by outliers in weights. Two schemes are subsequently proposed. An analysis is pursued to establish the filter's bounds selection by the maximum/minimum values of the weight distributions, by which outliers can be removed from the operation of the SN. A code scheme for protecting the sign and exponent bits of each weight in an FP number, is also proposed; this code incurs in no memory overhead by utilizing the 4 least significant bits (LSB) to store parity bits. Simulation shows that the filter has a better performance for multi-bit errors correction (a reduction of 95.288% in changed predictions), while the code achieves superior results in single-bit errors correction (a reduction of 99.775% in changed predictions). The combined method that uses the two proposed schemes, retains their advantages, so adaptive to all scenarios; The ASIC-based FP designs of the SN using serial and hybrid implementations are also presented; these pipelined designs utilize a novel multi-layer perceptron (MLP) (as branch networks of the SN) that operates at a frequency of 681.2 MHz (at a 32nm technology node), so significantly higher than existing designs found in the technical literature. The proposed error-tolerant approaches also show advantages in overheads comparing with for example traditional error correction code (ECC). These error-tolerant MLP-based designs are well suited to hardware/power-constrained platforms.

Data compression has been commonly employed to reduce the required memory size for emerging applications with large storage needs like Big Data and Machine Learning (ML). When considering the flexibility of decompression and its hardware implementation, variable-to-fixed length codes (e.g., Tunstall codes) are usually selected. However, memories are prone to suffer different types of errors, causing the stored data to be corrupted; if an error affects the compressed data, it can propagate and cause corruption in a sequence of bits of the decompressed data. Therefore, error resilience should be built-in as part of the memory design to provide reliable data, especially for safety-critical applications. However, Error Correction Codes (ECCs) that are widely used for memory protection, are not very efficient to protect compressed data, because ECCs further increase the memory size and the additional decoding process can impact the latency to decompress the stored data. In this paper, an efficient error-resilient data compression technique with Tunstall codes is proposed; it requires almost no memory overhead and can correct most errors during the decompression process by introducing a conversion table. An enhanced design is also presented to reduce the impact of errors when they cannot be corrected. The proposed scheme has been implemented and evaluated on three ML datasets; results show that it can deal with up to 99.98% errors with almost no memory overhead when Tunstall codes with smaller than 16-bit symbols are employed. The scheme has also been evaluated for two ML applications; results show that even though a small number of errors cannot be corrected in the proposed scheme, they have an extremely low impact on the classification results and the protection overhead is significantly lower than existing ECC techniques.

Counting Bloom Filters (CBFs) areapproximatemembership checking data structures, and it is normally believed that at most anapproximatereconstruction of the underlying set can be derived when interacting with a CBF. This paper decisively refutes this assumption. In a recent paper, we considered the privacy of CBFs when the attacker has access to the implementation details and thus, it sees the filter as a white-box. In that setting, we showed that the attacker may be able to extract the elements stored in the filter when the number of false positives over the entire universe is not significantly larger than the number of elements stored in the filter. In this work, we consider a black-box attacker that can only perform user interactions on the CBF to insert, remove and query elements with no knowledge of the filter implementation details. We show that even in this case, an attacker may be able to extract information from the filter at the cost of using more complex and time-consuming attack algorithms. The proposed algorithms have been implemented and compared with the white-box attack, showing that in most cases, almost the same information can be extracted from the filter.

Bloom filters are widely used in networking and computing to accelerate membership checking. In many applications filters store sensitive data, so their privacy is of primary concern. At first glance, it seems that extracting the set of elements inserted from the filter would not be possible, because in Bloom filters elements are mapped to positions using hash functions. However, previous works have shown that for the Bloom filter, it may be possible to identify few of the elements inserted in the filter. In this work, we consider the case of counting Bloom filters (CBFs) and show that in some cases, the entire set of elements used to create the filter can be extracted from the filter. This poses serious privacy and security concerns when an attacker can get access to the filter contents. In this article, an algorithm to extract the elements inserted from the filter is presented and analyzed theoretically; then, the feasibility of the CBF inversion is shown by simulation. A case study is presented in detail to illustrate that in practical applications, these conditions can be met by using additional restrictions that are implicit in the nature of the application itself.

Network-on-Chips (NoCs) are the standard on-chip communication fabrics for connecting cores, caches, and memory controllers in multi/many-core systems. With the increase in communication load introduced by emerging parallel computing applications, on-chip communication is becoming more costly than computation in terms of energy consumption. This paper contributes to existing research on approximate communication by proposing a slack-aware packet approximation technique to reduce the energy consumed by NoCs for sustainable parallel computation. The proposed approximation technique lowers both the execution time and NoC power consumption by reducing the packet size based on slack. The slack is the number of cycles by which a packet can be delayed in the network with no effect on execution time. Thus, low-slack packets are considered critical to system performance, and prioritizing these packets during the transmission will significantly reduce execution time. The proposed technique includes a slack-aware control policy to identify low-slack packets and accelerates these packets using two packet approximation mechanisms, namely, an in-network approximation (INAP) and a network interface approximation (NIAP). INAP mechanism prioritizes low-slack packets during the arbitration phase of the router by approximating packets with high-slack. NIAP mechanism reduces the latency of the network links and switch traversals by truncating data for the low-slack packets. An approximate network interface and router are implemented to support the proposed technique with lightweight packet approximation hardware for lower power consumption and execution time. Cycle-accurate simulations using the AxBench and PARSEC benchmark suites show that the proposed approximate communication technique achieves reductions of up to 24% in execution time and 38% in energy consumption with 1.1% less accuracy loss on average compared to existing approximate communication techniques.

Approximate computing has emerged as a new paradigm that provides power-efficient and high-performance arithmetic designs by relaxing the stringent requirement of accuracy. Nonlinear functions (such as softmax, rectified linear unit (ReLU), Tanh, and Sigmoid) are extensively used in deep neural networks (DNNs). However, they incur significant power dissipation due to the high circuit complexity. As DNNs are error-tolerant, the design of approximation-linear functions is possible and desired. In this article, the design of an approximate softmax function (AxSF) is proposed. AxSF is based on a double hybrid structure (DHS). AxSF divides the input of the softmax function into two parts for different processing methods. The most significant bits (MSBs) are processed with lookup tables (LUTs) and an exact restoring array divider (EXDr). Taylor’s expansion and a logarithmic divider are used for the less significant bits (LSBs). An improved DHS (IDHS) is also proposed to reduce the hardware complexity. In IDHS, a novel Booth multiplier is utilized for the hybrid scheme to improve the partial product generation and compression, while the truncated implementation is applied to the divider unit. The proposed DHS and IDHS are compared with existing softmax designs. The results show that the proposed approximate softmax design reduces hardware by 48% and delay by 54% while retaining a high accuracy.

Approximation is an emerging design methodology for reducing power consumption and latency of on-chip communication in many computing applications. However, existing approximation techniques either achieve modest improvements in these metrics or require retraining after approximation. Since classifying many images introduces intensive on-chip communication, reductions in both network latency and power consumption are highly desired. In this paper, we propose an approximate communication technique (ACT) to improve the efficiency of on-chip communications for image classification applications. The proposed technique exploits the error-tolerance of the image classification process to reduce power consumption and latency of on-chip communications, resulting in better overall performance for image classification. This is achieved by incorporating novel quality control and data approximation mechanisms that reduce the packet size. In particular, the proposed quality control mechanisms identify the error-resilient variables and automatically adjust the error thresholds of the variables based on the image classification accuracy. The proposed data approximation mechanisms significantly reduce packet size when the variables are transmitted. The proposed technique reduces the number of flits in each data packet as well as the on-chip communication while maintaining an excellent image classification accuracy. Cycle-accurate simulation results show that ACT achieves 27% in network latency reduction and 28% in dynamic power reduction as compared to existing approximate communication techniques with less than 0.85% classification accuracy loss.

Artificial Neural networks (ANNs) are widely used to solve classification problems for many machine learning applications. When errors occur in the computational units of an ANN implementation due to for example radiation effects, the result of an arithmetic operation can be changed, and therefore, the predicted classification class may be erroneously affected. This is not acceptable when ANNs are used in many safety-critical applications, because the incorrect classification may result in a system failure. Existing error-tolerant techniques usually rely on physically replicating parts of the ANN implementation or incurring in a significant computation overhead. Therefore, efficient protection schemes are needed for ANNs that are run on a processor and used in resource-limited platforms. A technique referred to as Selective Neuron Re-Computation (SNRC), is proposed in this paper. As per the ANN structure and algorithmic properties, SNRC can identify the cases in which the errors have no impact on the outcome; therefore, errors only need to be handled by re-computation when the classification result is detected as unreliable. Compared with existing temporal redundancy-based protection schemes, SNRC saves more than 60 percent of the re-computation (more than 90 percent in many cases) overhead to achieve complete error protection as assessed over a wide range of datasets. Different activation functions are also evaluated.

AS Dennard’s law is coming to an end, on-chip power consumption reduction and throughput improvement due to technology scaling pose serious challenges; workloads of today’s applications (such as AI, big data, and the IoT) have also reached extremely high levels of complex computation. Power dissipation has become the fundamental barrier to scale computing performance across all technology platforms. Computation at nanoscales requires innovative approaches.

The divider is one of the most complex hardware units in Stochastic Computing (SC); even though several new designs have been presented to reduce the computation latency of the conventional divider, all of them still require a considerable number of clock cycles. Moreover, they incur in low performance due to the employed arithmetic computational scheme. In this paper, a Delta Sigma Modulator (DSM) based stochastic divider is proposed. As an entirely digital circuit, the proposed divider offers the best computation latency and accuracy over all existing stochastic dividers found in the technical literature (with a typical reduction between 66.8% and 96.9% in the number of clock cycles and a reduction from$10^{\mathrm {-3.4}}$to$10^{\mathrm {-3.9}}$in the average mean square error for a 10-bit resolution). An SC-based Neural Network (NN) is considered as an initial case study to evaluate the advantages of the proposed design in an emerging application; results show that the proposed divider enables an SC-based NN to achieve a higher classification accuracy and hardware efficiency than existing designs. To show the flexibility of the proposed divider design, its application to Sobol-based sequences is also presented; also in this case, its superiority over other designs is confirmed. These features make the proposed design very attractive for hardware-constrained platforms; moreover, such a novel design approach that incorporates ideas from analog/mixed signal circuit design into a digital circuit design, can motivate other researchers to design efficient SC designs using similar schemes.

Estimating the number of distinct elements is required in many computing applications. One of the state-of-the-art algorithms for cardinality estimate is the HyperLogLog; it provides a good estimate over a large range of cardinality values using a small array of counters. As HLL is implemented in computing systems, it is exposed to soft errors that can corrupt bits stored in memories or registers. To avoid data corruption, memories are commonly protected with Error Correction Codes (ECCs). ECCs however incur in significant overhead because protection needs additional memory cells per word to store the parity check bits as well as additional computation for checking them. In this paper, we first study the impact of soft errors on the HLL algorithm by performing simulation by error injection. The results show that the algorithm is quite robust and can filter out most errors. However, for large cardinalities, there are some errors that can cause a large discrepancy in the HLL estimate. Based on the analysis of the experimental results and the HLL algorithm, a protection technique is proposed that effectively mitigates the impact of soft errors at a small overhead. The proposed Remove Minimum (RM) scheme has been validated by error injection experiments.

Data sketches are widely used to accelerate operations in big data analytics. For example, algorithms use sketches to compute the cardinality of a set, or the similarity between two sets. Sketches achieve significant reductions in computing time and storage requirements by providing probabilistic estimates rather than exact values. In many applications, an estimate is sufficient and thus, it is possible to trade accuracy for computational complexity; this enables the use of probabilistic sketches. However, the use of probabilistic data structures may create security issues because an attacker may manipulate the data in such a way that the sketches produce an incorrect estimate. For example, an attacker could potentially inflate the estimate of the number of distinct users to increase its revenues or popularity. Recent works have shown that an attacker can manipulate Hyperloglog, a sketch widely used for cardinality estimate, with no knowledge of its implementation details. This paper considers the security of K Minimum Values (KMV), a sketch that is also widely used to implement both cardinality and similarity estimates. Next sections characterize vulnerabilities at an implementation-independent level, with attacks formulated as part of a novel adversary model that manipulates the similarity estimate. Therefore, the paper pursues an analysis and simulation; the results suggest that as vulnerable to attacks, an increase or reduction of the estimate may occur. The execution of the attacks against the KMV implementation in the Apache DataSketches library validates these scenarios. Experiments show an excellent agreement between theory and experimental results.

Adaptation has recently been proposed to reduce the false positive rate of approximate membership check filters for applications in which the same elements are checked multiple times. Its operational principle is to adapt the filter when a false positive occurs for a given element, such that subsequent checks of that element do not cause a positive result (as beneficial for example in networking). Security is an important consideration for approximate membership check filters and several attacks have been described in the literature; therefore, it is of interest to study the security of adaptive filters. In this paper, we consider adaptive cuckoo filters and show that an attacker can generate sequences of lookups that cause the filter to continuously adapt and not being able to remove the false positives. This degrades the filter performance due to the adaptation overhead; it also makes it harder for other false positives to be removed, because adaptation can be monopolized by the attacker. This can be done when the attacker has only a black-box access to the filter being able to perform lookups but with no knowledge of the implementation of the filter. The proposed attacks have been implemented and tested to validate their effectiveness in terms of the construction of the attack set and the impact of the attack itself. The evaluation results confirm that adaptation unfortunately increases the attack surface of filters and new mechanisms to protect them should be developed.

Bloom filters are probabilistic data structures that are popular in networking for set representation; however, they show an inherent inaccuracy due to false positives. One of the potential attacks on Bloom filters is to pollute them with elements that cause the filter to have a larger false positive probability than under normal operation; Pollution is simple when an attacker knows the details of the filter implementation. Recent research has shown that also black-box adversaries can pollute a counting Bloom filter (a common variant of the filter that also supports removals) with no knowledge of its implementation. As over time, many variants and improvements of Bloom filters have been proposed, it is of interest to study whether they can also be polluted and if so also the increase in their false positive probability. This paper first proposes and then evaluates pollution attacks for some of the most common variants including the Block Bloom filters (BBFs), the Variable Increment and Fingerprint Counting Bloom filters (VI-CBFs and FP-CBFs). The results show that with or without knowledge of the implementation, these variants of the Bloom filter are significantly more vulnerable to pollution attacks than the traditional Bloom filter. In particular, BBFs are extremely vulnerable, so providing an insight on their impact and use in practical systems when the number of memory accesses per lookup must be reduced.

Due to the low complexity in arithmetic unit design, stochastic computing (SC) has attracted considerable interest to implement Artificial Neural Networks (ANNs) for resources-limited applications, because ANNs must usually perform a large number of arithmetic operations. To attain a high computation accuracy in an SC-based ANN, extended stochastic logic is utilized together with standard SC units and thus, a stochastic divider is required to perform the conversion between these logic representations. However, the conventional divider incurs in a large computation latency, so limits an SC implementation for ANNs used in applications needing high performance. Therefore, there is a need to design fast stochastic dividers for SC-based ANNs. Recent works (e.g., a binary searching and triple modular redundancy (BS-TMR) based stochastic divider) are targeting a reduction in computation latency, while keeping the same accuracy compared with the traditional design. However, this divider still requires$N$iterations to deal with$2^{N}$-bit stochastic sequences, and thus the latency increases in proportion to the sequence length. In this paper, a decimal searching and TMR (DS-TMR) based stochastic divider is initially proposed to further reduce the computation latency; it only requires two iterations to calculate the quotient, so regardless of the sequence length. Moreover, a trade-off design between accuracy and hardware is also presented. An SC-based Multi-Layer Perceptron (MLP) is then considered to show the effectiveness of the proposed dividers over current designs. Results show that when utilizing the proposed dividers, the MLP achieves the lowest computation latency while keeping the same classification accuracy; although incurring in an area increase, the overhead due to the proposed dividers is low over the entire MLP. When using as combined metric for both hardware design and computation complexity the product of the implementation area, latency, power and number of clock cycles, the proposed designs are also shown to be superior to the SC-based MLPs (at the same level of accuracy) employing other dividers found in the technical literature as well as the commonly used 32-bit floating point implementation.

Recurrent Neural Networks (RNNs) have been widely used in many sequential applications, such as machine translation, speech recognition and sentiment analysis. Long Term Short Term Memory (LSTM) and Gated Recurrent Unit (GRU) are widely used variants of RNN due to their effectiveness in overcoming gradient vanishing and exploding problems; however, compared to conventional RNN, their massive storage and computation requirements hinder their application. In addition, the recurrent structure of RNNs makes them prone to accumulate errors, resulting in a severe loss of accuracy. In this work, we propose a hybrid-iterative compression (HIC) algorithm for LSTM/GRU. By exploiting the error sensitivity of RNN, the gating units are divided into error-sensitive and error-insensitive groups, that are compressed using different algorithms. By using this approach, a 37.1×/32.3× compression ratio is achieved with negligible accuracy loss for LSTM/GRU. Further, an energy efficient accelerator for bidirectional RNNs is proposed. In this accelerator, the data flow of the matrix operation unit based on the block structure matrix (MOU-S) is improved through rearranging weights; the utilization of BRAM is improved through a fine-grained parallelism configuration of matrix-vector multiplications (MVMs). Meanwhile, the timing matching strategy alleviates the load-imbalance problem between MOU-S and the matrix operation unit based on top- k pruning (MOU-P). When running at 200MHz on Xilinx ADM-PCIE-7V3 FPGA, the proposed design achieves an improvement in energy efficiency in a range of 5%-237% for LSTM networks, and an improvement of 58% for GRU networks compared with state-of-the-art designs.

Convolutional neural networks (CNNs) have been widely used in image classification and recognition due to their effectiveness; however, CNNs use a large volume of weight data that is difficult to store in on-chip memory of embedded designs. Pruning can compress the CNN model at a small accuracy loss; however, a pruned CNN model operates slower when implemented on a parallel architecture. In this paper, a hardware-oriented CNN compression strategy is proposed; a deep neural network (DNN) model is divided into “no-pruning layers ($NP$-layers)” and “pruning layers ($P$-layers)”. A$NP$-layer has a regular weights distribution for parallel computing and high performance. A$P$-layer is irregular due to pruning, but it generates a high compression ratio. Uniform and incremental quantization schemes are used to achieve a tradeoff between compression ratio and processing efficiency at a small loss in accuracy. A distributed convolutional architecture with several parallel finite impulse response (FIR) filters is further proposed for the regular model in the$NP$-layers. A shift-accumulator based processing element with an activation-driven data flow (ADF) is proposed for the irregular sparse model in the$P$-layers. Based on the proposed compression strategy and hardware architecture, a hardware/algorithm co-optimization (HACO) approach is proposed for implementing a$NP-P$hybrid compressed CNN model on FPGAs. For a hardware accelerator on a single FPGA chip without the use of off-chip memory, a$27.5\times $compression ratio is achieved with 0.44% top-5 accuracy loss for VGG-16. The implementation of the compressed VGG-16 model on a Xilinx VCU118 evaluation board processes 83.0 frames per second (FPS) for image applications, this is$1.8\times $superior than the state-of-the-art design found in the technical literature.

Neural networks (NNs) are effective machine learning models that require significant hardware and energy consumption in their computing process. To implement NNs, stochastic computing (SC) has been proposed to achieve a tradeoff between hardware efficiency and computing performance. In an SC NN, hardware requirements and power consumption are significantly reduced by moderately sacrificing the inference accuracy and computation speed. With recent developments in SC techniques, however, the performance of SC NNs has substantially been improved, making it comparable with conventional binary designs yet by utilizing less hardware. In this article, we begin with the design of a basic SC neuron and then survey different types of SC NNs, including multilayer perceptrons, deep belief networks, convolutional NNs, and recurrent NNs. Recent progress in SC designs that further improve the hardware efficiency and performance of NNs is subsequently discussed. The generality and versatility of SC NNs are illustrated for both the training and inference processes. Finally, the advantages and challenges of SC NNs are discussed with respect to binary counterparts.

Approximate computing provides an emerging approach to design high performance and low power arithmetic circuits. The logarithmic multiplier (LM) converts multiplication into addition and has inherent approximate characteristics. In this article, dynamic range approximate LMs (DR-ALMs) for machine learning applications are proposed; they use Mitchell’s approximation and a dynamic range operand truncation scheme. The worst case (absolute and relative) errors for the proposed DR-ALMs are analyzed. The accuracy and the hardware overhead of these designs are provided to select the best approximate scheme according to different metrics. The proposed DR-ALMs are compared with the conventional LM with exact operands and previous approximate multipliers; the results show that the power-delay product (PDP) of the best proposed DR-ALM (DR-ALM-6) are decreased by up to 54.07 percent with the mean relative error distance (MRED) decreasing by 21.30 percent compared with 16-bit conventional design. Case studies for three machine learning applications show the viability of the proposed DR-ALMs. Compared with the exact multiplier and its conventional counterpart, the back-propagation classifier with DR-ALMs with a truncation length larger than 4 has a similar classification result for the three datasets; the K-means clustering application with all DR-ALMs has a similar clustering result for four datasets; and the handwritten digit recognition application with DR-ALM-5 or DR-ALM-6 for LeNet-5 achieves similar or even slightly higher recognition rate.

Deep neural networks (DNNs) have been widely used in classification due to their high accuracy. The softmax function is one of the important non-linear functions in DNNs. Therefore, high performance and efficient hardware design are sought. However, the improvement of the softmax function is difficult because the exponent and the division units are complex. In this paper, we propose new approximate hardware architectures for both the exponent and the division units. Compared with the state-of-the-art designs, the proposed approximate softmax design consumes significantly less resources and also achieves high performance while maintaining a very high accuracy.

Long Short-Term Memory (LSTM) has been widely adopted in many sequential applications, such as language model and speech recognition. LSTM usually incurs in a large memory requirement and high computational complexity. Therefore, LSTM has a limited applicability to embedded and mobile systems. In LSTM, a large number of operations and high storage are required for matrix-vector multiplication (MV). In this paper, we present a software and hardware co-design scheme for efficiently compressing MVs. By utilizing a structured matrix, quantization and selective top-k pruning, memory requirements are substantially reduced while only incurring in a negligible accuracy loss. Then, a block-parallel hardware architecture is proposed for the compressed LSTM. As requiring less multiplication operations and storage resources, the proposed architecture achieves the very good compression ratio. The proposed architecture is implemented on the Xilinx VCU118 and KC705 platforms. Experimental results show that the proposed design uses less DSP and BRAM resources.

Approximate computing is an advanced computational technique that trades the accuracy of computation results for better utilization of system resources. It has emerged as a new preferable paradigm over traditional computing architectures for many applications where inaccurate results are acceptable. However, approximate computing also introduces security vulnerabilities mainly due to the fact that the uncertain and unpredictable intrinsic errors during approximate execution may be indistinguishable from malicious modification of the input data, the execution process, and the results. On the other hand, interestingly, approximate computing presents new opportunities to secure the system and the computation. Existing work on the security of approximate computing covers threat models, countermeasures, and evaluations but lacks a framework for analysis and comparison. In this article, we provide a classification of the state-of-the-art works in this research field, including threat models in approximate computing and promising security approaches using approximate computing. Open questions and potential future research directions are also discussed.

Computing systems have been facing severe technology challenges in recent years with regard to power consumption, circuit reliability, and high performance. For many years, the issues of power consumption and performance have been addressed with the use of technology scaling.However, as Dennard’s scaling tends toward an end, it has become difficult to further improve the performance under the same power constraints. In addition to power, reliability also becomes a critical issue when the feature size of the complementary metal-oxide–semiconductor (CMOS) technology is reduced below 7 nm. Thus, ensuring the complete accuracy of the signal has become increasingly challenging in recent years.

Computing systems are conventionally designed to operate as accurately as possible. However, this trend faces severe technology challenges, such as power consumption, circuit reliability, and high performance. For nearly half a century, performance and power consumption of computing systems have been consistently improved by relying mostly on technology scaling. As per Dennard's scaling, the size of a transistor has been considerably shrunk and the supply voltage has been reduced over the years, such that circuits operate at higher frequencies but nearly at the same power dissipation level. However, as Dennard's scaling tends toward an end, it is difficult to further improve performance under the same power constraints. Power consumption has been a major concern, and it is now an industry-wide problem of critical importance. In addition to power, reliability deteriorates when the feature size of complementary metal-oxide-semiconductor (CMOS) technology is reduced below 7 nm, because parameter variations and faults at advanced nanoscales become difficult to control and prevent. Thus, to ensure the complete accuracy of signals, logic values, devices, and interconnects, manufacturing and verification costs will increase significantly.

This special issue explores the technological contributions and developments of approximate computing at disparate levels and provides insight into exciting directions for the future.

Taking advantage of the error resilience in many applications as well as the perceptual limitations of humans, numerous approximate arithmetic circuits have been proposed that trade off accuracy for higher speed or lower power in emerging applications that exploit approximate computing. However, characterizing the various approximate designs for a specific application under certain performance constraints becomes a new challenge. In this paper, approximate adders and multipliers are evaluated and compared for a better understanding of their characteristics when the implementations are optimized for performance or power. Although simple truncation can effectively reduce the hardware of an arithmetic circuit, it is shown that some other designs perform better in speed, power and power-delay product. For instance, many approximate adders have a higher performance than a truncated adder. A truncated multiplier is faster but consumes a higher power than most approximate designs for achieving a similar mean error magnitude. The logarithmic multipliers are very fast and power-efficient at a lower accuracy. Approximate multipliers can also be generated by an automated process to be very efficient while ensuring a sufficiently high accuracy.

Origin and functions of intermittent transitions among sleep stages, including short awakenings and arousals, constitute a challenge to the current homeostatic framework for sleep regulation, focusing on factors modulating sleep over large time scales. Here we propose that the complex micro-architecture characterizing the sleep-wake cycle results from an underlying non-equilibrium critical dynamics, bridging collective behaviors across spatio-temporal scales. We investigate θ and δ wave dynamics in control rats and in rats with lesions of sleep-promoting neurons in the parafacial zone. We demonstrate that intermittent bursts in θ and δ rhythms exhibit a complex temporal organization, with long-range power-law correlations and a robust duality of power law (θ-bursts, active phase) and exponential-like (δ-bursts, quiescent phase) duration distributions, typical features of non-equilibrium systems self-organizing at criticality. Crucially, such temporal organization relates to anti-correlated coupling between θ- and δ-bursts, and is independent of the dominant physiologic state and lesions, a solid indication of a basic principle in sleep dynamics.

Multiply and Accumulate (MAC) is one of the most common operations in modern computing systems. It is for example used in matrix multiplication and in new computational environments such as those executed on neural networks for deep machine learning. MAC is also used in critical systems that must operate reliably such as object recognition for vehicles. Therefore, MAC implementations must be able to cope with errors that may be caused for example by radiation. A common scheme to deal with soft errors in arithmetic circuits is the use of Reduced Precision Redundancy (RPR). RPR instead of replicating the entire circuit, uses reduced precision copies which significantly reduce the overhead while still being able to correct the largest errors. This paper considers the implementation of RPR Multiply and Accumulate circuits. First, it is shown that the properties of signed integer multiplication (two´s complement format) can be used to make RPR more efficient. Then its principles are extended to the MAC operation by proposing RPR implementations that improve the error correction capabilities with a limited impact on circuit overhead. The proposed schemes have been implemented and tested. The results show that they can significantly reduce the Mean Square Error (MSE) at the output when the circuit is affected by a soft error and the implementation overhead of the proposed schemes is extremely low.

In this paper, an adaptive approximation approach is proposed for the design of a divider and a square root (SQR) circuit. In this design, the division/SQR is computed by using a reduced-width divider/SQR circuit and a shifter by adaptively pruning some insignificant input bits. Specifically, for a $2n/n$ 2 n / n division, $2k$ 2 k and $k$ k ($k< n$ k < n ) consecutive bits are selected starting from the most significant ‘1’ in the dividend and divisor, respectively. At the same time, redundant least significant bits (LSBs) are truncated or if the number of remaining bits after pruning is smaller than the number of bits to be kept, ‘0's are appended to the LSBs of the inputs. To avoid overflow, a $2(k+1)/(k+1)$ 2 ( k + 1 ) / ( k + 1 ) divider is used to compute the $2k/k$ 2 k / k division. Finally, an error correction circuit is proposed to recover the error caused by the shifter using OR gates. For a $2n$ 2 n -bit approximate SQR circuit, similar pruning schemes are used to obtain a $2k$ 2 k -bit radicand. A $2k$ 2 k -bit SQR circuit and a shifter are then utilized to compute the SQR. This adaptive operation leads to very small maximum error distances of the approximate divider and SQR circuits, as shown by a theoretical error analysis. The proposed 16/8 approximate divider using an 8/4 exact array divider is $2.5\times$ 2 . 5 × as fast but only consumes 34.42 percent of the power of the accurate design. Compared to the accurate 16-bit array SQR circuit, the approximate design with a 6-bit radicand is $3.9\times$ 3 . 9 × as fast and consumes 20.66 percent of the power. The approximate SQR circuit using a 6-bit lookup table-based SQR circuit consumes 7.15 percent of the power of its corresponding accurate design. The proposed designs outperform other approximate designs in image processing applications including change detection (for the divider), envelope detection (for the SQR circuit) and image reconstruction (for both designs).

As technology scaling is reaching its limits, new approaches have been proposed for computional efficiency. Approximate computing is a promising technique for high performance and low power circuits as used in error-tolerant applications. Among approximate circuits, approximate arithmetic designs have attracted significant research interest. In this paper, the design of approximate redundant binary (RB) multipliers is studied. Two approximate Booth encoders and two RB 4:2 compressors based on RB (full and half) adders are proposed for the RB multipliers. The approximate design of the RB-Normal Binary (NB) converter in the RB multiplier is also studied by considering the error characteristics of both the approximate Booth encoders and the RB compressors. Both approximate and exact regular partial product arrays are used in the approximate RB multipliers to meet different accuracy requirements. Error analysis and hardware simulation results are provided. The proposed approximate RB multipliers are compared with previous approximate Booth multipliers; the results show that the approximate RB multipliers are better than approximate NB Booth multipliers especially when the word size is large. Case studies of error-resilient applications are also presented to show the validity of the proposed designs.

This paper presents a new write latency reduction scheme for a Phase Change Memory (PCM) made of Multi-Level Cells (MLCs). This scheme improves over an existing scheme found in the technical literature and known as CABS. The proposed scheme is based on the utilization of a new coding arrangement for the selection of candidate codewords. The code relies on the two-step feature found in the write operation of a MLC PCM and avoids the symbol that incurs in the largest latency at a higher rate than CABS. A detailed simulation based evaluation and comparison are also pursued; the proposed scheme accomplishes improvements in write latency (for parallel writing) as well as coding rate (16/17 for the proposed scheme versus 16/18 for CABS for 16 symbols or 32-bit word). As the proposed scheme utilizes novel selection criteria for the candidates, the design of the required circuitry (encoder and decoder) has also been changed with respect to CABS; in terms of hardware, the areas of the encoder and decoder for the proposed scheme are reduced by 73 and 56 percent respectively compared with CABS.

Error Correction Codes (ECCs) are commonly used to protect memories against soft errors with an impact on memory area and delay. For large memories, the area overhead is mostly due to the additional cells needed to store the parity check bits. In terms of delay, the overhead is mostly needed to detect and correct errors when the data is read from the memory. Most ECCs that can correct more than one error have a complex decoding process and so are limited in high speed memory applications. One exception is One Step Majority Logic Decodable (OS-MLD) codes for which decoding can be done in parallel at high speed. Unfortunately, there are only a few OS-MLD codes that provide a limited choice in terms of block sizes, error correction capabilities and code rate. Therefore, there is considerable interest in a novel construction of OS-MLD codes to provide additional choices for protecting memories. In this paper, a new method to construct Double Error Correction (DEC) OS-MLD codes is presented. This method is based on the use of parity check matrices in which two bits have at most two parity check equations in common; the proposed method provides codes that require a smaller number of parity check bits than existing codes like Orthogonal Latin Square (OLS) codes. The drawback of the proposed Two Bit Overlap (TBO) codes is that they require slightly more complex decoding than OLS codes. Therefore, they provide an intermediate solution between OLS and non OS-MLD codes in terms of decoding delay and number of parity check bits. The proposed TBO codes have been implemented for some block sizes and compared to both OLS and BCH codes to illustrate the trade off in delay and memory overhead. Finally, this paper discusses the generalization of the proposed scheme to codes with larger error correction capabilities.

With the rapid development of the Internet of Things (IoT), security has attracted considerable interest. Conventional security solutions that have been proposed for the Internet based on classical cryptography cannot be applied to IoT nodes as they are typically resource-constrained. A physical unclonable function (PUF) is a hardware-based security primitive and can be used to generate a key online or uniquely identify an integrated circuit (IC) by extracting its internal random differences using so-called challenge-response pairs (CRPs). It is regarded as a promising low-cost solution for IoT security. A logic reconfigurable PUF (RPUF) is highly efficient in terms of hardware cost. This article first presents a new classification for RPUFs, namely circuit-based RPUF (C-RPUF) and algorithm-based RPUF (A-RPUF); two Exclusive OR (XOR)-based RPUF circuits (an XOR-based reconfigurable bistable ring PUF (XRBR PUF) and an XOR-based reconfigurable ring oscillator PUF (XRRO PUF)) are proposed. Both the XRBR and XRRO PUFs are implemented on Xilinx Spartan-6 field-programmable gate arrays (FPGAs). The implementation results are compared with previous PUF designs and show good uniqueness and reliability. Compared to conventional PUF designs, the most significant advantage of the proposed designs is that they are highly efficient in terms of hardware cost. Moreover, the XRRO PUF is the most efficient design when compared with previous RPUFs. Also, both the proposed XRRO and XRBR PUFs require only 12.5% of the hardware resources of previous bitstable ring PUFs and reconfigurable RO PUFs, respectively, to generate a 1-bit response. This confirms that the proposed XRBR and XRRO PUFs are very efficient designs with good uniqueness and reliability.

The majority logic (ML) gate (MLG) is required in fast decoder implementations to protect memories from transient soft errors. In this paper, a novel MLG design is proposed; it consists of a pMOS pull-up network, an nMOS pull-down network, and an inverter. The proposed design is applicable to an arbitrary number of inputs γ (and operating as a mirror circuit when γ is odd). The proposed designs are simply requiring a small number of transistors; when simulated, they offer improved metrics such as reduction in delay, area, and power dissipation compared with existing designs found in the technical literature. When the combined power-delay-area product (PDAP) is considered, the advantages of the proposed designs are pronounced. The application of the proposed MLGs to design fast decoders for one-step ML decodable (OS-MLD) codes is also presented; the results show that the proposed MLGs are very efficient circuits for this coding application.

Recurrent neural networks (RNNs) are widely used to solve a large class of recognition problems, including prediction, machine translation, and speech recognition. The hardware implementation of RNNs is, however, challenging due to the high area and energy consumption of these networks. Recently, stochastic computing (SC) has been considered for implementing neural networks and reducing the hardware consumption. In this paper, we propose an energy-efficient and noise-tolerant long short-term memory-based RNN using SC. In this SC-RNN, a hybrid structure is developed by utilizing SC designs and binary circuits to improve the hardware efficiency without significant loss of accuracy. The area and energy consumption of the proposed design are between 1.6%-2.3% and 6.5%-11.2%, respectively, of a 32-bit floating-point (FP) implementation. The SC-RNN requires significantly smaller area and lower energy consumption in most cases compared to an 8-bit fixed point implementation. The proposed design achieves a higher noise tolerance compared to binary implementations. The inference accuracy is from 10% to 13% higher than an FP design when the noise level is high in the computation process.

This paper proposes a new design of an approximate hybrid divider (AXHD), which combines the restoring array and the logarithmic dividers to achieve an excellent tradeoff between accuracy and hardware performance. Exact restoring divider cells (EXDCrs) are used to generate the MSBs of the quotient for attaining a high accuracy; the other quotient digits are processed by a logarithmic divider as inexact scheme to improve figures of merit such as power consumption, area and delay. The proposed AXHD is evaluated and analyzed using error and hardware metrics. The proposed design is also compared with the exact restoring divider (EXDr) and previous approximate restoring dividers (AXDrs). The results show that the proposed design achieves very good performance in terms of accuracy and hardware; case studies for image processing also show the validity of the proposed designs.

Many approximate arithmetic circuits have been proposed for high-performance and low-power applications. However, most designs are either hardware-efficient with a low accuracy or very accurate with a limited hardware saving, mostly due to the use of a static approximation. In this paper, an adaptive approximation approach is proposed for the design of a divider. In this design, division is computed by using a reduced-width divider and a shifter by adaptively pruning the input bits. Specifically, for a 2n/n division 2k/k bits are selected starting from the most significant `1' in the dividend/divisor. At the same time, redundant least significant bits (LSBs) are truncated or if the number of remaining LSBs is smaller than 2k for the dividend or k for the divisor, `0's are appended to the LSBs of the input. To avoid overflow, a 2(k + 1)/(k + 1) divider is used to compute the division of the 2k-bit dividend and the k-bit divisor, both with the most significant bits being `0'. Thus, k <; n is a key variable that determines the size of the divider and the accuracy of the approximate design. Finally, an error correction circuit is proposed to recover the error caused by the shifter by using OR gates. The synthesis results in an industrial 28nm CMOS process show that the proposed 16/8 approximate divider using an 8/4 accurate divider is 2.5χ as fast and consumes 34.42% of the power of the accurate 16/8 design. Compared with the other approximate dividers, the proposed design is significantly more accurate at a similar power-delay product. Moreover, simulation results show that the proposed approximate divider outperforms the other designs in two image processing applications.

Deep neural networks (DNNs) are effective machine learning models to solve a large class of recognition problems, including the classification of nonlinearly separable patterns. The applications of DNNs are, however, limited by the large size and high energy consumption of the networks. Recently, stochastic computation (SC) has been considered to implement DNNs to reduce the hardware cost. However, it requires a large number of random number generators (RNGs) that lower the energy efficiency of the network. To overcome these limitations, we propose the design of an energy-efficient deep belief network (DBN) based on stochastic computation. An approximate SC activation unit (A-SCAU) is designed to implement different types of activation functions in the neurons. The A-SCAU is immune to signal correlations, so the RNGs can be shared among all neurons in the same layer with no accuracy loss. The area and energy of the proposed design are 5.27% and 3.31% (or 26.55% and 29.89%) of a 32-bit floating-point (or an 8-bit fixed-point) implementation. It is shown that the proposed SC-DBN design achieves a higher classification accuracy compared to the fixed-point implementation. The accuracy is only lower by 0.12% than the floating-point design at a similar computation speed, but with a significantly lower energy consumption.

Approximate computing is an emerging approach for designing high performance and low power arithmetic circuits. The logarithmic multiplier (LM) converts multiplication into addition and has inherent approximate characteristics. A method combining the Mitchell's approximation and a dynamic range operand truncation scheme is proposed in this paper to design non-iterative and iterative approximate LMs. The accuracy and the circuit requirements of these designs are assessed to select the best approximate scheme according to different metrics. Compared with conventional non-iterative and iterative 16-bit LMs with exact operands, the normalized mean error distance (NMED) of the best proposed approximate non-iterative and iterative LMs is decreased up to 24.1% and 18.5%, respectively, while the power-delay product (PDP) is decreased up to 51.7% and 45.3%, respectively. Case studies for two error-tolerant applications show the validity of the proposed approximate LMs.

This paper proposes an error compensation scheme of two-dimensional (2D) convolver in which both approximate circuit- and algorithm-level techniques are utilized in the design. Truncation and voltage scaling are used as circuit techniques, while bit-width reduction is utilized at the algorithm level. These different techniques are related to the configuration of the convolver by which its operation can be configured to meet different and often contrasting figures of merit. An extensive evaluation of different error metrics is performed. An error analysis is also presented to substantiate the simulation results; an error compensation scheme is introduced to remedy a loss of accuracy in computation. Convolution for image processing is treated in detail to show the effectiveness of the proposed approach. The design, the analysis and the simulation results show that the approximate techniques utilized in the inexact convolver can operate in synergy.

This paper presents the approximate designs of Fast Fourier Transformation (FFT) circuit. The tradeoff between accuracy and hardware performance is achieved by using bit-width selection for each stage. The error rate can be tuned with bit-width selection. We proposed two algorithms for bit-width selection under certain error restriction. The first algorithm is targeting an approximate FFT design with low hardware cost. While the second algorithm is proposed to achieve high performance. Both of proposed algorithms allow the designer to tradeoff hardware performance and computation accuracy in each stage. The proposed two designs are implemented on FPGA. The results show that the approximate FFT design using the first algorithm can reduce hardware resource consumption up to 30.2%. The second algorithm can increases the performance of the approximate FFT design up to 24.0%, while it also saves 25.2% resource consumption.

As a new paradigm in the nanoscale technologies, approximate computing enables error tolerance in the computational process; it has also emerged as a low power design methodology for arithmetic circuits. Majority logic (ML) is applicable to many emerging technologies and its basic building block (the 3-input majority voter) has been extensively used in digital circuit design. In this paper, we propose the design of a one-bit approximate full adder based on majority logic. Furthermore, multi-bit approximate full adders are also proposed and studied; the application of these designs to quantum-dot cellular automata (QCA) is also presented as an example. The designs are evaluated using hardware metrics (including delay and area) as well as error metrics. Compared with other circuits found in the technical literature, the optimal designs are found to offer superior performance.

This paper proposes a new framework for digital image processing; it relies on inexact computing to address some of the challenges associated with the discrete cosine transform (DCT) compression. The proposed framework has three levels of processing; the first level uses approximate DCT for image compressing to eliminate all computational intensive floating-point multiplications and executing the DCT processing by integer additions and in some cases logical right/left shifts. The second level further reduces the amount of data (from the first level) that need to be processed by filtering those frequencies that cannot be detected by human senses. Finally, to reduce power consumption and delay, the third level introduces circuit level inexact adders to compute the DCT. For assessment, a set of standardized images are compressed using the proposed three-level framework. Different figures of merits (such as energy consumption, delay, power-signal-to-noise-ratio, average-difference, and absolute-maximum-difference) are compared to existing compression methods; an error analysis is also pursued confirming the simulation results. Results show very good improvements in reduction for energy and delay, while maintaining acceptable accuracy levels for image processing applications.

Stochastic computation has recently been proposed for implementing artificial neural networks with reduced hardware and power consumption, but at a decreased accuracy and processing speed. Most existing implementations are based on pre-training such that the weights are predetermined for neurons at different layers, thus these implementations lack the ability to update the values of the network parameters. In this paper, a stochastic computational multi-layer perceptron (SC-MLP) is proposed by implementing the backward propagation algorithm for updating the layer weights. Using extended stochastic logic (ESL), a reconfigurable stochastic computational activation unit (SCAU) is designed to implement different types of activation functions such as the tanh and the rectifier function. A triple modular redundancy (TMR) technique is employed for reducing the random fluctuations in stochastic computation. A probability estimator (PE) and a divider based on the TMR and a binary search algorithm are further proposed with progressive precision for reducing the required stochastic sequence length. Therefore, the latency and energy consumption of the SC-MLP are significantly reduced. The simulation results show that the proposed design is capable of implementing both the training and inference processes. For the classification of nonlinearly separable patterns, at a slight loss of accuracy by 1.32-1.34 percent, the proposed design requires only 28.5-30.1 percent of the area and 18.9-23.9 percent of the energy consumption incurred by a design using floating point arithmetic. Compared to a fixed-point implementation, the SC-MLP consumes a smaller area (40.7-45.5 percent) and a lower energy consumption (38.0-51.0 percent) with a similar processing speed and a slight drop of accuracy by 0.15-0.33 percent. The area and the energy consumption of the proposed design is from 80.7-87.1 percent and from 71.9-93.1 percent, respectively, of a binarized neural network (BNN), with a similar accuracy.

Many systems have critical bits which must be decoded at high speeds; for example, flags to mark the start and end of a packet (SOP and EOP) determine subsequent actions, thus they must be decoded first and fast. This paper presents a new single and adjacent error correction (SAEC) code; as the codewords have critical bits, the proposed code accomplishes a fast decoding for them. The proposed code is a systematic code and permits shortening. This is accomplished by reducing the information bits, so that columns in the H matrix can be eliminated, while still keeping both the SAEC capability and the systematic feature, but for an odd number of information bits, an adjustment step in critical bits is required. It is shown that the check bit length of the proposed code is nearly the same as that of the traditional (optimal) Hamming SAEC code. The decoder of the proposed SAEC code is compared with the traditional Hamming SAEC code; this comparison shows that on average, the delay time for the critical bits is reduced by 6 percent compared with the traditional Hamming SAEC code (so at the same reduction level as a previous SEC scheme for fast decoding of critical bits over a traditional SEC code). Also, the area and power consumption of the proposed decoder show average reductions of 12 percent and 10 percent compared with the decoder of a traditional SAEC code.

This paper addresses at coding-level the challenge of providing a write latency reduction with either endurance enhancement and/or error control for a phase change memory (PCM) system. Endurance enhancement is assessed by considering the skewed write operations among the cells of a PCM system, i.e., when the maximal number of cell write operations is smaller, then the coding scheme achieves a better endurance, because the access of the memory cells in the system is more uniform (less skewed). As a first contribution, simulation of different industrial benchmarks shows that for realistic code rates (such as at k/n = 4/5), the write time speed-up (WTS) code not only reduces the write latency as previously reported, but it also reduces the skewed (nonuniform) use of PCM cells. This occurs because the WTS code uses as many cells as possible to reduce the number of SET operations in a PCM cell. Then, error control is considered. An encoding/decoding scheme that is compatible with a write latency reduction code, such as WTS, is proposed. For compatibility with the write latency reduction, a partition-based error control code (ECC) must be used. Also, the ECCs employed in these cases are systematic. The original information always appears in the codeword without modification. Evaluation by simulation shows that also in this case, the maximal number of write operations of the WTS code is smaller.

Approximate high radix dividers (HR-AXDs) are proposed and investigated in this paper. High-radix division is reviewed and inexact computing is introduced at different levels. Design parameters such as number of bits (N) and radix (r) are considered in the analysis; the replacement schemes with inexact cells and truncation schemes of exact cells in the binary signed-digit adder array is introduced. Circuit-level performance and the error characteristics of the inexact high radix dividers are analyzed for the proposed designs. The combined assessment of the normal error distance, power dissipation and delay is investigated and applications of approximate high-radix dividers are treated in detail. The simulation results show that the proposed approximate dividers offer extensive saving in terms of power dissipation, circuit complexity and delay, while only incurring in a small degradation in accuracy thus making them possibly suitable and interesting to some applications and domains such as low power/mobile computing.

This paper proposes a low-power non-volatile programmable inverter cell (NVPINV) that can be used with a COGRE (i.e. a compactly organized generic reconfigurable element) circuit to store the correct information for programming when establishing the desired logic function. The programmable data in the cell is read from a non-volatile SRAM (NVSRAM); two RMs (racetrack memories) are utilized as non-volatile elements. The RM is selected as non-volatile memory element due to its capability for independent operations (read and write), thus making possible a parallel execution of the programming process. The NVSRAM operates as a programmable circuit, i.e. a programmable circuit under control as either a buffer, or an inverter. The cell is extensively analyzed in terms of its operations with respect to different figures of merit, such as delay, power dissipation and power delay product (PDP). Simulation results show that in addition to low-power operation, the proposed NVPINV cell provides significant advantages (such as low delay and non-volatile storage) compared to an SRAM based Look-Up-Table (LUT) implementation.

Lower power has been a main challenge for IC design. Approximate computing provides a new approach for low power design. Logarithmic multiplier (LM) is a kind of approximate multipliers in nature. In this paper, the design of both non-iterative and iterative approximate LMs (IALM) are studied to further reduce the power consumption and improve the performance. Non-iterative approximate LMs (ALM) that use three inexact mantissa adders are presented. The proposed IALMs use set-one adder in both mantissa adders during the iteration and they also use lower-part-or adders and approximate mirror adders for the final addition. The error analysis and simulation results are also provided. It is found that the proposed approximate LMs with appropriate number of inexact bits has achieved even higher accuracy and lower power consumption compared with the conventional LMs using exact units. To be exact, compared with conventional LMs with exact units, the normalized mean error distance (NMED) of 16-bit approximate LMs is decreased by up to 18% and the power-delay product (PDP) has a reduction of up to 37%. The proposed approximate LMs are also compared with previous approximate Booth multipliers. It is found that approximate LMs are more suitable for applications allowing large errors but require less power consumption, while approximate Booth multipliers fit for applications allowing larger power but require less errors.

The increasing amount of circuit density possible in CMOS technology has the consequence of also increasing the power consumption of circuits using the technology. One possible method of offsetting these increased power demands is to use approximate computing designs in circuits where complete accuracy is not a strict requirement. These circuits use fewer logic gates which reduces power consumption at the cost of accuracy. Another possible method for reducing power consumption is to use an emerging nanotechnology which is already low power in nature. Combining approximate computing with an emerging nanotechnology has the potential to further cut power consumption. Unfortunately, existing approximate computing circuits were designed using standard logic gates found in CMOS technology which in turn can limit their effectiveness when implemented with the majority based logic used by some emerging nanotechnologies. For that reason, we propose designs of approximate arithmetic units which are specifically designed for use in majority logic based technologies.

A Physical Unclonable Function (PUF) is often used to uniquely identify an integrated circuit by extracting its internal random differences using so-called Challenge Response Pairs (CRPs). As CRPs include unique information about the underlying hardware variations, PUF design is a promising approach to provide authentication and IP-protection capabilities. In this paper, an XOR-gate-based configurable Ring Oscillator (RO) PUF (denoted as XCRO PUF) is presented. This XCRO PUF can generate more CRPs compared with state-of-the-art PUF designs by using the same number of configurable logic blocks (CLBs) in an FPGA implementation. This design is implemented in the Xilinx Spartan-6 XC6SLX9 FPGAs with fixed locations for the XCROs (placed within a ring to improve its uniqueness). The XCRO PUF shows better uniqueness and reliability than other PUF designs. Moreover, a XCRO PUF consumes only 12.5% of the hardware resources to generate a 1-bit response compared with other CRO PUFs implemented in FPGA.

Often as the most important arithmetic modules in a processor, adders, multipliers, and dividers determine the performance and energy efficiency of many computing tasks. The demand of higher speed and power efficiency, as well as the feature of error resilience in many applications (e.g., multimedia, recognition, and data analytics), have driven the development of approximate arithmetic design. In this article, a review and classification are presented for the current designs of approximate arithmetic circuits including adders, multipliers, and dividers. A comprehensive and comparative evaluation of their error and circuit characteristics is performed for understanding the features of various designs. By using approximate multipliers and adders, the circuit for an image processing application consumes as little as 47% of the power and 36% of the power-delay product of an accurate design while achieving similar image processing quality. Improvements in delay, power, and area are obtained for the detection of differences in images by using approximate dividers.

This paper relies on the principles of inexact computing to alleviate the issues arising in static masking by voting for reliable computing in the nanoscales. Two schemes that utilize in different manners approximate voting, are proposed. The first scheme is referred to as inexact double modular redundancy (IDMR). IDMR does not resort to triplication, thus saving overhead due to modular replication. This scheme is crudely adaptive in its operation, i.e., it allows a threshold to determine the validity of the module outputs. IDMR operates by initially establishing the difference between the values of the outputs of the two modules; only if the difference is below a preset threshold, then the voter calculates the average value of the two module outputs. The second scheme (ITDMR) combines IDMR with TMR (triple modular redundancy) by using novel conditions in the comparison of the outputs of the three modules. Within an inexact framework, the majority is established using different criteria; in ITDMR, adaptive operation is carried further than IDMR to include approximate voting in a pairwise fashion. So, the validity of the three inputs is established and when only two of the three inputs satisfy the threshold condition, the IDMR operation is utilized. An extensive analysis that includes the voting circuits as well as a probabilistic framework is included. The proposed IDMR and ITDMR schemes improve the power dissipation and tolerance to variations compared to a traditional TMR. To further validate the applicability of the proposed schemes, inexact voting has been used in two applications (image processing and FIR filtering); the simulation results show that performance is substantially improved over TMR.

A parallel decimal multiplier with improved performance is proposed in this paper by exploiting the properties of three different binary coded decimal (BCD) codes, namely the redundant BCD excess-3 code (XS-3), the overloaded decimal digit set (ODDS) code and the BCD-4221/5211 code. The signed-digit radix-10 recoding is used to recode the BCD multiplier to the digit set [-5, 5] from [0, 9]. The redundant BCD XS-3 code is adopted to generate the multiplicand multiples in a carry-free manner. The XS-3 coded partial products (PPs) are converted to ODDS PPs to fit binary partial product reduction (PPR). In this paper, a regular decimal PPR tree using ODDS and BCD-4221/5211 codes is proposed; it consists of a binary PPR tree block, a non-fixed size BCD-4221 counter block and a BCD-4221/5211 PPR tree block. The decimal carry-save algorithm based on BCD-4221/5211 is used in the PPR tree to obtain high performance multipliers. Moreover, an improved PPG circuit and an improved parallel prefix/carry-select decimal adder are proposed to further improve the performance of the proposed multipliers. Analysis and comparison using the 45 nm technology show that the proposed decimal multipliers are faster and require less hardware area than previous designs found in the technical literature.

Approximate computing is an attractive design methodology to achieve low power, high performance (low delay) and reduced circuit complexity by relaxing the requirement of accuracy. In this paper, approximate Booth multipliers are designed based on approximate radix-4 modified Booth encoding (MBE) algorithms and a regular partial product array that employs an approximate Wallace tree. Two approximate Booth encoders are proposed and analyzed for error-tolerant computing. The error characteristics are analyzed with respect to the so-called approximation factor that is related to the inexact bit width of the Booth multipliers. Simulation results at 45 nm feature size in CMOS for delay, area and power consumption are also provided. The results show that the proposed 16-bit approximate radix-4 Booth multipliers with approximate factors of 12 and 14 are more accurate than existing approximate Booth multipliers with moderate power consumption. The proposed R4ABM2 multiplier with an approximation factor of 14 is the most efficient design when considering both power-delay product and the error metric NMED. Case studies for image processing show the validity of the proposed approximate radix-4 Booth multipliers.

The design of high-performance adders has experienced a renewed interest in the last few years; among high performance schemes, parallel prefix adders constitute an important class. They require a logarithmic number of stages and are typically realized using AND-OR logic; moreover with the emergence of new device technologies based on majority logic, new and improved adder designs are possible. However, the best existing majority gate-based prefix adder incurs a delay of 2log2(n) - 1 (due to the nth carry); this is only marginally better than a design using only AND-OR gates (the latter design has a 2log2(n) + 1 gate delay). This paper initially shows that this delay is caused by the output carry equation in majority gate-based adders that is still largely defined in terms of AND-OR gates. In this paper, two new majority gate-based recursive techniques are proposed. The first technique relies on a novel formulation of the majority gate-based equations in the used group generate and group propagate hardware; this results in a new definition for the output carry, thus reducing the delay. The second contribution of this manuscript utilizes recursive properties of majority gates (through a novel operator) to reduce the circuit complexity of prefix adder designs. Overall, the proposed techniques result in the calculation of the output carry of an n-bit adder with only a majority gate delay of log2(n) + 1. This leads to a reduction of 40percent in delay and 30percent in circuit complexity (in terms of the number of majority gates) for multi-bit addition in comparison to the best existing designs found in the technical literature.

A parallel decimal multiplier is proposed in this paper to improve performance by mainly exploiting the properties of three different binary coded decimal (BCD) codes, namely the redundant BCD excess-3 code (XS-3), the overloaded decimal digit set (ODDS) code and BCD-4221/5211 code, hence this design is referred to as hybrid. The signed-digit radix-10 recoding with the digit set {-5, 5} and the redundant BCD excess-3 (XS-3) representations are used for partial product (PP) generation. In this paper, a new decimal partial product reduction (PPR) tree is proposed, it consists of a binary PPR tree block, a nonfixed size BCD-4221 counter correction block and a BCD-4221/5211 decimal PPR tree block. Analysis and comparison using the logical effort model and 45 nm technology show that the proposed decimal multiplier is faster compared with previous designs found in the technical literature.

This paper presents the design of a non-volatile register file using cells made of a SRAM and a Programmable Metallization Cell (PMC). The proposed cell is a symmetric 8T2P (8-transistors, 2PMC) design; it utilizes three control lines to ensure the correctness in its operations (i.e. Write, Read, Store and Restore). Simulation results using HSPICE are provided for the cell as well as the register file array (both one- and two-dimensional schemes). At cell level, it is shown that the off-state resistance has a limited effect on the Read time, because in the proposed circuit the transistor connecting the PMCs to the SRAM is off. While having no significant effect on the Store time, the time of the Restore operation depends on the value of the off-state resistance, i.e. an increase in off-state PMC resistance causes an increase in Restore time. Comparison between non-volatile register files utilizing either PMCs, or Phase Change Memories (PCMs) is provided. The register file using PMCs has a faster Store and Read times than the PCM-based counterpart; this is mostly caused by the difference in resistance values for these two non-volatile technologies. The lower delay involved in these operations confirms that the proposed PMC-based register file offers significant advantages in terms of delay performance.

A hybrid memory cell usually consists of a Static Random Access Memory (SRAM) and an embedded Dynamic Random Access Memory (eDRAM) cell; hybrid cells are particularly suitable for cache design. A novel hybrid cache memory scheme (that has also non-volatile elements) is initially proposed; this scheme is assessed through extensive simulation to show significant improvements in performance. Different design implementations of the hybrid cache are then proposed at architectural level and different features (such as the memory hit rate, the Instruction Per Cycle (IPC) access pattern and the memory cell access time) are also simulated at this level using benchmarks to show the advantages of the proposed scheme for use as an hybrid cache.

The physical unclonable function (PUF) produces die-unique responses and is regarded as an emerging security primitive that can be used for authentication of devices. The complexity of a conventional PUF design based on a ring oscillator (RO) is rather high, so limiting its use in many applications. The configurable ring oscillator (CRO) PUF has been advocated as a possible solution to this issue. In this paper, a low hardware complexity CRO PUF design with an enhanced capability to generate a large number of bit responses is proposed; only an inverter and a multiplexer are used in each delay unit. The responses are generated by considering the variation due to fabrication of the logic gates and wires in the CROs. A novel comparison strategy is proposed for the generation of the responses. The proposed PUF design is implemented on Xilinx Spartan-6 FPGAs. These results show that the proposed CRO PUF design has good uniqueness; moreover, it is also robust in its operation for the temperature range of -25°C~85°C.

Approximate or inexact computing has recently attracted considerable attention due to its potential advantages with respect to high performance and low power consumption. This paper presents the design of an approximate multiplier; this approximate multiplier consists of an approximate Booth encoder, an approximate 4-2 compressor and an approximate tree structure. The approximate design is implemented and verified for 8×8, 16×16 and 32×32-bit signed multiplication schemes targeting applications in embedded systems. Simulation results at 45 nm technology are provided and discussed. Compared with an exact Wallace-Booth multiplier as well as other approximate multipliers found in the technical literature, the proposed approximate scheme achieves significant improvements in power consumption, delay and combined metrics. These results show the viability of the proposed design.

This paper proposes several designs of approximate restoring dividers; two different levels of approximation (cell and array levels) are employed. Three approximate subtractor cells are utilized for integer subtraction as basic step of division; these cells tend to mitigate accuracy in subtraction with other metrics, such as circuit complexity and power dissipation. At array level, exact cells are either replaced or truncated in the approximate divider designs. A comprehensive evaluation of approximation at both cell- and array (divider) levels is pursued using error analysis and HSPICE simulation; different circuit metrics including complexity and power dissipation are evaluated. Different applications are investigated by utilizing the proposed approximate arithmetic circuits. The simulation results show that with extensive savings for power dissipation and circuit complexity, the proposed designs offer better error tolerant capabilities for quotient oriented applications (image processing) than remainder oriented application (modulo operations). The proposed approximate restoring divider is significantly better than the approximate non-restoring scheme presented in the technical literature.

Due to its high modularity and carry-free addition, a redundant binary (RB) representation can be used when designing high performance multipliers. The conventional RB multiplier requires an additional RB partial product (RBPP) row, because an error-correcting word (ECW) is generated by both the radix-4 Modified Booth encoding (MBE) and the RB encoding. This incurs in an additional RBPP accumulation stage for the MBE multiplier. In this paper, a new RB modified partial product generator (RBMPPG) is proposed; it removes the extra ECW and hence, it saves one RBPP accumulation stage. Therefore, the proposed RBMPPG generates fewer partial product rows than a conventional RB MBE multiplier. Simulation results show that the proposed RBMPPG based designs significantly improve the area and power consumption when the word length of each operand in the multiplier is at least 32 bits; these reductions over previous NB multiplier designs incur in a modest delay increase (approximately 5 percent). The power-delay product can be reduced by up to 59 percent using the proposed RB multipliers when compared with existing RB multipliers.

The Booth multiplier has been widely used for high performance signed multiplication by encoding and thereby reducing the number of partial products. A multiplier using the radix-$4$(or modified Booth) algorithm is very efficient due to the ease of partial product generation, whereas the radix-$8$Booth multiplier is slow due to the complexity of generating the odd multiples of the multiplicand. In this paper, this issue is alleviated by the application of approximate designs. An approximate$2$-bit adder is deliberately designed for calculating the sum of$1\times$and$2\times$of a binary number. This adder requires a small area, a low power and a short critical path delay. Subsequently, the$2$-bit adder is employed to implement the less significant section of a recoding adder for generating the triple multiplicand with no carry propagation. In the pursuit of a trade-off between accuracy and power consumption, two signed$16\times 16$bit approximate radix-8 Booth multipliers are designed using the approximate recoding adder with and without the truncation of a number of less significant bits in the partial products. The proposed approximate multipliers are faster and more power efficient than the accurate Booth multiplier. The multiplier with 15-bit truncation achieves the best overall performance in terms of hardware and accuracy when compared to other approximate Booth multiplier designs. Finally, the approximate multipliers are applied to the design of a low-pass FIR filter and they show better performance than other approximate Booth multipliers.

Power has become a key constraint in nanoscale integrated circuit design due to the increasing demands for mobile computing and higher integration density. As an emerging computational paradigm, an inexact circuit offers a promising approach to significantly reduce both dynamic and static power dissipation for error-tolerant applications. In this paper, an inexact floating-point adder is proposed by approximately designing an exponent subtractor and mantissa adder. Related operations such as normalization and rounding are also dealt with in terms of inexact computing. An upper bound error analysis for the average case is presented to guide the inexact design; it shows that the inexact floating-point adder design is dependent on the application data range. High dynamic range images are then processed using the proposed inexact floating-point adders to show the validity of the inexact design; comparison results show that the proposed inexact floating-point adders can improve the power consumption and power-delay product by 29.98 and 39.60 percent, respectively.

This manuscript proposes three classes of codes for error correction in a storage system in which the memory cells do not have the same number of levels, i.e., a multiscale storage. The proposed codes are single multiscale-symbol error correction (SMSEC) codes and are capable of correcting any errors occurring on a single memory cell, namely a column-deleted SMSEC code, an element-compacted SMSEC code and a product SMSEC code. In the proposed codes, the codewords are divided into two partitions, the elements on the first partition are over GF(2b1), while those on the remaining partition are over GF(2b2). This paper also gives guidelines for selection among the three SMSEC codes to meet the desired hardware overhead in the parallel decoder for realistic parameters of the partition pair, such as (b1, b2) 1/4 (4,3), (4,2) and (3,2). Moreover it is shown that the best choice for a MSS system is the SMSEC code with the shortest check bit length; if the check bit lengths of at least two codes are equal, then the use of the element-compacted SMSEC code incurs in the smallest hardware overhead.

Processing at the nanometric scales presents unique challenges that may require new computational paradigms such as approximate computing. In this paper a novel approach to memory protection using an unequal protection code (UEP) is proposed; this approach is in synergy with approximate (or inexact) computing. Multi-level burst error correcting UEP codes are analyzed. These codes improve over previously presented two-level burst error correcting UEP codes, because they utilize different conditions and criteria in the code partitions and decoder construction. An analysis by which multiple partitions can be selected to reduce the expected error magnitude, is provided. The area and power consumption of the parallel decoders closely depend on the desired code function. Simulation shows that the area and power consumption of the parallel error pattern generator are proportional to the partition length; the gate depth however is not strongly related to the partition length. The results of this manuscript confirm that the proposed multi-level burst error correcting UEP codes reduce the hardware overhead with no significant degradation in storage protection as potential storage application for approximate computing systems.

This paper proposes a novel scheme for a low-power non-volatile (NV) memory that exploits a two-level arrangement for attaining single event/multiple bit upsets (SEU/MBU) tolerance. Low-power hardened NVSRAM cell designs are initially utilized at the first level; these designs increase the critical charge and decrease power consumption by providing a positive (virtual) ground level voltage. A soft error rate (SER) analysis is also pursued to confirm the findings of the critical charge-based analysis. Simulation of these cells shows that their operation has a very high SEU tolerance, the charges in the nodes of the circuits for non-volatile storage and gate leakage current reduction have very high values, thus ensuring that a SEU will highly unlike affect the correct functions. A novel memory scheme with the proposed NVSRAM cells is proposed for tolerating MBU; in this scheme, only the error detection circuitry is required, because error correction is provided by the non-volatile elements of the NVSRAM cells. Simulation results show that the proposed scheme is very efficient in terms of delay and number of transistors (as measure of complexity). Moreover, the very high critical charge of some of the proposed cell designs reduces the number of MBU appearing as errors at the outputs of the memory, thus further reducing the error detection hardware required by the proposed scheme. An extensive evaluation and comparison of different schemes are presented.

A phased-mission system (PMS) usually consists of several nonoverlapping phases of tasks. All phases are required to be accomplished sequentially for a successful mission. Different features must be considered in the reliability evaluation of a PMS, including the dependence among the phases with respect to a common component and the different system topologies for the phases. To overcome the limitation of existing approaches, a stochastic computational approach is proposed for efficiently analyzing the reliability of a nonrepairable PMS. Stochastic logic models are proposed to analyze the common components in the different phases. In the stochastic analysis, the signal probabilities of the basic components are encoded as non-Bernoulli sequences of random permutations with fixed numbers of 1s and 0s. Thus, the proposed stochastic approach can be used to evaluate a PMS under any distribution. Based on the generated stochastic sequences for the basic components and the system topology, the failure probability of the PMS can be efficiently predicted. Several case studies are evaluated to show the accuracy and efficiency of the stochastic approach. Compared with a combinatorial analysis, the accuracy of the stochastic analysis varies with the length of the stochastic sequences. However, it is shown that the stochastic analysis is more efficient than a Monte Carlo simulation at the same execution complexity in the number of runs.

Presents a welcome message to introduce the first issue of this new publication.

This paper introduces two new cells for logic-in-memory (LiM) operation. The first novelty of these cells is the resistive random access memory configuration that utilizes a programmable metallization cell as nonvolatile element. CMOS transistors and ambipolar transistors are used as processing and control elements for the logic operations of the LiM cells. The first cell employs ambipolar transistors and CMOS in its logic circuit (7T2A1P), while the second LiM cell uses only MOSFETs (9T1P) to implement logic functions, such as AND, OR, and XOR. The operational mode of the proposed cells is voltage-based, which is much different from the previous designs in which a LiM cell operates on a current mode. Extensive simulation results using HSPICE are provided for the evaluation of these cells; comparison shows that the proposed two cells outperform previous LiM cells in metrics, such as logic operation delays, power delay product, circuit complexity, write time, and output swing.

This paper proposes several approximate divider designs; two different levels of approximation (cell and array levels) are investigated for non-restoring division. Three approximate subtractor cells are proposed and designed for the basic subtraction; these cells mitigate accuracy in subtraction with other metrics, such as circuit complexity and power dissipation. At array level, by considering the exact cells, both replacement and truncation schemes are introduced for approximate array divider design. A comprehensive evaluation of approximation at both cell and divider level is pursued. Different circuit metrics including complexity and power dissipation are evaluated by HSPICE simulation. Mean error distance (MED), normalized error distance (NED) and MED-power product (MPP) are provided to substantiate the accuracy and power trade-off of inexact computing. Different applications in image processing are investigated by utilizing the proposed approximate arithmetic circuits.

As an important arithmetic module, the adder plays a key role in determining the speed and power consumption of a digital signal processing (DSP) system. The demands of high speed and power efficiency as well as the fault tolerance nature of some applications have promoted the development of approximate adders. This paper reviews current approximate adder designs and provides a comparative evaluation in terms of both error and circuit characteristics. Simulation results show that the equal segmentation adder (ESA) is the most hardware-efficient design, but it has the lowest accuracy in terms of error rate (ER) and mean relative error distance (MRED). The error-tolerant adder type II (ETAII), the speculative carry select adder (SCSA) and the accuracy-configurable approximate adder (ACAA) are equally accurate (provided that the same parameters are used), however ETATII incurs the lowest power-delay-product (PDP) among them. The almost correct adder (ACA) is the most power consuming scheme with a moderate accuracy. The lower-part-OR adder (LOA) is the slowest, but it is highly efficient in power dissipation.

This paper presents the novel design of a Ternary Content Addressable Memory (TCAM); different from existing designs found in the technical literature, this cell utilizes a single Phase Change Memory (PCM) as storage element and ambipolarity for comparison. A memory core consisting of a CMOS transistor and a PCM is employed (1T1P); for the search operation, the data in the 1T1P memory core is read and its value is established using two differential sense amplifiers. Compared with other non-volatile memory cells using emerging technologies (such as PCM-based, and memristor-based), simulation results show that the proposed non-volatile TCAM cell offer significant advantages in terms of power dissipation, PDP for the search operation, write time and reduced circuit complexity (in terms of lower counts in transistors and storage elements).

Memory design has radically changed in the last few years; the emergence of new technologies has further improved performance and the traditional separation of storage levels between Static Random Access Memory (SRAM) and Dynamic Random Access Memory (DRAM) is not viable as in the past. Recently, the embedded DRAM (eDRAM) has been proposed for cache utilization to improve density while attempting to retain high performance operations; this scheme is often referred as hybrid due to the utilization of different technologies in a memory. In this paper, a hybrid scheme is proposed by adding non-volatile features and related circuits to the SRAM/eDRAM; an Oxide Resistive Random Access Memory (RRAM) is utilized as non-volatile storage in the embedded memory circuit. Different memory cells are proposed in this manuscript; they are evaluated with respect to circuit-level figures of merit as related to operational features (read, write, static noise margin, power delay product) as well as tolerance to event upsets (critical charge) and variations. Extensive simulation results using nanometric PTMs are provided. It is shown that the proposed designs offer substantial improvements over previous hybrid cells as well as a conventional NAND Flash memory cell.

Approximate adders have been considered as a potential alternative for error-tolerant applications to trade off some accuracy for gains in other circuit-based metrics, such as power, area and delay. Existing approximate adder designs have shown substantial advantages in improving many of these operational features. However, the error characteristics of the approximate adders still remain an issue that is not very well understood. A simulation-based method requires both programming efforts and a time-consuming execution for evaluating the effect of errors. This method becomes particularly expensive when dealing with various sizes and types of approximate adders. In this paper, a framework based on analytical models is proposed for evaluating the error characteristics of approximate adders. Error features such as the error rate and the mean error distance are obtained using this framework without developing functional models of the approximate adders for time-consuming simulation. As an example, the estimate of peak signal-to-noise ratios (PSNRs) in image processing is considered to show the potential application of the proposed analysis. This analytical framework provides an efficient method to evaluate various designs of approximate adders for meeting different figures of merit in error-tolerant applications.

Inexact (or approximate) computing is an attractive paradigm for digital processing at nanometric scales. Inexact computing is particularly interesting for computer arithmetic designs. This paper deals with the analysis and design of two new approximate 4-2 compressors for utilization in a multiplier. These designs rely on different features of compression, such that imprecision in computation (as measured by the error rate and the so-called normalized error distance) can meet with respect to circuit-based figures of merit of a design (number of transistors, delay and power consumption). Four different schemes for utilizing the proposed approximate compressors are proposed and analyzed for a Dadda multiplier. Extensive simulation results are provided and an application of the approximate multipliers to image processing is presented. The results show that the proposed designs accomplish significant reductions in power dissipation, delay and transistor count compared to an exact design; moreover, two of the proposed multiplier designs provide excellent capabilities for image multiplication with respect to average normalized error distance and peak signal-to-noise ratio (more than 50 dB for the considered image examples).

This manuscript proposes non-binary orthogonal Latin square (OLS) codes that are amenable to a multilevel phase change memory (PCM). This is based on the property that the proposed (n symbols, ksymbols) t-symbol error correcting code uses the same H matrix as an (n bits, kbits) binary t-bit error correcting OLS code. The new codes are shown to have a shorter check bit length and better probability in encoding/decoding than conventional binary OLS codes. Extensive results are provided for assessment and comparison. The proposed codes are also shown to be always better than the matrix codes, i.e. independently of the metric and the parameters employed in the comparison.

Approximate (or inexact) computing is an attractive paradigm for digital processing at nanometric scales for applications in which imprecision in computation can be tolerated for improvements in other computational figures of merit, such as power consumption, circuit complexity and delay. The same principles of approximate computing are investigated in this manuscript for storage protection using an unequal protection code (UEP). In the proposed UEP code, the codeword is divided into two partitions; these partitions have different error protection functions. This paper presents a new class of two-level burst error correcting UEP codes and its parallel decoder. The proposed code is more efficient than an existing code in term of code rate, area and power consumption for the parallel decoder.

A redundant system usually consists of primary and standby modules. The so-called spare gate is extensively used to model the dynamic behavior of redundant systems in the application of dynamic fault trees (DFTs). Several methodologies have been proposed to evaluate the reliability of DFTs containing spare gates by computing the failure probability. However, either a complex analysis or significant simulation time are usually required by such an approach. Moreover, it is difficult to compute the failure probability of a system with component failures that are not exponentially distributed. Additionally, probabilistic common cause failures (PCCFs) have been widely reported, usually occurring in a statistically dependent manner. Failure to account for the effect of PCCFs overestimates the reliability of a DFT. In this paper, stochastic computational models are proposed for an efficient analysis of spare gates and PCCFs in a DFT. Using these models, a DFT with spare gates under PCCFs can be efficiently evaluated. In the proposed stochastic approach, a signal probability is encoded as a non-Bernoulli sequence of random permutations of fixed numbers of ones and zeros. The component's failure probability is not limited to an exponential distribution, thus this approach is applicable to a DFT analysis in a general case. Several case studies are evaluated to show the accuracy and efficiency of the proposed approach, compared to both an analytical approach and Monte Carlo (MC) simulation.

In this brief, three nonvolatile flip-flop (FF)/SRAM cells that utilize a single magnetic tunneling junction (MTJ) as nonvolatile resistive element are proposed. These cells have the same core (i.e., 6T) but they employ different numbers of MOSFETs to implement the so-called instantly ON, normally OFF mode of operation. The additional transistors are utilized for the restore operation to ensure that the data stored in the nonvolatile circuitry can be written back into the FF core once the power is made available. These three cells (7T, 9T, and 11T) are extensively analyzed in terms of their operations in 32 nm technology, such as operational delays (for the write, read, and restore operations), the static noise margin (SNM), critical charge and process variations (in both the MOSFETs and the resistive element). Simulation results show that an increase in the number of MOSFETs in the cells causes improvements in critical charge and tolerance to process variations at the expense of an increase in power dissipation. The SNM and the delay of the restore operation, however, do not necessarily increase with the number of MOSFETs in the cell, but rather on the control of access to the storage nodes from the single MTJ.

This brief investigates the Restore mechanism of a nonvolatile static random access memory (NVSRAM) cell that utilizes two magnetic tunneling junctions (MTJs) as nonvolatile resistive elements and a 6T SRAM core. Two cells are proposed by employing different mechanisms for the Restore operation once the power is reestablished. The proposed cells use the bitline and supply as mechanisms to initiate the Restore operation, so connecting the two MTJs to different nodes of the NVSRAM circuitry. The cells are extensively analyzed in terms of their operations with respect to different figures of merit, such as operational delays (for the Write, Read, and Restore operations), the static noise margin, power consumption, critical charge, and process variations (in both the MOSFETs and the resistive elements). Simulation results show that the cell with the MTJs connected to the supply offers the best performance in terms of power for the Read/Restore operations; it also achieves the best Read delay, but the worst Restore delay.

Advances in CMOS technology have made digital circuits and systems very sensitive to manufacturing variations, aging, and/or soft errors. Fault-tolerant techniques using hardware redundancy have been extensively investigated for improving reliability. Quadded logic (QL) is an interwoven redundant logic technique that corrects errors by switching them from critical to subcritical status; however, QL cannot correct errors in the last one or two layers of a circuit. In contrast to QL, quadded transistor (QT) corrects errors while performing the function of a circuit. In this brief, a technique that combines QL with QT is proposed to take advantage of both techniques. The proposed quadded logic with quadded transistor (QLQT) technique is evaluated and compared with other fault-tolerant techniques, such as triple modular redundancy and triple interwoven redundancy, using stochastic computational models. Simulation results show that QLQT has a better reliability than the other fault-tolerant techniques (except in the very restrictive case of small circuits with low gate error rates and very short paths from primary inputs to primary outputs). These results provide a new insight for implementing efficient fault-tolerant techniques in the design of reliable circuits and systems.

This paper presents a hybrid non-volatile (NV) SRAM cell with a new scheme for SEU tolerance. The proposed NVSRAM cell consists of a 6T SRAM core and a Resistive RAM (RRAM), made of a 1T and a Programmable Metallization Cell (PMC). The proposed cell has concurrent error detection (CED) and correction capabilities; CED is accomplished using a dual-rail checker, while correction is accomplished by utilizing the restore operation; data from the non-volatile memory element is copied back to the SRAM core. The dual-rail checker utilizes two XOR gates each made of 2 inverters and 2 ambipolar transistors, hence, it has a hybrid nature. Extensive simulation results are provided. The simulation results show that the proposed scheme is very efficient in terms of numerous figures of merit such as delay and circuit complexity and thus applicable to integrated circuits such as FPGAs requiring secure on-chip non-volatile storage (i.e. LUTs) for multi-context configurability.

Approximate circuits have been considered for error-tolerant applications that can tolerate some loss of accuracy with improved performance and energy efficiency. Multipliers are key arithmetic circuits in many such applications such as digital signal processing (DSP). In this paper, a novel approximate multiplier with a lower power consumption and a shorter critical path than traditional multipliers is proposed for high-performance DSP applications. This multiplier leverages a newly-designed approximate adder that limits its carry propagation to the nearest neighbors for fast partial product accumulation. Different levels of accuracy can be achieved through a configurable error recovery by using different numbers of most significant bits (MSBs) for error reduction. The approximate multiplier has a low mean error distance, i.e., most of the errors are not significant in magnitude. Compared to the Wallace multiplier, a 16-bit approximate multiplier implemented in a 28nm CMOS process shows a reduction in delay and power of 20% and up to 69%, respectively. It is shown that by utilizing an appropriate error recovery, the proposed approximate multiplier achieves similar processing accuracy as traditional exact multipliers but with significant improvements in power and performance.

Dynamic Random Access Memories (DRAM) are widely used in processor design. Different cells have been proposed in the past to overcome concerns associated with low retention time, degradation in performance due to process variations and susceptibility to soft errors. This paper proposes two novel DRAM cells (referred to as 4TI and 4T1D) that utilize the techniques of gated diode and forward body-biasing to overcome the above issues. The designs of these cells are evaluated by HSPICE simulation; different figures of merits (such as Read delay, Write delay, retention time, power dissipation, critical charge and layout area) are assessed and a comparative analysis of the proposed cells with existing cells is pursued. The 4TI cell achieves the best power dissipation, while the 4T1D achieves the best retention time, the highest critical charge and the least average Read delay. An extensive simulation based evaluation of process variations is also presented to confirm that using static and Monte Carlo based analysis, the proposed cells are likely to be less affected by process variations (in threshold voltage and effective channel length) than the other cells found in the technical literature.

This paper presents a new method for diagnosing (detection and location) multiple faults in an application-dependent interconnect of a SRAM-based FPGA. For fault detection, the proposed technique retains the original interconnect configuration and modifies the function of the LUTs using the new LUT programming function 1-Bit Sum Function (1-BSF); in addition, it utilizes features such as branches in the nets as well as the primary (unused) IOs of the FPGAs. The proposed method detects all possible stuck-at and bridging faults of all cardinalities in a single configuration; fault detection requires$1 + {\rm log}_{2}k$test configurations for multiple stuck-at location and$2 + 2{\rm log}_{2}k$additional test configurations to locate more than one pair-wise bridging faults (where$k$denotes the maximum combinational depth of the FPGA circuit). Following detection, the locations of multiple faults are hierarchically identified using the walking-1 test set and an adaptive approach for the interconnect structure. Net ordering independence is accomplished by utilizing features such as the presence of paths of nets that are either disjoint or joint between the primary input and at least one primary output. As validated by simulation on benchmark circuits, the proposed method scales extremely well for different Virtex FPGA families; this results in a significant reduction in the number of configurations for diagnosing multiple faults.

Reliability is fast becoming a major concern due to the nanometric scaling of CMOS technology. Accurate analytical approaches for the reliability evaluation of logic circuits, however, have a computational complexity that generally increases exponentially with circuit size. This makes intractable the reliability analysis of large circuits. This paper initially presents novel computational models based on stochastic computation; using these stochastic computational models (SCMs), a simulation-based analytical approach is then proposed for the reliability evaluation of logic circuits. In this approach, signal probabilities are encoded in the statistics of random binary bit streams and non-Bernoulli sequences of random permutations of binary bits are used for initial input and gate error probabilities. By leveraging the bit-wise dependencies of random binary streams, the proposed approach takes into account signal correlations and evaluates the joint reliability of multiple outputs. Therefore, it accurately determines the reliability of a circuit; its precision is only limited by the random fluctuations inherent in the stochastic sequences. Based on both simulation and analysis, the SCM approach takes advantages of ease in implementation and accuracy in evaluation. The use of non-Bernoulli sequences as initial inputs further increases the evaluation efficiency and accuracy compared to the conventional use of Bernoulli sequences, so the proposed stochastic approach is scalable for analyzing large circuits. It can further account for various fault models as well as calculating the soft error rate (SER). These results are supported by extensive simulations and detailed comparison with existing approaches.

A novel ternary CNTFET-based SRAM cell is proposed in this paper; the operation of this CNTFET SRAM is nearly independent of the ternary values, therefore it is said to be balanced. Different from previous ternary cells, the proposed cell does not require a read buffer for changing the voltage level of the read bit line, because it uses additional CNTFETs to sink the bit lines to ground. By using four additional CNTFETs for ternary operation, a conventional (two-valued) sense amplifier is then used for output response. The contribution of this paper is not restricted to the design of the SRAM cell, but also the systematic modifications of the CNTFETs to substantially improve specific performance metrics. CNTFET features (such as sizing) and performance metrics (such as SNM, power delay product (PDP) and write/read times) are considered and assessed in detail. Extensive simulation results are provided to show that the proposed ternary SRAM cell has better performance compared to a previous CNTFET-based ternary cell as well as binary-based cells (implemented by either MOSFET or CNTFET).

This paper presents a new method for generating configurations for application-dependent testing of a SRAM-based FPGA interconnect. This method connects an activating input to multiple nets, thus generating activating test vectors for detecting stuck-at, open, and bridging faults. This arrangement permits a reduction in the number of redundant configurations, thus also achieving a reduction in test time for application-dependent testing at full fault coverage. As the underlying solution requires an exponential complexity, a heuristic algorithm that is polynomial and greedy in nature (based on sorting) is used for net selection in the configuration generation process. It is proved that this algorithm has an execution complexity of O(L3) (where L is the number of LUTs in the design). The proposed method requires at most log2(M + 2) configurations (where M denotes the number of activating inputs) as Walsh coding is employed. Moreover, it is scalable with respect to LUT inputs. Extensive logic-based simulation results are provided for ISCAS89 sequential benchmark designs implemented on Xilinx Virtex4 FPGAs; these results shows that the proposed method achieves a considerable reduction in the number of test configurations compared with methods found in the technical literature (on average, a reduction of 49.5 percent).

Scaling of CMOS technology into nanometric feature sizes has raised concerns for the reliable operation of logic circuits, such as in the presence of soft errors. This paper deals with the analysis of the operation of sequential circuits. As the feedback signals in a sequential circuit can be logically masked by specific combinations of primary inputs, the cumulative effects of soft errors can be eliminated. This phenomenon, referred to as error masking, is related to the presence of so-called restoring inputs and/or the consecutive presence of specific inputs in multiple clock cycles (equivalent to a synchronizing sequence in switching theory). In this paper, error masking is extensively analyzed using the operations of state transition matrices (STMs) and binary decision diagrams (BDDs) of a finite state machine (FSM) model. The characteristics of state transitions with respect to correlations between the restoring inputs and time sequence are mathematically established using STMs; although the applicability of the STM analysis is restricted due to its complexity, the BDD approach is more efficient and scalable for use in the analysis of large circuits. These results are supported by simulations of benchmark circuits and may provide a basis for further devising efficient and robust implementations when designing FSMs.

Addition is a fundamental function in arithmetic operation; several adder designs have been proposed for implementations in inexact computing. These adders show different operational profiles; some of them are approximate in nature while others rely on probabilistic features of nanoscale circuits. However, there has been a lack of appropriate metrics to evaluate the efficacy of various inexact designs. In this paper, new metrics are proposed for evaluating the reliability as well as the power efficiency of approximate and probabilistic adders. Reliability is analyzed using the so-called sequential probability transition matrices (SPTMs). Error distance (ED) is initially defined as the arithmetic distance between an erroneous output and the correct output for a given input. The mean error distance (MED) and normalized error distance (NED) are then proposed as unified figures that consider the averaging effect of multiple inputs and the normalization of multiple-bit adders. It is shown that the MED is an effective metric for measuring the implementation accuracy of a multiple-bit adder and that the NED is a nearly invariant metric independent of the size of an adder. The MED is, therefore, useful in assessing the effectiveness of an approximate or probabilistic adder implementation, while the NED is useful in characterizing the reliability of a specific design. Since inexact adders are often used for saving power, the product of power and NED is further utilized for evaluating the tradeoffs between power consumption and precision. Although illustrated using adders, the proposed metrics are potentially useful in assessing other arithmetic circuit designs for applications of inexact computing.

This paper presents a Ternary Content Addressable Memory (TCAM) cell that employs memristors as storage element. The TCAM cell requires two memristors in series to perform the traditional memory operations (read and write) as well as the search and matching operations for TCAM; this memory cell is analyzed with respect to different features (such as transistor sizing and voltage threshold) of the memristors to process fast and efficiently the ternary data. A comprehensive simulation based assessment of this cell is pursued by HSPICE.

This paper presents a novel HSPICE circuit model for designing and simulating a Single-Electron (SE) turnstile, as applicable at the nanometric feature sizes. The proposed SE model consists of two nearly similar parts whose operation is independent of each other; this disjoint feature permits to accurately model the sequential transfer of electrons through the turnstile in the storage node (modeled on a voltage level basis). It therefore avoids the transient (current-based) nature of a previous model. The model has been simulated and results show that it can correctly operate at 32 nm with excellent stability in its operation. Extensive simulation results are presented to substantiate the advantages of using the proposed model with respect to changes in the circuit model parameter.

This paper presents a new method for locating multiple faults in an interconnect following application testing of an FPGA. This method utilizes conditions related to the interconnect structure and in particular, the presence of paths of nets that are either disjoint or joint between the primary input and at least one primary output. They yield to a rather adaptive approach by which faults are hierarchically located using the walking-1 test set. The proposed method is not dependent on net ordering and is capable to locate multiple stuck-at and pairwise bridging faults. This process requires 1+log2k test configurations for multiple stuck-at location and 2+2log2k additional test configurations to locate more than one pair-wise bridging faults (where k denotes the maximum combinational depth). As validated by simulation for benchmark circuits (implemented on the Xilinx Virtex4), the proposed method results in a significant reduction in the number of configurations.

This paper presents a new method for application-dependent testing of SRAM-based FPGA interconnects at run time. This method utilizes new features related to the function for the programming of the LUTs, the utilization (by logic activation/deactivation) of the nets in a interconnect configuration as well as the primary (unused) IOs of the FPGAs. A new LUT programming function is introduced, the proposed method retains the original interconnect configuration and modifies the function of the LUTs using the so-called 1-Bit Sum Function (1-BSF), the 1-BSF detects all possible stuck-at and bridging faults (of all cardinalities) by utilizing the all zeros' vector and a walking-1 test set. As validated by simulation for benchmark circuits (implemented on the Xilinx Virtex4), the proposed method results in a single test configuration with 100% coverage under the assumed fault model.

This paper presents a novel memory cell consisting of a memristor and ambipolar transistors. Macroscopic models are utilized to characterize the operations of this memory cell. A detailed treatment of the two basic memory operations (write and read) with respect to memristor features is provided; particular, emphasis is devoted to the threshold characterization of the memristance and the on/off states. Extensive simulation results are provided to assess performance in terms of the write/read times, transistor scaling and power dissipation. The simulation results show that the proposed memory cell achieves superior performance compared with other memristor-based cells found in the technical literature.

The occurrence of a multiple node upset is likely to increase significantly in nanoscale CMOS due to reduced device size and power supply voltage scaling. This paper presents a comprehensive treatment (model, analysis and design) for hardening a memory cell against a soft error resulting in a multiple node upset at 32nm feature size in CMOS. A novel 13T memory cell configuration is proposed, analyzed, and simulated to show a better tolerance to the likely multiple node upset, i.e. a transient or soft fault affecting any two nodes in a cell. The proposed hardened memory cell utilizes a Schmitt trigger design; simulation shows that the multiple node upset tolerance is improved by nearly twice as much over existing designs. Moreover the 13T cell achieves a 33% reduction in write delay and only a 5% increase in power consumption compared to the DICE cell (consisting of 12 transistors). Simulation results are provided using the predictive technology file for 32nm feature size in CMOS. Monte Carlo simulation confirms the excellent multiple node upset tolerance of the proposed memory cell in the presence of process, voltage, and temperature variations in their designs.

This paper proposes a new hardening design for an 11 transistors (11T) CMOS memory cell at 32 nm feature size. The proposed hardened memory cell overcomes the problems associated with the previous design by utilizing novel access and refreshing mechanisms. Simulation shows that the data stored in the proposed hardened memory cell does not change even for a transient pulse of more than twice the charge than a conventional memory cell. Moreover it achieves 55% reduction in power delay product compared to the DICE cell (with 12 transistors) providing a significant improvement in soft error tolerance. Simulation results are provided using the predictive technology file for 32 nm feature size in CMOS.

Deep sub-micrometer/nano CMOS circuits are more sensitive to externally induced radiation phenomena that are likely to cause the occurrence of so-called soft errors. Therefore, the tolerance of the circuit to the soft errors is a strict requirement in nanoscale circuit designs. Since the traditional error tolerant methods result in significant cost penalties in terms of power, area, and performance, the development of low-cost hardened designs for storage cells (such as latches and memories) is of increasing importance. This paper proposes three new hardened designs for CMOS latches at 32 nm feature size; these circuits are Schmitt trigger based, while the third one utilizes a cascode configuration in the feedback loop. The Cascode ST latch has 112% higher critical charge than the conventional reference latch with only 10% area increase. A novel design metric (QPAR) for latches is introduced to assess the overall design effectiveness such as area, performance, power, and soft error tolerance. The novel metric (QPAR) shows the proposed cascode ST latch achieves up to 36% improvement in terms of QPAR compared with the existing hardening designs. Monte Carlo analysis has confirmed the robustness of the proposed hardened latches to process, voltage, and temperature (PVT) variations.

In this paper, capacitive 4-PWAM transmitter architectures and circuits are proposed and its performances are analyzed with random jitter and PVT variation comparing with other works. A novel technique is proposed to reduce power and to increase speed by using capacitive driven low swing transceiver. The proposed design saves 1.74~2.4x power and 4x higher data rate than conventional designs. To implement 4-PWAM transmitter new phase controller and adaptive capacitance network are designed. At receiver side, new architectures for PWM and PAM demodulation are proposed.

This paper investigates read-out schemes for a crossbar memory using CNTFET-based elements as cross-points. Two read-out schemes are presented in this paper; the first scheme biases the selected junction and measures the current flowing from the junction toward the ground while the second scheme involves biasing all other unselected bits and/or wordlines. Two figures of merit (the sense voltage on/off ratio and the sense current noise margin) are used to investigate the effectiveness of the proposed schemes for the CNTFET-based crossbar memory. Simulation results show that the CNTFET-based crossbar memory achieves improvements in both sense voltages on/off ratio and noise margin compared to the molecular memory implementation. Therefore, this paper demonstrates that these schemes make the CNTFET-based design a viable candidate for crossbar memory in the nanoscale era.

DNA self-assembly has been proposed as a promising "bottomup" manufacturing technique to supersede photolithography at nanometer scale. This paper discusses the application of DNA self-assembly for manufacturing templates of QCA circuits. Using a synthesis algorithm, a tile set of reduced cardinality is utilized for growing multiple patterns of the same QCA circuit on a two-dimensional template. Errors in the DNA self-assembly process are then considered; their implications on the operation of faulty QCA circuits following the deposition of QCA cells, are discussed. The errors are mostly clustered and along facets; a detailed treatment with respect to manufacturing yield, circuit functionality, error tolerance and growth speed is pursued. As a general conclusion, it is shown that errors are pattern dependent, hence the faults occurring in the assembled QCA circuits are physically and logically different.

Quantum-dot cellular automata (QCA) has been advocated as a promising emerging nanotechnology for designing future nanocomputing systems. However, at device level, the large number of expected defects represents a significant hurdle for reliable computation in QCA-based systems. In this paper, we present an information-theoretic approach to investigate the relationship between defect tolerance and redundancy in QCA devices. By modeling defect-prone QCA devices as unreliable information processing media, we determine the information transfer capacity, as bound on the reliability that QCA devices can achieve. The proposed method allows to evaluate the effectiveness of redundancy-based defect tolerance in an effective and quantitative manner.

As technology scales down in the deep sub-micron/nano ranges, CMOS circuits are more sensitive to externally induced phenomena to likely cause the occurrence of so-called soft errors. Therefore, the operation of these circuits to tolerate soft errors is a strict requirement in today’s designs. Traditional error tolerant methods result in significant cost penalties in terms of power, area and performance, and the development of low-cost hardened designs for storage cells (such as latches and memories) is of increasing importance. This paper proposes new hardened designs for CMOS latches at 32nm feature size. Three hardened latch circuits are proposed; two of these circuits are Schmitt trigger based, while the third one utilizes a cascode configuration in the feedback loop. These new hardened latches are shown to have superior performance in terms of power-delay product as well as highest tolerance to soft errors (measured by the critical charge) than existing hardened latches. Extensive simulation results are provided using the predictive technology file for 32nm feature size in CMOS.

Emerging technologies such as silicon NanoWires (NW) and Carbon NanoTubes (CNT) have shown great potential for building the next generation of computing systems in the nano ranges. However, the excessive number of defects originating from bottom-up fabrication (such as a self-assembly process) poses a pressing challenge for achieving scalable system integration. This article proposes a new nanosystem architecture that employs nanowire crossbars for Digital Signal Processing (DSP) applications. Distributed arithmetic is utilized such that complex signal processing computation can be mapped into regular memory operations, thus making this architecture well suited for implementation by nanowire crossbars. Furthermore, the inherent features of DSP-type computation provide new insights to remedy errors (as logic/computational manifestation of defects). A new defect/error-tolerant technique that exploits algorithmic error compensation is proposed; at system level different trade-offs between correctness in output and performance are established while retaining low overhead in its implementation. As an instance of its application, the proposed approach has been utilized to a generic DSP nanosystem performing frequency-selective filtering. Simulation results show that the proposed nanoDSP introduces only a minor performance degradation under high defect rates and at a range of operational conditions. The proposed technique also features good scalability and viability for various DSP applications.

The six papers in this special section cover a wide spectrum of techniques which are encountered in the design of circuits and systems for nano-scale computing.

A novel error detection/correction technique for algorithmic self-assembly is presented in this paper. Through the use of a tile set that allows errors to be isolated and propagated to the boundary edge of 2D (two-dimensional) assemblies, the proposed technique permits growth errors to be detected and corrected. For assemblies in which each four-sided tile is a party to only one tile mismatch, all growth errors in the assembly can be detected and corrected using the proposed method with only two additional tiles. This technique relies on the attachment of so-called isolation tiles at set periods, thus implementing a checkpoint for error detection/correction. The physical environment and related features for the removal of the erroneous sections of an assembly are presented.

This paper presents the design and evaluation of a new SRAM cell made of nine transistors (9T). The proposed 9T cell utilizes a scheme with separate read and write wordlines; it is shown that the 9T cell achieves improvements in power dissipation, performance and stability compared with previous designs (that require 10T and 8T) for low-power operation. The 9T scheme is amenable to small feature sizes as encountered in the deep sub-micron/nano ranges of CMOS technology.

In this paper, a novel CAD-based approach is presented for defect tolerance of QCA circuits. This approach is based on using QCA tiles and provides defect tolerance at circuit level with, in most cases, no area overhead. A ranking methodology is introduced to determine the tile configurations and logic functions that are optimal for logic synthesis of QCA circuits. Simulations on benchmark circuits show that the proposed methodology provides significant improvements in defect tolerance compared with QCA gate-based designs.

This paper presents a novel metric by which the effectiveness of punctures (as corrective action for error tolerance) can be assessed with respect to tile sets for DNA self- assembly in nano-manufacturing. Initially, the conditions for correct binding of a tile to an existing aggregate are analyzed using a Markovian approach; based on this analysis, it is proved that correct aggregation (as identified with a so-called Ideal Tile Set) is not always met for existing tile sets for nano-manufacturing. Hence, a metric is proposed for assessing tile sets by utilizing punctures. Tile sets are investigated and assessed with respect to features such error (mismatched tile) movement, punctured area and bond types. Subsequently, it is shown that the proposed metric can comprehensively assess the effectiveness of a type of a puncture for a tile set and its capability to attain error tolerance for the desired pattern. Extensive simulation results are provided.

Quantum-dot Cellular Automata is an emerging technology that offers significant improvements over CMOS. Recently QCA has been advocated as a technology for implementing reversible computing. However, existing tools for QCA design and evaluation have limited capabilities. This paper presents a new mechanical-based model for computing in QCA. By avoiding a full quantum-thermodynamical calculation, it offers a classical view of the principles of QCA operation and can be used in evaluating energy dissipation for reversible computing. The proposed model is mechanically based and is applicable to six-dot (neutrally charged) QCA cells for molecular implementation. The mechanical model consists of a sleeve of changing shape; four electrically charged balls are connected by a stick that rotates around an axle in the sleeve. The sleeve acts as a clocking unit, while the angular position of the stick within the changing shape of the sleeve, identifies the phase for quasi-adiabatic switching. A thermodynamic analysis of the proposed model is presented. The behaviors of various QCA basic devices and circuits are analyzed using the proposed model. It is shown that the proposed model is capable of evaluating the energy consumption for reversible computing at device and circuit levels for molecular QCA implementation. As applicable to QCA, two clocking schemes are also analyzed for energy dissipation and performance (in terms of number of clocking zones).

Time, power, and data volume are among some of the most challenging issues for testing system-on-chip (SoC) and have not been fully resolved, even if a scan-based technique is employed. A novel architecture, referred to the selective trigger scan architecture, is introduced in this paper to address these issues. This architecture reduces switching activity in the circuit-under-test (CUT) and increases the clock frequency of the scanning process. An auxiliary chain is utilized in this architecture to avoid the large number of transitions to the CUT during the scan-in process, as well as enabling retention of the currently applied test vectors and applying only necessary changes to them. The auxiliary chain shifts in the difference between consecutive test vectors and only the required transitions (referred to as trigger data) are applied to the CUT. Power requirements are substantially reduced; moreover, DFT penalties are reduced because no additional multiplexer is utilized along the scan path. Data reformatting is applied in order to make the proposed architecture amenable to data compression, thus permitting a further reduction in test time. It also permits delay fault testing. Using ISCAS 85 and 89 benchmark circuits, the effectiveness of this architecture for improving SoC test measures (such as power, time, and data volume) is experimentally evaluated and confirmed.

Quantum-dot Cellular Automata (QCA) has been widely advocated as a new device architecture for nanotechnology. QCA systems require extremely low power, together with the potential for high density and regularity. These features make QCA an attractive technology for manufacturing memories in which the paradigm of memory-in-motion can be fully exploited. This paper proposes a novel serial memory architecture for QCA implementation. This architecture is based on utilizing new building blocks (referred to as tiles) in the storage and input/output circuitry of the memory. The QCA paradigm of memory-in-motion is accomplished using a novel arrangement in the storage loop and timing/clocking; a three-zone memory tile is proposed by which information is moved across a concatenation of tiles by utilizing a two-level clocking mechanism. Clocking zones are shared between memory cells and the length of the QCA line of a clocking zone is independent of the word size. QCA circuits for address decoding and input/output for simplification of the Read/Write operations are discussed in detail. An extensive comparison of the proposed architecture and previous QCA serial memories is pursued in terms of latency, timing, clocking requirements, and hardware complexity.

This paper addresses the issues revolving around the synthesis of tile sets for DNA self-assembly as a promising approach for IC manufacturing in the nanoscale. As for a finite pattern, synthesis for minimizing tile or bond types is equivalent to a minimum graph coloring problem, two greedy algorithms that reduce the number of tiles (PATS_Tile) or bonds (PATS_Bond) in synthesized tile sets are proposed and evaluated. Both algorithms are O(l4) for a square pattern of dimension l. It is shown by simulation that PATS_Tile has a better average performance if both types of reduction must be accomplished.

At nanoscale, quantum-dot cellular automata (QCA) defines a new device architecture that permits the innovative design of digital systems. Features of these systems are the allowed crossing of signal lines with different orientation in polarization on a Cartesian plane, the potential of high throughput due to efficient pipelining, fast signal switching, and propagation. However, QCA designs of even modest complexity suffer from the negative impact due to the placement of long lines of cells among clocking zones, thus resulting in increased delay, slow timing, and sensitivity to thermal fluctuations. In this paper, different schemes for clocking and timing of the QCA systems are proposed; these schemes utilize 2D techniques that permit a reduction in the longest line length in each clocking zone. The proposed clocking schemes utilize logic-propagation techniques that have been developed for systolic arrays. Placement of QCA cells is modified to ensure correct signal generation and timing. The significant reduction in the longest line length permits a fast timing and efficient pipelining to occur while guaranteeing a kink-free behavior in switching.

This paper presents a novel modeling analysis of jitter as applicable to testing of serial data channels. Jitter is analyzed by considering separate and combined components. The primary goal is the generation of a signal containing a known amount of each jitter component. This signal can then be used for testing high speed serial data channels. Initially, jitter components are analyzed and modeled individually. Next, sequences for combining them are modeled, simulated and evaluated. Model simulation using Matlab is utilized to show the unique features of the components when they are combined into different injection sequences for producing the total jitter. Sequence dependency is investigated in depth and the validity of superposition of jitter components for typical values is confirmed. A good agreement between theory and simulation is verified; these results allow test engineers to have an insight into the interactions among jitter components in serial data channels.

Carbon nanotube field effect transistors (CNTFET) are promising nano-scaled devices for implementing high performance, very dense and low power circuits. The core of a CNTFET is a carbon nanotube. Its conductance property is determined by the so-called chirality of the tube; chirality is difficult to control during manufacturing. This results in conducting (metallic) nanotubes and defective CNTFETs similar to stuck-on (SON or source-drain short) faults, as encountered in classical MOS devices. This paper studies this phenomenon by using layout information and presents modeling and detection methodologies for nano-scaled defects arising from the presence of metallic carbon nanotubes. For CNTFET-based circuits (e.g. intramolecular), these defects are analyzed using a traditional stuck-at fault model. This analysis is applicable to primitive and complex gates. Simulation results are presented for detecting modeled metallic nanotube faults in CNTFETs using a single stuck-at fault test set. A high coverage is achieved (~98%)

This paper proposes a novel technique based on profiling the monomers for reducing the error rate in DNA self-assembly. This technique utilizes the average concentration of the monomers (tiles) for a specific pattern as found by profiling its growth. The validity of profiling and the large difference in the concentrations of the monomers are shown to be applicable to different tile sets. To evaluate the error rate new Markov based models are proposed to account for the different types of bonding (i.e. single, double and triple) in the monomers as modification to the commonly assumed kinetic trap model. A significant error rates reduction is accomplished compared to a scheme with constant concentration as commonly utilized under the kinetic trap model. Simulation results are provided

This paper presents a novel and efficient approach for reliability enhancement at the RT level. The reliability enhancement is performed by utilizing the available resources of a design in their dead intervals. Such resources are used for constructing dynamic TMR structures that can change per clock cycle. In this method all resources participate in constructing TMR structures at least once per a system input to output flow.To evaluate the proposed fault tolerance technique we consider dependability, and area/latency overhead imposed on a circuit by applying our method. In order to evaluate dependability, faults are injected into our test circuits before and after applying our algorithm and fault coverage is measured. Experimental results show that after applying our method, fault coverage is significantly reduced indicating that the reliability of designs is improved.

Self-assembly by DNA tiles has been advocated as a possible technique for bottom-up manufacturing of scaffolds in the nanoscale region. However, self-assembly is severely affected by facet roughening errors. A particularly effective error tolerant method utilizes snake tile sets with a square block of even dimension (i.e. 2 k times 2 k) of tiles. Snake tile sets of odd dimension (i.e. (2 k - 1) x (2k - 1)) have also been proposed. To analyze error tolerant mechanism of snake tile sets, this paper presents an analytical Markov model for facet roughening errors. A generalized model is proposed and used to analyze snake tile sets for the realistic cases of k = 2 and 3. Closed form solutions are attained in the analysis. Simulation results are presented to confirm that snake tile sets of odd dimension are more tolerant to facet errors than other tile sets for self-assembly.

As a possible technology for bottom-up manufacturing, DNA self-assembly requires tolerance to different errors. Among the methods for reducing the error rate, snake tile sets utilize a square block of even dimension of tiles (i.e., 2ktimes2k). In this paper, an odd-sized square block (i.e., (2k-1)times(2k-1)) is proposed as basis for snake tile sets. In comparison with all other tile sets, the proposed snake tile sets achieve a considerable reduction in error rate for growth and facet roughening errors. Simulation results are provided.

The five papers in this special section cover a wide spectrum of techniques which are encountered in nano-scale computing systems. Briefly summarizes the articles included in this section.

In this paper, different circuit arrangements of quantum-dot cellular automata (QCA) are proposed for the so-called coplanar crossing. These arrangements exploit the majority voting properties of QCA to allow a robust crossing of wires on the Cartesian plane. This is accomplished using enlarged lines and voting. Using a Bayesian network (BN) based simulator, new results are provided to evaluate the robustness to so-called kink of these arrangements to thermal variations. The BN simulator provides fast and reliable computation of the signal polarization versus normalized temperature. It is shown that by modifying the layout, a higher polarization level can be achieved in the routed signal by utilizing the proposed QCA arrangements

Quantum dot Cellular Automata (QCA) is one of the promising technologies for nano scale implementation. The operation of QCA systems is based on a new paradigm generally referred to as processing-by-wire (PBW). This paper analyzes the defect tolerance properties of PBW when tiles are employed using molecular QCA cells. Based on a 3×3 QCA block, with different input/output arrangements, different tiles are analyzed and simulated using a coherence vector engine. The functional characterization and polarization level of these tiles for undeposited cell defects are reported. It is shown that novel features of PBW are possible due to spatial redundancy and QCA tiles are robust and inherently defect tolerant.

Emerging technologies have attracted a substantial interest in overcoming the physical limitations of CMOS as projected at the end of the Technology Roadmap; among these technologies, quantum-dot cellular automata (QCA) relies on different and novel paradigms to implement dense, low power circuits and systems for high-performance computing. As applicable to existing technologies, a hierarchical process can be utilized to facilitate the design of QCA circuits. Tools and methodologies both at system and physical levels are required to support all design phases. This article presents an HDL model to describe QCA “devices” (also referred elsewhere in the technical literature as building blocks, i.e., majority voter, inverter, wire, crossover) and facilitate the evaluation of their design. This tool, referred to as HDLQ, allows a designer to verify the logic characteristics of a QCA system, while supporting within a design environment different operational mechanisms (such as fault injection) and the unique features of QCA (such as bidirectionality and timing/clocking partitioning). The applicability of this design environment to various memory circuits for logic and timing verification is presented in detail. Various defective conditions for kinks due to thermodynamic effects and permanent faults due to manufacturing defects are considered for injection.

IT is with great pleasure that we introduce the special section on Design and Test of Systems-on-Chips (SoC) to the readership of the IEEE Transactions on Computers. This special section consists of eight papers that have been selected to cover a wide spectrum of techniques and applications which are encountered in the design, manufacturing, assembly, and test of today’s SoC. These papers are authored by outstanding researchers and cover experimental and speculative topics. As with all special sections, these topics are only representative of the publically available literature currently provided by the technical community. Systems-on-a-Chip (SoC) represent a rapidly growing and promising field in the electronic and computer industry. Such tremendous growth is the result of significant advances in microelectronic technology that make it possible to build on the same silicon substrate complex systems, including electronic (analog, digital, and mixed mode), mechanical, optical, RF, and microwave cores, as well as sensors, actuators, and software-based systems. As a result, SoCs are very complex hardware/software systems, offering high-performance features. Examples of possible applications include wireless systems, real-time control systems, space exploration systems, and others. SoCs offer the inherent advantages in which computers and their digital domain can be merged to a variety of technologies and applications which, in the past, were attained at boardlevel. The design and test of such complex systems, however, still constitutes a major challenge. From a design point of view, the ability to have a correctly functioning SOC depends on the ability to design and analyze a mixed-technology and to properly account for the interactions among the various cores. Proper management of interfaces between diverse cores and synchronization are examples of the problems to be faced. The unavailability of proper design and simulation tools for such complex systems and the limited resources for different technologies (such as mixed-signal systems) make such an effort rather difficult. The relation between the different modules of an SoC must be properly established using advanced techniques whose technological basis is just emerging. It is expected that these techniques will be highly inter and intradisciplinary in nature, thus involving designers with different backgrounds. Configurability and programmability of the cores in an SoC suggest that wide applicability of these systems is indeed possible with great flexibility in integration. A further issue that designers are confronting is the evaluation of different configurations associated with the high density integration of cores. The merging of different technologies (such as digital and analog) on a single chip is also of high speculative interest because the manufacturing and organization of these systems is in its infancy. These new features must be evaluated at the early design stages because they have a considerable effect on the performance of SoCs as well as their viability for cost-effective implementation. From a testing point of view, the development of proper test access mechanisms is one of the major challenges to be faced in the near future, as indicated also by the 1999 International Technology Roadmap for Semiconductors. The test access mechanisms must be compatible with the IEEE P1500 standard, which was developed for embedded core testing and which leaves the problem of the Test Access Mechanism (TAM) design to the system integrator. Several test access mechanisms have been proposed, including dedicated test bus, multiplexed access, etc., but the goal is to find a solution allowing the best trade-off between the test quality and cost (including the testing time). To evaluate test quality, however, complex failure mechanisms which might occur in such complex systems should also be evaluated. As an example, the possible occurrence of undesired coupling, noise, and skews between clock signals of diverse cores are some of the simplest failures which may affect the operation of the interfaces among the cores. Proper models, fault simulation tools, and test quality figures are needed. Testing time should also be reduced. In fact, while the design and test of SoCs requires a long time (similar to any computer system), the time-to-market of an SoC should be kept as short as possible to meet today’s consumers’ changing requirements. The high performance possibly offered by the integration of complex systems on the same chip makes SoCs very promising for real-time applications, like control systems for automotive, avionic, space, chemical plants, etc. As an example, the first prototypes of SOCs, including electronic and mechanical cores, have already been employed by NASA for space exploration missions. Such a promising application potential, however, poses the problem of reliable design and verification as well as correct design and test. In the past, fault tolerance has been generally adopted to electronic systems for many critical mission applications. The possible adoption of fault tolerance techniques for SoCs (to include not only electronics, digital IEEE TRANSACTIONS ON COMPUTERS, VOL. 55, NO. 2, FEBRUARY 2006 97

This paper addresses error-resilience as the capability to tolerate bit-flips in a compressed test data stream (which is transferred from an automatic test equipment (ATE) to the device-under-test (DUT)). In an ATE, bit-flips may occur in either the electronics components of the loadboard, or the high speed serial communication links (between the user interface workstation and the head). It is shown that errors caused by bit-flips can seriously degrade the test quality (as measured by coverage) of the compressed data streams. The effects of bit-flips on compression are analyzed and various test data compression techniques are evaluated. It is shown that for benchmark circuits, coverage of test sets can be reduced by 10%-30%.

Single event upsets (SEU), as well as permanent faults, can significantly affect the correct on-line operation of digital systems, such as memories and microprocessors; a memory can be made resilient to permanent and transient faults by using modular redundancy and coding. Different memory systems are compared; these systems utilize simplex and duplex arrangements with a combination of Reed Solomon coding and scrubbing. The memory systems and their operations are analyzed by novel Markov chains to characterize the performance for dynamic reconfiguration as well as error detection and correction under the occurrence of permanent and transient faults. For a specific Reed Solomon code, the duplex arrangement is able to cope efficiently with the occurrence of permanent faults, while the use of scrubbing allows it to cope with transient faults.

This paper presents a novel approach for compressing functional test data in Automatic Test Equipment (ATE). A practical technique is presented for 2 Dimensional (2D) reordering of test data in which additionally to test vector reordering, column reordering is also applied. An ATE based approach to extract the original test vectors from the 2D ordered data is presented. The advantage of the approach is substantiated using the figure of merit of entropy for the 2D ordered test data of ISCAS benchmark circuits.

This paper presents a novel methodology to improve error resilience for reliable compression of test data of VLSI circuits. The presence of so-called "bit-flips" (due to the high speed manufacturing test or noise in the Automatic Test Equipment (ATE) head) can lead to a significant loss in coverage when compression is employed. As reported in the technical literature, coverage can experience a reduction of as much as 30% due to bit-flips in the compressed sequence of the test data. Differently from reported works, the proposed technique adds a very small amount of redundant information to test data prior to its compression; the objective of the redundant data is to limit the so-called "propagation" effect due to bit-flips once the sequence is decompressed. Extensive simulation results are presented to substantiate the increase in error resilience and to evaluate the impact of the redundancy introduced by the proposed approach on the compression ratio. It is shown that for the ISCAS89 benchmark circuits the reduction in coverage is only 0.20%-3.52% which is significantly better than previously reported works.

Quantum-dot Cellula Automata (QCA) has been widely advocated as a new device architecture fo nano technology. QCA systems require extremely low power together with the potential for high density and regularity. These features make QCA an attractive technology for manufacturing memories in which the paradigm of memory-in-motion can be fully exploited. This paper proposes a novel serial memory architecture for QCA implementation. This architecture is based on utilizing new building blocks (referred to as tiles) in the storage and input/output circuitry of the memory. The QCA paradigm of memory-in-motion is accomplished using a novel arrangement in the storage loop and timing/clocking; a three-zone memory tile is proposed by which information is moved across a concatenation of tiles by utilizing a two-level clocking mechanism. Clocking zones are shared between memory cells and the length of the QCA line in a clocking zone is independent of word size. This results in a substantial eduction in clocking zones compared with previous serial memories.

The design of circuits and systems in Quantum-dot Cellular Automata (QCA) is still in infancy. The basic logic primitive in QCA is the majority voter (MV), that is not a universal function; so, inverters (INV) are also required. Blocks (referred to as tiles) are utilized in this article. A tile with a combined logic function of MV and INV (MV-like function) is proposed. It is shown that the MV-like tile can be effectively used in logic design as basic primitive. Tiles based on both the fully populated (FP) and non-fully populated (NFP) grids are investigated in detail. Various arrangements in inputs and outputs are also possible among the 4 sides of a grid, thus defining different tiles. Using a coherence vector simulation engine, it is shown that the 3 × 3 grid offers versatile logic operation. Different combinational functions such as majority-like and wire crossing are obtained using these tiles. Tile-based design of different circuits is compared to gate-based and SQUARES designs.

This paper proposes arithmetic coding for application to data compression for VLSI testing. The use of arithmetic codes results in a codeword whose length is close to the optimal value (as predicted by entropy in information theory), thus achieving a higher compression. Previous techniques (such as those based on Huffman or Golomb coding) result in optimal codes for data sets in which the probability model of the symbols satisfies specific requirements. This paper shows empirically and analytically that Huffman and Golomb codes can result in a large difference between the bound established by the entropy and the attained compression; therefore, the worst-case difference is studied using information theory. Compression results for arithmetic coding are presented using ISCAS benchmark circuits; a practical integer implementation of arithmetic coding/decoding and an analysis of its deviation from the entropy bound are pursued. A software implementation is proposed using embedded DSP cores. In the experimental evaluation, fully specified test vectors and test cubes from two different ATPG programs are utilized. The implications of arithmetic coding on manufacturing test using an ATE are also investigated.

Quantum-dot cellular automata (QCA) offers a new computing paradigm for nanotechnology. The basic logic elements of this technology are the majority voter (MV) and the inverter (INV). However, an experimental evaluation has shown that MV is not efficiently used during technology mapping by existing logic-synthesis tools. In this paper, we propose the design and characterization of a novel complex, yet very small, QCA logic gate: the and-or-inverter (AOI) gate. The paper presents a detailed simulation-based analysis of the AOI gate, as well as the study of QCA defects and their effects at the logic level. The AOI implements a universal logic gate; all elementary gates can be implemented by the AOI gate. Moreover, many two-level logic functions can be directly implemented by a single AOI gate. The AOI gate performs quite favorably, in terms of digital logic synthesis. Unlike MV, this gate is efficiently used by existing logic-synthesis tools. Our experimental data on synthesis of complex designs show that using the AOI gate instead of MV, results in up to 23.9% logic area savings, while improving the overall delay.

A new application-independent approach for evaluating the fault tolerance of field-programmable gate-array (FPGA) interconnect structures is presented. Signal routing in the presence of faulty resources at switch block and FPGA levels is analyzed; this problem is directly related to the fault tolerance of FPGA interconnects for testing and reconfiguration at manufacturing and run-time applications. Two criteria are proposed and used as figure-of-merit for evaluating different FPGA interconnect architectures. The proposed approach is based on the number of available paths between pairs of end points and the probability to establish a one-to-one mapping between all input and output end points. A probabilistic approach is also presented to evaluate the fault-tolerant routing of the entire FPGA by connecting switch blocks in chains, as required for testing and to account for the input-output (I/O) pin restrictions of an FPGA chip. All possible interconnect faults for programmable switches and wiring channels are considered in the fault model. The proposed method is applicable to arbitrary switch block structures. Experimental results on commercial as well as academic designed FPGAs are presented and analyzed.

This paper presents a new approach for the evaluation of FPGA routing resources in the presence of faulty switches. This is considered under the worst case scenario of open faults. Signal routing in the presence of faulty switches is analyzed at switch block level; probabilistic routing (routability) is used as figure of merit for evaluating the interconnect resources of FP-GAs. The presented approach utilizes a path-based technique to find the probability of establishing a path between pairs of input and output endpoints in a switch block. The results are reported for various commercial and academic FPGAs.

There has been considerable research on quantum dots cellular automata as a new computing scheme in the nano-scale regimes. The basic logic element of this technology is a majority voter. In this paper, testing of these devices is investigated and compared with conventional CMOS-based designs. A testing technique is presented; it requires only a constant number of test vectors to achieve 100% fault coverage with respect to the fault list of the original design. A design-for-test scheme is also presented which results in the generation of a reduced test set.

Vector reordering is an essential task in testing VLSI systems because it affects this process from two perspectives: power consumption and correlation among data. The former feature is crucial and if not properly controlled during testing, may result in permanent failure of the device-under-test (DUT). The atter feature is a so important because correlation is captured by coding schemes to efficiently compress test data and ease memory requirements of Automatic-Test-Equipment (ATE),while reducing the volume of data and lowering the test application time. Reordering however is NP-complete. This paper presents an evaluation of different heuristic techniques for vector reordering using ISCAS85 and ISCAS89 benchmark circuits in terms of time and quality. For this application, it is shown that the best heuristic technique is not the famous Christofides or Lin-Kernighan, but the Multi-Fragment technique.

Quantum-dot Cellular Automata (QCA) offers a new computing paradigm in nanotechnology. The basic logic elements of this technology are the inverter and the majority voter. In this paper, we propose a novel complex and universal QCA gate: the And-Or-Inverter (AOI) gate, which is a 5 input gate consisting of 7 cells. This paper presents a detailed simulation-based analysis of the AOI gate as well as the characterization of QCA defects and study of their effects at logic level. Design implementations using the AOI gate are compared with the conventional CMOS and the majority voter-based QCA methodology. Testing of the AOI gate at logic level is also addressed, unique testing features of designs based on this complex gate have been investigated.

We give a Markov chain model of the yield of an embedded memory core. The model allows easy inclusion of the effect of possible defects elsewhere on the chip that includes the embedded memory. We propose a reconfiguration algorithm for the case of both spare rows and columns that is simple enough that it could serve as built-in self-repair on the chip. Compared to an optimal configuration algorithm, there is no visible difference in the yield. We use parameters from an IBM embedded SRAM process to illustrate the yield calculation. We study the effect of different spare allocations. We conclude that as long as there is at least one spare of each type, the spares do not need to be balanced, once the yield impact of being part of a system-on-a-chip has been taken into account.

Summary form only given. We present a new approach for the evaluation of FPGA routing resources in the presence of faulty switches. Switch stuck-open faults (switch permanently off) as well as switch stuck-closed faults (switch permanently on) are addressed, which is directly related to fault tolerance of the interconnect for testing and reconfiguration at manufacturing and run-time application. Signal routing in the presence of faulty switches is analyzed at both switch block and array levels; probabilistic routing (mutability) is used as figure of merit for evaluating the programmable interconnect resources of FPGA architectures. Two approaches are proposed in this paper. The first approach is based on finding a permutation (one-to-one mapping) between the input and output endpoints. A probabilistic approach is also presented to evaluate fault tolerant routing for the entire FPGA by connecting switch blocks in chains as required for testing and to account for the I/O pin restrictions of an FPGA chip. The results are reported for various commercial and academic FPGA architectures.

Summary form only given. There has been considerable research on quantum cellular automata (QCA) as a new computing scheme in the nanoscale regimes. A detailed simulation-based characterization of defects in different QCA logic and interconnect devices and study of their effects at logic-level are presented. Various failure mechanisms which can potentially happen during nanomannfacturing of these devices have been considered and simulated. Different implementations of QCA logic devices and interconnects are also compared in term of defect tolerance and testability. The same study is performed for new proposed QCA devices too. The simulation results show that additional fault models at logic level must be considered for testing of QCA-based circuits.

This work presents a new approach for the evaluation of FPGA routing resources in the presence of interconnect faults. All possible interconnect faults for programmable switches and wiring channels are considered. Signal routing in the presence of faulty interconnect resources is analyzed at both switch block and the entire FPGA. Two new probabilistic routing (routability) metrics are proposed and used as figures of merit for evaluating the interconnect resources of commercially available FPGAs as well as academic architectures.

There has been considerable research on quantum dot cellular automata (QCA) as a new computing scheme in the nano-scale regimes. The basic logic element of this technology is majority voter. In this paper, a detailed simulation-based characterization of QCA defects and study of their effects at logic-level are presented. Testing of these devices is investigated and compared with conventional CMOS-based designs. Unique testing features of designs based on this technology are presented and interesting properties have been identified.

We present an approach for fault detection in layered interconnection networks (LINs). An LIN is a generalized multistage interconnection network commonly used in reconfigurable systems; the nets (links) are arranged in sets (referred to as layers) of different size. Switching elements (made of simple switches such as transmission-gate-like devices) are arranged in a cascade to connect pairs of layers. The switching elements of an LIN have the same number of switches, but the switching patterns may not be uniform. A comprehensive fault model for the nets and switches is assumed at physical and behavioral levels. Testing requires configuring the LIN multiple times. Using a graph approach, it is proven that the minimal set of configurations corresponds to the node disjoint path sets. The proposed approach is based on two novel results in the execution of the network flow algorithm to find node disjoint path sets, while retaining optimality in the number of configurations. These objectives are accomplished by finding a feasible flow such that the maximal degree can be iteratively decreased, while guaranteeing the existence of an appropriate circulation. Net adjacencies are also tested for possible bridge faults (shorts). To account for 100 percent fault coverage of bridge faults a postprocessing algorithm may be required; bounds on its complexity are provided. The execution complexity of the proposed approach (inclusive of test vector generation and post-processing) is O(N/sup 4/WL), where N is the total number of nets, W is the number of switches per switching element, and L is the number of layers. Extensive simulation results are provided.

We examine the diagnosis of processor array systems formed as two-dimensional arrays, with boundaries, and either four or eight neighbors for each interior processor. We employ a parallel test schedule. Neighboring processors test each other, and report the results. Our diagnostic objective is to find a fault-free processor or set of processors. The system may then be sequentially diagnosed by repairing those processors tested faulty according to the identified fault-free set, or a job may be run on the identified fault-free processors. We establish an upper bound on the maximum number of faults which can be sustained without invalidating the test results under worst case conditions. We give test schedules and diagnostic algorithms which meet the upper bound as far as the highest order term. We compare these near optimal diagnostic algorithms to alternative algorithms, both new and already in the literature, and against an upper bound ideal case algorithm, which is not necessarily practically realizable. For eight-way array systems with N processors, an ideal algorithm has diagnosability 3N/sup 2/3/-2N/sup 1/2/ plus lower-order terms. No algorithm exists which can exceed this. We give an algorithm which starts with tests on diagonally connected processors, and which achieves approximately this diagnosability. So the given algorithm is optimal to within the two most significant terms of the maximum diagnosability. Similarly, for four-way array systems with N processors, no algorithm can have diagnosability exceeding 3N/sup 2/3//2/sup 1/3/-2N/sup 1/2/ plus lower-order terms. And we give an algorithm which begins with tests arranged in a zigzag pattern, one consisting of pairing nodes for tests in two different directions in two consecutive test stages; this algorithm achieves diagnosability (3/2)(5/2)/sup 1/3/N/sup 2/3/-(5/4)N/sup 1/2/ plus lower-order terms, which is about 0.85 of the upper bound due to an ideal algorithm.

In this paper we are presenting a test methodology for performing module-bused mixed level fault simulation and test generation on System-on-Chip (SOC) combinational Intellectual Property (IP) cores for which both a pre-synthesis behavioral description and a post-synthesis netlist is available but in an analyzer output intermediate format not readable by core integraters. We use the Verilog Procedural Interface (VPI) to access and perform serial fault simulation on a pre-compiled core available as a mixed behavioral structural level design. We also use VPI to prepare a testbench environment for performing random pattern test generation. The simulation time results of applying this VPI-based test methodology on ISCAS85 Verilog benchmarks are also presented and compared to the flat (non-mixed level) version the proposed VPI-based environment.

This paper deals with Hybrid multisite testing of VLSI chips by utilizing automatic test equipment (ATE) in connection with built-in self-test (BIST). The performance of a multisite testing process is analyzed using device-under-test (DUT) parameters (such as yield and average number of faults per DUT) as well as test process features (such as number of channels, coverage and touchdown time for the head). Two scenarios which permit immediate and delayed replacements, are considered and analytical models are given to establish the multisite test time of an ATE. A hybrid BIST and ATE approach is also analyzed to improve the performance of a multisite test environment and to better utilize the channels in the head of the tester. 1.

A highly dependable embedded fault-tolerant memory architecture for high performance massively parallel computing applications and its dependability assurance techniques are proposed and discussed in this paper. The proposed fault tolerant memory provides two distinctive repair mechanisms: the permanent laser redundancy reconfiguration during the wafer probe stage in the factory to enhance its manufacturing yield and the dynamic BIST/BISD/BISR (built-in-self-test-diagnosis-repair)-based reconfiguration of the redundant resources in field to maintain high field reliability. The system reliability which is mainly determined by hardware configuration demanded by software and field reconfiguration/repair utilizing unused processor and memory modules is referred to as HW/SW Co-reliability. Various system configuration options in terms of parallel processing unit size and processor/memory intensity are also introduced and their HW/SW Co-reliability characteristics are discussed. A modeling and assurance technique for HW/SW Co-reliability with emphasis on the dependability assurance techniques based on combinatorial modeling suitable for the proposed memory design is developed and validated by extensive parametric simulations. Thereby, design and Implementation of memory-reliability-optimized and highly reliable fault-tolerant field reconfigurable massively parallel computing systems can be achieved.

We give two algorithms for maximal diagnosis of wiring networks without repair under a general fault model. Maximal diagnosis consists of identifying all diagnosable faults under the assumptions that each net can have multiple drivers and receivers and can be affected by any number of short and open faults. This process is equivalent to verifying all connections between inputs and outputs. Matrices represent the connections in fault-free and faulty networks. We present two new algorithms and discuss prior algorithms. All algorithms discussed are adaptive and have their tests divided into two phases. Our first new algorithm exploits a unique condition for verifying the connections; our second new algorithm maps the connection verification problem to a bipartite graph. All algorithms discussed use an independent test set for the first test phase. Simulation results show that the proposed algorithms outperform previous algorithms for maximal diagnosis in terms of the number of tests. The total time complexity for computing the test sequences and analyzing the output response is polynomial.

This paper presents an approach for the maximal diagnosis of all faults (stuck-at, open and short) in the interconnect of a random access memory (RAM); and the interconnect includes data and address lines. This approach accomplishes maximal diagnosis under a complex model in which the lines in the interconnect of the RAM can be affected by multiple faults. Maximal diagnosis consists of detection and location of all diagnosable faults as well as type identification of multiple faults affecting each line. The proposed algorithm (referred to as the Improved Maximal Diagnosis Algorithm, or IMDA) requires max{n,m-1}+n+3 WRITE and max{n,m}+2n READ, where n is the number of address lines and m is the number of data lines. IMDA executes in three different steps: the first step diagnoses the data lines (and in particular the stuck-at faults); the second step accomplishes maximal diagnosis of the shorts (involving either the data lines only, or the data and address lines); and the third step completes the diagnosis of the address lines.

This paper investigates the co-effect of hardware and software on the reliability as measured by quality level (or defect level) of configurable multichip module (CMCM) systems. Hardware architecture of CMCM can be configured to accommodate target application design. An application, as provided in a form of software, is partitioned and mapped on the provided configurable hardware. Granularity of an application can be used as a criteria of partitioning and mapping, and can determine the utilization pattern of hardware resources. The utilization pattern of CMCM determines the configuration strategy of available hardware resources based on the application's granularity. Different utilization patterns of an application design on CMCM may result in various impacts on escape tolerance (i.e. the probability to avoid inclusion of hardware resources in the configuration that escaped from testing). A quality level model of CMCM is proposed to capture and trace the co-effect of hardware and software, referred to as co-reliability, with respect to escape-tolerance. Various configuration strategies are proposed and evaluated against various criterion granularity and utilization distributions based on the proposed models and evaluation techniques. Extensive analytical and parametric simulation results are shown.

A stratified technique is proposed for testing multichip module systems. Stratification in multichip modules due to the different nature and procurement of these chips is exploited for achieving a high quality-level at a saving of a significant number of tests during assembly. Unlike conventional random testing, the proposed approach (referred to as the lowest yield-stratum first-testing), takes into account the uneven known-good-yield. In the lowest yield-stratum first-testing approach, the effect of the uneven known-good-yield between strata is analyzed with respect to the variance of known-good-yield and the sample size. The lowest yield-stratum first-testing approach significantly outperforms conventional random testing and random stratified testing. This method is competitive even compared to a conventional exhaustive testing at a very small loss in quality-level by greedy (first) testing the chips in the stratum with lower known-good-yield. A Markov-chain model is developed to analyze these testing approaches under the assumption of physically independent failure of chips in multichip module systems.

In a multiprocessor under normal loading conditions, idle processors offer a natural spare capacity. Previous work attempted to utilize this redundancy to overcome the limitations of classic diagnosability and modular redundancy techniques while providing significant fault tolerance. A common approach is task duplexing. The usefulness of this approach for critical applications, unfortunately, is seriously undermined by its susceptibility to agreement on faulty outcomes (malicious agreement). To assess dependability of duplexing under malicious agreement, we propose a stochastic model which dynamically profiles behavior in the presence of malicious faults. The model uses the so-called policy referred to as NMR on demand (NMROD). Each task in a multiprocessor is duplicated, with additional processors allocated for recovery as needed. NMROD relies on a fault model favoring response correctness over actual fault status, and integrates online repair to provide non-stop operation over an extended period.

This paper presents a new model for analyzing the yield of MCM systems with repair process. It exploits the connectivity of the interconnected chips in which yield degradation due to both neighboring chips and interconnect structure are taken into account. Based on the connectivity, two MCM repair scheduling strategies, Smallest Number of Interconnections First (SNIF) and Smallest Number of Neighboring Chips First (SNCF) are proposed Two other scheduling strategies, Largest Number of Interconnections First (LNIF) and Largest Number of Neighboring Chips First (LNCF) are also introduced and analyzed to further explore the impact of connectivity-based repair scheduling on the overall yield of MCMs. Extensive parametric simulations demonstrate the efficiency of the proposed MCM repair scheduling strategies.

In a multiprocessor under normal loading conditions, idle processors naturally offer spare capacity. Previous work attempted to utilize this redundancy to overcome the limitations of classic diagnosability and modular redundancy techniques while providing significant fault tolerance. A popular approach is task duplexing. The usefulness of this approach for critical applications, unfortunately, is seriously undermined by its susceptibility to agreement on faulty outcomes (malicious agreement). To assess the dependability of duplexing under malicious agreement, we propose a stochastic model which dynamically profiles behavior in the presence of malicious faults. The model uses a more or less typical policy we call NMR on demand (NMROD). Each task in a multiprocessor is duplicated, with additional processors allocated for recovery as needed. NMROD relies on a fault model favoring response correctness over actual fault status, and integrates online repair to provide nonstop operation over an extended period.

1 Appeared in IEEE Transactions on Computers, Introduction to the special issue devoted to “Advances in High Performance Memory Systems,” November 2001. While microprocessor designs have continued to increase in speed and complexity, dynamic random access memories (DRAMs) have failed to keep pace. This trend has created a widening gap in performance between microprocessors and their supporting memory systems. While hierarchical memories (i.e., caches) have been used to bridge this gap in the past, the distance (in terms of cycles) between caches and DRAMs continues to grow. Our inability to design memory systems that can keep pace has warranted us to look for new approaches bridging the memory wall.

Presents an approach for fault detection in programmable wiring networks (PWNs). A comprehensive fault model which includes faults in the nets (open, stuck-at and shorts) as well as in the switches (stuck-off, stuck-on and programming faults) is assumed at both the physical and behavioral levels. In a PWN, the most important issue is to find the minimal number of configurations (or programming phases) as the dominant figure of merit of testing. Through the construction of different graphs, it is shown that this process corresponds to finding the node-disjoint path-sets such that each switch is turned on/off at least once and adjacencies in the nets for possible bridge faults (shorts) are verified. To account for 100% fault coverage of bridge faults, a post-processing algorithm may be required.

This paper deals with testing of inter-port faults in multi-port static random access memories (SRAMs). An inter-port fault is caused by a short between word/bit lines of different ports in a multi-port SRAM. By considering different implementations of the SRAM and its layout, an approach with achieves 100% coverage of fault detection, is proposed. The two-step approach is based on two novel algorithms: MMCA (Modified March C Algorithm) and WIPD (Write Inter-Port Detection). It is shown that inter-port fault detection is a combinatorial problem; hence, MMCA and WIPD must be executed a multiple number of times depending on the types, number of ports and line arrangement in the layout.

An approach is proposed to test FPGA logic blocks, including part of the configuration memories used to control them. The proposed AND tree and OR tree-based testing structure is simple and the conditions for constant testability can easily be satisfied. Test generation for only a single logic block is sufficient. We do not assume any particular fault model. Any number of faulty blocks in the chip can be detected. Members of the Xilinx XC3000, XC4000, and XC5200 families were studied. The proposed AND/OR approach was found to reduce the number of FPGA reprogrammings needed for testing by up to a factor of seven versus direct methods of multiple faulty block detection.

This paper presents an extensive model and algorithms for detecting faults in SRAM-based dual-port and uni-port CAMs (Content Addressable Memories). This model is based on analyzing the functionalities of a cell of an SRAM-based CAM and dividing it into two parts (storage and comparison parts). It is shown that faults can affect one or both parts. While storage faults can be detected using a traditional test algorithm (such as the March C), faults affecting the comparison part of the cell require a substantially different approach. A complete characterization of these faults is presented; by analyzing the structure of the cell in the dual and uni-port configurations, physical faults (such as stuck-at, stuck-open, stuck-on, bridge) in lines and transistors can be mapped to three functional fault sets by the execution of the comparison operation. Two new detection algorithms (directly compatible with the world-oriented March C algorithm, as widely used in existing commercial tools) are proposed; 100 percent coverage is achieved. The first algorithm (Concurrent Detection Algorithm or CDA) employs concurrent operations for testing a dual-port CAM; the second algorithm (Non Concurrent Detection Algorithm or NCDA) uses nonconcurrent operations and can be used for testing dual-port as well as uni-port CAMs. CDA requires eight passes and (10N+2L) tests, where N is the number of words of the CAM and L is the width of a word. NCDA requires eight passes, too, but (12N+2L) tests. The number of tests required by CDA (and NCDA, too) is significantly less than required by existing algorithms.

This paper presents a method to diagnose faults in FPGA interconnection resources. A single fault model is given. Under the given model, a diagnosing method is proposed. At most five programming steps in the proposed method is required if adaptive testing scheme is used. For non-adaptive test, eight programming steps is required to diagnose all the possible faults under the given single fault model. The accuracy of the fault diagnosing is one segment for a segment stuck-at or stuck-open fault, a segment pair for a bridge fault, a switch for switch stuck-on or stuck-off fault.

In this paper, a novel architecture for built-in self test (BIST) and different designs for both the control and data test pattern generators (CTPG and DTPG) are proposed for interconnect testing using the IEEE standard 1149.1. A general and complete procedure to implement this architecture is also presented. For the DTPG design, the complementary counting sequence (as an example of a maximal independent test set) is used for fault detection. One of the main features of this design is its independence with respect to the type of cell in the chain. A novel design is proposed for the CTPG to avoid damage to the circuit as well as to guarantee 100% fault coverage with low hardware overhead and time complexity.

This paper presents a procedure to diagnose single faults in SRAM based FPGAs. The procedure is nonadaptive and requires six programming steps to give the exact position and type of any single fault in a FPGA. It is proved that the number of programming steps required for the procedure is minimal for a non-adaptive procedure with the given interconnect model.

This paper presents a quiescent current-based (I/sub DDQ/) approach for testing input/output resources in SRAR-based FPGAs. Input/output resources include input/output blocks (IOBs) and the I/O interconnect. Test generation and application strategies are proposed by taking into account the limited controllability of the I/O resources. Configuration of these resources requires that the test stimuli must be provided by internal (logic and routing) resources. A detailed presentation for testing the I/O resources of the Xilinx XC4000 family is given.

This paper presents a novel fault tolerant approach for SRAM-based FPGAs. The proposed approach includes a fault tolerant architecture and its related routing procedure. In the approach, both the overheads for CLBs and interconnects are considered. The fault tolerant routing procedure under this novel approach is simple and less time-consuming. We provide the simulation results and show that the proposed approach has lower overhead than previous methods found in technical literature.

This paper presents an approach for the maximal diagnosis of all faults (stuck-at, open and short) in the interconnect of a random access memory (RAM); the interconnect includes data and address lines. This approach accomplishes maximal diagnosis under a complex model in which the lines in the interconnect of the RAM are involved in multiple faults simultaneously. The proposed algorithm (referred to as the Improved Maximal Diagnosis Algorithm, or IMDA) requires max{n,m-I}+n+3 WRITE and max{n,m}+2n READ, where n is the number of address lines and m is the number of data lines.

This paper presents a new approach to detecting faults in interconnects; the novelty of the proposed approach is that test generation and scheduling are established using the physical characteristics of the layout of the interconnect under test. This includes critical area extraction and a realistic fault model for a structural methodology. Physical layout information is used to model the adjacencies in an interconnect and possible bridge faults with a weighted graph, which is then analyzed to appropriately compact the tests and schedule their execution for (early) detection of bridge faults. Generation and compaction of the test vectors are accomplished by calculating node and edge weight heuristics from the weighted adjacency graph. Simulation has been performed for unweighted and weighted fault models. Results on random interconnects and the local interconnect of a commercially available field-programmable gate array are provided. The advantage of the proposed approach is that, on average, early detection of faults is possible using significantly fewer tests than with previous approaches. A further advantage is that it represents a realistic alternative to adaptive testing because it avoids costly on-line test generation, while still having a small number of vectors.

We present a novel approach for detecting faults in tristate system environments-e.g., in multiple board systems. These environments are made of an interconnect and drivers/receivers with tristate features. We present a comprehensive fault model that includes faults in terminals (drivers/receivers) and nets. Under this fault model, physical faults (stuck-at and short), as well as functional faults (dominance, permanently enabled or permanently disabled driver modes), are taken into account. We show that, for a single net with L drivers, 2L tests are necessary and sufficient for fault detection. This is independent of the number of receivers. We extend this result to a system environment with N nets and where K is the maximal number of drivers for a net. Under the proposed fault model, any number of faults of any type can be detected in a system environment using any types that can be detected in a system environment using max (2K, P) tests, where P is the minimal integer that satisfies C/sub /2//sup P//spl ges/N. If only the traditional (wired-AND or wired-OR) model is assumed, then the test set required for fault detection can be further reduced. We provide simulation results and show that the proposed approach outperforms previous methods found in the technical literature.

This paper presents a five-step programming method to diagnose faults in FPGA interconnection resources. A single and a multiple fault model are given. The accuracy of fault location is a single segment for a segment stuck-at fault or a segment open fault, a segment pair or terminal pair for bridge fault or switch stuck-off fault under the single fault assumption. Similar accuracy can be achieved under the multiple fault assumption.

This paper presents a vector generation approach for testing interconnects in configurable (SRAM-based) Field Programmable Gate Arrays (FPGAs). The proposed approach detects bridging faults and is based on quiescent current (IDDQ monitoring. Compared with previous voltage-based methods, IDDQ testing has the advantage of utilizing a small number of programming phases for configuring the FPGA during the test process with negligible observability requirements, even under multiple faults. Algorithms for test generation which exploit the homogeneous nature of the FPGA array, are described. An example using the XC4000 is described in detail. For testing the XC4000 series interconnect, a total of 20 phases and 11 vectors are required: 11 phases for S (switch) block testing, and 9 phases for C (connection) block testing.

This paper presents an I/sub DDQ/-based test strategy for detecting bridging faults in the logic resources of reprogrammable field programmable gate arrays (FPGAs). The approach utilizes the programmability of the configurable logic blocks (CLBs) to achieve 100% coverage of I/sub DDQ/-testable bridging faults. Since reconfiguration programming time can dominate total test time, even with slow I/sub DDQ/ vectors, we use a bottom-up test generation approach to minimize the number of programming phases first, and then to minimize the number of test vectors. 100% coverage for I/sub DDQ/-testable bridging faults is achieved in 5 programming phases and 16 I/sub DDQ/ vectors in the Xilinx XC4000 FPGA family. The RAM modes are tested in a further phase, using 48 test vectors and 38 I/sub DDQ/ measurements.

This paper presents two new approaches for testing interconnects of random access memories (RAM). Tire first algorithm is referred to as the Adaptive Diagnosis Algorithm (ADA), while the second algorithm is referred to as the Consecutive Diagnosis Algorithm (CDA). Initially, it is shown that the diagnosis of the address lines is the most difficult step in interconnect testing of memories as the diagnosis of faults in data lines can be resolved easily. The execution of ADA is such that the diagnosis of the address lines is performed sequentially (i.e. on a line by line basis), while enforcing the conditions by which it is possible to differentiate for each line a stuck-at fault from a short. This is determined by the operations as for diagnosis a short requires an additional READ compared with a suck-at fault. A different condition in the generation of the overall sequence is utilized in CDA; by using different test patterns for the address lines, a relation can be assessed between consecutive READ operations.

This paper presents an I/sub DDQ/-based test strategy for detecting bridging faults in the logic resources of reprogrammable field programmable gate arrays (FPGAs). The proposed approach utilizes the programmability of the configurable logic blocks (CLBs) to achieve 100 percent coverage of I/sub DDQ/ testable bridging faults. We use a hierarchical approach for generating tests and configurations. At the chip level, the CLBs are viewed as a homogeneous two-dimensional array. Two configuration strategies are suggested to simultaneously test each CLB. Within each CLB, we test for external bridging faults between the combinational and sequential logic modules (e.g., flip-flops, multiplexers, lookup tables), Finally, we test for internal bridging faults within each module based on their implementation. Since reconfiguration programming time dominates total test time, even with slow I/sub DDQ/ vectors, we use a bottom-up test generation approach to minimize the number of programming phases first and, then, to minimize the number of test vectors. The Xilinx XC4000 family of SRAM-based FPGAs is used as an example application of the proposed approach. One hundred percent coverage for I/sub DDQ/-testable bridging faults is achieved in five programming phases and 16 I/sub DDQ/ vectors. Since the lookup tables in the CLB can be configured as RAM, the RAM modes are also tested. This requires a further phase, using 48 test vectors and 38 I/sub DDQ/ measurements.

This paper presents a new approach for diagnosing shorts in interconnects in which the adjacencies between nets are known. This structural approach exploits different graph coloring techniques to generate a test set with no aliasing and confounding, i.e., full diagnosis (detection and location) is accomplished. Initially, a simple coloring approach based on a greedy condition of the adjacency graph is proposed for fault detection. Then, the conditions for aliasing and confounding are analyzed with respect to the sizes of the possible shorts. These results are used to generate new colors using a process called color mixing. Color mixing guarantees that additional tests, required in order to avoid aliasing/confounding, will use appropriate codes. The characteristics of unbalanced/balanced codes for encoding the colors in the vector-generation process of interconnect diagnosis are discussed and are proved to yield full diagnosis using a novel method. An algorithm for full diagnosis is then presented; this algorithm has an execution complexity of O ( max { N 2 , N × D 3 }) where N is the number of nets and D is the maximum degree of the nodes in the adjacency graph. Simulation results show that the proposed approach requires a smaller number of test vectors than previous approaches.

We present a new technique for testing field programmable gate arrays (FPGA's) based on look-up tables (LUT's). We consider a generalized structure for the basic FPGA logic element (cell); it includes devices such as LUT's, sequential elements (flip-flops), multiplexers and control circuitry. We use a hybrid fault model for these devices. The model is based on a physical as well as a behavioral characterization. This permits detection of all single faults (either stuck-at or functional) and some multiple faults using repeated FPGA reprogramming. We show that different arrangements of disjoint one-dimensional (l-D) cell arrays with cascaded horizontal connections and common vertical input lines provide a good logic testing regimen. The testing time is independent of the number of cells in the array (C-testability), We define new conditions for C-testability of programmable/reconfigurable arrays. These conditions do not suffer from limited I/O pins. Cell configuration affects the controllability/observability of the iterative array. We apply the approach to various Xilinx FPGA families and compare it to prior work.

This paper presents a novel approach for testing and diagnosing configurable field programmable gate arrays (FPGAs). The proposed approach is row-based and uses a two-session procedure. The approach arranges some logic blocks to be programmed as XOR-tree (or chain, or cascade) in the first session. The XOR-tree is effectively used as test vehicle for observability. The roles of the CLBs are inverted in the second session. It is shown that the proposed testing arrangement requires a number of tests independent of the number of CLBs in the FPGA (i.e. C-testability is accomplished). Routing is kept local, and compatibility for a CAD implementation is also accomplished.

This paper presents an efficient algorithm for multi-way balanced partitioning of VLSI circuits. The proposed algorithm is still based on the widely used net-cut model, but its novelty is the potential gain function into the net-cut cost function to relax the single-cell-move constraint (as commonly encountered in the Kernighan-Lin algorithm) for balanced partitioning. This feature permits to move a group of cells (referred to as a Multi-Cell-Move strategy) for partitioning a circuit, while reducing its sensitivity to size constraint. The new multi-way partitioning algorithm is fully analyzed; expressions for the potential gain function (with respect to the multi-move operation) and the cost (for the min-cut objective function) are presented. The time complexity of the proposed partitioning algorithm is O(P/spl times/k/sup 2/ log/sub 2/ (k)), where k is the number of blocks and P is the number of pins. Simulation results are presented and a remarkable improvement is achieved compared with existing algorithms, such as the k-Dual Part algorithm.

This paper presents new results for diagnosing (detection and location) multistage interconnection networks (MINs) in the presence of multiple faults. Initially, it is proved that the lower bound in the number of tests for multiple fault diagnosis (independent of the assumed fault model for the MIN) is 2/spl times/log/sub 2/N, where N is the number of inputs/outputs of the network. A new fault model is introduced; this fault model is applicable to interconnection networks implemented using CMOS technology. The characterization for diagnosing stuck-open faults is presented.

This paper deals with the inverse problem (namely, diagnosability) for diagnosing bridge faults in interconnects. Given a test set (T) and the layout of an interconnect, the diagnosability problem consists of establishing the probability (coverage) of diagnosing (detection and/or location) all faults and to identify the undiagnosable faults (if any). It is proved that this process is equivalent of checking each edge in the adjacency graph representation of the layout using the tests in T (either parallel, or sequential test vectors). Different algorithms are given for diagnosis and detection.

No abstract available.

This paper presents a new approach for diagnosing stuck-at and short faults in interconnects whose layouts are known. This structural approach exploits different graph coloring and coding techniques to generate a test set with no aliasing and confounding. The conditions for aliasing and confounding are analyzed with respect to the size and number of the shorts in the fault set. The characteristics of unbalanced/balanced codes for encoding the colors in the vector generation process for interconnect diagnosis are discussed and proved using a novel algebra. An algorithm for diagnosis is then presented.

This paper presents new algorithms for yield enhancement of redundant memories. These algorithms are based on the technique of spare cutting for a redundant memory chip in which repair is implemented by row/column deletion. Different approaches are proposed: some of these approaches are based on a fully exhaustive process, while others try to heuristically reduce the computational overhead involved in determining the repair-solution.

This paper presents an approach for verifying and validating time-dependent protocols, i.e. protocols for which the time spent for the functions is critical to a successful execution. The proposed approach is a novel modification of the traditional Unique Input/Output (UIO) method by explicitly taking into account the time specification of each edge in a protocol modeled as a finite state machine (FSM). A new FSM model which characterizes the timing properties of the protocol, is proposed. An algorithm which generates a test sequence with minimal traversal time for a time-dependent protocol in polynomial time complexity, is proposed.

This paper considers the diagnosis of field programmable interconnect systems (FPIS) in which programmable grids made of switches are included. For this type of interconnects, the number of times the grid must be programmed and the programming sequence of the switches an two of the most important figures of merit for full diagnosis (defection and location with no aliasing and confounding). A hierarchical approach to diagnosis is proposed and fully characterized. The application of this technique to commercially available FPIS such as FPGAs, is discussed. It is shown that the proposed diagnostic technique can be applied to the general purpose interconnect of the FPGAs in the 3000 family by Xilinx.

This paper presents a new general technique for testing field programmable gate arrays (FPGAs) by fully exploiting their programmable and configurable characteristics. A hybrid fault model is introduced based on a physical and behavioral characterization; this permits the detection of a single fault, as either a stuck-at or a functional fault. A general approach which regards testing as can application for the reconfigurable FPGA, is then proposed. It is shown that different arrangements of disjoint one-dimensional arrays with unilateral horizontal connections and common vertical input lines provide a very good solution. A further feature that is considered for array testing, is the relation between the configuration of the logic blocks and the number of I/O pins in the chip. As an example, the proposed approach is applied for testing the Xilinz 4000 family of FPGAs.

This paper presents new results and graph algorithms for the automatic testing of protocols using “unique input/output” (UIO) sequences. UIO sequences can be efficiently employed in checking conformance of protocols to their specifications by using transition testing. The optimization of the test sequence is based on finding the rural Chinese postman tour, of the state transition diagram of a finite state machine (FSM). The process of conformance test generation using a touring algorithm is valid provided that certain connectivity properties of the graph are present. This implies that a weakly connected graph must be constructed. It is possible that this connectivity condition may not be met when multiple UIO sequences are used even if the reset capability and/or the self-loop properties are present. The “weakly connected graph problem” consists of finding an edge-induced subgraph of the FSM which is still weakly connected when multiple UIO sequences are used. The “multiple UIO tour minimization problem” addresses the assignment of edges to UIO sequences for minimizing the degree of the directed UIO graph. This process may not also minimize the length of the tour. The above two problems, left open in previous papers, are solved in this paper. It is proved that by appropriately changing the original assignment graph and using network flow techniques with a new UIO generation process referred to as chaining, efficient solutions can be provided. The theoretical approaches behind the solution to these problems are fully characterized.

System-level diagnosis is an important technique for fault detection and location in multiprocessor computing systems. Efficient diagnosis is highly desirable for sustaining the original system power. Moreover, effective diagnosis is particularly important for a multiprocessor system with high scalability but low connectivity. Most of the existing results are not applicable in practice because of the high diagnosis cost and limited diagnosability. Over-d fault diagnosis, where d is the diagnosability, has only been addressed using a probabilistic method in the literature. Aiming at these two issues, we propose a hierarchical adaptive system-level diagnosis approach for hypercube systems using a divide-and-conquer strategy. We first propose a conceptual algorithm HADA to formulate a rigorous analysis. Then we present its practical variant IHADA. In HADA and IHADA, the over-d fault problem is inherently tackled through a deterministic method. Three measures for diagnosis cost (diagnosis time, number of tests, and number of test links) are analyzed for the proposed algorithms. It is proved that the diagnosis cost required by our approach is lower than in previous diagnosis algorithms. It is shown that the diagnosis cost for the proposed algorithms depends on the number and location of faulty units in the system and the cost is extremely low when only a small number of faulty units exist. It is also shown that our algorithms are characterized by lower costs than a pessimistic diagnosis algorithm which trades lower diagnosis cost for a lower degree of accuracy. Experimental results on the nCUBE are provided.

This paper presents a new structural approach for test generation and diagnosis of interconnects (such as wiring networks). The proposed technique is based on computational geometry by considering the physical adjacencies of the nets in the layout. This information is used by a sweeping line technique for generating the test vectors. A realistic fault model in which nets can be bridged only if they are physically adjacent, is proposed. The proposed approach generates a set of initial local vectors for testing all the nets at the inputs. A different set of local vectors is then, generated by sweeping the layout at every point where two nets may intersect. The set of local vectors is generally sparse. So, a compaction algorithm is proposed for generating the final set. The proposed approach has an execution time of O((p+k) log p) for generating the local tests, where p is the maximum number of segments in the nets and k is the number of possible intersection points. It is proved that the problem of generating the minimum number of test vectors by compaction is NP-complete, but simulation results show that the proposed heuristic criteria are very efficient for a practical application. The extension of the proposed approach to other fault models and to other routing schemes (as applicable to PCB and VLSI) is presented.

This paper presents a methodology for production-time testing of (uncustomized) segmented channel field programmable gate arrays (FPGAs) such as those manufactured by Actel. The principles of this methodology are based on configuring the uncommitted modules (made of sequential and combinational logic circuits) of the FPGA as a set of disjoint one-dimensional arrays similar to iterative logic arrays (ILAs). These arrays can then be tested by establishing appropriate conditions such as constant testability (C-testability). A design approach is proposed. This approach is based on adding a small circuitry (consisting of two transistors) between each pair of uncustomized modules in a row for establishing the ILA configuration as a one-dimensional unilateral array. It also requires the addition of a further primary pin. Features such as number of test vectors and hardware requirements (measured by the number of additional transistors and primary input/output pins) are analyzed; it is shown that the proposed design approach requires a considerably smaller number of test vectors (a reduction of more than two orders of magnitude) and hardware overhead for the testing circuitry (a reduction of 13.6%) than the original FPGA configuration of [1]. The proposed approach requires 8+2nf vectors for testing the uncommitted FPGA of [1], where nf is the number of flip-flops (equal to the number of sequential modules for the FPGA of [1]) in a row of the FPGA.

This paper presents a generalized new approach for testing interconnects (for boundary scan architectures) as well as field programmable interconnect chips (FPICs). The proposed structural test method explicitly avoids aliasing and confounding and as applicable to dense as well as sparse layouts. The proposed method is applicable to both one-step and two-step test generation and diagnosis. Two algorithms with an execution complexity of O(n/sup 2/), where n is the number of nets in the interconnect, are given. Simulation results for benchmark and randomly generated layouts show a substantial reduction in the number of tests using the proposed approaches compared with previous approaches. The applicability of the proposed approach to FPICs is discussed and evaluated by simulation.

This paper presents a new approach for rank order filtering on a MasPar array architecture in the presence of faulty processors. This approach is based on offseting the loss of one or more faulty processors (due to either faults, or defects in the manufacturing process) using the available computational capacity of the neighbor fault-free processors. A parallel algorithm which is applicable to this fault-tolerant procedure, is proposed with a time complexity ofO(N), where N is the dimension of the array.

This paper presents a new approach for finding the Unique Input/Output (UIO) sequences of the states in of a finite state machine (FSM). The proposed approach utilizes a different data structure for organizing the search tree. This reduces the amount of time and memory space required for finding the UIO sequences of all states of a FSM. Simulation results on sample benchmark FSMs from MCNC and commercially available protocols are provided.>

Traditional adaptive centralized system diagnosis assumes a fully connected network topology, hence it can not be used in a number of classes of multiprocessor systems, such as meshes. This paper proposes an adaptive system-level diagnosis algorithm for meshes with wraparound, such as Intel Paragon machine. It is proved that the diagnosis cost required by the proposed approach is lower than the known diagnosis algorithms which can be applied to mesh architectures. Also over-d fault problem can be efficiently solved by our method, where d is the diagnosability.

This paper examines a fault tolerant scheme for two-dimensional arrays of processors which functionally reconfigures the array without the use of spares. Reconfiguration approaches for different interconnection networks are analyzed. Also, three approaches are proposed for mapping image data to and from the array, depending on the type of array and computational power available in each processing element. The proposed reconfiguration approaches have been emulated on a 32x64 processor MasPar array computer.

Presents a new approach for design-for-testability (DFT) of sequential circuits. The proposed approach is based on augmenting the system under test (SUT) with additional circuitry such that the combinational part of the SUT and the sequential part (i.e. the flip-flops) can be tested independently (disjoint testing).>

The reconfiguration of multipipeline arrays in the presence of both faulty processing elements (PEs) and switching elements (SEs) is addressed. Different fault models are used for the PEs and SEs: a PE can be either fault free or faulty; a SE is modeled using a novel functional approach which relates its switching capabilities to its status. This permits a PE to retain a partial functionality in the presence of a fault. An appropriate transformation of the multipipeline array reconfiguration problem to a maximum flow problem is then presented. The conditions under which this transformation is possible, are fully analyzed. A reconfiguration algorithm based on the maximum flow algorithm is presented; the proposed algorithm is optimal as the number of reconfigured pipelines is maximized.>

Various new classes of unique input/output (UIO) sequences for verification and validation (conformance testing) of protocols modeled as finite state machines (FSMs) are presented. The proposed sequences are referred to as adaptive because test sequence generation is not a mere concatenation of test subsequences for all edges of the FSM, but rather subsequences are concatenated using appropriate conditions in the UIO sequence for length minimization and no degradation of fault coverage.>

Presents an approach for the detection of multiple stuck-open (SOP) and stuck-on (SON) faults in CMOS combinational logic circuits. It is proved that multiple SON and SOP faults do not mask each other. This is achieved using a behavioral analysis in which the maskable fault patterns are proved to be impossible. New testing approaches are proposed. Testing is implemented using a combination of two-pattern test sequences as well as universal test sets, as proposed in previous papers by different authors.>

An algorithm for fault diagnosis (detection and location) of baseline interconnection networks in the presence of multiple faults is presented. This algorithm requires 2(1+log/sub 2/ N) tests, where log/sub 2/ N is the number of stages. Multiple fault diagnosis is possible provided: (a) there exists no logically erroneous and unidentified outputs in each faulty switching element and (b) multiple link faults (of the type stuck-at-0 stuck-at-1) do not exist in the network. Fault location is accomplished using an iterative process which checks each stage of the multistage interconnection network. A new functional description of the network is introduced to facilitate fault location.>

The fault coverage of testing protocols using unique input/output (UIO) sequences is analyzed. UIO sequences can be efficiently employed in checking the conformance specifications of protocols by using transition testing. The test sequence is found using the rural Chinese postman tour algorithm. A comprehensive fault model is developed, and analytical expressions are given for the fault coverage. The conditions for undetectability are analyzed, and a new algorithm is proposed. Simulation results and illustrative examples are presented. Overhead issues are discussed, and significant improvements are shown for achieving 100% fault coverage. The major advantage of the proposed approach is that it provides the theoretical basis for fault coverage evaluation of protocol testing using UIO sequences.>

Automatic generation of conformance test sequences for communication protocols by means of unique input/output (UIO) sequences is addressed. It is shown that if multiple minimum-length UIO sequences are computed for each state of the finite-state-machine (FSM) specification, then the length of the resulting test sequence is significantly reduced without an appreciable increase in the time needed to compute the sequence. An algorithm for assignment of the multiple UIO sequences is given. This algorithm, which is based on network flow, is polynomial in the number of states and transitions of the FSM and is effective in reducing the overall length of the test sequence.>

A novel approach is analyzed for reconfiguring multipipeline arrays from two-dimensional arrays. The proposed approach is fully characterized and the conditions for switching and routing are given. A polynomial time complexity algorithm is proposed for the reconfiguration of multipipeline arrays. It is proved that 100% harvesting is possible using the proposed algorithm while achieving very small intercell and pipeline delays.>

A novel approach for the diagnosis of baseline interconnection networks with a fan-in/fan-out of 2 is presented. The totally exhaustive combinatorial fault model with single fault assumption is used in the analysis. Some new characteristics of baseline interconnection networks are proved. A characterization for the fault location and the fault type of the one-response fault are given. This characterization is used in proving that baseline interconnection networks with fan-in/fan-out of 2 can be diagnosed with a constant number of tests independent of the network size. The maximum number of tests is 12.>

An extension of a previous approach to fault detection and C-testability of orthogonal iterative arrays is presented. The state transition table of a basic cell is analyzed. Five new states are added to it. It is proved that even though the number of additional states in the proposed approach is greater than previous approaches, (five states compared to four), the required number of test vectors is considerably reduced (by a factor of approximately 4/9). An approach to implement the proposed C-testability approach into logic design is also presented. Complexity of this implementation is analyzed.>

Two approaches for the repair of large random access memory (RAM) devices in which redundant rows and columns are added as spares are presented. These devices, referred to as redundant RAMs, are repaired to achieve acceptable yield at manufacturing and production times. The first approach, the faulty line covering technique, is a refinement of the fault-driven approach. This approach finds the optimal repair solution within a smaller number of iterations than the fault-driven algorithm. The second approach exploits a heuristic criterion in the generation of the repair solution. This heuristic criterion permits a fast repair. The criterion is based on the calculation of efficient coefficients for the rows and columns of the memory. Simulation results are presented. Comparison of the proposed heuristic approaches with the fully exhaustive approach shows that repair can be accomplished in most cases. A considerable reduction in processing and complexity (number of records generated in the repair process for finding the optimal repair solution) is accomplished.>

R. Morris (see IEEE Trans. Comput., vol.TC-20, p.1578-9, 1971), suggested adding an extra field to the fixed floating point system, so that exponents can be stored more efficiently. The exponents are stored in the smallest possible space, passing the extra bits to the mantissa. The extra field is used to monitor the current length of the exponent. The gain in precision and/or exponent range outweighs the overhead of the extra field and the processing speed. The authors provide implementation details, error analysis, and some future research ideas. Simulation results are provided for comparison purposes.>

A testable structure is presented for programmable logic arrays (PLAs) which is amenable to production testing. A low overhead structure is proposed to keep the kill area at the lowest value. This is achieved by using a single additional input line to the original PLA. Fault detection is based on a specific set of conditions which must be satisfied in the characteristic matrix and structure of the minimized PLA. The characteristics of the vectors in the test set are discussed. A two-phase test is used to supplement the basic test vector if the specified constraint in the minimized PLA structure is not met. Hardware overhead is lower than any other method found in the technical literature.>

The authors present the basic structure of a testable and repairable programmable logic array (PLA) and the design modifications which are required for a full diagnosis and yield enhancement. The testing process is fully analyzed, and the conditions for diagnosis are presented. It is proved that identification in the presence of multiple (crosspoint, stuck-at, and bridging) faults is possible with high coverage. The criteria which permit diagnosis are based on a hierarchical organization of the testing process; significant improvements over previous redundant structures can be achieved. This results in a compact structure with a homogeneous layout which has been evaluated with respect to area overhead for VLSI implementation. Simulation results for benchmark devices are presented. These suggest that an efficient repair of VLSI PLAs for yield enhancement can be achieved.>

In VLSI arrays, redundant cells are added as spares. The proposed approach is applicable as an offline technique at either production time and/or run time. Reconfiguration is implemented by index mapping using a sequence of two operators. A reconfiguration algorithm which utilizes index mapping is proposed. This algorithm uses a new approach to the assignment problem. It is shown that reconfiguration of fault-free cells is equivalent to a covering of faulty cells by spare cells. It is also established that in a two-dimensional array the optimal spare assignment is given by a maximum matching. This translates to a maximum flow. It is shown that a variation of the matching preserves the optimality of the assignment, while reducing the time complexity of the reconfiguration algorithm Characterization theorems for index mapping and simulation results to substantiate the practicality of the approach are presented.>

An approach to array fault tolerance is presented. A parametric tool for reconfigurability detection and reconfiguration of arrays is introduced. The underlying methodology is based on a partitioning algorithm to determine reconfigurability. After reconfiguration a compaction algorithm is used to optimize results. The application of this methodology to fault-stealing-based algorithms has shown good results in terms of the added required redundancy, even for fault distributions that were unreconfigurable when the reconfiguration algorithm was applied alone.>

Two novel approaches are presented in which no spare cells are used. They are based on the full processing utilization of fault-free cells by exploiting the single-product-step of a systolic array. This results in a reconfigured array with no degradation of computational speed. The basic principles of the time-redundancy technique are discussed, with particular emphasis on the selection and allocation processes for finding the reconfiguration-solution in real-time. The first approach is based on a distributed execution of the reconfiguration process. The immediate advantages of this approach are its simplicity of implementation and the fast execution time. The second approach is based on a more complex reconfiguration procedure that accounts for an iterative execution of the first approach. Appropriate conditions for its correct execution are presented.>

This paper deals with a new approach to system-level diagnosis by comparison. This approach is based on temporal criteria for the identification of faulty units in a multiprocessor computer system for fault-tolerant processing. A hybrid fault model is presented. It relates the effects of different types of fault (permanent and transient) to the execution of jobs. Jobs are assigned on a unit-pair basis for fault-tolerant processing. An algorithm is presented to release the result outputs correctly using comparisons. This algorithm employs a scheduling technique referred to as sense of direction in the comparison assignment. A novel source for misdiagnosis, referred to as temporal invalidation, is introduced in the comparison assignment. The algorithm for the job-release process is optimal with respect to the number of comparisons. The analysis is extended to prove that a comparison-based system can yield a higher throughput than a voting arrangement with the same number of units.

This correspondence presents a new testing method for single instruction multiple data (SIMD) VLSI arrays. A new fault model is presented. Faults are defined at the functional level. A systematic test generation procedure is derived. Testing is performed by sequences of instructions. Two criteria are used. The first criterion establishes the external observability and controllability of the instructions. The second criterion uses instruction cardinality as a metric of instruction complexity. An example of the application of the proposed technique to an existing parallel scheme is described.>

An improved version of the C-testability approach for orthogonal iterative arrays presented by H. Elhuni et al. (see ibid., vol.CAD-5, p.573-81, 1986) is described. C-testability is defined by those criteria which characterize the complexity of the testing process as independent of the dimensions of the array and of the erroneous states of the cells. The proposed approach is based on a cellular automata characterization under single faulty assumption. This characterization analyzes the state transition table of a basic cell and adds new states to it. These states are used to reproduce internally to the array the test input and propagate the faulty state to the output pins of a chip. This process is analyzed exhaustively. The characteristics of the additional states are presented. The conditions of C-testability are fully proved. Complexity of the testing process (number of test vectors) is discussed. It is proved that the proposed approach has a lower complexity than that of Elhuni et al.>

A technique for reconfiguring an array of arbitrary rectangular shape from a fixed-size square array is presented. This type of reconfiguration is referred to as functional reconfiguration, as it maps processing functionalities (given by processing) into an array of dimensions different from those of the physical device. Functional reconfiguration is analyzed using index mapping. Locality and interconnection requirements are presented. Examples are given to illustrate the algorithm. It is also proven that the proposed technique achieves a lower intercell delay than previous techniques for certain values of ratio of the dimensions of the reconfigured rectangular array and the original square array.>

In this paper, a new approach to digital testing is presented. This is based on a dynamical modelling technique for the system under test (SUT). The proposed technique consists of an iterative self-test approach, that has been proved to be applicable to analogue fault analysis. A Discrete Component Connection Model (DCCM) is presented as a basis of modelling analysis. The DCCM describes a digital system by using a large-scale dynamic model for a reduction in computation. In this model, difference connection and component equations are simultaneously solved. Fault identification is accomplished by generating a pseudo-system partition of the SUT; a decision process is then executed to validate test results. The decision process is based on a novel Boolean technique for verification of results using a fault bound. This approach is applicable to testing of both sequential and combinatorial logic. Complexity of this testing technique is analysed; a reduction of complexity is accomplished by using covering set theory. Algorithms are presented for both the self-test and the decision processes. The benefits of this approach are computational compatibility to existing complex simulation packages and lower order of complexity of the decision process for single and multiple fault detection and location. Illustrative examples are presented.

This paper describes a set of novel conditions that can be integrated in a computer-aided-testing (CAT) package for repair of redundant RAM's. A new approach is proposed; the innovative feature of this approach is the independence of analysis on the distribution of faulty bits in memory. This results in better exploitation of redundancy and efficient adaptability of this technique to various testing methods, such as the ones that employ region totalizers and fault counters. Algorithms that provide repair solution and earliest detection of unrepairability of a device are presented. The benefits that result by using this approach include a reduction in repair time. Conditions of unrepairability are given as a function of the number of spare resources (columns and rows) in the redundant memory; significant improvement over existing techniques is accomplished. Simulation results are provided to substantiate the validity of the proposed theory.