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

л Л

1 ОБЪЕДИНЕННЫЙ ИНСТИТУТ ЯДЕРНЫХ ИССЛЕДОВАНИЙ

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

ТИУИЧИК Александр Александрович

УДК: 519.6 + 51:681.3.012

ИЕРАРХИЧЕСКИЙ МЕТОД ПОСТРОЕНИЯ ПАРАЛЛЕЛЬНЫХ ФОРМ ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМОВ ДЛЯ ОТОБРАЖЕНИЯ НА МАТРИЧНЫЕ ПРОЦЕССОРЫ С СИСТОЛИЧЕСКОЙ АРХИТЕКТУРОЙ

{01.01.07 — вычислительная математика)

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

Дубна 1995

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

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

Соболевский Павел Иосифович

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

Хоромский Борис Николаевич

кандидат физико-математических иаук Ланесп Евгении Борисович

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

институт, г. Москва

Защита диссертации состоится и ^ " . 1995 года

в час. мин, иа заседании Специализированного совета

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

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

Автореферат разослан " /1" СБИТЯбРЯ 1995 г

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

Специализированного совета Иванченко

кандидат физико-математических наук Зинаида Мироновна

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

Актуальность. Быстрое развитие технологии производства вычислительных устройств обусловило создание п и с о к о э ф ф е кт I: п -пых специализированных многопроцессорных систем, проектируемых с учетом особенностей реализуемых на них алгоритмов.

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

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

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

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

на СБИС-технологию.

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

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

Апробагргя работы. Основные результаты работы докладывались на меж дународных конференциях "Parallel Computing Teclmologies-91", г. Новосибирск, 1931 г., "Parallel Computing Teclxnologies-93", г. Обнинск, 1993 г., "Real Time Data Distributed Front-End Proccssbg", г. Дубна, 1991 г., "Parallel Processing ami Applied Mathematics", г. Ченстохова, Польша, 1994 г., на I Всесоюзной конференщш "Однородные вычислительные среды и систолические структуры", v. Львов, 1990 г., VI конференщш математиков Беларуси (г. Гродно, 1992 г.), заседаниях отдела математических проблем автоматизации проектирования Института математики АН Беларуси (1989-1995 гг.) к лаборатории вычислительной техники и автоматизации О ИЛИ (1995 г.).

Публикации. По теме диссертации опубликована 21 работа, список которых помещен в конце автореферата.

Объем и структура дассертацип. Диссертация состоит из введения, трех глав, разбитых на параграфы, и списка литературы из 170 наименовании. Объем основного текста диссертации - 159 страниц, включая 27 иллюстраций.

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

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

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

В параграфе 1.1 приведено описание специальных параллельных форм вычислительных алгоритмов, приспособленных для отображения на СБИС-процессоры, а также даны ссповиые определения и обозначения.

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

= ЯЫ» - гПМ» - 91).....- т

где /? - функциярпеременных хиз2,,-.,ау, Уг> •••>¥>. 13'»• •.. Ч - векторы из пространства 2,'п, определяющие координаты точек (и — у>?) и (и + »5/) в которых, соответстпенно, вычислена и используется в качестве аргумента функции пейичина ж,-. Область V — и,VI будем называть областью вычислении. Вектор, соединяющий точки области вычислений и соответствующий пересылке дапного ж,-между этими точками, будем называть вектором зависимости, а пек-тор, соответствующим вводу пли выводу этого данного - внешним вектором. Совокупность всех векторов обозначил через Е,

Граф £? = (К, Е) будем называть графом зависимостей, представляющим решетчатый алгоритм (1), если его. вершины идентифицируются с точками V 5 V, а множество дуг характеризуется пек-торами из множества Е. Граф зависимостей можно рассматривать как геометрический объект, отождествляя при этом его вершины с точками пространства 2т, а которых они расположены, а дуги зависимости - с соответствующими векторами, что дает возможность применять операторы аффинного отображения для преобразования графов зависимостей.

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

Пусть задай некоторый алгоритм и G — (V, Е) — его граф. Предположим, что мложестио вершив V разбито на такие непересекающиеся подмножества V¡, Vj,..., У//, что если v 6 V¡, и Vj и существует дуга (ir, и), то i < j. Тогда разбиение V — U^jV't назы-ш-.ется параллельном формой алгоритма, подмножества V¡, ..., V¡¡ — ее ярусами, а число И — высотой параллельной формы.

