BC/NW 2007, №2, (11) :7.2

о возможности обобщения параллельной модулярной арифметики

для работы с двоичными дробями.

Ш. А.Оцоков

(Москва, Московский Энергетический Институт (ТУ), Россия)

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

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

Цель настоящей работы обобщить арифметику МСС для работы с двоичными дробями и тем самым расширить область её применения. Для описания предложенных алгоритмов работы с дробями рассмотрим представление двоичных дробей в МСС.

Известно, что любую двоичную дробь можно представить в следующем виде:

, (1)

где

целая часть числа, некратная двум.
дробная часть числа, .

Пусть произведение простых модулей МСС, такое, что

, (2)

где

- максимально возможное значение.

Условие (2) обеспечивает представление отрицательных чисел в МСС.

В МСС число по модулю будет иметь следующий вид:

Восстановить число по его модулярному представлению при условии (2) можно, если:

- определить знаменатель .

- умножить знаменатель на по модулю и получить числитель .

Определение знаменателя

В процессе сложения, вычитания и умножения двоичных дробей возможны сокращения числителя и знаменателя на числа, которые являются степенями двойки. Для их обнаружения нужна проверка делимости числителя на числа вида 2^t, (t>=1) Необходимо, чтобы эта проверка осуществлялась как можно быстрее, т.к. в противном случае применение модулярной арифметики не даст какого-либо эффекта ускорения вычислений.

Один из эффективных способов обнаружения делимости числителя – применение арифметики кодов Гензеля по модулю два [2]. Вычисления проводятся с двоичными дробями в модулярной арифметике и в кодах Гензеля параллельно и независимо друг от друга. Делимость числителя проверяется с помощью свойства кодов Гензеля: если в мантиссе кода Гензеля t младших разрядов нулевые, то числитель имеет делитель 2^t . Коды Гензеля характеризуются двумя параметрами: модулем и длиной мантиссы. Так как вычисления проводятся с двоичными дробями, то модуль должен быть равным двум, если код Гензеля имеет s-разрядную мантиссу, то это означает, что может обнаружен делитель числителя вида 2^t, где (t<=s). Если в процессе выполнения арифметических операций с двоичными дробями получен код Гензеля с нулевой мантиссой, тогда необходимы преобразование предыдущего результата арифметических операций из МСС в дробь, коррекция соответствующего ему кода Гензеля, увеличение длины мантиссы.

Предложен следующий формат представления двоичных дробей
(рис 1).

m1

… mN

H

Рис. 1. Формат представления двоичной дроби

На рис.1 поля m₁, … m_N – это значения в МСС по модулям
m₁, … m_N соответственно, а поле Н – это код Гензеля числа .

Переполнение, округление в МСС

Неравенство (2) определяет диапазон представимых двоичных дробей в МСС. Если в результате вычислений получена дробь, выходящая за пределы допустимого диапазона, то возникает ошибка переполнения и необходимо округление результата. Один из известных способов обнаружения переполнения в модулярных вычислениях основан на методе нулевизации, разработанный Акушским И.Я [1]. Для его реализации необходимо выбрать дополнительный модуль m_N+1 удовлетворяющий условию:

( m₁ ×…× m_N mod m_N+1 )^-1 mod m_N+1 º 1.

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

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

1. По коду Гензеля числа А (поле Н рисунок 1) определение знаменателя А и преобразование его в МСС

2. Умножение модулярного представления числа А ( поля m₁, … m_N рис. 1) на результат в п.1

3. Преобразование модулярного представления числа А ( поля m₁, … m_N рис. 1) в позиционную систему счисления.

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

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

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

m₁ ×…× m_N > (K max)^V,

где

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

Модель вычислений с двоичными дробями представлена на рис.2.

В соответствии с этой моделью исходные данные, решаемой задачи – Х, преобразуются в СОК по заданным модулям р₁,…,р_N и коды Гензеля. Далее проводятся вычисления по правилам модулярной арифметики и кодов Гензеля. После выполнения каждых арифметических операций результат округляется. Если в ходе вычислений возникает ошибка переполнения, т.е. , то результат корректируется и вычисления продолжаются. Конечные результаты вычислений преобразуются в двоичные дроби Y.

Рис. 2 . Модель вычислений с двоичными дробями.

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

Ниже представлены правила сложения/вычитания и умножения двоичных дробей в МСС.

Сложение / вычитание

Входные данные:

Х₁ mod m₁, Х₁ mod m ₂, …, Х₁ mod m _N

Х₂ mod m ₁, Х₂ mod m ₂, …, Х₂ mod m _N

H(2,r, Х₁ ), H(2,r, Х₂ ) – коды Гензеля чисел Х₁ и Х₂

Выходные данные:

Сумма /разность чисел Y₁= Х₁ ± Х₂ .

Y₁ mod m ₁, Y₁ mod m ₂, …, Y₁ mod m _N

H(2,r, Y₁ ) – код Гензеля Y₁ суммы/разности чисел Х₁ и Х₂

1. Определяется сумма/разность H(2,r, Y₁ ) = H(2,r, Х₁ ) ± H(2,r, Х₂ )
2. Определяются значения выражений Y₁ как сумма/разность чисел Х₁ и Х₂ по модулям m₁, m ₂, …, m _N

Умножение

Входные данные:

Х₁ mod P₁, Х₁ mod P₂, …, Х₁ mod P_N

Х₂ mod P₁, Х₂ mod P₂, …, Х₂ mod P_N

H(2,r, Х₁ ), H(2,r, Х₂ ) – коды Гензеля чисел Х₁ и Х₂

Выходные данные:

Произведение чисел Y₁= Х₁ ± Х₂ .

Y₁ mod P₁, Y₁ mod P₂, …, Y₁ mod P_N

H(2,r, Y₁ ) – код Гензеля Y₁ произведения чисел Х₁ и Х₂

1. Определяется произведение H(2,r, Y₁ ) = H(2,r, Х₁ )* H(2,r, Х₂ )

2. Определяются значения выражений Y₁ как произведение чисел Х₁ и Х₂ по модулям m₁, m ₂, …, m _N

ВЫВОДЫ

В статье обобщены алгоритмы многомодульной арифметики для работы с двоичными дробями.

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

Литература

1. Акушский И.Я, Юдицкий. Д.И. Машинная арифметика системы остаточнх классов. – М.: 1968.

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