Введение к работе
Актуальность темы. Задачи линейной алгебры (ПА), такие как решение систем линейных алгебраических уравнений (СЛАУ), поиск собственных значений и собственных векторов матриц, сингулярное разложение матриц и другие, играют большую роль как в научных исследованиях, так и в практических приложениях.
В последние годы к вычислительной технике, используемой для решения этих задач, предъявляются все более высокие требования как в отношении производительности (количества задач, решаемых в единицу времени) и скорости вычислений, так и относительно снижения стоимости. Эти требования обусловлены, во-первых, возрастанием объема и сложности решаемых научных задач. Для ряда исследований (моделирование сложных физических и химических процессов, геофизические и геодезические исследования, задачи многокритериальной оптимизации и оптимального управления и другие) требуется обработка матриц большого размера, размерности которых достигают тысяч и даже сотен тысяч. Во-вторых, большой класс практических задач (задачи навигации, радиолокации, управления процессами производства, цифровой обработки сигналов (ЦОС), обработки изображений и другие) требует от вычислительного устройства способности работать в реальном масштабе времени (РМВ), когда на решение сложной математической задачи отводится от нескольких десятков секунд до долей секунды, что также приводит к необходимости повышать скорость вычислений. При этом операционная сложность решения матричных задач достаточно высока и имеет порядок 0(т3), где т - размерность обрабатываемой матрицы. Система, решающая задачу большой размерности или в реальном масштабе времени, должна характеризоваться очень высокой производительностью, а в ряде случаев и высоким быстродействием, что связано с увеличением скорости отклика системы.
Таким образом, создание высокопроизводительных вычислительных устройств и алгоритмов для решения типовых задач ЛА является актуальной задачей, значимость которой возрастает по мере развития науки и техники.
Требования практики привели к разработке ряда алгоритмов цифровой обработки сигналов с высоким разрешением, в которых активно используются комплексные матричные вычисления. Это, прежде всего, методы определения направления на источник сигнала, волновые алгоритмы ЦОС, алгоритмы обработки сигналов для антенных решеток (алгоритмы ESPRIT, MUSIC и другие). Комплексные матричные модели
начинают активно применяться и в других областях научных исследований. В связи с этим приобретают все большую актуальность исследование и разработка методов вычислений и вычислительных систем для решения задач линейной алгебры в комплексном случае.
Высокая операционная сложность численных методов линейной алгебры, особенно в случае обработки комплексных данных, в сочетании с необходимостью выполнять вычисления в РМВ зачастую требуют от вычислительных систем производительности порядка 10э-т-1014 операций с плавающей запятой в секунду. Традиционные универсальные ЭВМ, основанные на фон-неймановской архитектуре с одним арифметическим устройством (АЛУ) и предусматривающие последовательное выполнение вычислений по алгоритмам, развернутое во времени, не в состоянии обеспечить подобную производительность. Выход состоит в применении параллельной и конвейерной обработки информации, которая при той же тактовой частоте и той же технологии изготовления процессорных элементов (ПЭ) позволяет увеличить производительность устройств.
Параллельные системы, построенные на базе универсальных ПЭ общего назначения, как правило, включают небольшое число процессоров, так как при увеличении их количества возрастают расходы на синхронизацию устройств, разрешение конфликтов, организацию обмена информацией, что в значительной степени влияет на производительность системы. Параллельные и векторные суперкомпьютеры, выполняющие десятки и сотни миллиардов операций с плавающей запятой в секунду (такие, как Cray (Т90, С90, ТЗЕ-1200, Origin2000), Intel iWarp, СМ-5 и Sun НРСЮООО в США, Fujitsu АР3000, VPP700E, Hitachi SR2201, S-3800, NEC SX-4 и SX-5 в Японии и другие) в силу их высокой стоимости, габаритов и стационарного характера работы не являются широко доступными и имеют ограниченное применение.
Быстро развиваются системы массивного параллелизма, основанные на большом числе относительно простых ПЭ, включающих типовые устройства-умножитель и сумматор, для выполнения типичных для ЦОС и матричных задач операций типа зацепления. В то же время, данные системы при решении ряда задач, прежде всего требующих высокой численной устойчивости, точности вычислений (методы ЦОС с высоким разрешением, задачи управления роботами и высокоточными технологическими линиями), не всегда позволяют достичь требуемых результатов даже при большом числе ПЭ и отлаженной схеме их взаимодействия.
Перечисленные трудности могут быть преодолены при построении параллельных и конвейерных архитектур на базе специализированных процессоров, позволяющих максимально учесть особенности решаемой
задачи или класса задач и в сочетании с параллельной и конвейерной обработкой получить высокие показатели производительности и быстродействия зачастую при умеренных аппаратурных затратах.
При построении спецпроцессоров для решения задач линейной алгебры наиболее предпочтительной с точки зрения соотношения между производительностью и универсальностью является реализация типовых вычислительных процедур разного уровня.
Задача разработки специализированных процессоров, реализуемых в виде СБИС и ориентированных на параллельную обработку, тесно связана с разработкой алгоритмов, которые будут выполняться на этих процессорах. Такие алгоритмы должны учитывать как специфические ограничения, накладываемые технологией СБИС, так и требования параллельной и конвейерной обработки информации и носят название аппаратурно-ориентированных алгоритмов. Среди подобных алгоритмов для выполнения преобразований ЛА выделяют алгоритмы дискретных линейных преобразований (ДПП).
Исторически алгоритмы ДЛП возникли из аппаратурно-ориентированного подхода к вычислению элементарных функций (методы "цифра за цифрой"), прежде всего - тригонометрических, предложенного в работах Дж. Волдера (J.E. Voider), Дж. Меджита (J.-E. Meggitt), Дж. Уолтера (J.S. Walther) в конце 50-х и в 60-х годах. В настоящее время известно множество различных модификаций методов Волдера и Меджита для вычисления разнообразных функций (В том числе - работы В.Д. Байкова, В.В. Смолова, Е.И. Духнича, J.-M. Muller, W.-H. Specker, S. Majerski, В. DeLugish, M.-D. Ercegovac и другие). В методах ДЛП аналогичный подход используется для выполнения типовых матричных преобразований.
Среди ДЛП хорошо известен алгоритм Волдера для выполнения линейного преобразования вращения на плоскости и устройство на его основе - CORDIC(ot Coordinate Rotation Digital Computer - цифровой компьютер для преобразования координат вращением). Применявшийся вначале для вычисления элементарных функций, этот метод примерно с конца 70-х годов начал все более широко использоваться для обработки матриц, прежде всего - в задачах ЦОС. Возможность распространения методологии алгоритма Волдера и других методов "цифра за цифрой" на многомерный случай для обработки матриц показана в работах Е.И. Духнича, который предложил термин "дискретные линейные преобразования". С середины 70-х- начала 80-хгодов ведутся исследования по применению CORDIC и других методов ДЛП для решения задач ЛА, в частности - в методах Якоби, при отыскании сингулярных и собственных значений, для решения СЛАУ. Разрабатываются методы кватернионных ДЛП, вычисления компонент тензоров с помощью ДЛП, ДЛП многомерных
линейных преобразований вращения, сдвига, отражения Хаусхолдера. (Работы Е.И. Духнича, В.Д. Байкова, J.-M. Delosme, E.F. Deprettere, J. Cavallaro, G.J. Hekstra, M. Kung, KM. Ahmed, J. Goetze, СВ. Мурашова, B.A. Егунова, CO. Деревенскова и другие.)
Приблизительно с конца 80-х - начала 90-х годов ведутся разработки по использованию ДЛП - подхода для решения задач с комплексными матрицами, что в основном вызвано развитием алгоритмического обеспечения ряда областей, включая ЦОС, обработку изображений, моделирование сложных физических процессов. В настоящее время известны работы по исследованию применения ДЛП для выполнения типовых унитарных преобразований, прежде всего комплексного вращения (E.F. Deprettere, J.Cavallaro, A.EIster, J.-M. Delosme, S.-F. Hsiao, J. Freeman). В этих работах рассматривается использование ДЛП CORDIC для обработки комплексныхданных, либо - решение конкретных типов комплексных задач с помощью ДЛП. Предпринимаются попытки обобщенного подхода к выполнению унитарных преобразований с помощью ДЛП (E.F.Deprettere, G.J. Hekstra). Вместе с тем, практически не исследованы вопросы использования ДЛП для выполнения многомерных унитарных преобразований, а также реализация обобщенных унитарных ДЛП, выполняемых как одна унитарная макрооперация. Таким образом, задача разработки и исследования аппаратурно-ориентированных алгоритмов выполнения унитарных преобразований ЛА имеет несомненное научное и практическое значение и является актуальной, о чем можно судить, в частности, по анализу публикаций, посвященных этой проблеме.
Целью диссертации является исследование существующих и создание новых алгоритмов типовых унитарных преобразований, предназначенных для аппаратурной реализации решения задач линейной алгебры в рамках высокопроизводительных вычислительных систем, исследование возможности ускорения выполнения типовых преобразований и улучшения совокупности характеристик вычислительной системы за счет распараллеливания вычислений и укрупнения аппаратурно-реализуемых преобразований.
Для достижения поставленной цели требуется решение следующих основных задач:
-
Классификация задач линейной алгебры и выделение небольшого числа унитарных преобразований, широко применяемых для решения типовых задач линейной алгебры.
-
Исследование существующих и синтез новых алгоритмов, ориентированных на аппаратурную реализацию типовых унитарных преобразований линейной алгебры в рамках параллельных и конвейерных высокопроизводительных вычислительных систем и технологии СБИС.
3) Моделирование полученных аппаратурно-ориентированных
алгоритмов на ЭВМ и определение основных особенностей
вычислительного процесса.
4) Сравнительный анализ рассмотренных алгоритмов типовых
унитарных преобразований с точки зрения их операционной сложности и
времени получения решения.
5) Определение относительных показателей аппаратурных блоков,
реализующих исследуемые алгоритмы унитарных преобразований.
Методы исследования. В работе использовались методы математического моделирования, вычислительной математики, методы построения параллельных и векторных вычислительных систем и алгоритмов для них, итерационные методы вычислений, теория графов.
Научная новизна работы. В диссертации разработаны и вынесены на защиту следующие основные положения :
-аппаратурно-ориентированные итерационные алгоритмы типовых унитарных преобразований комплексного вращения, выполняемых в рамках единого итерационного процесса;
-аппаратурно-ориентированный алгоритм дискретного линейного преобразования гиперболического вращения вектора, характеризующийся сохранением нормы вектора;
-аппаратурно-ориентированные итерационные алгоритмы многомерных унитарных преобразований на базе преобразования отражения Хаусхолдера, выполняемые как единый итерационный процесс;
-обобщение подхода к выполнению унитарных преобразований с помощью аппаратурно-ориентированных алгоритмов, известного для плоских преобразований, на случай многомерных преобразований;
-методика оценки и сравнения аппаратурно-ориентированных алгоритмов унитарных преобразований линейной алгебры.
Практическая ценность. Разработаны алгоритмы выполнения унитарных преобразований линейной алгебры, ориентированные на аппаратурную реализацию в виде специализированных СБИС, предназначенных для использования в системах с матричной, систолической архитектурой. Использование разработанных методов позволяет в 2-6 раз снизить аппаратурные затраты, в ряде случаев в 1.5-4 раза уменьшить время решения задач и существенно (от 3 до 10 раз) увеличить производительность по сравнению с классическими алгоритмами при их аппаратурной реализации на СБИС. По сравнению с известными аппаратурно-ориентированными методами выполнения типовых унитарных преобразований при реализации на СБИС использование разработанных алгоритмов позволит в 1.5-2 раза уменьшить время решения задач с увеличением аппаратурных затрат на 20%-40%, либо - сократить
аппаратурные затраты до 60% при увеличении времени выполнения алгоритмов на 10-15%.
Реализация результатов работы. Результаты диссертации были использованы при проведении госбюджетных научно- исследовательских работ № 44-53/041-93 "Разработка и исследование алгоритмов для реализации в виде СБИС процесса решения задач линейной алгебры" и № 44-53/792-97 "Разработка структуры высокопроизводительных специализированных процессоров - цифровых линейных преобразователей, ориентированных на быстрое решение задач линейной алгебры" (направление "Конверсия"), проводимых в ВолгГТУ ( Волгоград ) под руководством д.т.н. , профессора Духнича Е.И. Автор является ответственным исполнителем НИР № 44-53/792-97.
Апробация работы. Основные результаты, полученные в диссертации, докладывались и обсуждались на II и III межвузовских научно-практических конференциях студентов и молодых ученых Волгоградской области (Волгоград, 1995-1996 гг.), I и III Волжских городских научно-практических конференциях (Волжский, 1995 г., 1997 г.), на ежегодных научных конференциях ВолгГТУ (Волгоград, 1995-1998 гг.).
Публикации. По материалам диссертации опубликованы 4 печатные работы.
Структура и объем работы. Диссертация состоит из введения, четырех основных разделов, заключения и списка использованных источников, содержащего 73 наименования. Работа изложена на 148 страницах основного текста, 45 страницах рисунков и таблиц, 6 страницах списка использованных источников.
