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

АКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ п КИБЕРНЕТИКИ МОСКОВСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА им. М.В.ЛОМОНОСОВА

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

Чочид Георгий Антонович

УДК 519.68

^следование и разработка коммуникационных средств в многопроцессорных вычислительных системах

05.13.11. Математическое и программное обеспечение вычислительных машин, комплексов, систем п сетей

Автореферат

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

Москва - 1994

Работа выполнена в Отделе вычислительной техника в, киформатЕкв И статута высоких температур РАН.

Научный руксьаднтель: доктор физ,-ыа.т. паук, профессор Ю.Ц. Боглаа

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

Р.П. Сыеляаскнд кандидат технических каув * Й.А. Степаиовская

Ведущая организация - Московский физико-технический институт. Зашита диссертации состоится

10Ш Г

// . часов на заседании Специализированного совета Л 053.05.33 Моско ского Государственного Университета им. М.В. Ломоносова по адресу: 11989 Москва, Ленинские Горы, МГУ, ф-т ВМиК, ауд. 685.

С диссертацией ыожио ознакомиться в библиотеке факультета ВМпК МП

Автореферат разослан * ^ » ^— 1994 г.

Ученый секретарь

Специализированного сон£та Д 053.05.38 „

проф. ¿Жи^. Трифон«» Н.1

Научное объединение "ИВТА11" Российской академии наук, 199^ г.

У к i уалыюсть темы.

цггва коммуникации в многопроцессорных слагемах могут бичь предел а-1Ы в виде трехуровневой иерарх,ин. illa нижнем уровне расположены апла-iue средства, возможности которых определяются архитектурой мичпсли-.ной 'системы (ВС). Следующий уровень составляют базовые или систем-средстла. Верхний (пол ькша W-'i ьск и и) уровень образуется совокупностью ггрументалышх средств, непосредственно используемых нри ipai,pa6o i ке паяльных программ.

1 практической (работе мы использовали два типа многопроцессорных си-многопроцессорный комплекс на базе матричны>. процессоров Е('-2?06 « кпьюг» рную сеть. Jl.'iя норной системы оба верхних уровня иерархии иракски отсутствовали, что инициировало наши разработки по ihx создаиию. нспьютерные системы обладают удобными средствами, такими как я'шгк \АМ, параллельные версии -языков Фортран и Си, для вваимодействия шро-ов расположенных в смежных узлах сети. Использование этих средств для шизации взаимодействия удаленных процессов значительно более -прудоем-К|н)ме тот. разрабатываемая параллельная «цмграмма часто становится 1вязанной" к фиксированной топологии сети и труднопереносимой -на дру-топологии и многопроцессорные ВС.

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

1есмотря на известные отличия, обе многопроцессорные системы могут ь отнесены к классу многопроцессорных систем с распределенной памя-. Обе рассматриваемые системы обладают большими стартовыми захра-и процессорного времени на инициирование ввода/выв< ча, для обеих при-«ют методы крупнозернистого распараллеливания.

Здной из ин череснейших, но пока нерешенных проблем в отношении систем о класса, о<чается проблема с[м?дств автоматического распараллеливания, н из алгоритмов автоматического распараллеливания, названный 'Earlieast ; First (ETF), был предложен Hwa^g J.J. et al. в 1989г.. В отличии от ¡шествующих алгоритмов, он принимает в расчет затраты, обусловленные

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

В настоящее время в мире ведутся активные исследования по созданию " версальной" параллельной ВС. На абстактном (верхний уровень иерар: уровне такую универсальность обеспечивает параллельная машина с пр вольным доступом к памяти (ПМПДП). Для достижения универсальности п лагаетгя модифицировать архитектуру ВС (нижний уровень иерархии), та образом, чтобы он мог эмулировать работу ПМПДП. Исследование нозмо; сти аффективной эмуляции ПМПДП с использованием ВС с распределе! памятью имеет целью нахождение архитектур ВС, алгоритмов маршрутизг сообщений, соотношений параметров, таких как, быстродействие процесс время обслуживания запроса в памяти и в канале и т.д.. которые оптим руют производительность. Эти исследования актуальны для разработок ми процессорных систем следующих поколений.

I

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

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

3. Разработка метода и программного обеспечения распараллеливания з, чн на многопроцессорном комплексе ЕС-НШ. ЕС-2700 в режимах ОН

и МКМД.

4. Исследование эффективности применения алгоритма автоматического распараллеливания ETF к вычислительным системам с распределенной памятью со значительными затратами на взаимодействие процессов.

5. Изучение эффективности эмуляции модели параллельной машины с произвольным доступом к памяти системами с распределенной памятью.

аучвая новизна.

1. Разработан алгоритм парного взаимодействия процессов, сочетающий конвейерный принцип и использующий р^рер^о-деез^висимые пути при передаче одного сообщения. Алгоритм црподиУРТ фиксированное число буферов ввода/выводу (произвольного рг^мрра) fl еффадяру порядок ijo-ступления сообщений 9 процесс np^P^HH^i роответстйУШШ ЩШЬУ их отправления. Алгоритм CBCsfkinei) от ТУП))*108-

2. Рассмотрена задача нахождения о^онцрро дерева носа juin рассылки данных oi одного процесса к груд[}р. Др[<ада^р, 4TQ задача apj|x-етса NP полной.

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

4. Изучена производительность моделей многопроцессорных систем с распределенной памятью, при эмуляции i>Mfi модели |ПМРДП, КАК ^¡унк^иа быстродействия процессора н памяти, числа независимых доекоррелигю-ванных параллельных процессов на процессор для тополргий: гиперкуб, гиперкуб из циклов, тор, сеть всепзможных соединений.

Практическое значение

Разработана система пересылки сообщений в транспьютерной сети, обеспеч« вающая возможность взаимодействия процессов, расположенных в произвол« ных узлах сети, гарантирующая коррскность выполнения ранее разработанны (корректных) транспьютерно-ориентированных программ на произвольном т< пологии процессорной сети с сохранением семантики взаимодействия процесс« Разработан параллельный программный интерфейс для многопроцессорш го комплекса ЕС-1037, ЕС-2706, обеспечивающий возможность одновременно! использования произвольного числа матричных процессоров ЕС-2706 при peiui нии одной задачи в операционной системе Виртуальных Машин (Подсистем Диалоговой Обработки).

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

Апробация работы. Результаты диссертации докладывалис., на 5"4 Московскс

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

тики и вычислительной техники (г. Москва, 1986г.), на Всесоюзном семина)

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

Москва 1986г.), и на 7м Британском семинаре по производительности вычисл:

тельных систем (г. Эдинбург 1991г.).

Публикации. По теме диссертации опубликовано 11 работ.

Структура и объем работы. Диссертация состоит из введения, четырех глав

заключения, содержит 134 страницы машинописного текста, 27 рисунков, сп

сок литературы Из 148 наименований и приложение.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

Первая глава диссертации посвящена анализу временных затрат на пересыл] сообщений в процессорной сети, рассмотрению алгоритмов, лежащих в осно разрабиганной СПС для транспьютерной сети. В ней анализируется структ ра процесса маршрутизатора и формулируется язык описания конфигураш (Я0К)[11).

U

Рассматриваются следующие типы взаимодействия процессов: парное вза-иоДествие, рассылка данных от одного процесса к произвольному подмноже-гву гароцесеоа и сборка данных от произвольного подмножества процессов в шом. Яри сборке выполняется поэлементное объединение сообщений с исполь-такием ассоциатяеэтэго а дистрибутивного оператора такого, как сложение, ыножеине, логячегчае операции "И*, "ИЛИ" и сложение по модулю 2. Целе-хзбразность введения операций рассылки н сборки обусловлена тем, что они асто нсйользуютса в вычислительных алгоритмах, например, при решении 1Стем линейных алгебраических уравнений "методом И) разложения и не »ф-ективностыо ах эмуляции парным взаимодействием.

Для парного взаимодействия процессов были разработаны конвейерные пгорнтмы пересылки по единственному пути и с использои; пнем реберно-езавнснмых путей. Пусть С — (V, Е) есть граф, сопоставляемый многопро-ессорвон сети н 5а = е,,, ...,еак е., 6 Е, г = I,Л; путь в грнфе длиной к. Два у ги 5а н 5» с длинами к и д реберно-независимы, ггли

е., П ек, = 0, 1 < I < к, \ <] <я.

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

.'еорема 0.1 Алгоритм пересылки с использование.-.! рсберно-независимых путей обеспечивает порядок поступления сообщений в процесс приемник, со-тветствунпций порядку иг отправления. Алгоритм свободен от тупиков и спользуст фиксированное число буферов ввода/вывода (про'Мвольного ра.ше-а).

1ля сохранения порядка поступления блоков, принадлежащих разним го-Стенном используется уведомление "конец сообщения'1, рассылаемое по сем ребрам (каналам), выходящим из вершины и принадлежащим реберио-езависимым путям. Блоки сообщений "вижутся по сети одновременно.

Приведем соотношения времени пересылки сообщения (ЫйЖмяя грань) пр парном взаимодействии с использованием трех различных алгоритмов. Испол! чуется следующий набор параметров: А - стартовые затраты, в - Пропуски; способность канала, I - длина сообщения, И - ¿.1нна маршрута, т - числь блоке (пакетов), на которое разбито сообщение. Про£тал (оДноблоМйая) переШ.^ка, -

и = ё{\ + 01). (

Конвейерная с использованием одного пути,

^ = + + 1). (:

При использовании блоков оптималЬИсНэ размера это выражение заНЙгЫМНч как

Конвейерная с использованием к ре бе ¡лю-независимых путей

Оптимальный размер блока равен ' •

<

Время пересылки при использовании блоков оптимального размера, ш„

с

Установлено условие

РЧтТ>{к- 1)А, С

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

Из (':) и (6) можно заключить, что предлагаемый алгоритм обеспечива« сокращение времени до к раз по отношешно к конвейерной пересылке по одно\

ijwifjyry, и до èk по .к ijppcToÈi пересылке, при выполне нии условий-

X. . • ,

.- • 'v. . , •

Сранива»^) я (6), при бЬдьщух .расс^о^^ях J можим «Одеть, что и предпо-жеюм равных стартоадх затрат А оба алгоритма цмеют одинаковую аелм-*>тику. *

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

Разработанная СПС .состоит из двух компонент: транслятора ЯОК и про-сса маршрутизатора. ЯОК определяет топологию сети, размещение Hjwum'OB Процессорам, декларирует взаимодействующие процессы, устанавливаем тин горитма маршрутизации, используемого f;pn р')аН"Ш1епстви||. Как результат ансляции ЯОК, генерируется таблмда маршрутцзащщ. Пользователю СПС »■доставляется возможность выбора алгоритма: дибо адррритм пересылки по инственному пути, либо с использованием независимых путей. В ле|>вом сду-? синтаксис ЯОК допускает явно? определение пути, как последоватездюги пов простой цени. По умолчанию СПС находит один из краТЧИНИЫХ путей учайным образом. Для нахождения множества кратчайших путей исполиу-гя алгоритм поиска а ширину. Поученная таблица маршрутизации.пересы-ется каждому процессу маршрутизатору на этапе загрузки сети. В процессе боты таблица маршрутизации не модифицируется. Процесс маршрутизатор резидентен в каждом узле и принимает участие во ?х взаимодействиях процессов друг с другом. На логическом уровне, взаимо-icTBue процессов осуществляется в соответствии с концепцией, предложенной аром - через канал. Любая пара процессов может иметь пронзврльное число 1авнсимых каналов для взаимодействия. Взаимодействующие процессы /' и гнческие каналы С могуг быть сопоставлены графу С'р = (Р,С), аналогично, ацессорная сеть представила'связным графом G = (V, Е) процессоров - V и паратных каналов-- Е. СПС допускает произвольное отображение Р на V к тнтнрует однозначность выполнения корректной параллельной программы я любого отображения.

