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

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

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

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

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

Целью изобретения является расширение функциональных возможностей устройства за счет частичного выбора ведущего элемента при вычислении выражений вида САИВ + D, где Ц п, ju. и Xr - матрицы (в частном случае, при г 1, р 1 матрицы С, В и матрица D могут быть векторами размерностью n и скаляром соответственно).

На фиг. 1 представлена структурная схема устройства для операций над матрицами; на фиг. 2 - структурная схема первого операционного блока (ОБ); на фиг. 3 - структурfe

XI

00 4 ЧЭ Ю v|

иая схема f-ro операционного блока (, п+г); на фиг. 4 - структурная схема возможного варианта построения блока синхронизации.

Устройство для операций над матрицами содержит ОБ 1.1-1.(п + г) и блок синхронизации 2, причем вход запуска устройства подключен ко входу запуска блока синхронизации 2, первый и второй выходы которого подключены соответственно к первому и вто- рд му управляющим входам первого ОБ, с первого по (п + г)-й входы элементов обрабо- тываемы матриц устройства подключены соответственно к первым информационным входам ОБ 1.1-1.(п + г), первый, второй и третий выходы ОБ 1,а (где а 1,.... п + г -1) подключены соответственно к первому управляющему, второму управляющему и ко второму информационному входам ОБ 1. а + 1, четвертые выходы ОБ 1.1 (I 2, п + г) подключены соответственно к выходам с первого по (п + г- 1}-й результата устройства, пятый выход ОБ 1.Ь (где о 2, ..., п + г - 1) подключен к третьему управляющему входу ОБ 1.(Ь +1), четвертый выход ОБ 1.1 подключен к третьему управляющему входу ОБ 1.2,

шестой выход ОБ 1,с (где с - 3п + г)

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

подключен к первому информационному входу коммутатора 8, выход которого подключен к первым информационным входам второго коммутатора 11, третьего коммутатора 12 и узла сравнения 10, выход которого подключен к первому входу элемента И 13, выход которого подключен к первому входу элемента ИЛИ 5, выход которого i подключен к управляющим входам коммутаторов

0 11 и 12 и ко входу третьего элемента задержки 14, выход которого подключен ко второму выходу ОБ 1.1, выход коммутатора 11 подключен к информационному входу узла задержки б, первый выход которого подклю5 чен ко входу четвертого элемента задержки 17, выход которого подключен ко входу записи/считывания первого регистра 18, ко входу декремента счетчика 9 и ко входу установки в ноль триггера 4, выход которого

0 подключен ко второму входу элемента И 13, второй и третий информационные входы ОБ 1.1 подключены соответственно ко второму информационному входу коммутатора 8 и к информационному входу счетчика 9, инфор5 мационный выход которого подключен ко еторому управляющему входу узла задержки б, второй выход которого подключен к первому информационному входу делителя 16, выход которого подключен к информаци0 онному входу второго регистра 15, выход которого подключен к третьему выходу ОБ 1.1, выход коммутатора 12 подключен к информационному входу третьего регистра 19 и к информационному входу регистра 18,

5 выход которого подключен ко второму информационному входу делителя 16, выход регистра 19 подключен ко вторым информационным входам коммутаторов 11 и 12 и узла сравнения 10, вход синхронизации ОБ

0 1.1 подключен ко входам синхронизации триггера 4, узла задержки б, регистра. 1.8 у счетчика 9, при этом аждый ОБ 1.1(, п+г) , ч содержит первый элемент задержки 20, / первый 21 и второй 22 коммутаторы, второй

5 элемент задержки 23, первый узел задержки 24, второй 25 и первый 26 регистры, третий элемент задержки 27, счетчик 28, сумматор 29, умножитель 30, четвертый регистр 31, третий коммутатор 32, четвертый

