@inproceedings{upm5737,
booktitle = {Proceedings of 19th International Symposium on Logic-based Program Synthesis and Transformation, LOPSTR 2009},
volume = {6037},
title = {Program Parallelization using Synchronized Pipelining},
author = {Leonardo Scandolo and Cesar Kunz and Manuel V. Hermenegildo},
address = {Berlin, Alemania},
publisher = {Springer Verlag},
year = {2010},
url = {http://oa.upm.es/5737/},
abstract = {While there are well-understood methods for detecting loops whose iterations are independent and parallelizing them, there are comparatively fewer proposals that support parallel execution of a sequence of loops or nested loops in the case where such loops have dependencies among them. This paper introduces a refined notion of independence, called eventual independence, that in its simplest form considers two loops, say loop1 and loop2, and captures the idea that for every i there exists k such that the iā+ā1-th iteration of loop2 is independent from the j-th iteration of loop1, for all jā?āk. Eventual independence provides the foundation of a semantics-preserving program transformation, called synchronized pipelining, that makes execution of consecutive or nested loops parallel, relying on a minimal number of synchronization events to ensure semantics preservation. The practical benefits of synchronized pipelining are demonstrated through experimental results on common algorithms such as sorting and Fourier transforms}
}