In this paper, we propose an iterative area/performance tradeoff algorithm for look-up table (LUT)-based field programmable gate array (FPGA) technology mapping. First, it finds an area-optimized, performance-considered initial network by a modified area optimization technique. Then, an iterative algorithm consisting of several resynthesizing techniques is applied to trade the area for the performance in the network gracefully. Experimental results show that this approach can efficiently provide a complete set of mapping solutions from the area-optimized one to the performance-optimized one for the given design. Furthermore, these two extreme solutions produced by our algorithm outperform the results provided by most existing algorithms. Therefore, our algorithm is very useful for the timing-driven, LUT-based FPGA synthesis.

To characterize the power consumption of a macrocell, a general method involves recording the power consumption of all possible input transition events in the look-up tables. However, though this approach is accurate, the size of the table becomes very large. In this paper, we propose a new power modeling technique that takes advantage of the structural information of a macrocell. In this approach, a subset of primary inputs and internal nodes in the macrocell are selected as the state variables to build a state transition graph (STG). These state variables can model the steady-state transitions completely. Moreover, by selecting the characterization patterns properly, the STG can also model the glitch power in the macrocell accurately. To further simplify the complexity of the STG, an incomplete power modeling technique is presented. Without losing much accuracy, the property of compatible patterns is exploited for a macrocell to further reduce the number of edges in the corresponding STG. Experimental results show that our modeling techniques can provide SPICE-like accuracy, while the size of the look-up table is significantly reduced.

In this paper, we propose an iterative area/delay tradeoff algorithm to solve the circuit clustering problem under the capacity constraint. It first finds an initial delay-considered area-optimized clustering solution by a delay-oriented depth first-search procedure. Then, an iterative procedure consisting of several reclustering techniques is applied to gradually trade the area for the performance. We then show that this algorithm can be easily extended to solve the clustering problem subject to both capacity and pin constraints. Experimental results show that our algorithm can provide a complete set of clustering solutions from the area-optimized one to the delay-optimized one for a given circuit. Furthermore, compared to the existing delay-optimized algorithms, this algorithm achieves almost the same performance but with much less area overhead. Therefore, this algorithm is very useful for solving the timing-driven circuit clustering problem.

In this paper, we present CB-Power, a hierarchical cell-based power characterization and estimation environment for static CMOS circuits. The environment is based on a cell characterization system for timing, power and input capacitance and on a cell-based power estimator. The characterization system can characterize basic, complex and transmission gates. During the characterization, input slew rate, output loading, capacitive feedthrough effect and the logic state dependence of nodes in a cell are all taken into account. The characterization methodology separates the power consumption of a cell into three components, e.g., capacitive feedthrough power, short-circuit power, and dynamic power. With the characterization data, a cell-based power estimator (CBPE) embedded in Verilog-XL is used for estimating the power consumption of a circuit. CB-Power is also a hierarchical power estimator. Macrocells such as flip-flops and adders are partitioned into primitive gates during power estimation. Experimental results on a set of MCNC benchmark circuits show that CB-Power provides within 6% error of SPICE simulation on average while the CPU time consumed is more than two orders of magnitude less.

To characterize a macrocell, a general method is to store the power consumption of all possible transition events at primary inputs in the lookup tables. Though this approach is very accurate, the lookup tables could be huge for the macrocells with many inputs. We present a new power modeling method which takes advantage of the structure information of macrocells and selects a minimum number of primary inputs or internal nodes in a macrocell as state variables to build a state transition graph (STG). Those state variables can completely model the transitions of all internal nodes and the primary outputs. By carefully deleting some state variables, we further introduce an incomplete power modeling technique which can simplify the STG without losing much accuracy. In addition, we exploit the property of the compatible patterns of a macrocell to further reduce the number of edges in the corresponding STG. Experimental results show that our modeling techniques can provide SPICE-like accuracy and can reduce the size of the lookup table significantly, compared to the general approach.

