Scheduling real-time DAGs in heterogeneous clusters by combining imprecise computations and bin packing techniques for the exploitation of schedule holes

In this paper, we investigate the improvement that can be gained in the performance of a heterogeneous cluster dedicated to real-time jobs, by exploiting schedule holes with a novel approach that combines imprecise computations and bin packing strategies. According to the imprecise computations technique, a real-time job can trade off precision for timeliness. Each job that arrives at the system has an end-to-end deadline and is a directed acyclic graph of component tasks, where the output data of a task may be used as input by another task. In case the input data of a task are imprecise, the task’s execution time is extended, in order to correct the error and produce a result of acceptable quality. Due to the data dependencies between the tasks of a job, schedule holes may appear in the schedule of a particular processor. Our approach is compared with other scheduling policies, under various workloads. The simulation results show that in the framework under study, the proposed strategy can lead to a better system performance.

► Investigation of dynamic real-time scheduling of DAGs in a heterogeneous cluster. ► A novel scheduling approach is used for the exploitation of schedule holes. ► The proposed heuristic combines imprecise computations and bin packing techniques. ► The proposed heuristic outperforms other scheduling policies. ► Significant performance improvement in the case of computationally intensive jobs.