BDDT: Block-level Dynamic Dependence Analysis for Task-Based Parallelism

Georgios Tzenakis, Angelos Papatriantafyllou, Hans Vandierendonck, Polyvios Pratikakis, Dimitrios S. Nikolopoulos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Citations (Scopus)
276 Downloads (Pure)


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.
Original languageEnglish
Title of host publicationAdvanced Parallel Processing Technologies
Subtitle of host publication10th International Symposium, APPT 2013, Stockholm, Sweden, August 27-28, 2013, Revised Selected Papers
EditorsChenggang Wu, Albert Cohen
Number of pages15
ISBN (Electronic)978-3-642-45293-2
ISBN (Print)978-3-642-45292-5
Publication statusPublished - Sept 2013

Publication series

NameLecture Notes in Computer Science

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science


Dive into the research topics of 'BDDT: Block-level Dynamic Dependence Analysis for Task-Based Parallelism'. Together they form a unique fingerprint.

    Nikolopoulos, D.


    Project: Research

Cite this