устройство для умножения матрицы на вектор

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

1. УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТРИЦЫ НА ВЕКТОР, содержащее n вычислительных модулей (где n - размерность квадратной матрицы), причем выход j-го вычислительного модуля (j = 1, . . . , n - 1) соединен с информационными входами первой группы (j + 1)-го вычислительного модуля, выход n-го вычислительного модуля соединен с выходом результата устройства, синхровход которого соединен с синхровходами всех вычислительных модулей, отличающееся тем, что, с целью повышения быстродействия устройства, в него введены две группы по n блоков ввода в каждой, причем i-й информационный вход первой и второй групп устройства соединены соответственно с информационными входами i-х блоков ввода первой и второй групп (i = 1, . . . , n), выходы которых соединены соответственно с информационными входами второй и третьей групп i-го вычислительного модуля, информационные входы четвертой и пятой групп которого соединены с входом логического нуля устройства, синхровход которого соединен с синхровходами всех блоков ввода первой и второй групп.

2. Устройство по п. 1, отличающееся тем, что вычислительный модуль содержит (i, j)-е вычислительные блоки первого типа (i = , j = , i j), где m - разрядность чисел, представленных в дополнительных кодах, (i, m)-е вычислительные блоки второго типа i = , (i, j) -е вычислительные блоки третьего типа (i = , j = , j>1), (i, m +1) -е вычислительные блоки четвертого типа (i = ; q= 2m + log₂n - 1, знак обозначает округление в сторону большего целого), причем i-й информационный вход первой группы модуля (i = ) соединен с первым информационным входом (i, m + 1)-го вычислительного блока четвертого типа, i-й информационный вход второй группы модуля (i = ) подключен к первому информационному входу (i, 1)-го вычислительного блока первого типа, первый выход (i, j)-го вычислительного блока первого типа (i = , j = 1, m-2, i j подключен к первому информационному входу (i + 1, j + 1)-го вычислительного блока первого типа, первый выход (i, m - 1)-го вычислительного блока первого типа (i = ) подключен к первому информационному входу (i + 1, m)-го вычислительного блока второго типа, первые информационные входы третьей и четвертой групп модуля подключены соответственно к второму и третьему информационным входам (1, 1)-го вычислительного блока первого типа j-е информационные входы третьей и четвертой групп (j = ) модуля подключены соответственно к первому и второму информационным входам (1, j)-го вычислительного блока третьего типа, первый и второй выходы (i, j)-го вычислительного блока третьего типа (i = , j = , i-j 2) подключены соответственно к первому и второму информационным входам (i + 1, j)-го вычислительного блока третьего типа, первый и второй выходы (i, j)-го вычислительного блока третьего типа (i = , j = 2, , i-j = 1) подключены соответственно к второму и третьему информационным входам (i + 1, j)-го вычислительного блока первого типа, первый и второй выходы (m - 1, m)-го вычислительного блока третьего типа подключены соответственно к второму и третьему информационным входам (m, m)-го вычислительного блока второго типа, первый и второй выходы (i, m)-го вычислительного блока второго типа (i = ) подключены соответственно к второму и третьему информационным входам (i + 1, m)-го вычислительного блока второго типа, второй и третий выходы (i, j)-го вычислительного блока первого типа (i = , j = , i-j 0) подключены соответственно к второму и третьему информационным входам (i + 1, j)-го вычислительного блока первого типа, i-й информационный вход пятой группы (i = ) модуля подключен к четвертому информационному входу (i, 1)-го вычислительного блока первого типа, i-й информационный вход пятой группы модуля (i = ), подключен к второму информационному входу (i, m + 1)-го вычислительного блока четвертого типа, четвертый выход (i, j)-го вычислительного блока первого типа (i = , j = , i-j>0) подключен к четвертому информационному входу (i, j + 1)-го вычислительного блока первого типа, четвертый выход (i, j)-го вычислительного блока первого типа (i, j = , i= j) подключен к третьему информационному входу (i, j + 1)-го вычислительного блока третьего типа, четвертый выход (i, m - 1)-го вычислительного блока первого типа (i= ) подключен к четвертому информационному входу (i, m)-го вычислительного модуля второго типа, третий выход (i, j)-го вычислительного блока третьего типа (i = , j = , j>i) подключен к третьему информационному входу (i, j + 1)-го вычислительного блока третьего типа, третий выход (i, m)-го вычислительного блока третьего типа (i = ) подключен к второму информационному входу (i, m + 1)-го вычислительного блока четвертого типа, третий выход (i, m)-го вычислительного блока второго типа (i = ) подключен к второму вычислительному входу (i, m + 1)-го вычислительного блока четвертого типа, третий информационный вход (i, m + 1)-го вычислительного блока четвертого типа (i = ) подключен к первому выходу (i - 1, m + 1)-го вычислительного блока четвертого типа, третий информационный вход (1, m + 1)-го вычислительного блока четвертого типа соединен с (m + 1)-м информационным входом четвертой группы модуля, второй выход (i, m + 1)-го вычислительного блока четвертого типа (i = ) подключен к i-му выходу группы модуля, синхровход которого подключен к синхровходам всех вычислительных блоков.

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

4. Устройство по п. 2, отличающееся тем, что вычислительный блок второго типа содержит четыре триггера, сумматор по модулю два, четыре элемента И и элемент ИЛИ, причем первый - четвертый информационные входы блока подключены соответственно к информационным входам первого - четвертого триггеров, инверсный выход первого триггера подключен к первому входу первого элемента И, выход которого подключен к первым входам второго и третьего элементов И и сумматора по модулю два, выход третьего триггера подключен к первому входу четвертого элемента И, вторым входам второго элемента И и сумматора по модулю два, выход второго триггера подключен к второму входу первого элемента И и второму выходу блока, выход четвертого триггера подключен к третьему входу сумматора по модулю два и вторым входам третьего и четвертого элементов И, выходы второго, третьего и четвертого элементов И подключены соответственно к первому, второму и третьему входам элемента ИЛИ, выход которого подключен к третьему выходу блока, первый выход которого подключен к выходу сумматора по модулю два, синхровход блока подключен к синхровходам всех триггеров.

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

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

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

Описание изобретения к патенту

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

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

Недостатком этого устройства является низкое быстродействие за счет большой длительности тактового импульса, равной времени умножения и сложения двух m-разрядных чисел.

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

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

Цель изобретения - повышение быстродействия. Поставленная цель достигается тем, что устройство для умножения матрицы на вектор содержит n вычислительных модулей, где n - размерность матрицы, причем выход 6_j-го вычислительного модуля (j= ) подключен к первой группе информационных входов 6_{(j + 1)}-го вычислительного модуля, 1_j-й вход первой группы информационных входов устройства (j = ) подключен к информационному входу 4_j-го блока ввода первой группы, выход которого подключен ко второй группе информационных входов 6_j-го вычислительного модуля, 2_j-й вход второй группы информационных входов устройства (j = ) подключен к информационному входу 5_j-го блока ввода второй группы, выход которого подключен к третьей группе информационных входов 6_j-го вычислительного модуля, выход 6_n-го вычислительного модуля подключен к выходу 7 устройства, синхровход 3 которого подключен к синхровходам всех блоков ввода и вычислительных модулей, при этом каждый вычислительный модуль 6 содержит вычислительные блоки первого типа 14_ij-е (i = , j = ; i > j), где m - разрядность чисел, представленных в дополнительных кодах, вычислительные блоки второго типа 15_im-е (i = ), вычислительные блоки третьего типа 16_ij-e (i = , j = ; j > i), вычислительные блоки четвертого типа 17 _{i, m + 1}-e(i = ; q = 2m + log₂n - 1, знак обозначает округление в сторону большего целого), причем 8_i-й вход первой группы информационных входов (i = ) подключен к первому входу 17_{i, m + 1}-го вычислительного блока четвертого типа, 9_i-йвход второй группы информационных входов (i = ) вычислительного модуля 6 подключен к первому информационному входу 14_i,1-го вычислительного блока первого типа, первый выход 14_i,j-го вычислительного блока первого типа (i = , j = ; i j) подключен к первому информационному входу 14_{i+1, j+1}-го вычислительного блока первого типа, первый выход 14_i,m-1-го вычислительного блока первого типа (i = ) подключен к первому информационному входу 15_{i +1, m}-го вычислительного блока второго типа, 10₁-й и 11₁-й входы соответственно третьей и четвертой групп информационных входов вычислительного модуля 6 подключены соответственно ко второму и третьему информационным входам 14₁₁-го вычислительного блока 6, 10_j-й и 11_j-й входы соответственно третьей и четвертой групп информационных входов (j = ) вычислительного модуля 6 подключены соответственно ко второму и третьему информационным входам 16_1j-го вычислительного блока третьего типа, второй и третий выходы 14_i1-го вычислительного блока первого типа (i = ) подключены соответственно ко второму и третьему информационным входам 14_i+1-1-го вычислительного блока первого типа, второй и третий выходы 16_ij-го вычислительного блока третьего типа (i = , j = ; j-i 2) подключены соответственно ко второму и третьему информационным входам 16_{i+1, j}-го вычислительного блока третьего типа, второй и третий выходы 16_ij-го вычислительного блока третьего типа (i = , j = ; j-i = 1) подключены соответственно ко второму и третьему информационным входам 14_{i+1, j}-го вычислительного блока первого типа, второй и третий выходы 16_{m-1, m}-го вычислительного блока третьего типа подключены соответственно ко второму и третьему информационным входам 15_m,m-го вычислительного блока второго типа, второй и третий выходы 15_im-го вычислительного блока второго типа (i = ) подключены соответственно ко второму и третьему информационным входам 15_{i+1, m}-го вычислительного блока второго типа, второй и третий выходы 14_ij-го вычислительного блока первого типа (i = , j = ; i-j 0) подключены соответственно ко второму и третьему информационным входам 14_i+1,j-го вычислительного блока первого типа, 12_i-й вход пятой группы информационных входов i = ) вычислительного модуля 6 подключен к четвертому информационному входу 14_i,1-го вычислительного блока первого типа, а 12_i-й вход пятой группы информационных входов ( i = ) - ко второму информационному входу 17_{i, m+1}-го вычислительного блока четвертого типа, четвертый выход 14_ij-го вычислительного блока первого типа (i = , j = , i-j > 0) подключен к четвертому информационному входу 14_{i+1, j}-го вычислительного блока первого типа, четвертый выход 14₁₁-го вычислительного блока первого типа подключен к первому информационному входу 16₁₂-го вычислительного блока третьего типа, четвертый выход 14_ij-го вычислительного блока первого типа (i, j = ; i = j) подключен к первому информационному входу 16_{i+1, j}-го вычислительного блока третьего типа, четвертый выход 14_i,m-1-го вычислительного блока первого типа (i = ) подключен к четвертому информационному входу 15_i,m-го вычислительного модуля второго типа, первый выход 16_ij-го вычислительного блока третьего типа (i = , j = ; j > i) подключен к первому информационному входу 16_i,j+1-го вычислительного блока третьего типа, первый выход 16_im-го вычислительного блока третьего типа (i = ) подключен ко второму информационному входу 17_i,m+1-го вычислительного блока четвертого типа, четвертый информационный вход 15_i,m-го вычислительного блока второго типа (i = ) подключен ко второму информационному входу 17_i,m+1-го вычислительного блока четвертого типа, третий информационный вход 17_i,m+1-го вычислительного блока четвертого типа (i = ) подключен к первому выходу 17_i-1,m+1-го вычислительного блока четвертого типа, второй выход 17_i,m+1-го вычислительного блока четвертого типа (i = ) подключен к 18_i-му выходу четвертой группы выходов вычислительного модуля 6, синхровход которого подключен к синхровходам всех вычислительных блоков, при этом вычислительный блок 14 первого типа содержит первый 19, второй 20, третий 21 и четвертый 22 информационные входы, синхровход 23, триггеры 24-28, элемент сумма по модулю два 29, элементы И30 - 33, элемент ИЛИ 34, первый 35, второй 36, третий 37 и четвертый 38 выходы, причем первый 19, второй 20, третий 21 и четвертый 22 информационные входы подключены соответственно к информационным входам первого 24, второго 25, третьего 26 и четвертого 27 триггеров, выход первого триггера 24 подключен к первому входу первого элемента И30 и к информационному входу пятого 28 триггера, выход которогоподключен к первому выходу 35 вычислительного блока 14, выход первого элемента И30 подключен к первым входам элемента сумма по модулю два 29, первого 31 и второго 32 элементов И, выход второго триггера 25 подключен к первому входу третьего элемента И33 и ко вторым входам элемента сумма по модулю два 29 и второго элемента И31, выход третьего триггера 26 подключен ко второму входу первого элемента И30 и к третьему выходу 37 вычислительного блока 14, выход четвертого триггера 27 подключен к третьему входу элемента сумма по модулю два 29, ко вторым входам третьего 32 и четвертого 33 элементов И, выходы второго 31, третьего 32 и четвертого 33 элементов И подключены соответственно к первому, второму и третьему входам элемента ИЛИ 34, выход которого подключен ко второму выходу 36 вычислительного блока 14, четвертый выход 38 которого подключен к выходу элемента сумма по модулю два 29 синхровход 23 вычислительного блока 14 подключен к синхровходам всех триггеров, при этом вычислительный блок 15 второго типа содержит первый 39, второй 40, третий 41 и четвертый 42 информационные входы, синхровход 43, триггеры 44-47, элемент сумма по модулю два 48, элементы И 49-52, элемент ИЛИ 53, первый 54, второй 55 и третий 56 выходы, причем первый 39, второй 40, третий 41 и четвертый 42 информационные входы вычислительного блока 15 подключены соответственно к информационным входам первого 44, второго 45, третьего 46 и четвертого 47 триггеров, инверсный выход первого триггера 44 подключен к первому входу первого элемента И49, выход которого подключен к первым входам второго 50 и третьего 51 элементов И и элемента сумма по модулю два 48, выход второго триггера 45 подключен к первому входу четвертого элемента И52, выход третьего триггера 46 подключен ко второму входу первого элемента И49 и к третьему выходу 56 вычислительного блока 15, выход четвертого триггера 47 подключен ко вторым входам элемента сумма по модулю два 48 и третьего элемента И51, выходы второго 50, третьего 51 и четвертого 52 элементов И подключены соответственно к первому, второму и третьему входам элемента ИЛИ 53, выход которого подключен ко второму выходу 55 вычислительного блока 15, третий 56 и первый 54 выходы которого подключены соответственно к выходу третьего триггера 46 и элемента сумма по модулю два 48, синхровход 43 вычислительного блока 15 подключен к синхровходам всех триггеров, при этом вычислительный блок 16 третьеготипа содержит первый 57, второй 58 и третий 59 информационные входы, синхровход 60, триггеры 61-63, первый 64, второй 65, и третий 66 выходы, причем первый 57, второй 58 и третий 59 информационные входы вычислительного блока 16 подключены соответственно к информационным входам первого 61, второго 62 и третьего 63 триггеров, выходы которых подключены соответственно к первому 64, второму 65 и третьему 66 выходам вычислительного блока 16, синхровход 60 которого подключен к синхровходам всех триггеров, при этом вычислительный блок четвертого типа 17 содержит первый 67, второй 68 и третий 69 информационные входы, синхровход 70, триггеры 71-73, элемент сумма по модулю два 74, элементы И 75-77, элемент ИЛИ 78, первый 79 и второй 80 выходы, причем первый 67, второй 68 и третий 69 информационные входы подключены соответственно к информационным входам первого 71, второго 72 и третьего 73 триггеров, выход первого 71 триггера подключен к первым входам первого 75 и второго 76 элементов И и элемента сумма по модулю два 74, выход второго триггера подключен к первому входу третьего 77 элемента И и ко вторым входам второго элемента 76 И и элемента сумма по модулю два 74, выход третьего триггера 73 подключен ко вторым входам первого 75 и третьего 77 элементов И и к третьему входу элемента сумма по модулю два 74, выходы первого 75, второго 76 и третьего 77 элементов И подключены соответственно к первому, второму и третьему входам элемента ИЛИ 78, выход которого подключен к первому 79 выходу вычислительного блока 17, второй 80 выход которого подключен к выходу элемента сумма по модулю два 80, синхровход 70 вычислительного блока 17 подключен к синхровходам всех триггеров, при этом блок ввода содержит синхровход 81, информационные входы 82_i (i = ) элементы задержки 83_i (i = ) и выходы 84_i (i = ) причем первый 82₁ информационный вход подключен к 84₁-му выходу блока ввода, 82_i-й информационный вход (i = ) подключен ко входу 83_(i-1)-го элемента задержки на (i-1) тактов, выход которого подключен к 84_i-му выходу блока ввода, синхровход 81 которого подключен к синхровходам всех элементов задержки 83. На фиг. 1 представлена структурная схема устройства для умножения матрицы на вектор; на фиг. 2 - структурная схема устройства для умножения матрицы на вектор для m = n = 3; на фиг. 3 - схема вычислительного модуля; на фиг. 4 - схема вычислительного модуля для m = 3; на фиг. 5 - схемавычислительного блока первого типа; на фиг. 6 - схема вычислительного блока второго типа; на фиг. 7 - схема вычислительного блока третьего типа; на фиг. 8 - схема вычислительного блока четвертого типа; на фиг. 9 - схема блока ввода.

