Expressing Inter-task Dependencies between Parallel Stencil Operations

Abstract. Complex embedded systems are designed under tight con-straints on response time, resource usage and cost. Design space ex-ploration 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, automat-ically 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 op-erations – 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.