An efficient cut-based algorithm on minimizing the number of L-shaped channels for safe routing ordering

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.