Устройство для умножения матрицы на вектор (см. фиг. 1) содержит первую 1 и вторую 2 группу информационных входов, синхровход 3, блоки ввода первой 4 и второй 5 групп, вычислительные модули 6, выход 7.

Вычислительный модуль 6 (см. фиг. 3) содержит первую 8, вторую 9, третью 11, четвертую 10 и пятую 12 группы информационных входов, синхровход 13, вычислительные блоки первого типа 14_ij (i = , j = ; i j), вычислительные блоки второго типа 15_im (i = ), вычислительные блоки третьего типа 16_ij (i = , j = ; j > i); вычислительные блоки четвертого типа 17_i,m+1 (i = ) и выходы 18.

Вычислительный блок 14 первого типа (см. фиг. 5) содержит первый 19, второй 20, третий 21 и четвертый 22 информационные входы, синхровход 23, триггеры 24-28, элемент сумма по модулю два 29, элементы И 30-33, элемент ИЛИ 34, первый 35, второй 36, третий 37 и четвертый 38 выходы.

Вычислительный блок 15 второго типа (см. фиг. 6) содержит первый 39, второй 40, третий 41 и четвертый 42 информационные входы, синхровход 43, триггеры 44-47, элемент сумма по модулю два 48, элементы И 49-52, элемент ИЛИ 53, первый 54, второй 55 и третий 56 выходы.

