Систолические системы для задач матричных модификаций тема диссертации и автореферата по ВАК РФ 01.01.10, кандидат физико-математических наук Бондаренко, Екатерина Владимировна

• Бондаренко, Екатерина Владимировна
• кандидат физико-математических наук
• 1984

Оглавление диссертации кандидат физико-математических наук Бондаренко, Екатерина Владимировна

Введение

Глава I. Параллельные метода линейной алгебры с малоранговыми модификациями.

§1.1. Общие принципы анализа параллельных алгоритмов.

§ 1.2. Обращение модифивдрованных матриц.

§ 1.3. Разложения Гаусса и Холесского для модифицированных матриц.

§ 1.4. Методы модификации разложений матриц на ортогональные и треугольные множители

§ 1.5. Метод модификации симметричной проблемы собственных значений.

§ 1.6. Основные фрагменты алгоритмов линейной алгебры с малоранговыми модификациями.

Глава 2. Систолические массивы для одного класса алгоритмов линейной алгебры.

§ 2.1. Необходимость разработки алгоритмов для систолических систгем.

§ 2.2. Описание одного класса алгоритмов линейной алгебры.

§ 2.3. Систолические массивы первого типа с двусторонними потоками данных) для алгоритмов из класса Л

2.4. Систолические массивы второго типа ( с односторонними потоками данных и локальной памятью) для алгоритмов из класса Л*

Глава 3. Систолические массивы для реализации методов матричных модификаций.

§ 3.1. Основные виды и функции элементарных процессоров.

§ 3.2. Фрагменты алгоритмов модификации, принадлежащие классу М, и их реализация на

§ 3.3. Систолические.массивы первого типа для решения треугольной системы линейных уравнений.

§ 3.4. Систолические массивы второго типа для решения треугольной системы линейных уравнений.

§ 3.5. Некоторые замечания

Введение диссертации (часть автореферата) на тему «Систолические системы для задач матричных модификаций»

На настоящем этапе развития вычислительной техники потребности в средствах обработки информации непрерывно возрастают. Это вызвано качественным и количественным изменением характера вычислительных задач, увеличением их сложности и объема. Как отмечено в работе [12] , возникает необходимость исследования объектов и явлений в целом, перехода от линейных моделей к нелинейным, изучения объектов в динамике, построения пространственных моделей. Наиболее крупные вычислительные ресурсы требуются для задач ядерной энергетики, аэродинамики и гидродинамики, теории климата, циркуляции атмосферы и океана, оптимального управления, исследования операций и др. Математическое моделирование в этих областях приводит к необходимости решать, например, системы линейных алгебраических уравнений с ленточными матрицами с числом переменных порядка 10 и шириной ленты около 10^ ; с разреженными симметричными матрицами размера ©Kofi ло 10 . В ряде приложений существует потребность решать задачи к линейного программирования с числом переменных порядка 10 и числом ограничений порядка 10^.

Быстродействие однопроцессорных машин традиционной структуры перестает удовлетворять возрастающим потребностям решения крупных научно-технических и экономических задач. Необходим новый подход к методам разработки, производства и применения ЭШ 1<6 , Щ

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

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

За последнее время появилось большое количество работ, посвященных двум направлениям развития параллельных вычислений: параллельным вычислительным методам и параллельным вычислительным системам. Существует ряд примеров построения быстродействующих ВС [J ,15* fH З3 . Проводилась также разработка параллельных вычислительных методов. Однако нередко при разработке методов недостаточно хорошо учитывались реальные ограничения со стороны ВС. Учитывались лишь некоторые характеристики метода, например, проводилась оптимизация высоты алгоритмам. Имеется ряд обзоров, посвященных параллельным методам, например, [ 2\ , 22,34, 42]

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

За последнее время появилось немало работ, в которых предлагаются модели параллельных вычислительных систем, эффективных для реализации определенных классов вычислительных методов С , 18 , 38 , 39 , НО , //1] . Часть этих работ посвящена разработке систолических вычислительных систем для некоторых методов решения задач линейной алгебры.

Понятие систолических систем было введено в работах ,

L**] , 139] , хотя похожие идеи встречались и в более ранних работах, например, ргб] , С35*3 • Систолическая система представляет собой совокупность элементарных процессоров (ЭП), объединенных в линейную или пленарную тзеть, или систолический массив (СМ). Каждый ЭП связан со своими ближайшими соседями и выполняет некоторый набор операций над последовательностью данных, которые упорядочений и ритмически проходят через СМ. Развитие идей СМ связано с развитием технологии сверхбольших интегральных схем (СШС) в построении вычислительной техники. Модели систолических систем были предложены в качестве одного t из возможных типов архитектур ВС на основе СШС.