Процесс маршрутизатор образуется совокупностью взаимодействующих процессов четырех Типов:

1. со-процесса взаимодействия с процессом отправителем в данном узле,

2. со-процесса взаимодействия с процессом приемником в данном узле,

3. со-процесса ввода данных по аппаратному каналу,

■t. со-процесса вывода данных по аппартному каналу.

Каждому процессу отправителю или приемнику в маршрутизаторе cooti ствует отдельный со-процесс 1 или 2 соответственно, взаимодействуют» ним но программному каналу. Каждому аппаратному каналу соответств пара со-процессов 3 и 4, взаимццейс. аующал с маршрутизатором соседнего у:

Приводятся алгоритмы взаимодействия со-процессов и доказывается, чт

1. Взаимодействие со-процессов, образующих процесс маршрутизатор свобо. от тупиков. *

2. Маршрутизатор обеспечивает пересылку сообщений между отправителе приемником при любом расположении взаимодействующих процессов в сет!

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

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

использовании дерева рассылки минимального веса, в котором каждому ру (шагу пересылки) присваивается единичный вес. Докалывается что:

>рема 0.2 Задача нагожденил остовного дерева рассьики мипимильнп.а а яь.иетс* Л'Р полной.

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

>рая глава иосвяшена рагсмот]>ению моделей многопроцессорных систем с пределенной памятью: гиперкуб, гиперкуб из циклов, тор и сеть нсежнмож-; соединений между парой процессор-память. Каждый узел сети состоит >11 |Цессора. аппаратного маршрутизатора и двух классов памяти: программ и них. Общая память ПМПДМ размером Л/, разбивается на N частей, где Л' цело узлов сети так, что каждый узел содержит Л//Л' ячеек обшей намягп. ждый процессор в состоянии сгенерировать запрос к прчтнч.чьнчй ячейке 1яти данных, расположенной в одном из процессоров сети. Для уменьшения флнктов по доступу к одному банку памяти последовательные логические >еса отображаются в физические с применением динамического хсшицова-I адреса. Для этой цели используют функции из класса Н

сь х - логический адрес, А(х) 6 Я - хэш функция из класса, М - максималь-й размер памяти, N - число процессоров в сети Р - простое число большее

Введенные функции обеспечивают равномерное распределение последова-1ьных логических адресов по процессорам, близкое к случайному. Физический эес.'представи..! парой (и(х),т(х)), где г(т) - номер узла, т[х) - локальный >ес внутри узла. Запрос к памяти есть структура из трех полей: фнзическо-адреса, управляющей информации (чтение/запись) и поля данных. Запросы гжутся к месту назначения в соответствии с алгоритмом маршрутизации, '»менялась маршрутизация по случайному кратчайшему пути. В результате исследования найдено соотношение параметров: быстродей-вие процессора при фиксированном времени доступа к памяти, и времени

а, € ¿0\С €

задержки запроса в канале, которое максимизирует* производительность. 11} . изводительность понимаете* как число с ге н е р и ровай и fa х iV удовлетворен«! запросов к общей памяти. Обращеиие различиях nponWtopliB к общей4 па* ти полагается некоррелированном. Быстродействие npotitvcopa моделирует средним временем, необходимым для генерации запроса' к обше'й памяти:

