Устройство для выполнения операций над матрицами Советский патент 1992 года по МПК G06F15/347 

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

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

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

Наиболее близким к предлагаемому по технической сущности является устройство для решения матричного уравнения вида Ах В, содержащее связанные соответствующим образом п вычислительных блоков первого типа и n(n-1)/2+n т вычислительных

блоков второго типа (где п и г- размерности матриц).

Недостатком этого устройства являются его ограниченные функциональные возможности.

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

На фиг. 1 изображена структурная схема устройства для случая, когда п 3. г 2 на фиг. 2 - структурная схема вычислительного блока (ВБ) первого типа; на фиг. 3 - структурная схема ВБ второго типа.

Устройство для выполнения операций над матрицами содержит (фиг. 1) вычисли- тельные блоки l.i.i первого типа и 2.J.J ( j i-1, n-i-r) второго типа, причем вход режима ВБ 1 1 1 соединен с входом запуска уст- ройства.лервый выход режима ВБ t.i.j (где i j 1, п-1) соединен с выходом режима ВБ 1-(i+1) ) второй выход режима ВБ Lab

Ч

Јь

СЛ 00

(где а b 1, п) соединен с входом режима ВБ 1.а.(Ь+1), выход режима ВБ 1 .c(d+k) (где с d 1, n; , n+r - с-1) соединен с входом режима ВБ 1.c(d+k+1), информационный вход ВБ 1.1.1 подключен к первому инфор- мационному входу устройства, информаци- онный вход ВБ 1.1.ji (где ji 2, n+n) подключен к ji-му информационному входу устройства, выход результата ВБ 1.1, j+1 (где i j, n-1) соединен с информационным вхо- дом ВБ 1.(i+1). (j+1). выход результата ВБ 1 .n.(n+ki) (где ki 1, г) соединен с ki-м выходом результата устройства, выход результата ВБ 1.1.(+к2)(где i j 1, n-1; K2 2, n+r-i) соединен с информационным входом ВБ 1.(i+1).(i+k2). С целью расширения функциональных возможностей устройства за счет реализации им алгоритма Фаддеева выход признака перестановки и выход деления ВБ 1.а.Ь (где а b 1, п) соединены с входом признака перестановки и входом деления ВБ 1.а.(Ь+1), выход признака перестановки и выход деления (с. d+k)-ro В Б 1 .c.(d+k) (где c d 1,, n+r-c-1) соединены с входами признака перестановки и деления ВБ 1.c.(d+k+1).

Вычислительный блок первого типа (фиг. 2) содержит первый 3 и второй 4 элементы задержки, RS-триггер 5, счетчик 6, регистр 7, третий элемент 8 задержки, эле- мент ИЛИ 9, схему 10 сравнения, первый 11 и второй 12 коммутаторы, четвертый элемент 13 задержки, блок 14 деления, блок 15 элементов задержки, элемент И 16, пятый 17 и шестой 18 элементы задержки. Вход режима вычислительного блока первого типа соединен с входом разрешения счетчика 6, входом установки в 1 триггера 5 и входом элемента 4 задержки, выход которого соединен с первым входом элемента ИЛИ 9. Выход счетчика 6 соединен с входом установки в О триггера 5, входом элемента 3 задержки и входом записи регистра. Выход элемента 8 задержки соединен с первым выходом режима В Б. выход элемента 3 за- держки соединен с входом элемента 8 задержки и вторым выходом режима ВБ. Выход триггера 5 соединен с первым входом элемента И 16, второй вход которого соединен с выходом элемента ИЛИ 9. Вы- ход элемента И 16 соединен с входом элемента 17 задержки и входами разрешения первого и второго коммутаторов. Выход элемента 17 задержки соединен с выходом признака перестановки ВБ, информацией- ный вход ВБ подключен к первым информационным входам схемы 10 сравнения, первого 11 и второго 12 коммутаторов, выход схемы 10 сравнения подключен к второму входу элемента ИЛИ 9. Информационный выход коммутатора 11 соединен с входом блока 15 элементов задержки, выход которого соединен с первым информационным входом блока 14 деления, информационный выход которого соединен с входом шестого элемента 18 задержки, выход которого соединен с выходом деления процессорного блока. Второй информационный вход блока 14 деления соединен с информационным выходом регистра 7, информационный вход которого соединен с информационным выходом коммутатора 12 и входом элемента 13 задержки, выход которого соединен с вторыми информационными входами схемы 10 сравнения, первого 11 и второго 12 коммутаторов, информационный вход счетчика 6 соединен с входом константы устройства.

Вычислительный блок второго типа (фиг. 3) содержит первый элемент 19 задержки, первый 20 и второй 21 коммутаторы, второй элемент 22 задержки, регистр 23, третий элемент 24 задержки, блок 25 элементов задержки, сумматор 26. блок 27 умножения, четвертый 28 и пятый 29 элементы задержки. Вход режима В Б соединен с входом элемента 24 задержки и входом записи регистра 23, информационный выход которого соединен с входом первого сомножителя блока 27 умножения, вход второго сомножителя которого соединен с входом элемента 28 задержки и входом деления ВБ. Выход элемента задержки подключен к выходу деления ВБ, вход признака перестановки которого соединен с входом элемента

