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

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

ОЦОКОВ ШАМИЛЬ АЛИЕВИЧ

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

05.13.15. - Вычислительные машины и системы. 05.13.05. - Элементы и устройства вычислительной техники и систем управления

АВТОРЕФЕРАТ

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

Москва -2004

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

Научный руководитель

Научный консультант

Официальные оппоненты

Ведущая организация

доктор технических наук, профессор Исмаилов Шейх-Магомед Абдуллаевич доктор технических наук, профессор Дзегелёнок Игорь Игоревич. доктор технических наук, профессор Борисов Вадим Владимирович кандидат технических наук Геништа Николай Евгеньевич Научно-исследовательский вычислительный центр МГУ

Защита состоится « 19 » марта в 16 ч. па заседании диссертационного совета Д 212.157.01 при Московском энергетическом институте (техническом университете) по адресу: 111250, Москва, Красноказарменная ул., д. 17, ауд. Г 306.

С диссертацией можно ознакомиться в библиотеке МЭИ.

Автореферат разослан «_»_

Отзывы в двух экземплярах, заверенные печатью организации, просим отправлять по адресу: 111250, г. Москва, Красноказарменная ул., д. 14, Учёный совет МЭИ(ТУ).

Учёный секретарь диссертационного совета к.т.н., профессор

И.И. Ладыгин

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

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

Актуальность темы исследования

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

Одной из существенных проблем решения таких задач на ЭВМ

является накопление ошибок округления в ходе вычислительного

процесса, учет которых требует больших временных затрат и

трудозатрат. | РОС НАЦИОНАЛЬНАЯ I

| БИБЛИОТЕКА I

I С Петербург л/ }

« 09 гоа4г«тГ^ I

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

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

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

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

Безошибочные вычисления активно развиваются как в теоретическом, так и программно-прикладном направлении.

В настоящее время проводятся интенсивные исследования по аппаратной реализации алгоритмов безошибочных вычислений.

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

Цель работы

Цель настоящей работы исследование модели безошибочных вычислений в системе остаточных классов (СОК) и ее усовершенствование в направлении создания высокопроизводительных ЭВМ.

Основными задачами диссертационной работы являются:

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

2. Усовершенствование модели безошибочных вычислений в части разработки:

• быстродействующего алгоритма деления в многомодульной СОК;

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

3. Экспериментальное исследование усовершенствованной модели параллельных безошибочных вычислений с рациональными числами в СОК.

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

Научная новизна основных результатов

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

На защиту выносятся следующие результаты:

• Алгоритмические принципы прямых и обратных преобразований чисел из позиционной системы счисления в СОК, включающие преобразование чисел, представленных в формате с фиксированной запятой.

• Ускоренный алгоритм деления в многомодульной СОК на основе таблиц индексов и антииндсксов.

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

• Метод организации безошибочных вычислений с расширением диапазона представления искомых результатов в классе дробей Фарея порядка N с модулем Р в СОК, определяемого исходя из

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

• Результаты экспериментального исследования модели безошибочных вычислений в многомодульной СОК с использованием параллельной мультикомпьютерной сети «КУРС-2000», разработанной на кафедре ВМСиС МЭИ (ТУ).

• Сравнительные оценки быстродействия аппаратной и программной реализации алгоритмов безошибочных вычислений в СОК.

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

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

Достоверность полученных результатов подтверждается следующим:

• корректным использованием математического аппарата теории чисел;

• соответствием основных теоретических положений результатам выполненных экспериментов;

следующего неравенства: , вместо

Практическая ценность работы

Достоверность основных результатов

• апробацией основных результатов на конференциях в том числе на Международных: «Информационные технологии в науке, образовании, телекоммуникации, бизнесе» (Украина, Крым, Ялта-Гурзуф, 2003 г.), «Информационные средства и технологии» МЭИ (ТУ) (Москва, 2003 г.), «Computational Fluid Dynamics» (Москва , 2003 г.), на Всероссийских конференциях: «Новые информационные технологии» (Москва 2003 г.), «Новые информационные технологии. Разработка и аспекты применения» (Таганрог, 2003 г.), на Республиканской конференции «Информационные и телекоммуникационные системы: интегрированные корпоративные сети» ДНЦ РАН (Махачкала, 2001 г.).

• опытом практического применения алгоритма безошибочных вычислений для расчета режимов ГЭС в энергосистеме ОАО «Дагэнерго».

Реализация результатов работы.

Разработана программа безошибочного решения системы линейных уравнений в одномодульной СОК ( свидетельство гос. регистрации №2003610764 в реестре программ для ЭВМ ).

Программа нашла применение в ОАО «Дагэнерго» и включена в состав комплекса программ "Расчет суточных режимов Сулакского каскада ГЭС", что подтверждено соответствующим актом о внедрении.

Результаты диссертационного исследования также используются в учебном процессе Дагестанского государственного технического университета по специальностям 22.01 и 22.04, имеется акт о внедрении.

Апробация работы

Основные результаты работы докладывались на Международных конференциях: «Информационные технологии в науке, образовании, телекоммуникации, бизнесе» (Украина, Крым, Ялта-Гурзуф, 2003 г.), «Информационные средства и технологии» МЭИ (Москва, 2003 г.), «Computational Fluid Dynamics» (ICCFD, Moscow, 2003 г.), на

Всероссийских конференциях: «Новые информационные технологии» МГАПИ (Москва 2003 г.), «Новые информационные технологии. Разработка и аспекты применения» (Таганрог, 2003 г.), на Республиканской конференции: «Информационные и телекоммуникационные системы: интегрированные корпоративные сети» ДНЦ РАН (Махачкала, 2001 г.).

Публикации

По материалам диссертационной работы опубликовано 10 трудов.

Структура и объём работы

Диссертация состоит из введения, четырёх глав, заключения, списка литературы и приложений. Общий объём 264 с, из них основного текста 140 с, список литературы из 143 наименований, 46 рисунка, 18 таблиц.

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

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

В первой главе дан обзор и проведен теоретический анализ безошибочных вычислений.

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

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

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

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

Если задан ряд положительных целых чисел Рх,..., рт , называемых основаниями системы или модулями, то под системой остаточных классов понимают такую систему, в которой целое положительное число представляется в виде набора остатков ( вычетов ) по выбранным основаниям:

в которой образование цифр осуществляется так, что

т.е. цифра ьго разряда а (числа А есть наименьший положительный остаток от деления М на

Величина диапазона Р представления чисел СОК в этом случае

т

равна

Арифметические операции в СОК, кроме деления выполняются так же, как и в позиционной системе счисления (ПСС). Но результаты арифметических операций в СОК, в отличие от ПСС приводятся по модулям.

Результаты арифметических операций сложения, вычитания (дополнения до модуля), умножения с операндами

представлены соответственно

остатками по основаниям

при условии:

А<Р, В<Р, А+В<Р,А-В<Р,АВ<Р.

При этом результаты определяются следующим образом:

Деление в СОК, в отличие от ПСС, выполняется в два этапа: 1) определение обратного делителя; 2) умножение обратного на делимое.

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

Для однозначного представления рациональных чисел в СОК используются дроби Фарея. Дробь Фарея, представляет собой несократимую дробь числитель и знаменатель которой удовлетворяет

следующим условиям:

0 5 ^,0 2 |б|£ И,(а,Ь) = 1,

где - числитель, знаменатель и порядок дроби Фарея

соответственно.

