2021-02-28T15:52:44Z
http://oa.upm.es/cgi/oai2
oai:oa.upm.es:5737
2016-04-20T14:28:11Z
7374617475733D707562
7375626A656374733D696E666F726D6174696361
747970653D636F6E666572656E63655F6974656D
Program Parallelization using Synchronized Pipelining
Scandolo, Leonardo
Kunz, Cesar
Hermenegildo, Manuel V.
Computer Science
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
Facultad de Informática (UPM)
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
2010
info:eu-repo/semantics/conferenceObject
Presentation at Congress or Conference
Proceedings of 19th International Symposium on Logic-based Program Synthesis and Transformation, LOPSTR 2009 | 19th International Symposium on Logic-based Program Synthesis and Transformation, LOPSTR 2009 | 09/09/2009 - 11/09/2009 | Coimbra, Portugal
PeerReviewed
application/pdf
eng
http://www.springerlink.com/content/x6r3549151421144/
info:eu-repo/semantics/openAccess
http://oa.upm.es/5737/