Уровень развития технологии, используемой при создании блоков центрального процессора и памяти ЭШ, всегда влиял на архитектуру ЭВМ . Как известно, современная полупроводниковая технология достигла того предела, за которым уже не следует ожидать значительного увеличения скорости срабатывания логических элементов и выполнения отдельных арифметических операций ( см.например, £3] ). Этот предел определяется скоростью распространения электрических сигналов и физическими размерами функциональных устройств. Однако степень интеграции продолжает расти, и в ближайшем будущем станет реальным размещение к с

10 - 10 логических элементов на одной грани кристалла. Такая CHIC олицетворяет новый этап технологии в разработке ВС, который требует новых идей в организации ЭШ, теории вычислений и других смежных областях.

Как отмечено в [16] , большой интерес представляет перспектива использования микропроцессоров в качестве элементов ЭШ. В настоящее время одно- и многокристальные микропроцессоры внедряются как компоненты микро и мини- ЭШ, как встроенные вычислительные устройства в приборах, и т.п. Развиваются новые подходы к применению в проектировании ЭШ микропроцессоров и "программируемых" БИС. Появление ШС и микропроцессоров и применение их как базовых конструкторских элементов вычислительных устройств и комплексов коренным образом меняют методы логического проектирования машин и их структуру.

Технология СШС представляет большие возможности разработчику систем, но налагает ограничения на разработку алгоритмов £18] . Главные ее преимущества: большое число приборов, доступное при низкой стоимости, малые размеры и повышенная надежность на схемном уровне.

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

Если параллельный алгоритм организован как совокупность вычислительных модулей меньших размеров, то такие модули могут быть распределены по различным СШС. Простейшая ВС может состоять из нескольких СШС, основной памяти, центрального процессора (ЦП) и схемы соединения [18] . Каждая СШС содержит несколько процессоров, работающих параллельно.

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

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

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

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

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

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

-процессоры могут быть различных типов и выполнить различные функции; одна из задач - как уменьшить число используемых типов ЭП. Обычно рассматриваются СМ, работа которых синхронизирована, хотя это требование и необязательно.

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

В настоящее время существует ряд работ, посвященных разработке моделей СМ для решения определенных классов актуальных задач. В основном они посвящены реализации на СМ различных алгоритмов линейной алгебры: умножение матрицы на вектор и матрицы на матрицу, решение треугольной системы уравнений, L~\J -разложение матриц , 39] , задачи свертки

33 , f QR -^алгоритм для решения проблемы собственных значений Е^] и других. В большинстве случаев предлагались систолические массивы, содержащие число элементарных процессоров, связанное с размером матрицы задачи. В частности, были рассмотрены одномерные и двумерные СМ для различных операций над ленточными матрицами с числом ЭП, равным или кратным ширине ленты матрицы. При уменьшении числа ЭП предлагалось решать задачи на СМ с помощью разбиения матрицы.

В этих работах, как правило, не использовался конвейерный принцип организации самих ЭП. Исключением является, например, работа 1^0] , в которой предложены двухуровневые СМ для задач свердки, и все ЭП состоят из конвейерных функциональных устройств (ФУ). В то же время применение этого принципа может значительно увеличить быстродействие ЭВМ и повысить эффективность использования всего оборудования.

В данной работе предлагаются математические модели систолических систем для одного важного класса задач линейной алгебры - задач малоранговых матричных модификаций. ' Особенности предлагаемых СМ состоят в том, что они содержат произвольное число р ЭП, не связанное прямо с размерами матрищ задачи. Каждый ЭП, входящий в их состав, в свою очередь, является конвейерным, и при реализации алгоритмов достигается высокая загруженность всех ФУ, вплоть до уровня выполнения микроопераций ( при достаточно малых значениях р ).

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

Л» ной матрицей А-А+& , где матрица Б имеет малый ранг. Существует ряд работ, посвященных методам решения задач с модификациями , ранг которых равен I или 2. Например, это задачи обращения модифицированных матриц , разложения Гаусса и Холесского [19, 2.9,30, 31] , используемые, например, для решения линейных систем уравнений^ ортогонально-треугольные разложения модифицированных матриц

2о , 31] , проблема собственных значений для модифицированных матриц ["24 , 33] и др. Число арифметических операций в этих алгоритмах для матриц размера YixYl имеет порядок О (lb2) , в то время как методы решения каждой из указанных задач для первоначальной матрищ требуют операций.

Задачи линейной алгебры с малоранговыми модификациями нередко встречаются в приложениях [1, \\, 2.3,25, 28 , Ъо , 33] Рассмотрим некоторые из них.

I) Задача последовательной регрессии [1] . Часто рассматривается следующая задача. Неизвестная функция ^(т) может наблюдаться экспериментатором при некоторых значениях ее аргумента "С . Требуется дать описание поведения этой функции. Обычно выбирают некоторое семейство функций ^("О* тг) и аппроксимируют ^(р) линейной комбинацией этих функций по методу наименьших квадратов (МНК).

Обозначим через ^ » > • • •» наблюдения значений функции ^ в моменты , ~СХ Р. > t^ . Задача ставится так: найти ••• > ^Иг

Обозначим г п, т, у м^ 2Z t-ftM Ю--1 v 1=1 О о ! с2 , . I ^J-Цхйьматрищ.

Тогда задача принимает вид: найти || Ст ос |Г эс»

Обычно находят нормальное псевдорешение линейной системы уравнений X =2 , т.е., из всех решений указанной задачи

А Л) минимизации выбирают вектор X с наименьшей нормой. Из* (т.) Г+ п + вестно, что X = U 2 , - матрица, псевдообратная к Ст . Пусть вектор х^ вычислен,, и значение И^-С^Х^Ц является неприемлемо большим. В этом случае к семейству функций присоединяется функщя ^-hOO э И решается та же задача, т.е. , задача минимизации функционала ^

Матрица С^ получена из С^ путем присоединения к ней (ttv+l)-ro столбца, т.е. , путем одноранговой модификации.

А /„.Л л +

Решение модифицированной задачи задается вектором X — 2 имеющим минимальную норму среди всех возможных решений. Зная i(m) , можно найти за 0(т.ю,) арифметических операций.

2) Задачи математического программирования [-И, Й]

Во многих современных задачах оптимизации, особенно в экономике, точка оптимума оказывается лежащей на границе области определения изучаемой функции. Часто в постановке задач исходные данные не могут быть заданы точно, в силу трудностей, связанных с большой размерностью задач и способами получения коэффициентов уравнений, задающих гранищ области. Поэтому процесс решения задачи обычно проходит следующие стадии: постановщики задачи грубо очерчивают границы области, уточняя их лишь в районе предполагаемого оптимума. Затем ЭВМ решает оптимизационную задачу, находя положение точки оптимума на заданной границе. На основе полученного решения постановщики задачи дают описание нового,уточненного района границы, в котором находится полученная точка, а также, возможно, и другую информацию; далее происходит уточнение точки оптимума, и т,д, Такой процесс решения задачи предлагает использование диалогового режима работы ЭВМ. Необходимы методы, которые позволяют выполнять уточнение уже полученного решения за значительно меньшее время, чем нахождение решения заново.

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

