Gridless router using maze and line probe techniques

Details Gridless router using maze and line probe techniques Gridless router using maze and line probe techniques

2001-03-08

2003-04-08

Nguyen, Cuong Quang (Department: 2811)

Active solid-state devices (e.g., transistors, solid-state diode

Thin active physical layer which is

Heterojunction

Reexamination Certificate

active

06545288

ABSTRACT:

BACKGROUND
This invention generally relates to maze routers and routing methods, and more specifically relates to a router and method which reduces the amount of data needed to plot routing space and determine a route therein.
It is common to use software tools and plotting methods (i.e. maze routers) to design routes or paths from targets to sources in a routing space. Such tools and methods are used to quickly plot out efficient routes in the routing space, where the routing space contains obstructions or the routes must meet certain design criteria. For example, it is common to use a maze router to route vias and wire paths from sources to targets in a multiple layer routing space.
One known algorithm for determining routes in a routing space is disclosed in Lee, C. Y., “An Algorithm for Path Connections and Its Applications”, IRE Transactions on Electronic Computers, VEC-10, pp.346-365, September 1961. Lee discloses plotting a grid to define the routing space, and then analyzing the grid points from a source to a target to determine the best route. Unfortunately, because Lee plots all the grid points in the grid which form the routing space, Lee requires that much data be used to define a given routing space. This is true even if the routing space contains little or no obstructions (i.e. blocks) and is generally a wide open space. With Lee, the size of the representation (i.e. the data which is needed to represent) of the routing space depends on the actual size of the routing space, regardless of the number of obstructions (i.e. blocks) in the routing space.
Lee also requires that to effectively go around a block, several steps must be attempted until the block can be cleared. Obviously, this consumes processing time, and may cause the router to take a long time to calculate the routes. For example, the number of steps which must be attempted to go East when a block is in the way will depend on the size of the block. Specifically, a step to the North or South is taken, and an attempt is made to turn East. If the block is still in the way, another step to the North or South is taken, and another attempt is made to turn East. The process is repeated until a turn can be made to the East. By having to attempt so many steps to go around a block, processing time is consumed, and performance of the router suffers.
Lee also does not take into account design rules while plotting the grid. Hence, after using the Lee algorithm to route paths, design rule checks (DRC) must be performed to ensure that the proposed design is acceptable. Additionally, Lee does not take into consideration any costs which are associated with the routes which are calculated.
Korn, Robert K., “An Efficient Variable-Cost Maze Router”, 19th Design Automation Conference, pp. 425-431, June 1982 discloses a maze routing algorithm which does take cost into account. However, other than accounting for costs, which Lee does not do, Korn provides many of the same disadvantages as Lee provides.
OBJECTS AND SUMMARY
A general object of an embodiment of the present invention is to provide a maze router and method which reduces the size of data which is needed to define routing space.
Another object of an embodiment of the present invention is to provide a maze router and method which obviates the need to run design rule checks after routes have been plotted.
Still another object of an embodiment of the present invention is to provide a maze router and method which takes less processing time (i.e. less time to plot routing space, and less time to determine routes in the routing space).
Briefly, and in accordance with at least one of the foregoing objects, an embodiment of the present invention provides a software tool and/or method for routing paths in a routing space. A grid is effectively built “on the fly”, therefore reducing the number of grid points which must be plotted. The boundaries of the routing space are defined. Blocks are then defined in the routing space. After the blocks have been defined, grid points are plotted corresponding to the corners of the blocks. The source points and target points are plotted, and grid points are plotted corresponding to the source and target points. Then, the paths from the source points to the target points are plotted along grid points which have been defined in the routing space. This process of defining the grid points not only preferably reduces the size of data needed to describe the available routing space, but preferably obviates the need to run design rule checks.


REFERENCES:
patent: 6182272 (2001-01-01), Andreev et al.
patent: 6412102 (2002-06-01), Andreev et al.
Lee, C.Y., “An Algorithm For Path Connections and Its Applications”, IRE Transactions on Electronic Computers, VEC-10, pp. 346-365, Sep., 1961.
Korn, Robert K., “An Effective Variable-Cost Maze Router” 19th Design Automation Conference, pp. 425-431, Jun. 1982.
Knuth, Donald, “The Art of Computer Programming”, vol. 3, pp. 458-475, published earlier than Mar. 8, 2001.

Affiliated with

Also associated with

Rating

Gridless router using maze and line probe techniques does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Gridless router using maze and line probe techniques, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Gridless router using maze and line probe techniques will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3014408