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

РГ6 од

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

МУРАШОВ Сергей Викторович

ИССЛЕДОВАНИЕ МЕТОДОВ РЕАЛИЗАЦИИ ДИСКРЕТНЫХ ЛИНЕЙНЫХ ПРЕОБРАЗОВАНИЙ В ЗНАКОРАЗРЯДНОЙ СИСТЕМЕ СЧИСЛЕНИЯ

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

ВОЛГОГРАД - 1995

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

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

Духнич Е.И.

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

Муха Ю.П.

кандидат технических наук^ (Ьуелил/1

Ссыи>нч1сс#а. Н.А

Ведущая организация - ОТДЕЛЬНОЕ КОНСТРУКТОРСКОЕ БЮРО

ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ (г.Волжский)

Защита состоится "22" МИРИЛ 1995г. в Ю часов на заседании диссертационного совета К 063.76.05 Волгоградского государственного технического университета по адресу: 400066, г. Волгоград, проспект Ленина 28,' ауд.209.

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

■■ 13" уМАЛ 1дд5г.

1

Ученый секретарь •!/ л

диссертационного совета Водопьянов В.И.

- 3 -

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

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

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

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

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

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

-- г1 ^" ■

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

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

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

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

Целью диссертации является разработка и исследование класса неавтономных и частично автономных алгоритмов в 1 избыточной знакоразрядной систейе' счисления для аппаратурной реализации типовых многомерных' ¿Йнёйных преобразований и разработка на их основе класса пробкемно-ориентированных вычислительных структур, позволяющих существенно (на порядок'' и 0 бЬлее)..... повысить

производительность вычислительных устройств. При этом структура таких вычислительных устройств должна строиться с учетом возможности их реализации в виде СБИС.

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

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

выбор критериев для оценки алгоритмов линейных преобразований, ориентированных на реализацию в виде СБИС;

анализ и выбор методов реализации неавтономных и частично автономных алгоритмов линейных преобразований;

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

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

разработка методики моделирования синтезированных алгоритмов и их моделирование на ЭВМ общего назначения.

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

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

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

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

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

неавтономные алгоритмы многомерных дискретных линейных преобразований (ДЛИ,,, вращения, отражения и кронекеровского

произведения);

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

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

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

Реализация результатов работы. Полученные в диссертации результаты были использованы в опытно-конструкторских работах, проводимых в НИИ МВС (Таганрог),по созданию высокопроизводительного проблемно-ориентированного вычислительного комплекса для отраслей машиностроения и систем научных исследований. Конкретно результаты работы были внедрены:

в ОКР по созданию опытного образца, высокопроизводительной многопроцессорной вычислительной системы цифровой обработки сигналов;

в ОКР по разработке неавтономного микропроцессора с программно-перестраиваемой структурой 4.601 ВЖЗ-0034.

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

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

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

отчете по хоздоговорной тематике.

Структура и объем работы. Диссертация состоит из введения, четырех разделов, заключения, списка литературы, содержащего 105 наименований, и приложения. Работа изложена на 205 страницах, 148 машинописных страницах основного текста. 47 страницах рисунков и таблиц, 8 страницах списка использованных источников, 2 страницах приложения.

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

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

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

Определены два альтернативных подхода при разработке вычислительных устройств (ВУ) на основе СБИС (в том числе и знакоразрядных ВУ): разработка ВУ с использованием современных и перспективных МП общего назначения и с использованием специализированных СБИС.

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

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

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

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

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

где матрица А1 содержит только нуди и целые степени основания системы счисления.

В этом случае вместо линейного преобразования вектора х

со

А - П А1 1-0

(1)

у « А-х

(2)

выполняется итерационный процесс

У1+1 - Агуь

(3)

где 1=0,1,...,п-1, у0=х.

В результате при п -» » уп -» у, а бесконечное произведение матриц (1) сойдется к матрице А. Как правило, итерационный процесс (3) строится таким образом, чтобы обеспечивалась линейная сходимость, и поэтому количество итераций п сравнимо с разрядностью операндов.

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

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

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

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

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

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

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

У1+1 - АгУь

•Pi+i = q>i - 5.1 ¿Vi.

t,i - sign?i; Д<h - arctg2_i,

Фо-а; Уо-х; 1-0,1,.,.,n-1,

(4)

где Ai

1

-Íi2T

UZ 1

-i

Ври этом результат получается в масштабе УП=1<У. где

п-1

к - п/ 1+2 21 - коэффициент деформации вектора.

1-0

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

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

простота вида матриц ДЛП; .., отсутствие деформации вектора в процессе преобразования (локальное масштабирование результата на каждой итерации);

определение знаков направлений ДЛП производится на первой итерации;

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

Методами моделирования были исследованы различные пути синтеза частично автономных алгоритмов ДЛП на основе (4). В результате был* получен алгоритм ДЛП вращения, отвечающий

сформулированным требованиям к частично автономным алгоритмам:

где

У1+1 - АгУь при п=±1,

У1+1 = У\, при п=0,

е.1 =

п

« - Е П2"1, 1-1

Пе{-1,0.1>; У1=х; 1=1,2.....п,

С052-1 *131П2~*

= « -4

-«,131п2 1 соэ2 1

(5)

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

В связи с тем. что в алгоритме (5) знаки направления вращения £.1 на каждой итерации известны заранее, появляется принципиальная возможность распараллеливания вычислений на уровне итераций.

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

На основе разработанной методики были синтезированы частично автономные алгоритмы многомерных- ДЛП вращения и кронекеровского произведения (в том числе и алгоритмы БДЛП).

Проведен синтез частично автономных алгоритмов ДЛП отражения на основе алгоритмов векторных ДЛП отражения, разработанных во втором разделе.

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

синтезирован частично автономный алгоритм ДЛП отражения, названный алгоритмом ЕДЛП отражения, с сокращенным количеством итераций, который отвечает сформулированным требованием к частично автономным алгоритмам ДЛП.

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

Предложена методика синтеза и синтезированы алгоритмы ВДПП отражения для пространств с произвольной размерностью.

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

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

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

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

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

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

вычисление . текущего значения вектора результата по

- 13 -

поступающим разрядам исходного вектора;

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

процедура выбора цифр результата не должна зависеть от конкретного вида алгоритма.

Полученный неавтономный алгоритм ДЛП в общем виде можно записать следующим образом:

1-1

У*1 = А1-1-у*1-1 + ПА1-Х12"1,

1=0

= 2Чу*1 - У*1-1) + 23!-! - 2РУ!-р,

г 1. при Бл^З,

УЯ1-р+1) = | о, при |Зл|<3,

