Probabilistic Rotation: Scheduling Graphs with Uncertain Execution Time

This paper proposes an algorithm called probabilistic rotation scheduling which takes advantage of loop pipelining to schedule tasks with uncertain times to a parallel processing system. These tasks normally occur when conditional instructions are employed and/or inputs of the tasks influence the computation time. We show that based on our loop scheduling algorithm the length of the resulting schedule can be guaranteed to be satisfied for a given probability. The experiments show that the resulting schedule length for a given probability of confidence can be significantly better than the schedules obtained by worst-case or average-case scenario. 1 Introduction In many practical applications such as interface systems, fuzzy systems, and artificial intelligence systems, etc., many tasks from these applications normally have uncertain computation time. Such tasks normally contain conditional instructions and/or operations that may take different computation time when calculating differe..