19задержки и входами разрешения первого

20и второго 21 коммутаторов Выход элемента 19 задержки подключен к выходу признака перестановки ВБ, информационный вход которого подключен к первым информационным входам первого 20 и второго 21 коммутаторов. Информационный выход коммутатора 20 соединен с входом блока 25 элементов задержки, выход которого соединен с входом первого слагаемого сумматора 26 информационный выход которого соединен с элементом 29 задержки, выход которого соединен с выходом результата В Б Выход блока 27 умножения соединен с входом второго слагаемого сумматора 26, информационный выход коммутатора 21 соединен с информационным входом регистра 23 и входом элемента 22 задержки, выход которого соединен с вторыми информационными входами коммутаторов 20 и 21. Выход элемента 24 задержки подключен к выходу режима В Б.

Устройство для выполнения операций над матрицами предназначено для вычисления с помощью алгоритма Фаддеева выра -1г

жения вида X СА B+D , где а общем случае {aij}; Bfnxr {bik}; {cej} и {йек} - матрицы, представленные в виде объединенной матрицы:

В

-С

D

причем суть алгоритма сводится к тому, что после обнуления в объединенной матрице нижнего левого квадранта (т.е. элементов матрицы -С), в правом нижнем квадранте (на месте матрицы D) получаем искомый результат . Фактически это выражение позволяет решать дополнительно еще не- сколько задач.

1.Решение системы линейных алгебраических уравнений с несколькими (или одной, в зависимости от размерности В) правыми частями

Х при С 1, D 0.

2.Обращение матрицы

Х при С В 1, 0 0.

3.Умножение матриц (или матрицы на вектор, в зависимости от размерности В)

при А 1, 0 0.

4.Умножение со сложением матриц Х СВ + О при А 1.

5.Задача адаптивной фильтрации, которая использует выражение

Х + D при В 1, где 1 - единичная матрица.

Обнуление нижнего левого квадранта объединенной матрицы можно осуществить, применяя к ней QR-разложение или, как реализовано в предлагаемом устройстве, искл-ючение Гаусса до приведения матрицы А к верхнему треугольному виду. Тогда автоматически на месте матрицы -С получается нулевая матрица. При этом с целью обеспечения численной устойчивости вычислений преобразование матрицы А выполняется по алгоритму исключения Гаусса с частичным выбором ведущего элемента пр столбцу. Это означает, что на i-м шаге (i 1, п-1) алгоритма.Гаусса исключению элементов aji (j i+1, n), принадлежащих исходной матрице А А (при i 1) или уже частично преобразованной матрице А (при i 1), предшествует последовательное сравнение их с элементом аи и, если очередной элемент laji l laii I, осуществляется перестановка j-й и i-й строк, г.е. i-я строка ставится j-й и наоборот. В противном случае перестановки строк не происходит. Только по окон- чании всех (на данном шаге) операций сравнения и перестановок (т.е. процесса выбора ведущего элемента) начинается процесс исключения элементов а/ и преобразования строк с (1+1)-й по n-ю матрицы А1

(в нашем случае еще и В ), заключающийся в попарном суммировании каждой из этих строк с i-й строкой матрицы А1 (объединенной матрицы в нашем случае), предварительно умноженной на коэффициент rriji -aji /ah . Однако поскольку в объединенной матрице под матрицей А находится матрица -С, которую необходимо привести к нулевой матрице, никаких перестановок строк матриц С и О со строками матриц А и В производить нельзя. Вследствие этого устройство осуществляет выбор ведущего элемента среди элементов 1-го столбца матрицы А (на i-м шаге), а процесс исключения осуществляется среди элементов 1-го столбца матриц А и С1, т.е. среди элементов Ьго столбца всей объединенной матрицы (i 1, п-1). Все признаки перестановки строк запоминаются и передаются между В Б в качестве элементов нижней треугольной матрицы перестановок V Vji. За (п-1)-й шаг алгоритма Гаусса обнуляются (п-1) столбцов объединенной матрицы. Однако для получения правильного результата необходимо обнулить также n-й столбец матрицы -С. Поэтому в данном случае алгоритм Гаусса имееттакже n-й шаг на котором отсутствует процесс выбора ведущего элемента (элемент апппсоазу становится ведущим, так как его не с чем сравнить), а процесс исключения производится аналогично предыдущим шагам алгоритма.

