Методы анализа информационной структуры программ и алгоритмы их распараллеливания для гетерогенных вычислительных систем тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Коробко, Алексей Юрьевич

• Коробко, Алексей Юрьевич
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Коробко, Алексей Юрьевич

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

Введение

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

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

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

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

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

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

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

1.5.2 Ограничения-неравенства

1.5.3 Алгоритм исключения переменной.

1.5.4 Получение векторов расстояния и направления . 63 Выводы.G

2 Распараллеливающее преобразование

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

2.2 Распараллеливание тесно вложенных гнёзд циклов .8G

2.3 Распараллеливание тел циклов.

2.3.1 Преобразование сети Петри.9G

2.3.2 Трансляция сети Петри в параллельную программу

2.3.3 Параллельная интерпретация сети Петри.

2.3.4 Критерии оценки.

Выводы.

3 Реализация разработанных алгоритмов

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

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

На протяжении нескольких десятилетий решается задача автоматического распараллеливания программ /1, 2, 3, 4/. В результате были сформированы основные принципы функционирования подобных систем, а также были разработаны некоторые алгоритмы распараллеливания. Однако, существующие алгоритмы позволяют проводить распараллеливание лишь циклических операций, в то время как тела циклов выполняются последователыто.

Путём анализа исходных кодов программ на языке программирования Фортран было установлено, что около 80% времени занимает выполнение циклов. При этом средняя глубина вложенности циклов составляет около 3/5/.

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

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

В настоящее время существуют три основных типа распараллеливающих преобразований:

1. Декомпозиция графа зависимостей в жёстко связные компоненты алгоритм Алена и Кеннеди /25/);

2. Унимодулярные преобразования циклов (алгоритм Вольфа и Лама /26/);

3. Использование одномерной или многомерной функции таймирования (алгоритмы /32/).

Данные группы алгоритмов различаются используемыми методами и формами представления зависимостей. Алгоритмы 1-й группы используют графовые алгоритмы и уровни зависимостей; 2-я группа алгоритмов оперирует матричными вычислениями и векторами направлений; алгоритмы, принадлежащие 3-й группе, основаны на линейном программировании и оперируют зависимостями в виде многомерных фигур в пространстве.

Все алгоритмы распараллеливания, которые представляют зависимости в виде векторов расстояний, могут быть сведены к обобщённому алгоритму, основанному на преобразовании, предложенном Карпом, Миллером и Виноградом /27/. Этот обобщённый алгоритм имеет следующие свойства:

1. Алгоритм может быть адаптирован для использования всех представлений зависимостей в виде векторов расстояний;

2. Алгоритм является оптимальным, независимо от выбранного представления векторов расстояний;

3. Алгоритм точно выделяет зависимости, препятствующие достижению параллелизма.

Вложенные циклы являются структурами кода, позволяющими описать множество вычислений, объем которых Tie пропорционален объёму кода, их описывающего. Например, п вложенных циклоп могут быть представлены как n-мерный объект в пространстве (объект описывается счётчиками циклов). При этом, число точек, заключённых в многомерном объекте, будет соответствовать числу выполняемых вычислительных операций. Однако, определение степени параллелизма в большинстве не является тривиальным.

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

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

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

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

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

Такое упрощение позволяет представлять итерации п вложенных циклов (п — глубина вложенности) в виде векторов в n-мерном пространстве Zn (такие вектора называют итерационными) ограниченных выпуклым многоугольником (доменом итераций), i-й компонент вектора итераций является значением счётчика г-го цикла (циклы нумеруются от внешнего к внутреннему). В последовательном коде итерации циклов выполняются в лексикографическом порядке соответствующих векторов итераций.

Обозначим домен итераций как Р; n-мерные вектора итераций как I и J; г'-е вычислительное выражение цикла как S{.

Существует три основных метода определить новый порядок срабатываний итераций циклов:

1. Использование элементарных преобразований (разбиение, перестановка и т.п.) в качестве основных операций алгоритма;