Вычислительный блок 16 третьего типа (см. фиг. 7) содержит первый 57, второй 58 и третий 59 информационные входы, синхровход 60, триггеры 61-63, первый 64, второй 65 и третий 66 выходы.

Вычислительный блок 17 четвертого типа (см. фиг. 8) содержит первый 67, второй 68 и третий 69 информационные входы, синхровход 70, триггеры 71-73, элемент сумма по модулю два 74, элементы И 75-77, элемент ИЛИ 78, первый 79 и второй 80 выходы.

Блок ввода 4 или 5 (см. фиг. 9) содержит синхровход 81, информационные входы 82_i (i = ), элементы задержки 83_i (i = ) на i тактов и выходы 84_i (i = ).

Вычислительный блок первого типа 14 (см. фиг. 5) обладает возможностью реализации функций

x^j+2 = x^j,

c^j+1 = c^jy^j V c^ja^jx^j V y^ja^jx^j,

a^j+1 = a^j,

y^j+1 = c^j y^j a^jx^j, где x^j, c^j, a^j и y^j - значения соответственно на первом 19, втором 20, третьем 21 и четвертом 22 информационных входах вычислительного блока 14 на j-м такте, x^j+2, c^j+1, a^j+1 и y^j+1 - значения соответственно на первом 35, втором 36, третьем 37 и четвертом 38 выходах вычислительного блока 14 на j+2 (j+1)-м такте.

