Automatic Extraction of Coarse-Grained Data-Flow Threads from Imperative Programs

Author

Li, Feng ; Pop, Antoniu ; Cohen, Albert

Volume

32

Issue

4

fYear

2012

Firstpage

19

Lastpage

31

Abstract

This article presents a general algorithm for transforming sequential imperative programs into parallel data-flow programs. The algorithm operates on a program dependence graph in static-single-assignment form, extracting task, pipeline, and data parallelism from arbitrary control flow, and coarsening its granularity using a generalized form of typed fusion. A prototype based on GNU Compiler Collection (GCC) is applied to the automatic parallelization of recursive C programs.

Keywords

data flow computing; data flow graphs; parallel programming; program compilers; program interpreters; GNU compiler collection; arbitrary control flow; automatic coarse-grained data-flow thread extraction; automatic recursive C program parallelization; data parallelism; imperative programs; parallel data-flow programs; program dependence graph; sequential imperative program transformation; task extraction; Instruction sets; Parallel processing; Pipeline processing; Radiation detectors; Sequential analysis; Synchronization; Instruction sets; Parallel processing; Pipeline processing; Radiation detectors; SSA form; Sequential analysis; Synchronization; automatic parallelization; data-flow model; loop fusion; program dependence graph; sequential imperative programs;

fLanguage

English

Journal_Title

Micro, IEEE

Publisher

ieee

ISSN

0272-1732

Type

jour

DOI

10.1109/MM.2012.49

Filename

6216345