Аннотация

Анализ последовательных программ на наличие зависимостей по данным играет важную роль для их последующего эффективного распараллеливания. Методика анализа отличается по своей природе: она может быть статической или динамической, причем каждая имеет свои достоинства и недостатки. Данная дипломная работа посвящена исследованию комбинации использования статической и динамической методики анализа - гибридного анализа последовательных программ. Изучены достоинства и недостатки статического и динамического анализа, их принципы организации. Разработан и практически реализован алгоритм гибридного анализа. Полученные программные реализации могут стать в будущем частью системы автоматизации распараллеливания САПФОР.



1 Введение

Интенсивное развитие вычислительной техники обусловлено в первую очередь необходимостью решения исследовательских задач в области фундаментальных наук. Причем всегда существует ряд крупномасштабных задач, решение которых просто невозможно силами однопроцессорной ЭВМ. Это связано с огромным числом вычислений, влекущих за собой совершенно неприемлемые временные затраты. Именно поэтому очень важным в подобной ситуации является использование многопроцессорных систем, позволяющих разделить решение одной задачи между разными процессорами таким образом, чтобы отдельные части вычислений могли выполняться одновременно на разных процессорах.

Для решения задач на многопроцессорных ЭВМ необходимо писать специальные параллельные программы, которые достаточно сильно отличаются от последовательных. Написание таких программ сопряжено с преодолением ряда трудностей. Первые возникают уже на этапе создания параллельного алгоритма решения задачи и связаны со сложностью восприятия человеком одновременного выполнения действий. Далее, отладка параллельных программ требует гораздо больше усилий от программиста, чем отладка последовательных программ. Это объясняется как недетерминизмом выполнения параллельных программ, так и сложностью понимания параллельных алгоритмов. Кроме того, параллельная программа должна быть эффективной. То есть, параллельная программа, реализующая решение некоторой задачи, должна выполняться на нескольких вычислительных узлах быстрее, чем последовательная программа для той же задачи выполняется на одном, в противном случае пропадает смысл использования многопроцессорной ЭВМ. На практике, для достижения требуемой эффективности, приходится многократно проходить путь от спецификации алгоритма до его реализации на языке параллельного программирования. И наконец, за долгие годы математики и физики накопили обширные библиотеки последовательных программ решения многих научных задач. Если во время написания параллельной программы потребуются элементы этих библиотек, то придется их реализовывать. Создать параллельные версии всех библиотек для многопроцессорных ЭВМ в настоящее время не представляется возможным из-за сложности параллельного программирования.

Одним из способов решения указанных выше проблем может стать использование системы автоматизации распараллеливания последовательных программ. С ее помощью существенно упростится процесс алгоритмизации поставленной задачи и сократится время, затраченное на ее программирование. Примером такой системы является САПФОР (Система Автоматизированной Параллелизации ФОРтран программ), разрабатываемая в Институте Прикладной математики им. М.В.Келдыша РАН [1].



1.1 САПФОР

САПФОР состоит из пяти отдельных взаимодействующих между собой компонент:

1. Диалоговая оболочка (пользовательский интерфейс).

2. Анализатор

3. Эксперт

4. Генератор

5. База данных (БД)

Диалоговая оболочка принимает команды от пользователя и визуализирует процесс и результаты распараллеливания. Она позволяет пользователю вводить дополнительную информацию о программе (например, описание задачи) и запускать генератор для получения текста программы на языке параллельного программирования, указанном в выбранной схеме распараллеливания.

Анализатор строит внутреннее представление программы, анализирует возможности распараллеливания отдельных её частей и помещает полученную информацию в БД системы.

Эксперт извлекает внутреннее представление программы из БД, находит возможные схемы распараллеливания программы (набор правил преобразования последовательной задачи в параллельную), оценивает их эффективность и с помощью пользователя выбирает оптимальный вариант распараллеливания. Построенные схемы распараллеливания для каждого выбранного пользователем описания задачи и описания ЭВМ записываются в БД.

Генератор по выбранным схемам распараллеливания строит тексты параллельных программ.

База данных хранит всю необходимую информацию для всех компонент системы, тем самым, обеспечивая их взаимодействие. Там хранится внутреннее представление программы, хранятся указания анализатору, указания по распараллеливанию, схемы распараллеливания и оценки их эффективности, описания задач, описания ЭВМ, конфигурации ЭВМ. Для каждой программы пользователя предусмотрена отдельная БД.

Схематически работу системы САПФОР можно представить следующим образом (Рисунок 1):

1. Пользователь подает свою последовательную программу на вход анализатору, и на выходе формируется БД.

2. Далее в работу вступает эксперт. Исходя из информации, хранящейся в БД, эксперт находит схемы распараллеливания, и для лучших схем выдает пользователю информацию, отражающую времена, полученные при прогнозировании параллельного выполнения программы.

3. Пользователь запускает генерацию текста параллельной программы для интересующей его схемы распараллеливания.

Рисунок 1

В системе САПФОР допускается использование нескольких анализаторов. Первый формирует БД, а все последующие дополняют ее более точными результатами анализа.

1.2 Цель работы

Данная работа посвящена второму компоненту системы САПФОР - анализатору последовательной программы. Анализатор может использовать один из двух методов анализа:

1. статический - анализ текста программы.

2. динамический - анализ выполнения исполняемого модуля программы на определенных входных данных.

У каждого метода свои достоинства и недостатки, а получаемая применением этих методов информация о сложностях распараллеливания программы может заметно отличаться. Выходит, было бы неплохо объединить результат работы статического и динамического анализатора для получения более эффективных схем распараллеливания.

Итак, цель работы - разработать принципы объединения работы двух анализаторов и реализовать гибридный анализ программы для получения информации, необходимой для формирования БД системы автоматизации распараллеливания последовательных программ САПФОР. Под гибридным анализом понимается комбинация статического и динамического анализа.



2 Постановка задачи

Задача данной дипломной работы заключается в разработке алгоритма гибридного анализа зависимостей по данным для последовательных программ и его реализации. Гибридный анализ должен объединить результаты работы динамического и статического анализаторов системы САПФОР и на выходе получить базу данных САПФОР. В качестве статического анализатора берется штатный анализатор системы САПФОР, за основу динамического анализатора берется библиотека функций динамического анализа, реализованная Остапенко Г.Ю. в рамках дипломной работы в 2008 году

Данная задача включает решение следующих подзадач:

1. Разработать алгоритм частичного динамического анализа последовательной программы и реализовать его на базе уже существующей библиотеки функций динамического анализа. Под частичным анализом понимается анализ зависимостей по интересующим нас переменным между итерациями интересующих нас циклов.

2. Разработать и реализовать алгоритм корректировки информации одной базы данных САПФОР полезной информацией из другой.

2.1 Зависимость по данным

Между двумя операторами программы возникает зависимость по данным, когда в этих операторах происходит обращение к одной и той же ячейке памяти, причем хотя бы в одном из этих операторов осуществляет запись в данную ячейку [2]. Другими словами, между двумя операторами программы возникает зависимость по данным, если от порядка следования этих операторов зависит результат их работы в программе.

Для примера рассмотрим два оператора S₁ и S₂, работающих со скалярными переменными или элементами массивов, причем оператор S₁ непосредственно следует за оператором S₂. Тогда возможны следующие пять случаев:

1. в первом случае операторы S₁ и S₂ не имеют общих переменных или элементов массивов. Следовательно, зависимостей по данным между операторами нет.

2. во втором случае оба оператора S₁ и S₂ считывают значение A. При этом запись в A не осуществляется, следовательно, зависимостей по данным между операторами также нет.

3. в третьем случае оператор S₁ записывает значение в A, а S₂ считывает А. Говорят, что между операторами S₁ и S₂ существует прямая зависимость по A.

4. в четвертом случае оператор S₁ считывает значение из A, а S₂ записывает в A. Говорят, что между операторами S₁ и S₂ существует обратная зависимость по A.

5. в пятом случае оба оператора S₁ и S₂ записывают значения в A. Говорят, что между S₁ и S₂ существует зависимость по выходу по A.

Теперь рассмотрим следующую ситуацию (Рисунок 3)



Мы имеем d тесно вложенных циклов. Для оператора S_v, содержащегося в теле этих циклов, вектором итераций I назовем номера итераций объемлющих циклов I = (I₁ ,…,I_d). Далее, пусть есть зависимость по данным между операторами S_v и S_w с векторами итераций I' и I''. Предполагается, что векторы I' и I'' имеют одинаковую размерность, и их соответствующие элементы относятся к одним и тем же циклам программы. Шагом зависимости назовем вектор D = I' - I''. Тогда, между витками цикла существует зависимость по данным, если операторы S_v и S_w выполняются на разных итерациях цикла, то есть D ? 0 [2].

Зависимость по данным между двумя операторами требует сохранения их порядка следования в программе. Следовательно, если найдена зависимость по данным между итерациями цикла, то все его итерации должны выполниться последовательно, а это значит, что цикл распараллеливанию не подлежит. Иначе обстоит дело с циклами, между итерациями которых зависимостей не обнаружено, витки таких циклов могут одновременно выполняться на разных процессорах, что позволит увеличить эффективность выполнения программы на многопроцессорных ЭВМ.

В системе автоматизированного распараллеливания последовательных программ за обнаружение зависимостей по данным между операторами или витками циклов отвечают анализаторы.



3 Обзор

В рамках обзора рассмотрим принципы организации статического и динамического анализа последовательных программ, достоинства и недостатки этих методов, а также пример организации гибридного анализа.

3.1 Статический анализ. Принципы организации

Статические методы анализа основаны на исследовании исходного текста программы с целью обнаружения в программе зависимостей по данным.

Для скалярных переменных зависимости по данным вычисляются просто, ведь мы точно знаем ячейку памяти, к которой происходит обращение. Большую сложность представляет анализ обращений к элементам массива внутри цикла, если индексные выражения этого массива включают переменные объемлющего цикла. Рассмотрим следующую ситуацию (Рисунок 4):

Мы имеем d тесно вложенных циклов, n-мерный массив X и две функции f и g из Z^d в Z, где Z - множество всех целых чисел.

