In this article, a novel hierarchical deep neural network (DNN) is introduced that augments an input DNN to significantly enhance its image classification accuracy while reducing the inference time and the hardware overhead. The architecture comprises a hybrid framework that combines binary classifiers based on Convolutional Neural Networks (CNNs) with refined classifiers employing Vision Transformers (ViTs). A distinctive training approach is employed, where embedded models are designed and trained based on image distributions processed by binary classifiers, enhancing the system’s precision and efficiency. An algorithm determines the optimal inclusion of components within a cascading structure, enabling the construction, training, and deployment of specialized deep-learning networks. Additionally, two algorithms are introduced to optimize the architecture for multi-GPU systems. Extensive experimentation across multiple baseline DNNs, including both CNNs and ViTs, and diverse datasets demonstrates the versatility and superiority of our proposed structure over traditional methods, with particularly strong improvements observed on larger and more complex datasets such as ImageNet.

A novel IC monitoring approach is proposed that uses deep learning to identify delayed events when non-robust tests are applied. A sensor captures events during the clock period, and the collected data are fed into the deep learning model. The deep learning model is trained with the collected data from manufacturing tests for delay defects. Experimental results with ISCAS’85, ISCAS’89, and ITC’99 benchmark circuits, considering process variations, demonstrate the accuracy and scalability of the proposed method.

False Data Injection Attacks (FDIAs) that target the state estimation pose an immense threat to the security of power grids. Deep Neural Network (DNN)-based methods have shown promising results in detecting such FDIAs. Among the existing state-of-the-art DNN models, time series analysis DNNs have demonstrated superior FDIA detection capability. This article discusses the challenges associated with applying time series analysis DNNs for detecting FDIAs and emphasizes the impact of the attack rate on the detection rate of attacks. We demonstrate that existing time series analysis DNNs are highly vulnerable to FDIAs executed at low attack rates. This article presents various alternative implementations for time series classifiers and time series predictors to improve the FDIA detection rate. A novel method is proposed to train time series classification neural networks to detect FDIAs of any attack rate with high efficiency. Subsequently, an enhanced FDIA detection framework that includes a time series classifier and multiple predictors is presented. Furthermore, an analytical criterion is derived to estimate the FDIA detection rate of time series analysis DNNs under any attack rate. Experimental results obtained on IEEE bus systems using state-of-the-art DNN architectures support the effectiveness of the proposed training method and the proposed framework. The proposed training method significantly improved the detection rate of FDIAs at low attack rates. Up to a 48% improvement in the FDIA detection rate was observed in the proposed framework when compared to the state-of-the-art.

Quantification is the task of estimating the class distribution of a given dataset. This paper presents an Enhanced Distribution Matching method that can directly quantify multiclass datasets. Our method utilizes inter-class conditional probability distributions for quantification. We also propose a heuristic to speed up the distribution matching to obtain class distributions with a minimum number of iterations. The proposed methods were tested with 14 binary and multiclass datasets. The proposed method outperformed 12 datasets by a minimum 26% Mean Absolute Error (MAE) reduction.

Convolutional neural networks (CNNs) have achieved state-of-the-art performance in image classification tasks. However, they may underperform for specific classes, resulting in misclassifications. To address this issue, the proposed method involves two steps that use the Mann-Whitney U test on generated image distributions. The method is evaluated on the publicly available dataset CIFAR100, utilizing ResNet-50 as the baseline network. The results show that the proposed method is effective in significantly improving the classification accuracy of low-accuracy image classes while preserving the high-accuracy classes.

An unforeseen change in the input data is called drift and may impact the accuracy of machine-learning models. A novel scheme for diagnosing data drift in the input stream of image classification neural networks is presented. The proposed drift detection and quantization method uses a threshold dictionary for the prediction probabilities of each class in the neural network model. The method is applicable to any drift type in images such as noise, and weather effects, among others. Experimental results on various datasets, drift types, and neural network models show that the proposed method estimates the drift magnitude with high accuracy, especially when the level of drift impacts the model's performance significantly.

A novel method is proposed in this paper to detect failures in the YOLO object detection network. The proposed method is derived based on the features extracted by the YOLO network and uses a secondary neural network to predict misdetections. Subsequently, a novel Recursive Feature Elimination (RFE) based approach is proposed to make the secondary network more lightweight by selecting important features for a target class(es). Hence the computational cost is reduced with a minimum loss of accuracy. Experimental evaluation was done using a YOLO network trained on the COCO dataset considering four of the most frequently appeared classes in the dataset. The proposed failure detection method achieved an 89.79% accuracy when a single class was considered, and a 16% improvement was observed in the accuracy compared to an existing method. By using the proposed feature selection method, an 88.89% accuracy with a 56% reduction in the inference time was achieved. Feature selection was 62 times faster and achieved almost the same failure detection accuracy with a lesser number of features compared to the conventional RFE approach. Moreover, the proposed failure detection framework was evaluated by considering multiple classes together as well, and high accuracy was observed.

This paper shows that input preprocessing using compression and subsequent rescale and rearrange operations implemented using Memristor Crossbar Arrays (MCAs) provides a robust defense against adversarial attacks. The rescale and rearrange operations are implemented using a fully connected layer followed by three convolution layers. The experimental results show up to a 5.18% improvement in adversarial robustness compared to similar input preprocessing techniques on MCAs.

It is shown that compressed learning tolerates adversarial attacks effectively and that classification accuracy is impacted minimally when the compression ratio is selected appropriately. An approach to select the compression ratio is presented. It is also shown that compressed learning is at least as tolerant to adversarial noise as the more power consuming compressive sensing method. Tolerance to adversarial attacks increases when the compressed learning-based neural network architecture is implemented on circuits that use Memristive Crossbar Arrays (MCAs). This paper shows that implementation on an MCA-based analog hardware circuit tolerates adversarial attacks more effectively than a hybrid MCA-based architecture while improving on latency and power consumption.

Recent studies have shown that Memristor Crossbar Array (MCA)-based Deep Neural Network (DNN) accelerators are resilient to adversarial attacks. This paper shows that adversarial attacks do not uniformly affect the classification accuracy of different chips due to inter-chip process variations. It is experimentally shown that on-chip training results in high resiliency to adversarial attacks in all chips. Experimentation considers various types of attack models in MCA-based analog and hybrid architectures.

Existing works indicate that Spiking Neural Networks (SNNs) are resilient to adversarial attacks by testing against few attack models. This paper studies adversarial attacks on SNNs using additional attack models and shows that SNNs are not inherently robust against many few-pixel L0black-box attacks. Additionally, a method to defend against such attacks in SNNs is presented. The SNNs and the effects of adversarial attacks are tested on both software simulators as well as on SpiNNaker neuromorphic hardware.

Despite the immense performance improvement of deep learning-based object detection, the state-of-the-art object detection systems are still prone to misdetections. This work presents a method to predict such misdetections at run-time by using a small network, referred to as ConsensusNet, to learn the correlation patterns or consensus of neighboring detections before non-maximum suppression (NMS). Based on such correlations, ConsensusNet predicts if there are misdetection failures. The proposed method is experimentally evaluated considering single person class from COCO dataset and using YOLOv3 as the object detection system. It shows the proposed method can achieve accuracy of 84.6% and the performance measured in other metrics are also promising. To the best of our knowledge, ConsensusNet is the first network reported for predicting misdetections in object detection.

A novel methodology of augmenting the design of an existing Convolutional Neural Network (CNN) is proposed to improve its accuracy over low accuracy classes, on any dataset. The proposed structure precedes the CNN and comprises shallow CNNs arranged in a novel cascading topology to minimize the inference time. The approach utilizes the confusion matrix of the input CNN on a specific dataset to identify sets of low accuracy classes that resemble each other with respect to the error distribution. The shallow networks operate in parallel to improve the accuracy of selected low accuracy classes, without increasing the inference time. Experimentation on benchmark datasets and established CNNs shows a significant increase, up to 36.8%, in the accuracy of selected classes over the input CNN, with practically no overhead on the inference time.

A novel broadside ATPG for low power hardware Trojan detection is proposed. The ATPG uses a set of built-in current sensors to observe the IDDT current drawn at gate level. Experimental results on the ISCAS'89 and ITC'99 benchmarks demonstrate its effectiveness. The generated test pattern set achieved high detection coverage using a small number of current sensors.

The statistical delay of a path is traditionally modeled as a Gaussian random variable assuming that the path is always sensitized by a test pattern. Its sensitization in various circuit instances varies among its test patterns and the pattern induced delay is non-Gaussian. It is modeled using probability mass functions (PMFs). This article presents an automatic test pattern generation (ATPG) method, where multiple uncorrelated test patterns per path improve its defect coverage (DC). The impact of the ATPG process is evaluated by comparing to traditional methods. It is also shown that the presented ATPG is useful in selecting critical paths.

In this paper, the problem of determining the sensitization probability of a path by a test vector is investigated which is important when testing for delay defects due to process variations. An algorithm and its extension are presented with a tradeoff in accuracy and execution time. Gate delays are modeled as probability mass functions, and novel operations are introduced that take into consideration circuit reconvergences and path correlations. The proposed approach estimates accurately the sensitization probability of a path for a test vector. It relies on novel operations at each gate on the target path. Experimental results and comparisons with Monte Carlo are presented on the ISCAS'85, ISCAS'89, and ITC'99 benchmarks.

