神威国产处理器应用程序的并行参数自动寻优

doi:10.3778/j.issn.1673-9418.1907054

摘要/Abstract

摘要：

有限差分模板计算算法常应用于“神威·太湖之光”上完成大气模拟、石油勘探等任务，由于该算法通信开销大，计算密度高，且神威系统结构复杂，应用程序数据规模大，在程序构建和执行时难以得到合理的参数对数据进行分割，程序性能难以得到保证。针对申威26010处理器硬件特性提出一种基于遗传算法的并行参数自动寻优方法。对消息传递接口数据规模参数和从核数据规模参数进行自动寻优，对二维有限差分模板计算算法进行高性能测试。该方法在10亿次的寻址空间内寻取更优解，与编译系统自动分配相比达到了10.79倍加速比。此外，还对逆时偏移成像算法进行优化测试，与编译系统自动分配相比表现出6.31倍加速比。该方法对应用程序数据规模参数进行自动寻优，为国产异构众核处理器的高性能并行优化提供有用指导。

关键词: 并行计算, 参数自动寻优, 遗传算法, 申威异构众核处理器, 有限差分算法

Abstract:

The finite difference algorithm is often applied to Sunway TaihuLight to complete atmospheric simula-tion, oil exploration, and other tasks. However, due to the high communication cost and calculation density of the algorithm, the complex structure of Sunway system and large scale of application data, it is difficult to obtain reason-able parameters for data distribution during application construction and execution, and the performance of corres-ponding applications is difficult to be satisfactory. According to the hardware characteristics of Sunway 26010 processor, a parallel parameter automatic optimization method based on genetic algorithm is proposed. The data size parameter of message passing interface and the kernel are automatically optimized, and the two-dimensional finite difference algorithm is tested for high performance. The method finds the better solution in the 1 billion addressing space and achieves an acceleration ratio of 10.79 times compared with the automatic allocation of compiler system. In addition, compared with the automatic allocation of compiler system, this paper achieves 6.31 times acceleration for optimizing reverse time migration. This method realizes the automatic optimization of the application data scale parameters and provides useful guidance for the high-performance parallel optimization of domestic heterogeneous many-core processors.

Key words: parallel computing, parameter automatic optimization, genetic algorithm, Sunway heterogeneous multi-core processor, finite difference algorithm

刘徐，肖志勇，甘霖，徐敬蘅，陈宏博. 神威国产处理器应用程序的并行参数自动寻优[J]. 计算机科学与探索, 2020, 14(11): 1838-1848.

