Title :
Avoiding Serialization Effects in Data / Dependency Aware Task Parallel Algorithms for Spatial Decomposition
Author :
Niethammer, Christoph ; Glass, Colin W. ; Gracia, José
Author_Institution :
High Performance Comput. Center, Stuttgart Univ., Stuttgart, Germany
Abstract :
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.
Keywords :
parallel algorithms; parallel programming; trees (mathematics); StarSs; computational fluid dynamics codes; data aware task parallel algorithms; dependency aware task parallel algorithms; dependency tree; dependency-driven task parallel programming models; memory addresses; molecular dynamics; serialization effects; spatial decomposition; Cascading style sheets; Computational modeling; Memory management; Parallel processing; Parallel programming; Runtime; OmpSs; SMPSs; StarSs; computational fluid dynamics; molecular dynamics;
Conference_Titel :
Parallel and Distributed Processing with Applications (ISPA), 2012 IEEE 10th International Symposium on
Conference_Location :
Leganes
Print_ISBN :
978-1-4673-1631-6
DOI :
10.1109/ISPA.2012.109