Industrial and automotive standards for safety critical System on Chips require fault coverage at the gate level. A scalable estimation method that avoids fault injection is presented. It is statistically correlated to the actual fault coverage.

An approach to detect ultra-low-power no-payload Trojans by analyzing IDDT waveforms at each gate is presented. The approach uses a novel ATPG to insert small number of current sensors in order to analyze the behavior of individual gates at the IDDT waveform. The proposed method is assisted by a standard cell placement method that strengthens Trojan detection. Experimental results on the largest ISCAS'85, ISCAS'89 and ITC'99 benchmarks demonstrate that low-power no-payload Trojans are detected without any area overhead and with negligible performance degradation.

An Integer Linear Programming based method to identify current mode threshold logic functions is presented. The approach minimizes the transistor count and benefits from a generalized definition of threshold logic functions. Process variations are taken into consideration. Experimental results show that many more functions can be implemented with predetermined hardware overhead, and the hardware requirement of a large percentage of existing threshold functions is reduced.

In this paper, an approach to select critical paths using a probabilistic delay model is presented. Paths through each fault site are selected to effectively test a device for small delay defects that may occur due to random process shifts in different pockets of the physical layout. Experimental evaluation shows significant improvement in time performance and quality of selected paths over existing work.

A method is presented that guides diagnosis using multiple transition faults on sensitized embedded segments. Suspect faults are eliminated with non-enumerative operations and non-pruned faults are ranked. The approach also considers speed-ups on gates. Experimental results demonstrate the scalability of the proposed approach and its effectiveness in fault diagnosis.

The problem of determining the sensitization probability of a path by a test vector is investigated. It is important when testing for delay defects due to process variations. An algorithm is presented which has high accuracy. Gate delays are modeled as probability mass functions, and novel operations are introduced that take into consideration circuit reconvergences and path correlations. Experimental results and comparisons with Monte Carlo are presented on the ISCAS'85, ISCAS'89 and ITC'99 benchmarks.

This paper shows that threshold logic functions can be implemented in CMOS-based current mode logic with reduced transistor count when the input weights are not restricted to be integers. A novel implementation of non-integer weights is proposed. Experimental results show that the transistor count reduction results in significant reduction in power dissipation and delay.

Most existing soft error simulators do not consider multiple event transients or use simple electrical masking models to model the pulse shape. In this paper, the METS tool is proposed which employs BDDs and partitioning for faster simulation. Additionally, it uses an accurate electrical masking model to determine the output pulse shape which allows for accurate calculation of the soft error rate in the presence of multiple event transients (METs). The tool is tested on various ISCAS 85 benchmarks and is shown to have a speedup of up to 90X compared to Monte Carlo simulation.

Resistive memory is a promising emerging technology but is prone to defects due to uncertainties in nanoscale fabrication. The test time of existing techniques for bipolar metal-oxide memristors is dominated by slow writes. Fast March tests are proposed that benefit from fast write operations. The test application time is reduced significantly while simultaneously reducing the average test energy per cell. Experimental evaluation in 45-nm technology shows a speed-up of approximately 70% with a decrease in energy by approximately 40%. Design for testability (DfT) schemes are proposed to implement the new test methods.

An approach capable of identifying the locations of distributed small delay defects, arising due to manufacturing aberrations, is proposed. It is shown that the proposed formulation can be transformed into a Boolean satisfiability form to be solved by any satisfiability solver. The approach is capable of providing a small number of alternative sets of potential defective segments, and one of the solutions is the actual defect configuration. This is shown to be a very important property toward the effective identification of the defective segments. Experimental analysis on International symposium on circuits and systems and International Test Conference benchmark suites show that the proposed approach is highly scalable and identifies the location of multiple delay defects.

Current mode is a popular CMOS-based implementation of threshold logic functions, where the gate delay depends on the sensor size. This paper presents a new implementation of current mode threshold functions for improved gate delay and switching energy. An analytical method is also proposed in order to identify quickly the sensor size that minimizes the gate delay. Simulation results on different gates implemented using the optimum sensor size indicate that the proposed current mode implementation method outperforms consistently the existing implementations in delay as well as switching energy.

Due to the reducing transistor feature size, the susceptibility of modern circuits to radiation induced errors has increased. This, as a result, has increased the likelihood of multiple transients affecting a circuit. An important aspect when modeling convergent pulses is the approximation of the gate output. Thus, in this paper, a model that approximates the output pulse shape for convergent inputs is proposed. Extensive simulations showed that the proposed model matched closely with HSPICE and provides a speed-up of 15X.

An automatic test pattern generation approach to detect delay defects in a circuit consisting of current mode threshold logic gates is introduced. Each generated pattern should excite the maximum propagation delay at the fault site. Manufactured weights may vary, and maximum delay is ensured by applying an appropriately generated set of patterns per fault. Experimental results show the efficiency of the proposed methods.

A Monte Carlo-based approach is proposed capable of identifying in a non-enumerative and scalable manner the distributions that describe the delay of every path in a combinational circuit. Furthermore, a scalable approach to select critical paths from a potentially exponential number of path candidates is presented. Paths and their delay distributions are stored in Zero Suppressed Binary Decision Diagrams. Experimental results on some of the largest ISCAS-89 and ITC-99 benchmarks shows that the proposed method is highly scalable and effective.

The path delay fault model is effective in detecting small delay defects. The proposed approach identifies the delay behavior of paths in various circuit instances without enumerating them. It selects critical paths through path implicit operations on a compact data structure potentially containing an exponential number of path candidates. The experimental analysis on some of the largest ISCAS-89 and ITC-99 benchmarks shows that the proposed approach is highly scalable and effective.

An approach for Trojan circuit detection in a finite state machine is presented. It is based on a model where long sequences of inputs that are applied to the system in the functional mode can detect if Trojan hardware is triggered with high probability. An efficient and scalable input generation algorithm for broadside tests is introduced.

For large modern circuits, it is desirable to trade hardware cost for time when making path delay fault coverage estimates, especially as a subroutine for ATPG and timing analysis solutions. A parallel adaptation of an established framework for implicit path delay fault grading on with a GPGPU implementation is presented. Experimental evaluation on a NVIDIA Tesla C2075 GPU shows on average 50x speedup against the basic version for the framework on an Intel Xeon E5504 host system. Over a 1200x speedup is observed against a single-threaded, more complex version in the framework which grades more faults.

Compressive sensing has been demonstrated as an appealing technique in the implementation of low-power sensors. This work studies the feasibility and potential power savings by adaptively adjusting the sampling rates in compressive sensing operations, which is referred to as adaptive compressive sensing in this paper. The results reveal that the sparsity of many biomedical sensor signals varies over time and hence it is possible to perform such adaptive operations. The study also shows that the adaptive operation can lead to significant reduction on sensor node power consumption

Gate delays in a circuit degrade as a function of time due to NBTI. This impacts the set of critical paths that must be tested for delay defects. We propose a method that determines a time period under which the circuit can be tested for delay defects in the presence of NBTI aging.

Searching for a particular pattern in a very large DNA database is a fundamental and essential component in computational biology. In the biological world, pattern matching is required for finding repeats in a particular DNA sequence, finding motif, aligning sequences, and other similar tasks. Due to an immense amount and continuous increase of biological data, the searching process requires very fast algorithms. A function-based tool set for fast offline pattern searches in large DNA sequences is proposed. The method benefits from the use of Boolean functions, their compact storage using canonical data structure, and the existence of built-in operators for these data structures. Experiments on DNA sequences from the NCBI database show that the proposed approach is scalable. The time complexity depends on the size of the data structure used for storing the function that represents the DNA sequence. It is shown that the presented approach exhibits sublinear time complexity to the DNA sequence size.

Existing threshold logic synthesis methods decompose larger input functions into smaller input functions and perform synthesis for them. It is shown that significantly larger input functions can be synthesized by implementing the existing methods in an implicant-implicit manner. Experimental results on the ISCAS 85 benchmarks show that this impacts the synthesis cost, which drops significantly. More specifically, as the size of the functions that can be handled by the synthesis algorithm increases, the number of threshold logic gates required to implement very large input functions decreases. In addition, the total weight decreases and the performance is improved.

Threshold logic gates allow for complex multiinput functions to be implemented using a single gate thereby reducing the power and area of a circuit. Clocked threshold gates are nanopipelined to increase network throughput. It is shown that synthesis methods that do not consider the synchronization of the nanopipeline can produce an enormous amount of buffers. The proposed algorithm synthesizes a Boolean network into a nanopipelined threshold logic network by minimizing not only the number of combinational clusters but also the associated buffer insertion overhead.

Capacitive and inductive coupling between bus lines results in crosstalk induced delays. Many bus encoding techniques have been proposed to improve the performance. Existing implementation techniques and mapping algorithms in the literature only apply the specific encoding. This paper presents the first generalized framework for a stall-free on-chip codeword generation strategy that is scalable and easy to automate. It is applicable to the coupling aware encoding techniques that allow recursive codeword generation. The proposed implementation strategy iteratively generates codewords without explicitly enumerating them. Codeword mapping relies on graph-based representation that is unique to the given encoding technique. The codewords are calculated on-chip using basic function blocks, such as adders and multiplexers. Three encoding techniques were implemented using the proposed strategy. Experimental results show significant reduction in the area overhead and power dissipation over the existing method that uses random logic to implement the codec.

