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

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

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

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

систем управления 05.13.15. - Вычислительные машины, комплексы и компьютерные сети

АВТОРЕФЕРАТ

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

0 3 ОЕЗ 2077

Москва-2010

4853690

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

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

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

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

доктор технических наук, профессор Дзегелёнок Игорь Игоревич доктор технических наук, профессор Амербаев Вильжан Мавлютинович доктор технических наук, профессор Борисов Вадим Владимирович доктор технических наук, профессор Горбатов Александр Вячеславович Федеральное государственное унитарное предприятие «НИИ «Квант»

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

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

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

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

Учёный секретарь

диссертационного совета л? .

к.т.н., доцент •—• С.А. Чернов

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

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

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

Один из традиционных способов борьбы с ошибками округления - применение высокоточных вычислений. В настоящее время существует множество библиотек, поддерживающие высокоточные вычисления: гЯЕАЬ (Россия), МРАБ1ТН (Германия), СМР (США) и др.

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

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

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

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

процессе вычислений. Недостатками этой системы являются сложность сравнения, деления, округления чисел.

Существенный вклад в развитие теории модулярных вычислений внесли в нашей стране работы Акушского И.Я, Юдицкого Д.И, Амербаева В. М, Коляда А.А, Червякова Н.И, Финько O.A. и др, среди зарубежных можно выделить работы М.А. Soderstand, D.D.Miller, G.A. Jullien, M.A. Jenkins, B.J. Leon и др.

Модулярные вычисления развиваются как в теоретическом, так и прикладном направлении.

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

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

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

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

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

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

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

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

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

3. Разработка единого формата предста&тения рациональных и комплексно-рациональных чисел на основе теоретических обобщений в модулярной системе счисления.

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

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

6. Анализ эффективности разработанных алгоритмов и структурных схем устройств., реализующих высокоточные вычисления.

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

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

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

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

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

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

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

1 Пункты2-5, 8,9 - поспециальности05.13.05, пункты6,7,10-по 05.13.15

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

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

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

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

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

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

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

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

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

2. Разработана библиотека, которая может найти применение при:

- проведении высокоточных вычислений с дробными и комплексными числами в таких областях как: электротехника, энергетика и др.;

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

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

Результаты работы внедрены в институте системного анализа РАН, в учебном процессе в Московском энергетическом институте (ТУ), в НПО «Энергонаука», а также нашли применение в Межрегиональной распределительной сетевой компании Северного Кавказа, институте

2 Пункт 1 - по специальности 05.13.05, пункт 2 - по 05.13.15

проблем геотермии Дагестанского научного центра РАН, что подтверждено соответствующими актами о внедрении.

Диссертационная работа выполнена при поддержке

• Гранта Президента РФ для молодых кандидатов наук МК-65190.2010.9

• Государственного контракта № 02.442.11.7546 по приоритетным направлениям, выполняемых в рамках программного мероприятия 1.9 "Проведение молодыми учеными научных исследований по приоритетным направлениям науки, высоких технологий и образования" федеральной целевой научно-технической программы "Исследования и разработки по приоритетным направлениям развития науки и техники" на 2002-2006 годы.

- т^---— ттттт тапчшпп итт--------------- ---------гг__________________у. „

— Í ponía Í 1111- / i\j.y A juiannpvjоапль шашшипшл aoiincjifc-nfm n

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

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

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

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

Апробация работы. Основные результаты работы докладывались и обсуждались на

- Юбилейной международной научной конференции "50 лет модулярной арифметике" (МИЭТ, Зеленоград, 2005 г.)

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

- Всероссийской научно-технической конференции "Микроэлектроника и информатика (МИЭТ, Зеленоград, 2006 г.)

- Международной конференции «Параллельные вычисления и задачи управления» ( РАСО 2006, г. Москва, 2006 г.)

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

- Международной научной конференции «Параллельная компьютерная алгебра» (Parallel Computer Algebra 2010, г. Тамбов, 2010 г.)

Публикации. Опубликовано 27 печатных работ, в том числе 18 работ при подготовке данной диссертационной работы, 12 статей, из них 8

в журналах, одобренных ВАК, 6 тезисов докладов. Получены 3 патента на изобретения в области вычислительной техники.

Структура и объем диссертации. Диссертация состоит из введения, семи глав, заключения, списка литературы из 126 наименований и приложения и изложено на 287 страницах машинописного текста, содержит 72 рисунка и 13 таблиц.

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

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

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

Один из основных недостатков формата с плавающей точкой -неравномерное распределение чисел внутри диапазона представления (рисунок 1). На рисунке 1 показано распределение чисел с плавающей точкой в двоичной системе счисления, с длиной мантиссы 3 разряда, и порядком, который принимает значения от -1 до 2. В формате с плавающей точкой с данной длиной мантиссы и порядком число 9 не представимо.

1 1 ! 1 1 1 : ! ! ! 1 ш !Н! 1 ! 11Н 111 1 I ! 11 1 1 | ! I ....................¿.

1...........1 1 ! I 1 ! 1 I 1 ! II! М \ 1II!! 1(1 1 ! 1 1 1! 1 1 1 1 1 I

-3 -2 -1 1 2 3 4

Рисунок 1. Неравномерное распределение чисел с плавающей точкой

Неравномерное распределение чисел может приводить к сильной потере точности компьютерных вычислений при решении вычислительных

задач с разномасштабными коэффициентами. Так, например, скалярное

--> —>

произведение векторов к, у с координатами:

х = (10",1223 ,10 18,10 15, 3, -1012), у = (Ю20, 2, -1019, 10", 2111, 1016)равно 8779, а вычисленное в арифметике с плавающей точкой одинарной

точности (стандарт IEEE 754) равно 4.61168602259351Е+0020.

Потеря точности компьютерных вычислений может происходить и при выполнении арифметических операций с комплексными числами на ЭВМ, распределение представимых комплексных чисел в формате с плавающей точкой в диапазоне [-Fmax, Fmax; -iFmax,iFmax] показано на. рисунке 2.

I Fmax

1

1

i—i-i- J-

t—№ н —?-1

! 1

1

1 1 1

-i Fmax

Рисунок 2. Неравномерное распределение комплексных чисел с плавающей точкой

Другой недостаток формата с плавающей точкой неоднозначным представлением целых и дробных чисел, например, число 1 можно представить, как целое и как бесконечную дробь: 1=0,(9)=0,999... Из-за чего в современных языках программирования (С++, Pascal и др.) условие для проверки равенства двух переменных: if А = В then ..., где переменная А имеет тип float (число с плавающей точкой), В - целое число, или А, В - имеют тип float некорректны. Вместо проверки условия if А = В then ... иногда используется выражение вида if abs(A - B)<=eps then ... и др., но в них вводится параметр eps, который не всегда легко определить. Неоднозначное представление целых и дробных чисел усложняет реализацию алгоритмов, где используются проверки равенства переменных различных числовых типов данных.

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

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

Задачи критичные к нарушению алгебраических свойств

'.■"-■'-'

Плохо обусловленные задачи

Задачи с . : разномасштабными ' коэффициентами

. . Задачи чувствительные к классу эквивалентных |

преобразований - !

1_

Задачи чувствительные к ' : изменению шага дискретизации

' ./Дискретное."-7 преобразование Фурье с сильно отличающимися по величине

входными *

• . .дайными -

Расчет .. параметрической

; УСТОЙЧИВОСТИ

решений систем дифференциальных - уравнений

12

Задачи с точно заданными исходными / данными .

| Обращение ... матрицы . ■ 1 Гильберта

.... .„V.* Двумерная краевая

задача для дифференциальных ) уравнений второго порядка

Метод Эйлера для ; решения задачи

КОШ1Л •• ;

