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

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

ЕГУНОВ Виталий Алексеевич

4

РАЗРАБОТКА И ИССЛЕДОВАНИЕ АЛПАРАТУРНО - ОРИЕНТИРОВАННЫХ АЛГОРИТМОВ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ХАУОЩЦЕРА

Специальность 05.13.1б-применение вычислительной техники, ■ математического моделирования и математических методов а научных исследованиях

АВТОРЕФЕРАТ

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

ВОЛГОГРАД 1995

Работа выполнена в Волгоградском государственном техническом университете.

Научный руководитель - доктор технических наук, профессор Духнич Е.М.

Официальные оппоненты: доктор технических наук, профессор Муха С. П.

' кандидат технических наук Серов A.A.

Ведущая организация - АООТ "Волгограднефтегеофигкка"

— „Л. ,„,.,, ¿о*.

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

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

Автореферат разослан "^-^-^-'£-—1996 г.

Ученый секретарь диссертационного совета Водопьянов В.И.

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

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

Перечисленные выше задачи требуют от вычислительной сис- • теш производительности порядка 109 + 1014 операций-с плавающей запятой в секунду .' Очевидно , что традиционные универсальные ЭВМ не в состоянии обеспечить подобную'производительность . В связи с этим , поиск решений проблемы повышения производительности идет в направлении развития принципов параллельной и/или конвейерной обработки информации . Парзлле-лизация вычислений идет в основном в двух направлениях :

1. Объединение в единую вычислительную.систему нескольких процессорных элементов ( ПЭ ) , предназначенных для последовательной обработки информации .

2. Создание специализированных проблемно - ориентированных процессоров , структура которых в максимальной степени

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

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

В настоящее время существуют и коммерчески доступны параллельные и векторные суперкомпьютерные системы , позволяющие производить тысячи миллионов операций с плавающей запятой в секунду . Это Cray - 1/2/Х-МР , Cyber £05 а HEP в США , Fujitsu VP200 , Hitachi S-810/20 и НЕС SX-2 в Японии . Однако , сложные управляю©» функции в универсальных ЭВМ часто ограничивают производительность при выполнении задач обработки сигналов . Стоимость таких супер - ЭВМ лежит в пределах от 10 до 15 миллионов долларов США , что препятствует их широкому распространения .

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

числительные системы , производительность которых может несложно нараяшватъся путем увеличения числа однотипных. ПЭ .

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

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

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

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

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

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

- б -

2. Синтез и исследование алгоритмов многомерных линейных преобразований , ориентированных на аппаратурную реализацию в виде СБИС , предназначенных для решения типовых задач линейной алгебры . ■

3. Моделирование полученных алгоритмов на ЭВМ и получение основных характеристик вычислительного процесса . - .

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

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

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

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

- методы расширения области сходимости алгоритмов быстро- -го преобразования Хаусхолдера , позволяющие синтезировать т -мерные алгоритмы быстрого преобразования Хаусхолдера , сходящиеся на полном наборе входных данных ;

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

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

Практическая ценность. Разработаны алгоритмы решения ключевых задач линейной алгебры , ориентированные на аппаратурную реализацию в виде специализированных СБИС предназначенных для использования в системах с матричной архитектурой . Использование разработанных алгоритмов позволит в 1,5 - 2 ра- . за уменьшить время решения задач , одновременно в 1,5 - 3 раза. снизить аппаратурные затраты и существенно ( на порядок и более ) увеличить производительность С число задач , решаемых

- ? -

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

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

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

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

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

Структура и объем работы. Диссертация состоит из введения , четырех разделов , заключения , списка использованных источников , содержащего 60 наименований , и приложения . Ра- . бота изложена на 128 страницах основного текста , 56 страницах рисунков и таблиц , 5 страницах списка использованных источников , 11 страницах приложения .

СОДЕРЖАЩЕ РАБОТЫ

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

Во втором разделе производится классификация задач линей-

- я -

ной ачгч'Орц и г.ыоирается круг задач , наиболее часто используемый л областях ЦОС , обработке ¡«сбрдхенш! и т.д. Это задачи решения систем линейных алгебраических уравноний (СЯДУ), поиска собственных чисел и системы собственных векторов и 1107 иска сингулярного разложения ,.

Для создания внсокоэ^Фектшшх вычислительных средств , - предназначенных для раагения этих задач , необходимо ьирабо-тать единый унифицированный подход . позволяющий решать любую иа шкеперечислешш задач . выработка такого подхода позволит создан* унифицировании« ьычислитольнк"? средства , которые могут омть использованы для решения любой задачи из заданного опектра .

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

