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

МИНИСТЕРСТВО СВЯЗИ РОССИЙСКОЙ ФЕДЕРАЦИИ Московский технический университет связи и информатики

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

УДК 681.324

Козырев Дмитрий Николаевич

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

Специальность 05.13.13 - Вычислительные машины, комплексы, системы и сети

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва 1995

Работа выполнена в Центральном научно-исследовательском институте связи Минсвязи России.

Научный руководитель - д.т.н., профессор, академик МАИ

Э.В.Евреинов Научный консультант - к.т.н., доцент .■: М.Ю.Артемьев

Официальные оппоненты - д.т.н., профессор, академик МАИ ' " В.К.Морозов;

к.т.н., доцент А.Б.Бурцев.

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

_ Защита состоится " ЛЯ " склеил_1995

г- в ^ ч. на заседании диссертационного совета К 118.06.02 в Московском техническом университете связи и информатики по адресу: 111024, Москва, Авиамоторная ул., д. 8а.

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

Автореферат разослан " /X» Л,- л ^¿йЯ^ ; 1995 г.

Ученый секретарь диссертационного совета К 118.06.02, к.т.н., доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность тем ы. В программе информатизации России решающая роль отводится построению глобальной информационно-вычислительной системы. Реализация вышеназванной программы обуславливает необходимость широкого использования средств вычислительной техники высокой производительности с целью решения научных и технических задач, необходимых для дальнейшего развития Российской Федерации.

Современный этап развития средств вычислительной техники высокой производительности характеризуется интенсивным использованием принципа параллельной обработки информации. Концепция развития систем параллельной обработки информации неразрывно связана с концепцией модели коллектива вычислителей, предложенной и развиваемой Э.В. Евреиновым. Проблема повсеместного внедрения и использования систем параллельной обработки информации в условиях высоких цен сложца и требует рассмотрения целого комплекса проблем, одной из которых является задача коллективного использования вычислительных ресурсов. В полной мере эта задача может быть решена только путем построения интеллектуальной распределенной информационно-вычислительной системы (ИРИС).

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

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

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

Наличие большого количества пользователей предполагает необходимость одновременной реализации большого числа алгоритмов в двухуровневой распределенной вычислительной системе (РВС), отличающейся тем, что ее элементами являются сосредоточенные

/Лз

3

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

Данная работа выполнена в рамках комплексных исследований, проводимых в области создания ИРИС на базе транспьютерной технологии в отделении "Инфраструктура информатизации и распределенная обработка информации" Международной академии информатизации.

Целью д и с сер т а ц и и является исследование и разработка программно-аппаратных средств для реализации вычислительных услуг в ИРИС.

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

- анализ и исследование существующих вычислительных средств высокой производительности и обоснование выбора транспьютерных сетей, как элемента распределенной вычислительной системы (РВС);

- разработка математической модели распределенной вычислительной системы, элементом которой является однородная вычислительная структура, построенная на базе транспьютеров;

- разработка процедуры оптимального отображения потока логических схем алгоритмов в ОВС;

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

< - разработка программных средств для оптимального отображения потока логических схем алгоритмов в РВС.

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

Научная новизна результатов работы заключается в следующем:

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

но

4

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

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

- найдены критерии оптимального отображения потока логических схем параллельных алгоритмов в распределенную вычислительную систему;

- найдены критерии оптимального отображения потока логических схем параллельных алгоритмов в однородную вычислительную систему;

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

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

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

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

Личный вклад автора. Все основные результаты, изложенные в диссертации, получены автором лично.

Практическая ценность работы.

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

/Л5

5

до 20%.

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

Реализация результатов работы.

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

- элемента распределенной вычислительной системы, построенной на основе ИРИС, который представляет собой транспьютерный ускоритель с эквисторными связями;

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

Теоретические и практические результаты диссертации отражены в двух научно-исследовательских отчетах.

