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

РГ:) с Л

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

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

А. X. М. Асадузэаман (Бангладеш)

УДК 681. 324

СПОСОБЫ И СРЕДСТВА ОРГАНИЗАЦИИ ТРАНСПЬЮТЕРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СРЕД ПРИ РЕШЕНИИ ЗАДАЧ БЫСТРЫХ ДИСКРЕТНЫХ ОРТОГОНАЛЬНЫХ ПРЕОБРАЗОВАНИЙ

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

системы и сети

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

Киев-1904 г.

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

Научный руководитель-доктор технических наук, профессор ЛУЦКИЯ Г. М.

Официальные оппоненты:-доктор технических наук, ' профессор КАТКОВ А. Ф.

кандидат технических наук,

старший научный сотрудник Скорик В. Е

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

Защита состоится <2*1 > февраля 1994 г. в 14.30 часов на заседании специализированного совета Д. 068.14. 09 Киевского политехнического института по адресу: 252056, г. Киев,проспект Победы,37. корп. 18, ауд 306.

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

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

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

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

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

А Н Н О Т А Ц И Я

Целью диссертационной работы является разработка эффективных способов организации вычислений применительно к быстрим дискретным ортогональным преобразованиям (БДОП) в травспыотерн-рых вычислительных средах (TDC).

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

1. Разработка способа эффективной реализации БДОП в TBC с минимальной длиной каналов связи и минимальным числом пересылок.

Й. Выработка единого подхода к приведению вычислительных алгоритмов БДОП к вид/, наиболее приемлемому для реализации в TBC.

3. Выбор структурной организации TBC для БДОП.

4. Разработка способа планирования параллельных процессов в транспьютерной сети.

Б. Разработка способа реализации вычислений итеративных алгоритмов в TBC.

б. Разработка методики определения эффективности вычисления БДОП в TBC.

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

1. Способ организации вычислений ВДОП в TBC.

2. Способ планирования параллельных процессов в транспьютерной сети.

3. Структурную организацию транспьютерной сети.

4. Методика определения производительности TBC при реализации БДОП.

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

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

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

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

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

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

ПРЕДМЕТОМ ИССЛЕДОВАНИЙ дис ^ртационой работы является структурная организация, ориентироваяая на параллельную реализацию итеративных процессов и алгоритмов БДОП.

МЕТОДЫ ИССЛЕДОВАНИЙ. В диссертационной работе использованы теоретические положения и методы теории вычислительных процессов и вычислительных систем,теория матриц,теория параллельного програмировашш, теория построения многопро-

цессорных ЭВМ,а также теории графив,базовые положений цифровое обработки сигналов.

НАУЧНАЯ НОВИЗНА. Предложена структурна:: органи-аация TBC,методика планирования вычислительных процессов и определения эффективных вычислений в TBC применительно к задача-БДОП, разработаны способы и средства параллельной реализации горитмов БДОП..

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ рабогь cüi:jl„ разработке структурных и алгоритмических методов построен/.» TBC, которые могут быть использованы, например для цифровой обработки сигналов, обработки и преобразования изображений в целя улучшения кочества, решения задач гидроакустики, ядерной физк-ки,гиофиеики, метрологии,медицины,сейсмологии, астрономии и т. д.

ПУБЛИКАЦИИ По теме диссертации опубликовано 2 печатные работы и одна сдана в печать.

СТРУКТУРА И ОБЪЕМ РАБОТЫ.

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

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

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

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

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

В четвертой главе расмотреаы вопросы описания конфигурации системы,распределеяйя памяти,управления сетью,загрузки данных в TBC,реализован алгоритмов БДОП (на примере быстрого лреобраеова-

ния Фурье (БПФ)), разработан способ определения эффективности вычисления БДОП в TBC.

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

