%A 司雨濛,韦建文,Simon SEE,林新华 %T 星系分组算法的并行设计与优化:SGI系统与分布式集群对比 %0 Journal Article %D 2017 %J 计算机科学 %R 10.11896/j.issn.1002-137X.2017.10.015 %P 80-84 %V 44 %N 10 %U {https://www.jsjkx.com/CN/abstract/article_16700.shtml} %8 2018-12-01 %X Halo-based Galaxy Group Finder (HGGF) 是一种有效的星系分组算法,它根据星系的空间位置、红移、质量等多种属性将星系分组,从而为星系组的形成与演化研究提供重要依据。但是,算法当前的OpenMP实现版本仅能利用单节点提供的资源,在大规模星系分组问题上的应用受到限制。一种优化思路是采用多机并行,使其可以利用更多资源来解决更大规模的星系分组问题,并缩短执行时间。因此,有必要对算法重新进行设计与实现。实现此目标的一大挑战是程序中存在大量半随机性远端内存访问,其在多机并行环境下会对性能造成重大影响。为克服这一难题,设计中提出了邻接星系链表思想,并采用Unified Parallel C (UPC)进行程序实现。对于核代码部分,使用4,8,16节点时,可分别取得2.25,2.78,5.07倍的加速比;同时,对单个节点的内存需求也显著减少。OpenMP版本在SGI UV 2000上的实验结果显示,受限于程序的访存特性与机器体系架构的特点,类似HGGF算法这种具有随机数据访问特征的程序,很难有效利用NUMA结构的共享内存系统中提供的大规模线程与内存资源来直接取得高加速比。在分布式内存集群上采用两级并行设计,以更好地利用局部性原理,可能是更好的解决方案。