Algorithms of Reconfigurable Resource Management and Hardware Task Placement

Reconfigurable computing system has the flexibility of traditional CPU and the speed of ASIC approximately. Based on the ability of partially dynamic reconfiguration, the tasks can be dynamically reconfigured on the reconfigurable hardware at runtime. Some hardware tasks can run at the same time with the execution of the reconfiguration process of other tasks. To some extent, the runtime reconfiguration overhead can be hidden and the system performance can be improved. Reconfigurable computing has become one of the most important computing methods. With the improvement of the size and integration, such as FPGA, more and more tasks can run and/or resident on the reconfigurable hardware concurrently. In order to utilize the reconfigurable hardware efficiently, the reconfigurable resource management and hardware task placement are very important. A task-top based keep all maximal empty rectangles (TT-KAMER) algorithm is presented in this paper. Maximal empty rectangles can efficiently represent all the empty reconfigurable resources on the reconfigurable hardware. Based on the TT-KAMER algorithm, hardware task placement can also be implemented by the first fit algorithm and the heuristic best fit algorithm. The results indicate that the algorithms can implement resource allocation and on-line task placement efficiently, and high reconfigurable resource utilization can be obtained.