Основы распараллеливания программ, их динамический анализ (стр. 2 из 5)
В языках, подобных Си, у статических методов появляется еще одна проблема: интенсивное использование указателей. Как правило, статические методы анализа не могут работать с указателями, равно как и с весьма сложными выражениями, являющимися в языке нормой. Можно обязать программиста писать программы без использования соответствующих конструкций языка, но такие ограничения не применимы при распараллеливании библиотек, оптимизированных для выполнения на однопроцессорной машине.
Таким образом, статические методы анализа работают только с текстом программы и из-за этого имеют ряд ограничений, способных воспрепятствовать обнаружению параллелизма в программе. Тем не менее, этот тип методов анализа широко применяется в существующих системах автоматизации распараллеливания.
1.4 Динамический анализ
Динамический анализ программ основан на вставке в исходную программу дополнительных операторов, проводящих анализ. Полученная программа выполняется на некотором тестовом наборе входных данных (или нескольких наборах), и во время выполнения собирается информация о фактических зависимостях, присутствующих в программе на данном конкретном наборе данных.
Такой подход позволяет производить выявление зависимостей во многих ситуациях, когда статический анализ невозможен. Поскольку анализ происходит во время выполнения программы, анализатору доступны значения всех переменных, присутствующих в программе. Поэтому появляется возможность проанализировать любые ссылки на элементы массивов: через индексные выражения любой сложности, включая вызовы функций, через указатели. Динамический анализатор всегда может однозначно установить ячейку памяти, которая используется в любом операторе программы.
Недостатки динамического анализа также следуют из того, что он производится во время выполнения. Динамический анализ показывает только те зависимости, которые возникают на данном конкретном запуске программы. Поэтому, используя динамический анализ, никогда нельзя быть уверенным, что найдены все зависимости в программе. Некоторые зависимости могут не проявиться на тестовых данных. Это может привести к генерации некорректной параллельной программы. Поэтому важной задачей становится составление хорошего набора тестов, достаточно полно покрывающего возможные поведения программы.
1.5 Распараллеливание во время выполнения
В некоторых случаях невозможно заранее сказать, будет ли некоторый цикл в программе параллельным (например, это зависит от входных данных). Как правило, в такой ситуации распараллеливание считается невозможным. Но иногда удается сформулировать достаточно простое условие, при котором вероятные зависимости по данным исчезают. Тогда применяется следующее решение: в параллельную программу включается два варианта данного фрагмента программы: один параллельный, другой последовательный. Во время выполнения программы проверяется выполнение условия, и в зависимости от результата выполняется либо один фрагмент, либо другой.
Аналогично работает схема inspector-executor. Спорный цикл выполняется 2 раза. Первый раз – для выяснения, является ли цикл параллельным. При этом никаких вычислений не производится. Второй раз – уже реальное выполнение вычислений с учетом результата первого прохода. Дополнительный плюс такой схемы состоит в том, что, когда один и тот же цикл выполняется много раз, а его основные параметры остаются одними и теми же, инспекционный проход можно делать только один раз, используя полученный результат при каждом новом выполнении цикла.
Таким образом, вынесение некоторых проверок с этапа анализа на этап выполнения программы позволяет смягчить ограничения методов, рассмотренных выше.
1.6 Цель работы
Данная работа посвящена методам динамического анализа. Ставится цель создать рабочую реализацию динамического анализатора – библиотеки, собирающей информацию о зависимостях по данным в исходной программе. В будущем этот анализатор может стать частью системы автоматизации распараллеливания программ для систем с общей памятью.
2. Постановка задачи
Зависимость по данным образуют любые два оператора программы, обращающиеся к одной ячейке памяти, если хотя бы один из них производит запись в эту ячейку [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.1 Схема работы динамического анализатора
Общая схема работы динамического анализатора показана на Рисунке 1. На первом этапе в исходный текст программы вставляются вызовы трассировочных функций, позволяющих анализатору получать информацию о ходе выполнения программы. Набор трассировочных функций может меняться в зависимости от целей и используемого алгоритма анализа. Но как минимум трассировочные вызовы вставляются на все доступы к памяти, входы и выходы циклов, изменения индексных переменных в циклах.
Далее полученная программа поступает на вход стандартного компилятора и затем запускается на различных наборах входных данных. По полученной трассировочной информации анализатор определяет зависимости между операторами в исходной программе.
Возможен вариант, когда инструментируется не вся программа, а некоторый фрагмент. В этом случае в качестве результатов будут получены только зависимости между операторами, попавшими в инструментированную часть программы. Это может быть полезно, если динамический анализ используется для уточнения результатов, полученных, например, с помощью статического анализатора.