Однородная параллельная вычислительная структура для вычисления произведения матрицы на вектор Советский патент 1986 года по МПК G06F17/16 

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

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

На фиг. 1 представлена схема однородной параллельной вычислительной структуры для вычисления произведения матриць на вектор при га 3, п 4; на фиг. 2 - схема блока сумматоров К-и строки j-ro столбца матрицы.

Однородная параллельная вьгчисли J

/ а

25

Ь.

(2)

30

и сформируем матрицу бипарных элементов 1зида

35

А

тельная структура для вычисления про- ,„ а; матрицы А в разрядной форме как изведения матрицы на вектор (фиг. 1) содержит блоки сумматоров I, К-разря- дов j входных шин (j 1, 2, ..., г) (при к 1-3) соответственно 2,3, 4 ; (m+i) входных шин (при i 1-3), соответственно 5-7 и m выходных шин 8-10 и К, i. входных шин i 1, „. .,m (при m 3), соответственно 11-19. Блоки сумматоров 1 сформированы в виде матрицы размерностью (т, п), причем каждый блок сумматоров 1 (фиг. 2) содержит m двухвходовых маторов 20, выход каждого i-ro из которых соединен со входом первого слагаемого (i+l)-ro сумматора 20. Выход т-го двухвходового сумматора 20 j-ro блока сумматоров 1 К-и строки матрицы соединен со сдвигом 2 со входом первого слагаемого первого двухвходового сумматора 20 (j+l)-го блока сумматоров 1 этой же строки матрицы, входы вторых слагаемых i-x двухвходовых сумматоров 20 всех блоков сумматоров 1 К-й строки матрицы объединены и соединены с (К, )-й входной шиной устройства. Управляющие входы i-x двухвходовых сумматоров 20 каждого блока сумматоров 1 j-ro столбца матрицы объединены и подключены к j-му разряду К-й входной шины устройства. Вход первого слагаемого первого двухвходового сумматора 20 i-ro блока сумматоров 1 первого столбца матрицы соединен с (т-«-1)-й входной шиной (при m 3,

40

(3)

45

i 1, ш

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

50

1,ш t3)

где компонентами Ь; вектора,Ь являются i-e компоненты векторов Ь.„, « . ..Ь,

im-«-U-fl входной шиной (.при m J, ся i-e компоненты векторов п., « . .о„ . соответственно 5-7) . Вьгход т-го двух- Тогда компоненты С; вектора С (С,, входового сумматора 20 i-ro блока сум- Cj , .. .,ё„) могут быть определены на сумматоров 1 последнего столбца мат- основе следую1Щ1х рекурентных выраже- риць соединен с (2m+i)-й выходной ний

3, соответ

шиной устройства (при m ственно 8-10) .

Работа однородной параллельной структуры для вычисления произведения матрицы А на вектор В, когда каяг дьй компонент результата произведений А Ь С вектора С (С,, , ...,С„) формируется как

т

21 Ь;,

1, га,

где а ;

Ь;

с.

элементы матрицы А;

-компоненты вектора Ь;

-компоненты вектора С, осуществляется следующим образом.

Для организации йднородной вычислительной структуры запишем компоненты С; , Ь; векторов С, Ь и элементы

J

;

/ а

25

Ь.

(2)

,„ а; матрицы А в разрядной форме как

30

и сформируем матрицу бипарных элементов 1зида

,„ а; матрицы А в разрядной форме как

А

; матрицы А в разрядной форме как

(3)

,„ а; матрицы А в разрядной форме как

45

i 1, ш

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

,„ а; матрицы А в разрядной форме как

50

1,ш t3)

; матрицы А в разрядной форме как

где компонентами Ь; вектора,Ь являются i-e компоненты векторов Ь.„, « . ..Ь,

ся i-e компоненты векторов п., « . .о„ . Тогда компоненты С; вектора С (С,, Cj , .. .,ё„) могут быть определены на основе следую1Щ1х рекурентных выраже- ний

-( U-2 Ь

+ 2 ., + ... + 2 Ajb, + + 2 A.b, C;;

ra

или соответственно

К

о, г, 2,..., rrJ;

1,2, ,, .,i)i.

Однородная параллельная вычислительная система для вычисления про изведения матрицы на вектор (фиг. 1) работает следующим образом. На ные шины 11-13 подаются элементы а„ , а,2 , а , матрицы А соответственно. На входные шины 14-19 подаются зна-

чения элементов а, , ajj,

а 23 а

31

