''Maximal Strips Data Structure to Represent Free Space on Partially Reconfigurable FPGAs''
J. L. Trahan
Proc. Workshop on Advances in Parallel and Distributed Computational Models (APDCM 08)
Partially reconfigurable devices allow the execution of multiple tasks
simultaneously on the same chip. To schedule a set of tasks in a
small amount of time, the scheduling algorithm will need to represent the
free space efficiently.
A data structure to represent the free space on the chip should allow the
scheduler to identify free space in which to place a new task and
admit efficient updates after placing or removing a task.
In this paper, we review some existing data structures and
analyze their time complexity.
We propose a new structure using maximal horizontal and vertical strips to
represent the free space.
These strips start and stop at task boundaries.
Simulation and time analysis showed that this method has
better time complexity than many other free space data structures and
at the same time has a very reasonable rejection ratio compared to
other methods on real-time tasks.
This work was supported in part by
the National Science Foundation under grant number CCR-0310916.