В качестве Сагового матричного преобразования предложено использовать ОК - разложение . Кроме того , что ЦК - разложение является универсальным ь перечисленном классе задач , необходимо отметить , что для решения проблемы собственных значений и поиска сингулярного разложения матриц . обдего вида СИ? - разложение является наиболее быстрым и удобным . Конечно , для решения систем линейных алгебраических уравнений существует ряд других более быстрых методов ( например , метод Гаусса ) , которые , однако , не могут претендовать на универсальность и не могут Сыть использованы для решения других задач линейной алгебры . '

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

Проведен анализ ограничений . накладываемых на вычислительную систему технологией СБИС . На основе этого анализа осуществлен выбор основных критериев сравнения алгоритмов ре-' иения ■ задач линейной алгебры с точки зрения их аппаратурной реализации в виде СБИС . Зги критерии разделены на две группы : критерии , определяющие принципиальную возможность реализации данного алгоритма в виде специализированного процес-

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

Для суаествоЕания принципиальной возможности реализации какого - либо алгоритма в гиде специализированного процессора , алгоритм должен удовлетворять следуют требованиям :

- алгоритм должен обладать гарантированной точностью'и устойчивость» решения при минимальной погрешности вычислений ;

- гарантированная сходимость метода аа заранее известное количество шагов для любого набора входных данных ;

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

Для минимизации времени вычислений и уменьшения сложности реолигашш в виде СВИС алгоритм должен удовлетворять следующим требованиям :

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

- алгоритм должен иметь минимальное количество точек ввода-вывода через граничные вершины своего графа ;

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

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

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

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

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

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

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

У=0(5)*0(Т) .

Здесь

V - аппаратурно - временная сложность ; " •

0(3) - мера аппаратурной сложности реализации алгоритма ;

ОСТ) - мера временной сложности алгоритма ( времени вычислений ) .

Так как меры аппаратурной и временной сложности являются характеристиками алгоритмов , имеющими несколько разную природу , определять их будем в сравнении нескольких алгоритмов по следующей методике . Пусть имеется п алгоритмов &1 аг , ■ ■ ■ , ал •

Каждый из этих алгоритмов имеет сложность М Мг'". ... , Мп ( аппаратурную или временную ) . Тогда меру сложности 2 -'го алгоритма будем определять следующим образом :

М,

0(М1)=- .

П ' Z Мз >1

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

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

Под ДЛИ - реализацией линейного оператора А * понимается разложение исходного линейного оператора в бесконечное произ-

- и -

ведение матриц Г)

А= П .

1=0

п

таких , что произведение П 81 стремится к исходной мат-

ЬО

рице А при п -* ® . Элементы матриц 84-выбираются таким обра-■зом , что умножение на очередную матрицу ДЛИ сводится к последовательности сложений и сдвигов , то есть элементы матриц Е\ выбираются равными нулю или целой степени основания системы счисления ( в двоичной системе - целой степени двух ) Это приводит к понижению аппаратур®) - временной сложности, алгоритма , реализованного на базе этого алгоритма , откуда следует невысокая стоимость этих устройств .

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

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

Как видно , рассматриваемые преобразования имеют однонаправленные регулярные графы , из чего вытекает возможность реализации данных преобразований в,виде систолических вычислительных модулей . Отсутствие циклов на графах алгоритмов предполагает отсутствие необходимости введения в вычислительную структуру дополнительных устройств памяти , необходимых для синхронизации вычислительного процесса Кроме того , так как матрицы 31 имеют одинаковую структуру , то алгоритм ДЛП состоит из п операций одинаковой сложности . Таким образом , дискретное линейное преобразование обладает прекрасной конве-йеризуемостью , причем ступени конвейера в ходе вычислитель-

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

п

вариант умножения на оператор.П В4 , чем на оператор А , так

1=0 - ■ как при заполненном конвейере решение на выходе ДЛП - преобразователя будет появляться в п.рзз чаще . Производительность вычислительного устройства , реализованного на базе алгоритма ДЛП , можно несложно наращивать С до пикового значения ) путем увеличения числа вычислительных модулей .

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

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

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

Было Еыделено три этапа синтеза алгоритмов ДЛП .

1. Определение вида матриц - сомножителей , которыми определяются матрицы линейного преобразования .

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

В предыдущем разделе была показана целесообразность выбора в качестве унифицированного базового матричного преобразо-

вания метода отражения Хаусхолдера .

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

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

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

