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

■ * .

РОССИЙСКАЯ АКАДЕМИЯ НАУК Сибирское отделение Вычислительный Центр

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

Седухии Станислав Гсоргисвич

РАЗРАБОТКА И АНАЛИЗ ВЫСОКОПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ II СТРУКТУР С ЛОКАЛЬНЫМИ ВЗАИМОДЕЙСТВИЯМИ

Специальность 05.13.11 -Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

Автореферат

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

Новосибирск - 1992

Работа выполнена в Вычислительном центре Сибирского отделения Российской Академии Наук

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

профессор ИЛЬИН В.П.,

доктор физико-математических наук, профессор ГОНЧАРОВ С.С.,

доктор физико-математических наук, профессор НУРИЕВ P.M.

Ведущая организация — НИИ "Квант" (Москва).

Защита состоится " 29 " декабря_1992 года в /б00 часов на

заседании специализированного совета Д.002.10.02 по защите диссертаций на соискание ученой степени доктора наук при Вычислительном центре СО РАН (630090, Новосибирск, 90, пр. ак. Лаврентьева, 6).

С диссертацией можно ознакомиться в читальном зале библиотеки ВЦ СО РАН по адресу: 630090, Новосибирск, 90, пр. ак. Лаврентьева, 6.

Автореферат разослан " /2р " ¡Сб-<3^рлр I"2 г-

Ученый секретарь специализированного совета,

кандидат технических наук ГМ. Забиняко

£-,." fj'üif i i'.V.r-j

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

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

Существенный вклад по разработке теоретических и практических основ параллельной обработки внесли Б.А. Бабаян, В.В. Воеводин, В.М. Глушков, Э.В. Евреинов, В.П. Ильин, A.B. Каляев, Ю.Г. Косарев, Л.Н. Королев, В.Е. Котов, В.П. Кутепов, В.К. Левин, A.A. Летичевский, В.А. Мельников, H.H. Миренков, P.M. Нуриев, Д.А. Поспелов, В.И. Прангишвили, И.Д. Софронов, В.Г. Хорошевский и их школы.

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

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

Большой теоретический и практический вклад в становление теории и практики массовых параллельных вычислений для СБИС внесли O.JI. Бандман,

B.А. Вальковский, Ю.Г. Дадаев, Ю.С. Каневский, В.В. Корнеев, Г.А. Кухарев, П.И. Соболевский, В.И. Шмерко, Я.И. Фет, М. Cosnard, S.Y. Kung, Н.Т. Kung,

C. Lengauer, D. Moldovan, P. Quinton, Y. Robert, R. Thompson и др.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Результаты работы были представлены и докладывались на Международной конференции по параллельной обработке СО.ЧРА1?-88 (Манчестер, 1988), Международной конференции по векторной и параллельной обработке СОЫРАЙ 90 — УААР IV (Цюрих, 1990), У-м Международном симпозиуме по параллельной обработке на клеточных автоматах и массивах РАИСЕЬ1Л-90 (Берлин, 1990), Международной конференции "Технологии параллельных вычислений" РаСТ-91 (Новосибирск, 1991), Международной конференции "Обработка сигналов" Ь5Р1С-90 (Рига, 1990), Всесоюзной конференции "Формальные модели параллельных вычислений" (Новосибирск, 1987), Всесоюзной школе "Отображение проблем вычислительной математики на архитектуру вычислительных систем" (Звенигород, 1983), Всесоюзной

конференции "Транспьютерные системы и их применение" (Звенигород, 1991) Всесоюзной конференции "Методы и микроэлектронные средства цифровоп преобразования и обработки сигналов" (Рига, 1989), 1-й Всесоюзно! конференции "Однородные вычислительные среды и систолические структуры (Львов, 1990), Всесоюзном совещании "Конвейерные вычислительные системы (Киев, 1988), Всесоюзном семинаре "Параллельные машины и параллельна; математика" (Киев, 1977), VI-й и VII-й Всесоюзных школах-семинара: "Распараллеливание обработки информации" (Львов, 1987, 1989), 1-м Всесоюз ком семинаре "Логические методы построения однородных и систолически: структур" (Москва, 1988), Всесоюзном научно-техническом семинар! "Программное обеспечение многопроцессорных систем" (Калинин, 1988) Vlll-м Всесоюзном семинаре "Параллельное программирование i высокопроизводительные структуры" (Киев, 1988), Межотраслевок научно-технический семинаре "Системы, средства и алгоритмы первично! обработки информации" (Ленинград, 1989), семинарах ВЦ СО РАН, ИМ СО РАН ИТиПМ СО РАН, ИТК САН (Братислава, Чехо-Словакия), КЦИИТ БАН (София Болгария), Институте Вычислительных Технологий АН КНР (Шеньян, Китай) Университете г. Турку (Финляндия), Лаборатории Информационного Параллелизма при Высшей исследовательской школе г. Лион (Франция) в 1977 — 199; гг. Результаты диссертации включались в годовые отчеты Вычислительное центра СО РАН, Сибирского отделения РАН и Отделения "Вычислительной техники и информатики" РАН. В 1991 году коллективная работа, в которую был? включены основные результаты диссертации, заняли призовое место на конкурсе прикладных работ Сибирского отделения РАН.

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

