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

КИЕВСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ .

СПОСОБЫ И СРЕДСТВА ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ МУЛЬТИТРАНСПЬЮТЕРНЫХ СИСТЕМ

Специальность 05.1з/|$— Вычислительные машины, системы и сети, элементы и устройства

вычислительной'техника и систем управления

АВТОРЕФЕРАТ

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

и

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

ЛЛЬ-ШАЛАБИ ХАСАН (ИОРДАНИЯ)

УДК 681.324

КИЕВ-1994

Диссертацией является рукопись

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

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

профессор Луцкий Георгий Михайлович

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

профессор Катков Александр Федорович — кандидат технических наук,

доцент Карачун Леонид Федорович

Ведущая организация — ,Институт проблем регистрации

информации НАН Украианы

Зо

2с, о2 14

Защита состоится " " 1995 г. в " ' / " часов на заседании специализированного Совета Л 01.02..06. в Киевском политехническом институте (г. Киев, пр. Победы, 37, корп. 18, ауд 306).

Отзывы на автореферат в двух экземплярах, заверенные печатью учреждения, просим направлять по адресу: 252056, г. Киев, пр. Победы, 37, Ученому секретарю КПИ.

■ ■ ~ л '* ' - ■

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

Автореферат разослан

и * Ян(£ьр$, 1995

г

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

О.В. Вузовский

АННОТАЦИЯ

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

Для достижения указанной цели в диссертации решаются следующие задачи:

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

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

3. Исследование и разработка параллельных алгоритмов и способов их реализации в мультитранспьютерных системах с ориентацией на широкое распараллеливание.

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

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

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

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

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

следующие положения и результаты:

ОБЩАЯХАРАКТЕРИСТИКАРАБОТЫ

—г —

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

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

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

Как отмечалось ранее, единственный путь реализации терафлопсных ЭВМ связан с МПО подходом, который предлагает агрегатирование вычислительных мощностей на основе объединения десятков и тысяч процессоров класса рабочих станций. Пиковая вычислительная мощность МПО должна быть равна сумме полных вычислительных мощностей каждого из вычислительных элементов. Но это может быть достигнуто только в том случае, если будет иметь место соответствующая структура связей этих процессоров и пропускная способность (производительность) ввода-вывода будет соответствовать вычислительной производимое™. Это было главной целью архитектуры параллельных ЭВМ в течение многих лет. Разработка высокой вычислительной мощности элементов, с одной стороны, и создание тем самым необходимых вычислительных возможностей, и создание мощной коммуникационной структуры, с другой стороны, — это ключ для создания аппаратной части МПО-систем.

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

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

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

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

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

Реализация работы. Основные результаты диссертационной работы использованы при выполнении Государственной научно-технической программы 6.3.1: "Высокопроизводительные профессиональные ЭВМ и проблмно-ориентированные комплексы широкого назначения". Заказчик — Государственный комитет по науке и технихе, а также в учебном процессе на кафедре вычислительной техники в в дисциплинах "Вычислительные системы, комплексы, системы и сети'*.

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

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, изложенных на 151 страницах машинописного текста, содержит 108 рисунков, список литературы из 43 наименований.

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

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

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

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

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

В заключении припедены основные результаты работы

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

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

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

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

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

Крупные достижения в области микроэлектроники привели к возможности создания такого элемента однородных вычислительных структур, как транспьютер, в основе которого лежит RISC-процессор. Транспьютер представляет собой вычислительный модуль, сочетающий в одном кристалле СБИС высокопроизводительный RISC-процессор с фиксированной точкой, АЛУ с плавающей точкой, быстродействующую локальную память и мощные средства для обмена данными — четыре пары последовательных каналов ("линков") передачи данных.

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

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

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

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

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

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

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

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

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

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

В работе исследованы всевозможные одномерные, двумерные к трехмерные топологии и показано, что наилучшими показателями среди этих структур обладают гиперкубические топологии. Основой таких топологий является трехмерный куб, с помощью которого могут быть построены л-кубы. В «-размерное двоичном гиперкубе (.'¡-кубе) имеется Л' = 2" углов. Стороны куба соединяют два узла тогда и только тогда, когда двоичные представления их номеров отличаются только одним битом. Двоичный гиперкуб обладает относительно небольшим диаметром -- п и относительно небольшой степенью 5 узлов 5 = п. Кроме того, алгоритм маршрутизации в таких топологиях является наиболее простым, поскольку сообщение отправляется б сторону узла, номер которого ближе к номеру узла назначения на один бит. Двоичный гиперкуб отличается , высокой отказоустойчивостью, поскольку он обладает множеством избыточных путей между парами узлов и благодаря простоте алгоритма маршрутизации допускает выбор любого из маршрутов ча пути х узлу назначения. Все этк свойства двоичного гиперкуба делают его достаточно привлекательным для построения сетевых топологий.

Однако диаметр и степень узлов двоичных гиперкубов возрастает с увеличением их размеров в логарифмической зависимости, сложность сетевой тополог-ги Р = В 5 - /г2, а число узлов а них может быть равно только степени д^о'гки.

Обобщенные гнперкубичсские сетевые ¡сползши (ОГСТ; являются обобщением двоичных гиперкубов к чогут быть представлены гмпергрэфями, т. е. непустым множеством V вершин ылесте с множестаом Е подмножеств множества V, называемых ребрами. ОГСТ строятся с использованием систем счисления со смешанным основанием. Если N —- число узлов в сети, то N ** пи « тг.\ *...хт,;...х тг * /П|, где г е N. т< > 1, / < I < г. Так, для двоичного куба 1 < г < 3, т|

< 3, mi "= тг = mi m 2, N = 8. Для ОГСТ значения элементов m¡ могут отличаться один от другого. Поэтому номер (адрес) каждого узла в такой сети будет равен xrxr.\—x¡...xix\, где 0 < х,- < (m¡.\). При этом

(-1

х = X (х,- П от/) , / /-о

где то " 1, й mj — основание системы счисления. Ребрами соединяются те узлы, номера которых отличаются только одним разрядом.

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

Таким образом, в отличие от обычного двоичного п-куба, где т,- = 2, в ОГСТ m¡ может принимать любые значения, а следовательно, в рамках небольших значений размерности топологии величины N обобщенных гиперкубов могут принимать большие значения. В рамках ОГСТ можно получить вполне приемлемые значения диаметра D. Однако степень узлов в таких топологиях равна

г

S = 2 (та -1). откуда следует, что при больших значениях mi значение степени i-i

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

Поэтому более приемлемый подход для получения структур с большим количеством элементов при малых размерностях топологии следует связывать с такой операцией над графами, как произкедение графов. При выполнении операции произведения графов Ci и Сг получаем граф G с множеством вершин V, равных декартовому произведению V = К1*Кг. Если V\ = {ut, иг,-.., upi}, Уг = {vi, V2,..., vpz}, а V " {si, si,..., sp}, то число узлов в полученном графе С будет равно р - pipi, а число ребер q = p\qi + piq\, а любые два узла (ш, иг) и (vi, V2) в графе С будут связаны ребром тогда и только тогда, когда ui = vi и U2V2 е Е (Gi) или иг " vi и uivi е Е (Gi).

При перемножении графов Gi со степенью Si и Сг со степенью получаем граф G со степенью S - Si + Si. Соответственно, если Di —диаметр графа Gt, а ГН — диаметр графа Ог, то граф G будет иметь диаметр D — Di + £>2- Кроме того, прч перемножении симметричных графов Gi и G2 получаем симметричный граф G.

Таким образом, при возведении в квадрат некоторого симметрического графа получаем квадратичное увеличение узлов и суммарное увеличение значений степеней и диаметров.

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

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

К такого рода графам относятся «-транзитивные графы.

Граф С называется л-транзитивным, п > !, если в нем имеется л-яуть и для любых двух п-путей найдется автоморфизм, отображающий один из этих путей на другой. Поэтому для любого л простой цикл длины п п-транзитивен и простая цепь длины п п-транзитивна. Если \У есть я-путь ит...^ и и — любая вершина, отличная от и смежная с v,,, то п-путь vi...Vr.ii называется последователем п-пути IV. Если — такой п-путь, что существуют автоморфизмы графа Сг, отображающие ИУ на любой из его последдователей, то граф <7 п-трап-зитивен.

Такие п-транзитивные графы обладают достаточно сильной симметрией. Однако существует ряд регулярных графов, которые в этом плане превалируют над л-трзнзкгивными графами. Такие графы называются клетками. Граф называется п-унитранзитивным (л-унирегулярньтм) графом, если он является связным, кубическим и /¡-транзитивным графом, в котором для любых двух л-путей Щ и №г существует точно один такой автоморфизм « графа О, что а - И/г. Кубический граф с обхватом п и наименее возможным числом вершин называется л-клеткой, где п > 3. Данные графы и должны представлять наибольший интерес для рассматриваемой в работе задачи. На рис. 1 представлены известные метки.

Для я > 5 п-транзитивных графов не существует. Поэтому кг существует и п-унитранзитивньтх графов. В этой связи следует рассмотреть графы с п < 5. Очевидно, что наивысший интерес здесь представляет граф Пстерсона. При степени вершин (узлов), равной 3, его диаметр Г) — ?., а число ^еретич Лг = ¡0. Для сравнения можно выбрать обычный двоичный куб, у которого при Лг - 8, степени узлов 5 » 3, диаметр равен 3. Преимущества схемы Петерсона по сравнению с одним из наиболее распространенных сетевых топологий очевидны.

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

а) 3-клетка

б) 4-клэтха

в) 5-клетка (Граф Петерсона)

