This paper presents a group-based dynamic stuck-at fault diagnosis scheme intended for resistive random-access memory (ReRAM). Traditional static random-access memory, dynamic random-access memory, NAND, and NOR flash memory are limited by their scalability, power, package density, and so forth. Next-generation memory types like ReRAMs are considered to have various advantages such as high package density, non-volatility, scalability, and low power consumption, but cell reliability has been a problem. Unreliable memory operation is caused by permanent stuck-at faults due to extensive use of write- or memory-intensive workloads. An increased number of stuck-at faults also prematurely limit chip lifetime. Therefore, a cellular automaton (CA) based dynamic stuck-at fault-tolerant design is proposed here to combat unreliable cell functioning and variable cell lifetime issues. A scalable, block-level fault diagnosis and recovery scheme is introduced to ensure readable data despite multi-bit stuck-at faults. The scheme is a novel approach because its goal is to remove all the restrictions on the number and nature of stuck-at faults in general fault conditions. The proposed scheme is based on Wolfram’s null boundary and periodic boundary CA theory. Various special classes of CAs are introduced for 100% fault tolerance: single-length-cycle single-attractor cellular automata (SACAs), single-length-cycle two-attractor cellular automata (TACAs), and single-length-cycle multiple-attractor cellular automata (MACAs). The target micro-architectural unit is designed with optimal space overhead.

This work proposes a re-usability aware fault remapping scheme for multicore NUCA cache. It replicates data in non-reusable blocks to ensure full error coverage and minimum latency, by forming dynamic remapping clusters around the home tiles. Simulations in Multi2Sim 5.0 claim up to 18.64% increase in hit ratio and 20.79% decrease in latency in last-level cache over the existing techniques with 3.17% area, 5.35% leakage power and 3.34% dynamic power overheads.

Power consumption in the dense chip multiprocessors restricts the operational life of the battery operated devices. Voltage scaling for ensuring longer battery life exhibits hard and soft errors in cache. Hard faults, early detectable at boot time, are tractable but soft errors, being unpredictable in nature, are indeed hard to handle. Error correcting codes for soft error mitigation perform effectively for single event upsets (SEUs) but future technology nodes are anticipated to have significant multi bit upsets (MBUs) due to miniaturization which demands additional system level protection. Several redundancy based schemes have been proposed but none of them reported any scalable solution for shared NUCA cache in multicore and suffered from either low coverage due to partial redundancy or performance degradation due to capacity loss in full coverage. This work addresses both these issues by ensuring full error coverage with minimum cache bypass. Errors are detected using simple error detection technique like CRC and the dirty as well as reusable clean words are replicated either locally in same tile or globally to remote tiles to ensure complete error coverage. Word re-usability is calculated using a Markov Chain based novel re-usability prediction mechanism by analysing the cache access pattern. An invalidation strategy is applied that invalidates non-reusable words for reducing the vulnerable time to soft errors. A re-usability aware replacement policy is also designed that replaces the line with lowest re-usability, calculated at line level. The proposed technique has been evaluated in Multi2Sim 5.0 simulation framework with the benchmark programs in SPEC CPU2000 suite. The results indicate on average 83.33% decrease of vulnerability for integer benchmarks and 87.09% for floating point benchmarks, with full multi-bit error coverage, at the cost of 4.99% area, 5.54% dynamic power and 6.55% leakage power overheads with negligible performance penalty.

Reversible logic is emerging as a prospective logic design style for implementing ultra-low-power VLSI circuits. It promises low-power consuming circuits by nullifying the energy dissipation in irreversible logic. On the other hand, as a potential alternative to CMOS technology, Quantum-dot Cellular Automata (QCA) promises energy efficient digital design with high device density and high computing speed. The integration of reversible logic in QCA circuit is expected to be effective in addressing the issue of energy dissipation at nano scale regime. This work targets the design of reversible ALU (arithmetic logic unit) in QCA framework and proposes a new “Reversible QCA” (RQCA). The primary design focus is on optimizing the number of reversible gates, quantum cost and the garbage outputs that are the most important hindrances in realizing reversible logic. Besides optimization, the fault coverage capability of RQCA under missing/additional cell deposition defects is analysed. The scope of reversible logic is further outstretched by introducing a novel DFT (design for testability) architecture around the reversible ALU that reduces testing overhead. The performance of proposed ALU is evaluated, subjected to different faults, and is established to be more effective than the existing ALU.

