Browse Prior Art Database

BRANCH-AND-BOUND ALGORITHM for VHV ROUTING in IRREGULAR CHANNELS

IP.com Disclosure Number: IPCOM000034450D
Original Publication Date: 1989-Feb-01
Included in the Prior Art Database: 2005-Jan-27
Document File: 4 page(s) / 19K

Publishing Venue

IBM

Related People

Chen, H: AUTHOR [+3]

Abstract

A branch-and-bound algorithm is described herein for the three-layer VHV-routing problem in channels with irregular upper and lower boundaries. Such channels can arise between adjacent macro cells in custom design, or in standard cell design in which the cells have varying heights, thus causing irregular channels between adjacent rows of standard cells. In the VHV-channel-routing model, layer 1 is used for the vertical segments originating from the upper boundary of the channel, layer 3 for the vertical segments originating from the lower boundary, and layer 2 for all horizontal segments. Since the vertical segments originating from the opposite sides are on different layers, there are no vertical constraints on the track assignment of the horizontal segments.

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

Page 1 of 4

BRANCH-AND-BOUND ALGORITHM for VHV ROUTING in IRREGULAR CHANNELS

A branch-and-bound algorithm is described herein for the three-layer VHV-routing problem in channels with irregular upper and lower boundaries. Such channels can arise between adjacent macro cells in custom design, or in standard cell design in which the cells have varying heights, thus causing irregular channels between adjacent rows of standard cells. In the VHV-channel-routing model, layer 1 is used for the vertical segments originating from the upper boundary of the channel, layer 3 for the vertical segments originating from the lower boundary, and layer 2 for all horizontal segments. Since the vertical segments originating from the opposite sides are on different layers, there are no vertical constraints on the track assignment of the horizontal segments. The only constraints are the non-overlapping constraints on the horizontal segments. Thus the underlying constraint graph is an undirected interval graph. An interval graph is constructed by having a vertex for each interval (horizontal segment), and edges are introduced between pairs of vertices which correspond to overlapping intervals.

It can be proved that the VHV-routing problem is NP-complete for channels with irregular boundaries. Therefore, it is unlikely that there is a polynomial time algorithm for finding the optimal solution. A branch-and-bound algorithm for optimal VHV-routing in channels with irregular boundaries is described here. The algorithm partitions the channel into boxes, and searches for the optimal among the various mappings of the horizontal net segments to the boxes. Pruning the search is done using infeasibility, dynamic upper bounds, and computation of a non-trivial static lower bound. The algorithm performs well in practice. THE MODEL A collection of horizontal segments of the nets is given. It is assumed that no jogs can be introduced in the horizontal segments, therefore the horizontal segments can be represented as closed intervals on the integer line. A channel with irregular upper and lower boundaries is also given with the following assumptions about the channel. 1. The two boundaries are fixed, and the only flexibility in the channel is the vertical movement of the two

boundaries towards or away from each other. 2. The channel is convex in the vertical direction. That is, any vertical line drawn through the channel will

cut the upper and lower boundaries at exactly one point

each. 3. The upper and lower boundaries of the channel can be

separated by a horizontal line. In other words, when

minimizing the number of tracks in the channel, the two

boundaries cannot be pushed towards each other in such

a way that some portion of the lower boundary is above

some portion of the upper boundary. An irregular channel can be partitioned into rectangular regions called boxes, by extending all horizontal portions of the two boundaries. Because of assumptions 1 and 3, the only flexible box...