Содержание к диссертации
Введение
Глава I. Параллельные методы линейной алгебры с малоранговыми модификациями
1.1. Общие принципы анализа параллельных алгоритмов
1.2. Обращение модифивдрованных матриц
1.3. Разложения Гаусса и Холесского для модифицированных матриц
1.4. Методы модификации разложений матриц на ортогональные и треугольные множители
1.5. Метод модификации симметричной проблемы собственных значений
1.6. Основные фрагменты алгоритмов линейной алгебры с малоранговыми модификациями. CLASS Глава 2. Систолические массивы для одного класса алгоритмов линейной алгебры , CLASS
2.1. Необходимость разработки алгоритмов для систолических систем
2.2. Описание одного класса алгоритмов линейной алгебры
2.3. Систолические массивы первого типа (с двусторонними потоками данных) для алгоритмов из класса
2.4. Систолические массивы второго типа ( с одно сторонними потоками данных и локальной памятью) для алгоритмов из класса л
Глава 3. Систолические массивы для реализации мето дов матричных модификаций 105
3.1. Основные виды и функции элементарных процессоров 105
3.2. Фрагменты алгоритмов модификации, принадлежащие классу М, и их реализация на СМ 109
3.3. Систолические.массивы первого типа для решения треугольной системы линейных уравнений 126
3.4. Систолические массивы второго типа для решения треугольной системы линейных уравнений 140
3.5. Некоторые замечания 147
Заключение
Литература
- Разложения Гаусса и Холесского для модифицированных матриц
- Метод модификации симметричной проблемы собственных значений
- Описание одного класса алгоритмов линейной алгебры
- Фрагменты алгоритмов модификации, принадлежащие классу М, и их реализация на СМ
Введение к работе
На настоящем этапе развития вычислительной техники потребности в средствах обработки информации непрерывно возрастают. Это вызвано качественным и количественным изменением характера вычислительных задач, увеличением их сложности и объема. Как отмечено в работе [12] , возникает необходимость исследования объектов и явлений в целом, перехода от линейных моделей к нелинейным, изучения объектов в динамике, построения пространственных моделей. Наиболее крупные вычислительные ресурсы требуются для задач ядерной энергетики, аэродинамики и гидродинамики, теории климата, циркуляции атмосферы и океана, оптимального управления, исследования операций и др. Математическое моделирование в этих областях приводит к необходимости решать, например, системы линейных алгебраических уравнений с ленточны-ми матрицами с числом переменных порядка 10 и шириной ленты около I03 ; с разреженными симметричными матрицами размера ©KO-ло 10 . В ряде приложений существует потребность решать задачи линейного программирования с числом переменных порядка 10 и числом ограничений порядка 10 .
Быстродействие однопроцессорных машин традиционной структуры перестает удовлетворять возрастающим потребностям решения крупных научно-технических и экономических задач. Необходим новый подход к методам разработки, производства и применения ЭШ [46 , Щ
Одно из главных направлений развития вычислительной техники включает радикальное увеличение суммарной производительности ЗИЛ за счет совершенствования технической и технологической базы и новых архитектурных решений; освоение более эффективных форм и методов взаимодействия человека с машиной; переход от мономапшн традиционной структуры к вычислительным системам (ВС) и комплексам разнообразных конфигураций, широких диапазонов мощностей и назначения.
Одним из средств ускорения решения задач большого размера является распараллеливание обработки информации на различных уровнях.
За последнее время появилось большое количество работ, посвященных двум направлениям развития параллельных вычислений: параллельным вычислительным методам и параллельным вычислительным системам. Существует ряд примеров построения быстродействующих ВС 13 ,15 ,ЧЪ \ . Проводилась также разработка параллельных вычислительных методов. Однако нередко при разработке методов недостаточно хорошо учитывались реальные ограничения со стороны ВС. Учитывались лишь некоторые характеристики метода, например, проводилась оптимизация высоты алгоритмам. Имеется ряд обзоров, посвященных параллельным методам, например,
Для оптимального решения задач из некоторого выделенного класса на ВС необходимо, чтобы параллельные методы и параллельные вычислительные системы развивались в тесной связи друг с другом. То есть, необходимо решать комплексную проблему отображения численных методов на ВС. Эта проблема заключается в следующем: имеется некоторый класс задач, время решения каждой из которых на существующих ВС неприемлемо. Требуется построить ВС, на которой можно было бы решить каждую из этих задач за нужное время с заданной точностью. Кроме того, при построении и использовании такой ВС следует добиваться по возможности минимальной затраты материально-технических и трудовых ресурсов и наиболее эффективного их использования ( например, наиболее полной загрузки всего оборудования полезной работой, и т.п.). В работах IJM4 содержится постановка общей проблемы в целом. Там же изложены основные принципы построения новых ВС, численных методов и средств отображения.
За последнее время появилось немало работ, в которых предлагаются модели параллельных вычислительных систем, эффективных для реализации определенных классов вычислительных методов
[ С , 18 , 38 , 39 , НО , И] . Часть этих работ посвящена разработке систолических вычислительных систем для некоторых методов решения задач линейной алгебры.
Понятие систолических систем было введено в работах , хотя похожие идеи встречались и в более ранних работах, например, ргб] , 35"[J . Систолическая система представляет собой совокупность элементарных процессоров (ЭП), объединенных в линейную или планарную тзеть, или систолический массив (СМ). Каждый ЭП связан со своими ближайшими соседями и выполняет некоторый набор операций над последовательностью данных, которые упорядоченно и ритмически проходят через СІЛ. Развитие идей СМ связано с развитием технологии сверхбольших интегральных схем (СШС) в построении вычислительной техники. Модели систолических систем были предложены в качестве одного t из возможных типов архитектур ВС на основе СШС.
Уровень развития технологии, используемой при создании блоков центрального процессора и памяти ЭЕМ, всегда влиял на архитектуру ЭВМ ]J8] . Как известно, современная полупроводниковая ТЕХНОЛОГИЯ достигла того предела, за которыгл уже не следует ожидать значительного увеличения скорости срабатывания логических элементов и выполнения отдельных арифметических операций ( см.например, 3] ). Этот предел определяется скоростью распространения электрических сигналов и физическими размерами функциональных устройств. Однако степень интеграции продолжает расти, и в ближайшем будущем станет реальным размещение к с. логических элементов на одной грани кристалла. Такая СШС олицетворяет новый этап технологии в разработке ВС, который требует новых идей в организации ЭВМ, теории вычислений и других смежных областях.
Как отмечено в [16] , большой интерес представляет перспектива использования микропроцессоров в качестве элементов ЭЕМ. В настоящее время одно- и многокристальные микропроцессоры внедряются как компоненты микро и мини- ЭВМ, как встроенные вычислительные устройства в приборах, и т.п. Развиваются новые подходы к применению в проектировании ЭВМ микропроцессоров и "программируемых" БИС. Появление ВИС и микропроцессоров и применение их как базовых конструкторских элементов вычислительных устройств и комплексов коренным образом меняют методы логического проектирования машин и их структуру.
Технология СШС представляет большие возможности разработчику систем, но налагает ограничения на разработку алгоритмов [48] . Главные ее преимущества: большое число приборов, доступное при низкой стоимости, малые размеры и повышенная надежность на схемном уровне.
Для эффективного использования огромных ресурсов, заключенных в СШС, необходимо использование параллелизма и кон-вейерности на различных уровнях организации вычислений!
Если параллельный алгоритм организован как совокупность вычислительных модулей меньших размеров, то такие модули могут быть распределены по различным СШС. Простейшая ВС может состоять из нескольких СШС, основной памяти, центрального процессора (Щ) и схемы соединения [18] . Каждая СШС содержит несколько процессоров, работающих параллельно.
Кроме того, используется параллелизм и конвейерность на уровне каждого вычислительного модуля, а также при одновременной обработке всех битов слова.
При разработке вычислительных систем на основе СШС возникают некоторые серьезные проблемы. Одним из ограничений при проектировании алгоритмов является узкое место, связанное с вводом-выводом информации (т.е. ограничения на число каналов связи и скорость обмена каждого процессора с оперативной памятью (ОП) ).
Решение этой проблемы - в разработке параллельных алгоритмов, которые можно расчленить таким образом, чтобы количество связей между модулями было как можно меньше. Кроме того, данные, поступающие в СШС, должны быть использованы наиболее полно, прежде чем они снова попадут на устройства ввода-вывода.
Другая проблема связана с пересылкой данных в пределах одной СШС. Длительность прохождения сигнала может быть намного больше времени срабатывания логического элемента. Поэтому для эффективного использования ресурсов СШС необходимо, чтобы схема содержала только локальные межсоединения. Возникает необходимость разработки алгоритмов, которые при их воплощении в аппаратуре на основе СШС требуют только локальной передачи данных.
В качестве возможного решения этих проблем были предложены архитектуры, организованные по принципу систолических массивов. Систолические системы на основе СШС обычно обладают следующими свойствами:
-система много раз использует входные данные при однократном их выборе из ОП, что снижает число обменов информацией с ОП;
-применяются принципы параллелизма и конвейерности;
-процессоры соединены в линейную или планарную сеть (сиетолический массив); каждый из них связан лишь с соседними ЭП и, может быть, с ОП;
-процессоры могут быть различных типов и выполнить различные функции; одна из задач - как уменьшить число используемых типов ЭП. Обычно рассматриваются СМ, работа которых синхронизирована, хотя это требование и необязательно.
В случае систолических массивов решение задачи отображения вычислительных методов на аппаратуру представляет собой проектирование матрицы СШС в соответствии с особенностями алгоритма.
В настоящее время существует ряд работ, посвященных разработке моделей СМ для решения определенных классов актуальных задач. В основном они посвящены реализации на СМ различных алгоритмов линейной алгебры: умножение матрицы на вектор и матрицы на матрицу, решение треугольной системы уравнений, LXJ" -разложение матриц ЗЧ , 39] , задачи свертки
[33 , ЦО ,44-] QR - алгоритм для решения проблемы собственных значений Е ] и других. В большинстве случаев предлагались систолические массивы, содержащие число элементарных процессоров, связанное с размером матрицы задачи. В частности, были рассмотрены одномерные и двумерные СМ для различных операций над ленточными матрицами с числом ЭП, равным или кратным ширине ленты матрицы. При уменьшении числа ЭП предлагалось решать задачи на СМ с помощью разбиения матрицы.
В этих работах, как правило, не использовался конвейерный принцип организации самих ЭП. Исключением является, например, работа Е °] і в которой предложены двухуровневые СМ для задач сверки, и все ЭП состоят из конвейерных функциональных устройств (ФУ). В то же время применение этого принципа может значительно увеличить быстродействие ЭВМ и повысить эффективность использования всего оборудования.
В данной работе предлагаются математические модели систолических систем для одного важного класса задач линейной алгебры - задач малоранговых матричных модификаций. Особенности предлагаемых СМ состоят в том, что они содержат произвольное число р ЭП, не связанное прямо с размерами матрицы задачи. Каждый ЭП, входящий в их состав, в свою очередь, является конвейерным, и при реализации алгоритмов достигается высокая загруженность всех ФУ, вплоть до уровня выполнения микроопераций ( при достаточно малых значениях Р ).
Сущность мало ранговых модификаций состоит в следующем: используя известное решение некоторой задачи линейной алгебры с первоначальной матрицей А, решают ту же задачу с модифицированной матрицей А"=А+& , где матрица Ь имеет малый ранг. Существует ряд работ, посвященных методам решения задач с модификациями, ранг которых равен I или 2. Например, это задачи обращения модифицированных матриц [45",М,48] f разложения Гаусса и Холесского [19, 2.9 , 30, 31] , используемые, например, для решения линейных систем уравнений ортогонально-треугольные разложения модифицированных матриц 2о j 31] , проблема собственных значений для модифицированных матриц \ 1Н ,33] и др. Число арифметических операций в этих алгоритмах для матриц размера Yi Yl имеет порядок 0(tb/, в то время как методы решения каждой из указанных задач для первоначальной матрицы требуют 0(л- ) операций.
Задачи линейной алгебры с мало ранговыми модификациями нередко встречаются в приложениях [1, \\, 2.3,25, 28 , Ъо , 33] Рассмотрим некоторые из них.
Разложения Гаусса и Холесского для модифицированных матриц
Подобные задачи возникают также в гидравлике, структурном анализе, численном интегрировании, исследовании экономических моделей, и т.д. Алгоритмы модификации используются также при построении некоторых методов обращения матриц и решения систем линейных алгебраических уравнений [2Д 32., ]
Итак, методы матричных модификаций находят широкое применение в решении различных научно-технических и экономических задач. Нередко при этом приходится решать последовательность задач модификации с матрицами больших размеров или в режиме реального времени и возникает необходимость существенного увеличения быстродействия ЭШ.
Предлагаемые в диссертации модели систолических систем -один из возможных подходов к решению этой проблемы. СМ могут размещаться на одной или нескольких СБИС и входить в состав более крупной ВС в качестве спецпроцессоров для решения определенных классов задач. Кроме того, моделирование потоков данных для некоторого алгоритма в соответствующем СМ позволяет понять возможно ли разделение этого алгоритма на отдельные модули с малым количеством связей между ними, и реализация каждого модуля с использованием только локальных передач данных. Подобный анализ облегчает реализацию данного алгоритма на параллельных ВС.
В первой главе диссертации исследуются формальные возможности распараллеливания некоторых методов модификации. Для этого каждый алгоритм расчленяется на связанные между собой модули - фрагменты. Рассматривается реализация этих фрагментов с использованием различного числа параллельных процессоров.
Приводятся значения высоты параллельных схем, ускорения счета, загруженности процессоров, требования к объему дополнительной памяти ЭЕМ, число конфликтов в памяти, возникающих при одновременном обращении нескольких процессоров к одной и той же ячейке памяти.
Характеристики параллельных схем даны в сводной таблице, приведенной в Приложении. В конце первой главы из всех фрагментов алгоритмов модификации выбираются основные фрагменты, имеющие регулярную структуру, на которые приходится основная доля ( 0(W2)) операций каждого алгоритма, Большинство из этих фрагментов встречается в нескольких разных алгоритмах.
Вопросы архитектуры параллельных ЭШ для реализации алгоритмов модификации исследуются в последующих главах. Результаты первой главы опубликованы в работе ]_Ч J
Во второй главе дается описание одного класса алгоритмов линейной алгебры, включающего в себя большую часть выделенных в первой главе основных фрагментов. Для реализации алгоритмов из этого класса Ж предлагаются модели СМ двух типов. Исследуются процессы решения задач на этих СМ, организация потоков данных, число и организация обменов с ОП. Показано, что при реализации всех алгоритмов из класса М/ на СМ потоки данных и организация обменов с ОП являются однотипными. Для разных алгоритмов различаются только виды и функции используемых элементарных процессоров. При этом достигается асимптотически полная загруженность элементарных процессоров, если их число р достаточно мало Р- (М При реализации алгоритмов на СМ достигается значительное ускорение счета по сравнению с обычным, последовательным способом выполнения алгоритмов на ЭВМ и уменьшается число обменов с ОП.
В третьей главе показано, что почти все выделенные основные фрагменты методов модификации принадлежат классу алгоритмов ДС, описанному во второй главе. На основе построенных моделей конкретизируются модели СМ двух типов для отдельных фрагментов. Предполагаются также модели систолических массивов для фрагментов методов модификации, не входящих в класс AL . Показано, что большинство из рассматриваемых фрагментов реализуется на СМ с использованием ЭП одних и тех же видов.
Основные результаты, второй и третьей глав опубликованы в работе 5 Результаты работы докладывались на заседаниях научно-исследовательских семинаров кафедры АСВК ф-та ВМК МГУ, ЙПК АН СССР и на научно-исследовательском семинаре "Архитектура ЭЕМ и численные методы" в ОВД АН СССР. Автор выражает глубокую благодарность своему научному руководителю профессору В.В.Воеводину за постоянное внимание, поддержку и помощь в работе..
Метод модификации симметричной проблемы собственных значений
Особенность распараллеливания рассматриваемых методов модификации разложений Гаусса и Холесского состоит в том, что процедура вычисления, скажем, столбцов нижней треугольной матрицы, входящей в разложение, является существенно последовательной, а число элементов в столбце, операции над которыми распараллеливаются, убывает с ростом его номера. Поэтому обычно трудно добиться загруженности процессоров, близкой к I; Число тактов в соответствующих параллельных схемах не может быть меньше (/( ), даже при неограниченном увеличении числа процессоров.
Пусть известно разложение Гаусса Irtxlo, чиатрицы А йл;] » А - L\J , (I#6) где L — КІЇ] - нижняя треугольная матрица, 4/=1.] -верх в о няя треугольная с единицами на диагонали. Модифицированная мат рица А имеет вид А = А + сгт , (1-7) - 27 -где С , Ъ - Kb - мерные вектор-столбцы. Тогда для поиска факторизации Гаусса А = L V предлагается следугощий метод ( см. [19] ). л(0) Л (0) Метод 1.5. I) Положить А —А (т.е., &. = & , Далее верхний индекс Ю будет указывать номер шага в методе Гаусса. 2) Для 1С =1,2, ..v, h/ выполнить: (к f = с vt» , - VJ„ І Для і = K+ir.. выполнить: Хі = J - Х "1 (1.8)
При каждом Ю разделена информация о предыдущей итерации и ее коррекция. Производится последовательная коррекция 1С-и строки матрицы U и к- г о столбца матрицы L Получаем соответствующие столбец и строку матриц v и L , которые записываем на место V и L . Число операций: 2h, умножений, сложений, Тл 4 h .
Алгоритм является последовательным по Ю . Но для каждо-го шага цикла по К, распараллеливается внутренний цикл по V , а также в некоторых случаях можно совместить во времени выполнение части операций для 1С -го и (ic+ty-ro шагов цикла.
Для каждого фиксированного 1С , К =1,2, ..., Уъ , пе ред циклом по \ выполняются 5 операций над величинами, зависящими только от 1С и не зависящими от А, Будем здесь и ниже называть такие операции скалярными. Затем, для 1С =1,2, ,.;, И-1 в цикле по \ , J =кИ ,...,1 , выполняются 8 одинаковых для всех \ операций над величинами, зависящими и от 1С , и от Л Такие операции назовем векторными.
Согласно утверждению I.I, высота параллельной схемы при любом числе процессоров не меньше, чем Зи-+О(0 Такую высоту можно получить при р= 2)1г+1 процессорах. При этом для каждого К=4,2,..., И-4 на 3(и-К)+4 процессорах за 3 такта параллельно выполняются некоторые векторные и скалярные операции для текущего ( 1С -го ) шага цикла, и остальные операции для следующего (к.-Н)-го шага цикла по 1С . Получим:
При О-іи + і параллельных процессорах можно получить "Чп.+1 41г ; Здесь для каждого 1С используются процессоров, на которых за 4 такта выполняются все векторные и последние две скалярные операции для 1С -го шага цикла, а также первые три скалярные операции (к+1)-го шага циклам Получим -І При р= KL+1 , аналогично можно получить При каждом К- работают Vt-k+2/ процессоров.
Если имеется произвольное число р ЇЬ процессоров, то можно предложить способ распараллеливания, который заключается в комбинировании различных путей распараллеливания при разных К- # Он основан на том, что с ростом К уменьшается число значений i и количество вычисляемых величин в формулах (1.8), Этот способ позволяет также повысить загруженность процессоров при р=а-Н и ф-1п+\ .
Для тех Ю , при которых її р 2(Vi-k)+3, тело цикла выполняется на Yl - К + Ъ параллельных процессорах за 8 тактов; если 3 + 2(п,-к) р 3(vt-k)-h Ц ,то для таких \С телоцикла выполняется на 2()г-к)+3 процессорах в 4 такта; наконец, если р 3(л-к)+ Ц , то распараллеливание производится на 3(л-к) + -Ч процессорах за 3 такта
Описание одного класса алгоритмов линейной алгебры
Принципы распараллеливания этого алгоритма такие же, как в методе 1,7. На I этапе элементы каждой 1С -й строки матрицы К и 2К делим на XfcK . Эти деления можно выполнить за I такт на hv +i процессорах, или за \\ \ тактов на и+1 процессорах. Получим левую треугольную систему с единичной диагональю, которую решаем за 2 ( Ki-1 ) тактов на л-4 процессорах, так же, как в методах її6 и 1,7,
На II этапе сначала вычислим все р Величины Р связаны линейным рекуррентным соотношением 0; 1 = 9: + o2-i , и все они находятся за Ь 9М тактов на \к/аї\ процессорах по схеме 3 из[24,с; 8 ] . Дальнейшие вычисления требуют 7 тактов на YI процессорах. Всего на II этапе имеем Іоак +0(4) тактов. III и ІV этапы при распараллеливании объединяются. Так же, как и в методе 1,7, , высота параллельной схемы этой части алгоритма не может быть меньше 8YI +0(\) при любом числе процессоров, что легко увидеть, если начертить граф объединенного цикла по I и воспользоваться утверждением 1,1, На р=п+4 процессорах можно получить 8 іг + 0(1) тактов, причем для каждого t работают h - і + Ъ процессоров, на которых за 8 тактов выполняются скалярные операции параллельно с векторными. Использовать большее число процессоров ( 0(ln2)) не имеет смысла по той же причине, что и в методе 1.7.
При v\+\ процессорах требуется 0(rv) СЛОв дополнительной памяти. Имеется около 5гъ конфликтов в памяти со средним порядком 1 ± , їх конфликтов со средним порядком VM ІҐЬ и около бгг 2-конфликтов.
В этом параграфе рассматриваются два метода факторизации модифицированных прямоугольных №хц -матриц. Распараллеливание их этапов, в большинстве случаев, выполняется так же, как распа раллеливание рассмотренных выше алгоритмов. Характеристики парал лельных схем существенно зависят от соотношений величин rYt , уь и других параметров алгоритма. К примеру, при некоторых наборах этих параметров можно получить загруженность процессоров, близ кую к единице, если число их равно to.+-lt и загруженность 1 при процессорах. Vnx а-матрица ранга "t , гП Метод 1.10. Полная ортогональная факторизация (ПОФ). Если А - Vnxа-матрица ранга "t , rYl H T , то ее ПОФ есть: (Г. 20) где (J, -ортогональная г хщ -матрица, с -ортогональная У\ % h -матрица, R -невырожденная верхняя треугольная t t матрица. Такое разложение матрицы А на множители можно использовать , например, для вычисления псевдообратной матрицы
Далее, возможны пять различных случаев сочетания об у и соответствующих значений ранга Q Q(А / в тРех из этих случаев: а) ФО, R o, +l- б) d Otj Oy р ; в) o Vj р О » J — матрица о3 является верхней треугольной и имеет соответствующий ранг (т.е. в случаях б) и в) получаем 4; = 0 ; 03 - 0 ). Тогда матрицы Q и Z = 2 уже вычислены, а матрица R == о3 в случае а) или R=-K в случаях б) ив), т.е. вычисления окончены.
В двух оставшихся случаях: для получения R , 2 и Ці необходимы дополнительные вычисления, которые аналогичны операциям ІУ этапа общей части алгоритма. Эти вычисления здесь не приводятся; подробности можно найти в работах [31 »М
Число операций общей части алгоритма: 4 (т + / -hi( m.3it)+ умножений, S(m2+K2)+-b(2m-2 )+2i сложений, УИ+м-2 квадратных корней. Распараллеливание алгоритма.
Во многих этапах можно выделить независимые части ("ветви") алгоритма, которые выполняются параллельно друг другу. Распараллеливаются также вычисления внутри каждой ветви.
I этап. Вычисляются параллельно два произведения матриц на векторы. Эффективное распараллеливание возможно на процессорах за iojjm, +1 тактов (так как w Ъ Yi ), с использованием схем сдваивания при суммировании. На wt+ п процессорах требуется 2т-1 тактов. При этом каждая сумма Иг или ЇЬ чисел вычисляется на отдельном процессоре.
II этап. Будем считать здесь и в дальнейшем, что все про-межуточные матрицы при получении Z и Q, записываются на одно и то же место ( на место Ї и Q. ) в память вычислительной системы.
Фрагменты алгоритмов модификации, принадлежащие классу М, и их реализация на СМ
Рассмотрим теперь реализацию алгоритмов из класса М на систолических массивах второго типа.
Опишем модель СМ второго типа. Пусть выбран некоторый алгоритм, например, формулы (2.1). Соответствующий СМ состоит из р элементарных процессоров и имеет вид, изображенный на рис. 2.9.
Каждый ЭП имеет локальную память (ЛП), размером в. 2л01 ячеек. Как и на рис. 2.1, верхние горизонтальные стрелки, соединяющие ЭП, означают каналы связи между ними, по которым слева направо передаются компоненты векторов X , одновременно для всех VwM,2,..., № . Стрелки с одним свободным концом означают каналы связи СМ с ОП. Нижние горизонтальные стрелки означают каналы связи ЛП всех ЭП, по которым производится засыл-ка в ЛП входных данных U - и выбор результатов U j При этом ячейки ЛП используются как проводники. Считается, что продвижение данных на одну ячейку вправо вдоль цепочки связанных между собой ЛП выполняется за I такт. Локальная память каждого ЭП связана также с функциональными устррйствами, входящими в его состав.
Все ЭП в СМ имеют один и тот же вид. Пусть Ь-і. » тогда элементарный процессор можно схематически изобразить так, как показано на рис. 2.10. Если ЬФ 1 ,то ЭП имеет аналогичный вид, но в ЛП отводится место для некоторых компонент векторов, и она имеет объем в 2Х0Ь ячеек. Эп состоит из конвейерных ФУ, выполняющих действия (2.4), (2.6), а также
Изменяемые и неизменяемые значения Ч. и и U j н для всех vM,...,l и очередных К0 значений С хранятся в ЛП каждого ЭП. Первоначально в две соседние ячейки ЛП засылаются из ОП одинаковые входные значения
Неизменяемое данное Ч-С н — выбирается из Ж в нужные моменты времени для вычисления 8«. (см. (2.4)). Значение іг«ц является изменяемым. В нужный момент времени оно выбирается из ЛП в ФУ "сложения", выполняется (2.21), и полученное новое зна-чение Ч и. возвращается в свою ячейку ЛП через N тактов. Это повторяется пока не будет вычислен окончательный результат Ч Как и в СМ первого типа, будем считать, что каждое ФУ в ЭП является конвейерным с тактом X . Функция %в вычис ляется за время Т КВТ . Считается, что все функции, выполняются за К тактов, и данные ос. выводятся из ЭП через к = 1чр+ Nft+ on A тактов после ввода их в него; Т = Kmax."C . Время пере А дачи данных между соседними ЭП включается во время Т , как и в СЖ первого типа. Для алгоритма (2.2) СМ имеет аналогичный вид.
Отметим, что описанные систолические массивы имеют одинаковое строение для всех алгоритмов из класса м/ . СМ для разных алгоритмов могут отличаться друг от друга лишь функциями Ш, входящих в их состав.
Реализация каждого алгоритма из класса М/ на таком СМ характеризуется теми же величинами Тр , о р, с р , что и в 2.3.
Теорема 2.2. Каждый алгоритм из класса Л может быть реализован на некотором СМ второго типа. При этом потоки данных однотипны для всех алгоритмов из класса Л . то достигается асимптотически полная загруженность ЭП, т.е. Доказательство. Рассмотрим организацию процесса счета по формулам (2.1) в описанном выше СМ. Предположим, что тогда соотношения (2.1) имеют вид (2.3). Если t или \п больше I, то реализация алгоритма на СМ аналогична, но число (ул) каналов передачи вдоль СМ данных (XV увеличивается в Иг раз, а объем 1-в I раз.
Матрица В разбивается на подматрицы, каждая из которых содержит р\0 строк Ъ » Будем говорить, что вычисления (2.3), проводимые для элементов bCi одной такой подматрицы, соответствуют частичной задаче. Перед решением очередной 43 в ЛИ каждого процессора засылаются входные данные
На верхний вход каждого ЭП подаются вперемежку элементы соответствующих К0 строк матрицы Элементы каждой строки вводятся с интервалами Vnax(J(0 Кф) тактов, в порядке возрастания л . Для асимптотически полной загрузки СМ необходимо выполнение условия к0 К@ , так как между любыми двумя данными, вводимыми с одного и того же входа для вычисления одного ijL , интервал времени не может быть меньше, чем Кф тактов, С левых входов СМ вводятся значения
