Результат интеллектуальной деятельности: КОНВЕЙЕРНЫЙ УМНОЖИТЕЛЬ ПО МОДУЛЮ

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

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

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

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

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

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

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

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

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

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

где A и B – целые положительные числа, 0≤A, B<P, называемые соответственно множимым и множителем;

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

C – целое положительное число, являющееся произведением чисел A и B, приведенным по модулю P.

Причем

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

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

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

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

n – количество разрядов в представлении чисел.

Задача состоит в том, чтобы по известным A и B отыскать произведение C по модулю P. Произведение чисел A и B по модулю P может быть представлено в следующем виде:

Учитывая, что операция приведения по модулю инвариантна к сложению и умножению, выражение (6) можно записать в виде:

Выражение (7) может быть представлено как:

Введем следующее обозначение:

Очевидно, что

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

В результате вычисление выражения (11) в конвейерном режиме может быть сведено к следующим вычислительным действиям.

На 1-й ступени конвейера вычисляют и t₀:

На 2-й ступени конвейера вычисляют a₁ и t₁:

На n-й ступени конвейера вычисляют значение а также t_n−1:

Значение t_n-1 и будет являться искомым произведением (6).

Вычисление в соответствии с (9) осуществляется последовательным удвоением числа B с одновременным приведением результата по модулю P.

Описанная выше процедура определяет вычисление произведения от одной пары чисел A и B.

Рассмотрим реализацию вычисления произведений для потока чисел A_j и B_j, поступающего потактово на вход конвейерного умножителя, j=1, 2, 3, …, .

Выражение (1) при этом примет следующий вид

Обозначим через t_i,j значение i-го частичного произведения j-й пары чисел A_j и B_j по модулю P на i-й ступени конвейера, где i =1, 2, … , n – номер ступени конвейера, j=1, 2, 3, …,  – номер такта работы устройства. Тогда

где a_i-1,j – коэффициенты в выражении (2) для A_j числа,

Очевидно, что

В результате вычисление выражения (11) в конвейерном режиме для пар чисел A_j и B_j по модулю P может быть сведено к следующим вычислительным действиям.

На первом такте работы устройства на 1-й ступени конвейера в соответствии с (19), (20) и (21) для пар чисел A₁ и B₁ вычисляют и t_0,1:

На втором такте работы устройства на 1-й ступени конвейера в соответствии с (19), (20) и (21) для пар чисел A₂ и B₂ вычисляют и t_0,2:

На j-м такте работы устройства на 1-й ступени конвейера в соответствии с (19), (20) и (21) для пар чисел A_j и B_j вычисляют и t_0,j:

На втором такте работы устройства на 2-й ступени конвейера в соответствии с (18) и (19) для пар чисел A₁ и B₁ вычисляют и t_1,1:

На третьем такте работы устройства на 2-й ступени конвейера в соответствии с (18) и (19) для пар чисел A₂ и B₂ вычисляют и t_1,2:

На j-м такте работы устройства на 2-й ступени конвейера в соответствии с (18) и (19) для пар чисел A_j и B_j вычисляют и t_1,j:

На n-ом такте работы устройства на n-й ступени конвейера в соответствии с (18) для пар чисел A₁ и B₁ вычисляют и t_1,1:

Значение t_n−1,1 и будет являться искомым произведением C₁≡(A₁·B₁) mod P.

На (n+1)-ом такте работы устройства на n-й ступени конвейера в соответствии с (18) для пар чисел A₂ и B₂ вычисляют и t_1,2:

Значение t _n−1,2 и будет являться искомым произведением C₂≡(A₂·B₂) mod P.

На (n+j)-ом такте работы устройства на n-й ступени конвейера в соответствии с (18) для пар чисел A_j и B_j вычисляют и t_{1, j}:

Значение t_n−1, j и будет являться искомым произведением C_j≡(A_j·B_j) mod P.

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

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

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

На фиг. 2 представлено распределение разрядности параллельных регистров 1.1 ÷ 1.n устройства. Первый параллельный регистр 1.1 имеет разрядность 2n, равную сумме разрядности входных чисел A и B. В разряды с 1-го по n-й первого параллельного регистра 1.1 записываются числа A_j, а в разряды с (n+1)-го по 2n-й записываются числа B_j. Параллельные регистры 1.i, где i = (2, …, n) – номер ступени конвейера, имеют разрядность равную (3n−i+1). В разряды с 1-го по (n−i+1)-й i-го параллельного регистра 1.i записываются значения разрядов числа A, причем количество этих разрядов уменьшается на каждой последующей ступени конвейера на один со стороны младших, в разряды с (n−i+2)-го по (2n−i+1)-й записываются соответствующие значения разрядов чисел а в разряды с (2n−i+2)-го по (3n−i+1)-й записываются значения разрядов чисел t_i-2.

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

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

В исходном состоянии параллельные регистры 1.1 ÷ 1.n−1 обнулены. На тактовый вход 9 устройства поступают тактовые импульсы. На первые информационные входы 5 устройства и вторые информационные входы 6 устройства с каждым тактовым импульсом подаются числа A_j и B_j, для которых необходимо вычислить произведение C_j по модулю P. На третьи информационные входы 7 устройства, в течение всего цикла формирования произведений, подаётся инверсный код модуля P. Произведение C_j по модулю P чисел A_j и B_j снимается с информационных выходов 8 устройства.

