Цена доставки диссертации от 500 рублей 

Поиск:

Каталог / ФИЗИКО-МАТЕМАТИЧЕСКИЕ НАУКИ / Математика

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

Диссертация

Автор: Бондаренко, Екатерина Владимировна

Заглавие: Систолические системы для задач матричных модификаций

Справка об оригинале: Бондаренко, Екатерина Владимировна. Систолические системы для задач матричных модификаций : диссертация ... кандидата физико-математических наук : 01.01.10 Москва, 1984 163 c. : 61 85-1/2685

Физическое описание: 163 стр.

Выходные данные: Москва, 1984






Содержание:

Глава
I Параллельные методы линейной алгебры с малорангоЕыми модификащями
§11 Обпрае принципы анализа параллельных алгоритмов
§12 Обращение модифиодрованных матриц
§13 Разложения Гаусса и Холесского для модифицированных матриц
§14 Методы модификации разложений матриц на ортогональные и треугольные множители
§15 Метод модификации симметричной проблемы собственных значений
§16 Основные фрагменты алгоритмов линейной алгебры с малоранговыми модификациями ,
Глава 2 Систолические массивы для одного класса алгоритмов линейной алгебры
§21 Необходимость разработки алгоритмов для систолических систем
§22 Описание одного класса алгоритмов линейной алгебры 6S
§23 Систолические массивы первого типа (с двусторонними потоками данных) для алгоритмов из класса Л '^ О
24 Систолические массивы второго типа ( с односторонними потоками данных и локальной памятью) для алгоритмов из класса М' -
Глава 3 Систолические массивы дяя реализации методов матричных модификаций
§31 Основные виды и функции элементарных процессоров
§32 Фрагменты алгоритмов модификации, принадлежащие классу М, и их реализация на СМ
§3w3 Систолическиемассивы первого типа для решения треугольной систеглы линейных уравнений
§34 Систолические массивы второго типа для решения треугольной системы линейных уравнений
§35 Некоторые захлечания ЗаключеШ'Ш , '

