Методы построения параллельных алгоритмов для реализации на систолических матричных процессорах тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

г" р. я

^ и '1 Академия наук Беларуси

ИНСТИТУТ МАТЕМАТИКИ

ЛИХОДЕЯ НИКОЛАЯ АЛЕКСАНДРОВИЧ

УДК 619.6+681.3.012

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

01.01.07 - вычислительная математике

Автореферат

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

МИНСК - 1996

Работа выполнена в Институте математики Академии наук Беларуси

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

профессор Абрашин В.Н.

доктор физико-математических наук профессор Ермаков С.М.

доктор физико-математических наук профессор Жидков Е.П.

Оппонирующая организация - Вычислительный центр Сибирского.

отделения Российской Академии наук

Защита состоится на заседании совета Д 01.02^02 по защите диссертаций на соискание ученой степени доктора физико-математических наук в Институте математики Академии наук Беларуси по адресу: 220072 Минск, ул. Сурганова, 11.

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

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

Г996 г.

и

Ученый секретарь совета по защите диссертаций

• ст.н.с. ЛЛстЦ^— ¿.И. Астровский

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

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

Связь работы с крупными научными программами, темами. Исследования проводились в рамках бюджетных тем "Исследование математических проблем теории принятия решений, моделирования процессов легирования многослойных полупроводниковых структур, проблем размещения и укладки графо-геометрических систем, проектирования систолических вычислителей на базе СБИС" (19901993) и "Метода моделирования процессов переноса в полупроводниковых структурах и отображение вычислительных алгоритмов на систолические матричные спецпроцессоры" (1993-1995), включенных в план важнейших НИР в области естественных, технических и общественных наук по Республике Беларусь.

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

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

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

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

Основные положения диссертации, выносимые на защиту:

1. Метод стыковки двух базовых вычислительных графов. Метод позволяет получать параллельные формы сложных (деко.чшзиро-ванннх) алгоритмов.

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

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

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

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

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

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

- 9. Способы получения двухуровневых вычислительных графов.

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

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

13. Параллельные формы алгоритмов вычислительной математики, представляющие модели систолических матричных процессоров. Соответствующие модели систолических матричных ' процессоров защищены авторскими свидетельствами и патентам!.

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

Апробация результатов. Основные результаты диссертации были представлены и докладывались на vil Всесоюзном совещании "Методы Монте-Карло в вычислительной математике и математической физике", Новосибирск, 1985; на II Всесоюзной конференции по актуальным проблемам информатики и вычислительной техники, Ереван, 1987; на I Всесоюзном семинаре "Логические метода построения однородных и систолических структур", Москва, 1988; на i Всесоюзной конференции "Однородные вычислительные среды и систолические структуры", Львов, 1990; на международных конференциях "Parallel Computing Technologies", Новосибирск, 1991; "Real Time Data Distributed Front-End Prooosaing", Дубна, 1994; "Parallel Processing and Applied Mathematics", Ченстохова, Польша, 1994; на семинарах в Институте математики АН Беларуси, в Институте прикладных проблем механики и математики АН Украины.

Опубликованность результатов. По результатам исследований в рамках данной диссертации опубликовано 93 работы, включая два выпуска библиотеки научных программ и 45 изобретений. Основные результаты диссертации опубликованы в работах [1-26].

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

СОДЕРЖАЩЕ РАБОТЫ

Приведем аббревиатуры, часто используемые ниже: ПФ -параллельная форма, ВГ - вычислительный граф, БВГ - базовый вычислительный граф.

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

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

Первые проекты систолических процессоров получили эври-

стически Kvrng H.Т. И leiserson C.E. Затем Cappello P.R. и Steiglitz K., Moldovan D.I., Quinton P., Li G.J. И Wah B.W. предложили первые методики синтеза систолических структур по задашюму алгоритму. Эти методики базируются на построении вычислительной модели алгоритма и отображении этой модели на систолическую структуру. Следует отметить, что способы отображения алгоритмов на систолические структуры можно рассматривать как способы построения параллельных форм алгоритмов для реализации на систолических процессорах. Заложенные в перечисленных работах идеи развили Воеводин В.В., Краснов С.А., Каневский Ю.С., Выжиковский Р., Седухин С.Г., Садахов Р.Х., Kung S.Y., Ramakrishnan I.V., Varman P.J., Chen M.S., Jagadish H.Y., Rao S.K., Kailath Т., Lee P., Kedera Z.M., Ulman J.D., Quinton P., Moldovan D.I., Portes J.A., Rajopadhye S.V., Fuo'irooto Ii., Shang VT. Метода построения параллельных форм алгоритмов для реализации на систолических матричных процессорах разрабатывались и исследовались начиная с <987 Г. п Институте математики Академии наук Беларуси Соболевским П.И., Косьянчу-ком В.В. и Тиунчиком A.A.

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

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

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

