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

■?ГБ О Л

(■-•'} 1 г " '

у " IV.-"-'

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

АНДРЕЕВ Андрей Евгеньевич

АППАРАТУРНО - ОРИЕНТИРОВАННЫЕ АЛГОРИТМЫ ТИПОВЫХ УНИТАРНЫХ ПРЕОБРАЗОВАНИЙ ЛИНЕЙНОЙ АЛГЕБРЫ

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

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

АВТОРЕФЕРАТ

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

ВОЛГОГРАД 1998

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

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

Духнич Е.И.

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

Дворянкин А.М.

кандидат технических наук, доцент Сальникова H.A.

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

Защита состоится ' <29 • с.е,НГЯ&рЯ 1998 г. в часов на заседании диссертационного совета К.063.76.05 Волгоградского государственного технического университета по адресу: 400066, г. Волгоград, проспект Ленина, 28, ауд. 209.

С диссертацией можно ознакомиться в библиотеке университета. Автореферат разослан " 27»СХ&Ч-УСТО. 1998 г.

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

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

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

В последние годы к вычислительной технике, используемой для решения этих задач, предъявляются все более высокие требования как в отношении производительности (количества задач, решаемых в единицу времени) и скорости вычислений, так и относительно снижения стоимости. Эти требования обусловлены, во-первых, возрастанием объема и сложности решаемых научных задач. Для ряда исследований (моделирование сложных физических и химических процессов, геофизические и геодезические исследования, задачи многокритериальной оптимизации и оптимального управления и другие) требуется обработка матриц большого размера, размерности которых достигают тысяч и даже сотен тысяч. Во-вторых, большой класс практических задач (задачи навигации, радиолокации, управления процессами производства, цифровой обработки сигналов (ЦОС), обработки изображений и другие) требует от вычислительного устройства способности работать в реальном масштабе времени (РМВ), когда на решение сложной математической задачи отводится от нескольких десятков секунд до долей секунды, что также приводит к необходимости повышать скорость вычислений. При этом операционная сложность решения матричных задач достаточно высока и имеет порядок 0(т3), где m - размерность обрабатываемой матрицы. Система, решающая задачу большой размерности или в реальном масштабе времени, должна характеризоваться очень высокой производительностью, а в ряде случаев и высоким быстродействием, что связано с увеличением скорости отклика системы.

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

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

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

Высокая операционная сложность численных методов линейной алгебры, особенно в случае обработки комплексных данных, в сочетании с необходимостью выполнять вычисления в РМВ зачастую требуют от вычислительных систем производительности порядка 10э-ь 1014 операций с плавающей запятой в секунду. Традиционные универсальные ЭВМ, основанные на фон-неймановской архитектуре с одним арифметическим устройством (АЛУ) и предусматривающие последовательное выполнение вычислений по алгоритмам, развернутое во времени, не в состоянии обеспечить подобную производительность. Выход состоит в применении параллельной и конвейерной обработки информации, которая при той же тактовой частоте и той же технологии изготовления процессорных элементов (ПЭ) позволяет увеличить производительность устройств.

Параллельные системы, построенные на базе универсальных ПЭ общего назначения, как правило, включают небольшое число процессоров, так как при увеличении их количества возрастают расходы на синхронизацию устройств, разрешение конфликтов, организацию обмена информацией, что в значительной степени влияет на производительность системы. Параллельные и векторные суперкомпьютеры, выполняющие десятки и сотни миллиардов операций с плавающей запятой в секунду (такие, как Cray (Т90, С90, ТЗЕ-1200, 0rigin2000), 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, H.M. Ahmed, J. Goetze, C.B. Мурашова, В. А. Егунова, C.O. Деревенскова и другие.)

Приблизительно с конца 80-х - начала 90-х годов ведутся разработки по использованию ДЛП - подхода для решения задач с комплексными матрицами, что в основном вызвано развитием алгоритмического обеспечения ряда областей, включая ЦОС, обработку изображений, моделирование сложных физических процессов. В настоящее время известны работы по исследованию применения ДЛП для выполнения типовых унитарных преобразований, прежде всего комплексного вращения (E.F. Deprettere, J.Cavallaro, A.Elster, J.-M. Delosme, S.-F. Hsiao, J. Freeman). В этих работах рассматривается использование ДЛП CORDIC для обработки комплексныхданных, либо - решение конкретных типов комплексных задач с помощью ДЛП. Предпринимаются попытки обобщенного подхода к выполнению унитарных преобразований с помощью ДЛП (E.F.Deprettere, G.J. Hekstra). Вместе с тем, практически не исследованы вопросы использования ДЛП для выполнения многомерных унитарных преобразований, а также реализация обобщенных унитарных ДЛП, выполняемых как одна унитарная макрооперация. Таким образом, задача разработки и исследования аппаратурно-ориентированных алгоритмов выполнения унитарных преобразований ЛА имеет несомненное научное и практическое значение и является актуальной, о чем можно судить, в частности, по анализу публикаций, посвященных этой проблеме.

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

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

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

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

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 страницах списка использованных источников.

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

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

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

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

1 уровень. Типовые прикладные задачи линейной алгебры, возникающие в практических приложениях (решение СЛАУ, решение

алгебраической проблемы собственных значений, поиск сингулярного разложения).

2 уровень. Типовые вычислительные задачи, не имеющие, как правило, самостоятельного прикладного значения, а являющиеся подзадачами для 1-го уровня (Ш- разложение и его модификации, разложение Холецкого, СШ- разложение и его модификации, приведение матрицы к верхней (нижней) Хессенберговой форме, трехдиагональной форме и к другим матрицам специального вида, и другие подзадачи).

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

-плоского комплексного вращения (КВ), которое может задаваться с помощью обобщенных параметров - комплексных чисел:

Л =

с

-я

Сг +

Сг ~ №

+ с,-

+ -У/

= 1.

где ] = (

либо с помощью параметров - углов вращения 9, фг ф2".

Ц0.Ф,.Ф2) =

