Scheduling real-time computations on hypercubes with load balancing

Abstract

This paper discusses the problem of scheduling hard real-time jobs on hypercube machines. Our model is different from traditional systems in that a job in our systems may be terminated if there is not enough time, producing an acceptable but less precise result. Each job thus can be divided into a hard (real-time) task which must always be finished before its deadline, and a flexible soft task which is executed only if there is enough processor time left. All hard tasks are scheduled first so that at least a minimally acceptable result is available for each job, but soft tasks are scheduled only after all hard tasks are done. We propose a new scheduling algorithm which combines the ahorteet refinement first algorithm with the well-known gradient load balancing method. The performance of the algorithm is studied by simulations.