xq(v)=FKtq(z,(v-<p1),xs(v-<i>2),...,xg(V-<p(3)), (1 )

l£q<Q, tete A, VsVycZ0-, где Xq, 7<q<Q, - переменные алгоритма; ü - точка d-мэрнаА решетки 2d; , uteh, isqsQ, - функции Q переменных;

Ф0. - ä-мерные векторы с координатам, не зависшими от

точки v, 1<Х<А, - области изменения точек v, nf^ =0 при

При фиксированном к для всех точек переменные

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

F^ £.....G* '■te0--60™ ^VjU^o.. .и7д будем называть областью вычислений алгоритма (1).

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

Пусть Gd(V,E) - граф зависимостей некоторого алгоритма, заданного в виде (t). Множество его вершин V совпадает с областью вычислений алгоритма. Каздой вершине соответствует вычисление, состоящее в выполнении Q операций, задаваемых функциями 1 ''' ^Qarac,rB0 ЛУГ EcVxV определяется

множеством пар информационно связанных вершин. Кзадую дугу (и-фд,и;сЕ, опрэделяицуи обмен информацией юзду вершинами

u-<f>g,v^V, ыояяо характеризовать вектором ф^. Таким образом, множество дуг графа зависимостей алгоритма (1) характеризуется набором Еекторов ф=Гф?,<р2,,.,,(pQ). Будем предполагать, что граф Gd является строго направленным. Это означает, что существует вектор п=(п},...,nd), образующий острые углы со всеми векторами множества Ф.

Введем в рассмотрение тайшрующую функцию Значе-

ние t(v) определяет время выполнения вычислений, соответствующих вершине ueV, и устанавливает принадлелшость тому или иному ярусу параллельной формы. Будем считать, что за единицу времени в вершине выполняются все предписанные ей операции и что для любых вершин и v2, связанных дугой (vjrv2), выполняется условие t(v2)-t(v1)z.1. Таймировать вершины строго направленного графа зависимостей (распределять по ярусам ПФ) будем посредством функции

t(v)=<n,v>+tn- min <n,V>=<n,V-V . >+t_, (2)

и min u

где <-,-> - знак скалярного произведения, tQ - произвольное целое неотрицательное число (номер первого яруса), вершины первого яруса v , &V определяются условием <n,v >=min<n,v>.

171171 min

Какдой области У^ соответствует свой тип веришь Будем пользоваться следующей формой описания фушсциошфования вершин типа А., реализующих функции Р^ ^ в области

д(£Ь.....V и<рЯ1' ^к' 0)

Такая запись означает: вершины типа Д. расположены в точках и множества V,; входные данные 1.п ,... ,Г поступают в вершину

по дугам, определяемым векторами <р;,...,<р0 соответственно; выходные данные 0.. ......О,. ъ вычисляются в соответствии с

М' I ч

функциями Р^ результаты вычислений передаются соседним вершинам с задержками 7г}=<п,ф|>,... ,Л0=<п,ф0> соответственно по дугам с направляющими векторами <р(,...,<рв.

Помеченный таким образом граф зависимостей алгоритма (1) назовем базовым вычислительным графом. БВГ - это четверка (V,Е^,Р), где 7,Е - множества вершин и дуг графа зависимостей реализуемого алгоритма, I - таймирунцая функция, Р={Р^(о), иеУ^, - множество функциональных описаний вершин Л

типов.

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

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

Обозначим через (?-=<?-(7а,Е?'-,га,Рх), а=1,2, два базовых вычислительных графа, га'(ь)=<па,v-v'^in>^■t<^,

К ^ < ф а *

Пусть результаты вычислений в G1 являются входными данными для вычислений в G2. Предположим, что вершины, реализующие вывод этих результатов из G1 и ввод их в G2, расположены в областях VoutcV' и VincV2, причем v°ut и Vln принадлежат нокоторым гиперплоскостям.

Под стыковкой базовых, вычислительных графов G1 и G2 будэм понимать построение нового кусочно регулярного БВГ путем совмещения с' и C,s в пространстве и согласования их работы по времени. Пространственное совмещение (объединение) означает размещение С* и G2 в zd так, чтобы V1 и V2 не пересекались, а векторы, соединяющие любую пару информационно связанных вэриин youteyout и yin^ytn фцщ одинаковы. Временное согласование означает, что временные интервалы меаду выводом данных из G1 и их вводом в Gs одинаковы: t2(vin)-t' (vautгде целое полоютельноэ число h одно и то же для любой пары информационно связанных воршш uotiieV°ui и vln*Vin.

Формально реаллзецая пространственного совмещения с' и G2 осуществляется еКинным преобразованием L:v+Av+b, veV2, с целочисленными матрицей А и вектор-столбцом Ы

Тоорзма I. Пусзь скоДракешэ Ъ удовлетворяет условия«; а; А-АТ*АТ-А*=Е (Е - единичная хсарица), deW=i, б) v'nirW,

где i73«{ye2d| v-Lv, vcV2), а ветор в один и тая же Оля хобой пары информационно c&nsomxz вершин v°aiey°ut и vincVln. Toeöa отобрахенш I осущзсшвлязя пространственное совмещение G1 и С2- :

Тоораш 2. Пусть базовые вычислительные грсфх £?' и G2 пространственно ео&сгцаны, Тогда рабагл G* и G3 согласована по вролет когда и шиъко тогда, когда

2) для всех youieV°ut,

где 6ерша. определяется, условная

■» min <п' Зи>, tteVout

Теореш 3. %сг«ъ базовые вычислительные графи С1 и С2 со-

сттсовсш, то есть со&хещет в пространстве и их работа согласована по врелени, П=<п1 ,е>. Тогда тОлирование вершин графа С2 8 зависилосгт от иг расположения в обмет и=1и,

и«У2} осуществляется с похщыо фуикцш

Тагом образом, базовый вычислительный граф бСУ.ЕД.Р;, получаемый стыковкой б'(V1,Е1д' ,Р1) и С2(V2.Е2.¿2.Р2;, задается следующим образом: 7.) V=У'и1У2, , 3) Ци)=

если ЦеУ1,

_ р=р'иьр2, где ХР2={1Р?(и;,

и2(и;, если Л Л

В разделе 1.3 рассматривается пространственно-временное отображение БВГ на ВГ менькей размерности. Необходимость получения таких ВГ обусловлена тем, что параллельные, формы алгоритмов, задаваемые й-моршми базовой вычислительными графами не могут быть непосредственно выполнены на г-мерных (г=7,2,3) систолических матричных процессорах, если й>г, так как требуется еще указать, в коком процессорном элементе (ПЭ) матричного процессора и в какой мог/тент времени будут выполнены операции, соответствующие вершинам БВГ.

Отображение ЕБГ на.ВГ осуществляется о поглощью линейного оператора (функции размэщешш) тс:2а-»гг, г<й. Определим отображение базового вычислительного графа 0(7,Е,^,Р) на вычислительный граф следующим образом:

— - граф, у которого Е%=<(о1,1>г)<&гхГ"\ и2«тсГи2;,

— - многозначная таймирущая функция, иеУ,

%(v)=v), для которой требуется, чтобы все ее значения

при фиксированном 1мУ'я: были различны, что равносильно условию

t(v1)*t(vг), если (4)

— Р%={Р^(и), /5Л5Л; - схеш функционирования вершин ВГ в различных режимах. Отображение Р*Р% будет рассмотрено

ниже.

Известно, что если размерности БВГ и получаемого ВГ отличаются на единицу (в~г=1), то условие (4) обеспечивается требованием <п,в>*0, где вектор такой, что к(з)=0. Если то это условие допускает следующее обобщение.

Обозначим ТоУ^Ги^г'-1) и=и,-и2> V, ке1«!$=П*г2й|

2={Кат*хп(¥ъГ})\(0сЖй}.

Тоора«а 4. Боли x(v¡)=ъ(vг) для кешгарад и;,иг«У, и,*1>2>

ш t(v1)*t(vc,) когда и шльио тогда, когда

<п,е>*0 ДЛЯ йеЯ. . (5)

Условие (5) иалоконструктивно. С его помощью моззга лишь прозерить, удовлетворяют ли условию (4) Конкретные оператор % и таймирувщая функция В раздело 1.3 приводится правило, позволяющее во топа случаях для заданного отобракения % найти шюеоство всех тайшруицшс функций вида (2), удовлетворяющих вместе с отображением я; условию (4).

В разделе 1.3 таккэ показано, как можно получить описание функционирования Р^ вершины получаемого ВГ из функционального описания Р^ соответствующего прообраза. Для этого используется более детальное ш сравнению с <з) функциональное описание вершин:

.....1%), (6)

если , то в описании равенства ЙдСр;=йд~'С(3-и.

отсутствуют. Здесь в описание введены переменные Через обозначено значение переменной в момент времени Равенства в описании (6) означают: Я, ) - присвоение переменной

Пп( 1) в момент времени г значения „(1т ;;

Ч л»ч . ч^ ч

=Я*_,ГР-О - присвоение переменной Л^гр; в текущий момент времени 1 значения переменной Е ($-1) в предыдущий момент вре-

мони 0(р - вывод из вершины в момент t+f.

Пусть тсСсрдМО, Тогда функциональное описание

вершины ВГ в ракше Л получается заменой в описании (б) векторов фд на %(<Рд):

.....

Если для какого-либо ,2,... ,Я), то в функциональном описании (7) следует вместо ^ писать а

равенство ) опускать.,

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

Ключевыми особенностями предлагаемого подхода являются:'

1) пристыковка к БВГ дополнительных ВГ, обеспечивающих ввод данных и вывод результатов вычислений только черэз две граничные вершины линейного вычислительного графа;

2) раздельное оптимальное таймирование ЕВГ и Пристыкованных ВГ;

3) включение в структуру получаемого ВГ магистралей, порождаемых пристыкованными к БВГ вычислительными графами

В разделе 1,5, с помощью разработанной в первой глава методики, построены ПФ алгоритма Гаусса-Йордана о предварительным умножением на транспонированную матрицу, алгоритма Гаусса-Жордана с частичным выбором ведущего элемента, алгоритма решения задачи наименьших квадратов.

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

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

.Разработанные в разделе 2.1 (ЛПарГПос стратегия разбиения) и разделе 2.2 ('ЛПосГПар стратегия) метода ориентированы на получение линейных вычислительных графов, являющихся моделями наиболее удобных для практической реализации систолических матричных процессоров - линейных СМИ. По сравнению о известными способами предлагаемые процедуры получения линейных ВГ проще и эффективнее. Приведем основные результаты раздала 2.1.

Пусть А - заданное целое положительное число, ic;zd-»z -

линейное отображение, удовлетворяющее условию %(у)^((0),(1)}

для всех (реф. обозначил К ,_=min %(v)f B=fmax %(v)-K. )/h.

min ^¿f ^y mir»

Не ограничивая общности, мокно предполагать, что В - целое число. В противном случае следует расширить область вычислений V и положить B=f(max %(v)-\min+1 )/К\, где fa] =minfz&2 | z>a).

Разобьем множество вершин 7 на подмножества Vp=ft*sV| kmlr+(f>-1)tev.(v)skmin+$K-1}, ß=/,£\ ... ,В. функцию размещения

/;V-»z, задающую для каждой вершины œV местоположение вершины

вычислительного графа, выполняющей приписанное вершине и

А

вычисление, определим следующим образом: с \1 ^(и), где

В

Таймирущую функцию определим равенством £ (c^+<n,v>)-

(v), где Ср - константы.

Теореиа 5. При филсированнол п хшаисиъная бисапа параллельной форш алгоритма достигается при аг,ог, ...,Cg, задаваемых рекуррекгтии coommenusuai Ср+ f=Cp+m

<В-1, где с. выбирается произвольно, xfl=mln <n,<p>-f, Оп={фсф|

Р (рвФр Р

Параллельная форма алгоритма заданной ширит А для

реализации на лшейном систолическом матричном процессоре шкет быть получена слодупцшл образом»

1. Выбрать линейную функцию удовлетворящую условию п(ц)ъ((0),(1)) для всех <реф.

2. Задать Л, определить В и области Ур, Ур.

3. Выбрать направляющий вектор графа, удовлетворявший усло-

В

вии <п,а>*0 для ((Ур»Ур;лкегтс)\(0).

4. Задать константы с(,сг,.. .,св рекуррентными соотношениями

Б. Вычислить временные задеркки Ь V*?, <р*Ф

{\(<р) - задержка в вершине V данного, пересылаемого в направлении вектора <р): Г1и((р)=<п,<р>, если и.и+срвУр, 75рзв,

6. Получить ПФ алгоритма в вида вычислительного графа. Граф содержит заданное число Л вершин, связи меяду вершинами определяются одномерными векторами с координатами О, 1, 1-Л. Задержка в вершине /(V) данного, пересалавмого в направлении

вектора f(v+q>)-f(v), определяется величиной \(ср); если f(v+(?)-f(v)t=0, то данное остается в вершине f(v) и будет участвовать в вычислениях через временной промекуток hv((p).

Основным недостатком известных реализаций ЛПарГПос стратегии является наличие у получаемого матричного процессора глобальных менсоэданений, что нежелательно для изготовления процессора на Оазе технологии СБИС. В разделе 2.3 цредлагает-ся ЛПарГПос способ построения параллельных форм алгоритмов фиксированной ширины для реализации на двумерных матричных процессора* без глобальных межсоединений.

Пусть задано линейное отображение icrz^z2, %=cszf,zs), -¡с} :zd-»2, удовлетворяйте условию %(y)<s( (0,0), (0,1),

(1,0), (1,1)) для фвф. Пусть Л и Л - заданные четные числа. Будем предполагать, что к(У) - прямоугольная область вида %(V)'{%(v)ezs\ l£Zt(v)^Q-A, H%2(v)s?-L), где В и Г - целые числа. Выполнения этого предположения всегда можно добиться аффинным преобразованием и (или) расширением области 7. Разобьем область 7 на подобласти

x^v^Ufß-DA, %s(v)=öH7-1MJ,

В Г

U u isteA, Hösi,, isßsB, 15Т£Г.

ß=f 7s,t p' I

Функцию размещения f:V+z определим следующим образом: А/г Ь./г

Таймирувдую функцию определим равенством

В Г

t(i>;= е е (сл ~+<n,v»1v (v), где cft „ - константы. ß=t 7=) Р»г Р>Т

обозначим

рй min <n,ra> -1, ой „= min <п,ф> -1, гй ,= müi <п,ф> -1,

ß'7 Ф-®Рл Рл ß'r Ф-хр,7

(p=v2-v)f fisosn), v2*Vpf1ty astet»,

фр(7=г<Н>1 <p=u2-u,, (Hteh), v^r+f

To = max fmax <7i,U> - min <n,v>}+1, P'l I<XSK, t)e7X.e .jsV^'0

уд max fmax <n,v> - min <n,v>}+1, P'7 usxsA. „.yX.Ö ^X.Ö

1<Q<A ^ß.T ß.7"

un max fmax <n,v> - min <n,v»+1,

P I g

Пусть zpfT>maxf-qß(T,yß(TJf ,^-Гр^, . JißsB-i,

}<"f<r~1. Тогда имеет место

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

с,>} - произвольно, %ltrcß,Suß,r (8)

1SJSV-1: cf,7+rcBl7+uB,T' %>,7+rcß.7"*Uß.7+i• H&B-i.

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

1. Выбрать линейную функции %, найти область %(V).

2. Задать Л и Д, определить В, Г, найти области V^^, V^J®.

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

В Г

ВИЮ <П,8>*0 для 8eS= и и ((7Л „öVft ) \ ГО>.

ßxt.y=t P'l P'l

4. Вычислить временные задеркки: hu(q)=<n,q», если u.twpe

если фсфр17>

\(4>)=Zptl+<n,4», если <реФрл, ««рвТр>7+|? \(<р)=

5. Получить параллельную форму алгоритма в виде ВТ.

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

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

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

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

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

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

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

4. Выбор оптимального таймировашм (временного регаша функционирования Берлин вычислительного графа), согласованного с оператором отображения и но зависящего от числа итераций.

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

В разделе 3.2 предложен способ построешхя параллельных форм итерационных алгоритмов .при заданном числе шагов. Число вэршпн вычислительных графов, получаемых при таком подходе, кратно числу реализуемых итераций. Полутона I© алгоритма последовательной верхней релаксация слотом линейкнх алгебран-чесюй. уравнений (СЛАУ) вида

coVVrV

(9)

где Yj, FJt J=0,1,...,1!, - вэктор-столбцн раз:,:эрности 11, At, A2,...,án, B0,Bt,...,BN_j - диагоналышо ÍM патрицы, CQ, C(,... ,C;? - трехдиагоналыше M*U матрица. Такого вида СЛАУ встречаются, например, при числешюм pecensi двумерных эллиптических уравнений в частных производных.

В разделе 3.3 предлагаются способы построения параллельных форм итерационных алгоритмов для реализации На линейных матричных процессорах о произвольно выбранным числом процессорных элементов. Пусть макрооперация, нродставлякцая итерационный' шаг алгоритма, задана в вида однородных рекуррентных уравнений (1), Gn(Vn,Em) - граф зависимостей для выполнения п-го итерациошого пага исходного алгоритма; Gn является графом зависимостей алгоритма (1). Граф зависимостей для согласованного выполнения произвольного числа пагов [.гогзю получить, используя аппарат пространственной стыковки (раздел 1.2) d-мерных графов, последовательно пристыковывая G¿ к Gf, G3 - к графу, полученному стыковкой С, л Gz, и т.д. Формально стшсов-ка каждого графа Gm с цепочкой графов, полученной стыковкой С;, G2,...,Gn_;, осуществляется аффинным преобразованием

L Пусть (f=G.o( о i G ) - цепочка графов, описывающая

m т ®

произвольно заданное число И итераций исходного алгоритма, и

Vй•= и у - множество вершин графа G", 4* - множество векторов,

SU f

характеркзувдах дуга втого графа. Предполагается, что цепочка графов ограничена цилиндром, диаметр которого не зависит от U, и что число векторов в множестве Ф* не возрастает, начиная с некоторого U. После того как граф С* построен, для получения параллельных форл заданной ширины в виде линейных вычислительных графов можно применить методы, разработанные в разделах 2.1 и 2.2. Следует лишь а георемах и выкладках этих параграфов область V заманить на область Vя, множество Ф заменить на шоке с тво ф", а также удовлетворить слэдуидее ограничение, позволяющее получать параллельные формы, у которых ширина и функционирование вершин не зависят от Uz я аннулирует направляющий вектор образующей цилиндра, ограничивающего граф G4, если используется ЛПосГПар стратегия разбиения, и и: не аннулирует направляющий вектор образующей цилиндра, в который заключен граф GH, если используется лПарГПос стратегия разбиения. Предлагаемый подход демонстрируется на примере построения ПФ алгоритма последовательной верхней релаксации для решения СЛАУ с плотной матрицей. ' •

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

В разделе 3.5 синтезируются вычислительные графы, представляющее юдела систолических матричных процессоров для решения методом матричной прогонки (блочным методом Гаусса) СЛАУ вида (9), где 4,,...,^, ß0,...,BN_t, C0,Cf,...,CM - ЫхЫ плотные матрицы, У0,...,YB, PQ,.,.- вектор-столбцы размерности U. Необходимость решения большого числа таких СЛАУ возникает, например, при численном решении нестационарных систем уравнений математической физики. По сравнению с известными систолическими структурами, реализующими метод Гаусса, полученные модели систолических процессоров требуют более чем на четверть меньше оборудования при одинаковых временных затратах.

Анализ алгоритмов вычислительной математики и цифровой

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

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

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

В разделе 4.2 получены вычислительные графы для выполнения операции умножения с накоплением э;-а-Ь, где э, а, Ъ - некоторые числа, представленные в дополнительном коде.

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

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

В разделе 4.5 показано, каким образом разработанная методика синтеза двухуровневых вычислительных графов позволяет в некоторых случаях получать особый вид двухуровневых ВГ - вычислительные графы тканевой структуры.

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

В пятой глава используются следующие обозначения.

U - знак математического ожидания (знак среднего значения).

£в, Osaste», - выходящие из нуля винеровский или центрированный пуассошвсккЗ (с параметром Л,) процессы, т.о. £в -однородный процессе независимыми пряращэгашш, распределен-шаа по нормальному или по пуассоновскому законам.

DIO,ti - онабгешюе топологией Скорохода пространство функций без разрывов второго рода, определенных на отрезке lO,tJ и принимающих значения в к.

ц. - мара на пространстве. DCO,tJ, соответствующая процессу 5в. 1

JP(tfc(dU - континуальный интеграл ао мэре ц от интегрируемого функционала Р(-). С вероятностной точки зрения континуальный интеграл от функционала Р по мере, соответствующей процессу ig, «окно рассматривать как среднее значение функционала по траекториям процесса j

1(-) - линейный непрерывный функционал нз DIO,ti.

~ функция, равная единица при W и нулю при W.

k=1,2,... N-1,2,.*. , - независимые одинаково распределенные случайные величины, иршшмаицио с вероятностью A(pS) значения р=? ,2; в вшгаровском случае

Л(Я>~ i , x(ll)=(-1)p/t7ii, (10)

р р

в пу асооновском -

аР')= i n-M^/ty, x<p")s | (U(~i)pdn), aN=Vu4\t/iL (11)

tt~lit/ll, k-C,1,.. .,11, - точки равномерного разбиения отрезка [0,t] на N частой.

Приближенные формулы для вычисления ¿{онтануалыта интегралов по мэро ц, точные для функционалов 1Р(- ), р-0,1,... ,п, называются формулами п-fi степени точности.

В разделэ 5.1 рассмотрена аипрсксимация вшюровского и цэнтрироваиного луассоновского процессов

te4(»>-Av.(»h(httl(B), ß,fO,tJ.

Леша, Конечнолерныо распределения процессов схо-

дятся к нонетюлераи распределениям процесса

Следствие. Пусть ? - огрсничш&Л непрерывный в летрино пространства BtO,tl функционал. ■ Тогда ncsea лесто сходилость №(t('n)) - UF(i) при М-*«.

Зададим äv^(at,32) следующим образом:

-tt tt 2 Л

JJf(a1.B2)äi'2n(3l,asHSr(91,a2)d3ida2-m s ' f(tk ,th oo oo w 1 2

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

о "

ч*1 oo 2

где Q - натуральное, - вещественные или комп-

лексные числа.

Теорема 7. Пятую степень точности илееш следующая составная приближенная форлула:

t I П bfVt it]( ■))+

.....qN«llfc:l J J»«/ qV ílk'w

4=' 00 ' *

2

где в винеровскал случав R¡)n)(P)=~-¿F(0)+

i ^^ .tjí-и, Р,.Рг*о.

U'J р*-р* i,J=t Pj fc=í * ílV»tJ ' ¿ ' ¿

б ш/ассонобсков случае R(nH)(F)=—-—FfOJ+í^-l2—•

0 1 J Т]И|

У. LF(a-í-vh^tt tJí-)). 7 j*=* * 1 J 2

Teopsua 8. Пусть F - непрерывный на DIO.t] функционал такой, что селейанSo случайных величин i)lf=F() рабнолерно tашгрируело. Тогда tuteen лваю сходилоаяъ

J(Ui(P) - JP(WHÍ) при К-»®.

В разделе 5,2 для приближенного вычисления кратных интегралов

п 1 ~

J(f)=J,(f)'S f(ut,...,un) П -—в ' du

Rn Jls1 i

и кратных рядов вида

а> п V/ е J

j(f)*j2(í)* Е ......WI.V'

*t»•»•»♦„«о J

где / - функция n переменных, v^>0, ísjsn, строятся кубатурные формулы, которые в некотором смысле аналогичны составным квадратурным формулам для вычисления интегралов по отрезку fO,tJ: при фиксированной степени точности сходимость к точному значении интеграла (ряда) осуществляется ва счет увеличения цело-

численного параметра формулы Н, который задает количество интервалов равномерного разбиения отрезка iÖ,tJ, i=v(+v2+-•

Пусть V0' W>fV HJSn> i=vJ,V

ViÄ;=n (%0, V»1 (%t, V' • • •'1

e.=(0.....0, f ,0.....OJ, fs/sn, - вектор размерности n, у

J (j)

которого координата с номером J принимает значение, равное едшшце, а остальные координаты нулевые,

0 Np'ß* w ltJ=1 ft

N ,

■ £ ftt-iyp^^t^)), ß,,p2-0, в гауссовом случае,

Лае- /

---f(°.....? -, •

lf((1-(-DJ7t)l%(tb)), f,.T%4, в пуассо-

N к

новском случае

Т V" в

2 S V 7. +х[г>в, ).

2 <4>ta=t Ч S Ца Jj.J^t S Jf. *а -»г

■ - 4 E /^Vb

н W 1 ' 2 2

и xjrN) определяются формулами (Ю) и (11) (при Теорема 9. Составная кубатурная форлула J(f J* Е f П Е

^(fhR^ifJ+R^^f)

точна для хногочленов на к" пятой су хлорной степени.

Построенные в разделах 5.1 и 5.2 формулы показали высокую эффективность, соответствующие программы включены в библиотеку прикладных программ [6,11]. Однако эти формулы содержат К-кратшш сукш, вычисление которых на однопроцессорных ЭВМ при N>20 связано с большими затратами времени. Так как с ростом И растет и точность составной приближенной формулы, то возникает задача построения параллельных форм алгоритма вычисления кратных сумм для реализации на матричных процессорах, использование которых позволило бы вычислять суммы больней кратности.

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

Э<*>- Е - .....<12)

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

Тзораыа Ю. БГ с селъл верхшюш, реализующий 2м*'-2 операции алгоритм вычисления кратай сулш вида (12), задает параллельную форлу трини 7 и высоки 2я'1+2, ВГ с боселыо варюхнаш, реализущШ п( операций вычисления зе крата ¿их

су лл вида (12), садаеа параллельную форлу ширины в и высоты

ВЫВОДЫ.

Приведем основные результаты диссертации:

1. Разработан штод стыковки двух базовых вычислительных графов.

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

3. Разработаны и иесладовавд методы построения параллельных

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

4. Предложены метода построения параллельных форм итерационных алгоритмов.

б. Разработаны способы получения двухуровневых вычислительных графов.

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

7. Построены параллельные формы алгоритмов, лредстовлящпэ модели систолических матричных процессоров, для

- перемножения двух и трех матриц,

- реализации метода Гаусса-Йордана реиэния СЛАУ и обращения матриц без выбора ведущего алеиэнто,

- реализации иатодз Гаусса-Нордаиа реиэния СЛАУ с предварительным умногэклзм па тргнспошрованную матрицу,

- реализация метода Гауссз-Яордяпа о частичным выбором ведущего элемента,

- решения задачи панмопьслх 1Свадрзтов,

- решения частичной проблемы собственных значений степенным методом,

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

- реализации метода последовательной верхней релаксации реоения СЛАУ с плотной матрицей,

- реализация метода последовательной верхней релаксации рзпепия СЛАУ, получаемых в результата разностной аппроксимация двумерных эллиптических уравнений в частных производных,

- реализация блочного метода Гаусса решения СЛАУ, встречающихся при решении нестационарных систем уравнений математической физики,

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

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

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

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

1. Лиходед H.A. Дискретные аппроксимации винеровских и пуас-соновских континуальных интегралов // Весщ АН БССР. Сер. ф1з.-маг. навук.- 1985.- JS Б.- С. 3-6.

2. Лиходед H.A. Аппроксимация винеровских континуальных интегралов и кратных интегралов с гауссовыми весовыми функциями // 7-е Всесоюзное совещание "Методы Монте-Карло в вычислительной математике и математической физике", Новосибирск, 9-11 октября 1985 Г.- Новосибирск, 1985.- С. 6871.

3. Лиходед H.A. Две аппроксимации пятой степени точности винеровских и пуассоновских континуальных интегралов.-Препринт / Ин-т математики АН БССР.- Минск, 1986.- 18 с.

4. Лиходед H.A. Составные кубатурные формулы для кратных интегралов с гауссовыми весовыми функциями и кратных пуассоновских рядов // Докл. АН БССР.- 1986.- Т. 30, й 9.-С. 780-782.

5. Лиходед H.A., Соболевский П.И. О приближенном вычислении одного класса континуальных и кратных интегралов // Весщ АН БССР. Сер. ф!з.-мат. навук,- 1988.- й 1,- С. 3-8.

6. Лиходед H.A., Соболевский П.И. Стыковка базовых систолических вычислителей // Дом. АН БССР,- 1989.- Т. 33, JJ5.-С. 389-392.

7. Лиходед H.A. О повышении загруженности систолических вычислителей / Сб. Многофункциональные систолические структуры.- Львов: ИППШ.- 1989. X 20.- С. 32-38.

С. Лиходед H.A. Уточнение монто-карловской оценки континуальных интегралов // Весц1 АН БССР. Сэр. ф!з.-мат. навук.- 1990.- Jt 2.- С. 8-13.

9. Косьянчук В.В., Лиходед H.A. Реализация на линейных сис-.толических структурах метода Гяусса-Нордана решения матричных уравнений // Весц! АН БССР. Сэр. ф!з.-мэт. навук.-1990.- » 3.- С. 95-100.

10. Лиходед H.A. Синтез систолических вычислителей для решения систем линейшх алгебраических уравнений методом ЗеЯ-доля // Весц! АН БССР. Сэр. ф!э.-мат. нсвук,- 1991.- й 3,- С. 109-114.

И. Лиходед H.A., Бовдаренйо Д.Е. Систолический вычислитель для решения полной проблема собственных значений треугольным степенным методом // ВесЩ АН БССР. Сор. ф1з.-мат. навук.- 1991.- й 2.- С. 88-91.

12. MMioded H.A., Sobolevskii P..t., Tiountohilc A.A. Design of systolio at-rays for iterative algorithms: eigenvalue computations // Proo. Int. Conf. Parallel Computing Technologies, Novosibirsk, USSR, Sept. 7-11, 1991Published by iVorld Soientifio, Singapore, Itew Jersey, London, Ilong Kong, 1991.-P. 129-138.

13. Лиходед H.A., Соболевский П.И.. Тиунчик A.A. Один метод синтеза систолических структур, реализующих итерационные алгоритмы // ВосЩ АН Беларус!. Сер. ф!з.-мат. навук.-1992.- >5 3-4.- С. 109-113.

14. Kosianohoulc V.V., Likhoded H.A., Sobolevskii P.I. Systolio architecture array Bynthesis.- Преприпт /Ин-Т математики АН Беларус!.- Минск, 1992.- 24 с.

15. Лиходед H.A., Соболевский П.И. Один подход к проектированию одномерных систолических вычислителей // ЕесЩ АН Беларуси Сер. ф1з.-мат. навук.- 1992. !Ь 2.- С. 81-88.

16. Косьянчук В.В., Лиходед H.A., Соболевский П.И. Синтез одномерных ограниченных систолических вычислителей двумерного дискретного преобразования Фурье // Электронное моделирование.- 1992.- Т. 14» » 1.- С. 37-41.

17. Косьянчук В.В., Лиходед H.A. Синтез линейного систолического вычислителя для решения матричных уравнений методом Гаусса-Яордана с частичным выбором ведущего элемента //

Электронное моделирование.- 1992.- Т. 14, J6 2.- С. 36-40.

18. Kosianohouk V.V., Likhoded N.A. An approaoh to fixed size linear systolio arohiteoture array.design.- Препринт / Ин-т математики АН Беларуси- Минск, 1992.- 20 с.

19. Likhoded N. Cno-dimensional systolic array for solving least squares problea // Proo. 1-st Int. Conf. on Parallel Prooessing and Applied Mathematioe, Czestoohowa, Poland, September 14-16, 1994.- Czestoohowa, 1994.- P. 270277.

20. likhoded N., Tiountohil: A. Systolic implementation of matrix sweep method // Proo. 1-st Int. Conf. on Parallel Prooessing and Applied Mathematics, Czestoohowa, Poland, September 14-16, 1994.- Czestoohowa, 1994.- P. 286-293.

21. Лиходед Н.А, 0 синтезе лннойних систолических процессоров с заданным числом процессорных элементов // Вэсц! АН Беларуси Сер. фхз.-мат. навук.- 1994.- JЬ 3,- С. 98-103.

22. Лиходед Н.А., Тиунчик А.А., Дурко Б.А. Процессорные матрицы дая решения нестационарных систем уравнений математической физики на систолических процессорах // Электронное моделирование. 1995. Т. 17, й 2. с. 41-48.

23. Лиходед Н.А., Соболевский П.И., Тиунчик А.А. Построение параллельных форм заданной ширины итерационных алгоритмов для реализации на матричных процессорах // До:сл. АН Беларуси. 1995. Т. 39, X 6. С. 17-20.

24. Likhoded N.A. Design of fixed-width parallel forma of iterative algorithms for array prooessor implementation // Proo.Int. Conf. on Oomputer-Aided Design of Discrete Devioes (CADDD'95). Minsk,' Belarus, November 15-17, 1995. Vol. 2. p.33-33.

25. Лиходед Н.А. Метод построений параллельных форм алгоритмов для реализации на ленточных матричных процессорах // В0СЦ1 АН Беларусь Сер. ф1з.-мат. навук. 1996. а 1.-С. 88-93.

26. Лиходед н.£. Новый метод построения параллельных форм алгоритмов // Докл. АН Беларуси. 1996. Т. 40, * 1,- С. 5-8.

РЭЗШВ

Л1хадзед М1калай Аляксандрав1ч

МЕТ АЛЫ БУДАВАННЯ ПАРАЛЕЛЬНЫХ АЛГАРЫТМАУ ДЛЯ РЭАЛ13АШ1 НА С1СТАЛ1ЧШХ МАТРИЧНЫХ ПРАЦЭСАРАХ

Ключавыя словн: паралельны алгарытм, сютал1чная арх1тэк-тура, адлюстраванне алгарытмау, паралельная форма мшмалънай вышын1, паралельная форма гададзенай пшрын!.

Дысертацыя прысвечана распрацоуцы 1 даследаванню метадау будавання паралельных форм выл1чальных алгарытмау для рэал!за-цы1 на с1стал1чных матричных працэсарах. Распрацавана тэорыя, дазваляючая фармал!заваць усе этапы адлюстравання алгарытмау не с1стал1чныя структуры 1 атрымл!ваць паралелымя Форш алгарытмау м№1мальнай вшын! для рэал1зацы! на гэтых структурах. Тэорыя уключае иэраг новых метадау: метад стыкоуш базавых вы-л!чальных графа?; спосаб атрымання аднамерннх выл1чальных графа?; мет ада будавання паралельных форм зададзенай шыршп; мэ-тады будавання паралельных форм 1тэрацыйннх алгарытмау; споса-бы атрымання двухузроуневых виМчалъкых графа?. Пабудаваны па-ралельныя алгарытмы рашэння задач выл1чальнай матэматык! для рэал!зацш на матричных працэсарах.

РЕЗЮМЕ

Лиходед Николай Александрович

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

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

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

SUMMARY Hiokolai A. lilchoded

METHODS OP CONSTRUCTION OF PARALLEL ALGORITHMS FOR IMPLEiEHl'ATIOIf INTO SYSTOLIC ARRAYS

•Key words: parallel algorithm, oyatolio arohiteoture, mapping of algorithms, reintaum height parallel form, fixed-width parallel form.

Dissertation is devoted•to the elaboration and investigation of the methods of construction of the parallel forms of calculation algorithms for tha implementation into systolic arrays. Tha theory which allow из to formalized all stages of the mapping of algorithms into systolic structures and to obtain the minimum height parallel forms for implementation into tha structures is elaborated, Tho theory contains a number of new methods: the method of matching of basa calculation graphs, the approach to obtain one-dimensional calculation graphs, the method for the construction of fisod-width parallel forms, tho method for the construction of Iterative algorithms parallel foras, the approach to obtain two-levsl calculation graphs. Parallel algorithms to solve nurosrioal analysis problems by array processors is constructed.