Для определения наличия зависимости между операторами S_v и S_w по переменной X, необходимо найти решение следующей системы уравнений:

1. для оператора S_v вектор итераций I' = (I'₁, I'₂,…,I'_d)

2. для оператора S_w вектор итераций I" = (I"₁, I"₂,…,I"_d)

3. I' ? I"

4. f_i(I') = g_i(I") для всех (1 <= i <= n) и для определенных I'₁, I'₂,…,I'_d, I"₁, I"₂,…,I"_d, таких что L_i<=I'_i<=U_i и L_i<=I''_i<=U_i.

Если решения системы нет, то зависимость между операторами S_v и S_w по переменной 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)).

Для определения прямых зависимостей по памяти в программе используется следующий алгоритм:

Для каждой ячейки памяти мы храним виртуальные точки последнего чтения и последней записи. Тогда, при каждом доступе к ячейке памяти на чтение a_r производим следующие действия:

1. определяем ячейку памяти m, к которой происходит доступ a_r;

2. получаем виртуальную точку VP(a_w) последней записи a_w в ячейку памяти m;

3. получаем по точкам доступа VP(a_w) и VP(a_r) значения цепочек векторов итераций IVC(a_w) и IVC(a_r);

4. определяем контекст C_L, являющийся наибольшим общим подпутём контекстов C(a_w) и C(a_r) в дереве контекстов CT(p);

5. находим контекст C_m, являющийся наибольшим процедурным подконтекстом или подконтекстом цикла контекста C_L, такой, что все его процедурные секции, кроме последней, имеют одинаковые значения векторов итераций в IVC(a_w) и IVC(a_r);

6. получаем по значениям цепочек IVC(a_w) и IVC(a_r) вектора итераций w и r последней процедурной секции контекста C_m; если размерность вектора r больше нуля, то определяем расстояние зависимости d: d = r - w, в противном случае полагаем d пустым вектором;

7. пусть вершина st₁ следует сразу после подконтекста C_m в контексте C(a_w), а вершина st₂ следует сразу после подконтекста C_m в контексте C(a_r), тогда добавим новую зависимость с расстоянием d между операторами st₁ и st₂.



Похожие алгоритмы можно применять для определения обратных зависимостей и зависимостей по записи. Для регистрации обратных зависимостей мы должны для всех операций записи анализировать предшествующие операции чтения. Для регистрации зависимостей по записи необходимо для каждой записи в ячейку памяти анализировать предыдущую запись в эту же ячейку.

3.4 Недостатки и преимущества динамического анализа

Динамический метод анализа зависимостей по данным обладает рядом преимуществ над статическим:

1. При динамическом анализе обращения к переменным определяются по доступам к соответствующим ячейкам памяти. Это позволяет преодолеть трудности статического анализа, связанные с обработкой входных данных или данных, полученных в результате выполнения программы.

2. При динамическом анализе работа с выражениями не представляет трудностей, они просто вычисляются. Это решает проблемы с косвенной индексацией и вызовами функций внутри индексных выражений.

3. Динамический анализ всегда дает полную картину зависимостей для данного конкретного запуска программы.

4. Динамический анализ никогда не укажет на зависимость по данным там, где ее на самом деле нет.

Но наряду со всеми достоинствами в динамическом методе анализа имеют место несколько существенных недостатков [2]:

1. Динамический анализ показывает только те зависимости, которые возникают на данном конкретном запуске программы. При выполнении программы на других входных данных зависимости могут измениться. Нужно очень точно подбирать покрытие тестов.

2. Время работы. Нам необходимо запустить программу на каждом тесте, а их может быть довольно много.

3.5 Гибридный анализ. Принцип организации

Гибридный анализ - комбинация использования статического и динамического метода анализа зависимостей по данным с целью получения наиболее полной информации для эффективного распараллеливания программы.

В результате работы статического анализатора мы получаем два вида информации:

1. Информация о наличии зависимостей по данным

2. Информация о предполагаемых зависимостях по данным

Если анализатор не может точно определить есть или нет зависимости при данном доступе к памяти, то он предполагает наличие зависимости. Неясность возникает из-за несовершенной природы статического анализа, ведь он работает только с текстом программы и не знает ничего о значениях переменных, следовательно, возникают проблемы с обработкой входных параметров и вводимых из окружения данных, с косвенной индексацией и сложными выражениями.

Динамический анализ полностью лишен проблем статического анализа. Обращения к переменным определяются по доступам к соответствующим ячейкам памяти, а сложные выражения просто вычисляются. Кроме того, существует возможность инструментации трассировочными функциями (функциями, собирающими информацию о ходе выполнения программы для дальнейшего анализа на поиск зависимостей по данным) не всей программы, а определенных ее фрагментов. В этом случае в качестве результатов будут получены только зависимости по данным между операторами, попавшими в инструментированную часть программы.

Таким образом, динамический анализ может использоваться для уточнения результатов, полученных с помощью статического анализатора. Причем, при частичной инструментации время работы динамического анализа значительно ускорится.

Отсюда, получаем алгоритм гибридного анализа зависимостей по данным:

1. Запускаем статический анализ текста программы, в результате получаем точную информацию о зависимостях по данным и информацию о предполагаемых зависимостях.