На рис. 1 показана модель безошибочных вычислений в СОК. В соответствии с этой моделью входные данные ( рациональные числа ) преобразуются в СОК. Далее проводятся все вычисления в СОК и если не возникло псевдопереполнение, конечный результат преобразуется в ПСС.

Если результат вычислений в СОК по модулю Р не имеет взаимно однозначного отображения в конечное множество дробей Фарея порядка N где N удовлетворяет неравенству: 2-Й2 + \ й Р , то возникает ситуация, называемая псевдопереполнением.

Псевдопереполнение является одной из проблем безошибочных вычислений в СОК и создаёт неопределенность в вопросе о правильности результата, т.к. если оно возникло в промежуточных результатах, но не в конечном, ответ все же принадлежит множеству дробей Фарея порядка N и оказывается верным.

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

Метод основан на том, что вне зависимости от возникновения псевдопереполнения истинные и полученные результаты безошибочных вычислений принадлежат одному классу вычетов. При известном произведении всех знаменателей дробей, с которыми проводятся безошибочные вычисления, по модулю СОК, истинный результат А I В определяется следующим образом:

где - конечный результат безошибочных вычислений,

Вг - произведение знаменателей всех дробей по модулю СОК.

Данный метод позволяет существенно расширить диапазон представления искомой дроби, так что А, В И Р , вместо

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

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

