Global Routing Using Monotone Staircases with Minimal Bends

This work proposes a top-down hierarchical monotone staircase bipartitioner of VLSI floorplans minimizing the number of bends in the obtained staircase channels at each level. Further, two more objectives are considered: (a) maximizing the ratio of the areas of each of the two partitions, and (b) minimizing the number of nets cut by a staircase at each level of the hierarchy. A pair of trade-off parameters β ,γ ∈ [0, 1] are used in the multi-objective optimization method. In our experiments, at each level of the hierarchy the (β ,γ) pair which yields the optimal monotone staircase cut is chosen from a set of values for both β and γ such that β +γ ≤1. The hierarchy of monotone staircase channels obtained is used for global routing with a recent monotone staircase channel based global router, STAIRoute, to estimate the effect of bend minimization on the number of vias using horizontal-vertical (HV) reserved layer model. The results for 8 metal layers on MCNC and GSRC benchmarks are promising.