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

'Гб ОД РОССИЙСКАЯ АКАДЕМИЯ НАУК О 7 Г 01 " Вычислительный центр

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

УЛЬЯНОВ Денис Эдуардович

РАЗРАБОТКА И РЕАЛИЗАЦИЯ СИСТЕМЫ КОНФИГУРИРОВАНИЯ ПРОГРАММ ДЛЯ ТРАНСПЬЮТЕРНЫХ СЕТЕЙ

(специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей)

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

Москва - 1995

Работа выполнена в Вычислительном центре Российской академии наук.

Научный руководитель: кандидат физико-математических наук

A.Н.Бирюков.

Официальные оппоненты: доктор физико-математических наук

B.А.Крюков,

кандидат физико-математических наук

C.СГайсарян. Ведущая организация: НИВЦ МГУ.

Защита диссертации состоится "21" декабря 1995 г. в ^ часов на заседании специализированного совета К 002.32.01 при Вычислительном центре Российской Академии наук. Адрес совета: 117967, ГСП1, Москва, ул. Вавилова, дом 40. С диссертацией можно ознакомится в библиотеке института.

Автореферат разослан ноября 1995 г.

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

Общая характеристика работы.

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

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

- поиск конфигурации для произвольно выбранной программы.

Пель диссертационной работы заключается в исследовании

*

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

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

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

Данная система использует генетический алгоритм для поиска наилучшей конфигурации.

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

Публикации. и_апробации работы, По теме диссертации

опубликовано 5 работ. Основные результаты докладывались на второй конференции / "Транспьютерные системы и их применения" (Домодедово, 1992), на всемирном транспьютерном конгрессе \VTC93 (Ахен, Германия, 1993), на научных семинарах кафедры алгоритмических языков факультета ВМиК МГУ (Москва 1992).

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

Содержание работы.

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

Первая глава содержит исторический обзор и обзор различных систем конфшурирования параллельных программ и стандартных средств описания конфи1урации программ на языке оссаш2. Термин "конфигурирование программ" обозначает . процесс поиска распределения процессов программы (то есть фрагментов ее кода) на процессоры параллельного компьютера. Различают два* вида конфигурирования - статическое и динамическое.

Статическое конфигурирование выполняется перед запуском программы, причем распределение процессов по процессорам остается фиксированным в процессе выполнения программы.

Динамическое конфигурирование, напротив, производится в процессе выполнения программы, то есть распределение процессов по • процессорам может изменяться (и, как правило, меняется) при выполнении про1раммы.

Основное место в обзоре занимают системы для статического конфигурирования. Как правило, такие системы используют представление программы в впде^ одного или нескольких графов, узлы которых соответствуют процессам, душ - коммуникациям между ними. Дуги могут иметь вес - объем коммуникации. В дальнейшем будем называть такой граф 1рафом коммуникации процессов. Сеть процессоров также представляется графом,, узлы. . которого соответствуют процессорам, а дуги соединяющим их линкам (каналам). Будем называть такой граф графом процессоров. Для поиска конфигурации используются методы, основанные на вложении графов -ищется вложение графа процессов в граф процессоров. Решение получается в виде набора рекомендаций, которые должны быть реализованы пользователем. Времена выполнения отдельных процессов и объемы коммуникаций должны задаваться пользователем, и нет никакою средства, позволяющего судить о достоверности их задания. Кроме того, пользователь вынужден "доверять" полученному решению - не существует никакого способа проверить, как быс~ро выполняется программа при выбранной конфигурации, кроме как написа'гь программу, реализующую ее. ' .

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

подходов - они либо встроены непосредственно в программу (выбранная стратегия конфигурирования использует характерные особенности программы) или выполнены как надстройка над операционной системой (используется предельно общий подход и конфшурированне выполняется на уровне единиц выполнения). Если алгоритм динамического Конфигурирования встроен непосредственно в программу, то, как правило, он работает по следующей схеме: входные данные делятся на части, время обработки которых примерно одинаково. И эта данные распределяются между процессами. На каждом процессоре' выполняются одни и те же процессы. Таким образом, балансировка загруженности достигается за счет перераспределения данных. Особенно эффективны такие схемы для задач обрабатывающих много неоднородных данных (обработка изображений). В том случае когда алгоритм конфигурирования встроен в операционную систему, во время выполнения программы возможно динамическое перераспределение фрагментов ее кода между процессорами для балансировки загруженности процессоров системы.

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

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

