Мы имеем d тесно вложенных циклов. Для оператора Sv, содержащегося в теле этих циклов, вектором итераций I назовем номера итераций объемлющих циклов I = (I1 ,…,Id). Далее, пусть есть зависимость по данным между операторами Sv и Sw с векторами итераций I'и I''. Предполагается, что векторы I'и I'' имеют одинаковую размерность, и их соответствующие элементы относятся к одним и тем же циклам программы. Шагом зависимости назовем вектор D = I'- I''. Тогда, между витками цикла существует зависимость по данным, если операторы Sv и Sw выполняются на разных итерациях цикла, то есть D ≠ 0 [2].
Зависимость по данным между двумя операторами требует сохранения их порядка следования в программе. Следовательно, если найдена зависимость по данным между итерациями цикла, то все его итерации должны выполниться последовательно, а это значит, что цикл распараллеливанию не подлежит. Иначе обстоит дело с циклами, между итерациями которых зависимостей не обнаружено, витки таких циклов могут одновременно выполняться на разных процессорах, что позволит увеличить эффективность выполнения программы на многопроцессорных ЭВМ.
В системе автоматизированного распараллеливания последовательных программ за обнаружение зависимостей по данным между операторами или витками циклов отвечают анализаторы.
3 Обзор
В рамках обзора рассмотрим принципы организации статического и динамического анализа последовательных программ, достоинства и недостатки этих методов, а также пример организации гибридного анализа.
Статические методы анализа основаны на исследовании исходного текста программы с целью обнаружения в программе зависимостей по данным.
Для скалярных переменных зависимости по данным вычисляются просто, ведь мы точно знаем ячейку памяти, к которой происходит обращение. Большую сложность представляет анализ обращений к элементам массива внутри цикла, если индексные выражения этого массива включают переменные объемлющего цикла. Рассмотрим следующую ситуацию(Рисунок 4):
Мы имеем d тесно вложенных циклов, n-мерный массив X и две функции f и g из Zd в Z, где Z – множество всех целых чисел.
Для определения наличия зависимости между операторами Sv и Swпо переменной X, необходимо найти решение следующей системы уравнений:
1. для оператора Sv вектор итераций Ī' = (I'1, I'2,…,I'd)
2. для оператора Sw вектор итераций Ī" = (I"1, I"2,…,I"d)
3. Ī' ≤ Ī"
4. fi(Ī') = gi(Ī") для всех (1 <= i <= n) и для определенных I'1, I'2,…,I'd, I"1, I"2,…,I"d, таких что Li<=I'i<=Ui и Li<=I''i<=Ui.
Если решения системы нет, то зависимость между операторами Sv и Swпо переменной X отсутствует. Если решить систему уравнений невозможно, то статический анализ не может точно доказать наличие или отсутствие зависимости между операторами и фиксирует возможную зависимость. Это предположение гарантирует генерацию корректной параллельной программы, но связано с потерей эффективности из-за недостаточного использования параллелизма, в случае, если реальной зависимости в программе нет.
3.2 Недостатки и преимущества статического анализа
По своей природе статический анализ обладает рядом ограничений, способных воспрепятствовать обнаружению параллелизма в программе:
1. Статический анализатор работает только с текстом исходной программы и не имеет никакой информации о значения переменных. Следовательно, затруднена работа со входными данными и данными, полученными из окружения программы в ходе ее выполнения.
2. Зачастую, статические методы анализа могут обрабатывать только линейные относительно переменных цикла индексные выражения, следовательно, возникают проблемы с косвенной индексацией, сложными выражениями и вызовами функций в индексах массивов.
Но наряду с существенными недостатками в статическом методе анализа присутствует важная положительная особенность:
1. Безопасность анализа. Если в результате статического анализа программы было выяснено отсутствие зависимостей по данным между операторами, то такой зависимости действительно нет.
3.3 Динамический анализ. Принципы организации
Идея динамического анализа заключается в определении зависимостей по данным в программе на основании информации, собранной в результате ее выполнения на тестовых наборах начальных данных [6]. Схематически это выглядит так (Рисунок 5):
1. В исходный текст программы вставляются вызовы трассировочных функций, позволяющих анализатору получать информацию о ходе выполнения программы. Обычно трассировочные вызовы сопровождают обращения к переменным, входы и выходы циклов, изменения индексных переменных в циклах, вызовы функций и процедур
2. Полученная программа подается на вход стандартному компилятору
3. Исполняемый модуль запускается на различных наборах входных данных. По полученной трассировочной информации анализатор определяет зависимости по данным в исходной программе.
Динамический анализ дает полную картину зависимостей по данным, но только для текущего конкретного запуска программы. Поэтому очень важно, чтобы тестовый набор входных данных полностью охватывал все возможное поведение программы.
Рассмотрим организацию динамического анализа зависимостей по данным с использованием дерева контекстов [6].
Введем ряд определений:
Определение 1: Контекстное дерево CT(program) программы program – дерево с тремя типами вершин: процедура, цикл или доступ к памяти. Две вершины контекстного дерева связаны ребром, если они непосредственно вложены друг в друга или если одна из этих вершин вызывает другую. Корень контекстного дерева – процедура, с которой начинает свое выполнение программа. Сложные программные выражения делятся на ряд контекстных вершин, по одной на каждое обращение к памяти.
Определение 2: Контекстом CT(program) назовем путь от корня дерева контекстов до любой его вершины. Пусть S(a) – контекстная вершина обращения к переменной ‘a’. Тогда, контекст C(a) обращения к ‘a’ – это путь от корня дерева контекстов до вершины S(a). Контекст процедуры(цикла) – контекст, заканчивающийся соответствующей этой процедуре(циклу) вершиной. Процедурная секция – наибольший подпуть контекста C, содержащий единственную процедурную вершину, с которой он и начинается.
Определение 3: Цепочка векторов итерации IVC(a) доступа к памяти «a» - список векторов итераций, соответствующих всем процедурным секциям в контексте C(a) на момент доступа ‘a’. Если процедурная секция не содержит ни одного цикла, то вектор итераций будет пустым вектором.
Определение 4
Виртуальная точка доступа к памяти «a» - пара VP(a) = (C(a), IVC(a)).
Для определения прямых зависимостей по памяти в программе используется следующий алгоритм:
Для каждой ячейки памяти мы храним виртуальные точки последнего чтения и последней записи. Тогда, при каждом доступе к ячейке памяти на чтение ar производим следующие действия:
1. определяем ячейку памяти m, к которой происходит доступ ar;
2. получаем виртуальную точку VP(aw) последней записи aw в ячейку памяти m;
3. получаем по точкам доступа VP(aw) и VP(ar) значения цепочек векторов итераций IVC(aw) и IVC(ar);
4. определяем контекст CL, являющийся наибольшим общим подпутём контекстов C(aw) и C(ar) в дереве контекстов CT(p);
5. находим контекст Cm, являющийся наибольшим процедурным подконтекстом или подконтекстом цикла контекста CL, такой, что все его процедурные секции, кроме последней, имеют одинаковые значения векторов итераций в IVC(aw) и IVC(ar);
6. получаем по значениям цепочек IVC(aw) и IVC(ar) вектора итераций w и r последней процедурной секции контекста Cm; если размерность вектора r больше нуля, то определяем расстояние зависимости d: d = r – w, в противном случае полагаем d пустым вектором;
7. пусть вершина st1 следует сразу после подконтекста Cmв контексте C(aw), а вершина st2 следует сразу после подконтекста Cmв контексте C(ar), тогда добавим новую зависимость с расстоянием d между операторами st1 и st2.
Похожие алгоритмы можно применять для определения обратных зависимостей и зависимостей по записи. Для регистрации обратных зависимостей мы должны для всех операций записи анализировать предшествующие операции чтения. Для регистрации зависимостей по записи необходимо для каждой записи в ячейку памяти анализировать предыдущую запись в эту же ячейку.
3.4 Недостатки и преимущества динамического анализа
Динамический метод анализа зависимостей по данным обладает рядом преимуществ над статическим:
1. При динамическом анализе обращения к переменным определяются по доступам к соответствующим ячейкам памяти. Это позволяет преодолеть трудности статического анализа, связанные с обработкой входных данных или данных, полученных в результате выполнения программы.
2. При динамическом анализе работа с выражениями не представляет трудностей, они просто вычисляются. Это решает проблемы с косвенной индексацией и вызовами функций внутри индексных выражений.
3. Динамический анализ всегда дает полную картину зависимостей для данного конкретного запуска программы.