For large modern circuits, it is desirable to trade hardware cost for time when making path delay fault (PDF) coverage estimates, especially as a subroutine for automatic test pattern generation and timing analysis solutions. A parallel adaptation of an established framework for implicit PDF grading on with a general-purpose computing on graphics processing units (GPU) implementation is presented. Experimental evaluation on a NVIDIA Tesla C2075 GPU shows on average 50× speedup against the basic version for the framework on an Intel Xeon E5504 host system. Over a 1200× speedup is observed against a single-threaded, more complex version in the framework which grades more faults.

The performance of a tightly coupled on-chip bus connecting several embedded cores can be improved using multithreshold comparators at the receiver end. Reduction in supply voltage may cause bit errors. An on-chip encoding technique for error correction is proposed to improve the robustness of the method. It relies on a novel algorithmic formulation that exploits the inbuilt redundancy of the multithreshold architecture to reduce the number of redundant bits required to achieve error correction when compared with the existing methods. Extensive experimental evaluation confirms that the overhead of the proposed encoding technique is significantly less than that of the traditional encoding techniques that use a single threshold voltage. Experimental evidence demonstrates that the proposed encoding technique can be implemented on-chip in a scalable nonenumerative manner.

The crosstalk induced delays have become a significant bottleneck in deep sub-micron communication. The encoding techniques proposed in existing literature, that cope with crosstalk while providing error detection capabilities require significantly high redundancy to achieve the goal. It is shown in recent publications that the effect of crosstalk can be mitigated by using multiple threshold voltages without the use of redundant bits. However such a method is more susceptible to noise due to the reduced voltage slack introduced by multiple threshold voltages. This paper proposes a novel error detection encoding technique suitable for multi-threshold capture mechanism. The proposed technique uses multiple thresholds to mitigate the effect of crosstalk while introducing redundant bits for error detection purpose only. As observed in the experimental evaluation section, the proposed encoding technique has significantly less amount of redundancy as compared to existing techniques.

The implementation of debugging tools through joint action test group (JTAG) has led to increased exposure of intellectual property through the interface. In this brief, the first hardware implementation of a flexible multilevel access security system for the JTAG interface is detailed. The proposed method is user-privilege aware, which allows for higher granularity for controlling user access of individual scan chains. The loading of individual JTAG instructions into scan chains can be blocked based on the credentials of the user. The hardware modifications proposed are compliant with IEEE 1149.1, have minimal timing overhead, and require no modifications to the core logic of the integrated circuit.

A scalable synthesis method for large input threshold logic circuits using Zero Suppressed Binary Decision Diagrams is introduced. Existing synthesis methods require that a large input function must be initially decomposed using small input functions and this impacts the synthesis cost. The presented approach in this paper does not consider such restrictions. It is experimentally shown that the proposed method can synthesize the primary outputs of existing benchmarks without consulting the net-list, and the synthesis cost is significantly reduced over the existing methods.

A Monte Carlo based approach capable of identifying the probability distributions that describe the delay of every sensitizable path in a path implicit manner is proposed. It is shown experimentally that the statistical information for all paths is generated as fast as the traditional Monte Carlo simulation that identifies the probability density function for the circuit delay.

A fast method to identify the given Boolean function as a threshold function with weight assignment is introduced. It characterizes the function based on the parameters that have been defined in the literature. The proposed method is capable to quickly characterize all functions that have less than eight inputs and has been shown to operate fast for functions with as many as forty inputs. Furthermore, comparisons with other existing heuristic methods show huge increase in the number of threshold functions identified, and drastic reduction in time and complexity.

Random voltage changes on bus lines may lead to reading corrupted digital data. A novel methodology for detecting such anomalies is proposed. It uses multiple threshold voltages at the receiver end. In earlier work it was shown that multiple voltage thresholds improve the performance along buses, especially when they are coupled as is often the case in deep-submicron. This work shows that multiple thresholds can also be used to identify voltage perturbations online. The mechanism is assessed on bus lines that may have up to two adjacent aggressors. The efficiency of the methodology is evaluated for perturbations at single and multiple receiving nodes of a data bus.

Recent literature shows that the performance of a bus with crosstalk is improved using a multi-threshold capture mechanism with the trade-off on the noise margin. This work proposes a method to generate error correction code suitable for multi-threshold receivers to circumvent the noise margin trade-off. The overhead of the proposed technique is significantly less than existing encoding techniques that take into account both crosstalk avoidance and error correction.

Increases in the powerful features being deployed through the JTAG interface has left the testing platform vulnerable to malicious users. In this paper the hardware implementation of a flexible multilevel security access system is described. The security mechanism allows for higher granularity for controlling user access of individual scan chains. This allows for blocking of individual opcodes from being loaded into scan chains. The hardware modifications proposed are complaint with IEEE 1149.1 and require no modifications to the core logic of the IC.

In sub-micron technology, a small inaccuracy in computing the probability of occurrence of a soft error results into an unacceptable chip failure rate. A method to estimate the probability of SET propagation to the output gate at any time instant within the latching window is proposed. Its accuracy is evaluated using Monte Carlo simulations.

Inductive and capacitive coupling are responsible for slowing down signals. Existing bus encoding techniques tackle the issue by avoiding certain types of transitions. This work proposes a codeword generation method for such techniques that is scalable to very wide buses. Experimentation on a recent encoding technique confirms that the conventional method is limited to 16-bit bus while the proposed method is easily extended beyond 128-bits.

It is a common practice to gate a limited number of scan cells in order to reduce overall switching activity during shift, thereby, reducing the circuit's dynamic power consumption. In this paper, we propose a novel approach to reduce overall shift power during test by inserting extra hardware at the output of scan cells and internal gates. Based on the estimated dynamic power (using PrimeTime-PX), the proposed approach uses a linear time algorithm to identify the nodes to be gated. To avoid degrading the timing of the circuit, additional logic is added only at paths that are not timing-critical. The proposed approach significantly outperforms all approaches that gate only scan cells. Experimental results on ISCAS and ITC benchmarks show that on average more than 48% of the dynamic power can be reduced while reducing the hardware overhead by up to 3.75X.

This paper presents a scalable method to determine that a Boolean function is a threshold logic function. When the number of inputs of the function increases, identifying a threshold logic function is a laborious task. It is shown experimentally that the proposed method is faster and identifies more threshold logic functions with weight assignment than any other existing method.

A novel method is proposed in order to calculate the probability of an SET resulting into SEU. The method is proposed to calculate the propagation of SET to the output gate at any time instant within the latching window. The method uses symbolic simulation and disjoint covers of appropriately formulated functions to take into consideration re-convergent paths and therefore more accurate calculations. This is evaluated experimentally on the benchmark circuits.

Random voltage changes on bus lines may lead to reading corrupted digital data. A novel methodology for detecting such anomalies is proposed. It uses multiple threshold voltages at the receiver-end. In our earlier work we have shown that multiple voltage thresholds improve the performance along buses, especially when they are coupled as is often the case in deep-submicron. This work shows that multiple thresholds can also be used to identify voltage perturbations on-line. The mechanism is presented assuming that each line can have only one aggressor. The efficiency of the methodology is evaluated for perturbations in single and multiple receiving nodes of a data bus.

Existing techniques for path delay fault (PDF) diagnosis prune fault-free candidates using nonfailing patterns but fail to reduce the size of suspect set significantly. This paper presents two alternative techniques that can be applied in a postprocessing manner to further reduce the suspect set by prioritizing paths using only the failing patterns. Experimental results on the ISCAS benchmarks demonstrate that they are time and memory efficient.

Recently several methods have been presented to measure the delay of a small set of path delay faults (PDFs), known as a basis set which is used to compute the delays of PDFs. All methods assume that the basis consists of strong robustly tested PDFs because their delays can be measured. This paper presents procedures to identify measurable PDFs whose delays otherwise could not be measured by traditional strong robust sensitization. Path measurement techniques that conditer the bounded delay model allow us to compute the delays of almost all PDFs in existing benchmarks.

A recent decision diagram-based algorithm was able to generate test patterns for each sensitizable path delay fault. Although scalable this approach results to prohibitively long test sets. This paper presents a novel technique to intelligently select paths for compaction. It guarantees optimal compaction subject to the order of processing faults. The compaction rate is superior to any published method, even for the small benchmarks where enumerative compaction methods have been proposed. Experimental results on the publicly available benchmarks demonstrate the scalability of the proposed method.

Transient faults have become increasingly observable in combinational logic. This is due to the weakening of some inherent protective mechanisms that logic traditionally holds against such flawed spurious events. One of the aforementioned mechanisms relates to the propagation of transient faults along sensitizable paths. Existing literature that relies on logic simulation under estimates the number of sensitizable paths per circuit. This leads to inconclusive and overly optimistic results when a worst-case analysis is required. In this paper, we present a zero-suppressed binary decision diagram (ZBDD) centered framework, for a complete consideration of all potentially sensitizable paths per circuit. The proposed method is validated in logic paths by evaluating worst-case transient-wave electrical characteristics, such as maximum duration and corresponding amplitude at the circuit outputs.

This paper presents a novel approach for identifying non-robustly unsensitizable paths using the bounded delay model for gate delays. A unique feature is that the unsensitizable paths are identified by working on a data structure that stores selected circuit paths instead of the netlist. It is shown that unless the delay of untestable paths are ignored, many non-robust paths will remain undetected. Experimental results show the approach implicitly identifies a large number of non-robustly unsensitizable paths, which were not identified with other existing techniques.