А__ р • Дг[ В вг

I р

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

Пусть решение некоторой вычислительной задачи включает в себя последовательное выполнение следующих арифметических операций: к1 сложений, умножений, вычитаний, к ^ делений и модуль СОК Р удовлетворяет неравенству 2 • N 2 + 1 £ Р , где N - порядок дроби Фарея . Тогда сумма к1 чисел в развернутой форме равна:

( ак 1-] _ айЬУ"Ьк%-\ +- + а1Ь0-Ь1~\ЬМ-Ьк,-\ + " + ак{-\Ъ0"Ьк1-2 Ь0 ¿>„¿>,...6^.,

1 — I

N <; шах £ П М-> * О, П Ь1

1 = 0 >=о

*,-1

п

1 = 0

>авенству:

и по

'.¡V < шах

к} -1 *2 ~1 П

у=о

к,-1

¡=0

Для разности к, чисел:

N 5 тах

; = 1 1 = 1 у = 1 1=0

Для деление чисел:

N £ тах

Л.-1

аоП Ь|.4оП

(=1 _/'=■!

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

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

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

Индексом числа а по простому модулю р называется такое число у 2 0 , которое удовлетворяет следующему сравнению:

- первообразный корень по простому

модулю р.

Индекс числа а по модулю р при основании g обозначается символом и аналогично понятию логарифма.

Для перехода от индекса к фактическому числу применяются антииндексы.

Антииндексом числа I называется число а такое, что

По определению обратного числа а"1 ■ а = l(modp) , где р

простое число. Из свойств индексов верно следующее: ind (а) + ind (а = ind 1 (mod Р - 1).

модулю

где ind "'(а) - антииндекс числа а .

Таким образом, при хранении для каждого модуля СОК таблиц индексов и антииндексов, операция деления сводится к определению антииндекса разности модуля СОК уменьшенного на единицу и индекса делителя.

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

Вторая глава посвящена разработке и исследованию способов и алгоритмов безошибочных вычислений в СОК, а также прямых и обратных преобразований целых чисел и с фиксированной запятой вида: {ПСС=>СОК}, {СОК=>ПСС}.

Основу алгоритма преобразования целых чисел из ПСС в СОК составляет формула разложения чисел по основанию ПСС и свойство сложения чисел по модулю.

Известно, что любое целое число М в ПСС при основании Ь можно

представить в следующем виде:

где коэффициенты с, могут принимать значения 0,1,...— Ь -1. Если р - модуль СОК, то верно следующее:

14 -

п-1

ХС!-Ь'

Д=0

1—11 .. и-1, , . ..

■Хк-ь' -ХЫ.-М ■

1=0'

1=0

Значения ^-записываются в таблицы соответствия. Перевод числа М из ПСС в СОК осуществляется следующим образом: определяется сумма , где п- разрядность числа, которая приводится по модулю р.

Суть алгоритма преобразования целых чисел из СОК в ПСС

заключается в следующем:

Пусть заданы число и модули СОК

В соответствии с правилом перевода числа из ПСС в СОК

вычисляются базисы СОК, а именно В^———, где Р равно

произведению модулей, от,- веса, которые выбираются так, что выполняется сравнение: остаток от деления Р на

Для ускорения реализуемого преобразования величины т/ вычисляются следующим образом: /и, = ¿ти/"1(/>,- -\-ind8i) и

л

результат п р е о б р ' Лпсс = ^Ш(Ы а, + Ы Л,) Д и т с я по модулю Р.

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

Пусть для преобразования дроби а в ЭВМ отводится г разрядов, г - количество разрядов, стоящих слева от запятой. Все дроби лежат в диапазоне - р' < а < р', где р - основание ПСС.

ос" v*~r с ^

Пусть а = ——— = — и —= -— , где -— - несократимая дробь. j а кг кг

В диссертации показано, что дроби соответствуют

одному и тому же числу СОК - где

Р = т<1-\Р-\-тй ¿)с = Ш(Ы(ШМ ¿)) + Ы с).

Преобразование чисел с фиксированной запятой в многомодульную СОК заключается в определении ¡а,/6, И г,-

выражении а/Ь = (а1/Ь1)-(т1)г'. Недостатком алгоритма преобразования (Матулы-Грегори) является необходимость деления а на ет/для определения г, . Для его устранения предлагается кратность а на определять при помощи таблицы соответствия по следующему выражению:

Если число а = ал_|...а0 кратно mit то S =0 и частное от деления определяется следующим выражением: d = ind~x ((ind а - ind (modр -1)).

Разработанный в главе набор алгоритмов прямых и обратных преобразований чисел с фиксированной запятой из одной системы счисления в другую, вида : { ПСС->СОК }, { СОК->ПСС } позволяет перейти к разработке структурных схем.

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

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

Как указывалось выше, все арифметические операции в СОК, кроме деления выполняются также, как и в ПСС. Но результаты арифметических операций, в отличие от ПСС приводятся по модулю.

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

Принцип структурной организации устройства нахождения обратного элемента в СОК приведен на рис. 2. Устройство состоит из следующих блоков: УУ - устройство управления ; ПЗУ 1, ПЗУ 2 -постоянные запоминающие устройства, содержащие значения индексов и антииндексов; Вычитатель 1, Вычитатель 2 - разрядно-параллельные вычитатели; Peг. - регистр для хранения результата.

Принцип работы заключается в следующем.

По приходу первого импульса с устройства управления на входы Вычитатель 1 поступают значение модуля и единица. По тому же такту на адресные входы первого постоянного запоминающего устройства ПЗУ 1 поступает исходное значение - число А. С информационных выходов ПЗУ 1 извлекается соответствующее значение индекса.

По приходу второго управляющего импульса коды с выходов Вычитателя 1 и ПЗУ 1 поступают на адресные входы ПЗУ 2, содержащего антииндексы. По приходу третьего импульса с устройства управления код с выходов ПЗУ 2 поступает в выходной регистр Peг.

Работа устройства заканчивается через 3 такта.

Объем хранимой информации в ПЗУ1 и ПЗУ2

условных бит.

Аппаратурные затраты на реализацию рассмотренной структурной схемы можно определить как:

где - затраты аппаратуры на реализацию первого разрядно-параллельного вычитателя; - затраты аппаратуры на реализацию

второго разрядно-параллельного вычитателя ;Уз - затраты памяти ПЗУ 1;

- затраты памяти ПЗУ 2; - затраты аппаратуры на реализацию устройства управления; - затраты регистровой памяти.

Принцип структурной организации устройства преобразования целых чисел из ПСС в СОК представлен на рис. 3.

Устройство содержит следующие блоки.

Peг. 1- регистр ввода данных ; Peг. 2 - регистр для хранения результата; УУ - устройство управления ; ПЗУ - постоянное запоминающее устройство, содержащее константы соответствия;- СМ -разрядно-параллельный позиционный сумматор; БСР - блок сравнения; Блок вычитателей - разрядно-параллельные устройства вычитания.

Принцип работы устройства заключается в следующем. Во входной регистр Peг 1 поступает ^разрядное число, представленное в ПСС. По приходу первого импульса с устройства управления на адресные входы ПЗУ поступают соответствующие разряды исходного числа, преобразованный код поступает на входы разрядно-параллельного сумматора СМ , имеющего входов, где Р - модуль, п -

разрядность исходного числа. По тому же такту значение суммы с выходов сумматора СМ поступает на входы блока сравнения БСР, который сравнивает входное число с кратными модуля . По приходу

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

Работа устройства преобразования чисел из ПСС в СОК заканчивается через 3 такта.

Объем хранимой информации постоянного запоминающего устройства ПЗУ - [9 -(л - 1) -log г(Р - 1)] условных бит, где п-разрядность числа, Р - модуль СОК.

Аппаратурные затраты на реализацию рассмотренной структурной схемы можно определить как:

где - затраты информации постоянного запоминающего устройства;

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

V« - затраты аппаратуры на реализацию блока вычитателей; Vj - затраты регистровой памяти; затраты аппаратуры на реализацию устройства управления.

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

Эффективность безошибочных вычислений в СОК исследовалась при решении систем линейных алгебраических уравнений (СЛАУ) с использованием разработанной на кафедре ВМСиС МЭИ (ТУ) параллельной мультикомпьютерной сети «КУРС-2000» с динамически изменяемой структурой обменов. Программное обеспечение сети «КУРС-2000» позволяет организовать выполнение распределенной параллельной программы на множестве персональных компьютеров - вычислителей, соединенных локальной сетью и таким образом, объединить их вычислительные ресурсы для решения общей задачи.

В результате проведенного исследования были получены оценки времени безошибочного решения СЛАУ методом Гаусса в одномодульной и многомодульной СОК. На основе времен решения СЛАУ в одномодульной СОК Г0 и параллельной реализации в

многомодульной СОК с количеством оснований: 2, 4, 8 - Тм вычислены

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

М

и их

Исследования проводились при помощи ПМК-сети «КУРС 2000» на компьютерах Pentium III - 600МГц, ОС Windows2000 в сети FastEthernet. В ходе эксперимента изменялось число уравнений системы от 1 до 100, коэффициенты левой части и ее неизвестные генерировались случайным образом в диапазоне от 1 до 10, на основе этого вычислялась правая часть системы. При этом, в одномодульной и многомодульной СОК, с числом модулей - 2,4, 8, порядки модулей составляли соответственно: 1022,101104,103.

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

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

Еще больший эффект повышения быстродействия безошибочного решения СЛАУ в многомодульной СОК достигается за счет применения ускоренного алгоритма деления с использованием индексов и антииндексов ( быстродействие решения СЛАУ размерностью от 1 до 100 возросло примерно в 2,5 раза).

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

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

В последнем разделе приведены результаты внедрения программы безошибочных вычислений в диспетчерском управлении ОАО «Дагэнерго» для расчета оптимальных режимов Чирюртовской ГЭС, входящей в каскад Сулакских ГЭС.

Так, экспериментальное исследование показало, что использование разработанной программы безошибочных вычислений позволило уточнить прогностическую оценку уровня воды в нижнем бьефе Чирюртовской ГЭС более чем на 2% по сравнению с используемой на практике программы «Расчет добегания расхода воды».

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

• приложение 1 - описание проекта безошибочного решения СЛАУ в среде C++Builder (свидетельство об официальной регистрации программы для ЭВМ №2003610764)

• приложение 2 - листинг динамической программной библиотеки DLL Windows для безошибочных вычислений в одномодульной системе остаточных классов в среде C++ Builder.

• приложение 3 - описание проекта безошибочного решения СЛАУ в многомодульной СОК в среде Delphi.

• приложение 4 - Результаты сопоставительного расчета оптимальных режимов Чирюртовской ГЭС по состоянию на 2 января 2003 г.

• приложение 5 - Задача обращения матрицы Гильберта.

• приложение 6 - Акты о внедрении.

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

Основные результаты данной работы состоят в следующем:

1. Уточнены классы задач, требующие повышенной точности вычислений на ЭВМ и среди которых один из важнейших - задачи большой размерности.

2. Усовершенствованы алгоритмические принципы прямых и обратных преобразований чисел из позиционной системы счисления в одномодулыгую и многомодульную СОК.

3. Разработан ускоренный алгоритм ( по сравнению с расширенным алгоритмом Евклида) нахождения обратного числа в многомодульной СОК на основе таблиц индексов и антииндексов.

4. Разработан метод организации безошибочных вычислений с расширением диапазона представления искомых результатов в классе дробей Фарея порядка N с модулем Р в СОК, определяемого исходя из следующего неравенства:

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

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

7. Проведено экспериментальное исследование модели безошибочных вычислений на основе системы остаточных классов на параллельной мультикомпьютерной сети «КУРС-2000», в результате которого показано, что быстродействие безошибочного решения систем линейных уравнений размерности от 1 до 100 в двух, четырех и восьмимодульной СОК увеличивается более чем на порядок.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ 1. Исмаилов Ш.А., Хачумов В.М., Оцоков Ш.А. Алгоритм решения систем линейных уравнений, по методу «цифра за цифрой» // Вестник Дагестанского государственного технического университета. Технические науки. Выпуск №4. -Махачкала, 2000. -С.92-97.

2. Исмаилов ША, Оцоков ША. Структура разрядно-параллельного устройства реализации алгоритма RSA // Доклады республиканской конференции ДНЦ РАН «Информационные и телекоммуникационные системы: интегрированные корпоративные сети». - Махачкала, 2001. - С. 57-61.

3. Исмаилов ША, Оцоков Ш.А. Разрядно-параллельный алгоритм и структура преобразования чисел из позиционной системы счисления в систему остаточных классов // Вестник. ДНЦ РАН. -

2001.-№9.-С. 40-43.

4. Оцоков ША, Исмаилов ША. Алгоритм вычисления элементарной функции в системе остаточных классов // Доклады научной конференции «Новые информационные технологии. Разработка и аспекты применения». - Таганрог,

2002.-С. 74-75.

5. Оцоков Ш.А. Алгоритм преобразования целых чисел из позиционной системы счисления в коды Гензеля // Объединенный паучный журнал. - М., 2002. - № 33. - С. 61-62.

6. Оцоков Ш.А. Алгоритм и структура разрядно-параллельного устройства для генерирования случайных чисел линейным конгруэнтным методом // Объединенный научный журнал. - М., 2002.-№33.-С. 59-60.

7. Дзегелёнок И. И. , Оцоков Ш.А. Экспериментальное исследование модели безошибочных вычислений на ПМК-сети КУРС 2000 // Сб. трудов международной научной конференции «Информационные средства и технологии» М.:МЭИ (ТУ), 2003.-С.103-106.

8. Оцоков ША. Алгоритм безошибочного суммирования чисел с фиксированной запятой. // Доклады научно-технической конференции «Новые информационные технологии» том 1, М.:МГАПИ, 2003. - С. 155-158.

18 0 *

2004-4

9. Оцоков Ш.А., Исмаилов Ш.А. Разрядно-параллельный алгоритм

и структура вычислительного устройства безошибочной 24178

обработки массивов числовых данных // Сб. трудов международной научной конференции «Информационные технологии в науке, образовании, телекоммуникации, бизнесе». - Украина, Крым, Ялта-Гурзуф, 2003.- С. 37-39.

10. Оцоков Ш.А., Исмаилов ША. Применение методов безошибочных вычислений в гидрологии // Доклады международной конференции «Параллельные вычисления в газовых и жидких средах» /на англ. яз./. - М., 2003. - С.206-208.

ВВЕДЕНИЕ.:.:.:.

ГЛАВА 1. МОДЕЛЬ БЕЗОШИБОЧНЫХ ВЫЧИСЛЕНИЙ КАК НАПРАВЛЕНИЕ РАЗВИТИЯ

ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ЭВМ.:.

1.1. Классы задач, определяющие необходимость перехода к безошибочным вычислениям.'.'.

1.2. Модель безошибочных вычислений на основе системы остаточных классов.!.

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

1.4. Цели и задачи диссертационного исследования.

1.5. Выводы.

ГЛАВА 2. РАЗРАБОТКА БАЗОВЫХ АЛГОРИТМОВ, ОБЕСПЕЧИВАЮЩИХ ВЫПОЛНЕНИЕ БЕЗОШИБОЧНЫХ ВЫЧИСЛЕНИЙ.

2.1. Алгоритмы целочисленной обработки в системе остаточных классов.

2.1.1. Преобразование целых чисел из позиционной системы счисления в систему остаточных классов.

2.1.2. Преобразование целых чисел из системы остаточных классов в позиционную систему счисления.

2.1.3. Целочисленная арифметика в системе остаточных классов.

2.2. Алгоритмы обработки чисел с фиксированной запятой в системе остаточных классов.

2.2.1.Преобразование чисел с фиксированной запятой в одномодульную систему остаточных классов.

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

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

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

2.2.5. Арифметика чисел с фиксированной 'запятой в многомодульной системе остаточных классов.

2.3. Выводы.'.!.;.;.

ГЛАВА 3. СТРУКТУРНАЯ ОРГАНИЗАЦИЯ УЗЛОВ ПРОЦЕССОРА ДЛЯ ОБРАБОТКИ ЧИСЕЛ ПО'СХЕМЕ БЕЗОШИБОЧНЫХ ВЫЧИСЛЕНИЙ.

3.1. Структурная организация устройств целочисленной арифметики в системе остаточных классов.

3.2. Принципы структурной организации основных узлов процессора, обеспечивающих безошибочную обработку чисел с фиксированной запятой.

3.3. Выводы.

ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНАЯ РЕАЛИЗАЦИЯ И ОЦЕНКА

ЭФФЕКТИВНОСТИ АЛГОРИТМОВ БЕЗОШИБОЧНЫХ ВЫЧИСЛЕНИЙ И СТРУКТУРНЫХ СХЕМ УСТРОЙСТВ.!

4.1. Сравнительные оценки временных и аппаратурных затрат разработанных структурных схем с известными.

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

4.3. Разработка программного модуля безошибочной обработки чисел в многомодульной системе остаточных классов с использованием параллельной мультикомпьютерной сети "КУРС-2000".

4.4. Применение разработанных алгоритмов для безошибочного решения системы линейных уравнений методом Гаусса.

4.5. Оценки аппаратной и программной реализации алгоритмов безошибочных вычислений в системе остаточных классов.:.!. 4.6. Опытное применение программы безошибочных вычислений для оптимизации суточных режимов каскада Сулакских ГЭС.

4.7. Выводы.:.'.

Одним из новых направлений развития средств вычислительной техники является разработка высокопроизводительных вычислительных устройств," сочетающих в себе современную элементную базу, развитое математическое обеспечение, достаточную емкость памяти и т.д [ 37 ].

Это обусловлено, в первую .очередь, необходимостью решения широкого спектра задач в реальном режиме времени, понятия которых приводятся в [ 53]. Такие задачи возникают, например, в аэродинамике [ 32 ], климатологии, машинной графике , ядерной физике , физике плазмы, энергетике [ 15 ].

В то же время следует отметить, что существующие высокопроизводительные ЭВМ удовлетворяют пользователей сегодня, но уже в ближайшие годы могут не соответствовать требуемым параметрам из-за постепенного роста сложности решаемых задач. [ 15, 70 ].

Однако, наряду со значительными успехами в истории архитектуры высокопроизводительных ЭВМ, традиционно функционирующих в двоичной системе счисления, еще недостаточно исследованы возможности, связанные с оптимизацией способов кодирования потоков числовых данных, с точки зрения повышения производительности [ 4 ].

Также следует отметить, что проблему повышения производительности ЭВМ необходимо решать в тесной взаимосвязи с задачей обеспечения заданной точности вычислений. Требование к высокой точности ЭВМ приобретает особую значимость при решении класса плохообусловленных задач , где не допускается накопление ошибок округления [16]. К таким задачам относятся, например, решение систем линейных уравнений с определителем близким к нулю, обращение матриц Гильберта и др. [44,83].

Значение ошибок округления можно уменьшить путем удлинения разрядной сетки сумматоров, что безусловно влечет за собой увеличение аппаратурных затрат и не приводит к полному устранению погрешности вычислений. Указанный факт требует поиска алгоритмических способов, связанных с применением новых нетрадиционных методов и систем счисления для представления и обработки чисел [ 3 ].

В [21] показывается, что это можно достичь, прежде всего, средствами специального кодирования, наиболее широкий интерес из которых представляет собой система остаточных классах (СОК). Ей присущи высокая скорость вычислений и точность результатов [1,2, 3].

В то же время практическая применимость СОК сдерживается рядом проблем, связанных со сложностью сравнения чисел, введения знака,

I • преобразования в позиционную систему счисления [ 3 ].

Многочисленные работы в области непозиционных систем' и математического аппарата теории чисел позволили выделить новое научное направление - теорию безошибочных вычислений [21, 101-104 ].

Существенный вклад в развитие теории внесли работы Р. Грегори, Е. Кришнамурти , О. Ватануки, А. Фромента, посвященные безошибочным вычислениям в системе остаточных классов и с использованием кодов , Гензеля [21,66,105,119,122,123,139, 140 ].

Известны также работы, посвященные исследованиям знакоразрядной системы счисления и диадических рациональных чисел, называемых также «псевдо-цифрами» для безошибочных вычислений с плавающей запятой [138].

В работах Д. Вуллинина, А.Нильсона, П. Корнерупа, Р.Хэкмана развиваются алгоритмы безошибочных вычислений над числами с плавающей запятой [112,123,118,119].

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

Объединение достоинств системы остаточных классов для безошибочных вычислений, табличной арифметики и разрядно-параллельных принципов обработки информации получило свое развитие в работе [ 4 ].

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

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

Следует отметить, что основными проблемами безошибочных вычислений, сдерживающими их применение на практике, являются невысокое быстродействие, отсутствие метода выбора модулей системы остаточных классов, рост разрядности операндов [112].

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

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

ЦЕЛЬ ДИССЕРТАЦИОННОЙ РАБОТЫ заключается в исследовании модели безошибочных вычислений в системе остаточных классов и ее усовершенствованию в направлении создания высокопроизводительных ЭВМ.

ПРЕДМЕТОМ ИССЛЕДОВАНИЯ является модель безошибочных вычислений в системе остаточных классов и её алгоритмическая, аппаратная и программная реализация.

МЕТОДЫ ИССЛЕДОВАНИЯ опираются на положения теории чисел, алгебры логики, линейной алгебры, компьютерных систем программирования для последовательных и параллельных ЭВМ, теорию алгоритмов и организации вычислительных процессов, теорию автоматов.

НАУЧНАЯ НОВИЗНА данного диссертационного исследования заключается в разработке модели безошибочных вычислений с рациональными числами в СОК, отличающейся от ранее известной "введением индексов, антииндексов, расширением диапазона представления искомых результатов, а также получением верхней оценки модуля СОК, для частных задач.

На защиту выносятся следующие результаты:

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

- Ускоренный алгоритм деления в многомодульной СОК на основе таблиц индексов и антииндексов.

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

- Метод организации безошибочных вычислений с расширением диапазона представления искомых результатов в классе дробей Фарея порядка N с модулем г в СОК, определяемого исходя из следующего неравенства: N < р - 1, вместо д, ^р -' .

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

- Результаты экспериментального исследования модели безошибочных вычислений в многомодульной СОК с использованием параллельной мультикомпьютерной сети «КУРС-2000», разработанной на кафедре ВМСиС МЭИ (ТУ).

- Сравнительные оценки быстродействия аппаратной и программной реализации алгоритмов безошибочных вычислений в СОК.

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ

Разработана программа безошибочного решения системы линейных уравнений в одномодульной системе остаточных классов (свидетельство гос. регистрации №2003610764 в реестре, программ для ЭВМ). Программа безошибочного решения системы линейных уравнений в одномодульной СОК нашла применение в ОАО «Дагэнерго» и включена в состав комплекса программ "Расчет суточных режимов Сулакского каскада ГЭС",, что подтверждено соответствующим актом о внедрении. I

Экспериментальное исследование, проведенное в ОАО «Дагэнерго» ' показало, что использование разработанной программы- безошибочных вычислений позволило уточнить прогностическую оценку уровня воды в нижнем бьефе Чйрюртовской ГЭС более чем на 2% по сравнению с используемой на практике программы «Расчет добегания расхода воды».

Результаты диссертационного исследования также используются в учебном процессе Дагестанского государственного технического университета по специальностям 22.01 и 22.04, имеется акт о внедрении.

АПРОБАЦИЯ РАБОТЫ.

•Основные результаты работы докладывались и обсуждались на :

- Республиканской научно-технической конференции «Информационные и телекоммуникационные системы: интегрированные корпоративные сети» («Дагинформ-2001» г. Махачкала, 2001 г.)

- Всероссийской научной конференции с международным участием молодых ученых и аспирантов «Новые информационные технологии. Разработка и аспекты применения» ( г.Таганрог, 2002 г.)

- Всероссийской научно-технической конференции «Новые информационные технологии» ( г. Москва, 2003 г.)

- Международной научной конференции «Информационные технологии в науке, образовании, телекоммуникации, бизнесе» ( Украина, Крым, Ялта-Гурзуф, 2003 г.)

- Международной научной конференции «Информационные средства и технологии» ( г. Москва, 2003 г.)

- Международной" научной конференции. Parallel Computational Fluid Dynamics ( г. Москва, 2003 г.)

ПУБЛИКАЦИИ. По материалам диссертационной работы опубликовано 11 трудов, в том числе 5. статьи, 6 тезисов докладов. Получено свидетельство о регистрации программы и поданы 3 заявки на предполагаемые изобретения в области вычислительной техники.

СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИИ . Диссертационная работа ' состоит из введения, 4 глав, заключения, списка литературы и приложения. Она изложена на 140 сраницах основного машинописного текста, содержит 42 рисунка, 18 таблиц, включает библиографию из 143 наименований. Общий объем диссертации составляет 264 страниц.

Основные результаты данной работы состоят в следующем:

1. Уточнены классы задач, требующие повышенной точности вычислений на ЭВМ и .среди которых один из важнейших - задачи большой размерности.

2. Усовершенствованы алгоритмические принципы прямых и обратных преобразований чисел из позиционной системы счисления в одномодульную и многомодульную СОК.

3. Разработан ускоренный алгоритм ( по сравнению с расширенным алгоритмом Евклида) нахождения обратного числа в многомодульной СОК на основе таблиц индексов и антииндексов .

4. Разработан метод организации безошибочных вычислений с расширением диапазона представления искомых результатов в классе дробей Фарея порядка N с модулем Р в СОК, определяемого исходя из следующего неравенства: N < Р - 1 , вместо N <

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

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

J?быстродействие предлагаемых устройств в несколько раз выше. При разработке структурных схем устройств использовались разрядно-параллельные принципы и табличная обработка данных. 7. Проведено экспериментальное исследование модели безошибочных вычислений на основе системы остаточных классов на параллельной мультакомпьютерной сети «КУРС-2000». * • *

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

- разработка быстродействующих алгоритмов безошибочных вычислений с числами с плавающей запятой;

- решение проблемы, связанной с большими затратами памяти для хранения операндов.в ходе безошибочных вычислений;

- разработка сопроцессора безошибочных вычислений с числами с плавающей запятой.

ЗАКЛЮЧЕНИЕ

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

1. Аветисян A.M. Некоторые новые методы построения корректирующих кодов. /.Диссерт. на соиск. учен, степени к.ф-м.н. Ленинакан, 1981.

2. Акушский И.Я., Амербаев В.М., Пак И.Т. Основы машинной арифметики комплексных чисел. Алма-Ата, Наука, 197Ö.- 250 с.

3. Акушский Н.Я, Юдицкий Д.И. Машинная арифметика в остаточных классах, М. «Сов. радио », 1968. 439 е.

4. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 536 с.

5. Бадман О.Л.,Миренков H.H. и др. Специализированные процессоры для высокопроизводительной обработки данных. Новосибирск: Наука, 1988. -207 с.

6. Байков В.Д. Смолов В.Б. Аппаратурная реализация элементарных функций в ЦВМ. Л.: Издательство Ленинградского университета, 1975. -96 с.

7. Байков В.Д. Смолов В.Б. Специализированные процессоры. Итерационные алгоритмы и структуры. М.: Радио и связь, 1985. - 288 с.

8. Ю.Балашов Е.П., Кокаев О.Г., Петров Г.А., Пузанков Д.В., Смагин A.A. Операционные устройства и процессоры с табличным методом обработки информации. УСим, N 5, 1975.- с.16-21.

9. П.Балашов Е.П., Негода В.Н., Пузанков Д.В., Смагин A.A., Смолов В.Б. Информационные системы. Табличная обработка информации. Л.: Энергоатомиздат, 1985. - 180 с.

10. Барашенков B.B., Кокаев О.Г., Тарасов В.Г., Темирханов Т.Э. Способ ускорения арифметических вычислений.- Известия вузов. Приборостроение, 1983, т.26, N 9, с.26-30.

11. Бахвалов Н.С, Жидков Н.П, Кобельков Г.М. Численные методы. Учеб.Iпособие. М.: «Наука». Гл. ред. физ.-мат. лит., 1987. - 600 с. М.Виноградов И.М. Основы теории чисел. - М.: «Наука», 1972. - 456 с.

12. Воеводин В.В, Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. - 608 с.1

13. Воеводин В.В. Вычислительные основы линейной алгебры. М.: «Наука», 1977. :303 с.

14. Воеводин В.В. Линейная алгебра. М.: «Наука», 1980. -400 с.

15. Воеводин В.В. Математические модели и методы в параллельных процессах. М.: «Наука», 1986'. - 296 с.

16. Гербер К.Дж. Архитектура высокопроизводительных систем/ пер. с англ.-М.: Наука. 1985,272 с.

17. Головкин Б.А. Параллельные вычислительные системы,- М.: Наука,. 1980.- 520 с.

18. Грегори Р, Кришнамурти Е. Безошибочные вычисления. Методы и приложения.М.:Мир,1988. -207 с.

19. Грэхем Р, Кнут Д, Паташник О. Конкретная математика. Основание информатики: Пер. с англ. М.: «Мир», 1998. - 703 с.

20. Давыдов O.E. Разработка и исследование шифраторов и цифровых фильтров для абонементской связи в системе остаточных классов. / Диссерт. на соиск. учен, степени канд. наук: 05.13.05/ Йошкар-Ола, 2000. 127 с.

21. Дадаева И.Г. Исследование помехоустойчивых свойств остаточных кодов в позиционной и непозиционной системах счисления. / Диссерт. на соиск. учен, степени к.т.н. М., 1978.

22. Демидович Б.П, Марон И.А. Основы вычислительной математики. М.: «Наука». Гл. ред. физ.-мат. лит., 1970. - 664 с.

23. Деревенское С.О. Разработка и исследование класса аппаратурно-ориентированных алгоритмов решения, систем линейных алгебраических уравнений. / Диссерт. на соиск. учен, степени к.т.н. Волгоград^ 1995 - 217 с.

24. Дзегелёнок И.И., Оцоков Ш.А. «Экспериментальное исследование модели безошибочных ' вычислений на ПМК-сети КУРС 2000» '// Сб. трудов международной научной конференции «Информационные средства и технологии» М.:МЭИ (ТУ), 2003, С. 103-106.I

25. Дзегелёнок И.И., Оцоков Ш.А. «О распараллеливании безошибочных вычислений на ПМК-сети КУРС 2000» // Электронный • журнал. Вычислительные сети. Теория и практика, http://network-journal.mpei.ac.ru

26. Евдокимов В.Ф., Стасюк А.И. Вычислительные системы на основе разрядной интерпретации обрабатываемой информации. // Электр, моделир., N4,1986.- с.33-41.

27. Егоров В.М., Косцов Э.Г. Перспективы создания цифровых высокопроизводительных вычислительных устройств.//Автометрия, N 1, 1985.-с.114-125. '

28. Журкин В.А. Синтез быстродействующих устройств, использующих системы счисления в остаточных классах на многозначных элементах. / Диссерт. на соиск. учен, степени к.т.н. -Ленинград, 1973. 202 с.

29. Забродин A.B., Луцкий А.Е. Марбашев К.Х, Чернов Л.Г. Численное обследование обтекания летательных аппаратов и их элементов в реальных полетных режимах // Общероссиский научно-техн. журнал «Полет». 2001. -№7- С.21-29.

30. Ильин В.А, Позняк Э.Г. Линейная алгебра. М.: «Наука». Гл. ред. физ.-мат. лит., 1974. -296 с.

31. Инютин С.А. Исследование методов кодирования, декодирования помехозащищенных кодов системы остаточных классов / Диссер. на соиск. учен, степени к.т.н. Алмата: 1982.

32. Ирхин В.П. Теоретическое обобщение и разработка методов построения непозиционных модулярных спецпроцессоров: Диссерт. на соиск. учен, степени д.т.н. / Воронеж, 1999.

33. Исмаилов Ш-М. А. . . Теория и применение разрядно-параллельных процессорных элементов обработки числовых данных в комплексе систем счисления . / Диссерт. на соиск. учен, степени д.т.н. Махачкала : 1996. 535 с.

34. Исмаилов Ш-М.А., Артамонов Е.И., Кокаев О.Г., Хачумов В.М. Специализированные алгоритмы й устройства обработки массивов данных. Махачкала, Дагестанское книжное издательство,. 1993. 304 с.

35. Исмаилов Ш-М.А., Оцоков Ш.А. Разрядно-параллельный алгоритм .и структура преобразования чисел из позиционной системы счисления в систему остаточных классов. // Вестник. ДНЦ РАН. 2001.№9.С. 40-43

36. Исмаилов Ш-М.А., Хачумов В.М., Оцоков Ш.А. Алгоритм решения систем линейных уравнений по методу «цифра за цифрой» // Вестник Университета. Тех. науки/ ДГТУ. Махачкала, 2000. - С.92-97

37. Казангапов А. H Функциональные вычисления в системе остаточных классов / Диссерт. на соиск. учен, степени к.т.н. Алма-Ата, 1968. - 127 с.

38. Касаткин В.Н. Новое о системах счисления . Киев : В.школа, 1982,-96 с.

39. Каханер Д.,. Моулер К, Нэш С. Численные методы и программное обеспечение.-М.: Мир, 2001. 575 е., ил.

40. Кисленко B.C. Разрядно-параллельные процессоры арифметической и логической обработки радиолокационной информации. Дисс. на соиск. уч. степ, к.т.н. Л.: ЛЭТЙ, 1989, - 171с.

41. Кнут Д. Э . Искусство программирования, том 2. Получисленные алгоритмы, 3-е изд.: Пер. с англ.: Уч. пос. М.: Издательский дом «Вильяме», 2001. - 832 с.I

42. Коблиц Н. Р-адические числа, р-адический анализ и дзета-функции / Пер. с англ.-М.: Мир, 1982. с. 24-35.

43. Кокаев О.Г. , Развитие и применение ассоциативных вычислений и структур. Дисс. на соиск. уч. степ, д.т.н. Л.:ЛЭТИ, 1989, - 498 с. ,

44. Коляда A.A. Модульные структуры конвейерной обработки числовой информации. Минск: Университетское, 1990.- 331 с.

45. Коляда А. А. Иктервально-модулярные коды с исправлением ошибок//Вестн. Белорус, ун-та. Сер. 1. Физ. Мат. Мех. 1988. № 2. С. 33 -36.

46. Коляда А. А., Селянинов М. Ю. О контроле модулярных вы числительных устройств конвейерного типа//Всесоюз. совет. «Конвейерные вычислительные системы» (Киев, 18-19 сект., 1985): Тез докл. и сообщ. Киев, 1985. С. 91 -93.

47. Коляда А. А., Селянинов М. Ю. О формировании интегральных характеристик кодов систем в остатках с симметричным диапазоном// Кибернетика. 1986. № 4. С. 20 24.

48. Коляда A.A. Модулярные структуры конвейерной экспресс — обработки цифровой информации в измерительно-вычислительных системах физического эксперимента. / Диссерт. на соиск. учен, степени д.т.н. -Минск: 1991.

49. Коляда A.A. О ядре числа в системе остаточных классов // Кибернетика. 1982. №2. С. 123-125.l

50. Коляда A.A. Обобщенные системы остаточных классов. / Диссерт. на соиск. учен, степени канд.физ.-м'ат.наук: 01.01.09 / Белор. гос университет. -Минск, 1973.- 149 с.

51. Коляда A.A., Пилиповец Ф.С. • О нахождении оснований систем<остаточных классов // Теория и применение мат. машин. Мн.: Изд-во БГУ им. В. И. Ленина, .1972. С 16-28

52. Краснобаев В.А., Ирхин В.П. Алгоритм реализации операции модульного умножения в системе остаточных кла'ссов.//Электр. моделир., N 5, 1993.-с.20-27.

53. Луцкий С.А. Исследование особенностей проектирования и разработки быстродействующих аппаратных средств реализации элементарных функций с высокой точностью. / Дисс. на соиск. уч. степ, к.т.н. Л.: 1982, -238 с.

54. Маккелан Дж.Х., Рейдер Ч.М. Применение теории чисел в цифровой обработке сигналов. М.: Радио и связь. 1983.- 252 с.

55. Марковский А.Д: Структура вычислительных систем с точки зрения точности и алгебраических критериев качества вычислений. / Диссерт. на соиск. учен, степени к.т.н. М., 1979.

56. Михелович Ш.Х. Теория чисел. М. «Высшая школа», 1962. 259 с.

57. Михлин С.Г. Некоторые вопросы теории погрешностей. Л.: Издательство Ленинградского университета. 1988. - 333 с.

58. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2001.-304 с.

59. Перспективы использования параллельной архитектуры для создания ЭВМ со сверхвысокой производительностью. Экспресс-информация. Сер. вычислительной техники. М.: ВИНИТИ, 1985, N 27, с. 1-14.

60. Прангишвили И.В., Виленкин С.Я., Медведев И.Л. Параллельные вычислительные системы с общим управлением,- М.: Энергоатомиздат, 1983,-312 с.

61. Преобразователь позиционного кода в код системы остаточных классов: Пат. 1557682. AI, 5 H 03 M 7/18 / В.А. Краснобаев, O.A. Финько, Н.И.Швецов ( СССР) №4450764; Заявл. 27.06.1988; Опубл. 15.04.1990. -Бюл. №14 - 3 с.

62. Преобразователь числа из кода системы счисления в остаточных классов в двоичный код: Пат. 1541783. AI, 5 H 03 M 7/18 / Ш-М.А. Исмаилов, Э.Х. Хаспулатов ( СССР) №4404695; Заявл. 04.04.1988; Опубл. 07.02.1990. -Бюл. №5 - 3 с.t

63. Савельев А.Я. Арифметические и логические основы цифровых автоматов: Учебник. М.: Высш.' школа, 1980. - 255 с.

64. Самарский А.А Николаев Е.С. Методы решения сеточных уравнений. -М.: «Наука», 1978. 589 с.

65. Селетков С.Н., Волков Б.Г. Хранение и поиск данных в ЭВМ.- М.: Сов. радио," 1971,276 с.

66. Смичкус .Е.А., Баранов B.JI. О преобразовании чисел системы остаточных классов в позиционный код.// У.СиМ, N 7,8,1992.- с.31-36.

67. Соренков Э.И. и др. Точность вычислительных устройств и алгоритмов.--М.: Машиностроение, 1976.- 200 с.

68. Стасюк А.И. Организация однородных матричных процессоров.//Электр. моделир., N 6,1985, с.20-28.

69. Суейдан Л.И. Исследование и разработка функциональной организации матричых и таблично-матричнь!х устройств для вычисления элементарных функций. Дисс. на соиск. уч. степ, к.т.н.- Л.: 1981.

70. Суммирующее устройство по модулю : Пат. 2034328. AI, 6 G.06 F 7/49 / Ш-М.А. Исмаилов, А.А Джанмурзаев, Э.Н. Курбанов (СССР) -№930112221; Заявл. 01.03.1993; Опубл. 30.04.1995.- Бюл. №12. 3 с.

71. Суммирующее устройство: A.C. 1062689. СССР, МКИ G 06 F 7/50. /Ш-М.А. Исмаилов, И.А. Айдемиров, О.Г. Кокаев, Т.Э. Темирханов. № 3502589/24-24; Заявл. 20.10.82; Опубл. 23.12.83. - Бюл. № 47.

72. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. М.: «Наука», 1986. -288 с.

73. Торгашев В.А. Система остаточных классов и надежность ЦВМ. М.: Сов. радио, 1973. 120 с

74. Устройство для преобразования числа из системы остаточных классов в позиционный код : Пат. 1501280. AI, 4 Н 03 М 7/18 / С.Н. Литвинов ( СССР) №4337158; Заявл. 03.12.1987; Опубл. 15.08.1989 - Бюл. №30 - 3 с.

75. Фет Я. И. Параллельные процессоры для управляющих систем. -М.:Энергоиздат, 1981. 160 с.

76. Фет Я.И. Вертикальная . обработка как основа крупноблочной архитектуры. //Техническая кибернетика. М. 1986. N 5. с.139-158.

77. Фет Я.И. Массовая обработка информации в специализированных однородных процессорах. Новосибирск: Наука, 1976,240с.I

78. Форсайт Дж., Малькольм М., Моулер К. Машинные методы математических вычислений. М.: Мир, 1980. - 276 с.

79. Шауман A.M. Основы машинной арифметики. -JI: Изд-во ЛГУ, 1979. -312 с.I

80. Aaron. R, Houg Т. L. Capps С. D. Optical computing using residue arithmetic//AIAA Comput. Aerosp. 6 Conf. (Wakifield. Mass., 7-9 Oct;, 1987). Collect Techn. Pap. Washington, D. C., 1987. P. 207 212.

81. Bayoumi M. A. A quadratic residue processor for complex DSP applications //ICASSP'87: Proc. Int. Conf.' Acoust., Speech and Signal Process. (Dallas, Tex. 6-9 Apr. 1987). 1987. Vol. 1. New York. P. 475 478.

82. Blum L. , Cucker F. , Shub M. and Smale S. Complexity and real computation, New York: Springer-Verlag. (1998).

83. Blum' L. , Shub M. and Smale S. On a theory of computation and complexity over the real numbers. Amer. Math. Soc. Bull. 21:1-46 (1989).

84. Boehm H and Cartwright R. Exact real arithmetic, formulating real numbers as functions. In David A. Turner, editor, Research Topics in Functional Programming, chapter 3,Addison-Wesley, 1990, pages 43-64.

85. Boehm H. J., Cartwright R., O'Donnel M. J. and Riggle M. Exact real arithmetic, a case study in higher order programming. Proc. of the ACM conference on Lisp and functional programming, 1986.August, P. 162-173.

86. Chang P. R., Lee C. S. G. Residue arithmetic VLSI arra. architecture for manipulator pseudo-inverse Jacobian computation Proc. IEEE Int. Conf. Rob. and Autom. (Philadelphia. Pa, 24-29 Apr. 1988). 1988. Vol. 1. Washington, D. C. P. 297-302.

87. Clemens K. A modified definition of symmetric RNS improving scaling and overflow detection //IEEE Trails, on Circuits and Syst. 1985. Vol. CAS-32, N 4. P.412- 413.

88. Di-Gianantonio. P. A Functional Approach to Computability on Real Numbers ,i •

89. PhD thesis, Universitá Degli Studi di Pisa, Dipartamento di Informática, 1993.

90. Dixon" J. D. Exact solution of linear equations using p-adic expansions. Number. Math., 40, 1982,137-141."

91. Edalat A and Potts P J. A new representation for exact real numbers. Electronic Notes in Theoretical Computer.Science, 6, 1997.

92. Edalat A. Domains for computation in mathematics, physics and exact real arithmetic. Symbolic Logic. Bull, 3(4):401-452 (1997).

93. Edalat A and M.H. Escardó. Integration in Real PCF. // In Proceedings of the Eleventh Annual IEEE Symposium ón Logic In Computer Science, New Brunswick, New Jersey, USA, 1996, p 382-393

94. Escardó M.H. PCF extended with real numbers: A domain-theoretic approach to higher-order exact real number computation. Technical Report ECS-LFCS-97-374, Department of Computer Science, University of Edinburgh, December 1997.

95. Froment A. Error Free Computation: A Direct Method to Convert Finite-Segment p-Adic Numbers into Rational Numbers // IEEE Trans, on comput., 1983, Vol. C-32, N 4, P 337-343.

96. Gregory R. T. A. method for and an application of error-free computations. • Proceedings of the AFCET Symposium «Mathematics for Computer Science». Paris, 152-158,1982.

97. Gregory R. T. Error-free computation with rational numbers. BIT, 21, 1981b, 194-202.

98. Gregory R. T. Exact computation with order-N Farey fractions. Computer Science and Statistics: Proceedings of the 15th Symposium on the Interface. J. E. Gentle Editor, North Holland, Amsterdam, 1983.

99. Gregory R. T. Residue arithmetic with rational operands. Proceedings 5th Symposium on Computer Arithmetic. IEEE Computer Society; Ann Arbor, Michigan, 144-145,1981a. ' ■

100. Gregory R. T. The use of Finite-segment p-adic arithmetic for exact computation. BIT, 18,1978,282-300. •

101. Gregory R. T., Matula D., W. Base conversion in residue number systems//BTT. 1977. Vol. 17. P. 286-302.

102. Heckmann R . The appearance of big integers in exact real arithmetic based on linear fractional transformations. In Proc. Foundations of Software Science and Computation Structures, Lisbon, 1998.

103. Hehner E. C. R., Horspool R. N. S. A new representation of the rational numbers for fast easy arithmetic. SIAM J. Comp., 8, 1979,124-134.

104. Howell J. A., Gregory R T. An algorithm for solving linear algebraic equations using residue arithmetic. Parts I and II. BIT, 9, 1969, 220-224.

105. Kinoshita E., Kosako H., Kojima Y. Floating-point arithmetic algorithms'in the symmetric residue number svstem//IEEE Trans. Comput. 1974. Vol. C-23, N 1. P. 9-20.

106. Klnoshua E., Kosako H., Kofirna Y. General division in the syrnmetris residue number system // IEEE Trans. Comput. 1973. Vol. C-22, N 2.P.134-142.

107. Kokaev O.G., Kislenko V.S., Ameho D. Parallel execution of logical operations in associative processor // IEE Proceedings-E. Computers and Digital Techniques.- London, 1989.

108. Kornerup P. and Matula D.W. Finite Precision Rational Arithmetic: An Arithmetic Unit// IEEE Trans, on comput., 1983, Vol. C-32, N 4, P. 378-397.

109. Kornerup Pr and Matula D. An algorithm for redundant binary bitpipelined rational arithmetic. IEEE Transactions on Computers, 39(8): 1106-1115, August 1990.

110. Krishnamurthy E. V. On optimal iterative schemes for high speed division. IEEE Transactions on Computers, C-19, 1970,227-231.

111. Krishnamurthy E. V., Adegbeyeni E. 0. Finite field computational techniques for the exact solutions of mixed-integer linear equations. Inter. J. Syst. Sci., 8,1977,1181-1192.

112. Krishnamurthy E.V. On the conversation of Hensel Codes to Farey Rationals//IEEE Trans, on comput., 1983, Vol. C-32, N 4, P 331-336.

113. Miola A. M. The conversion of Hensel codes to their rational equivalents. ACM Sigsarn Bulletin, Nov. 1982, 24-26.

114. Nielsen A. M. and Kornerup f\ MSB-first digit serial arithmetic. Journal of Universal Computer Science, l(7):527-547, 1995.

115. Ong S. and Atkins D.E. A Basis for the Quantitative Comparison of Computer Number Systems // IEEE Trans, on comput., 1983, Vol; C-32, N 4, P 359-369.

116. Otsokov S.A. , Ismailov S-M.A. "Application of Methods Error-free Calculations in Hydrology " // International Conference on Computational Fluid Dynamics, ICCFD, Moscow, Russia, 2003, P. 206-208.

117. Potts P. J. and Edalat A . Exact real computer arithmetic. Imperial College, March 1997. '

118. Potts P. J., Edalat A., and Escardo M. H. Semantics of exact computer arithmetic. In Twelfth Annual IEEE Symposium on Logic in Computer Science, Warsaw, Poland, 1997, P. 248-257.

119. Pour-el M.B. and Richards I. Computability and non-computability in classical analysis. Trans. Am. Math. Soc., P. 539-560, 1983.

120. Rao T. M. Error-free computation of characteristic polynomial of a matrix. Comp. and Math, with Appl., 4, 1978, 61-65.

121. Rao T. M. Finite field computational techniques for exact solution of numerical problems. Ph. D. Dissertation. Department of Applied Mathematics, Indian Institute of Sciences, Bangalore, 1975.

122. Rao T. M., and Gregory R. T. The conversion of Hensel codes to rational numbers. Proceedings 5th Symposium on Computer Arithmetic, IEEE Computer Society, Ann Arbor, Michigan, 1981, 10-20.

123. Rao T. M., Subramanian К., and Krishnamurthy E. V. Residue arithmetic algorithms for exact computation of q-inverses of matrices, SIAM J. Numer.• Anal., 13,1976,155-171.

124. Shooman W. Parallel computing with vertical data / AFIPS Confer. Proc. //EJCC.- 1960.-Vol. 18.-P.111-115. '1.•

125. Smyre J. S. Exact computation using extended-precision single-modulus residue arithmetic. M. S. Thesis. Department of Computer Science, Universityof Tennessee, Knoxville, 1983.

126. Soderstrand M. A. Escott R. A. VLSI implementation in multiple-valuedIlogic of an FIR digital filter iising residue number system arithmetic//IEEE Trans, on Circuits and Syst. 1986. Vol. CAS-33, N 1. P. 5-20.

127. Szabo N. S., Tanaka R. 1. Residue Arithmetic and its Applications ' to Computer Technology. McGraw-Hill, New. York, 1967.

128. Taheri M., lulliên G. A. Miller U". C. SvMolic ROM arrays for implementing RNS FIR filter // ICASSP'87: Proc. Int. Conf. Acoust. Speechand Signal Process. (Dallas, Tex. 6-9 Apr., 1987). 1987. Vol. 2. New York. P. 771-774.

129. Tayior F. J., Huang C. H. A comparasion ol DFT algorithms using residue architecture//Comput. Elect. Eng. 1981. Vol. 8 , N 3. P. 161 171.

130. Vuillemin J. E. . Exact real computer arithmetic with continued fractions. IEEE Transactions on Computers, 39(8):1087-1105, August 1990.

131. Vimawala A. p-adic Arithmetic Methods for Exact Computation of Rational Numbers. // Scholl of Electrical Engineering and Computer Science, Oregon• State University, 2003

132. Watanuki O. and Ercegovac M.D. Error Analysis of Certain Floating-Point On- Line Algorithms // IEEE Trans, on comput., 1983, Vol. C-32, N 4, P. 352358.