Program Parallelization using Synchronized Pipelining

Scandolo, Leonardo and Kunz, Cesar and Hermenegildo, Manuel V. (2010). Program Parallelization using Synchronized Pipelining. In: "19th International Symposium on Logic-based Program Synthesis and Transformation, LOPSTR 2009", 09/09/2009 - 11/09/2009, Coimbra, Portugal. ISBN 978-3-642-12591-1.

Description

Title: Program Parallelization using Synchronized Pipelining
Author/s:
  • Scandolo, Leonardo
  • Kunz, Cesar
  • Hermenegildo, Manuel V.
Item Type: Presentation at Congress or Conference (Article)
Event Title: 19th International Symposium on Logic-based Program Synthesis and Transformation, LOPSTR 2009
Event Dates: 09/09/2009 - 11/09/2009
Event Location: Coimbra, Portugal
Title of Book: Proceedings of 19th International Symposium on Logic-based Program Synthesis and Transformation, LOPSTR 2009
Date: 2010
ISBN: 978-3-642-12591-1
Volume: 6037
Subjects:
Faculty: Facultad de Informática (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (704kB) | Preview

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

More information

Item ID: 5737
DC Identifier: http://oa.upm.es/5737/
OAI Identifier: oai:oa.upm.es:5737
Official URL: http://www.springerlink.com/content/x6r3549151421144/
Deposited by: Memoria Investigacion
Deposited on: 19 Jan 2011 10:48
Last Modified: 20 Apr 2016 14:28
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM