Asynchronous nested parallelism for dynamic applications in distributed memory

Ioannis Papadopoulos, Nathan Thomas, Adam Fidel, Dielli Hoxha, Nancy Marie Amato, Lawrence Rauchwerger

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

Abstract

Nested parallelism is of increasing interest for both expressivity and performance. Many problems are naturally expressed with this divide-and-conquer software design approach. In addition, programmers with target architecture knowledge employ nested parallelism for performance, imposing a hierarchy in the application to increase locality and resource utilization, often at the cost of implementation complexity. While dynamic applications are a natural fit for the approach, support for nested parallelism in distributed systems is generally limited to well-structured applications engineered with distinct phases of intranode computation and inter-node communication. This model makes expressing irregular applications difficult and also hurts performance by introducing unnecessary latency and synchronizations. In this paper we describe an approach to asynchronous nested parallelism which provides uniform treatment of nested computation across distributed memory. This approach allows efficient execution while supporting dynamic applications which cannot be mapped onto the machine in the rigid manner of regular applications. We use several graph algorithms as examples to demonstrate our library’s expressivity, flexibility, and performance.

Original languageEnglish (US)
Title of host publicationLanguages and Compilers for Parallel Computing - 28th International Workshop, LCPC 2015, Revised Selected Papers
EditorsXipeng Shen, Frank Mueller, James Tuck
PublisherSpringer-Verlag
Pages106-121
Number of pages16
ISBN (Print)9783319297774
DOIs
StatePublished - Jan 1 2016
Externally publishedYes
Event28th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2015 - Raleigh, United States
Duration: Sep 9 2015Sep 11 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9519
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference28th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2015
CountryUnited States
CityRaleigh
Period9/9/159/11/15

Fingerprint

Distributed Memory
Parallelism
Data storage equipment
Graph Algorithms
Divide and conquer
Software Design
Software design
Locality
Latency
Distributed Systems
Irregular
Synchronization
Flexibility
Distinct
Resources
Target
Communication
Vertex of a graph
Demonstrate

Keywords

  • Asynchronous
  • Dynamic applications
  • Graph
  • Isolation
  • Nested parallelism

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Papadopoulos, I., Thomas, N., Fidel, A., Hoxha, D., Amato, N. M., & Rauchwerger, L. (2016). Asynchronous nested parallelism for dynamic applications in distributed memory. In X. Shen, F. Mueller, & J. Tuck (Eds.), Languages and Compilers for Parallel Computing - 28th International Workshop, LCPC 2015, Revised Selected Papers (pp. 106-121). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9519). Springer-Verlag. https://doi.org/10.1007/978-3-319-29778-1_7

Asynchronous nested parallelism for dynamic applications in distributed memory. / Papadopoulos, Ioannis; Thomas, Nathan; Fidel, Adam; Hoxha, Dielli; Amato, Nancy Marie; Rauchwerger, Lawrence.

Languages and Compilers for Parallel Computing - 28th International Workshop, LCPC 2015, Revised Selected Papers. ed. / Xipeng Shen; Frank Mueller; James Tuck. Springer-Verlag, 2016. p. 106-121 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9519).

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