Out of the several factors responsible for processor power dissipation, the branch prediction unit itself contributes to almost 10% of the overall processor power dissipation. The functioning of predictors is, therefore, to be more accurate especially for the CMPs (chip multiprocessors) with thousands of on-chip cores. This work reports that the design inaccuracy (fault) in a predictor can cause a huge power loss, even up to95%. The impact of faults causing additional loss in processor power is estimated to diagnose the faulty module of a predictor. This has been established through introduction of probable faults/design inaccuracies to each of the functional modules of a predictor. Exhaustive experimentations on the state-of-the-art predictors reveal that the amount of additional power loss during processor execution clearly points to the specific design inaccuracies. This effectively leads to identification of the faulty module of a predictor.

The data coherence in the cache systems of CMPs with thousands of processors are to be more accurate and reliable. This work proposes an effective solution to address this issue through introduction of highly efficient test logic with the cache controller. It is based on the modular structure of Cellular Automata (CA) and a special class of CA referred to as the SACA (single length single cycle attractor CA) has been introduced to identify the inconsistencies in cache line states of the processors' private caches. The hardware implementation of the proposed test logic can ensure quick verification of cache inconsistencies in CMPs. The proposed design eliminates the requirement of huge storage as well as the complex data structures commonly used to verify the data coherency in a multiprocessor system.

In CMPs (Chip Multi-Processors) with thousand of processors, the issue of power dissipation has emerged out as a matter of serious concern. Out of the several factors responsible for processor power dissipation, the branch prediction unit of a modern processor itself contributes to almost 10% of the overall power dissipation. It points to the fact that the functioning of predictors is to be more accurate as well as power efficient. In this work, we analyze the impact of inaccurate/faulty design on the branch predictors' power dissipation while realizing speculative execution. This issue has been addressed through introduction of probable faults, commonly arise out of the design inaccuracies, in a predictor that lead to mis-speculation. The evaluation of fault effect (design inaccuracy) is done by estimating the additional power consumed by a pipelined processor. The detail analysis reveals that the design inaccuracy/fault in a predictor can cause a huge power loss, even up to 95%.

In WSN (Wireless Sensor Network), the sensor nodes may become faulty due to low battery power or some other physical defects. The faulty nodes may badly affect the network performance while trying to reach an agreement on an event. This effectively leads to deviation from the desired outcome, ineffective utilization of network bandwidth and unproductive computational overhead. In this work, we propose a CA (Cellular Automata) based scheme that can efficiently identify the faulty nodes of a WSN in operation. The scheme is developed around the SACA (Single Attractor CA) to enable diagnosis of the network region with affected nodes, without consuming massive computational overhead and bandwidth.

This work proposes a testable QCA (Quantum-Dot Cellular Automata) logic gate (UQCALG) realizing the universal functions. The design of UQCALG is based on the Coupled Majority Minority (CMVMIN) QCA structure with the target to reduce wire crossings as well as the number of clock cycles required to operate a QCA circuit. The characterization of defects in such design leads to synthesis of a test block, realized with the majority and minority voters, that ensures the desired testability of a circuit. The experimental designs establish that the UQCALG can result in cost effective design of testable QCA logic circuits that may not be possible with conventional ULG (Universal Logic Gate).

The wireless sensor network (WSN) encounters resource restrictions such as low computational power, reduced bandwidth & limited power resource and it demands efficient management of such resources. This work proposes a scheme (SSMCA), developed around the cellular automata (CA), for efficient management of battery power in sensor nodes with optimized cost of implementation. Each sensor node is assumed to be equipped with a segment of the CA, selected for the network that defines the state (active/standby) of the node at next time instant. The CA based management of status (active/standby) of a node ensures the reduced battery power consumption in nodes of a cluster as well as in the whole sensor network. As a segment of the CA is planted within a node, the additional cost for implementation of the proposed scheme is marginal. The simulation results establish that the SSMCA can better utilize the resources and ensure a maximally covered energy efficient sensor network.

This work reports an efficient solution of reaching agreement in a distributed system. The proposed solution operates on a system with faulty processes that take arbitrary finite time before crash. It is set to tolerate more faults compared to the classical Byzantine simultaneously reducing the volume of message exchanges. The introduction of Cellular Automata (CA) based network partitioning scheme minimizes the message exchange overhead while reaching an agreement. The simulation results establish that the proposed solution significantly reduces the message complexity as well as enhances the fault-tolerance of a system. The solution proposed is also found to be effective for the self-configuring, easily deployable, infrastructure free Mobile-Ad-Hoc-Network (MANET).

