Содержание к диссертации
Введение
1 Анализ структуры программ 19
1.1 Постановка задачи 19
1.2 Класс анализируемых программ 24
1.3 Трансляция линейных фрагментов в граф зависимостей , . 26
1.4 Преобразование графа зависимостей линейного фрагмента в есть Петри 31
1.5 Анализ тесно вложенных гнёзд циклов 39
1.5.1 Ограничения-равенства 45
1.5.2 Ограничения-неравенства . 49
1.5.3 Алгоритм исключения переменной 49
1.5.4 Получение векторов расстояния и направления . 63
Выводы 66
2 Распараллеливающее преобразование 68
2.1 Постановка задачи 68
2.2 Распараллеливание тесно вложенных гнёзд циклов 8G
2.3 Распараллеливание тел циклов 96
2,3.1 Преобразование сети Петри 96
2.3.2 Трансляция сети Петри в параллельную программу . 99
2.3.3 Параллельная интерпретация сети Петри 100
2.3.4 Критерии оценки 101
Выводы 102
3 Реализация разработанных алгоритмов 103
Заключение 110
Литература
- Класс анализируемых программ
- Преобразование графа зависимостей линейного фрагмента в есть Петри
- Распараллеливание тесно вложенных гнёзд циклов
- Трансляция сети Петри в параллельную программу
Введение к работе
Актуальность темы.
Аппаратная база вычислительных систем постоянно совершенствуется. Что же касается алгоритмического багажа, то он в меньшей мере подвержен изменениям. На сегодняшний день существует множество уже разработанных программ, устраивающих своей функциональностью поль-:ювателея. Подобные программы решают задачи математического моделирования, управления и другие. Проблема возникает в том случае, если лолТкЗОватель решит повысить производительность вычислительного ком* плекса, перейдя на аппаратную платформу, реализующую концепцию многопроцессорности. Разумеется, в этом случае прироста производительности не произойдёт, и программа будет использовать только один вычислительный узел. Для использования ресурсов нескольких микропроцессоров, программное обеспечение должно быть написано в соответствии с определёнными правилами. Параллельное программирование является отдельным направлением, и может оказаться сложным для неподготовленного программиста. Соответственно затраты на перенос ПО резко возрастают.
На протяжении нескольких десятилетий решается задача автоматического распараллеливания программ. Наибольший вклад в развитие данной области внесли: Воеводин В.В., Бандман О.Л., Irigoin F., Kennedy К., Darte A., Wolf М., Lamport L., Feautrier Р.. В результате были сформированы основные принципы функционирования подобных систем, а также были разработаны некоторые алгоритмы распараллеливания. Однако, существующие алгоритмы позволяют проводить распараллеливание лишь циклических операций, в то время как тела циклоп выполняются последовательно.
Согласно работам Воеводина В.В., анализ исходных кодов программ показал, что около 80% времени занимает выполнение циклоп. При этом средняя глубина вложенности циклов составляет около 3.
Целью диссертационной работы является разработка эффектив
ных алгоритмов анализа информационной структуры программ и их ра<>
параллеливания. Для достижения поставленной цели решены следующие
задачи: -
-
разработан алгоритм анализа зависимостей в линейных участках программ;
-
модифицирован алгоритм анализа структуры циклов (Омега-тест) с
целью получения информации о зависимостях на микро-уровне;
3. разработан алгоритм распараллеливания линейных участков про
грамм на микро-уровне, работающий в режимах компиляции и ин
терпретации;
4, внесены необходимые модификации в ачгорптм распараллеливания
тесно пложенных гнёзд циклов (Аллена-Кеннеди) для достижения
работоспособности алгоритма на микро- и макро-уровнях.
Метод исследования заключается в системном подходи к разработке принципов, методов и моделей построения алгоритмов. В диссертационное работе использовались теория графов, теория сетей Петри, методы линейной алгебры, теория множеств.
Научная новизна.
Основным научным результатом диссертационной работы является разработка комплексных методов анализа информационной структуры программ н их распараллеливания на мнкро уровнях. Полученные алгоритмы были интегрированы в аналогичные методы, оперирующие на макро уровне. В результате были получены алгоритмы анализа зависимостей и распараллеливания, позволяющие оптимизировать исходные программы для выполнения на многопроцессорных вычислительных системах как с общей, так и с распределённой памятью.
Практическая значимость.
Разработанные алгоритмы анализа структуры программ и их распараллеливания позволяют распараллеливать программы в исходных кодах п автоматическом режиме. Это избавляет программистов от необходимости ручного разбиения задачи на множество процессоров, являющегося трудоёмкой алгоритмической задачей. Кроме того, ручное распараллеливание на практике не всегда даёт желаемых результатов: потенциально распараллеливаемые участки кода могут остаться не замеченными, а листинг программы может стать сложным для понимания, что повышает вероятность внесения ошибок и усложняет процесс отладки.
Существующие алгоритмы распараллеливания оперируют либо на макро, либо на мнкро уровне. При этом эффективных алгоритмов выявления мнкро параллелизма не известно. Полученные в диссертации алгоритмы/позволяют выявлять параллелизм, как на мнкро, так и на макро уровне.
Алгоритм анализа информационной структуры использует представление зависимостей между вычислительными операциями в виде сети Пет-
ри. Подобное представление позволяет вести распараллеливание на этапе компиляции (статическое) либо непосредственно в процессе выполнения программы (дішамігческое), учитывая наличие свободных вычислительных ресурсов, оптимальное размещение ветвей процесса среди вычислительных узлов и другие специфичные для вычислительной системы факторы.
Внедрение и реализация результатов.
Теоретические и практические результаты, полученные в диссертационной работе, применялись при выполнении работ, поддержанных гранта^ ми Российского фонда фундаментальных исследований (проекты №00-07-00300, 01-07-00211, 02-07-06057, 02-07-00050).
Апробация работы.
Основные результаты работы докладывались на: междунаїюдной научно-технической конференции -«СуперЭВМ и многоп]Х>цессорпые вычислительные системы» (Дивноморское, 2002), VI Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика,. радиоэлектроника и системы управления» (Таганрог, 2002), втором международном научно-практическом семинаре «Высокопроизводителт.ные параллелт.-ные вычисления на кластерных системах» (Нижний Новгород, 2002), международной конференции «Informational Systems and Technologies» (IST"02, Минск, 2002), шестой международной конференции «Parallel Computing Technologies» (РаСТ'Об, Новосибирск, 2001), третьей Всероссийской научной конференции молодых учёных и аспирантов «Новые информационные технологии. Разработка и аспекты применения» (Таганрог, 2000), международной конференции «Интеллектуальные и многопроцессорные системы» (Таганрог, Донецк, 2001), третьей Всероссийской молодёжной школе «Высокопроизводительные вычисления в фюико-химических расчётах» (Черноголовка, 2001).
Была опубликовала статья в журнале «Optical Memory and Neural Networks (Information Optics)» (издательство: AUerfcon Press, Inc).
Структура и объём диссертации.
Диссертация состоит из введения, трёх глав, заключения и списка литературы. Облюём диссертации составляет 118 страниц, в том числе 17 рисунков и 2 таблицы. Список литературы содержит 47 библиографических наименований.
На защиту выносятся:
1. метод поиска зависимостей в линейных участках программ:
2, метод преобразования матрицы, зависимостей в сеть Петри:
-
обобщенны?! метод анализа информационной структуры программ;
-
метод статического распараллеливания линейных фрагментов программ;
-
метод динамического распараллеливания линейных фрагментов программ;
-
обобщённый метод распараллеливания программ.
Класс анализируемых программ
Как уже было отмечено ранее, существует два основных класса методо» анализа структуры программ. В данной работе исследуются методы анализа тесно вложенных гнёзд циклов и линейных участков программ, представляющих собой тела циклов.
Гнездом циклов называют множество циклоп, каждый из которых (кроме последнего) содержит в себе ровно один вложенный цикл.
Под линейным фрагментом программ понимается такая последовательность инструкций, которая записана без использования операторов условных переходов (зависимость по управлению) и конструкций повторения (циклов) /1/.
Основное отличие методов анализа линейных программ и циклических конструкций заключается в объекте анализа. Так, при анализе ли нейных программ объектом анализа является в общем виде инструкция присваивания. При анализе же циклов осуществляется поиск зависимостей между отдельными итерациями. При этом анализ ведётся в итерационном многомерном пространстве, а распараллеливающее преобразование сводится к переходу в другое итерационное пространство.
Оперирование на уровне инструкций позволяет выявлять микропараллелизм, в то время как анализ итерационного пространства выявляет м акро-параллел из м.
Известно, что распараллеливание на уровне микро-параллелизма эффективно лини» в том случае, если целевая платформа представляет собой многопроцессорную систему с общей памятью /8/. Именно на такой класс систем и сделан упор в данной работе. Это обусловлено тем, в настоящее время большинство производителей развивает собственные микропроцессоры в направлении многоядерности, когда на одном кристалле размещается несколько отдельных микропроцессоров либо иных вычислительных узлов.
Входную программу, содержащую п операторов присваивания, представим в виде множества Р, а переменные (ячейки памяти) в виде множества L: где I — переменная, находящаяся до оператора присваивания (1-value), R — множество переменных после оператора присваивания (r-valuc). Множество R может быть пустым.
Последовательность инструкции можно представить в виде ориентированного графа, вершина S{ которого соответствует г-му оператору присваивания, а дуги задают последовательность срабатываний. Вершина S; получает управление, если осуществлены переходы по всем входящим дугам. Таким образом, такой граф является упрощением сети Петри (маркированный граф): Определим вектор начального состояния & = { kh г = п, d є 0,1. г-й элемент этого вектора равен 1, если г-я вершина не зависит ни от одной другой вершины. Таким образом, вектор началі.ного состояния указывает номера вершин, которые запускаются первоначально /23/.
Для построения графа вычислений требуется проанализировать множество операторов на наличие зависимостей по потоку данных. Как уже указывалось ранее, можно выделить три типа зависимостей по потоку данных: истинная, апти-зависимость и зависимость по результату. При этом только один тип зависимостей (истинная) требует достаточно сложных преобразований для устранения. Остальные же могут быть устранены путём замены переменной. Распространим определения зависимостей на операто-ры /И/. Определение 1. Оператор присваивания pj є Р истинно зависит от оператора присваивания р; Є Р по переменной в, если к = 0,0 Є Щ. Определение 2. Оператор присваивания р,- є Р зависит по результату от оператора присваивания Pj Є Р по переменной 0, если k = lj - 0.
Определение 3. Оператор присваивания рі Є Р анти-зависит от оператора присваивания pj Є Р по переменной $, если и Є Itj, lj — сЛ
Алгоритм автоматического распараллеливания линейных программ заключается в итерационном анализе множества операторов присваивания Р /7, S/. Результатом работы алгоритма является матрица зависимостей программы. Для переменной 0 определим следующие атрибуты: Vi(0) — номер последнего оператора присваивания, в левой части которого встречалась переменная в; Ц(9) — номер последнего оператора присваивания, в правой части которого встречалась переменная 9:
Преобразование графа зависимостей линейного фрагмента в есть Петри
Так как сеть должна моделировать структуру программы на уровне зависимостей, то необходимо организовать связи между переходами, представляющие найденные зависимости. Следовательно каждой найденной зависимости должна соответствовать одна позиция сети Петри. Кроме того, необходимо наличие двух дополнительных позиций, задающих начальное Wstart и конечное wS(op состояния, по определению сети Петри. Итак, множество состояний можно определить как П= { start,OJstop} U {iJij \ рі Є P,pj Є Pyditj {Ф, ,Ф)}, где Я — множество операторов присваивания распараллеливаемой программы; d{j — элемент матрицы зависимостей ] D ], представляющий тройку переменных, по которым существуют зависимости между операторами S{ И Sj.
Множество потоковых отношений Ф сети Петри, можно получить из матрицы зависимостей D ] следующим образом:
для всех пар операторов присваивания pi и pj, для которых существует зависимость (т.е. dij ф (0,0,0), где d;j — элемент матрицы зависимостей D ), добавим пару потоковых отношений между по-зи7щей ujij и переходами ф{ и фу.
для всех операторов присваивания pit не имеющих зависимостей от других операторов присваивания (т.е. входящих в вектор начального состояния — щ ф 0), добавим потоковое отношение между начальной позицией сети Петри Шеи и соответствующим оператору pi переходом V»:
для всех операторов присваивания рі, от которых не зависит тій один другой оператор присваивания (т.е. d % = (0,0,0) для любого к = 1, гг.), добавим потоковое отношение между соответствуют!(ИМ
Оператору pj перСХОДОМ 1р{ И КОНечНОЙ ПОЗИІШеЙ СЄТИ Петри Wstop Ф " = {{ip»b stop) \piP 8k,i = 0, к = Т п}. Множество потоковых отношении сети Петри формируется путём объединения множеств Ф , Ф" и Ф" следующим образом: Ф = Ф и Ф" и Ф ".
Так как условием выполнения оператора присваивания является выполнение одного (или более) предшествующего по зависимости оператора, то соответствующее потоковое отношение должно иметь единичный вес: Ш {ЮІ\Ь)І = 1,І = 1,\Ф\}. Таким образом, сеть Петри является ординарной /12/.
Для удобства анализа, в сети Петри была задана единственная начальная позиция, имеющая потоковые отношения со всеми операторами, входящими в вектор начального состояния. Таким образом, начальная маркировка сети Петри должна определять наличие фишек лишь в тіачальиой позиции bJstart- Число фишек определяется как сумма единичных элементов вектора начального состояния. Следовательно определим начальную маркировку как MQ:
Следует заметить, что вектор начального состояния может быть преобразован в начальную маркировку и иным образом, более точно приближенным к понятию вектора состояния. В таком случае необходимо переопределить множество позиций, потоковых отношений и началыгуто маркировку следующим образом: П = К І Рі Є Р} U {iOstop} U {Wy \piGP,Pj Р, dtj ф 0,0,0)}, М0 {ті\г= lJP \,Pi Є P,mJ - d?}. Примечание. В данном параграфе был показан метод преобразования матрицы зависимостей и вектора начального состояния в ординарную сеть Петри. Однако, как было показано ранее, элемент матрицы зависимостей представляется собой тройку переменных, по которым существует зависимость отдельного типа: истинная зависимость, зависимость по результату и анти-зависимость.
Распараллеливание тесно вложенных гнёзд циклов
Циклы в распараллеливаемых программах можно разделить на два основных типа: циклы с известными на момент компиляции границами изменения итерационных переменных; циклы, имеющие итерационные переменные с неизвестными на момент компиляции границами.
Однако, можно провести классификацию циклов на основе более формальных критериев. Также необходимо указать влияние наличия каждого типа циклов в распараллеливаемой программе на возможно достижимую степень параллелизма. Основным фактором при классификации являются: возможность определения границ изменения итерационной переменной цикла и форма, которую данные границы могут иметь. Под формой границ понимается форма возможного их описания.
1. Аффинные циклы. Границы изменения итерационной переменной у таких циклов описываются аффинными выражениями, содержащими индексные переменные внешних циклов. То есть, границы изменения итерационной переменной цикла зависят от конкретной итерации множества внешних циклов. FOR і = О ТО a DO FOR j = О ТО і + 5 DO ENDDO ENDDD
2. Замкнутые циклы. Если цикл вместе с внешними по отношению к нему циклами порождают некоторое замкнутое множество значений индексных переменных, то такому множеству циклов соответствует эквивалентное гнездо циклов, которое может быть преобразовано в пространственно-временное разбиение. То есть, одна из индексных переменных эквивалентного гнезда циклов принимается за модели-ругощуга переменную времени, в оставшиеся разбивают множество итераций по вычислительным узлам (пространству). К сожалению, не существует известного подхода к выявлению подобных циклов. FOR і = О ТО п DO FOR j = О ТО SQRT(i) DO
Следует заметить, что существует множество работ в этой области, являющихся методами нелинейного анализа /43, 44/, но все известные алгоритмы предназначены лить для выявления зависимостей. Техника, описанная в работе /43/ позволяет преобразовать полиномиальные границы изменения индексной переменной в кусочно-линейную функцию. В некоторых случаях это позволяет преобразовать цикл данного класса в обыкновенный FOR цикл. В обттіем же случае не существует обобщённой модели для обработки циклов данного класса.
3. Обыкновенные FOR циклы. Данный класс циклов является наиболее обширным. Он включает FOR циклы, границы изменения индексных переменных которых не известны в момент компиляции, однако точно определены перед непосредственным выполнением циклов. Границы изменения индексных переменных представлены арифметическими выражениями и зависят от внешних по отношению к циклам переменных и параметров.
Необходимо заметить, что в силу семантики FOR циклов, появление индексной переменной в верней границе ее изменения не оказывает влияния па выполнение цикла, так как границы вычисляются один раз (перед выполнением цикла).
Если цикл данного класса входит в гнездо циклов, то в обтцем случае итерационное пространство не является непрерывным (сканируемым), что приводит к невозможности непосредственного распараллеливания. Для устранения этого ограничения используют обобщённое итерационное пространство, являющееся надмножеством исходного, а точки, не входящие в оригинальное пространство, просто игнорируют.
4. Статические WHILE циклы. В большинстве WHILE циклов верхняя граница также является известной на момент выполнения цикла, но все же она не задаётся явно в виде арифметического выражения, а представлена логическим условием. Данное логическое условие вычисляется перед началом каждой итерации. Соответственно в таких циклах существуют зависимости по управлению между последовательными (соседними) итерациями.
Трансляция сети Петри в параллельную программу
Рассмотренные выше алгоритмы анализа зависимостей и распараллеливания были реализованы в виде библиотеки для операционной системы NenrOS /21, 22, 47/. Данная библиотека используется операционной системой при автоматическом распараллеливании программ. Как известно, NeurOS позволяет выполнять программы независимо от того, какие процессоры установлены в системе. На сегодняшний день имеется поддержка для процессоров Intel и NM6403. Однако добавление поддержки новых процессоров не является проблематичным, и достигается за счёт портиро-вания сравнительно небольнюго фрагмента кода планировщика на новую платформу.
Алгоритмы распараллеливания на уровне исходных кодов лучше всего подходят для использования в гетерогенных многопроцессорных системах, В то же время, те же идеи можно использовать и по отношению к объектному коду. В разработанной системе трансляция выполняется в байт код, который выполняется и распараллеливается операционной системой.
Все разработанные в работе алгоритмы реализованы в виде библиотеки. Это позволяет встраивать код в различные системы распараллеливания, анализа, трансляции и другие. Численные результаты получены в ходе анализа исходных программ на языке близком по синтаксису к Фортрану. Выбор Фортрана обусловлен тем фактором, что большинство программ, реализующих алгоритмы численных методов и математического модели рования, написаны именно на этом языке программирования. При этом время, занимаемое выполнением тесно вложенных гнезд циклов, составляет до 80% общего времени.
Упрощённая блок схема системы распараллеливания приведена на рисунке 3.1.
Для тестирования библиотеки было разработано тестовое приложение, принимающее на вход имя файла, содержащего исходную программу па языке подобном Фортрану. На выходе строится файл, содержащий зависимости, их типы и вектора направлений, а также сеть Петри в бинарном виде.
Каждая строка, описывающая зависимость имеет формат: ТИП Н0МЕР_1:ПЕРЕМ_1 — Н0МЕР_2:ПЕРЕМ_2 БЕКТОР.НАПР где ТИП — тип зависимости, НОМЕР_1 — номер строки, содержащей выражение, являющееся источником зависимости, ПЕРБМ_1 — переменная-источник зависимости, НОМЕР_2 — номер строки, содержащей зависимую переменную, ПЕРЕМ_2 — зависимая переменная, ВЕКТОР_НАПР — вектор направления.
Таким образом, пользователь должен набрать программу в текстовом файле с некоторым именем (например, filel.for) и запустить программу анализа зависимостей, danalisys filel.for
После этого в той же директории будет создан файл с именем filel .гїер, в котором будет содержаться описание зависимостей и бинарное представление сети Петри.
Для повышения производительности алгоритма при реализации были использованы следующие приёмы:
1. Ограничения-равенства и ограничения-неравенства представляются в виде векторов коэффициентов. Кроме того, так как алгоритм имеет дело только с целочисленными значениями, то переменные с плавающей и фиксированной точкой, требующие большего времени счета, не используются.
2. После устранения ограничения-равенства из задачи, осуществляется проверка на наличие переменных, не имеющих верхней или нижней границы. Назовём такие переменные неограниченными. Вместо выполнения исключения неограниченной переменной, удаляем все ограничения-неравенства, содержащее эту переменную. После этого необходимо проверить, не появилось ли новых неограниченных переменных. Если такие переменные появились, то повторяем процесс.
3. Затем необходимо нормализовать ограничения и добавить ключ хеширования. Хеширование позволяет осуществлять поиск ограничения за минимальное время. Также добавляется ключ ограничения, основанный на значениях коэффициентов при переменных. Два ключа ограничений равны только в том случае, если два ограничения отличаются только постоянным членом. Эти ключи могут быть как положительными, так и отрицательными. Если ключи двух ограничений равны по модулю, но отличаются знаком, то значения коэффициентов при переменных обоих ограничений равны, по противоположны. Ключи ограничений и ключи хеширования используются совместно.
4. В процессе нормализации необходимо осуществлять проверку на наличие во всех ограничениях только одной переменной. В этом случае дальнейшие вычисления проводить не следует и можно считать, что задача имеет решение.
Библиотека распараллеливания основывается на рассмотренных ранее алгоритмах, использующих элементарные преобразования для распараллеливания тесно вложенных гнёзд циклов и разработанные алгоритмы для распараллеливания тел циклов на основе моделирования сети Петри.
Реализация библиотеки распараллеливания осуществлялась на язы кс программирования C++. Таким образом, удалось провести разработку максимально приближено к стандартным методам. Для переноса на другую платформу потребуется внести незначительные изменения н код. Проектирование алгоритмов, описанных ранее, является тривиальным и здесь не приводится.
Однако, следует отметить, что реализованное программное обеспечение не является законченным продуктом и призвано лишь продемонстрировать основные возможности автоматического распараллеливания программ в гетерогенных многопроцессорных системах.
Для распараллеливания программы в соответствии с алгоритмом на основе элементарных преобразований используется следующий вызов: parallel source.for source.dep target.elf где source.for — исходная программа на языке подобному Фортран, source.dep — файл, содержащий зависимости, target.elf— бинарный файл в формате ELF, содержащий параллельный вариант программы и сеть Петри для интерпретации (если таковая необходима).
