Improved Local Wiring of Movable Terminals in VLSI Chips
Original Publication Date: 1984-May-01
Included in the Prior Art Database: 2005-Feb-03
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, ...