Введение к работе
Актуальность темы. С каждым годом в различных областях науки и техники неуклонно возрастает прикладная роль математического аппарата линейной алгебры. Особенно возрастает роль и расширяется область использования многомерных преобразований линейной алгебры с развитием электронной вычислительной техники. Аппарат линейной алгебры широко используется при решении задач аэродинамики, сейсмологии, метеорологии, ядерной физики и физики плазмы, численного моделирования непрерывных полей, навигации, машинной графики, распознавания образов, фильтрации, гармонического анализа и многих других.
С появлением систем цифровой обработки информации, работающих в реальном масштабе времени, возникла необходимость создания вычислительных'средств для быстрого решения перечисленных задач. В связи с этим значительные усилия затрачиваются как на разработку новых аппаратурно-ориентированных методов решения задач линейной алгебры, так и на разработку новых вычислительных средств с лучшим отношением производительности к стоимости.
Характер вычислительных задач линейной алгебры определяет возможность укрупнения машинных операций при их решении. Такими крупными операциями (макрооперациями), которые можно было бы реализовать на ЭВМ аппаратно, являются линейные преобразования. Основным достоинством линейных преобразований является принципиальная сводимость многокомпонентных преобразований к последовательности преобразований с меньшим количеством компонент. Таким образом, степень укрупнения макроопераций может меняться в зависимости от заданных времени решения или объема оборудования.
Важным фактором при анализе методов аппаратурной реализации линейных преобразований является выбор способа представления информации при передаче и обработке операндов, а также выбор системы счисления; В настоящее время тенденции к постепенному укрупнению макроопераций, выполняемых аппаратурно, и ограничения, накладываемые при реализации вычислительных устройств на основе технологии": СБИС, привели "К необходимости широкого использования последовательной передачи и обработки информации в СБИС на уровне разрядов операндов. ' '
Одним из перспективных направлений развития вычислительной техники с поразрядным режимом вычислений является использование неавтономных методов обработки информации в избыточной знакоразряднои системе счисления. Эти методы относятся к наименее исследованным с точки зрения их аппаратурной реализации, при этом реализация крупных макроопераций с использованием неавтономных методов позволит существенно повысить производительность вычислительной техники.
Ввиду всего вышеизложенного представляется целесообразным развитие и обобщение неавтономных методов обработки информации в избыточной знакоразряднои системе счисления и распространение их на многомерные линейные преобразования, а также разработка вычисленных структур, ориентированных на аппаратурную реализацию этих методов, что позволит существенно (на' порядок и более) повысить производительность вычислительной техники.
В диссертации проведены исследования и разработаны неавтономные и частично автономные алгоритмы в двоичной избыточной знакоразряднои системе счисления, ориентированные на аппаратурную реализацию базового набора линейных преобразований, и структуры знакоразрядных процессоров,включаемых в вычислительную систему и позволяющих повысить ее . производительность на порядок и более. Предложенные структуры отвечают требованиям технологии СБИС, что позволяет расширить диапазон применения разработанных алгоритмов.
Данная работа является частью исследований, проводимых в
Волгоградском Ордена Трудового Красного Знамени государственном
техническом университете (ВолгГТУ) под руководством доктора
технических наук, профессора Духнича Е.И. в области разработки
архитектуры вычислительньоГструктур для аппаратурной реализации
задач линейной алгебры. Тема диссертации тесно связана с планом
хоздоговорных работ ВолгГТУ, проводимых по заказам промышленных
предприятий, и с госбюджетными работами. "' ":
Целью диссертации является разработка и исследование класса
неавтономных и частично автономных алгоритмов" в"' избыточной
знакоразряднои системе'' счисления для аппаратурной реализации
типовых многомерных' линейных преобразований и разработка на их
основе класса проблемно-ориентированных вычислительных структур,
позволяющих существенно (на порядок'л~ и1 более) повысить
- 5 -производительность вычислительньк устройств. При этом структура таких вычислительных устройств должна строиться с учетом возможности их реализации в виде СБИС.
Достижение поставленной цели требует решения следующих задач теоретического и прикладного характера:
выделение базового набора линейных преобразований при решении основных задач линейной алгебры, которые целесообразно выполнять аппаратно;
выбор критериев для оценки алгоритмов линейных преобразований, ориентированных на реализацию в виде СБИС;
анализ и выбор методов реализации неавтономных и частично автономных алгоритмов линейных преобразований;
синтез класса неавтономных и частично автономных алгоритмов дискретных линейных , преобразований, ориентированных на аппаратурную реализацию на знакоразрядных СБИС;
разработка и исследование вычислительных структур знакоразрядных СБИС, предназначенных для аппаратурной реализации разработанных алгоритмов;
разработка методики моделирования синтезированных алгоритмов и их моделирование на ЭВМ общего назначения.
Методы исследования. В работе использовались методы математического моделирования, теория вычислительных систем, методы вычислительной и дискретной математики, итерационные методы вычислений, методы построения конвейерных и параллельных алгоритмов и структур, теория вероятностей, математическая статистика.
Научная новизна работы. В диссертации разработаны и вынесены на защиту следующие основные положения:
алгоритмы т-мерных векторных дискретных самосопряженных ортогональных преобразований (векторные ДЛП отражения);
частично автономные алгоритмы многомерных дискретных линейных преобразований (ДЛП вращения,отражения и кронекеровско-го произведения); ,
методика синтеза неавтономных алгоритмов многомерных линейных преобразований;
неавтономные алгоритмы многомерных дискретных линейных ^преобразований (ДЛИ,,, вращения, отражения и кронекеровского
произведения);
вычислительные структуры, ориентированные на эффективную реализацию неавтономных и частично автономных алгоритмов многомерных линейных преобразований;
методология моделирования машинно-ориентированных алгоритмов многомерных линейных преобразований.
Практическая ценность. Выделен базовый набор линейных преобразований, ориентированный на решение прикладных задач линейной алгебры. Разработаны неавтономные и частично автономные алгоритмы, ориентированные на аппаратурную реализацию базового набора линейных преобразований. Аппаратурная реализация предложенных алгоритмов позволит существенно повысить (на порядок и более) производительность вычислительных устройств при решении задач цифровой обработки информации. Синтезированы неавтономные энакоразрядные вычислительные структуры на основе разработанных алгоритмов, предназначенные для построения высокопроизводительных систем цифровой обработки информации. .
Реализация результатов работы. Полученные в диссертации результаты были использованы в опытно-конструкторских работах, проводимых в НИИ МВС (Таганрог),по созданию высокопроизводительного проблемно-ориентированного вычислительного комплекса для отраслей машиностроения и систем научных исследований. Конкретно результаты работы были внедрены:
в ОКР по созданию опытного образца, высокопроизводительной многопроцессорной вычислительной системы цифровой обработки сигналов;
в ОКР по разработке неавтономного микропроцессора с программно-перестраиваемой структурой 4.601 ВЯЗ-0034.
Результаты работы были также использованы при проведении госбюджетной научно-исследовательской работы "Разработка и исследование алгоритмов для реализации в виде СБИС задач линейной алгебры", проводимой в ВолгГТУ (Волгоград).
Апробация работы. Результаты диссертации докладывались и обсуждались на конференции "Микросистема-93". (Москва, 1993г.), на ежегодных научных конференциях ВолгГТУ (Волгоград, 1991-1994ГЇСК
- 7 -Публикации. По материалам диссертации опубликовано 4 печатные работы. Кроме того, результаты исследований отражены в
отчете по хоздоговорной тематике.
Структура и объем работы. Диссертация состоит из введения, четырех разделов, заключения, списка литературы, содержащего 105 наименований, и приложения. Работа изложена на 205 страницах, 148 машинописных страницах основного текста. 47 страницах рисунков и таблиц, 8 страницах списка использованных источников, 2 страницах приложения.