The gate that is implemented with threshold logic is called a threshold logic gate (TLG). The logic output value of an TLG depends on the weighted sum of its inputs. Manufactured weights in the threshold logic gates (TLGs) may differ from the designed values and significantly affects the fault coverage. A novel automatic test pattern generation (ATPG) tool is proposed to detect whether the circuit is malfunctioning due to such weight-related defects.

A framework to identify critical executable paths in an acyclic synthesizable very-high-speed integrated circuits hardware description language or software code is presented. It can be used effectively in a variety of problems that include compiler-level architectural optimization for improved performance and static software timing analysis. The approach is path implicit and scalable. The set of executable paths is stored implicitly using zero-suppressed binary decision diagrams. Functions that represent condition statements at the basic blocks are manipulated using binary decision diagrams. Postprocessing algorithms on the canonical data structures identify critical paths and other useful metrics such as a most frequently used critical path. Experimental results demonstrate the scalability of the proposed method.

A new way of fault collapsing for effect-cause diagnosis is presented. In contrast to existing dominance-based methods which operate on a pair of faults, the proposed method operates on pairs of sets of faults. The impact of the proposed method is evaluated with respect to effect-cause diagnosis. Experimental results show that the proposed collapsing methods can reduce the diagnostic simulation time on an average of 31% when compared to the existing techniques

A new framework is proposed to generate compact quality tests to detect small delay defects by activating and propagating transition faults only along implicitly kept sensitizable critical paths. It is shown how to implicitly generate functions to derive tests for the proposed framework. The novelty of the method relies on a multivalued algebra that is used to generate the test functions with a single circuit traversal, independent of the number of critical paths. Experimental results demonstrate the effectiveness of the method.

This article presents the speedups achieved in a generic single-chip microprocessor system by employing a high-performance datapath. The datapath acts as a coprocessor that accelerates computational-intensive kernel sections thereby increasing the overall performance. We have previously introduced the datapath which is composed of Flexible Computational Components (FCCs). These components can realize any two-level template of primitive operations. The automated coprocessor synthesis method from high-level software description and its integration to a design flow for executing applications on the system is presented. For evaluating the effectiveness of our coprocessor approach, analytical study in respect to the type of the custom datapath and to the microprocessor architecture is performed. The overall application speedups of several real-life applications relative to the software execution on the microprocessor are estimated using the design flow. These speedups range from 1.75 to 5.84, with an average value of 3.04, while the overhead in circuit area is small. The design flow achieved the acceleration of the applications near to theoretical speedup bounds. A comparison with another high-performance datapath showed that the proposed coprocessor achieves smaller area-time products by an average of 23% for the generated datapaths. Additionally, the FCC coprocessor achieves better performance in accelerating kernels relative to software-programmable DSP cores.

We propose a novel method for generating test patterns that can be encoded efficiently using reseeding of LFSR-based schemes for hybrid BIST. Our focus is to reduce the number of deterministic tests while keeping their overall number of specified bits small and, thus, reduce the storage requirements for the LFSR seeds. The proposed solution is based on test function manipulation and generates a compact test set in which individual tests have a high number of unspecified bits. The method uses binary decision diagrams (BDDs) and a modified version of the min-cost max-matching problem on graphs. The obtained experimental results clearly demonstrate the impact of the proposed ATPG algorithm in reducing the on-chip seed storage, when combined with the considered BIST schemes

This paper presents a new way of fault collapsing called dominance with sub-faults(DSF) collapsing. The proposed approach reduces the number of tests required to diagnose a fault. Experimental results on the ISCAS'85 benchmarks demonstrate the impact of the proposed method over the traditional fault collapsing method

This paper examines the problem of exact delay fault grading in non-scan sequential circuits using a sequence of test patterns that are applied with a rated clock. Delay faults ending at flip-flops are latched as uncorrelated errors. The errors latched on flip-flops by previous tests may enhance the at-speed delay fault coverage for each pattern in the sequence. In addition, the propagation of errors (and the faults they represent) may be facilitated by other latched errors as well as potential delayed transitions activated by each at-speed test application. An exact grading method is presented and its impact over existing methods is demonstrated experimentally

A scheme to functionally test the networking infrastructure of a system within a network on chip is presented. A fault model and a test pattern generation and application algorithm that relies on a network simulator are presented. Experimental results demonstrate the impact of the presented algorithm.

A flexible test architecture for embedded cores and all interconnects in a system-on chip (SOC) is presented. It targets core testing parallelism and reduced test application time by using, as much as possible, existing core interconnects to form TAM paths. It also provides for dynamic wrapper reconfiguration. Algorithms that minimize the use of extra interconnects for the TAM path formation are presented and evaluated.

A high-performance data path to implement digital signal processing (DSP) kernels is introduced in this paper. The data path is realized by a flexible computational component (FCC), which is a pure combinational circuit and it can implement any 2 times 2 template (cluster) of primitive resources. Thus, the data path's performance benefits from the intracomponent chaining of operations. Due to the flexible structure of the FCC, the data path is implemented by a small number of such components. This allows for direct connections among FCCs and for exploiting intercomponent chaining, which further improves performance. Due to the universality and flexibility of the FCC, simple and efficient algorithms perform scheduling and binding of the data flow graph (DFG). DSP benchmarks synthesized with the FCC data path method show significant performance improvements when compared with template-based data path designs. Detailed results on execution time, FCC utilization, and area are presented

A novel function-based method for error propagation is proposed for exact delay fault coverage, using a single rated clock for fault activation under any delay fault model. Sequential circuits without full scan are considered. A latched error at a flip-flop represents one or more delay faults and is allowed to propagate to an observable point with or without the support of other latched errors. Existing methods allow only one flip-flop to have an error during the propagation phase to simplify the process of error propagation at the expense of decreased fault coverage. The advantage of the proposed method is demonstrated experimentally using the path-delay-fault model with more than 20% improvement in fault coverage.

A method to implicitly derive all tests for each transition fault under established fault-sensitization criteria is presented. The derived quality test functions are enhanced in three different ways to derive better quality test sets. One enhancement restricts fault sensitization along critical subcircuits whose paths have long delays under a fixed-delay model. Another manipulates the functions to generate compact test sets. The last one enriches the test set with additional test vectors so that transition faults are tested through several activation and propagation paths without path enumeration. Experimental results demonstrate the effectiveness of deriving such enhanced test functions

The problem of fault grading for multiple path delay faults is introduced and a method of obtain exact coverage is presented. The faults are represented and manipulated as combinational sets using zero-suppressed binary decision diagrams. The presented methodology for fault grading uses only a polynomial number of zero-suppressed binary decision diagram operations. The efficiency of the proposed method is demonstrated by the experimental results on the ISCAS'85 and ISCAS'89 benchmarks.

The first path implicit and exact non-robust path delay fault grading technique for non-scan sequential circuits is presented. Non enumerative exact coverage is obtained, by allowing any latched error representing a delayed transition to propagate to a primary output with the support of other potentially latched errors. The generalized error propagation is done by symbolic simulation. Appropriate data structures for function manipulation are used. The advantage of the proposed method is demonstrated experimentally with consistent improvement in coverage over an existing pessimistic heuristic despite enforced bounds on the memory requirements.

We present in this paper a new security protocol especially suited for sensor networks. This protocol uses a novel encryption method for secure message transmission. We present the details of this encryption scheme along with experimental results performed on a network simulator.

A recent work describes an ATPG for path delay faults that limits the power dissipated by the test patterns to a given bound. However, the power dissipated by the intermediate patterns while applying the test patterns in a sequence is not considered. Experiments with test patterns derived from different ATPGs has shown that the switching activity due to intermediate patterns dissipate considerable power. This paper proposes a method to incorporate stability functions in a functional ATPG to derive test vectors that guarantee reduced power dissipation by the intermediate patterns without loss in PDF coverage.

A recent method generates high quality tests for transition faults using functions. Event sensitization criteria as well as path lengths can be taken into consideration during the generation of such test functions. It is shown how to manipulate the test functions to generate compact test sets. Experimental results on ISCAS'85 and ISCAS'89 circuits show that a compaction rate of the order of 70% to 84% is achieved without compromising fault coverage. Moreover, a novel method to enrich the compacted test set with additional vectors is presented so that transition faults are tested through different activation and propagation paths. Such test sets havehigher quality, compared to traditional transition fault test sets, since events propagate through many critical paths.

Compact high quality test sets to detect small delay defects can be generated using the transition fault model by insisting that events are activated and propagated only along the critical paths for each transition fault, implicitly kept in a zero-suppressed binary decision diagram. This paper shows how to implicitly generate test functions for the described high quality transition fault model. The novelty of the method relies on a multivalued algebra that is used to generate the test functions with a single circuit traversal.

A function representing path delay faults (PDFs) together with their nonrobust test cubes is presented. The function is manipulated effectively using zero suppressed binary decision diagrams (ZBDDs) and irredundant sum of products (ISOPs) in ZBDD-based representation, and is derived using a polynomial number, to the circuit size, of standard ZBDD operations. This new data structure can be used effectively during the ATPG process to derive high quality test sets. Experimental results demonstrate that the proposed structure can be implemented efficiently.

A resynthesis method to protect firm cores or circuit netlist representations is presented. The design is protected by embedding watermark by rewiring circuit with one or more redundancy addition/removal steps. This is the first known attempt to explore rewiring for watermarking. Area, performance, and testability requirements are preserved by the approach. We analyze several attack strategies and we experimentally demonstrate that the proof of authorship is guaranteed with very high probability for all ISCAS'85 benchmarks.

