Scheduling Parallel Loops Under Faulty Processors
Bob Broeg, Vikram A. Saletore, Jie Liu, John C. W. Marsaglia · 1993
Most of the self-scheduling schemes that schedule parallel loops having variable execution time per iteration assume the number of processors in unchanged. This paper introduces methods which enhance existing schemes by making them more tolerant of the loss of processors during loop execution. We discuss two different cases. In the first case, a processor completes its assigned iterations but is reassigned by the operating system to another job before the current job is completed. In the second case, a processor fails before it can complete its assigned iterations. There iterations must then be reassigned to other processors. The first case implemented by taking advantage of the two phase (static and self-scheduling) approach of SSS [11]. We propose using a scheme which is insensitive to processor faults during SSS''s self-scheduling phase. The second case is handled by adding a third phase to SSS. This phase performs self-scheduling on the unfinished iterations. Both methods are implemented, and benchmarks are given. Key Words: parallel loops, self-scheduling, load balance, faulty processors, processor utilization.