›› 2013, Vol. 28 ›› Issue (4): 657-670.doi: 10.1007/s11390-013-1366-9

Special Issue: Computer Architecture and Systems

• Architecture and VLSI Design • Previous Articles     Next Articles

Optimizing Parallel Sn Sweeps on Unstructured Grids for Multi-Core Clusters

Jie Yan1,2 (闫洁), Student Member, IEEE, Guang-Ming Tan1 (谭光明), Member, CCF, ACM, IEEE and Ning-Hui Sun1 (孙凝晖), Fellow, CCF, Member, ACM, IEEE   

  1. 1. State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences Beijing 100190, China;
    2. University of Chinese Academy of Sciences, Beijing 100049, China
  • Received:2012-05-10 Revised:2013-02-07 Online:2013-07-05 Published:2013-07-05
  • Supported by:

    This work is supported by the National Natural Science Foundation of China under Grant Nos. 60925009, 61003062, 61033009, 61272134, and the National Basic 973 Program of China under Grant Nos. 2011CB302502 and 2012CB316502.

In particle transport simulations, radiation effects are often described by the discrete ordinates (Sn) form of Boltzmann equation. In each ordinate direction, the solution is computed by sweeping the radiation flux across the grid. Parallel Sn sweep on an unstructured grid can be explicitly modeled as topological traversal through an equivalent directed acyclic graph (DAG), which is a data-driven algorithm. Its traditional design using MPI model results in irregular communication of massive short messages which cannot be efficiently handled by MPI runtime. Meanwhile, in high-end HPC cluster systems, multicore has become the standard processor configuration of a single node. The traditional data-driven algorithm of Sn sweeps has not exploited potential advantages of multi-threading of multicore on shared memory. These advantages, however, as we shall demonstrate, could provide an elegant solution resolving problems in the previous MPI-only design. In this paper, we give a new design of data-driven parallel Sn sweeps using hybrid MPI and Pthread programming, namely Sweep-H, to exploit hierarchical parallelism of processes and threads. With special multi-threading techniques and vertex schedule policy, Sweep-H gets more efficient communication and better load balance. We further present an analytical performance model for Sweep-H to reveal why and when it is advantageous over former MPI counterpart. On a 64-node multicore cluster system with 12 cores per node, 768 cores in total, Sweep-H achieves nearly linear scalability for moderate problem sizes, and better absolute performance than the previous MPI algorithm on more than 16 nodes (by up to two times speedup on 64 nodes).

[1] Downar T, Siegel A, Unal C. Science based nuclear energysystems enabled by advanced modeling and simulation at theextreme scale. Report of Workshop on Nuclear Energy, May2009, http://science.energy.gov//media/ascr/pdf/program-documents/docs/Sc nework shop report.pdf.

[2] Baker R S, Alcouffe R E. Parallel 3-D Sn performance forMPI on cray-T3D. In Proc. Joint Int. Conf. Math. Meth-ods and Supercomputing for Nuclear Applicat., Oct. 1997,pp.377-393.

[3] Baker R S, Koch K R. An Sn algorithm for the massivelyparallel CM-200 computer. Nuclear Science and Engineer-ing, 1998, 28: 312-320.

[4] Valiant L G. A bridging model for parallel computation.Communications of the ACM, 1990, 33(8): 103-111.

[5] Plimpton S, Hendrickson B, Burns S et al. Parallel algo-rithms for radiation transport on unstructured grids. In Proc.ACM/IEEE Conf. Super Computing, Nov. 2000, ArticleNo.25.

[6] Plimpton S, Hendrickson B, Burns S et al. Parallel Sn sweepson unstructured grids: Algorithms for prioritization, grid par-titioning, and cycle detection. J. American Nuclear Scienceand Engineering, 2005, 150(3): 267-283.

[7] Mo Z Y, Zhang A Q, Cao X L. Towards a parallel frameworkof grid-based numerical algorithms on DAGs. In Proc. the20th IPDPS, Apr. 2006, p.310.

[8] Hewitt C, Bishop P, Steiger R. A universal modular actorformalism for artificial intelligence. In Proc. the 3rd IJCAI,Aug. 1973, pp.235-245.

[9] Schloegel K, Karypis G, Kumar V. Parallel static and dy-namic multi-constraint graph partitioning. Concurrency andComputation: Practice and Experience, 2002, 14(3): 219-240.

[10] Karypis G, Kumar V. Multi-level graph partitioning schemes.In Proc. ICPP, Aug. 1995, pp.113-122.

[11] Hendrickson B, Leland R. A multilevel algorithm for parti-tioning graph. In Proc. ACM/IEEE Conf. Super Computing,Dec. 1995, Article No.28.

[12] Zhang A Q. Research on scalable parallel data driven algo-rithms and applications [Ph.D. Thesis]. China Academy ofEngineering Physics, 2009.

[13] Pautz S D. An algorithm for parallel Sn sweeps on un-structured meshes. Nuclear Science and Engineering, 2002,140(2): 111-136.

[14] Nowak P, Nemanic M K. Radiation transport calculations onunstructured grids using a spatially decomposed and threadedalgorithm. In Proc. Int. Conf. Mathematics and Computa-tion, Reactor Physics and Environmental Analysis in NuclearApplications, Sept. 1999, pp.379-390.

[15] Gong C Y, Liu J, Chi L H, Huang H W, Fang J Y, GongZ H. GPU accelerated simulations of 3D deterministic par-ticle transport using discrete ordinates method. Journal ofComputational Physics, 2011, 230(15): 6010-6022.

[16] Lubeck O, Lang M, Srinivasan R, Johnson G. Implementationand performance modeling of deterministic particle transport(Sweep3D) on the IBM Cell/BE. Scientific Programming,2009, 17(1/2): 199-208.

[17] Pennycook S J, Hammond S D, Mudalige G R, Wright S A,Jarvis S A. On the acceleration of wavefront applications us-ing distributed many-core architectures. The Computer Jour-nal, 2012, 55(2): 138-153.
No related articles found!
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved