During the process of very large scale integration design, specifications are often changed. To preserve as large a portion of the engineering effort as possible, it is desirable that such changes will not lead to a very different design. In this work, we consider logic synthesis algorithms for handling engineering changes. To solve it, we propose a combination of multiple-error diagnosis and logic minimization techniques. Given a new specification and an existing synthesized network, our algorithms first identify the candidate signals in the network, and then synthesize the candidate functions. The synthesis step utilizes the existing network as much as possible so that the new specification can be realized with minimal changes.

In this paper, w e presen t a new retiming-based technology mapping algorithm for look-up table-based field programmable gate arrays. The algorithm is based on a novel iterative procedure for computing all k-cuts of all nodes in a sequen tialcircuit, in the presence of retiming. The algorithm completely avoids flow computation whic his the bottleneck of previous algorithms. Due to the fact that k is very small in practice, the procedure for computing all k-cuts is v ery fast. Experimental results indicate the overall algorithm is very efficient in practice.

Conventional scan design imposes considerable area and delay overheads. To establish a scan chain in the test mode, multiplexers at the inputs of flip-flops and scan wires are added to the actual design. We propose a low-overhead scan design methodology that employs a new test-point insertion technique. Unlike the conventional test-point insertion, where test points are used directly to increase the controllability and observability of the selected signals, the test points are used here to establish scan paths through the functional logic. The proposed technique reuses the functional logic for scan operations; as a result, the design-for-testability overhead on area or timing can be minimized. We show an algorithm that uses the new test-point insertion technique to reduce the area overhead for the full-scan design. We also discuss its application to the timing-driven partial-scan design.

Conventional scan design imposes considerable area and delay overheads. To establish a scan chain in the test mode, multiplexers at the inputs of flip-flops and scan wires are added to the actual design. However, the functionality of the functional logic has not been utilized for the test purposes. We propose a low-overhead scan design methodology, called cost-free scan, which exploits the controllability of primary inputs to establish scan paths through the functional logic. We show how to analyze the circuit to determine all the free-scan flip-flops and select the best input vector to establish the maximum number of free-scan flip-flops for the scan chain design. Significant reduction in the scan overhead is achieved on ISCAS89 benchmarks. In full-scan designs, as many as 89% of the flip-flops are found free-scannable. In the partial-scan designs, we assume that selecting flip-flops for scan to break sequential cycles is used to increase circuit testability. Reduction can be as high as 97% in scan flip-flops needed to break sequential cycles.

We present a general methodology to determine the logic function of a programmable cell. It is based on the concept of universal logic gate (ULG) that is capable of being configured to a given set of functions. The cells studied here can be configured to the desired functionality by applying input permutation, negation, bridging or constant assignment, or output negation. One application of this technique is to select an appropriate programmable cell structure for FPGA architecture. The Actel 2 and the three-input look-up table cells are studied and compared to the cell that has been designed using the approach described here. Experimental results suggest that the new cell behaves as well as the Actel 2 cell in terms of logic power, but requires substantially less area and wiring overhead.

We propose a low-overhead scan design methodology which employs a new test point insertion technique to establish scan paths through the functional logic.The technique re-uses the existing functional logic; as a result, the design-for-testability (DFT) overhead on area or timing can be minimized.In this paper we show an algorithm which considers the test point insertion for reducing the area overhead for the full scan design.We also discuss its application to timing-driven partial scan design.

No abstract available.

In the process of VLSI design, specifications are often changed. It is desirable that such changes will not lead to a very different design so that a large part of engineering effort can be preserved. We consider synthesis algorithms for handling such engineering changes. Given a synthesized network, our algorithm modifies it minimally to realize a new specification.

Traditionally, the circuit partitioning problem is done by first modeling a circuit as a graph and then partitioning is performed on the modeling graph. Using the concept of alternative wires, we propose an efficient method that is able to preserve a local optimal solution in the graph domain while a different graph, representing the same circuit, is generated. When a conventional graph partitioning technique reaches a local optimal solution, our proposed technique generates a different graph that is logically equivalent to the original circuit, and that has equal or better partitioning solution. Faced with a different graph which is newly generated together with a currently good partitioning solution, a conventional graph partitioning technique may then escape from the optimum and continue searching for better solutions in a different graph domain. The proposed technique can be combined with almost any graph partitioner. Experiments show encouraging results.

Conventional scan design imposes considerable area and delay overhead by using larger scan flip-flops and additional scan wires without utilizing the functionality of the combinational logic. We propose a novel low-overhead scan design methodology, called cost-free scan, which exploits the controllability of primary inputs to establish scan paths through the combinational logic. The methodology aims at reducing scan overhead by (1) analyzing the circuit to determine all the cost-free scan flip-flops, and (2) selecting the best primary input vector to establish the maximum number of cost-free scan flip-flops on the scan chain. Significant reduction in the scan overhead is achieved on ISCAS89 benchmarks, where in full scan environment, as many as 89% of the total flip-flops are found cost-free scannable, while in partial scan environment, reduction can be as high as 97% in scan flip-flops needed to break sequential loops.