Апробация работы. Основные результаты диссертации докладывались и обсуждались на XLV Всесоюзной научной сессии, посвященной дню радио (Москва, 1990г.), Всесоюзном научно-техническом совещании-семинаре " Микропроцессорные системы управления технологическими процессами в ГПС " (Одесса, 1990г.), Всесоюзном научно-техническом семинаре " Районные распределенные вычислительные системы" (Москва 1990г.), V Всесоюзной научно-технической конференции " Однородные вычислительные системы, структуры и среды" (Москва 1991г.), Всесоюзной научно-технической конференции " Распределенные вычислительные системы и сети " (Смоленск, 1991г.), Международных форумах информатизации (Москва, 1992, 1993гг), научно-технических конференциях профессорско-преподавательского и инженерно-технического состава МТУСИ (Москва, 1990, 1991, 1992гг.).

Публикации. По теме диссертации опубликовано 13 печатных работ.

Основные положения, выносимые на защиту.

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

2. Метод оптимального отображения потока логических схем параллельных алгоритмов в ОВС с эквисторной топологией позволяет уменьшить количество простаивающих элементов ОВС в среднем на 20% по сравнению со случайным размещением.

3. Метод оптимального отображения потока логических схем параллельных алгоритмов в двухуровневую распределенную вычисли-

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

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

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

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

Схема, модели исследования двухуровневой распределенной вычислительной системы представляет собой совокупность сосредоточенных однородных вычислительных систем (СОВС), соединенных с коммутационным полем К, обеспечивающим передачу информации между элементами РВС. Так как заранее не определено, где будут располагаться единичные параллельные вычислители, коммутационное поле К представляет собой сеть связи с соответствующими свойствами и параметрами. Для исследования и разработки программного обеспечения двухуровневой РВС коммутационное поле К должно обладать следующим свойством: информация с любого входа/выхода может быть передана на любой другой вход/выход.

Связь между СОВС может быть организованна различными

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

Таким образом, математическая модель двухуровневой РВС может быть представлена в виде четверки параметров <М, К, , 3, Б>, где

N -количество единичных параллельных вычислителей (Сосредоточенных Однородных Вычислительных Систем) РВС;

К, - матрица связности СОВС;

Б - матрица статических коэффициентов;

Б - вектор динамических коэффициентов.

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

На основе анализа существующих вычислительных средств высокой производительности в работе обоснован выбор СОВС, как элемента РВС, и транспьютера, как элемента СОВС.

Вторая глава посвящена проблеме оптимального размещения алгоритмов в однородной п - мерной эквисторной структуре.

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

помимо связей с соседними элементами иметь связи через один элемент, два и т.д.). ОВС такого типа назовем ОВС с эквисторной топологией (эквисторные ОВС).

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

ОВС - это множество регулярно соединенных одинаковых ячеек среды. Структурой ОВС назовем граф в (В), где вершинам множества В поставлены в соответствие ячейки среды, а рёбрам -соединительные линии между ячейками среды. Регулярность структуры ОВС достигается, если для любой пары элементов 1, } е В существует автоморфизм а(1 => 3) , т.е. каждому элементу 1 е В ставится во взаимно однозначное соответствие некоторый элемент ] € В, и отметки всех ребер сохраняются.

Эквисторные ОВС предлагается классифицировать на абсолютно регулярные, регулярные и квадирегулярные.

Определение 1. Однородная среда называется абсолютно регулярной, если каждый ее элемент имеет однотипную структуру связей во' всех направлениях.

Определение 2. Однородная среда называется регулярной, если каждый ее элемент имеет однотипную структуру связей в отдельности по каждому из направлений.

Для одномерного случая понятия абсолютно регулярных и регулярных структур идентичны.

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

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

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

Ниже приводится способ описания ОВС с эквисторной топологией, предложенный автором.

Эквисторные ОВС могут быть описаны системой четырех параметров: < n, J, m, L > , где п - размерность.

J = { j,, j2, ... , jm } - множество, определяющее количество элементов по каждому из направлений пространства; ш - число направлений связи.

L = { 1(, 1,, ... , 1и } , где 1, - множество коэффициентов перекрытия по каждому из направлений.

В главе доказан ряд теорем:

Теорема 1. Любая регулярная одномерная эквисторная ОВС может быть представлена в виде совокупности конечного числа одномерных евклидовых решеток.

Следствие 1. Для линейных регулярных эквисторных ОВС, где выполняется условие N/(1 + 1) - целое число, Q = 1+1. Действительно, из начального условия следует Q = М/С = 1 + 1.

Следствие 2. Для линейных регулярных эквисторных ОВС, где выполняется условие N/(1 +■ 1) <= С, - не целое число, Q = (1 + 1)/р , где р - минимальное, такое, что p*N/(I + 1) = С,' - целое число.

Теорема 2. Любая абсолютно регулярная п - мерная эквисторная ОВС может быть представлена в виде совокупности конечного числа п - мерных евклидовых решеток.

На основе вышеизложенного найдены критерии оптимального отображения потока параллельных алгоритмов в ОВС с эквисторной топологией.

Пусть имеется п - мерная эквисторная абсолютно регулярная структура, состоящая из N элементов. Пусть также в этой структуре размещены два произвольных алгоритма. Тогда: А = { а,, а2, ... , а,, ... , а^ }, - множество элементов ОВС, занятых первым алгоритмом;

В = { Ь,, Ь2, ... , Ь., ... , Ь^ },- множество элементов ОВС, занятых вторым алгоритмом;

С = { с,, с2, ... , е., ... , с„ }, - множество свободных элементов ОВС.

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

а) i - й элемент ОВС должен быть задействован одновременно

только в одном алгоритме;

б) если N - количество элементов ОВС, то для размещения двух алгоритмов в ОВС необходимо выполнение неравенства

N Ü |А|+ |В| .

Пусть А'с А; В'сВи А'еО , ВЧ 0. Найдем прямое произведение А' х В' = К. Областью соприкосновения двух алгоритмов назовем множество: D = А' В' , если элементы каждой из пар множества К инцидентны друг другу.

Если все линии связи одного и того же к - го порядка, то множество К будем называть областью соприкосновения к - го порядка и обозначим Dk . Если линии связи имеют разный порядок, то такую область соприкосновения назовем комбинированной областью соприкосновения и обозначим ml . Множество Р = D," и D2u о... ш," ... , где нижние индексы множеств в правой части равенства - порядковые номера, назовем суммарной областью соприкосновения.

Пусть А" сА;В"сВиА"(Г0, В" сс 0. Пусть: А" ^ В" = S. Множество S называется множеством крайних элементов объединения алгоритмов А и В, если каждый элемент множества S инцидентен хотя бы одному элементу множества С.

Рассмотрим функции F, = |Р I и F,' = |S I. Оптимальным явля-етсмя такое размещение алгоритмов А и В, при котором достигается минимум функции F," , или максимум функции F, . Таким образом, первый критерий оптимальности размещения алгоритмов А и В в однородной абсолютно регулярной эквисторной структуре будет: шах F, (или min F,' ). Второй критерий оптимальности вытекает из определения порядка связи. Очевидно, что наиболее оптимальны связи меньшего порядка, поскольку они ближние. Таким образом, если ввести функцию F2 = к, то второй критерий оптимальности размещения алгоритмов А и В в однородной абсолютно регулярной структуре будет min F2 .

Таким образом, найден функционал F = { F, (р), F2 (к) }, который определяет оптимальное размещение двух алгоритмов в эквисторной ОВС.

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

Рассмотрим параллельный алгоритм А, представленный в виде графа G = (Р,Ка), в котором вершины - процессы, а дуги отражают информационные потоки между процессами. Пусть:

Р = { р(1 р2, ... ,р., ... , р№ } - множество вершин графа; Ыа - мощность множества Р;

кса = { кса) Р кса12. — >4*1' - • к«ш,№> > " множество весов дуг графа

О.

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

Такая РВС может быть описана полносвязным графом:

<2 = (V, Кс>) , где

V = { V,, у2, ... ... , у,^ } - множество вершин (СОВС, входящие в РВС);

К, = { к„,>- кс„.г ••• ••• . кс^,ыо»с } - множество весов дуг; * мощность множества V.

Пусть необходимо разместить алгоритм А в Ч - й ОВС, причем

1Р| <1Ч,ок! ,где

ок1 - множество свободных элементов в \ - й ОВС.

При разработке метода оптимального размещения алгоритма А на РВС будем основываться на следующих критериальных функциях:

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

- оптимальным размещением алгоритма А на РВС будем считать такое размещение, при котором достигается минимум обменных взаимодействий между ОВС, задействованных в выполнении алгоритма А. ' '

При разработке критериев оптимального размещения алгоритмов на РВС будем учитывать, что

а) стоимость машинного времени на всех ОВС, входящих в РВС, одинакова;

б) стоимость передачи информации между ОВС рассчитывается в соответствии с существующими тарифами на оплату каналов связи.

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

первый критерий оптимального размещения алгоритма А на РВС звучит так: найти на множестве V такой элемент v., что •

|Р| < J , где

N„ ж) - множество элементов j-й ОВС, свободных в данный момент времени.

Одним из важнейших условий минимизации времени выполнения алгоритма на РВС является минимизация объема информации, передаваемой по каналам связи, которые соединяют элементы РВС. Эта задача решается, если первый критерий ríe может быть выполнен, т.е. множество Nc>oií = { 0 }. Таким образом, второй критерий оптимальности может быть записан следующим образом: найти фактор-множество

Р/2 = {А,, А,, ... , А.....Ау}

при заданном у такое, что

k^j -» min. , где . - коэффициенты передачи между смежными классами фактормножества Р/Е.

к» = Ли. кч02. - , к ... } и К « f(KCA)

А, - смежные классы.

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

Третий критерий оптимального размещения алгоритма А на РВС связан с выбором каналов связи с минимальной стоимостью.

Пусть есть фактор-множества Р/Е и V/Z , причем I P/Zi £ Iv/zl, где V/Z - фактор-множество, смежными классами которого являются множества свободных элементов каждой ОВС, входящей в РВС. Пусть также Kw - множество всех возможных путей между любыми двумя вершинами графа Q, а С - множество стоимостей каждого из путей. Необходимо найти минимум функции

f(kw ) = 2 t с к

¡«1 j»i

/го

при ограничениях:

а) каждый канал используется ровно один раз -

£kwij=l - для всех i;

j-l ' .

б) каждому потоку информации будет поставлен в соответствие ровно один виртуальный канал

£ kWl . - 1 - для всех j;

m - мощность фактор-множества Р/Е, п - мощность фактор-множества V/Z.

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

kwi.. + kWi.2 + - + kwi.t = 1. .0 =

Кг, + kw2,j + ••• + kw.j = <j = 1, п), которое минимизирует функцию

f(kw ) = t t с kw .

1-1 и

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

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

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

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

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

Следующим шагом осуществляется анализ ИРИС по следующему алгоритму.

1. Анализ состояния всех ОВС ИРИС с целью определения возможности размещения смежных классов.

2. В случае успешного поиска осуществляется анализ каналов связи между найденными ОВС с целью исследования возможности передачи между найденными ОВС заданного объема информации с заданной скоростью.

3. В случае успешного завершения пунктов 1 и 2 настоящего алгоритма производится выбор каналов связи в соответствии с критериями 3 раздела 2.2 настоящей главы.

4. В случае неудачного завершения пунктов 1 и(или) 2 настоящего алгоритма коэффициент К увеличивается на единицу.

Для двухуровневой РВС получена формула эффективности.

Е = Та1с/(Т^ир + шах(ТЫс J^)), где

Тса|с - общее время вычислений; Т ш - общее время на управление и связь;

Т - время, необходимое для неперекрываемой операции настройки каналов и других накладных расходов; •

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

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

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

Алоритм описывается системой уравнений, в которых положение n-го элемента вычисляется исходя из положения (п-1) - го элемента, причем положение первого элемента алгоритма выбирается произвольным:

e(j) = j;

