BC/NW 2007, №2, (11) :7.2
о возможности обобщения параллельной модулярной арифметики
для работы с двоичными дробями.
Ш. А.Оцоков
(Москва, Московский Энергетический Институт (ТУ), Россия)
Эффективность решения многих вычислительных задач на ЭВМ зависит от быстродействия и точности вычислений с плавающей точкой. Быстродействие вычислений с плавающей точкой ограничивается необходимостью учета межразрядных переносов, возникающих при сложении, вычитании и умножении чисел.
В модулярной системе счисления (МСС) арифметические выполняются без переносов по нескольким выбранным модулям. Благодаря чему существует возможность ускорения вычислений с многоразрядными числами за счет их распараллеливания по нескольким модулям [1]. Однако, МСС ориентирована на проведение целочисленных вычислений и поэтому применяется при решении специализированных задач цифровой обработки сигналов, в помехозащищенном кодировании и др.
Цель настоящей работы обобщить арифметику МСС для работы с двоичными дробями и тем самым расширить область её применения. Для описания предложенных алгоритмов работы с дробями рассмотрим представление двоичных дробей в МСС.
Известно, что любую двоичную дробь 
можно представить в следующем
виде:
, (1)
где
целая часть числа,
некратная двум.
дробная
часть числа, 
.
Пусть
произведение
простых модулей МСС, такое, что
, (2)
где
-
максимально возможное значение
.
Условие (2) обеспечивает представление отрицательных чисел в МСС.
В МСС число по модулю 
будет иметь следующий вид:
Восстановить число по
его модулярному представлению 
при условии (2) можно, если:
1.
Определить знаменатель .
2.
Умножить знаменатель на
по
модулю и получить числитель .
Определение знаменателя .
В процессе сложения, вычитания и умножения двоичных дробей возможны сокращения числителя и знаменателя на числа, которые являются степенями двойки. Для их обнаружения нужна проверка делимости числителя на числа вида 2t, (t>=1) Необходимо, чтобы эта проверка осуществлялась как можно быстрее, т.к. в противном случае применение модулярной арифметики не даст какого-либо эффекта ускорения вычислений.
Один из эффективных способов обнаружения делимости числителя – применение арифметики кодов Гензеля по модулю два [2]. Вычисления проводятся с двоичными дробями в модулярной арифметике и в кодах Гензеля параллельно и независимо друг от друга. Делимость числителя проверяется с помощью свойства кодов Гензеля: если в мантиссе кода Гензеля t младших разрядов нулевые, то числитель имеет делитель 2t . Коды Гензеля характеризуются двумя параметрами: модулем и длиной мантиссы. Так как вычисления проводятся с двоичными дробями, то модуль должен быть равным двум, если код Гензеля имеет s-разрядную мантиссу, то это означает, что может обнаружен делитель числителя вида 2t, где (t<=s). Если в процессе выполнения арифметических операций с двоичными дробями получен код Гензеля с нулевой мантиссой, тогда необходимы преобразование предыдущего результата арифметических операций из МСС в дробь, коррекция соответствующего ему кода Гензеля, увеличение длины мантиссы.
Предложен следующий формат представления двоичных дробей (рис 1).
|
m1 |
… mN |
H |
Рисунок 1. Формат представления двоичной дроби.
На рисунке 1 поля m1, … mN –
это значения в
МСС по модулям m1, … mN соответственно, а поле Н – это код
Гензеля числа .
Переполнение, округление в МСС.
Неравенство (2) определяет диапазон представимых двоичных дробей в МСС. Если в результате вычислений получена дробь, выходящая за пределы допустимого диапазона, то возникает ошибка переполнения и необходимо округление результата. Один из известных способов обнаружения переполнения в модулярных вычислениях основан на методе нулевизации, разработанный Акушским И.Я [1]. Для его реализации необходимо выбрать дополнительный модуль mN+1 удовлетворяющий условию:
( m1 ×…× mN mod mN+1 )-1 mod mN+1 º 1.
Увеличение количества модулей с одной стороны дает возможность расширить диапазон представления двоичных дробей и уменьшить количество возможных округлений в процессе вычислений, с другой стороны при заданном диапазоне уменьшить величину самих модулей. Последнее можно использовать для ускорения вычислений путем совмещения модульных операций. Если модули невелики можно заранее вычислить результаты выполнения последовательности 2-х арифметических операций для всевозможных входных данных и за один такт их выполнить. Рассмотрим правило округления двоичных дробей.
Правило округления числа А.
1. По коду Гензеля числа А (поле Н рисунок 1) определение знаменателя А и преобразование его в МСС
2. Умножение модулярного представления числа А ( поля m1, … mN рисунок 1) на результат в п.1
3. Преобразование модулярного представления числа А ( поля m1, … mN рисунок 1) в позиционную систему счисления.
4. Округления результата, полученного в п.3. до ближайшего целого, принадлежащему допустимому диапазону представления двоичных дробей.
Округление в МСС отличается от округления в позиционной системе счисления, тремя дополнительными операциями (пункт 1-3).
Существуют различные способы ускорения их выполнения, поэтому можно считать, что время округления в МСС не сильно отличается от времени округления в ПСС.
Для уменьшения количества округлений в процессе вычислений необходимо увеличить величину каждого из модулей или их количество в соответствие с неравенством:
m1 ×…× mN > (K max)V, где
V - характеризует параметр, показывающий какое количество арифметических операций умножения можно провести без округлений.
Модель вычислений с двоичными дробями представлена на рис.2
В соответствии с этой моделью исходные данные,
решаемой задачи – Х, преобразуются в СОК по заданным модулям р1,…,рN
и коды Гензеля. Далее проводятся вычисления по правилам модулярной арифметики и
кодов Гензеля. После выполнения каждых 
арифметических операций результат
округляется. Если в ходе вычислений возникает ошибка переполнения, т.е. 
, то результат
корректируется и вычисления продолжаются. Конечные результаты вычислений
преобразуются в двоичные дроби Y.
Рис. 2 . Модель вычислений с двоичными дробями.
Деление двоичных дробей сводится к преобразованию в позиционную систему счисления делителя, нахождению его обратного, преобразования в МСС и умножения на делимое. Недостатком МСС является сложность деления чисел. Поэтому модулярные вычислений с двоичными дробями будут эффективны в задачах с минимальным количеством делений. В целях ускорения целесообразно заменять операцию деления где это возможно на операцию умножения, например, если деление производится на некоторые заданные константы.
Ниже представлены правила сложения/вычитания и умножения двоичных дробей в МСС.
Сложение / вычитание
Входные данные:
Х1 mod m1, Х1 mod m 2, …, Х1 mod m N
Х2 mod m 1, Х2 mod m 2, …, Х2 mod m N
H(2,r, Х1 ), H(2,r, Х2 ) – коды Гензеля чисел Х1 и Х2
Выходные данные:
Сумма /разность чисел Y1= Х1 ± Х2 .
Y1 mod m 1, Y1 mod m 2, …, Y1 mod m N
H(2,r, Y1 ) – код Гензеля Y1 суммы/разности чисел Х1 и Х2
1. Определяется сумма/разность H(2,r, Y1 ) = H(2,r, Х1 ) ± H(2,r, Х2 )
2. Определяются значения выражений Y1 как сумма/разность чисел Х1 и Х2 по модулям m1, m 2, …, m N
Умножение
Входные данные:
Х1 mod P1, Х1 mod P2, …, Х1 mod PN
Х2 mod P1, Х2 mod P2, …, Х2 mod PN
H(2,r, Х1 ), H(2,r, Х2 ) – коды Гензеля чисел Х1 и Х2
Выходные данные:
Произведение чисел Y1= Х1 ± Х2 .
Y1 mod P1, Y1 mod P2, …, Y1 mod PN
H(2,r, Y1 ) – код Гензеля Y1 произведения чисел Х1 и Х2
1. Определяется произведение H(2,r, Y1 ) = H(2,r, Х1 )* H(2,r, Х2 )
2. Определяются значения выражений Y1 как произведение чисел Х1 и Х2 по модулям m1, m 2, …, m N
ВЫВОДЫ
В статье обобщены алгоритмы многомодульной арифметики для работы с двоичными дробями. Перспективным направлением дальнейшей работы является исследование возможностей реализации методов решения дифференциальных уравнений Рунге-Кутта, Эйлера и других численных методов на основе многомодульной арифметики двоичных дробей на процессорах многоядерной архитектуры.
Литература
1. Акушский И.Я, Юдицкий. Д.И. Машинная арифметика системы остаточнх классов. – М.: 1968.
2. Грегори Р., Кришнамурти Е. Безошибочные вычисления. Методы и приложения: Пер. с англ. – М.: Мир, 1998.