We use cookies to improve your experience with our site.
闫洁, 谭光明, 孙凝晖. 非规则网格上的Sn Sweep并行算法[J]. 计算机科学技术学报, 2013, 28(4): 657-670. DOI: 10.1007/s11390-013-1366-9
引用本文: 闫洁, 谭光明, 孙凝晖. 非规则网格上的Sn Sweep并行算法[J]. 计算机科学技术学报, 2013, 28(4): 657-670. DOI: 10.1007/s11390-013-1366-9
Jie Yan, Guang-Ming Tan, Ning-Hui Sun. Optimizing Parallel Sn Sweeps on Unstructured Grids for Multi-Core Clusters[J]. Journal of Computer Science and Technology, 2013, 28(4): 657-670. DOI: 10.1007/s11390-013-1366-9
Citation: Jie Yan, Guang-Ming Tan, Ning-Hui Sun. Optimizing Parallel Sn Sweeps on Unstructured Grids for Multi-Core Clusters[J]. Journal of Computer Science and Technology, 2013, 28(4): 657-670. DOI: 10.1007/s11390-013-1366-9

非规则网格上的Sn Sweep并行算法

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

  • 摘要: 非规则网格上的离散纵标扫描(Sn Sweep),通常采用数据驱动的并行算法.其中,网格单元计算之间的数据依赖可以用等价的有向无环图(DAG)来表达,进而一次Sweep过程相当于对DAG进行一次拓扑遍历.在传统的基于MPI的设计中,这种算法会导致大量的无规则的即时小休息通信,而这种通信模式是MPI本身无法高效支持的.与此同时,多核处理器已经成为目前高端计算机系统的单节点主流配置,但其节点内多线程共享内存的优势却并没有被之前的数据驱动Sweep算法有效利用.我们发现,处理器中多核共享内存这个特点,事实上可以间接为前面基于MPI的Sweep算法实现中存在的一些问题提供有效的解决方案.本文中,我们使用MPI/Pthreads的混合并行编程模式,设计了一种新的并行数据驱动Sweep算法,即Sweep-H.通过特别设计的多线程并行方案和DAG顶点调度策略,Sweep-H在通信效率和负载均衡方面均比之前的算法有显著提升.进一步,我们给出了Sweep-H的性能模型,它解释了为什么和在什么情况下Sweep-H比之前的纯MPI实现更加高效.在一个64节点(其中每个节点有12个处理器核)的机群上,我们进行了实验评估.结果显示,针对中等问题规模,Sweep-H具有接近线性的强可扩展性,并且当节点数大于16时,Sweep-H性能明显高于之前的纯MPI 算法(如,在64节点上,Sweep-H性能是纯MPI实现的近两倍).

     

    Abstract: 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).

     

/

返回文章
返回