RU2814657C9

RU2814657C9 - Modulo conveyor accumulating adder

Info

Publication number: RU2814657C9
Application number: RU2023127194A
Authority: RU
Inventors: Вячеслав Иванович Петренко; Матвей Павлович Сутормин
Filing date: 2023-10-24
Publication date: 2024-06-11

Abstract

FIELD: computer technology.

SUBSTANCE: modulo pipeline accumulating adder contains 2n-bit and (n+1)-bit registers, where n is the width of the numbers being processed, n-bit and (n+1)-bit adders, a multiplexer, the first and second information inputs of the device, information device outputs and device clock input.

EFFECT: increasing the productivity of operations of cumulative summation of numbers modulo arbitrary.

1 cl, 1 dwg

Description

Область техники, к которой относится изобретениеField of technology to which the invention relates

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах конвейерного типа, а также в синтезаторах частот и делителях частоты с дробным коэффициентом деления и в криптографических приложениях.The invention relates to computer technology and can be used in conveyor-type digital computing devices, as well as in frequency synthesizers and frequency dividers with fractional division coefficients and in cryptographic applications.

Уровень техникиState of the art

Из существующего уровня техники известен накапливающий сумматор [1, рис. 5-250, стр. 741], содержащий 3 сумматора и 3 регистра, выполняющий операцию накапливающего суммирования по модулю 2ⁿ, где n - разрядность устройства.An accumulating adder is known from the existing level of technology [1, Fig. 5-250, p. 741], containing 3 adders and 3 registers, performing an accumulative summation operation modulo ²ⁿ , where n is the bit capacity of the device.

Недостатком данного сумматора является ограниченный функционал, а именно отсутствие операции суммирования по произвольному модулю.The disadvantage of this adder is its limited functionality, namely the absence of an arbitrary summation operation.

Наиболее близким к заявленному техническому решению по технической сущности и достигаемому техническому результату, выбранному в качестве прототипа, является накапливающий сумматор по модулю, содержащий n-разрядный сумматор, n-разрядный регистр, (n+1)-разрядный сумматор и n-разрядный мультиплексор [2], выполняющий операцию накапливающего суммирования по произвольному модулю. Технической проблемой, которая не может быть решена при использовании данного технического решения при конвейерной обработке информации, является низкая производительность операций накапливающего суммирования чисел по произвольному модулю при конвейерной обработке информации, так как суммирование очередных чисел по модулю в потоке не может быть начато до тех пор, пока не завершено суммирование по модулю предыдущих чисел.The closest to the claimed technical solution in terms of technical essence and achieved technical result, selected as a prototype, is a modulo accumulating adder containing an n-bit adder, an n-bit register, an (n+1)-bit adder and an n-bit multiplexer [ 2], which performs the operation of cumulative summation over an arbitrary modulo. A technical problem that cannot be solved when using this technical solution in pipeline information processing is the low performance of the operations of cumulative summation of numbers modulo arbitrary in pipeline information processing, since the modulo summation of successive numbers in a stream cannot be started until until the summation modulo the previous numbers is completed.

Техническим результатом, обеспечиваемым приведенной совокупностью признаков, является повышение производительности операций накапливающего суммирования чисел по произвольному модулю.The technical result provided by the given set of features is to increase the productivity of operations of cumulative summation of numbers modulo arbitrary.

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

