Устройство для вычисления скалярного произведения векторов Советский патент 1991 года по МПК G06F17/16 

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

Цель изобретения - расширение функциональных возможностей устройства за

счет умножения k пар векторов (k 1, N)

„ k

размерности Ni (i 1, k; 2) NI N), где N i 1

максимальная размерность перемножаемых векторов.

На фиг. 1 представлена структурная схема устройства; на фиг. 2 - структурная схема регистра бегущей единицы; на фиг. 3 - структурная схема блока сумматоров; на

фиг. 4 и 5 - структурная схема коммутатора.

Устройство (фиг. 1) содержит группу информационных входов 1i(i 1, N) устройства, вторую группу входов 2s коммутатора 3, первую группу выходов 4| коммутатора 3, вторую группу информационных входов 5| устройства, вторую группу выходов 6 коммутатора, группу настроечных входов 7i устройства, пятую группу входов 8i и третью группу выходов 9i коммутатора 3, входы начальной установки 10 и синхронизации 11 устройства, группу регистров 12 бегущей единицы, группу блоков 13 триггеров, группу сдвиговых регистров 14, группу блоков 15 элементов И, группу сумматоров 16, блок 17 сумматоров, l-ю группу выходов

о

00

ы ы

18м, j (I 1, log2N+1; j - номер выхода в группе) устройства.

Регистр 12 бегущей единицы (фиг. 2) содержит информационный выход 19, вход 20 начальной установки, вход 21 синхрони- зации, информационный вход 22, триггер 23, сдвигающий регистр 24, элемент И 25, выходы 26i, 262,.... 26п бегущей единицы.

Блок 17 сумматоров (фиг. 3} содержит триггер 27 хранения переноса, информаци- онные входы 28i, 28228м, вход 29 начальной установки, вход 30 синхронизации, двухвходовые последовательные сумматоры 31, каждый из которых состоит из комбинационного трехвходового сумматора 32, выходного триггера 33.

Коммутатор 3 содержит узлы 34 коммутации, каждый из которых состоит из инвертора 35, группы элементов И 36 и группы элементов ИЛ И 37, выходы 38 дешифратора 39, настроечные входы 40 узлов 34 коммутации, группу инверторов 41, группу элементов И 42, группу элементов ИЛИ 43.

Сумматоры 16 выполнены последовательными многойходовыми.

Работа дешифратора 39 поясняется табл. 1.

Устройство работает в 2L режимах, отличающихся размерностью перемножаемых векторов,где

L log2(log2N) - число управляющих входов 7i7ь

где N - число информационных входов в

первой 11,...,1ы и второй 5iSN группах

информационных входов устройства.

« В статическом состоянии при работе устройства, например, в первом режиме, когда перемножаются два вектора максимальной размерности N разрядности m каждый, либо вычисляют скалярные произ- ведения нескольких лар векторов размерностей

Nk 2Р, р - О, 1, 2Iog2N; №макс N,

перед 1-м синхроимпульсом на входы It,

12,...,1N и 5i, 62SN устройства подаются

1-е разряды элементов перемножаемых векторов, на настроечные входы 7i, 72,...,L устройства - статические уровни сигналов, соответствующие режиму работы устройства.

Значения сигналов на настроечных входах устройства в зависимости от режима работы приведены в табл. 2.

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

Пусть в первом режиме работы устройства перемножаются два вектора:

Х Х1Х2 ... XNl

и

Y yiy2 -yNi

максимальной размерности NI разрядности элементов щ.

Первоначально на упрарляющиу зходах 7i, 2, ... , 7i устанавливают сигналы, соответствующие первому режиму раЬоты устройства (см. табл. 2), затем на вход 10 начальной установки подают импульс, сопровождая его синхроимпульсом по входу 11 синхронизации. При этом устройство устанавливается в исходное состояние: в первые триггеры регистров 12 бегущей единицы записывается 1, все остальные триггеры устройства установлены в состояние логического О.

После этого на входы 1i, 12, ... ,1ы подают младшими разрядами вперед соответственно элементы вектора X:

...Х13Х12Хп, Х2 Х2щ ... Х23 Х22 X2l,

..., XN1 XNlni XN13XN12XN11

на входы 5i,52, ... ,5м подают младшими разрядами вперед соответствующие элементы вектора Y : yi yim ... У13У12 ynj,

У2 У2щ ...У23 У22

УМ1 УМЩ1 ... УМ13 Щ2 УМ11,

сопровождая каждый разряд импульсом на входы 11 синхронизации.

После второго синхроимпульса младшие разряды элементов вектора X xn. X21, ..., XN11 находятся в первых триггерах соответствующих триггеров блоков 13 группы, з младшие разряды операндов вектора Y уп, У21,..., уып находятся в первых триггерах соответствующих сдвиговых регистров 14 группы, логические произведения младших разрядов соответствующих операндов векторов xii уп, Х21 У21XNH УМЦ находятся на первых информационных входах сумматоров 16 группы, с выходов которых они поступают на группу информационных входов блока 17 сумматоров, на выходе 18/у.у (77 1092 N) которого появляется младший разряд скалярного произведения векторов.