г) б-клетка (Граф Хавида) i

д) 7-клетка

е) 8-клетка

Рис. 1

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

Применительно к транспьютерным системам наибольшее распространение

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

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

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

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

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

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

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

Известно, что многие алгоритмы, работающие с целыми числами, по существу совпадают с алгоритмами, работающими с полиномами одной переменной вида:-А(х) = а„-| х"л + ап-г х"2 + ... + ш х + во

или

л-1

А(х) =2 а/ х1 , 1-0

Наиболее очевидная аналогия между неотрицательными целыми числами и полиномами от одной переменной заключается в возможности представлять и те и другие конечными степенными рядами вида А(х). В случае целых чисел коэффициенты щ следует выбирать из множества {0, 1} при х *= 2, а в случае полиномов эти с; можно выбирать из некоторого множества коэффициентов, считая х переменной.

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

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

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

(аг-1 У1 +..Ла1Х + ао) (Ь,-1 х1"1 +...+ Ь1Х+Ы\) - (у^,^/4'2 +...+ ч'|Лг+Уо) где

Кг-ааЬг + а-,Ьг-\ +...+ Л-161 + причем з последнем выражении а; или 6,- принимаются равными нулю, если 1 > (г - 1) или > (« - 1).

Данные формулы могут быть использованы и в случае перемножения матриц А*В размером №<!■'. При этом любой элемент а,/ результирующей матрицы С будет определяться следующим образом:

N г» !

Отсюда следует, что при фиксированных значениях / " к получаем /V элемнтов матрицы с общим множителем аа, а при фиксированных значениях / и к получаем N элементов матрицы с общим множителем Ьк,/. Тем самым определяется множество произведений, упорядоченных таким же образом, как это имеет место при умножении двух целых чисел. В данном случае, для получения всех частичных произведений следует выполнить квазиумножение двух последовательностей:

(ем; ем;...; аа;—; ап.к)(ЬкХ, Ьмл',—', Ьк,/,..■', Ьк,п) При этом для каждого 1 < к а N такое перемножение можно осуществить

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

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

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

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

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

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

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

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

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

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

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

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

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

формулируются следующим образом:

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

1. Луцкий Г. М., Аль-Нсур Айман, Адъ-Шалг.бк Хасан, Срдмпсячй Ъ, Г>. Структурные и алгоритмические особенности op; ui-r.uamui матриц s транспьютерной системе с иерархзгческой гаперкубичгской топологией: Киев, 1994. - 13 с. Деи. в Г НТВ Украины. № 2465 — Ук. 94.

2. Луцкий Г. М., Аль-Нсур Айман, Аль-Шалаби Хасан, Ордынский Р. 3. Структурные и ал! аритмические ссобгнности организации прссбразсзаттпй Фурм в транспьютерной системе с нергршческой гаперкубической топологией. Киев, 1994. — Я с. — Деп. в ГНТБ Украины. № 2465 - Ук. 94.

Л. Луцкий Г. М., Аль-Нсур Айман, Аль-Шалаби Хасан, Ордынский Е. В Особенности структурной организации крупномасштабных мультитряче пь'пт-ерных топологий: Киев, 1994. — 14 с. Деп. в ГНТБ Украины. № 2465 — Ук. 94.

4. Лункой Г. М., Аль-Нсур Аймак.. Аль-Шалаби Хасан, Ордынский В. В. Особенности топологической и гтр;ттурной организации ргконфигур^У^ь^" мультитранспьютерных систем: Киев, 1994. — 13 с. Деп. в ГНТБ Украины. № 2465 - Ук. 94

5. Луцкий Г. М., Аль-Нсур Айман, Аль-Шалаби Хасан, Ордынский В. В. Организация систолических вычислений в м)шьтитракепыотерных системах. Киев, 1994. - 16 с. - Деп. в ГНТБ Украины, № 2113-Ук. 94.

6. Луцкий Г. М., Аль-Нсур Айман, Аль-Шалаби Хасан, Ордынский В. В. Структурные особенности крупномасштабных транспьютерных сетей на основе симметрических графов. Киев, 1994. — бе. — Деп. в ГНТБ Украины, Кг 2117-Ук. 94.

7. Луигага Г. М., Аль-Нсур Аймак, Аль-Шалаби Хасан, Ордынский В. В. Организация полиномиальных и матричных вычислений з транспьютерных системах. Клев, 1994. — 13 с. — Деп. в ГНТБ Украины, ;<rg ¿¡16-Ук. 94.

S. Lutsky G.M., Al-Shalabi Н., Al-Nsour A. Prailel continuous system simulation using the Transputer. Jordan, Mu'tah l.l-Buhooth Wa Al-Dirasat, No 3 [2J-1993 p. 73-81.

9. Lutsky G.M., Al-Nsour A, Al-Shalabi H. Transputer arrays гэг solving p-~r-titoned systems of linear equations. Jordan, Natural and Applied Sciences Series published by Univeisity Ma 20 [5]-1993 p.35-46.

Аль-Шалаби Хасан

Способы и средства повышения эффективности мультитранспьютерных

систем.

Работой является рукопись ;п соискание учечой степени кандидата технических наук по специальности 05,13.0-3 — Вычислительные машины, системы и сети, элементы и устройства вычислительной техники и сисгсм управления.

г. Киев, 1994 г.

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

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

Al-Sha!abi Haan

Manners and means to riasing the effectiveness of multitiansputer systems.

This scientific work is a manuscript to submit one's thesis for candidate's scientific degree in technical scienses in speciality 05.13.08 — Computers, systems and networks, elements and units of computer technique and control systems.

Kiev, 1994.

The aim of the thesis is to develop manners and means for rising the effectiveness of calculations in multitiansputer systems, which are competent on massive parallel computing processes. For this aim achievement in the thesis a research have been developed of hipercubic net topologys and there expansion manners, structural organization of large-scale multitransputer systems, organization manners of computing in multitiansputer systems by using the systotical methods of data processing, effective manners for implementation polynomial and matrix calculations in multitransputer systems.

Юпочов! слова: щдвищення ефективноеп, мультитрансп'ютерш системи, wacose розпаралелювання, Д1аметр, стушнь, топология, концепщя, тушкова сатуашя. -