Размещено на http://www.allbest.ru/

Анализ и преобразование последовательных программ с целью устранения индуктивных переменных циклов

14.01.2014 г., Н.А.Катаев

В 2013 году был предложен механизм анализа и преобразования последовательных программ с целью устранения индуктивных переменных циклов, мешающих эффективному распараллеливанию.

Переменная индукции, или индуктивная переменная цикла - переменная, на каждой итерации цикла изменяющая свое значение на некоторую величину, отличную от нуля и инвариантную (неизменную после любого количества итерации) для данного цикла. Введенное определение эквивалентно определению из [1, с. 820].

Значение переменной индукции в начале итерации с номером выражается, во-первых, через значение данной переменной в начале итерации с номером : , во-вторых, через номер итерации: . При этом - значение индукционной переменной перед входом в цикл, и - символьные константы (величины, инвариантные для цикла). Будем называть - шагом индукции, - начальным значением индукции.

Изменение значения переменной индукции на каждой итерации цикла вызывает в цикле антизависимость и зависимость через выход [1, с. 846], устранение которых необходимо для распараллеливания данного цикла.

Переменные индукции обычно используются для обращения к элементам массива. В этом случае знание шага индукции необходимо для доказательства отсутствия зависимости между двумя обращениями и возможности распараллеливания цикла.

Для эффективного распараллеливания последовательных программ необходимо:

1. Выполнить анализ переменных индукции: для каждого цикла программы определить переменные индукции, их начальные значения и шаги.

2. Выполнить преобразование последовательной программы: устранить зависимости, вызванные изменением значений переменных индукции.

Для анализа индукционных переменных было решено воспользоваться подходом, описанным в [1, с. 819] и использующим алгоритм анализа на основе областей [1, c. 803]. Указанный подход обладает следующими недостатками:

1. Анализ выполняется в рамках одной процедуры, без выполнения межпроцедурного анализа.

2. Анализ позволяет определить инварианты циклов, только если они являются афинными выражениями [1, c. 820]. Знание инвариантов циклов необходимо для выполнения предложенного преобразования последовательной программы.

3. Анализ позволяет определить только те индукционные переменные, шаг которых является константой (не символьной константой).

В ходе работы над проектом указанные недостатки были устранены. Анализ выполняется над представлением процесса распараллеливания программы в системе САПФОР [2], разработанном на предыдущем этапе проекта в 2012 году. Таким образом, разработанный в 2013 году алгоритм анализа переменных индукции не зависит от языка программирования и состоит из следующих шагов:

I. Построение иерархии и упорядочивание областей (см. Рис. 1):

1. Выделение сильно связных компонент [3, c. 635] в графе вызовов последовательной программы. Граф вызовов программы - ориентированный граф, вершинами которого являются процедуры, а дуги указывают направление вызова одной процедуры из другой. Каждой дуге графа соответствует список точек вызова, указывающих места в вызывающей процедуре, в которых осуществляется вызов вызываемой процедуры. Сильно связные компоненты разбивают граф вызовов на группы процедур, рекурсивно вызывающих друг друга.

2. Упорядочивание в глубину графа [1, c. 790], полученного на основе графа вызовов, каждая сильно связная компонента которого рассматривается как единая вершина.

3. Для каждой процедуры в порядке установленном на этапе (II.2), а для процедур, входящих в сильно связные компоненты, в произвольном порядке:

a. Построение графа потока управления (CFG) на основе представления процесса распараллеливания в САПФОР. Граф управления процедуры - ориентированный граф, вершинами которого являются базовые блоки [3, c. 641], а дуги показывают направление потока управления в программе. Вызовы процедур выделяются в отдельные базовые блоки, при необходимости могут быть введены временные внутренние переменные для сохранения промежуточных результатов вызовов функций.

b. Построение дерева доминаторов [1, c. 787] для графа потока управления процедуры.

c. Построение глубинного остовного дерева [1, c. 790] для графа потока управления процедуры.