We present a novel framework to identify all the testable and untestable path delay faults (PDFs) in a circuit. The method uses a combination of decision diagrams for manipulating PDFs as well as Boolean functions. The approach benefits from processing partial paths or fanout-free segments in the circuit rather than the entire path. The methodology is modified to identify all testable critical PDFs under the bounded delay fault model. The effectiveness of the proposed framework is demonstrated experimentally. It is observed that the methodology outperforms any existing method for identifying testable PDFs. Its scalability by focusing on critical PDFs is demonstrated by experimenting on very path-intensive benchmarks.

On-chip embedding of deterministic patterns is used for built-in test-pattern generation of large sets of vector pairs for path delay fault testing. A hardware efficient two-phase synthesis procedure is proposed to synthesize the test-pattern generator. Acceptable test-cycle requirements are met using a recent method, which reduces the test embedding problem to that of embedding the first vector in each pair. The approach is generalized to implement a hardware efficient on-chip pattern generator to test the embedded cores of a system on chip. The hardware overhead of the proposed method is reduced at a controllable increase on the number of test cycles.

We present a function-based nonenumerative automatic test pattern generation (ATPG) methodology for detecting path delay faults (PDFs). The proposed technique consists of a number of topological circuit traversals during each a linear number of Boolean functions is generated per circuit line. From each such function we derive a test that detects many PDFs. The two major strengths of the approach, that stem from the function-based formulations used, are very compact test sets, and scalability in test efficiency. The performance of an implementation based on binary decision diagrams is evaluated and compared with existing compact methods to demonstrate the superiority of the proposed method.

We present a novel framework to identify all the robustly testable and untestable path delay faults in a circuit. The method uses a combination of decision diagrams for manipulating path delay faults and Boolean functions. The approach benefits from processing partial paths or fanout free segments in the circuit rather than the entire path. The effectiveness of the proposed framework is demonstrated experimentally. It is observed that the methodology identifies 350% more testable faults in the ISCAS'85 benchmark C6288 than any existing technique by utilizing only a fraction of the time compared to earlier work.

In this paper, a high performance reconfigurable coarse-grain data-path, part of a mixed-granularity reconfigurable platform, is presented. The computational resources are coarse grain components of the same type. An automated methodology for mapping DSP applications on the data-path is also presented, and it is based on unsophisticated, yet efficient, algorithms. Results on DSP benchmarks show the performance improvements over previously published high-performance data-paths.

In this paper, an efficient implementation of a high performance coarse-grain reconfigurable data-path on a mixed-granularity reconfigurable platform is presented. It consists of several coarse grain components of the same type, a reconfigurable inter-component network, and a centralized register bank. The universal type of coarse grain component is shown to increase the system's performance due to significant reductions in the latency. A flexible interconnection network facilitates the data transfers between the coarse grain components and also from or to the register bank. An automated methodology for mapping DSP and multimedia kernels on the data-path is also presented. Chaining of operations is optimally exploited, and the architecture allows for simple and efficient algorithms for scheduling, live signal reduction, and component binding. Experimental results verify the impact of our architectural decisions and design automation methods.

In this paper we propose an implicit test pattern generation method so that many path delay faults are covered and the dissipated power satisfies a given bound. Typical delay values are considered from an accurate gate delay model. We use a timed ATPG that combines function-based and structural (PODEM-like) methods for faster test generation, which is also more accurate in sequential circuits.

We propose a novel way to further secure the data transmitted along routes of a wireless ad hoc network, after a potentially secure connection has been established between two nodes. In our method, the encryption/decryption key used is the message itself. Our approach requires that the message is split into parts (sub-messages) and that the encrypted sub-messages be transmitted along different paths (routes) which are reception disjoint.

An approach for selecting critical paths along which testable path delay faults can exist is presented. The proposed method is particularly helpful on path intensive circuits. Critical paths are selected implicitly with the aid of a combination of decision diagrams. An implicit method to eliminate untestable faults along the selected paths is also presented. The effectiveness of the approach is demonstrated on path intensive ISCAS'85, ISCAS'89 and ITC'99 benchmarks.

This work presents an efficient methodology to on-line test field programmable analog array (FPAA) circuits. It proposes to partition the FPAA circuit under test into sub circuits. Each sub circuit is tested by replicating the sub circuit with programmable resources on FPAAs, and comparing the outputs of the original partitioned sub circuit and its replication. The advantages of this approach includes: low implementation cost, enhanced testability, and flexible testing schedules. This work also presents circuit techniques to address stability problems which are often encountered in the proposed on-line testing approach. In addition, the impact of performing circuit partition on testability is investigated in this work. It shows that testability is generally improved in partitioned circuits. Finally, experimental results are presented to demonstrate the feasibility and effectiveness of the proposed techniques.

We present a generic framework that supports efficient generation of the traditional Boolean difference function of some output with respect to any line in a combinational circuit, which is important when testing for logic defects. The framework also allows for the generation of generalized Boolean difference functions, which reflect sensitivity on event propagation from a given line to some circuit output. This generalized function could apply in timing verification, analysis, and test. We implemented the proposed framework using various function representation environments, including binary decision diagrams, Boolean expression diagrams, and Boolean networks, and report experimental results on the ISCAS'85 and ISCAS'89 benchmarks.

This paper introduces an implicit version of the well-known deductive fault simulation technique suitable to delay fault models with an exponential number of faults. The proposed method calculates the fault coverage by generating lists of entities for each line during a single topological circuit traversal. Each stored entity only contains a number and a subset of the test vectors. No delay faults are stored, and no special data structures are required. There are significant differences between the presented implicit method and fault coverage using deductive fault simulation. The method is shown to be effective for delay the path and segment delay fault models.

A flexible test access mechanism (TAM) for embedded cores and their interconnects in a System-on Chip (SOC) environment is presented. It targets core testing parallelism and reduced test application time while explicitly taking into consideration area and performance issues. The TAM primarily uses core interconnects but also allows for extra interconnects. The DFT hardware can be implemented either at the SOC or at the core level. It combines features of TAMs that have been designed for low test application time and those for SOC area and performance criteria.

We formulate the path delay fault (PDF) coverage problem as a combinatorial problem that amounts to storing and manipulating sets using a special type of binary decision diagrams, called zero-suppressed binary decision diagrams (ZBDD). The ZBDD is a canonical data structure inherently having the property of representing combinational sets very compactly. A simple modification of the proposed basic scheme allows us to increase significantly the storage capability of the data structure with minimal loss in the fault coverage accuracy. Experimental results on the ISCAS85 benchmarks show considerable improvement over all existing techniques for exact PDF grading. The proposed methodology is simple, it consists of a polynomial number of increasingly efficient ZBDD-based operations, and can handle very large test sets that grade very large number of faults.

The first nonenumerative framework for diagnosing path delay faults (PDFs) using zero suppressed binary decision diagrams is introduced. We show that fault-free PDFs with certain validated nonrobust test may be used together with fault-free robustly tested faults to eliminate faults from the set of suspected faults. All operations are implemented by an implicit diagnosis tool based on the zero-suppressed binary decision diagram. The proposed method is space and time nonenumerative as opposed to existing methods which are space and time enumerative. Experimental results on the ISCAS'85 benchmarks show that the proposed technique is on average three times more efficient than the existing techniques.

Inserting controllable/observable points in the test architecture has been shown to be a viable method for reducing the number of path delay faults that need to be tested in a circuit. In order to have a minimal impact on the operation clock and more accuracy in testing, it is proposed that test points should be inserted with the additional constraint that every path has a bounded number of test points. A polynomial time solvable integer linear programming (ILP) formulation serves as the basis for the presented test placement methodology. Due to the ILP's global optimization property we achieve results that are comparable to those by an existing greedy technique for the less constrained test point placement problem.

The problem of fault grading for multiple path delay faults is studied and a method of obtaining the exact coverage is presented. The faults covered are represented and manipulated as sets by zero-suppressed binary decision diagrams (ZBDD), which are shown to be able to store a very large number of path delay faults. For the extreme case of memory problem, a method to estimate the coverage of the test set is also presented. The problem of fault grading is solved with a polynomial number of BDD operations. Experimental results on the ISCAS'85 benchmark include test sets from ATPG tools and specifically designed tests in order to investigate the limitations and properties of the proposed method.

The problem of determining the exact number of path delay faults that a given test set detects in a combinational circuit is shown to be intractable. This result further strengthens the importance of several recently proposed pessimistic heuristics as well as exact exponential algorithms for this nonenumerative problem. A polynomial time pessimistic algorithm which returns higher coverage than algorithms with the same order of complexity and at the same time compacts the test set is also presented.

The partition of the inputs of a circuit under test (CUT) into groups of compatible inputs reduces the size of a test pattern generator and the length of the test sequence for built-in self-test (BIST) applications. In this paper, a new test-per-clock BIST scheme is proposed which is based on multiple input partitions. The test session consists of two or more phases, and a new grouping is applied during each test phase. Using the proposed method a CUT can be tested at-speed and complete fault coverage (100%) is achieved with a small number of test vectors and small area overhead. Our experiments show that the proposed technique compares favorably to the already known techniques.

