This paper presents the Quick Error Detection (QED) technique for systematically creating families of post-silicon validation tests that quickly detect bugs inside processor cores and uncore components (cache controllers, memory controllers, and on-chip interconnection networks) of multicore system on chips (SoCs). Such quick detection is essential because long error detection latency, the time elapsed between the occurrence of an error due to a bug and its manifestation as an observable failure, severely limits the effectiveness of traditional post-silicon validation approaches. QED can be implemented completely in software, without any hardware modification. Hence, it is readily applicable to existing designs. Results using multiple hardware platforms, including the Intel® Core™ i7 SoC, and a state-of-the-art commercial multicore SoC, along with simulation results using an OpenSPARC T2-like multicore SoC with bug scenarios from commercial multicore SoCs demonstrate: 1) error detection latencies of post-silicon validation tests can be very long, up to billions of clock cycles, especially for bugs inside uncore components; 2) QED shortens error detection latencies by up to nine orders of magnitude to only a few hundred cycles for most bug scenarios; and 3) QED enables up to a fourfold increase in bug coverage.

Existing post-silicon validation techniques are generally ad hoc, and their cost and complexity are rising faster than design cost. Hence, systematic approaches to post-silicon validation are essential. Our research indicates that many of the bottlenecks of existing post-silicon validation approaches are direct consequences of very long error detection latencies. Error detection latency is the time elapsed between the activation of a bug during post-silicon validation and its detection or manifestation as a system failure. In our earlier papers, we created the Quick Error Detection (QED) technique to overcome this significant challenge. QED systematically creates a wide variety of post-silicon validation tests to detect bugs in processor cores and uncore components of multi-core System-on-Chips (SoCs) very quickly, i.e., with very short error detection latencies. In this paper, we present an overview of QED and summarize key results: 1. Error detection latencies of “typical” post-silicon validation tests can range up to billions of clock cycles. 2. QED shortens error detection latencies by up to 6 orders of magnitude. 3. QED enables 2- to 4-fold improvement in bug coverage. QED does not require any hardware modification. Hence, it is readily applicable to existing designs.

This paper presents techniques for designing nanoelectromechanical relay-based logic circuits using six-terminal relays that behave as universal logic gates. With proper biasing, a compact 2-to-1 multiplexer can be implemented using a single six-terminal relay. Arbitrary combinational logic functions can then be implemented using well-known binary decision diagram (BDD) techniques. Compared to a CMOS-style implementation using four-terminal relays, the BDD-based implementation can result in lower area without major impact on performance metrics such as delay, and energy (when the relays are scaled to small dimensions). Although it is possible to implement any combinational circuit with a single mechanical delay, the relay count can be significantly reduced for complex logic functions by allowing multiple mechanical delays.

We present a new technique for systematically creating postsilicon validation tests that quickly detect bugs in processor cores and uncore components (cache controllers, memory controllers, on-chip networks) of multi-core System on Chips (SoCs). Such quick detection is essential because long error detection latency, the time elapsed between the occurrence of an error due to a bug and its manifestation as an observable failure, severely limits the effectiveness of existing post-silicon validation approaches. In addition, we provide a list of realistic bug scenarios abstracted from "difficult" bugs that occurred in commercial multi-core SoCs. Our results for an OpenSPARC T2-like multi-core SoC demonstrate: 1. Error detection latencies of "typical" post-silicon validation tests can be very long, up to billions of clock cycles, especially for bugs in uncore components. 2. Our new technique shortens error detection latencies by several orders of magnitude to only a few hundred cycles for most bug scenarios. 3. Our new technique enables 2-fold increase in bug coverage. An important feature of our technique is its software-only implementation without any hardware modification. Hence, it is readily applicable to existing designs.

