Efficient algorithm for functional scheduling in hardware/software co-design

Task scheduling is one of the crucial steps during functional hardware/software co-design. Due to the possibly concurrent execution of the tasks implemented in hardware, the NP-hard scheduling problem becomes more difficult to solve optimally. In this paper an efficient algorithm is proposed for task scheduling in functional hadware/software co-design. The proposed algorithm assigns the priority for each task combining the information both in the communication penalty and the hardware-only critical path, to enhance the parallelism of the tasks. A large body of experimental results confirm that the proposed algorithm is superior to the most widely used approaches first-come first-schedule(FCFS) and level-by-level schedule (LBLS) in hardware/software scheduling, both for random graphs and some realistic application graphs, without large increase in running time. The improvement over FCFS and LBLS is up to 10% for some random graphs, and it is more significant for FFT application graphs, according to the simulation results on the same types of graphs (under the same assumptions) as in the literature where LBLS is employed