Computer Science ›› 2017, Vol. 44 ›› Issue (10): 80-84.doi: 10.11896/j.issn.1002-137X.2017.10.015

Previous Articles     Next Articles

Parallel Design and Optimization of Galaxy Group Finding Algorithm on Comparation of SGI and Distributed-memory Cluster

SI Yu-meng, WEI Jian-wen, Simon SEE and James LIN   

  • Online:2018-12-01 Published:2018-12-01

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

Key words: High performance computing,Galaxy group finding,Parallel computing,UPC,OpenMP

[1] KWON Y C,DYLAN N,JEFFREY G,et al.Scalable clusteringalgorithm for N-body simulations in a shared-nothing cluster[M]∥Scientific and Statistical Database Management.Springer Berlin Heidelberg,2010:132-150.
[2] YANG X H,MO H J,VAN DEN B,et al.A halo-based galaxy group finder:calibration and application to the 2dFGRS[J].Monthly Notices of the Royal Astronomical Society,2005,356(4):1293-1307.
[3] YANG X H,MO H J,VAN DEN B,et al.Galaxy groups in the SDSS DR4.I.The catalog and basic properties[J].The Astrophysical Journal,2007,671(1):153.
[4] WILLIAM C,et al.UPC Language Specifications Version 1.3
[5] Intel VTune Amplifier XE.
[6] Technical Advances in the SGI UV Architecture.
[7] HAO H,SI Y M,WEI J W,et al.Optimizing Irregular Memory Access in Astrophysical Clustering Studies[J].Journal of Frontiers of Computer Science and Technology,2017,11(1):80-90.(in Chinese) 郝赫,司雨蒙,韦建文,等.天体物理成团研究中的非规则访存优化[J].计算机科学与探索,2017,11(1):80-90.
[8] MARK D,GEORGE E,CAROS F,et al.The evolution of large-scale structure in a universe dominated by cold dark matter[J].The Astrophysical Journal,1985,292(2):371-394.
[9] NEAL K,LARS H,DAVID W.Galaxies and gas in a cold dark matter universe[J].The Astrophysical Journal,1992,399(2):L109-L112.
[10] EISENSTEIN D J,HUT P.Hop:A new group-finding algo-rithm for n-body simulations[J].The Astrophysical Journal,1998,498(1):137.
[11] LIU Y,LIAO W K,CHOUDHARY A.Design and evaluation of a parallel HOP clustering algorithm for cosmological simulation[C]∥International Parallel and Distributed Processing Symposium,2003.IEEE,2003.
[12] FU B,REN K,LPEZ J,et al.DiscFinder:A data-intensivescalable cluster finder for astrophysics[C]∥Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing.2010:348-351.

No related articles found!
Full text



No Suggested Reading articles found!