Основы распараллеливания программ, их динамический анализ

31

Аннотация

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

Оглавление

1 Введение 3

1.1 Параллельное программирование 3

1.2 Автоматизация распараллеливания 5

1.3 Статический анализ 6

1.4 Динамический анализ 8

1.5 Распараллеливание во время выполнения 9

1.6 Цель работы 10

2 Постановка задачи 11

2.1 Зависимости по данным 11

2.2 Система автоматизации распараллеливания 12

2.3 Задача анализатора 13

3 Динамический анализ 14

3.1 Схема работы динамического анализатора 14

3.2 Динамический анализ с использованием дерева контекстов 15

3.3 Динамический анализ с использованием глобальных номеров итераций. 17

3.4 Преимущества и недостатки динамического анализа. 19

4 Практическая реализация 22

4.1 Инструментация 22

4.2 Формат результатов 24

4.3 Внутреннее устройство анализатора 26

4.4 Результаты тестирования 28

5 Заключение 30

6 Литература 31

1. Введение

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

1.1 Параллельное программирование

Параллельным программированием будем называть процесс написания программы для многопроцессорной системы. Разумеется, параллельное программирование имеет ряд особенностей по сравнению с традиционным последовательным программированием. Кроме того, в зависимости от типа многопроцессорной системы применяются различные средства программирования:

Системы с общей памятью (SMP) - набор параллельно работающих процессоров, имеющих доступ к общей для всех процессоров памяти, причем скорость доступа к памяти одинакова для всех процессоров. Применяется программирование в модели общей памяти, как правило, с использованием интерфейса OpenMP.

Системы с неоднородным доступом (NUMA) - набор блоков, содержащих несколько процессоров и общую для них память. При этом допускается обращение любого процессора к удаленной памяти, т.е. памяти другого блока, но обращение происходит медленнее, чем обращение к локальной памяти. При программировании применяется, например, система Shmem.

Системы с распределенной памятью (MPP) - набор узлов, состоящих из процессора и памяти, и коммутационной среды для связи между узлами. Каждый процессор имеет непосредственный доступ только к своей локальной памяти. При программировании применяется модель передачи сообщений, используются библиотеки MPI, PVM и др.

Смешанные системы - набор SMP-узлов, соединенных коммутационной средой. Применяется комбинация моделей передачи сообщений и общей памяти. Часто также используется чистая модель передачи сообщений, тогда каждый процессор в SMP-узле трактуется как независимый узел со своей локальной памятью.

К сожалению, специалист в предметной области, способный разработать алгоритм и запрограммировать его на каком-либо языке программирования (например, Си или Фортране), далеко не всегда знаком с приемами написания параллельных программ и зачастую не может самостоятельно привести свою программу к виду, выполнимому на многопроцессорной машине. Поэтому распараллеливанием таких программ занимаются отдельные люди - специалисты по написанию параллельных программ. Это приводит к увеличению необходимого числа программистов, работающих над программой и потере времени на хотя бы минимальное знакомство специалиста с предметной областью.

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

1.2 Автоматизация распараллеливания

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

Процесс распараллеливания можно разделить на две части:

Анализ исходной программы.

Синтез параллельной программы.

Анализ необходим для выявления скрытого параллелизма в исходной последовательной программе. Прежде всего, сюда включается выявление зависимостей по данным между операторами программы. Такая зависимость возникает, например, в случае, если один оператор использует значение переменной, вычисленное некоторым другим оператором. Независимые операторы могут быть выполнены параллельно на разных процессорах. Обычно этот принцип применяется к циклам: если нет зависимостей по данным между разными витками цикла, то витки могут быть выполнены параллельно разными процессорами. Также на этапе анализа могут собираться сведения о необходимом размещении данных в случае, если используется система с распределенной памятью. Кроме того, возможен сбор сведений о времени выполнения различных участков программы с целью выбора наилучшего варианта распараллеливания программы.

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

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

Помимо анализа программы система автоматизации распараллеливания может получать различную информацию от пользователя. Так, например, система ParaWise [1] предлагает итерационный процесс анализа: статический анализ исходной программы и получение дополнительной информации от пользователя чередуются до получения приемлемого результата.

