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. Данное исследование является шагом на пути к созданию полностью автоматической системы распараллеливания, способной минимизировать участие разработчика в процессе подготовки параллельной версии программы.

This publication has 13 references indexed in Scilit: