Арифметико-логическое устройство и способ преобразования данных с использованием такого устройства Российский патент 2019 года по МПК G06F15/76 

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

Настоящее устройство относится к цифровым вычислительным устройствам, а именно к элементам вычислительных машин с запоминаемой программой.

Предшествующий уровень техники

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является, принятое за прототип, арифметико-логическое устройство высокопроизводительного криптографического процессора Cryptoraptor (Gokhan Sayilar, Derek Chiou. Cryptoraptor: High Throughput Reconfigurable Cryptographic Processor ISBN: 978-1-4799-6277-8), которое состоит из блока арифметики AU, блока логических операций LOU, блока вращения и сдвига SRU, блока опроса таблиц TLU и блока перемешивания PEU. Причем, блок арифметики AU имеет четыре входных порта для передачи данных шириной четыре байта, один выходной порт для передачи данных шириной один байт, сумматор Adder, вычитатель Subtracter, четыре блока для выполнения операции XOR, три мультиплексора, два модуля для сложения и вычитания по модулю 8 и 2 модуля для сложения и вычитания по модулю 16. Блок логических операций LOU имеет 6 входных портов для передачи данных, один выходной порт для передачи данных и восемь модулей логических преобразований CLB.

Арифметико-логическое устройство криптографического процессора Cryptoraptor имеет древовидную структуру и позволяет реализовать большую часть алгоритмов дискретной математики, причем стоит отметить, что блок арифметики AU позволяет реализовать за такт одну операцию сложения и одну операцию вычитания по модулю 8, 16 или 32 двух операндов. Отсутствие возможности провести суммирование более чем двух операндов за один такт в арифметико-логическом устройстве замедляет работу некоторых криптографических алгоритмов, например, MD5. Также, за счет широкого покрытия возможных операций арифметико-логическое устройство криптографического процессора Cryptoraptor содержит большое количество различных функциональных узлов, требующих большое количество аппаратных ресурсов для их реализации.

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

Задача изобретения

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

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

Сущность изобретения

Поставленная задача решается, а заявленный технический результат достигается за счет того, что арифметико-логическое устройство (АЛУ) для решения задач дискретной математики, содержит:

- три внешние группы входа данных,

- внешнюю группу входа кода операций и внешнюю группу выхода данных,

- блок циклического сдвига, вход данных которого соединен с входом данных №1, вход команды блока циклического сдвига соединен с входом кода операций, а выход данных со вторым входом блока инверсии, содержащий мультиплексор MX 1, входы данных которого соединены с входом данных №1, причем на второй вход мультиплексора подан операнд с входа данных №1 циклически сдвинутый на 8 бит вправо, на третий вход операнд с входа данных №1 циклически сдвинутый на 16 бит вправо, а на четвертый вход операнд с входа данных №1, циклически сдвинутый на 24 бита вправо, причем первый, управляющий, вход мультиплексора MX 1 соединен с входом команды блока циклического сдвига, а выход с выходом блока циклического сдвига,

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

- блок маски, первый вход которого соединен с входом кода операций, а выход с входом А АЛУ 1 и с входом А АЛУ 2 №2, состоящий из элемента логического И, первый вход которого соединен с первым входом блока маски, второй вход со вторым входом блока маски, а выход - с выходом блока маски,

- АЛУ 1, вход Б которого соединен с входом данных №2, вход К с входом кода операций, а выход с входом А АЛУ 2 №1, которое содержит модуль сложения по модулю два, первый вход которого соединен с входом К, второй вход с входом Б, а выход со вторым входом сумматора ADD, сумматор ADD, первый вход которого соединен с входом А, а выход - с первым входом мультиплексора MX 2, модуль сложения по модулю два, первый вход которого соединен с входом А, второй вход соединен с входом Б, а выход - со вторым входом мультиплексора MX 2, модуль логического ИЛИ, первый вход которого соединен с входом А, второй вход соединен с входом Б, а выход с третьим входом мультиплексора MX 2, модуль логического И, первый вход которого соединен с входом А, второй вход соединен с входом Б, а выход с четвертым входом мультиплексора MX 2, мультиплексор MX 2, пятый, шестой, седьмой, восьмой, девятый, десятый, одиннадцатый входной порт которого соединен с входом А, причем на входы мультиплексора подается операнд с входа А циклически сдвинутый вправо на 1, 2, 3, 4, 5, 6, 7 бит соответственно, двенадцатый вход соединен с входом А, тринадцатый вход с входом Б, управляющий вход с входом К, а выход - с выходом АЛУ 1,