This paper reports an efficient synthesis scheme for pseudorandom pattern generators (PRPGs) of arbitrary length. The$n$-bit PRPG, synthesized in linear time$(O(n))$, generates quality pseudorandom patterns leading to a highly efficient test logic for the very-large-scale integration (VLSI) circuit. The cascadable structure of proposed$n$-cell PRPG is utilized to construct the$(n+1)$-cell PRPG, in two time steps, without sacrificing the pseudorandomness quality. This eases the design of on-chip test pattern generators for the system-on-a-chip implementing multiple cores. It avoids the requirement of disparate test hardware for different cores and thereby ensures drastic reduction in the cost of test logic. The effective characterization of nonlinear cellular automata (CA) provides the foundation of such a design. Extensive experimentation confirms the better efficiency of the proposed test structure compared to that of the conventional designs, developed around maximal length CA/linear feedback shift register of$O(n^{3})$complexity.

This paper reports synthesis of a built-in self-test logic for the cores integrated into an SoC. The test logic is developed around a nonlinear cellular automata (CA). The CA based scalable PRPG, synthesized in linear time (O(n)), enables the design of such a highly efficient test logic. The cascadable structure of the PRPG is utilized to construct the on-chip Test Pattern Generators (TPGs) for the SoC implementing multiple cores. It avoids the requirement of disparate test hardware for the SoC cores and thereby ensures drastic reduction in the cost of test logic. Extensive experimentation confirms the better efficiency of the proposed test structure than that of the conventional designs, developed around maximal length CA/LFSR.

This work targets modeling traffic flow in roads of a congested city. The cellular automata (CA) have been configured for such modeling. The urban traffic models, in general, concentrate on low traffic density. The inabilities of traditional models to address the issues arise out of heavy traffic in crowded cities of third world countries are properly addressed in the proposed elementary CA based model. The effectiveness of the model is verified considering the traffic in Kolkata. It is established that the model can fairly reproduce various traffic conditions as found empirically. Further, the proposed model succeeds the limitations of traffic flow models in congestion and also reproduces the empirical results.

This work reports an efficient solution for reaching agreement (consensus) among the processes of a distributed system. The better efficiency is achieved through early disposal of faulty processes while approaching for a consensus. The introduced network partitioning scheme further facilitates the progress by reducing the message exchange overhead. Simulation results establish that the proposed solution significantly reduces the message exchange complexity, in comparison to the schemes reported so far, simultaneously ensuring the fault-tolerance ability of a system as that of the known best results.

This paper presents a C-testable technique for detecting transition faults with 100% fault coverage in the polynomial basis (PB) bit parallel (BP) multiplier circuits over GF(2m). The proposed technique requires only 10 vectors, which is independent of multiplier size, at the cost of 6% (avg.) extra hardware and three control pins. The proposed constant test vectors which are sufficient to detect both the transition and stuck-at faults in the multiplier circuits can be derived directly without any requirement of an ATPG tool. As the GF(2m) multipliers have found critical applications in public key cryptography and need secure internal testing, a built-in self-test (BIST) circuit is proposed for generating test patterns internally. This obviates the need of having three extra pins for the control inputs and also provides public-key security in cryptography. Area and delay of the testable circuit are analyzed using 0.18mum CMOS technology library from UMC

QCA (quantum dot cellular automata) are projected as the replacement of state-of-the-art CMOS designs. The wide acceptance of QCA based design of logic circuits demands analysis and estimation of defect coverage in such circuits. Conventional single stuck-at fault model has been commonly employed to identify the majority of defects at the logic level. However, stuck-at fault model may not fully capture the defects in QCA based designs but approximates the defects in such designs. This work evaluates the effectiveness of such state-of-the-art VLSI test mechanisms, and investigates the possibility of more defect coverage through N-detectability in QCA designs. An experimental set up has been created to study the test quality of such designs subject to a PRPG (pseudo-random-pattern generator). The results shown in the paper point to the fact that the conventional test technique for CMOS designs is also effective in QCA based designs

