Аннотация
Анализ зависимостей по данным является важнейшим этапомпри распараллеливании программ. Данная работа посвящена методам динамическогоанализа зависимостей. Рассматриваются два метода динамического анализа, а такжепрактическая реализация одного из них. Полученный динамический анализатор можетстать в будущем частью системы автоматизации распараллеливания программ.
Оглавление
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
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
proc(i);/* st1 */
}
void proc(int i) {
for (int m=0; m
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
for (j=1; 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
В сущности, данный метод позволяет делать то же самое,что и предыдущий, но только на уровне целых итераций циклов, а не отдельныхоператоров и использует при этом другие технические решения. Помимо этого,предыдущий метод вводит удобное понятие дерева контекстов, которое может бытьиспользовано также и для иных целей кроме динамического анализа. Поэтому врамках данной работы реализовывался метод дерева контекстов.
/>/>
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[], longelemsize, 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 Structuresfor Automatic Parallelization of C Code [PDF](http://www.css.edu/depts/cis/mics_2003/MICS2003_Papers/Jacobson.PDF).
4. Karkowski I.,/> Corporaal H. Overcoming theLimitations of the Traditional Loop Parallelization // Journal of FutureGeneration Computer Systems. 1998. № 13. P. 407-416.
/>5. Petersen P.M. Evaluation of Programs and Parallelizing Compilers UsingDynamic Analysis Techniques. Champaign, IL, USA: University of Illinois atUrbana-Champaign, 1993. 164 p.
/>6. DVM-система [HTML] (http://www.keldysh.ru/dvm).