e(n) = f(e(n-l»;

где e(n) - номер элемента ОВС, выполняющего те же действия, что и 11-й элемент алгоритма.

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

, участках ОВС.

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

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

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

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

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

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

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

е(р = еО-1) + УБ + У5(1+1) + + УИ(1+1)

где ] - номер элемента алгоритма,

УБ - горизонтальный орт ОВС,

УМ - вертикальный орт ОВС,

1 - порядок перекрытия ОВС.

Очевидно, что манипулируя значениями У5 и УЫ, можно получить различные ориентации исходного алгоритма.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

1. На основе анализа существующих вычислительных средств высокой производительности предложена структура двухуровневой распределенной вычислительной системы, элементом которой является сосредоточенная однородная вычислительная система, построенная на основе транспьютеров.

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

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

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

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

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

7. Разработана алгоритмическая реализация процесса опти-

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

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

СПИСОК ПУБЛИКАЦИЙ

1. Артемьев М. Ю., Козырев Д. Н. Метод оптимального отображения алгоритмов в экристорные ОВС // В сб. Судостроительная промышленность, серия Системы автоматизации проектирования, производства и управления. - М.: ЦНИИ "РУМБ", 1991., вып. 23, -С. 81 -90.

2. Артемьев М. Ю., Козырев Д. Н. Формальные описания однородных вычислительных структур и сред // Всесоюзный научно-технический семинар "Районные распределенные вычислительные системы": Тез. докл. - М., 1990. - С. 12.

3. Артемьев М. Ю., Козырев Д. Н. Организация оптимальной реализации алгоритмов на ОВС / / Всесоюзная научно-техническая конференция "Распределенные вычислительные системы и сети": Тез. докл. - Смоленск, 1991. - С. 6.

4. Карандин В Н., Козырев Д. Hw Прокопенко А. Л. Реализация устройств контроля и управления на базе однородных вычислительных сред // XLV всесоюзная Научная сессия, посвященная Дню радио: Тез. докл. - М., 1990. - С. 35 - 36.

5. Артемьев М. Ю., Абдрахманов Б. К., Козырев Д. Н., Карандин В. Н. Транспьютерная и систолическая технологии в распределенной информационно-вычислительной системе / / XLVII Научная сессия, посвященная Дню радио: Тез. докл. - М., 1992. - С. 111 -112.

6. Артемьев М. Ю., Козырев Д. Н. Формальное описание однородных вычислительных структур и сред с регулярной топологией // Всесоюзное научно-техническое совещание семинар "Микропроцессорные системы управления технологическими процессами в ГПС": Тез. докл. - Одесса, 1990. - С. 50.

7. Козырев Д. Н. Метод оптимального отображения алгоритмов в эквисторные ОВС // Деп. ЦНТИ "Информсвязь", №1843. -М., 1991.

8. Козырев Д. Н. Планирование и реализация алгоритмов в ОВС с эквисторной топологией // Научно-техническая конференция профессорско-преподавательского состава, научных и инженерных работников и аспирантов МТУСИ: Тез. докл. - М., 1992. - С. 45.

/So

18

9. Козырев Д. Н. Организация функционирования ОВС при решении задач цифровой обработки сигналов // V Всесоюзная научно-техническая конференция "Однородные вычислительные системы, структуры и среды": Тез. докл. - М., 1991. - С. 182.

10. Козырев Д. Н. Метод реализации вычислительной услуги в интеллектуальной распределенной информационной системе // Международный форум информатизации: Тез. докл. - М., 1992. - С. 102 -104.

11. Козырев Д. Н. Аппаратно-программная реализация вычислительного комплекса коммутационной станции // Международный форум информатизации: Тез. докл. - М., 1992. - С. 104 - 105.

12. Козырев Д. Н. Оптимизация размещения логических схем параллельных алгоритмов на интеллектуальной распределенной информационно-вычислительной системе // Международный форум информатизации: Тез. докл. - М., 1993. - С. 4 - 5.

13. Козырев Д. Н. Разработка программного комплекса поддержки вычислительной услуги в интеллектуальной распределенной информационно-вычислительной системе // Международный форум информатизации: Тез. докл. - М., 1993. - С. 5.

Подписано в печать 11.04.95. Формат 50x64/15. Печать офсетная. Объем 1,0 усл. п. л. Тира'к 100 экз. З.-каз 180.

ООП МП "Игфэрмсвяэьиздат". Москва, ул. Авиамоторная, 8.