Sensor network has been identified as the most important technology for the next century. Despite of its potential application, wireless sensor network encounters resource restrictions such as low computational power, reduced bandwidth and specially limited power resource. This work reports a network monitoring protocol to provide a logical topology for an energy efficient maximally covered ad-hoc sensor network (Eemca). It is developed around the regular structure of 1-dimensional cellular automata. The simulation results establish that the monitoring of sensor nodes with the proposed technique shows better utilization of the resources that effectively leads to an energy efficient maximally covered sensor network topology.

This paper reports a scheme for cost optimal design of PRPG, built around nonlinear cellular automata (CM). The characterization of 3-neighborhood CA rules provides the foundation of designing the n-bit PRPG in linear time. The GA (genetic algorithm) framework proposed to evolve the CA results in a minimal cost PRPG structure, in terms of area overhead and delay

This paper reports an efficient state encoding scheme for synthesis of large FSMs with enhanced BIST quality. A metric, referred to as degree-of-freedom (DOF) [5] in FSM states has been employed to quantify the BIST quality. Analysis of DOF enables efficient encoding of FSM states and gives solution to the problem of handling unreachable/ hard-to-exit/ hardto- reach state codes of an FSM. The synthesis of a large FSM is realized through decomposition. DOF analysis for the individual component sub-FSM states is done to reduce the complexity of synthesis. A scheme is proposed for encoding the sub-FSM states that significantly improves testability of the synthesized resultant FSM, displaying the terminal behavior as the original FSM.

This work presents an efficient scheme for processing queries on location dependent data in a cellular mobile environment. It is developed around the theory of cellular automata (CA) which act as a search engine and implements computation for query processing that either can be done at the network base station or at the mobile unit depending on the requirement specified by the service provider. The scheme also ensures efficient handling of disconnection problem due to hand-off. The experimental results confirm that the overhead & delay, query processing, in the proposed scheme is much less than that of the existing schemes.

This paper reports a fault diagnosis scheme for very large scale integrated (VLSI) circuits. A special class of cellular automata (CA) referred to as multiple attractor CA (MACA) is employed for the design. State transition behavior of MACA has been analyzed to build a model that can efficiently classify the test responses of a VLSI circuit to diagnose its faulty subcircuit. The MACA-based model, in effect, provides an implicit storage for voluminous test response data and replaces the traditional fault dictionary used for diagnosis of VLSI circuits. The proposed diagnosis scheme employs significantly lesser memory to store the MACA parameters and performs faster diagnosis. Experimental results establish the efficiency of the model in respect of memory overhead, execution speed and percentage of diagnosis.

This paper reports the design of an efficient test set generator (TSG) for VLSI circuit. It is built around the regular structure of cellular automata (CA) employing nonlinear CA rules and targets detection of hard-to-detect pseudo-random pattern resistant faults. The optimal design of TSG structure is achieved with the framework of SA (simulated annealing) to ensure proper selection of CA rules for TSG cells. Efficiency of TSG in comparison to linear CA/LFSR based designs is validated through experimentation.

This paper reports an efficient design of test pattern generators (TPGs) for a chip having multiple cores. It is built around nonlinear cellular automata (CA) based pseudo-random pattern generator (PRPG). The modular and cascadable structure of proposed n-cell PRPG can be utilized to construct the (n+1)-cell PRPG without sacrificing the pseudo-randomness quality. The efficiency of such a scalable PRPG structure is demonstrated in designing the on-chip TPGs for a VLSI chip implementing multiple cores.

This work reports the design of a fool proof on-chip test pattern generator (TPG) for very large scale integration circuits. The TPG is designed to generate pseudorandom test patterns without a given prohibited pattern set (PPS). It ensures desired pseudorandom quality of the generated test patterns and maintains fault coverage close to the figures achieved with a conventional maximal length linear feedback shift register/cellular automaton (CA)-based TPG. The theory of vector subspace generated by a CA (Chaudhuri, 1997) has provided the foundation of this design. The proposed TPG does not incur any additional cost for the avoidance of PPS.

This paper reports a cellular automata (CA) based model of associative memory. The model has been evolved around a special class of CA referred to as generalized multiple attractor cellular automata (GMACA). The GMACA based associative memory is designed to address the problem of pattern recognition. Its storage capacity is found to be better than that of Hopfield network. The GMACA are configured with nonlinear CA rules that are evolved through genetic algorithm (GA). Successive generations of GA select the rules at the edge of chaos. The study confirms the potential of GMACA to perform complex computations like pattern recognition at the edge of chaos.