0 элемент задержки 33, второй узел задержки 34, третий регистр 35, причем в каждом ОБ 1.1 первый управляющий вход ОБ подключен ко входу первого элемента задержки 20, выход которого подключен к первому управ5 Ляющему йходу первого узла задержки 24 и к первому выходу ОБ 1,1, второй управляющий вход которого подключен к управляющим входам первого 21 и второго 22 коммутатора и ко входу второго элемента 23 задержки, выход которого подключен ко

второму выходу ОБ 1.1, первый информационный вход которого подключен к первому информационному входу третьего коммутатора 32, выход которого подключен к первым информационным входам коммута- торов 21 и 22, выход коммутатора 21 подключен к информационному входу узла задержки 24, первый и второй выходы которого подключены соответственно к первому информационному входу сумматора 29 и ко входу третьего элемента задержки 27, выход которого подключен ко входу записи/считывания первого регистра 26 и ко входу декремента счетчика 28, информационный выход которого подключен ко второ- му управляющему входу узла задержки 24, выход коммутатора 22 подключен к информационному входу регистра 26 и к информационному входу второго регистра 25, выход которого подключен ко вторым информаци- онным входам коммутаторов 21 и 22, выход регистра 26 подключен к первому информационному входу умножителя 30, выход которого подключен ко второму информационному входу сумматора 29, информационный выход ко- торого подключен к информационным входам третьего регистра 35 и второго узла задержки 34, второй информационный вход ОБ 1.1 подключен ко второму информационному входу умножителя 30 и к информаци- онному входу четвертого регистра 31, выход которого подключен к третьему выходу ОБ 1.1, третий, четвертый и пятый информационные входы которого подключены соответственно ко второму информационному входу коммутатора 32, к информационному входу счетчика 28 и к управляющему входу узла задержки 34, выход которого подключен к- шестому выходу ОБ 1.1, четвертый выход и третий управляющий вход которого подключены соответственно к выходу регистра 35 и ко входу четвертого элемента задержки 33, выход которого подключен к управляющему входу коммутатора 32, ко входу режима счетчика 28 и к пятому выходу ОБ 1.1, вход синхронизации которого подключен ко входам синхронизации узлов задержки, сумматора, умножителя, счетчика и регистра 26 и ко входам записи/считывания регистров 25. 31 и 35.

Устройство для операций над матрица- ми предназначено для вычисления с помощью алгоритма Фаддеева выражения вида X + D, где в общем случае {ац}, B njcr -{brk}, Хп {сц}, Dfp f. n {dik} матрицы, представленные в виде объединенной матрицы: AIB

да

причем суть алгоритма сводится к тому, что после обнуления в объединенной матрице нижнего левого квадранта (т.е. элементов матрицы - С), в правом нижнем квадранте (на месте матрицы D) получаем искомый результат Ј г (см. J.G. Nash, S.Hansen, modified algorithm for concurrent execution of lirear algebra operations // IEEE Trans. Сотр., v. 37. № 2, Febr. 1988, p. 130). Фактически это выражение К + D позволяет решать дополнительно еще несколько задач, а именно:

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

при С

I, D-0:

2)обращение матрицы

приС В 1, 0 0;

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

X С В при А i, D - 0;

4)умножение со сложением матриц

X С В + D при А i;

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

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

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

