This paper reviews the step-response of the semi-in nite distributed RC line and focuses mainly on the step-response of a nite-length RC line with a capacitive load termination, which is the most common model for a wire inside the present d a y i n tegrated CMOS chips.In particular, we obtain the values of some of the common threshold-crossing times at the output of such a line and show that even the simplest rst order lumped -approximation to the nite-length RC line terminated with a capacitive load is good enough for obtaining the 50% and 63.2% threshold-crossing times of the step-response.Higher order lumped approximations are necessary for more accurate predictions of the 10% and 90% thresholdcrossing times.

A general sequential circuit consists of a number of combinational stages that lie between latches. For the circuit to meet a given clocking specification, it is necessary for each combinational stage to satisfy a certain delay requirement. Roughly speaking, increasing the sizes of some transistors in a stage reduces the delay, with the penalty of increased area. The problem of transistor sizing is to minimize the area of a combinational stage, subject to its delay being less than a given specification. Although this problem has been recognized as a convex programming problem, most existing approaches do not take full advantage of this fact, and often give nonoptimal results. An efficient convex optimization algorithm has been used here. This algorithm is guaranteed to find the exact solution to the convex programming problem. We have also improved upon existing methods for computing the circuit delay as an Elmore time constant, to achieve higher accuracy, CMOS circuit examples, including a combinational circuit with 832 transistors are presented to demonstrate the efficacy of the new algorithm.>

The problem of partitioning the vertex set of an edge-weighted undirected graph into two parts of specified sizes so that the cost of the partition defined as the sum of the weights on edges joining vertices in different parts is minimized is addressed. This problem is NP-hard and has several important applications in VLSI layout, where the graph size is typically large and the brute-force approach of listing all feasible partitions and comparing costs is computationally prohibitive. It is shown that if the n*n connection matrix of the graph has rank p, then the search can be confined to a smaller set of n/sup p(p+1)/2/ partitions. Procedures are developed for constructing all such partitions in O(n/sup p(p+3)/2/) time. For matrices with large rank, a principal components approximation of the connection matrix is suggested. The algorithms provide a bound on the proximity of the cost of the constructed partition to the optimal cost based on the eigenvalues left out in the rank reduction process.>

The transistor sizing problem of minimizing the circuit area, subject to the circuit delay being less than a given specification, is formulated as a convex programming problem. An efficient convex programming algorithm is then used to obtain the exact solution. Experimental results on a variety of circuits show that, for a given delay specification this approach is able to produce circuits with significantly smaller area when compared with TILOS.>

A systematic methodology for automatic consistency checking and optimization of parameterized macromodels is described. An overview of the entire macromodel verification system. iMAVERICK, is provided. An efficient stochastic algorithm to optimize the parameters of a given macromodel is described, and a number of characteristics of the algorithm are examined. A heuristic measure of the likelihood that a cost evaluation will provide useful information or a better solution that is used in the algorithm is based on the information accumulated from the previous cost evaluations. This heuristic measure is used to reject poor sample points without sacrificing the quality of solutions. A waveform comparison technique for evaluating the performance of the proposed configuration in the optimization process is described. It is sensitive to phase errors between waveforms and has the capability of filtering out glitches and high-frequency noise. Several examples of macromodel optimization using the iMAVERICK system are presented.>

A novel technique is introduced, called stochastic evolution (SE), for solving a wide range of combinatorial optimization problems. It is shown that SE can be specifically tailored to solve the network bisection, traveling salesman, and standard cell placement problems. Experimental results for these problems show that SE can produce better quality solutions than sophisticated simulated annealing (SA)-based heuristics in a much shorter computation time.>

There are two canonical optimization problems, namely, NETWORK BISECTIONING (NB) and TRAVELING SALESMAN (TS), that emerge from the physical design and layout of integrated circuits. In this paper, we use an analogy between iterative techniques for combinatorial optimization and the evolution of biological species to obtain the Stochastic Evolution (SE) heuristic for solving a wide range of combinatorial optimization problems. We show that SE can be specifically tailored to solve both NB and TS. Experimental results for the NB and TS problems show that the SE algorithm produces better quality solutions and is faster than the Simulated Annealing algorithm in all instances considered.

The graph bisectioning problem has several applications in VLSI layout, such as floorplanning and module placement. A sufficient condition for optimality of a given bisection is presented. This condition leads to an algorithm that always finds an optimal bisection for a certain class of graphs. A greedy approach is then used to develop a more powerful heuristic. On small random graphs with up to 20 vertices, one of the greedy algorithms generated the optimal bisection in each case considered. For very large graphs with 300 vertices or more, the algorithm generated bisections with costs within 30% of a lower bound previously derived. An adaptive algorithm that iteratively improves upon a given initial bisection of a graph is presented. Its performance is compared with that of the well-known Kernighan-Lin method on many random graphs with large numbers of vertices. The results indicate that the new adaptive heuristic produces bisections with costs within 2% of those produced by the Kernighan-Lin method (the costs were actually lower in about 70% of the cases) with a three times faster computation speed in most cases.>

In the design of application specific integrated circuits (ASIC), it is often required to partition a logic complex into smaller subcomplexes satisfying a number of constraints. Due to the complexity of the problem, most existing algorithms try to optimize on only one constraint. In this paper, we use the concept of evolution to derive a partitioning algorithm capable of handling a number of constraints. Our algorithm provides a uniform multi-way partitioning scheme, obtains good partitions, and has a fast execution time.

A decomposition technique known as node tearing is used to perform circuit simulation on a multiprocessor. The effect of partitioning the circuit on the final speedup achieved is considered. Using a very simple model for the LU decomposition time of sparse matrices, a circuit-partitioning problem based on node tearing is formulated to maximize speedup on a multiprocessor. An abstract hypergraph partitioning problem is then posed along with an algorithm for its solution. The original circuit partitioning problem is then transformed into an equivalent hypergraph partitioning problem, thereby generating partitions for the circuit. The effect of the tradeoff of circuit-partitioning time versus the number of available processors on the speedup factor is also studied.>

A hierarchical parasitic circuit extractor HPEX for Manhattan layouts is described. HPEX can model interconnection lines as distributed lumped circuits directly from a circuit layout by using analytical formulas instead of numerical methods. The difference in feature sizes between mask layouts and actual fabricated conductors is also taken into account by a geometrical preprocessing algorithm based on a novel Y-X scanline method and a simple rectangle data structure. In addition, a simple and accurate node reduction technique based on the concept of Elmore's delay is employed in HPEX to make layout verification simpler. All features mentioned above clearly indicate that HPEX will be a promising tool in verifying VLSI system performance especially when interconnect parasitics associated with VLSI circuits are taken into consideration.

This paper describes the algorithms used in a presimulation phase to partition an MOS digital network into various special subnetworks (or blocks) and to order these subnetworks for processing in a switch-level timing simulator such as MOSTIM [1]. A transistor-level SPICE2-type [3] description of the network is assumed to be provided. The key to the partitioning strategy is to divide the set of enhancement transistors into driver and pass transistors. The driver transistors are then grouped together in a de-connected sense to form multiple-input single-output combinatorial logic blocks, while the pass transistors are grouped together to form pass transistor blocks. A graph algorithm performs the partitioning step in computation time that is linear with the number of enhancement transistors. The partitioning step is an automatic process that is completely transparent to the user. The partitioned blocks are then ordered for simulation such that, whenever possible, a block is scheduled for processing only after all its input waveforms are known. A clear and precise notion of feedback among the various blocks in the partitioned network is introduced, and a distinction is made between feedback among different blocks and feedback internal to a block. It is shown that a good ordering for processing the blocks in a network is possible only in the absence of any form of feedback among the blocks. In case of a partitioned network with feedback, a linear time algorithm is presented that detects the strongly connected blocks, which are then flagged for simulation using special dynamic windowing techniques [4]. The strongly connected components are then topologically ordered for simulation.