устройство для обращения n x n матриц
Классы МПК: | G06F17/16 матричные или векторные вычисления |
Автор(ы): | Якуш В.П., Косьянчук В.В., Лиходед Н.А., Соболевский П.И. |
Патентообладатель(и): | Якуш Виктор Павлович |
Приоритеты: |
подача заявки:
1990-05-23 публикация патента:
09.06.1995 |
Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для обращения n n-матриц. Цель изобретения - сокращение аппаратурных затрат. Цель достигается тем, что устройство содержит фиксированное число m вычислительных модулей, где m < n, причем каждый вычислительный модуль содержит три триггера, три параллельных регистра, пять сдвигающих регистров, умножитель, вычитатель, узел вычисления обратной величины числа, два элемента НЕ, пять элементов И, десять блоков элементов И и четыре блока элементов ИЛИ. 2 ил.
Формула изобретения
УСТРОЙСТВО ДЛЯ ОБРАЩЕНИЯ N X N МАТРИЦ, содержащее m вычислительных модулей, где m целое число, m < n, n порядок матрицы, причем первый - четвертый выходы i-го вычислительного модуля, где i 1, m-1, подключены соответственно к информационному входу, к первому третьему входам режима (i + 1)-го вычислительного модуля, первый выход m-го вычислительного модуля подключен к выходу результата устройства, синхровход которого подключен к синхровходам всех вычислительных модулей, отличающееся тем, что, с целью сокращения аппаратурных затрат, оно содержит узел сдвигающих регистров, три сдвигающих регистра, блок элементов И, блок элементов ИЛИ, три элемента И и три элемента ИЛИ, причем информационный вход устройства подключен к первому входу блока элементов ИЛИ, второй вход и выход которого подключены соответственно к выходу блока элементов И и к информационному входу первого вычислительного модуля, первый третий входы режима устройства подключены соответственно к первым входам первого третьего элементов ИЛИ, выходы которых подключены соответственно к первому третьему входам режима первого вычислительного модуля, первый выход m-го вычислительного модуля подключен к информационному входу узла сдвигающих регистров, выход переноса узла сдвигающих регистров подключен к первому входу блока элементов И, четвертый вход режима устройства к второму входу блока элементов И и к первым входам первого третьего элементов И, второй четвертый выходы m-го вычислительного модуля подключены соответственно к информационным входам первого третьего сдвигающих регистров, выходы переноса которых подключены соответственно к информационным входам первого третьего сдвигающих регистров, выходы переноса которых подключены соответственно к вторым входам первого третьего элементов И, выходы которых подключены соответственно к вторым входам первого третьего элементов ИЛИ, синхровход устройства подключен к входам сдвига всех сдвигающих регистров и узла сдвигающих регистров, причем каждый вычислительный модуль содержит три триггера, пять сдвигающих регистров, умножитель, вычитатель, три регистра, узел вычисления обратной величины, два элемента НЕ, десять блоков элементов И и четыре блока элементов ИЛИ, причем в каждом вычислительном модуле информационный вход вычислительного модуля подключен к первым входам первого и второго блоков элементов И, выходы которых подключены соответственно к первому входу первого блока элементов ИЛИ и к информационному входу первого регистра, выход которого подключен к первым входам третьего и четвертого блоков элементов И и к первому информационному входу вычитателя, выход которого подключен к первому входу пятого блока элементов И, выход которого подключен к первому входу второго блока элементов ИЛИ, выход которого подключен к первому выходу устройства, первый вход режима которого подключен к первому входу первого элемента И и к информационному входу первого триггера, прямой выход которого подключен к информационному входу первого сдвигающего регистра и к первому входу второго элемента И, выход которого подключен к первым входам третьего и шестого блоков элементов И и к второму входу чертвертого блока элементов И, выход которого подключен к первому входу третьего блока элементов ИЛИ, выход которого подключен к первому информационному входу умножителя, выход которого подключен к второму информационному входу вычитателя и к информационному входу второго регистра, выход которого подключен к первым входам седьмого и восьмого блоков элементов И, выход последнего подключен к второму входу третьего блока элементов ИЛИ, выход первого элемента И подключен к второму входу первого блока элементов И и входу первого элемента НЕ, выход которого подключен к первому входу девятого блока элементов И, выход которого подключен к второму входу первого блока элементов ИЛИ, выход которого подключен к информационному входу третьего регистра, выход которого подключен к входу узла вычисления обратной величины, к информационному входу второго сдвигающего регистра и к первому входу десятого блока элементов И, выход которого подключен к первому входу четвертого блока элементов ИЛИ, выход которого подключен к второму информационному входу умножителя, выход третьего элемента И подключен к входу записи/считывания второго регистра, выходы переноса первого и второго сдвигающих регистров подключены соответственно к второму выходу устройства и второму входу девятого блока элементов И, выход узла вычисления обратной величины подключен к второму входу шестого блока элементов И, выход которого подключен к второму входу четвертого блока элементов ИЛИ, второй вход режима устройства подключен к информационному входу второго триггера, к второму входу первого элемента И и входу второго элемента НЕ, выход которого подключен к второму входу второго блока элементов И, прямой выход второго триггера подключен к информационному входу третьего сдвигающего регистра и к первому входу третьего элемента И, выход которого подключен к второму входу седьмого блока элементов И, выход которого подключен к второму входу второго блока элементов ИЛИ, выход переноса третьего сдвигающего регистра подключен к третьему выходу устройства, третий вход режима которого подключен к информационному входу третьего триггера, прямой выход которого подключен к информационному входу четвертого сдвигающего регистра и второму входу третьего блока элементов И, выход которого подключен к информационному входу четвертого сдвигающего регистра, выход переноса которого подключен к третьему входу второго блока элементов ИЛИ, инверсный выход первого триггера подключен к второму входу третьего элемента И и к первому входу четвертого элемента И, выход которого подключен к вторым входам пятого, восьмого и десятого блоков элементов И, инверсный выход второго триггера подключен к вторым входам второго и четвертого элементов И, выход переноса четвертого сдвигающего регистра подключен к четвертому выходу устройства, синхровход которого подключен к входам сдвига всех сдвигающих регистров, к второму входу третьего элемента И, к входам записи/считывания первого и третьего регистров.Описание изобретения к патенту
Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для обращения (n x n)-матриц. На фиг. 1 представлена структурная схема устройства для обращения (n x n)-матриц; на фиг. 2 схема вычислительного модуля. Устройство для обращения (n x n)-матриц (фиг. 1) содержит информационный вход 1, первый 2, второй 3, третий 4 и четвертый 5 входы режима, синхровход 6, вычислительные блоки 7i (i ), узел сдвигающих регистров 8i (i ), первый 9, второй 10 и третий 11 сдвигающие регистры, блок 12 элементов И, блок 13 элементов ИЛИ, первый 14, второй 15 и третий 16 элементы И, первый 17, второй 18 и третий 19 элементы ИЛИ и выход 20. Вычислительный модуль 7 (фиг. 2) содержит информационный вход 21, первый 22, второй 23 и третий 24 входы режима, синхровход 25, регистры 26, 27 и 28, узлы 29 и 31 задержки, регистры 30i (i ) и 32i (i ) узлов задержки, умножитель 33, вычитатель 34, узел 35 вычисления обратной величины числа, триггеры 36, 37 и 38, сдвигающие регистры 39, 40 и 41, триггеры 42i (i ), 43i (i ) и 44i (i ) сдвигающих регистров, блоки 45-54 элементов И, блоки 55-58 элементов ИЛИ, элементы И 59-63, элементы НЕ 64 и 65, первый 66 и второй 67, третий 68 и четвертый 69 выходы. В основу работы устройства положен метод Гаусса-Жордана, который представляется следующими рекуpрентными соотношениями:B A-1;
a(0ij) aij, i,j
a(i-1)i,n+i 1, a(i-1)i+j,n+i 0, i , j
k
akk(k) 1/akk(k-1)
a(kik) a(kik-1), i
a(kkj) a(kkj-1)a(kkk), j
a(kij) a(kij-1)-a(kik)a(kkj), i
a(k)k+n,j a(kkj), j
bij an+i,n+j(n).
Вычислительный модуль обладает возможностью выполнения функций вида
Uj+n+3 j;
Vj+n+3 j;
Wj+n+3 j, где j, j и j значения на первом, втором и третьем входах режима вычислительного модуля на j-м такте
Uj, Vj и Wj значения на втором, третьем и четвертом выходах вычислительного модуля на j-м такте,
Fj+1
Fj+n+2 aj, если ( j j j) (1,0,1)v(0,0,1), где aj значение на информационном входе вычислительного модуля на j-м такте;
bj+1 aj/aj-z при ( j j j) (1,0,0) v (1,0,1);
сj+1 aj при (j j j) (1,1,0);
P
z n + 1;
Fj значение на выходе вычислительного модуля на j-м такте. Вычислительный модуль работает в шести режимах. В первом режиме на входы 2, 3 и 4 подаются соответственно управляющие сигналы ( ) (1,1,0). При этом триггеры 36, 37 и 38 устанавливаются соответственно в состояния "1", "1" и "0", на выходе элемента И 59 формируется единичный сигнал, который открывает блок 45 элементов И. Элемент а, подаваемый на вход 21, через блок 45 элементов И и блок 55 элементов ИЛИ по заднему фронту тактового импульса записывается в регистр 28. Содержимое регистра 30i (i ) переписывается в регистр 30i+1. Управляющие сигналы ( ) выдаются соответственно на выходы 67, 68 и 69 с задержкой на n + 3 тактов. Во втором режиме подаются управляющие сигналы ( ) (1,0,0). При этом на выходе элементов И 61 и НЕ 64, 65 формируется единичный сигнал, открываются блоки 46, 47, 48, 50 элементов И и элемент И 63. Элемент akj(k-1) , подаваемый на вход 21, через блок элементов 46 И по заднему фронту тактового импульса записывается в регистр 26. Содержимое регистра 30i (i=1,n-1 ) переписывается в регистр 30i+1, а содержимое аkk(k-1) регистра 30n в регистр 301 через блок 47 элементов И и блок 55 элементов ИЛИ. На входе узла 35 вычисления обратной величины числа формируется значение akk(k) 1/akk(k-1), которое подается на первый вход умножителя 33 через блок 50 элементов И и блок 57 элементов ИЛИ, на второй вход умножителя 33 подается с выхода регистра 26 элемент аkj(k-1) через блок 48 элементов И и блок 56 элементов ИЛИ. На выходе умножителя 33 формируется значение аkj(k) akj(k-1) akk(k), которое записывается на следующем такте по переднему фронту тактового импульса в регистр 27 (регистр 27 построен на однотактовых триггерах). В третьем режиме подаются управляющие сигналы ( ) (0,0,0). На выходе элемента И 60 и элементов НЕ 64, 65 формируется единичный сигнал, открываются блоки 46, 47, 49, 51 и 52 элементов И. На вход 21 подается элемент aij(k-1) и записывается в регистр 26. В регистре 27 хранится элемент akj(k). В регистрах 28 и 30i (i 1,n ) происходит циклическая перезапись (в регистр 28 записывается элемент аik(k). На первый вход умножителя 33 подается элемент aik(k) с выхода регистра 28 через блок 51 элементов И и блок 57 элементов ИЛИ. На второй вход умножителя 33 подается элемент аkj(k) с выхода регистра 27 через блок 49 элементов И и блок 56 элементов ИЛИ. На выходе умножителя 33 формируется значение аik(k) akj(k), которое подается на первый вход вычитателя 34, на второй вход которого подается значение аij(k-1) с выхода регистра 26. На выходе вычитателя 34 формируется значение aij(k)= aij(k-1) aik(k) akj(k), которое через блок 52 элементов И и блок 58 элементов ИЛИ выдается на выход 66. В четвертом режиме подаются управляющие сигналы ( ) (0,1,0). При этом в регистрах 28 и 30i (i ) информация циклически переписывается (блок 47 элементов И открыт). Содержимое akj(k) регистра 27 через открытый блок 53 элементов И (на выходе элемента И 62 единичный сигнал) и блок 58 элементов ИЛИ выдается на выход 66. В пятом режиме подаются управляющие сигналы ( ) (1,0,1). На вход 21 подается число, равное единице и записывается регистр 26 (блок 46 элементов И открыт). В регистрах 28 и 30i (i 1,n ) информация циклически перезаписывается (блок 47 элементов И открыт). В регистр 28 записывается элемент аkk(k-1), с выхода которого подается на узел 35 вычисления обратной величины числа. Значение аk,k+n(k) 1/akk(k-1) с выхода узла 35 вычисления обратной величины числа через открытый блок 50 элементов И (на выходе элемента И 61 единичный сигнал) и блок 57 элементов ИЛИ подается на первый вход умножителя 33, на второй вход которого подается единица с выхода регистра 26 через открытый блок 48 элементов И и блок 56 элементов ИЛИ. На выходе умножителя 33 формируется значение аk,k+n(k) 1/akk(k-1), которое записывается в регистр 27 на следующем такте (элемент И 63 открыт, что обеспечивает прохождение тактового импульса на вход синхронизации регистра 27). С выхода регистра 26 единица на следующем такте записывается в регистр 321 (блок 54 элементов И открыт). В шестом режиме подаются управляющие сигналы ( ) (0,0,1). Нулевое число подается на вход 21 и записывается в регистр 26. На первый и второй входы умножителя 33 подаются соответственно элемент aik(k) с выхода регистра 28 и элемент аk,k+n(k) с выхода регистра 27. На выходе умножителя 33 формируется значение аik(k) ak,k+n(k), которое подается на первый вход вычитателя 34, на второй вход которого подается нулевое значение с выхода регистра 26. На выходе вычитателя 34 формируется значение аik(k) ak,k+n(k), которое подается на выход 66. Работает устройство следующим образом. На вход 1 подаются элементы aij в моменты времени
t= i + (n + 1)j n 2. Кроме того, на вход 1 подается единичное значение на n(n + 1)-м такте, а нулевые значения подаются с [n(n + 1) + 1]-го такта по [(n + 1)n + n 1]-й такт. На управляющие входы 2, 3 и 4 подаются соответственно управляющие сигналы
( ) (1,1,0) с 0-го такта по n-й такт;
( ) (1,0,0) на (n + 1)-м такте;
( ) (0,0,0) с (n + 2)-го такта на 2n-й такт. Эта группа из n управляющих сигналов (1,0,0) и (0,0,0) повторяется еще n- 2 раза:
( ) (1,0,1) на n(n + 1)-м такте;
( ) (0,0,1) с [n(n + 1) + 1]-го такта по [(n + 1)2 1]-й такт. Элемент обратной к А матрицы bij выдается на выходе 20 в моменты времени
t= (n/m 1)(n + 1)2 + (m 1)(n + 3) + i + (n + 1)j. Период ввода элементов матриц очередной задачи обращения в поточном режиме составляет (n/m)(n + 1)2 тактов. Для обеспечения поточного режима при обращения L матриц на вход 5 подается управляющий сигнал равный нулю в моменты времени t = 0 (l 1)z + i, где z (n + 1); i 1,(n+1)2 l 1,L номер обращенной матрицы, равный единице в моменты времени
t = 1= (l 1)z + (n + 1)2 + i, i 1,(n+1)2(n/m-1). При 0 блок 12 элементов И и элементы И 14, 15 и 16 закрыты, элементы аij, подаваемые на вход 1, через блок 13 элементов ИЛИ подаются на информационный вход вычислительного модуля 71. При 1 блок 12 элементов И и элементы И 14, 15 и 16 открыты, на инфоpмационный вход вычислительного модуля 71 подаются элементы аij с выхода регистра 8p через блок 12 элементов И и блок 13 элементов ИЛИ. Управляющие сигналы и подаются на настроечные входы вычислительного модуля 71 соответственно с выходов сдвигающих регистров 9, 10 и 11 через соответствующие элементы И 14, 15 и 16 и элементы ИЛИ 17, 18 и 19. Таким образом исключается искажение информации по цепи обратной связи.
Класс G06F17/16 матричные или векторные вычисления