Аннотация
Анализ зависимостей по данным является важнейшим этапом при распараллеливании программ. Данная работа посвящена методам динамического анализа зависимостей. Рассматриваются два метода динамического анализа, а также практическая реализация одного из них. Полученный динамический анализатор может стать в будущем частью системы автоматизации распараллеливания программ.
Оглавление
1 Введение. 3
1.1 Параллельное программирование. 3
1.2 Автоматизация распараллеливания. 5
1.3 Статический анализ. 6
1.4 Динамический анализ. 8
1.5 Распараллеливание во время выполнения. 9
1.6 Цель работы.. 10
2 Постановка задачи. 11
2.1 Зависимости по данным. 11
2.2 Система автоматизации распараллеливания. 12
2.3 Задача анализатора. 13
3 Динамический анализ. 14
3.1 Схема работы динамического анализатора. 14
3.2 Динамический анализ с использованием дерева контекстов. 15
3.3 Динамический анализ с использованием глобальных номеров итераций. 17
3.4 Преимущества и недостатки динамического анализа. 19
4 Практическая реализация. 22
4.1 Инструментация. 22
4.2 Формат результатов. 24
4.3 Внутреннее устройство анализатора. 26
4.4 Результаты тестирования. 28
5 Заключение. 30
6 Литература. 31
С момента появления вычислительных машин одной из основных их функций является выполнение трудоемких вычислений. При этом сложность поставленных задач растет быстрее, чем производительность отдельного процессора. Многие современные вычислительные задачи невозможно решить с помощью однопроцессорных ЭВМ, поскольку программа будет выполняться слишком долго либо затребует большой объем ресурсов таких, как, например, память. Поэтому для увеличения скорости вычислений применяется также и другой путь – создание многопроцессорных ЭВМ.
1.1 Параллельное программирование
Параллельным программированием будем называть процесс написания программы для многопроцессорной системы. Разумеется, параллельное программирование имеет ряд особенностей по сравнению с традиционным последовательным программированием. Кроме того, в зависимости от типа многопроцессорной системы применяются различные средства программирования:
Системы с общей памятью (SMP) – набор параллельно работающих процессоров, имеющих доступ к общей для всех процессоров памяти, причем скорость доступа к памяти одинакова для всех процессоров. Применяется программирование в модели общей памяти, как правило, с использованием интерфейса OpenMP.
Системы с неоднородным доступом (NUMA) – набор блоков, содержащих несколько процессоров и общую для них память. При этом допускается обращение любого процессора к удаленной памяти, т.е. памяти другого блока, но обращение происходит медленнее, чем обращение к локальной памяти. При программировании применяется, например, система Shmem.
Системы с распределенной памятью (MPP) – набор узлов, состоящих из процессора и памяти, и коммутационной среды для связи между узлами. Каждый процессор имеет непосредственный доступ только к своей локальной памяти. При программировании применяется модель передачи сообщений, используются библиотеки MPI, PVM и др.
Смешанные системы – набор SMP-узлов, соединенных коммутационной средой. Применяется комбинация моделей передачи сообщений и общей памяти. Часто также используется чистая модель передачи сообщений, тогда каждый процессор в SMP-узле трактуется как независимый узел со своей локальной памятью.
К сожалению, специалист в предметной области, способный разработать алгоритм и запрограммировать его на каком-либо языке программирования (например, Си или Фортране), далеко не всегда знаком с приемами написания параллельных программ и зачастую не может самостоятельно привести свою программу к виду, выполнимому на многопроцессорной машине. Поэтому распараллеливанием таких программ занимаются отдельные люди – специалисты по написанию параллельных программ. Это приводит к увеличению необходимого числа программистов, работающих над программой и потере времени на хотя бы минимальное знакомство специалиста с предметной областью.
Проблема осложняется тем, что за десятилетия существования компьютеров было накоплено большое число библиотек подпрограмм для различных предметных областей. Эти библиотеки широко применяются при написании обычных последовательных программ. Однако для использования возможностей многопроцессорных ЭВМ необходимо написание параллельного варианта каждой библиотеки. В силу трудоемкости процесса распараллеливания и большого количества библиотек массовое создание параллельных вариантов библиотек на основе существующих последовательных вариантов не представляется возможным.
1.2 Автоматизация распараллеливания
Возможное решение описанной проблемы – создание системы автоматизации распараллеливания программ. При наличии подобной системы существенно облегчается работа специалистов по параллельному программированию, повышается эффективность их работы, что сильно сокращает время, необходимое на разработку параллельной программы.
Процесс распараллеливания можно разделить на две части:
Анализ исходной программы.
Синтез параллельной программы.
Анализ необходим для выявления скрытого параллелизма в исходной последовательной программе. Прежде всего, сюда включается выявление зависимостей по данным между операторами программы. Такая зависимость возникает, например, в случае, если один оператор использует значение переменной, вычисленное некоторым другим оператором. Независимые операторы могут быть выполнены параллельно на разных процессорах. Обычно этот принцип применяется к циклам: если нет зависимостей по данным между разными витками цикла, то витки могут быть выполнены параллельно разными процессорами. Также на этапе анализа могут собираться сведения о необходимом размещении данных в случае, если используется система с распределенной памятью. Кроме того, возможен сбор сведений о времени выполнения различных участков программы с целью выбора наилучшего варианта распараллеливания программы.
Синтез параллельной программы включает выбор схемы распределения данных (если необходимо) и вычислений, а также непосредственно генерацию текста параллельной программы с использованием подходящих инструментов параллельного программирования. Подробное рассмотрение возникающих при этом вопросов выходит за рамки данной работы.
Выявление зависимостей по данным в исходном тексте программы является важнейшим этапом анализа. Существуют различные методы выявления зависимостей: статические методы, анализирующие текст программы, динамические методы, исследующие ход выполнения программы на некоторых тестовых данных, различные тесты, проводимые в ходе выполнения готовой параллельной программы.
Помимо анализа программы система автоматизации распараллеливания может получать различную информацию от пользователя. Так, например, система ParaWise [1] предлагает итерационный процесс анализа: статический анализ исходной программы и получение дополнительной информации от пользователя чередуются до получения приемлемого результата.
Другим примером системы автоматизации распараллеливания может служить проект V-Ray [2]. Эта система включает статический анализ структуры программы и информационных зависимостей, присутствующих в программе, а также динамический анализ параллельных программ. Система позволяет оптимизировать существующие программы, а также получить эффективные реализации программ для различных аппаратных платформ путем анализа лежащего в основе программ алгоритмического подхода.
1.3 Статический анализ
Статические методы анализа основаны на исследовании исходного текста программ. Основная идея таких методов заключается в построении по индексным выражениям в операторах, обращающихся к массивам, систем уравнений и неравенств с неизвестными, соответствующими индексным переменным циклов. Например, для следующего фрагмента программы:
for (i=1; i<n; i++)
a[i] = a[i-1] + 1;
на основе использование одного и того же массива «а» может быть получено уравнение
<инд. выр-е в левой части> = <инд. выр-е в правой части на другой итерации>, то есть i1 = i2-1 .
Решение данного уравнения покажет наличие зависимости между соседними итерациями цикла: каждая следующая итерация использует значение, вычисленное на предыдущей итерации.
Существуют различные методы статического анализа зависимостей, различающиеся методами построения системы (возможно, неявно) по тексту программы и ее решения. В спорных ситуациях, когда метод не может доказать наличие или отсутствие зависимости, предполагается наличие зависимости. Это консервативное предположение гарантирует генерацию корректной параллельной программы, но связано с потерей эффективности из-за недостаточного использования параллелизма, в случае, если реальной зависимости в программе нет.
По своей природе статические методы анализа обладают рядом ограничений. Одно из основных связано с тем, что при анализе текста программы никогда не известны значения переменных, используемых в программе. В особенности это относится к входным данным, получаемым программой из внешних источников. В случае, если такие переменные используются в индексных выражениях при обращениях к массивам или в граничных значениях циклов, статические методы анализа не смогут сделать какие-либо выводы и будут вынуждены предположить наличие зависимости. В ряде случаев эта проблема может быть решена с помощью подсказок со стороны разработчика исходной программы, указывающих возможные значения некоторых переменных.
Помимо этого, большинство статических методов способны анализировать только линейные относительно переменных циклов индексные выражения. Это ограничение не является слишком сильным ограничением, поскольку зачастую используются именно линейные индексные выражения. Однако это препятствует проведению анализа в таких важных случаях, как косвенная индексация, а также вызовы функций в индексных выражениях.