Любой сигнал х( t), принадлежащий конечному линейному пространству, натянутому на элементы полной ортогональной системы,может быть единственным образом и с минимальной погрешностью представлен в виде линейной комбинации ортогональных функций,на которые натянуто данное паространство. Существует множество систем ортогональных базисных функций, удовлетворяющих требованиям теоремы о наилучшей аппроксимации. При обработке сигналов средством обобщеной спектральной ил:» секвентной теории выбор оптимальных базисов обычно связывают с вычислительной эффективностью, предлагающей выделение такого подмножества базисов,которое допускает возможность.реализации ортогональных преобразований при помощи быстрих ортогональных алгоритмов. В работе' проведен анализ алгоритмов вычислений БДОП и способов их реализации. При описании ортогональных преобразований и в практике' их применения широко используются матрицы. Матричный метод сформировался и как метод обобщеного представления БДОП. При таком описании преобразуемая исходная последовательность представляется в вид< Еектора столбца,ваданкое преобразование в виде соОтвествую-щей ему матрицы. Умножая эту матрицу на указанный вектор-столбец, получаем вектор-столбец,содержащий результат преобразования, являющейся спектром заданной последователности. При матричном представлении информации, исходная матрица заменяется вычисляемой по определенным правилам суммой слабозаполненных матриц,каждая из которых содержит лишь незначительное количество отличных от нуля элементов. При матричном выполнении БПФ, быстрого преобразования Уолиа, быстрого преобразования Хаара и других быстрых ортогональных преобразований, матрицы соотвествующих преобразований оказываются различного вида. Однако в всех случаях в конечном счете матрица представляется в форме,над которой производятся относительно простые вычислительные операции. Применяемый в диссертационой работе способ факторизации позволяет разложить исходную матрицу на множество слабозаполненных матриц также и для систем ортогональных функций, -которые не обладают свойством мультипликативности, таких как система функций Хаара.

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

включают в себя три вида матриц: матрицу С(1) евяаеи.тп.ни Я(1) весовых коэффициентов и матриг"' Б перестановок Показано. что структура матрицы С(О вависит лишь от номера итерации. Зго обостоятельство создает определенные предпосылки для построения обобщенных спектральных анализаторов. Матрица 0( О должна иметь регулярную структуру, которая сохраняет независимость С(О от номера итерации,что позволяет получить однородные с<тукту{и .-и числительных алгоритмов БДОП с минимальной аппарату) но;'. и; (,1.'::./Ч ности.При реализации ортогональных преобравовплий прел.." .- ->.те>, использовать однородные вычислительные алгоритмы,которые можно представить следующим образом:

X = 1 / »ЛЙ * 5'{ А >* 5 * ЗС ( 1 )

¿к к +

где, х -вектор входных отчетов; X -вектор выходных мэзффкциенгоь; S -матрица цифровой инверсии;

матрица идеальной перестановки;

<~ik г И*

-базовая подматрица; где t= ^ ■ ""

-диагональная матрица,

- % -блочнодиагональная матрица;

Представление алгоритмов БДОП в виде (1) порволяет адекватно отражать вычислительный процесс в TBC. Допустим есть ТЮ, число процессорных элементов которой равно Р, предположим, что Р * К =* N. где .К-целое число, и М-число входных отсчетов. Матрицу А. наш разделить на подматрицы с размером К * К, В работе предложи способ реализации алгоритмов БДОП в ТВ.-. Рассмотрена реалнзацьл этого способа на примере вычисления алгоритма БПФ. Разработан способ реализации алгоритма БПФ для TBC. Предложенный способ характеризуется высотой степенью параллелизма, минимальным числом пересылок сообщений и позволяет обрабатывать массивы данных любой размерности.

Известно, что эффективный параллельный алгоритм для ТБС должен иметь следующие особенности:

-равномерное распределение данных по процессорным элементам

ТЭ).Нри атом каждый ПЭ выполняет идентичную операцию над разными данными и объем вычислений для каждого процессора один и

ТСС же;

-доминирование объема вычислений над передачей сообщений; -время вычислений в ПЗ должно быть больше, чем время обмена данным:.

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

ЛМ

