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

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

ДЕРЕВЕНСКОВ Сергей Олегович .

РАЗРАБОТКА И ИССЛЕДОВАНЙЕ КЛАССА АППАРАТУРНО-ОРИЕНТИРОВАННЫХ АЛГОРИТМОВ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ .АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

Специальность 05.13.16 - применение вычислительной техники,

математического моделирования и математических методов в научных исследованиях

АВТОРЕФЕРАТ

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

ВОЛГОГРАД. 1995

Работа выполнена в ческом унизерситс-те.

Волгоградском, государственном техни-

доктор технических наук , профессор Духнич'Е.И.

доктор технических* наук , .профессор Глушань В.М. ■

кандидат технических наук", доцент Дворянкин A.M. .

АЮТ "Волгограднефтегеофизика"

Защита состоится " 1995 г. в "/У^часов

на заседании диссертационного совета К 063.76.05 Волгоградского государственного технического университета по адресу: .400006 , г.Волгоград , проспект Ленина-, 28 , ауд.209.

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан "_" _ 1995 г.

Научный руководитель Официальные оппоненты:

Ведущая организация -

Ученый секретарь диссертационного совета

Водопьянов В.И.

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

Актуальность темы. Репение систем линейных апгебраичес-. них.уравнений (СЛАУ), особенно СЛАУ с патрицами большой размерности , принадлежит к тому кругу задач , которые , с одной стороны , являются чрезвычайно важными как в области научных вычислений , так и при реиении значительного числа практических задач . а с другой стороны, имеют очень высокую операционную сложность "(порядка N ? операций с плавающей запятой , где N - размерность матрицы СЛАУ), При этом целый ряд прикладных задач , в частности задачи акустики , гидро-и радиолокации , аэродинамики . автоматического управления и ■ регулирования . излагают жесткие ограничения на допустимое время вычислений . требуя их выполнения в режиме "реального времени". Кроме того, существует большое количество науч- . но-практических задач, которые не требуют вычислений в режиме "реального времени", но объем, вычислений для их решения -настолько велик , что требует от вычислительной'системы необычайно высокой производительности.. К числу таких задач-, например , можно отнести задачи численного моделирования физических процессов , в основе которого лежит решение дифференциальных уравнений и систем уравнений большого порядка , своди! их к решению СЛАУ.

В сзязи с этим , задача разработки вычислительных систем • и алгоритмов для решения СЛАУ- является одним из наиболее привлекательных и практически значимых направлений научных исследований как в нашей стране , так и за рубежом.

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

процессорных элементов (ПЭ) . образующим матрицу ПЭ (процессорную сеть) и в ходе обработки передаются от одного ПЗ ¡. другому. При этом задача решается в процессе "прокачивания"

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

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

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

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

Одним из путей решения этой проблемы является использование в вычислительных системах с матричной архитектурой специализированных СБИС , . ориентированных на решение одной задачи , в частности на решение СЛАУ. Это позволит крайне упростить устройство управления такой системой , обеспечить построение ПЭ на основе матричной архитектуры , то есть использования распараллеливания и конвейеризации вычислитель. ного процесса на уровне отдельных операций и за счет этого резко увеличить реальное значение производительности. При ' этом внутренняя структура специализированных СБИС однозначно определяется используемым вычислительным алгоритмом.

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

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

Достижение поставленной цели требует решения следую:." основных задач теоретического и прикладного характера;

1. Анализ возможностей аппаратурной реализации в виде ■ СБИС классических вычислительных• алгоритмов решения СЛАУ по методам Гаусса , Гаусса-Жордана и Гивенса.

2. Разработка класса аппаратурно-ориентированных алгоритмов решения СЛАУ и обращения матриц на основе соответствующих классических мате' этических методов.

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

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

Научная новизна работы. В диссертации разработаны и вынесены на защиту следующие основные положения:

аппаратурно-ориентированные алгоритмы выполнения триан-

гуляции матрица {прямого хода рс^еник СЛАУ) по методам Гауе- . са. Гаусса-Йордана для вещественных и комплексных матриц;