^ -1, при БлС-З,

У^о=0; з3о=0; Уз (-р+1) =У1 с-р+2)=- • • -Узо=0, п

х - £ *12_1; 1=1,2.....п; 3=1,2.....ш,

1-1

(6)

где у*1- текущее значение вектора результата; вектор

частичного остатка; *1- вектор, состоящий из 1-ых разрядов

исходного вектора х; вектор, состоящий из 1-ых разрядов

вектора результата у; р - задержка неавтономной работы; - -

При вычислении текущего вектора результата по алгоритму (6)

необходимо вычислять произведение матриц ДЛП 1-1

П А1. 1-0

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

единичного вектора.

Разработанная процедура синтеза неавтономных алгоритмов в общем виде описывает методику перехода от автономных алгоритмов ДШ к неавтономным. Для синтеза конкретного алгоритма ДЛП необходимо разработать только процедуру вычисления текущего вектора результата у*ь Для .этого в выражение

1-1

У*1 = А1-1-у*1-1 + П Агх12-1 1-0

нужно подставить соответствующую матрицу ДЛП. .......-.

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

предварительная деформация исходного вектора х, путем " ' умножения всех одноразрядных компонент на коэффициент деформации к"1;

предварительная деформация вспомогательного единичного

вектора, при этом г=<к_1,0.....0>Ч

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

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

содержат в своем составе только простые операции типа сложения и сдвига;

не приводят к деформации результата.

• Разработана методика' и проведено моделирование синтезированных алгоритмов. По результатам моделирования была проведена модификация синтезированных алгоритмов.

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

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

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

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

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

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

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

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

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

По принятой классификации тип структуры можно охарактеризовать тремя цифрами (а.Ь.с) от единицы до тройки (где 1 - последовательные. 2 - последовательно-параллельные, 3 -параллельные структуры).

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

Дана оценка аппаратурных и вычислительных затрат для разработанных вычислительных структур. Затраты на вычисления оценивались в тактах. Проведено сравнение характеристик операци-

онных устройств по аппаратурно-временной сложности ¡ (ABC). Даны рекомендации по выбору типа структуры операционного устройства.

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

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

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

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

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

1. Синтезированы алгоритмы m-мерных векторных дискретных самосопряженных ортогональных преобразований, операционная сложность которых по сравнению с известными ¡алгоритмами ДЛП меньше в (пн-3)/3 раз.

; 2. Щюведен синтез частично автономных алгоритмов ДЛП вращения, отражения • и кронекеровского ■ произведения для пространств с произвольной размерностью.

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

4. Разработана методика синтеза неавтономных алгоритмов дискретных линейных преобразований.

5. Цроведен синтез неавтономных алгоритмов ДЛП вращения, отражения и кронекеровского произведения для пространств с

произвольной размерностью.

6. Разработана методика моделирования синтезированных алгоритмов на ЭВМ общего назначения.

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

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

1. ДухничЕ.И.. Мурашов C.B. Два варианта алгоритмов для быстрой аппаратурной реализации линейного преобразования отражения // Проектирование ЭВМ: Межвуз. Сб. научн. трудов. -Рязань, 1992. -С.47-51.

2. ДухничЕ.И., Мурашов C.B. Особенности реализации алгоритмов дискретных линейных преобразований с помощью СБИС // Многопроцессорные вычислительные структуры. -Таганрог, 1992. -Вып.14. -С.38-40.

3. Духнич Е.И., Мурашов C.B. Алгоритмы дискретных линейных преобразований для знакоразрядных микропроцессоров. Сб. тезисов докладов научно-технической конференции "Микросистема-93". -М., 1993. -С.80-83.

4. Разработка алгоритмов для аппаратурной реализации базового набора функциональных преобразований: Отчет по НИР (заключительный) / Волгоградский политехнический институт; Исполнители ДухничЕ.И., Мурашов C.B., Серов A.A. -№ ГР 0.191.0049198. -Волгоград, 1991. -76с.

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