https://doi.org/10.26089/NumMet.v27r331

Определение в системе SAPFOR устранимых зависимостей по массивам в последовательных Fortran-программах для их эффективного распараллеливания на вычислительные кластеры

Авторы

  • А. С. Колганов
  • О. Ю. Никитин

Ключевые слова:

SAPFOR (System FOR Automated Parallelization)
автоматизация распараллеливания для кластерных систем
устранимые зависимости
анализ зависимостей массивов
параллельные вычисления
DVM (Distributed Virtual Memory)
кластеры с графическими процессорами

Аннотация

Процесс автоматизации распараллеливания последовательных программ сталкивается с проблемой устранения зависимостей поданным, которые препятствуют параллельному выполнению циклов. Одним из эффективных методов решения этой проблемы является приватизация переменных, позволяющая создавать локальные копии данных для каждой итерации цикла. В данной статье представлен разработанный алгоритм статического анализа для определения приватизируемых массивов в программах на языке Fortran и его реализация в системе автоматизированного распараллеливания SAPFOR (System FOR Automated Parallelization). Предложенный алгоритм основан на анализе графа потока управления с удалением обратных ребер, решении уравнений потока данных и применении операции свертки вложенных циклов. Алгоритм был протестирован на четырех прикладных программах, входящих в пакет NAS Parallel Benchmarks. Данное исследование является шагом на пути к созданию полностью автоматической системы распараллеливания, способной минимизировать участие разработчика в процессе подготовки параллельной версии программы.


Загрузки

Опубликован

2026-08-17

Выпуск

Том 27 (2026): Выпуск 3.

Раздел

Параллельные программные средства и технологии

Авторы

А. С. Колганов

Московский государственный университет имени М.В. Ломоносова, факультет вычислительной математики и кибернетики

• научный сотрудник

О. Ю. Никитин

Московский государственный университет имени М.В. Ломоносова, факультет вычислительной математики и кибернетики

• магистрант