2. Проводим частичную инструментацию текста программы трассировочными функциями динамического анализа в соответствии с полученными при статическом анализе результатами о предполагаемых зависимостях.

3. Корректируем информацию о зависимостях статического анализа информацией, полученной в результате динамического анализа.

Полученный алгоритм гибридного анализа не только объединяет достоинства обоих методов анализа, но и уменьшает их недостатки.



4 Исследование и построение решения задачи

4.1 Представление базы данных САПФОР

База данных САПФОР основана на реляционной модели и представлена более чем двадцатью таблицами, связанными между собой.

Таблицы содержат информацию о некоторых сущностях, введенных для описания программы, результатов анализа, параметров и результатов распараллеливания. К основным сущностям относятся: файлы, программные единицы, циклы, переменные, имена и описания COMMON-блоков, выражения, операторы, вызовы подпрограмм, обращения к элементам массивов и т.д. Зачастую, информация о некоторой сущности разбита между таблицами базы данных. Например, чтобы собрать информацию о переменной var, скажем, программную единицу, в которой объявлена переменная, тип, размерность и атрибуты переменной, необходимо ознакомится с содержимым трех таблиц базы данных. Этот факт достаточно неудобен для организации дополнения базы данных новыми элементами, сравнения двух одинаковых элементов разных баз данных, или сбора информации об определенной сущности базы данных. Именно поэтому было решено создать представление базы данных, для которого будут справедливы следующие утверждения:

1. Представление базы данных должно иметь интерфейс для хранения и обработки всей информации из базы данных.

2. Полная информация о конкретной сущности базы данных должна быть быстро и легко доступна из представления базы данных. Побочным эффектом данного требования будет возможное дублирование в представлении информации о некоторых сущностях базы данных.

Для уменьшения числа дублированной информации в представлении предлагается разбить всю информацию о сущностях базы данных на четыре логически законченные части, связанные между собой.

1. Хранилище информации о файлах программы

2. Хранилище информации об общих блоках программы

3. Хранилище информации о программных единицах программы

4. Хранилище информации о циклах программы

Рассмотрим каждое хранилище более подробно:

1. Хранилище информации о файлах программы, состоит из множества структур, каждая из которых содержит информацию о файле.

a. Структура, содержащая информацию о файле, заключает в себе:

· имя файла

· идентификатор файла в базе данных

2. Хранилище информации об общих блоках программы, состоит из множества структур, каждая из которых содержит информацию об общем блоке.

a. Структура, содержащая информацию об общем блоке, заключает в себе:

· название общего блока

· идентификатор общего блока в базе данных

3. Хранилище информации о программных единицах программы, состоит из множества структур, каждая из которых содержит информацию о программной единице.

a. Структура, содержащая информацию о программной единице, заключает в себе:

· идентификатор программной единицы в базе данных

· название программной единицы

· идентификатор файла в базе данных, в котором описана программная единица

· номер строки, с которой начинается программная единица

· идентификатор цикла в базе данных, который соответствует данной программной единице (программная единица является корнем дерева циклов)

· число параметров программной единицы

· множество структур, каждая из которых содержит информацию о переменной, зарегистрированной в данной программной единице

· соответствие параметров программной единицы зарегистрированным переменным

· множество структур, каждая из которых содержит информацию об описании общего блока для данной программной единицы.

b. Структура, содержащая информацию о переменной, заключает в себе:

· идентификатор переменной в базе данных

· имя переменной

· тип переменной

· список атрибутов переменной

· размерность переменной

· для каждой размерности структуру, содержащую информацию о выражении, для нижней и верхней грани

c. Структура, содержащая информацию об описании общего блока, заключает в себе:

· идентификатор общего блока в базе данных

· идентификатор описания общего блока в базе данных

· информацию о переменных, входящих в это описание общего блока.

d. Структура, содержащая информацию о выражении, заключает в себе:

· идентификатор выражения в базе данных

· текстовое представление выражения

· постфиксное представление выражения

· список структур, каждая из которых содержит информацию об одночлене выражения, если данное выражение можно представить в линейном виде, иначе список пуст.

e. Структура, содержащая информацию об одночлене линейного выражения, заключает в себе:

· идентификатор одночлена в базе данных

· коэффициент при одночлене

· информацию о переменной одночлена

4. Хранилище информации о циклах программы, состоит из множества структур, каждая из которых содержит информацию о цикле

a. Структура, содержащая информацию о цикле, заключает в себе:

· идентификатор цикла в базе данных

· тип цикла (цикл или программная единица)

· номер строки начала цикла

· суммарное время выполнения итерации цикла

· информацию о переменной - итераторе цикла

· структуры, содержащие информацию о выражениях начала, конца и шага итератора

· идентификатор программной единицы базы данных, содержащей цикл

· признак тесной вложенности

· список структур, содержащих информацию о дочерних циклах

· список структур, содержащих информацию об операторах внутри цикла

· структуру, содержащую информацию об операторе самого цикла

· список структур, содержащих информацию о зависимостях по данным в цикле

· список структур, содержащих информацию о возможных зависимостях по данным в цикле

b. Структура, содержащая информацию об операторе, заключает в себе:

