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

ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ н КИБЕРНЕТИКИ МОСКОВСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА вы. М.В.ЛОМОНОСОВА

РГ6 о

2 \ (ЛА? ВЙ

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

Чочял Георге! Антонович

УДК 5! 9.68

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

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

Автореферат

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

Москва- 1994

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

Научный руководитель: доктор фиэ.-м&т. наук, профессор Ю.П. Боглаев

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

Р. Д. Сиелтсшй: кандидат-технических наук Й.А. Степаиовская

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

Задцита диссертации состоится " " О- _£ ' 1994 г. 1

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

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

Автореферат разослан **„ ^_* — ^ _1994 г.

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

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

проф. Трифонов Н.П

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

Ак I уальность темы. дедгтва коммуникации в многопроцессорных оисиемах могут быть »фсдсга-it1»ы в аиле трехуровневой нгра,рхнн. 1На нижнем уровне расположены ашла-1гные средства, возможности которых оцределщотся архитектором «ь/чйсли-льной >сист«?мы .(¡BCi). 'Следующий уровень составляют базовые или систсм-je средства. Верхний '(.пользовательский) уровень образуется совокупностью [ст,рументальных средств, непосредственно используемых при разраСнп ке па-ллельных программ.

В практической работе мы использовали два типа многопроцессорных си-ем: многопроцессорный комплекс на базе матричны.\ процессоров E('-'J?0fi in 1анспьюл'р«ую сеть. Для норной системы оба верхних уровня иерархии црак-[чески отсутствовали, что инициировало наши разработки ни «х созданию. 1аиспьюгерные системы обладают удобными средствами, такими как ятоик \КАМ, параллельные версии явыков Фортран и Си, для «ваимодействия гроссов расположенных в смежных узлах сети. Использование этих средств для ганизации взаимодействия удаленных процессов »начшигельно более щрудоем-. К|н>ме того, разрабатываемая параллельная ¡программа часто становится рн вязан ной" к фиксированной топологии сети и труднопереносимой на дру-е топологии и многопроцессорные ВС. Один из возможных путей решения .проблемы состоит в разработке универ-льном системы пересылки сообщений (0I1C), которая обеспечивает выгюл-мооть существующих параллельных программ на произвольной топологии оцессорной сети.

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

Одной из инзереснейших, но пока нерешенных проблем в отношении систем иго класса, остается проблема средств автоматического распараллеливания. 1ин из алгоритмов автоматического распараллеливания, названный 'ЕагПеая! sk First (ETF). был предложен Hwa~g J.J, et al. в 1989г.. В отличии от елшестнующих алгоритмов, он принимает в расчет затраты, обусловленные

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

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

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

I. Обеспечение возможности выполнения существующих транспьютер»

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

3. Разработка метода и программного обеспечение распараллеливания зад чи на многопроцессорном комплексе ЕС-1037. ЕС-2706 в режимах О К У

и МКМД.

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

памятью ¿о значительными затратами на взаимодействие процессов.

-

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

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

1. Разработан алгоритм парного взаимодействия процессов, сочетающий конвейерный принцип и использующий рр(5ерн<>-це^висимые пути при передаче одного сообщения. Алгоритм использует ф^рпроианиоо число буферов ввода/выроди (яроизво^ы(орз р<ццрра) ц сохраняет ! юр идо к цо-ступления сообщений в процесс прИРМНЙР» роответст«У(0(Ц!1Й нпрадьу их отправления. Алгоритм от ТУПИКОВ.

2. Рассмотрена задача нахождение ОРТОДДОГР дерева веса для рассылки данных 01 одного процесса к грУПП"- Дркзлацр, что задача является Л'Р полной.

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

4. Изучена производительность моделей многопроцессорных срсурм с распределенной памятью, при эмуляции Чмц модели ГШЩЩ, рэк функция быстродействия процессора и памяти, чада независимых декоррели;х> ванных параллельных процессов на процессор для топологий: гиперкуб, гиперкуб из циклов, тор, сеть всерозможных соединений.

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

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

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

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

Апробация работы. Результаты диссертации докладывалис,. на 5°4 Московской городской конференции молодых ученых и специалистов по проблеме кибернетики и вычислительной техники (г. Москва, 1986г.), на Всесоюзном семинаре молодых ученых и специалистов по информатике и вычислительной технике (г. Москва 1986г.), и на 7й Британском семинаре по произвоцитсльност'и вычислительных систем (г. Эдинбург 1991г.). Публикации. По теме диссертации опубликовано 11 работ. Структура и объем работы. Диссертация состоит из введения, четырех глав в заключения, содержит 134 страницы машинописного текста, 27 рисунков, спи: сок литературы из 148 наименований и приложение.

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

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

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

h

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

Для парного озаимодействня процессов были разработаны конвейерные алгоритмы пересылки по единственному пути и с использовг иием реберно-неэависимых путей. Пусть С = (У, Е) есть граф, сопоставляемый многопроцессорной сети и 5» = еа,, ...,еа1 «а, €/?,« = 1,..., Дг путь в графе длиной к. Два пути 5. и с длинами к и у реберно-независнмы, если

е.. П сь, - 0, 1 < » < к, I <j <д.

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

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

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

Приведем соотношения времени пересылки сообщения (ЙЙЖН«Я грань) при парном взаимодействии с использованием трех различных алгоритмов. Используется следующий набор параметров: Л - стартовые затраты, В - Пропускная способность канала, I - длина сообщения, |/ - д^йна маршрута, т - Число блоков (пакетов), на которое разбито сообщение. Простая (однобло^йая) пе]>еЬ1л<ка, и

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

|{гп-Ы-1). (2)

При использовании блоков оптималЬЙЬНз размера это выражение зайк^УМ^тс* как

ы„ = 01 + -!)/?/+(</- 1)А, (3)

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

(£-<*-»И ♦<'-'> И)

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

А

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

15)

(6)

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

№Г>(1--1)А, (7)

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

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

Ь

«йршруту, н до dk поотнсрие-Щ'ЮРppqcyoü ие}>есыл*е, прр выполш'-нии условий- . •

лгь-шм п.: \ . г- „ ^ •••

Сранивая ^3) и (6), при.Сюл^ц^х ^сстододоХ' d можно ВШН'П., чТо 'в предположении равных стартовых затрат Ж оба алгоритма имеют одинаковую асимптотику. '

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

■Разработанная CilC .состоит из двух компонент: транслятора ИОК и Л)*>-lecca маршрутизатора. ЯОК определяет топологию сети, размещение процессов ю процессорам, декларирует взаимодействующие процессы, устанавливает Тип лгоритма маршрутизации, используемого ори рзаимодепстнии- Как результат -рансляцин ЯОК, генерируется таблица маршрутмзац»^. П^'Ьзователю СПС [редоставляется возможность выбора алгоритма: jjmÖQ алгоритм пересылки по динегвеиному пути, либо с использованием независимых путей. В первом <лу-;ае синтаксис ЯОК допускает явное определение пути, как [югледонаге.чынх'и злов простой цепи. По умолчанию СПС находит один из крптчайпых путей лучайным образом. Для нахождения множества кратчайших путей исцилиу-тгя алгоритм поиска в ширину. Полученная таблица маршру т main; и. передается каждому процессу маршрутизатору на этапе загрузки сети. В процессе аботы таблица маршрутизации не модифицируется.

Процесс маршрутизатор резидентен в каждом узле и принимает участие во гех взаимодействиях процессов друг с другом. На логическом уровне, взаимо-ействие процессов осуществляется в соответствен с концепцией, предложенной оаром - через канал. Любая пара процессов может нмегь произвольное число ?завис11мых каналов для взаимодействия. Взаимодействующие процессы /' и эгические каналы С могу г быть сопоставлены графу (Jf = (f\ (J), аналогично, роцессорная сеть препставима связным графом G = (V, Е) процессоров - V и тпаратных каналий - Е. СПС допускает произвольное отображение Р на V н фантирует однозначность выполнения корректной параллельной П(юграммы зя любого отображения.

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

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

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

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

4. со-проиесса вывода данных по аппартному каналу.

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

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

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

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

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

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

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

Георема 0.2 Задача нахождения остовного дерева рассылки минимального »сса является NP полной.

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

ЗУорая глава посвящена рассмотрению моделей многопроцессорных систем с определенной памятью: гиперкуб, гиперкуб из циклов, тор и сеть всевозможных соединений между парой процессор-память. Каждый узел сети состоит и i iponeccopa, аппаратного маршрутизатора и двух классов памяти: программ и latuibix. Общая память ПМПДМ размером М, разбивается на N частей, где Л' - число узлов сети так, что каждый узел содержит M/N ячеек общей памяти, чаждый процессор в состоянии сгенерировать запрос к произвольной ячейке !амяти данных, расположенной в одном из процессоров сети. Для уменьшения гонфликтов по доступу к одному банку памяти последовательные логические лреса отображаются в физические с применением динамического хеширова-шя адреса. Для этой цели используют функции из класса Н

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

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

В результате исследования найдено соотношение параметров: быстродей-твие процессора при фиксированном времени доступа к памяти, и времени

tf, а, 6 Z+.C 6 Z+.

задержки запроса в канале, которое максимизирует п^кЬводителыгостЬ: HJ*»-> .изводителыюсть понимается как число creHeptrjtoti'aWHÜx ri' удовлетворенных^ запросов к обшей памяти. Обращение различных nfJbuWtojWSfc к общей1 памяти полагается некоррелированном. Быстродействие процессора моделируется* средним временем, необходимым для генерации запроса' к обйк'й памяти:

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

Найдено аналитическое выражение дЬя производительности в приближении слабозагруженной сети, в котором среднее время ожидания в очереди к каналу и к памяти много меньше времени обслуживания запроса в канале и в памяти. Такая ситуация имеет место при р — 1. ЦЬсло обслуженных запросов к общей памяти в единицу времени на один процессор (Зав'но

(f . (8)

где .Sjink, Smtm - время обслуживания запроса в канаЛе и' паМ'ги. £)(•) - количество узлов в сети на растоянин i от рассматриваемого,' \> - среднее время генерации запроса к памяти. Выражение (8) проверялось' численным экспериментом. Для рассматриваемых топологий предсказания'производительности с использованием этого выражения имели относительную» ошибку менее десяти процентов.

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

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

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

!П

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

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

Аналитически предсказанная производительность моделей СВС согласует« * численным экспериментом в пределах погрешности моделирования. 'реты» глава.

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

Распараллеливаемая задача представляется множеством подзадач Т. На Т пределен частичный порядок, посредством отношения предшествования: если < М' € Т, то Í' вычисляется по окончании вычисления t и получения от необходимых данных. На множестве Т определена функция, t?(М'Ь сопоста-пяемая объему данных, пересылаемых между t и <'. На множестве процессоров \ определена функция ег(р,р'), р.р' 6 Р, сопоставляемая времени пересылки эобшени» единичной длины между р и р'. Множество подзадач представимо в иде ориентированного ациклическом графа (ОАГ) Gt = (7\<). где < - от-эшение предшествования. В качестве Gj- использовался ОАГ, известный, как эиллнантовый размерности n х п — |7"|. Положение подзадачи в графе опреде-яется парой, декартовых координат 1 < i,j < п. Частичный порядок в графе зределяется соотношениями

'.j < Uj < f,j+t, l<»,J<n

'í,n < <¿+i.n; 'n.f < U.i+i, 1 < i < ñ.

/

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

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

эоцессоров

*[»*)-{ если | i — ^ |< |fc/2J *

j если | t — j |> \k¡2\ 1 (9)

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

Доказывается следующая теорема

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

P(lij) = (»-!) mod k, 1 < ij < п. (10)

Если число процессоров в кольце к < у^, то процессоры, участвующие в вычислен им, не имеют простоев, после которых они бы использовались повторно.

Иначе говоря, каждая новая линия графа Gj вычисляется' ближайшим процессором в кольце по отношению к тому, который вычисляет текущую линию. По окончании вычисления некоторой задачи t;j, 1 < i,j < п, процессор с номером q переходит к вычислению задачи <IJ+i, одновремейЯо с этим инициируя пересылку данных объемом г процессору q + 1. Когда процессор заканчивает вычисление задачи tjt„, 1 < » < п, он используется для вычисления задач ti+kj, 1 ^ i + (:,J < п. Условие

' , • к< СП'

~ 1 +г 4

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

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

и, = ~{п + Ат) + (**-1)((1 + г)11 + л) -Л. 412

где к' - тт(к,'1:тм), а кттг находится из условия -

• 7 ... 1

< . . „Г , (") 1 ' п+Лт

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

Для обобщенной модели коммуникаций .рассмотрен способ отображения задач «а процессоры в виде полос. Бриллиантовый г(раф разбиваете)! на к полос равной ширины, каждая из .которых отображается ,последовательно на .процессор в кольце. Число полос .больше, либо радио числу ¡цроцессиров. Каждая полоса разбивается на 1 < щ < N ¡блоков. Це;ресылка данных между соседними процессорами в кольце цнциИйОДеТЗД »по окрнчании вычисление ¡бл<дка, .содержащего пг/кт подзадач. (Как и в случае отображения линиями, учитываются стартовые затраты. На рис. 1 представлено .расписание вычисления графа для рассматриваемого отображения. На первом этапе процессор 1 вычисляет.црямо-

1 n /тк Л fn/m г П /тк

2 п /тк

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

угольный блок с числом задач п2[тк, »автором этапе ^инициирует перепилку Процессору '2, которая начинается по прошествии времени А. (Пересылка требует rn/m времени, так как число подзадач - непосредственных предшественников Я вычисленном блоке - равно n/m. Процессор Д (Переходит к вычислению следующего горизонтального блока. По аналогичной схеме продолжаемся работа процессора '2 и т.д.

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

• приближении m,i » 1, < 1, найдены оптимальные размеры полосы » блока- „

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

1. при А = 0и0<т<1 отображение полосами и отображение линиями (алгоритм ETF) имеют равную временную сложность

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

2. при А = 0 и г = п оптимальное время вычисления графа с использованием отображения полосами и числом блоков m = п равно ~ 2»»\/"< в то время как алгоритм ETF требует времени п3,

3. при А ф О, отображение линиями имеет \/Л/4 раз большую временную сложность, чем отображение полосами при использовании оптимальных размеров блоков и полос. Алгоритм ETF, соответствующий числу блоков г» = п, в этом случае неэффективен.

Можно заключить, что алгоритм ETF оказывается неэффективным при пересылке больших объемов данных для любых стартиных затрат и при больших стартовых затратах длн Любых объемов пересылаемых данных. Область эффективности алгоритма ограничивается условием 1. Четвертая глава

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

в Разработан конвейерный алгоритм пересылки сообщений с использован ем реСерно-независимых путей в сети произвольной топологии для парн го взаимодействия Нроцессов. Алгоритм требует фиксированного колич ства буферов ввода/вывода, выполняет динамическую балансировку ко муникашюнной загрузки сети. Доказано, что алгоритм сохраняет поряд поступления сообщений в процесс приемник, соотиекгвуюший пород их отправления. Алгоритм свободен иг тупиков. Найдено аналитическ выражение (ни&ндя грань) для времени доставки сообщении с и с пол ь' ванием независимых путей.

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

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

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

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

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

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

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

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

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

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

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

3. Ананьев A.B. Чочиа Г.А., Базовое математическое обеспечение высокопр* • изводительного комплекса ЕС-1037, С-2706 в операционной системе вирт;

альных машин - Миогопроцессорный вычислительный комплекс ЕС-ЮЗ' ЕС-2706, М: ИКИ АН СССР, 1987, сс. 7-19.

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

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

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

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

8. Chochia G.A., Transputer Network Simulator - Edinburgh Parallel Computing

Centre Newsletter, No. 13, 1991, pp.9-10.

i

i

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

10. 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 Serb's, Springer-Verlag, London, December 1991.

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