Вычислительный блок второго типа 15 (см. фиг. 6) обладает возможностью реализации функций

a^j+1 = a^j,

c^j+1 = c^jy^j V c^ja V y^ja,

y^j+1 = c^j y^j a, где x^j, c^j, a^j и y^j - значения соответственно на первом 39, втором 40, третьем 41 и четвертом 42 информационных входах вычислительного блока 15 на j-м такте, y^j+1, c^j+1 и a^j+1 - значения соответственно на первом 54, втором 55 и третьем 56 выходах вычислительного блока 15 на (j+1)-м такте.

Вычислительный блок третьего типа 16 (см. фиг. 7) обладает возможностью реализации функций

y^j+1 = y^j,

x^j+1 = c^j,

aj⁺¹ = a^j, где y^j, c^j и a^j - значения соответственно на первом 57, втором 58 и третьем 59 информационных входах вычислительного блока 16 на j-м такте, y^j+1, c^j+1 и a^j+1 - значения соответственно на первом 64, втором 65 и третьем 66 выходах вычислительного блока 16 на (j+1)-м такте.

Вычислительный блок четвертого типа 17 (см. фиг. 8) обладает возможностью реализации функций

c^j+1 = y^jc^j V y^jg^j V g^jc^j,

y^j+1 = y^j g^j c^j,