О

о

„Л

соя 9 ятВ -ял 8 созб

-плоского комплексного гиперболического вращения (сдвига),

задаваемого аналогично круговому комплексному вращению :

Уф' о " "с/г е 5Й9"

. 0 сие

М0'Ф|'Ф2) =

Во-вторых, к типовым можно отнести процедуры многомерных преобразований, такие как:

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

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

Н(\у) = Е - 2

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

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

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

-гарантированная точность и устойчивость решения по алгоритму с минимальными погрешностями;

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

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

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

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

-возможность блочной организации алгоритма при решении задач большой размерности;

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

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

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

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

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

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

со

А

г=о

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

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

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

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

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

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

С =

V«" о

О еУф2

О О

О О

преобразований. (Методы выполнения многомерных унитарных ДЛП с предварительными вращениями можно назвать "комбинированными".)

Вариантом данного подхода является метод выполнения КВ с предварительным расчетом параметров вращения (также с помощью СОЯОЮ), и последующим вращением, фактически предусматривающий выполнение КВ в три этапа (и. СауаПаго).

Для большинства методов ДЛП характерно изменение модуля вектора в К раз :

К = п*,

1=1

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

Уиы)=У»+Уи2-:а-1 -Л-2-4'"3 + Ум 2~6'"4 - уи + ^ 2'г 1 = ЪУи 2"' + Ь + У2{ 2'2М - >2,- 2~4'"3 + у2, 2-6''-4 - у„ г^5 } ■