Х(И)-/Х(К) *УчК

.,')< _ ТО )7 К {Ы

где. V =е - с 1

г*

^М; К,7? =0,1,2,.., ,(N-1). Предлагаем организовать последовательность Х(К) в виде матрицы, состоящей из Н1 строк и N2 столбцов где, Н=Н1*Н2. Матрица имеет следующий вид:

Х(0), Х(1), ... Х(N2-1)

Х(М2),Х(Н2+1),

Х(Н1-1)*иг,

Х(2*М2-1)

Х(Ш*Н2-1)

Рис. 1.

Для реализации Е1И> основной операцией является операция "бабочки". Операция "бабочки" определяется между двумя точками Х(К1) и Х(К2) с параметром М .где К1 и К2 -это индексы двух комплексных чисел в исходной матрице. Целое число М можно представить в виде функции в зависимости от К1 и 1, где ¿-это номер итерации. Способ вычисления м следующей: К1 записывается в виде числа длиной I .которое сдвигается вправо на .разрядов (умножается на 2 ) и затем перигшсывзегся в обратном порядке. Операция "бабочки" в математическом виде представляется в следующем виде:

Х{(К1)-Х(,(К1) +Х(._|К2) * V,"

Х;(К2)=Х.(К2)-Х.р(2) * V„A!

W" =EXP(-J2Pi * M/N)

»C0S(2Pi * M/H)"JSIN(2Pi * M/N) ; Предлагаемый способ реализации алгоритма БПФ для TBC состоит ив следующих 6 шагов:

U1AT1: Все столбцы матрицы предстанля'ются как векторы размерностью L. На атом шаге итерационно выполняется L/2 операций "бабочки", число итераций равно lo^L. Например, для 16-точечного ИМ, последовательность исходных данных будем представлять в виде матрицы 4x4. Тогда необходимо 1оцг4=2 итерации по каждому вектору. Для вектора (Х(0) ,Х( 4) ,Х(8), Х(12)), на первой итерации операция "бабочки" будет вычисляться между элементами вектораСточками отсчета) Х( 0) и Х(8) а также между Х(4) и Х(12), а на второй итерации мелвду Х(0) и Х(4) и между 7(8) и Х(12) точками.

ШАГ2: На этом шаге элементы всех векторов преобразуются по методу двоичной инверсии. То есть новое место каждого элемента опредля&тся после инверсии его адреса в двоичном представлении в векторе. Например, вектор (Х(3), Х( 7), Х( 11) ,Х( 16)) после второго шага будет преобразован к виду (Х(3),Х(11),Х(7),Х(1Б)).

ШАГЗ: На этом шаге производится транспонирование магрицн.

ШАГ 4,6: На этих шагах производится повторение шага 1 и ыага 2, но только с транспонированной матрицей. Очивидно ,что шаг 4 и 5 это повторение шагов 1 и 2,но только для строк матрицы.

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

В работе предложен способ реализации вычислений итератив ыд: алгоритмов для TBC. Предложенный способ основан на определении такой вычислительной модели, в которой алгоритмы представляются в виде множества параллельных процессов,погруженных в некоторой" TBC, и обмен сообщениями происходит асинхронно. Способ представления асинхронного вычисления следующий: фаза вычисления J-oft итерации процесса T¿ может быть лредставленна в виде отображения : Sij : Di ---> С, , где i-ГГп, J=1,Ncгде tl -количество итерации

Рис. 2. Блок схема,способ распределение входных отсчетов по транспьютерной сети при вычислении алгоритмов БДОП.

процесса Т/. Допустим необходимое вргмя вычисления J-ofi итерации процесса Т* равно tjj , в общем случае Hj ф tKJ у Ф к

XiCI'T^'fvfriCHT-O^tftVtj)), — , Хп (&(***)))

Ч Ьг Т), , ... , (Тп (itf)))

• $ * * * ♦

Xn Ипт) =

