Space-time transformation of while-loops using speculative execution

Automatic parallelization techniques of sequential programs have focused on nests of for-loops. This work describes a method to extend some of these techniques to while-loops enclosing a nest of for-loops. This kind of nest is common in numerical applications, where a while-loop iterates a convergent computation on a discrete space scanned by the for-loop nest. The method relies on speculative execution expressed as an affine scheduling function, as in recent automatic parallelization techniques of for-loops. We show how this scheduling function can be found automatically. We also address the problem of mapping the operations onto the processors.<
>