Для описанных выше архитектур проведено изучение того, какое влияв на производительность оказывает наличие в процессоре р > 1 независим! процессов, что известно как пароли fUbii'aJ' избыточность. В этом случае, пр цессор может сгенерировать не более р независимых запросов к памяти, пос чего наступает его блокировка (до поступления первого обслуженного запро из памяти).

Найдено аналитическое выражение для производительности в приближен! слабозагруженной сети, в котором среднее время ожидания в очереди к кана. и к памяти много меньше времени обслуживания запроса в канале и в памят Такая ситуация имеет место при р = 1. Шкло обслуженных запросов к обии памяти в единицу времени на один процессор равно

где Sunk, Smem ~ время обслуживания запроса в канаЛе и' паМти, D(i) - к личество узлов в сети на растоянии i от рассматриваемого, v - среднее в pel генерации запроса к памяти. Выражение (8) проверялось' численным эксперт ментом. Для рассматриваемых топологий предсказания'производительности использованием этого выражения имели относительную ошибку менее десят процентов.

Все перечисленные архитектуры моделировались с использованием *зы* Симула-67, пакета DEMOS, на рабочей станции Sun-j [10].

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

Для модели сети всевозможных соединений (СИС) разработан аналитнч< ский метод предсказания производительности'с использованием, цепей Маркс па г дискретным временем [9]. Найдены правила вычисления коэффициенте:

V0

»трицы переходов, вычислены предельные вероятности состояний, найдены ia-штические выражения для производительности ряда моделей этого класса.

При нахождении коэффициентов матрицы переходов применена группи|ювкп ■стояний, инвариантных относительно преобразований симметрии в классы вивалентности. Показано, "то введение классов эквивалентности позволяет «еньшить порядок системы линейных уравнений от 0(2"')- до 0(2" ,09,0'п).

Аналитически предсказанная производительность моделей СНС согласует! *

i

численным экспериментом в пределах погрешности моделирования. эетья глава.

этой главе анализируется эффективность алгоритма автоматического рас-раллеливания ETF w рассматривается возможность его использования лт югопроцессориых ВС с распределенной памятью, со значительными старто-|ми затратами.

Распараллеливаемая задача представляется множеством подзадач Т. На Т релелен частичный порядок, посредством отношения предшествования: если í t', t,t' € Т. то /' вычисляется по окончании вычисления t и получения от необходимых данных. На множестве Т определена функция, rj(t,t'), сопоста-яемая объему данных, пересылаемых между t и /'. На множестве процес соров определена функция <т(р,р'). р.р' € Р, сопоставляемая времени пересылки >бшения единичной длины между р н ;/. Множество подзадач представихю в зе ориентированного ациклического графа (ОАГ) Gj = (Т,<), где < - от-нение предшествования. В качестве Gj использовался ОАГ, известный, как 1Ллпантовий размерности г» х п — |Т|. Положение подзадачи в графе опреде-■тся парой декартовых координат 1 < i,j < п. Частичный порядок в графе оделяется соотношениями

'.j < Л+1..,: < t,j+1, 1 < i,j < n

'i.» < ■+!.»; «п., < 1 < i < ñ.

t

•mi вычисления каждой подзадачи полагается равным 1.

Функция а выбрана таким образом, чтобы моделировать кольцо из к = \Р\

щессоров

сг

1.-Л если|.-Л<.[*/2] fc-|.'-;| если | í — j |> \k¡2\ '

(9)

в котором каждый процессор имеет номер от 0 до к — 1. Функция г; полагаете» равной константе г. Допускается совмещение операций ввода/вывода и счета Процессоры вычисляют задачи без прерываний. Доказывается следующая теорема

Теорема 0.3 Алгоритм ЕТР для бриллиантового графа, вычисляемого мнп гопроцессорной системой с топологией кольцо, генерирует отображение за дач на процессоры

