Hierarchical Partitioning of VLSI Floorplans by Staircases

摘要

This article addresses the problem of recursively bipartitioning a given floorplan F using monotone staircases. At each level of the hierarchy, a monotone staircase from one corner of F to its opposite corner is identified, such that (i) the two parts of the bipartition are nearly equal in area (or in the number of blocks), and (ii) the number of nets crossing the staircase is minimal. The problem of area-balanced bipartitioning is shown to be NP-hard, and a maxflow-based heuristic is proposed. Such a hierarchy may be useful to repeater placement in deep-submicron physical design, and also to global routing.