In this paper, we propose an iterative area/performance trade-off algorithm for LUT-based FPGA technology mapping. First, it finds an area-optimized performance-considered initial network by a modified area optimization technique. Then, an iterative algorithm consisting of several resynthesizing techniques is applied to trade the area for the performance in the network gracefully. Experimental results show that this approach can provide a complete set of mapping solutions from the area-optimized one to the performance-optimize one for the given design. Furthermore, these two extreme solutions, the area-optimized one and the performance-optimized one, produced by our algorithm outperform the results of most existing algorithms. Therefore, our algorithm is very useful for the timing driven FPGA synthesis.

In this paper, we propose power consumption models for complex gates and transmission gates, which are extended from the model of basic gates proposed in Lin et al., (1994). We also describe an accurate power characterization method for CMOS standard cell libraries which accounts for the effects of input slew rate, output loading, and logic state dependencies. The characterization methodology separates the power consumption of a cell into three components, e.g., capacitive feedthrough power, short-circuit power, and dynamic power. For each component, power equation is derived from SPICE simulation results where the netlist is extracted from cell's layout. Experimental results on a set of ISCAS'85 benchmark circuits show that the power estimation based on our power modeling and characterization provides within 7% error of SPICE simulation on average while the CPU time consumed is more than two orders of magnitude less.

No abstract available.

Conventional fault relationships are mostly restricted to faults at a gate or within a fanout free region. In this paper, we analyze the fault relationships beyond the fanout free region for general digital logic circuits. An improved fault collapsing procedure is proposed and applied to several kinds of combinational benchmark circuits and 31 sequential benchmark circuits to collapsing faults. Improvements of 2-8% for an initial set of target faults of a circuit can be obtained. For some of circuits, the reduction ratio can have up to 20% improvement. This may save a lot of time in test generation and fault simulation processes.

partition tends to produce better results.However, to the best of our knowledge, finding a good input partition in Roth-Karp decomposition has not been formally addressed in previous research.In this paper, we propose a new heuristics to solve this problem.Roth-Karp decomposition is a classical decomposition method.Because it can reduce the number of input variables of a function, it becomes one of the most popular techniques used in LUT-based FPGA technology mapping.However, the lambda set selection problem, which can dramatically affect the decomposition quality in Roth-Karp decomposition, has not been formally addressed before.In this paper, we propose a new heuristic-based algorithm to solve this problem.The experimental results show that our algorithm can efficiently produce outputs with better decomposition quality than that produced by other algorithms without using lambda set selection strategy.This paper is organized as follows.Section 2 briefly introduces some terminologies used in this paper.Section 3 describes Roth-Karp decomposition and a classical implementation for it.In Section 4, our newly developed heuristics for selecting a good λ set is given in detail.Section 5 shows some experimental results and concluding remarks are given in Section 6.2. Preliminaries m cover of a cover C, denoted as C m , is the set containing all m cubes in C.The corresponding compatibility graph is illustrated in Fig. 1.

Roth-Karp decomposition is one of the most popular techniques for LUT-based FPGA technology mapping because it can decompose a node into a set of nodes with fewer numbers of fanins. In this paper, we show how to formulate the compatible class encoding problem in Roth-Karp decomposition as a symbolic-output encoding problem in order to exploit the feature of the two-output LUT architecture. Based on this formulation, we also develop an encoding algorithm to minimize the number of LUT's required to implement the logic circuit. Experimental results show that our encoding algorithm can produce promising results in the logic synthesis environment for the two-output LUT architecture.

In this paper we present a power dissipation model considering the charging/discharging of capacitance at the gate output node as well as internal nodes, and capacitance feedthrough effect. Based on the model, a Cell-Based Power Estimation (CBPE) method is developed to estimate the power dissipation in CMOS combinational circuits. In our technique, we first construct a modified state transition graph called STGPE to model the power consumption behavior of a logic gate. Then, according to the input signal probabilities and transition densities of the logic gate, we perform an efficient method to estimate the expected activity number of each edge in the STGPE. Finally, the energy consumption of a logic gate is calculated by summing the energy consumptions of each edge in STGPE. For a set of benchmark circuits, experimental results show that the power dissipation estimated by CBPE is on average within 10-percent errors as compared to the exact SPICE simulation while the CPU time is more than two order-of-magnitudes faster.