Поступпение исходных данных организовано следующим образом. На i-й .информационный вход устройства (i 1, п) в каждый такт поступает элемент i-ro столбца объединенной матрицы, начиная с элемента aii и заканчивая -cpi. на (п+к)-й информационный вход устройства (k 1, г) - аналогично, начиная с элемента bik и заканчивая dpk. В свою очередь элементы каждого столбца объединенной матрицы поступают на соответствующие входы устройства со сдвигом на один такт. т.е. элемент aii поступает на i-й информационный вход устройства в I-M такте его работы, а элемент bik - в (n+k)-M такте работы устройства.

Устройство работает следующим образом.

Для простоты описания и без потери общности положим п - 3, р г 2. Условимся что прием информации во все счетчики триггеры и элементы 3, 4, 8 и 24 задержки всех В Б происходит по переднему фронту синхроимпульса, т.е. вначале такта, а во все регистры, блоки элементов задержки и остальные элементы задержки - по заднему фронту синхроимпульса.

В первом такте на вход запуска устройства поступает единичный импульс, который записывается вэлемент4.1.1 задержки, а также поступает на вход разрешения счетчика 6.1.1 и на вход установки триггера 5.1.1, который устанавливается в единицу, которая поступает на первый вход элемента И 16.1.1, с выхода которого единица поступает на управляющие входы коммутаторов 12.1.1 и 11.1.1 и записывается в элемент 17.1,1 задержки, Кроме того, в счетчик 6.1.1 записывается значение (п-1) 2 в двоичном коде, на его выходе нулевого состояния находится нуль. На информационный вход ВБ 1.1.1-поступает an an1 и, пройдя через первый вход второго коммутатора 12.1.1, записывается в элемент 13.1.1 задержки.

Во втором такте на первый вход коммутатора 11.1.1 поступает элемент аи с выхода элемента 13.1.1 задержки, а на первые входы схемы 10.1.1 сравнения и коммутатор 12.1.1 поступает элемент 321 321 . В схеме 10.1.1 срэвнения происходит сравнение и больший по абсолютному значению элемент записывается в элемент 13.1.1 задержки, а меньший - в первый регистр блока 15.1.1 элементов задержки. Допустим, что Iaii1l 1э2111. Тогда элемент аи снова записывается в элемент 13.1.1 задержки, элемент 321 - в первый регистр блокэ 15.1.1 элементов задержки, нуль с выхода схемы 10.1.1 сравнения (признак отсутствия пере- становки строк) (V21 0) записывается в элемент 17.1.1 задержки, а в элемент 19.1.2 задержки записывается единица. В этом же такте счетчик 6.1.1 уменьшает свое значение на единицу, на его выходе нулевого состояния остается нуль, который там находится до тех пор, пока содержимое счетчика 6.1.1 не станет равным нулю. Кроме того, элемент 312 ai2 поступает на информационный вход ВБ 1.1.2 и записывается в эле- мент 22.1.2 задержки (на управляющих входах коммутаторов 20.1.2 и 21.1.2 - единица).

В третьем такте счетчик 6.1.1 уменьшает свое значение до нуля. На информацией- ный вход ВБ 1.1,1 поступает элемент аз1 аз1 . В схеме 10.1.1 сравнения азт сравнивается с аи1. Пусть Ian11 |аз111 (Vsi 0). Тогда элемент аи записывается в регистр 7.1.1 (на выходе нулевого состояния счетчи- ка 6.1.1 -единица), а элемент азт1 -в первый регистр блока 15.1.1 элементов задержки, 321 переписывается во второй регистр блока 15.1.1 элементов задержки. В ВБ 1.1.2 значение ai2 опять переписывается в эле- мент 22.1.2 задержки, а новое значение 322 Э22 в первый регистр блока 25.1.1 элементов задержки. Кроме того, в В Б 1.1.3 через его информационный вход поступает элемент ai3 атз и записывается в элемент

22.1.3 задержки, единица из элемента 19.1.2 задержки переписывается в 19.1.3, а в элемент 19.1.2 задержки записывается V21 0.

В четвертом такте в элемент 3.1.1 задержки записывается единица, на выходе счетчика 6.1.1 снова появляется нуль, триггер 5.1.1 устанавливается в нулевое состояние. На первый вход делителя 14.1.1 с выхода второго регистра блока 15,1.1 элементов задержки поступает 321 , а с выхода регистра 7.1.1 - аи1, и результат деления (-3211/ац1): 121 записывается в элемент 18.1.1 задержки. Кроме того, на информационный вход ВБ 1.1.1 поступает элемент-си -сц1, который записывается в первый регистр блока 15.1.1 элементов задержки (на выходе элемента 16.1.1 - нуль). В В Б 1.1.2 на управляющий вход регистра 23.1.2 поступает единица, и в регистр 23.1.2 записывается ai21 с выхода элемента 22.1.2 задержки. На второй вход ВБ 1.1.2 поступает аз2 зз21 и зэписывается в первый регистр блока 25.1.2 элементов задержки, а в первый регистр блока 25.1.3 элементов задержки записывается 323 , поступающее с второго входа В Б 1.1.3. В элемент 19.1.3 задержки записывается нуль. В элемент 22.1.4 задержки записывается элемент матрицы В - bn bn1. В элемент 19.1.4 задержки записывается единица.