Библиографические ссылки

  1. A. S. Tanenbaum and H. Bos, Modern Operating Systems, 4th ed. (Pearson, Boston, 2015).
  2. OpenMP Architecture Review Board, OpenMP Application Programming Interface Version 5.1 (2020).
    https://www.openmp.org/specifications/ Cited August 14, 2026.
  3. OpenACC-Standard.org, The OpenACC Application Programming Interface, Version 3.3 (2022).
    https://www.openacc.org/specification Cited August 10, 2026.
  4. XcalableACC Language Specification, Version 1.0. RIKEN AICS and University of Tsukuba, (2017).
    http://xcalablemp.org/download/XACC/xacc-spec-1.0.pdf Cited August 10, 2026.
  5. Cetus: A Parallelizing Source-to-Source Compiler for C Programs.
    https://sites.udel.edu/cetus-cid/ Cited August 10, 2026.
  6. T. Grosser, A. Groesslinger, and C. Lengauer, “Polly – Performing Polyhedral Optimizations on a Low-Level Intermediate Representation,” Parallel Processing Letters 22 (04), Article Number 1250010 (2012).
    doi 10.1142/S0129626412500107
  7. CUDA Toolkit Documentation. NVIDIA Corporation.
    https://docs.nvidia.com/cuda/ Cited August 10, 2026.
  8. DVM-system | System for developing parallel programs.Documentation for C-DVMH and Fortran-DVMH Languages.
    http://dvm-system.org/ru/docs/ Cited August 10, 2026.
  9. A. S. Kolganov and G. D. Gusev, “Implementation of Private Variables Contraction Transformation of Sequential Fortran Programs for their Effective Parallelization into Computing Clusters in the SAPFOR,” Numerical Methods and Programming 26 (1), 58–84 (2025).
    doi 10.26089/NumMet.v26r105
  10. Z. Li, “Array Privatization for Parallel Execution of Loops,” in Proceedings of the 6th ACM International Conference on Supercomputing (ICS ’92), Washington D.C. USA, July 19–24, 1992(ACM, New York, NY, USA, 1992), pp. 313–322.
    doi 10.1145/143369.143426
  11. L. Rauchwerger and D. Padua, “The privatizing DOALL test: A run-time technique for DOALL loop identification and array privatization,” in Proceedings of the 8th International Conference on Supercomputing (ICS ’94), Manchester, England, July 11–15, 1994(ACM, New York, NY, USA, 1994), pp. 33–43.
    doi 10.1145/181181.181254
  12. P. Tu, D. Padua, “Automatic array privatization,” in Banerjee U., Gelernter D., Nicolau A., Padua D. (eds) Languages and Compilers for Parallel Computing. LCPC 1993.(Lecture Notes in Computer Science, vol 768. Springer, Berlin, Heidelberg, 1994), pp. 500–521.
    doi 10.1007/3-540-57659-2_29
  13. B. Blume, R. Eigenmann, K. Faigin, et al., “Polaris: The Next Generation in Parallelizing Compilers,” in Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing(Ithaca, NY, USA, 1994), pp. 459–474.
  14. J. Gu and Z. Li, “Efficient Interprocedural Array Data-Flow Analysis for Automatic Program Parallelization,” IEEE Transactions on Software Engineering 26 (3), 244–261 (2000).
    doi 10.1109/32.842950
  15. S. Rus, G. He, C. Alias, and L. Rauchwerger, “Region Array SSA,” in Proceedings of the 15th International Conference on Parallel Architectures and Compilation Techniques (PACT ’06), Seattle, WA, USA, September 16–20, 2006(ACM, New York, NY, USA, 2006), pp. 43–52.
    doi 10.1145/1152154.1152165
  16. P. Feautrier and C. Lengauer, “Polyhedron Model,” in Encyclopedia of Parallel Computing(Springer, New York, 2011), pp. 1581–1592.
  17. U. Bondhugula, A. Hartono, J. Ramanujam, and P. Sadayappan, “A practical automatic polyhedral parallelizer and locality optimizer,” ACM SIGPLAN Notices 43 (6), 101–113 (2008).
    doi 10.1145/1379022.1375595
  18. S. Verdoolaege, J. C. Juega, A. Cohen, et al., “Polyhedral Parallel Code Generation for CUDA,” ACM Transactions on Architecture and Code Optimization 9 (4), Article Number 54 (2013).
    doi 10.1145/2400682.2400713
  19. T. Grosser and T. Hoefler, “Polly-ACC Transparent Compilation to Heterogeneous Hardware,” in Proceedings of the International Conference on Supercomputing, Istanbul, Turkey, June 1–3, 2016(ACM Press, New York, NY, USA, 2016), pp. 1–13.
    doi 10.1145/2925426.2926286
  20. C. Lattner and V. Adve, “LLVM: A Compilation Framework for Lifelong Program Analysis and Transformation,” in Proceedings of the International Symposium on Code Generation and Optimization (CGO’04), San Jose, USA, March 20–24, 2004(IEEE Press, 2004), pp. 75–86.
    doi 10.1109/CGO.2004.1281665
  21. S. Wienke, P. Springer, C. Terboven, and D. an Mey, “OpenACC — First Experiences with Real-World Applications,” in Proceedings of the 18th International Conference on Parallel Processing (Euro-Par 2012), Rhodes Islands, Greece, August 27–31, 2012(Springer Berlin, Berlin, 2012), pp. 859–870.
    doi 10.1007/978-3-642-32820-6_85
  22. System for Automated Parallelization of FORtran programs (SAPFOR).
    http://keldysh.ru/dvm/SAPFOR/ Cited August 10, 2026.
  23. V. A. Bakhtin, O. F. Zhukova, N. A. Kataev, A. S. Kolganov, et al., “Automation of Parallelization of Software Complexes,” in Proc. XVIII All-Rus. Sci. Conf. on “Scientific Service on the Internet”, Novorossiysk, September 19–24, 2016(KIAM RAS, Moscow, 2016), pp. 76–85.
    doi 10.20948/abrau-2016-31
  24. A. S. Kolganov, Automation of Parallelization of Fortran Programs for Heterogeneous ClustersCandidate’s Dissertation in Mathematics and Physics. (Keldysh Inst. Applied Math., Moscow, 2020).
  25. A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques, and Tools, 2th ed.(Pearson/Addison Wesley, Boston, 2007).
  26. A. B. Kahn, “Topological sorting of large networks,” Communications of the ACM 5 (11), 558–562 (1962).
    doi 10.1145/368996.369025
  27. NAS Parallel Benchmarks.
    https://www.nas.nasa.gov/software/npb.html Cited August 10, 2026.

Лицензия

Copyright (c) 2026 А. С. Колганов, О. Ю. Никитин

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.