A solution to drawbacks in capturing execution requirements on heterogeneous platforms

摘要

Real-time embedded systems are increasingly being implemented onheterogeneous multiprocessorplatforms in which the same piece of software may require different amounts of time to execute on different processors. Computation of optimal schedules for such systems is non-trivial. Recently, Zhang et al. proposedlinear and dynamic programmingalgorithms for real-time task scheduling for heterogeneous platforms. The authors have formulated alinear programming problemwhich is then iteratively solved by the linear programming algorithm (LPA) to produce a feasible schedule. Further, they compared the performance of LPA against their proposed dynamic programming algorithm (DPA) and claimed that LPA is superior to DPA, in terms of scalability. In this paper, we show that theirlinear programming problem does not correctly capture the execution requirement of real-time tasks on heterogeneous platforms. Consequently, LPA fails to produce valid execution schedules for most task sets presented to it. We first illustrate this flaw and strengthen our claim theoretically using a counterexample. Then, we present necessary modifications to their linear programming formulation to address the identified flaw. Finally, we show that our proposed algorithm can be used to find a feasible schedule for real-time task sets, using a real-world case study and experiments.