Incremental cost calculation for fast wire length minimization

摘要

Compacting layout is the process of shrinking the polygons that were devices and wires, and were represented thorough the GDS (general data stream) standard format. To shrink the polygons under the constraints and rules for VLSI design and manufacturing, there is lots of computation time to find optimum width. Especially, the wire is the most complex and takes the most of the time among devices, such as transistors, resistors, and capacitors in the VLSI design. Proposed is the technique to reduce the most computation time in computation of wire length in the shrinking the VLSI layout design. By applying the incremental technique on the shrinking the wire minimization procedure, the performance of the compaction can be improved compared with the technique without incremental one. Wire length minimization process can be formulated by the linear programming, and find optimum solutions by the Simplex1. The Simplex is the technique to find global solutions, by applying successive conversion with pivoting1. The successive conversion procedure is based on the graph theory; set the initial spanning tree, convert it with less cost if any, repeatedly, until there is tree that has minimum cost. The performance can be achieved since the computation to find the cost is performed only on the transformed tree node of the spanning tree