В пятом такте 8.1.1 задержки записывается единица, в элемент 3.1.1 - нуль. На входы делителя 14.1.1 в ВБ 1.1.1 поступают элементы аз1 и аи и результат деления (-аз1 /аи ) 131 записывается в элемент

18.1.1задержки, 121 записывается в элемент

28.1.2задержки ВБ 1.1.2, а также подается на вход умножителя 27.1.2. Кроме того, на информационный вход ВБ 1.1.1 подается элемент-С21 -С211. который записывается в первый регистр.элемента 13.1.1 задержки, а -си - во второй регистр блока 15.1.1 элементов зэдержки. В ВБ 1.1.2 с выходэ регистра 23.1.2 нз второй вход умножителя 27.1.2 поступает ai21. В элемент 24.1.2 задержки записывается единицз. Результэт умножения 121-312 поступэет нз вход сумматора 26.1.2. где складывается с Э221, и сумма 121-312 + Э221 Э222 записывэется в элемент 29.1.2 задержки. Кроме того, с второго входа ВБ 1.1.2 в первый регистр блока 25.1.2 элементов задержки записывается-С121, аз21 переписывается во второй регистр блока

25.1.2элементов задержки. В ВБ 1.1.3 с выхода элемента 22.V.3 задержки в регистр

23.1.3записывается атз , а в первый регистр блока элементов 22.1.3 задержки записывается азз с информационного входа В Б 1.1.3. .В ВБ 1.1.4 в элемент 19.1.4 задержки зэписывается нуль, с выхода элемента 22.1.4 задержки, пройдя через коммутатор 21 1.4, в него же переписывается bn1, а в первый регистр блока 25.1.4 элементов задержки записывается значение Ь21 Ь211, поступившее с второго входа ВБ 1.1.4. В ВБ 1.1.5 в элемент 19.1.5 задержки записывается единица, в элемент 22.1.5 задержки записывается Ь12 Ь121.

В шестом такте управляющие сигналы поступают аналогично первому такту, а именно в элементы 4.2.2 и 17.2.2 задержки записываются единицы, S-триггер 5.2.2 устанавливается в единицу, значение п-2 1 записывается в счетчик 6.2.2. На входы делителя 14.1.1 в ВБ 1.1.1 поступают -си1 и аи , результат деления -сц1/ац1 Мт записывается в элемент 18.1.1 задержки, с выхода которого 1з1 записывается в элемент 28.1.2 задержки ВБ 1.1.2 и поступает на вход умножителя 27.1.2. На второй вход ВБ 1.1.1 поступает элемент новой матрицы А1 - аи . В ВБ 1.1.2 на входы умножителя 27.1.2 поступают 312 и ISL Результат умножения ai21 -1з1 поступает на вход сумматора 26.1.2. куда поступает аз2 , а сумма 1з1 312 + 332 аз2 поступает в элемент 29.1.2 задержки, с выхода которого элемент 322 через коммутатор 21.2.2 поступает в элемент 22.2.2 задержки ВБ 1.2.2. Кроме того, на второй вход В Б 1.1.2 поступает элемент (-С22 -С221) и, пройдя через первый коммутатор 20.1.2, записывается в блок 25.1.2 элементов задержки. В ВБ 1.1.3 на входы умножителя 27.1.3 поступают 121 и an . Результат умножения ai31 121 поступает на вход сумматора 26.1.3. куда поступает элемент Э231, а сумма 121 -ai3 f + Э231 - 3232 поступает в элемент 29.1.3 задержки. Кроме того, на информационный вход ВБ 1.1.3 поступает (-С1з -С1з1) и, пройдя через первый коммутатор 20.1.3, записы- вается в блок 25.1.3 элементов задержки. В ВБ 1.1.4 с выхода третьего элемента 22.1.4 задержки через второй коммутатор 21.1.4 в регистр 23.1.4 записывается bn1 а через первый коммутатор 20.1.4 с второго входа ВБ 1.1.4 в-блок 25.1.4 элементов задержки записывается Ьз1 Ьз11 В ВБ 1.1.5 в элемент 19.1.5 задержки записывается нуль, с выхода третьего элемента 22.1.5 задержки через второй коммутатор 21.1.5 в него же записывается bis1, а в блок 25.1.5 элементов задержки записывается Ь22 022 с второго входа ВБ 1.1.5.

