Boolean Satisfiability (SAT) is a core NP-complete problem. Several heuristic software and hardware approaches have been proposed to solve this problem. In this paper we present a Boolean satisfiablity approach with a new GPU-enhanced variable ordering heuristic. Our results demonstrate that over several satisfiable and unsatisfiable benchmarks, our technique (MESP) performs better than MiniSAT. We show a 2.35× speedup on average, over 68 from the SAT Race (2008) competition.

SPICE based circuit simulation is a traditional workhorse in the VLSI design process. Given the pivotal role of SPICE in the IC design flow, there has been significant interest in accelerating SPICE. Since a large fraction (on average 75%) of the SPICE runtime is spent in evaluating transistor model equations, a significant speedup can be availed if these evaluations are accelerated. This paper reports on our early efforts to accelerate transistor model evaluations using a Graphics Processing Unit (GPU). We have integrated this accelerator with a commercial fast SPICE tool. Our experiments demonstrate that significant speedups (2.36times on average) can be obtained. The asymptotic speedup that can be obtained is about 4times. We demonstrate that with circuits consisting of as few as about 1000 transistors, speedups in the neighborhood of this asymptotic value can be obtained. By utilizing the recently announced (but not currently available) quad GPU systems, this speedup could be enhanced further, especially for larger designs.

In this paper, we explore the implementation of Monte Carlo based statistical static timing analysis (SSTA) on a graphics processing unit (GPU). SSTA via Monte Carlo simulations is a computationally expensive, but important step required to achieve design timing closure. It provides an accurate estimate of delay variations and their impact on design yield. The large number of threads that can be computed in parallel on a GPU suggests a natural fit for the problem of Monte Carlo based SSTA to the GPU platform. Our implementation performs multiple delay simulations at a single gate in parallel. A parallel implementation of the Mersenne Twister pseudo-random number generator on the GPU, followed by box-Muller transformations (also implemented on the GPU) is used for generating gate delay numbers from a normal distribution. The mu and sigma of the pin-to-output delay distributions for all inputs and for every gate, are obtained using a memory lookup, which benefits from the large memory bandwidth of the GPU. Threads which execute in parallel have no data/control dependencies on each other. All threads compute identical instructions, but on different data, as required by the single instruction multiple data (SIMD) programming semantics of the GPU. Our approach is implemented on a NVIDIA GeForce GTX 8800 GPU card. Our results indicate that our approach can obtain an average speedup of about 260times as compared to a serial CPU implementation. With the recently announced quad 8800 GPU cards, we estimate that our approach would attain a speedup of over 785times. The correctness of the Monte Carlo based SSTA implemented on a GPU has been verified by comparing its results with a CPU based implementation.

In recent times, the contribution of leakage power to the total power consumption of a chip has been increasing at an alarming rate. Leakage power is expected to exceed dynamic power in newer process technologies. Since leakage exhibits an exponential increase with temperature, it is possible that the high leakage of an IC causes a temperature increase, which in turn causes an increase in leakage, and so on, until the IC fails due to overheating. At the very least, this may cause the temperature and power consumption of the IC to be poorly estimated by traditional thermal or power modeling techniques. We developed a framework to model this situation in an FPGA context. Our CAD framework accurately models the total power consumption of the design at a given temperature, finds the thermal profile of the IC under this power consumption, and then uses this new thermal information to update the power consumption. This is iterated until the temperature of the IC converges, or until the temperatures on the die exceed a safe value. The iterations are very fast, due to the use of accurate and compact mathematical macromodels for leakage and temperature computation in the inner loop. We have exhaustively verified the fidelity of all our leakage macromodels. They estimate the leakage, at any temperature, to within 3% of the values generated by SPICE, while providing greater than four orders of magnitude speedup over explicit SPICE runs. Our experiments show that this model helps avoid an incorrect estimation of chip temperature and total power consumption, and also helps detect the increase in device temperature beyond a safe value. The average (maximum) error of our temperature estimates has been found to be within 1% (2.5%) compared to a full-chip 3D temperature modeling tool.

