''Maximal Strips Data Structure to Represent Free Space on Partially Reconfigurable FPGAs''
J. L. Trahan
International Journal of Parallel, Emergent and Distributed Systems
(IJPEDS), special issue on APDCM'08,
vol. 24, no. 4, pp. 349-366, 2009.
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 free space 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 on real-time tasks compared to other methods.
This work was supported in part by
the National Science Foundation under grant number CCR-0310916.