Probabilistic loop scheduling considering communication overhead

This paper presents a new methodology for statically scheduling a cyclic data-flow graph whose node computation times can be represented by random variables. A communication cost issue is also considered as another uncertain factor in which each node from the graph can produce different amount of data depending on the probability of its computation time. Since such communication costs rely on the amount of transfered data, this overhead becomes uncertain as well. We propose an algorithm to take advantage of the parallelism across a loop iteration while hiding the communication overhead. The resulting schedule will be evaluated in terms of confidence probability—the probability of having a schedule completed before a certain time. Experimental results show that the proposed framework performs better than a traditional algorithm running on an input which assumes fixed average timing information.