КОНВЕЙЕРНЫЙ НАКАПЛИВАЮЩИЙ СУММАТОР ПО ПРОИЗВОЛЬНЫМ МОДУЛЯМ Российский патент 2024 года по МПК G06F7/38 

Область техники, к которой относится изобретение

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

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

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

Из существующего уровня техники также известно устройство для конвейерных арифметических вычислений по заданному модулю, содержащее однородную вычислительную среду, три таблицы подстановок, информационные входы и информационные выходы, тактовый вход, позволяющее выполнять суммирование чисел по произвольным простым модулям [2, фиг. 5]. Технической проблемой, которая не может быть решена при использовании данного технического решения при конвейерной обработке информации, является ограниченность функциональных возможностей устройства, так как устройство позволяет выполнять операции суммирования чисел только по модулям простых чисел. Кроме того, использование таблиц подстановки требует при каждой смене модуля изменять содержимое таблиц подстановки, что не позволяет оперативно менять модуль при организации конвейерных вычислений.

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

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

Раскрытие сущности изобретения.

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

Сущность изобретения заключается в реализации следующего способа конвейерного накапливающего суммирования чисел A_k,i по модулям P_k, где (i=1, 2, 3,…) - такты работы устройства, k - количество потоков чисел.

Поступающие на вход конвейерного накапливающего сумматора неотрицательные целые числа A_k,i (i=1, 2, 3,…), 0 ≤ A_k,i < P_k, где P_k ≥ 2 - произвольное натуральное число, называемое модулем, потактово суммируются в k раздельных потоках с числами, записанными в его памяти на предыдущих тактах, образуя k независимых выходных последовательностей чисел S_k,i, причем 0 ≤ S_k,i < P_k. При этом

S_k,i (∑ A_k,(i−k+1)) mod P_k, i=1, 2, 3,… ,(1)

где A_k,(i−k+1) = 0 при (i−k+1) ≤ 0.

Накапливающее суммирование может быть реализовано рекуррентным способом, тогда выражение (1) может быть записано в следующем виде:

S_k,i (S_k,(i−k) + A_k,(i−k+1)) mod P_k, i=1, 2, 3,… ,(2)

при этом считаем, что S_k,(i−k) = 0 при (i−k) ≤ (k-1), а S_k,i = 0 при i ≤ (k-1).

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

Выполняя с помощью одной однородной вычислительной среды операцию суммирования (S_k,(i−k) + A_k,(i−k+1)), а с помощью второй однородной вычислительной среды операцию (S_k,(i−k) + A_k,(i−k+1)) - P_k, можно по результатам вычисления второй однородной вычислительной среды выбирать корректное значение в выражении (2) для суммы S_k,i.

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

Сущность изобретения поясняется чертежами.

На фиг. 1 представлена схема конвейерного накапливающего сумматора по произвольным модулям. Конвейерный накапливающий сумматор по произвольным модулям содержит группу полных одноразрядных сумматоров 1, первую однородную вычислительную среду 2.1 разрядности n, где n - разрядность обрабатываемых чисел, вторую однородную вычислительную среду 2.2 разрядности (n+1), мультиплексор 3 разрядности n, первые 4 и вторые 5 информационные входы устройства, тактовый вход 6 и информационные выходы 7 устройства. Первые информационные входы 4 устройства соединены с первыми информационными входами первой однородной вычислительной среды 2.1 и с первыми информационными входами группы полных одноразрядных сумматоров 1. Вторые информационные входы 5 устройства соединены со вторыми информационными входами группы полных одноразрядных сумматоров 1. Первые информационные выходы группы полных одноразрядных сумматоров 1 соединены с младшими n разрядами первых информационных входов второй однородной вычислительной среды 2.2, вторые информационные выходы соединены со вторыми информационными входами второй однородной вычислительной среды 2.2 со сдвигом на один разряд в сторону старшего. Тактовый вход устройства 6 соединен со входами синхронизации первой 2.1 и второй 2.2 однородной вычислительной среды. Младшие n разрядов информационных выходов второй однородной вычислительной среды 2.2 соединены со вторыми информационными входами мультиплексора 3, а выход разряда переноса соединен с управляющим входом мультиплексора 3, первые информационные входы которого соединены с информационными выходами первой однородной вычислительной среды 2.1. Информационные выходы мультиплексора 3 соединены с информационными выходами устройства 7, со вторыми информационными входами первой однородной вычислительной среды 2.1 и с третьими информационными входами группы полных одноразрядных сумматоров 1. На (n+1)-й разряд первых информационных входов и на первый разряд вторых информационных входов второй вычислительной среды 2.2 подается сигнал логической единицы. На первые информационные входы 4 устройства подается поток кодов чисел A _k,i, j=1, 2, 3, …, на вторые информационные входы 5 устройства подается поток инверсных кодов модулей P_k. С информационных выходов 7 устройства снимаются коды суммы S _{k, i} чисел A_{k, i} по модулю P _k.

Осуществление изобретения.

Конвейерный накапливающий сумматор по произвольным модулям работает следующим образом (см. Фиг. 1).

