ВЫЧИСЛИТЕЛЬНЫЙ ЭЛЕМЕНТ БИМОДУЛЬНОЙ МОДУЛЯРНОЙ АРИФМЕТИКИ

Область техники
Полезная модель относится к устройствам автоматики и вычислительной техники, входящим в состав модульных и немодульных арифметико-логических устройств модулярного процессора, предназначенного для реализации арифметических операций, и может быть использовано в вычислительных структурах, функционирующих в модулярной системе счисления.
Уровень техники
Характерной чертой современной вычислительной техники является стремление использовать вычислительные системы с повышенным быстродействием и относительно высокой степенью надежности. Существуют различные методы повышения быстродействия от использования специализированных алгоритмов до повышения степени интеграции схем. При этом параметры надежности вычислительных систем в основном не оптимизируются. Основным методом, который широко применяется при построении высоконадежных устройств, является резервирование [1]. Однако для любого из способов резервирования характерна высокая избыточность элементов системы, это объясняется, прежде всего, универсальностью метода, поскольку, таким образом, корректируются ошибки любых типов, и практически не учитывается специфика конкретного вычислительного устройства. В этой связи становится актуальной задача построения такой вычислительной системы, которая удовлетворяла бы необходимым требованиям по быстродействию и надежности при высокой степени интеграции элементов схемы. К таким оптимизированным системам относятся модулярные вычислительные системы. Известно, что модулярная арифметика обладает не только высокой степенью параллелизма при выполнении модульных операций, но и высокой точностью и надежностью вычислений, способностью системы контролировать и исправлять ошибки во время выполнения модульных операций [2].
Известные технические решения (US 005117383 A (1992 г.), RU 2109326 (1998 г.), RU 2157560 (2000 г.)), реализующие модулярные вычисления, базируются в первую очередь на схемотехническом исполнении вычислений данного класса, а не на применении специализированного математического аппарата. Элементная база, использованная в данных технических решениях, в настоящее время морально устарела. Также к недостаткам подобных решений можно отнести существенные аппаратные затраты, связанные с использованием больших объемов памяти для реализации вычислительных операций.
Наиболее близким по технической сущности прототипом предлагаемой полезной модели является техническое решение, описанное в патенте RU 123995 (2012 г.), основанное на традиционных способах построения арифметических узлов. К недостаткам прототипа можно отнести значительные аппаратные и временные различия при выполнении мультипликативных и аддитивных операций.
Раскрытие полезной модели
Задачей предлагаемой полезной модели является повышение быстродействия и уменьшение аппаратных затрат при выполнении арифметических операций в модулярной арифметике. Технический результат, позволяющий достичь поставленной задачи, состоит в выполнении аддитивных и мультипликативных операций на одних узлах (то есть аппаратно однотипно) вычислительного элемента бимодульной модулярной арифметики, что становится возможным благодаря однотипному кодовому представлению операндов. Такое решение позволило сократить время выполнения модульных операций, а также площадь, занимаемую вычислительным элементом на кристалле в сравнении с аналогами.
Согласно предлагаемой полезной модели, этот технический результат достигается за счет того, что в вычислительный элемент бимодульной модулярной арифметики (фиг. 1), содержащий устройство управления (1), оперативное запоминающее устройство (ОЗУ) (2), постоянное запоминающее устройство (ПЗУ) (3), мультиплексор (4) введен арифметический узел (5). реализованный с помощью пяти мультиплексоров (6-10), двоичного сумматора (11), двух преобразователей «минус единица» (12, 13), преобразователя «минус р» (14), преобразователя «минус (р-1)» (15), компаратора (16), логического блока (17), ПЗУ для хранения таблицы бимодульной пары (18), блока выходных регистров (19), причем выход устройства управления (1) соединен с четвертым входом логического блока (17), управляющим входом ПЗУ для хранения таблицы бимодульной пары (18) и управляющими входами первого (6), второго (7), четвертого (9) и пятого (10) мультиплексоров арифметического узла, сигнал с первого мультиплексора (6) поступает соответственно на вход первого преобразователя «минус единица» (12), первый вход двоичного сумматора (11) и второй вход логического блока (17), сигнал со второго мультиплексора (7) поступает соответственно на вход второго преобразователя «минус единица» (13), второй вход двоичного сумматора (11) и третий вход логического блока (17), выход первого преобразователя «минус единица» (12) соединен с первым информационным входом третьего мультиплексора (8), выход второго преобразователя «минус единица» (13) соединен с восьмым информационным входом третьего мультиплексора (8), выход двоичного сумматора (11) соединен с входом преобразователя «минус р» (14), входом преобразователя «минус (р-1)» (15), пятым информационным входом третьего мультиплексора (8) и входом компаратора (16), выход преобразователя «минуса» (14) соединен с третьим информационным входом третьего мультиплексора (8), выход преобразователя «минус (р-1)» (15) соединен с четвертым информационным входом третьего мультиплексора (8), а на второй, шестой и седьмой информационные входы третьего мультиплексора (8) поступают константные значения, выход компаратора (16) соединен с первым входом логического блока (17), выход третьего мультиплексора (8) соединен с информационным входом ПЗУ для хранения таблицы бимодульной пары (18) и с первыми информационными входами четвертого (9) и пятого (10) мультиплексоров арифметического узла, выход ПЗУ для хранения таблицы бимодульной пары (18) соединен со вторыми информационными входами четвертого (9) и пятого (10) мультиплексоров, выходы которых соединены с блоком выходных регистров (19), выход которого является выходом арифметического узла (5), при этом первый вход первого мультиплексора (6) арифметического узла соединен с ПЗУ (3), вторые входы первого (6) и второго (7) мультиплексоров арифметического узла соединены с ОЗУ (2), а выход блока выходных регистров (19) соединен с первым информационным входом мультиплексора (4).
Краткое описание чертежей
На фиг. 1 представлена схема Вычислительного элемента бимодульной модулярной арифметики.
На фиг. 2 представлены графики зависимости занимаемой на кристалле площади от величины базового модуля р для прототипа и предлагаемой полезной модели.
Осуществление полезной модели
i
1
2
m
i
i
i
Д.А. Поспелов в работе [3] предложил каждый вычет  модулярной арифметики, где р является базисным основанием из набора {p, р, …p} простых модулей, представлять парой - . Такое представление вычетов позволяет свести все операции по каждому модулю p, к однотипной реализации через сумматоры по модулям p, p-1 соответственно. Такого типа компьютерная арифметика называется бимодульной модулярной арифметикой (биМА).
При выполнении модульного суммирования по модулю р в бимодульной арифметике используется следующее соотношение:
а при выполнении модульного умножения по модулю р используется соотношение:
Операции получения индекса  и получения вычета  реализуются таблично. Таким образом, операции сложения и умножения сведены к операциям модульного сложения по модулям р и р-1, соответственно, и одной табличной операции выбора второй компоненты пары результата. В данном случае для сохранения требований однотипности сумматоры по модулям р и р-1 должны проектироваться по одному методу, а именно методу прямой логической реализации с использованием двоичных функциональных блоков [4].
Однако в настоящее время все большую популярность завоевывают гибридные методы построения базовых арифметических узлов модулярной арифметики, представляющие собой комбинацию методов прямой логической реализации и методов на основе таблиц состояний, являющиеся более эффективными [4].
В предлагаемой полезной модели модифицирован парный код, рассмотренный в [3], и реализована идея однотипности не только базовых узлов, но и представления самих компонент пар операндов с целью использования специализированных алгоритмов построения арифметических узлов.
Сущность однотипности в предлагаемом техническом решении состоит в переходе от представления компонент пар операндов по модулям р и р-1 к однородному представлению по модулю р-1. Для этого введено понятие модифицированного вычета по модулю р:
где  - функция Кронекера,  - кофункция Кронекера.
Для представления второй компоненты пары используется дискретно-логорифмическое представление вычета по модулю р:
где  - индекс вычета  по основанию w (первообразный корень поля GF(p)),
p
p-1
t
t-1
t
t
Константный символ λ=2-1 не является элементом кольца Z. Он обозначает «сингулярное» значение дискретного логарифма в точке . Технологичность такого выбора обусловлена следующим: если р - t-битное простое число, т.е. 2<р<2, то р≤2-1.
В результате такого представления арифметические операции вычислительным элементом бимодульной модулярной арифметики будут выполняться по следующему принципу:
мультипликативные операции будут выполняться как:
аддитивные операции будут выполняться однотипно за счет введения дополнительных логических функций как:
Таким образом, переход к однородному представлению операндов позволяет выполнять аддитивные и мультипликативные операции на одних базовых элементах, что влияет как на уменьшение площади, занимаемой вычислительным элементом на кристалле, так и на надежность выполнения арифметических операций.
Функционально работу вычислительного элемента бимодульной модулярной арифметики (фиг. 1), реализующего вышеописанные алгоритмы модульного суммирования и умножения, можно описать следующим образом: на вход устройства управления (1) подается код операции, которую должен выполнить вычислительный элемент бимодульной модулярной арифметики; устройство управления (1) подает управляющие сигналы на ОЗУ (2), предназначенное для хранения промежуточных результатов вычислений, ПЗУ (3), предназначенное для хранения необходимых при выполнении служебных операций константных значений, и мультиплексоры (4,6-10). Данные (входные операнды) могут быть получены по шине данных, из ОЗУ (2) или ПЗУ (3).
Работу арифметического узла (5) следует рассматривать в следующих режимах:
1. Режим определения результата операций модульного сложения и вычитания (сигнал устройства управления (1) - «0»).
2. Режим определения результата операций модульного умножения (сигнал устройства управления (1) - «1»).
В первом режиме сигнал с устройства управления (1) равный «0» поступает на четвертый информационный вход логического блока (17), управляющий вход ПЗУ для хранения таблицы бимодульной пары (18), управляющие входы четвертого (9) и пятого (10) мультиплексоров арифметического узла. Значение первого операнда (вычета) с первого мультиплексора (6) одновременно поступает на первый преобразователь «минус единица» (12), первый вход двоичного сумматора (11) и второй вход логического блока (17), значение второго операнда (вычета) со второго мультиплексора (7) одновременно поступает на второй преобразователь «минус единица» (13), второй вход двоичного сумматора (11) и третий вход логического блока (17). Сигнал с выхода двоичного сумматора (11) поступает одновременно на преобразователь «минус р» (14), на преобразователь «минус (р-1)» (15) и на компаратор (16), с выхода которого поступает сигнал на первый вход логического блока (17).
Логический блок (17) реализует набор булевых функций из таблицы 1 согласно выполняемым арифметическим операциям в соответствии с формулами (4) и (6). Результат работы логического блока (17) - это формирование управляющего сигнала для третьего (8) мультиплексора арифметического узла.
Логический блок (17), работающий в соответствии с таблицей 1, формирует управляющий сигнал для третьего мультиплексора (8), на информационные входы которого подаются следующие сигналы: на первый вход - сигнал с первого преобразователя «минус единица» (12), на второй вход - константное значение «0», на третий вход - сигнал с преобразователя «минус р» (14), на четвертый вход - сигнал с преобразователя «минус (р-1)» (15), на пятый вход - сигнал с выхода двоичного сумматора (11), на шестой вход - константное значение р-1 (р - базовый модуль), на седьмой вход - константное значение р-1, на восьмой вход - сигнал со второго преобразователя «минус единица» (13). Сигнал с выхода третьего мультиплексора (8) поступает одновременно на первые информационные входы четвертого (9) и пятого (10) мультиплексоров арифметического узла и на информационный вход ПЗУ для хранения таблицы бимодульной пары (18), на управляющий вход которого поступает сигнал с устройства управления (1). Сигнал с выхода ПЗУ для хранения таблицы бимодульной пары (18) поступает на вторые информационные входы четвертого (9) и пятого (10) мультиплексоров, на управляющий вход четвертого мультиплексора (9) поступает сигнал с устройства управления (1), а на управляющий вход пятого мультиплексора (10) поступает инверсный сигнал с устройства управления (1). Полученная в результате вычислений бимодульная пара с выходов мультиплексоров (9) и (10) передается на информационные входы блока регистров (19), выход которого является выходом арифметического узла (5), который соединен с первым информационным входом мультиплексора (4). Мультиплексор (4) формирует конечный результат выполненной операции вычислительным элементом бимодульной модулярной арифметики и передает его на выход вычислительного элемента, либо (по дополнительному сингалу от устройства управления (1)) записывает результат в ОЗУ (2).
Во втором режиме сигнал с устройства управления (1) равный «1» поступает на четвертый информационный вход логического блока (17), управляющий вход ПЗУ для хранения таблицы бимодульной пары (18), управляющие входы четвертого (9) и пятого (10) мультиплексоров арифметического узла. Значение первого операнда (логарифм вычета) с первого мультиплексора (6) одновременно поступает на первый преобразователь «минус единица» (12), первый вход двоичного сумматора (11) и второй вход логического блока (17), значение второго операнда (логарифм вычета) со второго мультиплексора (7) одновременно поступает на второй преобразователь «минус единица» (13), второй вход двоичного сумматора (11) и третий вход логического блока (17). Сигнал с выхода двоичного сумматора (11) поступает одновременно на преобразователь «минуса» (14), на преобразователь «минус (р-1)» (15) и на компаратор (16), с выхода которого поступает сигнал на первый вход логического блока (17). Логический блок (17), работающий в соответствии с таблицей 1, формирует управляющий сигнал для третьего мультиплексора (8), на информационные входы которого подаются следующие сигналы: на первый вход - сигнал с первого преобразователя «минус единица» (12), на второй вход - константное значение 0, на третий вход - сигнал с преобразователя «минуса» (14), на четвертый вход - сигнал с преобразователя «минус (р-1)» (15), на пятый вход - сигнал с выхода двоичного сумматора (11), на шестой вход - константное значение р-1 (р - базовый модуль), на седьмой вход - константное значение р-2, на восьмой вход - значение со второго преобразователя «минус единица» (13). Сигнал с выхода третьего мультиплексора (8) поступает одновременно на первые информационные входы четвертого (9) и пятого (10) мультиплексоров арифметического узла и на информационный вход ПЗУ для хранения таблицы бимодульной пары (18), на управляющий вход которого поступает сигнал с устройства управления (1). Сигнал с выхода ПЗУ для хранения таблицы бимодульной пары (18) поступает на вторые информационные входы четвертого (9) и пятого (10) мультиплексоров, на управляющий вход четвертого мультиплексора (9) поступает сигнал с устройства управления (1), а на управляющий вход пятого мультиплексора (10) поступает инверсный сигнал с устройства управления (1). Полученная в результате вычислений бимодульная пара с выходов мультиплексоров (9) и (10) передается на информационные входы блока регистров (19), выход которого является выходом арифметического узла (5), который соединен с первым информационным входом мультиплексора (4). Мультиплексор (4) формирует конечный результат выполненной операции вычислительным элементом бимодульной модулярной арифметики и передает его на выход вычислительного элемента, либо (по дополнительному сигналу от устройства управления (1)) записывает результат в ОЗУ (2).
Технический результат предлагаемой полезной модели достигается за счет того, что вычислительный элемент бимодульной модулярной арифметики выполняет аддитивную и мультипликативную операции не только аппаратно однотипно, но и однотипно в кодовом представлении операндов, при этом операнд представляется модифицированной парой - арифметическим остатком (вычетом) по модулю р-1 и дискретным логарифмом вычета по модулю р-1. Такое представление позволяет сбалансировать выполнение мультипликативных и аддитивных операций, а также сократить время выполнения модульных операций и площадь, занимаемую вычислительным элементом на кристалле (Фиг. 2), в сравнении с аналогами.
Реализуемость полезной модели подтверждается результатами моделирования с использованием лицензированных средств САПР фирмы Synopsys Design Compiler. Для оценки аппаратных затрат на проектирование вычислительного элемента бимодульной модулярной арифметики, а также для сравнительного анализа с аналогами. Предложенное техническое решение было реализовано в виде RTL-моделей, описанных на языке Verilog. Структурный синтез проводился в базисе 45 нм библиотеки стандартных ячеек Nangate Open Cell Library с использованием САПР Synopsys Design Compiler. Симуляция и верификация Verilog-проектов проводилась средствами ModelSim-Altera Starter Edition. Моделирование схем проводилось в диапазоне представления базовых модулей до 8 бит включительно.
[1] Н.П. Ямпурин, А.В. Баранова Основы надежности электронных средств. М.: Академия, 2010, 240 с.
[2] Торгашев В.А. Система остаточных классов и надежность ЦВМ - Москва: «Советское радио», 1973, 117 с.
[3] Поспелов Д.А. Арифметические основы вычислительных машин дискретного действия» М.: Высш. шк., 1970, 308 с. - стр. 296.
[4] Корнилов А.И., Исаева Т.Ю., Семенов М.Ю. Методы логического синтеза сумматоров с ускоренным переносом по модулю (2n-1) на основе BDD-технологии // Изв. ВУЗов. Электроника. - 2004. - №3. - С. 54-60.