Введение к работе
. Актуальность темы. Реігение задач линейной алгебры , таких как реиение систем линейных алгебраических уравнений (СЛАУ) , поиск собственных чисел и системы собственных векторов матриц , сингулярное разложение , обращение матриц , вычисление определителей и другие , относится к кругу задач , являющихся чрезвычайно важными как в области научных вычислений , так и при решении огромного числа прикладных проблем . Данные задачи , с одной стороны , имеют очень высокую операционную сложность ( порядка т3 операций с плавающей запятой , где m -размерность обрабатываемой матрицы ) , с другой стороны , целый ряд прикладных проблем % в частности задачи акустики , гидро- и-радиолокации , аэродинамики , автоматического управ- " ления и регулирования , налагают жесткие требования на предельно допустимое время вычисления , часто требуя их выполнения в режиме " реального " времени . Кроме того , существует целый ряд проблем , не требующих решения в режиме " реального " времени , ' но объем вычислений в которых очень велик . В основном , это задачи геофизического , геодезического характера , задачи геологоразведки и другие . Для, них характерно предварительное накопление огромных объемов информации с последующей ее обработкой . Для рещения данных задач также необходимо иметь вычислительные системы с очень высокой производительностью .
Перечисленные выше задачи требуют от вычислительной сие- темы производительности порядка Ш9 * 1014 операций-с плавающей запятой в секунду .' Очевидно , что традиционные универсальные ЭВМ не в состоянии обеспечить подобную'производительность . В связи с этим , поиск решений проблемы повышения производительности идет в направлении развития принципов параллельной и/или конвейерной обработки информации . Паралле-лизация вычислений идет в основном в двух направлениях :
-
Объединение в единую вычислительную.систему нескольких процессорных элементов ( ПЭ ) , предназначенных для последовательной обработки информации .
-
Создание специализированных проблемно - ориентированных процессоров , структура которых в максимальной степени
учитывает структуру решаемых задач , и , кроме того ,'производится..по возможности наиболее полная замена программных вычислительных средств аппаратными , что приводит к повышению быстродействия при решении конкретных задач и к увеличению производительности вычислительной системы в целом .
При объединении в единую систему нескольких параллельно работающих ПЭ общего назначения возникают проблемы распараллеливания решаемых задач , распределения ресурсов , коммутации , взаимодействия , разрешения конфликтных ситуаций и множество других . С увеличением степени распараллеливания дачные проблемы усложняются и становятся трудно разрешимыми '. Это приводит к неэффективному использованию параллельных средств вычислительной техники , к уменьшению коэффициента загрузки оборудования и. к заметному снижению производительности по отношению к номинальному ( пиковому ) значению .
В настоящее время существуют и коммерчески доступны параллельные и векторные суперкомпьютерные системы , позволявшие производить тысячи миллионов операций с плавающей запятой в секунду . Это Cray - 1/2/Х-МР , Cyber 205 и HEP в США , Fujitsu VP200 , Hitachi S-810/20 и НЕС SX-2 в Японии . Однако , сложные управляющие функции в универсальных ЭВМ часто ограничивают производительность при выполнении задач обработки сигналов . Стоимость таких супер - ЭВМ лежит в пределах от 10 до 15 миллионов долларов США , что препятствует их широкому распространения .
Другим перспективным направлением повышения производительности вычислительных систем является"создание проблемно -ориентированных процессоров . Использование подобных специализированных процессоров позволяет строить наиболее эффективные параллельные вычислительные системы . Кроме того ,' все более усиливающийся интерес к проблеме создания проблемно -ориентированных процессоров обусловлен достижениями в области технологии сверхбольших интегральных схем ( СБИС ) , которая в настоящее время позволяет создавать быстродействующие СБИС с высокой плотностью компоновки элементов . Таким образом , все более увеличивающаяся,сложность СБИС позволяет " разместить " алгоритм решения конкретной прикладной задачи в пределах одного - кристалла и создавать на их базе параллельные вы-
числительные системы , производительность которых может несложно нараяшватъся путем увеличения числа однотипных. ПЭ .
Таким образом , одним из наиболее перспективных и практически значимих направлений научных исследований в области повышения производительности вычислительных систем является разработка и создание специализированных процессоров , реализующих многомерные ЛИНЄЙНЦЄ преобразования и предназначенные для реаения задач линейной алгебры .
Однако , специфические ограничения , накладываемые технологией производства СБИС выдвигают специфические требования к вычислительным алгоритмам , ориентированным на аппаратурную реализацию . Вычислительные алгоритмы решения задач линейной anreopu по классическим методам , разработанные для универ-. сальных ЭВМ , в абсолютном большинстве не удовлетворяют дан- . ним требованиям . В связи с этим актуальной проблемой является разработка аппаратура - ориентированных алгоритмов для их реализации на СБИС .
5 диссертационной работе показано , что з качестве базового метода для разработки алларатурно - ориентированных алгоритмов реиения задач линейной алгебры наиболее целесообразно использовать преобразование отражения Хаусхолдера . В связи, с этим , а также , учитывая тот Факт , что структура проблемно - ориентированного процессора изоморфна графу вычислений алгоритма , актуальной является задача разработки аппара-турно - ориентированного алгоритма быстрого преобразования Хаусхолдера .
Целью диссертации является создание и исследование аппаратура - ориентированных алгоритмов решения задач линейной алгебры на основе метода отражения Хаусхолдера , полностью удовлетворяющих технологии производства СБИС и позволяющих уменьшить время решения задач линейной алгебры и снизить аппаратурные затраты по сравнению с аппаратурной реализацией классического метода .
Достижение поставленной цели требует решения следующих основных задач теоретического и прикладного характера :
1. Классификация задач линейной алгебры и выбор универ- . сального базового матричного преобразования для решения типовых задач линейной алгебры .
- б -
-
Синтез и исследование алгоритмов многомерных линейных преобразований , ориентированных на аппаратурную реализацию е ваде СБИС , предназначенных для решения типовых задач линейной алгебры . .
-
Моделирование полученных алгоритмов на ЭЕМ и получение основных характеристик вычислительного процесса . - .
-
Исследование и сравнительный анализ основных характеристик разработанных алгоритмов и соответствующих известных алгоритмов при их аппаратурной реализации в виде СБИС .
Методы исследований, В работе использовались' методы математического моделирования , методы вычислительной математики , методы построения параллельных к векторных вычислительных систем и алгоритмов для них , итерационные методы вычислений , теория графов .
Научная", новизна работы. В диссертации разработаны и вынесены на защиту следующие основные положения :
аппаратурно - ориентированные алгоритмы решения ключевых задач линейной алгебры , построенные на базе метода отражения Хаусхолдера (алгоритмы быстрого преобразования Хаусхол- .' дера) ; ' - ' . '
методы расширения области сходимости алгоритмов быстро- -го преобразования Хаусхолдера , позволяющие синтезировать m -мерные алгоритмы быстрого преобразовачия Хаусхолдера , сходя-киеся на полном наборе входных данных ;
методы повышения скорости реализации алгоритмов быстрого преобразовачия Хаусхолдера , позволяющие на порядок и вьше повысить скорость реализации указанных 'алгоритмов ;
. - методика сценки л сравнения аппаратурно - временной сложности аппаратурно - ориентированных алгоритмов решения задач линейной алгебры . -
Практическая ценность. Разработаны алгоритмы решения ключевых задач линейной алгебры , ориентированные на аппаратурную реализацию в виде специализированных СБИС , предназначенных для использования в системах с матричной архитектурой . Использование разработанных алгоритмов позволит в 1,5 - 2 pa- . за уменьшить время решения задач , одновременно в 1,5 - 3 раза, снизить аппаратурные затраты и существенно ( ка порядок и более ) увеличить производительность С число задач , решаемых
- ? -
в единицу времени ) по сравнению с классическими алгоритмами при их аппаратурной реализации в виде СБИС . , и значительно ( более . чем на порядок ) снизить время решения задач по сравнению с программной реализацией известных методов на традиционных универсальных ЭВМ .
Реализация результатов" работы. Результаты работы были внедрены в ОКР по созданию платы - ускорителя ПЭВМ IBM PC AT по заказу АООТ "Волгограднефтегеофизика" .
Кроме того , результаты диссертации были тагосе использо
ваны при проведении госбюджетной научно - исследовательской
работы "Разработка и исследование алгоритмов для реализации в
виде СБИС процесса решения задач линейной алгебры" , проводи
мой в ВолгГТУ ( Волгоград ) под руководством д.т.н. , профес
сора Духнича Б. И. .
Апробация работы. Результаты диссертации докладывались и обсуждались' на I межвузовской научно - практической конференции студентов и молодых ученых Волгоградской области ( Волгоград , 1994 ) , Волжской городской научно - практической конференции ( Волжский . 1995 ) , а также на ежегодных конференциях ВолгГТУ ( Волгоград , 1993 - 1995 ) .
Публикации. По материалам диссертации опубликовано 4 пе
чатные работы и получено решение о Еыдаче патента РФ на изобт
ретение . , -
Структура и объем работы. Диссертация состоит из введения , четырех разделов , заключения , списка использованных источников , содержащего 60 наименований , и приложения . Работа изложена на 128 страницах основного текста , 56 страницах рисунков и таблиц , 5 страницах списка использованных источников , 11 страницах приложения .