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

1. Кафедра Вычислительных машин систем и сетей

Московский энергетический институт
Кафедра Вычислительных машин систем и сетей
Моё направление:
«Проблемы организации высокоточных вычислений»
Лекция на тему:
«Применение модулярной арифметики
в высокоточных вычислениях»
Москва 2013 г.

2.

Обобщенный модулярный формат представления вещественных
чисел
Любое вещественное число А в формате с фиксированной точкой можно представить в виде:
A
K
2t
Пример:
A
или:
x x x ... x , y y y ... y
nf 3
101,101
A
где
nf
kf
длина целой части числа с
фиксированной точкой,
длина дробной части числа с
фиксированной точкой,
0 t k f порядок А
kf 3
Модулярный формат представления А имеет вид:
kf
nf
101101
23
1 , 2 ,..., i , n , t
где
i A P K 2 t
i
– целые числа
Pi
P1 , P2 ,..., Pn – модули.
A
y
остаток от деления числа
A
на
K целое число такое, что
K 2
n f k f
1
1
2
…
Условие выбора модулей:
.
n
t
n
P
i
i 1
2
n f k f 1
y

3.

Правила выполнения арифметических операций в модулярном
формате
Входные данные:
A1
1 , 2 ,..., n , t1 и
A2
1 , 2 ,..., n , t 2
Сложение
i i i P ,
Шаг №1.
i 1,..., n
Вычисляем:
Шаг №2. Порядок результата равен большему порядку
i
чисел A1
Вычитание
и A2
i i i Pi P , i 1,..., n
Шаг №1.
Вычисляем:
Шаг №2. Порядок результата равен большему порядку
i
чисел
A1
и A2
Умножение
i i i
Шаг №1.
Вычисляем:
,
i 1,..., n
Шаг №2. Порядок результата равен сумме порядков
чисел
.
Pi
A1
и A2
Достоинством модулярной
системы счисления является
отсутствие переносов
между модулями, что
позволяет распараллелить
процесс выполнения
арифметических операций и
ускорить высокоточные
вычисления.
Недостатком:
сложность округления и
деление чисел только на
константы.

4.

Обобщенное представление комплексных чисел в модулярном
формате
Любое комплексное число А в формате с фиксированной точкой можно представить в виде:
a a a ... a, b b b ... b i (c c c ... c, d d d ... d )
kf
nf
A
или
где
nf
kf
x i y
x i y
2
kf
целое комплексное число такое, что:
x Z, y Z, 0 x 2
n f k f
1, 0 y 2
n f k f
1
Для представления комплексных чисел в модулярной системе счисления
должно выполняться неравенство:
( n 1)
Pi 2
i 1
2 ( n f k f ) 1

5.

Схема высокоточных вычислений с отложенным округлением
в модулярном формате
Выполнение q арифметических
операций без округления по
модулям P1 , P2 ,..., Pn
Выполнение q
арифметических
операций без округления
Нет
Прямое
преобразование
исходных
данных в
модулярную
систему
1
...
q
...
...
...
1
...
q
Проверка
необходимости
округления
q+1
...
2q
...
...
...
q+1
...
2q
Да
...
Преобразование
результатов в
позиционную
систему
счисления
...
Округление
до
требуемой
точности
Требования:
Входные данные:
1.
2.
Числовые данные (рац. и
компл. рациональные)
1.
Модули
(простые
P1 , P2 ,...,
Pn числа):
2.
Максимальная относительная
погрешность:
Максимальная абсолютная
k
погрешность 2 f
Правило выбора модулей:
n 1 / 2
Pi 2
(n f k f )
i 1
где
n f длина целой части
k f длина дробной части

6.

Возможная реализация схемы высокоточных вычислений с
отложенным округлением в многоядерной среде
Рациональные числа
A
B
Традиционные
вычисления
C
A
B
A
B
A
…
ЯДРО 1
A m1
ЯДРО 2
A m2
B m2
B m1
C m1
ЯДРО N-1
N 1
Bm
C m1
Целые числа
Am
B
N 1
Cm
C m2
C m2
…
ЯДРО N
C
Cm
N 1
N 1

7.

Структура графического ускорителя, на котором проводились
вычислительные эксперименты.
Мультипроцессор N
Графический ускоритель GeForce 9600M GT:
32 ядра, 4 мультипроцессора, 512Мб общей
Мультипроцессор 2
памяти.
Архитектура SIMD. Порядок использования
Мультипроцессор 1
графического ускорителя:
Разделяемая память
Регистры
Регистры
Регистры
Блок
Ядро 1
Ядро 2
Ядро N
команд
Константная
память
Текстурная
память
Общая память

8.

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

9.

СТРУКТУРНАЯ СХЕМА МОДУЛЯРНОГО ПРОЦЕССОРА
Оперативная память
Очередь команд
Декодирование команды
Диспетчеризация
Блок
переходов
Блок
сравнения
Блок
выбора
модулей
МС ПСС
Исполнительное ядро
Передача
Блок передачи результата
Процессор использует
конвейерную
обработку команд.
Процессор
содержит:
128 128-разрядных
регистров данных
АЛУ,
функцион.
модулярной
системе счисления

10.

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

11.

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

12.

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

13.

Структурные схемы узлов модулярного сопроцессора высокоточных
вычислений
1. Структурная схема устройства преобразования
Исходные данные:
целых чисел из позиционной системы в
целое число
модуль
N
модулярную систему счисления
p
Np
Результат:
N
p
t 1
ci bi
i 0
t 1
i 0
ki
kr
kl
i 0
p
где
ki c i
p
* bi
( t 1) / 2
k
i 0
i p
p
,
,
( t 1)
k
i p
i ( t 1) / 2
t log b N
t 1
i 0
p
( t 1) / 2
p
,
ki
p
c i bi
p
t 1
i 0
( t 1)
k
i p
i ( t 1) / 2
p
ci
p
bi
p
k r kl
p
p
,

14.

Структурные схемы узлов модулярного сопроцессора высокоточных
вычислений
2. Структурная схема сумматора
в модулярном формате
Исходные данные:
A
a1 , a2 ,..., an , ar
B
b1 , b2 ,..., bn , br
по mod p1
с1 , с2 ,..., сn , cr .
где:
a1 b1 ,
c1
a1 b1 p1 ,
a2 b2 ,
c2
a2 b2 p2 ,
...
Нахождение максимума порядков
,
Результат:
С
по mod pn
,
an bn ,
cn
an bn pn ,
cr max(ar , br )

15.

16.

Сводная таблица структурных схем с оценкой временных затрат
Структурная схема
Временные затраты в вентильных
задержках
Преобразователь 32-х разрядного
двоичного целого числа из ПСС в
27
МСС без суммирования
Конвейерный преобразователь N 32-х
разрядных двоичных целых чисел из
12 N 15
ПСС в МСС без суммирования
Преобразователь 32-х разрядного
числа с фиксированной точкой из
60
ПСС в МСС
32-х разрядный двоичный сумматор
чисел в модулярном формате
24
32-х разрядное двоичное устройство
умножения чисел в модулярном
37
формате
Конвейерный преобразователь N 32-х
разрядных двоичных целых чисел из
( n N 1) 37
n - модульной системы в смешанную
систему счисления
Устройство округления N 32-х
разрядных двоичных чисел в
модулярном формате по n -модулям
49 N n 22