Browse Prior Art Database

Premaze Runner Analyzer

IP.com Disclosure Number: IPCOM000081057D
Original Publication Date: 1974-Mar-01
Included in the Prior Art Database: 2005-Feb-27
Document File: 4 page(s) / 47K

IBM

Related People

Hanan, M: AUTHOR [+2]

Abstract

This is a method for determining whether a path exists between any pair of points before actually employing a maze-runner. Hence, it saves considerable time in path connection problems, e.g. logical drawings, wire-routing routing or optimal path finding algorithms.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 49% of the total text.

Page 1 of 4

Premaze Runner Analyzer

This is a method for determining whether a path exists between any pair of points before actually employing a maze-runner. Hence, it saves considerable time in path connection problems, e.g. logical drawings, wire-routing routing or optimal path finding algorithms.

Lee's algorithm or some version of it is used extensively within and outside of IBM in wire routing programs. (The algorithm is sometimes referred to as a "maze-runner" since it guarantees to find the way out of a maze in an efficient manner.) Wire-routing programs usually employ a combination of heuristics and a maze-runner. The heuristic is used to wire the simple connections (e.g., the collinear connections), and the maze-runner is used to wire those connections which cannot be wired with simple heuristics.

The main drawback to the maze-runner is the computation time involved. If no wire (or path) exists between a pair of points to be connected, then time is wasted determining this fact. According to the technique disclosed below, a determination is made whether a path exists between any pair of points before the maze-runner is used.

As background material, the wire-routing problem is discussed in general terms. We are given an array of cells placed on a "board" and a list of pairs of cells which must be connected. Also, associated with each cell boundary there is a "capacity", which is the number of wires that can cross the cell boundary.

After a certain point in the wire-routing program, e.g., after the heuristic algorithm fails to wire any more connections, some capacities on the cell boundaries may have become zero. This in effect means a "blockage" is generated since a wire can no longer cross this boundary. If the set of blocked lines forms a closed curve or a continuous line whose end points join with the edge of the board, then the set of cells is partitioned into, at least, two regions. If a connection has its terminating points in different regions, there exists no path connecting them.

Lee's algorithm, as taught in "An Algorithm for Path Connections and Its Application"; C. Y. Lee, IRE TRANS. ELEC. COMP., Vol. EC-10, No. 3 (Sept. 1961) pp. 346-365, guarantees to find a path if it exists. However, if no path exists then time is wasted determining this fact by using a maze-runner. The present algorithm eliminates the necessity of attempting Lee's algorithm for each individual connection.

In one example, a heuristic was used to wire 288 connections out of a total of 297. At this point the premaze-runner analyzer was employed and 5 regions generated. It was then determined that 7 of the remaining 9 connections could not be made since their terminal points were in different regions. (The other two connections were completed using Lee's algorithm.) The regions generated are shown in the table, which is an actual computer output.

The computation time for the maze-runner is a function of the length of the shortest path between the two point...