где I - номер итерации, % (= sgn(y2.').

Количество слагаемых в приведенных соотношениях (от 2 до 6) выбирается исходя из требуемой точности приближения модуля вектора, если нет необходимости в точном приближении модуля, слагаемые с младшими двоичными порядками отбрасываются. В работе приводятся необходимые данные о точности преобразования в зависимости от количества слагаемых.

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

Альтернативный подход предусматривает выполнение унитарных преобразований в рамках единого итерационного процесса ДЛП, то

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

Предлагается для выполнения плоских комплексных вращений (KB) использовать алгоритмы многомерных вещественных ДЛП. Исследована возможность использования ДЛП многомерного вращения, предложенного С.О. Деревенсковым, и показано, что с помощью указанного вещественного преобразования не удается получить унитарное преобразование комплексного вращения. Рассмотрен вариант реализации KB, предложенный S.-F. Hsiao и J.-M. Delosme, предусматривающий использование кватернионного ДЛП. Преимуществом данного метода, позволяющего реализовать KB за один этап ДЛП, является относительно низкая операционная сложность. Недостатками метода являются реализация преобразования KB в неявном виде, что не позволяет рассчитать параметры преобразования - углы KB Э, фг ф2, а также увеличение числа итераций, необходимых для обеспечения сходимости.

Для реализации KB в явном виде с вычислением параметров 6, ф.,, ф2за один этап ДЛП предлагается использовать два ДЛП кронекеровских произведений матриц вращения (КП), разработанных Е.И. Духничем. Тогда алгоритм комплексного вращения на базе кронекеровских произведений матриц вращения будет выглядеть следующим образом:

ЛТ .

z = [zx z2]

Xn =

в режиме вычисления модуля :

V 'RefzJ 0

х2 Im( zi) < Уо ~ У2 0

0 Уз Re(z2)

*4. 0 0 Уа_ 0 Jm(z2)

е0 = о Фю=о ф20 =0

в режиме вращения :

е0 = е Ф10 = Ф1 Ф 20 = 4> 2

1 ' х\

1

1 х3

1+1 1 .ХА.

1 V

Уг 1 У 2

Уз 1 -43,2-'" Уз

.УА. 1+1 1 Уа.

в режиме вычисления модуля :

в режиме вращения:

^¡=-sgn(x3¡+y3¡)

'5,1=^(8,)

Даг = 2"'

г = 17п

/ ~У\ \

+ У2

Уз

v Л. п .Уа. п)

0^ = 0,-$« Да, Фп+1 =Фц -^2«Аа/

1т(1[) Яе(2'2) 1т(1'2)

к=ПО /сау2 Ла.)=ПО+2"2') = И

1=1 (=1

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

Проведенное исследование сходимости метода (с помощью моделирования на ЭВМ) позволило определить общее количество итераций

и количество повторений отдельных итераций, необходимых для обеспечения сходимости с заданной точностью. Повторение части итераций является распространенным подходом для обеспечения сходимости методов ДЛП. Для предложенного метода требуется несколько большее число итераций, чем для метода ДЛП плоского вещественного вращения (на 15-20%), но при этом на 2-3 итерации меньше, чем для метода S.-F. Hsiao. Операционная сложность предложенного метода выше, чем у метода S.-F.Hsiao, однако он позволяет выполнять преобразование KB в явном виде и характеризуется меньшим числом итераций.

В данном разделе рассматриваются варианты реализации унитарного ДЛП отражения Хаусхолдера. Базовый алгоритм ДЛП Хаусхолдера (для вещественного случая) был предложен в работах Е.И. Духнича, а его модификации - в работах В. А. Егунова. В базовом алгоритме для реализации преобразования Хаусхолдера вектор отражения выбирается как

w,

(V

= -2-4;

Ч)

w,

т

со

^i)=s8n{z/c'i));

у = 2, т; к = 1, т

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

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

w

W

(i)

= -Г

0)

~ *bpRe О J

Re

(О

Um>

+ i E (i>

+ J S plm >

^Rr = sSn(Re(z/iJ)); ^=sSn(lm(zk(iJ)); p = 2,m ; k-\,m ; j = -J^1;

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

И',10 = §/(0 +У5/(,)."

^-Ц/Ц*/0));

р=1т; /=0Д; ] = г(0) =г; г'= г[к]

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

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

Рассмотрено применение предложенного подхода для получения ДЛП псевдоотражений, основанных на других методах ДЛП вещественного

отражения, обладающих лучшими характеристиками сходимости по сравнению с базовым вариантом. В частности, рассмотрены унитарные модификации ДЛП отражения Хаусхолдер-CORDIC, предложенного S.-F. Hsiao, а также ДЛП направленного отражения, разработанного В.А. Егуновым.

В ДЛП псевдоотражения на базе алгоритма Хаусхолдер-CORDIC

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

w

Н)

1

