William Mclendon
Bruce Hendrickson
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.
- 1.T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. M.I.T. Press, Cambridge, MA, 1990. Google Scholar
Digital Library
- 2.L. K. Fleischer, B. Hendrickson, and A. Panar. On identifying strongly connected components in parallel. In Solving Irregularly Structured Problems in Parallel: 7th Intl. Symp., Irreg. '00, Vol 1800 of Lecture Notes in Comp. Sci., pp. 505-512. Springer-Verlag, 2000. Google ScholarDigital Library
- 3.William C. McLendon III, B. Hendrickson, S. Plimpton, and L. Rauchwerger. Finding strongly connected components in parallel in particle transport sweeps. Technical Report TR01-005, Texas A&M University, 2001. Google ScholarDigital Library
- 4.William C. McLendon III, B. A. Hendrickson, S. J. Plimpton, and L. Rauchwerger. Identifying strongly connected components in parallel. Proc. of 10th SIAM Conference on Parallel Processing for Sci. Computing, March 2001.Google Scholar
- 5.Karp and Ramachandran. Parallel algorithms for shared-memory machines. In Handbook of Theoretical Computer Science, Algorithms and Complexity, Vol 1. Jan van Leeuwen, Elsevier and MIT Press, 1990. Google ScholarDigital Library
- 6.J. H. Reif. Depth-first search is inherently sequential. Information Processing Letters, 20(5):229-234, 1985.Google ScholarCross Ref
- 7.R. Tarjan. Depth-first search and linear graph algorithms. SIAM J. Computation, 1:146-160, 1972.Google ScholarCross Ref
Index Terms
- Finding strongly connected components in parallel in particle transport sweeps
Recommendations
Richardson's Theorem for k -colored kernels in strongly connected digraphs
A digraph D = ( V , A ) is said to be m -colored if its arcs are colored with m colors. An m -colored digraph D has a k -colored kernel if there exists K V such that (i) for every v V K there exist a q -colored directed path, with q k , from v to a ...
Comments