Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Automatic Wiring System for Ultra LSIS

IP.com Disclosure Number: IPCOM000104590D
Original Publication Date: 1993-May-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 2 page(s) / 90K

Publishing Venue

IBM

Related People

Ezaki, T: AUTHOR [+2]

Abstract

Disclosed is a system for designing Ultra LSI physical layout using compression or expansion of the wiring regions for X-Y dimensional direction. Regarding wiring algorithm, maze is the most widely known technique to design LSI physical layout. But this algorithm can not always guarantee 100% automatic wiring. Therefore, using invented compaction/expansion algorithm with maze, 100% automatic wiring can be guaranteed to design LSI physical layout.

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

Automatic Wiring System for Ultra LSIS

      Disclosed is a system for designing Ultra LSI physical layout
using compression or expansion of the wiring regions for X-Y
dimensional direction.  Regarding wiring algorithm, maze is the most
widely known technique to design LSI physical layout.  But this
algorithm can not always guarantee 100% automatic wiring.  Therefore,
using invented compaction/expansion algorithm with maze, 100%
automatic wiring can be guaranteed to design LSI physical layout.

      The compaction algorithms adapted in this system are mainly
compression ridge method which is well known technique and an
invented optimum jog position determination algorithm for further
more efficient and fast compaction.  At least one grid downward
compaction with no redundant jogs can be guaranteed if jogs are
inserted at the appropriate positions determined by this algorithm.
The expansion algorithm is the opposite compaction method, whose
algorithm expands wiring space to connect unwiring points, if maze
can not connect completely.  Using both compaction and expansion
algorithm, automatic wiring system can guarantee to execute 100
wire-ability in physical layout.  Compression ridge utilizes maze
method as a exploration technique of vacant series points, which is
starting at the left-edge of the wiring region and continues until
either the right-edge of the wiring region is reached.  compression
ridge, removing this compression ridge results in at least one-grid
downward compaction.  In order to realize more efficient compaction,
not only horizontal and vertical exploration, but also slant
exploration in the wiring region is utilized by recent compression
ridge method.  To improve the compaction ratio more effectively,
optimized-jog insertion algorithm is invented using via replacement
and bundle jog method.  Following is this invented algorithm.

      If considering the optimized-jog insertion into a single
horizontal line, the different points from previously mentioned
compression ridge exploration are following:

1.  In searching a next upper or lower vacant point from the current
    position, even if there is a horizontal wiring at the position,
    it is allowed to be regarded as a vacant point.  At the same
    time, it should be memorized as a cross-point of the line and
    then the sea...