Leakage power consumption is a large fraction of the total power consumption in contemporary VLSI designs. Since memories occupy a large portion of the total area of many high-performance ICs, it is crucial to reduce the leakage energy of memories. This problem is particularly aggravated for memories implemented in the 45nm technology node, since these processes exhibit significantly higher leakage power. For these memories, leakage is a significant problem not only from a power point of view, but also from a performance degradation standpoint. In this paper, we quantify this problem and provide a solution, using a 512KByte SRAM implemented in a 45nm bulk process as a design example. We show that implementing the SRAM as a monolithic memory results in increased delay as well as power. We illustrate a methodology to optimally reduce leakage power and improve performance in memories by splitting the memory array into word line groups (WLGs) which are selectively forward body biased when accessed. We present a derivation of optimal number of WLGs and the forward body bias voltage value, and show that our approach results in a 9:2% access time reduction, and a 53:4% reduction in power during a read operation. Our approach also achieves an 18% reduction in power during a write operation and a 69% leakage power improvement. The area overhead of our scheme is 7:2% compared to a monolithic memory.

Multi-node optimization using Boolean relations is a powerful approach for network minimization. In this paper, we present an algorithm to perform Boolean relation-based multi-node optimization using a robust, fast and memory efficient algorithm. In particular, we simultaneously optimize two nodes at a time. The robustness of our approach arises from the use of a window-based technique for computing these Boolean relations. Secondly, we perform early quantification during the computation, keeping memory utilization low. Finally, we employ smart heuristics for selecting the node pair to be optimized simultaneously.

In this paper, we describe a low-area, reduced-power on-chip point-to-point bidirectional communication scheme for heavily pipelined systems. When data needs to be transmitted bidirectionally between two on-chip locations, the traditional approach resorts to either using two unidirectional wires, or to using a single wire (with a unidirectional transfer at any given time instant). In contrast, our bidirectional communication scheme allows data to be transmitted simultaneously between two on-chip locations, with a single wire performing the bidirectional data transfer. Our approach borrows ideas from the emerging area of network coding (in the field of communication). By utilizing coding units (which also serve the purpose of buffering the signals) along the wire between the two endpoints, we are able to achieve the same throughput as a traditional approach, while reducing the total area utilization by about 49.8% (thereby reducing routing congestion), and the total power consumption by about 11.5%. The area and power results include the contribution of routing wires, coding units, drivers, the clock distribution network and the required reset wire. Our bidirectional communication approach is ideally suited for heavily pipelined data intensive systems.

This paper describes a novel algorithm for sorting binary numbers in hardware, along with a custom VLSI hardware design for the same. For sorting n, k-bit binary numbers, our proposed algorithm takes O(n + 2 k) time. Sorting is performed by assigning relative ranks to the input numbers. A rank matrix of size n times n is used to store ranks. Each row of the rank matrix corresponds to one of the n numbers, and it stores a single non-zero entry. The position of this entry represents the relative rank of the corresponding number. In the worst case, our algorithm requires n+2 k clock cycles for assigning the final ranks. We start with a condition in which each number has an identical rank. In each of clock cycle, ranks are iteratively updated until the final ranks are determined after n+2 k clock cycles. The proposed algorithm is implemented in a 65 nm process, using a custom design approach to obtain a fast circuit. Our design is significantly faster than the fastest reported hardware sorting engine, with area performance which is superior for larger numbers.

We present an FPGA-based hardware solution to the Boolean satisfiability (SAT) problem, with the main goals of scalability and speedup. In our approach the traversal of the implication graph as well as conflict clause generation are performed in hardware, in parallel. The experimental results and their analysis, along with the performance models are discussed. We show that an order of magnitude improvement in runtime can be obtained over MiniSAT (the best-in-class software based approach) by using a Virtex-4 (XC4VFX140) FPGA device. The resulting system can handle instances with as many as 10K variables and 280K clauses.