аппаратурно-ориентированные алгоритмы решения СЛАУ с треугольной матрицей (обратного хода решения СЛАУ);

аппаратурно-ориенгйрованные алгоритмы обращения вещественных и комплексных матриц по методам Гаусса и Гаусса-Кор-дана;

аппаратурно-ориентированный алгоритм рспения СЛАУ.по методу Гивонса; •

методика сравнения основных количественных«- качественных характеристик аппаратфно-ориентированных алгоритмов решения СЛАУ.

Практическая ценность. Разработаны алгоритмы решения СЛАУ с вещественной и комплексной матрицей и алгоритмы обращения вещественных и комплексных матриц , ориентированные на аппаратурную реализацию на спсциализированых СБИС , предназначенных для использования в системах с матричной архитектурой. Использование разработанных алгоритмов позволит' существенно (в 1.5-3 раза) снизить время решения СЛАУ и одновременно во столько же раз уменьшить необходимые, аппаратурные затраты при их реализации на СБИС по сравнению с аппаратурной реализацией классических вычислительных алгоритмов при прочих равных условиях и более чем на порядок уменьшить время решения названных задач по сравнению с их решением на универс? •'ьных ЭВМ при сопоставимых аппаратурных затратах.

Реализация результатов работы. Результаты работы были внедрены в ОКР по создан® платы-акселератора ПЭВМ 1ВМ РС АТ ' по заказу АООТ "Волгограднефтегеофизика".

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

Апробация работы. Результаты диссертации докладывались и обсуждались на I межвузовской научно-практической конференции студентов и молодых ученых Волгоградской области (Волгоград , 1994) , Волкской Городской научно-практической конференции (Волжский , 1995) . а также на ежегодных научных конференциях ВолгГТУ (Волгоград . 1993- 1995).

Публикации. По материалам диссертации опубликовано 6 печатных работ и получено решение о выдаче патента РФ на изобретение.

Структура и объем работы. Диссертация состоит из введения , • четырех разделов . заключения , списка использованных источников , содержащего 63 наименованияи приложения. Работа изложена на 148 страницах основного текста . 56 страницах . рисунков и таблиц 5 страницах списка использованных источников , 8,страницах приложения.

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

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

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

- алгоритм должен иметь возможность разбиения на оптимальное количество подалгоритмов (макроопераций) , которые возможно выполнять параллельно и на конвейере.

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

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

На процессорном уровне аппаратурно-ориентирозанный алгоритм должен удовлетворять следующим требованиям:

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

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

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

- алгоритм должен иметь ограниченное число операций ввода/вывода.

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

р - производительность устройства на операции . • то есть число операций, закрепленных за вершиной, выполняемых устройством , реализующим эти операции , в единицу времени;

I - время выполнения на устройстве операций , закрепленных за вершиной;

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

Полученный таким образом граф назван графом вычислений алгоритма (ГВ). Для ГВ введены понятия пока.ателей производительности , быстродействия / сложности аппаратурной реализации ГВ , конвейерного такта ГВ , определяемые через показатели р.иэ его вершин. С использованием этих понятий сформулирован основной критерий оценки аппаратурно-ориентированных алгоритмов'- на языке теории графов:

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

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

В зависимости от того . какого "уровня операция алгоритма закрепляется за вершиной ГВ (ГЗ) , для одного алгоритма можно выделить ГВ (ГЗ) разных уровней. При этом каждую вершину такого графа можно рассматривать как некоторый подграф , вершинами которого являются операции более низкого уровня'. Обосновано . что для наиболее корректного сравнения аппара-турно-ориентированных алгоритмов следует рассматривать ГВ (ГЗ) алгоритмов на уровне коротких операций , а в качестве единиц измерения показателей рД.э некоторого ГВ использовать показатели рк, ^, ГВ короткой операции. Под короткой операцией понимается операция , выполняемая над операндами как над единым целым , которая на СБИС не может быть выполнена как последовательность других , более мелких (сложение (вычитание) , сдвиг чисел , представленных в формате с фиксированной запятой . и ряд других подобных операций). В противном случае операция является длинной.

