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

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

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

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

УДК: 519.6 + 51:681.3.012

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

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

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

Дубна 1995

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

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

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

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

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

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

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

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

Защита диссертации состоится ".' " ОСТЯ&РЯ 1995 года в час. мин. на заседании Специализированного совета

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

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

Автореферат разослан " ^ " С В ИТД б'РЯ 1995 г.

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты работы докладывались на международных конференциях "Parallel Computing Technologied-01", г. Новосибирск, 1991 г., "Parallel Computing Tcchnologscs-93", г. Обяинск, 1993 г., "Real Time Data Distributed Front-End Processing", г. Дуби a, 1991 г., "Parallel Processing and Applied Mathematics", г. Ченстохова, Польша, 1994 г., на I Всесоюзной конференции "Однородные вычислительные среды и систолические структуры", г. Львов, 19S0 г., VI конференции математиков Беларуси (г. Гродно, 1992 г.), заседаниях отдела математических проблем автоматизации проектирования Института математики АН Беларуси (1989-1995 гг.) и лаборатории вычислительно!! техники и автоматизации ОИЯИ (1995 г.).

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

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

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

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

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

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

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

*.МТ 0?) = ЛЫ» - V»!). *»(« - VI), • • •,*,(« - <Р1)), т 1 <«' < р, 1 < ч < Я, ^ е VI с ът, к '

где Ц - функция р переменных х{, х2,..., л;р; <р[, ;,., <рчр, \)1,г)1,.. - векторы из пространства Ът, определяющие координаты точек (у — <р']) и (« + й') в которых, соответственно, вычислена и используется в качестве аргумента функции величина Х{. Область V — будем называть областью вычислении. Вектор, соединяющий точки области вычислений и.соответствующий пересылке данного я,-между этими точками, будем называть вектором зависимости, а вектор, соответствующий вводу или выводу этого данного - впешшш вектором. Совокупность всех векторов обозначим через Е.

Граф С — (V, Е) будем называть графом зависимостей, представляющим решетчатый алгоритм (1), если его вершины идентифицируются с точками V 6 V, а множество дуг характеризуется векторами из множества Е. Граф зависимостей Можно рассматривать как геометрический объект, отождествляя при этом его вершины с точками пространства й"', в которых они расположены, а дуги зависимости - с соответствующими векторами, что дает возможность применять операторы аффинного отображения для преобразования графов зависимостей.

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

б

Пусть задан некоторый алгоритм и G — (V, Е) — его граф. Предположим, что множество вершин V разбито на такие непересекающееся подмножества \\, V?,..., V}/, что если v Ç Vï, и € Vj и существует дуга (v, и), то i < j. Тогда разбиение V — U"_,Vi называется параллельной формой алгоритма, подмножества Vj, Vj,..., Vu — ее ярусами, а число Я — высотой параллельной формы.

