Parallel S_n Sweep Scheduling Algorithm on Unstructured Grids for Multigroup Time-Dependent Particle Transport Equations

Sweep scheduling methods used in particle transport problems belong to the class of precedence-constrained scheduling problems that are NP-complete. It is difficult to schedule local tasks for this type of transport problem and simultaneously optimize computational performance and parallel processor communication. In this paper, we present a parallel spatial-domain-decomposition algorithm to divide the tasks among the available processors. We also present a new algorithm for scheduling tasks within each processor. The scheduling algorithm has the required data and does not need to communicate with any other processor. This algorithm optimizes and assigns task priorities within the processor. Computational tasks whose results are required by another processor receive the highest priority. We combined these two algorithms to solve two-dimensional particle transport equations on unstructured grids. Our results show good performance and scalability up to 16 384 processors on the TianHe-2 supercomputer.