IMDEA Software

IMDEA initiative

Home > Events > Software Seminar Series > 2009 > Program Parallelization using Synchronized Pipelining

Tuesday, March 3, 2009

11:00am Meeting room 302 (Mountain View), level 3

Leo Scandolo, Research Intern, IMDEA Software Institute

Program Parallelization using Synchronized Pipelining

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 work 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 loop 1, 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.