Browse Prior Art Database

"Gzp" Algorithm in LAYOUT

IP.com Disclosure Number: IPCOM000046536D
Original Publication Date: 1983-Aug-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 3 page(s) / 16K

Publishing Venue

IBM

Related People

Cook, PW: AUTHOR [+2]

Abstract

An algorithm for solving an inequality constraint problem without matrices is described. The present algorithm may be useful in VLSI design for generating ground-rule-independent layout files and for translating mask data. A program for VLSI layout recognizes three "types" of rules. As coded for input to the program, these are The symbols ">" and "<" are used because of the limitations of the Fortran character set, and are meant also to allow equality. Thus, if V(x) designates the value of the variable whose name is x, the three rule types have the actual significance For each variable x in LAYOUT, a number of flag values and indicators are kept.

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

Page 1 of 3

"Gzp" Algorithm in LAYOUT

An algorithm for solving an inequality constraint problem without matrices is described. The present algorithm may be useful in VLSI design for generating ground-rule-independent layout files and for translating mask data. A program for VLSI layout recognizes three "types" of rules. As coded for input to the program, these are The symbols ">" and "<" are used because of the limitations of the Fortran character set, and are meant also to allow equality. Thus, if V(x) designates the value of the variable whose name is x, the three rule types have the actual significance For each variable x in LAYOUT, a number of flag values and indicators are kept. These include V(x), the lower bound LB(x), the upper bound UB(x), "levels" for the lower and upper bounds [LBL(x) and UBL(x)], and a flag D(x) which, when true, marks a variable x as defined. In all of this, x is the symbolic name of the variable. In solving the rules part of the problem, the boundary propagation algorithm first factors out all of the equality relationships, so that no inequality exists which refers to a variable appearing in the left hand side of an equality.

This makes the solution of the equalities trivial. The basic algorithm then works to propagate boundary information through the inequalities from one variable to another, starting with one or more known variables. The propagation is somewhat complex. Consider a rule of Type 2. In terms of the boundaries of the appropriate variables, the rule

(Image Omitted)

Thus, if one thinks of a graph representation of the rules, with each node representing a variable, each arc representing a rule, and each arc directed from xi to xd, the propagation of boundary information in the graph is in fact in both directions along each arc (although the specific type of information that is propagating differs). Initially, variables are divided into two classes. Variables which are (as yet) undetermined are initialized to V(x)=0

D(x)=F

LB(x)=0

UB(x)=0

LBL(x)=-1

UBL(x)=-1 Similarly, all variables which are defined (either through an external definition or as a result of previous passes of the algorithm) are initialized to V(x)=value of symbolic variable x

D(x)=T

LB(x)=V(x)

UB(x)=V(x)

LBL(x)=0

UBL(x)=0 Whether or not a variable x, as defined, is determined by D(x); whether or not a bound to a variable has been

1

Page 2 of 3

given any value or not is determined by the appropriate bound level. This latter information is required by the present algorithm because it makes no attempt to order rules in any way; they are rather processed as entered by the user (with the exception of equalities).

All of the processing required by the algorithm can be reduced to two forms of boundary propagation: The complexity of some aspects of the algorithm arise from the fact that no attempt is made to re-order the rules from the order given by the user. The LPROP case will be described in detail, as the UPROP case is essentially the sam...