Другим примером системы автоматизации распараллеливания может служить проект V-Ray [2]. Эта система включает статический анализ структуры программы и информационных зависимостей, присутствующих в программе, а также динамический анализ параллельных программ. Система позволяет оптимизировать существующие программы, а также получить эффективные реализации программ для различных аппаратных платформ путем анализа лежащего в основе программ алгоритмического подхода.

1.3 Статический анализ

Статические методы анализа основаны на исследовании исходного текста программ. Основная идея таких методов заключается в построении по индексным выражениям в операторах, обращающихся к массивам, систем уравнений и неравенств с неизвестными, соответствующими индексным переменным циклов. Например, для следующего фрагмента программы:

for (i=1; i<n; i++)

a[i] = a[i-1] + 1;

на основе использование одного и того же массива «а» может быть получено уравнение

<инд. выр-е в левой части> = <инд. выр-е в правой части на другой итерации>, то есть i1 = i2-1 .

Решение данного уравнения покажет наличие зависимости между соседними итерациями цикла: каждая следующая итерация использует значение, вычисленное на предыдущей итерации.

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

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

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

В языках, подобных Си, у статических методов появляется еще одна проблема: интенсивное использование указателей. Как правило, статические методы анализа не могут работать с указателями, равно как и с весьма сложными выражениями, являющимися в языке нормой. Можно обязать программиста писать программы без использования соответствующих конструкций языка, но такие ограничения не применимы при распараллеливании библиотек, оптимизированных для выполнения на однопроцессорной машине.

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

1.4 Динамический анализ

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

Такой подход позволяет производить выявление зависимостей во многих ситуациях, когда статический анализ невозможен. Поскольку анализ происходит во время выполнения программы, анализатору доступны значения всех переменных, присутствующих в программе. Поэтому появляется возможность проанализировать любые ссылки на элементы массивов: через индексные выражения любой сложности, включая вызовы функций, через указатели. Динамический анализатор всегда может однозначно установить ячейку памяти, которая используется в любом операторе программы.

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

1.5 Распараллеливание во время выполнения

В некоторых случаях невозможно заранее сказать, будет ли некоторый цикл в программе параллельным (например, это зависит от входных данных). Как правило, в такой ситуации распараллеливание считается невозможным. Но иногда удается сформулировать достаточно простое условие, при котором вероятные зависимости по данным исчезают. Тогда применяется следующее решение: в параллельную программу включается два варианта данного фрагмента программы: один параллельный, другой последовательный. Во время выполнения программы проверяется выполнение условия, и в зависимости от результата выполняется либо один фрагмент, либо другой.

Аналогично работает схема inspector-executor. Спорный цикл выполняется 2 раза. Первый раз - для выяснения, является ли цикл параллельным. При этом никаких вычислений не производится. Второй раз - уже реальное выполнение вычислений с учетом результата первого прохода. Дополнительный плюс такой схемы состоит в том, что, когда один и тот же цикл выполняется много раз, а его основные параметры остаются одними и теми же, инспекционный проход можно делать только один раз, используя полученный результат при каждом новом выполнении цикла.

Таким образом, вынесение некоторых проверок с этапа анализа на этап выполнения программы позволяет смягчить ограничения методов, рассмотренных выше.

1.6 Цель работы

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

2. Постановка задачи

2.1 Зависимости по данным

Зависимость по данным образуют любые два оператора программы, обращающиеся к одной ячейке памяти, если хотя бы один из них производит запись в эту ячейку [3]. Существует 3 вида зависимостей по данным. Пусть s1 и s2 - операторы в программе, обращающиеся к одной ячейке памяти, и s2 выполняется после s1. Операторы s1 и s2 могут быть одним и тем же оператором программы. В зависимости от порядка чтения и записи используемой ячейки зависимости подразделяются следующим образом:

прямая зависимость (true dependence) - s1 записывает значение в ячейку памяти, а s2 считывает,

обратная зависимость (anti dependence) - s1 считывает значение, а s2 записывает,

зависимость по выходу (output dependence) - оба оператора s1 и s2 производят запись в ячейку.

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

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

Пусть есть зависимость по данным между операторами s1 и s2 с соответствующими векторами итераций i1 и i2. Предполагается, что векторы i1 и i2 имеют одинаковую размерность, и соответствующие их элементы соответствуют одним и тем же циклам программы. Расстоянием или шагом зависимости назовем вектор d = i2 - i1.