Digital signal processing applications often require the computation of linear systems. These computations can be considerably expensive and require optimizations for lower power consumption, higher throughput, and faster response time. Unfortunately, system designers do not have the necessary tools to take advantage of the wide flexibility in ways to evaluate these expressions. Therefore, we address the problem of efficiently computing a set of linear systems through a tool, Xquasher, that is developed by us to enable elimination of large common subexpression from expressions with an arbitrary number of terms. Xquasher provides a methodology for efficient computation of both single and multiple linear expressions. We also introduce the concept of power set encoding which helps us to provide an effective optimization method and achieves significant improvement over previously published work. Our tool provides optimized designs with 15% less area with the cost of 3% increase in delay by reducing number of additions on average by 45%.

This paper addresses the problem of low-power fanout optimization for near-continuous-size inverter libraries. It is demonstrated that because of neglecting short-circuit current, previous techniques proposed to optimize the area of a fanout tree may result in excessive power consumption. This paper describes how the problem of low-power fanout optimization can be reduced to inverter-chain optimization problem and formulates the minimization of the total power consumption of an inverter chain as a geometric program. Moreover, it describes an efficient method to minimize the total power consumption of a fanout tree by using multiple-channel-length (multi-LGate) and multiple-threshold-voltage (multi-Vt) techniques. Experimental results show that the proposed technique can reduce the power consumption of the fanout trees by an average of 11.17% over SIS fanout-optimization program.

The design of a suitable power gating (e.g., multithreshold or super cutoff CMOS) structure is an important and challenging task in sub-90-nm very large scale integration (VLSI) circuits where leakage currents are significant. In designs where the mode transitions are frequent, a significant amount of energy is consumed to turn on or off the power gating structure. It is thus desirable to develop a power gating solution that minimizes the energy consumed during mode transitions. This paper presents such a solution by recycling charge between the virtual power and ground rails immediately after entering the sleep mode and just before wakeup. The proposed method can save up to 43% of the dynamic energy wasted during mode transition while maintaining the wakeup time of the original circuit. It also reduces the peak negative voltage value and the settling time of the ground bounce.

Aggressive CMOS scaling results in low threshold voltage and thin oxide thickness for transistors manufactured in deep submicrometer regime. As a result, reducing the subthreshold and tunneling gate leakage currents has become one of the most important criteria in the design of VLSI circuits. This paper presents a method based on dual-Vtand dual-Toxassignment to reduce the total leakage power dissipation of static random access memories (SRAMs) while maintaining their performance. The proposed method is based on the observation that read and write delays of a memory cell in an SRAM block depend on the physical distance of the cell from the sense amplifier and the decoder. Thus, the idea is to deploy different configurations of six-transistor SRAM cells corresponding to different threshold voltage and oxide thickness assignments for the transistors. Unlike other techniques for low-leakage SRAM design, the proposed technique incurs neither area nor delay overhead. In addition, it results in a minor change in the SRAM design flow. The leakage saving achieved by using this technique is a function of the values of the high threshold voltage and the oxide thickness, as well as the number of rows and columns in the cell array. Simulation results with a 65-nm process demonstrate that this technique can reduce the total leakage power dissipation of a 64 times 512 SRAM array by 33% and that of a 32 times 512 SRAM array by 40%.

A downside of using Multi-Threshold CMOS (MTCMOS) technique for leakage reduction is the energy consumption during transitions between sleep and active modes. Previously, a charge recycling (CR) MTCMOS architecture was proposed to reduce the large amount of energy consumption that occurs during the mode transitions in powergated circuits. Considering the RC parasitics of the virtual ground and VDD lines, proper sizing and placement of charge-recycling transistors is key to achieving the maximum power saving. In this paper, we show that the sizing and placement problems of charge-recycling transistors in CR-MTCMOS can be formulated as a linear programming problem, and hence, can be efficiently solved using standard mathematical programming packages. The proposed sizing and placement techniques allow us to employ the CR-MTCMOS solution in large row-based standard cell layouts while achieving nearly the full potential of this power-gating architecture, i.e., we achieve 44% saving in switching energy due to the mode transition in CR-MTCMOS compared to standard MTCMOS.

