Fast online task placement on FPGAs: free space partitioning and 2D-hashing

Partial reconfiguration allows for mapping and executing several tasks on an FPGA during runtime. Multitasking on FPGAs raises a number of questions on the management of the reconfigurable resource which leads to the concept of a reconfigurable operating system. A major aspect of such an operating system is task placement. Online placement methods are required that achieve a high placement quality and lead to efficient implementations. This paper presents placement methods that rely on efficient algorithms for the partitioning of the reconfigurable resource and a hash matrix data structure to maintain the free space. Given n as the number of currently placed tasks, previously known placers find a feasible location in O(n) time. Our approach is able to find a feasible location in constant time. Additionally, simulations show that our methods improve the placement quality by up to 70%.