Аналогично устройство работает щ тактов. С(щ + 1)-го по 2п-|-й такты на входы 1i,

12,... 1l, 5i, 625L поступают логические

О, а с выхода 18/j. (77 1092 N) при этом считывают значения щ старших разрядов скалярного произведения векторов.

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

Ni N1 разрядности щ, во втором - N2 -г1 и

Ni П2 - 2щ, в третьем - N3 -7- и пз 4щ и

I

т.д., в I 2-м режиме перемножаются два вектора размерности N2L 1 разрядности ni. Индексы задействованных входов в первой 1i, 1а, ... , IN и второй 5i, 62,..., SN группах информационных входов устройства, на которые подаются элементы векторов в 1-м режиме, образуют ряд, каждый член которого fc может быть вычислен по формуле

(D

fc 1 + (с-1),

где с - порядковый номер члена ряда;

I - номер режима.

В первом режиме элементы первого вектора подаются соответственно на входы

11, 12, 1з1м, элементы второго вектора

- соответственно на входы 5i, 62, 5з5ы

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

нечетные входы 1i, 1з, 1sIN-I первой

группы информационных входов, элементы другого - на нечетные входы 5i, 5з, 5s, ... , 5м-1 второй группы информационных входов устройства. В третьем режиме элементы первого вектора подаются по порядку на каждый четвертый вход первой группы информационных входов: 1i, 1s, 1, ... , 1м-з, элементы второго вектора - на каждый четвертый вход второй группы информационных входов устройства: 5i, 5в, S...., SN-З и т.д. В I 2-м режиме элемент первого вектора подается на вход 1i, элемент второго вектора - на вход 5i устройства. При перемножении двух векторов в перечисленных режимах их скалярное произведение считывается с выхода 18 (7 Iog2 N) устройства.

Устройство позволяет одновременно вычислять скалярное произведение нескольких векторов, разделенных на две группы. Полученные в результате умножения векторов первой группы на соответствующие вектора второй группы скалярные произведения считываются с соответствующих выходов из множества 8 (ц 1,2,...,

IOQ2 N-1, J 1, 2 -) , а с выхода 18

()/ loQ2 N) можно считать сумму всех полученных скалярных произведений. Размер

ности перемножаемых векторов при этом

Nki.2p, гдер 0, 1,2log2Ni.

Индексы входов в первой 1i, 12,..., IN и второй 5i, 62 SN группах информационных входов устройства, на которые подаются первые элементы перемножаемых

0

5

0

векторов, образуют ряд, каждый член mt которого может быть найден по формуле

mt - 1 + 2м Nk| (t - 1), где t - порядковый номер члена ряда;

Nki - размерность k-ro вектора;

I - номер режима;

k - номер вектора в группе.

Вторые и следующие элементы перемножаемых векторов подаются последовательно за первыми элементами на входы с индексами, найденными по формуле (1).

Сумма размерности Nki перемножаемых векторов в каждой группе векторов не превышает максимальной размерности NI при перемножении двух векторов в данном

NI режиме Z Nki 5 N1 . Соответствующие скаk 1

лярные произведения считывают с выходов 1{Ы, причем

Г}

M.MV (2М -Nki-1)

Iog2 (2Ь1 Nk,); j

21 Nki

Формула изобретения

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

сти Ni (I 1, k;

где N i 1

максимальная размерность перемножаемых векторов, в него введены коммутатор, группа регистров бегущей единицы, группа сдвиговых регистров, блок сумматоров, причем первая и вторая группы входов коммутатора образуют соответственно первую и вторую группы информационных входов устройства, группа настроечных входов которого является третьей группой коммутатора, i-й выход первой группы выходов и 1-й вход четвертой группы входов которого подключены соответственно к информационным входу и выходу i-ro сдвигового pein- стра (1 1, N), группа разрядных выходов которого подключена к соответствующим входам первой группы элементов И блока i-й группы, входы второй группы которого подключены к выходам соответствующих триггеров 1-го блока группы, информационные входы которых объединены с i-м выходам второй группы выходов коммутатора, 1-й выход третьей группы выходов и i-й вход пятой группы входов которого подключены

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

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

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

образована выходами 1-й группы блока сумматоров.

Изобретение относится к вычислительной технике и может быть использовано при построении высокопроизводительных конвейерных систем с последовательной поразрядной обработкой операндов. Целью изобретения является расширение функциональных возможностей устройства за счет умножения к пар векторов (к 1, N) размерности NI (I 1, к; 2) Ni N), где N - максиI 1 мальная размерность перемножаемых векторов. Для этого в устройство, содержащее группу блоков триггеров, группу блоков элементов И, группу сумматоров, введены коммутатор, группа регистров бегущей единицы, группа сдвиговых регистров и блок сумматоров. Элементы перемножаемых векторов поступают на первую и вторую группы информационных входов устройства одновременно в последовательном коде. Результаты вычислений считываются с групп выходов устройства. 2 табл , 5 ил 1Л

1 1 1

Таблица 1

11

Таблица 2

#M/i

7, , 7/

Сриг.5