В исходном состоянии все ячейки первой 2.1 и второй 2.2 однородной вычислительной среды обнулены.

На тактовый вход устройства 6 поступают тактовые импульсы i=1, 2, 3, …, . На первые информационные входы 4 устройства с каждым тактовым импульсом подаются числа A_k,i, для которых необходимо вычислить сумму S_k,i по модулю P_k. На вторые информационные входы 5 устройства подается инверсный код модуля P_k. Сумма S_k,i по модулю P_k чисел A_k,i снимается с информационных выходов 7 устройства.

Длина конвейера k определяет его латентный период работы и зависит от структуры однородных вычислительных сред 2.1 и 2.2.

На первом такте с первых информационных входов 4 устройства на первые информационные входы первой однородной вычислительной среды 2.1 поступит число A_1,1, а на ее вторые информационные входы с выхода мультиплексора 3 поступит значение S_1,0, равное, в соответствии с (2), нулю. В первый столбец однородной вычислительной среды 2.1 запишется вектор значений, зависящий от структуры построения однородной вычислительной среды 2.1 и значений чисел A_1,1 и S_1,0, который можно определить, как первую частичную сумму A_1,1 и S_1,0. Полная сумма этих чисел появится на информационных выходах однородной вычислительной среды 2.1 через k тактов работы устройства. Одновременно число A_1,1 поступает на первые информационные входы группы полных одноразрядных сумматоров 1, на вторые информационные входы которых со вторых информационных входов 5 устройства подается инверсный код значения модуля P₁, а на третьи информационные входы с выхода мультиплексора 3 подается нулевое значение S_1,0. На первых и вторых информационных выходах группы полных одноразрядных сумматоров 1 будут формироваться числа X_i и Y_i соответственно. При этом в соответствии с правилами сложения разряды чисел X_i и Y_i будут вычислены как:

x_j,i=a_j,i b_j,i p_j,i, (3)

y_j,i=a_j,ib_j,ib_j,ip_j,ia_j,ip_j,i. (4)

где j = 0, 1, 2, 3 - номер разряда в двоичном представлении чисел;

i =1, 2, 3, …, - номер такта работы устройства;

x_j,i - j-ый разряд i-го числа X_i,

y_j,i - j-ый разряд i-го числа Y_i;

a_j,i - j-ый разряд i-го числа A_k,i;

b_j,i - j-ый разряд i-го числа S_k,i;

p_j,i - j-ый разряд числа P_k на i-ом такте;

символ означает суммирование по модулю два;

символ означает логическую дизъюнкцию.

Тогда вычисление значения ((S_k,(i−k) + A_k,(i−k+1)) - P_k),состоящего из трех операндов, может быть сведено к вычислению значения (2ⁿ⁺¹ +X_j +2 Y_j + 1), состоящего из двух операндов и двух констант, с увеличением на одну единицу разрядности вычислителя.

Числа X₁ и Y₁ поступают на первые и вторые информационные входы второй однородной вычислительной среды 2.2. В первый столбец второй однородной вычислительной среды 2.2 по окончании первого тактового импульса запишется вектор значений, зависящий от структуры построения однородной вычислительной среды 2.2 и значений чисел X₁ и Y₁. Полное значение выражения ((A_1,1 + S_1,0) - P₁) появится на информационных выходах однородной вычислительной среды 2.2 через k тактов работы устройства.

В общем случае, если (S_k,(i−k) + A_k,(i−k+1)) P_k, то на выходе переноса второй однородной вычислительной среды 2.2 образуется сигнал переноса, который поступит на управляющий вход мультиплексора 3 и скоммутирует вторые информационные входы на информационные выходы и на информационных выходах мультиплексора 3 появится разность (S_k,(i−k) + A_k,(i−k+1)) - P_k, а иначе на его информационных выходах появится сумма (S_k,(i−k) + A_k,(i−k+1)). Результат S_k,i поступит на информационные выходы устройства 7, на вторые информационные входы первой вычислительной среды 2.1 и на третьи информационные входы группы полных одноразрядных сумматоров 1. На следующих тактах работа устройства продолжится аналогичным образом.

Таким образом, на информационных выходах 7 устройства в соответствии с выражением (2) на каждом такте работы устройства будут появляться значения S_k,i, образующие k независимых потоков накапливающих сумм входных чисел A_k,i по k различным модулям P_k.

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

Источники информации.

1. Патент на изобретение RU 2310223 С1. МПК G06F 7/72 (2006.01). Однородная вычислительная структура для выполнения операций по заданному модулю. Опубликован 10.11.2007. Бюл. № 31.

2. Патент на изобретение RU 2477513 С1. МПК G06F 7/72 (2006.01). Ячейка однородной вычислительной среды, однородная вычислительная среда и устройство для конвейерных арифметических вычислений по заданному модулю. Опубликован 10.03.2013. Бюл. № 7.

3. Патент на изобретение RU 2805939 С1. МПК G06F 7/72 (2006.01). Устройство для конвейерного суммирования чисел по произвольному модулю. Опубликован 24.10.2023. Бюл. № 30.

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

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