В седьмом такте на входы делителя 14.1.1 в ВБ 1.1.1 поступают (-С211)и аи1, и результат деления -С2) /an Mi записывается в шестой элемент 18.1.1 задержки, с выхода которого Ui записывается в четвертый элемент 28.1.2 задержки ВБ 1 1.2 и поступает на вход умножителя 27.1.2. В ВБ 1.1.2 на входы умножителя 27.1,2 поступают и ai2 . Результат умножения Й1 -ai2 поступает на вход сумматора 26.1.2, куда поступает элемент -С12 , и сумма Ui -ai2 - 012- ci2 поступает в элемент 29.1.2 задержки, с выхода которого элемент аз22 поступает в ВБ 1.1.2. На выходе нулевого состояния счетчика 6.2.2 - единица. В схеме 10.2.2 сравнения происходит сравнение, и больший элемент записывается в третий элемент 13.2.2 задержки, а меньший - в блок 15.2.2 элементов задержки. Допустим, что при сравнении |аз2 822 I , тогда элемент аз22 записывается в третий элемент 13.2.2 задержки, а элемент 322 в блок

15.2.2элементов задержки. В умножителе

27.1.3ВБ 1.1.3 происходит умножение I3vai3 и результат поступает на вход сумматора 26.1.3. куда поступает элемент азз1. а сумма 1зт -ai3 + азз1 азз2 поступает в элемент 29.1.3 задержки,с выхода которого 323 поступает вэлемент22.2.3 задержки ВБ 1.2.3. Кроме того, на второй вход ВБ 1.1.3 поступает -С23 -С231 и через первый коммутатор 20.1.3 записывается в блок 25.1.3 элементов задержки. В ВБ 1.1.4 на входы умножителя 27.1.4 поступают 121 и bn и результат 121 bn поступает на вход сумматора 26.1.4. куда поступает элемент Ь21 и сумма 12гЬц1+ b2i1 Ь212 поступает в элемент 29.1.4 задержки. Кроме того, на второй вход ВБ 1.1.4 поступает элемент матрицы D -dn dn и через первый коммутатор 20.1.4 записывается в блок 25.1.4 элементов задержки. В В Б 1.1.5 с выхода третьего элемента 22.1.5 задержки bia1 перезаписывается в регистр 23.1.5, а с информационного входа ВБ 1.1.5 Ьз2 Ьз21 проходит через первый коммутатор 20.1.5, записывается в блок 25.1.5 элементов задержки.

В восьмом такте в ВБ 1.1.2 на входы умножителя 27.1.2 поступает Isi и ai2 и результат умножения 151 312 поступает на второй вход сумматора 26.1.2, на первый вход которого поступает элемент -С22 и результат I si -ai21 - С22 С22 записывается в элемент 29.1.2 задержки, с выхода которого С12 поступает в ВБ 1.2.2 и записывается в блок 15.2.2 элементов задержки. В элемент 3.2.2 задержки записывается единица. На входы делителя 14.2.2 поступает-322 /аз2

-1з2 и результат записывается в элемент 18.2.2 задержки. В В Б 1.1.3 на входы умножителя 27.1.3 поступает l/ц и ais и результат Ui -ai3 поступает на вход сумматора 26.1.3, куда лостугэет -стз1 и сумма Ui -ai31 - ci31

--С13 поступает в элемент 29.1.3 задержки, с выхода которого азз записывается в ВБ

1.2.3 и через коммутатор 21.2.3 записывается в элемент 22.2.3 задержки. В ВБ 1.1.4 на входы умножителя 27.1.4 поступает 1з1 и bn и результат умножения 1з1 bn поступает на вход сумматора 26.1.4, куда поступает ЬзЛ и сумма 1з1 bn + Ьз1 Ьз1 записывается в элемент 29.1.4 задержки, с выхода которого Ь22 поступает в ВБ 1.2.4 и через коммутатор 21.2.4 записывается в элемент 22.2.4 задержки. Кроме того, на информационный вход В Б 1.1.4 поступает элемент d2i dai и через коммутатор 21.1.4 записывается в элемент 22.1 А задержки. В ВБ 1.1.5 на вхожки, с выхода которого элемент dn поступает в ВБ 1.2.4. В В Б 1.1.5 на входы умножителя 27.1.5 поступают элементы Isrbi21, результат поступает в сумматор 26.1.5, сумма

5 lsi -bi2 + d221 d222 поступает в элемент 29.1.5 задержки, с выхода которого Ьз22 поступает в ВБ 1.2.5 и через коммутатор 21.2.5 записывается в элемент 22.2.5 задержки. В ВБ 1.2.2 на входы делителя 14.2.2 поступают С22 и аз2 и

10 результат деления с222/аз2 I52 записывается в элемент 18.2.2 задержки, с выхода которого 42 поступает на входы умножителя 27.2.3 и элемента 28.2.3 задержки. Результат умноды умножителя 27.1.5 поступают 121 и b 12 и жения 142-азз с выхода умножителя 27.2.3

результат умножения hrbi21 поступает на вход сумматора 26.1.5, куда поступает элемент Ь22, И Сумма 121 bl2 + D22 D22 ЗЭПИсывается в элемент 29.1.5 задержки. Кроме того, на информационный вход ВБ 1.1.5 поступает элемент di2 di21 и через второй коммутатор 21.1.5 записывается в элемент 22.1.5 задержки.

