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

На правах рукописи

Короб ко Алексей Юрьевич

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

Специальность: 05.13.17 — Теоретические основы информатики

Автореферат диссертации на соискание учёной степени кандидата технических наук

Таганоог— 2006

Работа выполнена в Таганрогском государственном радиотехническом университете.

Научный руководитель: Официальные оппоненты:

Ведущая организация:

доктор технических наук, профессор Берштейн Л. С.

доктор технических наук,

профессор

Ромм Я, Е,

кандидат технических наук Троценко Р. В.

Ростовский государственный университет путей сообщения

Защита состоится мин, на за-

седании Диссертационного совета Д-212.259.02 при Таганрогском государственном радиотехническом университете по адресу; 347928, г, Таганрог, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться е библиотеке Таганрогского государственного радиотехнического университета.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы.

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

На протяжении нескольких десятилетий решается задача автоматического распараллеливания программ. Наибольший вклад в развитие данной области внесли: Воеводин В.В., Бандман О.Л., Irigoin F., Kennedy К., Darte A., Wolf М., Lamport L., Feautrier Р.. В результате были сформированы основные принципы функционирования подобных систем, а также были разработаны некоторые алгоритмы распараллеливания. Однако, существующие алгоритмы позволяют проводить распараллеливание лишь циклических операций, в то время как тела циклоп выполняются последовательно.

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

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

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

2. модифицирован алгоритм анализа структуры циклов (Омега-таст) с

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

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

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

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

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

Разработанные алгоритмы анализа структуры программ и их распараллеливания позволяют распараллеливать программы в исходных кодах п автоматическом режиме. Это избавляет программистов от необходимости ручного разбиения задачи на множество процессоров, являющегося трудоёмкой алгоритмической задачей. Кроме того, ручное распараллеливание на практике не всегда даёт желаемых результатов: потенциально распараллеливаемые участки кода могут остаться не замеченными, а листинг программы может стать сложным для понимания, что повышает вероятность внесения ошибок и усложняет процесс отладки.

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

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

ь

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

Внедрение и реализация результатов.

Теоретические и практические результаты, полученные в диссертационной работе, применялись при выполнении работ, поддержанных гранта^ ми Российского <]юнда фундаментальных исследований (проекты №00-0790300, 01-07-00211, 02-07-06057, O2-07-0G05C).

Апробация работы.

Основные результаты работы докладывались на: междуна]>одной научно-технической конференции -«СуперЭВМ и многоп]Х>цессорные вычислительные системы» (Дивноморское, 2002), VI Всероссийской научной конференции студентов н аспирантов «Техническая кибернетика,. радиоэлектроника и системы управления» (Таганрог, 2002), втором международном каучно-практкчйском семинаре «Высокопроизводительные параллели ные вычисления на кластерных системах» (Нижний Новгород, 2002), международной конференции «Informational Systems and Technologies » (IST'02, Минск, 2002), шестой международной конференции «Parallel Computing Technologies» (PaCT'06, Новосибирск, 2001), третьей Всероссийской научной конференции молодых учёных и аспирантов «Новые информационные технологии. Разработка и аспекты применения» (Таганрог, 2000), международной конференции «Интеллектуальные и многопроцессорные системы» (Таганрог, Донецк, 2001), третьей Всероссийской молодёжной школе «Высокопроизводительные вычисления в фюико-химических расчётах» (Черноголовка, 2001).

Была опубликовала статья в журнале «Optical Memory and Neural Networks (Information Optics)» (издательство: Allerfcon Press, Ine).

Структура и объём диссертации.

Диссертация состоит из введения, трёх глав, заключения и списка литературы. Облюём диссертации составляет 118 страниц, в том числе 17 рисунков и 2 таблицы. Список литературы содержит 47 библиографических наименований.

На защиту выносятся:

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

2. метод преобразования матрицы, зависимостей в сеть Петри:

3. обобщаютыП метод анализа информационной структуры программ;

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

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

Работы в области анализа структуры протрамм можно условно разделить не две группы:

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

2. Динамически А йм«.ш — выполняется непосредственно перед работой п]юграммы и/или в процессе выполнения. Позволяет достичь более высоких показателей распараллеливания. Циклические конструкции могут не анализироваться.

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

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

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

Оперирование на уровне инструкций позволяет выявлять микропараллелизм, в то время как анализ итерационного пространства выявляет макро-параллелизм.

Входную программу, содержащую п операторов присваивания, представим в виде множества Р, а переменные (ячейки памяти) в виде множества Ь:

р = ъ)}^ 61 = {1, ...,п},1 е Ь, Я С I и {{0}}. -

где I — переменная, находящаяся до оператора присваивания (1-уа1ие), Н

— множество переменных после оператора присваивания (г-уа!це). Множество Л может быть пустым.

Последовательность инструкций можно представить в виде ориентированного графа, вершина которого соответствует ¿-му оператору присваивания, а дуги задают последовательность С1>абатываний. Вершина ^ получает управление, если осуществлены переходы по всем входящим дугам. Таким образом, такой граф является упрощением сети Петри (марки-1К>ванныЙ граф):