Papadopoulos, I, Thomas, N, Fidel, A, Hoxha, D, Amato, NM & Rauchwerger, L 2016, Asynchronous nested parallelism for dynamic applications in distributed memory. in X Shen, F Mueller & J Tuck (eds), Languages and Compilers for Parallel Computing - 28th International Workshop, LCPC 2015, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9519, Springer-Verlag, pp. 106-121, 28th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2015, Raleigh, United States, 9/9/15. https://doi.org/10.1007/978-3-319-29778-1_7
Papadopoulos I, Thomas N, Fidel A, Hoxha D, Amato NM, Rauchwerger L. Asynchronous nested parallelism for dynamic applications in distributed memory. In Shen X, Mueller F, Tuck J, editors, Languages and Compilers for Parallel Computing - 28th International Workshop, LCPC 2015, Revised Selected Papers. Springer-Verlag. 2016. p. 106-121. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-29778-1_7
Papadopoulos, Ioannis ; Thomas, Nathan ; Fidel, Adam ; Hoxha, Dielli ; Amato, Nancy Marie ; Rauchwerger, Lawrence. / Asynchronous nested parallelism for dynamic applications in distributed memory. Languages and Compilers for Parallel Computing - 28th International Workshop, LCPC 2015, Revised Selected Papers. editor / Xipeng Shen ; Frank Mueller ; James Tuck. Springer-Verlag, 2016. pp. 106-121 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{0719321cc37c447cbe66068d55e0d281,
title = "Asynchronous nested parallelism for dynamic applications in distributed memory",
abstract = "Nested parallelism is of increasing interest for both expressivity and performance. Many problems are naturally expressed with this divide-and-conquer software design approach. In addition, programmers with target architecture knowledge employ nested parallelism for performance, imposing a hierarchy in the application to increase locality and resource utilization, often at the cost of implementation complexity. While dynamic applications are a natural fit for the approach, support for nested parallelism in distributed systems is generally limited to well-structured applications engineered with distinct phases of intranode computation and inter-node communication. This model makes expressing irregular applications difficult and also hurts performance by introducing unnecessary latency and synchronizations. In this paper we describe an approach to asynchronous nested parallelism which provides uniform treatment of nested computation across distributed memory. This approach allows efficient execution while supporting dynamic applications which cannot be mapped onto the machine in the rigid manner of regular applications. We use several graph algorithms as examples to demonstrate our library’s expressivity, flexibility, and performance.",
keywords = "Asynchronous, Dynamic applications, Graph, Isolation, Nested parallelism",
author = "Ioannis Papadopoulos and Nathan Thomas and Adam Fidel and Dielli Hoxha and Amato, {Nancy Marie} and Lawrence Rauchwerger",
year = "2016",
month = "1",
day = "1",
doi = "10.1007/978-3-319-29778-1_7",
language = "English (US)",
isbn = "9783319297774",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag",
pages = "106--121",
editor = "Xipeng Shen and Frank Mueller and James Tuck",
booktitle = "Languages and Compilers for Parallel Computing - 28th International Workshop, LCPC 2015, Revised Selected Papers",

}

TY - GEN

T1 - Asynchronous nested parallelism for dynamic applications in distributed memory

AU - Papadopoulos, Ioannis

AU - Thomas, Nathan

AU - Fidel, Adam

AU - Hoxha, Dielli

AU - Amato, Nancy Marie

AU - Rauchwerger, Lawrence

PY - 2016/1/1

Y1 - 2016/1/1

N2 - Nested parallelism is of increasing interest for both expressivity and performance. Many problems are naturally expressed with this divide-and-conquer software design approach. In addition, programmers with target architecture knowledge employ nested parallelism for performance, imposing a hierarchy in the application to increase locality and resource utilization, often at the cost of implementation complexity. While dynamic applications are a natural fit for the approach, support for nested parallelism in distributed systems is generally limited to well-structured applications engineered with distinct phases of intranode computation and inter-node communication. This model makes expressing irregular applications difficult and also hurts performance by introducing unnecessary latency and synchronizations. In this paper we describe an approach to asynchronous nested parallelism which provides uniform treatment of nested computation across distributed memory. This approach allows efficient execution while supporting dynamic applications which cannot be mapped onto the machine in the rigid manner of regular applications. We use several graph algorithms as examples to demonstrate our library’s expressivity, flexibility, and performance.

AB - Nested parallelism is of increasing interest for both expressivity and performance. Many problems are naturally expressed with this divide-and-conquer software design approach. In addition, programmers with target architecture knowledge employ nested parallelism for performance, imposing a hierarchy in the application to increase locality and resource utilization, often at the cost of implementation complexity. While dynamic applications are a natural fit for the approach, support for nested parallelism in distributed systems is generally limited to well-structured applications engineered with distinct phases of intranode computation and inter-node communication. This model makes expressing irregular applications difficult and also hurts performance by introducing unnecessary latency and synchronizations. In this paper we describe an approach to asynchronous nested parallelism which provides uniform treatment of nested computation across distributed memory. This approach allows efficient execution while supporting dynamic applications which cannot be mapped onto the machine in the rigid manner of regular applications. We use several graph algorithms as examples to demonstrate our library’s expressivity, flexibility, and performance.

KW - Asynchronous

KW - Dynamic applications

KW - Graph

KW - Isolation

KW - Nested parallelism

UR - http://www.scopus.com/inward/record.url?scp=84961189464&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84961189464&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-29778-1_7

DO - 10.1007/978-3-319-29778-1_7

M3 - Conference contribution

AN - SCOPUS:84961189464

SN - 9783319297774

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 106

EP - 121

BT - Languages and Compilers for Parallel Computing - 28th International Workshop, LCPC 2015, Revised Selected Papers

A2 - Shen, Xipeng

A2 - Mueller, Frank

A2 - Tuck, James

PB - Springer-Verlag

ER -