· идентификатор оператора в базе данных

· номер строки оператора

· список структур, каждая из которых содержит информацию о переходе на другой оператор

· список структур, каждая из которых содержит информацию о доступе к переменной в операторе

· список структур, каждая из которых содержит информацию о вызове функции в операторе

· список особенностей ввода/вывода для оператора

c. Структура, содержащая информацию о зависимости для цикла, заключает в себе:

· тип зависимости

· информацию о переменной зависимости

· тип редукции (для редукционной зависимости)

d. Структура, содержащая информацию о переходе на другой оператор, заключает в себе:

· идентификатор цикла, в который происходит переход

· идентификатор оператора, на который происходит переход

· номер строки оператора, на который происходит переход

· вероятность перехода

e. Структура, содержащая информацию о вызове функции в операторе, заключает в себе:

· идентификатор вызова функции в базе данных

· информацию о программной единице, вызов которой происходит в операторе

· список информаций о параметрах программной единицы

· список доступов к памяти для параметров данного вызова программной единицы

· список структур, каждая из которых содержит информацию о выражениях для параметров данного вызова программной единицы

f. Структура, содержащая информацию о доступе к переменной в операторе, заключает в себе:

· идентификатор доступа к переменной в базе данных

· информацию о переменной, к которой осуществляется доступ

· тип доступа к переменной

· список структур, содержащих выражения для размерностей массива в момент доступа, для переменной массива

Общая схема организации представления базы данных отражена на Рисунке 6. Пунктирные стрелки указывают на возможное использование элементами одного хранилища информации элементов другого, сплошные - на связь хранилищей с интерфейсом представления базы данных. Через интерфейс осуществляется создание, удаление и корректировка элементов хранилищей.

ИИ

Также с помощью интерфейса осуществляется заполнение хранилищ информацией базы данных САПФОР и создание новой базы данных САПФОР по информации, содержащейся в хранилищах.

4.2 Возможные зависимости по данным

Основным свойством информации о зависимостях по данным, полученной в результате статического анализа текста программы, является безопасность. То есть, в спорных ситуациях, когда метод статического анализа не может доказать наличие или отсутствие зависимости, предполагается наличие зависимости. Именно для таких случаев в базе данных САПФОР введен способ фиксации возможных зависимостей по данным [10] (Тип зависимости VAR_DEP_POS в таблице depends базы данных говорит о возможном наличии зависимости по определенной переменной). Такая организация базы данных способствует проведению анализа программы сразу несколькими анализаторами, причем каждый следующий анализатор будет проводить анализ программы только для циклов, в которых обнаружена возможная зависимость по данным, и только для тех переменных, по которым возникла эта зависимость. Для проведения подобного анализа необходимо решить следующие проблемы:

1. Определить, какую информацию о цикле (о переменной) необходимо выделить из базы данных САПФОР, чтобы легко отличить в анализируемой программе данный цикл (переменную)

2. Разработать алгоритм частичного анализа программы, то есть, анализа зависимостей по интересующим нас переменным между витками интересующих нас циклов.

3. Разработать алгоритм сравнения двух баз данных САПФОР одной программы с последующим замещением неточной информации из первой базы данных на точную информацию из второй базы данных

Любой цикл программы однозначно определяется названием файла, содержащего цикл, и номером строки цикла в этом файле. А любая переменная программы однозначно определяется названием файла, содержащего программную единицу, в которой описана переменная, номером строки начала этой программной единицы в файле, а также именем, типом и размерностью переменной. Вся перечисленная информация содержится в базе данных САПФОР, следовательно, первая проблема сводится к получению необходимой информации из базы данных. Рассмотрим возможные решения второй и третьей проблемы в следующих пунктах.

4.3 Частичный анализ

В 2008 году Остапенко Г.Ю. в рамках дипломной работы разработал алгоритм динамического анализа последовательных программ, написанных на языке FORTRAN, соответствующий требованиям системы автоматизированного распараллеливания САПФОР, и на основе этого алгоритма программно реализовал динамический анализатор [5]. Доработаем динамический анализатор возможностью проведения частичного анализа программы.

4.3.1 Принципы работы динамического анализатора.

Общая схема работы динамического анализатора показана на Рисунке 7.



1. исходный текст программы поступает на вход инструментатору

2. инструментатор вставляет в текст программы вызовы функций динамического анализатора

3. проинструментированная программа подаётся на вход стандартному компилятору Fortran

4. скомпилированная программа линкуется со статической библиотекой динамического анализатора, и на выходе получается исполняемая программа с вызовами динамического анализатора

5. исполняемая программа запускается на входном наборе данных. В ходе выполнения программы осуществляется её анализ

6. полученная при анализе информация об исходной программе помещается в базу данных системы САПФОР

В качестве инструментатора в динамическом анализаторе используется инструментатор Fortran DVM/OpenMP программ [8]. Этот инструментатор предоставляет для нужд динамического анализа информацию об объявлениях скалярных переменных и массивов, об обращениях к памяти переменных и массивов для чтения и записи, о начале, новой итерации и конце цикла, о местоположении цикла в программе и его параметрах, об объявлениях и вызовах функций и процедур, о формальных и фактических параметрах функций.

