Constraint graph (layout)

In some tasks of integrated circuit layout design a necessity arises to optimize placement of non-overlapping objects in the plane. In general this problem is extremely hard, and to tackle it with computer algorithms, certain assumptions are made about admissible placements and about operations allowed in placement modifications. Constraint graphs capture the restrictions of relative movements of the objects placed in the plane. These graphs, while sharing common idea, have different definition, depending on a particular design task or its model.

Floorplanning

In floorplanning, the model of a floorplan of an integrated circuit is a set of isothetic rectangles called "blocks" within a larger rectangle called "boundary" (e.g., "chip boundary", "cell boundary").

A possible definition of constraint graphs is a s follows. The constraint graph for a given floorplan is a directed graph with vertex set being the set of floorplan blocks and there is an edge from block b1 to b2 (called horizontal constraint), if b1 is completely to the left of b2 and there is an edge from block b1 to b2 (called vertical constraint), if b1 is completely below b2.

If only horizontal constraints are considered, one obtains the horizontal constraint graph. If only vertical constraints are considered, one obtains the vertical constraint graph.

Under this definition, the constraint graph can have as many as $O(n^2)$ edges, where n is the number of blocks. Therefore other, less dense constraint graphs are considered. The horizontal visibility graph is a horizontal constraint graph in which the horizontal constraint between two blocks exists only if there is a horizontal line segment which connects the two blocks and does not intersect any other blocks. In other words, one block is a potential "immediate obstacle" for moving another one horizontally. The vertical visibility graph is defined in a similar way.

Channel routing

Channel routing example

Channel routing is the problem of routing of a set of nets N which have fixed terminals on two opposite sides of a rectangle ("channel"). In this context, the horizontal constraint graph is the undirected graph with vertex set N and two nets are connected by an edge if and only if horizontal segments of the routing must overlap. In the given example, only nets 5 and 6 do not have a horizontal constraint between them. The vertical constraint graph is the directed graph with vertex set N and two nets are connected by an edge if and only if there are two pins from different nets on the same vertical line and the edge is directed from the net with pin on the upper edge of the channel. This direction means that this net must be routed on a horizontal track above the horizontal tracks of the second net. In the given example, only nets 1 and 3 have a vertical constraint.^[1]

References

1. Shi, Z.; Feng, D.D.; Shimohara, K. (2006). Intelligent Information Processing III: IFIP TC12 International Conference on Intelligent Information Processing (IIP 2006), September 20-23, Adelaide, Australia. Springer. p. 308. ISBN 9780387446417. Retrieved 2015-01-01.