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

• Автор: Оцоков, Шамиль Алиевич
• Шифр специальности: 05.13.05, 05.13.15
• Научная степень: Докторская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 294 с. : ил.

ОГЛАВЛЕНИЕ

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

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

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

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

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

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

организации высокоточных вычислений

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

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

ГЛАВА 2. РАЗВИТИЕ МАТЕМАТИЧЕСКОГО АППАРАТА ВЫСОКОТОЧНЫХ ВЫЧИСЛЕИЙ НА ОСНОВЕ ТЕОРЕТИЧЕСКИХ ОБОБЩЕНИЙ В МОДУЛЯРНОЙ СИСТЕМЕ СЧИСЛЕНИЯ
2.1. Решение задачи о выборе модулей для реализации
арифметики с фиксированной точкой
2.2. Поиск новых инвариантных свойств арифметики
с плавающей точкой.
2.2.1. Целочисленный инвариант арифметики с плавающей точкой
2.2.2. Знаковый инвариант арифметики с плавающей точкой.
2.3. Усовершенствование многомодульной арифметики с исключением ошибок округления с рациональными числами .
2.4. Обобщение одномодульной арифметики с исключением ошибок округления для работы с комплексными рациональными
числами.
2.5. Решение задачи о выборе модулей для реализации
комплексной арифметики с фиксированной точкой
2.6. Сводная таблица результатов и структурноалгоритмические принципы
обеспечения высокоточных вычислений
Основные результаты и выводы по главе
ГЛАВА 3. РАЗРАБОТКА АЛГОРИТМИЧЕСКОГО
ОБЕСПЕЧЕНИЯ ВЫСОКОТОЧНЫХ ВЫЧИСЛЕНИЙ .
3.1. Алгоритм проверки целочисленности результата
арифметических операций с плавающей точкой
3.2. Алгоритм проверки знака результата арифметических операций с плавающей точкой.
3.3. Алгоритмическое обеспечение модулярной арифметики над полем вещественных чисел.
3.3.1. Вспомогательный алгоритм преобразования числа с фиксированной точкой в модулярную систему счисления
3.3.2. Базовые алгоритмы
3.3.3. Служебный алгоритм округления, проверки переполнения и восстановления числа из модулярной системы счисления
3.4. Алгоритмическое обеспечение модулярной арифметики над полем
комплексных чисел.
3.4.1. Вспомогательный алгоритм преобразования комплексного числа с фиксированной точкой в модулярную систему счисления.
3.4.2. Базовые алгоритмы
3.4.3. Служебный алгоритм округления, проверки переполнения и
восстановления комплексного числа из модулярной системы счисления.

3.5. Рекомендации по применению разработанных алгоритмов Выводы по главе 3.
ГЛАВА 4. РЕАЛИЗАЦИЯ СТРУКТУРНЫХ ПРИНЦИПОВ
МАШИННОЙ АРИФМЕТИКИ.
4.1. Конкретизация структурных схем поддержки модулярной арифметики на уровне арифметического устройства, сопроцессора,
процессора.
4.2. Структурная схема узлов модулярного сопроцессора
4.2.1. Структурные схемы устройств преобразования
4.2.2. Структурная схема устройства реализации арифметики
в модулярном формате представления чисел.
4.2.3. Структурные схемы устройств округления чисел в модулярном формате, проверки переполнения и восстановления числа из модулярной системы счисления
4.3. Обобщенная структурная схема модулярного сопроцессора для поддержки высокоточных вычислений
4.4. Сводная таблица структурных схем с оценкой аппаратурных
затрат.
Выводы по главе
ГЛАВА 5. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ БИБЛИОТЕЧНЫХ ФУНКЦИЙ ДЛЯ ПОДДЕРЖКИ ВЫСОКОТОЧНЫХ ВЫЧИСЛЕНИЙ.
5.1. Состав библиотечных функций.
5.2. Возможности предлагаемой библиотеки высокоточных
вычислений.
5.3. Библиотека вычислений с исключением ошибок округления над полем рациональных чисел.
5.4. Среда для поддержки высокоточных вычислений на модулярном
сопроцессоре.
Выводы по главе
ГЛАВА 6. ЭКСПЕРИМЕНТАЛЬНАЯ РЕАЛИЗАЦИЯ И ОЦЕНКА
ЭФФЕКТИВНОСТИ РАЗРАБОТАННЫХ МЕТОДОВ
6.1. Экспериментальная оценка быстродействия выполнения арифметических операций в модулярной системе счисления на многоядерном графическом ускорителе
6.2. Зависимость времени вычислений в модулярной системе счисления от числа выбранных модулей.
6.3. Оценка эффективности параллельных модулярных вычислений на
примере итерационного решения систем линейных уравнений
Выводы по главе
ГЛАВА 7. ПРИМЕНЕНИЕ РАЗРАБОТАННЫХ МЕТОДОВ И
СРЕДСТВ
7.1. О возможности применения целочисленного инварианта арифметики с плавающей точкой в задачах геоинформатики.
7.2. Применение целочисленного инварианта для определения управляемости многомерных линейных динамических систем
7.3. Применение разработанной библиотеки для численного решения уравнения теплопроводности с разномасштабными коэффициентами
7.4. Применение высокоточных вычислений в итеративных алгоритмах мехатроники.
7.5. О возможности применения высокоточных вычислений для решения задач спутниковой навигации
7.6. Внедрение в учебный процесс
7.7. Сводная таблица результатов применения высокоточных
вычислений.
Выводы по главе
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ


