Optimal asynchronous scheduling algorithm for software cache consistency

Abstract

We present a linear time algorithm for scheduling iterations of a loop that has no loop-carried dependences. The algorithm is optimal in the sense that any p consecutive iterations in the schedule can be executed simultaneously without any possibility of false sharing, where p is the number of processors, and the algorithm uses at most two wait synchronizations per iteration. Our algorithm is asynchronous in the sense that it allows the loop iterations to be scheduled greedily so that no processor will ever be kept idle if it could be safely executing an iteration. This property makes our algorithm superior to a `barrier' type algorithm, in which barrier synchronizations are used instead of pairwise signal-wait synchronizations.