The large magnitude of supply/ground bounces, which arise from power mode transitions in power gating structures, may cause spurious transitions in a circuit. This can result in wrong values being latched in the circuit registers. We propose a design methodology for limiting the maximum value of the supply/ground currents to a user-specified threshold level while minimizing the wake up (sleep to active mode transition) time. In addition to controlling the sudden discharge of the accumulated charge in the intermediate nodes of the circuit through the sleep transistors during the wake up transition, we can eliminate short circuit current and spurious switching activity during this time. This is, in turn, achieved by reducing the amount of charge that must be removed from the intermediate nodes of the circuit and by turning on different parts of the circuit in a way that causes a uniform distribution of current over the wake up time. Simulation results show that, compared to existing wakeup scheduling methods, the proposed techniques result in a 1-2 orders of magnitude improvement in the product of the maximum ground current and the wake up time

Designing an energy efficient power gating structure is an important and challenging task in Multi-Threshold CMOS (MTCMOS) circuit design. In order to achieve a very low power design, the large amount of energy consumed during mode transition in MTCMOS circuits should be avoided. In this paper, we propose an appropriate charge recycling technique to reduce energy consumption during the mode transition of MTCMOS circuits. The proposed method can save up to 46% of the mode transition energy while, in most cases, maintaining, or even improving, the wake up time of the original circuit. It also reduces the peak negative voltage value and the settling time of the ground bounce.

Aggressive CMOS scaling results in low threshold voltage and thin oxide thickness for transistors manufactured in very deep submicron regime. As a result, reducing the subthreshold and gate-tunneling leakage currents has become one of the most important criteria in the design of VLSI circuits. This paper presents a method based on dual-Vtand dual-Toxassignment to reduce the total leakage power dissipation of SRAMs while maintaining their performance. The proposed method is based on the observation that the read and write delays of a memory cell in an SRAM block depend on the physical distance of the cell from the sense amplifier and the decoder. Thus, the idea is to deploy different types of six-transistor SRAM cells corresponding to different threshold voltage and oxide thickness assignments for the transistors. Unlike other techniques for low-leakage SRAM design, the proposed technique incurs neither area nor delay overhead. In addition, it results in a minor change in the SRAM design flow. Simulation results with a 65 nm process demonstrate that this technique can reduce the total leakage power dissipation of a 64 Kb SRAM by more than 50%

Carry save adder (CSA) trees are commonly used for high speed implementation of multi-operand additions. We present a method to reduce the number of the adders in CSA trees by extracting common three-term subexpressions. Our method can optimize multiple CSA trees involving any number of variables. This optimization has a significant impact on the total area of the synthesized circuits, as we show in our experiments. To the best of our knowledge, this is the only known method for eliminating common subexpressions in CSA structures. Since extracting common subexpressions can potentially increase delay, we also present a delay aware extraction algorithm that takes into account the different arrival times of the signals

This paper addresses the problem of low-power fanout optimization. We show that due to neglecting short-circuit current, previous analytical techniques proposed to optimize the area of a fanout tree may result in excessive power consumption. This shows to achieve a low-power fanout tree, an accurate power consumption model should be used as the objective function. Moreover, we propose an efficient method to minimize the total power consumption of a fanout tree by using MTCMOS and Multi-Vt techniques. Experimental results show that depending on the activity factor of the circuit, the proposed technique can reduce the power consumption of the fanout tree 18% to 45%.

Polynomial expressions are frequently encountered in many application domains, particularly in signal processing and computer graphics. Conventional compiler techniques for redundancy elimination such as common subexpression elimination (CSE) are not suited for manipulating polynomial expressions, and designers often resort to hand optimizing these expressions. This paper leverages the algebraic techniques originally developed for multilevel logic synthesis to optimize polynomial expressions by factoring and eliminating common subexpressions. The proposed algorithm was tested on a set of benchmark polynomial expressions where savings of 26.7% in latency and 26.4% in energy consumption were observed for computing these expressions on the StrongARM SA1100 processor core. When these expressions were synthesized in custom hardware, average energy savings of 63.4% for minimum hardware constraints and 24.6% for medium hardware constraints over CSE were observed