Указанный технический результат при осуществлении изобретения достигается тем, что в конвейерный накапливающий сумматор по модулю содержащий n-разрядный сумматор, (n+1)-разрядный регистр, (n+1)-разрядный сумматор, мультиплексор, первые информационные входы устройства, тактовый вход, вторые информационные входы устройства, информационные выходы устройства, причем первые n разрядов первых информационных входов (n+1)-разрядного сумматора соединены со вторыми информационными входами устройства, на (n+1)-й разряд первых информационных входов и на вход переноса подается сигнал логической единицы, первые n разрядов вторых информационных входов соединены с первыми информационными входами мультиплексора, вторые информационные входы которого соединены с первыми n разрядами информационных выходов (n+1)-разрядного сумматора, управляющий вход соединен с выходом переноса (n+1)-разрядного сумматора, а вход синхронизации (n+1)-разрядного регистра соединен с тактовым входом устройства, введен (2n)-разрядный регистр, вход синхронизации которого соединен с тактовым входом устройства, младшие n разрядов информационных входов соединены с первыми информационными входами устройства, старшие n разрядов информационных входов соединены с информационными выходами мультиплексора и с информационными выходами устройства, младшие n разрядов информационных выходов соединены с первыми информационными входами n-разрядного сумматора, старшие n разрядов соединены со вторыми информационными входами n-разрядного сумматора, информационные выходы которого соединены с младшими n разрядами информационных входов (n+1)-разрядного регистра, а выход переноса соединен с (n+1)-м разрядом информационных входов (n+1)-разрядного регистра, информационные выходы которого соединены со вторыми информационными входами (n+1)-разрядного сумматора.The specified technical result when implementing the invention is achieved by the fact that the conveyor accumulating adder modulo contains an n-bit adder, an (n+1)-bit register, an (n+1)-bit adder, a multiplexer, the first information inputs of the device, a clock input, second information inputs of the device, information outputs of the device, and the first n bits of the first information inputs of the (n+1)-bit adder are connected to the second information inputs of the device, a logical signal is supplied to the (n+1)th bit of the first information inputs and to the transfer input units, the first n bits of the second information inputs are connected to the first information inputs of the multiplexer, the second information inputs of which are connected to the first n bits of the information outputs of the (n+1)-bit adder, the control input is connected to the transfer output of the (n+1)-bit adder, and the synchronization input of the (n+1)-bit register is connected to the clock input of the device, a (2n)-bit register is introduced, the synchronization input of which is connected to the clock input of the device, the lowest n bits of information inputs are connected to the first information inputs of the device, the highest n bits of information inputs are connected to the information outputs of the multiplexer and to the information outputs of the device, the low n bits of the information outputs are connected to the first information inputs of the n-bit adder, the high n bits are connected to the second information inputs of the n-bit adder, the information outputs of which are connected to the low n bits of the information inputs (n+1)-bit register, and the carry output is connected to the (n+1)-th bit of the information inputs of the (n+1)-bit register, the information outputs of which are connected to the second information inputs of the (n+1)-bit adder.

Сущность изобретения заключается в реализации следующего способа накопительного суммирования чисел A_i по модулю Р. Поступающие на вход накапливающего сумматора целые числа A_i (i=1, 2, 3,…), 0≤A_i<Р, потактово суммируются в двух раздельных потоках с числами, записанными в его памяти на предыдущих тактах, образуя две независимые выходные последовательности чисел, сопряженные соответственно с нечетными и четными номерами тактов. Нечетная и четная выходные последовательности поступают на выход накапливающего сумматора поочередно. Суммирование для нечетного и четного потоков чисел может осуществляться для разных модулей Р₁ и Р₂ соответственно. Обозначим сумму по модулю для первого (нечетного) потока чисел S_1,i, а для второго (четного) потока чисел S_2,i. ТогдаThe essence of the invention is to implement the following method of cumulative summation of numbers A _i modulo P. The integer numbers A _i (i=1, 2, 3,...), 0≤A _i <P, arriving at the input of the accumulating adder, are summed clockwise in two separate streams with the numbers recorded in its memory on previous measures, forming two independent output sequences of numbers, paired with odd and even numbers of measures, respectively. Odd and even output sequences are supplied to the output of the accumulating adder alternately. Summation for odd and even number streams can be carried out for different modules P ₁ and P ₂ , respectively. Let us denote the modulo sum for the first (odd) stream of numbers S _1,i , and for the second (even) stream of numbers S _2,i . Then

Накапливающий сумматор имеет две ячейки памяти, выполненные, например, в виде регистра.The accumulating adder has two memory cells, made, for example, in the form of a register.

Первая ячейка памяти имеет размерность 2n, где n - разрядность входных чисел, а вторая ячейка памяти имеет размерность (n+1). Первая ячейка памяти на каждом такте сохраняет входные числа A_i разрядностью n, выходные числа S_1,i на четном такте и выходные числа S_2,i на нечетном такте разрядностью n.The first memory cell has a dimension of 2n, where n is the width of the input numbers, and the second memory cell has a dimension of (n+1). The first memory cell at each clock cycle stores input numbers A _i with n-bit capacity, output numbers S _1,i at an even clock cycle and output numbers S _2,i at an odd clock cycle with n-bit capacity.

