A fast algorithm for finding maximal empty rectangles for dynamic FPGA placement

Abstract

In this paper, we present a fast algorithm for finding empty area on the FPGA surface with some rectangular tasks placed on it. We use a staircase data structure to report the empty area in the form of a list of maximal empty rectangles. We model the FPGA surface using an innovative encoding scheme that improves runtime and reduces memory requirement of our algorithm. Worst-case time complexity of our algorithm is O(xy) where x is number of columns, y is number of rows, and x.y is the total number of cells on the FPGA.