Граф зависимостей G будем называть строго налраилешшм, если существует такой вектор « ~ Ьг\,п2,..., п,„) 6 Z'", который образует острые углы со всеми Гекторами <p¡, 1 < q < Q, 1 < i < р. Множество всех таких пекторов для графа G обозначим через К(<?).

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

Квазисистолпчссклн граф зависимостей G будем называть систолическим, если все его векторы зависимости локальны, а число типов мсршии »того графа невелико. Решетчатый алгоритм, представляемый систолическим графом зависимостей, будем называть систолическим алгоритмом. ' ' .

Функцию вида

t(v)~ {¡i,v)-inm{rj, f)-i-10,

fCV

где (•, •) означает скалярное произведение, <о — некоторая неотрицательная целочисленная j-.онст.шта, будем называть таМмирующсИ функцией.

Та1Ьшруюг;ая функция нри фиксированном » G К(С) задает одну из варпллелышл форм алгоритма, представленного квазисистолическим ли. систолическим графом зависимостей G ~ {V, Е), и определяет режим рабохы систолического процессора.

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

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

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

Пусть графы зависимостей С91 и С!сс вложены в пространства 2° и ЪА соответственно, а их вершины определяются наборами координат V9' — (%{',..., и V1'-" — (г',"-,..., г^} соответственно. Каждой вершине V3' графа С?*' мояспо поставить п соответствие граф С'"", представляющий реализуемую на локальном уровне операцию, приписанную вершине у5'. ТакоН граф будем обозначать (гу', С1ое).