Обнаружение зависимостей по данным между итерациями циклов в динамическом анализаторе осуществляется по алгоритму, использующему дерево контекстов. Реализация этого алгоритма определила внутреннее представление программы - в виде дерева, которое хранится в памяти компьютера до конца анализа и отражает всю информацию о ходе выполнения программы.

Опишем указанный алгоритм:

Для каждой переменной (элемента массива) хранятся все её точки чтения и записи. При очередном доступе на чтение (на запись) выполняется следующий анализ:

1. определяем ячейку памяти, к которой происходит доступ на чтение a_r (на запись a_w1);

2. для каждой предшествующей записи в ячейку памяти a_w (для каждого предшествующего чтения a_r и каждой предшествующей записи a_w2) определяем виртуальную точу доступа VP(a_w) (виртуальные точки доступа VP(a_r) и VP(a_w2));

3. находим контекст C_L (контексты C_Lr и C_Lw) - длиннейший общий подпуть контекстов C(a_r) и C(a_w) (C(a_w1) и C(a_r), C(a_w1) и C(a_w2));

4. находим контекст C_m (контексты C_mr и C_mw) - длиннейший контекст, являющийся подконтекстом контекста C_L (контекстов C_Lr и C_Lw соответственно) таким, что соответствующие цепочки IVC(a_r) и IVC(a_w) (IVC(a_w1) и IVC(a_r), IVC(a_w1) и IVC(a_w2)) содержат одинаковые значения на отрезке, соответствующем контексту C_m (контекстам C_mr и C_mw соответственно);

5. пусть r и w (w₁, r, w₂) - векторы, образованные отрезками цепочек IVC(a_r) и IVC(a_w) (IVC(a_w1), IVC(a_r), IVC(a_w2) соответственно), не вошедшими в контекст C_m (C_mr и C_mw); вычислим расстояние зависимости как d = r - w (d₁ = w₁ - r, d₂ = w₁ - w₂), если dim(r)>0 (dim(w₁)>0) и положим d=[] (d₁ = [] и d₂ = []) иначе;

6. пусть f₁ (f_r и f_w) - самый «глубокий» цикл в контексте С_L (C_Lr и C_Lw), добавим зависимость между итерациями цикла f₁ с расстоянием d (между итерациями цикла f_r с расстоянием d₁, и между итерациями цикла f_w с расстоянием d₂);

7. пусть st₁ и st₂ - вершины, соответствующие первому и второму доступу к памяти и непосредственно следующие за C_L (C_Lr или C_Lw); добавить зависимость между операторами st₁ и st₂ с расстоянием d (d₁ или d₂).

Для построения дерева циклов программы, необходимого базе данных САПФОР, программные единицы тоже рассматриваются как циклы с одной итерацией. Поэтому любая зависимость по данным между операторами программы всегда будет рассматриваться в контексте объемлющего цикла. В базе данных САПФОР предусмотрено пять типов сложностей распараллеливания: редукционная зависимость, зависимость по собственной переменной между итерациями цикла, зависимость, связанная с неплановым завершением цикла (например, с помощью оператора перехода на оператор программы, находящийся вне цикла), зависимость по переменной между итерациями цикла, потенциальная зависимость по переменной между итерациями цикла. Рассмотренный выше алгоритм позволяет обнаруживать только реально существующие зависимости по переменным между итерациями цикла.

4.3.2 Алгоритм частичного динамического анализа

Расширим структуру, содержащую информацию о переменной во внутреннем представлении программы динамического анализа, добавлением атрибута «счетчик необходимости» целого беззнакового типа. Данный атрибут будет отвечать за необходимость обработки обращения к переменной при проведении частичного динамического анализа программы.

Расширим структуру, содержащую информацию о цикле во внутреннем представлении программы динамического анализа, добавлением атрибута «флага проверки» булевого типа и списка структур-переменных, необходимых для анализа в данном цикле. «Флаг проверки» будет отвечать за необходимость обработки обращений к структуре-переменной из списка необходимых для анализа в данном цикле структур-переменных при проведении частичного динамического анализа программы.

Алгоритм частичного динамического анализа:

Для облегчения повествования под переменной будем понимать структуру, содержащую информацию о переменной во внутреннем представлении программы динамического анализатора, а под циклом - структуру, содержащую информацию о цикле во внутреннем представлении программы динамического анализатора (Программная единица также рассматривается как цикл)

1. При регистрации новой переменной устанавливаем атрибут «счетчик необходимости» этой переменной в ноль.

2. При регистрации нового цикла, устанавливается «флаг проверки» этого цикла положительным, если цикл содержит возможные зависимости по переменным, в противном случае - отрицательным. Заполняем список необходимых для анализа переменных данного цикла, переменными, по которым существует возможная зависимость в данном цикле.

3. При входе в цикл, если «флаг проверки» цикла истинен, то у каждой переменной из списка необходимых для анализа переменных этого цикла «счетчик необходимости» увеличивается на единицу

4. При выходе из цикла, если «флаг проверки» цикла истинен, то у каждой переменной из списка необходимых для анализа переменных этого цикла «счетчик необходимости» уменьшается на единицу.