2. Изменение линейного базиса итерационного домена с помощью уни-модулярных преобразований итерационных векторов;

3. Определение d-мерпой функции таймирования и её использование для осуществления перехода из пространства Zn в пространство Zd. При этом размерность результатирующего пространства является меньшей, а отброшенные размерности соответствуют параллельным циклам.

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

1. Лучи и вершины в пространстве. Некоторые алгоритмы анализа информационной структуры программ /30/ предоставляют информацию о зависимостях (описанную в виде многоугольника в пространстве) в виде лучей и вершин. Такое представление даёт наиболее полную информацию о зависимостях, однако не всегда удобно, так как требуемый объем вычислений достаточно велик;

2. Вектора направлений. Множество векторов расстояний (вектор, элементы которого представляют разность между соответствующими элементами итерационных векторов, описывающих зависимые итерации) аппроксимируется одним вектором, элементы которого задают границы изменения соответствующих элементов векторов расстояний;

3. Уровень зависимости. Множество векторов расстояний аппроксимируется целым числом I € [1.П+1], определяющим такое наибольшее целое, что I — 1 первых компонентов векторов расстояния равны нулю. Уровень зависимости I < п означает, что зависимость вносится 1-й циклом. Если / = п + 1, то зависимость вносится телом наиболее вложенного цикла. Данное представление наиболее удобно, так как не требует сложных вычислений и описывает (главным образом) только зависимости вносимые циклами.

Рассмотрим основные алгоритмы распараллеливания. Алгоритм Алена-Кеннеди основан на следующих предположениях:

1. внешний цикл является параллельным, если он не вносит зависимости, т.е. отсутствует зависимость уровня 1;

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

1-е предположение позволяет принимать решение о распараллеливании внешнего цикла; 2-е предположение позволяет выполнять распараллеливание жёстко связных компонентов сокращённого графа зависимостей независимо.

На вход алгоритма подаётся описание сокращённого графа зависимостей, дуги которого помечены уровнями зависимостей. Распараллеливание выполняется путей перераспределения циклов.

Пусть G — сокращённый граф зависимостей; п — глубина вложенности циклов; G(k) — подграф графа G, в котором убраны дуги, описывающие зависимости уровня меньшего к. Алгоритм является рекурсивным. Первоначальный вызов выполняется следующим образом: ALLEN — KENNEDY(G, к).

• Если к > п, то осуществляется завершение работы алгоритма;

• Выполняется декомпозиция G(k) на жёстко связные подграфт.т Gi. Подграфы топологически сортируются;

• Переписываем код таким образом, что бы каждый Gi принадлежал к отдельному гнезду циклов уровня к;

• Для каждого Gi помечаем цикл уровня к как параллельный, если Gi не имеет дуг уровня к. Иначе помечаем цикл как последовательный;