= 1« ~ 1) М < < п. (10

Если число процессоров в кольче к < то процессоры, участвующие

вычислениях, не имеют простоев, после которых они бы использовались пг вторно.

Иначе говоря, каждая новая линия графа С7- вычисляется ближайшим проце! сором в кольце по отношению к тому, который вычисляет текущую линию. Г] окончании вычисления некоторой задачи 1 < ¿,/ < я, процессор с ном' ром ^ переходит к вычислению задачи -j.fi, одновременно с этим инициир} пересылку данных объемом т процессору ^ + 1. Когда процессор заканчивав вычисление задачи /,->п, 1 < а < «, он используется для вычисления зал; '■'+*,»» ^ 5: «'+ к,} < п. Условие

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

Для установления эффективности применения отображения линиями к I альным ВС, вводится более общая модель коммуникаций, учитывающая стг товые затраты А. В новой модели процессоры, вычисляющие соседние лил взаимодействуют по окончании вычисления блока, содержащего п/т подзад! где 1 < т < п число блоков. Найдена временная сложн ость вычисления бр! лнантового графа для обобщенной модели коммуникаций, и.-/

Ы| = ~(п + А»п) + (к' - 1) ((1 + г)- + А) - Д. 4

к' . \ т 1

■де к' — ггип(1Ь,']Ьга„), а кттх находится из условия -

*т.х < , Шпг - , (13)

1 + п+Ат

¡бобщадащего (И) для случая А > 0 и произвольного т. Найдено оптимальное шсло'блоков (область т/А < 1)