где y^j, g^j и c^j - значения соответственно на первом 67, втором 68 и третьем 69 информационных входах вычислительного блока 17 на j-м такте,

y^j+1 и c^j+1 - значения соответственно на первом 79 и втором 80 выходах вычислительного блока 17 на (j+1)-м такте.

Рассмотрим работу блока ввода (см. фиг. 9).

Входной элемент x подается одновременно всеми разрядами на t-м такте на входы 82. В обозначении x_(i)^t индекс t указывает номер такта, индекс i в скобах - номер разряда элемента x, индекс без скобок - номер элемента x. Элемент задержки 83_i-й задерживает разряды x_(i)-e на i тактов, т. е. на 84_i-й выход подается i-й разряд элемента x на (t+1)-м такте. С выхода 84 блока ввода элемент x_j подается на соответствующий вход 6_j-го вычислительного модуля.

Рассмотрим работу вычислительного модуля 6 (см. фиг. 3).

Вычислительный модуль 6 выполняет операцию вида y" = ax+y, где a, x, y, y" - числа, представленные в дополнительном коде. На входы 8_i-й (i = ) подается (i-1)-й разряд числа y на (i-1)-м такте. На вход 9_i-й (i = ) подается (i-1)-й разряд числа x на (i-1)-м такте. На входы 10_j-e (j = ) постоянно подаются нулевые значения, а на вход 10_m-й-(m-1)-й разряд числа a на (m-1)-м такте. На вход 11_j-й (j = ) подается (j-1)-й разряд числа a на (j-1)-м такте. На входы 12_i-e (j = ) постоянно подаются нулевые значения. При этом, в соответствии с выполняемыми функциями вычислительных блоков 14, 15, 16, и 17, на 18_i-x (i = ) выходах вычислительного модуля 6 формируется операция y" = ax + y в виде следующих рекуррентных соотношений:

y_-1j = 0, j = , q = 2m +log₂n - 1;

c_i,i-1 = 0, i = ;

c_{m-1, m-2} = a_m-1;

x_j = x_m-1, j m-1.

i = , j = ;

y_ij = y_i-1, j V c_i,j-1 V a_ix_j-i,

c_ij = y_i-1,j c_ij-1 V y_i-1,j a_ix_j-i V c_i,j-1 a_jx_j-i;

j = ;

y_m-1,j = y_m-2,j c_{m-1, j} a_m-1 x_j-m+1,

c_m-1,j = y_m-2,j c_m-1,j V y_m-2,j a_m-1 V

V c_m-1,j a_m-1 ;

i = , j = ;

y_ij = y_i,j-1;

i = , j = ;

y_ij = y_i,j-1.

g_j = y_m-1,j, j = 1.

y_j" = g_j + y_j, j = .

На 18_i-м выходе формируется (i-1)-й разряд операции y" = ax + y на (m+i)-м такте. Последний (q-1)-й разряд формируется на (m+q)-м такте. На фиг. 4 для m = 3 приведена организация подачи разрядов чисел a и x соответственно на входах 11 и 9, на выходе 18 - разряды результата y". Таким образом, на первых выходах вычислительных блоков 16_im-x (i = ) и 15_im-x (i = ) формируется произведение ax, а на выходах 18_i-x - результат y" = ax+y. В табл. 1 приведены значения на входах и выходах при формировании произведения ax, а в табл. 2 - при формировании результата y".