В дальнейшем мы будем говорить о распараллеливании циклов программы. Поэтому значение приобретают зависимости между витками циклов. Такие зависимости возникают, если операторы s1 и s2 выполнялись на разных итерациях цикла, то есть d ? 0. Такая зависимость требует сохранения порядка выполнения итераций. Цикл, не содержащий зависимостей между витками, можно легко распараллелить, поскольку витки могут выполняться независимо в любом порядке.

2.2 Система автоматизации распараллеливания

Планируемая система автоматизации распараллеливания состоит из следующих составных частей:

инструментатор / преобразователь программы,

анализатор,

экспертные модули по распараллеливанию программы,

модуль-ассистент, позволяющий пользователю работать с системой.

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

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

2.3 Задача анализатора

Задача анализатора в рамках системы автоматизации распараллеливания состоит в получении из программы необходимой для распараллеливания информации. В данной работе не рассматриваются вопросы, связанные с распараллеливанием программ для распределенной памяти.

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

3. Динамический анализ

3.1 Схема работы динамического анализатора

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

Далее полученная программа поступает на вход стандартного компилятора и затем запускается на различных наборах входных данных. По полученной трассировочной информации анализатор определяет зависимости между операторами в исходной программе.

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

Далее рассматриваются два возможных алгоритма динамического анализа.

3.2 Динамический анализ с использованием дерева контекстов

Эта схема анализа описана в работе [4] и в несколько измененном виде приводится здесь.

Введем следующую терминологию.

Дерево контекстов (context tree) CV(p) программы p -- дерево, состоящее из вершин следующих типов: функция, цикл, оператор вызова функции или доступа к памяти, условный оператор, и другие типы операторов, присутствующие в языке. Между двумя вершинами есть ребро, если одна из них непосредственно вызывает другую. Корень дерева - функция main(), основное тело программы или другое аналогичное понятие из используемого языка программирования.

Контекст -- это путь от корня до любой вершины дерева контекстов.

Пусть вершина S(a) соответствует оператору доступа к памяти a. Контекст CV(a) оператора a -- путь от корня дерева контекстов к вершине S(a).

Контекст функции (цикла) -- путь от корня дерева контекстов к вершине, соответствующей этой функции (циклу).

Рассмотрим пример.

int A[10], B[10];

void main() {

for (int i=0; i<10; i++)/* f1 */

proc(i);/* st1 */

}

void proc(int i) {

for (int m=0; m<10; m++) {/* f2 */

if (i%2 == 0)/* if1 */

A[m] = ...;/* st2 */

else

... = A[m];/* st3 */

B[m] = ...;/* st4 */

}

}

В этом примере оператор st2 может иметь контекст C(a) = (main f1 st1 proc f2 if1 st2). В случае наличия рекурсивной функции rfunc контекст мог бы быть таким: C(a) = (… rfunc st1 rfunc st1 rfunc …).

Цепочка векторов итераций (iteration vector chain) IVC(a) -- это список номеров итераций для каждого узла-цикла контекста C(a). Если контекст не содержит циклов, то список не будет содержать ни одного элемента.

Цепочка векторов итераций относится к конкретному моменту выполнения программы, поэтому каждый оператор может иметь несколько разных IVC. Так, например, для оператора st2 может быть IVC(a) = (1, 4) или IVC(a) = (4, 1).

Виртуальная точка доступа a (virtual point) -- это пара VP(a) = (C(a), IVC(a)).

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

Алгоритм нахождения прямых зависимостей.

Для каждой операции чтения ar:

Определить ячейку памяти, читаемую ar.

Определить виртуальную точку VP(aw) последней записи aw в эту ячейку.

Найти контекст CL - длиннейший общий подпуть контекстов C(ar) и C(aw).

Найти контекст Cm - длиннейший контекст, являющийся подконтекстом контекста CL таким, что соответствующие цепочки IVC(ar) и IVC(aw) содержат одинаковые значения на отрезке, соответствующем контексту Cm.

Пусть r и w - векторы, образованные отрезками цепочек IVC(ar) и IVC(aw), не вошедшими в контекст Cm. Вычислить расстояние d = r - w, если dim(r)>0 и положить d=[] иначе.

Пусть f1 - самый «глубокий» цикл в контексте СL. Добавить зависимость между итерациями цикла f1 (и обрамляющих циклов) с расстоянием d.

