Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,674

MORE ACCURATE METHOD OF CALCULATING THE APPROXIMATE POSITIONAL CHARACTERISTIC FOR IMPLEMENTATION NON-MODULAR OPERATIONS IN RNS

Isupov K.S. 1
1 Vyatka State University
The residue number system (RNS) has several advantages over the positional number systems. It allows you to process individual digits of numbers without carry out transfers between, and so is suitable for multi-core architecture of modern processors. The main drawbacks of the RNS associated with the unobviousness of non-modular operations (comparison, overflow control, work with the sign, etc.). Exact methods of implementation non-modular operations have high computational or hardware complexity, therefore, the method, which is based on the approximate positional characteristics of numbers in the RNS, is most perspective among the well-known. It has low computational complexity and does not require large hardware expenses for implementation. However, the calculation of the approximate positional characteristics of modular numbers can be accompanied by significant rounding errors, which, ultimately, may contribute to incorrect execution of non-modular operation. The method of calculate the approximate positional characteristics of the modular numbers, which allows you to reduce the amount of rounding errors, considered in this article.
residue number system
non-modular operation
positional characteristic
rounding errors
1. Akushskiy I.Ya., Yuditskiy D.I. Mashinnaya arifmetika v ostatochnykh klassakh [Machine arithmetic in residue classes] Moskow, «Sovetskoe radio», 1968. 440 p.
2. Kopchenova N.V., Maron I.A. Vychislitel’naja matematika v primerah i zadachah [Computational mathematics in examples and tasks] St. Petersburg, «Lan’», 2008. 368 p.
3. Knut D. Iskusstvo programmirovanija dlja JeVM. T. 2. Poluchislennye algoritmy [The Art of Computer Programming. Volume 2: Seminumerical Algorithms]. Moscow, «World», 1977. 728 p.
4. Chervyakov N.I. Metody, algoritmy i tekhnicheskaya realizatsiya osnovnykh problemnykh operatsiy, vypolnyaemykh v sisteme ostatochnykh klassov – Methods, algorithms and technical implementation of the basic problematic operations performed in the residue number system. Infokommunikatsionnye tekhnologii – Infocommunication Technology. 2011, no. 4. pp. 4–12.
5. Chervyakov N.I., Averbukh V.M., Babenko M.G., Lyakhov P.A.,Gladkov A.V., Gapochkin A.V. Priblizhennyj metod vypolnenija nemodul’nyh operacij v sisteme ostatochnyh klassov – Approximate method of implementation non-modular operations in the residue number system – Fundamental Research. 2012, no.6. pp. 189–193.
6. Omondi, Amos R., and Benjamin Premkumar. Residue number systems theory and implementation. London: Imperial College Press, 2007. 312 p.

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

1. Представление чисел в системе остаточных классов

Пусть задан ряд натуральных попарно взаимно простых чисел p1, p2, ..., pn. Тогда для любых целых x1, x2, ..., xn, таких, что 0 ≤ xi < pi существует целое X ∈ [0, P – 1], которое при делении на pi дает остаток xi для всех i = 1, 2, …, n, где Eqn1.wmf (китайская теорема об остатках [3]). Сказанное означает, что между прямым произведением колец Eqn2.wmf и кольцом Eqn3.wmf существует биективное отображение Eqn4.wmf. Кортеж ⟨x1, x2, ..., xn⟩ определяется решением сравнений Eqn5.wmf для всех i = 1, 2, …, n. Зададим последовательность чисел B1, B2, ..., Bn, таких, что Eqn6.wmf где Eqn7.wmf, а Eqn8.wmf – мультипликативная инверсия от Pi по модулю pi. Тогда отображение Eqn120.wmf определится следующим образом:

Eqn9.wmf (1)

Тем самым на основе чисел p1, p2, ..., pn определяется система остаточных классов (СОК, Residue Number System) [1, 6] с полным диапазоном P и ортогональными базисами B1, B2, ..., Bn. Порождающие числа p1, p2, ..., pn называются основаниями (модулями) СОК. Вычеты xi в выражении (1) называют модулярными разрядами, а образованный ими кортеж – модулярным числом. Модулярное число будем обозначать следующим образом [6]:

Eqn10.wmf (2)

В СОК определены основные арифметические операции, которые делятся на две группы:

1. Модульные операции, к которым относятся арифметическое сложение, умножение, поразрядное сравнение модулярных чисел и т.д.

2. Немодульные операции, которые включают сравнение, вычитание модулярных чисел с возможностью получения отрицательного результата, контроль переполнения, округление (частный случай – масштабирование), деление и т.д.

Важнейшим преимуществом СОК является возможность параллельного выполнения модульных операций по всем разрядам операндов. Например, если даны Eqn11.wmf, Eqn12.wmf и необходимо получить Eqn13.wmf, такой, что Eqn14.wmf, то функция Eqn15.wmf, отвечающая модульной операции, естественным образом представляется в виде декомпозиции более простых функций Eqn16.wmf, таких, что Eqn17.wmf т.е. каждый разряд результата является функцией разрядов мантисс операндов по соответствующему основанию и не зависит от остальных разрядов.

