Browse Prior Art Database

Adaptive Sparse Grid Generation for Printed Circuit Board Auto-Router

IP.com Disclosure Number: IPCOM000116647D
Original Publication Date: 1995-Oct-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 4 page(s) / 179K

Publishing Venue

IBM

Related People

Hama, T: AUTHOR

Abstract

Disclosed is a method for generating sparse partial grid for an auto-router for Printed Circuit Board (PCB), and also a method for updating the partial grid as routing task proceeds. An auto-router finds a route between a pin-pair by applying shortest path algorithm to the partial grid, and its efficiency depends on the number of nodes in the grid. The partial grid generated by this method is always maintained to be as sparse as possible in order to retain the efficiency of the shortest path algorithm.

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

Adaptive Sparse Grid Generation for Printed Circuit Board Auto-Router

      Disclosed is a method for generating sparse partial grid for an
auto-router for Printed Circuit Board (PCB), and also a method for
updating the partial grid as routing task proceeds.  An auto-router
finds a route between a pin-pair by applying shortest path algorithm
to the partial grid, and its efficiency depends on the number of
nodes in the grid.  The partial grid generated by this method is
always maintained to be as sparse as possible in order to retain the
efficiency of the shortest path algorithm.

      The grid generator divides the routing region into rectangles,
and generates a partial grid using the rectangles.  In the following
paragraphs, a method for generating a partial grid is described, and
then a method for updating the partial grid after a wire is placed on
the routing region is described.

      The grid generator generates horizontal and vertical grids
separately.  Fig. 1 shows an example of horizontal grid generation.
Horizontal (vertical) boundaries of all the objects (a board 1,
terminals 2, inhibited regions 3) are extended until they encounter
other objects.  Then, among the rectangles into which the extended
boundaries divide a routing region, the generator selects, as
horizontal (vertical) grid, rectangles (hatched rectangles in Fig. 1)
whose lower horizontal (right vertical) boundary touches upper
horizontal (left vertical) boundary of an objects and whose upper
horizontal (left vertical) boundary touches lower horizontal (right
ve...