Double RAM buffer technique is widely used in row-column method to decompose the multidimensional transformation. In this paper, we propose a new approach, named single RAM technique. Base on the accurate arrangement of the location and timing of the input and output data, only a single RAM is used as the reorder buffer. Therefore, approximately half of the memory size is reduced. In addition, a long length DFT processor which can handle 1008-point real-valued DFT with nonstop input sequence is presented to demonstrate the benefits of the single RAM buffer technique. Goertzel Algorithm and CORDIC technique are adopted to realize a two level pipeline linear array for attaining higher speed. Besides, based on the symmetric property of real value DFT, we can compute N-point real-valued DFT with a length-N/2 complex-valued DFT.>

The pseudoexhaustive testing (PET) scheme is an economical approach to testing a large embedded programmable logic array (PLA). The authors propose an efficient algorithm named low overhead PET (LOPET) to partition the product lines. By applying this algorithm, both the area overhead and test length are reduced significantly.>

The untestability cube-number product (UCP), a testability measure that can accurately indicate the extra logic needed in testable programmable logic arrays (PLAs), is discussed. Two UCP-based PLA synthesis algorithms are developed. The first one is a restructuring algorithm named REST, and the other is a logic minimizer for testable PLA named LMTPLA. REST can make the restructured PLA testable by taking less extra hardware. LMTPLA is based on EXPRESSO-II and REST. It can consider the testability at the logic minimization process. In order to minimize UCP as well as the number of product terms, four strategies are developed: deleting the cubes with poor testability and reserving the cubes with good testability; giving up the primes, if necessary: partitioning the more untestable cubes into smaller cubes; and deleting the procedures which are useless in LMTPLA. REST and LMTPLA have been implemented on SUN4/260 in C language. For 40 benchmark circuits, the hardware overheads required are reduced by about 30-40%.>

A study is made of single-fault fault collapsing in sequential logic circuits. Two major phenomena, self-hiding (SH) and delayed reconvergence (DR), which arise from the existence of feedback paths and storage elements in sequential circuits, are analyzed and found to cause the dominance relationship which is valid in combinational circuits but no longer valid in sequential circuits. A fault-collapsing procedure is proposed to collapse faults in sequential circuits. It first collapses faults in the non-SAD (self-hiding and delayed-reconvergence) gates of the combinational part of the sequential circuit and then further collapses faults by identifying the prime fan-out branches. Finally, it collapses faults in feedback lines. The collapsed faults constitute a sufficient representative set of prime faults.>

This paper describes a parallel pattern mixed level, i.e. switch-level and gate-level, fault simulator. The switch-level allows the simulator to treat faults at the transistor level while the gate level simulation conserves the simulation speed and the parallel pattern strategy further enhances the simulation speed for more than one order of magnitude.

A study of fault collapsing for synchronous sequential circuits is presented. Two phenomena, self-hiding and delay-reconvergence, which invalidate the combinational fault dominance relationship in sequential circuits are identified. These phenomena are caused by the existence of feedback paths and storage elements in sequential circuits. From this analysis, a single-fault fault-collapsing procedure for synchronous irredundant sequential circuits is proposed to reduce the faults for which test has to be generated. This procedure can be applied not only to a nonscan mode circuit, but also to a full-scan and a partial-scan mode circuit by cutting the inputs and outputs of scannable D flip-flops as the primary outputs and inputs of the circuit, respectively. This procedure has been applied to collapse faults for the 31 benchmark sequential circuits, and a 57% reduction in the number of faults as compared with the total number of original faults has been obtained.>