Вторая ячейка памяти сохраняет в течение очередного такта сумму (A_i+S_1,i) на четном такте и сумму (A_i+S_2,i) на нечетном такте. На выходе второй ячейки памяти осуществляется приведение по модулю P_k суммы (A_i+S_k,i), где k=1,2. Если указанная сумма больше модуля P_k, соответственно производится вычитание из нее этого модуля, в противном случае сумма без изменения поступает на выход устройства.The second memory cell stores during the next clock cycle the sum (A _i +S _1,i ) on the even clock cycle and the sum (A _i +S _2,i ) on the odd clock cycle. At the output of the second memory cell, the sum (A _i +S _k,i ) is reduced modulo P _k , where k=1.2. If the specified sum is greater than the module P _k , this module is correspondingly subtracted from it, otherwise the sum without change is sent to the output of the device.

Повышение производительности операций накапливающего суммирования чисел по произвольному модулю в предлагаемом устройстве достигается за счет того, что операция суммирования по модулю для потока последовательных чисел выполняется сразу для двух пар чисел.Increasing the productivity of the operations of cumulative summation of numbers modulo arbitrary in the proposed device is achieved due to the fact that the modulo summation operation for a stream of sequential numbers is performed for two pairs of numbers at once.

Краткое описание чертежей.Brief description of the drawings.

Сущность изобретения поясняется чертежами.The essence of the invention is illustrated by drawings.

На фиг. 1 представлена схема конвейерного накапливающего сумматора по модулю. Конвейерный накапливающий сумматор по модулю содержит 2n-разрядный и (n+1)-разрядный регистры 1 и 3, где n - разрядность обрабатываемых чисел, n-разрядный и (n+1)-разрядный сумматоры 2 и 4, мультиплексор 5, первые 6 и вторые 8 информационные входы устройства, информационные выходы устройства 9 и тактовый вход устройства 7, который соединен со входами синхронизации 2n-разрядного и (n+1)-разрядного регистров 1 и 3. Младшие n разрядов информационных входов 2n-разрядного регистра 1 соединены с первыми информационными входами устройства 6, старшие n разрядов информационных входов соединены с информационными выходами устройства 9 и с информационными выходами мультиплексора 5, младшие n разрядов информационных выходов соединены с первыми информационными входами n-разрядного сумматора 2, а старшие n разрядов информационных выходов соединены со вторыми информационными входами n-разрядного сумматора 2. Информационные выходы n-разрядного сумматора 2 соединены с младшими n разрядами информационных входов (n+1)-разрядного регистра 3, а выход переноса соединен с (n+1)-м разрядом информационных входов (n+1)-разрядного регистра 3, n разрядов информационных выходов разрядного регистра 3 соединены с первыми n разрядами вторых информационных входов (n+1)-разрядного сумматора 4 и с первыми информационными входами мультиплексора 5, а (n+1)-й разряд информационных выходов соединен с (n+1)-м разрядом первых информационных входов (n+1)-разрядного сумматора 4. Первые n разрядов первых информационных входов (n+1)-разрядного сумматора 4 соединены с первыми информационными входами устройства 8, а на (n+1)-й разряд первых информационных входов и на вход переноса подается сигнал логической единицы. Вторые информационные входы мультиплексора 5 соединены с первыми n разрядами информационных выходов разрядного сумматора 4, управляющий вход соединен с выходом переноса (n+1)-разрядного сумматора 4.In fig. Figure 1 shows a diagram of a conveyor modulo accumulating adder. The modulo pipeline accumulating adder contains 2n-bit and (n+1)-bit registers 1 and 3, where n is the bit depth of the numbers being processed, n-bit and (n+1)-bit adders 2 and 4, multiplexer 5, first 6 and the second 8 information inputs of the device, information outputs of the device 9 and the clock input of the device 7, which is connected to the synchronization inputs of the 2n-bit and (n+1)-bit registers 1 and 3. The lower n bits of the information inputs of the 2n-bit register 1 are connected to the first information inputs of the device 6, the highest n bits of the information inputs are connected to the information outputs of the device 9 and the information outputs of the multiplexer 5, the low n bits of the information outputs are connected to the first information inputs of the n-bit adder 2, and the highest n bits of the information outputs are connected to the second information inputs of the n-bit adder 2. The information outputs of the n-bit adder 2 are connected to the low-order n bits of the information inputs of the (n+1)-bit register 3, and the transfer output is connected to the (n+1)-th bit of the information inputs (n+1 )-bit register 3, n bits of information outputs of bit register 3 are connected to the first n bits of the second information inputs of the (n+1)-bit adder 4 and to the first information inputs of the multiplexer 5, and the (n+1)th bit of information outputs is connected with the (n+1)-th bit of the first information inputs of the (n+1)-bit adder 4. The first n bits of the first information inputs of the (n+1)-bit adder 4 are connected to the first information inputs of the device 8, and on (n+ 1)th bit of the first information inputs and a logical one signal is supplied to the transfer input. The second information inputs of the multiplexer 5 are connected to the first n bits of the information outputs of the bit adder 4, the control input is connected to the transfer output of the (n+1)-bit adder 4.

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

