关键词: 天体物理成团, 非规则访存优化, 数据预排序, 并行计算

Abstract: Halo-based galaxy group finder (HGGF) tries to find galaxies in the same dark matter halo which is not directly visible. It plays a very important role in the research of large-scale structure of the universe. However, because of the growth of data scale, it’s extremely necessary to increase the running speed by optimizing the group finder coding algorithm. After a thorough investigation on the original HGGF code, it is found that the kernel part of the algorithm is seriously affected by the irregular memory access. This paper proposes a specific data pre-sorting approach and analyzes how it affects the process of memory access according to the structure of the algorithm and the irregular memory access pattern. Moreover, this paper uses data alignment and loop fission to optimize the memory access as well as improving the efficiency of OpenMP with load balance and mutex privatization. Eventually the HGGF application gets 11.6 times speedup on 12 threads, and gets better weak scalability. The following is the original contributions: (1) Analyze the irregular memory access of the HGGF application; (2) Propose and analyze the  data pre-sorting; (3) Improve the parallel performance of HGGF application with another four approaches including data alignment, loop fission, load balance and mutex privatization.

Key words: astrophysical clustering studies, optimizing irregular memory access, data pre-sorting, parallel computing