JigsawPlanner: Jigsaw-like Floorplanner for Eliminating Whitespace and Overlap among Complex Rectilinear Modules

As an early step in physical design, floorplanning plays a pivotal role in determining the performance upper bounds for downstream tasks and greatly impacts the PPA (power, performance, area) of the system. Efforts in floorplanning usually simplify modules as rectangles; however, assumptions of rectangular modules are not necessary for modern floorplan designs but could restrict floorplan solutions, typically resulting in lower chip area utilization with whitespace or overlaps among modules. In this paper, we challenge the widely accepted fixed-outline floorplanning problem setting which could lead to an inherent trade-off between whitespace and overlaps. We introduce JigsawPlanner, a novel and flexible Jigsaw-like floorPlanner that facilitates floorplanning to handle complex-shaped rectilinear modules. Given a global floorplan solution derived from an analytical method, we obtain the central positions of each module. Subsequently, we respectively partition the chip and modules into multiple grids and submodules, and assign these submodules to the grids using hierarchical Jonker-Volgenant algorithms and Cellular Automata. Empirical evaluations on public datasets show that JigsawPlanner can effectively eliminate white-space and overlaps simultaneously and significantly reduce the Half Perimeter Wire Length (HPWL) by an average of 10.50% compared to state-of-the-art baselines.