3) Задачи моделирования и анализа кусочно-линейных резистивных электрических цепей [Зо] . Пусть кусочно-линейная резистивная цепь описывается уравнением ^ ? где fy - непрерывная кусочно-линейная функция, отображающая

Yi -мерное пространство R в себя; х -точка из R , соответствующая множеству выбранных переменных цепи; Ц/ r>)rv произвольная точка 1ч , соответствующая входу в цепь.

Для непрерывной кусочно-линейной функции l' все пространство R делится на конечное число t полиэдральных областей конечным числом граничных гиперплоскостей. Граничная гиперплоскость описывается уравнением гтх= с , где Ъ - нормаль к гиперплоскости.

В каждой mrv -й области функция является линейной, и уравнение цепи имеет вид

АЫХ = II ,

А W 6 ы где А -постоянная кьха - матрица ? ЯаГ -постоянный Yi -мерный вектор. Непрерывность функции f накладывает ограничения на матрицы дН соседних областей. Пусть две области Ъ4 и -соседние, т.е., имеют общую границу - гиперплоскость с нормалью Ъ . Необходимое и достаточное условие непрерывности ^ на Н : если на границе i7aoc = 0 , то должно выполняться равенство . ^

А 41- А л ос .

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

При решении задачи анализа кусочно-линейных резистивных цепей используется метод, в котором возникает необходимость последовательного решения систем линейных алгебраических уравдОн) (m) п нений вида А Х= U , \п = 1,2,., v . Для их решения обычно используется метод Гаусса, причем только для матрица А ЦТ- разложение находится полностью, а для факторизации остальных матриц Д^ ^ применяются соответствующие методы модификации.

Подобные задачи возникают также в гидравлике, структурном анализе, численном интегрировании, исследовании экономических моделей, и т.д.

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

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

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

- 15

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

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

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

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

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

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

Основные результаты, второй и третьей глав опубликованы в работе £ 5 ]

Результаты работы докладывались на заседаниях научно-исследовательских семинаров кафедры АСВК ф-та ВМК МГУ, ИПК АН СССР и на научно-исследовательском семинаре "Архитектура ЭШ и численные методы" в OEM АН СССР.

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

- 17

Заключение диссертации по теме «Математическое обеспечение вычислительных машин и систем», Бондаренко, Екатерина Владимировна

Основные результаты работы заключаются в следующем.

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