LIU Xu, XIAO Zhiyong, GAN Lin, XU Jingheng, CHEN Hongbo. Automatic Optimization of Parallel Parameters for Sunway TaihuLight Super-computer Application Program[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(11): 1838-1848.

参考文献

[1] Fu H H, Liao J F, Yang J Z, et al. The Sunway TaihuLight supercomputer: system and applications[J]. Science China Information Sciences, 2016, 59(7): 072001.
[2] Top500 committee. The 25th Top500 list on Nov 2018[EB/OL]. [2018-11-13]. https://www.top500.org/lists/2018/11/.
[3] Xu J H, Fu H H, Shi W, et al. Performance tuning and analy-sis for stencil-based applications on POWER8 processor[J]. ACM Transactions on Architecture and Code Optimization, 2018, 15(4): 41.
[4] Araya-Polo M, Cabezas J, Hanzich M, et al. Assessing accelerator-based HPC reverse time migration[J]. IEEE Transactions on Parallel and Distributed Systems, 2010, 22(1): 147-162.
[5] Ortigosa F, Liao Q B, Guitton A, et al. Speeding up RTM velocity model building beyond algorithmics[M]//SEG Tech-nical Program Expanded Abstracts 2008. Society of Explora-tion Geophysicists, 2008: 3219-3223.
[6] Shen H X, Zheng K, Liu Y, et al. Parallel NSGA-II on Sunway many-core processor[J]. Computer Engineering and Applica-tions, 2018, 54(17): 35-40.沈焕学, 郑凯, 刘垚, 等. 申威众核处理器的并行NSGA-II算法[J]. 计算机工程与应用, 2018, 54(17): 35-40.
[7] Cantú-Paz E. Efficient and accurate parallel genetic algo-rithms[M]//Genetic Algorithms & Evolutionary Computation. Boston: Kluwer Academic Publishers, 2000.
[8] Man K F, Tang K S, Kwong S. Genetic algorithms. concepts and designs[J]. Assembly Automation, 1999, 20(1): 86-87.
[9] Williams S, Waterman A, Patterson D. Roofline: an insightful visual performance model for floating-point programs and multicore architectures: UCB/EECS-2008-134[R]. Berkeley: University of California, 2009.
[10] Shalf J, Kamil S, Oliker L, et al. Analyzing ultra-scale applica-tion communication requirements for a reconfigurable hybrid interconnect[C]//Proceedings of the ACM/IEEE SC2005 Con-ference on High Performance Networking and Computing, Seattle, Nov 12-18, 2005. Washington: IEEE Computer Society, 2005: 17.
[11] Sreepathi S, Grodowitz M L, Lim R, et al. Application characterization using Oxbow toolkit and PADS infras-tructure[C]//Proceedings of the 1st International Workshop on Hardware-Software Co-Design for High Performance Com-puting, New Orleans, Nov 16-21, 2014. Piscataway: IEEE,2014: 55-63.
[12] Shen M M, Lu Z H, Wang Y G. Parallel algorithm for para-meter optimization of hydrologic simulation[J]. Computer Engi-neering and Design, 2017, 38(4): 1002-1007.申蒙蒙, 陆忠华, 王彦棡. 水文模拟中并行参数优化算法[J]. 计算机工程与设计, 2017, 38(4): 1002-1007.
[13] Sunway TaihuLight user guide[EB/OL]. [2020-01-15]. http://www.nsccwx.cn/guide/5d47ec278ffa3771592d5baf.
[14] Fu H H, Liao J F, Ding N, et al. Redesigning CAM-SE for peta-scale climate modeling performance and ultra-high resolu-tion on Sunway TaihuLight[C]//Proceedings of the 2017 Inter-national Conference for High Performance Computing, Net-working, Storage and Analysis, Denver, Nov 12-17, 2017. New York: ACM, 2017: 1.
[15] Xu Y T, Fu H H, Gan L, et al. Performance optimization and analysis for different stencil kernels on multi-core and many-core architectures[C]//National Annual Conference on High Performance Computing, Guilin, 2013-10-29: 628-637.徐阳彤, 付昊桓, 甘霖, 等. 多核与众核架构下对不同Stencil的性能优化和分析[C]//全国高性能计算学术年会, 桂林, 2013-10-29: 628-637.
[16] Hong W J, Li K L, Quan Z, et al. PETSc’s heterogeneous par-allel algorithm design and performance optimization on the Sunway TaihuLight system[J]. Chinese Journal of Computers, 2017, 40(9): 2057-2069.洪文杰, 李肯立, 全哲, 等. 面向神威·太湖之光的PETSc可扩展异构并行算法及其性能优化[J]. 计算机学报, 2017,40(9): 2057-2069.
[17] Chen B W, Fu H H, Wei Y W, et al. Simulating the Wen-chuan earthquake with accurate surface topography on Sunway TaihuLight[C]//Proceedings of the 2018 International Conference for High Performance Computing, Networking, Storage, and Analysis, Dallas, Nov 11-16, 2018. Piscataway: IEEE, 2018: 40.
[18] Liang J J, Qu B Y, Suganthan P N, et al. Problem definitions and evaluation criteria for the CEC 2013 special session on real-parameter optimization: 201212[R]. Zhengzhou: Zhengzhou University, 2013.
[19] Luo J, Baz D E. A survey on parallel genetic algorithms for shop scheduling problems[C]//Proceedings of the 2018 IEEE International Parallel and Distributed Processing Symposium Workshops, Vancouver, May 21-25, 2018. Washington: IEEE Computer Society, 2018: 629-636.
[20] Xu Z G, Lin J, Matsuoka S. Benchmarking SW26010 many-core processor[C]//Proceedings of the 2017 IEEE Interna-tional Parallel and Distributed Processing Symposium Work-shops, Orlando, May 29-Jun 2, 2017. Washington: IEEE Com-puter Society, 2017: 743-752.
[21] Arcuri A, Fraser G. On parameter tuning in search based software engineering[C]//LNCS 6956: Proceedings of the 3rd International Symposium on Search Based Software Engi-neering, Szeged, Sep 10-12, 2011. Berlin, Heidelberg: Sprin-ger, 2011: 33-47.
[22] Durillo J J, Gschwandtner P, Kofler K, et al. Multi-objective region-aware optimization of parallel programs[J]. Parallel Computing, 2019, 83: 3-21.
[23] Wu F, Weimer W, Harman M, et al. Deep parameter optimisa-tion[C]//Proceedings of the Genetic and Evolutionary Com-putation Conference, Madrid, Jul 11-15, 2015. New York:ACM, 2015: 1375-1382.
[24] Cosenza B, Durillo J J, Ermon S, et al. Autotuning stencil computations with structural ordinal regression learning[C]//Proceedings of the 2017 IEEE International Parallel and Distri-buted Processing Symposium, Orlando, May 29-Jun 2, 2017. Washington: IEEE Computer Society, 2017: 287-296.
[25] Zhou Y, He F Z, Hou N, et al. Parallel ant colony optimization on multi-core SIMD CPUs[J]. Future Generation Computer Systems, 2018, 79: 473-487.
[26] Khmelev A, Kochetov Y. A hybrid local search for the split delivery vehicle routing problem[J]. International Journal of Artificial Intelligence, 2015, 13(1): 147-164.
[27] Bramerdorfer G, Zavoianu A C, Silber S, et al. Possibilities for speeding up the FE-based optimization of electrical mach-ines—a case study[J]. IEEE Transactions on Industry Appli-cations, 2016, 52(6): 4668-4677.
[28] Jhajj L S, Singh S. Deadline and cost based ant colony optimization algorithm for scheduling workflow applications in hybrid cloud[J]. International Journal of Scientific & Engineering Research, 2014, 5(10): 1417-1420.
[29] Harmanani H M, Drouby F, Ghosn S B. A parallel genetic algorithm for the open-shop scheduling problem using deter-ministic and random moves[C]//Proceedings of the 2009 Spring Simulation Multiconference, San Diego, Mar 22-27, 2009. New York: ACM, 2009: 30.
[30] Andreolli C, Thierry P, Borges L, et al. Characterization and optimization methodology applied to stencil computations[M]//Reinders J, Jeffers J. High Performance Parallelism Pearls. San Mateo: Morgan Kaufmann, 2015: 377-396.