Title :
On locally optimal breaking of complex cyclic vertical constraints in VLSI channel routing
Author :
Johnson, Anthony D.
Author_Institution :
Dept. of Electr. Eng. & Comput. Sci., Toledo Univ., OH, USA
Abstract :
Existing theory has supported deterministic polynomial time procedures for locally optimal breaking (LOB) of two classes of directed circuits (DC) in the vertical constraint graph, the classes of vertex disjoint DCs, and of couples of connected DCs. New LOB theory is reported that supports procedures for LOB of any number of DCs sharing a common vertex, or a common path, and of DCs in uniform ladder VCGs. A significant aspect of the new theory is that it relies on procedures for couples of connected DCs as tools for breaking more complex structures of connected DCs. Application of the theory in genetic channel routers is reported elsewhere
Keywords :
VLSI; approximation theory; circuit layout CAD; genetic algorithms; integrated circuit layout; network routing; polynomials; LOB theory; VLSI channel routing; common path; common vertex; complex cyclic vertical constraints; connected DC; deterministic polynomial time procedures; directed circuits; genetic channel routers; locally optimal breaking; uniform ladder VCG; vertex disjoint DC; Computer science; Constraint theory; Costs; Coupling circuits; Distributed control; Genetics; Lattices; Polynomials; Routing; Very large scale integration;
Conference_Titel :
VLSI, 1996. Proceedings., Sixth Great Lakes Symposium on
Conference_Location :
Ames, IA
Print_ISBN :
0-8186-7502-0
DOI :
10.1109/GLSV.1996.497600
