Search

This paper presents two primary results relevant to physical design problems in CAD/VLSI through a case study of the linear placement problem. First a local search mechanism which incorporates a sophisticated neighborhood operator based on constraint relaxation is proposed. The strategy exhibits many of the desirable features of analytical placement while retaining the flexibility and non-determinism of local search. The second and orthogonal contribution is in netlist clustering. We characterize local optima in the linear placement problem through a simple visualization tool—the displacement graph. This characterization reveals the relationship between clusters and local optima and motivates a dynamic clustering scheme designed specifically for escaping such local optima. Promising experimental results are reported.

The main goal of the paper is to explore the effectiveness of a new method called Tabu Search [1] on partitioning and compare it with two techniques widely used in CAD tools for circuit partitioning i.e., Sanchis Interchange method and Simulated Annealing, in terms of the running time and quality of solution. The proposed method integrates the well known iterative multi-way interchange method with Tabu Search and leads to a very powerful network partitioning heuristic. It is characterized by an ability to escape local optima which usually cause simple descent algorithms to terminate by using a short term memory of recent solutions. Moreover, Tabu Search permits backtracking to previous solutions, which explore different directions and generates better partitions.The quality of the test results on MCNC benchmark circuits are very promising in most cases. Tabu Search yields netlist partitions that contain 20%–67% fewer cut nets and are generated 2/3 to (1/2) times faster than the best netlist partitions obtained by using an interchange method. Comparable partitions to those obtained by Simulated Annealing are obtained 5 to 20 times faster.

A new hierarchical layout vs. schematic (LVS) comparison system for layout verification has been developed. The schematic hierarchy is restructured to remove ambiguities for consistent hierarchical matching. Then the circuit hierarchy is reconstructed from the layout netlist by using a modified SubGemini algorithm recursively in bottom-up fashion. For efficiency, simple gates are found by using a fast rule-based pattern matching algorithm during preprocessing. Experimental results show that our hierarchical netlist comparison technique is effective and efficient in CPU time and in memory usage, especially when the circuit is large and hierarchically structured.

Traditional placement problems are studied under a fully specified cell library and a complete netlist. However, in the first, e.g., 2 years of a 2 – 3 year microprocessor design cycle, the detailed netlist is unavailable. For area and performance estimation, layout must nevertheless be done with incomplete information. Another source of incompleteness comes from logic synthesis changes; some instances and their parameters will change as the project evolves. In the re-configurable computing area, sometimes we need to perform quick placement before all information is available. The problem of placement with incomplete data (PID) can be abstracted as having to place a circuit when pc% of the cells and pn% of the nets are missing. The key challenge in PID is how to add missing cells and nets.In this paper, two “patching-methods” for adding missing nets and cells are proposed. The methods are called abstraction and fusion.Experimental results are very interesting. First, they show that PID is a difficult problem and an arbitrary (and perhaps intuitively sound) method may not produce highquality results. Experiments verify that the abstraction method is a very good predictor and that fusion is not. Specifically, when a circuit has 10% incompleteness, abstraction can predict the final total wirelength with an error of 5.8% while fusion has a 67.8% error in predicting the wirelength in the same circuit.

Fault sets that accurately describe physical failures are required for efficient pattern generation and fault coverage evaluation. The fault model presented in this paper uniquely describes all structural changes in the transistor net list that can be caused by spot defects, including bridging faults that connect more than two nets, break faults that break a net into more than two parts, and compound faults. The developed analysis method extracts the comprehensive set of realistic faults from the layout of CMOS ICs and for each fault computes the probability of occurrence. The results obtained by the tool REFLEX show that bridging faults connecting more than two nets account for a significant portion of all faults and cannot be neglected.

The system-level design process typically involves refining a design specification down to the point where each of the system's components is described as a block diagram or netlist of abstract Register-Transfer (RT) level components. In this paper, we motivate the need for such a standard RT component set, and describe a library environment that supports automatic model generation, design reuse, and synthesis with technology-specific estimators. We demonstrate the efficacy of the standard RT-component set approach with experiments performed on the HLSW92 benchmarks. Our preliminary results indicate only a small overhead of about 10% in using these standard, generic components. We then describe an automatic model generation and technology projection scheme that uses fast (on-line) estimators for predicting the area and delay of generic RT components tuned to a particular technology library with an accuracy of 10%. These model generators and estimators have been integrated with a high-level synthesis system at U.C. Irvine.