- АЛУ 2 №1, вход Б которого соединен с выходом АЛУ 2 №2, вход К с входом кода операций, а выход с выходом данных, которое содержит сумматор ADD, первый вход которого соединен с входом А, второй вход с входом Б, а выход с первым входом мультиплексора MX 3, модуль сложения по модулю два, первый вход которого соединен с входом А, второй вход с входом Б, а выход со вторым входом мультиплексора MX 3, модуль логического ИЛИ, первый вход которого соединен с входом А, второй вход с входом Б, а выход с третьим входом мультиплексора MX 3, модуль логического И, первый вход которого соединен с входом А, второй вход с входом Б, а выход с четвертым входом мультиплексора MX 3, мультиплексор MX 3, пятый вход которого соединен с входом А, управляющий вход с входом К, а выход с выходом АЛУ 2 №2,

- АЛУ 2 №2, внутренняя структура которого совпадает с внутренней структурой АЛУ 2 №1, а вход Б которого соединен с входом данных №3 и вход К которого соединен с входом кода операций, внутренняя структура которого совпадает со структурой АЛУ 2 №1.

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

- на входы данных описанного устройства подают операнды, а на вход поля команд подают требуемую команду,

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

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

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

- если два младших бита требуемой команды равны '00', '01', '10', '11', блок циклического сдвига будет выполнять операцию циклического сдвига вправо операнда с входа данных №1 на 0, 8, 16, 24 бита соответственно;

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

- если биты требуемой команды от четвертого до тридцать пятого включительно принимают значения от '0×00000000' до '0×FFFFFFF', блок маски выполнит операцию маскирования операнда с значением в соответствующих битах команды, если бит команды равен '0', то соответствующий ему бит операнда на выходе блока маски будет равен '0', а если бит команды равен '1', то бит операнда будет равен значению соответствующего бита операнда на входе блока маски;

- если биты требуемой команды от тридцать шестого до тридцать девятого включительно принимают значения от '0000' до '1110', то соответственно АЛУ 1 будет выполнять операции - передача операнда А, передача операнда Б, логический сдвиг на 1-7 бит операнда А, операция сложения операндов по модулю 2, логическая операция ИЛИ над операндами, логическая операция И над операндами, вычитание из операнда А операнда Б, сложение операндов;

- если биты требуемой команды от сорокового до сорок второго включительно принимают значение от '000' до '101', соответственно малый АЛУ 2 №1 будет выполнять операции - передача операнда А на выход, операция сложения операндов по модулю два, логическая операция ИЛИ над операндами, логическая операция И над операндами, сложение операндов.

Сущность изобретения заключается в том, что арифметико-логическое устройство включает в себя три входа данных, вход кода операций, выход данных, блок циклического сдвига на 8,16, 24 бита, блок инверсии, блок наложения маски '0×FF', АЛУ 1, выполняющий операции сложения операндов, вычитания операндов, логические операции AND, OR, XOR, сдвиг на 1-7 битов первого операнда, передача одного из операндов на выход, АЛУ 2 №1 и АЛУ 2 №2, выполняющие операции сложения операндов, логические операции AND, OR, XOR, передача первого операнда на выход.

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

Краткое описание чертежей

Устройство поясняется фиг. 1, на которой представлена структурная схема арифметико-логического устройства.

На фиг. 1 приняты следующие обозначения:

- элемент логического И,

- модуль сложения по модулю 2,

- модуль логического ИЛИ,

ADD - сумматор,

>>N - циклический сдвиг на N бит вправо,

MX 1, 2, 3 - мультиплексоры,

Арифметико-логическое устройство состоит из блока циклического сдвига, состоящего из мультиплексора MX 1, блока инверсии, состоящего из модуля сложения по модулю два, блока маски, состоящего из модуля логического И, АЛУ 1, состоящего из модуля сложения по модулю 2, сумматора ADD, модуля сложения по модулю 2 операндов, модуля логического ИЛИ, модуля логического И и мультиплексора MX 2, АЛУ 2 №1 и АЛУ 2 №2, состоящих из сумматора ADD, модуля сложения по модулю два операндов, модуля логического ИЛИ, модуля логического И и мультиплексора MX 3.

Подробное описание сущности изобретения

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

Если два младших бита команды равны '00', '01', '10', '11', блок циклического сдвига будет выполнять операцию циклического сдвига вправо операнда с входа данных №1 на 0, 8, 16, 24 бита соответственно.

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