This paper presents a novel technique to reduce the number of operations in Multiplierless implementations of linear DSP transforms, by iteratively eliminating two-term common subexpressions. Our method uses a polynomial transformation of linear systems that enables us to eliminate common subexpressions consisting of multiple variables. Our algorithm is fast and produces the least number of additions/subtractions compared to all known techniques. The synthesized examples show significant reductions in the area and power consumption.

The large magnitude of supply/ground bounces, which arise from power mode transitions in power gating structures, may cause spurious transitions in a circuit. This can result in wrong values being latched in the circuit registers. We propose a design methodology for limiting the maximum value of the supply/ground currents to a user-specified threshold level while minimizing the wake up (sleep to active mode transition) time. In addition to controlling the sudden discharge of the accumulated charge in the intermediate nodes of the circuit through the sleep transistors during the wake up transition, we can eliminate short circuit current and spurious switching activity during this time. This is in turn achieved by reducing the amount of charge that must be removed from the intermediate nodes of the circuit and by turning on different parts of the circuit in a way that causes a uniform distribution of current over the wake up time. Simulation results show that, compared to existing wakeup scheduling methods, the proposed techniques result in a one to two orders of magnitude improvement in the product of the maximum ground current and the wake up time.

This paper presents a technique for eliminating redundant cache-tag and cache-way accesses to reduce power consumption. The basic idea is to keep a small number of most recently used (MRU) addresses in a memory address buffer (MAB) and to omit redundant tag and way accesses when there is a MAB-hit. Since the approach keeps only tag and set-index values in the MAB, the energy and area overheads are relatively small even for a MAB with a large number of entries. Furthermore, the approach does not sacrifice the performance. In other words, neither the cycle time nor the number of executed cycles increases. The proposed technique has been applied to the Fujitsu VLIW processor (FR-V) and its power saving has been estimated using NanoSim. Experiments for 32 kB 2-way set associative caches show the power consumption of I-cache and D-cache can be reduced by 40% and 50%, respectively.

Yield improvement through exploiting fault-free sections of defective chips is a well-known technique (Koren and Singh (1990) and Stapper et al. (1980)). The idea is to partition the circuitry of a chip in a way that fault-free sections can function independently. Many fault tolerant techniques for improving the yield of processors with a cache memory have been proposed. In this paper, we propose a defect-aware code placement technique which offsets the performance degradation of a processor with a defective cache memory. To the best of our knowledge, this is the first compiler-based technique which offsets the performance degradation due to cache defects. Experiments demonstrate that the technique can compensate the performance degradation even when 5% of cache lines are faulty. In some cases the technique was able to offset the impact even in presence of 25% faulty cache-lines.

This paper addresses the problem of low-power fanout optimization with multiple threshold voltage inverters. Introducing splitting and merging conversions that preserve delay, power, and input capacitance, the fanout tree is converted to a set of inverter chains and for each chain the optimal sizes and threshold voltages are determined. Experimental results show that using this technique, the power dissipation of fanout tree is reduced by an average of 33% for a state-of-the-art CMOS technology.

This paper proposes a non-uniform cache architecture for reducing the power consumption of memory systems. The non-uniform cache allows having different associativity values (i.e., the number of cache-ways) for different cache-sets. An algorithm determines the optimum number of cache-ways for each cache-set and generates object code suitable for the non-uniform cache memory. The paper also proposes a compiler technique for reducing redundant cache-way accesses and cache-tag accesses. Experiments demonstrate that our technique can reduce the power consumption of memory systems by up to 76% compared to the best result achieved by the conventional method