We present an ATPG tool for functional delay faults which applies to the single-input transition (SIT) and the multi-input transition (MIT) fault models, and is based on Reduced Ordered Binary Decision Diagrams (ROBDDs). We are able, for the first time, to identify all faults that do not have any SIT tests, and generate all SIT tests for nonredundant faults in combinational circuits. We also provide methodologies for efficient generation of MIT tests. Our experimental results on the ISCAS'85 benchmarks is by far superior to existing methods as well as a Satisfiability-based tool that we have developed for comparative purposes. The presented tool, coupled with advancements in path delay fault coverage, shows that both the SIT and MIT functional models are very useful in ATPG for robust path delay faults for synthesized circuits.

Formulates the fault grading problem as a combinatorial problem that amounts to storing and manipulating sets on a special type of binary decision diagrams (BDDs), called zero-suppressed BDDs (ZBDDs), that represent sets in a unique and compact manner. A simple modification of the basic scheme allows us to overcome memory problems that may arise by complex set representation. Experimental results on the ISCAS'85 benchmarks show considerable improvement over all existing techniques for exact PDF grading. The main advantages of the proposed methodology are the simplicity of the approach, in terms of it being expressed by a polynomial number of increasingly efficient BDD-based operations, its organization, and its ability to handle very large test sets.

We propose an on-chip test pattern generator that uses an one-dimensional cellular automaton (CA) to generate either a precomputed sequence of test patterns or pairs of test patterns for path delay faults. To our knowledge, this is the first approach that guarantees successful on-chip generation of a given test pattern sequence (or a given test set for path delay faults) using a finite number of CA cells. Given a pair of columns (C u , C v ) of the test matrix, the proposed method uses alternative “link procedures” P j that compute the number of extra CA cells to enable the generation of (C u , C v ) by the CA. A systematic approach uses the link procedures to minimize the total number of needed CA cells. The performance of the scheme depends on an appropriate choice of link procedures P j .

This paper examines the problem of transmitting a given amount of data along a single path from a designated source to a designated target in a directed network so that the reliability of the transmission is maximum. In this routing problem, the subpaths of an optimal path are not necessarily optimal. This complicates the process of selecting a path along which the data-transmission is completed in minimum time. A polynomial-time algorithm is presented which guarantees an optimal solution. On acyclic networks with interconnections that operate with the same reliability, another polynomial time algorithm is presented that computes the best route for each possible value of data. This is a useful pre-computation when different amounts of data need to be transmitted at different time periods.

Linear Feedback Shift Registers (LFSRs) are the most efficient and popular pseudo-exhaustive test pattern generation (TPG) mechanism. The goal is to minimize the required test length with low hardware overhead while obtaining pseudo-exhaustive TPG. Primitive characteristic polynomials are widely used because they require only one seed but the candidate polynomials are few and our experiments show that often the pseudoexhaustive test length is prohibitive. In this paper, we present a novel pseudoexhaustive approach with provably low number of seeds where the characteristic polynomial is the product of a primitive and an irreducible polynomial satisfying certain conditions. Our experimental results on the ISCAS'85 benchmarks show that using the proposed method requires very low hardware overhead. The list of characteristic polynomials for pseudoexhaustive TPG is greatly enhanced and our experiments show that pseudoexhaustive TPG is more feasible.

We propose two methods for embedding on-chip a given set of pairs of test patterns that have been generated by an arbitrary ATPG tool for path delay faults. The first method uses an LFSR with multiplexers. It applies to any set of test patterns and it is experimentally verified to have reasonable hardware overhead. The second method applies to the important special case of single input pattern changes within each pair and is very hardware overhead efficient.

One of the key issues in providing end-to-end quality-of-service guarantees in packet networks is how to determine a feasible route that satisfies a set of constraints while simultaneously maintaining high utilization of network resources. In general, finding a path subject to multiple additive constraints (e.g., delay, delay-jitter) is an NP-complete problem that cannot be exactly solved in polynomial time. Accordingly, heuristics and approximation algorithms are often used to address to this problem. Previously proposed algorithms suffer from either excessive computational cost or low performance. In this paper, we provide an efficient approximation algorithm for finding a path subject to two additive constraints. The worst-case computational complexity of this algorithm is within a logarithmic number of calls to Dijkstra's shortest path algorithm. Its average complexity is much lower than that, as demonstrated by simulation results. The performance of the proposed algorithm is justified via theoretical performance bounds. To achieve further performance improvement, several extensions to the basic algorithm are also provided at low extra computational cost. Extensive simulations are used to demonstrate the high performance of the proposed algorithm and to contrast it with other path selection algorithms.

We present a protocol and a scheduling algorithm that determine the time interval during which each node with low energy will be powered off (deactivated) to recharge its local energy source. The subnetwork induced each time by the active network nodes must remain connected. A fast algorithm for this scheduling problem is presented and experimental results are given.

A new routing method for improved quality of service in mobile ad hoc networks is presented. The route selection takes into consideration an estimate for the duration of the transmission, the energy life of each node in the network, and an estimate of the energy consumption on each node along the path. The routing approach guarantees the shortest feasible data transmission subject to the accuracy of estimating the energy-related functions. The worst case time complexity of the proposed method is O(c*m+c*n log n), where c* is the number of different capacities on the links of the network, m is the number of links, and n is the number of nodes in the network. Experimental results are given which support the applicability of the presented approach.

This paper presents a functional level ATPG tool for delay faults which handles all existing fault models. The tool generates patterns using either binary decision diagrams or Boolean satisfiability. Experimental results are presented on the ISCAS'85 benchmarks.

We examine the problem of transmitting a units of data in the most reliable manner along an (s,t) path of a network N=(V,E,c,d,r,s,t). Each edge of a network is assigned a capacity, a delay and a reliability value. In contrast to the similarly defined shortest path problem, it is shown that for this more complex routing problem the subpaths of an optimal path are not necessarily optimal. However, an optimal polynomial is presented. On acyclic networks with interconnections that operate with the same reliability probability, we present a polynomial time algorithm that computes the best route for each value of /spl sigma/. This is a very useful precomputation when different amount of data need to be transmitted at different time periods.

We examine the problem of determining the exact number of path delay faults that a given set of p pairs of patterns detects in a combinational circuit consisting of I lines. Several fault coverage pessimistic heuristics and exact algorithms with worst case exponential behavior have been recently presented with trade-offs between the quality of fault coverage and the time performance. None of the existing approaches has provably good performance. This paper presents the first polynomial time algorithms that calculate the path delay fault coverage exactly. Experimental results on the ISCAS'85 benchmarks demonstrate the effectiveness of the presented approaches.

We present a polynomial-time algorithm that finds the maximum weighted independent set of a transitive graph. The studied problem finds applications in a variety of VLSI contexts, including path delay fault testing, scheduling in high-level synthesis, and channel routing in physical design automation. The algorithm has been implemented and incorporated in a CAD tool for path delay fault testing. We experimentally verify its impact in the latter context.

We examine the problem of transmitting in minimum time a given amount of data between a source and a destination in a network with finite channel capacities and nonzero propagation delays. In the absence of delays, the problem has been shown to be solvable in polynomial time. In this paper, we show that the general problem is NP-complete. In addition, we examine transmissions along a single path, called the quickest path, and present algorithms for general and special classes of networks that improve upon previous approaches. The first dynamic algorithm for the quickest path problem is also given. © 1999 John Wiley & Sons, Inc. Networks 33: 167–174, 1999

Counter-based mechanisms have been proposed for use in built-in test set embedding. A single counter or multiple counters may be used with one or multiple seeds. In addition, counters may be combined with ROM's. Each alternative design scenario introduces a difficult combinatorial optimization problem: minimization of the time required to reproduce the test patterns by an appropriate synthesis of the built-in test pattern generator. This paper presents fast synthesis techniques that result in almost optimal designs. For any given circuit, they efficiently determine whether counter-based schemes are applicable as built-in generators for a given circuit. The proposed techniques have been implemented and tested on the ISCAS'85 benchmarks. Comparative studies with a weighted random linear feedback shift register scheme show that counter-based designs may offer good hardware/time solutions.

This paper presents a nonenumerative automatic test pattern generator for robustly testable path delay faults. In contrast to earlier work by I. Pomeranz, et al. (see IEEE Trans. Computer-Aided Design, vol. 14, p. 1505-15, Dec. 1995), the pattern generator takes into consideration the conditions for robust propagation while sensitizing sets of paths. This increases the probability of testing them robustly with a single test. Novel algorithms are described which identify sets that contain many such potentially compatible paths. The number of detected faults is estimated using a simple and fast method. The approach compares favorably to that of Pomeranz et al. in both fault detection and time performance.

We present a board-level partitioning scheme for improved partial scan on the resulting integrated circuits (IC). Fuzzy logic rules and two adaptation techniques allow us to simultaneously minimize four important independent objective functions in the examined problem formulation. The maximum among all sets in the partition are the following quantities: 1) number of scanned nodes in a set; 2) number of incident nets to a set; 3) number of inputs to any set; and finally 4) the period of the global clock. The sets must satisfy upper and lower capacity bounds. We experimented with some ISCAS'89 benchmark circuits and we compared the performance of our tool with four iterative improvement heuristics, each considering only one of the four different functions. Our experimental results indicate that the performance of the proposed tool is very effective.

This paper presents a test pattern generator for path delay faults which generates a polynomial number of test patterns that target a large number of functionally sensitizable faults. The number of these faults may be exponential to the input site. Experimental results are presented on the ISCAS'85 benchmarks.

