Browse Prior Art Database

Cost Measure Computation for Placement and Routing

IP.com Disclosure Number: IPCOM000049454D
Original Publication Date: 1982-Jun-01
Included in the Prior Art Database: 2005-Feb-09
Document File: 3 page(s) / 32K

Publishing Venue

IBM

Related People

Gracer, F: AUTHOR [+2]

Abstract

A method is described herein for computing general classes of cost measures suitable for use in placement and routing in a design automation system with advantages in both speed and store requirements. Further, the measures can be easily changed by the designer without program modification.

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

Page 1 of 3

Cost Measure Computation for Placement and Routing

A method is described herein for computing general classes of cost measures suitable for use in placement and routing in a design automation system with advantages in both speed and store requirements. Further, the measures can be easily changed by the designer without program modification.

The physical design of a computer requires the placement of circuit packages which must be interconnected with minimal wire length to form a backplane. The backplane itself consists of a hierarchy of intra and inter wired packages. For the sake of being concrete, however, and without loss of generality, the method described is in terms of placement of modules to form boards. (Other levels of the backplane can be similarly treated). The board can be represented as a pxq rectangularly arranged set of locations or slots in which the modules must be placed.

The placement and routing (interconnection) routines require the extensive computation of distances for the trial placement and/or interconnection of modules. In general, the measure employed is that of rectilinear distance, i.e., (see original), where (x(i), y(i)) and (x(j), y(j)) are the locations of modules i and j.

There are technologies and applications where a non-rectilinear distance is demanded. For example, Euclidean distance (see original) is also employed. Frequently, in backplanes, there is even a mixture of rectilinear and Euclidean distances, corresponding to right angle and point to point wiring.

Occasionally there are other measures of a layout used beside minimal wire length. For example, with right angle wiring, it may be required to keep minimal the maximum wire length in either the vertical or horizontal dimension in addition to securing near minimal total wire distance. In that case, the following measure can be adopted as an artifice to achieve the stated goal and still aim at minimal total wire length. (See original), where d(i,j) equals I x(i)-x(j) I/M/ + y(i)-...