Polynomial expressions are used to compute a wide variety of mathematical functions commonly found in signal processing and graphics applications, which provide good opportunities for optimization. However existing compiler techniques for reducing code complexity such as common subexpression elimination and value numbering are targeted towards general purpose applications and are unable to fully optimize these expressions. This work presents algorithms to reduce the number of operations to compute a set of polynomial expression by factoring and eliminating common subexpressions. These algorithms are based on the algebraic techniques for multi-level logic synthesis. Experimental results on a set of benchmark applications with polynomial expressions showed an average of 42.5% reduction in the number of multiplications and 39.6% reduction in the number of clock cycles for computation of these expressions on the ARM processor core, compared to common subexpression elimination.

In this paper, we introduce a class of irredundant low-power techniques for encoding instruction or data source words before they are transmitted over buses. The key idea is to partition the source-word space into a number of sectors with unique identifiers called sector heads. These sectors can, for example, correspond to address spaces for the code, heap, and stack segments of one or more application programs. Each source word is then dynamically mapped to the appropriate sector and is encoded with respect to the sector head. In general, the sectors may be determined a priori or can dynamically be updated based on the source word that was last encountered in that sector. These sector-based encoding techniques are quite effective in reducing the number of interpattern transitions on the bus, while incurring rather small power and delay overheads. For a computer system without an on-chip cache, the proposed techniques decrease the switching activity of data address and multiplexed address buses by an average of 55% to 67%, respectively. For a system with on-chip cache, up to 55% transition reduction is achieved on a multiplexed address bus between the internal cache and the external memory. Assuming a 10 pF per line bus capacitance, we show that, by using the proposed encoding techniques, a power reduction of up to 52% can be achieved for an external data address bus and 42% for the multiplexed bus between cache and main memory.

The first part of this paper describes two runtime mechanisms for reducing the leakage current of a CMOS circuit. In both cases, it is assumed that the system or environment produces a "sleep" signal that can be used to indicate that the circuit is in a standby mode. In the first method, the "sleep" signal is used to shift in a new set of external inputs and pre-selected internal signals into the circuit with the goal of setting the logic values of all of the internal signals so as to minimize the total leakage current in the circuit. This minimization is possible because the leakage current of a CMOS gate is strongly dependent on the input combination applied to its inputs. In the second method, nMOS and pMOS transistors are added to some of the gates in the circuit to increase the controllability of the internal signals of the circuit and decrease the leakage current of the gates using the "stack effect". This is, however, done carefully so that the minimum leakage is achieved subject to a delay constraint for all input-output paths in the circuit. In both cases, Boolean satisfiability is used to formulate the problems, which are subsequently solved by employing a highly efficient SAT solver. Experimental results on the combinational circuits in the MCNC91 benchmark suite demonstrate that it is possible to reduce the leakage current in combinational circuits by an average of 25% with only a 5% delay penalty. The second part of this paper presents a design technique for applying the minimum leakage input to a sequential circuit. The proposed method uses the built-in scan-chains in a VLSI circuit to drive it with the minimum leakage vector when it enters the sleep mode. The use of these scan registers eliminates the area and delay overhead of the additional circuitry that would otherwise be needed to apply the minimum leakage vector to the circuit. Experimental results on the sequential circuits in the MCNC91 benchmark suit show that, by using the proposed method, it is possible to reduce the leakage by an average of 25% with practically no delay penalty.

This paper introduces a new approach for minimizing power dissipation on the memory address bus. The proposed approach relies on the availability of smart memories that have certain awareness of the instruction format of one or more architectures. Based on this knowledge, the memory calculates or predicts the instruction and data addresses. Hence, not all addresses are sent from the processor to the memory. This, in turn, significantly reduces the activity on the memory bus. The proposed method can eliminate up to 97% of the transitions on the instruction address bus and 75% of the transitions on the data address bus with a small hardware overhead. The actual power savings of 85% for the instruction bus and 64% for the data bus were achieved for a per-line bus capacitance of 10pF.