2. Вторим этапом синтеза ДЛЯ - алгоритмов был выделен синтез законов формирования множеств {и;операторов ДЛП .

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

аи=?('(«к>) .

где

а^ - о -ый элемент 1-ой строки матрицы отражения ; «к - к - ый элемент вектора отражения .

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

где

а - основание системы счисления ,

к - целое число .

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

3. Третьим этапом синтеза ДЛП - алгоритмов является разработка структурных способов реализации итераций ДЛП .

.На данном этапе рассматривается возможность и пути использования алгоритма для реализации его в виде параллельной систолической структуры , определяется степень его внутреннего параллелизма , а также изучается возможность' построения вычислительных систем размерности п на базе вычислительных блоков размерности m , причем min , то есть блочное соединение процессорных элементов для увеличения размерности решаемой задачи • _

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

k=l,m ;

у

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

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

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

В процессе плоского ДЛП - отражения величина направляющего угла равна

«^»агс^г-1) ,

где

1 - номер итерации ,

и процесс ДЛП - отражения сходится , если

Здесь 9 - угол между отражаемым вектором и осью ОХ . В случае многомерного отражения ситуация меняется . Величина направляющего угла в данном случае равна

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

Ситуация сужения области сходимости является недопустимой , так как прикладные задачи ЦОС требуют решения задач линейной алгебры с размерностью пространства 10э + 104 и более. В связи с этим актуальной является задача расширения области

к

(1)=агс1е(-

)

сходимости процесса ДЛП - отражения .

Для того , чтобы сохранить область сходимости в рамках г К Кл

, необходимо предпринять дополнительные меры . Для

этого представляется две возможности : '

. 1) замедление скорости падения величины направляющего угла а(1> ;

2) введение в ДЛП - последовательность дополнительных

тг

членов , увеличивающих ее сумму до - .

1). Замедление скорости падения величины направляющего угла .

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

• 3=2,т ;

¿,кт=31еп(УкШ) ; к=1,т ;

Здесь д £ JО;13 - параметр сходимости , регулирующий скорость падения величины направляющего угла и расширяющий область сходимости до необходимых размеров . Параметр <1 - монотонно убывающая функция от размерности пространства , вид которой был определен экспериментально путем моделирования . Однако данный вариант расширения области сходимости ведет к значительному увеличению числа итераций

. к=Ш(п/с1) .

где

п - число требуемых точных двоичных .двоичных разрядов результата .

2). Введение дополнительных членов последовательности , расширяющих область сходимости процесса ДЛП - отражения .

Область сходимости процесса ДЛП - отражения можно расширить путем введения в ДЛП - последовательность дополнительных

. я

членов , увеличиваотх её сумму до - . Необходимо , чтобы эти

2

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

г « ® 1

р-ш (- - Е еп)/е0 2 п=0 1

ж

раз , мы увеличиваем сумму до - . Но , в силу случайно-

2

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

Вводится понятие вектора повторений Я={Н(1)} , который имеет п компонент (а - необходимое количество точных двоичных цифр результата) . Каждая компонента вектора повторений указывает , сколько раз надо повторять данную итерацию . Тогда , если I?-вектор повторений , алгоритм ДЛП-отражения запишется

п . {V

У=АХ~ П {( П АШ)Х) .

1=0 3=1

-Здесь

X - исходный вектор ;

У - результирующий вектор ;

А - матрица отражения ;

А(1) - матрица ДЛП-отражения на 1-ой итерации ;

¡? - вектор повторений .

Вид вектора повторений был определен экспериментально путем моделирования .■

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

п

• 1=1

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

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

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

1). Повышение скорости реализации алгоритмов ДЛП - отражения путем полной замены " длинных " операций " короткими

Полностью избавиться от необходимости выполнения " длинных " операций можно , заменив операцию умножения на каждой итерации двумя операциями сдвига и одним сложением . Для этого в качестве размерности пространства выбираются величины п\=21+1 , где 1=0,1,2,... Полученный алгоритм ДЛП - отражения выглядит следующим образом :

у^'-у^'/г1

J-l.ni

3=2. п

Р-1.Ш

1=о. к

ус0)=х

/

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

П-1

мации равен к= П - ,где 1 = ¡ойгСго-Ш т ~ размерность

1=0 21

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

2) Повышение скорости реализации алгоритмов ДЛП - отражения путем уменьшения числа итераций .

Процесс ДЛП - отражения на каждой итерации можно представить как процесс отражения с вектором отражения , который является приближением точного вектора отражения . Число итераций , необходимое для достижения требуемой точности решения , заииеит от точности приближения вектора отражения . Во всех рассмотренных выше алгоритмах ДЛП - отражения при Формировании вектора отражения на итерации использовались только знаки истинного .вектора отражения и ке принимались во внимание модули значений его элементов , В данном алгоритме_оило предложено для погмаения точности оценки вектора отражения на итерации учитывать не только знаки элементов истинного вектора отражения ,.но и их двоичные порядки

witll'=tiil)*orcl(yitl,+-sipi(Vitn)*s) ; u)j.(i)^JinAord(Vj (1)) .

