Authors: Ioannis Papadopoulos, Nathan Thomas, Adam Fidel, Dielli Hoxha, Nancy M. Amato, Lawrence Rauchwerger

Venue: In Wkshp. on Lang. and Comp. for Par. Comp. (LCPC)
DOI: 10.1007/978-3-319-29778-1_7
Link to Publication

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 intra-node 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. 

@inproceedings{Papadopoulos-anpfda-2016, 
 address = {Cham}, 
 author = {Papadopoulos, Ioannis 
and Thomas, Nathan 
and Fidel, Adam 
and Hoxha, Dielli 
and Amato, Nancy M. 
and Rauchwerger, Lawrence}, 
 booktitle = {Languages and Compilers for Parallel Computing}, 
 editor = {Shen, Xipeng 
and Mueller, Frank 
and Tuck, James}, 
 isbn = {978-3-319-29778-1}, 
 pages = {106--121}, 
 publisher = {Springer International Publishing}, 
 title = {Asynchronous Nested Parallelism for Dynamic Applications in Distributed Memory}, 
 year = {2016} 
}