• Для каждого Gi повторяем алгоритм ALLEN — KENNEDY (Gi, к 4

Доказано, что алгоритм Алена-Кеннеди является оптимальным среди всех алгоритмов распараллеливания, принимающих сокращённый граф зависимостей и зависимости, аппроксимированные уровнями зависимостей /31/.

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

Алгоритм Вольфа-Лама является адаптированным алгоритмом Лампорта, использующим информацию о зависимостях в виде векторов направлений. Алгоритм использует унимодулярные преобразования для конвертирования произвольных циклов в идеально вложенные гнезда. Множество циклов вложенности п преобразуется в один последовательный цикл и d — 1 параллельных циклов. Используемая аппроксимация в виде векторов направлений является более точной, чем уровни зависимостей, применяющиеся в алгоритме Алена-Кеннеди. Однако, структура сокращённого графа зависимостей не используется во время распараллеливания. Таким образом, данный алгоритм может порождать максимально распараллеленный код только в случае, когда подобные зависимости аппроксимируемы векторами направлений.

Алгоритм Фиатре /33, 34/ использует основные аффинные преобразования. В зависимости от точности анализа информационной струк

Алгоритм Зависимости Преобразования Оптим.

Алена-Кеннеди Уровень зависимостей Распределение Да

Вольфа-Лама Вектор направлений Унимодулярные Да

Дарте-Вивьен Многогранник Аффинные Да

Фиатре Вектор расстояний Аффинные Нет

Таблица 0.1. Характеристики алгоритмов распараллеливания туры исходной программы, данный алгоритм может распараллеливать как идеально вложенные гнезда циклов, так и ординарные последовательности циклов. Хотя алгоритм показывает один из лучших результатов при распараллеливании наиболее вложенных циклов, он не является оптимальным, так как аффинные преобразования применимы в редких случаях. Более того, алгоритм не адаптирован для распараллеливания внешних (наименее вложенных) циклов.

Алгоритм Дарте-Вивьен /35/ является упрощённым алгоритмом Фиатре. Алгоритм использует описание зависимостей в виде многомерного многоугольника. На практике коэффициент распараллеливания достигаемый этим алгоритмом значительно уступает алгоритму Фиатре.

Основные характеристики рассмотренных алгоритмов приведены в таблице 0.1.

Существующие алгоритмы способны распараллеливать тесно вложенные гнезда циклов, однако тело цикла остаётся исходным. В настоящее время распространение получили многопроцессорные вычислительные системы с общей памятью. Кроме того, технология Hyper Thread корпорации Intel позволяет эффективно выполнять код, распараллеленный на микро уровне.

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

Из следующего примера видно, что выражение S3 зависит от выражения S2, так как S2 содержит определение переменной А, используемой в выражении S3:

SI: А = 4 * В S2: А = 3 S3: С = А * 3.

Подобная информация полностью определяет ограничения по допустимому порядку выполнения инструкций в программе. В примере, приведённом выше, выражение S3 всегда должно вычисляться перед выражением S2. На выражение S1 подобных ограничений не накладывается.

Итеративные и интервальные /46/ методы анализа информационной структуры программ применимы только к скалярным переменным.

Большинство научных и инженерных программ с вложенными циклами используют массивы данных большой размерности /38, 39/ и требуют более сложных методов анализа для определения отношений зависимостей между элементами массивов. Анализ зависимостей между элементами массивов сложен в силу того, массивы достаточно велики, что ведёт к увеличению размерности задачи, а также требует сложного анализа индексных переменных.

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

DO I = 1, N, 2 S1: А(2*1) = . S2: . = А(2*1+1) . ENDD0.

В тоже время, методы выявления зависимостей по потоку данных должны выполнять анализ индексных переменных и определять, что выражения S1 и S2 в действительности не находятся в отношении зависимости (S1 определяет чётные элементы массива, в то время как S2 использует нечётные элементы массива). Так как выражения S1 и S2 не зависят друг от друга, то могут выполняться независимо и параллельно без использования синхронизации, давая прирост производительности в 2 раза по сравнению с последовательным выполнением.

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

1. разработать алгоритм анализа зависимостей в линейных участках программ;

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

3. разработать алгоритм распараллеливания линейных участков программ на микро-уровне;

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

Алгоритмы Омега теста /36/ и Алена-Кеннеди были модифицированы с целыо работы как на макро, так и на микро уровнях.

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

Все полученные алгоритмы были реализованы в операционной системе для гетерогенных многопроцессорных систем NeurOS /6, 7, 8, 9/.

Заключение диссертации по теме «Теоретические основы информатики», Коробко, Алексей Юрьевич

Выводы

В главе приведена постановка задачи распараллеливания программ на основе результатов структурного анализа, представленного сетью Петри.

Приведены критерии применимости преобразований сети Петри на основании требования сохранения эквивалентности. Представлен класс допустимых преобразований сети Петри.

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

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

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

Разработан метод определения степени параллелизма для каждого из алгоритмов.

3. Реализация разработанных алгоритмов

Рассмотренные выше алгоритмы анализа зависимостей и распараллеливания были реализованы в виде библиотеки для операционной системы NeurOS /21, 22, 47/. Данная библиотека используется операционной системой при автоматическом распараллеливании программ. Как известно, NeurOS позволяет выполнять программы независимо от того, какие процессоры установлены в системе. На сегодняшний день имеется поддержка для процессоров Intel и NMG403. Однако добавление поддержки новых процессоров не является проблематичным, и достигается за счёт портиро-вания сравнительно небольшого фрагмента кода планировщика на новую платформу.

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

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

Упрощённая блок схема системы распараллеливания приведена на рисунке 3.1.

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

Каждая строка, описывающая зависимость имеет формат: ТИП Н0МЕР1:ПЕРЕМ1 —> Н0МЕР2:ПЕРЕМ2 ВЕКТОР.НАПР где ТИП — тип зависимости, НОМЕР1 — номер строки, содержащей выражение, являющееся источником зависимости, ПЕРЕМ1 — переменная-источник зависимости, НОМЕР2 — номер строки, содержащей зависимую переменную, ПЕРЕМ2 — зависимая переменная, ВЕКТОРНАПР — вектор направления.

Таким образом, пользователь должен набрать программу в текстовом файле с некоторым именем (например, filel.for) и запустить программу анализа зависимостей, danalisys filel.for

После этого в той же директории будет создан файл с именем filel.dep, в котором будет содержаться описание зависимостей и бинарное представление сети Петри.

Рис. 3.1. Упрощённая блок схема системы распараллеливания

Рассмотрим работу библиотеки на примере. Возьмём текстовый файл со следующим содержимым. real а(100,100) real s

S4: s = 2 for i=l to 100 by 2 do for j=l to 100 by 3 do S7: s += a(i,j) + 2 S8: s += a(j,i) - 1 endfor endfor Sll: a(50,50) = s

В результате работы библиотеки будет создан файл, имеющий следующее содержимое (бинарная часть, относящаяся к сети Петри, здесь не приводится) flow 7: s —> 11: s reduce 7: s —> 7: s (0, +) reduce 7: s —> 7: s (+, *) reduce 7: s —> 8: s (0, 0) reduce 7: s —> 8: s (0, +) reduce 7: s —> 8: s (+, *)

Для повышения производительности алгоритма при реализации были использованы следующие приёмы:

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

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

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

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

Библиотека распараллеливания основывается на рассмотренных ранее алгоритмах, использующих элементарные преобразования для распараллеливания тесно вложенных гнёзд циклов и разработанные алгоритмы для распараллеливания тел циклов на основе моделирования сети Петри. Реализация библиотеки распараллеливания осуществлялась на языке программирования С++. Таким образом, удалось провести разработку максимально приближено к стандартным методам. Для переноса на другую платформу потребуется внести незначительные изменения в код. Проектирование алгоритмов, описанных ранее, является тривиальным и здесь не приводится.

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

Для распараллеливания программы в соответствии с алгоритмом на основе элементарных преобразований используется следующий вызов: parallel source.for source.dep target.elf где source.for — исходная программа на языке подобному Фортран, source.dep — файл, содержащий зависимости, target.elf — бинарный файл в формате ELF, содержащий параллельный вариант программы и сеть Петри для интерпретации (если таковая необходима).

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

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

Заключение

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

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

Полученные алгоритмы были реализованы в виде библиотеки для операционной системы NeurOS. Результаты опубликованы в виде статей и тезисов докладов /6, 7, 8, 9, 10, 21, 22/.

Работа выполнялась при поддержке Российского фонда фундаментальных исследований (номера грантов: 00-07-90300. 01-07-90211, 02-0706057, 02-07-0G056).

Основными результатами полученными в работе являются:

1. алгоритм анализа информационной структуры линейных программ;

2. модифицированный обобщённый алгоритм анализа информационной структур ы;

3. алгоритм преобразования сокращённого графа зависимостей в сеть Петри;

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

5. алгоритм динамического распараллеливания линейных участков программ;

G. обобщённый алгоритм распараллеливания;

7. реализация разработанных алгоритмов в виде библиотеки для операционной системы NeurOS.

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

Существующие алгоритмы /25. 2G, 32/ оперируют исключительно на уровне макро параллелизма. Анализ информационной структуры программ выполняется только на уровне тесно вложенных гнёзд циклов. Алгоритмы используют преобразования циклов при распараллеливании и не выполняют оптимизацию порядка следования операторов присваивания. Следовательно, коэффициент распараллеливания упомянутых алгоритмов значительно ниже коэффициента распараллеливания разработанного алгоритма.

Список литературы диссертационного исследования кандидат технических наук Коробко, Алексей Юрьевич, 2006 год

1. Воеводин В.В., Информационная структура алгоритмов, Москва, МГУ, 139 стр., 1997.

2. Francois Irigoin, Minimal Data Dependence Abstractions for Loop Transformations: Extended Version // International Journal of Parallel Programming Volume 23, Number 4, August, pp. 359-388, 1995.

3. Alain Darte, Frederic Vivien, Parallelizing Nested Loops with Approximation of Distance Vectors: a Survey // Parallel Processing Letters, 7(2):133-144, 1997.

4. Michel Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge MA, G70 p, 1989.

5. Воеводин В.В., Воеводин Вл.В., Параллельные вычисления, С-Пб, БХВ-Петербург, 599 стр., 2002.

6. G. Goff, Ken Kennedy, C-W. Tseng, Practical dependence testing // Proceedings of the ACM SIGPLAN '91 Conference on Programming Language Design and Implementation, Vol. 26, Num. 6, pp. 15-29, June 1991.

7. Ачасова С.М., Бапдман O.JI., Корректность параллельных вычислительных процессов, Наука, 1990, 252 стр.

8. Т. Мурата, Сети Петри: Свойства, анализ, приложения // ТИИЭР, Том 77, 1989, стр. 41-85

9. Alain Darte, Yves Robert, Scheduling Uniform Loop Nests, Technical Report RR92-10, Laboratoire de l'lnformatique du Parallelisme, 1992.

10. Alain Darte, Frederic Vivien, Revisiting the Decomposition of Karp, Miller and Winograd // Parallel Processing Letters, World Scientific Publishing Company, Volume 3, pp. 45-57, 1991.

11. Alain Darte, Frederic Vivien, On the optimality of Allen and Kennedy's theory for parallelism extraction in nested loops // Journal of Parallel Algorithms and Applications, Special issue on Optimizing Compilers for Parallel Languages, 199G.

12. William Pugh, David Wonnacott, Going beyond Integer Programming, Technical Report UMIACS-TR-93-132, CS-TR-3191, Univ. of Maryland, 17 p., 1992.

13. Pierre Boulet, Alain Darte, Georges-Andre Sibler, Frederic Vivien, Loop parallelization algorithms: from parallelism extraction to code generation // Proceedings of PACT'96, Boston, MA, October 1996, IEEE Computer Society Press

14. C. Lengauer, Loop parallelization in the polytop model // ACM Toplas, 2, 1994, pp.91-142

15. David F. Bacon, Susan L. Graham, and Oliver Sharp, Compiler Transformations for High-Performance Computing // Computing Surveys, volume 26, number 4, December 1994.

16. L.K. Babenko, A.G. Chefranov, P.A. Fedorov, A.Yu. Korobko, О.В. Makarevich, Operating System for Multiprocessor System Based on NM6403 Microprocessors // Optical Memory and Neural Networks (Information Optics), Vol. 11, Number 2, 2002, pp. 117-121.

17. Wayne Kelly, William Pugh, A Framework for Unifying Reordering Transformation, Technical Report UMIACS-TR-93-134, CS-TR-3193, Univ. of Maryland, 24 p., 1993.

18. Alexander Schrijver. Theory of Linear and Integer Programming, John Wiley and Sons, New York, 89G p, 198G.

19. J.R. Allen, Ken Kennedy, Automatic translations of fortran programs to vector form // ACM Toplas, 9, 1987, pp.491-542

20. Michael E. Wolf, Monica S. Lam, A loop transformation theory and an algorithm to maximize parallelism // IEEE Trans. Parallel Distributed Systems, 2(4), October 1991, pp.452-471

21. R.M. Karp, R.E. Miller, S. Winograd, The organization of computations for uniform recurrence equations // Journal of the ACM, 14(3), July 1967, pp.563-590

22. Hans Zima, Barbara Chapman, Supercompilers for Parallel and Vector Computers, ACM Press, 1990

23. Paul Feautrier, Dataflow analysis of array and scalar references // Int. J. Parallel Programming, 20(1), 1991, 23-51

24. F. Irigoin, R. Triolet, Computing dependence direction vectors and dependence cones with linear systems, Technical Report ENSMP-CAI-87-E94, Ecole des Mines de Paris, Fontainebleau (France), 1987

25. Alain Darte, Frederic Vivien, A comparison of nested loops parallelization algorithms, Research Report N 95-11, 1995, Laboratoire de l'lnformatique du Parallelisme

26. Leslie Lamport, The parallel execution of DO loops // Communications of the ACM, 17(2), February 1974, pp.83-93

27. Paul Feautrier, Some efficient solutions to the affine scheduling problem, part I: one-dimensional time // Int. J. Parallel Programming, 21(5), October 1992, pp.313-348

28. Paul Feautrier, Some efficient solutions to the affine scheduling problem, part II: multidimensional time // Int. J. Parallel Programming, 21(6), December 1992, pp.389-420

29. Alain Darte, Frederic Vivien, Optimal fine and medium grain parallelism detection in polyhedral reduced dependence graphs // Proceedings of PACT'96, Boston, MA, October 1996, IEEE Computer Society Press

30. William Pugh, The Omega Test: a fast and practical integer programming algorithm for dependence analysis // Comm. of the ACM, August 1992, pp.122-140

31. David F. Bacon, Susan L. Graham, Oliver J. Sharp, Compiler Transformations for High-Performance Computing, Technical Report UCB/CSD-93-781, Computer Science Division, University of California, Berkeley, 1993, 79 p.

32. Manoj Kumar, Measuring Parallelism in Computation-Intensive Scientific/Engineering Applications, IEEE Trans, of Computers, vol. 37, no. 9, Sept. 1988, pp 1088-1098

33. Z. Shen, Z. Li, Pen-Chung Yew, An Empirical Study of FORTRAN Programs for Parallelizing Compilers, IEEE Trans. Parallel and Distributed Systems, vol. 1, no. 3, July 1990, pp. 356-364

34. D.J. Kuck. The Structure of Computers and Computation, Volume I, John Wiley, NY, 1978

35. D. Kuck, P. Budnik, S-C. Chen, Jr. E. Davis, J. Han, P. Kraska, D. Lawrie, Y. Muraoka, R. Strebendt, R. Towle, Measurements of Parallelism in Ordinary FORTRAN Programs, Computer, vol. 7, no. 1, 1974, pp. 37-46

36. С. Polychronopoulos, Compiler Optimizations for Enchancing Parallelism and Their Impact on Architectural Design, IEEE Trans. Computers, vol. C-37, no. 8, 1988, pp. 991-1004

37. H. Nobayashi, C. Eoyang, A Comparison Study of Automatically Vectorizing FORTRAN Compilers, in Proc. Supercomputing'89, 1989

38. C. Polychronopoulos, M. Girkar, Parafrase-2: A New Generation Parallelizing Compiler, Int. Journal of High Speed Computing, vol. 1, May 1989, pp 45-72

39. Л.К.Бабепко, А.Ю.Коробко, О.Б.Макаревич, П.А.Федоров, А.Г.Чефрапов, Операционная система и технология программирования для нейрокластера на базе процессоров NM6403, Известия ТРТУ, №1/2002, с.82-83