Field-programmable systems with multiple FPGAs on a PCB or an MCM are being used by system designers when a single FPGA is not sufficient. We address the problem of partitioning a large technology mapped FPGA circuit onto multiple FPGA devices of a specific target technology. The physical characteristics of the multiple FPGA system (MFS) pose additional constraints to the circuit partitioning algorithms: the capacity of each FPGA, the timing constraints, the number of I/Os per FPGA, and the pre-designed interconnection patterns of each FPGA and the package. Existing partitioning techniques which minimize just the cut sizes of partitions fail to satisfy the above challenges. We therefore present a timing driven N-way partitioning algorithm based on simulated annealing for technology-mapped FPGA circuits. The signal path delays are estimated during partitioning using a timing model specific to a multiple FPGA architecture. The model combines all possible delay factors in a system with multiple FPGA chips of a target technology. Furthermore, we have incorporated a new dynamic net-weighting scheme to minimize the number of pin-outs for each chip. Finally, we have developed a graph-based global router for pin assignment which can handle the pre-routed connections of our MFS structure. In order to reduce the time spent in the simulated annealing phase of the partitioner, clusters of circuit components are identified by a new linear-time bottom-up clustering algorithm. The annealing-based N-way partitioner executes four times faster using the clusters as opposed to a flat netlist with improved partitioning results. For several industrial circuits, our approach outperforms the recursive min-cut bi-partitioning algorithm by 35% in terms of nets cut. Our approach also outperforms an industrial FPGA partitioner by 73% on average in terms of unroutable nets. Using the performance optimization capabilities in our approach we have successfully partitioned the MCNC benchmarks satisfying the critical path constraints and achieving a significant reduction in the longest path delay. An average reduction of 17% in the longest path delay was achieved at the cost of 5% in total wire length.

The design of integrated fault detector for on-line testing of linear analog systems is discussed in this paper. The method consists in a concurrent processing of available the node voltage signals to provide a residual on-line, that carries information about the faults. Contrary to the few previous works dealing with the particular case of state variable analog systems, the method proposed here is useable without limitation for a larger class of linear analog systems, even when the state variables are not available as measurable voltages. For this purpose, an algorithm providing an extended state space model for any linear analog system from its netlist description is developed and implemented.

In this paper, we present a Simulated Evolution Gate Matrix layout Algorithm (SEGMA) for synthesizing CMOS random logic modules. The gate-matrix layout problem is solved as a one-dimensional transistor gates placement problem. Given a placement of all the transistor gates, simulated evolution offers a systematic method to improve the quality of the layout that is measured by the number of tracks needed for the given netlist. This is accomplished by identifying a subset of gates whose relative placements are deemed “poor quality” according to a heuristic criterion. By rearranging the placement of these identified subsets of gates, it is hoped that a gate placement with better quality, meaning fewer tracks, may emerge. Since this method enables the current “generation” of gate placement to evolve into a more advanced one in a way similar to the biological evolution process, this method is called simulated evolution. To apply simulated evolution to solve the gate-matrix layout problem, we propose a novel heuristic criterion, called randomized quality factor, which facilitates the judicious selection of the subset of poor quality gates. Several carefully devised and tested strategies are also implemented. Extensive simulation results indicate that SEGMA is producing very compact gate-matrix layouts.

We present a new approach to the problem of register-transfer level design optimization of pipelined data paths. The output of high level synthesis procedures, such as Sehwa, consists of a schedule of operations into time steps, and a fixed set of hardware operators. In order to obtain a register-transfer level design, we must assign operations to specific operators, values to registers, and finish the interconnections. We first perform module assignment with the goal of minimizing the interconnect requirements between RT-level components as a preprocessing procedure to the RT-level design. This will result in a smaller netlist which makes the design more compact and the design process more efficient. In addition to reducing the total number of interconnects, this approach will also reduce the total number of multiplexors in the design by eliminating unnecessary multiplexing at the inputs of shared modules. The interconnect sharing task is modeled as a constrained clique partitioning problem. We developed a fast and efficient polynomial time heuristic procedure to solve this problem. This procedure is 30–50 times faster than other existing heuristics while still producing better results for our purposes. Using this procedure, we can produce near optimal interconnect sharing schemes in a few seconds for most practical size pipelined designs. This efficient approach will enable designers to explore a larger portion of the design space and trade off various design parameters effectively.