Browse Prior Art Database

Improved Hierarchical System for Global Wiring in VLSI Chips

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

Publishing Venue

IBM

Related People

Burstein, M: AUTHOR [+2]

Abstract

Global wire routing for very large-scale integrated (VLSI) chips can be performed by hierarchical partitionings of the chip network and sequential wiring at every level of hierarchy. The global wiring stage is to be first reduced to a problem of wiring within a (2 X N) grid of cells (Image Omitted) Let e(1), e(2),... , e(M) denote the set of nets. Each net e(i) is identified with a set of cells of this array, called terminal cells of this net. If cell C(i,j) is a terminal cell for the net e(k), then at least one of the LST-s of this net is located somewhere within this cell. There is also a 2 X (N-1) matrix of horizontal channel capacities; h(1,1), h(1,2), ... , h(1,n-1) h(2,1), h(2,2), ... , h(2,n-1) and an N-vector of vertical channel capacities v(1), v(2), ...

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 56% of the total text.

Page 1 of 1

Improved Hierarchical System for Global Wiring in VLSI Chips

Global wire routing for very large-scale integrated (VLSI) chips can be performed by hierarchical partitionings of the chip network and sequential wiring at every level of hierarchy. The global wiring stage is to be first reduced to a problem of wiring within a (2 X N) grid of cells

(Image Omitted)

Let e(1), e(2),... , e(M) denote the set of nets. Each net e(i) is identified with a set of cells of this array, called terminal cells of this net. If cell C(i,j) is a terminal cell for the net e(k), then at least one of the LST-s of this net is located somewhere within this cell. There is also a 2 X (N-1) matrix of horizontal channel capacities; h(1,1), h(1,2), ... , h(1,n-1) h(2,1), h(2,2), ... , h(2,n-1) and an N-vector of vertical channel capacities v(1), v(2), ... , v(N) associated with the array; h(i,j) denotes the number of available wiring tracks crossing the boundary between the cells C(i,j) and C(i,j+1); v(i), similarly, denotes the number of tracks between C(1,i) and C(2,i). The heuristic solution of the global wiring herein described is based on (2 X
2) grids and uses a recursive procedure. First, the (2 x N) grid is vertically partitioned into two parts, generally in half. Then a "factorized" (2 x 2) wiring problem is constructed considering only the new cut line and the horizontal lines as cell boundaries: After this (2 X 2) grid is routed, the problem is reduced to smaller size problems (2 X N1...