Структура работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы (254 наименования) и трех приложений. Работа изложена на 296 страницах машинописного текста, иллюстрированных 95 рисунками и 19 таблицами. Приложения насчитывают 54 страницы.

Исследования проводились в соответствии с планами Вычислительного центра СО РАН по государственным научно-техническим программам: "Информатизация России" (НИП 3.58.2), "Разработка программно-технического комплекса для обработки геофизической информации" (шифр "Сибирь"), "Высокопроизводительные информационно-вычислительные системы для нового поколения центров математического моделирования" (НИП 111), программе Сибирского отделения РАН "Новые поколения вычислительной техники,

математическое моделирование и информационные технологии (п. 1.2.3. "Разработка систем автоматизации проектирования спецпроцессоров").

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

Во Введении дана общая характеристика диссертации, обзор ее структуры и результатов работы. Глава 1 посвящена синтезу высокопархчлельных алгоритмов и структур с массовым параллелизмом, ориентированных на непосредственную реатизацию в СБИС. Рассматриваются (п. 1.1) физические и схемотехнические ограничения сверхвысокой интеграции, предъявляющие определенные требования к алгоритмам для их эффективной СБИС-реализации. К числу таких требований относятся: (1) регулярность внутренней структуры алгоритма, т.е. однотипность и массовость выполняемых операций и связен между ними, диктуемая условием однородности СБИС, в которых фактор повторяемости элементов должен быть очень высоким; (2) сверхлинейная операционная сложность алгоритма, т.е. многократное использование при вычислении каждой единицы входных данных, отвечающая условию относительно небольшого числа внешних связей кристалла СБИС в сравнении с числом внутренних связей; (3) двумерность пространства реализации вычислений, отвечающая присущему на сегодняшний день требованию планарности СБИС (появление трехмерных СБИС предельно увеличит размерность возможного физического пространства осуществления вычислений); (4) локальность зависимости вычислений алгоритма, удовлетворяющая требованию соединений элементов в СБИС по принципу блнзкодействия; (5) параллелыю-поточная организация вычислений, обеспечивающая высокое быстродействие и эффективность СБИС-устройства. Для введения в проблематику проектирования параллельных алгоритмов и соответствующих СБИС-ориентированных матричных процессоров неформально осуществляется (п. 1.2) синтез и анализ параллельно-поточных вычислительных схем для непосредственного решения ряда задач линейной алгебры (решение системы линейных алгебраических уравнений и обращение матрицы). Показывается, что используемый эвристический подход, основанный на выявлении внутренней зависимости вычислений, позволяет эффективно обнаруживать присущий матричному алгоритму параллелизм и осуществлять множество одновременных вычислений и коммуникаций как при неограниченном (число ПЭ в системе пропорционально размеру задачи), так и при ограниченном параллелизме (число ПЭ не зависит от размера задачи). Для последнего случая предложено использовать существующие клеточные аналога матричных алгоритмов.

Далее, в Главе 1 рассматриваются особенности организации параллельно-поточных вычислений (п. 1.3) и характеристики линейных рекуррентных уравнений (п. 1.4), являющихся традиционной формой записи матрично формулируемых алгоритмов. При процедурном описании некоторого алгоритма для обозначения любой переменной используется имя и так называемые индексные переменные (координаты), которые могут принимать только целочисленные значения и которые однозначно указывают на желаемую переменную. Число индексных переменных определяет размерность пространства вычислений, а допустимый диапазон этих переменных — область внутренних вычислений №.и). которая для конечных алгоритмов представляет собой ограниченный выпуклый многогранник. Традиционно, координата к используется для обозначения рекуррентного шага в общей последовательности обработки. При этом, до задания соотношений для <:-го шага должны быть явно определены начальные значения всех переопределяемых далее переменных. Эти начальные значения образуют в пространстве вычислений область входных )i а финальные значения — область выходных (Р ) вычислений.

^ oui

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

sin) - f(g(p0-et), g(p0-e2).....8(р0-вт», (1)

где р — является точкой в /i-мериом пространстве, с которой связано

некоторое частное вычисление алгоритма; f — однозначная функция, которая

строго зависит от своих аргументов и сложность вычисления которой — ОО);

£</>) — вычисление функции g в точке />; 0, ¡6(1,2,...,т}, — целочисленный

/¡-мерный вектор, который задает непосредственную информационную зависимость

вычисления в точке р от вычисления в точке ;>=/> -0.

II ' t II I

Для большого класса матрично формулируемых алгоритмов характерным

является зависимость координат части векторов в..., в от

местоположения точки р в области вычислений так, что ' о '

р - в(р ) = Л-р + Ь, (2)

'и 'ii | и i

где A, — (;! x/О-матрица констант, Ь — вектор-столбец констант. В этом случае уравнение (I) является рекуррентным соотношением с линейными связями. Для подавляющего числа алгоритмов линейной алгебры, цифровой обработки сигналов, теории графов и т.п., размерность пространства вычислений ;is3. Не теряя общности, дальнейший анализ излагается для случая л=3.

- и -

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

'*(<Р> <- yip - в,)\ х,(р) <- у(р - в );

(3)

Xj(p) «- у(р - в}); w