Основные недостатки СОК связаны с неочевидностью выполнения немодульных операций. В отличие от модульных, немодульные операции требуют знания величины модулярных чисел в целом. Значение каждой цифры результата немодульной операции не является функцией значений соответствующих цифр операндов, а зависит от значений этих операндов в целом, что обуславливает сложность выполнения таких операций.

2. Выполнение немодульных операций в СОК на основе приближенных позиционных характеристик

В основе алгоритмов выполнения немодульных операций лежат методы вычислений позиционных характеристик модулярных чисел [5]. Под позиционной характеристикой принято понимать выраженную тем или иным образом информацию о позиционном значении модулярного числа (2). Известны точные позиционные характеристики: ранг, след, коэффициенты обобщенной позиционной системы, диагональ и т.д. [1, 6]. Однако методы их вычисления характеризуются высокой вычислительной сложностью либо требуют больших аппаратурных затрат для хранения подстановочных данных. Поэтому полезной альтернативой точных является приближенный метод выполнения немодульных операций, предложенный Н.И. Червяковым и его коллегами в работах [4, 5]. Данный метод основан на вычислении приближенной позиционной характеристики, которая представляет собой округленное значение отношения модулярного числа к полному диапазону СОК [4, 5]:

Eqn18.wmf (3)

где Eqn19.wmf – разряды модулярного числа Eqn20.wmf, Eqn21.wmf – константы, вычисляемые заранее и округленные в пределах разрядности вычислительного устройства, Eqn8.wmf– мультипликативная инверсия от Eqn7.wmf, Eqn22.wmf – дробная часть аргумента. В работе [5] определен ряд простых правил применения приближенных позиционных характеристик для выполнения таких операций, как определение знака, сравнение, обнаружение ошибки и переполнения модулярных чисел, локализации ошибочного разряда.

Главным преимуществом приближенного метода выполнения немодульных операций в СОК является его низкая вычислительная сложность, порядка О(n) по количеству модулей (для последовательного алгоритма), в то время как точные методы либо требуют выполнения n2 и более операций, либо вызывают необходимость хранения подстановочных таблиц больших объемов. Например, при известных приближенных характеристиках правило сравнения чисел Eqn11.wmf и Eqn12.wmf состоит в анализе условий [5]:

Eqn23.wmf

т.е. операция сравнения чисел в СОК сводится к вычислению приближенных позиционных характеристик по формуле (3) и их сопоставлению как обычных дробных чисел, представленных в одном из аппаратно поддерживаемых форматов данных. Вместе с тем, эта же операция при использовании, например, метода потактового перехода к полиадическому коду требует в предельном случае выполнения 2n тактов, каждый i-й из которых состоит из 2n – i операций над модулярными разрядами сравниваемых чисел.

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

Пример. Пусть p1 = 7, p2 = 9, p3 = 11, p4 = 13 – модули СОК, P = 9009 – их произведение. Для данных модулей константы Ki из формулы (3) определятся следующим образом: K1 ≈ 0,86, K2 ≈ 0,56, K3 ≈ 0,82, K4 ≈ 0,77. Число разрядов для представления констант выбиралось в соответствии с числом разрядов, необходимых для представления модулей СОК. Пусть Eqn24.wmf, Eqn25.wmf – модулярные числа, которые необходимо сравнить по величине.В соответствии с формулой (3) имеем: Eqn26.wmf, Eqn27.wmf. Таким образом, будет сделан вывод, что Eqn28.wmf. Однако это заключение не соответствует истине. Действительно, преобразуя числа Eqn29.wmf и Eqn30.wmf к целочисленному представлению по формуле (1), получим:

Eqn31.wmf;

Eqn32.wmf. □

В рассмотренном примере показана ситуация, когда ошибки округления привели к существенной относительной погрешности при вычислении приближенной характеристики модулярного числа Eqn29.wmf: точное ее значение равно ≈ 0,089, следовательно, Eqn33.wmf. Такое значение погрешности указывает на то, что приближенная позиционная характеристика не содержит ни одного верного разряда, что и привело в итоге к неверному заключению о результате сравнения чисел Eqn29.wmf и Eqn30.wmf. При этом модулярный код числа Eqn24.wmf не указывает явно на возможность появления такой существенной погрешности, вследствие чего верифицировать корректность операции сравнения Eqn29.wmf и Eqn30.wmf, как, впрочем, и любой другой немодульной операции, выполняемой с использованием приближенных позиционных характеристик, не представляется возможным.

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

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

Оценим погрешности, свойственные приближенной позиционной характеристике модулярного числа, вычисленной по формуле (3) с учетом округлений. Пусть в СОК с модулями p1, p2, ..., pn и полным диапазоном P = p1∙p2∙...∙pn задано модулярное число Eqn11.wmf. Пусть Eqn34.wmf – точное значение отношения Eqn29.wmf к P, определяемое, в соответствии с китайской теоремой об остатках, следующим образом:

Eqn35.wmf (4)

Здесь предполагается, что все слагаемые представленной суммы определяются точно (без округлений). Представим отношение мультипликативной инверсии от Pi к модулю pi в виде:

