Non-Preemptive Scheduling of Periodic Tasks with Data Dependencies in Heterogeneous Multiprocessor Embedded Systems

Heterogeneous multiprocessor architecture is frequently employed as an economical and efficient means of providing excellent parallel processing capabilities while keeping production cost and power consumption under control. Although this architecture achieves significant performance enhancement and cost reduction, it results in a serious task allocation and scheduling problem, especially for periodic tasks with data dependencies, all of which should be reasonably scheduled and executed in a timely manner such that their deadlines and dependence requirements could be satisfied even if the worst happens. In this article, we concentrate on the non-preemptive scheduling problem of periodic tasks with data dependencies upon heterogeneous multiprocessor platforms. First, with models of data-dependent tasks and heterogeneous processors, we analyze the time, space, precedence, and data dependence constraints of tasks and design an exact formulation based on the mixed integer linear programming to completely explore the solution space and produce the optimal solutions. Then, by constructing a directed acyclic graph to depict the dependence relationship of jobs generated by tasks, we propose an efficient off-line list-based scheduling algorithm to provide a reasonable time and processor allocation for each job, with a view to minimizing the completion time of jobs. Experiments with randomly generated tasks are performed to evaluate the effectiveness and efficiency of the proposed algorithm, and the experimental results show that our algorithm can averagely enhance the scheduling success ratio by 28.5%, and, respectively, reduce the task completion time and the deviation ratio by 23.3% and 17.2%, on average.