Исследование эффективности методов оптимизации программ для параллельных вычислительных систем с GPU

Цель. В работе определена актуальность задачи повышения эффективности программного обеспечения, под которой в данном случае понимается сокращение времени работы проектируемого программного обеспечения в процессе решения вычислительно-сложных задач. Метод. В качестве примера подобной задачи используется выполнение сингулярного разложения методом Якоби. Данная задача находит свое применение в различных областях от обработки сигналов и изображений до систем искусственного интеллекта. В качестве целевой вычислительной архитектуры выбраны параллельные вычислительные системы, оснащенные GPU. В работе рассматриваются методы повышения эффективности программного обеспечения для целевых вычислительных архитектур с использованием CUDA. Результат. Описаны существующие аналитические модели оценки эффективности компьютерных программ. Рассматривается влияние различных оптимизаций, таких как оптимизация пересылок данных, использования системы unified memory, количества потоков, паттерна доступа к памяти и ряда других на эффективность получаемого программного обеспечения. Описывается процесс оптимизации программной реализации сингулярного разложения, приводятся результаты вычислительных экспериментов. Вывод. При увеличении числа потоков производительность может вырасти больше, чем количество потоков. Влияние паттерна доступа к памяти: при оптимальной последовательности доступа к памяти производительность заметно повышается. Настройка доли памяти, используемой для L1 кеша и для shared memory не оказывает существенного влияния на производительность.

1. A. G. Akritas and G. I. Malaschonok, “Applications of singular-value decomposition (SVD),” Mathematics and Computers in Simulation, vol. 67, pp. 15-31, 2004

2. Natarajan, Venkatanathan. “Singular Spectral Analysis (Ssa) of Solid Earth Tide (Set)-Implications to Identify Earthquake Precursors and Earthquakes in the Himalayan Region (M≥ 6) During 1991-2021.” (2022).

3. Ahmadi-Asl S. et al. Randomized algorithms for computation of Tucker decomposition and higher order SVD (HOSVD), 2021, IEEE Access, vol. 9, pp. 28684-28706

4. Wall M. E., Rechtsteiner A., Rocha L. M. Singular value decomposition and principal component analysis //A practical approach to microarray data analysis. – Boston, MA : Springer US, 2003. – С. 91-109.

5. Hammarling S. The singular value decomposition in multivariate statistics //ACM Signum Newsletter. – 1985. – Т. 20. – №. 3. – С. 2-25.

6. Amey J. L. et al. Neural network interpretation using descrambler groups //Proceedings of the National Academy of Sciences. – 2021. – Т. 118. – №. 5. – С. e2016917118.

7. S. Williams, A. Waterman, and D. Patterson, “Roofline: An Insightful Visual Performance Model for Multicore Architectures,” Comm. ACM, vol. 52, no. 4, pp. 65-76, 2009

8. H. Jia, Y. Zhang, G. Long, J. Xu, S. Yan, and Y. Li, “GPURoofline: A Model for Guiding Performance Optimizations on GPUs,” Proc. 18th Int’l Conf. Parallel Processing (Euro-Par ’12), vol. 7484, pp. 920-932, 2012.

9. T. Cramer, D. Schmidl, M. Klemm, and D. an Mey, “OpenMP Programming on Intel Xeon Phi Coprocessors: An Early Performance Comparison,” Proc. Many-Core Applications Research Community Symp. at RWTH Aachen Univ., pp. 38-44, 2012.

10. J. Treibig, G. Hager and G. Wellein: LIKWID: A lightweight performance-oriented tool suite for x86 multicore environments. Proceedings of PSTI2010, the First International Workshop on Parallel Software Tools and Tool Infrastructures, San Diego CA, September 13, 2010. DOI: 10.1109/ICPPW.2010.38 Preprint: http://arxiv.org/abs/1004.4431

11. Tutorial: Empirical Roofline Model // github.com: электронный ресурс. URL: https://github.com/RRZE-HPC/likwid/wiki/Tutorial:-Empirical-Roofline-Model (дата обращения: 18.08.2023)

12. Z. Cui, Y. Liang, K. Rupnow, and D. Chen, “An Accurate GPU Performance Model for Effective Control Flow Divergence Optimization,” Proc. IEEE 26th Int’l Parallel Distributed Processing Symp. (IPDPS), pp. 83-94, 2012

13. W. W. L. Fung, I. Sham, G. Yuan, and T. M. Aamodt, “Dynamic Warp Formation and Scheduling for Efficient GPU Control Flow,” in Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, ser. MICRO 40, 2007, pp. 407–420.

14. J. Meng, D. Tarjan, and K. Skadron, “Dynamic warp subdivision for integrated branch and memory divergence tolerance,” in Proceedings of the 37th annual international symposium on Computer architecture, ser. ISCA’10, 2010, pp. 235–246

15. E. Z. Zhang, Y. Jiang, Z. Guo, and X. Shen, “Streamlining GPU applications on the fly: thread divergence elimination through runtime thread-data remapping,” in Proceedings of the 24th ACM International Conference on Supercomputing, ser. ICS ’10, 2010, pp. 115–126.

16. CUDA C++ programming guide // docs.nvidia.com: электронный ресурс. URL: https://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html (дата обращения: 18.08.2023)

17. Yu, Qi & Childers, Bruce & Huang, Libo & Qian, Cheng & Wang, Zhiying. (2020). A quantitative evaluation of unified memory in GPUs. The Journal of Supercomputing. 76. 10.1007/s11227-019-03079-y.

18. Chien, Steven & Peng, Ivy & Markidis, Stefano. (2019). Performance Evaluation of Advanced Features in CUDA Unified Memory. 50-57. 10.1109/MCHPC49590.2019.00014. A quantitative evaluation of unified memory in GPUs Qi Yu Bruce Childers Libo Huang Cheng Qian Zhiying Wang

19. How to Access Global Memory Efficiently in CUDA C/C++ Kernels // Nvidia technical blog: электронный ресурс. URL: https://developer.nvidia.com/blog/how-access-global-memory-efficiently-cuda-c-kernels/ (дата обращения: 18.08.2023)

20. QueryPerformanceCounter function – Win32 apps // Microsoft Learn: электронный ресурс. URL: https://learn.microsoft.com/en-us/windows/win32/api/profileapi/nf-profileapi-queryperformancecounter (дата обращения: 18.08.2023)

21. CUDA Pro Tip: Write Flexible Kernels with Grid-Stride Loops // Nvidia technical blog: электронный ресурс. URL: https://developer.nvidia.com/blog/cuda-pro-tip-write-flexible-kernels-grid-stride-loops/ (дата обращения: 18.08.2023)