Multi-Shape Task Placement Algorithm Based on Low Fragmentation Resource Management on 2D Heterogeneous Dynamic Partial Reconfigurable Devices

Abstract

The Dynamic Partial Reconfiguration function of reconfigurable devices permits tasks to be performed simultaneously on a single device. Nevertheless, task placement and resource management problems emerge with the parallelism of reconfigurable devices. Traditional task placement algorithms are based on the assumption of a homogeneous architecture and simplify the task as a rectangular shape, which inevitably results in internal unused areas, thereby wasting a significant amount of programmable resources. To address the resource waste that comes with the assumption of a rectangular task shape and improve the placement quality, we adopted an interval list set to manage available programmable resources for a heterogeneous reconfigurable device and proposed an interval-based placement algorithm combined with a low-fragmentation selection strategy targeting the placement problem of multi-shape tasks. The efficiency of the proposed approach is proved theoretically, and simulation results demonstrate that the rejection ratio is decreased by at least 8.9% with an average fragmentation reduction of 18.1%.

Keywords

• Multi-shape task
• task placement algorithm
• dynamic partial reconfiguration
• heterogeneous reconfigurable device