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

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

Москва 2013 г.

Моё направление: «Проблемы организации высокоточных вычислений»

с фиксированной точкой можно представить в виде:

или:

где

целое число такое, что

длина целой части числа с
фиксированной точкой,

порядок А

– модули.

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

где

остаток от деления числа

на

.

… t

– целые числа

длина дробной части числа с
фиксированной точкой,

Пример:

Условие выбора модулей:

Сложение

Шаг №1. Вычисляем:

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

и

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

Вычитание

Шаг №1. Вычисляем:

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

и

Умножение

Шаг №1. Вычисляем:

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

и

формате с фиксированной точкой можно представить в виде:

где

целое комплексное число такое, что:

или

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

(рац. и компл. рациональные)

Модули (простые числа):

Требования:

Максимальная относительная погрешность:

Максимальная абсолютная погрешность

Правило выбора модулей:

Округление
до требуемой точности

Проверка необходимости
округления

1

...

q

q+1

...

2q

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

Да

Нет

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

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

...

Преобразование результатов в позиционную систему счисления

...

1

...

q

...

...

...

...

...

...

q+1

2q

...

где

длина целой части

длина дробной части

числа

Традиционные вычисления

ЯДРО 1

ЯДРО 2

…

ЯДРО N-1

A

B

A

B

A

B

A

B

ЯДРО N

…

C

C

Целые числа

GT:
32 ядра, 4 мультипроцессора, 512Мб общей памяти.
Архитектура SIMD. Порядок использования графического ускорителя:

Мультипроцессор N

Мультипроцессор 2

Мультипроцессор 1

Разделяемая память

Регистры

Регистры

Регистры

Ядро 1

Ядро 2

Ядро N

Блок
команд

Константная память

Текстурная память

Общая память

с 20 неизвестными

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

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

где время преобразования в модулярную систему счисления коэффициентов СЛАУ

время вычисления одного корня СЛАУ в условных тактах

размерность СЛАУ

счисления

МС ⇒ ПСС

Блок сравнения

Блок переходов

Исполнительное ядро

Передача

Блок передачи результата

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

Процессор
содержит:
128 128-разрядных
регистров данных

Блок выбора модулей

арифметики.

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

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

чисел из позиционной системы в
модулярную систему счисления

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

целое число

модуль

Результат:

максимума порядков

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

Результат:

где:

2. Структурная схема сумматора
в модулярном формате