An online task placement algorithm based on maximum empty rectangles in dynamic partial reconfigurable systems

Dynamic Partial Reconfigurable Systems can significantly improve the utilization of hardware by performing multiple tasks on the reconfigurable resources in run-time, whereas the limited reconfigurable resources constraint the number of tasks. To achieve efficient operation of systems, it is crucial to increase the utilization of resources while allocating tasks. This paper proposes a novel MER-based heuristic based on 3D-Adjacency heuristic, trying to reduce the area fragmentation, to improve the utilization rate and to deal with the problem that more than one task may arrive at the same time. It is a new attempt to combine MER technique with adjacency heuristic. Meanwhile, this paper also introduces an innovative task placement algorithm which taking into account the types of resources (like CLBs, RAMs and so on) and their relative positions that tasks contain. Simulation experiment results indicate that our methods have higher resource utilization, a higher task acceptance ratio, and a lower fragmentation ratio compared with some existing methods. Our algorithm can improve 17% to 26% in terms of task acceptance ratio compared to conventional algorithms.