Вместо п.6 можно записать зависимость между конкретными операторами в теле цикла. Пусть st1 и st2 - вершины C(ar) и C(aw), непосредственно следующие за CL. Добавить зависимость st1 от st2 с расстоянием d. Поскольку в данной работе рассматривается только распараллеливание циклов, в текущем анализаторе этого не делается.

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

3.3 Динамический анализ с использованием глобальных номеров итераций

Другой подход к динамическому анализу использует понятие глобальных номеров итераций (GIN - Global Iteration Number) [5]. Это означает, что все итерации всех циклов нумеруются по порядку. Например, в следующем примере

for (i=1; i<=3; i++)

for (j=1; j<=3; j++)

A[f1(i,j)]= ... A[f2(i,j)] ...;

глобальные номера итераций будут распределены следующим образом:

(1,-) 1	(1,1) 2	(1,2) 3	(1,3) 4
(2,-) 5	(2,1) 6	(2,2) 7	(2,3) 8
(3,-) 9	(3,1) 10	(3,2) 11	(3,3) 12

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

Данный метод используется для нахождения зависимостей между итерациями циклов. При входе в цикл запоминается GIN первой итерации. Кроме того, при входе в очередную итерацию цикла запоминается GIN текущей итерации, а GIN предыдущей итерации добавляется в специальный буфер, в котором записаны k последних итераций этого цикла (k - это емкость буфера). При вычислении расстояний для зависимостей этот буфер будет просматриваться в поисках подходящей итерации, поэтому метод позволяет определить расстояние, если оно не превосходит k, либо установить, что оно превышает k. Для каждой ячейки памяти запоминается GIN последней записи для отслеживания прямых зависимостей и зависимостей по выходу, а также предшествующих чтений, для того чтобы отслеживать также и обратные зависимости.

Рассмотрим случай, когда некоторая ячейка массива A записывается на итерации (2, 2), а затем читается на итерации (2, 3). К моменту чтения состояние выполнения программы будет таким:

Цикл	Начало цикла	Текущая итерация	Буфер
i	1	5	1
j	6	8	7,6

Запись в ячейку массива имела GIN = 7. Это было на той же итерации внешнего цикла. Просмотрев буфер цикла по j, можно вычислить расстояние между записью и чтением, равное 1.

Теперь пусть запись производилась на итерации (1,1), а чтение на итерации (3,3). Состояние программы в момент чтения:

Цикл	Начало цикла	Текущая итерация	Буфер
i	1	9	5,1
j	10	12	11,10

Запись в массив (GIN = 2) произошла не в текущем цикле (2 < 10), а в объемлющем цикле (1 <= 2 <= 9). Просматривая буфер цикла по i в поисках итерации с GIN <= 2, мы определяем расстояние, равное 2.

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

3.4 Преимущества и недостатки динамического анализа

По сравнению со статическим анализом динамический анализ обладает рядом преимуществ:

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

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

динамический анализ всегда дает полную картину зависимостей для данного конкретного запуска программы с данным конкретным набором входных данных. Если ход выполнения программы зависит только от входных данных (не используется, например, генератор случайных чисел), то динамический анализ дает полную картину зависимостей для любого запуска программы с этим набором данных.

динамический анализ никогда не укажет на зависимость операторов там, где ее на самом деле нет.

Основные недостатки динамического анализа также обусловлены необходимостью выполнения программы:

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

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

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

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

4. Практическая реализация

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

программу-инструментатор (реализована в рамках отдельной работы);

библиотеку, содержащую реализации функций анализатора.

Библиотека-анализатор была реализована на языке C++. Этот язык легко может быть использован совместно с языками Си и Фортран, которые широко используются для программирования вычислительных задач.

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

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

4.1 Инструментация

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

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

должны инструментироваться все доступы к данным с указанием ячейки и операции (чтение или запись),

должны инструментироваться входы и выходы подпрограмм, начало каждого цикла, его завершение, а также переход к новой итерации,

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

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

Разработка инструментатора ведется с использованием библиотеки Sage++, реализующей синтаксический разбор программ на языке Си. Эта библиотека вводит для каждого оператора программы уникальный идентификатор. Кроме того, Sage создает внутреннее представление программы, которое можно использовать при формировании ее измененных вариантов. Поэтому было принято решение использовать идентификаторы Sage также и в анализаторе. Также необходимо получать информацию о номерах строк исходной программы для обеспечения возможности удобного отображения результатов пользователю.

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