В девятом такте с выхода элемента 29.1.2 задержки ВБ 1.1.2 элемент С222 поступает в ВБ 1.2.2 и записывается в блок 15.2.2 элементов задержки. В элемент 8.2.2 задержки записывается единица. В делителе

14.2.2происходит деление С122/аз22 i42 и результат записывается в элемент 18.2.2 задержки, с выхода которого 1з2 поступает в ВБ 1.2.3, где записывается в элемент задержки 28.2.3 и поступает на вход умножения 27.2.3, где происходит умножение 1з2 азз . результат умножения поступает на второй вход сумматора 26.2.3, на первый вход которого поступает азз2, и сумма 1з2 -азз2 + 3232

азз записывается в элемент 29.2.3 задержки. В ВБ 1.1.4 на входы умножителя 27.1.4 поступают Ui и bn1 и результат умножения Mi Ь1 поступает в сумматор 26.1.4, сумма

141 -bir +dn dn2 записывается в элемент 29.1.4 задержки, с выхода которого элемент Ьз12 поступает в ВБ 1.2.4. В ВБ 1.1.5 на входы умножителя 27.1.5 поступает 1зт и bi2 , где происходит умножение, и результат 1з1 Ь12 поступает в сумматор 26.1.5 и сумма 1з1 -bi2 + Ьз2 Ьз2 поступает в элемент 29.1.5 задержки, с выхода которого С222 поступает в ВБ 1.2.5. Кроме того, на второй вход В Б 1.1.5 поступает d22 d22 и записывается в элемент 22.1.5 задержки. В десятом такте с выхода элемента

29.1.3задержки в ВБ 1.2.3 поступает С2з2. В элементы 4.3.3 и 17.3.3 задержки записывается единица и на выходе нулевого состояния счетчика 6.3.3 появляется единица. На входы умножителя 27.1.4 ВБ 1.1.4 поступают элементы lsi и bn и результат умножения поступает в сумматор 26.1.4, сумма Isi bn +

Ud2i1 d2i2 поступает в элемент 29.1.4 задер15 поступает в сумматор 26.2.3, сумма ец -азз2 + i-ci32 C133 записывается в элемент 29.2.3 задержки, с выхода которого элемент азз3 поступает в ВБ 1.3.3 и через коммутатор 12.3.3 записывается в элемент 13.3.3 задержки. В

20 ВБ 1.2.4 на входы умножителя 27.2.4 поступают элементы 1з2 и Ьз1 , результат умножения поступает в сумматор 26.2.4, с выхода которого 1з2 Ьз1 -D21 Ьз13 записывается в элемент 29.2.4 задержки.

25 В одиннадцатом такте с выхода элемента 19.1,4 задержки элемент d2i поступает в ВБ 1.2.4 и через коммутатор 21.2.4 записывается в элемент 22.2.4 задержки. В ВБ 1.1.5 на входы умножителя 27.1.5 поступают Isi и

® bi2 , результат умножения Isi bi2 поступает в сумматор 26.1.5, и результат суммирования I5rbi21 + d221 d222 поступает в элемент 29.1.5 задержки, с выхода которого элемент d nocTynaeT в ВБ 1.2.5, где через

35 коммутатор 21.2.5 записывается в элемент 22.2.5 задержки. С выхода ВБ 1.2.2 элемент I 52 поступает на входы умножителя 27.2.3 и элемента 28.2.3 задержки. Результат умножения 1б2-азз2 ВБ 1.2.3 поступает в сумма40 тор 26,2.3 и сумма 152 азз2 + С232 С233 поступает в элемент 29.2,3 задержки, с выхода которого С1з3 поступает в ВБ 1.3.3 и, пройдя через блок 15.3.3 элементов задер- жки,поступает на вход делителя 14.3.3. Ре- зультат деления С1з /азз Мз записывается в элемент 18,3.3 задержки. В ВБ 1.2.4 на входы умножителя 27.2.4 поступают элементы М2 и Ьзт2, результат умножения I-42 Ьзг поступает в сумматор 26.2.4 и сумма U2 b3i2 + dn2 dii3записывается вэлемент

29.2.4задержки, с выхода которого элемент bsi3 поступает в ВБ 1.3.4. В ВБ 1.2.5с выхода умножителя 27.2.5 1з2 Ьз2 поступает в сумматор 26.2.5, результат суммирования I32 -Ьз22 + Ь222 Ьз23 записывается в элемент

29.2.5задержки.

В двенадцатом такте с выхода элемента 29.1.5 задержки элемент d22 поступает в ВБ 1.2.5. С выхода элемента 29.2.3 задержки

жки, с выхода которого элемент dn поступает в ВБ 1.2.4. В В Б 1.1.5 на входы умножителя 27.1.5 поступают элементы Isrbi21, результат поступает в сумматор 26.1.5, сумма

