星系分组算法的并行设计与优化:SGI系统与分布式集群对比

摘要

Halo-based galaxy group finder (HGGF) is an effective algorithm that accomplishes the task of galaxy group finding based on galaxy coordinates,redshift and mass etc.,and provides great help in the research of galaxy group formation and evolution.However,current pure OpenMP implementation of the algorithm is limited by the resource of the underlying single compute node when dealing with large-scale group finding problems.One of the possible solutions is using resources from multiple nodes to reduce execution time while solving large-size galaxy group finding problem.Therefore,it is essential to redesign and implement the algorithm.The major hurdle for such an attempt is remoting memory access due to semi-random galaxy access in the algorithm which damages the performance in multi-node environment.To tackle such a problem,we paralleled the algorithm with adjacent galaxy list design and used unified parallel C (UPC) to implement it.2.25,2.78 and 5.07 times speedup for the kernel were achieved with 4,8 and 16 nodes respectively.Meanwhile,the memory requirement on each node was also reduced significantly.Experiments of OpenMP version of the algorithm on SGI UV 2000 show that due to the nature of the program and the features of NUMA architecture,programs with random memory access behavior like HGGF may not readily benefit from the large number of threads and shared memory provided by such machines.Two-level parallel design that takes advantage of locality principle on distributed memory clusters may be a better solution.%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结构的共享内存系统中提供的大规模线程与内存资源来直接取得高加速比.在分布式内存集群上采用两级并行设计,以更好地利用局部性原理,可能是更好的解决方案.