В этом же разделе обосновано использование дискретных линейных преобразований (ДЛП) как аппаратурно-ориентирован-ных алгоритмов решения СЛАУ.

В процессе решения СЛАУ по методам Гаусса . Гаусса-Жор-дана и Гивенса на каждом шаге алгоритма над исходной матрицей А и вектором свободных членов В осуществляется итераци-

онная. процедура :

• Р, АС:! .

+ Р. В(:) , 1 » 1ГЫ-1

где А1" и А(преобразованные матрицы исходной" сис- ■ темы соответственно "на Ьми (1+1)-м этапе алгоритма . В'! ] и В1: 5 - преобразованные векторы-голбцы сво-богных членов исходной системы соответственно на .1-й и (1+1) -м этапе алгоритма , Р, - матрица преобразования на. 1-м этапе алгоритма , N - размерность исходной матрицы СЛАУ. ' Подобная процедура осуществляется и при выполнении обратного хода реиения СЛАУ. При этом матрицы Р, выбираются таким образом, чтобы матрица А1ь' имела более простой вид , чем А .

• В силу этого для рассматриваемых методов , определяющим. збсноя . члиявщии на эффективность использования того или иного алгоритма решения СЛАУ , является алгоритм обработки столбца матрицы. Поэтому , операция умножения матрицы преобразования на вектор-столбец оказывает решающее влияние ' на ■ эффективность выполнения алгоритм решения СЛАУ в целом.

ДЛП-алгоритмы предусматривают представление матрицы преобразования Р, на некоторм этапе алгоритма в виде :

с\з

Р, = П Р(1)..

Матрицы Р!1; при этом преимущественно имеют в качестве своих элементов либо нули , либо степени основания системы счисления. Умножение вектора на матрицу преобразования-Р, может быть при этом представлено в виде итерационной процедуры:

+ 1 - , 3 - « .

ГД6 - X , Ую Р X , X - исходный вектор-столбец.

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

-и -

чем больше число итераций.

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

1)' в отличие от классических алгоритмов , ДЛП - алгоритмы не требуют предварительного вычисления матрицы преобразования;

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

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

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

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

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

1) наличие в алгоритмах значительного числа динамических связей между операциями , пропорционального размерности обрабатываемого вектора , из-за необходимости выполнения операции перестановки строк в ходе выполнения этих алгоритмов;

2) наличие в алгоритме значительного числа длинных операций . также пропорционального размерности обрабатываемого

вектора;

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

Предложен ДЛП-алгоритм обработки столбца матрицы на этапе алгоритма Гаусса (или Гаусса-Жордана):

X,,

Н, X,

