Title :
Automatic Extraction of Coarse-Grained Data-Flow Threads from Imperative Programs
Author :
Li, Feng ; Pop, Antoniu ; Cohen, Albert
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;
Journal_Title :
Micro, IEEE
