A general performance model for parallel sweeps on orthogonal grids for particle transport calculations

ABSTRACT

The key contribution of this paper is the first general model which can be used to predict the running time of transport sweeps on orthogonal grids for any regular mapping of the grid cells to processors. Our model, which accounts for machine dependent parameters such as computation cost and communication latency, can be used to analyze and compare the effects of various spatial decompositions on the running time of the transport sweep. Insight obtained from the model yields two significant contributions to the theory of optimal transport sweeps on orthogonal grids. First, our model provides a theoretical basis which explains why, and under what circumstances, the column decomposition of the current standard KBA algorithm is superior to the 'balanced' decomposition obtained by classic domain decomposition techniques. Second, our model enables us to identify a new decomposition, we call Hybrid, which proves to be almost as good as, and sometimes superior to, the current standard KBA method. Our analysis covers sweeps in two- and three-dimensional spatial domains, and first considers sweeps in only one direction, and then sweeps involving multiple simultaneous directions. We obtain expressions for the completion time and discuss theoretical results.

REFERENCES

• 1: Randal S. Baker and Raymond E. Alcouffe. Parallel 3D SN Performance for DANTSYS/MPI on the Cray T3D. In Proc. Int. Conf. on Mathematical Methods and Bupercomputin 9 for Nuclear Applications, volume 1, pages 377-393, October 19977.
• 2: A. Hoisie, O. Lubeck, and H. Wasserman. Performance and scalability analysis of teraflop-scale parallel architectures using multidimensional wavefront applications. Technical Report LAUR-98-3316, Los Alamos National Laboratories, August 1998.
• 3: Adolfy Hoisie , Olaf Lubeck , Harvey Wasserman, Scalability Analysis of Multidimensional Wavefront Algorithms on Large-Scale SMP Clusters, Proceedings of the The 7th Symposium on the Frontiers of Massively Parallel Computation, p.4, February 21-25, 1999
• 4: George Karypis and Vipin Kumar. METIS, unstructured graph partitioning and sparse matrix ordering system, version 2.0. Technical report, University of Minnesota, Department of Computer Science, Minneapolis, MN 55455, August 1995.
• 5: K. R. Koch, R. S. Baker, and R. E. Alcouffe. Solution of the first-order form of the 3D discrete ordinates equation on a massively parallel processor. Transactions of the American Nuclear Society, 65:198-199, 1992. 1992 Annual Meeting, Boston, MA.
• 6: E. E. Lewis and W. F. Miller. Computational methods of neutron transport. In American Nuclear Society Inc., LaGrange Park, IL, 1993.
• 7: Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Modeling and recovery of physical attributes
  I.6 SIMULATION AND MODELING

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Physics

General Terms:
Design, Measurement, Performance, Theory