Суперпозиция 0'ир — (<?-"', представляет собой граф зависимостей, полученныМ заменоН вершин на графы (~о>1, размещенные в пространстве и реализующие приписанные

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

Пусть ("£'. ~ локаяыше графы, реализованные в пространстве и соответствующие вершинам И пусть глобальный граф С1 представляет собой. совокупность * информационно связанных вершин I <£<8. Тогда суперпозицию графов

и С!ос будем обозначать также - В

Теорема 1.1. Суперпозиция С" = (С1-', Ок*) =

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

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

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

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

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

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

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

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

Определим преобразование каждой вершины v = (vf, vlM) су-

перпозиции Е оператором Т( : Ъ0и( — аффинного пре-

образования

Т^»; = + '/'о

где - оператор линейного преобразования, гК- - лектор параллельного переноса, имеющие вид

•«-и. °»г)' *>•

Е — матрица тождественного преобразования размерности О х О, ОохЛ и 0,1*1) ~ нулевые матрицы размерности Й х (! и Л х 1) соответственно, - матрица размерности о' х <(, О о - Б'-мерш.'л; пулевой, а ф^ - ¿-мерный векторы. Обозначим через множество таких аффинных преобразовании ~£;-х 1 < £ < а,

что — Ех, — 0> а через Е ТА у с'1, С'/к) обозначим граф за-'

е=1 5 - '

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

Теорема 1.2. Грпф зависимостей Е СТ") представляет

л >/ * I

тот >ку алгоритм, что и суперпозиция Е ('•>,- , ТеС,).

с=г

В случае реализации глобального графа в одномерном прос-транстпе для каждой пары соседних перший , и г?' можно определить оператор : 7>пи 7лШЛ, Т(<) ~ -(-

;,''((), а преобразование графа (г,',задать оператором — Т(1)'Г(2)Т(3)'','%-1)Т(£). Обозначим через и инфор-

мационно связанные соседние области вывода и ввода н графах

Теорема 1.3. Если для графа квазнсисголического алгоритма £(*)> 6 У*' С 21, существует такое множество аффинных преобразований что выполняются следующие условия:

+ Фш « (КГ')(->, 2 < ^ <

ЗА, А 6 N : Ф(А{) = Е,

П|=1К(Ф{1)Ф(2) • • ■ ф С,

хо множество обеспечивает отображение графа квазисис-

толического алгоритма 3 (г>|', в граф систолического алгоритма Т^).

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

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

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

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

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

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

<*(*)+!

в суперпозиции графов зависимостей уменьшается с ¿(ж) -г 2 гЧ3ч)

{=1

до шах (£ — 1 + гДе " количество дуг дли пересылки

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

пересылки одного данного х в локальном графе 1 < £ < <1(х) +1.

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

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

Пространственное отображение суперпозиции графов зависимостей на граф систолического спецпроцессора определено посредством двух линейных операторов: П5' : Ъ° —> 2Г и П,0<: : Ъл —» 2Г (г = 0, 1 или 2). Образ П"ip^>,,иг, точки задает формула П^uPv'u^' = + П,05и,пе.

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

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

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

Процедура вложепия определяется формулой г»л = СР°г)9' + где Д - тах(ДЛ), Рп = (р/-),/"' = (р^) - матрицы порядка I? х Д и 6 X Д соответственно, = 1 при г = ] и = О

при С —- < г < Д, - диагональная матрица, Л -

ортогональная матрица.

Для вычисления матриц Р!), С? и Я разработаны формальные методы.

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

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

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

В параграфе 2.3 осуществлено построение систолического алгоритма для ¿{/-разложения матрицы и модификация полученного графа методом расширения.

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

В параграфе 3.1 рассмотрена задача построения двухуровневого систолического алгоритма умножения и сложения плотных матриц, реализованного на уровне поразрядной обработки информации. Для получения этого алгоритма использована суперпозиция графов систолических алгоритмов, построенных в параграфах 2.1 и 2.2. Полученная суперпозиция реализована в пространстве 2'. Рассмотрено вложение этой суперпозиции в пространство 7?. Показано,, что полученный в результате, такого вложения двухуровневый алгоритм является/систолическим. Па.базе этого алгоритма разработана вычислительная модель систолического процессора.

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

Параграф 3.3 посвящен построению двухуровневых и трехуровневых систолических алгоритмов решения полной проблемы собственных значении треугольным степенным методом. Дли построения суперпозиции, представляклцен такой алгоритм, использованы систолические графы алгоритмов перемножения плотной и нижней треугольной матриц, а также Х17-разложсшш (полученные в §2.2 и Ç'2.3 соответственно). Преобразование полученного н результате построения суперпозиции кпазисистолического графа зависимостей в систолический реализовано методом последовательных трансформации с последующим вложением полученного графа в пространство Z3. На основе этого алгоритма построены вычислительные модели двумерного и одномерного систолических процессоров. Кроме того, рассмотрела задача построения трехуровневого алгоритма для реализации итерационного процесса па систолическом устройстве с фиксированным числом процессорных элементов и построена соответствующая вычислительная модель.

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

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

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

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

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

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

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

1. Косьянчук В.В., Лиходед Н.А., Соболевский II.И., Тиуцчик А. А. О проектировании систолических вычислителей с двухуровневой конвейеризацией. - Львов, 1089. - G9 с.

- (Препринт / АН УССР. Институт прикладных проблем механики и математики,- N 20-89). - С. 42-47.

2. Лиходед Н.А;, Тиуцчик А.А. О синтезе двухуровневых систолических вычислитеяеИ // 1-я Всесоюз. конф. "Однородные вычислительные среды и систолические структуры", 10-20 апр., 1990: Тез. дока. Т. 1. / Львов, 1990. - С. 89-95.

3. Тиуцчик А. А. Систолический вычислитель с распределенной арифметикой для умножения двух матриц // 1-я Всесоюз. конф. "Однородные вычислительные среды и систолические структуры", 10-20 апр., 1990: Тез. докл. Т. 1. / Львов, 1990.

- С. 139-142.

4. Лиходед II.А., Тиунчик А.А. О проектировании двухуровневых систолических вычислителей. - Ми., 1990. - 5G с. - (Препринт / АН БССР. Институт математики; N 2С(42С)).

5. Likhocled N.A., Sobolevskji P.I., Tiotintcliik А.А. design of systolic arrays for iterative algorithms: eigenvalue computations // Proc. Int. Conf. "Parallel Computing Technologies - 91", Novosibirsk, USSR, Sept. 7—11, 1991. /.World Scientific, Singapore, New Jersey, Loudon,

' Hong Kong, 1991. - P. 129-138.

6. Tiountchik A. A. Design of multi-level processor arrays // Proc. Int. Conf. "Parallel Computing Technologies - 93'-, Vol.3, Obninsk, Russia, Aug. 30 - Sept. 4, 1993. / Computing Center, Novosibirsk, Russia, 1993. - P. 691-696. ;

7. Kotov V., Aleksandrov I., Pose R., Liklioded N., Tiountchik A. On a systematic approach to the programming of the systolic structures for fast trigger pipe-processing. // Int. Conf. ou Real Time Data Distributed Eront-End Processing, JINR, Dubna, Russia, June 27 - July 1,1994. / Conference Handbook, Dubna, Russia, 1994. - P. 31 32.

8. Лиходед H.A., Соболевский П.И., Тиунчик A.A. Синтез систолических вычислителей для решения полной проблемы собственных значений треугольным степенным методом. - Ми.,

1991. - 40 с. - (Препринт / АН БССР. Институт математики; N 12(462)).

9. Тиунчик A.A. Метод построения алгоритмов для систолических процессоров уровпп разрядов // G Копф. мат. Беларуси, 29 со г; г.- 2 окт., 1902: Тез. докл. Ч. 2. / Гродп. гос. ун-т. -Гродно, 1992. - С. 161.

10. A.C. 1721611 (СССР) М.Кл. G 06 F 15/347. Устройство для вычисления собтвепных значений (п х п)-матрицы / Якуш В.П., Лиходед H.A., БоидаренКо Д.Е., Тиунчик A.A. // Бюллетеяь изобретений и открытий, 1992, N 11.

11. A.C. 1721 Gl2 (СССР) М.Кл. G 06 F 15/347. Устройство для операций над матрицами / Якуш В.П., Лиходед H.A., Тиунчик

A.A., Косьяпчук Î3.B. // Бюллетень изобретении и открытий,

1992, N 11.

12. A.C. 1737463 (СССР) М.Кл. G 06 F 15/347 Устройство для умножения матрицы па вектор / Я кум В.П., Лиходед H.A., Косьяпчук В.В., Тиупчик A.A. // Бюллетень изобретений л открытий, 1992, N 20.

13. A.C. 1730948 (СССР) М.Кл. G 06 F 15/324. Устройство для решения систем линейных алгебраических уравнений / Якуш

B.П., Лиходед H.A., Соболевский П.И., Тиупчик A.A. // Лля служебного пользования, 1993.

14. A.C. 1779180 (СССР) М.Кл. G OG F 15/347. Устройство для умножения матриц / Якуш В.П., Лиходед H.A., Косьяпчук В.В., Тиупчик A.A. // Для служебного пользования, 1993.

15. A.C. 1819018 (СССР) М.Кл. G DGF 15/324. Устройство для решения систем линейных алгебраических уравнений / Якуш В.П., Лиходед H.A., Соболевский П.И., Тиупчик A.A. // Для служебного пользования, 1993.

16. A.C. 1782132 (СССР) М.Кл. G 06 F 15/347. Устройство для вычисления свертки / Якуш В.П., Лиходед H.A., Косьяпчук В.В., Тиунчик A.A., Черяега II.И. // Бюллетень изобретений и открытий, 1992, N 11.

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

18. Тиунчик А. А. О проектировании двухуровневых систолических процессоров с распределенной арифметикой // Весщ АИБ. Сер.ф^з.-мат. навук. - 1993, N 4. С. 101-106.

19. Тиунчик А.А. О проектировании многоуровневых систолических процессоров // Доклады АНБ. - 1994. - Т. 38, N 4. С. 16-18.

20. Likhoded N., TiountcUik A. Systolic implementation of matrix sweep method // Proc. 1-st Int. Conf. on Parallel Processing and Applied Mathematics, Czestochawa, Poland, September 14-16, 1994. / Czestocliowa, Poland, 1994. - P. 270-277.

21. Sobolevsld P., Tiountchik A. Systolic implementation of multidimensional Discrete Fourier Transform // Proc. 1-st Int. Conf. on Parallel Processing and Applied Mathematics, Czestocliowa, Poland, September 14-16, 1991. / Czestocliowa, Poland, 1994. - P. 278-285.

ae