Если биты команды от четвертого до тридцать пятого включительно принимают значения от '0×00000000' до '0×FFFFFFF', блок маски выполнит операцию маскирования операнда с значением в соответствующих битах команды, если бит команды равен '0', то соответствующий ему бит операнда на выходе блока маски будет равен '0', а если бит команды равен '1', то бит операнда будет равен значению соответствующего бита операнда на входе блока маски.

Если биты команды от тридцать шестого до тридцать девятого включительно принимают значения от '0000' до '1110', то соответственно АЛУ 1 будет выполнять операции - передача операнда А, передача операнда Б, логический сдвиг на 1-7 бит операнда А, операция сложения операндов по модулю 2, логическая операция ИЛИ над операндами, логическая операция И над операндами, вычитание из операнда А операнда Б, сложение операндов.

Если биты команды от сорокового до сорок второго включительно принимают значение от '000' до '101', соответственно малый АЛУ 2 №1 будет выполнять операции - передача операнда А на выход, операция сложения операндов по модулю два, логическая операция ИЛИ над операндами, логическая операция И над операндами, сложение операндов.

Примеры осуществления изобретения

Предлагаемое арифметико-логическое устройство для решения задач дискретной математики может быть реализовано на базе ПЛИС Xilinx XC7V585 вычислительного устройства из 512-ти процессорных элементов. Ширина шины данных входов и выходов устройства составляет 4 байта, а частота работы тактового сигнала работы арифметико-логического устройства составляет 250 МГц.

Для оценки количества занимаемых ресурсов необходимых для реализации арифметико-логического устройства на СБИС была проведена оценка с использованием библиотечных элементов 28 нм технологического процесса в САПР Cadence RTL Compiler системы из 512-ти процессорных элементов. Одно арифметико-логическое устройство в данном устройстве занимает около 1250 кв. мкм, что в более чем 20 раз меньше, чем суммарная площадь блоков AU, LOU, SRU арифметико-логического устройства в рассмотренном прототипе около 28000 кв. мкм (Table III).

Одной из задач дискретной математики является алгоритм вычисления криптографической хэш-функции MD5. Графическая схема, в которой показаны этапы расчета одного раунда MD5 в прототипе представлена на Figure 7.17 диссертации (Gokhan Sayilar, Cryptoraptor: High Throughput Reconfigurable Cryptographic Processor for Symmetric Key Encryption and Cryptographic Hash Functions. PhD dissertation. The University of Texas. Austin. 2014). Из раздела 7.3.2 данной диссертации следует, что реализация одного раунда MD5 на двух процессорных элементах требует 4 такта, причем второй процессорный элемент используется для суммирования операндов A, Mi, Ki и позволяет сократить требуемое для реализации количество тактов на один. Таким образом, выполнение одного раунда MD5 на одном арифметико-логическом устройстве криптографического процессора Cryptoraptor (прототип) занимает 5 тактов.

Реализация раунда MD5 в предлагаемом устройстве занимает 4 такта, причем выигрыш в производительности обусловлен наличием в малом арифметико-логическом блоке №2 сумматора, что позволяет выполнять суммирование трех операндов A, Mi и Ki за один такт.

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

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

Изобретение относится к области вычислительной техники. Технический результат заключается в увеличении производительности устройства при решении задач дискретной математики. Устройство включает в себя три входа данных, вход кода операций, выход данных, блок циклического сдвига на 8, 16, 24 бита, блок инверсии, блок наложения маски '0×FF', АЛУ 1, выполняющий операции сложения операндов, вычитания операндов, логические операции AND, OR, XOR, сдвиг на 1-7 битов первого операнда, передача одного из операндов на выход, АЛУ 2 №1 и АЛУ 2 №2, выполняющие операции сложения операндов, логические операции AND, OR, XOR, передача первого операнда на выход. 2 н.п. ф-лы, 1 ил.

1. Арифметико-логическое устройство для решения задач дискретной математики, содержащее:

- три внешние группы входа данных;

- внешнюю группу входа кода операций и внешнюю группу выхода данных;

- блок циклического сдвига, вход данных которого соединен с входом данных №1, вход команды блока циклического сдвига соединен с входом кода операций, а выход данных со вторым входом блока инверсии, содержащий мультиплексор MX 1, входы данных которого соединены с входом данных №1, причем на второй вход мультиплексора подан операнд с входа данных №1, циклически сдвинутый на 8 бит вправо, на третий вход - операнд с входа данных №1, циклически сдвинутый на 16 бит вправо, а на четвертый вход - операнд с входа данных №1, циклически сдвинутый на 24 бита вправо, причем первый, управляющий, вход мультиплексора MX 1 соединен с входом команды блока циклического сдвига, а выход - с выходом блока циклического сдвига;

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

