АНАЛИТИЧЕСКАЯ ФОРМА МЕТОДА ГАРНЕРА ДЛЯ РАСШИРЕНИЯ БАЗИСА СИСТЕМЫ ОСТАТОЧНЫХ КЛАССОВ
Авторы:
1.
Северо-Кавказский федеральный университет
Тип:
Статья
Страницы:
с 53
по 59
Статус:
Опубликован
Получено:
05.07.2016
Одобрено:
25.07.2016
Опубликовано:
25.07.2016
Классификаторы:
ВАК 05.12.2013 Системы, сети и устройства телекоммуникаций
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 004.02:004.2
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 004.02:004.2
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
Язык материала:
русский
Ключевые слова:
система остаточных классов, метод Гарнера, расширение базиса, преобразование в позиционный код
Аннотация (русский):
Проведен анализ основных методов расширения базиса системы остаточных классов, получены аналитические оценки аппаратных затрат. Сделан вывод о большей эффективности классического варианта метода Гарнера при аппаратной реализации с позиций аппаратных и временных затрат. По существующему алгоритмическому описанию построена аналитическая форма метода Гарнера, которая позволяет упростить синтез вычислителей расширения базиса системы остаточных классов, в особенности аппаратных реализаций, благодаря тому, что алгоритмический способ построения заменен его рекуррентной формулой. Сравнение аппаратной реализации модулей расширения базиса системы остаточных классов на основе предложенной аналитической формы и классического варианта метода Гарнера показало их эквивалентность. Аналитическую форму метода Гарнера предложено использовать для осуществления преобразования непозиционных кодов системы остаточных классов в позиционный код традиционной системы счисления. Показана эффективность такого решения при аппаратной реализации.
Проведен анализ основных методов расширения базиса системы остаточных классов, получены аналитические оценки аппаратных затрат. Сделан вывод о большей эффективности классического варианта метода Гарнера при аппаратной реализации с позиций аппаратных и временных затрат. По существующему алгоритмическому описанию построена аналитическая форма метода Гарнера, которая позволяет упростить синтез вычислителей расширения базиса системы остаточных классов, в особенности аппаратных реализаций, благодаря тому, что алгоритмический способ построения заменен его рекуррентной формулой. Сравнение аппаратной реализации модулей расширения базиса системы остаточных классов на основе предложенной аналитической формы и классического варианта метода Гарнера показало их эквивалентность. Аналитическую форму метода Гарнера предложено использовать для осуществления преобразования непозиционных кодов системы остаточных классов в позиционный код традиционной системы счисления. Показана эффективность такого решения при аппаратной реализации.
Ключевые слова:
система остаточных классов, метод Гарнера, расширение базиса, преобразование в позиционный код
система остаточных классов, метод Гарнера, расширение базиса, преобразование в позиционный код
Введение Рост быстродействия вычислительных машин в настоящее время не может быть осуществлен только за счет совершенствования технологического процесса, увеличения быстродействия элементарных вентилей и тактовой частоты вычислителей в целом. В связи с этим возникает острая необходимость в проведении вычислений параллельными средствами. Известно, что не все алгоритмы могут быть эффективно реализованы на параллельных вычислительных устройствах. Одним из путей решения этой проблемы является проведение вычислений в системе остаточных классов (СОК). Данная непозиционная система счисления позволяет, за счет естественного параллелизма, увеличить быстродействие некоторых операций [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. Гранкин В. В., Мезенцева О. С. К вопросу о реализации модулярных вычислителей элементарных функций в среде LabVIEW и их реализации на ПЛИС // Материалы VI Междунар. науч.-техн. конф. «Инфокоммуникационные технологии в науке, производстве и образовании». Ставрополь: СевКавГТИ, 2014. С. 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. Червяков Н. И., Мезенцева О. С., Лавриненко И. Н., Сивоплясов Д. В. Метод расширения динамического диапазона модулярного нейрокомпьютера // Нейрокомпьютеры: разработка, применение. 2005. № 7. С. 64-69.
6. Червяков Н. И., Лавриненко И. Н., Лавриненко С. В., Мезенцева О. С. Методы и алгоритмы округления, масштабирования и деления чисел в модулярной арифметике // 50 лет модулярной арифметике. Материалы Междунар. науч.-техн. конф. (Зеленоград, 2005). М.: МИЭТ, 2005. С. 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. Червяков Н. И., Ряднов С. А., Сахнюк П. А., Шапошников А. В. Модулярные параллельные вычислительные структуры нейропроцессорных систем. М.: Физматлит, 2003. 288 с.