На первом такте работы устройства первые два числа A₁ и B₁ записываются в параллельный регистр 1.1. При этом значение младшего разряда a_0,1 первого числа A₁ с выходов параллельного регистра 1.1 поступает на управляющий вход первого ключа 2.1, а оставшиеся значения (a_1,1, …, a_n−1,1) разрядов первого числа A₁ поступают на (1, …, n−1)-е разряды информационных входов второго параллельного регистра 1.2. На информационные входы первого ключа 2.1 и на первые информационные входы первого умножителя на два по модулю 3.1 с (n+1, …, 2n)-го разрядов информационных выходов первого параллельного регистра 1.1 поступает код первого числа B₁. В соответствии с (23) на выходе первого ключа 2.1 образуется произведение t_0,1 = a_0,1·B₁, а в соответствии с (22) на выходе первого умножителя на два по модулю 3.1 образуется число mod P. Умножители на два по модулю 3.1 ÷ 3.n–1 могут быть реализованы в соответствии с [1].

На втором такте работы устройства в (1, …, n−1)-е разряды информационных входов второго параллельного регистра 1.2 записываются значения (a_1,1, …, a_n−1,1) разрядов первого числа A₁, в (n, …, 2n−1)-е разряды записывается значение числа а в (2n, …, 3n−1)-е разряды записывается значение числа t_0,1. С выхода первого разряда второго параллельного регистра 1.2 значение (a_1,1)-го разряда первого числа A₁, поступает на управляющий вход второго ключа 2.2. Значения (a_2,1, …, a_n−1,1) разрядов первого числа A₁ с (2, …, n−1)-х разрядов информационных выходов второго параллельного регистра 1.2 поступают на (1, …, n−2)-е разряды информационных входов третьего параллельного регистра 1.3. Значение числа с (n, …, 2n−1)-х разрядов информационных выходов второго параллельного регистра 1.2 поступает на информационные входы второго ключа 2.2 и на первые информационные входы второго умножителя на два по модулю 3.2. Значение числа t_0,1 с (2n, …, 3n−1)-х разрядов информационных выходов второго параллельного регистра 1.2 поступает на первые информационные входы первого сумматора по модулю 4.1, на вторые информационные входы которого поступает значение а на информационных выходах образуется значение числа t_1,1 в соответствии с (29), которое поступает на (2n−1, …, 3n)-е разряды информационных входов третьего параллельного регистра 1.3, на (n−1, …, 2n−2)-е разряды которых поступает значение числа в соответствии с (28). Сумматоры по модулю 4.1 ÷ 4.n–1 могут быть реализованы согласно [4].

Также на втором такте устройства вторые два числа A₂ и B₂ записываются в параллельный регистр 1.1. При этом значение младшего разряда a_0,2 второго числа A₂ с выходов параллельного регистра 1.1 поступает на управляющий вход первого ключа 2.1, а оставшиеся значения (a_1,2, …, a_n−1,2) разрядов второго числа A₂ поступают на (1, …, n−1)-е разряды информационных входов второго параллельного регистра 1.2. На информационные входы первого ключа 2.1 и на первые информационные входы первого умножителя на два по модулю 3.1 с (n+1, …, 2n)-го разрядов информационных выходов первого параллельного регистра 1.1 поступает код второго числа B₂. В соответствии с (25) на выходе первого ключа 2.1 образуется произведение t_0,2 = a_0,2·B₂, а в соответствии с (24) на выходе первого умножителя на два по модулю 3.1 образуется число

На следующих тактах работа устройства осуществляется аналогичным образом.

На n-ом такте работы устройства на информационных выходах 8 устройства в соответствии с (34) для пар чисел A₁ и B₁ будет получено значение t_n−1,1, которое и будет являться искомым произведением

На (n+1)-ом такте работы устройства на информационных выходах 8 устройства для пар чисел A₂ и B₂ в соответствии с (36) будет получено значение t_n−1,2, которое будет являться искомым произведением

На (n+j)-м такте работы устройства на информационных выходах 8 устройства для пар чисел A_j и B_j в соответствии с (36) будет получено значение t_{n−1, j} которое будет являться искомым произведением

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

Сравним быстродействие вычисления произведений чисел устройства прототипа [3] и предлагаемого устройства при реализации операции вычисления произведений для 100 пар 16-разрядных чисел. Устройство прототип при его реализации для работы с 16-разрядными числами будет содержать 8 последовательных ступеней преобразования. Обозначим через T_пр – время вычисления на одной ступени преобразования. При условии, что вычисление следующего произведения чисел не может быть начато до тех пор, пока не будет выполнено текущее вычисление, время, затрачиваемое устройством прототипом на вычисления произведения 100 пар 16-разрядных чисел, составит 800 T_пр. Предлагаемое устройство для выполнения аналогичной задачи будет содержать 16 последовательных ступеней конвейера. Обозначим через T_из – время обработки информации одной ступенью конвейера. Тогда общее время вычисления произведения 100 пар 16-разрядных чисел составит 132 T_из. Полагая (хотя фактически T_пр>T_из), получим выигрыш B в быстродействии для указанных условий вычислений

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

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

1. Патент на изобретение RU 2015537 C1. МПК G06F 7/49 (1990.01). Умножитель на два по модулю. Опубликован 30.06.1994.

2. Патент на изобретение RU 2316042 C1. МПК G06F 7/523 (2006.01), G06F 7/72 (2006.01). Устройство для умножения чисел по произвольному модулю. Опубликован 27.01.2008. Бюл. № 3.

3. Патент на изобретение RU 2751802 C1. МПК G06F 7/72 (2006.01), G06F 7/523 (2006.01). Умножитель по модулю. Опубликован 19.07.2021 Бюл. № 20.

4. Патент на изобретение RU 2032934 C1. МПК G06F 7/49 (1995.01). Сумматор по модулю. Опубликован 10.04.1995.