Eqn36.wmf

где Ki – константа СОК из формулы (3), вычисленная с конечной точностью представления, а Δ(Ki) – ее абсолютная погрешность округления. Тогда, воспользовавшись законами распространения абсолютных ошибок при умножении [2], получим:

Eqn37.wmf,

где x1, x2, ..., xn – модулярные разряды числа Eqn29.wmf. Так как Eqn38.wmf, то

Eqn39.wmf

Известно, что максимальная абсолютная погрешность алгебраической суммы приближенных чисел равна сумме абсолютных погрешностей слагаемых, поэтому

Eqn40.wmf

где Eqn34.wmf определяется по формуле (4).

Следовательно, если приближенная позиционная характеристика определяется по формуле (3), то абсолютная и относительная погрешности будут ограничены неравенствами

Eqn41.wmf

Заключаем таким образом, что погрешности, возникающие при определении приближенной позиционной характеристики по формуле (3), существенным образом зависят от суммы x1 + x2 + ... + xn значений разрядов модулярного числа Eqn29.wmf. Пусть двоичное представление всех констант Ki состоит из k разрядов, причем под дробную часть отведено k – 1 разрядов. Если все модули СОК p1, p2, ..., pn состоят также из k разрядов, то при округлении «до ближайшего» Eqn42.wmf. Следовательно,

Eqn43.wmf (5)

Способом уменьшения погрешностей (5) является изменение порядка арифметических действий при вычислении приближенной позиционной характеристики с ограниченной точностью по формуле (4): вначале следует вычислить произведение Eqn44.wmf, а уже потом поделить его на модуль pi. Это позволит избежать накопления погрешностей при умножении округленного числа на соответствующий модулярный разряд. Обозначим Eqn45.wmf и выполним его разложение: Qi = Si pi + Ni для всех i = 1, 2, …, n. Здесь Ni является остатком от деления Qi на основание СОК pi, т.е.

Eqn46.wmf

тогда формула (5) перепишется в следующем виде:

Eqn47.wmf

Целой частью Si каждого слагаемого в данной сумме можно пренебречь, что позволит работать в пределах разрядности модулей СОК. Таким образом, получается уточненная формула для определения приближенной позиционной характеристики модулярного числа:

Eqn48.wmf (6)

Погрешность каждого слагаемого в представленной сумме не зависит прямым образом от значений знакопозиций xi и определяется при использовании алгоритма округления «до ближайшего» половиной значения младшего разряда машинного представления позиционной характеристики. Если под представление Eqn49.wmf отведено k двоичных разрядов (и столько же для каждого модуля СОК), из которых k – 1 разряд соответствует дробной части, то формуле (6) будут свойственны следующие оценки погрешностей:

Eqn50.wmf (7)

Сопоставив формулы (5) и (7), получим, что формула (6) позволяет уменьшить погрешности при вычислении приближенной позиционной характеристики в Eqn51.wmf раз, где M[xi] – математическое ожидание значения i-й цифры xi в представлении модулярного числа.

Пример. Возьмем исходные данные из рассмотренного ранее примера: p1 = 7, p2 = 9, p3 = 11, p4 = 13, P = 9009. Для представленных модулей СОК значения мультипликативных инверсий Eqn8.wmf определятся следующим образом:

Eqn52.wmf, Eqn53.wmf,Eqn54.wmf, Eqn55.wmf

Пусть, как и ранее, требуется сравнить модулярные числа Eqn56.wmf и Eqn57.wmf. Вычисляя их приближенные позиционные характеристики в соответствии с формулой (6), с округлением до двух десятичных разрядов после точки, получим:

Eqn58.wmf

Eqn59.wmf, поэтому будет сделан верный вывод, что Eqn60.wmf. Таким образом, при равных условиях вычисление приближенных позиционных характеристик по уточненной формуле позволило получить правильный результат сравнения чисел в СОК. □

Заключение

Предложен способ вычисления приближенной позиционной характеристики модулярного числа, позволяющий уменьшить значения ошибок округления, по сравнению с известным способом, в Eqn61.wmf раз, где n – количество модулей СОК, а M[xi] – математическое ожидание значения i-й цифры в представлении модулярного числа. Определение приближенной характеристики по уточненной формуле требует выполнения n обращений к памяти за выборкой значений мультипликативных инверсий, n умножений, n делений и одну операцию n-операндного суммирования с отбрасыванием целой части. Таким образом, его временная сложность, выраженная в условных тактах, составляет 4n, где n – количество модулей СОК, в то время как известная формула (3) требует приблизительно 3n тактов. Очевидно, что порядок сложности при этом остается прежним, O(n). Применяя параллельные вычисления, определение приближенной позиционной характеристики по формуле (6) может быть выполнено за Eqn62.wmf тактов.

Рецензенты:

Шатров А.В., д.ф.-м.н., профессор, заведующий кафедрой математического моделирования в экономике Вятского государственного университета, г. Киров;

Частиков А.В., д.т.н., профессор, декан факультета прикладной математики и телекоммуникаций Вятского государственного университета, г. Киров.

Работа поступила в редакцию 22.02.2013.