Dynamic, Reliability-driven Scheduling of Parallel Real-time Jobs in Heterogeneous Systems

Xiao Qin
Griffith University, Australia
xqin@cse.unl.edu

Hong Jiang
Department of Computer Science and Engineering
University of Nebraska-Lincoln
Lincoln, NE 68588-0115, (jiang@cse.unl.edu)

In this paper, a heuristic dynamic scheduling scheme for parallel real-time jobs in a heterogeneous system is presented. The parallel real-time jobs studied in this paper are modelled by directed acyclic graphs (DAG). We assume a scheduling environment where parallel real-time jobs arrive at a heterogeneous system following a Poisson process. The scheduling algorithms developed in this paper take the reliability measure into account, in order to enhance the reliability of the heterogeneous system without any additional hardware cost. In addition, scheduling time and dispatch time are both incorporated into our scheduling scheme so as to make the scheduling result more realistic and precise. Admission control is in place so that a parallel real-time job whose deadline cannot be guaranteed is rejected by the system. The performance of the proposed scheme is evaluated via extensive simulations. The simulation results show that the heuristic algorithm performs significantly better than two other algorithms that do not consider reliability cost. Furthermore, results suggest that shortening the scheduling time results in a higher guarantee ratio. Hence, if parallel scheduling algorithm is devised and employed to shorten the scheduling time, the performance of the heterogeneous system will be further enhanced.

in Proceedings of the 30th International Conference on Parallel Processing (ICPP 2001), Valencia, Spain, September 3-7, 2001.

---