We present a polynomial time algorithm that finds the maximum weighted independent set of a transitive graph. The studied problem finds applications in a variety of VLSI contexts, including path delay fault testing, scheduling in high level synthesis and channel routing in physical design automation. The algorithm has been implemented and incorporated in a CAD tool for path delay fault testing. We experimentally verify its impact in the latter context.

A recent method proposed that a lower bound on the number of path delay faults excited by a given test set can be computed using a set independent lines that form a cut. For each line in the cut a subcircuit consisting of all paths that contain the line is defined, and a lower bound to the number of excited path delay faults can be obtained by working on the respective subcircuits. A polynomial time algorithm is presented here for computing the maximum cardinality set of independent circuit lines. Experimental results show that the more the subcircuits the better the lower bound on the number of excited path delay faults is. More subcircuits may be generated only in a heuristic manner. It was proposed to consider two or more line-disjoint cuts C/sub i/. We propose a technique where only one C/sub i/ must be a cut. This scheme is based on novel algorithms, and results in more subcircuits than the previous one.

Nonenumerative path-delay fault coverage estimation for combinational circuits estimates the fault coverage of a given test set without explicit enumeration of all paths in the circuit. In a recent nonenumerative method, it was proposed that a set C of lines be located in the circuit so that the set forms a cut and no lines in the set belong to the same path. Each line in the cut defines a subcircuit consisting of all paths that contain the line. Fault coverage may be obtained by working on all the subcircuits without double-counting path-delay faults. The main result of this paper is a polynomial time algorithm for finding a maximum cardinality set C. Besides its theoretical importance, our extensive experimental results on the ISCAS'85 benchmarks show that the larger the set C (and the number of subcircuits), the better the fault coverage estimation. More subcircuits may be generated only in a heuristic manner. It was proposed to consider two or more line-disjoint cuts C/sub i/. We propose a technique where only one C/sub i/ must be a cut. This scheme is based on novel algorithms and results in more subcircuits than the previous one.

Several mechanisms based on ROMs, LFSRs, counters, cellular automata, have been proposed as built-in test pattern generators with trade-offs between hardware and time overhead. This paper presents and analyses a scheme based on a counter with multiple seeds to generate a test set with low hardware overhead. A fast CAD tool determines the number of clock cycles required for the test set generation and this number is shown to be close to the best possible. A comparison to other existing approaches on the ISCAS'85 benchmarks shows that the proposed mechanism can offer a favorable hardware/time overhead for many circuits.

We examine the problem of minimizing the number of modules in an FPGA with combinational and sequential modules (like the C-modules and S-modules of the ACT2 and ACTS architectures). The constraint is that a combinational module can be combined with one flip-flop in a single sequential module, only if the combinational module drives no other combinational modules. We show that the problem of rearranging the flip-flops by retiming so as to satisfy prescribed individual bounds on the number of combinational and sequential modules is NP-complete. However for the problem of rearranging the flip-flops by retiming so as to minimize the total number of combinational and sequential modules, we present a quadratic-time algorithm. The algorithm uses a minimum-cost flow formulation and offers a significant time improvement over a previous approach that used a general linear program.

In this paper we present an efficient test pattern generator for robust path delay faults, which we call ATPD. Our CAD tool detects much faster more robust path delay faults than any other existing nonenumerative approach. ATPD generates patterns for a non necessarily polynomial number of path delay faults. The nature of the problem indicates that for a test generator to be efficient it must count nonenumeratively the additional delay paths detected by each generated pair of patterns. ATPD generates each pair of patterns and determines the number of paths covered in a novel way that combines these two phases effectively.

We study the behavior of counter-based schemes as very low hardware overhead built-in mechanisms for reproducing unordered test patterns. We show that a small number of seeds, each defining a test pattern generation session, can result in an economical design in terms of both time and hardware. We present counter-based schemes with a trade-off on the time and hardware overhead. Experimental results on the ISCAS'85 benchmarks and comparisons with other built-in mechanisms show that the proposed schemes constitute a promising technique for effective built-in deterministic test pattern generation.

A generally effective criterion for the selection of flip-flops in the partial scan problem for sequential circuit testability is to select flip-flops that break the cyclic structure of the circuit and reduce its sequential depth. The selection of flip-flops may also be subject to a prescribed bound on the clock period of the modified circuit (timing-driven partial scan). In this paper we propose two techniques (for non-timing-driven and timing-driven partial scan) which address the above criterion based on a transformation of sequential circuits known as retiming. For non-timing-driven partial scan, we employ retiming to rearrange the flip-flops of the circuit, so that its functionality is preserved, while the number of flip-flops that are needed to break all cycles and bound the sequential depth is significantly reduced. For timing-driven partial scan, we propose a retiming-based technique that reduces the overall area overhead required to achieve the clock period bound. Experimental results on the ISCAS'89 circuits show the benefit of our approach in both timing-driven and non-timing-driven partial scan.

We propose a very simple and fast CAD tool to check whether a binary counter can reproduce a predetermined set of test patterns in a reasonable time. Given a test matrix T, the tool uses column merging, complementation, and permutation so that the distance between the starting and the finishing vector of the corresponding counter is minimized. The hardware overhead of the proposed approach is by far lower than that of any other existing approach. Although it is computationally difficult (NP-hard) to obtain the absolute minimum distance, we present an algorithm which in the absence of don't cares in the test matrix, finds an appropriate column merging, complementation, and permutation that guarantees the distance is never more than twice as large as the best possible. In the presence of don't cares, the latter algorithm forms the basis of a powerful heuristic. Experiments on various test sets on benchmark circuits show that the exact number of clock cycles needed for a binary counter to reproduce all the patterns for the hard-to-detect faults compares favorably with the expected number yielded by existing Weighted Random LFSR-based approaches which have significantly higher hardware overhead.

We consider two generalizations of the min-cut partitioning problem where the nodes of a circuit C are to be mapped to the vertices of an underlying graph G, and the cost function to be minimized is the cost of associating the nets of C with the edges of G. Let P be the number of pins, the the number of nodes of G, and d be the maximum number of cells on a net of C. In the first problem the graph G is a tree T. An iterative improvement heuristic is given (Vijayan, 1991) with O(P.t/sup 3/) time per pass. Our proposed heuristic guarantees identical solutions in O(P.t.min(d,t)) time per pass. The second problem is defined on any graph G. The standard iterative improvement heuristic requires O(P t/sup 4/) time per pass, but our proposed approach guarantees O(P.t.min(d,t)) time per pass. The problems find applications in VLSI physical design and in distributed systems.

We present a quadratic-time algorithm for minimizing the number of modules in an FPGA with combinational and sequential modules (like the C-modules and S-modules of the ACT2 and ACT3 architectures). The constraint is that a combinational module can be combined with one flip-flop in a single sequential module, only if the combinational module drives no other combinational modules. Our algorithm uses a minimum-cost flow formulation to solve the problem with a significant time improvement over a previous approach that used a general linear program.

We consider the problem of selecting the proper implementation of each circuit module from a cell library to minimize the propagation delay along every path from any primary input to any primary output. An earlier problem definition, known as the general circuit implementation problem, assumes that each implementation has different delays on the input-output paths in the circuit, and that different implementations may have different areas. We primarily focus on the version of the problem, where no restrictions for the overall area of the circuit exist and therefore we ignore the module areas. We show that this problem is NP-hard even for directed acyclic graphs with two implementations per module, and we present a polynomial time algorithm for trees. We have developed heuristics for combinational and sequential circuits.

All previously known algorithms for solving the multicommodity flow problem with capacities are based on linear programming. The best of these algorithms uses a fast matrix multiplication algorithm and takes O(k3.5n3m0.5 log(nDU)) time for the multicommodity flow problem with integer demands and at least O(k2.5n2m0.5 log(nϵ−1DU)) time to find an approximate solution, where k is the number of commodities, n and m denote the number of nodes and edges in the network, D is the largest demand, and U is the largest edge capacity. As a consequence, even multicommodity flow problems with just a few commodities are believed to be much harder than single-commodity maximum-flow or minimum-cost flow problems. In this paper, we describe the first polynomial-time combinatorial algorithms for approximately solving the multicommodity flow problem. The running time of our randomized algorithm is (up to log factors) the same as the time needed to solve k single-commodity flow problems, thus giving the surprising result that approximately computing a k-commodity maximum-flow is not much harder than computing about k single-commodity maximum-flows in isolation. In fact, we prove that a (simple) k-commodity flow problem can be approximately solved by approximately solving O(k log2n) single-commodity minimum-cost flow problems. Our k-commodity algorithm runs in O (knm log4n) time with high probability. We also describe a deterministic algorithm that uses an O(k)-factor more time. Given any multicommodity flow problem as input, both algorithms are guaranteed to provide a feasible solution to a modified flow problem in which all capacities are increased by a (1 + ϵ)-factor, or to provide a proof that there is no feasible solution to the original problem. We also describe faster approximation algorithms for multicommodity flow problems with a special structure, such as those that arise in "sparsest cut" problems and uniform concurrent flow problems.