, ( р

= 1 + 7/

W- - 1 SpRe + J2 bplm .

vkRe

skim

0 = sgn(lm[z<l)^sgn(lm(zk(i^;

р = 2, т ; к = 1, т ; у = 7-1;

Моделирование алгоритма псевдоотражения на базе ДЛП Хаусхолдер-СОЯЭЮ показало, что количество необходимых итераций для ДЛП псведоотражения в данном случае будет больше примерно на 8 итераций по сравнению с базовым (вещественным) алгоритмом для всех рассмотренных размерностей векторов (рассматривались размерности до т = 100).

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

w.

С')

w

О)

_ н^ь

р=2,т; к = \,т; j = \; где Ord(X) - двоичный порядок числа А^

к (i)

SkRe =Sgn \кы1) =sgn

ОМ(Х) = 2Л0Ш0{'°г2Х)~\

Я01ЖВ(Х) - ближайшее кХцелое число,

а величины и равны соответственно

"I т

1=1 ¡=1

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

Хт = М{Хт)0гс1(Хпз).

Здесь Хт - число в формате с плавающей запятой,

М(ХПЗ) - мантисса числа, Огс1(Хт) - двоичный порядок числа.

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

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

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

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

-алгоритмы унитарных ДЛП характеризуются значительно меньшей операционной сложностью (в 2-6 раз) по сравнению с классическим способом реализации этих преобразований и на порядок более высокой производительностью вычислительного конвейера, при этом время выполнения преобразований в общем случае также сокращается (в 1.5 - 4 раза), но может быть и несколько больше (в 1.2 -2 раза), если предположить, что "длинные" операции при классическом способе реализации максимально распараллелены (при этом, однако, возрастет аппаратурная сложность реализации "длинных" операций);

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

-из алгоритмов ДЛП комплексного вращения наименьшим временем выполнения характеризуется разработанный ДЛП КВ на базе кронекеровских произведений (требует в 1.5-2 раза меньше времени по сравнению с ДЛП КВ на базе ССЖЭЮ в зависимости от разрядности операндов), при этом данный алгоритм обладает наибольшей операционной сложностью из всех рассмотренных ДЛП методов (операционная сложность в 1.8-3 раза выше, чем для варианта на СОИОЮ); наименьшей сложностью характеризуется метод, основанный на обычном алгоритме СОРОС, по соотношению сложности и быстродействия предпочтительнее известный алгоритм на базе кватернионного ДЛП (соответственно в 1.2-1.5 раза сложнее и примерно в 1.4-1.6 раза быстрее варианта на СОЯОЮ), который при этом реализует преобразование КВ только в неявном виде;

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

эбрабатываемых векторов), поэтому данные методы в основном могут применяться при небольших размерностях задачи (до 10), для которых их ускорение по сравнению с другими методами ДЛП может достигать 2-3 эаз; наиболее предпочтительными по соотношению времени выполнения преобразования и сложности являются алгоритмы ДЛП Хаусхолдер-ЗОРЮ1С; алгоритмы псевдоотражений с комплексным вектором отражения по сравнению с комбинированными методами на вещественных ДЛП карактеризуются несколько большей операционной сложностью (на 30% эольше, при этом в расчете на одну итерацию - даже меньше на 30%) и меньшим временем выполнения преобразования (при использовании Ы-арных сумматоров), при этом для методов Хаусхолдер-СОРЮЮ алгоритм псевдоотражения позволяет получить небольшое ускорение (до 15%), а алгоритм направленного псевдоотражения - до 2-3 раз.

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

В пятом разделе проводится оценка основных характеристик аппаратурных реализаций ряда алгоритмов унитарных преобразований, выделенных в четвертом разделе как наиболее перспективные (ДЛП КВ на базе КП, ДЛП КВ на базе кватернионных ДЛП, алгоритмы унитарных ДЛП на базе ДЛП Хаусхолдер-ССЖОЮ и направленных отражений). Рассматриваются некоторые схемные решения, использование которых позволяет эффективно использовать преимущества разработанных аппаратурно-ориентированных алгоритмов, в частности большое внимание уделено вопросам реализации операции быстрого многоместного сложения, рассмотрены варианты реализации быстрых параллельных сумматоров, выделены сумматоры с сохранением переноса (ССП), как наиболее оптимальные схемы с точки зрения аппаратурной сложности и времени выполнения сложения. Анализ характеристик аппаратурных реализаций алгоритмов, в качестве которых выбрана аппаратурная сложность в условных вентилях и время задержки, выраженное через время задержки на условном вентиле, позволяет утверждать, что реализация унитарных преобразований с помощью специальных унитарных ДЛП в рамках одного итерационного процесса позволяет в общем случае уменьшить время выполнения преобразований (для комплексного вращения -до 1.5 раз, для

направленного отражения - более чем в 2 раза) по сравнению с поэтапно! реализацией на вещественных блоках ДЛП, то есть подтверждайте временные показатели алгоритмов, приведенные в четвертом разделе; I то же время относительные показатели аппаратурной сложност! оказываются в ряде случаев более предпочтительными, чем показател! операционной сложности унитарных ДЛП, за счет учета накладны: расходов и сложности аппаратурной реализации отдельных операций. Так для разработанных алгоритмов КВ сложность аппаратурной реализаци! оказывается выше, чем для реализации на СОРЮЮ только на 25-50%, I то время как операционная сложность для этих методов выше в 1.8-: раза, для алгоритма ДЛП псевдоотражения Хаусхолдер-СОРЮЮ сложносп неконвейерного ПЭ оказывается на 50-60% ниже, чем для устройств нг базе вещественных блоков ДЛП отражения при увеличении времен! задержки на 15-20%. Таким образом, показано, что унитарные ДЛП реализующие унитарные преобразования комплексного вращения I отражения как макрооперации, по сравнению с поэтапной реализацией унитарных ДЛП, позволяют при аппаратурной реализации уменьшать врем} выполнения преобразования в среднем в 1.5 раза, при увеличении затра-на 20-50%, либо - существенно снижать аппаратурные затраты (до 60%) з; счет сокращения накладных расходов при незначительном увеличена времени преобразования (10-20%), либо - добиваться одновременное снижения затрат и уменьшения времени вычислений.

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

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

В диссертационной работе проведены исследования возможное™ реализации ряда типовых преобразований линейной алгебрь (комплексного кругового и гиперболического вращения, многомерны: унитарных преобразований вращения и отражения Хаусхолдера) в вид< аппаратурно-ориентированных алгоритмов дискретных линейны: преобразований (ДЛП). Разработаны алгоритмы унитарных ДЛП реализующие заданные преобразования в рамках единого итерационной процесса как укрупненные макрооперации, а также модифицированные алгоритм ДЛП гиперболического вращения без удлинения. Проведен« сравнение полученных алгоритмов и оценка характеристик аппаратурны: блоков, построенных на базе разработанных и известных методо! выполнения унитарных преобразований.

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

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

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

2) проведено обобщение подхода к синтезу многомерных зещественных ДЛП на комплексный случай;

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

4) для оценки сходимости и точности разработанных алгоритмов проведено моделирование работы алгоритмов на ЭВМ, предложены меры по расширению области сходимости;

