Результат интеллектуальной деятельности: Конвейерный вычислитель

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

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

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

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

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

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

Из существующего уровня техники известно устройство для формирования остатка по произвольному модулю от числа, содержащее l=((k/N)−1) блоков формирования частичных остатков (где k – количество разрядов в двоичном представлении числа, от которого формируется остаток, с учетом добавленных для достижения кратности N разрядов), (l+1) блоков умножения по модулю, блока распределения коэффициентов и сумматора по модулю [4]. Технической проблемой, которая не может быть решена при использовании данного технического решения, является низкое быстродействие при вычислении остатков по модулю для потока чисел, так как формирование частичного остатка и выполнение операций умножения и сложения по модулю производится заново для каждого из чисел в потоке, кроме того, вычисление остатка по модулю для очередного числа в потоке не может быть начато до тех пор, пока не завершено вычисление остатка по модулю для предыдущего числа.

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

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

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

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

Сущность изобретения заключается в реализации следующего способа конвейерного вычисления остатка R от числа A по модулю P. Пусть

где A – целое положительное число, от которого необходимо вычислить остаток;

P – целое положительное число, называемое модулем;

Q – целое положительное число, являющееся неполным частным от деления A на P;

R — целое положительное число, являющееся остатком от деления A на P.

Причем

где a_i, - коэффициенты, принимающие значение 0 или 1 в зависимости от значения числа A;

p_i, - коэффициенты, принимающие значение 0 или 1 в зависимости от значения модуля P;

q_i, - коэффициенты, принимающие значение 0 или 1 в зависимости от значения неполного частного Q;

r_i, - коэффициенты, принимающие значение 0 или 1 в зависимости от значения остатка R;

n – количество разрядов в представлении числа A, m – количество разрядов в представлении модуля P,

Задача состоит в том, чтобы по известным A и P отыскать остаток R. Остаток R является в терминах теории чисел вычетом числа A по модулю P, поэтому говорят, что A сравнимо с R:

Значение остатка R может быть вычислено следующим образом:

Перепишем выражение (7) в следующем виде:

Из теории чисел известно, что операция приведения по модулю инвариантна к сложению и умножению, т. е. величина остатка не зависит от того, вычислен он от суммы (произведения) или от каждого слагаемого (сомножителя), а затем соответствующие частичные остатки просуммированы (перемножены) и от результата вычислен остаток по модулю.

Поэтому выражение (8) может быть представлено в следующем виде

В таком виде значительно облегчается задача нахождения остатка R и неполного частного Q от числа А по модулю P с использованием конвейерного режима.

Вначале на первом такте в первом слое конвейера от первого числа вычисляют первый частичный остаток t₁:

а также старший разряд неполного частного q_n−2:

где ⌊x⌋ – целая часть числа x.

На втором такте во втором слое конвейера от первого числа вычисляют второй частичный остаток t₂:

а также (q_n−3)-й разряд неполного частного:

При этом одновременно от второго числа в первом слое конвейера вычисляют первый частичный остаток t₁ в соответствии с (10), а также старший разряд неполного частного q_n−2 в соответствии с (11).

На третьем такте в третьем слое конвейера от первого числа вычисляют третий частичный остаток t₃:

а также (q_n−4)-й разряд неполного частного:

При этом одновременно от второго числа во втором слое конвейера вычисляют второй частичный остаток t₂ в соответствии с (12), а также (q_n−3)-й разряд неполного частного в соответствии с (13), а от третьего числа в первом слое конвейера вычисляют первый частичный остаток t₁ в соответствии с (10) и (q_n−2)-й разряд неполного частного в соответствии с (11).

На (n−1)-м такте в (n−1)-м слое конвейера от первого числа вычисляют (n−1)-й частичный остаток t_n−1:

который и является искомым остатком R от первого числа A по модулю P, поступившего на вход конвейера, а также q₀-й разряд неполного частного

При этом в (1…(n−2))-м слоях конвейера будут находиться соответствующий частичный остаток, согласно вышеприведенным выражениям, от поступивших на его вход чисел, а также соответствующие разряды неполного частного. Соответственно на каждом следующем такте будем в (n−1)-м слое конвейера получать остатки и неполные частные от чисел, поступающих на вход по модулю P.

Операция приведения по модулю P в каждом слое конвейеризации выполняется исходя из следующих соображений.

По определению величина t_i−1 лежит в диапазоне 0≤t_i−1≤P−1, поэтому величина

до приведения ее по модулю может принимать значения в диапазоне от 0 до 2P−1, так как a_n−i−1 может принимать значение 0 или 1. Приведение по модулю величины t_i осуществляется по следующим правилам:

Причем, если справедливо выражение (19), то (q_n−i−1)-й разряд неполного частного принимает значение равное 0, если же справедливо выражение (20), то (q_n−i−1)-й разряд неполного частного принимает значение равное 1.

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

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

На фиг. 1 представлена схема конвейерного вычислителя. Конвейерный вычислитель содержит (n−1) параллельных регистров 1.1 ÷ 1.n−1, (n−1) блоков формирования частичных остатков 2.1 ÷ 2.n−1, где n – разрядность входных чисел, первые информационные входы 3 устройства, вторые информационные входы 4 устройства, первые информационные выходы 5 устройства, вторые информационные выходы 6 устройства, тактовый вход 7 устройства. Тактовый вход 7 устройства соединен с тактовыми входами (n−1) параллельных регистров 1.1 ÷ 1.n−1. Первые информационные входы 3 устройства соединены с информационными входами первого параллельного регистра 1.1, два старших разряда информационных выходов которого соединены с первыми информационными входами первого блока формирования частичных остатков 2.1, вторые информационные входы устройства соединены со вторыми информационными входами блоков формирования частичных остатков 2.1 ÷ 2.n−1, информационные выходы (n−1)-го блока формирования частичных остатков 2.n−1 соединены с первыми информационными выходами 5 устройства. Второй информационный выход (n−1)-го блока формирования частичных остатков 2.n−1 соединен с самым младшим разрядом вторых информационных выходов 6 устройства. Первые информационные выходы i-го блока формирования частичных остатков 2.i, i=(1, …, (n−2)), соединены с m младшими разрядами информационных входов (i+1)-го параллельного регистра 1.i+1, где m – разрядность модуля, m=(2, …, n), а (n−1) – разрядность неполного частного, второй информационный выход соединен с (m+1)-м разрядом информационных входов (i+1)-го параллельного регистра 1.i+1, m младших разрядов информационных выходов которого соединены со (2, ... , (m+1))-ми разрядами первых информационных входов (i+1)-го блока формирования частичных остатков 2.i+1, с первым разрядом первых информационных входов которого соединён самый старший (n+m−1)-й разряд информационных выходов (i+1)-го параллельного регистра 1.i+1, (n+m−i−1) старших разрядов информационных входов которого соединены с (n+m−i−1) старшими разрядами информационных выходов i-го параллельного регистра 1.i, ((m+1), …, (n−2))-ые разряды информационных выходов (n−1)-го параллельного регистра 1.n−1 соединены соответственно с ((n−1), …, 2)-ми разрядами вторых информационных выходов 6 устройства, разрядность первого параллельного регистра 1.1 равна n, а 1.2, …,1.n−1-го параллельного регистра равна (m+n−1).

На фиг. 2 представлена схема блока формирования частичных остатков 2.i, i=1, …, (n−1). Блок формирования частичных остатков 2.i содержит сумматор 8 и мультиплексор 9. Первые информационные входы сумматора 8 и мультиплексора 9 соединены с первыми информационными входами блока формирования частичных остатков 2.i, вторые информационные входы сумматора 8 соединены со вторыми информационными входами блока формирования частичных остатков 2.i, информационные выходы сумматора 8 соединены со вторыми информационными входами мультиплексора 9, а выход переноса соединён со вторым информационным выходом блока формирования частичных остатков 2.i и с управляющим входом мультиплексора 9, выходы которого соединены со вторыми информационными выходами блока формирования частичных остатков 2.i, а на вход переноса сумматора 8 подаётся сигнал логической единицы.

На фиг. 3 представлено распределение разрядности параллельных регистров 1.1 ÷ 1.n−1. Первый параллельный регистр 1.1 имеет разрядность n, равную разрядности входных чисел, а параллельные регистры 1.2, …, 1.n−1 имеют разрядность равную (m+n−1), где m – разрядность модуля.

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

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

В исходном состоянии параллельные регистры 1.1÷1.n−1 обнулены. На тактовый вход 7 устройства поступают тактовые импульсы. На первые информационные входы 3 устройства с каждым тактовым импульсом подаются числа A_i, от которых необходимо вычислить остаток по модулю P. На вторые информационные входы 4 устройства, в течение всего цикла формирования остатков, подаётся инверсный код модуля P.