We address the issue of pseudo-exhaustive test pattern generation (TPG) for the built-in self-test (BIST) of sequential circuits. Let d be the sequential depth, and w be the input dependency limit. We use an LFSR/SR Test Pattern Generator and a small additional hardware overhead to automatically generate d/spl middot/2/sup w/ test patterns to test the circuit pseudo exhaustively or, alternatively, pseudo-randomly with less hardware overhead and extremely high fault coverage. Our scheme uses novel retiming algorithms and transforms the circuit to an equivalent (for test purposes) one by scanning a subset of flip-flops for breaking its cyclic structure, bounding the sequential depth, forcing the input dependency limit, balancing the circuit, and maintaining the clock period. We present the first polynomial time algorithm to bound the sequential depth of a circuit by retiming with minimum number of flip-flops and subject to a clock period bound. We also give a retiming-based polynomial time algorithm to balance a circuit by inserting a minimum number of bypass delay cells. Experimental results on the ISCAS'89 benchmarks indicate that our method outperforms a previously proposed approach, which not only does not provide for on-chip test pattern generation but also requires O(q/spl middot/f/spl middot/2/sup w/) test patterns, where q is the total number of primary or pseudo-primary outputs in the circuit and f is the total number of flip-flops.>

We have developed a mathematical model for estimating the probability of routing on an electrically programmable logic cell array (LGA). Using the model the variation of the routability or the probability of routing with the average span of the nets, and flexibility of programming resources is determined. The results obtained from the model have been verified experimentally. As expected, the routability also increases when the number of programming elements is increased. We also show a three dimensional relationship between routability, placement, and programming flexibility. Our results show a strong relationship between module placement and the routability for an LCA.>

A very popular and established methodology for testing complex sequential circuits is to break the cyclic structure of the circuit by incorporating a minimum number of flip-flops into a partial scan register. The circuit can then be tested by applying sequences of test patterns or using techniques for testing combinational logic. In the former case, it is very important to minimize the sequential depth, i.e. the maximum number of flip-flops on any path from the inputs to the outputs. In the latter case, it is also necessary to balance the circuit, so that all paths between any pair of nodes have the same number of flip-flops. In this paper, we address the above goals using the sequential logic synthesis concept of retiming. We present polynomial-time algorithms that solve optimally the following problems: (i) minimization of the sequential depth of the circuit; (ii) minimization of the number of flip-flops in the circuit so that the sequential depth and the clock period are less than prescribed bounds; and (iii) minimization of the number of flip-flops that need to be inserted in the circuit so that it becomes balanced. These algorithms extend the areas where retiming can be successfully applied.>

We consider the generalization of the min-cut partitioning problem in which the nodes of a circuit C are to be mapped to the vertices of a graph G, and the cost function to be minimized is the cost of associating the nets of C with the edges of G. Vijayan (see IEEE Trans. on Computers, vol. 40, no. 3, 1991) recently presented an iterative improvement heuristic for the case when G is a tree T. Let P be the number of pins, t be the number of nodes of T, and d be the maximum number of cells on a net of C. The running time of a pass of the heuristic given in Vijayan's paper is O(P/spl middot/t/sup 3/). For a graph G, this approach requires O(P/spl middot/t/sup 4/) time per pass. We present a heuristic for this particular problem which guarantees exactly the same partitions in time O(P/spl middot/t min/spl lcub/d,t/spl rcub/) per pass, for any graph G. The problem finds important applications in a variety of situations that arise in VLSI physical design, and in distributed systems.>

Linear Feedback Shift Registers (LFSRs) constitute a very efficient mechanism for generating pseudo-exhaustive or pseudo-random test sets for the built-in self-testing of digital circuits. However, a well-known problem with the use of LFSRs is the occurrence of linear dependencies in the generated patterns. In this paper, we show for the first time that the amount of linear dependencies can be controlled by selecting appropriate characteristic polynomials and reordering the LFSR cells. We identify a class of such polynomials which, by appropriate LFSR cell ordering, guarantees that a large ratio of linear dependencies cannot occur. Experimental results show significant enhancements on the fault coverage for pseudo-random testing and support the theoretical relation between minimization of linear dependencies and effective fault coverage.>

Test sets for built-in self-test (BIST) test pattern generation (TPG) are normally pseudorandom or truncated pseudoexhaustive. In this work, the authors propose a pseudorandom TPG scheme which is based on the idea of ordering appropriately the cells of a linear feedback shift register (LFSR) in order to control the percentage of linear dependencies in the generated patterns. The LFSR cell ordering is done prior to the circuit's layout phase, in accordance with the design for testability principles. The proposed pseudorandom scheme compares favorably with the use of truncated pseudoexhaustive test sets with or without cell reordering.>

In order for pseudo-exhaustive test pattern generation to be practical (time requirement less than 2/sup /spl omega//, /spl omega//spl les/20), two conditions must be satisfied: 1). The function of every element in the circuit must be controllable from no more than /spl omega/ inputs, and 2). The overall time to exercise all elements in the circuit must not exceed 2/sup /spl omega//. We address both these requirements by inserting a small number of bypass storage cells in the circuit under test and constructing appropriate Linear Feedback Shift Registers (LFSRs) to serve as built-in test pattern generators. Our method is applicable to both the gate-level and the module-level and achieves low hardware overhead by using a new graph model for the representation of the circuit and a metric quantity that couples requirements 1 and 2 above.>

A generally effective approach to the partial scan problem is to select flip-flops that break the cyclic structure of the circuit.A large number of techniques are based on this framework but they are all static, in the sense that the fllp-flops remain fixed on their original positions.In this paper, we present a method that rearranges the D flip-flops of a synchronous sequential circuit by retiming, so that the overhead of partial scan is minimized.Experiments on IS CAS'89 circuits show that retiming irnproves significantly both non-timing-driven and timing-driven partial scan.

Two partitioning problems on graphs are considered. In the first problem the nodes of a directed graph are partitioned into sets of sizes within prescribed ranges. If in(V/sub i/) is the sum of the weights on the incoming edges to set V/sub i/ in the partition, the goal is to minimize max/sub i/ (in(V/sub i/)). It is shown that the problem is NP-hard if the maximum set size is at least three or there is a constant number of sets of the same size. For the case where n and m are the number of nodes and the number of edges of the input graph, respectively, an O(m square root n) time algorithm is obtained when the maximum set size is two. The same problem is then considered on undirected graphs. It is shown that this partitioning problem is NP-hard for partitioning into equal-size sets, but polynomial-time algorithms are obtained when the maximum set size is a constant k. Applications of the problems are in layout, built-in self-test (BIST), and high-level synthesis.>

We present a method that can be used to test a sequential circuit pseudoexhaustively or almost pseudoexhaustively using LFSR/SRs as ATPGs with d-2/sup w/ test patterns, where d is the sequential depth and w is the input dependency limit. Our approach is based on the following techniques: (1) Use of LFSR/SRs as ATPGs (2) Rearrangement of the flip-flops of the circuit by retiming so that the hardware overhead for breaking all cycles and bounding the sequential depth is minimized. (3) Introduction of bypass storage cells (BSCs) so that no combinational element in the circuit has input dependence greater than a user-defined constant w. (4) Introduction of bypass delay cells (BDCs) so that the graph becomes more easily balanced or approximately balanced. Comparative experimental results indicate that our method behaves better than full-scan. It also outperforms a previous approach which, not only does not provide for on-chip TPG, but also requires O(q-f-2/sup 2/) test patterns, where q is the total number of primary or pseudoprimary outputs in the circuit and f is the total number of flip-flops.>

The generation of pseudoexhaustive test sets for the built-in self-test (BIST) of combinational circuits is addressed, using as a test pattern generator a simple linear feedback register (LFSR), structure, known as LFSR/SR. It is shown that particular orderings of the LFSR cells can significantly reduce the test set size. In addition, it is shown that an LFSR/SK designed with a particular cell ordering and the allowance of a marginal number of additional cells guarantees pseudoexhaustive test sets of the minimum size 2/sup w/, where w is the maximum input dependency limit of the circuit under test. Extensive experimentation on benchmark circuits and comparisons with the hardware overhead of other methods indicate the advantage of this approach.>

A self-contained method with very low bypass storage cell (BSC) overhead is presented. The method uses a graph model to represent the circuit under test. This unifying model makes the method applicable to both the gate level and the module level. A non-necessarily-partitioning technique reduces the number of BSCs considerably.>

All previously known algorithms for solving the multicommodity flow problem with capacities are based on linear programming.The best of these algorithms [14] uses a fast matrix multiplication algorithm and takes O(k25n2m5 log(nDU))time to find an approximate solution, where k is the number of commodities, n and m denote the number of nodes and edges in the network, D is the largest demand, and U is the largest edge capacity.Substantially more time is needed to find an exact solution.As a consequence, even multicommodit y flow problems with jnst a few commodities are believed to be much harder than single-commodity maximum-flow or minimum-cost flow problems.In thk paper, we describe the first polynomial-time combinatorial algorithms for approximately solving the multicommodity flow problem.The running time of our randomized algorithm is (up to ,log factors) the same as the time needed to solve k single-commodity flow problems, thus giving the surprising result that approximately computing a k-commodity maximum-flow is not much harder than computing about k single-commodity maximum-flows in isolation.In fact, we prove that a (simple) k-commodity flow problem can be approximately solved by approximately solving O(k log2 n) single-commodity minimum-cost flow problems.Our k-commodity algorithm runs in O(knm log4 n) time with high probability.We also describe a deterministic algorithm that uses an O(k)-factor more time.Given any multicommodit y flow problem as input, both rdgorithms are guaranteed to provide a feasible solution to a modified @ 1991