d. Построение дерева естественных циклов [1, c. 798]. В алгоритме предполагается, что граф потока управления процедуры приводим [1, c. 794]. Данное предположение оправдано тем, что при использовании структурированных инструкций (ветвления, циклы) графы потока всегда приводимы. В остальных случаях можно воспользоваться алгоритмом расщепления графа потока [1, c. 816].

e. Получение иерархии областей, являющихся базовыми блоками, телами циклов, циклами и всей процедурой [1, c. 805]. Циклы обрабатываются в направлении обратного обхода дерева циклов (от самых внутренних к внешним). При построении области, являющейся телом цикла, выполняется упорядочивание всех ее подобластей в топологическом порядке [3, c. 632].

II. Восходящий анализ последовательности областей в порядке, обратном установленному на этапе I.

III. Нисходящий анализ в порядке, установленном на этапе I, для поиска значений потока данных в начале и конце каждой области.

Рис. 1. Построение иерархии и упорядочивание областей.

На шагах II и III используется общая схема алгоритма анализа на основе областей с рядом дополнений.

Во-первых, если рассматриваемая в данный момент область является базовым блоком, содержащим вызов процедуры (согласно I.3.а такой базовый блок не может содержать других операций), считается, что данная область является внешней по отношению к области соответствующей всей процедуре.

Во-вторых, передаточные функции, их композиция, сбор и замыкания расширяют описанные в [1, с. 819] с целью устранения недостатков (2) и (3) указанных пере описанием данного алгоритма.

Если после вычисления передаточной функции для инструкции присваивания некоторого значения переменной , вводится вспомогательная ссылочная переменная [1, с. 819] и инструкция присваивания . Далее считается, что . Здесь - символическое отображение [1, c. 822], отображающее переменную на ее представление в виде афинного выражения, - специальный символ, представляющий неафинное выражение.

В результате влияние одной итерации цикла будет подытожено передаточной функцией одного из следующих видов:

1.

2.

3.

Где - константы, - вспомогательные ссылочные переменные, введенные во внешних по отношению к обрабатываемому циклу областях, - вспомогательные ссылочные переменные введенные внутри тела обрабатываемого цикла.

Если значение является инвариантной величиной для обрабатываемого цикла, то в случае (1) или (2) является символьной константой, а в случае (2) переменной индукции с шагом . Так как вспомогательные ссылочные переменные получают значение только один раз в точке появления, сумма имеет величину инвариантную для данного цикла. Для проверки инвариантности суммы достаточно убедиться в инвариантности переменных , то есть убедиться, что на каждой итерации им присваивается одно и то же значение. Для этого достаточно убедиться, что переменные , используемые в выражении из инструкции присваивания , являются инвариантными. Если , то является символьной константой, , то символьной константой, не является. Если и если инструкция присваивания значения вспомогательной ссылочной переменной, доминирует над инструкцией присваивания , то символьной константой, не является (см. Рис. 2), иначе переходим к исследованию переменной . Отметим, что в этом случае инструкция присваивания доминирует над инструкцией присваивания .

Рис. 2. Определение переменной, не являющейся символьной константой

Полученная в процессе анализа информация об переменных индукции и инвариантах циклов позволяет выполнить в автоматическом режиме ряд преобразований, устраняющих в циклах зависимости по данным, вызванные использованием переменных индукции. На Рис. 3 приведено тривиальное преобразование, на выполнении которого основаны другие преобразования, u(Var_P) - символьная константа, Var_P - множество переменных программы.

индуктивный переменная распараллеливание

Рис. 3. Тривиальное преобразование цикла.

Рассмотрим гнездо циклов на Рис. 4.

Рис. 4. Преобразуемое гнездо циклов

Если r_i(Var_P) - инвариант для цикла по переменной j, то переменная x является переменной индукции для данного цикла и можно выполнить преобразование, показанное на Рис. 5.

Рис. 5. Преобразование для случая, когда r_i(Var_P) - инвариант для цикла по переменной j