где X i (t ¡j )-результат J-ой итерации процесса Т/, ^(i/j-) , -момент времени в который ХК готов к вводу процесса Tt- для вычисления j-ой итерации. Тогда С iij - '^(V/jJ ] представляют собой временную задержку для передачи значения Х^ . Из вышеуказанных соотношений следует,что каждая следующая итерация выполняется без временной задержки для получения входного значения. В работе этот способ реализован на языке параллельного программирования ОККАМ.

В работе предложена серугстурная организация TBC в виде гиперкуба, состоящего из 16 транспьютеров и разработана обобщенная гиперкубическая структура ' для организации TBC из N транспьютеров. N можно разложить в виде :

N» т,* п^;каждый ПЭ X можно представить в виде кортежа Х«(Хг Х^.. X, ) где 0 <= X/ m/-l л 7ДИ-1

v;" X; V/fl'r-'t ™ my mt-i * mt-£ * ••• * mi > гДе i"l«r;w -вес.

¿'Г

Степень узла в обобщенной гиперкубической структуре равна:

г

1 - 2 (»г Ds ' t:f

количество линий связи в ОГС равно: L = N / Z ) ( mj - 1);

kl

Допустим Н^ количесво узлов, Хэминговое расстояние между которыми равно d Тогда,

Среднее расстояние'сообщений в ОГС равно':

с

ibт£

йср - г. ( ш-1 ) . rt*' /(М-1), ю = 5TÜ7

)

где i - коэффициент обслуживания в ОГС. При определенной загрузке структура насыщается,при этом = 1 / ванятость ОГС равна: Т - (d^* 23 )/( 1 - dC([J * )> ) ; плотность сообщений в

линиям связи ОГС равна Р ■ ( 2 * dCf ) / £ ( n^ - 1).

В ОГО dt/t) ■ и F " имеют минимальные значения по сравнении с другими структурами и более высокую степень отказоустойчивости. Для данной структуры ОГС г - 4, 1 ~ 4, dc„ =2,13 , Р = 1,06, У -0,47.

В работе предложена модель вычисления ЕДОП в TBC,которая состоит из трех процессов: глаг"чй процесс управления ( ГШ' ), процесс вычисления (ВП), процесс передачи( IUI). ГПУ распределяет зекторы по ГО в TBC. ВП выполняет базовую операцию и "другие операции преобразования, а ПП выполняет маршрутизацию в TBC. Модель представлена на рис. 3, а отображения параллельных процессов показаны ка рис. 4.

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

При реализации ВП на TBC заданной структуры с неизменяемыми связями возникает задача планирования вычислений. 'Это задача заключается в нахождении такого распределения вычислительных процессов по ГО .которое приводит к минимизации времени выполнения параллельной программы, Реализация задачи планирования связана с разработкой программ« конфигурации. Практическая реализация .такой программы связана с существенными трудностями. Число линков При росте числа процессоров N должно расти пропорционально Мг, а чпово nop'joB на каждом элементе - пропорционально N.

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

Представим транспьютерную сеть в виде графа процессоров аР (Р ,Ер },я параллельную программу в виде графа задач G^ (Т ,Е< );\"7ie р,т мнояе^тво вершин и Ер -множество ребер соотвест-

Рис. 3. Модель вычислений ЕДОП в TBC

Рис. 4. Отображение вычислительных процессов в TBC.

вукэдэго графа. В множество вершин Т и множество ребер представляют операции и коммуникационные каналы между' ними, причем под операцией понимают один или несколько процессов программа Каждой вершине t(и ребру Еуграфа G^поставлены в соотвествие веса, w, и е^, представляющие собой оценки объема вычислений соот-вествующэй операции и объема информации при передаче сообщений между операциями i и Проблема планирования исходной программы на заданную транспьютерную сеть состоит в отображении графа G^ на G р .которое можно представить функцией 1: Т—> Р,

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

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

В процессе группировки придерживаются следующих правил: -если число операции(п0 ) в исходном графе больше числа ч р&аспыотеров (Р), то необходимо произвести такую группировку мграций, чтобы n0 <=Pj

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