1. По исходной программе автоматически строится ее промежуточное представление - временная диаграмма. Она используется для определения качества распределения процессов по процессорам (качеством распределения является время выполнения программы при данном распределении).

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

2. При помощи генетического алгоритма осуществляется поиск наилучшего распределения процессов профаммы по процессорам.

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

Ограничения используемого подхода:

- не допускается динамическое порождение процессов;

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

За основу входного языка был взят оссат2, так как параллельные процессы легко Moiyr быть выделены из текста программы, а статическое определение параллельных процессов необходимо при выбранном нами подходе. Кроме того, простой и ясный синтаксис occam'a облегчает анализ программ, написанных на нем. Однако на язык были наложены некоторые ограничения, которые можно разделить на две группы:

1. Принципиальные ограничения:

- не допускается использование конструкции ALT;

- тип канала должен быть задан явно при его описании, т.е. протоколы не разрешаются, при этом тип должен быть или простым, или массивом. Объявления CHAN OP ANY не допускаются;

все переменные и константы в программе должны быть глобальными.

2, Технические:

- все объявления и выражения не должны занимать больше одной строки - перенос на следующую строку не допускается;

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

С точки зрения DYNAMO, любая программа представляется своей временной диаграммой. Эта диаграмма строится для некоторого набора входных, данных, поэтому их выбор очень важен - данные должны быть достаточно типичными или критическими. Для каждого процесса исходной программы. диаграмма содержит упорядоченное множество интервалов, соответствующих временам выполнения отдельных работ и ожиданий процесса. Диаграмма строится в предположении, что программа, выполняется на некоторой "идеальной" сети процессоров, в которой каждому процессу отведен отдельный процессор, и все процессоры соединены между собой (так, чтобы обеспечить прямые коммуникации между процессами). Пример диаграммы представлен на рисунке 1.

На диаграмме сплошные линии соответствуют работам, пунктирные - обменам, отсутствие линии - синхронизации между процессами.

Каждый из процессов Р и R состоит всего из двух работ -ввода(вывода) данных и обмена по каналу. Основные вычисления сосредоточены в процессе Q, который состоит из четырех работ (условный оператор распадается на две работы - вычисление последовательности условий и выполнение соответствующего оператора присваивания).

Про-; цес-сы

R Q Р

Т Х2

1

t5

t3 t4

Рис 1. Пример временной диафаммы.

время

INT a,b,c,d: CHAN OF INT cl, c2: PAR SEQ --$S+ Input(a)

— $S-cl! a

SEQ cl?b IF

b > 0

с := b b = 0

с := 0 b < 0 с := -b

c2! с SEQ c2?d --$S+