На первом такте первое число A записывается в параллельный регистр 1.1. При этом два старших разряда a_n−1 и a_n−2 первого числа A с выходов параллельного регистра 1.1 поступают на первые информационные входы блока формирования частичных остатков 2.1, который вычисляет значение первого частичного остатка от первого числа в соответствии с выражением (10), а также значение старшего разряда q_n−2 неполного частного в соответствии с (11). С первых информационных выходов блока формирования частичных остатков 2.1 m – разрядное значение первого частичного остатка первого числа поступает на (1...m)-ые разряды информационных входов второго параллельного регистра 1.2. Значение старшего разряда q_n−2 неполного частного первого числа со второго информационного выхода блока формирования частичных остатков 2.1 поступает на (m+1)-й разряд информационных входов параллельного регистра 1.2. На (m+2)…(m+n−2)-ые разряды информационных входов этого же параллельного регистра 1.2 поступают значения (1…n−2)-ых разрядов первого входного числа с информационных выходов первого параллельного регистра 1.1.

На втором такте в первый параллельный регистр 1.1 с первых информационных входов 3 устройства записывается второе число, а во второй параллельный регистр 1.2 записывается первый частичный остаток t₁ первого числа с первых информационных выходов блока формирования частичных остатков 2.1, значение старшего разряда неполного частного q_n−2 с его второго информационного выхода и значения (1…(n−2)) разрядов первого числа с информационных выходов параллельного регистра 1.1. В результате на первый разряд первых информационных входов блока формирования частичных остатков 2.2 с информационных выходов второго параллельного регистра 1.2 поступит значение (n−2) разряда первого числа, а на остальные разряды поступит значение первого частичного остатка от первого числа с информационных выходов первого блока формирования частичных остатков 2.1.

В результате на первых информационных выходах блока формирования частичных остатков 2.1 будет сформирован первый частичной остаток t₁ от второго числа, на втором информационном выходе блока формирования частичных остатков 2.1 будет сформировано значение старшего разряда q_n−2 неполного частного второго числа, на первых информационных выходах блока формирования частичных остатков 2.2 будет сформирован второй частичный остаток t₂ от первого числа в соответствии с (12), а на втором информационном выходе блока формирования частичных остатков 2.2 будет сформировано значение q_n−3 разряда неполного частного первого числа в соответствии с (13).

На (n−1)-ом такте на первых информационных выходах (n−1)-го блока формирования частичных остатков 2.(n−1) будет сформирован (n−1)-й частичный остаток t_n−1 от первого числа, являющийся остатком от числа по модулю P, который и поступит на информационные выходы 5 устройства. На втором информационном выходе (n−1)-го блока формирования частичных остатков 2.(n−1) будет сформирован q₀ разряд неполного частного первого числа, который вместе с (q_n−2, … , q₁) разрядами неполного частного первого числа с (m+1) … (m+n−2) разрядов информационных выходов 1.n-1 параллельного регистра поступят на вторые информационные выходы 6 устройства, образуя неполное частное первого числа, поступившего на первые информационные входы 3 устройства на первом такте, по модулю P.

На последующих тактах на первых информационных выходах 5 устройства будут последовательно сформированы остатки от второго, третьего и последующих чисел, поступивших на первые информационные входы 3 устройства, а на вторых информационных выходах 6 устройства будут последовательно сформированы неполные частные от второго, третьего и последующих чисел, поступивших на первые информационные входы 3 устройства.

Блок формирования частичных остатков 2.i, i=(1, …, (n−1)) реализует выражения (19) и (20) следующим образом (см. Фиг. 2). Так как на вторые информационные входы сумматора 8 поступает инверсный код модуля P, а на вход переноса сигнал логической единицы, то сумматор 8 реализует операцию вычитания t_i−P. В случае, если t_i≥P на выходе переноса сумматора 8 появляется сигнал логической единицы, который, поступая на управляющий вход мультиплексора 9, скоммутирует с его выходами вторые информационные входы, если же t_i<P, то на выходе переноса сумматора 8 будет сигнал логического нуля и на выходы мультиплексора 9 будут скоммутированы его первые информационные входы. В результате на выходах мультиплексора 9 всегда будет значение t_i mod P, которое поступает на первые информационные выходы блока формирования частичных остатков 2.i. Сигнал с выхода переноса сумматора 8 также поступает на второй информационный выход блока формирования частичных остатков 2.i и является соответствующим разрядом неполного частного.

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

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

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

1. Патент на изобретение RU 2012137 C1. Устройство для формирования остатка по произвольному модулю от числа. Опубликован 30.04.1994.

2. Патент на изобретение RU 2348965 C1. Вычислительное устройство. Опубликован 10.03.2009, Бюл. №7.

3. Патент на изобретение RU 2029435 C1. Комбинационный рекуррентный формирователь остатков. Опубликован 20.02.1995.

4. Патент на изобретение RU 2324972 C2. Устройство для формирования остатка по произвольному модулю от числа. Опубликован 20.05.2008. Бюл. №14.

5. Патент на изобретение RU 2421781 C1. Устройство для формирования остатка по заданному модулю. Опубликован 20.06.2011. Бюл. №17.