Учитывая вышесказанное, был получен следующий интерфейс библиотеки анализатора.

DA_init() - инициализация библиотеки анализа, необходимо вызывать до вызова любой другой функции.

DA_exit() - завершение анализа и сохранение результатов

DA_SagePos(long sageNumber) - сообщает анализатору о начале оператора с идентификатором sageNumber

DA_LinePos(long lineNumber, char * filename) - сообщает анализатору о текущем номере строки и файле.

DA_WriteBegin(void * addr, long size), DA_WriteEnd() - пара функций, отмечающие начало и завершение оператора присваивания - запись в ячейку памяти

DA_Read(void * addr, long size) - чтение ячейки памяти

DA_LoopDo(), DA_LoopFor(), DA_LoopWhile(), DA_LoopDowhile() - начало соответствующего цикла.

DA_LoopIter() - начало очередной итерации цикла

DA_LoopEnd() - завершение цикла

RegArrId(long id, void * addr, long rank, long size[], long elemsize, const char * name) - регистрация нединамического массива в анализаторе.

RegArr(void * addr, long rank, long size[], long elemsize, const char * name) - регистрация динамического массива.

DA_UnregArrId(long id), DA_UnregArr(void * addr) - соответствующие функции отмены регистрации массивов.

4.2 Формат результатов

В качестве результата анализатор предоставляет дерево контекстов с дополнительной информацией, размещенной в вершинах:

список зависимостей между витками каждого с векторами расстояний, группированные по переменным, обращения к которым создали эти зависимости,

список массивов, используемых оператором, а также, если элементы массива использовались линейным образом, то параметры соответствующей арифметической прогрессии

Также в узлах накапливается профилировочная информация, которая может быть полезной при принятии решений о распараллеливании:

количество выполнений поддерева с корнем в данном узле,

общее время выполнения поддерева с корнем в данном узле,

среднее, минимальное и максимально время однократного выполнения поддерева с корнем в данном узле.

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

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

Основу библиотеки работы с результатами составляет класс ContextNode, представляющий вершину дерева контекстов. В этом классе предусмотрены методы для:

добавления непосредственных потомков,

навигации по дереву контекстов: переход к родительской вершине, к потомкам, к следующей вершине на том же уровне,

получения и изменения идентификационной информации о вершине: Sage-номер, тип вершины, номер строки исходного файла программы,

получения и изменения информации о зависимостях по данным, сохраненных в данной вершине,

получения и изменения профилировочной информации,

сохранения информации в файл и загрузки информации из файла.

Для хранения зависимостей в библиотеке предусмотрены классы:

Dependence - класс, представляющий одну зависимость, содержащий вектор расстояния,

DependenceStore - класс, предназначенный для хранения всех зависимостей одного типа.

Информация о массивах, используемых в программе, представляется классами CArrays и CArrayData. Класс CArrayData содержит информацию об одном массиве:

имя массива, номер строки, в котором он был определен,

Sage-номер или внутренний идентификатор массива для динамических массивов,

число измерений массива и размеры каждого измерения,

размер одного элемента массива.

При сохранении в файл данные записываются в формате XML. Удобство данного формата состоит в том, что он имеет древовидную структуру и, кроме того, является текстовым форматом, а потому может быть непосредственно прочитан человеком. Следует также отметить, что существуют простые и удобные библиотеки для работы с XML.

Конкретное представление дерева контекстов в виде XML несущественно. Предполагается, что все модули, требующие для работы результаты анализа, будут использовать предназначенную для этого библиотеку.

4.3 Внутреннее устройство анализатора

Внутренняя структура анализатора показана на Рисунке 2.

Ядро является основной частью динамического анализатора. Фактически, ядро - это реализация алгоритмов, описанных в разделе 3.2, использующая блок внешнего интерфейса для получения информации о ходе выполнения программы, а остальные блоки как структуры данных для хранения информации.

Рисунок 2 Внутренняя структура анализатора

