Authors: William McLendon, Bruce Hendrickson, Steve Plimpton, Lawrence Rauchwerger

Venue: Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures
DOI: 10.1145/378580.378751
Link to Publication

Abstract:
Discrete ordinates methods are commonly used to simulate radiation transport for fire or weapons modeling. The computation proceeds by sweeping the flux across a grid. A particular cell cannot be computed until all the cells immediately upwind of it are finished. If the directed dependence graph for the grid cells contains a cycle then sweeping methods will deadlock. This can happen in unstructured grids and time stepped problems where the grid is allowed to deform. In this paper we present a parallel algorithm to detect cycles in the dependence graphs present in these grids as well as an implementation and experimental results on shared and distributed memory machines. 

@inproceedings{McLendon-fsccip-2001, 
 address = {New York, NY, USA}, 
 author = {Mclendon, William and Hendrickson, Bruce and Plimpton, Steve and Rauchwerger, Lawrence}, 
 booktitle = {Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures}, 
 doi = {10.1145/378580.378751}, 
 isbn = {1581134096}, 
 location = {Crete Island, Greece}, 
 numpages = {2}, 
 pages = {328–329}, 
 publisher = {Association for Computing Machinery}, 
 series = {SPAA '01}, 
 title = {Finding Strongly Connected Components in Parallel in Particle Transport Sweeps}, 
 url = {https://doi.org/10.1145/378580.378751}, 
 year = {2001} 
}