сравнение их с элементом аи , и, если очередной элемент I aji I an I , осуществляется перестановка j-й и 1-й строк, т.е. 1-я строка становится j-й, и наоборот. В противном случае перестановка строк не происходит. Только после окончания всех (на данном

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

Поступление исходных данных организовано еле дующим-образом. На 1-й вход устройства (I 1, п) каждый такт поступает элемент i-ro столбца объединенной матрицы, начиная с элемента аи и заканчивая-Cpi. на (п + kj-й вход устройства (k 1, V) - аналогично, начиная с элемента bite и заканчивая dpk. В свою очередь, элементы столб- ца объединенной матрицы поступают на соответствующие входы устройства со сдвигом один такт, т.е. элемент аи поступает на 1-й вход устройства в 1-м такте его работы, а элемент b ik - в (п + к)-м такте работы устрой- ства.

Рассмотрим работу устройства. Для простоты описания и без потери общности положим п 3, р г 2, Условимся, что прием информации во все регистры, в том числе в регистры узлов задержки, в элементы задержки 14 и 27 всех операционных блоков осуществляется по заднему фронту синхроимпульса, т.е. в конце такта, а во все остальные триггеры всех ОБ и счетчик 37

блока 2 - по переднему фронту синхроимпульса, т.е. в начале такта. Условимся также что изменение состояния счетчиков 9 и 28 происходит по положительному перепаду сигнала на их декрементирующих входах. Считаем, что перед началом вычислений (гл + 1)-е в разряды всех регистров узла 6.1 установлены в нулевое состояние.

Импульс пуска, поступающий на вход запуска устройства, устанавливает в единицу RS-триггер 40, а также поступает на вход режима счетчика 36, в который записывается значение (п + р - 1) 4, и (через элемент ИЛИ 39) на вход режима счетчика 37.

В первом такте по переднему фронту синхроимпульса в счетчик 37 записывается информация с выхода счетчика 36, т.е. (п + р - 1), и на выходе отрицательногоо переноса счетчика 37 - единица, а также устанавливаются в единицу элементы задержки 3.1, 7.1 и 14.1, после чего в счетчик 9.1 записывается значение (п -1) 2. Кроме того, элемент аи аи1 исходной матрицы .поступает на первый вход блока 1.1 и, пройдя через коммутаторы 11.1 и 12,1, записывается в конце такта в регистр 19.1 (на управляющих входах обоих коммутаторов - единицы), а единица с выхода элемента задержки 3.1 записывается в (т + 1)-й разряд первого регистра (Р1) узла 6.1.

Во втором такте счетчик 37 уменьшает свое значение на единицу. В блоке 1.1 на выходе элемента, задержки 3.1 - нуль, йа выходе триггера 4.1 появляется единица, содержимое (т + 1)-го разряда Р1 узла 6.1 переписывается в Р2 узла 6.1. Элемент 321 321 поступает через коммутатор 8.1 на входы коммутаторов 11.1 и 12,3, и узла с равнения 10.1, на другие входы которых поступает ац пусть I an1 } I 3211 I. Тогда нуль с выхода узла сравнения 10.1 (признак перестановки строк) поступает через элементы 13.1 и 5.1 в элемент задержки 14.1 и на управляющие входы коммутаторов 11.1 и 12.1, вследстеие чего ал1 переписывается в регистр 19.1, а эгг записывается в Р1 узла 6.1. В блоке 1.2 в счетчик 28.2 записывается значение п -1, элементы задержки 20.2,23.2 и 33.2 устанавливаются в единицу. На первый информационный вход блока 1.2 поступает элемент 312 ai21 и. пройдя через коммутатор 32.2, поступает на входы коммутаторов 21.2 и 22.2 и в конце такта записывается в регистр 25.2.

В третьем такте счетчик 37 уменьшает свое значение на единицу. В блоке 1.1 на выходе элемента задержки 17.1 появляется единица. Элемент аз1 аз11 поступает через коммутатор 8.1 на входы коммутаторов 11.1 и 12.1 и узла сравнения 10.1, на

другие входы которых поступает а . Пусть S | ац1| . Тогда единица с выхода узла сравнения 10.1 записывается в элемент задержки 14.1 и управляет коммутаторами 11.1 и 12.1, вследствие чего аи1 записывается в Р1 узла 6.1 (э21 переписывается в Р2 узла 6.1), а аз11 записывается в регистры 18.1 и 19.1. В блоке 1.2 единица из (т + 1)-го разряда Р1 узла 24,2 переписывается в Р2 узла 24.2. Элемент 322 3221 посту- пает на вход коммутатора 32.2, с выхода которого поступает на входы коммутаторов

21.2и 22.2 и в конце такта записывается в регистр 25.2 {ai21 переписывается в Р1 узла 24.1). В блоке 1.3 элементы задержки 20.3,

23.3и 33.3 устанавливаются в единицу, в счетчик 28,3 записывается значение п - 1. На первый вход ОБ 1.3 поступает элемент ai3 ai31 и, пройдя через коммутаторы 32.3, 21.2 и 22,2, в конце такта записывается в регистр 25.3.

В четвертом такте счетчик 37 уменьшает свое значение на единицу. В блоке 1.1 триггер 4.1 устанавливается в нуль. На входы коммутаторов 11.1 и 12.1 поступает -Си -Си1 и записывается в Р1 узла 6.1, aj,. - переписывается в Р2 узла 6/1, 3211 поступает на первый вход делителя 16.1, на второй вход которого поступает аз11 из регистра 18.1. Делитель 16.1 выполняет деление и резуль- тат -321 /аз1 tet, пройдя регистр 15.1, поступает на его выход. В блоке 1.2 на выходе элемента задержки 27.2 - единица. Элемент аз2 аз21 поступает на вход коммутатора 32.2 и, пройдя коммутатор 22.2, записывает- ся в регистры 25.2 и 26.2. В блоке 1.3 на выходе элемента задержки 20.3 - нуль. На вход коммутатора 32.3 поступает элемент 323 /а23 и, пройдя коммутатор 21.3, записывается в Р1 узла 24.3. В блоке на выходе элементов задержки 20.4,23.4 и 33.4 устанавливается единица. В счетчик 28.4 записывается значение п -1. Элементен Ьц1 поступает на вход коммутатора 32.4 и, пройдя коммутатор 22.4, записывается в регистр 25.4.

В пятом такте счетчик ,37 уменьшает свое значение на единицу. В блоке 1.1 на входы коммутаторов 11.1 и 12.1 поступает элемент -С21 -С211 и записывается в Р1 узла 6.1 а -Си переписывается в Р2 узла 6.1. На вход делителя 16.1 поступают аи1 и азг и результат деления -anVasi1 1з1 поступает на выход регистра 15.1, с выхода которого lai поступает на вход блока 1.2 и на второй вход умножителя 30.2, на первый вход которого поступает аз21 с выхода регистра 26.2, результат hi аз21 поступает на второй сумматор 29.2, на первый вход которого поступает ам с Р2 узла 24.2 и сумма 121 аз21 + 3221 322 поступает в регистр 35.2 и узел 34.2. Элемент -Ci2 -Сгг1 поступает на входы коммутаторов 21.2 и 22.2 и записывается в Р1 узла 24.2. В блоке 1.3 элемент задержки 27.3 устанавливается в единицу. Элемент азз азз1 поступает на вход коммутатора 32.3 и записывается в регистры 25.3 и 26.3, Э231 переписывается в Р2 узла 24.3, ai31 записывается вР1 узел 24.3. В блоке 1.4 элемент Ь21 Ь211 поступает на вход коммутатора 32.4 и записывается в Р1 узла 24.4, а Ьц1 перезаписывается в Р2 узла 24.4. В блоке 1.5 в счетчик 28.5 записывается значение п -1. Элемент bra bi21 поступает на вход коммутатора 32.5 и, пройдя коммутатор 21.5, записывается в узел 24.5.

В шестом такте Э222 из узла 34.2 поступает на первый вход блока 1.1 и через коммутатор 12.1 записывается в регистр 19.1. На вход делителя 16.1 поступает-Сц и азт1 и результат Сц1/аз11 М| поступает на вход регистра 15.1. В блоке 1.2 на вход умножителя 30.2 поступает Ы и аз21, умножается и поступает на второй вход сумматора 29.2, на первый вход которого с выхода узла 24.2 поступает ai21 и сумма з1 332 + ai21 аз22 передается на выход регистра 35.2 и записывается в 34.2. На вход коммутатора 32,2 поступает -С22 -С221. В блоке 1.3 на входы умножителя 30.3 поступает bi и азз1, результат поступает на второй вход сумматора 29.3, на первый вход которого поступает Э231 и сумма 121 азз + 323 Э232 записывается в регистр 35.3 и в узел 34.3. На вход коммутатора 32.3 поступает элемент -Ci3 -С131. В блоке 1.4 на вход коммутатора 32.4 поступает элемент Ьзт Ьз11„и, пройдя коммутатор 22.4, записывается в регистры 25,4 и 26.4. В блоке 1.5 на вход коммутатора 32.5 поступает и записывается в Р1 узла 24.5.

В седьмом такте в блоке 1.1 на входы делителя 16.1 поступает -С211 и аз11 и результат С211/аз11 151 поступает на выход регистра 15.1. На вход коммутатора 8.1 поступает аз22 и в схеме сравнения происходит сравнение Э222 и аз22. Пусть i аз22 I 1э22 I. тогда аз2 записывается в регистры 18.1 и 19.1, а Э222 - в Р1 узла 6.1. В блоке 1.2 на входы умножителя 30.2 поступает Ui и аз21 и результат подается на второй вход сумматора 29.2 и сумма Ui аз21 - Ci21 Ci22 записывается в регистр 35.2 и в узел 34.2. На вход коммутатора 32.2 поступает элемент 323 . В блоке 1.3 на входы умножителя 30.3 поступает 1з1 и азз1. результат поступает на второ й вход сумматора 29.3, сумма з1 азз1+ ai31 азз поступает в регистр 35.3

и в узел 34.3. На вход коммутатора 32.3 поступает-С231 и через коммутатор 21,3 записывается в узел 24.3. В блоке 1.4 на входы умножителя 30.4 поступает 121 и Ьз11, результат поступает на второй вход сумматора, сумма 121 Ьз1 + bat1 bar поступает на выход регистра 35.4 и в узел 34.4. На вход коммутатора 32.4 поступает элемент dn dn1 и, пройдя коммутатор 21.4, записывается в узел 24.4. В блоке 1.5 на вход коммутатора 32.5 поступает элемент Ьз2 ш Ьз21 и записывается в регистры 25.5 и 26.5.

В восьмом такте в блоке 1.1 на входы делителя 16.1 поступает Э22 и аз2 и результат Э222/аз22 1з2 поступает на выход регистра 15.1. В блоке 1.2 на входы умножителя 30.2 поступает tgi и 332 , результат поступает на второй вход сумматора 29.2 и сумма lsi аз21 - С221 Сза2 записывается в узел

34.2.В блоке 1.3 на входы умножителя 30.3 поступает Ui и азз1 и результат умножения поступает на второй вход сумматора 29.3, на первый вход которого поступает -Cis1 и сумма азз - Cis1 Cis2. принимается в регистр 35.3 и узел 34.3. На второй вход коммутатора 32.3 с выхода узла 34.4 посту- паЁет элемент Ь212 и, пройдя коммутатор

21.3,записывается в узел 24.3. В блоке 1.4 на входы умножителя 30.4 поступает 1з1 и Ьз11 и результат поступает на второй вход сумматора 29.4, на первый вход которого поступает b 111 и резул ьтат bi Ьз1 + b 111 Ьзг записывается в регистр 35.4 и з Р1 узла 34.4. В блоке 1.5 на вход умножителя 30.5 поступает 121 и Ьзз1 и результат поступает на второй вход сумматора 29.5, на первый вход которого поступает Ь221 и результат 121 Ьз21 + Q221 0222 записывается в регистр 35.5 и в узел 34.4.

В десятом так Те в блоке 1.1 на входы делителя 16.1 поступает С222 и аз22 и результат -С222/аз22 bs2 поступает на выход регистра 15.1. На второй вход коммутатора 8.1 поступает азз3 и записывается в регистры

18.1и 19.1. В блоке 1.2 на входы умножителя поступают 142 и азз2 и результат поступает на второй вход сумматора 29,2, на первый вход которого поступает Cis и результат 42 азз2 + Cis2 Cis3 поступает в регистр

35.2и узел 34.2. В блоке 1.3 на входы умножителя 30.3 поступает 1з2 и Ьз12 и результат поступает на второй вход сумматора 29.3, на первый вход которого поступает D212 и результат 1з2 Ьз12 + bar Ьз13 записывается в регистр 35.3 и узел 34.3. В блоке 1.4 на входы умножителя 30.4 поступает Isi и Ьз11 и результат поступает на второ й вход сумматора 29.4, на первый вход которого поступает d2i1 и результат Isi Ьз11 + d2i1 d2i2 записывается в регистр 35,4 и в узел 34.4. В блоке 1.5 на входы умножителя 30.5 поступает Ui и Ьз21 и результат поступает на второй вход сумматора 29.5, на первый вход которого поступает di21 и результат + + di21 - di22 записывается в регистр 35.5 и в узел 34.5.

В одиннадцатом такте в блоке 1.1 на

0 входы делителя 16.1 поступает (из3 и азз3 и результат-Cis/азз 143 поступает на выход регистра 15.1, на входы умножителя 30.2 поступает Ig2 и азз2 и результат поступает на второй вход сумматора 29.2, на первый

5 вход которого поступает С232 и результат I52 азз2 + С232 C23S поступает в регистр 35.2 и в узел 34.2. На вход коммутатора 32.2 поступает Ьз13 и записывается в регистры 25.2 и 26.2. В блоке 1.3 на входы умножителя

0 30.3 поступает л2 и bsi2 и результат поступает на второй вход сумматора 29 3, на первый Б.ХОД которого поступает dn2 и результат J42 bsi +dii-dn записывается в регистр 25.3 и узел 34.3. В блоке 1,4 на

5 входы умножителя 30.4 поступает 1з2 и Ьз22 и результат поступает на второй вход сумматора 29.4, на первый вход которого поступает d221 и результат fsi Ьз11 + d221 d222 записывается в регистр 35.4 и в узел-3.4.4. В

0 блоке 1.5 на входы умножителя 30.5 поступает Isi и bsi1 и результат поступает на второй вход сумматора 29.5, на первый вход которого поступает d221 и результат Isi bar + d22 -d22 записывается в регистр

5 35.5 и в узел 34.5.

В двенадцатом такте а блоке 1.1 на входы делителя 16.1 поступает С233 и азз3 и резул ьтат-С23 /азз -Iss поступает на выход

0

регистра 15 1. В блоке 1,2 на входы умножителя 30.2 поступают и Ьз13 и результат поступает на второй вход сумматора 29.2, на первый вход которого поступает djj и результат 1««Ьзг + dn dn4 Хц записывается в узел 23.2 и появляется на первом

5 выходе устройства. В блоке 1.3 на входы умножителя 30.3 поступают (52 и Ьз12 и результат поступает на второй вход сумматора 29.3, на первый вход которого поступает d2r и результат 52 bsi2 + dzi2 d2i3 посту0 пает в узел 34,3 и в регистр 35.3. На вход коммутатора 32.3 поступает Ьз23 и записывается в регистры 25.3 и 26.3. В блоке 1.4 на входы умножителя 30.4 поступают д2 и Ьз22 и результат поступает на второй вход сум5 матора 29.4, на епрвый вход которого поступает di22 и результат 1л2 bi22 + di22 di23 записывается в 34,4 и в регистр 35.4.

В тринадцатом такте в блоке 1.2 на входы умножителя 30.2 поступает Iss и Ьз13 и

результат поступает на второй вход сумматора 29.2, на первый вход которого поступает d2i3, и сумма IKJ Ьзг + dai d2i4 Xzi записывается в узел 34.2 и появляется на первом выходе устройства. В блоке 1.3 на входы умножителя 30.3 поступают АЗ и Ьз23 и результат поступает на второй вход сумматора 29.3, на первый вход которого поступает di23 и результат 4з«Ьз2 + di23 di2 ° Xi2 записывается в узел 34.3 и появляется на втором выходе устройства. В блоке 1.4 на входы умножителя 30.4 поступает 52 и Ьз2 и результат поступает на второй вход сумматоре 29.4, на первый вход которого поступает d222 И результат I52 Ь322 + d22 d22

поступает в узел 34.4 и в регистр 35.4.

В четырнадцатом такте в блоке 1.3 на входы умножителя поступают БЗ и Ьз2 и результат поступает на второй вход сумматора 29.3, на первый вход которого поступает d223 и резул ьтат Iss 032 + d223 d22 Х22 появляется на втором выходе устройства.

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

+р + (р -1) (п - 2) + тактов, причем

элементы результирующей матрицы X выдаются на выходы устройства последние р + г-. -1 тактов (при этом с k-ro выхода устройства выдается k-й столбец матрицы X (к 1, С)) аналогично поступлению исходных элементов матриц В и D на соответствующие входы устройства. Однако в случае решения потока аналогичных задач, период работы устройства составляет t T-(p + r-1) тактов,

т.е. 2п + 1 + (р -1) (п - 2) + тактов.

IЈ.

Это означает, что первый элемент а очередной объединенной матрицы можно пода вать через t тактов после подачи элемента аи предыдущей объединенной матрицы. В нашем случае Т 14, t 11, следовательно, элементы следующей матрицы можно начинать подавать на вход устройства {вместе с импульсом запуска) с двенадцатого такта. Формула изобретения Устройство для операций над матрицами, содержащее п + г операционных блоков, где п и г - порядки обрабатываемых матриц, и блок синхронизации, причем вход запуска устройства подключен к входу запуска блока синхронизации, первый и второй выходы которого подключены соответственно к первому и второму управляющим входам первого операционного блока, с первого по (п + г)-й входы элементов обрабатываемых матриц устройства подключены соот ветственно к первым информационным

входам операционных блоков с первого по (п + г)-й, первый, второй и третий выходы а-го

операционного блока (где а 1п + г - 1)

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

0 первого по (п +г- 1)-й результата устройства, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет частичного выбора ведущего элемента при вычислении выра5 жений вида (СА В + D), где А матрица размерностью (п хг). В -матрица размерностью (п Ј г), С - матрица размерностью (pi Xn), D - матрица размерностью (р Хг), в нем пятый выход b-го операционного блока (где

0 b - 2 п + г - 1) подключен к третьему

управляющему входу (Ь + 1)-го операционного блока, четвертый выход первого опера- ционного блока подключен к третьему управляющему входу второго операционнб5 го блока, шестой выход С-го операционного

блока (где С 3 n -f r) подключен к

третьему информационному входу (С - 1)-го операционного блока, шестой выход второго операционного блока подключен к

0 второму информационному входу первого операционного блока, первый вход константы устройства подключен к третьему информационному входу первого операционного блока и к четвертым информационным вхо5 дамоперационныхблоковсвторогопо(п + г}-й, второй вход константы устройства подключен к пятым информационным входам операционных блоков с второго по (п + г)-й, третий выход блока синхронизации подклю0 чен к входам синхронизации операционных блоков с первого по (п + г)-й, при этом первый операционный блок содержит три коммутатора, счетчик, триггер, делитель, четыре элемента задержки, узел задержки,

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

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

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

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

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

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

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

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

/K/IV/JV ( /jv

i it

, i i i

i I Г ММ

Устройство для операций над матрицами относится к автоматике и вычислительной технике и может быть использовано при построении специализированных, в том числе и систолических устройств. Целью изобретения является расширение функциональных возможностей за счет частичного выбора ведущего элемента при вычислении выражений вида + D (с помощью алгоритма Фаддеева), где X n, г, ft n, X г - матрицы. Устройство для операций над матрицами содержит n Ar операционных блоков и блок синхронизации. 4 ил.

/iv/jv/M /jv

;. i it

i i i «

.t. i iv i

«si

v/ W ч

л

J 8

Т