Probabilistic Rotation Scheduling

One of the biggest problems in parallel processing is to obtain a good schedule without having a knowledge of exact computation time of the tasks. These tasks normally occur when conditional instructions are employed and/or inputs of the tasks influence the computation time. The relationship of these tasks can be represented by a data-flow graph where each node models the task associated with a probabilistic computation time. In order to address the problem, the synchronous parallelism computing style is assumed in this paper, i.e., the synchronization is enforced at the end of each iteration. An algorithm called probabilistic rotation scheduling which takes advantage of loop pipelining is developed to schedule these tasks to a parallel processing system. 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 con..