Constraint-driven floorplan repair

Floorplanning algorithms have traditionally underperformed experienced designers, even when relatively simple interconnect metrics are concerned. However, the sheer scale of modern systems on chip makes an all-manual design flow infeasible. In this paper, we propose a new efficient automated approach to the floorplan repair problem, where a set of violated design constraints are satisfied by applying small changes to an existing rough floorplan. Such a floor-plan can be produced by a human designer, by a scalable placement algorithm, or result from engineering adjustments to a pre-existing floorplan. In all cases, overlapping modules must be separated, and in some instances, modules may need to be repositioned to satisfy other requirements. The algorithmic framework we propose is built upon an expressive graph-based encoding of constraints. While capable of representing floorplans with or without overlapping modules, it can also support the outline of the core area, fixed module locations, region constraints, proximity and alignment constraints, etc. Instead of applying randomized local search in the hope of satisfying these constraints, we track all implications of imposed constraints and resolve violations by invoking gradual modifications to the floor-plan. The primary focus of this paper is on a particularly efficient conflict-directed algorithm for floorplan repair and legalization. It is shown to completely eliminate overlaps from layouts produced by Capo 9.4, Feng Shui 5.1 and APlace 2.01 on IBM-HB benchmarks with hard blocks; typically requiring negligible runtime and increasing interconnect length by only several percent. Furthermore, we are able to generate legal solutions for these instances that surpass previously reported results in wirelength by an average of roughly 7%