Jt. Yan, An efficient cut-based algorithm on minimizing the number of L-shaped channels for safe routing ordering, IEEE COMP A, 18(10), 1999, pp. 1519-1526
Citations number
23
Categorie Soggetti
Eletrical & Eletronics Engineeing
Journal title
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
Because definition of L-shaped channels in a floorplan graph breaks all the
cyclic precedence constraints in a building block layout, routing space in
a layout can be fully separated and defined as straight and L-shaped chann
els to guarantee a safe routing ordering. However, L-shaped channel routing
is more difficult than straight channel routing. Hence, it is necessary fo
r the completion of detailed routing to minimize the number of L-shaped-cha
nnels in channel definition of a floorplan graph. In this paper, based on a
geometrical topology of a floorplan graph and precedence relations in a ch
annel precedence graph, cuts in a floorplan graph are classified into S-cut
s, redundant L-cuts, balanced L-cuts, nonminimal L-cuts, noncritical L-cuts
and critical L-cuts. An efficient cut-based algorithm on minimizing the nu
mber of L-shaped channels in channel definition of a floorplan graph is pro
posed, and the time complexity of our cut-based algorithm is proved to be i
n O(n) time, where n is the number of line segments in a floorplan graph. F
inally, several examples have been tested on Dal's algorithm [5], Cai's alg
orithm [15] and our cut-based algorithm, respectively. The experimental res
ults show that our cut-based algorithm defines fewer L-shaped channels in a
floorplan graph than Dai's algorithm and Cai's algorithm to guarantee a sa
fe routing ordering.