П , 2. Рассмотрим правило выбора модулей и проверки переполнения. Для представления положительных и отрицательных чисел разобьем интервал О,. Р на 4 части рисунок 2. О,. Р Р2 ХР Р 4
где
4
Рисунок 2. Назовем рабочим положительным диапазоном РПД полуинтервал О,. МСС. Если результат арифметической операций Л больше нуля и он не принадлежит РПД из 2. Р 4 Р . РПД. РОД интервал р о4 р , в котором представляются отрицательные результаты арифметических операций в МСС. Если результат арифметических операций Л меньше нуля и не принадлежит РОД то он попадт в интервал Р р , т. Из 2. Рх Р2 ,. I 4 I 2 . А , совпадает с условием выхода для положительного результата Р А . Выход результата за пределы РПД и РОД сигнализирует о том, что его необходимо округлить. Таким образом, если число А принадлежит РПД, то А положительное, если А принадлежит РОД, то А отрицательное и если А не принадлежит ни РОД, ни РПД, то его необходимо округлить. Для того чтобы определить принадлежность числа А РПД или РОД его необходимо сравнить с 4. МСС в соответствии с теоремой 2. Способ сравнения чисел в МСС, который используется в настоящей работе, основан на представлении чисел в смешанной системе счисления числа переводятся в смешанную систему счисления, в которой они легко сравниваются . Этот способ сравнения не требует выполнения немодульных операций. Рассмотрим способ округления чисел в МСС. Правила выполнения арифметических операций в МСС представлены
К 2 1
1. Шаг Ао. Вычисляем у, а, , р , п Шаг 2. Шаг3. Проверка на округление рассматривается далее. Шаг . Шаг М2. Шаг М3. Проверка на округление. Шаг . Шаг М2. Порядок результата з равен сумме порядков чисел А , и
Шаг М3. Проверка на округление. Рассмотрим как осуществляется проверка i округление. В первой главе рассматривались три стратегии вычислений в модулярной системе счисления стратегия конечного результата, стратегия постоянного шага, стратегия переменного шага. В стратегии конечного результата нет проверок на округления в процессе вычислений в МСС. В стратегии постоянного шага отложенного округления разрядность результатов изменяется на постоянную величину. Обозначим эту величину через г . Пусть шаг отложенного округления. Г 2к8 . Т.е наибольший шаг отложенного округления при вычислениях в модулярной арифметике по данной стратегии определяется формулой
Е ,ое 2Л
п к г г
В стратегии постоянного шага также нет проверок на округления, т. МСС. В стратегии переменного шага отложенного округления шаг может изменяться в процессе вычислений, округление производится тогда когда оно необходимо. В этой стратегии уже нет ограничения на изменении разрядности результатов на постоянную величину. П8 дЛ ,
ЛК
Умножение чисел Л, и А 2 С А1 А 3 осуществляется по правилам
Л. А 2 тах ,,2 2 1 ,
к К К . К . Л 1 , . Если условие не выполняется, то вычисления продолжаются, если выполняется, то производится округление чисел л, и А 2 , корректировка значения порядка числителя а , и л 2 и повтор операции. Причем, если для некоторого из чисел А, или А, не требуется округление, то его значение порядка числителя не корректируется. В целях ускорения величина 2 2 заранее вычисляется. Таким образом, в стратегии переменного шага выполняется проверка данного условия после каждой арифметической операции в МСС. А и А г в модулярном формате, который необходимо округлить. Пусть е
максимальная допустимая относительная погрешность округления, 2. Пусть дробь , соответствует числу А з 9 т с
Тогда
тос Р. К у, 2 3 тос Р, 2. Преобразуем представление К в смешанной системе счисления на основе алгоритма, описанного в . Получим представление К в смешанной системе счисления
2. I цифры разложения К. Рассмотрим способ определения переполнения. Если К Ра. Если К РШ , то А 0 и требуется округление А . РОД. Найдем дополнение Аз до модуля Аз и вычислим К по формуле 2. А 2 . Если К Р4 то А принадлежит рабочему отрицательному диапазону и его округление не требуется. Если Ром К Р 9 хо л 2 не принадлежит рабочему отрицательному диапазону и требуется его округление.