Constant Complexity Management of 2D HW Multitasking in Run-Time Reconfigurable FPGAs

This paper presents a constant complexity and fast algorithm for the management of run-time reconfigurable resources by an operating system with extended hardware multitasking functionality. Our algorithm manages a two dimensional reconfigurable device by dividing the resource area into four partitions with different sizes. Each partition has an associated queue where the hardware manager places each arriving task depending on its size, shape, deadline requirements and the state of queues. It is possible to merge partitions for tasks not fitting any partition. The sizes of the partitions may be adapted to different circumstances.