Введение к работе
Актуальность темы. В настоящее время эффективная организация массовых параллельных вычислений в многопроцессорных системах является предметом широких научных исследований и инженерных экспериментов. В этой области эффективное решение многих важных задач возможно только при глубоком распараллеливании процессов вычислений.
Современный этап развития и успехи в области технологии сверхбольших интегральных схем (СБИС) делают возможным построение высокопараллельных вычислительных структур, ориентированных на непосредственную реализацию базовых алгоритмов линейной алгебры, цифровой обработки сигналов, распознавания образов и др. Вместе с тем, интегральная технология предъявляет ряд схемотехнических требований при разработке СБИС-алгоритмов. Разработка высоко-параллельных алгоритмов, удовлетворяющих требованиям интегральной технологии, является по существу проектированием проблемных 'СБИС-ориентированных вычислительных структур. Задача состоит не только в выявлении из алгоритма подходящей для СБИС параллельной формой, но и в получении для заданного алгоритма соответствующей СБИС-архитектуры, выбранной из множества решений.
Появление СБИС существенным образом увеличило интерес к массовым параллельным вычислением. Большой вклад в становление теории и.практики массовых параллельных вычислений для СБИС внесли О.Л. Бандман, Ю.Г. Дадаев, В.И. Варшавский Ю.С. Каневский, В.В. Корнеев, Г.А. Кухарев, Н.Н. Миренков, П.И. Соболевский,
С.Г. СЄДУХИН, Я.И. ФЄТ, S.Y. Kung, Н.Т. Kung, Ch. Lengauer, D. Moldovan, P.V.K. Kumar И Др.
Одним из подходов к проектированию высокопараллельных вычислительных структур для непосредственной реализации регулярных алгоритмов в СБИС является разработка систолических процессорных структур. Систолические структуры - это одномерные или двумерные матрицы регулярно и локально связанных процессорных элементов (ПЭ) одного или нескольких типов, которые под управлением общих часов ритмически (синхронно) обрабатывают взаимодействущие потоки входных данных, поступающие на перифирийные ПЭ структуры.
Следует отметить, что проектирование систолических структур выполнялось ранее в основном на эвристической и интуитивной основе и без связи друг с другом. Для решения одной и той. же задачи разными авторами были предложены разные вычислительные структуры. В
частности, для алгоритма умножения матриц к настоящему времени разработаны десятки проектов высокопараллельных вычислительных структур систолического типа. Существует большое количество методик, которые в той или иной мере систематически решают задачу проектирования процессорных матриц для СБИС-реализации матричных алгоритмов. Однако, существующие методики проектирования обладают рядом* недостатков, которые затрудняют или делают невозможным их практическое использование при разработке и' анализе систолических структур. Среди них можно отметить следующие: - как правило, исходные алгоритмы задаются непосредственно или в виде алгоритмической програми в форме однородных рекуррентных уравнений, т.е. считается, что информационные связи между отдельными вычислениями уже локализованы и алгоритм приведен к удобному для СБИС-реализации виду; - временное упорядочение множества вычислений алгоритма задается только линейной формой, поиск которой часто осуществляется эмпирически; - не рассматривается получение для заданного алгоритма множества допустимых проекннх решений, позволяющих проектировщику выбрать наилучшую процессорную матрицу по некоторому сложному критерию оптимизации (время - площадь -топология - специализация - форматы потоков данных и т.п.).
Одним из ' базовых методов решения многих задач является алгоритм умножения матриц. В частности, произведение матриц является центральной вычислительной задачей линейной алгебры, поскольку к ней сводится целый класс других важных задач: обращение матриц, решение систем линейных уравнений, умножение последовательности уатриц, нахождение кратчайших путей в графе, нахождение транзитивного замыкания графа и др. Важность и высокая операционная сложность традиционного алгоритма умножения матриц стимулирует многочисленные исследования, связанные о поиском параллельных вычислительных структур для быстрого выполнения алгоритма, в том числе, специализированных структур, ориентированных на ленточные, разряженные и т.п. матрицы. Сказанное выше позволяет сделать вывод, что проектирование СБИС-ориентированных систолических структур для умножения матриц, минимальных с точки зрения времени обработки и числа ПЭ является весьма актуальной задачей.
Целью диссертации является разработка и анализ оптимальных высокопараллельных систолических систем ориентированных на технологию СБИС для умножения матриц различной структуры.
Для достижения поставленной цели решаются следующие задачи:
исследование теоретических основ и особенностей выполнения алгоритмов умножения ленточных матриц и последовательностей ленточных матриц при их отображения на современную технологию СБИС;
разработка пространственно-временной структурной, схемы вычислений алгоритмов, оптимальной для СБИС-реализации;
получение и исследование множества допустимых двумерных и одномерных матричных процессоров систолической архитектуры.
Методы исследования. В диссертационной работе использовались методы линейной алгебры, теории графов, теории множеств, аналитической геометрии и формализованный подход к проектированию и анализу вычислительных структур на базе СБИС.
Научная новизна работы заключается в том, что для алгоритма умножения матриц получено и теоретически исследовано допустимое для СБИС-реализации множество проектных решений, позволяющее найти оптимальную (в смысле минимизации критерия "пространство-время") систолическую структуру. Исследования позволили установить- формальную связь между предложенными ранее систолическими структурами и получить новые оригинальные решения. Для умножения последовательности матриц синтезирована планарная систолическая структура, которая характеризуется минимальнымвременем обработки и'числом ПЭ.
Практическая ценность. Полученные в работе результаты' позволяют строить параллельные алгоритмы и вычислительные средства,' ориентированные на современную технологию СБИС, и. могут быть эффективно использованы при разработке параллельных и векторно-конвейерных программ для существующих и перспективных многопроцессорных систем simd- и mimd- архитектуры. Они также могут быть использованы в учебном процессе, свзанном с курсами по методам и средствам параллельных вычислений.
Публикации и апробация. По теме диссертации, опубликовано 4 работы. Основные результаты диссертационной работыпредставлялись и докладывались на заседаних семинара "Математическое и архитектурное обеспечение параллельных вычислений" (Новосибирск, 1991, 1992), на семинарах кафедры "Вычислительные системы" Новосибирского госуниверситета (1991, 1992), на хи Всесоюзном семинаре "Однородные
Вычислительные Среды И СИСТОЛИЧеские СТРУКТУРЫ" (ЛЬВОВ, 1992).
Структура и объем работы. Диссертация состоит из введения, 4-х глав, заключения, списка литературы из 80 наименований. Работа содержит 97 страниц основного текста, 27 иллюстраций, 5 таблиц.