2. Показано, что некоторые из рассмотренных алгоритмов имеют высоту параллельной схемы или (?(i) при

0(vi?) процессорах для матриц размера Ю-xVL . При процессорах высота схемы равна 0(|г) ; для части алгоритмов эта высота является минимальной.

3. На основе проведенных исследований выделены основные фрагменты алгоритмов модификаций, на которые приходится главная доля ( 0(|г2) ) арифметических операций. Описан класс «Л алгоритмов линейной алгебры, включающей в себя почти все эти фрагменты.

I -V

4. Построены и исследованы модели систолических систем двух типов для реализации алгоритмов из класса М/ .

5. Показано, что все алгоритмы из класса М/ можня реализовать на построенных СМ с асимптотически полной загруженностью при достаточно малом числе процессоров р , р « о (Vl)

6. Исследованы процессы реализации алгоритмов на СМ и организация потоков данных. Получены основные характеристики процессов: время реализации алгоритмов, ускорение счета, средняя загруженность ЭП.

7. Для каждого из выделенных фрагментов методов модификации показано, что он принадлежит классу А или имеет похожую структуру. Конкретизированы модели СМ для их реализации, в частности, описаны типы наиболее часто используемых Ш.

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

Приведены характеристики процессов.

ЗАКЛКЯЕНИЕ

Список литературы диссертационного исследования кандидат физико-математических наук Бондаренко, Екатерина Владимировна, 1984 год

1. Алберт А, Регрессия, псевдоинверсия и рекуррентное оценивание. М.: Наука, 1977.

2. Алгоритмы,математическое обеспечение и архитектура многопроцессорных вычислительных систем. М.: Наука, 1982.

3. Бабенко К.И. Некоторые вопросы анализа математических алгоритмов решения задач и архитектуры ЭВМ. Препринт ОШ АН СССР № 7. М: ШШИ, 1981.

4. Бондаренко Е.В. Распараллеливание методов модификации матричных факторизации. В сб.: Вычислительные процессы и системы, вып.2. М.: Наука, 1985, с.228-264.

5. Бондаренко Е.В. Систолические массивы для некоторых методов решения задач с малоранговыми модификациями. -В сб: Архитектура ЭВМ и численные методы. М.: OEM АН СССР, 1984, с.15-57.

6. Воеводин А.В. О математической модели спецпроцессора для решения задач линейной алгебры. В сб.: Численные методы алгебры. М: Изд-во МГУ, 1981, с.69-111.

7. Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, IS77.

8. Воеводин В. В. Некоторые машинные аспекты распараллеливания вычислений. Препринт ОШ АН СССР № 22. М.: ШНИТИ, 1981.

9. Воеводин В.В. Математическая модель конвейерных вычислений. Препринт ОШ АН СССР В 42. М: ВИНИТИ, 1982.

10. Воеводин В.В. Конвейерные вычисления на потоках алгорифмов. Препринт ОШ АН СССР В 48. М.: ВИНИТИ, 1983.

11. Глушков В.М. О диалоговом методе решения оптимизационных задач. Кибернетика, 1975, $ 4, с.2-6.

12. Глушков В.М., Молчанов И.Н. О некоторых цроблемах решения задач на ЭВМ с параллельной организацией вычислений.-Кибернетика, 1981, л'4 (100), с.82-88.

13. Головкин Б.А. Параллельные вычислительные системы. М: Наука, 1980.

14. Карманов В.Г. Математическое программирование. М. :Наука, 1975.

15. Королев Л.Н. Структуры ЭВМ и их математическое обеспечение. М.: Наука, 1974.

16. Марчук Г.И., Котов В.Е. Модульная асинхронная развиваемая система 4.1,2. Препринты ВЦ СО АН СССР № 86, $ 87. Новосибирск, 1978.

17. Марчук Г.И.,Котов В.Е. Проблемы вычислительной техники и фундаментальные исследования. Автоматика и вычислительная техника, 1979, Л 2, с.3-14.

18. Молдован Д.И. О разработке алгоритмов для систолических матриц СШС. ТЙИЭР, 1983, т. 71, № 1,с. 21-30.

19. Петренко А.И., Власов А.П., Тимченко А.П. Метод припасовы-вания для решения линейных алгебраических систем уравнений. В кн;-: Автоматизация проектирования в электронике. Респ. межвед.научно-техн.сборник. Киев, 1977, с.27-31.

20. Соренсен Д.К. Обзор некоторых методов модернизации матричных факторизаций. Численный анализ на Фортране, вып.17. М: Мир, 1976.

21. Фаддеева В.Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре. 4.1. Препринт ЛОМИ АН СССР, Р-6-77. Л., 1977.

22. Фаддеева В.Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре. 4.2. Препринт ЛШИ АН СССР, P-6-8I. Л., 1981.

23. C.Q. J cfax of Mettods fit <io$VitL<p <Ho ntcht Q.4, iCtoullfi OUi equ^t'ons . — MaiL . Соиьр> Pv. M , p.

24. EurucJv R- , Л/Ze/W С. Я, Swe*seb Я.С. Ra*K-ohtmJifrcah'on, of- ibe iymmiUtc гуекр^&м

25. Лимы. Mdk . , 49¥Г, * 34, J4 , Р- 31-42 . ВььсА > tott&b С. P. Up Jai Си £ Ит ^прЬъ

26. VOJUul decomposition. Jfum&c. Mati 494-8 } zr 24, f. 444-<*9.toh S. А/. hal'-i^e Coyui^'oh fy ь-Ышенiional Cie-valCve afttifi of fcHcU"SMemoki'Hes. IEEE Tt**c. Coy., 4969, « C-4t,p. ЗМ-ЗбГ.3. МЛ*** Сигаем ххтк

