Browse Prior Art Database

Knowledge-Based Overflow Embedder for VLSI Routing

IP.com Disclosure Number: IPCOM000119396D
Original Publication Date: 1991-Jan-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 1 page(s) / 48K

Publishing Venue

IBM

Related People

Chang, HT: AUTHOR [+3]

Abstract

The process of routing a set of nets such that all nets are properly connected is characterized by the finding of disjoint path in a graph, which is proved to be NP-complete. Automatic routers will route a very high percentage of the total nets, but will generally terminate with nets remaining to be routed. A Lee's algorithm applied to net routing on a grid system will find any existing path to route a net. An overflow condition exists when there are nets remaining to be wired and Lee's algorithm fails to find a path.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 63% of the total text.

Knowledge-Based Overflow Embedder for VLSI Routing

      The process of routing a set of nets such that all nets
are properly connected is characterized by the finding of disjoint
path in a graph, which is proved to be NP-complete. Automatic routers
will route a very high percentage of the total nets, but will
generally terminate with nets remaining to be routed.  A Lee's
algorithm applied to net routing on a grid system will find any
existing path to route a net.  An overflow condition exists when
there are nets remaining to be wired and Lee's algorithm fails to
find a path.

      Well known processes, "Rip Up and Reroute", and "Shove Aside"
are used by chip physical designers to manually embed overflows.
These processes have been incorporated in both standard procedural
language programs, and logic programs (LISP, PROLOG) with limited
success.

      The logic programs in general search the database of nets to be
routed and compared the nets with the database of configurations that
have solutions.  When a comparison is successful, the program must be
written such that all cases of possible overflows are considered, and
all solutions are coded.

      The procedural programs route overflows ignoring wire
violations.  Then nets that were wire violations are ordered and an
attempt is made to wire those nets without causing additional
violations.  All of these programs are based on manipulating existing
nets with overflow nets.  The database represents...