у(р) <- f(.v;(p), .v^i/)), х (р))\

где у(р) — выходная, .г.(р), / = 1, 2, 3, — входные переменные вычисления в точке /*=(/', У, £) GP Для определенности считается, что у(р — в является рекуррентно переопределяемой переменной, т.е. А}—13 — единичная (н х л)-матрица, Ь=0=(0, 0,-1) — для обратной, Ь=в=(0, 0, 1) — для прямой рекуррентности. Система уравнений (3), решаемая в каждой точке />6Р. , определяет частично упорядоченное по отношению непосредственного

int

предшествования множество вычислении, которому однозначно соответствует конечный ориентированный ациклический граф непосредственной информационной связи (НИС-граф) вычислений

Г = (Р , 0),

пи

где в = {вj, Для дальнейшего анализа НИС-граф Г дополняется

входными и выходными вершинами-вычислениями и соответствующими дугами.

Система уравнений (3) и, в еще более наглядной форме, — НИС-граф Г, позволяют выявить важную особенность матричных вычислений, а именно — характерное для них свойство глобальной трансляционной связи множества вычислений. Это свойство в общем случае заключается в существовании такого подмножества точек р','1 = {pf, р2,—, р } €= Р , что

(1) все вычисления из используют одну и ту же выходную переменную некоторого вычисления в точке /)(ЕР Up ;

(2) мощность подмножества р"1' пропорциональна размеру решаемой задачи (размеру входных данных).

Подмножество вычислений р"" образует область влияния вычисления в точке р,

i II г

т.е. для любого вычисления в точке (/ € [1, /1) выполняется

равенство

р. - 0(/>.) = А.-р + Ь. = р. Глобальная трансляционная связь вычислений, указывающая на вырожденность матриц линейных преобразований Л, противоречит технологическому требованию связи элементов в СБИС по принципу близкодействия и поэтому должна быть устранена.

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

х^р) <- if = Т s¡ then у(р - 0() else х^р ± е(); л:Ар) <- if в = Т е, then у(р - в) else х(р ± е,);

(4)

<-у(р - w

у(р) <- fíx/p), х2(р), Х](р)) ,

где — векторы локальной информационной связи, определяющие

зависимость вычисления в точке р от выходных либо входных переменных вычислений в соседних точках (р ± <?.). Доказывается (теорема 1.1), что при трехмерной области вычислений трансляционное уравнение (3) сводится к локализованному уравнению (4) тогда и только тогда, когда ядра линейных преобразований и А2 являются плоскостью и/или прямой линией. Вводятся схемы локализации для одномерной и двумерной трансляции данных. Множеству внутренних вычислений, задаваемому системой уравнений (4), соответствует граф локальной информационной связи (ЛИС-граф) вычислений

Г* = (Р , Е),

¡ni

где Е S {± ± е2, с^} — множество векторов локальной информационной связи. ЛИС-графу может быть поставлен в соответствие новый алгоритм, эквивалентный исходному, но обладающий локальной зависимостью множества вычислений.

Третий этап проектирования связан с получением множества допустимых пространственно-временных осуществлений алгоритма. Построенному ЛИС-графу Г* = (Р.^, Е) ставится в соответствие ранжирующая (временная) функция t(p): Р ->z, сопоставляющая каждой вершине реР ранг (такт) ее

¡ni ¡ni

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

Ир) = а-р + ß,

где pGP. aSI1— вектор временно'го планирования, /?€Z. Минимально

возможный ранг осуществления всего множества вычислений алгоритма, заданного ЛИС-графом Г*, определится величиной

Г.....(Г*) = t(p'"ax),

где р"шх е Р — максимальная точка (точки) множества внутренних вычислений. Если величина Т"""(Г*) равна длине критического пути в ЛИС-графе Г*, то функция Hp) имеет минимальную форму, т.к. любая последовательность вычислений, лежащих на критическом пути в ЛИС-графе Г*,

должна выполняться последовательно. Предлагается процедура нахождения функции t(p) минимальной формы. Если вычисление в произвольной точке />6Р( выполняется на ранге г, то непосредственно предшествующие вычисления в соседних точках (р-е), i = 1, 2, 3, где е являются базисными векторами, будут выполняться на ранге г-1. Векторы и = е-е , v = е-е лежат на плоскости, которая содержит все точки из Р , имеющие ранг т-1. Вектор временного планирования а минимальной формы, который ортогонален этой плоскости, находится (с точностью до знака) из соотношений:

(а, и) = 0; (a, v) = 0.

Направление (знак) вектора « определяется из так называемых условий Лампорта, сохраняющих предшествование вычислений: (е, а)>0, /= 1, 2, 3. Зная предельную (минимальную) точку р"""еР частично упорядоченного множества внутренних вычислений, для которой Нр'"")=0, можно легко вычистить значение скалярной величины /?, определяющей расстояние между ранжирующими плоскостями.

Ранжирующая функция позволяет найти векторы скоростей движения соответствующих потоков данных. Если переменная v распространяется вдоль направления e^sE и последовательно используется при вычислении сначала в точке />ер , а затем в точке <7£р. (> т. е. Hp) < i(iy), то вектор скорости движения этой переменной определится следующим образом:

flow(v) = (q - p)/[t(<i) - Hp)}. Развертка входных данных или расширение области входных вычислений задается соотношением: р : - рд — It(p ) + 1] 'flow(v). Развертка входных данных соответствует рекуррентному шагу к = 0. Выходные данные займут положения в точках <7 е р Для которых ((</) = Т"""(.Г*) +1. Развертка входных и выходных данных приводит к модификации исходного ЛИС-графа алгоритма, позволяющая получить требуемые проекции входных-выходных потоков данных на границах результирующих систолических структур.

Пространственное планирование (размещение) множества вычислений осуществляется путем ортогонального проецирования модифицированного ЛИС-графа Г*=(р , Е) на гиперплоскость меньшей размерности вдоль некоторого направления. Используется линейная функция планирования а(р)=Лц'р, где A^ является в общем случае [(н-1) х н]-матрицей размещения вычислений, которая соответствует некоторому вектору направления проецирования г]. Строки матрицы Л^=\Л}, Л•••, Лп зависят от выбора системы координат и ортогональны вектору ц. Множество Р^={Л^-р: pG Р определяет процессорное пространство при отображении ЛИС-графа вдоль

направления проецирования г\.

При таком линейном отображении ЛИС-графа алгоритма важно сохранить свойство связи по близкодействию, т. е. топологически локально связанные вершины ЛИС-графа должны отображаться на локально связанные ПЭ получаемой сети. Чтобы обеспечить это, значения элементов матрицы Л должны принадлежать множеству {-1, 0, 1). Очевидно, что число таких матриц будет равно Зп(п-" . Разумеется, не все эти матрицы будут отвечать параллельному выполнению алгоритма. Однако, матрица Л ^ всегда будет требуемой, если координаты направляющего вектора т/ также выбираются из множества {-1, 0, +1}. Число таких возможных векторов, каждый из которых определяет одно проектное решение, будет равно, в общем случае, (3"-1)/2; при этом исключаются нулевое и симметричные (кратные) направления проецирования. Для трехмерных ЛИС-графов число возможных векторов проецирования, соответствующих матрице Л , будет равно 13, а для двумерных графов — 4. Естественным условием корректности отображения является то, что вершины ЛИС-графа, для которых ранжирующая функция t(p) сопоставляет одинаковый ранг (такт) вычисления, должны отображаться на разные ПЭ результирующей сети, т. е. задаваемое пространственное отображение является корректным, если скалярное произведение (а, ф ^ 0. Векторы t], удовлетворяющие этому условию, называются допустимыми, а множество всех проектных решений (прототипов систолических матриц ПЭ) получается в результате отображения ЛИС-графа по всем допустимым направлениям проецирования. Каждый проект характеризуется различными пространственно-временными характеристиками: числом ПЭ, топологией их связи, форматами потоков входных-выходных данных, временем обработки, периодом конвейеризации задач и данных, латентностью. Многие из этих характеристик могут быть выражены формально. Например, период конвейеризации данных Z(S) некоторого проекта S, определяющий число тактов, которые разделяют соседние данные, вводимые или выводимые с какого-либо входа-выхода систолической структуры, выражается как Z(S)—\(а, Методика проектирования иллюстрируется на примере проектирования систолических алгоритмов и структур для ¿¿/-разложения (п X и)-матрицы.

Предложенная методика синтеза систолических алгоритмов и структур применяется далее (п. 1.6) для разработки S4CAD — компьютерной системы автоматизированного проектирования, анализа и моделирования высокопараллельных алгоритмов и матричных процессоров систолической архитектуры. Используя мощный графический интерфейс (MS Windows 3), система S4CAD позволяет:

• интерактивно выбрать из библиотеки и настроить алгоритм, заданный в виде

взвешенного ЛИС-графа и ранжирующей функции, на желаемые параметры входных данных задачи (размер и структуру исходных матриц);

• получить и просмотреть на мониторе множество всех допустимых для выбранного алгоритма высокопараллельных проектов сетей систолической архитектуры;

• осуществить пошаговое пространственно-временное моделирование процессов обработки и коммуникации для любого выбранного проекта;

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

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

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

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

Работа системы иллюстрируется на примере проектирования систолических структур для разложения матрицы по методу Холецкого. Входная для 54САО программа метода Холецкого приведена в Приложении 1, а полное описание и руководство пользователя системы 54САО — в Приложении 3. На рис. 1. показано основное окно 54САО, содержащее некоторую анализируемую систолическую структуру (нахождение транзитивного замыкания бинарной матрицы).

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

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

S4CAD - Unsavcd Tunsltrve dosur

жа

E'le Proicct S'ep View gplicn Window fcjelp

' I:! Ш "1 S' - -fetbfci......

S4CAD: Parallel Profile

__XSleplD-23]

I Sp^o 7Б0ЙЬ%

S<CAD: Space Schedule

10 I I I 2 I 3 Ц J 5 111

m && w»

. 1 Ц^Яг

.... to

♦w,.....

1 I., m

ш.

1 IB I э 110 111

_l_l_I

i I I J I J

sa I_ ¡_.'_.

¡.Ii

"tl'^ljiw I' 1 Olli

Рис. 1.

зависимости вычислений на двумерное процессорное пространство. В зависимости

от внутренней структуры перемножаемых матриц среди полученных проектных

решений выбирается оптимальная структура, которая характеризуется как

минимальным временем параллельного выполнения операций, так и минимальным

числом ПЭ. Например, для умножения ленточных (л х п)-матриц с шириной лент

со -р +а -1 и су=о+о-1 оптимальным проектом является сеть, содержащая и а а Ь о Ь

гексагонально и ациклически связанных ПЭ и выполняющая произведение за н+ттСр^, (/а)+тт(ро, q|)-3 временных шагов.

Для алгоритма обращения (п х п)-матрицы осуществляется (п. 2.2) формальный синтез множества допустимых трехмерных, двумерных и одномерных систолических реализаций, различающихся временем и периодом обработки, числом ПЭ и их топологией связи, форматами входных-выходных данных и т.п. Доказывается (теорема 2.1), что при неограниченном параллелизме оптимальным систолическим процессором является сеть, содержащая пХп ортогонально связанных Г1Э двух типов, которая выполнит 0(п3) операций алгоритма обращения матрицы за минимально возможное число 5п — 4 временных шагов. Показывается (теорема 2.2), что эта оптимальная систолическая структура имеет асимптотическую сложность СБИС-реализации АТ2=0(п4 ), где А — площадь кристалла, Т — время выполнения заданных вычислений в интегральной

технологии.

Далее рассматривается и анализируется (п. 2.3) допустимое множество систолических алгоритмов и структур для вычисления матричного произведения А-В'1, где Л и Л являются входными (пХп)- и (рхп)-матрицами соответственно. Выполнение такой операции часто требуется при выполнении, например, адаптивной фильтрации. Доказывается, что минимальным по числу ПЭ является либо проект систолического процессора, использующего п(п+2р+1)/2 ПЭ, при р<(п-1)/2, либо проект, содержащий п(п+1) ПЭ — в противном случае. Оба проекта выполнят п2(п+2р+1)/2 операций алгоритма за минимальное число 4п+р-2 временных шагов.

Глава 3 посвящена разработке и анализу систолических алгоритмов и структур для решения задач на графах. Показывается (п. 3.1), что математическая формулировка таких задач как построение транзитивного и рефлексивного замыкания графа (алгоритм Уоршолла), нахождение кратчайших путей во взвешенном графе (алгоритм Флойда) и построение минимального остовного дерева для неориентированного графа (алгоритм Маггса-Плоткина), являются различными версиями обращения матрицы (алгоритм Гаусса-Жордана без выбора ведущего элемента). Все эти задачи (расходующие О Ol3) операций из соответствующей алгебры, где п — либо число вершин в графе, либо размер входной матрицы) образуют так называемую общую проблему алгебраических путей (algebraic path problem — АРР).

В теоретико-графовой постановке АРР формулируется следующим образом. Пусть задан взвешенный ориентированный граф G - (V, Е, if), где V = {0, 1, ..., /1-1} — конечное множество из п пронумерованных вершин, Е £ Vx V — множество дуг, w\ Е -> Н — функция, ставящая каждой дуге из Е некоторый вес из замкнутого полукольца (И, (+), (х), *), в котором определены операции "сложение" (+), "умножение" (х) и унарная операция "замыкание":

с* = Хс' = 1 + с + (с х с) + (с х с х с) + ...

Путем р в графе G называется последовательность связанных вершин (v^, v(, ..., v), где О S г и (v. , v) S Е. Вес пути р определяется как произведение весов дуг, входящих в этот путь, т. е.

w(p) = w(( х )tv^( х)...( х )w(, где w, является весом дуги (v v). Необходимо найти для всех пар вершин (i, /) величину

d = (+) { w(p)\ р е ),

где М обозначает множество всех путей из v в v . и I j

Приведенная задача может быть сформулирована в матричном виде. В этом случае взвешенному графу С = (V, Е, и>), содержащему п вершин, ставится в соответствие (пXп)-матрица С = [е.], где

' кЦ, /), если (/, /) 6 Е ;

с =

V

О, в противном случае.

Если через обозначить множество всех путей из I в /', которое

содержит только вершины х с номерами 1 ^ х £ к как промежуточные вершины (т.е. лежащие на путях из /в ¡), то при ¿^ = е.. имеем:

</*; = (+) { Мр): р € М^},

и, следовательно, с'п) = ¡1 .

Ч и

Используя разработанную методику формального проектирования, для исходного (базового) алгоритма решения задачи АРР синтезируется (п. 3.2) граф локальной зависимости вычислений, определяется ранжирующая функция, синтезируется и исследуется множество пространственно-временных систолических реализаций (п. 3.3). Доказывается (теорема 3.1), что множество вычислений базового алгоритма решения АРР завершится на минимальном шаге 5п-4. Осуществляется регуляризация исходного графа зависимости вычислений, которому ставится в соответствие ротационный алгоритм решения АРР (п. 3.4). Показывается (теорема 3.3), что широко известная спиралевидная систолическая структура, содержащая пхп ПЭ четырех типов и решающая задачу за 6л-5 шагов, является одной из возможных плоскостных проекций графа зависимости вычислений ротационного алгоритма.

Далее осуществляются дальнейшие эквивалентные преобразования (п. 3.5), которые трансформируют граф ротационного алгоритма в новый высокорегулярный граф зависимости выислений, оптимальный для отображения в СБИС. Полученному графу ставится в соответствие регулярный алгоритм решения АРР и показывается, что О (л3) операций алгоритма могут быть выполнены за минимальное число 5п-2 временных шагов. Доказывается (теоремы 3.5 и 3.6), что широко известные проекты систолических матриц, использующие п2+2п и л (л+1) ПЭ соответственно, являются различными проекциями трехмерного графа зависимости вычислений регулярного алгоритма на плоскость. Предлагается новый оптимальный систолический проект, который использует минимальное (теорема 3.7) число п2 ортогонально связанных ПЭ двух типов и п элементов задержки (рис. 2).

Глава 4 посвящена синтезу и анализу систолических алгоритмов и структур для решения базовых задач цифровой обработки сигналов. Для одномерной (линейной) апериодической свертки (п. 4.1) и деконволюции (п. 4.2)

(21) (12)

(31) <22> <13)

(32) (23)

данные - •> управление

п =3

О (И)

О (21) С2) .

1 (31) (22) (13)

(32) (23) Рис. 2. <33>

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

Далее (п. 4.4) осуществляется разработка множества допустимых проектных решений для различных алгоритмов вычисления двумерного N хТУ -точечного ДПФ по известной формуле:

где [х 1, кгк2

[у 1 ] — являются (Л^хЛу-матрицами входных и выходных

соответственно, = ехр{-2п;/Nсо^ = ех/){-2л//лу, / =

V;

2

Показывается, что оптимальной систолической структурой является сеть, содержащая N х N ортогонально связанных однотипных ПЭ и выполняющая ОШ^ )) комплексных операций алгоритма за минимальное число

-1) временных шагов. На рис. 3 приведена такая структура для выполнения двумерного (Зх5)-ДПФ, т.е. N N =5.

Предлагаются (п. 4.5) три варианта эффективной организации решения больших задач на ограниченных структурах синтезированных ДПФ-процессоров (модульное расширение, использование систолической и транспыотероподобной структур). Приводятся соответствующие сложностные оценки вычисления ДПФ произвольно большого размера на сети с ограниченным числом ПЭ. Используя известное сведение одномерного ДПФ к многомерному (алгоритм взаимно простых множителей) и полученный оптимальный систолический процессор двумерного ДПФ, предлагается (п. 4.6) параллельный алгоритм и архитектура СБИС-процессора для параллельного выполнения одномерного быстрого дискретного преобразования Фурье (БПФ). Предложенная структура для выполнения Ы(=Ы ^ N 2)-точечного БПФ, во-первых, преобразует одномерный входной сигнал в двумерную форму, пригодную дл;1 высокопроизводительной обработки, во-вторых, параллельно выполняет двумерное ДПФ и, наконец,

V/2 V/ 1 J 1

11111 ООО

0

Х2,

Х22 хп

Х2, Х,2 х<п

х20 X 1 1 Х02 *

х,о X 0 1

С

1 10 г 1 / --> 1 12 --> 2м —»

Ж ¥

у у V У У

04 ^03 02 *01 '00

Рис. 3.

производит обратное преобразование сигнала в последовательную форму. При N , систолическая БПФ-структура, использующая сеть из Ы=Ии2хЫ112

однотипных ПЭ, способна выполнить 0(Ы-Ы112) операций за 0(Ы,/2) временных шагов.

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

Для умножения матрицы на вектор, являющейся базовой вычислительной операцией для кольцевой архитектуры, исследуются две схемы эффективной параллельной реализации (п. 5.1). Далее разрабатываются и оцениваются на эффективность параллельно-поточные версии выполнения на кольце из п компьютеров ряда численных алгоритмов решения системы для п линейных алгебраических уравнений (п. 5.2) прямыми (метод Гаусса без выбора и с выбором ведущего элемента) и итерационными (п. 5.3) методами (алгоритмы Якоби и Гаусса-Зейделя), определения (п. 5.4) собственных значений (п х п)-матрицы (методы Крылова и Данилевского), нахождения (п. 5.5) сингулярного разложения (п х п)-матрицы (алгоритм Хаусхолдера) и решения (п. 5.6) системы из п обыкновенных дифференциальных уравнений (метод Рунге-Кутта). Для каждого параллельного алгоритма приводятся соответствующие программы и профиль параллелизма, показывающий изменение числа активных вычислителей от номера временного шага. На рис. 4 представлен профиль параллелизма для метода Данилевского.

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

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

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

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

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

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

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

время Рис. 4.

вычислений.

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

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

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

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

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

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

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

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

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

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

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

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

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

Основное содержание диссертации отражено в следующих работах:

1. Специализированные процессоры для высокопроизводительной обработки данных/Бандман О.Л., Миренков H.H., Седухин С.Г. и др. — Новосибирск: Наука. Снб. отд-ние, 1988. - 207 с.

2. Параллельная обработка информации. Том. 4. / Грицык В.В., Седухин С.Г., Якуш В.П. и др. — Киев: Наукова думка. — 1989. — 272 с.

3. Седухин С.Г. Вычислительные структуры алгоритмов и архитектура ЭВМ на базе СБИС// В кн.: Вычислительные процессы и системы. Вып. 2. /Под ред. Г.И. Марчука. — М.: Наука. Главная редакция физико-математической литературы. - 1985. - С. 129-139.

4. Седухин С.Г. Систематический подход к проектированию вычислительных структур на базе СБИС. — Новосибирск, 1985. — 46 с. (Препринт /АН СССР, Сиб. отд-ние: ВЦ; N. 589).

5. Мишин А.И., Седухин С.Г. Вычислительные системы и параллельные вычисления с локальными взаимодействиями// Вычислительные системы. -Новосибирск: Институт Математики СО АН СССР. — 1979. — Вып. 78.

- С. 90-103.

6. Мишин А.И., Седухин С.Г. Однородные вычислительные системы и параллельные вычисления. — Автоматика и вычислительная техника.

- 1981. N. 1. - С. 20-24.

7. Седухин С.Г. Параллельно-поточная интерпретация метода Гаусса. Вычислительные системы. — Новосибирск: Институт математики СО АН СССР. - 1982. - Вып. 94. - С. 70-80.

8. Седухин С.Г. Параллельно-поточная интерпретация метода Холецкого. Электронное моделирование. — 1984. — Т. 6, N. 6. — С. 3 — 6.

9. Седухин С.Г. Параллельно-поточная интерпретация прямых методов линейной алгебры. Программирование. — 1984. — N. 4, — С. 57 — 68.

10. Sedukhin S.G. Highly parallel algorithms and the architecture of a computer system for solving large matrix problems/ In: Artificial Intell. and Inform. Contr. Syst. of Robots, I.Plander (Ed.): North-Holland. - 1984. - P. 319-323.

11. Седухин С.Г. Вычислительные структуры нахождения путей в графе. — Изв. АН СССР. Технич. кибернетика. - М., 1985, N. 1. - С. 29-36.

12. Седухин С.Г. Некоторые аспекеты организации параллельных вычислений // Вычислительные системы. — Новосибирск: Институт Математики СО АН СССР. - 1985. - Вып. 112. - С. 16-30.

13. Седухин С.Г. Проектирование параллельных алгоритмов и вычислительных структур для быстрого обращения матриц. Вычислительные системы.

- Новосибирск: Институт математики СО АН СССР. — 1985.— Вып. 109.

- С. 74-88.

14. Седухин С.Г. Проектирование и анализ систолических алгоритмов и вычислительных структур для решения алгебраической проблемы нахождения путей. — Новосибирск, 1987. — 44 с. (Препринт /АН СССР, Сиб. отд-ние: ВЦ; N. 744).

15. Седухин С.Г. Проектирование матричных процессоров для дискретного преобразования Фурье // Ред. журн. "Электронное моделирование".

- Киев, 1987. - 19 с. - Деп. в ВИНИТИ 19.11.87, N. 8179-В87.

16. Устройство для перемножения матриц! А .С. N. 1363247. Авт. Якуш В.П., Седухин С.Г., Козюминский В.Д., Авгуль Л.Б. - БИ N. 48, 1987.

17. Седухин С.Г., Тищенко Т.П. Проектирование высокопараллельных вычислительных структур для алгоритма Гаусса-Жордана в применении к задачам фильтрации. — Новосибирск, 1988.— 28 с.(Препринт/ АН СССР, Сиб. отд-ние: ВЦ; N. 813).

18. Устройство для обращения плотных матриц/ A.C. N. 1387013. Авт. Якуш В.П., Седухин С.Г., Мищенко В.А., Авгуль Л.Б. - БИ N. 13, 1988.

19. Устройство для выполнения матричных операций/ A.C. N. 1388897. Авт. Якуш В.П., Седухин С.Г., Мищенко В.А., Подрубный О.В. — БИ N. 14, 1988.

20. Матричное устройство для вычисления свертки/ A.C. N. 1401477. Авт. Якуш В.П., Седухин С.Г., Мищенко В.А., Авгуль Л.Б. - БИ N. 21, 1988.

21. Устройство для матричных операций/ A.C. N. 1429127. Авт. Якуш В.П., Седухин С.Г., Авгуль Л.Б., Ленев A.A. - БИ N. 37, 1988.

22. Устройство для обращения матриц/ A.C. N. 1429126. Авт. Якуш В.П., Седухин С.Г., Семашко А.Н., Белоус А.И., Грицык В.В. — БИ N. 46,

1988.

23. Устройство для обращения матриц и решения систем линейных уравнений/ A.C. N. 144420. Авт. Якуш В.П., Седухин С.Г., Авгуль Л.Б., Семашко А.Н., Подрубный О.В. - БИ N. 46, 1988.

24. Sedukhin S.C., Trishina E.V. An automated procedure for synthesis of systolic/wavefront arrays. — Proc. Intern. Conf. CONPAR 88. Eds. C.RJesshope and K.D.Reinartz. Cambridge Univ. Press. — 1988.

- P. 735-742.

25. Важенин А.П., Седухин С.Г., Фет Я.И. Высокопроизводительные вычислительные системы комбинированной архитектуры. — Новосибирск,

1989. - 24 с. (Препринт/АН СССР, Сиб. отд-ние: ВЦ; N. 866).

26. Седухин С.Г. Систолические процессоры двумерного дискретного преобразования Фурье// В кн.: Архитектура, матобеспечение и средства

интеллектуализации вычислительных систем. — Новосибирск, 1989. ВЦ СО АН СССР. - С. 46-65.

27. Седухин С.Г., Тришина Е.В. Автоматизация процессов синтеза систолических и волновых процессорных матриц// Методы теоретического и экспериментального программирования (на англ. яз.) /Под ред. В.Е. Котова. - Новосибирск, ВЦ СО АН СССР. - 1989. - С. 129-141.

28. Устройство для операций над матрицами/ А.С. N. 1464171. Авт. Якуш В.П., Седухин С.Г., Соболевский П.И., Лиходед Н.А. - БИ N. 9, 1989.

29. Устройство для вычисления деконволюции! А.С. N. 1494017. Авт. Якуш В.П., Седухин С.Г., Авгуль Л.Б., Ленев А.А. - БИ N. 26, 1989.

30. Матричное устройство для вычисления свертки/ А.С. N. 1494018. Авт. Якуш В.П., Седухин С.Г., Соболевский П.И., Лиходед Н.А. — БИ N. 26,

1989.

31. Устройство для решения матричного уравнения вида АХ=В/ А.С. N. 1509932. Авт. Якуш В.П., Седухин С.Г., Мищенко В.А., Авгуль Л.Б., Семашко А.Н. - БИ N. 35, 1989.

32. Устройство для обращения матриц/ А.С. N. 1527643. Авт. Якуш В.П., Седухин С.Г., Соболевский П.И., Лиходед Н.А. - БИ N. 45, 1989.

33. Седухин С.Г. Архитектура систолического процессора для быстрого дискретного преобразования Фурье. — УСиМ. — 1990. — N. 4.

- С. 10-19.

34. Седухин С.Г. Проектирование и анализ систолических алгоритмов и структур. — Программирование. — 1991. — N. 2. — С. 20-40.

35. Седухин С.Г., Карапетян Г.З. Проектирование оптимальных систолических систем для произведения матриц различной структуры. — Новосибирск,

1990. - 48 с. (Препринт /АН СССР, Сиб. отд-ние: ВЦ; N. 885).

36. Устройство для перемножения матриц/ А.С. N. 1552200. Авт. Якуш В.П., Седухин С.Г., Соболевский П.И., Лиходед Н.А. - БИ N. 11, 1990.

37. Sedukhin S.G. Systolic Array architecture for two-dimensional discrete Fourier transform// Proc. Joint Int. Conf. on Vector and Parallel Processing. H. Burkhart (Ed.). Zurich, Switzerland, Sept. 10-13, 1990/

- Lect. Notes in Computer Sciences. - 1990, N. 457, p. 682-691.

38. Sedukhin S.G. Organization of systolic computations on a ring of computers// PARCELLA'90 (Eds. G.Wolf, T.Legendi, U.Schendel). - 1990.

- Vol. 2. Academie-Verlag, Berlin. - P. 273-278.

39. Sedukhin S.G. Systolic processor for two-dimensional DFT// Proc. Latvian Signal Processing. Int. Conf. Riga. — 1990. Vol. 2.

- P. 173-177.

40. Sedukhin S.G. Array processor for 2D discrete Fourier transform// Proc. 1st World Conf. Parallel Computing in Eng. and Educ., UNESCO, Paris, Oct. 8-12, 1990. The Chameleon Press Ltd., London. - 1990.

- P. 299-303.

41. Процессор дискретного преобразования Фурье/ А.С. N. 1635195. Авт. Демидов А.В., Седухин С.Г., Семашко А.Н. и др. - БИ N. 10. - 1991.

42. Седухин С.Г. Проектирование и анализ систолических алгоритмов и структур (Обзор)// Программирование. — 1991. — N. 2. — С. 20-40.

43. Vazhenin А.Р., Sedukhin S.G., Fet Ya.I. High-performance computing systems of combined architecture// Proc. Int. Confer. "Parallel Comput. Technologies", PaCT-91. Ed. N.N. Mirenkov. - 1991. - P. 246-257.

44. Sedukhin S.G. Design and analysis of systolic algorithms for the algebraic path problem. — Computers and Artificial Intelligence.

- 1992. - Vol. 11, N. 3, - P. 269-292.