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

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

doi:10.1007/978-3-642-45293-2_2

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 proceeding › Conference contribution

9 Citations (Scopus)

302 Downloads (Pure)

Abstract

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 language	English
Title of host publication	Advanced Parallel Processing Technologies
Subtitle of host publication	10th International Symposium, APPT 2013, Stockholm, Sweden, August 27-28, 2013, Revised Selected Papers
Editors	Chenggang Wu, Albert Cohen
Publisher	Springer
Pages	17-31
Number of pages	15
Volume	8299
ISBN (Electronic)	978-3-642-45293-2
ISBN (Print)	978-3-642-45292-5
DOIs	https://doi.org/10.1007/978-3-642-45293-2_2
Publication status	Published - Sept 2013

Publication series

Name	Lecture Notes in Computer Science

ASJC Scopus subject areas

General Computer Science
Theoretical Computer Science

Access to Document

10.1007/978-3-642-45293-2_2

BDDT: Block-level Dynamic Dependence Analysis for Task-Based Parallelism
© 2013 Springer International Publishing AG The final publication is available at Springer via http://link.springer.com/chapter/10.1007%2F978-3-642-45293-2_2
Accepted author manuscript, 396 KB

R1131CSC: ERA-Net CHIST-ERA
Nikolopoulos, D. (PI)
01/08/2012 → 09/01/2016
Project: Research

Invited Talk and membership in panel at the "European Initiative on Runtime Systems and Architecture Co-Design"
Vandierendonck, H. (Speaker)
07 May 2015
Activity: Talk or presentation types › Invited talk

Cite this

Tzenakis, G., Papatriantafyllou, A., Vandierendonck, H., Pratikakis, P., & Nikolopoulos, D. S. (2013). BDDT: Block-level Dynamic Dependence Analysis for Task-Based Parallelism. In C. Wu, & A. Cohen (Eds.), Advanced Parallel Processing Technologies: 10th International Symposium, APPT 2013, Stockholm, Sweden, August 27-28, 2013, Revised Selected Papers (Vol. 8299, pp. 17-31). (Lecture Notes in Computer Science). Springer. https://doi.org/10.1007/978-3-642-45293-2_2

Tzenakis, Georgios ; Papatriantafyllou, Angelos ; Vandierendonck, Hans et al. / BDDT: Block-level Dynamic Dependence Analysis for Task-Based Parallelism. Advanced Parallel Processing Technologies: 10th International Symposium, APPT 2013, Stockholm, Sweden, August 27-28, 2013, Revised Selected Papers. editor / Chenggang Wu ; Albert Cohen. Vol. 8299 Springer, 2013. pp. 17-31 (Lecture Notes in Computer Science).

@inproceedings{1f36ecdf062a48ffa50c26773d4c7f02,

title = "BDDT: Block-level Dynamic Dependence Analysis for Task-Based Parallelism",

abstract = "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.",

author = "Georgios Tzenakis and Angelos Papatriantafyllou and Hans Vandierendonck and Polyvios Pratikakis and Nikolopoulos, {Dimitrios S.}",

year = "2013",

month = sep,

doi = "10.1007/978-3-642-45293-2_2",

language = "English",

isbn = "978-3-642-45292-5",

volume = "8299",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "17--31",

editor = "Chenggang Wu and Albert Cohen",

booktitle = "Advanced Parallel Processing Technologies",

}

Tzenakis, G, Papatriantafyllou, A, Vandierendonck, H, Pratikakis, P & Nikolopoulos, DS 2013, BDDT: Block-level Dynamic Dependence Analysis for Task-Based Parallelism. in C Wu & A Cohen (eds), Advanced Parallel Processing Technologies: 10th International Symposium, APPT 2013, Stockholm, Sweden, August 27-28, 2013, Revised Selected Papers. vol. 8299, Lecture Notes in Computer Science, Springer, pp. 17-31. https://doi.org/10.1007/978-3-642-45293-2_2

BDDT: Block-level Dynamic Dependence Analysis for Task-Based Parallelism. / Tzenakis, Georgios; Papatriantafyllou, Angelos; Vandierendonck, Hans et al.
Advanced Parallel Processing Technologies: 10th International Symposium, APPT 2013, Stockholm, Sweden, August 27-28, 2013, Revised Selected Papers. ed. / Chenggang Wu; Albert Cohen. Vol. 8299 Springer, 2013. p. 17-31 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Tzenakis, Georgios

AU - Papatriantafyllou, Angelos

AU - Vandierendonck, Hans

AU - Pratikakis, Polyvios

AU - Nikolopoulos, Dimitrios S.

PY - 2013/9

Y1 - 2013/9

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-45293-2_2

DO - 10.1007/978-3-642-45293-2_2

M3 - Conference contribution

SN - 978-3-642-45292-5

VL - 8299

T3 - Lecture Notes in Computer Science

SP - 17

EP - 31

BT - Advanced Parallel Processing Technologies

A2 - Wu, Chenggang

A2 - Cohen, Albert

PB - Springer

ER -

Tzenakis G, Papatriantafyllou A, Vandierendonck H, Pratikakis P, Nikolopoulos DS. BDDT: Block-level Dynamic Dependence Analysis for Task-Based Parallelism. In Wu C, Cohen A, editors, Advanced Parallel Processing Technologies: 10th International Symposium, APPT 2013, Stockholm, Sweden, August 27-28, 2013, Revised Selected Papers. Vol. 8299. Springer. 2013. p. 17-31. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-45293-2_2

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

Abstract

Publication series

ASJC Scopus subject areas

Access to Document

Fingerprint

Projects

R1131CSC: ERA-Net CHIST-ERA

Activities

Invited Talk and membership in panel at the "European Initiative on Runtime Systems and Architecture Co-Design"

Cite this