В основу работы устройства для умножения матрицы A = { a_ij} , i, j = на вектор x = { x-j} , j = положены рекуррентные соотношения

y_i,o = 0, i = ;

y_ij = y_i,j-1 + a_ij x_j, i, j = ;

y_i = y_i,n, i = .

Элементы x_j^t и a_ij^t подаются на входы соответственно 4_j-го и 5_j-го блоков ввода (j = ) с выхода которых данные элементы подаются на соответствующие входы 6_j-го вычислительного модуля. Причем блоки вводов 4 и 5 осуществляют задержку i-го разряда элементов x и a на (i-1) тактов, т. е. i-й разряд этих элементов выдается на (t+i-1)-м такте. Длительность тактового импульса t_ти, подаваемого на синхровход 3, равна

t_ти = t_тр + 2t_и + t_или, где t_тр - время записи в триггер;

t_и - задержка элемента И;

t_или - задержка элемента ИЛИ.

На выходе 7 устройства i-й разряд элемента y_j-го формируется на (m+n+i+j-1)-м такте.

Рассмотрим работу устройства при формировании элемента y₁результирующей матрицы Y для случая m = n = 3 (см. фиг. 2). На входы 1_jи 2_j (j = 1,3) подаются соответственно элементы x_j и a_ij, причем i-e разряды данных элементов подаются на входы вычислительных модулей 6 на (t+i-1)-м такте. На выходе вычислительного модуля 6₁ формируется младший разряд y₁ на m-м такте, а старший разряд y₁ - на (m+q-1)-м такте. На выходе вычислительного модуля 6₂ формируется младший разряд y₁ на (m+1)-м такте, а старший разряд y₁ - на (m+q)-м такте. На выходе вычислительного модуля 6₃ формируется младший разряд y₁ на (m+n-1)-м такте, а старший разряд y₁ - на (m+n+q-2)-м такте, т. е. младший разряд y₁ формируется на 5-м такте, а старший разряд y₁ - на 12-м такте. Аналогичным образом формируются элементы y₂ и y₃ (младшие разряды элементов y₂ и y₃ формируются соответственно на 6-м и 7-м такте, а старшие - на 13-м и 14-м тактах).

Полное время умножения (n x n) - матрицы на вектор равно (m+2n+q-1) тактов.

Таким образом,

предлагаемое устройство обладает более высоким быстродействием по сравнению с прототипом. Прототип реализует умножение (n x n)-матрицы на вектор за (2n-1) тактов, причем длительность тактового импульса равна времени умножения и сложения двух m-разрядных чисел. Например, для m = 32 и длительности тактового импульса 100 нс время умножения матрицы размерностью n = 100 на вектор составляет 20 мкс. Предлагаемое устройство выполняет данную задачу при меньшей длительности тактового импульса t_ти = t_тр + 2t_и + t_или 10 нс за 2,94 мкс (выигрыш во времени составляет 7 раз). (56) Kung H. T. Leiseerson C. E. Systohic Arrays (for VLSI)-Sparse Matrix Proc. 1978, Society for Industrial and Applied Mathematicf, 1979, p. 262, fig 3-2.

Авторское свидетельство СССР N 1517039, кл. G 06 F 15/347, 1989.