A solution to drawbacks in capturing execution requirements on heterogeneous platforms

Real-time embedded systems are increasingly being implemented on heterogeneous multiprocessor platforms 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. proposed linear and dynamic programming algorithms for real-time task scheduling for heterogeneous platforms. The authors have formulated a linear programming problem which 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 their linear 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.