Browse Prior Art Database

PDQROUTE - a Rapid Line Router for Automatically Generating Interconnections on a Logic Diagram

IP.com Disclosure Number: IPCOM000044331D
Original Publication Date: 1984-Dec-01
Included in the Prior Art Database: 2005-Feb-05
Document File: 6 page(s) / 84K

Publishing Venue

IBM

Related People

Lesser, JD: AUTHOR

Abstract

PDQROUTE is a heuristic line router which automatically generates the interconnections on a logic diagram sheet on which the logic blocks and the pin names have already been placed. Output from PDQROUTE is a character representation of a routed logic diagram sheet which can be displayed on a suitable display, such as the IBM 3277. The interconnection information is also available in the form of a vector list which contains a pair of end-point coordinates (x1,y1,x2,y2) for each interconnection segment in the diagram and a list of the x,y coordinates of all corner locations in the diagram.

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 20% of the total text.

Page 1 of 6

PDQROUTE - a Rapid Line Router for Automatically Generating Interconnections on a Logic Diagram

PDQROUTE is a heuristic line router which automatically generates the interconnections on a logic diagram sheet on which the logic blocks and the pin names have already been placed. Output from PDQROUTE is a character representation of a routed logic diagram sheet which can be displayed on a suitable display, such as the IBM 3277. The interconnection information is also available in the form of a vector list which contains a pair of end-point coordinates (x1,y1,x2,y2) for each interconnection segment in the diagram and a list of the x,y coordinates of all corner locations in the diagram.

Written in PL/1, PDQROUTE operates on 2 two-dimensional character arrays representing an NxM sheet image of an EDS-like logic diagram, a logic diagram in which the blocks line up vertically in columns and pins are located on either the left or righthand side of the blocks.

The first array, called PICT, contains the character representation of all blocks and pin (signal) names on the sheet. The second array, called BTAB, is a shadow image of the first array, except that in the BTAB array information is coded in terms of routing blockage. Making one pass over a pin list containing the locations of all pins on the sheet, PDQROUTE quickly generates the interconnections net by net, using a 'greedy' algorithm which has some local lookahead. Required as input to this procedure are a block list and a net/pin list which describe the logic. The block list contains for each block in the diagram a separate record which specifies the block location (the x,y coordinates of the upper lefthand corner of the block) and the width and length of the block. This block area is coded in BTAB as 'hard blockage', since no routing is permitted through it. Each block record also contains 'soft blockage' information. 'Soft blockage' areas are generated on both sides of a block by extending the block rectangle to include the longest pin names to the right and left of the 'hard blockage' rectangle. Each block record specifies the x,y coordinates of the upper lefthand corner, and width and length of the 'soft blockage' rectangle. The term 'soft blockage' is used because in some cases, a route can extend into it. Fig. 1 shows how this block information is reflected in the PICT and BTAB arrays. The net/pin list contains a separate record for each pin on the sheet, and the pin records are grouped by net. Each pin record specifies the x,y coordinates of the pin location on the sheet, the block to which it belongs, and whether the pin is a source or sink pin (i.e., on the left or right-hand side of the block) or a sheet I/O pin (primary input or output pin). PDQROUTE PROCEDURE I. Process all block records in the block list. From the hard and soft blockage information for all blocks, compute the number of block columns, the number of vertical routing channels, and the number of tracks avai...