Software programs written in some programming languages like C, C++, Java, etc, are mostly verified by functional simulation. Since exhaustive functional simulation is impossible for even a small C program, it is important to quantitatively measure the extent of design verification during simulation by a set of test vectors. Various coverage metrics have been proposed for measuring the degree of design verification. Most of them compute the extent of design excitation (controllability) but are unable to say whether the excitation responses have propagated to observable points in the program (observability). In this paper we propose a metric for code coverage analysis of C programs that addresses not only controllability but tackles observability as well. Thus, this metric is able to tell what percentage of the simulation responses have been propagated to observable points in the program like primary outputs or printed variables. We improve upon a recently proposed observability enhanced software coverage metric by increasing the accuracy of the analysis as well as decreasing the simulation runtime overhead by using an event-driven coverage analysis method. We report some experimental results of using our coverage analysis tool for several C programs.

We present a precomputation-based guarding technique to reduce both dynamic and static power consumptions in CMOS VLSI circuits. More precisely, a high threshold sleep transistor is placed in series with some portions of the circuit. Based on the input values of the circuit, the sleep transistor is turned on and off, thus, saving both dynamic and static power. We show how to apply this technique to a number of common arithmetic blocks, including comparators, adders and multipliers. Finally, dynamic guarding and sleep transistor activity reduction techniques for improving the performance of the method are presented. Experimental results show 81% reduction in the power consumption of data path modules of a commercial VLIW processor can be achieved using our techniques. This is 20% higher than what has been achieved by previous methods.

In this paper, we introduce a class of irredundant low power encoding techniques for memory address buses. For a data address bus, the proposed encoding techniques make use of two working zones in the memory address space, whereas for a multiplexed data and instruction address bus, up to four working zones can be supported The zones are dynamically updated to increase the saving in switching activity. Our techniques decrease the switching activity of data address and multiplexed address buses by an average of 55% and 77%, respectively, up from 25% and 64% achieved by previous methods.

This paper introduces a new method for performing time-frame expansion based on writing the number of time frames in terms of powers of two. In the proposed method, the behavior of a circuit for t time frames, where n 0 ⪣t

In this paper we present a satisfiability-based approach to the scheduling problem in high-level synthesis. We formulate the resource constrained scheduling as a satisfiability (SAT) problem. We present experimental results on the performance of the state-of-the-art SAT solver Chaff, and demonstrate techniques to reduce the SAT problem size by applying bounding techniques on the scheduling problem. In addition, we demonstrate the use of transformations on control data flow graphs such that the same lower bound techniques can operate on them as well. Our experiments show that Chaff is able to outperform the integer linear program (ILP) solver CPLEX in terms of CPU time by as much as 59 fold. Finally, we conclude that the satisfiability-based approach is a promising alternative for obtaining optimal solutions to NP-complete scheduling problem instances.

Abstract. This paper describes two runtime mechanisms for reducing the leakage current of a CMOS circuit. In both cases, it is assumed that the system or environment produces a "sleep" signal that can be used to indicate that the circuit is in a standby mode. In the first method, the "sleep" signal is used to shift in a new set of external inputs and pre-selected internal signals into the circuit with the goal of setting the logic values of all of the internal signals so as to minimize the total leakage current in the circuit. This minimization is possible because the leakage current of a CMOS gate is a strong function of the input combination applied to its inputs. In the second method, NMOS and PMOS transistors are added to some of the gates in the circuit to increase the controllability of the internal signals of the circuit and decrease the leakage current of the gates using the "stack effect". This is, however, done carefully so that the minimum leakage is achieved subject to a delay constraint for all input-output paths in the circuit. In both cases, Boolean satisfiability is used to formulate the problems, which are subsequently solved by employing a highly efficient SAT solver. Experimental results on the circuits in the MCNC91 benchmark suite demonstrate that it is possible to reduce the leakage current by up to 70% in VLSI circuits at the expense of a very small overhead.

