Browse Prior Art Database

Path Connection Methodology for LSI Circuits

IP.com Disclosure Number: IPCOM000084159D
Original Publication Date: 1975-Sep-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 2 page(s) / 29K

Publishing Venue

IBM

Related People

Ellozy, HA: AUTHOR

Abstract

A technique for determining paths having the minimum wiring lengths and the minimum number of bends in a large-scale integrated (LSI) chip is described herein.

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

Page 1 of 2

Path Connection Methodology for LSI Circuits

A technique for determining paths having the minimum wiring lengths and the minimum number of bends in a large-scale integrated (LSI) chip is described herein.

The path connection methodology (PACO) makes use of the cell calculus proposed by J. P. Roth in IBM research report (RA 50) (7/5/73) entitled "Algorithmic Design III. Embedding; Diagnosis, Hard and Soft". The method can be subdivided into the following two major algorithms: i) The determination of the set of chains linking the source to the target, LINK; and ii) The calculation of the "minimum" path among these chains, MINPATH.

The LINK algorithm determines the sets of connecting paths (chains) required to connect the various points on the chip.

The MINPATH algorithm determines the chain of cells of minimum wiring length and, within this chain, calculates the path having minimum bends.

(Image Omitted)

(Image Omitted)

(Image Omitted)

III. ADVANTAGES.

1. Very compact representation of data. The standard path connection algorithms require on the order of one-half byte to store information for every grid point. For example, a 200x200 grid would require on the order of 20K-30K bytes of storage. Assuming about 400 wire segments on the grid, PACO would require on the order of 2K bytes of storage.

2. The present day algorithms perform a point-by-point search, whereas this algorithm performs the topologically equivalent channel-by-channel search, increasing the search sp...