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

(5(15 6 06 Р 15 ИСАНИЕ ИЗОБРЕТЕ и инстит ой социал ий,в СР 88 СР ОСУДАРСТВЕННЫЙ КОМИТЕТО ИЗОБРЕТЕНИЯМ И ОТКРЫТИРИ ГКНТ СССР ВТОРСКОМУ СВИДЕТЕЛЬСТВУ 21) 4826157/2422) 09,04.9046) 15.06.92. Бюл. М 2271) Киевский политехническим,50-летия Великой Октябрьскстической революции72) Р,Выжиковски, Ю.С.КаневсМ.К,Клименко и О,В,Масленник53) 381,325(088,8)56) Авторское свидетельство СМ 1443003, кл. О 06 Р 15/347, 1Авторское свидетельство СК. 1509932, кл, О 06 Р 15/347, 1 Изобретение относится к вычислительной технике и может быть использовано при построении специализированных. в том числе и систолических устройств. предназначенных для операций над матрицами;Известно устройство для операций над матрицами, содержащее связанные соответствующим образом и операционныхгблоков, (п - 1) элементов задержки и распределитель импульсов,Недостатками этого устройства являются сравнительно большие аппаратурные затраты и невысокая точность вычислений,Наиболее близким к предлагаемому по технической сущности является устройство для решения матричного уравнения вида Ах= = В, содержащее связанные соответствующим образом и вычислительных блоков первого типа и п(п)/2+и г вычислительных(54) УСТРОИСТВО ДЛЯ ВЫПОЛНЕНИЯ ОПЕРАЦИЙ НАД МАТРИЦАМИ(57) Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных, в том числе и систолических устройств, предназначенных для выполнения операций над матрицами. Цель изобретения - расширение функциональных возможностей устройства за счет реализации им алгоритма Фаддеева. Устройство содержит и вычислительных блоков первого типа и и вычислительных блоков второго типа и имеет вход запуска, информационные входы и информационные выходы, 2 з.п. ф-лы. 3 ил. блоков второго типа (где и и г - размерности матриц).Недостатком этого устройства являются его ограниченные функциональные возможности,ДЦель изобретения - расширение функ- - д циональных возможностей устройства.зззззйНа фиг. 1 изображена структурная схе- л ма устройства для случая, когда п = 3. г = 2: ( ) на фиг, 2 - структурная схема вычислительного блока ВБ) первого типа; на фиг. 3- структурная схема ВБ второго типа, Устройство для выполнения операцийззай над матрицами содержит (фиг. 1) вычислительные блоки 1 первого типа и 2.ц (=1, п.= -1, и+г) второго типа, причем вход режима ВБ 1.1.1 соединен с входом запуска устройства, первый выход режима ВБ 1,Ч (где=== 1, и) соединен с выходом режима ВБ 1,(+1).0+1), второй выход режима ВБ 1.а.Ь.Кравцова ри ГКНТ СС зводственно-издательский комбинат "Патент", г, УжгорУг Я,Гагарина, 10 Заказ 2087ВНИИПИ оставитель М,Климе ехред М.Моргентал Тиражарственного комитета по изобре 113035, Москва, Ж, Рауш Подписноениям и открытияая наб., 4/5(где а = Ь = 1, и) соединен с входом режима ВБ 1.а,(Ь+1), выход режима ВБ 1.с(б+М) (где с = б = 1, и; 1=1, и+г - с) соединен с входом режима ВБ 1,с(0+1+1), информационный вход ВБ 1.1.1 подключен к первому информационному входу устройства, информациионный вход ВБ 1.1.1 (где )1 = 2, и+п) подключен к ) -му информационному входу устройства, выход результата ВБ 1. , /+1 (где ( = ), и) соединен с информационным входом ВБ 1.+1), +Я, выход результата ВБ 1.п.(п+М) (где 11 = 1, г) соединен с 11-м выходом резуп агата устройства, выход результата ВБ 1(.Д+1 с 2)(где (=) =1, и; К 2=2, и+г) соединен с информационным входом ВБ 1,+1).+12). С целью расширения функциональных возможностей устройства за счет реализации им алгоритма Фаддеева выход признака перестановки и выход деления ВБ 1.а.Ь (где а = Ь = 1, и) соединены с входом признака перестановки и входом деления ВБ 1.а.(Ь+1), выход признака перестановки и выход деление (с, сьв(-го ББ 1.с,(сьх) (где с = б = 1, и; К = 1, и+г-с) соединены с входами признака перестановки и деления В Б 1,с,(0+к+1).Вычислительный блок первого типа (фиг. 2) содержит первый 3 и второй 4 элементы задержки, ЯЯ-триггер 5, счетчик 6, регистр 7, третий элемент 8 задержки, элемент ИЛИ 9, схему 10 сравнения, первый 11 и второй 12 коммутаторы, четвертый элемент 13 задержки, блок 14 деления, блок 15 элементов задержки, элемент И 16, пятый 17 и шестой 18 элементы задержки, Вход режима вычислительного блока первого типа соединен с входом разрешения счетчика 6, входом установки в н 1 и триггера 5 и входом элемента 4 задержки, выход которого соединен с первым входом элемента ИЛИ 9. Выход счетчика 6 соединен с входом установки в и 0 и триггера 5, входом элемента 3 задержки и входом записи регистра, Выход элемента 8 задержки соединен с первым выходом режима ВБ, выход элемента 3 задержки соединен с входом элемента 8 задержки и вторым выходом режима ВБ. Выход триггера 5 соединен с первым входом элемента И 16, второй вход которого соединен с выходом элемента ИЛИ 9. Вы- ход элемента И 16 соединен с входом элемента 17 задержки и входами разрешения первого и второго коммутаторов, Выход элемента 17 задержки соединен с выходом признака перестановки ВБ, информационный вход ВБ подключен к первым информационным входам схемы 10 сравнения, первого 11 и второго 12 коммутаторов, выход схемы 10 сравнения подключен к второму входу элемента ИЛИ 9, Информацион 5 10 15 20 25 30 35 40 45 50 55 ный выход коммутатора 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А(пхп = (ац); Впхг) = (Ьк); С(рхп) = (се 1) и О(Рхг = (бек) - матРицы, пРедставленные в виде объединенной матрицы: причем суть алгоритма сводится к тому, что после обнуления в объединенной матрице нижнего левого квадранта (т.е. элементов матрицы -С), в правом нижнем квадранте (на месте матрицы О) получаем искомый результат Хрхг 1, Фактически это выражение позволяет решать дополнительно еще несколько задач.1, Решение системы линейных алгебраических уравнений с несколькими (или одной, в зависимости от размерности В) правыми частямиХ=А В при С=1,0=0.2. Обращение матрицыХ=А" при С=В=1, О=О.3. Умножение матриц (или матрицы на вектор, в зависимости от размерности В)Х= СВ при А= 1, О =О.4, Умножение со сложением матриц Х=СВ+О приА=1,5. Задача адаптивной фильтрации, которая использует выражениеХ=СА +О при В=1,где 1 - единичная матрица,Обнуление нижнего левого квадранта объединенной матрицы можно осуществить, применяя к ней СЯ-разложение или, как реализовано в предлагаемом устройстве, исключение Гаусса до приведения матрицы А к верхнему треугольному виду, Тогда автоматически на месте матрицы -С получается нулевая матрица, При этом с целью обеспечения численной устойчивости вычислений преобразование матрицы А выполняется по алгоритму исключения Гаусса с частичным выбором ведущего элеме. та по столбцу, Это означает, что на -м шаге ( = 1, и) алгоритма Гаусса исключению элементов а 0 = +1, и), принадлежащих исходной матрице А = А (при = 1) или уже частично преобразованной матрице А (при1); предшествует последовательное сравнение их с элементом а и, если очередной эле 1ментараи , осуществляется перестановка )-й и 1-й строк, т.е, -я строка ставится )-й и наоборот, В противном случае перестановки строк не происходит. Только по окончании всех (на данном шаге) операций сравнения и перестановок (т,е. процесса выбора ведущего элемента) начинается процесс исключения элементов а;, и преобразования строк с (+1)-й по и-ю матрицы А10 риц С и О со строками матриц А и В производить нельзя, Вследствие этого устройство осуществляет выбор ведущего элемента среди элементов -го столбца матрицы А(на 1-м шаге), а процесс исключения осуществляется среди элементов -го столбца матриц А и С, т,е, среди элементов -,го столбца всей объединенной матрицы ( = 1, и). Все признаки перестановки строк запоминаются и передаются между ВБ в качестве элементов нижней треугольной матрицы перестановок Ч = (/), За (и)-й шаг алгоритма Гаусса обнуляются (и) столбцов объединенной матрицы, Однако для получения правильного результата необходимо обнулить также и-й столбец матрицы -С. Поэтому в данном случае алгоритм Гаусса имееттакже и-й шаг, на котором отсутствует процесс выбора ведущего элемента (элемент апг" соазу становится ведущим, так как его не с чем сравнить), а процесс исключения производится аналогично предыдущим шагам алгоритма,Поступление исходных данных организовано следующим образом, На 1-й информационный вход устройства ( = 1, и) в каждый такт поступает элемент 1-го столбца объединенной матрицы, начиная с элемента а 1; и заканчивая -срь на (и+к)-й информационный вход устройства (К = 1, г) - аналогично, начиная с элемента Ь 1 к и заканчивая ср. В свою очередь элементы каждого столбца объединенной матрицы поступают на соответствующие входы устройства со сдвигом на один такт, т.е, элемент а 1 поступает на -й информационный вход устройства в -м такте его работы, а элемент Ь 1 к - в (и+К)-м такте работы устройства.Устройство работает следующим образом,Для простоты описания и без потери общности положим и = 3, р = г = 2, Условимся. что прием информации во все счетчики. триггеры и элементы 3, 4, 8 и 24 задержки всех ВБ происходит по переднему фронту синхроимпульса, т.е. вначале такта, а во все регистры, блоки элементов задержки и остальные элементы задержки - по заднему фронту синхроимпульса;В первом такте на вход запуска устройства поступает единичный импульс, кото 15 20 25 30 35 40 45 50 55(в нашем случае еще и В), заключающийся в попарном суммировании каждой из этих строк с -й строкой матрицы А (объединенной матрицы в нашем случае), предвари тельно умноженной на коэффициент гпту; ==-а,"/а. Однако поскольку в объединеннойматрице под матрицей А находится матрица -С, которую необходимо привести к нулевой матрице, никаких перестановок строк матрый записывается вэлемент 4.1,1 задержки, а также поступает на вход разрешения счетчика 6.1,1 и на вход установки триггера 5.1.1, который устанавливается в единицу, которая поступает на первый вход элемента И 16,1.1, с выхода которого единица поступает на управляющие входы коммутаторов 12,1,1 и 11,1,1 и записывается в элемент 17,1,1 задержки, Кроме того, в счетчик 6,1,1 записывается значение (и) = 2 в двоичном коде, на его выходе нулевого состояния находится нуль, На информационный вход ВБ 1,1.1.поступает а 11 = а 11 и, пройдя через первый вход второго коммутатора 12,1,1, записывается в элемент 13,1.1 задержки.Во втором такте на первый вход коммутатора 11,1,1 поступает элемент а 11 с выхода элемента 13.1,1 задержки, а на первые входы схемы 10.1.1 сравнения и коммутатор 12.1.1 поступает элемент а 21 = а 21 . В схеме 10.1.1 сравнения происходит сравнение и больший по абсолютному значению элемент записывается в элемент 13,1,1 задержки, а меньший - в первый регистр блока 15.1.1 элементов задержки, Допустим, что а 11а 21 1, Тогда элемент а 11 снова записывается в элемент 13,1,1 задержки, элемент а 21 - в первый регистр блока 15,1,1 элементов задержки. нуль с выхода схемы 10,1.1 сравнения (признак отсутствия перестановки строк) (Ч 21= О) записывается в элемент 17,1,1 задержки, а в элемент 19,1.2 задержки записывается единица, В этом же такте счетчик 6,1.1 уменьшает свое значение на единицу, на его выходе нулевого состояния остается нуль, который там находится до тех пор, пока содержимое счетчика 6,1.1 не станет равным нулю, Кроме того, элемент а 12 = а 12 поступает на информационный вход ВБ 1.1,2 и записывается в элемент 22,1.2 задержки (на управляющих входах коммутаторов 20,1,2 и 21.1.2 - единица),В третьем такте счетчик 6,1,1 уменьшает свое значение до нуля, На информационный вход ВБ 1,1,1 поступает элемент аз 1 = =.аз 1 . В схеме 10,1,1 сравнения аз 1 сравниваЕтСя Са 11. ПуСть а 11аЗ 1(ЧЗ 1=0). Тогда элемент а 11 записывается в регистр 7,1,1 (на выходе нулевого состояния счетчика 6,1,1 - единица), а элемент аз 1 - в первый регистр блока 15,1,1 элементов задержки, а 21 переписывается во второй регистр блока 15,1.1 элементов задержки. В ВБ 1,1,2 значение а 12 опять переписывается в элемент 22.1,2 задержки, а новое значение а 22: = а 22 - в первый регистр блока 25.1.1 элементов задержки. Кроме того, в ВБ 1,1,3 через его информационный вход поступает элемент а 1 з = а 1 з и записывается в элемент1 22.1.3 задержки, единица из элемента 19,1,2 задержки переписывается в 19,1,3, а в элемент 19.1.2 задержки записывается Ч 21 = О.В четвертом такте в элемент 3.1.1 задержки записывается единица, на выходе счетчика 6.1.1 снова появляетея нуль, триггер5.1.1 устанавливается в нулевое состояние,На первый вход делителя 14,1,1 с выходавторого регистра блока 15,1,1 элементов за 10 держки поступает а 21, а с выхода регистра7,1,1 - а 11, и результат деления (-а 21 /а 11 ):1= 21 записывается в элемент 18.1.1 задержки. Кроме того, на информационный входВБ 1.1.1 поступает элемент -с 11 = -с 11, кото 115 рый записывается в первый регистр блока15,1,1 элементов задержки (на выходе элемента 16,1,1 - нуль). В ВБ 1,1,2 на управляющий вход регистра 23,1,2 поступаетединица, и в регистр 23,1,2 записывается20 а 12 с выхода элемента 22.1.2 задержки, Навторой вход ВБ 1.1.2 поступает аз 2 = аз 2 изаписывается в первый регистр блока 25,1.2элементов задержки, а в первый регистрблока 25,1,3 элементов задержки записыва 25 ется а 2 з, поступающее с второго входа ВБ1.1,3. В элемент 19,1,3 задержки записывается нуль. В элемент 22,1.4 задержки записывается элемент матрицы В - Ь 11 = Ь 11, Вэлемент 19,1,4 задержки записывается еди 30 ница,В пятом такте 8.1,1 задержки записывается единица, в элемент 3.1.1 - нуль, Навходы делителя 14,1,1 в ВБ 1,1,1 поступаютэлементы аз 1 и а 11 и результат деления35 (-аз 1 /а 11) = з 1 записывается в элемент1 118.1,1 задержки, 21 записывается в элемент28.1.2 задержки ВБ 1,1.2, а также подаетсяна вход умножителя 27,1,2, Кроме того, наинформационный вход ВБ 1.1,1 подается40 элемент-с 21=-с 21, который записывается впервый регистр, элемента 13,1,1 задержки, а-с 11 - во второй регистр блока 15,1,1 элементов задержки. В В Б 1.1.2 с выхода регистра 23.1,2 на второй. вход умножителя45 27,1,2 поступает а 12 . В элемент 24.1,2 задержки за писы вается единица. Резул ьтатумножения 21 а 12 поступает на вход сумматора 26,1,2. где складывается с а 22", и сумма21 а 12 + а 22 = а 22 записывается в элемент1 1 250 29,1.2 задержки. Кроме того, с второго входаВБ 1.1,2 в первый регистр блока 25,1.2 элементов задержки записывается -с 12, аз 2переписывается во второй регистр блока25,1.2 элементов задержки. В ВБ 1,1.3 с55 выхода элемента 22.1.3 задержки в регистр23.1,3 записывается а 1 з, а в первый регистрблока элементов 22,1,3 задержки записывается азз с информационного входа В Б 1.1.3.,5 держки, пройдя через коммутатор 21.1.4, внего же переписывается. Ь 11, а в первый1регистр блока 25.1.4 элементов задержкизаписывается значение Ь 21= Ь 21, поступив 1шее с второго входа ВБ 1,1.4, В ВБ 1.1,5 вэлемент 19.1,5 задержки записывается единица, в элемент 22.1.5 задержки записывается Ь 12 = Ь 12 .В шестом такте управляющие сигналыпоступают аналогично первому такту, аименно в элементы 4.2.2 и 17.2.2 задержкизаписываются единицы, Я-триггер 5.2.2 устанавливается в единицу, значение п= 1записывается в счетчик 6.2.2, На входы делителя 14.1,1 в ВБ 1.1.1 поступают -с 11 иа 11, результат деления -с 11 /а 11 = 141 запи 1сывается в элемент 18,1,1 задержки, с выхода которого 1 з 1 записывается в элемент28.1.2 задержки ВБ 1,1,2 и поступает навход умножителя 27,1,2, На второй вход ВБ1,1.1 поступает элемент новой матрицы А -а 11 . В ВБ 1.1,2 на входы умножителя 27,1.2поступают а 12 и 1 з 1, Результат умноженияа 12 1 з 1 поступает на вход сумматора 26.1,2,12куда поступает аз 2, а сумма 1 з 1 а 12 + азг ==аз 2 поступает в элемент 29,1,2 задержки,с выхода которого элемент а 22 через комму 2татар 21,2,2 поступает в элемент 22.2,2 задержки ВБ 1,2,2. Кроме того, на второй входВБ 1.1,2 поступает элемент (-с 22 = -с 22 ) и,пройдя через первый коммутатор 20.1,2, записывается в блок 25,1,2 элементов задержки. В ВБ 1.1.3 на входы умножителя 27.1,3поступают 121 и а 1 з . Результат умноженияа 1 з 121 поступает на вход сумматора 26,1,3,куда поступает элемент а 2 з, а сумма 121 а 1 з 1- 1,+ а 2 з = а 2 з поступает в элемент 29,1,3 загдержки, Кроме того, на информационныйвход ВБ 1.1.3 поступает(-с 1 з =-с 1 з ) и, пройдя через первый коммутатор 20.1,3, записы-вается в блок 25,1.3 элементов задержки. ВВБ 1.1.4 с выхода третьего элемента 22.1,4задержки через второй коммутатор 21,1,4 врегистр 23,1,4 записывается Ь 11 . а черезпервый коммутатор 20.1.4 с второго входаВБ 1,1,4 в.блок 25.1,4 элементов задержкизаписывается Ьз 1 = Ьз 1 . В ВБ 1.1,5 в элемент 19,1,5 задержки записывается нуль, свыхода третьего элемента 22.1,5 задержкичерез второй коммутатор 21,1,5 в него жезаписывается Ь 12, а в блок 25.1,5 элементовзадержки записывается Ь 22 = Ь 22 с второговхода В Б 1.1.5.В седьмом такте на входы делителя14,1,1 в ВБ 1.1.1 поступают (-с 21 )и а 11, ирезультат деления -с 21 /а 11 = 141 записывается в шестой элемент 18,1,1 задержки, свыхода которого 41 записывается в четвертый элемент 28.1.2 задержки ВБ 1 1.2 и поступает на вход умножителя 27.1.2. В ВБ1.1.2 на входы умножителя 27.1,2 поступают41 и а 12, Результат умножения 41 а 12 по 1 1ступает на вход сумматора 26.1.2, кура по 5 ступает элемент -с 12, и сумма 141 а 12 - с 12=12= с 12 поступает в элемент 29.1,2 задержки,с выхода которого элемент аз 2 поступает вгВБ 1,1.2. На выходе нулевого состояниясчетчика 6.2,2 - единица. В схеме 10.2.210 сравнения происходит сравнение, и больший элемент записывается в третий элемент 13.2.2 задержки, а меньший - в блок15.2.2 элементов за 2 держки, допустим, чтопри сравненииаз 2а 22 , тогда эле 15 мент аз 2 записывается в третий элемент213,2.2 задержки, а элемент а 22 - в блок215.2.2 элементов задержки, В умножителе27.1.3 ВБ 1.1.3 происходит умножение1 з 1 а 1 з и результат поступает нэ вход сум 20 матора 26,1,3, кда поступает элемент азз,а сумма з 1 а 1 з + азз = азз поступает в1 2элемент 29,1,3 задержки,с выхода которого2а 2 з поступает в элемент 22,2.3 задержки ВБ1,2,3, Кроме того, на второй вход ВБ 1,1,325 поступает -с 2 з = -с 2 з и через первый коммутатор 20,1.3 записывается в блок 25,1,3 элементов задержки, В ВБ 1,1.4 на входыумножителя 27.1.4 поступают 121 и Ь 11 ирезультат 121 Ь 11 поступает на вход сумма 30 тора 26.1.4. куда поступает элемент Ь 21 исумма 121 Ь 11+ Ь 2", -- Ь 21 .поступает в эле 2мент 29.1.4 задержки, Кроме того, на второйвход ВБ 1,1,4 поступает элемент матрицы О- о 11= 011 и через первый коммутатор 20.1,435 записывается в блок 25.1.4 элементов задержки. В ВБ 1.1.5 с выхода третьего элемента 22,1,5 задержки Ь 12 перезаписывается врегистр 23,1.5, а с информационного входаВБ 1,1,5 Ьз 2 = Ьз 2 проходит через первый40 коммутатор 20,1.5, записывается в блок25,1.5 элементов задержки,В восьмом такте в ВБ 1,1,2 на входыумножителя 27.1,2 поступает 151 и а 12 и результат умножения 51 а 12 поступает на45 второй вход сумматора 26.1.2, на первыйвход которого поступает элемент -с 22 и ре 2зультат (51 а 12 - с 22 = с 22 записывается вэлемент 29.1.2 задержки, с выхода которого2с 12 поступает в ВБ 1.2,2 и записывается в50 блок 15.2.2 элементов задержки, В элемент3,2,2 задержки записывается единица, Навходы делителя 14.2.2 поступает-а 22 /аз 2 =1 з 2 и результат записывается в элемент18.2.2 задержки, В ВБ 1.1,3 на входы умно 55 жителя 27.1,3 поступает 141 и а 1 з и результат141 а 1 з поступает на вход сумматора 26.1.3,куд 2 э поступает -с 1 з и сумма 141 а 1 з - с 1 з1 1 1- :с 1 з поступает в элемент 29,1.3 задержки, с выхода которого азз записывается в ВБ1.2.3 и через коммутатор 21,2.3 записывается в элемент 22.2.3 задержки, В ВБ 1,1.4 навходы умножителя 27.1.4 постпает 1 з 1 и Ь 11и результат умножения 131 Ь 11 поступает навход сумматора 26.1.4, куда поступает Ь 31,и сумма 13 Ь 1 + Ь 31 = Ь 31 записывается1 1 2в элемент 29.1,4 задержки, с выхода которого Ь 22 поступает в ВБ 1,2,4 и через комму 2татор 21.2,4 записывается в элемент 22.2.4задержки, Кроме того, на информационныйвход В Б 1.1,4 поступает элемент б 2 = б 21 и1через коммутатор 21.1,4 записывается вэлемент 22,1,4 задержки, В ВБ 1.1.5 на входы умножителя 27,1.5 поступают 121 и Ь 12 и1результат умножения 21 Ь 12 поступает на1вход сумматора 26.1.5, ктуда поступает элемент Ь 22, и сумма 121 Ь 12 + Ь 22 = Ь 22 запи 1сывается в элемент 29.1.5 задержки. Крометого, на информационный вход ВБ 1,1,5 поступает элемент б 12 = б 12 и через второйкоммутатор 21.1,5 записывается в элемент22.1.5 задержки,В девятом такте с выхода элемента29.1.2 задержки В Б 1,1,2 элемент с 22 поступает в ВБ 1,2,2 и записывается в блок 15,2,2элементов задержки. В элемент 8.2.2 задержки записывается единица. В делителе14.2,2 происходит деление с 12 /аз 2 = 142 и2 2результат записывается в элемент 18,2.2 задержки, с выхода которого 132 поступает вВБ 1.2,3, где записывается в элемент задержки 28.2.3 и поступает на вход умножения27.2,3, где происходит умножение 132 азз .грезультат умножения поступает на второйвход сумматора 26,2,3, на первый вход которого поступает а 23, и сумма 132 азз + а 23 =2=азз записывается в элемент 29,2,3 задерж 3ки. В ВБ 1,1.4 на входы умножитедя 27.1,4поступают 141 и Ь 1 и результат умножения14 Ь поступаетвсумматор 26.1.4,сумма141 Ь 11 +б 11 =б 11 записывается в элемент1129,1.4 задержки, с выхода которого элементЬ 31 поступает в ВБ 1.2,4. В ВБ 1,1.5 на2входы умножителя 27,1,5 поступает 13 иЬ 2, где пооисходит умножение, и результат 131 Ь 12 поступает в сумматор 26.1,5 исумма 131 Ь 2 + ЬЗ 2 = Ь 32 поступает в элемент 29,1.5 задержки, с выхода которогос 22 поступает в ВБ 1,2.5, Кроме того, на2второй вход ВБ 1,1,5 поступает б 22 = б 22 изаписывается в элемент 22.1.5 задержки.В десятом такте с выхода элемента29.1.3 задержки в ВБ 1.2.3 поступает с 23 . Вэлементы 4.3.3 и 17,3.3 задержки записывается единица и на выходе нулевого состояния счетчика 6.3,3 появляется единица. Навходы умножителя 27.1.4 ВБ 1.1.4 поступаютэлементы 151 и Ь 1 и результатумножения;б 21 = б 21 поступает в элемент 29,1,4 задержки, с выхода которого элемент б 11 постугпает в ВБ 1,2.4. В ВБ 1.1,5 на входы умножителя 27.1,5 поступают элементы 151 Ь 12, результат поступает в сумматор 26.1,5, сумма 5 151 Ь 12+ б 22 = б 22 поступает в элемент 29,1,5гзадержки, с выхода которого Ь 32 поступает вгВБ 1,2.5 и через коммутатор 21,2.5 записывается в элемент 22,2,5 задержки. В В Б 1.2,2 на входы делителя 14,2.2 пост 2 упаютс 22 и аз 2 и2 2 10 результат деления с 22 /аз 2 = 152 записываетгся в элемент 18,2.2 задержки, с выхода которого 142 поступает на входы умножителя 27.2,3 и элемента 28,2,3 задержки. Результат умножения 142 азз с выхода умножителя 27,2.3215 поступает в сумматор 26,2.3, сумма 142 азз +Фс 13 = с 1 з записывается в элемент 29.2,3 за 3держки, с выхода которого элемент азз поступает в ВБ 1.3,3 и через коммутатор 12.3.3 записывается в элемент 13.3.3 задержки. В 20 ВБ 1,2,4 на входы умножителя 27,2.4 поступают элементы 132 и Ьз, результат умноже 2ния поступает в сумматор 26,2.4, с выхода которого 132 Ь 31 - Ь 2 = ЬЗ записывается2 2 3в элемент 29,2,4 задержки.В одиннадцатом такте с выхода элемента 19,1,4 задержки элемент б 21 поступает в ВБ 1.2,4 и через коммутатор 21,2,4 записывается в элемент 22.24 задержки. В ВБ 1.1.5 на входы умножителя 27,1.5 поступают Ь и Ь 2, результат умножения Ь Ь 122 поступает в сумматор 26.1,5, и результат суммирования у Ь 12 + б 22 = б 22 поступает в1 1 2элемент 29.1.5 задержки, с выхода которого элемент б 12 поступает в ВБ 1.2,5, где через коммутатор 21,2.5 записывается в элемент 22.2.5 задержки, С выхода ВБ 1.2.2 элемент52 поступает на входы умножителя 27.2,3 и элемента 28.2.3 задержки. Результат умножения 152 азз. ВБ 1,2,3 поступает в сумматор 26,2.3 и сумма 52 азз + с 23 = с 232поступает в элемент 29.2,3 задержки, с выхода которого с 13 поступает в ВБ 1.3.3 и, пройдя через блок 15.3.3 элементов задержки, поступает на вход дзелителя 14,3.3, Результат деления с 13/азз = 14 з записывается в элемент 18,3.3 задержки, В ВБ 1,2.4 на входы умножителя 27.2.4 поступают элементы 142 и Ь 31, результат умножения2142 Ь 31 поступает в сумматор 26.2.4 и сумма2142 Ь 31+ б 112 = б 11 записывается в элемент329.2.4 задержки, с выхода которого элемент Ь 31 поступает в ВБ 1,3,4, В ВБ 1.2,5 с выхо 3да умножителя 27,2,532 Ь 32 поступает в2сумматор 26,2.5, результат суммирования 132 Ь 32 +Ь 22 =Ь 32 записывается вэлемент2 2 329,2,5 задержки.В две.адцатом такте с выхода элемента29,1,5 задержки элемент б 22 поступает в ВБ 1,2,5. " выхода элемента 29,2,3 задержки50 55 элемент с 23 поступает в В Б 1.3.3, где, и рой 3дя блок 15.3.3 элементов задержки, поступает на вход делителя 14.3,3 и результат деления 53 записывается в элемент 18,3,3 задержки, с выхода которого элемент 43 поступает в элемент 28.3.4 задержки ВБ 1.3.4 и на вход умножителя 27.3,4, с выхода которого 43 Ь 31 поступает в сумматор 26,3,4, с3выхода которого сумма 43 Ь 31 + с 11 = б 11: = х 11 записывается в элемент 29,3,4 задержки. В ВБ 1,2.4 на входы умножителя 27,2,4 поступают 52 и Ь 31, результат умножения2252 Ь 31 посту 2 пает в сумматор 26,2,4 и сумма 52 Ь 312+ 021 = б 21 записывается в элемент329.2,4 задержки, с выхода которого элемент 011 поступает в ВБ 1.3.4. На входы умножи 3теля 27.2.5 ВБ 1,2.5 поступают элементы 42 и Ь 32, результат умножения 42 Ь 32 посту 2 2 пает в сумматор 26,2,5, и сумма 42 Ь 32 + 1012 = с 12 поступает в элемент 29,2.5 задер 2 3жки,с выхода которого с 12 поступает в ВБ31.3.5.В тринадцатом такте из ВБ 1.2,4 элемент с 21 поступает в В Б 1.3,4, В В Б 1.2.5 на3входы умножителя 27.2.5 поступают элементы 32 и Ь 32, результат умножения252 Ь 32 поступает в сумматор 26.2,5 и сумма252 Ь 32 + о 22 = с 22 поступает в элемент2 2,29.2,5 задержки, с выхода которого с 12 поступает в ВБ 1.3.5, В ВБ 1,3.4 на входы умножителя 27.3.4 поступают 53 и Ь 31, результат умножения 53 Ь 31 поступает в сум 3матор 26.3,4 и сумма 53 Ь 31 + с 21 = г 21 .=х 21 записывается в элемент 29,3,4 задержки, с выхода которого х 21 поступает на первый выход устройства. В,ВБ 1,3,5 на входы умножителя 27 3.5 поступают 43 и Ь 32, резул ьтат умножения 43 Ь 32 поступает в3сумматор 26.3,5, сумма которого 43 Ь 32 +,3 41 С 12 = 012 = х 12 записывается в элемент 29,3,5 задержки, и х 12 поступает на второй выход устройства.В четырнадцатом такте с выхода ВБ 1.2.5 элемент с 22 поступает в ВБ 1.3.5, С3выхода ВБ 1.3.4 на первый выход устройства выдается х 21, В ВБ 1.3.5 на входы умно- жителя 27,3.5 поступают элементы 53 и Ь 32, результат умножения 53 Ь 32 поступает в3сумматор 26.3.5 и сумма 53 Ь 32 +с 22 = 022=- = х 22 записываЕтся в элемент 29,3,5 задержки,с выхода которого на второй выход устройства выдается х 22.На этом вычисление элементов результирующей матрицы Х = СА В+О заканчива-.-1ется. Таким образом, полное время реализации алгоритма Т = п(п)/2+2(п) + -:п+ р+ г тактов, причем элементы результирующей матрицы Х выдаются на входы устройства последние г+ р+ 1 тактов (причем 10 15 20 25 30 35 40 45 с 1-го выхода устройства выдается 1-й столбец матрицы Х (1 = 1, г) аналогично поступлению исходных элементов матриц В и О на соответствующие входы устройства. Однако в случае решения потока аналогичных задач . период работы устройства составляет т = п + 1-р тактов. Это означает, что первый элемент а 11 очередной объединенной матрицы можно подавать через т тактов после подачи элемента а 11 предыдущей объединенной матрицы, В нашем случае Т = 14, 1 = 5 тактов. следовательно, элементы следующей матрицы можно начинать подавать на вход устройства (вместе с импульсом запуска) с шестого такта,Таким образом, предлагаемое устройство при примерно равных аппаратурных затратах и временных характеристиках с известным устройством позволяет существенно расширить функциональные возможности последнего. Кроме того, реализация частичного выбора ведущего элемента позволяет в ряде задач значительно повысить устойчивость, а следовательно, и точность вычислительного процесса по сравнению с известным устройством.Формула изобретения 1. Устройство для выполнения операций над матрицами, содержащее п вычислительных блоков первого типа и (п (и)/(2+п г) вычислительных блоков второго типа (где и и г - размерности матриц), причем вход пуска первого вычислительного блока первого типа соединен с входом запуска устройства, первый выход режима (ц)-го вычислительного блока первого типа (где== 1, п) соединен с входом режима (+1, +1)-го вычислительного блока первого типа, второй выход режима (а, Ь)-го вычислительного блока первого типа (где а = Ь = 1, п) соединен с входом режима (а, Ь+1)-го вычислительного блока второго типа, выход режима(с, б+Е)-го вычислительного блока второго типа (где ст=б=1, и; 1=1, и+г-с)соединен с входом режима (с, 0+1+1)-го вычислительного блока второго типа, информационный вход первого вычислительного блока. первого типа подключен к первому информационному входу устройства, информационный вход (1, )1)-говычислительного блока второго типа (где 1=.= 2, и+г) подключен к 1-му информационному входу устройства, выход результата вычислительного блока второго типа (где==.(+1, )+1)-го вычислительного блока первого типа. выход результата (и, и+11)-го вычислительного блока второго типа (где М 1 = Г соединен с 11-м выходом результата устройства, выход результата (, )+12)-го вычислительного блока второго типа(где = );50 55 и; 12 = 2, п+г) соединен с информационным входом (1+1, )+к 2)-го вычислительного блока второго типа, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных воэможностей устройства за счет реализации им алгоритма Фаддеева, выход признака перестановки и выход деления (а, Ь)-го вычислительного блока первого типа (где а = Ь = 1, и) соединены с входом признака перестановки и входом деления (а, Ь+1)- го вычислительного блока второго типа, выход признака перестановки и выходделения (е, Оча)-го вычислительного блока втолого типа (где с = с 3 = 1, п; Е = 1, п+г-с) соединены с входами признака перестановки и деления (с, О+К+1)-го вычислительного блока второго типа,2. Устройство по и. 1, о тл и ч а ю щее с я тем, что вычислительный блок первого типа содержит первый и второй элементы задержки, триггер, счетчик, регистр, третий элемент задержки, элемент ИЛИ, схему сравнения, первый и второй коммутаторы, четвертый элемент задержки, блок деления, блок элементов задержки, элемент И, пятый и шестой элементы задержки, причем вход режима вычислительного блока первоготипа соединен с входом разрешения счетчика, входом установки в н 1 и триггера и входом второго элемента задержки, выход которого соединен с первым входом элемента ИЛИ, выход счетчика - с входом установки в нОн триггера, входом первого элемента задержки и входом записи регистра, выход третьего элемента задержки - с первым выходом режима блока первого типа, выход первого элемента задержки - с входом третьего элемента задержки и вторым выходом режима вычислительного блока первого типа, выход триггера - с первым входом элемента И, второй вход которого соединен с выходом элемента ИЛИ, выход элемента И - с входом пятого элемента задержки и входами разрешения первого и второго коммутаторов, выход пятого элемента задержки - с выходом признака перестановки вычислительного блока первого типа, информационный вход вычислительного блока первого типа подключен к первым информационным входам схемы сравнения, первого и второго коммутаторов, выход схемы сравнения подключен к второму входу элемента ИЛИ, информационный выход первого коммутатора соединен с входом блока элементов задержки, выход которого соединен с первым информационным входом блока деления, информационный выход которого соединен с входом шестого элемента задержки, выход 10 15 20 25 30 35 40 45 которого соединен с выходом деления процессорного блока первого типа, второй информационный вход блока деления соединен с информационным выходом регистра, информационный вход которого соединен с информационным выходом второго коммутатора и входом четвертого элемента задержки, выход которого соединен с вторыми информационными входами схемы сравнения, первого и второго коммутаторов, информационный вход счетчика соединен с входом константы устройства. 3. Устройство по п. 1, о т л и ч а ю щ ее с я тем, что вычислительный блок второго типа содержит первый элемент задержки, первый и второй коммутаторы, второй элемент задержки, регистр, третий элемент задержки, блок элементов задержки, сумматор, блок умножения, четвертый и пятый элементы задержки. причем вход режима вычислительного блока второго типа соединен с входом третьего элемента задержки и входом разрешения регистра, информационный выход которого соединен с входом первого сомножителя блока умножения, вход второго сомножителя которого соединен с входом четвертого элемента задержки и входом деления вычислительного блока второго типа, выход четвертого элемента задержки подключен к выходу деления вычислительного блока второго типа, вход признака перестановки которого соединен с входом первого элемента задержки и входами разрешения первого и второго коммутаторов, выход первого элемента задержки подключен к выходу признака перестановки вычислительного блока второго типа, информационный вход которого под-. ключен к первым информационным входам первого и второго коммутаторов, информационный выход первого коммутатора соединен с входом блока элементов задержки, выход которого соединен с входом первого слагаемого сумматора, информационный выход которого соединен с пятым элементом задержки, выход которого соединен с выходом результата вычислительного блока второго типа, выход блока умножения соединен с входом второго слагаемого сумматора, информационный выход второго коммутатора - с информационным входом регистра и входом второго элемента задержки, выход которого соединен с вторыми информационными входами первого и второго коммутаторов, выход третьего элемента задержки подключен к выходу режима вычислительного элемента второго типа.