С = (5, Е), в = €1 = {1,2, ...,п}, В = {еЛ, 3 е 3 = {1,2,..., т}.

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

— переменные га множества Ь, по которым (существуют зависимости — истинная, по результату и антн-зависимоеть:

£> = !! = £ £,оу е е ь. ■ ■■

Определим вектор начального состояния: ..О0 = {с^}, i = ^ £ 0,1. *-й элемент этого вектора равен 1, если г-я вершина не зависит ни от одной

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

Для построения графа вычислений требуется проанализировать множили« операторов на наличие зависимостей по потоку данных. Распространим определения зависимостей на операторы.

Оператор присваивания 6 Р истинно зависит от оператора присваивания р4 е Р по переменной 0, если ^ = в, в 6 Д,-. Оператор присваивания р1 £ Р зависит по результату от оператора присваивания € Р по переменной в, если = = в. Оператор присваивания Pi е Р анти-зависит от оператора присваивания р^ € Р по переменной в, если в 6 = в.

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

Алгоритм, 1>еализующий метод, состоит из цикла, в каждой итерации которого осуществляется проверка на зависимость текущего оператора присваивания.

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

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

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

Метод анализа зависимостей между итерациями циклов использует аппарат линейного программирования. Для этого структурные характеристики циклов преобразуются в' множество ограничений равенств и неравенств. На примере показан метод исключения ограничений равенств.

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

Для распараллеливания циклов в диссертации используется техника

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

• преобразования гнезда циклов в идеально вложенное;

• создания подциклоп с меньшим числом зависимостей;

• снижения требования к памяти за счёт сокращения операционных данных:

• сокращения необходимых регистров за счет уменьшения объёмов данных, обрабатываемых циклом.

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

Входными данными задачи распараллеливания являются:

1. сеть Петри, моделирующая зависимости между инструкциями и последовательность их выполнения;

2. начальная маркировка сети Петри;

3. число целевых процессоров.

Циклы в распараллеливаемых программах можно разделит», па два основных пгпа:

• циклы с известными на момент компиляции границами изменения итерационных переменных;

• циклы, имеющие итерационные переменные с неизвестными на момент компиляции границами.

На основе данных критериев приводится детальная классификация циклов. При этом основным определяющим фактором является форма представления ограшгченнй итерационных переменных циклоп.

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

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

1. Все срабатывания итерации р; могут быть вынесены вперёд срабатываний итерации pj, если в сокращенном графе нет зависимости от pj

К Pi.

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

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

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

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

Существует целый ряд преобразований сети Петри, удовлетворяющих поставленному условию. Ниже приведены некоторые простые преобразования сети Петри:

1. операция слияния последовательно соединённых позиций;

2. опе1>ацня слияния последовательных переходов;

3. операция слияния параллельных позиций;

4. операция слияния параллельных переходов;

5. операция исключения позиций с петлями;

. б. операция исключения переходов с петлями.

Таким образом, используя данные преобразования мы можем быть уверенны в выполнении условия сохранения эквивалентности.

Предложены два алгоритма распараллеливания тел циклов на ослов«1 сети Петри — алгоритм статического и алгоритм динамического распараллеливания.

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

Определим степень параллелизма следующим образом:

£ ■ _ Ы(иМеСР

te

где tc — время выполнения эквивалентной программы.

Определим критерий эффективности распараллеливания к", как

^ j CP у

где кр - степень параллелизма; | CP \ - число процессоров в вычислительной системе.

Критерий эффективности распараллеливания показывает кумулятивную загруженность используемых вычислительных узлов. Область значений данного критерия лежит в пределах 0 < ке < 1.

Критерий эффективности не является достоверным в случае выполнения на целевой вычислительной системе более одной программы.

Трстм глав а диссертации посвящена реализации разработанных в работе алгоритмов.

Алгоритмы анализа зависимостей и распараллеливания были реализованы в виде библиотеки для операционной системы NeurOS. Данная библиотека используется операционной системой при автоматическом распараллеливании программ. Как швестно, NenrOS позволяет выполнят!, программы независимо от того, какие процессоры установлены в системе. На сегодняшний день имеется подцержка для процессоров Intel и NM0403. Однако, добавление поддержки новых процессоров ве является проблематичным, и достигается за счёт порти1>ования сравнительно небольшого фрагмента кода планировщика на новую платформу.

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

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

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

В главе приведены методы, использованные для повышения производительности алгоритма при реализации.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

Полученные алгоритмы были реализованы в виде библиотеки для операщгонной системы НешСЙ.

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

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

2. модификация Омега теста, используемого для анализа информационной структуры;

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

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

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

6. обобщенный метод распараллеливания;

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. L.K. Babciiko, A.G. Chcfranov, А. lu. Korobka, O.B. Mokarcirich, Compiler Witt Operating System Integration for SPMD Tasks Code Generation and Execution in Heterogeneous Cluster Systems -'/ «Informational Systems and Technologies (IST~2002) >>, Part 3, Минск, Тин. Б ГУ, стр. 48-53, 2002.

2. L.K. ВаЪепко, A.G. Chefranov, P.A. Fedorov, Л.Ум. КогоЪко. О.В. Makarewh, Mechanisms of Parallel Computing Organization for NeuroCluster // Parallel Computing TVxrlmologies: 6tli international conference; proceedings / PaCT 2001, Victor Malyshkin (ed.), LNCS 2127, 513 p, pp. 181-185.

3. Бабеико Л.К., Коробка А.Ю.. Чефранов А.Г., Федоров U.A., Мака-ревич О.В., О роли компилятора и операционной системы в генерации SPMD задач для гетерогенных систем // СуперЭВМ и многопроцессорные вычислительные системы, Материалы Международной научно-технической конференции, Таганрог, Тип. ТРТУ, 357 стр., стр. 172-178, 2002.

4. Бабенка Л.К., Коробка А.Ю., Чефранов А.Г., Федоров П.А., Макарович О.Б.. Распределенная микроядерная архитектура для проектирования операционных систем // СуперЭВМ и многопроцессор-

■ ные вычислительные системы, Материалы Международной научно-технической конференции, Таганрог, Тип. ТРТУ, 357 стр., стр. 108171, 2002.

5. Коротко А.Ю.. Чефранов А. Г., Операционная система дли параллелг»-ного вычислителя на базе нейропроцессора NMC403 // Новые информационные технологии. Разработка и аспекты применения, тезисы докладов 3-й всероссийской научной конференции молодых учёных и аспирантов, Таганрог, Тип. ТРТУ, 174 стр., стр. 130-132, 2000.

С. Бабенко Л.К., Коробко А.Ю., Чефранов А.Г., Федоров П.А., Мака-рсви-ч О.Б., Операционная система с распределённой микроядерной архитектурой для параллельной нейропроцессорной системы / Тезисы 3 всероссийской молодёжной школы «Высокопроизводительные вычисления в физико-химических расчётах», Черноголовка, 323 стр., стр. 22-27,2001.

7. L.K. Babcnko, A.G. СНфапаг, P.A. Fcdovov.- .-).)«- Korohko, O.B. Maknremch, Opera.t.inji Sutern for MuHiproeessor System Bascd hu NM 6403 Micropmcessoi« 1' Opt.kaJ Мммп- and Neural Networks (Information Opt.ics), Vol. 11, Nunibra' 2, 200*2, pp. 117-121.

8. L.K, Bahe.nko. A.G. Chefranaw, P.A. Fnlarov, A.Yn. Karahka, O.B. Макатстск, Operatinj; System, and Programming Technology for Neurocluster Based on NMG403 Mkroproccssors . / Тезисы докладов международной конкуренции «Имтел.чскту ¡vi i.ht ,то ir шшгощюцгссор-HWfi системы», Таганрог-Донецк. 343 стр.. стр. 237-341. 2001.

0. Коробка А.Ю., Kamtupt И.Г.. Транслятор дли гетс]>огс]П1оП щгтомi>i на базе процессора NMC403 / -' VI Всероссийская нлучиля конкуренция студентов и аспирантов «Техническая кибернетика. радпозлек-трошгка и системы управления*. Тезисы докладов, Тагащотг, Thti. ТРТУ, -140 стр., стр. 342-343, 2002.

