Устройство для вычисления скалярного произведения векторов

Устройство для вычисления скалярного произведения векторов

Иллюстрации

Показать все

Реферат

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК (505 Q 06 F 15/347

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4751872/24 (22) 23.10.89 (46) 07.10.91. Бюл. М 37 (72) В.В.Гричук, А.П.Царев, И.И,Чебан и

А.Г.Шенешеуцкий (53) 681.3(088.8) (56) Авторское свидетельство СССР

ЬЬ 1280389, кл. G 06 F 15/347, 1984.

Авторское свидетельство СССР йи905814, кл.G 06 F 7/52, 1981. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

СКАЛЯРНОГО ПРОИЗВЕДЕНИЯ BEKTOРОВ (57) Изобретение относится к вычислительной технике и может быть использовано при построении высокопроизводительных конвейерных систем с последовательной поразрядной обработкой операндов. Целью

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

Цель изобретения — расширение функциональных возможностей устройства эа счет умножения k пар векторов (k - 1, N)

k размерности Ni (! =- 1, k; ), М N), где й—

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

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

„„Я „„1683033 А1 изобретения является расширение функциональных возможностей устройства за счет умножения k пар векторов (k = 1, N) размерk ности Nl(i=1, k; g Nl ЯЧ), где N — макси1=1 мальная размерность. перемножаемых векторов. Для этого в устройство, содержащее группу блоков триггеров, группу блоков элементов И, группу сумматоров, введены коммутатор, группа регистров бегущей единицы, группа сдвиговых регистров и блок сумматоров. Элементы перемножаемых векторов поступают на первую и вторую группы информационных входов устройства одновременно в последовательном коде.

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

16, блок 17 сумматоров, I-ю группу выходов

1683033

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

Регистр 12 бегущей единицы (фиг. 2) содержит информационный выход 19, вход

20 начальной установки, вход 21 синхронизации, информационный вход 22, триггер

23, сдвигающий регистр 24, элемент И 25, выходы 261, 262, ..., 26n бегУщей единицы.

Блок 17 сумматоров (фиг. 3) содержит триггер 27 хранения переноса, информационные входы 281, 282, ..., 28N, вход 29 начальной.установки, вход 30 синхронизации, двухвходовые последовательные сумматоры 31, каждый из которых состоит из комбинационного трехвходового сумматора 32, выходного триггера ЗЗ.

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

39, настроечные входы 40 узлов 34 коммутации, группу инверторов 41, группу элементов И 42, группу элементов ИЛИ 43.

Сумматоры 16 выполнены последовательными многойходовыми, Работа дешифратора 39 поясняется табл. 1.

Устройство работает в 2 режимах, отличающихся размерностью перемножаемых векторов, где ! = log2(log2N) — число управляющих входов 71,...,7i, где и — число информацйонных входов в первой 11,...,1N и второй 51,...,5N группах информационных входов устройства.

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

Nk = 2Р, p = 0, 1, 2,..., log2N; К! макс = N, перед !-м синхроимпульсом на входы l1, 12 11м и 51 52 5й устройства подаются !

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

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

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

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

