Expressing Inter-task Dependencies between Parallel Stencil Operations

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


    Complex embedded systems are designed under tight constraints on response time, resource usage and cost. Design space exploration tools help designers map and schedule embedded software to complex architectures such as heterogeneous MPSoC's. Task graphs are coarse grained representations of parallel program behaviour which are used to evaluate the feasibility of a particular design. However, automatically extracting an accurate task graph from source code is challenging. This paper investigates how to describe data dependencies to aid tools based on program analysis in extracting task graphs from source code. We will examine a common parallel programming pattern - stencil operations - and show that even for such codes with a regular control flow, the precise dependencies between two stencil operations cannot always be determined at compile time. We introduce a language construct which i) captures an upper bound on the number of dependencies between successive stencil operations and ii) instructs the compiler to generate code which ensures that the bound holds for each execution of the program. The impact of our proposal is evaluated using a micro-benchmark and two soft real-time embedded image processing applications. The coding effort is low - at most one line of code per parallel loop was added. The performance impact is evaluated on a quad-core Linux workstation and we observe no statistically significant slowdown.
    Original languageEnglish
    Title of host publicationProceedings of MULTIPROG 2010
    Publication statusAccepted/In press - 2010
    EventProgrammability Issues for Multi-Core Computers - Piza, Italy
    Duration: 1 Jan 2010 → …
    Conference number: 3


    ConferenceProgrammability Issues for Multi-Core Computers
    CityPiza, Italy
    Period01/01/2010 → …


    Dive into the research topics of 'Expressing Inter-task Dependencies between Parallel Stencil Operations'. Together they form a unique fingerprint.

    Cite this