Energy efficiency and idle power consumption are becoming important parameters in the design of embedded systems that are realized with nanometer-scale CMOS devices. In nanometer-scale CMOS, Excessive quiescent power dissipation can lead to excessive heat generation and reliability issues. To address energy efficiency and idle power consumption, we present a novel Complementary Nano-Electro-Mechanical (CNEM) switch that we manufactured which operates with virtually zero leakage current, has 1 to 2 Volts operation voltage, >; 1 GHZ fundamental resonant frequency, and nanometer-scale footprint. These CNEM switches can be “dropped” in and hybridized with CMOS at the metallization or device levels to manage leakage current and power. In this paper, we present a hybrid CMOS/CNEMS FPGA. The hybrid FPGA is based on using the CNEM switching device as a replacement of CMOS devices in the switch and connection block components found in FPGA architectures. We analyzed the impact of the CNEM substitution on power and delay using VPR and the MCNC benchmark circuits. We present experimental results showing an average 98%, 85%, 71%, and 99.99% reduction in critical path delay, routing energy, total energy, leakage power when comparisons are made between FPGA design using pure CMOS (180nm technology and hybrid CNEMS and CMOS (180nm) technology.

Exact path delay fault (PDF) coverage calculation of large circuits with an exponential number of detectable PDFs requires exponential memory space. This often yields memory overflow in computations. One common approach to avoid memory overflow is to partition or virtually cut circuits into several subcircuits and to perform coverage calculation at the partition-level circuit. Partitioning reduces the number of PDFs to be stored in memory exponentially at the expense of losing considerable coverage. This paper describes an algorithm to improve the reported coverage value by recovering the lost PDFs up to a user-controlled degree (Delta), which is a function of the length of cut net sequences. The reported coverage monotonically increases as Delta increases: the exact coverage value is guaranteed when Delta is equal to the number of consecutive partitions on the longest path. Experimental results are provided for the ISCAS85 circuits that illustrate the trade-off between the computation time, the number of partitions, the values of Delta, and the reported coverage. The results indicate that as Delta and the number of partitions increase, the runtime does not increase after some point since the cost of set operations reduces as more partitions are created.

This article introduces a novel lookup table (LUT) and its usage in the configurable logic block (CLB) architectures for SRAM-based field-programmable gate array (FPGA) architectures. The proposed CLB allows sharing of SRAM tables of LUTs among NPN-equivalent functions to reduce the size of memories used for storing the functions and also reduces the number of configuration bits required. We measured many different characteristics of FPGAs using our new CLB architecture, including area, delay, routing, and power requirements. We experimentally found that for many different FPGA architectures, CLBs can share one-fourth of their SRAM tables between two basic logic elements (BLEs), which reduced both power consumption and area without negatively affecting routing or wirelength, and there was only a negligible increase in critical path delay of 0.27%. Specifically, we find that FPGAs consisting of CLBs with 16 BLEs and 34 inputs can be implemented with eight normal SRAMs and four SRAMs shared between two BLEs, for an overall reduction of four out of sixteen SRAM tables per CLB. With this new CLB architecture, we measured an approximate reduction in overall power consumption of 2% and an estimated reduction in area of 3%

Summary form only given. Acyclic partitioning of VLSI circuits is studied under area/delay, 1-0 size and communication constraints. In this paper, we define the path-delay-fault emulation problem which adds a new constraint, viz. path count constraint, to partitioning problem. We present two algorithms to solve the problem. The first algorithm decomposes a circuit into entirely-fanout-free cones (EFFC), and clusters them into partitions. The second one finds an intermediate partitioning solution with the partitioning algorithm ignoring path count constraint. Later, it applies the first algorithm to the partitions which violate the path count constraint. We implemented the first algorithm and measured its efficiency in terms of the number of resulting partitions, cut-cost, and time cost for ISCAS85 benchmarks.

We devise one exact and one pessimistic path delay fault (PDF) grading algorithms for combinational circuits. The first algorithm, an extension to the basic grading algorithm of Padmanaban, Michael, and Tragoudas (2003), does not store all of the detected PDFs during the course of grading, and, as a further improvement, it utilizes compressed representation of PDFs. These two techniques yield a space-and-time efficient algorithm. To enable grading of circuits with exponential number of paths, a circuit is first partitioned into a set of subcircuits. The second algorithm efficiently calculates the coverage of partitioned circuits. The former algorithm results in 50%-70% reduction in space and a speedup from 1.6 to 2.48 in ISCAS85 benchmarks. The time complexity of the latter algorithm is O(N/sup 2/) subset operations per test vector where N is the number of nets in the circuit.

SRAM-based field programmable gate arrays (FPGAs) have fixed numbers of wires, switches, and look-up tables. An application does not fully utilize all available components in a FPGA, e.g. wires. In this paper, we propose methods to improve reliability of less reliable operational interconnections by efficiently utilizing unused wires to mark errors dynamically. With these methods, we are able to improve the reliability of more than two-thirds of all interconnections in the studied MCNC benchmarks. As a result, the overall unreliability of operational interconnections decreases more than 20%.

In this paper, a randomized k-way graph partitioning algorithm is mapped onto reconfigurable hardware. The randomized algorithm relies on repetitive running of the same algorithm with different random number sequences to achieve the (near-) optimal solution. The run-time and hardware requirements of this reconfigurable solution per a random number sequence are O(|V|-K) cycles and O(|V|log|V|+|E|) gates and flip-flops, respectively. Performance is improved further at the expense of more hardware by running multiple copies of the partitioning algorithm with different random number sequences concurrently, and/or splitting a random sequence into subsequences and running them in parallel. Furthermore, in the context of this mapping, dynamic randomly configurable pattern-generation-based random number generation methods are introduced.

In this paper, a randomized k-way graph partitioning algorithm is mapped onto reconfigurable hardware. The randomized algorithm relies on repetitive running of the same algorithm with different random number sequences to achieve the (near-)optimal solution. The run-time and hardware requirements of this reconfigurable solution per a random number sequence are O(|V|-K) cycles and O(|V|log|V|+|E|) gates and flip-flops, respectively. Performance is improved further at the expense of more hardware by running multiple copies of the partitioning algorithm with different random number sequences concurrently, and/or splitting a random sequence into subsequences and running them in parallel. Furthermore, in the context of this mapping, dynamic randomly configurable pattern-generation-based random number generation methods are introduced.

In this paper, a new approach for generating test vectors that detects faults in combinational circuits is introduced. The approach is based on automatically designing a circuit which implements the D-algorithm, an automatic test pattern generation (ATPG) algorithm, specialized for the combinational circuit. Our approach exploits fine-grain parallelism by performing the following in three clock cycles: direct backward/forward implications, conflict checking, selecting next gate to propagate fault or to justify a line, decisions on gate inputs, and loading the state of the circuit after backup. In this paper, we show the feasibility of this approach in terms of hardware cost and speed and how it compares with software-based techniques.

In this paper, we introduce a new approach for locating and diagnosing faults in combinational circuits.The approach is based on automatically designing a circuit which implements a closest-match fault location algorithm specialized for the combinational circuit under diagnosis (CUD).This approach eliminates the need for large storage required by a software based fault diagnosis.In this paper, we show the approach's feasibility in terms of hardware resources, speed, and how it compares with software based techniques.

In this paper, a new approach for generating test vectors that detects faults in combinational circuits is introduced. The approach is based on automatically designing a circuit which implements the D-algorithm, an automatic test pattern generation (ATPG) algorithm, specialized for the combinational circuit. Our approach exploits fine-grain parallelism by performing the following in three clock cycles: direct backward/forward implications, conflict checking, selecting next gate to propagate fault or to justify a line, decisions on gate inputs, loading the state of the circuit after backup. In this paper, we show the feasibility of this approach in terms of speed, and how it compares with software based techniques.

In this paper, we introduce a new approach for locating and diagnosing faults in sequential circuits. The approach is based on automatically designing a circuit which implements a closest match fault location algorithm specialized for the sequential circuit under diagnosis. Our result shows an order of magnitude improvements in term of speeds over software based fault location.