Конвейерный накапливающий сумматор по модулю работает следующим образом (см. Фиг. 1).The modulo conveyor accumulating adder operates as follows (see Fig. 1).

В исходном состоянии 2n-разрядный и (n+1)-разрядный регистры 1 и 3 обнулены. На тактовый вход устройства 7 поступают тактовые импульсы i=1,2,3,…. На первые информационные входы устройства 6 с каждым тактовым импульсом подаются числа A_i. На вторые информационные входы устройства 8 на четных тактах подается инверсный код модуля Р₁, а на нечетных тактах (начиная с 3) подается инверсный код модуля Р₂. Сумма S_1,i-1 по модулю P₁ для чисел A_i (i=2, 4, 6,…) и сумма S_2,i-1по модулю Р₂ для чисел A_i (i=1, 3, 5, …) снимается с информационных выходов устройства 9. Причем 0≤A_i (i=2, 4, 6, …)<P₁, а 0≤A_i (i=1, 3, 5, …)<Р₂. Длина конвейера составляет две ступени. Латентный период работы конвейера равен одному такту.In the initial state, 2n-bit and (n+1)-bit registers 1 and 3 are cleared. The clock input of device 7 receives clock pulses i=1,2,3,…. Numbers A _i are supplied to the first information inputs of device 6 with each clock pulse. The inverse code of module P ₁ is supplied to the second information inputs of device 8 on even clock cycles, and the inverse code of module P ₂ is supplied on odd clock cycles (starting from 3). The sum S _1,i-1 modulo P ₁ for numbers A _i (i=2, 4, 6,...) and the sum S _2,i-1 modulo P ₂ for numbers A _i (i=1, 3, 5 , …) is removed from the information outputs of device 9. Moreover, 0≤A _i (i=2, 4, 6, …)<P ₁ , and 0≤A _i (i=1, 3, 5, …)<P ₂ . The conveyor is two stages long. The latent period of the conveyor is equal to one clock cycle.

На первом такте работы устройства первое n-разрядное число А₁ записывается в 2n-разрядный регистр 1. Причем оно записывается в младшие n разрядов, а старшие n разрядов обнулены. С младших n разрядов информационных выходов 2n-разрядного регистра 1 число А₁ поступает на первые информационные входы n-разрядного сумматора 2, а на вторые информационные входы поступает нулевое значение со старших n разрядов информационных выходов 2n-разрядного регистра 1. На информационных выходах n-разрядного сумматора 2 образуется значение суммы А₁+S_1,0. Так как на первом такте значение S_1,0 равно 0, то на информационных выходах n-разрядного сумматора 2 образуется значение A₁. Это значение затем на следующем такте запишется в (n+1)-разрядный регистр 3.On the first clock cycle of the device, the first n-bit number A ₁ is written to the 2n-bit register 1. Moreover, it is written to the lower n bits, and the highest n bits are reset to zero. From the lower n bits of the information outputs of the 2n-bit register 1, the number A ₁ is supplied to the first information inputs of the n-bit adder 2, and the second information inputs receive a zero value from the highest n bits of the information outputs of the 2n-bit register 1. At the information outputs n- bit adder 2 produces the value of the sum A ₁ +S _1.0 . Since at the first cycle the value of S _1.0 is 0, the value A ₁ is formed at the information outputs of the n-bit adder 2. This value is then written to (n+1)-bit register 3 on the next clock cycle.

