[Back]

G. Tzenakis, A. Papatriantafyllou, H. Vandierendonck, P. Pratikakis, D. Nikolopoulos:
"BDDT: Block-Level Dynamic Dependence Analysis for Task-Based Parallelism";
Talk: 10th International Symposium on Advanced Parallel Processing Technologies, APPT 2013, Stockholm, Sweden; 2013-08-27 - 2013-08-28; in: "Advanced Parallel Processing Technologies, 10th International Symposium, APPT 2013, Revised Selected Papers", C. Wu, A. Cohen (ed.); Springer, LNCS 8299 (2013), ISBN: 978-3-642-45292-5; 17 - 31.

We present BDDT, a task-parallel runtime system that dynamically
discovers and resolves dependencies among parallel tasks. BDDT allows the programmer to specify detailed task footprints on any memory address range, multidimensional array tile or dynamic region. BDDT uses a block-based dependence analysis with arbitrary granularity. The analysis is applicable to existing C programs without having to restructure object or array allocation, and provides flexibility
in array layouts and tile dimensions.
We evaluate BDDT using a representative set of benchmarks, and we compare it to SMPSs (the equivalent runtime system in StarSs) and OpenMP. BDDT performs comparable to or better than SMPSs and is able to cope with task granularity as much as one order of magnitude finer than SMPSs. Compared to OpenMP, BDDT performs up to 3.9× better for benchmarks that benefit from dynamic dependence analysis. BDDT provides additional data annotations to bypass dependence analysis. Using these annotations, BDDT outperforms OpenMP also in benchmarks where dependence analysis does not discover additional parallelism,
thanks to a more efficient implementation of the runtime system.

Compilers and runtime systems, Task-parallel libraries, Middleware for parallel systems, Synchronization and concurrency control.

http://dx.doi.org/10.1007/978-3-642-45293-2_2