Введение:
На настоящем этапе развития вычислительной техЕшки потребности в средствах обработки информации непрерывно возрастают.Это вызвано качественным и количественным изменением характера вычислительных задач, увеличением их сложности и объема. Как отмечено в работе [12] , возникает необходимость исследования объектов и яЕяений в целом, перехода от линейных моделей к нелинейным, изучения объектов в динамике, построения пространственных моделей. Наиболее крупные вычислительные ресурсы требуются для задач ядерной энергетики, аэродинамики и гидродинамики, теории климата, циркуляции атмосферы и океана, оптшлального управления, исследования операций и др. Математическое моделирование в этих областях приводит к необходимости решать, например, системы линейных алгебраических уравнений с ленточными матрипами с числом переменных порядка 10 и шириной ленты около 10^ ; с разреженными симметричными матрицами размера около 10 . в ряде приложений существует потребность решать задачи линейного программирования с числом переменных порядка 10 и числом ограничений порядка 10 .Шстродействие однопроцессорных машин традиционной структуры перестает удовлетворять возрастающим потребностям решения крупных научно-технических и экономических задач. Необходим новый подход к методам разработки, производства и применения ЭШ [^б , Ш .Одно из главных направлений развития вычислительной техники включает радикальное увеличение суммарной производительности ША за счет совершенствования технической и технологической базы и новых архитектурных решений; освоение более эффективных - 5 форм и методов взаимодействия человека с машиной; переход от мономашин традиционной структуры к вычислительным системам (ВС) и комплексам разнообразных конфигураций, широких диапазонов мощностей и назначения.Одним из средств ускорения решения задач большого размера является распараллеливание обработки информации на различных уровнях.За последнее время появилось большое количество работ, посвященных двум направлениям развития параллельных вычислений: параллельным вычислительным методам и параллельным вычислительным системам. Существует ряд примеров построения быстродействующих ВС ]^ ib ,i^ ,^33 . Проводилась также разработка параллельных вычислительных методов. Однако нередко при разработке методов недостаточно хорошо учитывались реальные ограничения со стороны ВС. Учитывались лишь некоторые характеристики метода, например, проводилась оптимизапдя высоты алгоритмаСз].Имеется ряд обзоров, посвященных параллельным методам, например, Для оптимального решения задач из некоторого выделенного класса на ВС необходимо, чтобы параллельные методы и параллельные вычислительные системы развивались в тесной связи друг с другом. То есть, необходимо решать комплексную проблему отображения численных методов на ВС. Эта проблема заключается в еле- ' дующем: имеется некоторый класс задач, время решения каждой из которых на существующих ВС неприемлемо. Требуется построить ВС, на которой можно было бы решить каздую из этих задач за нужное время с заданной точностью. Кроме того, при построении и использовании такой ВС следует добиваться по возможности минимальной затраты материально-технических и трудовых ресурсов и наиболее эффективного их использования ( например, наиболее полной - 6 загрузки всего оборудования полезной работой, и т.п.). В работах ^^'^Ч содержится постановка общей проблемы в целом.Там же изложены основные принципы построения новых ВС, численных методов и средств отображения.Понятие систолических систем было введено в работах f3?] , L^^l f Г39] , хотя похожие идеи встречались и в более ранних работах, например, (^ 26] , ЕЗ^"] . Систолическая система представляет собой совокупность элементарных процессоров (ЭП), объединенных в линейную или планарную хзеть, или систолический массив (СМ). Каждый ЭП связан со своими ближайшими соседями и выполняет некоторый набор операций над последовательностью данных, которые упорядоченно и ритмически проходят через С1Д. Развитие идей СМ связано с развитием технологии сверхбольших интегральных схем (СШС) в построении вычислительной техники.Модели систолических систем были предложены в качестве одного i из возможных типов архитектур ВС на основе СШС. Уровень развития технологии, используемой при создании блоков центрального процессора и пах^ти ЭШ, всегда влиял на архитектуру ЭВМ Z^^l • Как известно, современная полупроводниковая ТЕХНОЛОГИЯ достигла того предела, за которыгл уже не следует ожидать значительного увеличения скорости срабатывания логических элементов и выполнения отдельных ариретических операций ( см.например, [J3] ). Этот предел определяется скоростью распространения электрических сигналов и физическими размерами - 7 функциональных устройств. Однако степень интеграции продолжает расти, и в ближайшем будущем станет реальным размещение к с.10 - 10 логических элементов на одной грани кристалла. Такая С Ш С олицетворяет новый этап технологии в разработке ВС, который требует новых идей в организации ЭШ, теории вычислений и других смежных областях.Как отмечено в [16] , большой интерес представляет перспектива использования микропроцессоров в качестве элементов ЭШ. В настоящее время одно- и многокристальные микропроцессоры внедряются как компоненты микро и мини- ЭНЛ, как встроенные вычислительные устройства в приборах, и т.п. Развиваются новые подходы к применению в проектировании ЭйЛ микропроцессоров и "программируемых" БИС. Появление Ш С и микропроцессоров и применение их как базовых конструкторских элементов вычислительных устройств и комплексов коренным образом меняют методы логического проектирования машин и их структуру.Технология С Ш С представляет большие возможности разработчику систем, но налагает ограничения на разработку алгоритмов ?18] . Главные ее преимущества: большое число приборов, доступное при низкой стоимости, малые размеры и повышенная надежность на схемном уровне.Для эффективного использования огромных ресурсов, Заключенных в СШС, необходимо использование параллелизма и конвейерности на различных уровнях организации вычисленийСЗ] .Если параллельный алгоритл? организован как совокупность вычислительных модулей меньших размеров, то такие модули могут быть распределены по различным СШС. Простейшая ВС может состоять из нескольких СШС, основной памяти, центрального процессора (Ш) и схемы соединения [18] . Каждая С Ш С содержит несколько процессоров, работающих параллельно.Кроме того, используется параллелизм и конвейерность на уровне каадого вычислительного модуля, а также при одновременной обработке всех битов слова.При разработке вычислительных систем на основе С Ш С возникают некоторые серьезные проблемы. Одним из ограничений при проектировании алгоритмов является узкое место, связанное с вводом-выводом информации (т.е. ограничения на число каналов связи и скорость обмена каждого процессора с оперативной памятью (ОП) ).Решение этой проблемы - в разработке параллельных алгоритмов, которые можно расчленить таким образом, чтобы количество связей между модулями было как можно меньше. Кроме того, данные, поступающие в СШС, ДОЛЖЕШ быть использованы наиболее полно, прежде чем они снова попадут на устройства ввода-вывода.Другая проблема связана с пересылкой данных в пределах одной СШС. Длительность прохождения сигнала может быть намного больше времени срабатывания логического элемента. Поэтому для эффективного использования ресурсов СШС необходимо, чтобы схема содержала только локальные межсоединения. Возникает необходимость разработки алгоритмов, которые при их воплощении в аппаратуре на основе С Ш С требуют только локальной передачи данных.В качестве возможного решения этих проблем были предложены архитектуры, организованные по принципу систолических массивов, Систолические системы на основе С Ш С обычно обладают следующими свойствами: -система много раз использует входные данные при однократном их выборе из ОП, что снижает число обменов информацией с ОП; -применяются принципы параллелизма и конвейерности; -процессоры соединены в линейную или планарную сеть (сие- 9 толический массив); кадцый из них связан лишь с соседит® ЭП и, может быть, с ОП; -процессоры могут быть различных типов и выполнить различные функвди; одна из задач - как уменьшить число используемьгх типов ЭП. Обычно рассматриваются СМ, работа которых синхронизирована, хотя это требование и необязательно.В случае систолических массивов решение задачи отображения вычислительных методов на аппаратуру представляет собой проектирование матрицы СШС в соответствии с особенностями алгоритма.В частности, были рассмотрены одномерные и двумерные СЗМ для различных операций над ленточными матрицами с числом ЭП, равным или кратным ширине ленты матриод. При уменьшении числа ЭП предлагалось решать задачи на Ш с помощью разбиения матриод.В этих работах, как правило, не использовался конвейерный принцип организации самих ЭП. Исключением является, например, работа E^Ol f в которой предложены двухуровневые СМ для задач свершЕИ, и все ЭП состоят из конвейерных функциональных устройств (ФУ). В то же время применение этого принципа может значительно увеличить быстродействие дШ и повысить эффективность использования всего оборудования. - 10 в данной работе предлагаются математические модели систолических систем для одного важного класса задач линейной алгебры - задач малоранговых матричных модификаций. ' Особенности предлагаемых СМ состоят в том, что они содержат произвольное число р ЭП, не связанное прямо с размерами матрищ задачи.Каждый ЭП, входящий в их состав, в свою очередь, является конвейерным, и при реализации алгоритмов достигается высокая загруженность всех ФУ, вплоть до уровня выполнения микроопераций ( при достаточно малых значениях Р ).Сущность малоранговых модификаций состоит в следующем: используя известное решение некоторой задачи линейной алгебры с первоначальной матрицей А, решают ту же задачу с модифицированной матрицей А ' = А + & , где матрипр. Ъ имеет малый ранг.Задачи линейной алгебры с малоранговыми модификациями нередко встречаются в приложениях [1, 'И , 2.3,25, 28 , Зо , 33] Рассмотрим некоторые из них. I) Задача последовательной регрессии [l] . Часто рассматривается следующая задача. Неизвестная функция ^(^) может - II наблюдаться экспериментатором при некоторых значениях ее аргумента "С • Требуется дать описание поведения этой функции.Обычно выбирают некоторое семейство функций р^|('с}, ^ fz(^ )*•••; Ср^(т) и аппроксимируют ^(р) линейной комбинацией этих функций по методу наименьших квадратов (1ЖК).2) Задачи математического програшлирования ['И,^] Во многих современных задачах оптимизации, особенно в экономике, точка оптимума оказывается лежащей на границе области определения изучаемой функции. Часто в постановке задач исходные данные не могут быть заданы точно, в силу трудностей, связанных с большой размерностью зацач и способами получения коэффициентов уравнений, задающих гранивд области. Поэтому процесс решения задачи обычно проходит следующие стадии: постановщики задачи грубо очерчивают границы области, уточняя их лишь в районе предполагаемого оптимума. Затем ЭВМ решает оптимизационную задачу, находя положение точки оптимуьэа на заданной границе.На основе полученного решения постановщики задачи дают описание нового,уточненного района границы, в котором находится полученная точка, а также, возможно, и другую информацию; далее происходит уточнение точки оптимума, и т,д, Taicofi процесс решения задачи предлагает использование диалогового режима работы ЭШ. Необходимы методы, которые позволяют выполнять уточнение уже полученного решения за значительно меньшее время, чем нахождение решения заново.В ряде случаев (например, в задачах линейного программирования) процесс поиска точки оптимума в области с уточненной границей сводится к решению систем линейных уравнений или поиску обратной матрицы для матривд ограничений, отличающейся от первоначальной на матрицу малого ранга ( например, одной строкой или столбцом).3) Задачи моделирования и анализа кусочно-линейных резне- 13 тивных электрических цепей [Зо] . Пусть кусочно-линейная резистивная цепь описывается уравнением т('х)= Ц ? где -у непрерывная кусочно-плинейная функция, отображающая У1 чйерное пространство R в себя; х -точка из К , соответствующая множеству выбранных переменных цепи; Ц/ r>lrv произвольная точка гч , соответствующая входу в цепь.Для непрерывной кусочно-линейной функции у все пространство К делится на конечное число t полиэдральных областей конечным числом граничных гиперплоскостей. Граничная гиперплоскость описывается уравнением где Ъ - нормаль к гиперплоскости.В каждой nrv -й области А ) ^ функция f- является линейной, и уравнение цепи имеет вид Л И ^ Ы где А -постоянная Кьха - матрищ , IxT -постоянный КЬ-мерный вектор.Это условие выполняется тогда и только тогда, когда где С - некоторый постоянный 1г - мерный вектор.Т.е., матрица каждой из областей А ) ^ является одноранговой модификацией матрицы любой области, соседней с х ) ^ .Подобные задачи возникают также в гидравлике, структурном анализе, численном интегрировании, исследовании экономических моделей, и т.д.4) Алгоритмы модификации используются также при построении некоторых методов обращения матриц и решения систем линейных алгебраических уравнений [2.1-,32.,^'^] Итак, методы матричных модификаций находят широкое применение в решении различных научно-технических и эконотлических задач. Нередко при этом приходится решать последовательность задач модификации с матрищми больших размеров или в режиме реального времени и возникает необходимость существенного увеличения быстродействия ЭШ. Предлагаемые в диссертации модели систолических систем один из возможных подходов к решению этой проблемы. Ш могут размещаться на одной или нескольких СБИС и входить в состав более крупной ВС в качестве спецпроцессоров для решения определенных классов задач. Кроме того, моделирование потоков данных для некоторого алгоритма в соответствующем СМ позволяет понять возможно ли разделение этого алгоритма на отдельные модули с малым количеством связей между ними, и реализация каждого модуля с использованием только локальных передач данных.Подобный анализ облегчает реализацию данного алгоритма на параллельных ВС. - 15 Б первой главе диссертации исследуются формальные возможности распараллеливания некоторых методов модификации. Для этого каждый алгоритм расчленяется на связанные между собой модули - фрагменты. Рассматривается реализация этих фрагментов с использованием различного числа параллельных процессоров.Приводятся значения высоты параллельных схем, ускорения счета, загруженности процессоров, требования к объему дополнительной najyiHTH дШ, число конфликтов в памяти, возникающих при одновременном обращении нескольких процессоров к одной и той же ячейке памяти.Характеристики параллельных схем даны в сводной таблице, приведенной в Приложении. В конце первой главы из всех фрагментов алгоритмов модификации выбираются основные фрагменты, имеющие регулярную структуру, на которые приходится основная доля ( 0[у\^)/ операций каждого алгоритма. Большинство из этих фрагментов встречается в нескольких разных алгоритмах.В третьей главе показано, что почти все выделенные основные фрагменты методов модификации принадлежат классу алгоритмов Д 1 , описанному во второй главе. На основе построенных моделей конкретизируются модели Ш двух типов для отдельных фрагментов.Предполагаются также модели систолических массивов для фрагментов методов модификации, не входящих в класс AL . Показано, что большинство из рассматриваемых фрагментов реализуется на СМ с использованием ЭП одних и тех же видов.Основные результаты, второй и третьей глав опубликованы в работе [ 5" J Результаты работы докладывались на заседаниях научноисследовательских семинаров кафедры А С Ж ф-та Ш К МГУ, ШПС АН СССР и на научно-исследовательском семинаре "Архитектура Э Ш и численные методы" в О Ш АН СССР. Автор выражает глубокую благодарность своему научному руководителю профессору В.В,Воеводину за постоянное внимание, поддержку и помощь в работе.. - 17