На втором такте работы устройства второе n-разрядное число А₂ записывается в 2n-разрядный регистр 1, а значение А₁ с выходов n-разрядного сумматора 2 записывается в (n+1) разрядов (n+1)-разрядного регистра 3. Число А₂ записывается в младшие n разрядов 2n-разрядного регистра 1, при этом в старшие n разрядов записывается нулевое значение. С младших n разрядов информационных выходов 2n-разрядного регистра 1 число А₂ поступает на первые информационные входы n-разрядного сумматора 2, а на вторые информационные входы поступает нулевое значение со старших n разрядов информационных выходов 2n-разрядного регистра 1. На информационных выходах n-разрядного сумматора 2, образуется значение суммы (А₂+S_2,0). Так как на втором такте значение S_2,0 равно 0, то на информационных выходах n-разрядного сумматора 2 образуется значение А₂. При этом на первые информационные входы (n+1)-разрядного сумматора 4 с информационных выходов (n+1)-разрядного регистра 3 поступит значение А₁, а на младшие n разрядов вторых информационных входов поступит n-разрядный инверсный код модуля который дополняется до (n+1)-го разряда значением логической единицы, поступающей на (n+1)-й разряд вторых информационных входов (n+1)-разрядного сумматора 4. Так как на вход переноса (n+1)-разрядного сумматора 4 поступает сигнал логической единицы, то этим сумматором по существу выполняется операция вычитания (A₁+S_1,0)-Р₁.On the second clock cycle of the device, the second n-bit number A ₂ is written to 2n-bit register 1, and the value of A ₁ from the outputs of n-bit adder 2 is written to (n+1) bits of (n+1)-bit register 3. Number And ₂ is written to the low n bits of the 2n-bit register 1, while a zero value is written to the high n bits. From the lower n bits of the information outputs of the 2n-bit register 1, the number A ₂ is supplied to the first information inputs of the n-bit adder 2, and the second information inputs receive a zero value from the highest n bits of the information outputs of the 2n-bit register 1. At the information outputs n- bit adder 2, the value of the sum is formed (A ₂ +S _2.0 ). Since in the second cycle the value of S _2.0 is equal to 0, the value A ₂ is formed at the information outputs of the n-bit adder 2. In this case, the first information inputs of the (n+1)-bit adder 4 will receive the value A ₁ from the information outputs of the (n+1)-bit register 3, and the low-order n bits of the second information inputs will receive the n-bit inverse code of the module which is supplemented to the (n+1)-th bit by the value of a logical unit arriving at the (n+1)-th bit of the second information inputs of the (n+1)-bit adder 4. Since the transfer input of the (n+1)-bit adder 4 receives a logical one signal, then this adder essentially performs the subtraction operation (A ₁ +S _1.0 ) - P ₁ .

На следующих тактах работа устройства осуществляется аналогичным образом.On the following cycles, the device operates in a similar way.

