Static scheduling techniques for dependent tasks on dynamically reconfigurable devices

Dynamically reconfigurable hardware not only has high silicon reusability, but it can also deliver high performance for computation-intensive tasks. Advanced features such as run-time reconfiguration allow multiple tasks to be mapped onto the same device either simultaneously or multiplexed in time domain. These tasks need to be scheduled optimally or near optimally in order to efficiently utilize the device. It is a NP-hard problem, because task scheduling, allocation and configuration prefetching all need to be considered. In this paper, we target dependent task models and propose three static schedulers that use different problem solving strategies. The first is a heuristic approach developed from traditional list-based schedulers. It presents high efficiency but the least accuracy. The second is based on a full-domain search using constraint programming. It can guarantee to produce optimal solutions but requires significant searching effort. The last is a guided random search technique based on a genetic algorithm, which shows reasonable efficiency and much better accuracy than the heuristic approach.