где X. и X.,; - обрабатываемый вектор-стсг^ец матрицы соответственно на j-й и (j+D-й итерациях ,

1 0 0 . . . 0 0

Г -J

-z., 2 ' 1 " 0 . . . 0 ' 0

' f, -J

Hj - -2c-2 " 0 1 . . . 0 0

f.v-i -j

0 0 . . . 0 1

zk; » sgn(x:.) sgn(x, , k = i.N-1

'X: , и

- / 1 .

а = {

4 -1 , если а < 0 , - разность порядков к-го исключаемого поддиаго-

нального элемента главного столбца обрабатываемой матрицы и диагонального элемента этого столбца ,

- элементы главного столбца обрабатываемой матрицы на ,3-й итерации . если о£ > О

j = 0. п , .

п - разрядность мантисс операндов ", N - размерность обрабатываемого вектора.

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

рационная сложность классического алгоритма. Анализ ГЗ ДПП-алгор.итма как на уровне итераций , так и на уровне отдельных операций , показывает . что ГЗ алгоритма имеет' только локальные статические связи. ГЗ одной итерации алгоритма имеет О(N3 непересекающихся путей равной длины (И - размерность обрабатываемого столбца) . при этом каждый путь включает не более трех коротких операций. При реализации на СБИС ото позволяет использовать параллелизм алгоритма на уровне коротких операций , а также организовать конвейер с величи-но'"' такта . равной времени выполнения короткой операции. Вторым преимуществом предложенного алгоритма перед классическим является возможность практически полностью распараллелить операции обработки главного и зависимого столбцов.

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

+ ; - Н. X; , -Хо - Р О X ,

где X, и X.+ ; - обрабатываемый вектор-столбец матрицы * соответственно на а-й и (¿+1)-й итерациях ,

Хз - обрабатываемый вектор столбец матрицы на нулевой итерации , X - исходный вектор-столбец ,

ЗЯП(Х1) 5§п(х2) 5^(Х:3) зеп(х^)

О 1 0 . . . О

0 0 1 . . .' о

1 0 0 0

0 9 . . 0

О' 0 'г 2 0

-го, 2

-2

С К

„,г

■з

• о

0 о

1 о

О 1

о о

. о о .0 о . о о

1

г.;, = ЗЕП(Х13) б§п(х(К + 1!,) . к - 1.М-1 , х . и х:.,:: - элемента главного столбца обрабатываемой матрицы на ;}-й итерации ,

■ х, . х:.....х[; . исходные элементы главного

столбца обрабатываемой матрицы, / 1 , если а ) О з^ а « <

1 -1 , если й < 0 , ■ Г}. - разность порядков диагонального элемента главного столбца обрабатываемой матрицы и к-го исключаемого поддиагонального элементы этого столбца перед начальной итерацией,

3 - сСп ,

п-- разрядность .мантисс операндов N - размерность обрабатываемого вектора.

Этот алгоритм отличается от предыдущего тем , что перед каждым этапом исключения все столбцы матрицы системы , обрабатываемой на этом этапе . умножаются на матрицу Б. Фактически это означает сложение строки , содержащей ведущий элемент исключения , со всеми поддиагональными строками . умноженными на -1. При этом ГЗ рассматриваемой операции полностью удовлетворяет требованиям . предъявляемым к ГЗ аппа-

Н

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

На основе предложенных ДЛП-алгоритмов обработки столбца .матрицы были, разработаны ДЯП-алгоритш резения СЛАУ и обращения матриц по методам Гаусса и'Гаусса-Яордана для вещественных и комплексных матриц , -свободные от большинства недостатков , свойственных классическим алгоритмам и препятствующим их эффективной аппаратурной реализации , и , в то же время , обладающие в целом , лучшими показателями операционной сложности. . .

В четвертом разделе проведен анализ возможностей аппаратурной реализации классического алгоритма решения СЛАУ по методу-вращения Гизенса выделены основные недостатки , препятствующие его эффективной реализации на СБИС: ■

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

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

3) невозможность параллельной обработки главного и зависимого столбцов на каждом этапе алгоритма.

В- качестве альтернативы классическому алгоритму предложен ДПЛ-алгоритм многопер :ого вращения вектора:

+ 1 * Н^. Х^ ,

где Хо - вектор до вращения .

X; - вектор после- вращения ,

Н} - К; Н1К^ ,

«1^(1.-1,к."1,к."2,'... ,к"(К~г)) . К^сПайС^-К^к/2.....V"'15) •

к) ' соэ Д<р . -Д<р - аг^ 2'^ , -

н, =

1 Ъ\, 2 го<2 ^ 2(1». 11.!

-г\з2 1 -гг, г2,2 ь) - '1 ... О