- блок маски, первый вход которого соединен с входом кода операций, а выход - с входом А АЛУ 1 и с входом А АЛУ 2 №2, состоящий из элемента логического И, первый вход которого соединен с первым входом блока маски, второй вход - со вторым входом блока маски, а выход - с выходом блока маски;

- АЛУ 1, вход Б которого соединен с входом данных №2, вход К с входом кода операций, а выход с входом А АЛУ 2 №1, которое содержит модуль сложения по модулю два, первый вход которого соединен с входом К, второй вход с входом Б, а выход со вторым входом сумматора ADD, сумматор ADD, первый вход которого соединен с входом А, а выход - с первым входом мультиплексора MX 2, модуль сложения по модулю два, первый вход которого соединен с входом А, второй вход соединен с входом Б, а выход - со вторым входом мультиплексора MX 2, модуль логического ИЛИ, первый вход которого соединен с входом А, второй вход соединен с входом Б, а выход с третьим входом мультиплексора MX 2, модуль логического И, первый вход которого соединен с входом А, второй вход соединен с входом Б, а выход с четвертым входом мультиплексора MX 2, мультиплексор MX 2, пятый, шестой, седьмой, восьмой, девятый, десятый, одиннадцатый входной порт которого соединен с входом А, причем на входы мультиплексора подается операнд с входа А, циклически сдвинутый вправо на 1, 2, 3, 4, 5, 6, 7 бит соответственно, двенадцатый вход соединен с входом А, тринадцатый вход с входом Б, управляющий вход с входом К, а выход - с выходом АЛУ 1;

- АЛУ 2 №1, вход Б которого соединен с выходом второго АЛУ 2 №2, вход К с входом кода операций, а выход с выходом данных, которое содержит сумматор ADD, первый вход которого соединен с входом А, второй вход с входом Б, а выход с первым входом мультиплексора MX 3, модуль сложения по модулю два, первый вход которого соединен с входом А, второй вход с входом Б, а выход со вторым входом мультиплексора MX 3, модуль логического ИЛИ, первый вход которого соединен с входом А, второй вход с входом Б, а выход с третьим входом мультиплексора MX 3, модуль логического И, первый вход которого соединен с входом А, второй вход с входом Б, а выход с четвертым входом мультиплексора MX 3, мультиплексор MX 3, пятый вход которого соединен с входом А, управляющий вход с входом К, а выход с выходом АЛУ 2 №2;

- АЛУ 2 №2, внутренняя структура которого совпадает с внутренней структурой АЛУ 2 №1, а вход Б которого соединен с входом данных №3 и вход К которого соединен с входом кода операций, внутренняя структура которого совпадает со структурой АЛУ 2 №1.

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

- на входы данных устройства по п. 1 подают операнды, а на вход поля команд подают требуемую команду;

- если два младших бита требуемой команды равны '00', '01', '10', '11', блок циклического сдвига будет выполнять операцию циклического сдвига вправо операнда с входа данных №1 на 0, 8, 16, 24 бита соответственно;

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

- если биты требуемой команды от четвертого до тридцать пятого включительно принимают значения от '0x00000000' до '0xFFFFFFF', блок маски выполнит операцию маскирования операнда со значением в соответствующих битах команды, если бит команды равен '0', то соответствующий ему бит операнда на выходе блока маски будет равен '0', а если бит команды равен '1', то бит операнда будет равен значению соответствующего бита операнда на входе блока маски;

- если биты требуемой команды от тридцать шестого до тридцать девятого включительно принимают значения от '0000' до '1110', то соответственно АЛУ 1 будет выполнять операции - передача операнда А, передача операнда Б, логический сдвиг на 1-7 бит операнда А, операция сложения операндов по модулю 2, логическая операция ИЛИ над операндами, логическая операция И над операндами, вычитание из операнда А операнда Б, сложение операндов;

- если биты требуемой команды от сорокового до сорок второго включительно принимают значение от '000' до '101', соответственно малый АЛУ 2 №1 будет выполнять операции - передача операнда А на выход, операция сложения операндов по модулю два, логическая операция ИЛИ над операндами, логическая операция И над операндами, сложение операндов.