lsi -bi2 + d221 d222 поступает в элемент 29.1.5 задержки, с выхода которого Ьз22 поступает в ВБ 1.2.5 и через коммутатор 21.2.5 записывается в элемент 22.2.5 задержки. В ВБ 1.2.2 на входы делителя 14.2.2 поступают С22 и аз2 и

результат деления с222/аз2 I52 записывается в элемент 18.2.2 задержки, с выхода которого 42 поступает на входы умножителя 27.2.3 и элемента 28.2.3 задержки. Результат умножения 142-азз с выхода умножителя 27.2.3

5 поступает в сумматор 26.2.3, сумма ец -азз2 + i-ci32 C133 записывается в элемент 29.2.3 задержки, с выхода которого элемент азз3 поступает в ВБ 1.3.3 и через коммутатор 12.3.3 записывается в элемент 13.3.3 задержки. В

0 ВБ 1.2.4 на входы умножителя 27.2.4 поступают элементы 1з2 и Ьз1 , результат умножения поступает в сумматор 26.2.4, с выхода которого 1з2 Ьз1 -D21 Ьз13 записывается в элемент 29.2.4 задержки.

5 В одиннадцатом такте с выхода элемента 19.1,4 задержки элемент d2i поступает в ВБ 1.2.4 и через коммутатор 21.2.4 записывается в элемент 22.2.4 задержки. В ВБ 1.1.5 на входы умножителя 27.1.5 поступают Isi и

® bi2 , результат умножения Isi bi2 поступает в сумматор 26.1.5, и результат суммирования I5rbi21 + d221 d222 поступает в элемент 29.1.5 задержки, с выхода которого элемент d nocTynaeT в ВБ 1.2.5, где через

5 коммутатор 21.2.5 записывается в элемент 22.2.5 задержки. С выхода ВБ 1.2.2 элемент I 52 поступает на входы умножителя 27.2.3 и элемента 28.2.3 задержки. Результат умножения 1б2-азз2 ВБ 1.2.3 поступает в сумма0 тор 26,2.3 и сумма 152 азз2 + С232 С233 поступает в элемент 29.2,3 задержки, с выхода которого С1з3 поступает в ВБ 1.3.3 и, пройдя через блок 15.3.3 элементов задер- жки,поступает на вход делителя 14.3.3. Ре- зультат деления С1з /азз Мз записывается в элемент 18,3.3 задержки. В ВБ 1.2.4 на входы умножителя 27.2.4 поступают элементы М2 и Ьзт2, результат умножения I-42 Ьзг поступает в сумматор 26.2.4 и сумма U2 b3i2 + dn2 dii3записывается вэлемент

29.2.4задержки, с выхода которого элемент bsi3 поступает в ВБ 1.3.4. В ВБ 1.2.5с выхода умножителя 27.2.5 1з2 Ьз2 поступает в сумматор 26.2.5, результат суммирования I32 -Ьз22 + Ь222 Ьз23 записывается в элемент

29.2.5задержки.

В двенадцатом такте с выхода элемента 29.1.5 задержки элемент d22 поступает в ВБ 1.2.5. С выхода элемента 29.2.3 задержки

10

элементС23 поступаете ВБ 1.3.3, где, пройдя блок 15.3.3 элементов задержки, поступает на вход делителя 14.3.3 и результат деления бз записывается в элемент 18.3.3 задержки, с выхода которого элемент Цз поступает в элемент 28.3.4 задержки ВБ 1.3.4 и на вход умножителя 27.3.4, с выхода которого 143 Ьз1 поступает в сумматор 26.3.4, с выхода которого сумма Цз Ьзт3 + dn3 dn хц записывается в элемент 29.3.4 задержки. В ВБ 1.2.4 на входы умножителя 27,2,4 поступают I52 и Ьз12, результат умножения s2 b3if поступает в сумматор 26.2.4 и сумма I52 Ьз12 + d2i d2i3 записывается в элемент 29.2.4 задержки, с выхода которого элемент 15 d 113 поступает в В Б 1.3.4. На входы умножителя 27.2.5 ВБ1.2.5 поступают элементы I42 и Ьз22, результат умножения U2 b322 поступает в сумматор 26,2.5, и сумма Ц2 Ьз22 + Н22 di23 поступает в элемент 29.2.5 задер- жки,с выхода которого di23 поступает в ВБ

20

1.3.5.

В тринадцатом такте из ВБ 1 2.4 элемент d2i3 поступает в ВБ 1.3.4. В В Б 1.2.5 на входы умножителя 27.2.5 поступают эле- 25 менты 1з2 и Ьз2 , результат умножения I52 Ьз22 поступает в сумматор 26.2,5 и сумма 1б2 Ьз22 + d222 d22u поступает в элемент 29.2.5 задержки, с выхода которого di23 поступает в ВБ 1.3.5. В ВБ 1.3.4 на входы 30 умножителя 27.3.4 поступают Isa и Ьзг, результат умножения 1бЗ-Ьз13 поступает в сумматор 26.3.4 и сумма Iss bai3 + d2i3 d2i4