Если r_i(Var_P)- инвариантом для цикла по переменной j не является, то переменная x является переменной индукции только для цикла по переменной i. Если воспользоваться тривиальным преобразованием, будет потеряна тесная вложенность циклов. Это может негативно сказаться на эффективности проводимого распараллеливания. Можно ввести дополнительный массив, в котором заранее рассчитать количество итераций внутреннего цикла, выполненных до начала каждой итерации внешнего. Указанное преобразование приведено на Рис. 6. Отметим, что данное преобразование стоит выполнять лишь в том случае, если порождаемые им накладные расходы будут компенсированы полученным выигрышем от распараллеливания цикла. Соответствующие оценки должен выполнять блок распараллеливания (эксперт) системы САПФОР при построении схем распараллеливания программы.

Рис. 6. Преобразование для случая, когда r_i(Var_P) - не инвариант для цикла по переменной j

Возможно ситуация, когда при выполнении описанных преобразований количество итераций в цикле в момент начала выполнения цикла не известно, например, из-за дополнительных выходов из цикла с помощью оператора exit. В этом случае рассчитать значение индукционной переменной после выхода из цикла не возможно.

Для того, чтобы итерации цикла можно было выполнять независимо в произвольном порядке необходимо удостоверится, что значение индукционной переменной не используется после цикла. Для этого необходимо и достаточно, чтобы переменная индукции после преобразования стала приватной [4], а не приватной по выходу [4]. Для этого можно воспользоваться алгоритмом анализа приватных переменных приведенном в [4].

Рассмотрим разработанные алгоритмы на примере программы на языке программирования Фортран, представленной на Рис. 7. Значения массивов a и b после выполнения программы с параметрами N = 2 и M = 2 приведены на Рис. 8.

В циклах из строк 12 и 14 присутствуют зависимости по данным, вызванные использованием вспомогательных переменных индукции k и l, которые могут быть выявлены с помощью разработанного алгоритма анализа переменных индукции. Начальное значение переменных равно 0, шаг равен M.

Рис. 7. Тестовая программа на языке Фортран

Рис. 8. Значения массивов a и b после выполнения программы с параметрами N = 2 и M = 2

Разработанный алгоритм преобразования последовательных программ позволяет заменить циклы из строк 12 и 14 гнездом тесно вложенных циклов, приведенным на Рис. 9.

Воспользовавшись алгоритмом анализа приватных скалярных переменных, описанным в [4], можно доказать, что в преобразованной программе переменные k и l стали приватными и их значения после выхода из цикла не используются.

В результате программа может быть распараллелена как с помощью технологии OpenMP так и в модели DVM. Отметим, что при автоматическом распараллеливании в модели DVM является важным тесная вложенность преобразованных циклов. Результаты запусков преобразованных OpenMP и DVM версий программы приведены в Таблице 1 и Таблице 2.

Рис 9. Преобразованное гнездо циклов

Таблица 1. Результаты запусков OpenMP версии программы с параметрами N = 500 и M = 2

Таблица 2. Результаты запусков DVM версии программы с параметрами N = 10000 и M = 2

Ахо А.В., Лам М.С., Сети Р., Ульман Дж.Д. Компиляторы: принципы, технологии и инструментарий, 2-е издание. : Пер. с англ.- М. : ООО "И.Д.Вильямс", 2008.-1184 с. Главы 9-12.

1. Катаев Н.А. Особенности внутреннего представления системы САПФОР. -- Параллельные вычислительные технологии (ПаВТ'2013): труды международной научной конференции (1-5 апреля 2013 г., г. Челябинск). 2013. С. 380-386

2. Алгоритмы: построение и анализ, 2-е издание. : Пер. с англ. - М.: Издательский дом «Вильямс», 2005. - 1296 с. Глава 22.

3. Катаев Н.А. Статический анализ последовательных программ в системе автоматизированного распараллеливания САПФОР // Вестник Нижегородского университета им. Н.И. Лобачевского. - Н. Новгород: Изд-во ННГУ. N5(2) , 2012.

Размещено на Allbest.ru