In this paper, we introduce a class of irredundant low power encoding techniques for memory address buses. The basic idea is to partition the memory space into a number of sectors. These sectors can, for example, represent address spaces for the code, heap, and stack segments of one or more application programs. Each address is first dynamically mapped to the appropriate sector and then is encoded with respect to the sector head. Each sector head is updated based on the last accessed address in that sector. The result of this sector-based encoding technique is a reduction in the number of bus transitions when encoding consecutive addresses that access different sectors. Our proposed techniques have small power and delay overhead when compared with many of the existing methods in the literature. One of our proposed techniques is very suitable for encoding addresses that are sent from an on-chip cache to the main memory when multiple application programs are executing on the processor in a time-sharing basis. For a computer system without an on-chip cache, the proposed techniques decrease the switching activity of data address and multiplexed address buses by an average of 55% and 67%, respectively. For a system with on-chip cache, up to 55% transition reduction is achieved on a multiplexed address bus between the internal cache and the external memory. Assuming a 10pF per line bus capacitance, we show that power reduction of up to 52% for an external data address bus and 42% for the multiplexed bus between cache and main memory is achieved using our methods.

Design validation and verification is the process of ensuring correctness of a design described at different levels of abstraction during the design process. Design validation is the main bottleneck in improving design turnaround time. Currently, simulation is the primary methodology for validation of the first description of a design. In this paper we integrate directed search methods and observability-based code coverage metric (OCCOM) computation into an algorithm for generating test vectors under OCCOM for sequential HDL models. A prototype system for design validation under OCCOM has been built. The system uses repeated coverage computation to minimize the number of vectors generated. Experimental results using the test vector generation system are presented.

This paper introduces a new method for manually generating test programs to validate a processor design. Current manual methods do not utilize high level of abstraction for describing test programs and lack many important features like reusability, incremental validation, and test program compaction; they also work on a formal model specifically developed for validation purposes. To solve the above problems, we use test specification expressions to describe test programs and generate test sequences based on an instruction-set description of a processor written for synthesis purposes. We provide experimental results of generating test programs for several processors to show the effectiveness of our method.

We present a simulation-based semi-formal verification method for sequential circuits described at the register-transfer level. The method consists of an iterative loop where coverage analysis guides input pattern generation. An observability-based coverage metric is used to identify portions of the circuit not exercised by simulation. A heuristic algorithm then selects probability distributions for biased random input pattern generation that targets non-covered portions. This algorithm is based on an approximate analysis of the circuit modeled as a Markov chain at steady state. Node controllability and observability are estimated using a limited depth reconvergence analysis and an implicit algorithm for manipulating probability distributions and determining steady-state behavior. An optimization algorithm iteratively perturbs the probability distributions of the primary inputs in order to improve estimated coverage. The coverage enhancement achieved by our approach is demonstrated on benchmarks from the ISCAS89 and VIS suites.

This paper proposes efficient encoding techniques for decreasing power dissipation on global buses. The best target for these techniques is a wide and highly capacitive memory bus. Building on T0 and Offset-Xor encoding techniques, we present three irredundant bus-encoding techniques. Our methods decrease switching activity up to 83 % without the need for redundant bus lines. The power dissipation of encoder and decoder circuitry has also been calculated and shown to be small in comparison with the power savings on the memory address bus itself. 1

Our strategy for automatic generation of functional vectors is based on exercising selected paths in the given hardware description language (HDL) model. The HDL model describes interconnections of arithmetic, logic, and memory modules. Given a path in the HDL model, the search for input stimuli that exercise the path can be converted into a standard satisfiability (SAT) checking problem by expanding the arithmetic modules into logic gates. However, this approach is not very efficient. We present a new HDL-SAT checking algorithm that works directly on the HDL model. The primary feature of our algorithm is a seamless integration of linear-programming techniques for feasibility checking of arithmetic equations that govern the behavior of data-path modules and SAT checking for logic equations that govern the behavior of control modules. This feature is critically important to efficiency, since it avoids module expansion and allows us to work with logic and arithmetic equations whose cardinality tracks the size of the HDL model. We describe the details of the HDL-SAT checking algorithm in this paper. Experimental results that show significant speedups over state-of-the-art gate-level SAT checking methods are included.

Functional simulation is still the primary workhorse for verifying the functional correctness of hardware designs. Functional verification is necessarily incomplete because it is not computationally feasible to exhaustively simulate designs. It is important, therefore, to quantitatively measure the degree of verification coverage of the design. Coverage metrics proposed for measuring the extent of design verification provided by a set of functional simulation vectors should compute statement execution counts (controllability information) and check to see whether effects of possible errors activated by program stimuli can be observed at the circuit outputs (observability information). Unfortunately, the metrics proposed thus far either do not compute both types of information or are inefficient, i.e., the overhead of computing the metric is very large. In this paper, we provide the details of an efficient method to compute an observability-based code coverage metric that can be used while simulating complex hardware description language (HDL) designs. This method offers a more accurate assessment of design verification coverage than line coverage and is significantly more computationally efficient than prior efforts to assess observability information because it breaks up the computation into two phases: functional simulation of a modified HDL model followed by analysis of a flowgraph extracted from the HDL model. Commercial HDL simulators can be directly used for the time-consuming first phase and the second phase can be performed efficiently using concurrent evaluation techniques.

Unate and binate covering problems are a subclass of general integer linear programming problems with which several problems in logic synthesis, such as two-level logic minimization and technology mapping, are formulated. Previous branch-and-bound methods for solving these problems exactly use lower bounding techniques based on finding maximal independent sets. In this paper, we examine lower bounding techniques based on linear programming relaxation (LPR) for the covering problem. We show that a combination of traditional reductions (essentiality and dominance) and incremental computation of LPR-based lower bounds can exactly solve difficult covering problems orders of magnitude faster than traditional methods.

Validation of RTL circuits remains the primary bottleneck in improving designturnaround time, and simulation remains the primary methodology for validation. Simulation-based validation has suffered from a disconnect between the metrics used to measure the error coverage of a set of simulation vectors, and the vector generation process. This disconnect has resulted in the simulation of virtually endless streams of vectors which achieve enhanced error coverage only infrequently. Another drawback has been that most error coverage metrics proposed have either been too simplistic or too inefficient to compute. Recently, an effective observability-based statement coverage metric was proposed along with a fast companion procedure for evaluating it. The contribution of our work is the development of a vector generation procedure targeting the observability-based statement coverage metric. Our method uses repeated coverage computation to minimize the number of vectors generated. For vector gen...

Our strategy for automatic generation of functional vectors is based on exercising selected paths in the given hardware description language (HDL) model. The HDL model describes interconnections of arithmetic, logic and memory modules. Given a path in the HDL model, the search for input stimuli that exercise the path can be converted into a standard satisfiability checking problem by expanding the arithmetic modules into logic-gates. However, this approach is not very efficient.

Functional simulation is still the primary workhorse for verifying the functional correctness of hardware designs. Functional verification is necessarily incomplete because it is not computationally feasible to exhaustively simulate designs. It is important therefore to quantitatively measure the degree of verification coverage of the design. Coverage metrics proposed for measuring the extent of design verification provided by a set of functional simulation vectors should compute statement execution counts (controllability information), and check to see whether effects of possible errors activated by program stimuli can be observed at the circuit outputs (observability information). Unfortunately, the metrics proposed thus far, either do not compute both types of information, or are inefficient, i.e., the overhead of computing the metric is very large. In this paper, we provide the details of an efficient method to compute an Observability-based Code COverage Metric (OCCOM) that can be used while simulating complex HDL designs. This method offers a more accurate assessment of design verification coverage than line coverage, and is significantly more computationally efficient than prior efforts to assess observability Information because it breaks up the computation into two phases: Functional simulation of a modified HDL model, followed by analysis of a flowgraph extracted from the HDL model. Commercial HDL simulators can be directly used for the time-consuming first phase, and the second phase can be performed efficiently using concurrent evaluation techniques.