Output(*ABS=',d)

— $S-

— process P

-- process Q

- process R

Текст профаммы, временная диафамма которой приведена выше.

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

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

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

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

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

Эта задача очень сложна из-за большого количества процессов и еще большего количества работ в реальных программах. Для того

чтобы облегчить поиск, система DYNAMO распределяет по процессорам не отдельные работы, а целые процессы.

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

- скрещивание (размножение);

- мутации (введение случайных факторов);

- отбор (с учетом желаемой цели).

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

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

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

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

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

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

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

Рассмотрим реализацию генетического алгоритма в системе DYNAMO:

Каждый индивидуум представляется как вектор.

Р= {Р},Р2 v>AK roe л - число процессов,

i<, р, <. число имеющихся процессоров.

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

Скрещивание представляет собой разрезание двух индивидуумов Р и Q в некоторой произвольно выбранной позиции к, в результате чего получаются два новых индивидуума PI и Q1, таких что:

Л={д,А,..

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

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

Деградация популяции может произойти, если появляются индивидуумы, которые не являются допустимыми решениями, или если скрещивание не производит новых индивидуумов.

В настоящее время в системе DYNAMO используется два вида мутаций:

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

являются: "увеличить/уменьшить произвольно выбранное р на единицу", "обменять значения pt и р j для некоторых произвольно выбранных i, j" и т.д. Используя эти мутации достаточно часто, можно не допустить деградации популяции. В то же время эксперименты показали, что обычно этих мутаций недостаточно, чтобы существенно улучшить решение. Это можно объяснить тем, что зачастую наилучшее решение может быть получено только одновременной модификацией нескольких Pj. Подобная модификация является результатом мутации второго вида.

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

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

Для вычисления времени работы каждого процессора система DYNAMO моделирует работу менеджера процессов транспьютера, который выполняет разделение времени между всеми активными процессами (то есть теми, которые находятся в очереди процессов). При этом используется следующая г-хиика: максимальный размер кванта времени выбирается так. что время выполнения каждой работы кратно его длине. Как правило, лот квлпг равен !. Для каждою кианга

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

Т= t0 х (я, +пг / 2), если л, +и2 > 0, ще /0 - длина интервала Т = 0 . в противном случае

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

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

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

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

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

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

После описания тополопш сети процессоров пользователь может задать собственное распределение процессов по процессорам. В этом случае DYNAMO просто вычисляет время выполнения программы на заданной сети при заданном распределении процессов по процессорам. Таким образом, пользователь может сам искать конфигурацию программы, используя DYNAMO только для оценки качества найденного им распределения. Кроме того, этот режим может быть использован для адаптации распределения, полученного системой, то есть если пользователь считает, что найденное распределение слишком неудобно для реализации, он может оценить проигрыш Ш времени выполнения при другом, более "технологичном" распределении. Прн работе в режиме автоматического поиска распределения пользователю в начале предлагается задать группы процессов - процессы нз одной группы всегда будут находиться на одном процессоре. После foro как группы заданы, начинается сам поиск. Как правило, нользовагель должен сам прервать поиск - это объясняется спецификой генетического алгоритма, но, при желании, он может задать критерий окончания поиска - максимальное время выполнений Программы или количество итераций алгоритма, в течение которых качество решения не изменяется.

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

,При работе системы в автоматическом режиме в любой ¿момент времени можно прервать работу н посмотреть лучшее решение ,ра данный момент.

Кроме того, для решения имеется возможность посмотреть д^угутодополнительнуго информацию:

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

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

В работе рассматриваются примеры использования системы Р^^АМО для поиска конфигураций различных программ. Приводятся .примеры подтверждающие правильность выбора способа подсчета .времени выполнения параллельной программы, показано преимущество данной системы перед другими, использующими только общие характеристики программы. Рассматриваются нетрадиционные применения системы - для поиска конфигурации программ для ,гетерогенных сетей, для определения наилучшего способа добавления дополнительной мощности в систему. Часть примеров показывает способы повышения производительности системы - иг пользование метода "разделяй и властвуй" для конфигурирования сложных программ, тонкую настройку параметров, генетического алгоритма для оптимальной работы с конкретной программой.

Заключение.

В диссертации получены следующие основные результаты:

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

1.5

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

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

3. Найден алгоритм для определения времени выпфШийя программы при заданной временной диаграмме, конфигурации cefit процессоров и распределения процессов программы по процессора^. Эксперименты показали что времена выполнения программ, получаемые при помощи моделирования близки k BpCMCiiaiU выполнения программ' на реальной аппаратуре.. .

4. Определен круг задач, которые могут быть ¡эеШейУ при помощи данной системы. Кроме решения основной задачй * Поиска конфигурации программы при заданной конфигурации c'etih система DYNAMO может применяться и для поиска оптимальной способа добавления дополнительной вычислительной Moiiiiibctli в вычислительную систему. Кроме того, система Ш)кет быть использована и для конфигурирования программ для гетерогенных сетей процессоров.

5. Реализована система программирования. $ состав.

реализованной системы входят:, набор средств для Получения

»

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

Основные положения диссертации опубликованы в следующих работах:

1. Бирюков А., Ульянов Д., Фатыхов А. Система автоматизированного поиска отображения ОККАМ-профамм на

транспьютерную сеть.//Транспьютерные системы и их применение. Тезисы конференции. Домодедово, 27-29 июля 1992г.

2. Biriukov A., Fatychov A., Ulyanov D. A practical approach to the mapping problera.//Proc. of the PACTA'92. Barselona, Spain, Sept 21-24 1992.

3. Biriukov A., Fatychov A., Ulyanov D. DYNAMO: A Processes-Processors Mapper for occam2 Programs .//Transputers, aplication and systems./ed. Mike Jane et al. Proc. of the World Transputer Congress (WTC'93), Aachen, Germany, 1993y. IOS Press 1993.

4. Biriukov A., Ulyanov D. Simulation of parallel time-critical programs with the DYNAMO system.//Proc. of the 3rd IEEE Conference on Control Applications. 1994, vol. 2, 825-829pp.

5. Biriukov A., Ulyanov D. Parallel application development with DYNAMO/ЛРгос. of the WoTUO-95. Manchester, UK, 1995y. - IOS Press, 1995.

Подписано в печать 24.10.95 Формат 60/84/16 Объем: 1,5 п.л. Тираж 80 экз. Цена договорная Заказ № 2 8