Введение к работе
Актуальность. Среди различных научно-технических задач, ресаемых на ЭВМ, с каждым годом все больший удельный вес приобретают вычислительные задачи большого объема, которые часто встречаются в аэродинамике, метеорологии, машинной графике и обработке изображений, ядерной физике и физике плазмы. К таким задачам могут Сыть отнесены задачи искусственного интеллекта, числового моделирования непрерывных по-^ лей в реальном масштабе времени и многие другие. В связи с этим считается необходимым создание ЭВМ с производительностью в миллиарды операций в секунду. Определяющим требованием при построении"таких ЭВМ является практическая независимость времени вычислений от числа одновременно обрабатываемых операндов.
Повышение быстродействия вычислительных устройств наряду с использованием прогрессивных интегральных технологий и скоростных табличных методов вычислений идет в направлении временного и пространственного распараллеливания алгоритмов и структур этих устройств. Данная проблема рассматривалась в раоотахИ.В.Прангишвили, Я.И.Фета, Б.Н.Малиновского, В.Мур-тафа, Г.Е.Пухова. Однако отсутствие соответствующей элементной базы приводило к необходимости организации попарной обработки массивов числовых данных (МЧД), что неизбежно снижало эффективность распараллеливания и приводило к увеличению аппаратурных затрат.
Дополнительным резервом роста производительности ЭВМ служит оптимизация способов кодирования МЧД. Так, представляется целесообразным использование в параллельных ЭВМ не только двоичной системы счисления (СС), главный недостаток которой наличие "длинных" межразрядных переносов, а некоторого комплекса, включающего как позиционные, так и непозиционные системы счисления. Особого внимания заслуживают коды Фибоначчи (КФ), золотой пропорции (КЗП), SD-двоичные коды, система счисления в остаточных классах (СОК), двоичная комплексная система счисления по основанию (-1+1). Их применение
способствует значительному сокращению времени реализации арифметических операций над потоком числовых данных за счет их выполнения в наиболее рациональной СС. Кроме того они позволяют решать вопросы надежности и точности обработки данных, которые приобретают все большее значение, особенно когда это касается алгоритмов и структур ориентированных на параллельную обработку больших массивов информации. Вопросы совместного использования кодов Фибоначчи и золотой пропорции рассматривались, например, в работах А.П.Стахова, В.А.Лужецкого, Ю.М.Вишнякова, Н.А.Соляниченко, и др. ученых. Однако и здесь авторы пользовались классическими арифметическими узлами, ориентированными на попарную обработку, что существенно снижало производительность разработанных устройств.
Компромиссным решением, возникших противоречий, является применение в одном устройстве комплекса систем счисления (КОС) с использованием таблично-алгоритмических принципов обработки информации и разрядно-параллельных правил вычисления, при которых аргументами операции выступают не сами числа, а их разрядные срезы, состоящие из одноименных разрядов чисел, имеющих одинаковые весовые коэффициенты. Такой подход был рассмотрен в работах О.Г.Кокаева и Ш-М.А.Ис'маилова.
Таким образом вопросы совершенствования алгоритмических и структурных способов повышения быстродействия арифметических устройств, использующих разрядно-параллельные способы обработки информации в КСС, представляет собой сложную научную проблему, решение которой имеет важное народнохозяйственное значение.
Цель работы. Совершенствование алгоритмических и структурных способов повышения производительности арифметических устройств и специализированных процессорных элементов на их основе, за счет использования разрядно-параллельных методов в сочетании с таблично-алгоритмическими способами обработки информации в комплексе систем счисления.
В соответствии с поставленной целью основные задачи ра-
Соты формулируются следующим образом:
анализ способов параллельной обработки информации с учетом способов ее кодирования в вычислительном устройстве (ВУ);
повышение производительности ВУ параллельной обработки числовых данных;
разработка алгоритмических основ разрядно-параллельных вычислений в КСС;
исследование структурной организации разрядно-параллельных арифметических устройств в КСС;
разработка способов комплексирования арифметических устройств, использующих КСС;
разработка разрядно-параллельного процессорного элемента (РППЭ), функционирующего в КСС.
Предметом исследования являются алгоритмические и структурные способы повышения производительности ВУ, на базе РППЭ, в основу которых положены таблично-алгоритмические принципы обработки МЧД, в КСС включающем КФ, КЗП, SD-двоич-ную СС, СОК и двоичную комплексную СС по основанию (-1+1).
Методы исследования. При решении поставленных задач использованы методы теории множеств, теории графов, теории-чисел, алгебры логики, теории матриц и теории вычислительных систем. Решение опирается на иерархическую схему "Задача -способ - алгоритм - структура - интерпретация" с оценкой временных и аппаратурных затрат.
Научная новизна выполненных исследований определяется разработкой способов разрядно-параллельных вычислений и принципов построения процессорных элементов в нетрадиционных СС:
разработаны алгоритмы и структуры процессорных элементов для выполнения операций разрядно-параллельного сложения, вычитания, умножения в КФ, КЗП, SD-двоичной СС, в СОК и двоичной комплексной ОС по основанию (-1+1). отличающихся высокой производительностью, надежностью, точностью и много-фу нкциональностыэ.
предложены способы її алгоритмы прямых и обратных
-o-
преобразований числовых данных в КСС, а также соответствующие им структуры устройств.
- предлолен способ рациональной организации вычисли
тельных процессов решения задач обработки МЧД в рассмотрен
ном КСС.
Практическая ценность. 1. Синтезированы разрядно-параллельные суммирующие модули в КФ. КЗП, SD-двоичной СС, в СОК и двоичной комплексной СС по основанию (-1+1) с возможностью их микроэлектронного исполнения.
2. Разработанные на основе этих модулей вычитатели, умножители, пребразователи МЧД. обладают следующими преимуществами:
высокой производительностью, из-за отсутствия потерь на обмен с ОЗУ и применения разработанных для массива чисел правил сложения, вычитания, умножения;
большой точностью, т.к. результат вычислений не ограничен определенной разрядной сеткой;
повышенной информационной надежностью;
итеративностью структур.
Реализация результатов работы. Диссертационная работа выполнялась в рамках госбюджетных тематик Дагестанского государственного технического университета: "Математические и технические аспекты организации массовой обработки числовой информации в процессорных элементах с изменяемой системой счисления" (1992-1995 гг.), и темы "Способы, алгоритмы и структуры специализированных вычислительных устройств параллельной обработки потоков данных и их применение для задач машинной графики" (1997-2001 гг.) в соответствии с приказами Министерства общего и профессионального образования Российс-якой Федерации.
Результаты исследований используются в учебном процессе Дагестанского государственного технического университета по специальностям 22.01 и 21.01.
Апробация работы. Основные результаты работы докладывались и обсуждались на: Всероссийской научно-техническая конференция "Информационно-управляющие системы и' специализиро-
ванные вычислительные устройства для обработки и передачи данных" (г.Махачкала, 1996); Всероссийском симпозиуме "Математическое моделирование и компьютерные технологии" ( Кисловодск, 1997); Международном симпозиуме "Мониторинг и прогнозирование чрезвычайных ситуаций" (Махачкала, 1997).
Публикации. По материалам диссертационной работы опубликовано 10 печатных работ, в том числе 3 патента, 5 тезисов докладов и 2 статьи.
Структура и объем работы. Диссертационная работа состоит из введения, 4 глав, заключения и списка литературы. Общий объем' диссертации -210 стр. Она изложена на 147 страницах основного машинописного текста, содержит 35 рисунка, 38 таблиц и включает библиографию из 1В0 наименований.