Граф зависимостей G будем называть строго направленным, если существует такой вектор u = ('¡ii"2) • •., пт) 6 Z'", который образует острые углы со всеми векторами <р], 1 < <] < Q, 1 < г < р. Множество всех таких векторов для графа G обозначим через K(G).

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

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

Функцию вида

t(v) = (п, «) - mïn(n, v) + tg,

где {•, •) означает скалярное произведение, ¿о — некоторая неотрицательная целочисленная константа, будем называть таймиругащей функцией.

ТаНмируюклл функция мри фиксированном »г G K(G) задает одну из параллельных (¡юрм алгоритма, представленного квазисистолическим или систолическим-графом зависимостей G — (V,E), и определяет режим работы систолического процессора.

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

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

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

Пусть графы зависимостей С9' и С'"* вложены и пространства Ъ° и Ъл соответственно, а их вершины определяются наборами координат V1' — (¿¡', п ь1ос = (г'^,..., г''°с) соответственно. Каждой вершине V1' графа С3' .можпо поставить в соответствие граф <5'ос, представляющий реализуемую на локальном уровне операцию, приписанную вершине и5'. Такой граф будем обозначать {ма',С!ос).

Суперпозиция С"!' — (£?'', С'"с) представляет собой граф зависимостей, полученный заменой вершин па графы (ь9>, С'м), размещенные в пространстве и реализующие прнписапяые

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

Пусть (*'<?', С^"") - локальные графы, реализованные в пространстве Z0+'i п соответствующие вершинам И пусть глобальный граф б*' представляет собой, совокупность в информационно связанных вершин г|', 1 < £ < в. Тогда суперпозицию графов

С'1 и будем обозначать также = I (1

Теореиа 1.1. Суперпозиция Сщ> = (С9', С'0*) - Е , С^)

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

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

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

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

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

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

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

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

Определим преобразование каждой вершины V = у'°с) су-

перпозиции Е (''(', оператором Т^ : '¿"+,< -* Ъ1НЛ аффинного преобразования

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

*«-и. X)- *-«>»

Е - матрш;а тождественного преобразования размерности £) х £>, ОдхЛ и О^хо ~ пулевые матрицы размерности О X Л \\ (I у. И соответственно, Ф^ - матрица размерности Л х /1, О о - С-мерный нулевой, а - ¿-мерный векторы. Обозначим через {Т^}£=1 множество таких аффинных преобразований Т^.г = Ц^х+ф/, 1 < £ < 5,

что $135 = Ех, ф[ — 0, а через Н (г>|', Сг^*) обозначим граф зависимостей, полученный в результате отображения суперпозиции Е (и£'> множеством операторов

Теорема 1.2. Граф зависимостей Е ТЛ^'.С!1*) представляет

{=1 ; <

тот же алгоритм, что и суперпозиция Е (ч'1, Т^С^00).

В случае реализации глобального графа в одномерном пространстве для каждой пары соседних вершин и ъ'1 можно определить оператор Т({) : 20+н ZD+'', Т(() — ФК) +

а преобразование графа («!',(?£*) задать оператором = Т(1)Т(2)Т(3) )Т(£). Обозначим через " ('.и")« инфор-

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

Теорема 1.3. Если для графа квазнсистолического алгоритма Е С^06)» € У' С й1, существует такое множество аффинных преобразований что выполняются следующие условия:

е в? : € {£}, ЗА, Л 6 N : Ф^, = Е,

П|=1К(Ф(!)Ф(5) • • • ) ^ 0,

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

толического алгоритма S (vf >(*'") в граф систолического алгоритма

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

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

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

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

возможна по отношению к данному х в локальном графе G^*, если в соответствующей вершине vf не производятся преобразования над этим ДРЛШЫМ.

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

¿i*)+i f

в суперпозиции графов зависимостей уменьшается с d(x)+ 2 (4xj)

i=i

до шах (( — 1 + ti(x;)), где d(x) - количество дуг для пересылки

данного х в глобальном графе Gloc между последовательно соединенными вершинами vf, v^1, ..., a à(x() - количество дуг для

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

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

\

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

Пространственное отображение суперпозиции графов зависимостей на граф систолического спецпроцессора определено посредством двух линейных операторов: IV' : Ъ° —» 7,т и П''ос : Ъ* —» Ъг (г = 0, 1 или 2). Образ П'"ри'"'' точки задает формула =

Гр'и'' + и,ось'м.

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

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

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

Процедура вложения определяется формулой V — ПР,!ь'"с, где Д = шах(Да[), Р" - (рР.),Р:1 = (р1) - матрицы порядка £> х Д и (1 х Д соответственно, рфру = 1 при I = ] и = О

при г ф О — ^Лпц(<7,), 1 < г < Д, - диагональная матрица, Я -ортогональная матрица.

Для вычисления матриц Р", Р1*, С и -Л разработаны формальные методы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- С. 139-142.

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

5. Likhoded N.A., Sobolevskii РЛ,, Tiountcliik A.A. 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.

G. Tiountcliik 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. G91-696.

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

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

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

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

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

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

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

1992, N11.

12. A.C. 1737463 (СССР) М.Кл. G 06 F 15/347 Устройство для умножения матрицы на вектор / Якуш В.II., Лиходед 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 06 F 15/347. Устройство для умножения матриц / Якуш В.П., Лиходед II.A., Косьянчук В.В., Тиупчик A.A. // Для служебного пользования, 1993.

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

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

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

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

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

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

21. Sobolevski P., Tiountchik A. Systolic implementation of multidimensional Discrete Fourier Transform // Proc. 1-st Int. Conf. on Parallel Processing mul Applied Mathematics, Czestochowa, Poland, September 14-1G, 1994. / Czestochowa, Poland, 1994. - P. 278-285.