A New Method for Defining Monotone Staircases in VLSI Floorplans

Physical design of a chip typically entails the global routing (GR) step after detailed placement. In this step, the grid graph (GG) model is used widely for the one or two-bend pattern routing stage. While several iterations may be required for GR, these may be reduced with appropriate route planning at the floor planning stage. In this case, the routing regions can be identified as recursive top-down bipartitioning by either straight cut lines or monotone staircases. The capacity of each region is estimated as the number nets that can fit in it without design rule violation. Given a floor plan, identifying a set of monotone staircases such that (a) the balance in area of each bipartition is maximized, (b) the number of nets cut, and (c) the number of bends in a monotone staircase are minimized, is a multi-objective optimization problem and is NP-hard. The existing heuristic methods are based on either max flow or directed search on floor plan adjacency graph. In this paper, we propose a new monotone staircase bipartitioning method using a randomized neighbor search technique. Compared to the earlier methods, our experimental results on a set of floor planning benchmark circuits demonstrate on an average 3% improvement in the cost function, as well as 9% and 7% in the number of vias and congestion after global routing.