In this paper, we explore the implementation of fault simulation on a Graphics Processing Unit (GPU). In particular, we implement a fault simulator that exploits thread level parallelism. Fault simulation is inherently parallelizable, and the large number of threads that can be computed in parallel on a GPU results in a natural fit for the problem of fault simulation. Our implementation fault-simulates all the gates in a particular level of a circuit, including good and faulty circuit simulations, for all patterns, in parallel. Since GPUs have an extremely large memory bandwidth, we implement each of our fault simulation threads (which execute in parallel with no data dependencies) using memory lookup. Fault injection is also done along with gate evaluation, with each thread using a different fault injection mask. All threads compute identical instructions, but on different data, as required by the Single Instruction Multiple Data (SIMD) programming semantics of the GPU. Our results, implemented on a NVIDIA GeForce GTX 8800 GPU card, indicate that our approach is on average 35 x faster when compared to a commercial fault simulation engine. With the recently announced Tesla GPU servers housing up to eight GPUs, our approach would be potentially 238× faster. The correctness of the GPU based fault simulator has been verified by comparing its result with a CPU based fault simulator.

With current technology trends, FPGA routing is an important problem, since routing in FPGAs contributes significantly to delay and resource utilization, as compared to the logic portion of FPGAs. In this paper we improve the FPGA routing characteristics by applying the technique of network coding.

In a typical IC design flow, circuits are optimized using multilevel don't cares. The computed don't cares are discarded before Technology Mapping or Automatic Test Pattern Generation (ATPG). In this paper, we present two combinational ATPG algorithms for combinational designs. These algorithms utilize the multilevel don't cares that are computed for the design during technology independent logic optimization. They are based on Boolean Satisfiability (SAT), and utilize the single stuck-at fault model. Both algorithms make use of the Compatible Observability Don't Cares (CODCs) associated with nodes of the circuit, to speed up the ATPG process. For large circuits, both algorithms make use of approximate CODCs (ACODCs), which we can compute efficiently. Our first technique speeds up fault propagation by modifying the active clauses in the transitive fanout (TFO) of the fault site. In our second technique, we define new j - active variables for specific nodes in the transitive fanin (TFI) of the fault site. Using these j-active variables we write additional clauses to speed up fault justification. Experimental results demonstrate that the combination of these techniques (when using CODCs) results in an average reduction of 45% in ATPG runtimes. When ACODCs are used, a speed-up of about 30% is obtained in the ATPG run-times for large designs. We compare our method against a commercial structural ATPG tool as well. Our method is slower for small designs, but for large designs, we obtain a 31% average speedup over the commercial tool.

We compare the complexity of "internal" and "external" equivalence checking. The former is meant for proving the correctness of a synthesis transformation by which circuit N2is obtained from circuit N1. The latter is meant for proving that circuits N1and N2are functionally equivalent without making any explicit assumptions about the origin of N1and N2. We describe logic synthesis procedures that can produce a circuit N2whose equivalence with the original circuit N1, most likely, can not be efficiently proved by an external equivalence checker. On the other hand, there are internal equivalence checking procedures that easily prove that N1and N2are equivalent. We give experimental data showing that these logic synthesis procedures are not a mathematical curiosity but indeed can be used as a powerful method of logic optimization.

We describe a procedure (called the TEP procedure) that, given a multi-output circuit M, builds another multi-output circuit M* that is toggle equivalent to M. The TEP procedure can be used in the following two scenarios. First, since for single- output circuits toggle equivalence means functional equivalence, the TEP procedure can be used in "regular" logic synthesis. Second, the TEP procedure enables a powerful synthesis method called LS_TE (Logic Synthesis preserving Toggle Equivalence). Given a circuit N and its partitioning into subcircuits NiLS_TE builds an optimized circuit N* by replacing subcircuits Niwith their toggle equivalent counterparts Ni. The replacement of Niwith N*iis done by the TEP procedure. We give results of optimizing single-output circuits by the TEP procedure and some preliminary results of using the TEP procedure in LS_TE. These results show the promise of the TEP procedure and LS_TE.