X = (x1.õ2 „, xN1) Y = (у1у2 "уй1) максимальной размерности N1 разопдности элементов п1.

Первоначально на управляющих входах

71, 72, ..., 7! устанавливают сигналы, соответствующие первому режиму работы устройства (см. табл. 2), затем на вход 10 начальной установки подают импульс, сопровождая его синхроимпульсом по входу

11 синхронизации, При этом устройство устанавливается в исходное состояние: в пер10 вые триггеры регистров 12 бегущей единицы записывается "1", все остальные триггеры устройства установлены в состояние логического "0".

После этого на входы 11, 12, „,,1м подают младшими разрядами вперед соответственно элементы вектора Х;

Х1 = (X1n1 ... Х13 Х12 Х n ) Х2 = (Х2п1 „, X23 Х22 Х21), „„Х(ц1 = (ХИ1п1 .. ХИ13 XN12 XN11) на входы 51,52, ...,5м подают младшими разрядами вперед соответствующие элементы вектора Y: у1 = (у1п1 „, у13 у12 у11), У2 = (У2п1 У23 У22 У21)

У!41 (УИ1п1 ° ° У 13 УК12 УИ11) сопровождая каждый разряд импульсом на

30 входы 11 синхронизации.

После второго синхроимпульса младшие разряды элементов вектора X х11. х21, ..., xN11 находятся в первых триггерах сооТветствующих триггеров блоков 13 группы, а младшие разряды операндов вектора Y у11, у21,..., yN11 находятся в первых триггерах соответствующих сдвиговых регистров 14 группы, логические произведения младших разрядов соответствующих операндов векторов х11 j11 х21 у21,..., xN11 ум11 находятся на первых информационных входах сумматоров 16 группы, с выходов которь:х они поступают на группу информационных входов блока 17 сумматоров, на выходе

18 (g =log2 N) которого появляется младший разряд скалярного произведения векторов.

Аналогично устройство работает п1тактов. C(n1+ 1)-го по 2п1-й такты на входы 11, 12„.. 11, 51, 52,..., 5 поступают логические

"О", а с выхода 18,. (y = log2 N) при этом считывают значен я п1 старших разрядов скалярного произведения векторов.

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

1683033

N> разрядности п1, во втором — Ng - — и

N1

N1 п2 - 2n>, в третьем — йз = — и пз - 4п1 и

4 т.д„в l - 2 -.м режиме перемножаются два 5 вектора размерности Nz = 1 разрядности пг = N> п . Индексы задействованных входов в первой 11, Ы...,, 1м и второй 5i, 5z,..., 5н группах информационных входов устройства, на которые подаются элементы векторов в 1-м режиме, образуют ряд, каждый член которого fc может быть вычислен по формуле

fc=1+ 2 (с-1), где с — порядковый номер члена ряда;

l — номер режима.

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

1>, l2, 1з, ..., 1ы, элементы второго вектора 20 — соответственно на входы 51, 52, 5з,..., 5м устройства. При работе устройства во втором режиме элементы одного иэ перемножаемых векторов подаются по порядку на нечетные входы 1>, 1з, 1в, ..., 1м-1 первой группы информационных входов, элементы другого — на нечетные входы 51. 5з, 56, ..., 5N-1 второй группы информационных входов устройства. В третьем режиме элементы первого вектора подаются по порядку на каждый четвертый вход первой группы информационных ВхОдОВ: 11, 15, 17, ..., 1Я-з, элементы второго вектора — на каждый четвертый вход второй группы информационных входов устройства 5I, 55, 57,..., 5й-3 и 35 т.д, В = 2 -м режиме элемент первого векL тора подается на вход 1I, элемент второго вектора — на вход 5> устройства, При перемножении двух векторов в перечисленных режимах их скалярное произведение считы- 40 вается с выхода 18>, (y = loge N) устройст-. ва.

Устройство позволяет одновременно вычислять скалярное произведение нескольких векторов, разделенных на две 45 группы. Полученные в результате умножения векторов первой группы на соответствующие вектора второй группы скалярные произведения считываются с соответствующих выходов из множества 18 (= 1, 2, ..., log2 N-1, j = 1, 2, .„, — -), а с выхода 18

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

Nk;= 2, где р = О, 1, 2...„!Оцгйь р

Индексы входов в первой 1i, 1z,..., 1м и второй 5, R,"., 5N группах информационных входов устройства, на которые подаются первые элементы перемножаемых векторов, образуют ряд, каждый член mq которого может быть найден по формуле

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

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

1 — номер режима;

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

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

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

Nl режиме Z Nkl N> . Соответствующие скаk=1 лярные произведения считывают с выходов

18Ц, причем

rj

٠+ (2 Nkl — 1)

= loge(2 f+lj; J— г и, Формула изобретения

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

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

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

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

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

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

Таблица 1

Статические уровни сигналов на входах дешифратора 39

Статические уровни сигналов на выходах дешифратора 39

Режим

1 I

7 .- г 38 38 з 38,, 38 ...38 ц38 д

О 0

О О 0

О О )

О 1: О

0 1 1

О ° а е

О

0 ° ° °

О О

О О

0 О

0 0

О ... 1 0

1 1 1 1

Та блица 2

Режим

Статические уровни сигналов на управляющих входах устройства

7 7г. 7з .. ° 7 z 7 -т 7а

1 О О

2 О О

3 О 0

4 О О

О О О

О О

1 О

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

О

0 ° ° °

О

О а ° °

9 Э Р

1683033

° ° °

° ° °

° ° .Ф

° °

Э ° °

28

288

88 гвв

2ЬЮу

2У

1683033

1683033

Составитель К.Кухаренко

Техред М.Моргентал Корректор В.Гирняк

Редактор Т.Юрчикова

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101

Заказ 3414 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5