Для обобщенной модели коммуникаций рассмотрен способ отображения за-1ач «а процессоры в виде полос. Бриллиантовый граф разбивается на к полос >авной ширины, каждая из .которых отображается .последовательно на npouec-ор в кольце. Число полос .больше, либо ра,йио числу процессоров. ¡Каждая по-ioca разбивается на 1 < гп < ,п ¡блоков. Пересылка дгщных между соседние ■роцессорами в кольце инициируемся ,по окончании аычислещ!? .блрка, .содер-кащего п3/Ьп подзадач. (Как и в случае отображения линиями, учитываются тартовые затраты. На рис. 1 представлено расписание вычисления графа для усматриваемого отображения. На первом этапе процессор 1 вычисляет прямо-

*ис. 1: Расписание вычисления бриллиантового графа ,^ри отображении поло-ами.

гольный блок с числом задач п2[тк, пастором этапе рн.инцЦКЦРУет.перекупку [роцессору "2, которая начинается по прошествии времени А. (Пересылка требует п/гп времени, так как число подзадач - непосредственных предшественников | вычисленном блоке - равно n/m. Процессор Д ¡переходит к вычислению еле-[уюшего горизонтального блока. По аналогичной схеме продолжаемся работа [роцессора 2 и т.д.

Получено выражение для временной сложности,вычнсленид^рилди^тсарго рафа для отображения полосами, с учетом стартовых затрат

(14)

г г

n /тк Д Xn/m п /тк

п /тК

+ А + —г

т

В приближен!» ТО, £ >-1, ^ <£ 1, найдены оптимальные размеры полосы

блока ' ' '"_ . ' .Л

Проведено сравнение вычислительной сложности отображений полосами и л ниями в разных диапазонах изменения параметров

1. при А — 0и0<г<1 отображение полосами и отображение линия! (алгоритм £77") имеют равную временную сложность

п + (п-1)(1 + г).

2. при А = 0 и т = п оптимальное время вычисления графа с использована отображения полосами и числом блоков т = и равно ~ '2пу/п, в то вре; как алгоритм ЕТР требует времени п3,

3. при А ф 0, отображение линиями имеет у/Х/А раз большую времени; сложность, чем отображение полосами при использовании оптимальш размеров блоков и полос. Алгоритм £77^, соответствующий числу блок тп = п, в этом случае неэффективен.

Можно заключить, что алгоритм ЕТР оказывается неэффективным при пе| сылке больших объемов данных для любых

стартовых затрат и

При биЛЬШ

стартовых затратах для Ьюбых объемов пересылаемых данных. Область з фективности алгоритма ограничивается условием I. Четвертая гласа

В четвертой главе, рассматривается метод, разработанный для распаралле^ ваш;а задачи на многопроцессорном комплексе ЕС-1037, ЕС-2706. Миогопроц сорный комплекс ЕС-1037, ЕС-2706, создан совместными усилиями ученых инженеров Болгарской Академии Наук и ИКИ АН СССР [1]. Основу компл са составляют матричные процессоры (МП) ЕС-2706. В десятипроцессорь конфигурации комплекс обладает пиковой производительностью ¡20МРЮ1 Архитектура комплекса приведена на рис. 2.

с. 2: Схема многопроцессорного комплекса ЕС-1037, ЕС-2706, состоящего и< т ЕС-1037, 8 МП ЕС-2706, дисковой и дисплейной подсистем.

Стандартна математическое обеспечение матричного процессора ЕС-27П(1, по разработано для операционной системы ОС и допускало использование более одного процессора из одного процесса. Для обеспечения возможности ювременного использования нескольких процессоров в операционном Системе ртуальных Машин (СВМ) были решены следующие задачи

• разработано программное обеспечение, поддерживающее работу МП пол СВМ: параллельный программный интерфейс и система разделения времени [3],

• разрабо!аны расширенна языков высокого уровня, позволяющие распараллеливать задачу в режимах ОКМД и МКМД [4],[5].

Параллельный программный интерфейс и параллельные расширения языков зтран и Паскаль и обеспечивают возможность:

• инициирования параллельных-процессов на произвольном подмножестве процессоров в режимах ОКМД и МКМД,

» синхронизации завершения выполнения любого подмножества процессов,

• синхронизации работы каналов ввода/вывода с работой хост ЭВМ,

• совмещение операций ввода/вывода и счета в матричном процессоре.

Проведено исследование влияния стартовых затрат на эффективность р параллеливання задачи на многопроцессорном комплексе, определяющее рас гласованне в запуске матричных процессоров .[1]. Для их минимизации раз ботан оптимизированный параллельный интерфейс, основанный ыа динами ской модификации реальных канальных программ, который обеспечивает чти 50 кратное сокращение затрат по отношению к стандартным затра-ввода/вывода СВМ (4].

Для отладки задач ориентированных на использование математической блиотекн был разработан эмулятор МП на универсальной ЭВМ [2). Все п< численные средства вошли в комплект базового математического обеспече комплекса и находятся в эксплуатации.

Разработанное обеспечение использовалось при решении вычислительно ких задач в физике плазмы [6], астрофизике, квантовой хромодинамике [' ряде других областей. Помимо ИКИ РАН, разработанное математическое о< печение использовалось на факультете ВМиК МГУ, в ИПМ РАН, ИВ'Г Р. ИПФ РАН г.Ннжний Новгород и ряде отраслевых НИИ.

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

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

• Разработан конвейерный алгоритм пересылки сообщений с использов; ем реберно-независимых путей в сети произвотьной топологии для па] го взаимодействия процессов. Алгоритм требует фиксированного кол ства. буферов ввода/вывода, выполняет динамическую балансировку i муникационной загрузки сети. Доказано, что алгоритм сохраняет пор: поступления сообщений в процесс приемник, соответствующий пор! их отправления. Алгоритм свободен от тупиков. Найдено аналитиче выражение (нижняя грань) для времени доставки сообщения с ислаг ванием независимых путей.

с Разработана и исследована структура процесса маршрутизатора соси ний. Доказана корректность работы маршутмзаюра для пронзволь

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

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

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

зработан метод распараллеливания задач на многопроцессорной снсте-ЕС-1037, ЕС-2706, обеспечивающий возможность использования про-юльного числа матричных процессоров при решении одной задачи в жимах ОКМД и МКМД. Проведена минимизация затрат на взанмодей-зие хост ЭВМ ЕС-1037 с матричными процессорами.

учена эффективность расписаний, генерируемых алгоритмом автомати-:кого распараллеливания ЕТР. На примере вычисления бриллиантового *фа показано существование расписаний, имеющих временную слож-:ть меньшую, чем временная сложность расписания алгоритма ЕТР. йдены аналитические выражения временной сложности расписаний для числения .бриллиантового графа с учетом стартовых затрат, согласу-шеся при относительной ошибке не более 5% со временем вычисления ьфа на транспьютерной сети.

о валено изучение эмуляции модели ПМПДП моделями параллельных :тем'с распределенной памятью, такими ка*: гиперкуб, гиперкуб из цн->в, тор и сеть всевозможных соединений. Для каждой из них найдено 1Тношение параметров: быстродействия "процессора по отношению ко :меш! доступа к памяти и пропускной способности каналов, которые -имизируют производительность. Найдено аналитическое выражепие

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

По теме диссертации опубликованы следующие работы:

1. Велихов Е.П., Назаров Вл., Марков Ст., Рог&льский A.B., Сагдеев Р. Чочна Г.А., Шевченко В.И., Решение нелинейных задач физики на мно процессорном комплексе ЕС-1037, ЕС 2706 - М: Препринт ИКИ АН СС N. i 169, 1986, 18 с.

2. С'оломатин В.В., Чочиа Г.А., Имитатор матричного процессора - 1 докл. Всесоюзный семинар молодых ученых и специалистов по инфор: тике и вычислительной технике. Под редакцией В.А. Мельникова, Моек Наука, 1906г.

3. Ананьев A.B. Чочиа Г.А., Базовое математическое обеспечение высокоп изводительного комплекса ЕС-1037, С-2706 в операционной системе ьир альных машин - Многопроцессорный вычислительный комплекс ЕС-К ЕС-2706, М: ИКИ АН СССР, 1987, сс. 7-19.

4. Курбатов М.Г., Чочиа Г.А., Реализация параллельного расширения яз! Паскаль в операционной системе виртуальных машин - М: Препринт И

АН СССР N. 1502, 1989, 24 с.

•

5. Курбатов М.Г., Чочиа Г.А., Расширение компилятора языка Паскаль работы с системой присоединенных процессоров - М: Препринт ИКИ СССР N. 1458, 1988, 22 с.

6. Галинский В.Л., Сагдеев Р.З., Соловьев Г.И., Чочиа Г.А., Шевчс В.И., Решение системы двумерных гидродинамических уравнений ci ной ленгмюровской турбулентности на конвейерном процессоре - Ми процессорный вычислительный комплекс ЕС-1037, EC-270fi, M: ИКИ СССР, 1987, сс. 82-100.

7. Веселое А.ИМ Поликарпов М.И., Чочиа Г.А., Сверхбыстрое нахождение низшего cocToiHii* уравнение Шредингера - Многопроцессорный вычислительный комплекс ЕС-1037, ЕС-2706, М: ИКИ АН СССР, 1987, сс. 129133.

8. Chochia G.A., Transputer Network Simulator - Edinburgh Parallel Computing Centre Newsletter, No. 13, 1991, pp.9-10.

i

9. Chochia G.A., Utilising Symmetry to Simplify Computer Model Performance Evaluation - Edinburgh Parallel Computing Centre, TR91-28, 1991, 23 p.

0. Chochia G.A., On the Performance Prediction of PRAM Simulating Models - in 7th UK Performance Engineering Workshop, J.Hillston, P.J.B.King and R.J.Pooley (eds), Workshops in Computing Seri'-s, Springer-Verlag, London, December 1991.

1. Chochia G.A., Message Passing System for Transputer Network, Preprint 1VTAN N8-370, M.: 1993, pp. 21. Submitted to Scientific Programming.

J