5. При доступе к переменной (чтение или запись), если доступ происходит в цикле с утвердительным «флагом проверки» к переменной с положительным «счетчиком необходимости», то фиксируем его, в противном случае - нет.

При данном алгоритме, мы будем проводить анализ зависимостей по интересующим нас переменным в интересующих нас циклах и программных единицах.

4.4 Коррекция информации в базе данных САПФОР

Итак, пусть мы имеем программу program и два разных анализатора, соответствующие требованиям системы автоматизированного распараллеливания САПФОР, anlsr1 и anlsr2. В результате работы анализатора anlsr1(anlsr2) над программой program, получаем базу данных САПФОР db1(db2). Необходимо определить, какие из возможных зависимостей по переменным между итерациями циклов db1 являются реальными в db2, заменить возможные зависимости по переменным между итерациями циклов из db1 соответствующими реальными зависимостями из db2.

Для решения поставленной задачи воспользуемся представлением базы данных САПФОР, описанным в пункте 4.1.

Для упрощения повествования далее:

1. цикл - структура представления базы данных САПФОР, содержащая информацию о цикле

2. переменная - структура представления базы данных САПФОР, содержащая информацию о переменной

3. зависимость - структура представления базы данных САПФОР, содержащая информацию о сложностях распараллеливания программы, за исключением возможных зависимостей по переменным между итерациями цикла

4. возможная зависимость - структура представления базы данных САПФОР, содержащая информацию о возможной зависимости по переменной между итерациями цикла

Путь loop1 (loop2) - цикл, fileName1 (fileName2) - название файла, содержащего цикл loop1( loop2), lineNumber1 (lineNumber2) - номер строки цикла loop1 (loop2) в файле. Тогда цикл loop1 эквивалентен loop2, если fileName1 = fileName2 и lineNumber1 = lineNumber2.

Путь var1 (var2) - переменная, fileName1 (fileName2) - название файла, содержащего программную единицу, в которой описана переменная var1( var2), lineNumber1 (lineNumber2) - номер строки начала этой программной единицы в файле, name1(name2) - имя переменной var1(var2), type1(type2) - тип переменной var1(var2), dims1(dims2) - размерность переменной var1(var2). Тогда переменная var1 эквивалентна var2, если fileName1 = fileName2, lineNumber1 = lineNumber2, name1 = name2, type1 = type2 и dims1 = dims2 .

Далее, пусть repres1(repres2) - представление db1(db2), loopsLst1(loopsLst2) - список циклов, соответствующих программным единицам repres1(repres2), тогда:

1. Если loopsLst1 пуст, то завершаем вычисления, иначе для каждого цикла loop1из loopsLst1 ищем эквивалентный цикл loop2 из loopsLst2

2. Пусть posDepsLst1 - список возможных зависимостей из loop1, depsLst1(depsLst2) - список зависимостей из loop1(loop2)

3. Для каждой возможной зависимости dep1 по переменной var1 из списка posDepsLst1 ищем список реальных зависимостей tmpDepLst по переменной var2, эквивалентной var1, из списка depsLst2.

4. Если tmpDepLst не пуст, то дополняем список depsLst1 зависимостями из списка tmpDepLst и удаляем dep1 из posDepsLst1, иначе идем на пятый шаг.

5. Устанавливаем loopLst1(loopLst2) как список дочерних циклов цикла loop1(loop2), идем на шаг 1.



4.5 Общая схема работы гибридного анализа



Введем обозначения:

База данных статического анализатора - база данных системы САПФОР, полученная в результате анализа текста программы статическим анализатором.

База данных динамического анализатора - база данных системы САПФОР, полученная в результате динамического анализа выполнения программы, запущенной на определенных входных данных.

Общая схема работы гибридного анализа (Рисунок 8):

1. Текст исходной программы подается на вход статическому анализатору. На выходе получаем базу данных статического анализатора.

2. База данных статического анализатора подается на вход программе поиска возможных зависимостей. Программа поиска возможных зависимостей строит внутреннее представление базы данных статического анализатора на основе функций статической библиотеки организации представления базы данных, затем выделяет из представления информацию о возможных зависимостях по переменным между итерациями циклов и, наконец, выводит собранную информацию в файл «Файл возможных зависимостей».

3. Текст исходной программы подается на вход инструментатору. Инструментатор вставляет в текст программы вызовы функций динамического анализатора. Проинструментированная программа подаётся на вход стандартному компилятору Fortran. Скомпилированная программа линкуется со статической библиотекой динамического анализатора, и на выходе получается исполняемая программа с вызовами динамического анализатора. Полученная исполнительная программа запускается на некотором входном наборе данных. В ходе выполнения программы осуществляется её частичный динамический анализ с учетом информации из файла возможных зависимостей (при отсутствии файла или отсутствии информации внутри файла предполагается полный динамический анализ программы). Полученная при анализе информация об исходной программе помещается в базу данных динамического анализатора.

4. Базы данных статического и динамического анализаторов подаются на вход программе сравнения баз данных. Программа строит внутренние представления обоих баз данных на основе функций из библиотеки организации представления базы данных, далее, руководствуясь полезной информацией, записанной в базе данных динамического анализатора, корректирует внутреннее представление базы данных статического анализатора. На выходе программы сравнения баз данных получаем базу данных, сформированную на основе скорректированного внутреннего представления базы данных статического анализатора.



