Устройство для операций над матрицами

(19) 06 Р 15/3 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ ПРИ ГКНТ СССРОПИСАНИЕ ИЗОБРЕТЕНИЯ АВТОРСКОМУ СВИДЕТЕЛЬСТВ(71) Киевский политехнический институт им.50-летия Великой Октябрьской социалистической революции(56) 1, Авторское свидетельство СССР 3 Ф 1443003, кл, 0 06 Р 15/347, 1988.2. Авторское свидетельство СССР М 1226484, кл. О 06 Р 15/347, 1986.(54) УСТРОЙСТВО ДЛЯ ОПЕРАЦИЙ НАД МАТРИЦАМИ Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специалйзйрованных, в том числе и систолических, устройств, предназначенных для выполнения операций над матрицами.Известно устройство для операций над матрицами, содеРжащее связанные соответствующим образом и операционных блоков (где и - порядок обрабатываемых матриц), иэлементов задержки и распределитель импульсов, подключенный к управляющим входам всех операционных блоков 1. Устройство позволяет выполнять 03 разложение либо обращение исходной матрицы, или решать систему из и линейных алгебраических уравнений методом Жордана-Гаусса с периодом 2 п тактов.Недостатками этого устройства являютсд большие аппаратурные затраты, а также сравнительно невысокая точность вычислений из-за реализации всех алгоритмов без выбора ведущего элемента.(57) Устройство для операций над матрицами относится к автоматике и вычислительной технике и может быть использовано при построении специализированных, в том числе и систолическйх устройств. Целью изобретения является расширение функциональных возможностей за счет частичного выбора ведущего элемента при вычислении выражений вида СА В+ О (с помощью ал горитма фаддеева), где Ап )( и, Вп )(г, Сри, Ор )( г - матрицы. Устройство для операций над матрицами содержит и Нг операционных блоков и блок синхронизации, а ил,Наиболее близким к предлагаемому изобретению по технической сущности яв- Я ляется устройство для умножения матрицы на вектор, содержащее и последовательно соединенных процессорных элементов и блок управления, соединенный с первым 4 процессорным элементом 2. Оно выбрано 00 в качестве прототипа.ЬНедостатком прототипа являются егонебольшие функциональные возможности. 0. Целью изобретения являетсярасширение функциональных возможностей устройства за счет частичного выбора ведущего элемента при вычислении выражений вида ффСА В + О, где Ап )( и, Впг, Ср) и и 0 р Хг - матрицы (в частном случае, при г = 1, р = 1 матрицы С, В и матрица О могут быть векторами размерностью и и скаляром соответственно).На фиг, 1 представлена структурная схема устройства для операций над матрицами; на фиг, 2 - структурная схема первого операционного блока (ОБ); на фиг. 3 - структурСоставитель О.МасРедактор М,Кузнецова Техред М,Моргентал Подписноепо изобретениям и открцтиям при ГКНТ С-35, Раушская наб., 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 Заказ 4366 Тираж ВНИИОИ Грсударственного комите 113035, Москва.наясхема 1-гооперационногоблока(1=2,й+г); подключен к первому информационномуна фиг. 4 - структурная схема возможного входу коммутатора 8, выход которого подварианта построения блока синхрониза- ключен к первым информационным входам ции. второго коммутатора 11, третьего коммутаустройство для операций над матрица тора 12 и узла сравнения 10, выход которого ми содержит ОБ 1.1-1.(п+ г) и блок синхро- подключен к первому входу элемента И 13, низации 2, причем вход запуска устройства выход которого подключен к первому входу подключен ко входу запуска блока синхро- элемента ИЛИ 5, выход которого у подклюнитзации 2,петрвыйивтоцройвйходыкоторогочен к управляющим входам коммутаторов подключены соответственно к первому и вто 11 и 12 и ко входу третьего элемента задеррсййуа"управляющимт входам"первого ОБ, с жки 14,выходкоторогоподключенковторопгервечгойо(п+г)-й входы элементовобрабо- му выходу ОБ 11, выход коммутатора 11 тываемыуматриц устройства подключены со- подключен к информационному входу узла ответственно к первым йнформационным задержки 6, первыйвыходкоторогоподклювходам ОБ 11-Цп + г), первый, второй и 15 чен ко входучетвертого элемента задержки трЕтИй ВЫХОДЫ ОБ 1.а ГДЕа - 1, ., П+ Г -1) 17, ВЫХОД КОтОрОГО. ПбдуКЛтЮЧЕН КО ВХОду Заподключены соответственно к первомууп-. писи/считывания первого регистра 18, ко равляющему, второму управляющему и ко: . входу декремента счетчика 9 и ко:входу усвторому информационному входам ОБ 1.-" тановки в ноль триггера 4, выход которого а+ 1, четвертые выходы ОБ 1.2, л +. гг 20 подклоченхо второму входуалемента И 3; подключены соответственно к выходам С второйитретийинформационные входы ОБ, первого пго(п+ г)-й результата устройства, 1.1 подклЮчены соответственно ко второму пятый выход ОБ 1;Ь где Ь = 2, и + г - 1) информацгионхнему входу коммутатора 8 и к подключенг к третьему управляющему входу информационному входу:счетчика 9, инфор- ОБ 1.(Ь+1), чЕтвтертый выход ОБ 1.1 подклю мационный выход которого подключен ко чен к третьемууправляющему входу ОБ 1.2, второмууправляющему входу узла задержшестой вйход ОБ 1,с (где с = 3, ; и + г) . ки 6; второй выход которого подклцочен к подключен к третьему информационному первому информационному входу делителя входу ОБ 1.с - 1), шестой выход ОБ 1.2 16,выходкнототроцгоподключенкинфоргмациподключен ко второму информационному 30 онному входу второгго регистра 15, выход входу ОБ 1.1; первый вход констайты уст- -которого подклгючей к третьему выходу ОБ ройства подключен к третьему информаци,1, выход коммутатора 12 подключен к инонному входу ОБ 1.1 и.к четвертым формационнохмууувходутгретьегоргегистра 19 информационным входам ОБ со второго по . и к информационному входу рчегитстрь 18, (и+ г)-й, второй вход константы устройства 35 выход которсго подключен ко второму ин подключен к пятым информационным вхо- формационйомту входу делителя 16, выход дам ОБ совторого по (и + г)-й, третий вйход . регистра 19 подклмючен ко вторым инфторма. блока синхронизации 2 подключен ко вхо- циойныМ входам коммутаторов 11 и 12 идамсинхронизации ОБ с первого по(п+ г)-й, узла сравнения 10, входсинхргойизации ОБ при этом ОБ 1.1 содержит первый элемент 40. 1.1 подключен ко входамсинхронизации задержки 3, триггер 4, элемент ИЛИ 5, узед триггера 4, узла зздекржки 6, регистра 18 и задержки 6, второй элемент задеркки 7, счетчика 9, при этом каждый ОБ 1 Л(=2 и+г) первый коммутатор 8, счетчик 9; узел срав-содержит первый элемент задержки 20;,г нения 10, второй 11 и третий 12 коммутато- первый 21 ивторой 22 коммутаторы, второй ры, элемейт И 13, третий элемент задержки 45 элемент задержки 23, первый узел задерж, второй регистр 15, делитель 16, четвер- ки 24, второй 25 и первый 26 регистры, третый элемент задержки 17, первый"фетистртий элемент задержки 27, счетчик 28, 18,третий регистр 19, причем первыйуправ-сумматор 29, умножитель 30, четвертый реляющий вход ОБ 1.1 подключен ко входу гистр 31, третий коммутатор 32, четвертый первого элемента задержки 3, выход кото элемент задержки 33, второй узел задержки рогоподключен к информационному входу 34, третий регистр 35, причем в каждом ОБ триггера 4, к первому входу элемента ИЛИ . 1 Л первый управляющий вход ОБ подклю, к первому управляющему входу узла за- чен ко входу первого элемента задержки 20, держки 6 и к первому выходу ОБ 1,1, второй выход которого подключен к первомууправуправляющий вход которого подключен ко 55 зияющему входу первого узла задержки 24 и входу второго элемента задержки 7, выход к первому"выходу ОБг 1,1, второй управляю- которого подключен к управляющему входу щий вход которого подключен к управляю- первого коммутатора 8, ко входу режима щим входам первого 21 и второго 22 счетчика 9 и к четвертому выходу ОБ 1.1, коммутатораиковходувторогоэлемента 23 первый информационный вход которого задержки, выход которого подключен ко1784997 510 2) обращение матрицы 20 25 30 35 40 регистров 25, 31 и 35 50 второму выходу ОБ 1., первый информационный вход которого подключен к первому информационному входу третьего коммутатора 32, выход которого подключен к первым информационным входам коммутаторов 21 и 22, выход коммутатора 21 подключен к информационному входу узла задержки 24, первый и второй выходы которого подключены соответственно к первому информационному входу сумматора 29 и ко входу третьего элемента задержки 27, выход которого подключен ко входу записи/считывания первого регистра 26 и ко входу декремента счетчика 28, информационный выход которого подключен ко второму управляющему входу узла задержки 24, выход коммутатора 22 подключен к информационному входу регистра 26 и к информационному входу второго регистра 25, выход которого подключен ко вторым информационным входам коммутаторов 21 и 22, выход регистра 26 подключен к первому информационному входу умножителя 30, выход которого подключен ко второму информационному входу сумматора 29, информационный выход которого подключен к информационным входам третьего регистра 35 и второго узла задержки 34, второй информационный вход ОБ 1. подключен ко второму информационному входу умножителя 30 и к информационному входу четвертого регистра 31, выход которого подключен к третьему выходу ОБ 1 третий, четвертый и пятый информационные входы которого подключены соответственно. ко второму информационному входу коммутатора 32, к информационному входу счетчика 28 и к управляющему входу узла задержки 34, выход которого подключен к шестому выходу ОБ 1 четвертый выход и третий управляющий вход которого подключены соответственно к выходу регистра 35 и ко входу четвертого элемента задержки 33, выход которого подключен к управляющему входу коммутатора 32, ко входу режима счетчика 28 и к пятому выходу ОБ 1., вход синхронизации которого подключен ко входам синхронизации узлов задержки, сумматора, умножителя, счетчика и регистра 26 и ко входам записи/считывания Устройство для операций над матрицами предназначено для вычисления с помощью алгоритма Фаддеева выражения вида Х = СА В + О, где в общем случае А(п Хп=(ац), В =и Хг=(Ьа), Ср Хп-(сц),Рр Х и " (б к) - матрицы. представленныев виде объединенной матрицы: причем суть алгоритма сводится к тому, что после обнуления в объединенной матрице нижнего левого квадранта (т.е. элементов матрицы - С), в правом нижнем квадранте (на месте матрицы 0) получаем искомый результат Х(рг (см. ,6, йазЬ, Я.Напзеп, пзобйеб адогйе аког сОпсоггепт ехесщоп о 1 пеаг аЯеЬга орегатопз // ЕЕЕ Тгапз. Соп 1 р., ч. 37, М 2, РеЬк. 1988, р.130), Фактически это выражение К - СА 1 В + Р позволяет решать дополнительно еще несколько задач, а именно;1) решение системы линейных алгебраических уравнений с несколькими (или одной, в зависимости от размерности В/ правыми частями: Х = А В при С = 3, 0-0; Х= А 1 при С = В = 1, 0 = 0;,3) умножение матриц (или матрицы навектор, в зависимости от размерности В) Х=С ВприА=1,0=0; 4) умножение со сложением матриц Х=С В+РприА=;5) адаптивная фильтрация, при которойиспользуется выражение Х = СА + 0 при В = , где- единичнаяматрица.Обнуление нижнего левого квадрантаобъединенной матрицы можно осуществить, применяя исключение Гаусса, до приведения матрицы А к верхнетреугольному виру. Тогда автоматически на место матрицы -С получится нулевая матрица. При этом, с целью обеспечения численной устойчиво сти вычислений, преобразование матрицы Авыполняется по алгоритму исключения Га- усса с частичным выбором ведущего элемента по столбцу, Это означает, что на -м шаге ( - 1, и - 1) алгоритма Гаусса исключению элементов а О =+ 1, ф принадлежащих исходной матрице А=А (при=1) или уже частично преобразованной матрице А (при1), предшествует последовательное сравнение их с элементом ав, и,если оче 5 редной элементаап , осуществляется перестановка )-й и -й строк. т.е, 1-я строка становится )-й, и наоборот. В противном случае перестановка строк не происходит, Только после окончания всех (на данном1784997шаге) операций сравнения и перестановок блока 2 - по переднему фронту синхроим(т,е, процесса выбора ведущего элемента) пульса, т.е. в начале такта. Условимся также,начинается процесс исключения элементов что изменение состояния счетчиков 9 и 28ар и преобразования строк с 0+ 1)-й по п-ю происходит по положительному перепадуматрицы А (а в нашем случае еще и В), 5 сигнала на их декрементирующих входах,1заключающийся в попарном суммировании Считаем, что перед началом вычисленийкаждой из этих строк с 1-й строкой (объеди- (а + 1)-е, в разряды всех регистров узла 6.1ненной матрицы в нашем случае), пред- установлены в нулевое состояние,варительно умноженной на коэффициент1Импульс пуска, поступающий на входпц - -ая /ан. Однако поскольку в объединен запуска устройства, устанавливает в едининой матрице под матрицей А находится мат- цу ВЯ-триггер 40, а также поступает на входрица -С, которую необходимо привести к режима счетчика 36, в который записываетнулевой матрице, никаких перестановок ся значение (и+ р - 1) - 4, и (через элементстрок матриц С и 0 со строками матриц А и ИЛИ 39) на вход режима счетчика 37,В производить. нельзя. Вследствие этого ус В первом такте по переднему фронтутройствоосуществляет выбор ведущегоэле- синхроимпульса в счетчик 37 записываетмента среди элементов 1-го столбца ся информация с выхода счетчика 36, т.е.матрицыА(йа 1-мшаге),а процесс исключе- (и + р - 1), и на выходе отрицательногоония осуществляетсреди элементов 1-го стол- . переноса счетчика 37 - единица а такжебца матриц А и С, т.е. среди элементов 20 устанавливаются в единицу элементы эа 1-го столбца всей объединенной матрицы держки 3,1, 7.1 и 14 1, после чего в счетчик( = 1, и -1). Отметим также, что все признаки 9.1 записывается значение (и - 1) =.2. Кромеперестановки строк запоминаются и пере- того, элемент а 11 = а 11. исходной матрицыдаются между ОБ в качестве элементов поступает на первый вход блока 1.1 и, пройнижйей треугольной матрицы перестановок 25 дя через коммутаторы 11,1 и 12,1,записывач=чД. Отметимтакже,что за ишагов,ется в конце такта в регистр 19,1 (наалгоритма Гаусса обнуляются и -1 столбцОв управляющих входах обоих коммутаторовобъединенной матрицы. Однако для пол- единицы), а единица с выхода элемента за- сучения правильного результата необходи- держки 3.1 записывается в (е+ 1)-йразряд, мо обнулить и и-й столбец матрицы С. 30 первого регистра(Р 1) узла 6,1,Поэтому в данном случае алгоритм Гаусса Во втором такте Счетчик 37 уменьшаетимеет и-й шаг, на котором отсутствует про- . свое значение на единицу; В блоке 1,1 нэцесс выбора ведущего элемента (элемент выходе элемента, задержки 3.1 - нуль, Маа" сразустановится ведущим,т,к."егонес" выходе триггера 41,появляется единица,чем сравнивать), а процесс. исключения про-: 35 содержимое (е+ 1)-го разряда Р 1 узла 6.1изводитсяаналогично предыдущим шагам переписывается в Р 2 узла 6,1, Злемеалгоритма; а 21 = аг поступает через коммутатор 8.1 наПоступление исходных данных органи- входы коммутаторов 11.1 и 1,Ц,и узла сравзовано следующим. образом, На 1-й вход нения 10.1, на другиевходы которых постуустройства 0 =1, й) каждый такт поступает 40 пает а 11, пустьац 1а 211. Тогдаэлемент 1-.го столбца обьединенной матри" нуль с выхода узла сравнения 10.1 (признакцы,начинаясэлементааяизаквнчивая-Срь перестановки строк) поступает через элена (п + Ц-й вход устройства (к 1, Я - менты 13.1 и 5.1 в элемент задержки 14.1 ианалогично, начиная с элемента Ьь и закан- на управляющие входы коммутаторов 11.1 ичивая ярк, В свою очередь, элементы столб 12.1, вследствие чего а 11 переписываетсца объединенной матрицы постуйают на регистр 19,1, а ааз записывается в Р 1 узласоответствующие входы устройства со сдви. 6 Л, В блоке 1,2 в счетчик 28;2.записываетсягом один такт, т.е, элемент а 11 поступает на значение п -1, элементы задержки 20;2,23,21-й вход устройства в 1-м такте его работы, а и 33.2 устанавливаются в единицу. На перэлемент Ь ь - в(л+ К) м такте работы устрой вый информационный вход блока 1.2 посту-.пает элемент ац - а 12 и. пройдя черезРассмотрим работу устройства. Для коммутатор 32,2, поступает на входы коммупростоты описания и без потери общности таторов 21,2 и 22.2 и в конце такта записыположим п - 3, р = г = 2, Условимся, что вается в регистр 25.2,прием информации вовсе регйстры, в том 55 В третьем такте счетчик 37 уменьшаетчисле в регистры узлов задержки, в элемент- свое значение на единицу. В блоке 1.1 наты задержки 14 и 27 всех: операционных выходе элемента задержки 17.1 появляетблоков осуществляется по заднему фронту ся единица. Элемент аз 1 - аз 1 поступаетсинхроимпульса, т.е, в конце такта, а во все через коммутатор 8 1 на входы коммутатоостальные триггеры всех ОБ и счетчик 37 . ров 11.1 и 12,1 и узла сравнения 10,1, надругие входы которых поступаета,:. Пусть рого поступает ад с Р 2 узла 24.2 и суммааза 11 . Тогда единица с выхода г 1 азг +агг =а 22 поступаетврегистр 35,2 узла сравнения 10,1 записывается в эле- и узел 34.2.Элемент-С 12 -С 12 поступает мент задержки 14.1 и управляет коммутато- нэ входы коммутаторов 21.2 и 22.2 и записырами 11.1 и 13.1, вследствиЕ чего а 111 5 вается в Р 1 узла 24.2. В блоке 1.3 элемент записывается в Р 1 узла 6,1 (а 21 переписы- задержки 27.3 устанавливается в единицу.вается в Р 2 узла 6.1), а аз 1 записывается в Элемент азз = азз поступает на вход коммурегистры 18,1 и 19,1. 8 блоке 1,2 единица из татара 32.3 и записывается в регистры 25.3 (гп+ 1)-го разряда Р 1 узла 24,2 переписыва- и 26.3, а 2 з переписывается в Р 2 узла 24.3, ется в Р 2 узла 24,2. Элемента 22=а 2 г посту а 1 з записывается вР 1 узел 24,. В блоке 1.4 пает на вход коммутатора 32.2, с выхода элемент Ь 21= Ь 21 поступает на вход коммукоторого поступает на входы коммутаторов татора 32.4 и записывается в Р 1 узла 24.4, э 21,2 и 22,2 и в конце такта записывается.в Ь 11 перезаписывается в Р 2 узла 24.4. В регистр 25,2 (а 12 переписывается в Р 1 узла блоке 1.5 в счетчик 28.5 записывается зна 24.1). В блоке 1.3 элементы задержки 20.3, 15 чение и -1. Элемент Ь 12 = Ь 121 поступает на 23.3 и 33.3 устанавливаются в единицу, ввход коммутатора 32.5 и, пройдя коммутасчетчик 28,3 записывается значение и - 1. тор 21.5, записывается в узел 24.5На первый вход ОБ 1.3 поступает элемент В шестом такте а 222 из узла.34,2 постуа 1 з =.а 1 з и, пройдя через коммутаторы 32.3, . пает на первый вход блока 1,1 и через ком 21.2 и 22.2, в конце такта записывается в 20 мутатор 12,1 записывается в регист 1 о 19,1.регистр 25.3, Навход делителя 16 1 поступает -С 11 и аэ 1В четвертом такте. счетчик 37 уменьшает и результат С 11 /аз 1 = 141 поступает на входсвое значение на единицу. В блоке 1.1 триг.- регистра 15,1. В блоке 1,2 на вход умножигер 4.1 устанавливается в нуль. На входы ком-теля 30,2 поступает 1 з 4 и аз 2, умножается Й мутаторов 11.1 и 12,1 поступает -С 11 = -С 11 и 25 поступает нэ второй вход сумматора 29.2, на записывается в Р 1 узла 6.1, а - пережи- первый вход которого с выхода узла 24.21 Дсывается в Р 2 узла 6.1, а 21 поступает на поступаета 12 и сумма 1 з 1 азг +а 12 -аз 2 первый вход делйтеля 16.1, на второй вход передается на выход регистрЭ 35,2 и запикоторого поступает аз 1 из регистра 18.1.: сывэется в 34,2. На вход коммутатора 32,21Делитель 16.1 выполняет деление и резуль поступает -С 22 = -С 22 . В блоке 1,3 на входы . тат -а 21 /аз 1 = 121, пройдя регистр 15.1, по- умножителя 30.3 поступает 121 и азз 1, резульступаетнаеговыход, Вблоке 1.2 на выходе тат поступает на второй вход сумматора элементазадержки 27.2-единица. Элемент 29,3, на первый вхор которого поступает аз 2 = азг поступает на вход коммутатора . агз и сумма 121 эзз + агз - агзг записы 32.2 и, пройдякоммутатор 22.2., записывает вэется в регистр 35;3 и в узел" 34,3. На ся в регистры 25.2 и 26.2. 8 блоке 1.3 на. вход коммутатора 32.3 поступает элевыходе элемента задержки 20,3 - нуль. Нэ мент -С 1 з = -С 1 з . В блоке 1.4 на вход комму- вход коммутатора 32.3 поступает элемент татара 32,4 поступает элемент Ьз 1 = Ьз 1 и, а 2 З =,а 2 З и, пРойдя коммутатор 21.3, зэпи- пройдя коммутатор 22.4, записывается в ресывается в Р 1 узла 24.3. В блоке 1,4 на 40 гистры 25,4 и 26.4,8 блоке 1.5 навходкоммувыходе элементов задержки 20.4,23,4 и 33.4 татора 32,5 поступает Ь 22=Ьг 21 и записывается устанавливается единица. В счетчик 28,4 за- " в Р 1 узла 24,5.писываетсяэйачениео,ЭлементЬ 11=Ь 11 В седьмом такте вблоке 1.1 на входы1поступает на вход коммутатора 32.4 и, прой-: делителя 16;1 поступает -С 211 и аз 1 и редя коммутатор 22,4,записывается врегистр 45 зультат Сг 1 /аз 1 = 151 поступает на выход 25.4, регистра 15.1. На вход коммутатора 8.1 поВ пятом такте счетчик 37 уменьшает ступаетазг и всхемесравнения происходгит2свое значение йа единицу, В блоке 1.1 на сравнение агг иазг . пустьазг1 а 22 ,2входы коммутаторов 11.1 и 12.1 поступает. тогда азг записывается в регистры 18.1 и элемент -С 21 "-С 21 и записывается в Р 1 50 19.1, а агг -в Р 1 узла 6.1. В блоке 1.2 нагузла 6.1 а -С 11 переписывается в Р 2 узла входы умножителя 30.2 поступает 141 и азг 6,1. На вход делителя 16,1 поступают а 11 и и результат подается нэ второй вход сумма 1аз 1 и результатделения -а 11/аз 1 "1 з 1 по- тора 29.2 и сумма 141 азг - С 12 = С 12 ступает на выход регистра 151, с выхода записывается в регистр 35,2 и в узел 34.2.котброго 121 поступаетна входблока 1.2 и на 55 На вход коммутатора 32.2 поступает элевторой вход умножителя 30,2, на первый мент агз, В блоке 1.3 на входы умножителя вход которого поступает азг с выхода реги.3 поступает 1 з 1 и азз, результат поступастра 26.2, результат 1 г 1 аз 2 поступает на ет на второй входг сумматора 29,3, сумма второй сумматор 29.2, на первый вход кото з 1 аЗз 1+ а 1 З 1.= аЗЗ поступаЕт в региСтР 35.3 .1784997и в узел 34.3. На вход коммутатора 32,3 пает б 21 и результат 151 Ь 31 + бг = б 2121 1: поступает -Сгз и через коммутатор 21,3 за- записывается в регистр 35,4 и в узел 34.4. В1писывается вузел 24,3, В блоке 1.4 на входы блоке 1.5 на входы умножителя 30,5 постуумножителя 30,4 поступает 1 г 1 и Ьз 1, резуль- пает 41 и Ьзг и результат поступает на вто-:1 1тат поступает на второй вход сумматора, 5 рой вход сумматора 29.5, на первый вхофсумма 121 ЬЗ 1+ Ь 21 = Ь 21 поступает на которого поступает б 12 и результат 141 Ьзг1 2выход регистра 35.4 и в узел 34.4. На вход + б 12 = б 12 записывается в регистр 35;5 и в1 2коммутатора 32.4 поступает элемент узел 34.5,б 11= б 11 и, пройдя коммутатор 21.4, запи- . В одиннадцатом такте в блоке 1.1 насывается в узел 24.4, В блоке 1.5 на вход 10 входы делителя 16,1 поступает С 1 зз и аззз икоммутатора 32.5 поступает элемейт результат-С 1 з /азз 14 з поступает на выход3 3Ьз 2 - Ьз 2 и зайисывается в регистры 25.5 и регистра 15,1, на входы умножителя 30.2126,5. :..: . поступает 52 и азз и результат поступает2В восьмом такте в блоке 1.1 на входы на второй вход сумматора 29.2, на первыйделителя 16.1 поступает а 22 и азг и резуль вход которого поступает Сгзг и результат2 2тат а 22 /азг = 1 з 2 поступает на выход реги азз + С 2 з Сгз поступает в регистр2 2 2 2стра 15,1. В блоке 1.2 на входы умножителя 35,2 и в узел 34.2. На вход коммутатора 32.2330.2 поступает 151 и эзг., результат йоступа- поступает Ьз и записывается в регистрыет на второй вход сумматора 29.2 и сумма 25.2 и 26.2, В блоке 1,3 на вхОды умножителя151 азг -,Сгг. = Сгг записывается в узел 20 30.3 постуйает 142 и Ь 312 и результат посту- .г34.2, В блоке 1.3 на входы умножителя 30,3 пает на второй вход сумматора 29,3, на перпоступает 141 и азз и результат умножения вый вход котоого поступает.б 112 ипоступает йа второй вход сумматора 29.3, на результат 142 Ьз 1 + б 11 - б 11 записываетсяпервый вход 1 которого поступает-С 1 з исум- в регистр 25.3 и узел 34;3. В блоке 1,4 нама 141 азз. - С 1 з = С 1 з, принимается в 25 входы умножителя 30,4 поступает 1 зг и Ьзгг1 2регистр 35,3 и узел 34.3. На второй вход и результат поступает на второй вход сумкоммутатора 32.3 с выхода узла 34.4 посту- матора 29.4,на первый вход которого поступавет элемент Ь 21 и, проидя коммутатор пает б 22 и результат 151 Ь 31 + б 22 = б 222 1121.3, записывается в узел 24,3. В блоке 1.4 записывается в регистр 35,4 и в узел 4.4. Вна входы умножителя 30.4 поступает 1 з 1 и 30 блоке 1,5 нэ входы умножителя 30.5 постуЬз 1 и результат поступает на второй вход пает 151 и Ьз и результат поступает на .сумматора 29,4, на первыйвход 1 которого по-второй вход сумматора 29.5, на первыйступает Ь 11 и результат 1 з 1 Ь 31 + Ь 11 = Ьз 1вход которог 1 о поступает бгг и результат1:, 1 2записывается врегистр 35.4 и в Р 1 узла 34.4, 151Ьз 1 +бг 2 =б 22 записывается в регистрВ блоке 1,5 на вход умножителя 30,5 посту 35.5 и: в узел 34.5.пает 121 и Ьзз и результат поступает на В двенадцатом такте в блоке 1.1 на вховторой. вход сумматора 295, нэ первый. ды делителя 16 Л поступает Сгз и азз ивход которого поступает Ьгг и результат результат-Сгз /азз =153 поступаетна выход121 Ьз 2 + Ьгг "Ь 22 записывается врегистр регистра 15,1, В блоке 1,2 на входы умножи 1 1 235,5 и в узел 34.4. 40 теля 30,2 поступают 14 З и Ьз 13 и результатВ десятом такте в блоке 1 1 на входыпоступает"на-второй входсумматора 29,2, на.делителя 1.6 Л поступает С 222 и азг и резуль- первый вход которого". поступает бф итат-С 22 /азг - ь 52 постуйает на выход реги- результат 14 з ьз 1 + б 11 - б 11 =х 11 записы-г 23 з-. 4 41стра 15.1. На второй вход коммутатора 8 Л вается в узел 23.2 и появляется на первомпоступает азз и записывается в регистры 45 выходе устройства. В блоке 1.3 на входы:318 Л и ЙЛ. В блоке 1.2 на входыумнбжителя умножителя 30.3 поступают 52 и Ь 312 йрепоступают 142 й аззг и результат поступает зультат поступает на второй вход сумматорана второй вход сумматора 292, на первый 29.3, на первый вход которого поступаетвход которого йоступает С 13 и результат б 21 и результатж Ьз 1 +б 21 -б 213 посту 142аззг + С 13 = С 1 з поступает в регистр 50 йает в узел 34,3 и в регистр 35.3. На входг 3352 и узел 34.2. В блоке 1.3 на входы умно- коммутатора 32.3 поступает Ьз 23 и записыжителя 30.3 поступает 1 з 2 и Ь 312 и результат вается врегистры 25.3 и 26.3, В блоке 1.4 напоступает на второй входсумматора 29,3, на входы умножителя 30.4 поступают 142 и Ьз 22первый вход которого поступает Ь 21 и ре- и результат поступает на второй вход сум 2зультат 1 зг Ьз 1 + Ь 21 = Ь 31 записывается 55 матора 29,4, нэепрвыйвходкоторогопосту 2 2 3: в регистр 35,3 и узел 34.3, Вблоке 1,4 на пает б 12 и результат 142 Ь 122+ б 12 = б 123входй умножителя 30,4 поступает 151 и Ь 311 записывается в 34.4 и в регистр 35.4,и результат поступает на второй вход Сум- В тринадцатом такте в блоке 1.2 на вхоматора 29.4, на первый входкоторогб посту- ды умножйтеля 30.2 поступает 153 и Ь 313 ирезультат поступает на второй вход сумма- . тора 29.2, на первый вхозд которого поступает б 21, и сумма 5 зе Ьз 1 + б 21 = б 21 = Х 21ззаписывается в узел 34.2 и появляется на первом выходе устройства. В блоке 1.3 на 5 входы умножителя 30.3 поступают 4 з и Ьзг и результат поступает на второй вход сумматора 29.3, нэ первый вход которого поступает б 12 и результат 4 зе Ьз 2 + б 12 = б 12 Х 12 записывается в узел 34,3 и появляется на 10 втором выходе устройства. В блоке 1,4 на входы умножителя 30.4 поступает 52 и Ьз 2 и результат поступает на второй. вход сумматора 29.4, на первый вход которогог поступает бгг и результат 52 Ьзг + б 22 = бг 2 15г.поступает вузел 34,4 и в регистр 35.4.В четырнадцатом такте в блоке 1,3 на входы умножителя поступают 5 з и Ьз 2 и результат поступает на второй вход сумма- . тора 29.3, на первый вход которого поступа ет б 22 и результат 5 з ф Ьзг + бгг = б 22 - Х 22з= появляется на втором выходе устройства.На этом вычисление элементов ре-. зультирующей матрицы Х = СА "В + О заканчивается. Таким образом, полнОе 25 время реализации.алгоритма Т=2 п+,г+пй - 1+р+(р) (и -2)+ тактов, причем элементы результирующей матрицы Х выдаются на выходы устройства последние р+ г -1,тактов (при этом с М-го выхода устрой(;твавыдается 1-й столбец матрицы Х (1 = 1, г . аналогично поступлению исходных элемен- тов матриц В и О нэсоответствующие входы устройства. Однако в случае решения пото ка аналогичных задач, период работы устройства составляет с = Т -(р+ г) тактов,п(п - 11 т.е.2 п+1+(р) (и)+-тактов,ФЭто означает, что первый элемент а . оче редной обьединенной матрицы можно по. даватьчереэ тактов после подачи элементаа 11 предыдущей обьединенной матрицы, В нашем случае Т = 14, т = 11, следовательно,элементы следующей матрицы можно начи нать подавать на вход устройства (вместе с импульсом запуска) с двенадцатого такта,Формула изобретен ияУстройство для операций над матрицами, содержащее и+ г операционных блоков, 50 где и и г - порядки обрабатываемых матриц, и блок синхронизации, причем вход запуска" устройства подключен к входу запуска блока синхронизации, первый и второй выходы которого подключены соответственно к 55 первому и второму управляющим входам первого операционного блока, с первого по (п + г)-й входы элементов обрабатываемых матриц устройства подключены .соответственно к первым информационным входам операционных блоков с первого по (и + г)й, первый, второи и третий выходы а-го операционногоблока (где а = 1, , п + г - 1) подключены соответственно к первому управляющему, второму управляющему и к второму информационному входам (а+ 1)го операционного блока, четвертые выходы операционных блоков с второгоо по (и+ г)-й подключены соответственно к выходам с первого по(п+ г)-й результата устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет частичного выбора ведущего элемента при вычислении выражений вида (СА. В + О), где А - матрица размерностью(п хг), В - . матрица размерностью (и Ф г), С - матрица размерностью (р Х и), О - матрица размерностью (р Х г), в нем пятый выход Ь-го операционного блока (где Ь = 2 п + г - 1) подключен к третьему управляющему входу (Ь + 1)-го операционного блока, четвертый выход первого операционного блока подключен к третьему управляющему входу второго операционнбго блока, шестой выход С-го операционного блока (где С = 3, , п + г) .подключен к третьему информационному входу (С - 1)-го операционного, блока, шестой выход второгооперационного блока подключен к второму информационному входу первого операционного блока, первый вход константы устройства подключен к третьему информационному входу первого операционного блока и к четвертым информационным входам операционных блоков с второго по (п + г)-й, второй вход константы устройства подключен к пятым информационным входам оперЩионных блоков с второго по (и + г)-й, третий выход блока синхронизации подключен к входам синхронизации операционных блоков с первого по (и + г)-й, при этом первый операционный блок содержит три коммутатора, счетчик, триггер, делитель, четыре элемента задержки, узел задержки, узел сравнения, три регистра, элемент И и элемент ИЛИ, причем первый управляю- щий вход первого операционного блока подключен к входу первого элемента задержки, выход которого подключен к информационному входу триггера, к первому входу элемента ИЛИ, к первому управляющему входу узла задержкии к первому выходу первого операционного блока, второй управляющий. вход которого подключен к входу второго элемента задержки, выход которого подключен к управляющему входу первого коммутатора, к входу режима счетчика и к четвертому выходу первого операционного блока, первый информационныйвход которого подключен к первому информационному входу первого коммутатора, выход которого подключен к первым информационным входам второго коммутатора, третьего коммутатора и узла сравнения, выход которого подключен к первому входу элемента И, выход которого подключен к первому входу элемента ИЛИ, выход которого подключен к управляющим входам второго и третьего коммутаторов и к входу третьего элемента задержки, выход которого подключен к второму выходу первого операционного блока, выход второго коммутатора подключен к информационному входу узла задержки, первый выход которого подключен к входу четвертого элемента задержки, выход которого подключен к входу записи-считывания первого регистра, к входу декремента счетчика и к входу установки в "0" триггера, выход которого подключен к второму входу элемента И, второй и третий информационные входы первого операционного блока подключены соответственно к второму информационному входу первого коммутатора и к информационному входу счетчика, информационный выход которого подключен к второму управляющему входу узла задержки, второй выход которого подключен к первому информационному входу делителя, выход которого подключен к информационному входу второго регистра, выход которого подключен к третьему выходу первого операционного блока, выход третьего коммутатора подключен к информационному входу третьего регистра и к информационному входу первого регистра, выход которого подключен к второму информационному входу делителя, выход третьего регистра подключен к вторым информационным входам второго коммутатора, третьего коммутатора и узла сравнения, вход синхронизации первого операционного блока подключен к входам синхронизации триггера, узла .задержки, первого регистра и счетчика и к входам записи-считывания второго и третьего регистров, при этом каждый операционный блок с второго по (и + г-й содержит три коммутатора, счетчик, два узла задержки, сумматор. умножитель, четыре регистра и четыре элемента задержки, причем в каждом операционном блоке с второго по п+ г)-й первый управляющий вход операционного блока подключен к входу первого элемента задержки, выход которого подключен к первому управляющему входу первого узла задержки и к первому выходу операционного блока, вто го коммутатора, выход которого подключен к первым информационным входам перво го и второго коммутаторов, выход первого 15 20 управляющему входу первого узла задерж 30 40 соответственно к второму информационно 5055 рой управляющий вход которого подключен к управляющим входам первого и второго коммутаторов и к входу второго элемента задержки, выход которого подключен к второму выходу операционного блока, первый информационный вход которого подключен к первому информационному входу третьекоммутатора подключен к информационному входу первого узла задержки, первый и второй выходы которых подключены соответственно к первому информационному входу сумматора и к входу третьего элемента задержки, выход которого подключен к входу записи-считывания первого регистра и к входу декремента счетчика, информационный выход которого подключен к второму ки, выход второго коммутатора подключен к информационному входу первого регистра и к информационному входу второго регистра, выход которого подключен к вторым информационным входам первого и второго коммутаторов, выход первого регистра подключен к первому информационному входу умножителя, выход которого подключен к второму информационному входу сумматора, информационный выход которого подключен к информационным входам третьего регистра и второго. узла задержки, второй информационный вход операционного блока подключен к второму информационному входу умножения и к информационному входу четвертого: регистра, выход которого подключен к третьему выходу операционного блока, третий, четвертый и пятый информационные входы которого подключены му входу третьего коммутатора, к информационному входу счетчика и к управляющему входу второго узла задержки, выход которого подключен к шестому выходу операционного блока, четвертый выход и третий управляющий вход которого подключены соответственно к выходу третьего регистра и к входу четвертого элемента задержки, выход которого подключен к управляющему входу третьего коммутатора, к вхОду режима счетчика и к пятому выходу операционного блока, вход синхронизации которого подключен к входам синхронизации первого и второго, узлов задержки, сумматора,.умно- жителя, счетчика и первого регистра и ко входам записи-считывания второго, третьего и четвертого регистров,