10. Коробка А.Ю.. Ковтуи И.Г.. Бабснко Л.К., Чгфуюнов .-1.Г.. Трансляция гт]юграммного кола rt rereiKnvmroii системе ■ • *Омсокппро№ги>-дительиые параллельные вычисления на кластерных системах» материалы второго Международного научно-практического семинара. Нижний Новгород, Изд. НГУ, 352 стр.. стр. 141-147, 2002.

1L Л.К.Бабенка, А.Ю.Корабка, . О.Б.Макаргмич, . П.А.Федоров, .4.Г. 1?сф)хпюв, Операционная система н технология н |>о грамм it-рования для неfii>oкластера на базе п|>оцесоороп NMG-103. Известия ТРТУ, .№1, 2002, C.82-S3

В работах опубликованных rt coanTojxrrne, автору принадлежат следующие. результаты: fl-З] — методы и алгоритмы интеграции операционной системы и распараллеливающего компилятора исходных кодов; [4-8.11| — основные принципы проектирования и реализации операционной системы, поддерживающей функции'динамического и декларативного распараллеливания; [9-10] — алгоритмы анализа информационном структуры программ, алгоритмы автоматического распараллеливания программ.

Соискатель А, Ю. Короб ко

Tu:i<irpíuJ»iIii TaiMiTjxkrt'Koiv «х^сударггпетитого р^ип/л^итчщкого yiiitnppamí-Tíi* Заказ А*Ткргж 100 ък*. 20GG г+

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

Введение

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/ оперируют исключительно на уровне макро параллелизма. Анализ информационной структуры программ выполняется только на уровне тесно вложенных гнёзд циклов. Алгоритмы используют преобразования циклов при распараллеливании и не выполняют оптимизацию порядка следования операторов присваивания. Следовательно, коэффициент распараллеливания упомянутых алгоритмов значительно ниже коэффициента распараллеливания разработанного алгоритма.

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