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