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

• Автор: Коробко, Алексей Юрьевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Таганрог
• Количество страниц: 118 с. : ил.

Оглавление

Принятые обозначения

Введение О

1 Анализ структуры программ

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

1.2 Класс анализируемых программ

1.3 Трансляция линейных фрагментов в граф зависимостей . .

1.4 Преобразование графа зависимостей линейного фрагмента в

сеть Петри

1.5 Анализ тесно вложенных гнзд циклов .

1.5.1 Ограниченияравенства.

1.5.2 Ограничениянеравенства . . . .
1.5.3 Алгоритм исключения переменной
1.5.4 Получение векторов расстояния и направления
Выводы
2 Распараллеливающее преобразование
2.1 Постановка задачи.
2.2 Распараллеливание тесно вложенных гнзд циклов
2.3 Распараллеливание тел циклов
2.3.1 Преобразование сети Петри.
2.3.2 Трансляция сети Петри в параллельную программу .
2.3.3 Параллельная интерпретация сети Петри.
2.3.4 Критерии оценки.
3 Реализация разработанных алгоритмов
Заключение
Литература


Разумеется, в этом случае прироста производительности не произойдёт, и программа будет использовать только один вычислительный узел. Для использования ресурсов нескольких микропроцессоров, программное обеспечение должно быть написано в соответствии с определёнными правилами. Параллельное программирование является отдельным направлением, и может оказаться сложным для неподготовленного программиста. Соответственно затраты на перенос ПО резко возрастают. На протяжении нескольких десятилетий решается задача автоматического распараллеливания программ /1, 2, 3, 4/. В результате были сформированы основные принципы функционирования подобных систем, а также были разработаны некоторые алгоритмы распараллеливания. Путём анализа исходных кодов программ на языке программирования Фортран было установлено, что около % времени занимает выполнение циклов. При этом средняя глубина вложенности циклов составляет около 3 /5/. Для распараллеливания обычных вложенных циклов используются различные преобразования. Тип преобразования зависит от целевой архитектуры, на которой должен выполняться параллельный вариант приложения. Данная зависимость продиктована различиями в типах памяти. Для оптимального распараллеливания, преобразование должно порождать оптимальную гранулярность целевой программы. Микро-параллелизм оптимален для векторных машин; для систем с общей памятью наиболее эффективен макро-параллелизм (достигаемый путём преобразований циклов). Таким образом, достигается цель минимизации межпроцессных взаимодействий. Общая задача распараллеливания разбивается на три основных этапа: поиск параллелизма, применение распараллеливающего преобразования, кодогенерация. Первые два этапа в наименьшей степени зависят от целевой архитектуры и в большей от структуры исходной программы и могут выполняться независимо от ее выбора. Использование одномерной или многомерной функции таймирования (алгоритмы //). Данные группы алгоритмов различаются используемыми методами и формами представления зависимостей. Алгоритмы 1-й группы используют графовые алгоритмы и уровни зависимостей; 2-я группа алгоритмов оперирует матричными вычислениями и векторами направлений; алгоритмы, принадлежащие 3-й группе, основаны на линейном программировании и оперируют зависимостями в виде многомерных фигур в пространстве. Все алгоритмы распараллеливания, которые представляют зависимости в виде векторов расстояний, могут быть сведены к обобщённому алгоритму, основанному на преобразовании, предложенном Карпом, Миллером и Виноградом //. Алгоритм точно выделяет зависимости, препятствующие достижению параллелизма. Например, п вложенных циклов могут быть представлены как п-мерный объект в пространстве (объект описывается счётчиками циклов). При этом, число точек, заключённых в многомерном объекте, будет соответствовать числу выполняемых вычислительных операций. Однако, определение степени параллелизма в большинстве не является тривиальным. Этот аспект делает распараллеливание вложенных циклов достаточно сложной задачей. Распараллеливающее преобразование должно быть способным достичь максимальной степени параллелизма за время меньшее, чем последовательное выполнение исходной программы. Для достижения этой цели, необходимо определить сложность алгоритмов распараллеливания и размер входных и выходных данных. Входные данные распараллеливающего преобразования — это информация о зависимостях; выходные данные представляют эквивалентную распараллеленную программу. Каждой итерации циклов, окружающих некоторое вычислительное выражение, соответствует выполнение этого выражения на вычислительной системе, которое называется срабатыванием. Зависимости между срабатываниями представляются в виде ацикличного графа, множество вершин которого соответствует множеству срабатываний. Такой грае}) называют расширенным графом зависимостей. Дуги графа задают порядок срабатываний, который гарантирует получение корректного результата вычислений. Поиск параллелизма в циклах эквивалентен поиску независимых маршрутов в расширенном графе зависимостей.