This paper introduces a novel BIST-quality metric termed as the FiF -- FoF (Fan-in-Factor & Fan-out-Factor) defined on FSM-states. Based on the FiF -- FoF analysis, an efficient scheme is presented that ensures all state codes appear with uniform likelyhood at the present state (PS) lines during the test phase. This results in higher fault efficiency in a BIST structure. Experimental results on MCNC benchmarks show that the scheme improves fault efficiency of sequential circuits significantly, with marginal area overhead.

This paper reports an efficient BIST solution for VLSI circuits. The solution is based on an onchip Pseudo-Random Pattern Generator (PRPG). The test solution guarantees non-issuence of the test patterns declared prohibited to a CUT (Circuit Under Test). It has been developed around non-linear Cellular Automata (CA) and provides a linear time solution of designing an n-bit PRPG. Experimental results confirm the enhanced pseudo-random quality of the test patterns due to application of non-linear CA rules.

This paper presents an efficient BIST scheme with low power consumption for sequential circuits. The BIST structure is obtained by using a ghost-FSM. A multiobjective genetic algorithm (MOGA) is employed to optimize the twin criteria of BIST quality and power consumption of the resultant circuit simultaneously. The scheme ensures enhancement of fault coverage along with minimization of power overhead of the BISTed circuits. Experimental results on MCNC benchmarks confirm the effectiveness of the proposed scheme to produce circuits with improved fault efficiency along with lower power consumption.

This paper reports the design of an on-chip Test Pattern Generator (TPG) for VLSI circuits that avoids generation of a given Prohibited Pattern Set (PPS). The design ensures desired pseudo-random quality of the test patterns generated while ensuring fault coverage close to the figures achieved with a typical Pseudo Random Pattern Generator (PRPG) designed around maximal length LFSR/CA. The theoretical framework of CA has provided the foundation of this work. A GA based evolution scheme is employed to achieve the desired TPG developed over the theory of cellular automata.

This paper reports an efficient technique of evolving Cellular Automata (CA) as an associative memory model. The evolved CA termed as GMACA (Generalized Multiple Attractor Cellular Automata), acts as a powerful pattern recognizer. Detailed analysis of GMACA rules establishes the fact that the rule subspace of the pattern recognizing CA lies at the edge of chaos — believed to be capable of executing complex computation.

This paper introduces the concept of hierarchical cellular automata (HCA). The theory of HCA is developed over the Galois extension field GF(2(pqr..)), where each cell of the CA can store and process a symbol in the extension field GF (2(pqr..)). The hierarchical field structure of GF(2(pqr..)) is employed for design of an HCA-based test pattern generator (HCATPG). The HCATPG is ideally suited for testing very large scale integration circuits specified in hierarchical structural description. Experimental results establish the fact that the HCATPG achieves higher fault coverage than that which could be achieved with any other test structures. The concept of percentile improvement in fault coverage is introduced to have a realistic assessment of fault coverage achieved with the proposed RCATPG.

This paper presents an efficient BIST solution for VLSI circuit testing based on GF(2p) CA (Cellular automata on an extended Galois Field). The novel architecture of GF(2p)) CA permits the BIST structure to be highly customized to the circuit under test (CUT). A methodology has been proposed to optimize the design of GF(2p) CA structure to maximize the fault coverage in a given CUT. In addition, an innovative scheme based on logic folding is presented to reduce the BIST overhead and make it more effective for large circuits.

This paper uses the hierarchical structure of a VLSI circuit to design an efficient diagnosis scheme. A special class of non-group GF(2/sup p/) CA referred to as multiple attractor cellular automata (MACH) is introduced to diagnose the faulty block of a circuit under test (CUT). The scheme employs significantly lesser memory and performs faster diagnosis than the existing methods reported so far. Experimental results validate the efficiency of the proposed scheme in terms of diagnostic resolution and execution speed along with significant reduction of memory.

Designing a BIST structure for sequential circuits is rather a complex problem as some states remain unreachable and some act as the sink under any input sequence. This paper reports an efficient scheme to provide uniform mobility, referred to as degree of freedom, in a sequential machine by enhancing the reachability as well as the emittability of the states. The uniform mobility of states ensures higher fault efficiency in a BIST structure of the circuit. Moreover, as a non-scan scheme, the technique provides lower test application time and at-speed testing.