  Spatial decomposition is a popular basis for parallelising code. Cast in the
frame of task parallelism, calculations on a spatial domain can be treated as a
task. If neighbouring domains interact and share results, access to the
specific data needs to be synchronized to avoid race conditions. This is the
case for a variety of applications, like most molecular dynamics and many
computational fluid dynamics codes. Here we present an unexpected problem which
can occur in dependency-driven task parallelization models like StarSs: the
tasks accessing a specific spatial domain are treated as interdependent, as
dependencies are detected automatically via memory addresses. Thus, the order
in which tasks are generated will have a severe impact on the dependency tree.
In the worst case, a complete serialization is reached and no two tasks can be
calculated in parallel. We present the problem in detail based on an example
from molecular dynamics, and introduce a theoretical framework to calculate the
degree of serialization. Furthermore, we present strategies to avoid this
unnecessary problem. We recommend treating these strategies as best practice
when using dependency-driven task parallel programming models like StarSs on
such scenarios.