5 Описание практической части

В ходе практических работ были реализованы:

1. статическая библиотека функций организации и дальнейшей обработки представления базы данных САПФОР

2. программа поиска информации о возможных зависимостях по переменным между итерациями циклов из представления базы данных САПФОР

3. программа сравнения двух представлений баз данных САПФОР одной программы, с последующей коррекцией первого представления за счет полезной информации второго представления

также была доработана статическая библиотека функций динамического анализа возможностью проведения частичного анализа. Рассмотрим подробнее каждый из перечисленных элементов.

5.1 Статическая библиотека представления базы данных САПФОР

Статическая библиотека представления базы данных САПФОР реализована в среде разработки Microsoft Visual C++ 2008 Express Edition на языке программирования C++. Она содержит:

1. набор классов, каждый из которых описывает сущность базы данных САПФОР и включает методы доступа к информации этих сущностей и коррекции этой информации.

a. класс FileInfo описывает структуру, содержащую информацию о файле, изложенную в пункте 4.1.

b. класс RoutineInfo описывает структуру, содержащую информацию о программной единице, изложенную в пункте 4.1.

c. класс ArrayInfo описывает структуру, содержащую информацию о переменной, изложенную в пункте 4.1.

d. класс Monom описывает структуру, содержащую информацию об одночлене линейного выражения, изложенную в пункте 4.1.

e. класс Expression описывает структуру, содержащую информацию о выражении, изложенную в пункте 4.1.

f. класс VariableAcces описывает структуру, содержащую информацию о доступе к переменной, изложенную в пункте 4.1.

g. класс CommonBlockInfo описывает структуру, содержащую информацию об общем блоке, изложенную в пункте 4.1.

h. класс ComBlockDef описывает структуру, содержащую информацию о конкретном описании общего блока, изложенную в пункте 4.1.

i. класс Dependence описывает структуру, содержащую информацию о сложности распараллеливания, изложенную в пункте 4.1.

j. класс LoopInfo описывает структуру, содержащую информацию о цикле, изложенную в пункте 4.1.

k. класс OperatorInfo описывает структуру, содержащую информацию об операторе, изложенную в пункте 4.1.

l. класс Branch описывает структуру, содержащую информацию о переходе на другой оператор, изложенную в пункте 4.1.

m. класс Call описывает структуру, содержащую информацию о вызове функции, изложенную в пункте 4.1.

2. Набор классов, каждый из которых описывает хранилище представления базы данных САПФОР и включает методы добавления и удаления элементов хранилища, доступа к элементам хранилища.

a. Класс FilesStorage описывает хранилище информации о файлах программы

b. Класс CommonBlocksStorage описывает хранилище информации об общих блоках программы

c. Класс RoutinesStorage описывает хранилище информации о программных единицах программы

d. Класс LoopsStorage описывает хранилище информации о циклах программы

3. Оновной класс InternalRepresentation, который включает методы инициализации хранилищей информацией базы данных САПФОР,методы доступа к хранилищам представления, методы создания и заполнения новой базы данных, основываясь на информации, содержащейся в хранилищах представления.

Стоит отметить, что, при инициализации хранилищей представления информацией базы данных САПФОР, проверяется ссылочная целостность базы данных САПФОР. Ссылочная целостность - это ограничение базы данных, гарантирующее, что ссылки между данными являются действительно правомерными и неповрежденными. Таким образом, если в базе данных САПФОР будет присутствовать некорректная информация, то в представление она не попадет.

5.2 Программа поиска возможных зависимостей

Программа поиска возможных зависимостей реализована в среде разработки Microsoft Visual C++ 2008 Express Edition на языке программирования C++ и использует статическую библиотеку представления базы данных САПФОР.

На вход программа получает базу данных САПФОР, на выходе файл с информацией о возможных зависимостях по данным между витками цикла «posDepsInfo.txt».

Файл «posDepsInfo.txt» представляет собой набор строк вида:

название_файла ; номер_строки_программной_единицы ; номер_строки_начала_цикла ; имя_переменной ; тип_переменной ; размерность_переменной;

Таким образом, каждая строчка файла точно определяет цикл и переменную, по которой предполагается возможная зависимость между итерациями данного цикла.

5.3 Изменения, внесенные в статическую библиотеку функций динамического анализа

Статическая библиотека функций динамического анализа была пересобрана в среде Microsoft Visual Studio 2005. В этой же среде велась работа по изменению и дополнению некоторых функций библиотеки.

Основных дополнений два:

1. При наличии в каталоге исполняемого файла непустого текстового файла "posDepsInfo.txt" будет проводится частичный динамический анализ программы в соответствии с алгоритмом, описанным в пункте 4.3.2. Иначе, если файл "posDepsInfo.txt" отсутствует или пуст, то проводится полный динамический анализ программы.

2. В динамический анализ добавлен механизм измерения времени работы итераций цикла и программных единиц без учета времени работы вложенных циклов. Эта информация необходима для заполнения базы данных САПФОР и раньше игнорировалась.