Urn группировке элементов матрицы исходных последователь-нос >.. >; но предлагаемому способу вычислении, БДОП, необходимо произ-вес. ги группировку по столбцам.

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

-если у данной операции ti поручается процессору Р* и имеет только одну соседнюю операцию ,то при размешэнии других < операций ее помещают в ГО, расположенный на возможно близком расстоянии к процессору Рк данной операции;

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

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

При размещении я маршрутизации векторов матрицы (рис.1} а работе предложен следующий способ: чтобы распределить Евктори по ПЭ, с каждый вектор сопровождается тегом. Этот тег содержит следующую информацию: 3 - знак направления передачи; I - размерность вектора: N8 - номер группа,каждая группа состоит из НЬ вектора,и каждый вычислительный процесс получает один вектор из одной группы; МСР-номер вычислительного- процесса. С помощью тега векторы распределяются по ПЭ в сети. Г!ри отказе маршрутизации процедура настройки настраивает процедуру группировки (с перегруппированием) и процедуру размещэния( с изменением схемы размещения) . Сущность процедуры самонастройки следующая: допустим ''и и а/// -это набор путей отказа и набор узлов отказа соотвествен-но.где 1 <= 1 <=Уи 1 <= J <="[. Р -это набор путей,которые проходили или достигли узла отказа Г( . Допустим, что после группировки количество операций равно значении п 0 в ). Далее- необходимо выполнить следующие действия над каждой из п0 операций:

-выполнить инициализацию, 1?=Га1зе;

