Detection within the SAPFOR system of eliminable array dependencies in sequential Fortran programs for efficient parallelization on computing clusters
Open Access
- 1 July 2026
- journal article
- Published by Research Computing Center Lomonosov Moscow State University in Numerical Methods and Programming (Vychislitel'nye Metody i Programmirovanie)
- Vol. 27 (3) , 489-513
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. Процесс автоматизации распараллеливания последовательных программ сталкивается с проблемой устранения зависимостей по данным, которые препятствуют параллельному выполнению циклов. Одним из эффективных методов решения этой проблемы является приватизация переменных, позволяющая создавать локальные копии данных для каждой итерации цикла. В данной статье представлен разработанный алгоритм статического анализа для определения приватизируемых массивов в программах на языке Fortran и его реализация в системе автоматизированного распараллеливания SAPFOR (System FOR Automated Parallelization). Предложенный алгоритм основан на анализе графа потока управления с удалением обратных ребер, решении уравнений потока данных и применении операции свертки вложенных циклов. Алгоритм был протестирован на четырех прикладных программах, входящих в пакет NAS Parallel Benchmarks. Данное исследование является шагом на пути к созданию полностью автоматической системы распараллеливания, способной минимизировать участие разработчика в процессе подготовки параллельной версии программы.Keywords
This publication has 13 references indexed in Scilit:
- Polyhedral parallel code generation for CUDAACM Transactions on Architecture and Code Optimization, 2013
- POLLY — PERFORMING POLYHEDRAL OPTIMIZATIONS ON A LOW-LEVEL INTERMEDIATE REPRESENTATIONParallel Processing Letters, 2012
- OpenACC — First Experiences with Real-World Applications2012
- A practical automatic polyhedral parallelizer and locality optimizerACM SIGPLAN Notices, 2008
- Region array SSA2006
- LLVM: A compilation framework for lifelong program analysis & transformation2004
- Efficient interprocedural array data-flow analysis for automatic program parallelizationIEEE Transactions on Software Engineering, 2000
- The privatizing DOALL test1994
- Automatic array privatization1994
- Array privatization for parallel execution of loops1992