Workshop: The 9th Annual Parallel Applications Workshop, Alternatives to MPI+X (PAW-ATM)
Authors: Rohan Chanani and Alex Aiken (Stanford University), Michael Bauer (NVIDIA), and Rohan Yadav (Stanford University)
Abstract: Dependent partitioning is a flexible framework for compactly describing and efficiently computing partitions of distributed data structures that contain indirections and interconnected references. These data structures are commonly found in scientific applications, which operate over meshes, graphs, and sparse tensors. However, existing implementations of dependent partitioning process the individual elements of their input data sequentially on CPUs. This limitation makes dependent partitioning an expensive component of application initialization, and hinders its use in dynamic or on-line contexts. In this work, we present parallel algorithms for computing dependent partitions, and show that these algorithms perform well on accelerators like GPUs. Across a series of microbenchmarks and existing applications that use dependent partitioning, we show that our work achieves speedups of 9.4–9,807× for computing dependent partitions. We then show that our algorithms enable dynamic and on-line partitioning during steady-state execution.
Back to The 9th Annual Parallel Applications Workshop, Alternatives to MPI+X (PAW-ATM) Archive Listing
Back to Full Workshop Archive Listing