Home research People General Info Seminars Resources Intranet

W Hawkins, Timmie Smith, Michael Adams, Lawrence Rauchwerger, Nancy Amato, Marvin Adams, Teresa Bailey, Robert Falgout, "Provably Optimal Parallel Transport Sweeps on Regular Grids," In Proc. Int. Conf. on Math. Meth. and Supercomp. for Nuc. App., Idaho, May 2013.
Proceedings(pdf, abstract)

We have found a set of provably optimal algorithms for executing full-domain discrete-ordinate transport sweeps on regular grids in 3D Cartesian geometry. We describe these algorithms and sketch a “proof” that they will always execute the full eight-octant sweep in the minimum possible number of stages for a given P x × P y × P z partitioning. A stage includes each processor choosing a task to execute, if at least one is available, and communicating its result to downstream neighbors. A task is an aggregation of cells, directions, and energy groups. Our computational results demonstrate that our optimal scheduling algorithms do execute sweeps in the minimum possible stage count, and further they agree reasonably well with our performance model. An older version of our PDT transport code achieves almost 80% parallel efficiency on 131,072 cores, on a weak-scaling problem with only one energy group, 80 directions, and 4096 cells/core. A newer version is less efficient at present—we are still improving its implementation—but still achieves almost 60% parallel efficiency on 393,216 cores. These results conclusively demonstrate that sweeps can perform with high efficiency on core counts approaching one million.