Навигация
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. На первом этапе в исходный текст программы вставляются вызовы трассировочных функций, позволяющих анализатору получать информацию о ходе выполнения программы. Набор трассировочных функций может меняться в зависимости от целей и используемого алгоритма анализа. Но как минимум трассировочные вызовы вставляются на все доступы к памяти, входы и выходы циклов, изменения индексных переменных в циклах.
Далее полученная программа поступает на вход стандартного компилятора и затем запускается на различных наборах входных данных. По полученной трассировочной информации анализатор определяет зависимости между операторами в исходной программе.
Возможен вариант, когда инструментируется не вся программа, а некоторый фрагмент. В этом случае в качестве результатов будут получены только зависимости между операторами, попавшими в инструментированную часть программы. Это может быть полезно, если динамический анализ используется для уточнения результатов, полученных, например, с помощью статического анализатора.
Далее рассматриваются два возможных алгоритма динамического анализа.
Похожие работы
... для хранения директив FortranDVM, формирование которых осуществляет блок распределения вычислений и данных, и методы для их вставки, а также реализован экспорт этих комментариев в файл. 3.3 Алгоритмы Реализованные в дипломной работе классы блока статического построения расширенного графа управления программы и вспомогательных структур данных содержат большое число членов-методов, решающих ...
... из-за динамической подзагрузки программы из файловой системы) и отлаживать его производительность по той же методике, которая была описана выше применительно к программе целиком. 5. Средство анализа эффективности MPI программ 5.1 Постановка задачи В системе DVM существуют развитые средства анализа эффективности выполнения параллельной DVM-программы. Эти средства являются более мощными, ...
... лишь контекстным анализом. Как было отмечено в [12], применение глубокого статического анализа программ может позволить существенно снизить количество ложных срабатываний и повысить точность обнаружения уязвимостей защиты. 4.3. Использование методов анализа потоков данных для решения задачи обнаружения уязвимостей В отделе компиляторных технологий по контракту с фирмой Nortel Networks ...
... практичных алгоритмов оптимизированного перебора, позволяющих за разумное время осуществлять распараллеливание достаточно больших участков. Анализ работ, посвященных оптимизации кода для процессоров с параллелизмом на уровне команд показывает, что для достижения наилучших результатов необходимо применение комплекса оптимизаций, среди которых можно выделить следующие классы. Преобразования циклов ...
0 комментариев