In this paper, we describe a structured ASIC design methodology which utilizes a regular, pre-fabricated array of pass transistor logic based if-then-else (ITE) cells as the building block for the circuit. Given a logic netlist, we first construct reduced order binary decision diagrams (ROBDDs) for the circuit in a partitioned manner, thereby allowing the approach to handle large designs. We place the ITE cells corresponding to the ROBDD nodes in a manner that minimizes crossings in the ROBDD graph. Our placement also effectively 'folds' the ITE cells of different variables into a single row, so as to obtain a layout with a more uniform distribution of ITE cells along each physical row of ITE cells. The design methodology has been demonstrated to implement sequential as well as combinational designs, by customizing the lowest 4 METAL layers along with their associated VIA layers. A low area and delay overhead is achieved, in comparison with an ASIC approach. In particular, the average delay (area) overhead is 1.5 times (3.41 times) for combinational designs and 2 times (6 times) for sequential designs

The parasitic inductances within IC packaging cause supply bounce as well as glitches on the signal pins, significantly limiting the frequency of high-speed inter-chip communication. Also, off-chip communication contributes a large fraction of the total system power. Until recently, the parasitic inductance problem was addressed by aggressive package design, which is expensive. In this work we present a technique to encode the off-chip data transmission to i) limit bounce on the supplies, ii) reduce glitching caused by inductive signal coupling from neighboring signals, iii) limit the edge degradation of signals due to mutually inducted voltages from neighboring switching signals and iv) control the total power consumption of the I/O logic. All these factors are modeled in a unified mathematical framework. Our experimental results show that the proposed encoding based techniques result in reduced supply bounce and signal glitching due to inductive cross-talk, closely matching the theoretical predictions. Also, we show that the bus size overhead is reasonable even after stringent power reduction constraints are imposed. We demonstrate that the overall bandwidth of a bus actually increases by 100% over an unencoded bus, using our technique with inductive constraints only (even after accounting for the encoding overhead). When the power constraints were added (to limit the power to 20% of worst case switching power) in addition to the inductive constraints, the bandwidth was again 100% improved over the unencoded bus. The asymptotic bus size overhead depends on how stringent the user-specified power and inductive cross-talk parameters are. We have validated our approach by simulating it in an ASIC setting as well as prototyping and testing it in an FPGA environment.

This paper presents a design flow that optimizes a standard cell based circuit for performance by implementing critical paths in a Programmable Logic Array (PLA). Given a standard-cell based circuit as input, our approach iteratively extracts critical paths from this circuit, which are then implemented using a PLA circuit. PLAs are a good candidate for such an approach, since they exhibit a gradual increase in delay as additional vectors are added. In subsequent iterations, these critical paths are treated as don't cares, allowing the standard cell based design to be simplified after each iteration. The final design consists of a portion which is implemented using a PLA, and another portion which is implemented using standard cells. We demonstrate that on average, our approach can achieve about 22.5% improvement in the SPICE based delay of a design, along with a placed-and-routed area improvement of 11%.

With the standard approach for establishing multicast connections over a network, network nodes are utilized to forward and duplicate the packets received over the incoming links. Recently, there has been a significant interest in a novel paradigm of network coding. Network coding generalizes the traditional routing approach by allowing the network nodes to generate new packets by performing algebraic operations on packets received over the incoming links. It has been shown that network coding can increase the throughput of multicast communication. In this paper, we explore the benefits of network coding for improving the routing characteristics of VLSI designs. We demonstrate that when data has to be routed across the IC, it is often beneficial to perform network coding. Initial results demonstrate that network coding can result in a healthy reduction in wire length, wire area, interconnect power as well as the active area associated with the interconnects. This comes at a small delay penalty.

