An Online Task Placement Algorithm Based on MER Enumeration for Partially Reconfigurable Device

摘要

Recently, due to the development of technology, the embedded application becomes more and more complex. Consequently, not only the performance of chips, but also the flexibility and dynamic adaptation of the implemented systems are required. To achieve these requirements, the partially reconfigurable device is promising. In this paper, we propose a novel online task placement algorithm based on the Maximal Empty Rectangle (MER) enumeration for partially reconfigurable device. On the assumption that each task utilizes the rectangle shaped resources, we propose a very simple but powerful algorithm to enumerate MERs. Then, by utilizing the result of MER enumeration, the fragmentation of the reconfigurable device can be reduced during task's assignment. Finally, we analyze the complexity of the proposed algorithm and confirm its efficiency empirically.