а.,., а матрицы А. Кроме того, на первый 2 , второй 2, третий 2 и четвертый 2 разряды первой входной шины подаются значения разрядов с первого по четвертый Ь , , Ь, , Ъ , и Ь соответственно первого компонента Ъ, вектора Ь, а также на первый 3,4 вторые 3, 4, третий 3, 4 и четвертые разряды 3 , 4 второй н третьей входных шнн подшотся значения первых разрядов Ь , b вторых - b , Ь, третьих Ь, b j и четвертых Ь, Ь второго bi и третьего Ь компонентов вектора b . Если на входные шины 5-7 подаются значения компонентов L, Lj, L;j некоторого вектора L (L,, LJ, , L), то в устройстве

4)

to

f5

реализуется выражение L + Ab, когда L, L 0 O вычисляется только произведение матрицы А на вектор b (каждый двухвходовый матор 20 блока сумматоров 1 выпол иен на интегральной схеме и реализует операцию суммирования, когда па его управляющем входе единичный сигнал, и пропускает информацию с первого входа на выход без изменения, когда на его управляющем входе нулевой сигнал) . После подачи исходной информации в схеме устройства протекает переходной процесс, по окончании которого на выходах первого, второго и третьего блоков сумматоров 1 первого столбца по выражению (5) вычисляются значения

(5) 25

соответственно каждое из которых поступает со сдвигом 2 на первый вход первого двухвходового сумматора 20 соответственно первого, второго и третьего блоков сумматоров 1 второго столбца. В каждом блоке сумматоров 1, начиная с первого, второго столбца, матрицы вычисляются по выражению (5) соответственно значения

35

(О

+ 2-(а„Ь а; Ь, 4- ,)

Ч

5

0

5

каждое иэ которых подается со сдвигом 2 на первьш вход двухвходового сумматора 20 соответствующего блока сумматоров 1 третьего столбца матрицы. На выходе последнего двухвходово- го сумматора 20 первого, второго и третьего блока сумматоров 1 третьего столбца матрицы, по выражению 5) образуются значения С,, С , , которые со сдвигом 2 подаются на первые входы первых двухвходовых сумматоров 20 соответственно первого, второго и третьего блоков сумматоров 1 последнего столбца матрицы. И, наконец, на выходах первого, второго и третьего блоков сумматоров 1 последнего столбца матрицы по выражению (5)

оВразуются значения компонент С|

p(ti -

г - г 2 г

С - С искомого

произведения матрицы А на вектор Ь, т.е.

А Ь С (С,, С, Сд) .

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

Однородная параллельная вычисли-- тельная структура для вычисления произведения матрицы на вектор, содер жащая матрицу (т, п) блоков суммато-- ров, причем каждый блок сумматоров содержит два сумматора, выход первог сумматора подключен к входу первого слагаемого второго сумматора, о т личающаяся тем, что, с целью повышения быстродействия за счет уменьшения числа тактов до одного, в каждый блок сумматоров введены допол нительно (т-2)сумматоров, причем выход i-ro (i 3| m-1) сумматора подключен к входу первого слагаемого (i+l)-ro сумматора, выход га-го сум-

матера блока сумматоров j-ro столбца (J I, п-1) и К-й строки (К 1, га) матрицы подключен со сдвигом на один разряд в сторону старших разрядов к входу первого слагаемого первого сумматора блока сумматоров (j+l)-ro столбца К-и строки матрицы, входы вторых слагаем1)1х К-х сумматоров блоков сумматоров К-и строки матрицы объединены и образуют К-ю входную шину значений элементов матрицы структуры, входы управления операцией дв; / свходовых сумматоров блоков сумматоров j-ro столбца матрицы объединены и подключены к j-му разряду к-й входной шины задания первого вектора структуры, входы первого слагаемого первых сумматоров блоков сумма- торов первого столбца матрицы подключен к входной шине задания второго вектора структуры, выход m сумматоров блоков сумматоров последнего столбца матрицы образуют выходную шину ре- зулътата структуры.

Изобретение относится к вычислительной технике и позволяет сократить время вьгаислений произведения матрицы на вектор. Одновременная параллельная вычислительная структура для вычисления произведения матрицы на вектор . содержит матрицу (т, t блоков сумматоров, причем каждый блок сумматоров содержит m сумматоров. В общем случае изобретение позволяет вычислять, выражение вида L + А Б, где L и В - первый и второй векторы; А - матрица. Результат вычислений формируется на выходах соответствующих блоков сумматоров последнего столбца матрицы. 2 ил. (Л с го С/д Oi ел

Ю

ш

4-4 гз

Фиг.г