Fast On-Line Task Placement and Scheduling on Reconfigurable Devices

This paper focus on on-line placement and scheduling of tasks with known executing time on reconfigurable devices. The notion of recognition-earliest for scheduling algorithms is introduced, that is the algorithm can arrange the start time of a newly arrived task as early as possible. A new scheduling algorithm is proposed. By exploit the knowledge about temporal properties of each task, the algorithm attains recognition-earliest. A fast placement algorithm is also presented. The evaluation results show that the proposed placement algorithm is one of the fastest algorithm, and the proposed scheduling algorithm achieves the best performance compared with previous algorithms, while has a quite low runtime cost.