A new approach to fault-tolerant scheduling using task duplication in multiprocessor systems
In this paper we propose a new approach to fault-tolerant scheduling of parallel programs in multiprocessor systems. It is well known that inter-processor communication makes serious effects on the performance of parallel processing, and that task duplication is an effective technique to reduce overheads of communication. Though it was originally developed only for improving performance, we propose the use of this technique also for achieving fault-tolerance. Based on this approach, we develop a scheduling algorithm for tolerating a single processor failure. This algorithm duplicates all tasks of a program and allocates them to processors so as to eliminate communication delays as much as possible. The experimental results show that the obtained schedules can achieve fault-tolerance at the cost of small degree of time redundancy.
fault-tolerant scheduling task duplication mutiprocessor task graph interprocessor communication delay