Browse Prior Art Database

Improved Local Wiring of Movable Terminals in VLSI Chips

IP.com Disclosure Number: IPCOM000042433D
Original Publication Date: 1984-May-01
Included in the Prior Art Database: 2005-Feb-03
Document File: 3 page(s) / 38K

Publishing Venue

IBM

Related People

Coppersmith, D: AUTHOR [+3]

Abstract

In the local wiring of very-large scale integrated (VLSI) chips having interconnection terminals which can be moved along the boundary of the blocks while maintaining their relative ordering fixed, the problem of specifying the placement of the terminals within each functional block and a description of the actual wiring can be found using a dynamic programming algorithm. The placement is essentially an assignment of each terminal to a vertical track, and the actual wiring is a complete specification of the vertical and horizontal tracks used by the various segments in each connection. Assuming there are two vertically aligned functional blocks, with A1, A2, ..., AT labeled the terminals in the upper block and B1, B2, BT the terminals in the lower block, a connection function f: (1,..., T) (1, ...

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

Page 1 of 3

Improved Local Wiring of Movable Terminals in VLSI Chips

In the local wiring of very-large scale integrated (VLSI) chips having interconnection terminals which can be moved along the boundary of the blocks while maintaining their relative ordering fixed, the problem of specifying the placement of the terminals within each functional block and a description of the actual wiring can be found using a dynamic programming algorithm. The placement is essentially an assignment of each terminal to a vertical track, and the actual wiring is a complete specification of the vertical and horizontal tracks used by the various segments in each connection. Assuming there are two vertically aligned functional blocks, with A1, A2, ..., AT labeled the terminals in the upper block and B1, B2, BT the terminals in the lower block, a connection function f: (1,..., T) (1, ..., T) may be defined which specifies that terminal Ai be connected to terminal Bf(i) . A placement restriction is imposed requiring that in any solution the placement of terminals be such that terminals Ai and Bj share the same vertical track only if j=f(i). This restriction does not eliminate the possibility of finding a minimum width solution; it is always possible to transform any minimum width solution into a solution which satisfies the placement restriction simply by identifying any terminals which violate the restriction and moving one of these terminals to an adjacent newly added vertical track. Such placement restriction implies that there are no vertical constraints, which permits wiring each connection with just one horizontal segment. Thus, given a placement which satisfies such restriction, each connection requirement can be viewed as forming an interval on the real line, the end points of the interval being determined by the placement of the two terminals. Then a track assignment algorithm can be used to assign the horizontal segments of each connection to the appropriate horizontal track in a manner which ensures that the minimum number is horizontal tracks are used. This minimum number of simply given by the maximum crossing number (MCN) of the intervals. The crossing number at some point is the number of intervals that have their left end points on or to the left of that point and their right end points to the right of that point; the MCN is the maximum over-all points on the real line. Assume now that vertical tracks are scanned from left to right, and at each track a terminal from the upper or the lower functional block (or from both) is placed. Let us say...