A fast and efficient algorithm for finding empty area is necessary for online placement, task relocation and defragmentation on a partially reconfigurable FPGA. We present an algorithm that finds empty area as a list of overlapping maximal rectangles. Using an innovative representation of the FPGA, we are able to predict possible locations of the maximal empty rectangles. Worst-case time complexity of our algorithm is O(xy) where x is the number of columns, y is the number of rows and x.y is the total number of cells on the FPGA. Experiments show that, in practice, our algorithm needs to scan less than 15% of the FPGA cells to make a list of all maximal empty rectangles.

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.

Summary form only given. Placement time is an overhead on the application execution time in an online placement system. In a partially reconfigurable system, the inherent parallelism of the reconfigurable hardware can be explored to speed up the placement process. We present three different architectures for two dimensional online placement. Each architecture makes different trade-offs between area usage, memory requirement and execution time. These architectures are capable of achieving very fast placement while using a very small number of hardware resources.