Provably optimal parallel transport sweeps with non-contiguous partitions
Conference Paper
Overview
Identity
Additional Document Info
View All
Overview
abstract
We have found provably optimal algorithms for full-domain discrete-ordinate transport sweeps in 2D and 3D Cartesian geometry for partitionings that assign non-contiguous spatial subdomains to each processor. We describe these algorithms and show theoretically that they always execute the full eight-octant sweep in the minimum possible number of stages provided that the partitioning satisfies conditions that we derive. Computational results from a sweep-emulation code agree with our theoretical results, showing that our optimal scheduling algorithm does execute sweeps in the minimum possible stage count whenever the partitioning meets the defined conditions. Previous work has shown that sweeps can be executed with high parallel efficiency on core counts approaching 106 given a different class of partitionings with contiguous subdomains assigned to each processor. Our results here show that discontiguous subdomains, an example of a "domain overloading" technique, can allow even higher efficiencies at higher processor counts, because in many cases they allow sweeps to complete in fewer stages than is possible with contiguous processor domains.