В случае, если значение (A_i+S_k,i-1)≥P_k, то на выходе переноса (n+1)-разрядного сумматора 4 образуется сигнал переноса, который поступит на управляющий вход мультиплексора 5 и скоммутирует с его информационным выходом его второй информационный вход, на который поступает значение (A_i+S_ki-1) - P_k с информационных выходов (n+1)-разрядного сумматора 4. Если же значение (A_i+S_k,i-1) < P_k, то сигнал переноса на выходе переноса (n+1)-разрядного сумматора 4 отсутствует и с информационным выходом мультиплексора окажется скоммутирован его первый информационный вход, на который с информационного выхода (n+1)-разрядного регистра 3 поступает значение (A_i+S_k,i-1). В результате на информационном выходе мультиплексора 5, а следовательно и на информационном выходе 9 устройства будут формироваться значения S_k,i отдельно для нечетного потока чисел S_1,i и для четного потока чисел S_2,i.If the value (A _i +S _k,i-1 )≥P _k , then a carry signal is generated at the transfer output of the (n+1)-bit adder 4, which will go to the control input of the multiplexer 5 and connect with its information output its second information input, which receives the value (A _i +S _ki-1 ) - P _k from the information outputs of (n+1)-bit adder 4. If the value (A _i +S _k,i-1 ) < P _k , then the carry signal at the transfer output of the (n+1)-bit adder 4 is absent and its first information input will be connected to the information output of the multiplexer, to which the value (A _i + S _k,i-1 ). As a result, at the information output of the multiplexer 5, and therefore at the information output 9 of the device, values S _k,i will be generated separately for the odd stream of numbers S _1,i and for the even stream of numbers S _2,i .

Значения чисел в десятичном виде на входах и выходах элементов устройства при его работе на конкретном примере приведены в табл. 1.The values of numbers in decimal form at the inputs and outputs of the device elements during its operation using a specific example are given in Table. 1.

Изобретение позволяет при конвейерной обработке информации за промежуток времени, при котором устройство прототип выполняет операцию суммирования по модулю для потока последовательных чисел, выполнять операцию суммирования по модулю для двух пар чисел. Таким образом, производительность вычисления суммы чисел по модулю при конвейерной обработке информации у предлагаемого устройства будет выше в два раза.The invention allows, during pipeline processing of information for a period of time during which the prototype device performs a modulo summation operation for a stream of consecutive numbers, to perform a modulo summation operation for two pairs of numbers. Thus, the performance of calculating the sum of numbers modulo during pipeline processing of information for the proposed device will be twice as high.

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

1. Тарабрин Б.В. Справочник по интегральным микросхемам / Б.В. Тарабрин, С.В. Якубовский, Н.А. Барканов и др./ Под ред. Б.В. Тарабрина. - 2-е изд., перераб. и доп. - М.: Энергия, 1981.1. Tarabrin B.V. Handbook of integrated circuits / B.V. Tarabrin, S.V. Yakubovsky, N.A. Barkanov et al. / Ed. B.V. Tarabrina. - 2nd ed., revised. and additional - M.: Energy, 1981.

2. Патент на изобретение RU 2500017 С1. МПК G06F 7/72 (2006.01), G06F 7/50 (2006.01). Накапливающий сумматор по модулю. Опубликован 27.11.2013 Бюл. №33.2. Patent for invention RU 2500017 C1. IPC G06F 7/72 (2006.01), G06F 7/50 (2006.01). Modulo accumulating adder. Published November 27, 2013 Bulletin. No. 33.

Claims

A conveyor modulo accumulating adder containing an n -bit adder, an ( n +1)-bit register, an ( n +1)-bit adder, a multiplexer, the first information inputs of the device, a clock input, the second information inputs of the device, information outputs of the device, and the first n bits of the first information inputs of the ( n +1)-bit adder are connected to the second information inputs of the device, a logical one signal is supplied to the ( n +1)th bit of the first information inputs and the transfer input, the first n bits of the second information inputs are connected to the first information inputs of the multiplexer, the second information inputs of which are connected to the first n bits of the information outputs of the ( n +1)-bit adder, the control input is connected to the transfer output of the ( n +1)-bit adder, and the synchronization input of the ( n +1)-bit register is connected to the clock input of the device, characterized in that a ( 2n )-bit register is introduced into it, the synchronization input of which is connected to the clock input of the device, the lowest n bits of information inputs are connected to the first information inputs of the device, the highest n bits of information inputs are connected to information outputs of the multiplexer and with information outputs of the device, the lower n bits of the information outputs are connected to the first information inputs of the n -bit adder, the highest n bits are connected to the second information inputs of the n -bit adder, the information outputs of which are connected to the lower n bits of the information inputs ( n + 1)-bit register, and the transfer output is connected to the ( n +1)-th bit of the information inputs of the ( n +1)-bit register, the information outputs of which are connected to the second information inputs of the ( n +1)-bit adder.