Ядро анализатора использует внутренний интерфейс, основные операции которого соответствуют операциям интерфейса анализатора, описанным в разделе 4.1. Имеются, тем не менее, незначительные отличия, обусловленные соображениями удобства и простоты. Блок внешнего интерфейса необходим для преобразования вызовов функций анализа в вызовы интерфейса ядра. Исторически такое преобразование было необходимо в связи с тем, что первая версия анализатора была реализована на основе интерфейса отладчика системы DVM [6]. Этот отладчик предназначен для проверки корректности DVM-программы посредством моделирования ее параллельного выполнения, а также посредством накопления и сравнения трасс при ее последовательном и параллельном выполнении. В его интерфейс входят базовые функции, необходимые динамическому анализатору: чтение и запись значений переменных, начало и завершение циклов, начало итераций циклов. Поэтому до появления специального инструментатора было возможно использовать инструментатор, предназначенный для отладчика DVM. В данный момент наличие блока внешнего интерфейса позволяет при необходимости изменять интерфейс анализатора, не затрагивая основную часть библиотеки.

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

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

4.4 Результаты тестирования

Тестирование анализатора проводилось на программах, реализующих решение уравнения Пуассона в трехмерном пространстве классическими итерационными методами: методом Якоби, методом последовательной верхней релаксации (SOR), методом красно-черного упорядочения (RedBlack), а также на программе, реализующей решение системы линейный алгебраических уравнений методом Гаусса.

Основные показатели производительности показаны на Таблице 1. В методах Якоби, SOR и RedBlack использовалась матрица размера 16x16x8. В методе Гаусса решалась система размера 100x100.

Таблица 1 - Показатели производительности

Метод	Время выполнения, сек	Используемая память, Kb
	без анализатора	с анализатором	без анализатора	с анализатором
Якоби	0,05	4,73	924	58136
SOR	0,05	2,23	908	25096
RedBlack	0,05	5,52	908	65752
Гаусс	0,04	6,45	980	51756

Из приведенных результатов следует, что текущая реализация динамического анализатора замедляет работу программы в 100 и более раз, используя при этом в десятки раз больший объем памяти. Это ограничивает возможности применения анализатора, поскольку для того, чтобы время анализа оставалось в разумных пределах, необходимо сильно уменьшать размерность решаемой задачи.

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

5. Заключение

Подведем некоторые итоги данной работы. Динамический анализ зависимостей по данным обладает рядом преимуществ по сравнению с традиционными статическими методами анализа. Поскольку анализ производится во время выполнения программы, доступна вся информация о производимых доступах в память. Это позволяет получить абсолютно точную информацию о зависимостях по данным независимо от сложности индексных выражений массивов, наличия косвенной индексации или указателей.

Основным недостатком данного метода является отсутствие гарантии того, что все возможные зависимости по данным обнаружены. Это означает, что для проведения анализа необходимо наличие набора тестов, достаточно полно покрывающего различные варианты поведения программы. Кроме того, существенные затраты ресурсов анализатором при каждом запуске программы на выполнение заставляют уменьшать размерность задач для анализа, что, быть может, не всегда возможно.

В рамках данной работы один из методов динамического анализа был реализован в виде библиотеки на языке С++ (около 2500 строк исходного кода). Проведено тестирование анализатора на наборе программ на языке Си, представляющих собой реализации классических итерационных методов (Якоби, SOR, RedBlack) и метода Гаусса. Тем самым показана возможность применения динамического анализа для поиска зависимостей в программах, требующих распараллеливания.

6. Литература

1. ParaWise. The Computer Aided Parallelization Toolkit [HTML, PDF] (http://www.parallelsp.com).

2. Проект V-Ray [HTML] (http://parallel.ru/v-ray).

3. Jacobson T., Stubbendieck G. Dependency Analysis of FOR-Loop Structures for Automatic Parallelization of C Code [PDF] (http://www.css.edu/depts/cis/mics_2003/MICS2003_Papers/Jacobson.PDF).

4. Karkowski I., Corporaal H. Overcoming the Limitations of the Traditional Loop Parallelization // Journal of Future Generation Computer Systems. 1998. № 13. P. 407-416.

5. Petersen P.M. Evaluation of Programs and Parallelizing Compilers Using Dynamic Analysis Techniques. Champaign, IL, USA: University of Illinois at Urbana-Champaign, 1993. 164 p.

6. DVM-система [HTML] (http://www.keldysh.ru/dvm).