5) получены оценки основных вариантов аппаратурных блоков для эеализации наиболее эффективных алгоритмов унитарных ДЛП, согласно <оторым аппаратурная реализация предложенных методов по сравнению : известными позволяет уменьшить время выполнения унитарных преобразований в 1.5-2 раза при соответствующем увеличении аппаратурных затрат, либо - существенно снизить аппаратурные затраты [до 60%) при незначительном (до 15%) увеличении времени вычислений.

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

1. Духнич Е.И., Андреев А. Е. Алгоритмы для аппаратурной реализации комплексного вращения // Тезисы докладов I межвузовской научно-практической конференции студентов и молодых ученых г. Волжского/ВПИ ВолгГТУ - Волжский, 1995.-C.107-109.

2. Андреев А.Е. Дискретное линейное преобразование комплексного вращения IIII Межвузовская научно-практическая конференция студентов л молодых ученых Волгоградской области: Сб.науч. ст. - Вып.5,-Волгоград: Издательство Волгоградского государственного университета, 1997-С.84-89.

3. Духнич Е.И., Андреев А.Е. Сходимость процесса ДЛП-отражения в комплексном случае // Тезисы докладов III межвузовской научно-практической конференции студентов и молодых ученых г. Волжского/ВПИ ВолгГТУ-Волжский, 1997.-е. 98-99.

4. Духнич Е.И., Андреев А.Е. Модифицированный алгорил дискретного линейного преобразования гиперболического вращения , Концептуальное проектирование в образовании, технике и технологии: С6 науч. тр./ВолгГТУ. Волгоград, 1997. - с. 39-42.

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

Андреев Андрей Евгеньевич

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

Подписано в печать ^' . формат60x84 у^.

Усл. печ. л. 1,0. Тираж 100 экз. Заказ -4&Я Печать офсетная. Бумаг писчая. Типография РПК "Политехник" Волгоградского государственног технического университета. 400005, г. Волгоград, ул. Советская, 35.