Boolean Satisfiability (SAT) is a core NP-complete problem in logic synthesis. Several heuristic software and hardware approaches have been proposed to solve this problem. In this paper, we present a hardware solution to the SAT problem. We propose a custom IC to implement our approach, in which the traversal of the implication graph as well conflict clause generation are performed in hardware, in parallel. In our approach, clause literals are stored in specially designed cells. Clauses are implemented in banks, in a manner that allows clauses of variable width to be accommodated in these banks. To maximize the utilization of these banks, we initially partition the SAT problem. Our design is flexible in that it can implement various Boolean Constraint Propagation (BCP) engines on the same die, at the same time, allowing the user to switch BCP engines dynamically. Our solution has significantly larger capacity than existing hardware SAT solvers, and is scalable in the sense that several ICs can be used to simultaneously operate on the same SAT instance, effectively increasing capacity further. Our area and performance figures are derived from layout and SPICE (using extracted parasitics) estimates. Additionally, the approach presented in this paper have been functionally validated in Verilog. Preliminary results demonstrate that our approach can accommodate instances with approximately 63K clauses on a single IC of size 1.5cmx 1.5cm. The approach re suits in over 4 orders of magnitude speed improvement over BCP based software SAT approaches (2-3 orders of magnitude over other hardware SAT approaches). The capacity of our approach is significantly higher than most hardware based approaches.

In recent times, the ratio of the cross-coupling capacitance between adjacent on-chip wires on the same metal layer to the total capacitance of any wire is becoming quite large. As a consequence, signal wires exhibit a significant delay variation and noise immunity problems. This problem is aggravated for long on-chip buses. In this paper, we develop memory-based crosstalk canceling CODECs for on-chip buses. We describe an reduced ordered binary decision diagram (ROBDD) based methodology to accurately compute the bus area overhead of the CODECs. We report the asymptotic overhead for CODECs which cancel three kinds of crosstalk patterns, and demonstrate that the bus size overheads are lower than the corresponding overheads for a memoryless CODEC. This results in a reduced overall area utilization for memory-based crosstalk canceling CODECs, compared to their memoryless counterparts. We also demonstrate that the use of these crosstalk canceling CODECs enables a user to speed up a bus by a factor of over 6/spl times/. Further, by using our techniques, a user may trade off the speed gain against the attendant bus size overhead.

"Parking" a circuit in a minimum leakage state during its standby mode of operation is one of the techniques of reducing leakage power consumption in a circuit. However, the problem of finding this minimum leakage state is NP-hard. In this paper, we present a heuristic approach to determine the input vector which minimizes leakage for a combinational design. Our approach utilizes approximate signal probabilities of internal nodes to aid in finding the minimum leakage vector. We use a probabilistic heuristic to select the next gate to be processed, as well as to select the best state of the selected gate. A fast SAT solver is employed to ensure the consistency of the assignments that are made in this process. Experimental results indicate that our method has very low run-times, with excellent accuracy, compared to existing approaches

In this paper, we describe a BDD-based hierarchical don't care computation algorithm. In contrast to traditional don't care computation techniques, our method retains the hierarchy in the design netlist during the don't care computation. Although this may reduce some of the flexibility inherent in the optimization process, it allows our technique to handle large designs. Our method computes don't cares at input and output interfaces of different modules in the hierarchy by an image computation process. In case an exact image cannot be computed, our method computes the largest approximate image. Once the don't cares at the input and output interfaces are computed, the hierarchical instances are optimized separately using a traditional optimization flow. Experimental results demonstrate that our technique can achieve a 36% reduction in literal count for large hierarchical designs, with reasonable runtimes. Our method can complete for several examples in which flattened optimization fails.

In this paper, we present an Algebraic Decision Diagram (ADD) based approach to determine and implicitly represent the leakage value for all input vectors of a combinational circuit. In its exact form, our technique can compute the leakage value of each input vector. To broaden the applicability of our technique, we present an approximate version of our algorithm as well. The approximation is done by limiting the total number of discriminant nodes in any ADD. Previous sleep vector computation techniques can find either the maximum or minimum sleep vector. Our technique computes the leakages for all vectors, storing them implicitly in an ADD structure. We experimentally demonstrate that these approximate techniques produce results which have reasonable errors. We also show that limiting the number of discriminants to a value between 12 and 16 is practical, allowing for good accuracy and lowered memory utilization