Constrained floorplanning using network flows

This paper presents algorithms for a constrained version of the "modern" floorplanning problem proposed by Kahng in "Classical Floorplanning Harmful?" (Kahng, 2000). Specifically, the constrained modern floorplanning problem (CMFP) is suitable when die-size is fixed, modules are permitted to have rectilinear shapes and, in addition, the approximate relative positions of the modules are known. This formulation is particularly useful in two scenarios: 1) assisting an expert floorplan architect in a semiautomated floorplan methodology and 2) in incremental floorplanning. CMFP is shown to be negative-positive hard. An algorithm based on a max-flow network formulation quickly identifies input constraints that are impossible to meet, thus permitting the floorplan architect to modify these constraints. Three algorithms [Breadth First Search (BFS), Improved BFS (IBFS), Compromise BFS (CBFS)] based on using BFS numbers to assign costs in a min-cost max-flow network formulation are presented. Experiments on standard benchmarks demonstrate that IBFS is fast and effective in practice.