-Щ

)2"' "zl;z(^'-l)j2 —^ к - П] 2 23 ... 1.

гк. * зеп(х1з) зеп(х(к,'. ^ ) К « 1*.N-1 . . х,, и х('г," элементы главного столбца обрабатываемой матрицы на 3-й йеерации , 1 , если а ) О

есл: а < О

эеп <* = /

4 -1

0.1 .

1 - количество итераций ,

N - размерность матрицы , обрабатываемой на 1-м этапе алгоритма.

ДЛП-алгоритм многомерного вращения вектора содержит ограниченное количество только коротких операций, имеет операционную сложность, меньшую, чем операционная сложность классического алгоритма, позволяет почти полностью совместить во времени операции обработки главного и зависимых столбцов матрицы при решении СЛАУ и, в то же время, свободен от главного недостатка классического алгоритма : ДЛП-алгоритм осуществляет вращение мкпгомерного вектора. как одну макроопе^ацию, что позволяет одновременно обрабатывать все элементы вектора.

• На основе ДЛП-алгоритма многомерного вращения вектора разработан ДЛП-алгоритм решения СЛАУ по методу Гивенса, свободный от основных недостатков классического алгоритма , препятствующих его эффективной аппаратурной реализации , и в то же время имеющий меньшую операционную сложность , а также показана возможность использования ДЛП-алгоритма как' для решения совместных СЛАУ по методу Гивенса , так и несовместных СЛАУ по методу наименьших квадратов.

Пятый раздел посвящен сравнительному анализу основных количественных показателей вариантов ГВ классических алгоритмов решения СЛАУ и разработанных ДЛП-алгоритмов при аппаратурной реализации названных алгоритмов на СБИС.

• Проведен анализ вариантов ГВ алгоритмов решения СЛАУ системного и процессорного уровня , в результате которого

выделены три основных варианта построения ГБ алгоритмов решения СЛАУ , отличающиеся показателями производительности , быстродействия и сложности аппаратурной реализации , а также проведен сравнительный анализ их основных количественных показателей , на основе которого выделен вариант , обладающий наилучшим показателем производительности. Это вариант аппаратурной реализации алгоритмов решения СЛАУ , максимально использующий все возможности распараллеливания и конвейеризации вычислительного процесса и , как следствие . имеющий максимально возможный показатель производительности. Число задач , решаемых в единицу времени для него не зависит от размерности матрицы и равно l/tк. Для этого варианта ГВ проведен сравнительны!" анализ показателей Лиз. обеспечиваемых разработанными ДЛП-алгоритмами и соответствующими классическими алгоритмами, который показал , что аппаратурная реализация ДЛГЬалгоритмов в 1,5-3 раза позволяет уменьшить время решения задачи и одновременно в то. же число раз снизить требуемые затраты оборудования по сравнению с аппаратурной реализацией классических алгоритмов при прочих- равных условиях. При сопоставимых аппаратурных затратах увеличение быстродействия за' счет аппаратурной реализации ДЛП-алгорит-моз по сравнению с программной реализацией классических алгоритмов на универсальных ЭВМ будет , как минимум , на порядок выше.

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

В заключении обобщаются теоретические и практические результаты , полученные в диссертационной работе:

В приложении приведены документы , подтверждающие использование результатов диссертационной работы , в частности описание изобретения "Матричный спецпроцессор" авторов Дух-нича Е. И. , Деревенскова С. О. и платы-акселератора ПЭВМ 1ВМ РС АТ (авторы Деревенсков С.О. . Егунов В.А.).

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

В диссертационной работе разработан и. исследован класс аппаратурно-орие--тированных алгоритмов для решения СЛАУ с вещественной.и комплексной матрицей и обращения матриц на основе дискретных линейных преобразований.

Основной научный результат состоит в разработке класса аппаратурно-ориентированных алгоритмов решЬния СЛАУ и. обращения. патриц на основе известных -классических методов с учетом специфических требований и ограничение , /¿аюзадываешх на такие алгоритмы технологией производства СБИС. Предложенные алгоритмы полностью удовлетворяют .этим требованиям и позволяют существенно уменьшить время решения и снизить ап-' паратурные затраты при аппаратурной реализации процесса решения, прикладных задач , основное'математическое содержание коуорых составляет решение СЛАУ и обращение матриц.

В работе получены следующие основные теоретические и практические результаты:

1>. на основе анализа ограничений , накладываемых на вычислитель' 7» систему , осуществлен выбор количественных и качественных критериев оценки и сравнения аппаратурно-ориентированных алгоритмов с использованием математического аппарата теории графов и предложена методика сравнения алгоритмов на основе этих характеристик;

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

3) разработан класс ДПП-алгоритмоз решения СЛАУ и обращения матриц по методам-Гаусса и Гаусса-Кордана. для- вещественных и комплексных матриц , имеющих по сравнению с классическими алгоритмами меньшую операционную сложность , удовлетворяющих основным требованиям . предъявляемым к аппара-турно-ориентированным алгоритмам технологией производства ■ СБИС . и позволяющих при одинаковой.производительности (количестве задач , решаемых в единицу времени) в 1,5-3 раза уменьшить время решения задачи и одновременно во столько же оаз снизить аппаратурные затраты по сравнению с классическими

алгоритмами при их аппаратурной реализации на СБИС,, и значительно (более чем на порядок) сократить время решения задачи по сравнению с универсальными ЭВМ при сопоставимых аппаратурных затратах;

4). разработан ДЛП-алгоритм многомерного вращения вектора для решения СЛАУ с вещественной матрицей , который также удовлетворяет основным требованиям . предъявляемым к аппара-турно-ориентированнш алгоритмам и позволяет при одинаковой производительности в 2,5-3 раза уменьшить время решения и аппаратурные затраты по сравнению с классическими алгоритмами при их аппаратурной реализации на СБИС;

5) на основе предложенной# методики сравнения основных количественных и качественных характеристик аппаратурно-ори-ентированных алгоритмов проведен сравнительный анализ вариантов аппаратурной реализации предложенных ДЛП-алгоритмов и выработаны основные рекомендации по их применению в различных практических областях.

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

1. Духнич Е. И. , Деревенское С.О. ДЛП-алгоритмы многомерных вращений для СВИС реализации //Многопроцессорные вычислительные структуры: Междуведомственный тематический научный сборник. - Таганрог: ТРТИ .. 1995 . вып. 15-16 .- с. 25-27.

2. Духнич Е.И. , Деревенское С.О. Матричный спецпроцессор : заявка на изобретение N 94030340 (решение о выдаче патента РФ от 30.10.95).

3. Деревенское С.О. , Егунов В.А. Аппаратно-программные методы повышения производительности ЭВМ // Тезисы докладов I межвузовской научно-практической конференции студентов. и молодых ученых Волгоградской области. Выпуск "Новые промышленные техника и технологии." Компьютерное обеспечение и компьютерные технологии"/ВолгГТУ. - Волгоград : Перемена , 1994.-с. 168-170.

4. Деревенское С.О. Аппаратурно-ориентированные ДПП-ал-горитмы Ш-разлохения для решения СЛАУ с комплексной матрицей/Волгоград, гос. техн. ун-т. -Волгоград, 1995. - 7 с. - Деп. в ВИНИТИ. N В95.

5. Деревенсков С.О.Алпаратурно- ориентированные алгоритмы Ш-разложения вещественных матриц для решения СЛАУ /Волгоград. гос. техн. ун-т.-Волгоград. 1995.-8 С; - Деп. в ВИНИТИ. N 2446 - В95. . .

6. Деревенсков С.О. Быстрый ДЛП-алгоритм многомерного, вращения вектора /Волгоград, гос. техн.ун-т.-Волгоград. 1995. - 4с. - Дег.. в ВИНИТИ. N 2442 - В95. •

Личный вклад автора диссертации в. опубликованных работах состоит в следующем: . ..

в работе /1/ предложен ДЛП-алгоритм' многомерного вращения вектора , в работе /2/ разработаны режимы 2 и 3 работы матричного спецпроцессора на основе ДЛП-алгоритмов прямого и обратного хода решения СЛАУ по методам Гаусса и Гаусса-Жор-дана , в работе / 3 /"выделены основные требования , предъявляемые к аппаратурно-ориентированным алгоритмам решения задач линейной алгебры.

Деревенсков Сергей Олегович

Автореферат диссертации на соискание ученой степени кандидата технических наук

Подписано в печать 17; 11.95 г.- Заказ N 624. Тираж' 100 ¡экз. Формат 60 х 84 1/16. Усл. - печ.л. 1.0. Бумага писчая. Печать офсетная. Типография "Политехник" Волгоградского государственного технического университета . Волгоград - 66 , ул.Советская .35