This paper presents algorithms for a constrained version of the "modern" floorplanning problem proposed by Kahng in "Classical Floorplanning Harmful?" [1]. Specically, 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 semi-automated floorplan methodology and (2) in incremental floorplanning. CMFP is shown to be NP 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 (BFS, IBFS, 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 BFS and IBFS are fast and obtain zero whitespace floorplans.
展开▼
