Scalable Parallel Prefix Solvers for Discrete Ordinates Transport in Multidimensions

The well-known “sweep” algorithm for inverting the streaming-plus-collision term in first-order deterministic radiation transport calculations suffers from parallel scaling issues caused by a lack of concurrency in the spatial dimension along the direction of particle travel. We investigate a new class of parallel algorithms that involves recasting the streaming-plus-collision problem in prefix form and solving via cyclic reduction. This method, although computationally more expensive at low levels of parallelism than the sweep algorithm, offers better theoretical scalability properties. Previous work has demonstrated this approach for one-dimensional calculations; we show how to extend it to multidimensional calculations. Notably, for multiple dimensions it appears that this approach is limited to long-characteristics discretizations; other discretizations cannot be cast in practical prefix form. Computational results on two different massively parallel computer systems demonstrate that both our “forward” and “symmetric” algorithms behave similarly, scaling well to larger degrees of parallelism than sweep-based solvers. We do observe some issues at the highest levels of parallelism (relative to the computer system size) and discuss possible causes. We conclude that this approach shows good potential for future parallel systems but that parallel scalability will depend on the architecture of the communication networks of these systems.