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

Аннотация

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



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₂ с...