Fault-secure scheduling of arbitrary task graphs to multiprocessor systems
Kazumune Hashimoto, Tatsuhiro Tsuchiya, Tohru Kikuno · 2002
Proposes new scheduling algorithms to achieve fault security in multiprocessor systems. We consider the scheduling of parallel programs represented by directed acyclic graphs with arbitrary computation and communication costs. A schedule is said to be 1-fault-secure if the system either produces correct output for a parallel program or it detects the presence of any single fault in the system. Although several 1-fault-secure scheduling algorithms have been proposed so far, they can all only be applied to a class of tree-structured task graphs with a uniform computation cost. In contrast, the proposed algorithms can generate a 1-fault-secure schedule for any given task graph with arbitrary computation costs. Applying the new algorithms to two kinds of practical task graphs (Gaussian elimination and LU-decomposition), we conduct simulations. Experimental results show that the proposed algorithms achieves 1-fault security at the cost of a small increase in schedule length.