Title :
A faster compaction algorithm with automatic jog insertion
Author :
Mehlhorn, Kurt ; Näher, Stefan
Author_Institution :
Fachbereich Inf., Univ. des Saarlands, Saarbrucken, West Germany
fDate :
2/1/1990 12:00:00 AM
Abstract :
The work of F.M. Maley (Proc. Chapel Hill Conf. on VLSI, p.261-83, 1985) on one-dimensional compaction with automatic jog insertion is refined. More precisely, an algorithm with running time O((n2+k)log n), where k=O(n3) is a quantity which measures the difference between the input and output sketch, is given, and Maley´s O(n4) algorithm is improved. The compaction algorithm takes as input a layout sketch, the wires in a layout sketch are flexible and only indicate the topology of the layout. The compactor minimizes the horizontal width of the layout while maintaining its routability. The exact geometry of the wires is filled in by a router after compaction
Keywords :
VLSI; circuit layout CAD; network topology; CAD; IC design; O(n4) algorithm; VLSI layout; automatic jog insertion; compaction algorithm; layout sketch; topology; Circuit synthesis; Compaction; Geometry; Productivity; Routing; Shape; Topology; Very large scale integration; Wires; Wiring;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on