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

Detection within the SAPFOR system of eliminable array dependencies in sequential Fortran programs for efficient parallelization on computing clusters

Authors

  • Alexander S. Kolganov
  • Oleg Yu. Nikitin

Keywords:

SAPFOR (System FOR Automated Parallelization)
automation of parallelization for clusters
eliminable dependencies
array dependence analysis
parallel computing
DVM (Distributed Virtual Memory)
GPU clusters

Abstract

The process of automating the parallelization of sequential programs faces the problem of eliminating data dependencies that prevent the parallel execution of loops. One of the effective methods to solve this problem is a variable privatization, which allows creating local copies of data for each loop iteration. This paper presents the implementation in the system SAPFOR (System FOR Automated Parallelization) of a static analysis algorithm for identifying privatizable arrays in Fortran programs. The proposed algorithm is based on the control flow graph analysis with back edge removal, solving data flow equations, and applying nested loop convolution. The algorithm was tested on four application programs from the NAS Parallel Benchmarks suite. This research is a step towards creating a fully automatic parallelization system capable of minimizing developer involvement in the process of preparing a parallel version of a program.


Downloads

Published

2026-08-17

Issue

Vol. 27 (2026): Issue 3.

Section

Parallel software tools and technologies

Authors

Alexander S. Kolganov

Lomonosov Moscow State University, Faculty of Computational Mathematics and Cybernetics

• Researcher

Oleg Yu. Nikitin

Lomonosov Moscow State University, Faculty of Computational Mathematics and Cybernetics

• Masterʼs student

References

  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.

License

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

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.