-выполнить сбалансированную нагрузку в . так,чтобы п0 < = т, (провести такую группировку операций,чтобы полученное число новых операций не превышало число процессоров лО;

' -размещение графа задачи Gt в граф процессоров ВР таким образом, чтобы соседние операции в размещались ' по возможности в соседних ПЭ в ,это обеспечивает гарантию минимального диаметра систем;

-выполнить процедуру маршрутизации для графа вадачяКЗр : при успешной маршрутизации РМгие, иначе выводить набор путей отказа Р{ и набор узлов М/ ;

-если И=Га1Бе,тогда выполнить следующие настройки до тех пор, пока Я=Тгие: а) 1.если пв< ш ,для р{, р/.....Ре* в Р*необходимо проверить, можно ли установить связь( осуществить обмен) с процессорами в врнли нет,если можно выполнять это действие.

2. для Г/ , Гг , ... , ^ в (I;, определить существует ли пара путей в (ЗД с помощью сравнения результата маршрутизации до и поели обмена) и осуществлять обмен если можно.

г1' для i , i ч- i n„- 1 , объединить пути до того момента,-лока количество путей отказа в Pf после группировки не увеличивается.

1. Выполнить группировки для ^операций в G^ в операции, где ir..,-l.

2.ТРаамещать задачу в графе G р .

'¿, Выполнить процедуру маршрутизации и получить новые Pf и Nf , если они существуют.

В работе приведен анализ временной сложности при вычислении перечисленных процедур, Процедура группировки требует времени, равного аначению Tt,» 0( п2-), где п количество операции. Процедура размещения требует времени,равного значению Тр= 0(г£+ n„« т)<=0(тг );где ^-количество ГО в TBC. Процедураа маршрутизации требует времени,равного величине 0(КН ),где й-количество каналов связи для маршрутизации процессов разменянных в Bp , где К<«0(п). Необходимое время для маршрутизации равно TR = 0(Кг + К*«!2-) < 'Olm3). В работе показано, что при отказе процедуры маршрутизации управление передается к процедуре самонастройки. Время выполнения етой процедуры равно TAß <= 0(m*) -0(inМаксимальное время планирования п процессов в транспьютерной сети с m КЗ равно величине:

i/л + ТР + TR + TAJ) < = СКта'Лп*- , т* >)

При атом требуется выполнить процедуру самонастройки при планировании каждого процесса. 'Если нет необходимости в процедуре са-мгзастройки,то вначение Tn < = 0(max{ nS m >).В этом случае в TL2 поддерживаются только процедура маршрутизации и мультиплексирования.

При реализации БПФ одиночный транспьютер с внутренней памятью 4К байт на кристалле.может хранить информацию о 2Б6 точках без необходимости использования внешной памяти. На рис. 1 видно, что можно вычислить 32768-точечное БШ> (2Т8 х 2Т7) без применения внешней , памяти. При тактовой частоте 30 Мгц (ТВ00-30) транспьютер, реаливующиий арифметическую обработку будет выполнять 1024 точечное БПФ в одном транспьютере га 11,80 мс,а для 16 транспьютеров с топологией гиперкуба это время будет составлять 1,765 мс. В работе представлен график зависимости времени вычисления от' размерности исходных данных. В нем показано, что при вычислении ВПФ с числом отсчетов менее 4096 в гиперкубе, оптимальнее количество транспьютеров равно 4,добавление транспьюте-

ш

ров в сети для вычисления ЕПФ с указанным числом точек не дает значительного выигрыша во времени. Для вычисления 32768 точек ШФ при применении 4 и В транспьютеров в сети получаем ускорение 'равное 3,34 и 5,61 соответственно,а при применении lö и 32 транспьютеров эти значения равны 8,38 и 11,19. Последний случай показывает,что при удвоении количества ГО не получается значительного выигриша во времени. Для вычисления 1024 и 32768 точечного ВЛФ эффективность вычисления равна 327. и 54% соэгвествел-но. То есть эффективность вычисления увеличивается при увелечении массива данных входных отсчетов.

Разработчики транспьютера уже объявили о разработка ¡sonoro поколения транспьютеров, серии W (Т9000),с быстродействием 1С'.' Mips и 20 Mflops. Интересной особенностью новых транспьютеров является введение в их состав "Виртуальных линков" ,т. е. встроенных мультипплексоров>позволяющих расширять число линков до необходимого количества, требуемого согласно используемой архитектуры сети. Скорость обмена по линку доведена до 100 Шит /се дуплексном режиме. По всем параметрам он в десять раз быстрее, чзи Т0ОО. Т9СЮО состоит из двух' чипов: это Нх-транспьютеры и схема пакета переключателей С104. Задержка при передачи пакета сообщений в С104 составляет Б00 не. При применении транспьютеров серил НКТ9000) южно улучшть перечисленные выше результаты с кратностью 10.

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

1. Предложен анализ существующих алгоритмов ВДОП, определены приемущэствз я недостатки этих алгоритмов при их реализации в ТЕС.

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

3. Предложен способ реализации ВДОП в TBC, который характеризуется высокой'степенью параллелизма к минимальным числом пересылок данных.

4. Предложен способ реализации вычислений итеративных алгоритмов в TBC.

5. Предложена' гиперкубическая организация ТЕС в обобщенном виде для любого количества ПЭ и при этом определены пптималыкый

- диаметр системы,плотность сообщений в линиях связи и занятость ОГС.

6. Предложен эффективный способ планирования вычислительных

процессов в ТВС.

?, Предложена методика определения эффективности вычисления 6Д0П в ТВС.

РАБОТЫ. ОПУБЛИКОВАННЫЕ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Русанова О. В. ,асл. А. X. Ы, Асадуэ^аман, .Реализация алгоритма БШ> ь транспьютерной системе. Киев,1993-Зс. ( Вестник КПИ, принята к печати).

2. А. И. М. AS3iiuzza.'ii3n, The implementation of asynchronous parallel iterative algorithms on transputer system,Bangladesh university of engineering and technology,The scientific publications: Dhaka, pp. ¡5c, ID 103166/93 (June-1993).

3. A. H. M. Asaduzzanian. Concurrent processes mapped onto the transputer network,engineering university,Bangladesh,The scientific publications,Dhaka,pp. 3, ID 103187/93 (August 1S93).

Автор </■'!■ .