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

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

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

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

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

Область техники

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

Уровень техники

Характерной чертой современной вычислительной техники является стремление использовать вычислительные системы с повышенным быстродействием и относительно высокой степенью надежности. Существуют различные методы повышения быстродействия от использования специализированных алгоритмов до повышения степени интеграции схем. При этом параметры надежности вычислительных систем в основном не оптимизируются. Основным методом, который широко применяется при построении высоконадежных устройств, является резервирование [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 представлены графики зависимости занимаемой на кристалле площади от величины базового модуля р для прототипа и предлагаемой полезной модели.

Осуществление полезной модели

Д.А. Поспелов в работе [3] предложил каждый вычет модулярной арифметики, где р_i является базисным основанием из набора {p₁, р₂, p_m} простых модулей, представлять парой - . Такое представление вычетов позволяет свести все операции по каждому модулю p_i, к однотипной реализации через сумматоры по модулям p_i, p_i-1 соответственно. Такого типа компьютерная арифметика называется бимодульной модулярной арифметикой (биМА).

При выполнении модульного суммирования по модулю р в бимодульной арифметике используется следующее соотношение:

а при выполнении модульного умножения по модулю р используется соотношение:

Операции получения индекса и получения вычета реализуются таблично. Таким образом, операции сложения и умножения сведены к операциям модульного сложения по модулям р и р-1, соответственно, и одной табличной операции выбора второй компоненты пары результата. В данном случае для сохранения требований однотипности сумматоры по модулям р и р-1 должны проектироваться по одному методу, а именно методу прямой логической реализации с использованием двоичных функциональных блоков [4].

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

В предлагаемой полезной модели модифицирован парный код, рассмотренный в [3], и реализована идея однотипности не только базовых узлов, но и представления самих компонент пар операндов с целью использования специализированных алгоритмов построения арифметических узлов.

Сущность однотипности в предлагаемом техническом решении состоит в переходе от представления компонент пар операндов по модулям р и р-1 к однородному представлению по модулю р-1. Для этого введено понятие модифицированного вычета по модулю р:

где - функция Кронекера, - кофункция Кронекера.

Для представления второй компоненты пары используется дискретно-логорифмическое представление вычета по модулю р:

где - индекс вычета по основанию w (первообразный корень поля GF(p)),

Константный символ _p=2^t-1 не является элементом кольца Z_p-1. Он обозначает «сингулярное» значение дискретного логарифма в точке . Технологичность такого выбора обусловлена следующим: если р - t-битное простое число, т.е. 2^t-1<р<2 ^t, то р2^t-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.

Вычислительный элемент бимодульной модулярной арифметики, содержащий устройство управления, оперативное запоминающее устройство (ОЗУ), постоянное запоминающее устройство (ПЗУ), мультиплексор, отличающийся тем, что в состав вычислительного элемента введен арифметический узел, реализованный с помощью пяти мультиплексоров, двоичного сумматора, двух преобразователей «минус единица», преобразователя «минус р», преобразователя «минус (р-1)», компаратора, логического блока, ПЗУ для хранения таблицы бимодульной пары, блока выходных регистров, причем выход устройства управления соединен с четвертым входом логического блока, управляющим входом ПЗУ для хранения таблицы бимодульной пары и управляющими входами первого, второго, четвертого и пятого мультиплексоров арифметического узла, сигнал с первого мультиплексора поступает соответственно на вход первого преобразователя «минус единица», первый вход двоичного сумматора и второй вход логического блока, сигнал со второго мультиплексора поступает соответственно на вход второго преобразователя «минус единица», второй вход двоичного сумматора и третий вход логического блока, выход первого преобразователя «минус единица» соединен с первым информационным входом третьего мультиплексора, выход второго преобразователя «минус единица» соединен с восьмым информационным входом третьего мультиплексора, выход двоичного сумматора соединен с входом преобразователя «минус р», входом преобразователя «минус (р-1)», пятым информационным входом третьего мультиплексора и входом компаратора, выход преобразователя «минус р» соединен с третьим информационным входом третьего мультиплексора, выход преобразователя «минус (р-1)» соединен с четвертым информационным входом третьего мультиплексора, а на второй, шестой и седьмой информационные входы третьего мультиплексора поступают константные значения, выход компаратора соединен с первым входом логического блока, выход третьего мультиплексора соединен с информационным входом ПЗУ для хранения таблицы бимодульной пары и с первыми информационными входами четвертого и пятого мультиплексоров, выход ПЗУ для хранения таблицы бимодульной пары соединен со вторыми информационными входами четвертого и пятого мультиплексоров, выходы которых соединены с блоком выходных регистров, выход которого является выходом арифметического узла, при этом первый вход первого мультиплексора арифметического узла соединен с ПЗУ, второй вход первого и второго мультиплексоров арифметического узла соединены с ОЗУ, а выход блока выходных регистров соединен с первым информационным входом мультиплексора.