[ - Краевая задача для

стационарного , | л уравнения I. теплопроводности, с ••' 1 ' сильно отличающимися !

друг от друга по "'Ц } величине «

коэффициентами

Жесткие задачи с разномасштабными коэффициентами;

Отсечение , триангуляционного,,

проецируемого на плоскость ХУ

Рисунок 3. Вычислительные задачи, критичные к нарушению алгебраических свойств

Плохо обусловленные задачи, в свою очередь, можно разграничить на:

1. Плохо обусловленные с точно заданными исходными данными,

2. Чувствительные к изменению шага дискретизации.

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

Так, для матрицы Гильберта уже порядка 20 относительная погрешность при вычислении коэффициентов обратной матрицы в арифметике с плавающей точкой одинарной точности ( стандарт ШЕЕ 754) превышает 100% и с увеличением порядка исходной матрицы относительная погрешность резко возрастает. Для этой матрицы нарушается алгебраическое свойство Я • я ~1 = 1 , где Я - матрица Гильберта,

Я - обратная матрица, / - единичная матрица Простейшим примером задачи, чувствительной к изменению шага дискретизации является решение задачи Коши методом Эйлера. Рассмотрим дифференциальное уравнения х'(t)=t, х0=0, t0=0. Аналитическое решение этого уравнения известно и можно вычислить относительную погрешность решения, полученного численным путем s арифметике с плавающей точкой. В качестве шага интегрирования были выбраны числа 1/2?, где q - натуральное число. Результаты работы программы представлены на рисунке 4, где показаны зависимости относительной погрешности решения задачи Коши Е от числа q . Верхняя кривая представляет собой зависимость при использовании вычислений с плавающей точкой, нижняя - при использовании вычислений с исключением ошибок округления.

0,00025 ^

О ----------7-----—------т——

11 12 13 14 15 16 17 18 19 20 21

q

Рисунок 4 - Зависимости относительной погрешностей от q

Из рисунка видно, что при уменьшении шага интегрирования относительная погрешность решения задачи Коши при использовании вычислений с плавающей точкой уменьшается при ? < 19 . Затем начинается резкий рост погрешности.

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

1 -1--------- --------1 Т Г^ ' и1

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

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

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

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

Выполнение ч арифметических Выполнение я

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

Рисунок 5. Общая схема высокоточных вычислений в МСС с отложенным

округлением

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

Любое вещественное число А в формате с фиксированной точкой можно представить в виде:

• У\ У г Уъ - ук/

В другой форме: К

А =

2 '

где

К - целое число такое, что ¡X") < 2 ^ 1 -1; " г ~ длина целой части числа в формате с фиксированной точкой, * / длина дробной части числа в формате с фиксированной точкой. Пусть Л > >•■•> Р* - модули (последовательность простых чисел) такие, что Л < < >•••> < Р„ , Р, > 2 ; п _ ЧИсло модулей и Р ~ Л " • - ' их произведение. Определение 1.

Модулярным форматом числа А назовем представление в виде (рис. 6):

А = [(а,,а2,..., а,,..., а„),/ ], где

= И,, = \К •2"|л,

1 = 1 ..... П

О < Г < к/ .

Число ( (после точки) назовем модулярным порядком.

Рисунок 6. Модулярный формат представления чисел с фиксированной

точкой

В данном случае фиксированная точка в (1) является перемещаемой и ее положение определяется набором арифметических действий решаемой задачи. Сам по себе принцип «перемещаемой точки» является универсальным с точки зрения нахождения единой формы представления рациональных и комплексно-рациональных чисел. Доказана теорема о единственности представления чисел с фиксированной точкой в модулярном формате.

Фарея равен

. Т.е. данный формат представления значительно

Теорема 1

Существует одно и только одно представление числа вида , к

А = —, о < 1 < к1

в модулярном формате:

А = [(а ,, а 2,..., а ,,..., а „) , г ]

по модулям Р, < Р2 <,..., < Рп для всех | < — р,

Из теоремы единственности следует, что если модули Р1, Рг,..., Р„ приблизительно равны между собой значению Р\ то \к\< .В

традиционном представлении в МСС при тех же модулях *******

(Р'Уп

л

расширяет диапазон представления чисел с фиксированной точкой в МСС.

Правила для выполнения арифметических операций сложения, вычитания и умножения чисел в модулярном формате имеют вид: Входные данные:

А, = [(а,,а2>..., а„),11 ] и А2 = [(/?,, р2 ,..., /?„),/2].

1. Сложение ШагМ1. Вычисляем: \а , + 0 ,\р > = 1,-, « .

Шаг М2. Порядок результата равен большему порядку

чисел А, и А 2 . Шаг №3. Проверка на переполнение и округление.

2. Вычитание Шаг№1. Вычисляем: \а, - Р,\р , ' = 1..... « .

Шаг №2. Порядок результата равен большему порядку

чисел А , и А 2 . ШагМЗ. Проверка на переполнение и округление.

3. Умножение ШагМ1. Вычисляем: ¡а, ■ Р,\р, ' = !>-> " ■

Шаг №2. Порядок результата равен сумме порядков чисел А, и

А 2 .

ШагМЗ. Проверка на переполнение и округление.

Что касается деления, то эта операция в МСС яатяется наиболее

сложной арифметической операцией. Рассмотрим два случая: деление на константу, деление на произвольное число. Деление на константу всегда можно заменить умножением делимого на обратную к константе, которая заранее вычислена и храниться в памяти. Во втором случае используется один из быстрых алгоритмов деления, основанный на итерационной формуле Ньютона, которая имеет вид: + 1 = ¡V с -(2 - Ж с ■ В). С помощью данной формулы определяется приближенное значение выражения IV = ~. В предельном случае, когда число итераций

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

в

Возникает вопрос о выборе начального приближения. Известный способ выбора начального приближения для любого 0,5 < В < 1 не эффективен, в вид}' сложности проверки условия 0,5 < В < 1 в МСС и выполнения операции сдвига. Для решения задачи выбора начального приближения в МСС используем двойное представление в модулярном формате и в формате с плавающей точкой. Если В имеет два представления в модулярном формате В т и формате с плавающей точкой В / , то преобразуя # г в модулярную систему счисления, можно получить искомое начальное приближение IV 5 .

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

получим, что для вычисления IV = —- с максимальной допустимой

В

абсолютной погрешностью округления 2 к' достаточно Г

I 2

итераций.

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

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

где т ; — мантисса числа В ^ > сама записанная в формате с плавающей точкой, р / - порядок числа В ^ .

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

Модулярно-позиционным форматом числа А назовем представление в виде:

А = [(а,, а 2,..., а,,..., а „) ,г,т п р 7 ] , где

г = 3 ,..., п О < г к I ,

т , - мантисса числа А Во вложенном формате с

плавающей точкой, р} _ порядок числа А во вложенном формате с плавающей точкой. Перейдем к рассмотрению правила выбора модулей для представления результатов арифметических операций в МСС.

Разобьем интервал

[О,..., Р) на 4 части (рисунок 7): [О,..., Р((/4) ), [Р(1/4) Р(1/2) )ЛР(1/2) >•■■' Р (1/4) )' [Р (1/4) >■■■> Р) и будем использовать интервалы:

[О,..., Р(1/4) ) - для представления положительных чисел,

[Р (1/4) >••■, Р) - для представления отрицательных чисел, [Р (1/4) ,..., Р(1/2) ) - для представления положительных чисел, требующих округления

[Р (1/2) >■■•> Г" (1/4) ) - для представления отрицательных чисел, требующих округления,

где

п п-1 К»-1)-^

Р=ГМ> РП/4)= ГК (2)

¡=1 ¡=1 ¡=1

Р' = р - р

г (1/4) г (1/4)'

Определение 3.

Назовем рабочим положительным диапазоном (РПД)

полуинтервал [О,..., Р(1/4) ), в котором представляются все положительные результаты арифметических действий в МСС.

Если результат арифметической операций А больше нуля и он принадлежит [Р (1/4) ,..., Р(Ь2) ) , то эта ситуация сигнализирует о том, данный результат необходимо округлить и, таким образом, вернуть в РПД. Определение 4.

Назовем рабочим отрицательным диапазоном (РОД) интервал [Р' (¡д) >•••> Р), в котором представляются все отрицательные результаты арифметических операций в МСС.

Если результат арифметических операций А меньше нуля и принадлежит [Р' 0/2) Р' (1/4) ) , то его необходимо округлить и вернуть в РОД.

Р(1/4) Р(1Я) Р (1Я)

Рисунок 7. Представление чисел с определением области округления

в МСС

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

Р 0/4) >2("' + <Л (3)

Единственность представления чисел с фиксированной точкой

следует из теоремы 1

Рассмотрим способ округления вещественных чисел в МСС. Пусть А = [ (a J ,а 2 ,..., ап ), t] - результат выполнения одной

из арифметических операций сложения, вычитания и умножения чисел А1 и Л 2 в МСС, который необходимо округлить. Пусть £ -максимальная допустимая относительная погрешность округления,

2- к j- максимальная допустимая абсолютная погрешность округления.

К

Пусть дробь ^ I , соответствует числу А , т.е. а,. = К • (2 1)mod Р,.

Тогда

2') mod Р.. (4)

Преобразуя £ в смешанную системе счисления, получим:

п- 1

K=lvi-ai> (5)

(=0

где

vQ = 1, - основания смешанной

i

v. = ГТ Р ., 1 < / < я - 1, системы счисления,

а i - цифры разложения К в системе счисления со смешанными основаниями,

п-1

Пусть К = ^ v -а, значения выражения (5) в формате с

о

плавающей точкой.

г^ " /

Если ,— - 2 , то возникает ошибка переполнения

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

формате с фиксированной точкой), если <2 , то полученный

результат меньше минимально представимого числа в формате с фиксированной точкой и он заменяется нулем. Далее сравнения производится в смешанной системе счисления. Если К < Р (Ы) , то

А > 0 и его округление не требуется. Если Р(1/4) < К < Р(1/2) ) то А > 0 и его необходимо окрутить. В противном случае число А отрицательное и здесь возможны два варианта: А принадлежит РОД или не принадлежит. Проверим принадлежность его РОД. Найдем дополнение А до модулей (А * ), вычислим К * по формуле (4) , преобразуем К * в смешанную систему счисления. Если К * < Р(1/4) , то А принадлежит РОД и округление не требуется. Если Р(1/4) < К * < Р(1/2) , то А не принадлежит рабочему отрицательному диапазону и требуется его округление. Округление отрицательного числа производится следующим образом: определяется его дополнение до модулей, далее результат округляется как положительное число и опять находится его дополнение до модулей. В целях ускорения округления ряд операций могут выполняться параллельно: преобразование чисел К , К * в смешанную систему, определение числа К ~ . Так как округление отрицательных чисел сводится к округаению положительных, то правило округления рассмотрим только для положительных чисел. Для округления положительных чисел в МСС необходимо решить две вспомогательные задачи:

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

К ~ , относительная погрешность К ~ не превышала £ .

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

К ~ абсолютная погрешность не превышала 2 к' .

Справедлива следующая вспомогательная теорема.

Теорема 2.

Для того чтобы относительная погрешность К не превышала £ и абсолютная погрешность не превышала 2 к' достаточно выбрать длину мантиссы N шут равной:

N

млит

шах

V

/

Рассмотрим правило округления.

Правило округления

1. Вычислим К в арифметике с плавающей точкой с длиной мантиссы равной N ш„ .

ИЯ/ | | - к у

<2 51А | > 2 . Если условия выполняются, т.е. предполагается, что не было переполнение и

| больше минимального представимого числа, то проверяем М | > Р (1 / 4) . Если оно выполняется, то требуется округлить число А . Сокращаем числитель и знаменатель так, чтобы К - < Р„,4Ч для этого делим числитель и знаменатель А на величину 2 Рк " ~к' , где р к - порядок числа К

3. Представляем К в виде целого числа и преобразуем его в МСС.

Далее во второй главе рассмотрено представление комплексных чисел в МСС. Так как в современных ЭВМ арифметические операции с комплексными числами = Х1 + ' ■ У-.< = Х1 + ' ■ Уг, как правило, выполняются в арифметике с плавающей точкой по формулам:

г,±г2 =(*,±х2) + ;•(>•, ±>>2) г, • г2 = (х,х2 - у,у2) + / • (х,уг + ухх2),

г, __ хххг + у,у2 у,х2 - х.у2 г 2 2 2 '

¿2 х2 + У 2 Х2 + У 2

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

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

Определение 5.

Определим множество комплексных дробей Фарея порядка ^ следующим образом:

Х + ,'У , хе г, Уе2,ае7.,Ье2,

В =

:2 а + I ■ Ь

где

О < 1*1 < N , О < |>>|< N , О < \а\< N, 0 < \Ь\< А\ 22 * О, НОД (2х,г2) = 1.

2 — множество целых чисел, N > О - порядок комплексных дробей Фарея. Доказана следующая теорема.

Теорема 3.

Если N - порядок комплексных дробей Фарея, удовлетворяющий неравенству:

4 - К 2 <

Р2 + ч1-1

(6)

м+м

и х = г1/г2 - комплексная дробь Фарея порядка N сравнимая с целым числом к По модулю т = р + г ■ д , то х - единственная комплексная дробь Фарея порядка N , сравнимая с к по модулю т .

Ниже в таблице 1 приведены комплексные дроби Фарея первого порядка и соответствующие им целочисленные представления в модулярной системе счисления по вещественному модулю р2 + ^г2 = 101 , где т = р + ¡д - 10 + г.

Таблица 1. Комплексные дроби Фарея 1-го порядка и соответствующие им целые числа по модулю т .

В, г

-1+01/жн, 100

-1+-П /1+01 9

-1+Н/1+01 90

1+01 /о+н 10

0+01 /1+01 0

0+Н/1+01 91

1+01 / -1+-П 45

1+01/-1+Н 55

1+01/ 1+-П 46

1+01/1+П 56

1+-П/1+Ш 11

1+П /1+01 92

1+01 /1+01 1

Приведем примеры.-+ 1 =--=-.

-1 + / - 1 + / 1 + 1

Пользуясь таблицей 1, имеем: (55 +1)то<1 101 = 56 и из таблицы 1

видно, что число 56 соответствует дроби •

1 — / — ¿ = 1 - 2 - г. Пользуясь таблицей 1. имеем:

(11 - 91 )то(1 ¡01 = (- 80 )тоа 101=21, но число 21 отсутствует в таблице 1. Произошла ошибка псевдопереполнения (выхода результата за пределы допустимого диапазона, определяемого неравенством (6)), т.к. истинный результат 1-2-1 комплексная дробь Фарея порядка два, а не один. Далее в главе рассматривается представление комплексного числа А в формате с фиксированной точкой в виде: х + / • у

А =

* с 2 f

(7)

где

х + i ■ у - целое комплексное число такое, что: х е Z, у 6 Z, 0 <; |х| <; 2"/+,/ -1, 0 < \у\< 2"/+А/ - 1, п г — целая часть комплексного числа с фиксированной точкой, * / - дробная часть комплексного числа с фиксированной точкой.

Вводится обозначения для комплексных модулей м 1 = Pi + ' -4i,M2 = Р2 + i -q2,..; м „ = Р„ + i -qn _ последовательности простых целых комплексных чисел, нормы которых возрастают Norm (М,)< Norm (М2) <„..,< Norm (М J и их произведение равно М = М , • М 2 ■... ■ М , = р * + г • q *

Доказана следующая теорема.

Теорема 4.

Если модули ^1 = = p2 + i-q2,..., М„ = p„+i-q„

удовлетворяют условиям: iPi,Qi) = 1,-, (Р„-Я„) = 1 ,

ПМ,]>0,?* = 1т(ПМ( 1>0' (Р*> Я*)

p* = Re

и выполняются неравенства:

1

> 2

при р* > д'

¥

¿-I > 2"/+i/ при q* > р '

р* V2 q * VT

2 2

£ 2

"i+kf

при q* = р'

то комплексные числа с фиксированной точкой вида (7) представляются по этим модулям единственным образом.

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

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

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

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

При выборе модулей малых по величине возможно ускорение высокоточных вычислений в модулярной арифметике за счет использования « table lookup » метода, суть которого заключается в том, что в памяти хранятся всевозможные результаты для каждой арифметической операций и результаты этих операций не вычисляются, а извлекаются из памяти. Это дает возможность выполнения в модулярной арифметике всех операций за одинаковое время, что является одним из преимуществ модулярной системы счисления перед другими системами счисления.

Схема алгоритма выполнения арифметических операций: сложения, вычитания и умножения над двумя числами А, В в модулярном формате показана на рисунке 8.

Исходные данные:

1. Числа Ах = [(а,,а2,..., аа „) ,]

А2 = [ < vS 1, yS 2р0„),t2 ] заданные в МСС.

2. Модули - Р„

Выходные данные: Число Л3 = [(у г, у г п-, Г„)>'з ] в МСС равное А3 = А, * л2, где

Рисунок 8. Схема алгоритма сложения, вычитания и умножения чисел в модулярном формате

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

Ускорение высокоточных вычислений при решении

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

Исходя из этого можно предложить рекомендации по применению высокоточных вычислений в МСС для решения тех вычислительных задач, в которых:

1. Минимальное число преобразований конечного результата из МСС в ПСС. Примеры: вычисление суммы ряда, определителя матрицы, значения некоторой функции и др. Нежелательный пример; нахождение обратной матрицы большой размерности, в ней число преобразуемых

величин равно квадрату порядка матрицы.

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

Глава 4 «Реализация структурных принципов машинной арифметики» посвящена вопросам проектирования структурных схем поддержки высокоточных вычислений на основе разработанных в третьей главе алгоритмов, Пока?ян<т что при реализации разработанных алгоритмов на аппаратном уровне обеспечивается наибольшее ускорение высокоточных вычислений. Определены различные уровни аппаратной поддержки высокоточных вычислений: на уровне специализированного вычислительного устройства, модулярного сопроцессора. Вычислены оценки временных затрат основных узлов модулярного сопроцессора в вентильных задержках. Под вентильной задержкой понимают задержку при прохождении сигнала через один логический элемент. Разработана обобщенная структурная схема модулярного сопроцессора для поддержки высокоточных вычислений (рис.9). В целях упрощения структурной схемы некоторые узлы модулярного сопроцессора не приведены. В модулярный сопроцессор входят следующие блоки:

• блок постоянной памяти;

• блок общей памяти;

• группа потоковых вычислительных устройств (ГПВУ1,..., ГПВУЧ);

• блоки округления (Б01,."»Б0ч);

• потоковые преобразователи в МСС (ППЬ..., ППЧ);

• блоки поддержки вычислений с плавающей точкой (БСП1,..., БСПЧ);

• шины данных (ШДь..., ШД,);

• шина команд (ШК).

Рисунок 9. Структурная схема модулярного сопроцессора.

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

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

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

Пятая глава «Программная реализация библиотечных функций для поддержки высокоточных вычислений» посвящена программной реализации высокоточных вычислений. Анализ возможностей программной реализации высокоточных вычислений на кластере и многоядерном процессоре показал, что реализация на процессорах многоядерной архитектуры более эффективна. Каждое ядро многоядерного процессора проводит параллельные и независимые друг от друга вычисления по своему модулю, а при округлении данные со всех ядер передаются одному ядру, производящему округление. Время передачи данных между ядрами на порядки меньше времени передачи между процессорами внутри кластера, поэтому этот вариант обеспечивает более удобную реализацию ряда алгоритмов модулярной арифметики (сложения, вычитания, умножения, округления и др). Для программной реализации разработанных алгоритмов использовались графические ускорители NVIDIA, которые имеют невысокую стоимость и достаточно распространены. Число ядер современных графических ускорителей может достигать 480 и более.

Разработаны ряд библиотечных функций для поддержки высокоточных вычислений в МСС на основе CUDA Runtime API и Visual Studio, включающие в себя:

1. Init - инициализацию библиотеки, выбор модулей;

2. AddRNS ( А, В ) - сложения двух чисел, входные параметры: два числа, выходные - результат суммирования;

3. SubRNS ( А, В ) - вычитания двух чисел, входные параметры: два числа, выходные - разность двух чисел;

4. MulRNS ( А, В ) - умножения двух чисел, входные параметры: два числа, выходные - результат произведения двух чисел.

Функции преобразования чисел:

1. ConvertToRNS (A, module ; Result) - преобразование числа А из позиционной системы счисления в МСС по модулю module;

2. ConvertFarea (А) -преобразование числа А из МСС в ПСС.

Функция округления числа:

1. Okrug ( А ; Result) - округление числа А в МСС .

Функция сравнения чисел:

1. Compare (А, В) - сравнение чисел.

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

Ход основной программы, исполняемом на CPU

Нить 1 Нить 2

I I

Нить q

Вызов библиотечных функций на GPU

Ход основной программы, исполняемой на CPU

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

высокоточных вычислении.

В пятой главе работы порядок вызова библиотечных функций рассматривался на примере определения скалярного произведения двух векторов с числом координат т равным 15000, 10000, 3000 и 500. Были получены оценки времени определения скалярного произведения векторов в МСС на 32-х ядерном графическом ускорителе NVIDIA GeForce 9600М GT и при использовании существующей библиотеки высокоточных вычислений MPArith при одинаковой точности. Построен график зависимости коэффициента абсолютного ускорения от длины мантиссы, определяемого по формуле: Т

R = —Ц Т2

где

Г, - время вычислений с использованием библиотеки MPArith,

Т 2 - время вычислений в модулярной арифметике при той же точности.

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

Ллинз мантиссы, бит

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

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

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

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

ср и

ПРИЛОЖЕНИЕ

Библиотека

Драйвер

Модулярный сопроцессор высокоточных

Рисунок 12. Среда для поддержки высокоточных вычислений

В шестой главе «Экспериментальная реализация и оценка эффективности разработанных методов» отражены результаты оценки эффективности разработанных методов и средств поддержки высокоточных вычислений по схеме с отложенным округлением. Исследована аналитически зависимость времени вычислений в МСС ко схеме с отложенным округлением на примере выполнения группы арифметических операций и решения системы линейных уравнений методом Гаусса-Зейделя.

Для системы линейных уравнений с 20 неизвестными зависимость времени вычислений в условных тактах от числа модулей представлена на рисунке 13.

Из графика видно, что:

1. Увеличение числа модулей приводит к ускорению вычислений.

2. При решении СЛАУ с большим количеством модулей, время решения при увеличении точности изменяется в меньшей степени, чем при решении СЛАУ с меньшим количеством модулей. Например, при увеличении точности вычислений в 2 и 5 раз общее время решения СЛАУ для 30 модулей увеличивается в 1,6 и 5 раз, а для 1000 модулей в 1,1 и 1,5 раза.

1400000

1200000

1000000

з 800000

8 600000

I 400000

200000

V

■одинарная точность -двойная точность "пятикратная точность

200 400 600 Б00 1000 1200 1400 1600

Рисунок 13. Зависимость времени вычислений в МСС от числа модулей.

Седьмая глава «Применение разработанных методов и средств»

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

1. Геоинформатика.

Задача: определение пересечения двух отрезков в проекции на

плоскость ХУ.

В случае, когда отрезки «почти параллельны» в арифметике с плавающей точкой происходят ошибки при определении параллельности отрезков, например, для отрезков А В, СО с координатами А,В,С,Б соответственно (100,2,100.0001,2.0001,120, 22, 120.0001, 22.0001). Применение целочисленного инварианта арифметики с плавающей точкой позволило исключить ошибки при определении параллельности отрезков, что подтверждено актом о внедрении в институте проблем геотермии Дагестанского научного центра РАН.

2. Робототехника.

Задача: Анализ многосвязных мехатронных систем высокой размерности прямыми корневыми методами.

Прямые корневые методы анализа многосвязных мехатронных систем высокой размерности основаны на решении полиномиальных уравнений высокой степени. В случае, когда корни полиномиального уравнения высокой степени кратные или «почти кратные» (плохо обусловленный полином) точность решения существенным образом зависит от точности вычислений. Численные эксперименты показали, что при нахождении решений плохо обусловленного полинома степени 400 со случайно заданными коэффициентами методом Хичкока происходила сильная потеря точности и дальнейшее увеличение числа итераций не повысило точности решения. Применение высокоточных вычислений позволило получить искомые решения.

3. Тетоэнергетжа.

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

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

8и 2 82Х . , , «

-= а--, 0 < х < /, ¿> 0

Ы 81

с граничными условиями первого рода:

и(0,/) = <р0 (*), I > 0;

и(/,0 = <р;(0, ( > 0,

и начальными условиями при I = 0 :

и(х,0) = ^ (х) , 0 < х <1 .

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

г = {xJ = = 0,1,..., N;

Л = кт, к - 0,1,..., К). с пространственным шагом /г = I / N и шагом по времени г = Т / К и исходное уравнение аппроксимируется системой конечно-разностных уравнений.

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

а = 0.044 , А = 10 "3, т = 10 4, N = 1000 , произошла резкая потеря

точности результатов (относительная погрешность составила 100% при числе итераций равной 5000). Физически эти параметры могут соответствовать случаю, когда ищется распределение температуры магистрального трубопровода длиной 1000 м через каждый метр, каждые 3 часа. В этом случае параметр А принимает значение 10 "3, а

г приблизительно 10 4 сек, N = 1000 . Применение высокоточных вычислений позволило получить искомые результаты с требуемой точностью.

4. Теория управления.

Задача: Определение управляемости линейных динамических систем.

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

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

5. Физика плазмы.

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

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

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

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

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

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

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

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

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

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

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

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

В приложении к диссертации приведены листинги программ: «Преобразование целых комплексных чисел в модулярной системе счисления», «Преобразование комплексных дробей Фарея в модулярной системе счисления», «Целочисленный инвариант», структурные схемы узлов модулярного сопроцессора для поддержки вычислений с комплексными числами, описание лабораторной работы по теме: «Проблемы организации вычислений», вынесены акты о внедрении.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Статьи в периодических изданиях, рекомендованных ВАК РФ

1. Оцоков Ш.А. Структурная организация ненропроцессора с использованием модели безошибочных вычислений. // Нейрокомпьютеры: разработка и применение, № 12 - 2004.

2. Оцоков Ш.А. Нейронный алгоритм расширения диапазона представления результатов безошибочных вычислений. П Нейрокомпьютеры: разработка и применение, № 12 - 2004.

3. Оцоков Ш.А. Алгоритм ускоренного отображения дробей Фарея в систему остаточных классов. // Вестник Дагестанского научного центра РАН, №19 - 2004, с.40-43

4. Оцоков Ш.А. Критерий целочисленности результата арифметических операций с плавающей точкой. // Информационные технологии, № 7-2007, с. 50-52.

5. Оцоков Ш.А. Возможные приложения арифметики кодов Гензеля. // Вестник МЭИ № 5,2007 — С. 97-101

6. Оцоков 111.А. Обобщение вычислений над полем комплексных чисел с исключением ошибок округления // Информационные технологии, № 6 - 2009, с. 17-23.

7. Оцоков Ш.А. Применение модулярной арифметики с фиксированной точкой для ослабления влияния ошибок округления компьютерных вычислений. И Информационные технологии, № 12 - 2009

8. Дзегеленок И.И, Оцоков Ш.А. Алгебраизация числовых представлений в обеспечении высокоточных суперкомпьютерных вычислений // Вестник МЭИ №3 - 2010,107-116

Публикации в других изданиях

10. Дзегеленок И.И, Оцоков Ш.А. Абдулатиф О. А., Ильин П.Е., Ильин И.В. Декомпозиционный подход к осуществлению впсЬтехнологий. М., Физматлит, "Информационная математика" №1(5), 2005.

11. Дзегеленок И.И., Мазуренко А.К., Оцоков Ш.А. Подход к численному возпроизведению моделей альтернативной энергетики // Сб. науч. тр. ВЭИ. - М.: ВЭИ, 2006. - С. 107.

12. Д.А.Орлов. Ш.А. Оцоков О возможности применения "безошибочных" вычислений для решения задачи Коши. // Труды международной конференции "Информационные средства и технологии", МФИ - 2006, Т.2., Москва, 2006.

13. Оцоков Ш.А. Метод организации вычислений с исключением ошибок округления в модулярной системе счисления. //Труды всероссийской научно-технической конференции "Микроэлектроника и информатика - 2006", МИЭТ-2006.

14. Дзегеленок И.И., Оцоков Ш.А. Метод ускорения модулярной арифметики с самоисключением ошибок округления. Сб. научных трудов, посвященный юбилейной международной научно-технической конференции "50 лет модулярной арифметике", Зеленоград (Россия), 23-25 ноября 2005. - М.:ОАО "Ангстрем", МИЭТ, 2006, с.576-586.

15. Оцоков Ш.А. О возможности обобщения параллельной модулярной арифметики для работы с двоичными дробями. // Вычислительные сети, теория и практика 2007, Номер 2, (11).

16. Оцоков Ш.А. Применение модулярной арифметики для решения непрерывной задачи наименьших квадратов. // Инфокоммуникационные технологии в науке, производстве и образовании: сборник материалов третьей международной научно технической конференции. - Ставрополь, 2008. - С.210-217.

Патенты

17. Патент РФ 2235423. Устройство для преобразования числа из системы остаточных классов в позиционный код// Оцоков Ш.А., Шухман И.М. Опубл. 27.08.2004.

18. Патент РФ 2293437. Устройство для преобразования числа из системы остаточных классов в позиционный код // Оцоков Ш.А., Исмаилов Ш-М.А. Мугугдинова Х.М. Опубл. 10.02.2007.

19. Патент РФ 2305861. Устройство для округления числа в системе остаточных классов // Оцоков Ш.А., Мугутдинова Х.М. Опубл. 10.09.2007.

Подписано в печать ЮГ. заказ № Ш тираж /£. {/ печатных листов 1,6 Типография МЭИ; Красноказарменная, 13

Введение

ОГЛАВЛЕНИЕ

ГЛАВА 1. ОРГАНИЗАЦИЯ ВЫСОКОТОЧНЫХ ВЫЧИСЛЕНИЙ КАК НАПРАВЛЕНИЕ РАЗВИТИЯ

КОМПЬЮТЕРНЫХ СИСТЕМ.

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

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

1.3. Состояние работ в области осуществления высокоточных вычислений.

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

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

Выводы по главе 1.

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

2.1. Решение задачи о выборе модулей для реализации арифметики с фиксированной точкой.

2.2. Поиск новых инвариантных свойств арифметики с плавающей точкой.

2.2.1. Целочисленный инвариант арифметики с плавающей точкой.

2.2.2. Знаковый инвариант арифметики с плавающей точкой.

2.3. Усовершенствование многомодульной арифметики с исключением ошибок округления с рациональными числами

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

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

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

Развитие современных супер-ЭВМ происходит за счет использования новых архитектурных решений и усовершенствования элементной базы. Тенденцией является создание процессоров» с многоядерной архитектурой. Увеличение количества ядер в процессоре повышает производительность, снижает стоимость и энергопотребление супер-ЭВМ. С ростом производительности супер-ЭВМ расширяется спектр решаемых задач и их размерность, повышаются требования к точности компьютерных вычислений. В связи с этим проблему повышения производительности ЭВМ необходимо решать в тесной взаимосвязи с задачей повышения точности вычислений. Большинство компьютерных вычислений проводятся в арифметике с плавающей точкой, в которой неизбежны ошибки округления. Известны случаи, когда ошибки округления приводили к катастрофам и авариям с многомиллиардными убытками и человеческими жертвами, например, сбой в работе комплекса Patriot, предназначенного для защиты от самолетов, крылатых ракет и баллистических ракет ближнего радиуса действия, состоящей на вооружении армии США. Сбой в системе Patriot 25 февраля 1991 года помешал перехватить иракскую ракету, в результате, ракета достигла цели, погибли 28 американских солдат и еще около 100 человек получили ранения. Причиной сбоя стали ошибки округления, которые привели к некорректному расчету местонахождения приближающейся ракеты [18]. Из-за ошибок округления для арифметических операций с плавающей точкой не выполняются законы алгебры (коммутативности, дистрибутивности), например, х не равно (л: + х) - х [1]. Нарушение алгебраических свойств в арифметике с плавающей точкой приводит к появлению вычислительных аномалий [12,81,90,83]. Программисты должны учитывать особенности арифметики с плавающей точкой, составляя корректные с вычислительной точки зрения программы, в которых нет вычислительных аномалий. Существуют правила для программистов по составлению «вычислительно-корректных» программ, таких как, например: при суммировании массива чисел с плавающей точкой, для уменьшения роста ошибок округления, необходимо предварительно сортировать массив по возрастанию и начать суммирование с меньших чисел [35]. Однако, они-не всегда гарантируют обнаружение в расчетной программе скрытых вычислительных аномалий. Для обнаружения вычислительных аномалий необходим анализ ошибок округления. Существует множество работ, посвященных анализу ошибок округления для типовых задач линейной алгебры, таких как, решение систем линейных уравнений и др.[10,11,29,56,60 ]. Для других задач провести такой анализ очень сложно и требуются специальные знания в этой области. Простейший способ, который обнаруживает некоторые вычислительные аномалии: решение задачи с другим режимом округления в арифметике с плавающей точкой или с большей точностью вычислений и определение в программе сильно отличающихся друг от друга результатов, там возможны вычислительные аномалии [57,81,80]. Другой более надежный способ -использование интервальных или достоверных вычислений [33 ]. С помощью интервальной арифметики можно, получить конечный результат в виде некоторого интервала, который гарантированно содержит в себе истинный искомый результат. Главный недостаток интервальной арифметики - это расширение интервалов в процессе выполнения арифметических операций и потеря информативности результатов [33] . В первой главе приводится пример, когда полученный с помощью интервальной арифметики интервал, очень широкий и никакой полезной информации о точности не дает. Интервальная арифметика не всегда может помочь, в каждом случае требуется анализ целесообразности ее применения.

Один из традиционных способов борьбы с вычислительными аномалиями связан с применением высокоточных вычислений или с преобразованием расчетных формул и вычислительных алгоритмов тогда, когда это возможно сделать. Под высокоточными вычислениями понимаются вычисления, которые имеют точность более высокую, чем поддерживаемую современными ЭВМ. В настоящее время существует множество библиотек высокоточных вычислений, таких как, ZREAL, MPARITH, GMP и др. [76,77,78, 79,107,108,109,84-88 ]

Основной проблемой суще ствую щих библиотек высокоточных вычислений, сдерживающей их применение на практике, является сильная зависимость времени выполнения арифметических операций от точности вычислений. При малом объеме вычислений это не существенно, но для задач большой размерности использование высокоточных вычислений приводит к катастрофическому росту времени решения задач [68,89,102].

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

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

Указанная проблема требует поиска новых алгоритмических способов, связанных с применением нетрадиционных методов и систем счисления для представления и обработки чисел [ 69,70,72,91,101,106,115 ].

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

Существенный вклад в развитие теории модулярных вычислений внесли в нашей стране работы, Акушского И.Я, Юдицкого Д.И, Амербаева В. М, Коляда А.А, Червякова Н.И, Финько O.A. и др [ 1,2,31,32,54,61 ].

Исследование модулярной системы счисления показало новую возможность применения модулярной арифметики как средство повышения, точности вычислений и ослабления зависимости времени вычислений от точности, что позволяет выделить новое научное направление - теорию модулярных высокоточных вычислений [42,46,47,48,49 ].

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

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

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

- поиск инвариантных свойств арифметики с плавающей точкой.

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

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

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

- анализ эффективности разработанных алгоритмов и структурных схем устройств, реализующих высокоточные вычисления

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

ОБЪЕКТОМ ИССЛЕДОВАНИЯ являются многоядерные компьютерные системы и их составляющие в виде: сопроцессора и арифметического устройства, обеспечивающих высокоточные вычисления.

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

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

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

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

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

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

- Целочисленный инвариант арифметики с плавающей точкой:

- Знаковый инвариант арифметики с плавающей точкой.

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

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

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

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ Разработанные методы и программные средства позволяют:

- ускорить высокоточные вычисления за счет их распараллеливания;

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

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

- исключить возможную резкую потерю точности при решении задач с разномасштабными величинами.

Результаты работы внедрены в учебный процесс в Московском энергетическом институте (ТУ), в Московском институте радиотехники, электроники и автоматики, а также нашли применение в Межрегиональной распределительной сетевой компании Северного Кавказа, институте проблем геотермии Дагестанского научного центра РАН, что подтверждено соответствующими актами о внедрении.

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

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

- Юбилейной международной научной конференции "50 лет модулярной арифметике" (МИЭТ, Зеленоград, 2005 г.)

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

- Всероссийской научно-технической конференции "Микроэлектроника и информатика (МИЭТ, Зеленоград, 2006 г.)

- Международной конференции «Параллельные вычисления и задачи управления» (РАСО 2006, г. Москва, 2006 г.)

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

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

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

Выводы по главе 7

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

2. Универсальность технологии высокоточных вычислений в модулярной арифметике достигается тем, что: a. арифметические операции с числами различной природы ( целые, рациональные, коплексно-рациональные) выполняются по одним и тем же правилам; b. отсутствует недостаток формата с плавающей точкой, связанный с неравномерным распределением чисел внутри диапазона.

3. В отличие от существующих библиотек высокоточных вычислений (МрАгПИ, гЯеа1, ОМР) созданной библиотека обладает слабой зависимостью времени выполнения арифметических операций от точности при увеличении числа модулей и ядер. В этом состоит ее главное преимущество.

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Амербаев В.М. Теоретические основы машинной арифметики.- Алма-Ата: Наука, 1986,- 224 с.

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

3. Аль Массри. М.И. Разрядно-параллельные процессоры обработки вещественных чисел в непозиционных системах счисления. Дисс. на соиск. уч. степ, к.т.н. Л.: ЛЭТИ, 1993,- 208 с.

4. Амосов A.A., Дубинский Ю.А., Копченова Н.В. Вычислительные методы для инженеров. М.: «Высшая школа», 1994. — 544 с.

5. Акритас А. Основы компьютерной алгебры с приложениями. М.: Мир,1994. 543 с.

6. Барабанов И.Н. Спутниковые навигационные системы GPS и GLONASS. http://www.intuit.ru/video/7/

7. Воеводин В.В. Математические основы параллельных вычислений.www.parallel.ru/info/voevodin.doc.

8. Виноградов И.М. Основы теории чисел. М.: «Наука», 1972. - 456 с.

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

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

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

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

13. Герасименко А.А, Федин В.Т. Передача и распределение электрической энергии. Ростов- н./Д.: Феникс; Красноярск: Издательские проекты, 2006. - 720 с.

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

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

16. Григоренко В.П. Об одном методе решения нелинейных краевых задач, описывающих распределение неосновных носителей в базе полупроводниковой структуры // ВМиМФ, 1975, с.923-930.

17. Дискретное преобразование Фурье — Википедия.ru. wikipedia. org/. ./ДискретноепреобразованиеФурье.

18. Живич М., Каннингэм Р. Истинная цепа программных ошибок // Открытые системы. 2009.ЖЗ.

19. Дмитрий Чеканов nVidia CUDA: вычисления на видеокарте или смерть CPU?. Tom's Hardware, www.thg.ru/graphic/nvidiacuda/nvidiacuda01.html

20. Дзегелёнок И.И, Оцоков Щ.А. Подход к решению проблемы безошибочных вычислений с использованием ускоренного алгоритма отображения дробей Фарея. // Труды научной конференции, посвященной 75-летию со дня рождения академика В.А.Мельникова. РАН. М. 2004.

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

22. Дзегелёнок И.И, Оцоков Ш.А. Абдулатиф О. А., Ильин П.Е., Ильин И.В. Декомпозиционный подход к осуществлению Grid-технологий. М., Физматлит, "Информационная математика" №1(5), 2005.

23. Дзегеленок И.И., Мазуренко A.K:, Оцоков Ш.А. Подход к численному воспроизведению моделей альтернативной энергетики. // Сб. научных трудов ВЭИ, М., 2006.

24. Ильин В.П. Линейная алгебра: от Гаусса до суперкомпьютеров. http://nature.web.ru/db/msg.html?mid=l 178356&uri=page2.html

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

26. Мисриханов М.Ш. Инвариантное управление динамическими системами. Алгебраический подход. М:. Энергоатомиздат, 2003.

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

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

29. Кобзаренко Д.Н., Аскеров С.Я. Внутреннее отсечение триангуляционного объекта, проецируемого на плоскость XY. // Геоинформационные технологии, №4 2008.

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

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

32. Кулиш У., Рац Д., Хаммер Р., Xoicc М. Достоверные вычисления и их компьютерная реализация. РХД., 2005. 450 с.

33. Литвинов ГЛ., Родионов А.Я., Чуркин A.B. Приближенная рациональная арифметика с контролируемыми ошибками округления// Вычислительные технологии, т.6, №5 2001.

34. Мак-кракен Д., Дорн У. Численные методы и программирование на фортране. М.: Мир, 1977, 584 с.

35. Неочевидные особенности вещественных чисел.www.delphi1cingdoni.com/asp/viewitem.asp?catalogid::=374

36. Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток. М.: РАДИО И СВЯЗЬ, 1985

37. Орлов ДА., Оцоков Ш.А. О возможности применения «безошибочных» вычислений для решения задачи Коши // Сб. трудов международной научной конференции "Информационные средства и технологии" М.:МЭИ (ТУ), 2006. 207-210.

38. Оцоков Ш.А. Критерий целочисленности результата арифметических операций с плавающей точкой. // Информационные технологии7.2007, с. 50-52.

39. Оцоков Ш.А. Нейронный алгоритм расширения диапазона представления результатов безошибочных вычислений. // Нейрокомпьютеры: разработка и применение, № 12 2004.

40. Оцоков Ш.А. О возможности обобщения параллельной модулярной арифметики для работы с двоичными дробями. // Вычислительные сети, теория и практика 2007, Номер 2, ( 11).

41. Оцоков Ш.А. Структурная организация нейропроцессора с использованием модели безошибочных вычислений. // Нейрокомпьютеры: разработка и примеиение, № 12 2004.

42. Оцоков Ш.А. Алгоритм ускоренного отображения дробей Фарея в систему остаточных классов. // Вестник Дагестанского научного центра РАН, №19-2004, с.40-43

43. Оцоков Ш.А. Обобщение вычислений над полем комплексных чисел сисключением ошибок округления // Информационные технологии, № 6-2009, с. 17-23.

44. Оцоков Ш.А. Применение модулярной арифметики с фиксированной точкой для ослабления влияния ошибок округления компьютерных вычислений. // Информационные технологии, № 12 2009/

45. Оцоков Щ.А., Мугутдинова Х.М. Устройство для округления числа в системе остаточных классов. Патент РФ № 2305861., опубл. 10.09.2007.

46. Оцоков Ш.А., Шухман И.М. Устройство для преобразования числа из системы остаточных классов в позиционный код. Патент РФ № 2235423., опубл. 27.08.2004.

47. Ортега Дж., Пул У. Введение в численные методы решения дифференциальных уравнений. М. 1986. -288 с.

48. Петров Ю.П. Как получать надежные решения систем уравнений. СПб.: BHV-СПб, 2009.- 176 с.

49. Пи кипа Г. А. Математические модели технологических объектов. М.: Изд. дом МЭИ , 2008

50. Поспелов Д. А. Арифметические основы вычислительных машин дискретного действия . М.: Высшая школа, I960;

51. Сахшок П.А., Червяков Н.И., Шапошников А.В. Модулярные вычислительные структуры пейропроцессорных систем.: Учебное55. пособие М.: Физматлит, 2003

52. Стренг Г. Линейная алгебра и ее применения. Мир, 1980.

53. How Futile are Mindless Assessments of Roundoff in Floating-Point Computation?", William Kahan.ttp://www.cs.berkeley.edu/~wkahan/Mindless.pdf

54. Тихонов A.Ii. Арсенин В .Я. Методы решения некорректных задач. — М.: Наука, 1979.г1У. . --—

55. Тягунов Олег Аркадьевич Развитие технологий анализа,многокритериальной оптимизации и моделирования многосвязных мехатронных систем управления. Дисс. на соиск. уч. степ. д.т.н.М: МИРЭА, 2009

56. Уоткинс Д. Основы матричных вычислений. М.: Бином, 2006, 660 с.

57. Финько О.А. Модулярная арифметика параллельных логических вычислений: Монография / Под ред. В.Д. Малюгина. — М.: ИПУ РАН, 2003. —224 с.

58. Форсайт Дж., Молер К. Численное решение систем линейных алгебраических уравнений. М.: Мир, 1969

59. Хамахер К., Вранешич 3., Заки С. Организация ЭВМ. 5-е изд. Спб.: Питер; Киев: Издательская группа BHV, 2003. 848 с.

60. Чарыков, IT. А. Учебное пособие по курсу "Физика полупроводниковых приборов и компонент интегральных схем": Физические явления в р-п-переходах / Н. А. 41 .Чарыков, Ред. К. В. Шалимова, Моск. энерг. ин-т (МЭИ) . М. : Изд-во МЭИ, 1982 . - 80 с.

61. Ясницкий JI.H. Введение в искусственный интеллект. М.: Изд. центр «Академия», 2005.

62. Яненко Н.Н. Введение в разностные методы математической физики. 4.1,2. Новосиб. гос. ун-т, 1968

63. Яценков B.C. Основы спутниковой навигации. Системы GPS NAVSTAR и ГЛОНАСС. М.: Горячая Линия Телеком, 2005 г. - 272 с.

64. A.M. Frolov and D.Ii. Bailey, "Highly Accurate Evaluation of the Few-Body Auxiliary Functions and Four-Body Integrals," J. Physics B, vol. 36, no. 9, 2003, pp. 1857-1867.

65. A. Edalat, R. Heckmann, Computing with real numbers: (i) LFT approach to real computation, (ii) Domain-theoretic model of computational geometry, Lecture Notes in Computer Science, vol.2395, Springer, 2002, pp.193-267.

66. A. Edalat and F. Rico.Two Algorithms for Root Finding in Exact real Arithmetic.Third Real Numbers and Computers Conference, 27-44, (1998).

67. Blanck, J.:Exact real arithmetic systems: Results of competition, Computability and Complexity in Analysis, Lecture Notes in Computer Science, Vol. 2064, (2001) 390-394

68. Brabec, T., Lorencz, R.; Arithmetic Unit based on Continued Fractions, submitted for review to ECI 2006. http://service.felk.cvut.cz/anc/brabectl/pub/eci06.pdf

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

70. 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).

71. 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.

72. 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.

73. Chang P. R., Lee C. S. G. Residue arithmetic VLSI arra. architecture f°r 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.

74. David H. Bailey, Yozo Hida, Xiaoye S. Li and Brandon Thompson, "ARPREC: An Arbitrary Precision Computation Package," technical report LBNL-53651, software and documentation available at http://crdl.bl.gov/~dhbailey/mpdist.

75. D.M. Priest: Algorithms for Arbitrary Precision Floating Point Arithmetic. Lrx Proceedings of the J 0th Symposium on Computer Arithmetic, 1991.

76. D. H. Bailey: High-precision Floating-point Arithmetic in Scientific Computation. Computing in Science and Engineering, May-June 2005.

77. David H. Bailey. Resolving Numerical Anomalies in Scientific1.wrence Berkeley National Laboratory, 2008.

78. David H. Bailey. High-Precision Computation and Mathematical Physics. Lawrence Berkeley National Laboratory, 2009.

79. David Goldberg «What Every Computer Scientist Should Know About Floating-Point Arithmetic» ACM Computing Surveys (CSUR), v. 23 , Issue 1 (March 1991), pp. 5-48

80. D.Ii. Bailey, R. Krasny, and R. Pelz, "Multiple Precision, Multiple Processor Vortex Sheet Roll-Up Computation," Proc. 6th SIAM Conf. Parallel Processing for Scientific Computing, SIAM Press, 1993, pp. 52-56.

81. D.H. Bailey, P.B. Borwein, and S. Plouffe, "On the Rapid Computation of Various Polylogarithmic Constants," Mathematics of Computation, vol. 66, no. 218, 1997, pp. 903-913.

82. David FI. Bailey, Jonathan M. Borwein and Richard Crandall, "Integrals of the Ising Class," 2006, available at http://crd.lbl.gov/~dhbailey/dhbpapers/ising.pdf.

83. D.H. Bailey and S. Robins, "Highly Parallel, High-Precision Numerical Integration," Computational Research Division, Berkeley

84. Lab Computing Sciences, 2004; http://crd.lbl.gov/~dhbailey/ dhbpapers/quadparallel.pdf.

85. Escardo 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 Scicnce, University of Edinburgh, December 1997.

86. Floating Point Arithmetic," Proceedings of ARITIT-15, IEEE Computer Society, 2001.

87. 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.

88. Gregory R. T. A. method for and an application of error-free com/p

89. Proceedings of the AFCET Symposium «Mathematics for CZ Science». Paris, 152-158, 1982.

90. Gregory R. T. Error-free computation with rational numbers. BIT, 2 3 194-202.

91. Gregory R. T. Exact computation with order-N Farey fractions. CZ

92. Science and Statistics: Proceedings of the 15th Symposium on the Int«e E. Gentle Editor, North Holland, Amsterdam, 1983.

93. Gregory R. T. Residue arithmetic with rational operands. ProceecL Symposium on Computer Arithmetic. IEEE Computer Society, A Michigan, 144-145, 1981a.

94. Gregory R. T. The use of Finite-segment p-adic arithmetic fo computation. BIT, 18, 1978, 282-300.

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

96. Heckmann, R.: The Appearance of Big Integers in Exact Real Arithme based on Linear Fractional Transformations, Foundations of Software and Computation Structures, Springer LNCS 1378, 1998, pp. 172-188.

97. Koren, O. Zinaty, Evaluating Elementary Functions in a Numerical Coprocessor Based on Rational Approximations, IEEE Trans, on Comp> Vol. 39, No. 8, Aug. 1990.

98. Jen Vuillemin, Exact real computer arithmetic with continued fractions IEEE Transactions on Computers, Vol. 39, 1990, pp. 1087-1105.

99. J.R. Shewchuk: Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates. Technical Report CMU-CS-96-140, Carn< Mellon University, 1996.natations. Computer1981b,imputerirface. J.jigs 5th Arbor,exactumberiters,

100. J. M. Borwein and B. Salvy, "A proof of a recursion for Bessel raoraen"C Exp.Mathematics, vol. 17 (2008), 223-230.t&Z

101. Kornerup, P., Matula, D. W.; An Algorithm for Redundant Binary Bit-Pipelined Rational Arithmetic, IEEE Transactions on Computers, Vol. 39, No. 8, 1990, pp. 1106-1115.

102. Kornerup, P. and Matula, D., "Algorithms for Arbitrary Precision Floating Point Arithmetic," Proceedings of the 10th IEEE Symposium on Computer Arithmetic, 1991.

103. K. Briggs, Implementing exact real arithmetic in python, C++ and C, Theoretical Computer Science, vol.351, 2006, pp. 74-81.

104. Limongelli, C. ''Exact solution of computational problems via parallel truncated p-adic arithmetic" in: A. Miola and M. Temperini Eds. "Advances in Design of Symbolic Computation Systems" RISC Series in Symbolic Computation, Springer-Verlag 1997.

105. Mencer, O., Morf, M. and Flynn, M. J., "Precision of Scmi-Exact Redundant Continued Fraction Arithmetic for VLSI," SPIE '99 ,Arithmetic session, 1999

106. Matula, D. and Kornerup, P., "Finite Precision Rational Arithmetic: An Arithmetic Unit," IEEE Transactions on Computers, Vol. C-32 pp. 378-387, 1983.

107. MPFR C library for multiple-precision floating-point computations. http://www.mpfr.org/

108. NVIDIA CUDA Compute Unified Device Architecture: http://developer.download.nvidia.com/compute/cuda/l0/NVIDIACUDAP rogrammingGuidel .O.pdf

109. Online book from CUDA programming course at UIUC. http://courses.ece.illinois.edu/ece498/al/Syllabus.html

110. Peter R. Turner: Fraction-Free RNS Algorithms for Solving Linear Systems, IEEE Symposium on Computer Arithmetic 1997: Asilomar, CA, USA, pp 218-217

111. P.FI. Hauschildt and E. Baron, "The Numerical Solution of the Expanding

112. Stellar Atmosphere Problem," J. Computational and Applied Mathematics, vol. 109, 1999, pp. 41-63.

113. 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.

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

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

116. 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.

117. 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.

118. Rao T. M., Subramanian K., and Krishnamurthy E. V. Residue arithmetic algorithms for exact computation of q-inverses of matrices, SI AM J. Numer. Anal., 13, 1976, 155-171.

119. Simpson A. Lazy functional algorithms for exact real functionals. Mathematical Foundations of Computer Science 1998, volume 1450 of Lecture Notes in Computer Science, pages 323-342. Springer-Verlag, 1999.

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

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

122. Y. Fie and C. Ding, "Using Accurate Arithmetics to Improve Numerical Reproducibility and Stability in Parallel Applications," J. Supercomputing, vol. 18, no. 3, 2001, pp. 259-277.

123. Yozo Hida, Xiaoye S. Li and David FI. Bailey, "Algorithms for Quad-Double Precision"

124. 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-352-358.

125. Newton division. http://en.wikipedia.org/wiki/Division(digital)