Х21 записывается в элемент 29.3.4 задержки, с выхода которого Х21 поступает на первый выход устройства. В ВБ 1.3,5 на входы умножителя 27 3.5 поступают дз и Ьз2 . результат умножения Цз-Ьз2 поступает в сумматор 26.3.5, сумма которого Цз-Ьз23 +.

di2 - di2 xi2 записывается в элемент 29.3.5 задержки, и Х12 поступает на второй выход устройства.

В четырнадцатом такте с выхода ВБ 1.2.5 элемент d223 поступает в ВБ 1.3.5. С выхода ВБ 1.3.4 на первый выход устройства выдается Х21. В В Б 1.3.5 на входы умножителя 27,3.5 поступают элементы Is3 и Ьз23. результат умножения Is3 b32 поступает в сумматор 26.3.5 и сумма 53-Ьз23 +d223 d22 Х22 записывается в элемент 29.3.5 задержки, с выхода которого на второй выход устройства выдается Х22.

На этом вычисление элементов результирующей матрицы X СА 1B+D заканчивается. Таким образом, полное время реализации алгоритма Т п(л-1)/2+2(п-1) +

п + р + г тактов, причем элементы результирующей матрицы X выдаются на входы устройства последние г + р + 1 тактов(причем

35

55

40

45

50

0

5

0

5 0

с k-ro выхода устройства выдается k-й столбец матрицы X (k 1, г) аналогично поступлению исходных элементов матриц В и D на соответствующие входы устройства. Однако в случае решения потока аналогичных задач период работы устройства составляет т п + fp тактов. Это означает, что первый элемент ац очередной объединенной матрицы можно подавать через t тактов после подачи элемента аи предыдущей объединенной матрицы. В нашем случае Т 14, t 5 тактов, следовательно, элементы следующей матрицы можно начинать подавать на вход устройства (вместе с импульсом запуска) с шестого такта.

Таким образом, предлагаемое устройство при примерно равных аппаратурных затратах и временных характеристиках с известным устройством позволяет существенно расширить функциональные возможности последнего. Кроме того, реализация частичного выбора ведущего элемента позволяет в ряде задач значительно повысить устойчивость, а следовательно, и точность вычислительного процесса по сравнению с известным устройством.

Формула изобретения 1. Устройство для выполнения операций над матрицами, содержащее п вычислительных блоков первого типа и п -(п-1)/(2+п -г) вычислительных блоков второго типа (где п иг- размерности матриц), причем вход пуска первого вычислительного блока первого типа соединен с входом запуска устройства.

5 первый выход режима (i.j)-ro вычислительного блока первого типа (где i j 1. n-1) соединен с входом режима (i+1, j+1)-ro вычислительного блока первого типа, второй выход режима (а. Ь)-го вычислительного блока первого типа (где а b 1. п) соединен с входом режима (а, Ь+1)-го вычислительного блока второго типа, выход режима (с, d+k)-ro вычислительного блока второго типа (где ,,n + r-c-1)соединен с входом режима.(с, d+k+1)-ro вычислительного блока второго типа, информационный вход первого вычислительного блока первого типа подключен к первому информационному входу устройства информационный вход (1, ji)-ro вычислительного блока второго типа (где ji 2, n+r) подключен к ji-му информационному входу устройства, выход результата вы- числительного блока второго типа (где i j - - 1, n-1) соединен с информационным входом

5 (i+1, j+1)-ro вычислительного блока первого типа, выход результата (п. n+ki)-ro вычисли- тельного блока второго типа (где ki 1. г) соединен с ki-м выходом результата устройства, выход результата (i, j+k2)-ro вычислительного блока второго типа(где j i{

0

5

0

n-1; k2 2, n+r-i) соединен с информационным входом (i+1, j+k2)-ro вычислительного блока второго типа, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет pea- лизации им алгоритма Фаддеева, выход признака перестановки и выход деления (а, Ь)-го вычислительного блока первого типа (где а b T7n) соединены с входом признака перестановки и входом деления (а, Ь+1)- го вычислительного блока второго типа, выход признака перестановки и выход деления (с, d+k)-ro вычислительного блока второ- го типа (где с d 1, n; k 1. n+r-c-1) соединены с входами признака перестанов- ки и деления (с, d+k+1)-ro вычислительного блока второго типа.

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

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

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

,

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных, в том иисле и систолических устройств, предназначенных для выполнения операций над матрицами. Цель изобретения - расширение функциональных возможностей устройства за счет реализации им алгоритма Фаддеева. Устройство содержит п вычислительных блоков первого типа и п вычислительных блоков второго типа и имеет вход запуска, информационные входы и информационные выходы. 2 з.п. ф-лы. 3 ил

ъ,

фиг.З