ANALYTICAL FORM OF GARNER’S METHOD OF BASIS EXTENSION OF THE RESIDUE NUMBER SYSTEM
Authors:
1.
North Caucasus Federal University
Type:
Article
Pages:
from 53
to 59
Status:
Published
Received:
05.07.2016
Accepted:
25.07.2016
Published:
25.07.2016
Subject area:
VAC 05.12.2013 Системы, сети и устройства телекоммуникаций
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 004.02:004.2
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 004.02:004.2
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
Language:
Russian
Keywords:
residue number system, Garner method, basis extension, backward conversion, programmable logic device
Abstract (English):
The basic methods of extension of the basis of the residue number system are analyzed, the analytical assessments of the apparatus expenses are received. The conclusion on higher efficiency of the classical variant of Garner’s method while apparatus operating in terms of apparatus and time expenses is made. In accordance with the existing algorithmic description the analytical form of Garner’s method is designed; it helps to simplify the synthesis of the numerators of the basis extension of the residue number system, in particular apparatus operations, due to the fact, that the algorithmic method is replaced with its recurrent formula. The comparison of the apparatus operations of the modules of the basis extension of the residue number system based on the proposed analytical form and Garner’s classical method showed the equivalence. It is proposed to use the analytical form of Garner’s method to carry out the transformation of the codes of the residue number system into the positional codes of the traditional number system. The effectiveness of this solution while apparatus operating is shown.
The basic methods of extension of the basis of the residue number system are analyzed, the analytical assessments of the apparatus expenses are received. The conclusion on higher efficiency of the classical variant of Garner’s method while apparatus operating in terms of apparatus and time expenses is made. In accordance with the existing algorithmic description the analytical form of Garner’s method is designed; it helps to simplify the synthesis of the numerators of the basis extension of the residue number system, in particular apparatus operations, due to the fact, that the algorithmic method is replaced with its recurrent formula. The comparison of the apparatus operations of the modules of the basis extension of the residue number system based on the proposed analytical form and Garner’s classical method showed the equivalence. It is proposed to use the analytical form of Garner’s method to carry out the transformation of the codes of the residue number system into the positional codes of the traditional number system. The effectiveness of this solution while apparatus operating is shown.
Keywords:
residue number system, Garner method, basis extension, backward conversion, programmable logic device
residue number system, Garner method, basis extension, backward conversion, programmable logic device
Введение Рост быстродействия вычислительных машин в настоящее время не может быть осуществлен только за счет совершенствования технологического процесса, увеличения быстродействия элементарных вентилей и тактовой частоты вычислителей в целом. В связи с этим возникает острая необходимость в проведении вычислений параллельными средствами. Известно, что не все алгоритмы могут быть эффективно реализованы на параллельных вычислительных устройствах. Одним из путей решения этой проблемы является проведение вычислений в системе остаточных классов (СОК). Данная непозиционная система счисления позволяет, за счет естественного параллелизма, увеличить быстродействие некоторых операций [1]. В СОК существует ограничение на диапазон M представления чисел, равный произведению оснований и в общем случае , где - набор взаимно простых чисел [1]. При решении некоторых задач возникает необходимость изменения данного диапазона во время вычислений [2]. Изменение диапазона СОК возможно благодаря методам расширения базиса без осуществления преобразования кодов СОК в коды традиционной позиционной системы счисления (ПСС) с последующим обратным преобразованием в СОК. Уменьшение временных и аппаратных затрат позволяет считать расширение базиса важной немодулярной операцией. Аппаратные затраты - это важный критерий, отражающий количество элементарных логических вентилей, необходимых для построения аппаратных вычислителей. Методы расширения базиса системы остаточных классов В работе [3] показан метод Гарнера, являющийся основным для расширения базиса СОК. Суть метода состоит в последовательном вычитании из числа остатка модуля и последующем умножении на обратный элемент к этому модулю, последовательность выполняется для всех модулей [4]. В работах [5, 6] предложен так называемый метод матриц и констант. Метод основан на построении матрицы размера , с инициализацией предвычисленных констант и последующим умножением остатков на константы, сложением величин, и вычислении результирующего остатка. Недостатком данного метода является необходимость в реализации таблицы большого размера. Методы, предложенные в [7, 8], построены на основе ортогональных базисов и вычисления ранга числа. Суть данных методов состоит в неявном вычислении базиса и ранга числа (как при преобразовании кодов СОК в позиционный код). В случае явного преобразования новый остаток вычисляется как что эквивалентно . Существенным недостатком методов, описанных в [7, 8], являются вычисления с числами, значительно превышающими размер модуля СОК, в том числе при вычислении ранга числа a, что увеличивает затраты и задержки распространения сигналов при аппаратной реализации. В работе [9] рассмотрен метод расширения, основанный на промежуточном переходе через полиадический код. Недостатком такого подхода является вычисление промежуточных величин (константы полиадического кода), что требует размещения аппаратных многоразрядных вычислителей. При аппаратной реализации метода расширения базиса основными критериями выбора являются время вычисления и аппаратные затраты. На основании асимптотик времени вычисления и асимптотик аппаратной сложности возможно попытаться сделать вывод о предпочтительном методе или алгоритме при построении вычислителя. Для обеспечения высокой скорости вычисления необходимо, чтобы комбинационный путь распространения сигнала был как можно короче. Для сравнения методов можно сопоставить асимптотики комбинационного пути и аппаратных затрат (табл. 1). Таблица 1 Оценка асимптотик времени вычисления и аппаратных затрат основных методов расширения базиса СОК Метод расширения Асимптотика Оценка времени вычислений аппаратных затрат числа таблиц числа сумматоров n - число бит n - число модулей Гарнера Матриц и констант Shenoy A. P., Kumaresan R. [8] и Полиадический код и * Полноразрядный умножитель или таблица, разрядность которого эквивалентна диапазону СОК (разрядности произведения всех модулей). Результаты анализа позволяют сделать вывод, что для аппаратной реализации с модулями малой разрядности следует предпочесть метод Гарнера, для модулей большой разрядности - метод матриц и констант. Аналитическое описание метода Гарнера для расширения базиса системы остаточных классов Практическое применение алгоритмической записи метода Гарнера для расширения базиса СОК характеризуется высокой сложностью алгоритмизации для решения частной задачи [3]. Построим аналитическое описание методом индукции. 1. Приведем формулу для частного решения с одним модулем: . 2. Построим формулу для частного решения с двумя модулями (для примера СОК с набором оснований (3, 5) решение рассмотрено в табл. 2). Таблица 2 Пример расширения базиса методом Гарнера, до нового набора оснований (3, 5, 7) по исходным основаниям (3, 5) Операция Модуль 3 5 7 (новый) Исходное число 7 1 2 -1 0 1 1/3 2 -2 0 Можно заметить, что в данном случае , и для общего случая получим . 3. Аналогично, для большего числа оснований и путем обобщения результатов установлено, что для расширения базиса СОК можно использовать следующие выражения: (1) где искомый новый остаток от модуля ; - существующие модули СОК; - существующие остатки СОК; под операцией подразумевается взятие по модулю m, т. е. ; в качестве функций используются: (2) В общем виде можно предложить рекуррентную формулу: (3) где под операцией подразумевается умножение на обратный элемент по данному модулю m. Используя формулы (1)-(3), можно получить выражение для вычисления нового остатка по имеющемуся набору остатков. Для примера приведем формулу расширения базиса с набором оснований (3, 5, 7): где - новое основание (новое основание выбирает пользователь, т. е. тот, кто строит вычислитель для решения своей задачи). Аппаратная реализация При непосредственной тривиальной аппаратной реализации формул (1)-(3) аппаратные затраты имеют асимптотику и время вычисления . Обратим внимание на регулярную структуру выражений и построим вычислительный тракт модуля расширения базиса в виде дерева (рис. 1). На рис. 1 изображены вычислительные устройства расширения базиса СОК с набором оснований (3, 5), (3, 5, 7) и (3, 5, 7, 11), построенные по приведенным аналитическим выражениям (1)-(3). В квадрате с цифрой обозначен сумматор-умножитель, умножение происходит на константу по модулю. Это сделано в предположении, что в аппаратной реализации в каждом вычислительном узле фиксированный набор модулей. Благодаря этому отпадает необходимость в хранении таблиц обратных чисел, в вычислении этих чисел и реализации затратного аппаратного модулярного умножителя. Тем самым, объединив умножитель на константу (сумматор-умножитель) и сумматор, можно добиться экономии ресурсов. Заключительный этап вычисления - сложение - происходит по требуемому целевому модулю. Рис. 1. Схематическое изображение регулярной структуры аппаратной реализации расширения базиса СОК При реализации в виде дерева (рис. 1) аппаратные затраты имеют асимптотику , а время вычислений , где n - число модулей. Сумматор-умножитель (умножитель на константу) может быть реализован по различным схемам, таким как предварительное суммирование и табулирование (характерна малая задержка, но большой размер таблицы), а также модулярное суммирование и табулирование (меньший размер таблицы, но несколько большая задержка). На рис. 2 изображена аппаратная реализация расширения базиса с набором оснований (3, 5, 7), в которой реализованы сумматоры по модулю (модуль сумматора указан в обозначении сумматора, сумматор с обозначением m является сумматором по целевому модулю). Не трудно заметить, что данная схема состоит из n модулярных сумматоров с убывающими младшими модулями. В квадратах буквой «Т» обозначена таблица (таблица поиска, LUT). Рис. 2. Аппаратная реализация расширения базиса СОК с набором оснований (3, 5, 7): а - по предложенной аналитической записи; б - по методу Гарнера Очевидно, что реализации по аналитическим выражениям и по методу Гарнера требуют эквивалентных аппаратных затрат и имеют эквивалентный комбинационный путь, что говорит о сопоставимой задержке распространения сигналов. Таким образом, на основе полученных аналитических выражениях и рекуррентной формуле возможно строить вычислители любых наборов оснований более простым способом, чем в случае классического метода Гарнера, автоматизировав синтез схем. Преобразование кода системы остаточных классов в традиционный позиционный код путем расширения базиса СОК Предлагается использовать метод расширения базиса СОК в качестве преобразователя кодов СОК в коды традиционной ПСС. Для этого в качестве целевого модулярного сумматора достаточно применить сумматор по модулю , где n - разрядность целевой машины, т. е. применить традиционный двоичный сумматор. Данный преобразователь кодов имеет асимптотику времени вычислений , эквивалентную асимптотике преобразователя на основе метода ортогонального базиса. Достоинствами данного метода являются: - выполнение всех операций на модулярных вычислительных устройствах; - отсутствие необходимости хранить константы больших размеров; - отсутствие вычислений с длинной арифметикой; - высокая скорость преобразования. В табл. 3 приведена аналитическая оценка аппаратных затрат программируемой логической интегральной схемы (ПЛИС) при реализации устройства обратного преобразования кодов СОК в коды ПСС методом Гарнера для расширения базиса и методом ортогональных базисов. Таблица 3 Потребление ячеек ПЛИС при преобразовании из СОК в традиционную систему счисления Набор модулей СОК Метод Гарнера Метод ортогональных базисов Аналитическая форма Классический вариант Количество ячеек Длина Количество ячеек Длина Количество ячеек Длина (2) 0 0 0 0 0 0 (2, 3) 4 3 5 4 10 4 (2, 3, 5) 16 5 18 6 32 5 (2, 3, 5, 7) 36 7 38 8 78 6 (2, 3, 5, 7, 11) 57 9 60 10 135 7 Как видно из табл. 3, метод Гарнера требует меньше ячеек ПЛИС для своей реализации (разница более чем в 2 раза), причем с увеличением диапазона СОК достигается большее преимущество, зависящее от конкретного набора оснований. Основные затраты при реализации метода ортогональных базисов приходятся на вычисление ранга числа при нормировании результата. Следует отметить, что методы имеют эквивалентную длину комбинационного пути. При аналитической оценке аппаратных затрат предполагалось использование табличных вычислений (без встроенных умножителей), оптимизация трассировщиком не учитывалась. Длина комбинационного пути при использовании метода Гарнера несколько выше, число сумматоров в пути при распространении сигнала одинаково, увеличение длины комбинационного пути связано с размещением таблиц, время срабатывания которых минимально (т. к. требуется один дешифратор для срабатывания мультиплексора, реализующего таблицу поиска LUT). Вышеизложенное позволяет сделать вывод об эквивалентности времени вычислений и уменьшении аппаратных затрат. Заключение Таким образом, в ходе исследований были получены следующие результаты. 1. На основе классического варианта метода Гарнера получена аналитическая форма метода для расширения базиса СОК. 2. Для вычисления нового остатка СОК по существующему набору оснований получена рекуррентная формула. 3. Данные выражения позволяют организовать алгоритмический синтез аппаратных реализаций расширения базиса более простым путем. 4. Приведены аппаратные реализации для некоторых оснований. 5. Оценка времени вычислений и аппаратных затрат некоторых методов расширения базиса СОК показала, что асимптотика эквивалентна для всех методов, отличие состоит в сложности более низкого порядка и константе. 6. Предложено нестандартное использование метода расширения базиса СОК в качестве преобразователя кодов СОК в коды ПСС с целью уменьшения потребления ресурсов.
1. Omondi A., Premkumar B. Residue number systems. Theory and Implementation. London, Imperial College Press. 2007. 310 p.
2. Grankin V. V., Mezenceva O. S. K voprosu o realizacii modulyarnyh vychisliteley elementarnyh funkciy v srede LabVIEW i ih realizacii na PLIS // Materialy VI Mezhdunar. nauch.-tehn. konf. «Infokommunikacionnye tehnologii v nauke, proizvodstve i obrazovanii». Stavropol': SevKavGTI, 2014. S. 248-254.
3. Banerji D. K., Brzozowski J. A. On Translation Algorithms in Residue Number Systems // IEEE Transactions on Computers. 1972. Vol. C-21, No. 12, pp. 1281-1285.
4. Garner H. L. The residue number system // IRE Trans. Electronic Computer. 1959. Vol. EC-8. P. 140-147.
5. Chervyakov N. I., Mezenceva O. S., Lavrinenko I. N., Sivoplyasov D. V. Metod rasshireniya dinamicheskogo diapazona modulyarnogo neyrokomp'yutera // Neyrokomp'yutery: razrabotka, primenenie. 2005. № 7. S. 64-69.
6. Chervyakov N. I., Lavrinenko I. N., Lavrinenko S. V., Mezenceva O. S. Metody i algoritmy okrugleniya, masshtabirovaniya i deleniya chisel v modulyarnoy arifmetike // 50 let modulyarnoy arifmetike. Materialy Mezhdunar. nauch.-tehn. konf. (Zelenograd, 2005). M.: MIET, 2005. S. 291-310.
7. Bajard J. C., Didier L. S., Kornerup P. Modular multiplication and base extensions in residue number systems // Proceedings of the 15th IEEE Symposium on Computer Arithmetic. 2001. Vol. 2. P. 59-65.
8. Shenoy A. P., Kumaresan R. Fast base extension using a redundant modulus in RNS // IEEE Transactions on Computer. 1989. 38 (2). P. 292-296.
9. Chervyakov N. I., Ryadnov S. A., Sahnyuk P. A., Shaposhnikov A. V. Modulyarnye parallel'nye vychislitel'nye struktury neyroprocessornyh sistem. M.: Fizmatlit, 2003. 288 s.