27. AlW . Mali. Сомр. , 49GC, v. 20, JV93,p. Mo-w. A / nъчМ Seifa S.N. J toil оь -tit

28. AlCUt^t ioUiCoK of ntaiux pined tydlnnl1. BIT, p. Ш-121.

29. FhtcW РоигеМ 0fu ^ hboJifi'cbit'oH,

30. G-otJpvti Ъ. Jiodi^i'caiCoh, HieU.oJs ^^ ChWcichtp toaiuces and totvttia tutier»* of- Itnea-^c aige-iiaCc £aua it-'on6 , — JJaik . Сотр. 9 4632) ir. 2.6, p. 829- 8S2 .гойг^ H. Some tboch'j-.feJ mapxof terns. Si AM Reir. , №3 , к /Г, M2,p. 3JV-33S

31. UeHhi #.£. J Survey pa^aWei aicjotCihftisin Mumziicai h'fteat . $ZAM fair.,194.% , ir. 20, Л/4 , p. Mo-W?.

32. Цеит'е F. C. HviaiCv-z att-Ct^g

33. Uicu-Ch : М1Г Press, 1961.

34. House bolder- A.S. Pb-Lnccpies нкмггс'еаРanalysis : Mc. (ггаъг- Hiti, Л/его- Уочж 9

35. Кипу H-T. Tkz s-ltt<c4v>te. у pa^ifel afyoW^ms.

36. Qdirances in compuittsy 1980> v. i9, p. £5~-H2. Kun^ И.Т. brky, axckdetivLtes ?1.EE Co^ccUt , W2, v. p.

37. Kung И.Т., LeCsetson . S^ioicc atrags jUt VLSI.

38. Sparse mailt* ptoceec/t'figgy ,p. 2.S8-282.

39. Ктр H.T., L.M,P Уеи L. Л iuro-&trefpCpzit-'neJ ^d-fv&'c ceecaiy to nvofcroons. —

40. Co и fete* с e он VLSI and compu+aitotis}

41. Кипу H.T., So^S.IV. J iyih&c 2-% cohtroLicoftchCp . TechhecaP ЧАроъЬ , СалИедСг- ftleffon 4/mlv. ^hp. <f Coy. , PMsSwig 9w<i,p.itt-jeo. Ml гайке г W. L. J раьл&е&Ъм u,humit^cac Quaiy$,'s . SI AM Rev. , mi, v: /jT MH , p. $24-5-1*.

42. Russzli R.M. TU Qxay-j tornfuiib iyiietn,. — Comm. ACM , /m, v. 21 , p. 63-42 .

43. ScAt^'^W R. Sys-t-oio'c attays Jtoi ugetLtraiues .— Leciute. Noies Си, M<db. ; 1923 , JVjOOf SkPttoan 3. , Ml owl's on W.3. Adjusihiehi an LttVe'cse maivCx Coxites рои d

44. Ch, CU CotiL/nfv ОЪ *coltr -Uj2,0%C%Chat mailtX Г . Sbii'si. , ir. 29,1. ЫЧ , f. w.

45. Sherman 3. , ffloxtiSon W. 3. JJj Lhvezse malic x Coxiespon dg. ~to a cJ\ahge onei&metti of Л- tjCire/i matte x. — dm. m*tt. si. , , v. 2<f 9 M 9 p. W.

46. Характеристики параллельных алгоритмов малоранговых матричных модификаций

47. Алгоритм Размерность матрицы Число операций, Тч Число процессоров, р Асимптотические' значения

48. Число тактов, ть Г Ускорение Sp Загруженность

49. Обращение матрицы при изменении единственного элемента уь * п ОМ 5" 0,4 лг1. Р 1

50. Обращение матрищ при изменении единственного столбца 1к Н-Г- 1 £©9 и, цгх /г к Уи1. Чп* Р р 13, Обращение симметричной матрицы при изменении симметричных строки и столбца V + 0(к) vt2+ п Щъ 2 и* 2. -Co^h,k,x п, к V К 11. W р Р 1