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

Аннотация

 

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

 

 

Введение

 

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

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

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

 

САПФОР

 

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

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

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

3. Эксперт

4. Генератор

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

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

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

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

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

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

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

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

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

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

 

Рисунок 1

 

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

Цель работы

 

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

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

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

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

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

 

 

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

 

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

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

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

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

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

 

Между двумя операторами программы возникает зависимость по данным, когда в этих операторах происходит обращение к одной и той же ячейке памяти, причем хотя бы в одном из этих операторов осуществляет запись в данную ячейку [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)

 

 

Рисунок 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].

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

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

 

Обзор

 

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

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

 

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

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

 

 

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

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

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

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

3. Ī' ≤ Ī"

4. f_i(Ī') = g_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 отсутствует. Если решить систему уравнений невозможно, то статический анализ не может точно доказать наличие или отсутствие зависимости между операторами и фиксирует возможную зависимость. Это предположение гарантирует генерацию корректной параллельной программы, но связано с потерей эффективности из-за недостаточного использования параллелизма, в случае, если реальной зависимости в программе нет.