A profile-based tool for finding pipeline parallelism in sequential programs

Sean Rul, Hans Vandierendonck, Keon De Bosschere

Research output: Contribution to journalArticlepeer-review

37 Citations (Scopus)

Abstract

Traditional static analysis fails to auto-parallelize programs with a complex control and data flow. Furthermore, thread-level parallelism in such programs is often restricted to pipeline parallelism, which can be hard to discover by a programmer. In this paper we propose a tool that, based on profiling information, helps the programmer to discover parallelism. The programmer hand-picks the code transformations from among the proposed candidates which are then applied by automatic code transformation techniques.

This paper contributes to the literature by presenting a profiling tool for discovering thread-level parallelism. We track dependencies at the whole-data structure level rather than at the element level or byte level in order to limit the profiling overhead. We perform a thorough analysis of the needs and costs of this technique. Furthermore, we present and validate the belief that programs with complex control and data flow contain significant amounts of exploitable coarse-grain pipeline parallelism in the program’s outer loops. This observation validates our approach to whole-data structure dependencies. As state-of-the-art compilers focus on loops iterating over data structure members, this observation also explains why our approach finds coarse-grain pipeline parallelism in cases that have remained out of reach for state-of-the-art compilers. In cases where traditional compilation techniques do find parallelism, our approach allows to discover higher degrees of parallelism, allowing a 40% speedup over traditional compilation techniques. Moreover, we demonstrate real speedups on multiple hardware platforms.

Original languageEnglish
Pages (from-to)531-551
Number of pages21
JournalParallel Computing
Volume36
Issue number9
Early online date08 Jun 2010
DOIs
Publication statusPublished - Sept 2010

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Software
  • Hardware and Architecture
  • Artificial Intelligence
  • Computer Graphics and Computer-Aided Design
  • Theoretical Computer Science

Fingerprint

Dive into the research topics of 'A profile-based tool for finding pipeline parallelism in sequential programs'. Together they form a unique fingerprint.

Cite this