. tJ<i)«üi|fn(y1tl)) j-Й.М ; .

^десь s - либое приближение модуля отражаемого Вектора,.

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

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

Было проведено моделирование алгоритма направленного ДЛП - отражения с целью определить оптимальное приближение

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

Полученные алгоритмы БДЛП - отражения и направленного ДЛП - отражения имеют меньшую операционную сложность , временную сложность и большую проиаводительность вычислительного кон*5?"

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

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

Наименьшую операционную сложность при решении указанных задач имеет алгоритм направленного ДЛИ - отражения , наименьшее время получения решения - алгоритмы ЕДЛП - отражения "и направленного ДЛП - отражения .

При проведении сравнения алгоритмов по параметру произво-, дительности вычислительного конвейера был получен результат , в соответствии с которым производительность вычислительного конвейера алгоритма БДЛП - отражения в среднем на порядок превосходит'производительность вычислительного конвейера всех •остальных ДЛП - схем и на два порядка превосходит классическое преобразование Хаусхолдера .

В связи с этим можно сделать выеод , что наиболее перс-

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

В этом же разделе рассмотрен алгоритм разбиения задач на подзадачи с понижением размерности пространства при использовании алгоритмов ДЛП-отражения - алгоритм блочного ДЛП - отражения .

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

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

- время реализации Ь арифметической операции , соответствующей данному узлу графа зависимости ;

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

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

- для реализации короткой операции требуется одна единица аппаратуры ;

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

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

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

1

Е Б;) , 3=1

где

3 - аппаратурная сложность реализации алгоритма ;

SJ - количество аппаратуры , необходимое для реализации арифметической операции , соответствующей 3 - му узлу ГР ;

1 - число узлов ГР алгоритма .

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

Наилучшее значение алпаратурно - временной сложности имеют алгоритмы БДЛП - отражения и направленного ДЛП - отражения . При фактическом равенстве данного параметра алгоритмы имеют различные аппаратурные и временные характеристики :

- алгоритм БДЛП - отражения является более быстрым ;

- алгоритм направленного ДЛП - отражения имеет более простую аппаратурную реализацию .

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

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

В приложении приведены документы , подтверждающее исполь-

- Е 4 -

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

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

В диссертационной работе разработаны и исследованы алгоритмы . предназначенные для реализации быстрого' преобразования Хаусхолдера к ориентированные на аппаратурную реализацию в виде СБИС . Проведена оценка-основных характеристик аппаратурной и программной реализации разработанных алгоритмов .

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

Главные теоретические и практические результаты , полученные е работе , можно сформулировать следующим образом :

1)осуществлен выбор количественных и качественных критериев оценки и сравнения аппаратурно - ориентированных алгоритмов ;

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

ния задач по сравнению с программной реализацией известных методов на традиционных универсальных ЭВМ ;

3) предложены методы расширения области сходтости процесса ДЛП - отражения , позволяющие синтезировать ш - мерные алгоритмы быстрого преобразования Хаусхолдера , сходящиеся на полном наборе входных данных ;

4)предложены методы повышения скорости реализации алгоритмов ДЛП - отражения , позволяющие на порядок и выше повысить скорость реализации указанных алгоритмов ;

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

6)проведена оценка и сравнение аппаратурно - временной сложности разработанных алгоритмов при их аппаратурной реализации в виде СБИС .

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

1.Духнич Е.И. , Егунов В.А. Алгоритмы многомерных отражений , ориентированные на систолическую реатизацию/ЛТроектиро-вание ЭВМ : Межвузовский сборник научных трудов. - Рязань : РГРА ; 1994 . - С.57-63.

2.Духнич Е.И.., Егунов В.А. Устройство для вычисления мо- . дуля т - мерного вектора : заявка на изобретение N 95104370

( решение о Еыдаче патента РФ от 18.01.96 г. ).

3.Духнич Е.И. , Егунов В.А. Расширение области сходимости процесса ДЛП - отражения /Волгоград.гос.техн.ун-т. -Волгоград, 1995. - 7 с. - Деп.в ВИНИТИ.' N 2529 - В95.

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

5. Егунов В.А. Сходимость процесса ДЛП - отражения / Волгоград, гос. техн.ун-т. -Волгоград, 1995. - 8 с. - Деп.в ВИНИТИ. N 2505 - В95.

Личный вклад автора диссертации в опубликованных работах •

состоит в следующем:

е работе /1/ предложены пути расширения области сходимости процесса ДЛП - отражения , в работе /2/ предложена аппаратурная реализация алгоритма БДЛП - отражения , е работе /3/ проанализирована методика расширения области сходимости процесса ДЛП - отражения , в работе /4/ выделены основные требования , предъявляемые к аппаратурно - ориентированным алгоритмам . •