Browse Prior Art Database

Wire Layer Assignment

IP.com Disclosure Number: IPCOM000077172D
Original Publication Date: 1972-Jun-01
Included in the Prior Art Database: 2005-Feb-25
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Rubin, F: AUTHOR

Abstract

In certain technologies, notably large-scale integrated circuit chips, wires must be routed on single layers of multilayer circuit boards. The wiring process is greatly aided if a proper assignment of the wires to the layers available is made in advance. Such an algorithm is presented here.

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

Page 1 of 1

Wire Layer Assignment

In certain technologies, notably large-scale integrated circuit chips, wires must be routed on single layers of multilayer circuit boards. The wiring process is greatly aided if a proper assignment of the wires to the layers available is made in advance. Such an algorithm is presented here.

The basis for an assignment is to make up some measure of whether two wires conflict or not, and to minimize the sum of these measures over all wire pairs. A very simple measure is to assume some simple canonical path for each wire, say the straight line between its endpoints. Then the measure will be 1 if the paths intersect, 0 if they do not. The algorithm here is designed for any such 0-1 measure of interference, but will work satisfactorily with other measures.

It is fairly well known that an assignment can be improved by reassigning wires to layers on which they have fewer intersections. Even more improvement could be achieved by reassigning wire pairs. However, the cost of considering all wire pairs increases as W/3/ for W wires (since there are 1/2 W/2/ distinct pairs, and the cost of testing a pair is 2W intersection tests). This is too expensive for practical problems.

However, it can be shown mathematically that whenever a pair can be profitably reassigned, but that neither wire in the pair could be reassigned profitably, then one of the wires must be reassigned at equal cost. This suggests that reassignment of equal-cost wires would allow profitable reassignment of the other wire in certain pairs.

Although random reassignment of wires appears to be a reasonable approach, there is a specific technique which will increase the like...