An efficient algorithm for free resources management on the FPGA
Yi Lu, Thomas Marconi, Georgi Gaydadjiev, Koen Bertels · 2008
Finding the available empty space for arrival tasks on FP-GAs with runtime partially reconfigurable abilities is the most time consuming phase in on-line placement algorithms. Naturally, this phase has the highest impact on the overall system performance. In this paper, we present a new algorithm which is used to find the complete set of maximum free rectangles on the FPGA at runtime. During scanning, our algorithm relies on dynamic information about the edges of all already placed tasks. Simulation results show that our algorithm has 1.5x to 5x speedup compared to state of the art algorithms aiming at maximum free rectangles. In addition, our proposal requires at least 4.4x less scanning load.