Timing model extractor builds a timing model of a digital circuit for use with a static timing analyzer. This paper proposes a novel method of generating a gray box timing model from gate-level netlist by reducing a timing graph. Previous methods of generating timing models sacrificed accuracy and/or did not scale well with design size. The proposed method is simple, yet it provides model accuracy including arbitrary levels of latch time borrowing and capability to support timing constraints that span multiple blocks. Also, cpu and memory resources required to generate the model scale well with size of the circuit. The generated model can provide a capacity improvement in timing verification by more than two orders of magnitude.

Variants of delay-cost functions have been used in a class of technology mapping algorithms [l, 2, 3, 41.We illustrate that in an industrial environment the delay-cost function can grow unboundedly and lead to very large runtimes.The key contribution of this work is a novel bounded compression algorithm.We introduce a concept of a delaycost curve, (o-DC-curve)that requires upto exponentially less delay-cost points to be stored compared to that stored by the delay function.We prove that the solution obtained by this exponential compaction of the delay-function is bounded to cy% of the optimal solution.We also suggest a large set of CAD applications which may benefit from using Q-DC-curve.Finally, we demonstrate the effectiveness of our compaction scheme on one such application, namely technology mapping for low power.Experimental results on industrial environment show that we are more than 17 times faster than [2] on certain MCNC circuit.

In this paper we formulate the problem of timing analysis with known false sub graphs. This problem is important when we want the timing analysis system to take into account false path information that is supplied either by the user or by another program, and supply accurate timing information to optimization programs such as placement and wiring. We present an efficient algorithm for the problem.

Two approaches to handling the computational requirements of computer-aided design problems are considered. One approach is to take advantage of the hierarchical nature of circuit design and develop hierarchical CAD algorithms. Another involves the use of parallel processing and development of parallel CAD algorithms. How these two approaches can be combined to speed up various CAD applications is discussed. Toward this goal, two general problems in scheduling are solved: parallelizable independent task scheduling (PITS) and parallelizable dependent task scheduling (PDTS). The PITS scheduling theory is applied to a parallel hierarchical circuit extractor, and the PDTS scheduling theory is applied to a parallel hierarchical global router. Both implementations show speedups of about six on eight processors of a shared-memory multiprocessor.>

The authors deal with reconfiguration of a rectangular array of processors arranged as an N*N mesh, and a complete binary tree of N processors. They present new reconfiguration techniques that are modifications of the Diogenes approach proposed earlier by A.L. Rosenberg et al. (1983). These techniques reduce the overheads incurred in the earlier Diogenes schemes. Some of the previous approaches to the problem are summarized. Two schemes are presented for reconfiguring rectangular arrays and a scheme for reconfiguring trees. For the analysis of the different schemes presented, it is assumed that a processor has a square layout. These schemes are analyzed and their performance results are presented.>

Parallel algorithms for the geometric connected component labeling (GCCL) problem on a hypercube multiprocessor can be designed by dividing the domain, consisting of a number of rectangles, into regions using a slice or rectangular partitioning scheme. Each processor in the hypercube is assigned one partition. The processor determines the connected sets of rectangles in its partition. The connected sets at different processors have to then be combined across processors into globally connected sets. This merging problem is defined as the GCCL problem. Different algorithms for the GCCL problem are presented. Each of the algorithms involves d stages of message passing, for a d-dimensional hypercube. The basic idea in these algorithms is that in each stage a processor increases its knowledge of the domain. The algorithms described in this paper differ in their run time, memory requirements, and message complexity. These algorithms have been implemented on an Intel iPSC2/D4/MX hypercube.>

The authors propose parallel algorithms to speedup the VLSI circuit extraction task. Given a VLSI layout as input, the problem of circuit extraction consists of determining the circuit connectivity and estimating the various electrical parameters such as the resistances of lines, capacitances of nodes, and dimensions of devices. Circuit extraction is a computationally intensive problem. The basic approach used in the parallel algorithms is the partitioning of a circuit into small regions, assigning each region to a processor and having the processors cooperate in performing the extraction procedures. The authors present a number of partitioning strategies that could be used. The authors have implemented the parallel algorithms on an Intel iPSC2 hypercube and an Encore 510 multimax shared memory multiprocessor.>

An algorithm is presented that combines the benefits of hierarchical analysis and parallelism. The input is a hierarchical description of the circuit. The authors formulate and solve a general problem in scheduling. The parallel algorithm for hierarchical circuit extraction has been implemented on an Encore shared memory multiprocessor.>

An algorithm, PACE2, is described which is targeted to the second phase of extraction, called the parameter extraction phase. The authors have interfaced two models for resistance and capacitance. They propose a different partitioning scheme, namely, by equal number of rectangles, so as to balance the load. The parallel algorithm has been implemented on the Intel iPSC2/D4-MX hypercube.>

Hypercube multiprocessors achieve a cost-effective and feasible approach to supercomputing by directly connecting a large number of low-cost processors with local memory, which cooperate on tasks by message-passing. An efficient parallel algorithm to speed up the VLSI circuit extraction task on a hypercube multiprocessor is proposed. The basic approach consists of partitioning of a circuit into smaller regions, assigning each region to a processor of the hypercube, and having the processors cooperate in performing the extraction procedures. The algorithm supports the use of different models for electrical parameter calculations of varying degrees of accuracy and computational complexity. The algorithm has been implemented in a program called PACE (parallel circuit extractor) on the Intel iPSC/D4-MX hypercube. Speedup results for the algorithm on many realistic VLSI circuits are presented.>

Reconfiguration strategies in VLSI processor arrays have been advocated in the recent literature as a means of achieving higher production yield and higher reliability. The authors present reconfiguration techniques for rectangular arrays that are generalizations of the Diogenes approach proposed earlier by A.L. Rosenberg (1983). These techniques overcome many of the limitations of the earlier Diogenes schemes. Two schemes for reconfiguring rectangular arrays are presented. The first scheme for reconfiguring an N*N rectangular array uses r additional rows and c additional columns. It guarantees reconfiguration as long there are at most c columns that have more than r faulty processors. The second scheme uses spare processors. It guarantees reconfiguration as long as there are enough spare processors, and in any window of N processors in a particular linearization there are at most k faulty processors, where k is a parameter of the design.>