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

А 1 СОЮЗ СОВЕТСНИХСОЦИАЛ ИСТИЧЕСНИРЕСПУ БЛИН 801735868 51)5 С 06 Р 15/ ГОСУДАРСТВЕННЫЙПО ИЗОБРЕТЕНИЯМ ИПРИ ГКНТ СССР МИТЕТ ОЧНРЫТИЯМНИЯ МУ СВИДЕтЕЛьСтВУ НАВ ПКРАЦИЙ НАД ИА( ) р е относится к автоматике и вычислительной технике и можетбыть использовано в специализированных матричных вычислителях. Цельизобретения - расширение функциональных возможностей за счет вычислениявыражений вида Х = СА " В + О. Цельдостигается тем, что в устройствовведены М вычислительных модулей (Мчисло столбцов матрицы С) со связями.Устройство работает в соответствии салгоритмом Фаддеева с частичным выбором ведущего элемента. 4 ил нсти(Рт.),. ков (БНКак сленн8)видет06 Ридетел06 Р ельство СССР15/348, 1988. ство СССР 15/31, 1986. Недостатками этог ляются большие аппар а также сравнительно ность вычислений извсех алгоритмов без элемента.Наиболее близк технической сущно ройство для умнож тор, содержащее и соединенных вычиблок, управления.Недостатком из являк,тся его срав функциональные возможнос йства явзатраты кая точизации ведущего о устр атурны Изобретение отноке и вычислительнойбыть использовано пциализированных, влических, устройствдля выполнения опер ав томатие и может роении спеле и систоазначенных.д матрицаитс техи по невысза реалвыбора том чи пред ацнй ним к изобретению пости .является,устения матрицы на век последовательнослительных модулей и вестного устройства кительно небольшие,ми Известно устройство для операций над матрицами, содержащее связанные соответствующим образом и операционных блоков (где и - порядок обрабатываемых матриц), (и) элементов задержки и распределитель импульсов, подключенный к управляющим входам; всех операционных блоков. Устройство позволяет выполнять.Ж-разложение либо обращение исходной матрицы или решать систему иэ и линейных алгебраических уравнений методом Еордана" Гаусса с периодом 2 и тактов. Целью иэобретенир ение функциональнустройства за счет ргоритма Фаддеева с ч. ведущего элемента, квычислять выражение является расши; ых возможностейеализации им аластичным выбором оторый.позволяетвида Х в СК ф В + ОПИСАНИЕ ИЗОБР1735868 оставитель О.Масленников ехред И.Дидык Корректор И.Самборска ктор И.ймакова Тираж Подписноеенвого комитета по изобретениям и открытиям при ГЕНТ 13035, Москва, Ж 35, Раушская иаб., д. 4/5 Зак осуд Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 10которых поступает а, .".усть ац)а. Тогда нуль (Б = О) с выхода схемы 9.1 сравнения (признак отсутствия перестановки строк) поступз- ет через элементы 18.1, 22.1 и коммутатор 19,1 (на его управляющем входе имеется нуль) на управляющие входы , коммутаторов 6. 1 и 8,1, вследствие чего а перезаписывается в регистрИ7 1 а а записывается в Р 1 блокаф 2114.1. Кроме того, единица из (в+1)-го разряда Р 1 блока 14.1 переписывается в Р 2 блока 14,1 и появляется на его выходе, Б записывается в триггер 25.1 и появляется. на входе признака перестанЬвки строк иодуля 1.2, в счетчики.23.2 и 24.2 записываются значения соответственно (и) и 1, и на инверсном выходе отрицательного переноса счетчика 24,2 - единица, которая находится там до тех пор, пока содержимое счетчика 24.2 не станет равныи нулю. В третьем такте счетчик 46 уменьщает свое значение на единицу, на выходахтриггеров 16.2,20.3,21.3 и 15.1появляются единицы а на выходе триггера 21.2 - нуль, элемент а поступаетна вход модуля 1.3 и записывается в регистр 7,3, а единица с выхода триггера 21.3 - в (ш+1)-й разряд Р 1 блока 14,3 ф аф поступает на ля 1.2, поскольку на выходе счетчика 24.2 находится единица, коммутатор 19,2 передает на свой выход Б = О, которое переписывается в регистр 25.2 и управляет работой коммутаторов 6.2 и 8,2 так, что а записывается . в Р 1 блока 14.2, а а 4 перезаписывается в регистр 7.2. Кроме того, а, поступает на входы коммутаторов 6.1, 8. 1 и схемы 9. 1 сравнения, на другиевходы которых поступает а . Пустьа, с а. Тогда единица (01 = 1) с выхода схеиы 9.1 записывается втриггер 25.1 и управляет коммутаторами 6. 1 и 8.1, вследствие чего а записывается в Р 1 блока 14.1 (а переписывается в Р 2 блока 14,1), а азаписывается в регистры 7. 1 и 5.1.Кроме того, единица из (а+1)-го разряда Р 1 блока 14,2 переписывается в Р 2 блока 14.2, на выходе счетчика 24.3 находится единица, счетчики 23.1, 24.1 не меняют своего состояния, поскольку на их управляющем .входе остается единица (режим параллельного занесения инФормации). В четвертом такте счетчик 46уиеньпает свое значение на единицу,а в счетчик 4 1.1 записывается (п),на выходах триггеров 16.3, 34,1, 35.1и 15,2 появляется единица, на выходетриггеров 16.1 и 21.3 - нуль, Ъц= Ъпоступает на вход модуля 2. 1 изаписывается в регистр 31.1, а единн 0ца с входа триггера 35,1 - в (в+1)-йразряд Р 1 блока 42,1, а поступаетна вход модуля 1,3 и, поскольку накоммутаторы 6.2 и 8.2 поступает Б, == О, записывается в Р 1 блока 14.3, 1511, записывается в триггер 25.3, аа перезаписывается в регистр 7.3.Кроме того, а поступает на вход мо 4дуля 1.2, и, поскольку 11 = 1, агзаписывается в Г 1 блока 14.2, а а" 20 в регистры 7.2 и 5.2. Кроме того,единица из (а+1)-го разряда Р 1 блока14.3 переписывается в Р 2 блока 14.3,Б переписывается в триггер 25.2,-С поступает на входы коммутаторов256.1 и 8.1 и, поскольку на выходе элемента И 18,1 (независиио от выходасхемы 9.1 сравнения) нуль, -С записывается в Р 1 блока 14. 1, ачерезкоммутатор 111 поступает на второйвход блока 4.1 умножения-деления, напервый вход которого поступает аз изрегистра 5,1, блок 4 выполняет деление и результат -а/а = ш принимается в регистр 26.1, пройдя черезкоимутатор 12,1 (па выходе элемента З 5 ПЛИ 17.1 нуль).В пятом такте в счетчик 41.2 записывается (п), счетчик 46 уменьшает свое значение на единицу, его содержимое становится равным кулю и наего выходе отрицательного переносапоявляется единица, которая сбрасывает триггер 47 в нуль, и поступает надекрементирующий вход счетчика 45,уменьшая его содеряимое .на единицу.В этом яе такте на выходах триггеров34.2, 35.2 и 15.3 появляется единица,на выходе триггеров 16.2 и 35.1нуль Ъ поступает на вход модуляЭ Д22 и записывается в регистр 31.2, а 50 единица с выхода триггера 35.2 - в(в+1)-й разряд Р 1 блока 42,2, Ь , поступает на вход модуля 2.1 и, поскольку 0 = О, записывается вР 1 блока 42,1, 0 записывается в Ятриггер 36,1 а Ъ перезаписываетсяф Нв регистр 31.1 1 роме того, а, по"ступает на вход модуля 1.3 и, так как1 а записывается в Р 1 блока-С поступает на блок 4, 1, с выхода которого значение С,ц /аш 41 принимается в регистр 26.1, -С переписывается в Р 2 блока 141,1114,3), а а записывается в регистры 7.3 и 5.3. Кроме того, 0, переписы" вается в регистр 25,3, "С, поступает на входы коммутаторов 6.2 и 8.2 и, поскольку на выходе элемента И 18,2 нудь, записывается в Р 1 блока 14.2(у а, переписывается в Р 2 блока 14.2, ,ш , через коммутатор 11.2 поступает на блок 4,2, который выполняет умножение, на второй вход сумматора 13.2 поступает аг из Р 2 блока 14.2, и результат аг+шг а г = а принимаетгся в Р 1 блока 27.2, а ш переписываг ется в регистр 26,2 (на выходе элемента ИЛИ 1.2 единица). В этом же такте -Сг поступает на входы коммутаторов 6,1 и 8.1 и записывается в Р 1 блока 14.1, -С переписывается в Р 2 блока 14.1, а поступает на блок 4.1, с выхода которого значение .-а 1 /а, = ш 1 принимается в регистр 26,1. В шестом такте в счетчик 46 записывается (и+р) = 3 с выхода счетчика 45, триггеры 21.1 и 20.1. устанавливаются соответственно в единицу и нуль, единица с выхода триггера 21,1 записывается в конце такта в .(ш+1)-й разряд Р 1 блока 14 1 (аналогично первому такту), триггер 44,1 устанавливается в единицу, а триггеры 15.3,16.3 и 35.2 - . в нуль, Ьгг поступает на вход модуля 2.2 и записывается в Р 1 блока 42.2, 0 г записывается в триггер 36,2, Ь, .перезаписывается в регистр 31.2, Ь поступает на вход модуля 2,1 и (01 = 1) записывается в регистры 31.,1 и 29.1 а Ь - в Р 1ф Н блока 42.1, -С поступает на,входы коммутаторов 6.3 и 8.3 и, поскольку на выходе элемента И 18.3 нуль, записывается в Р 1 блока 14.3 а 1 пе"ф И реписывается в Р 2 блока 14.3 ш поф О ступает на блок 4,3, который выполняет умножение, на второй вход сумматора 13,3 поступает аи.результат аг)+шг аэ = а 2 принимается в Р 1 блока 27.3; а ш д переписываетсяв регистр 26.3. В этом же такте -Сгг. цоступает на вход модуля 1.2 и записывается в Р 1 блока 142, -С переписывается в Р 2 .блока 14.2, ш ц = .- ".-ац /ае поступает на блок 4.2, ко . торый выполняет умножение, на вход сумматора 13.2 поступает а из Р 2 .блока 14.2, и результат а +ш " аЫ М" 2а принимается в Р 1 блока 272, шпереписывается в регистр 26.2,В седьмом такте аналогично второму такту триггеры 20,2, 44.1 и 21.1устанавливаотся в йуль, триггеры 1 О44,2, 21.2 н 16.1 - в единицу счетчик 24.1 уменьшает свое состояние наединицу (доминус единицы), .но на его.инверсном выходе остается нуль, единица с выхода триггера 21,2 записывается в (ш+1)-й разряд Р 1 блока 14.2Ъ г поступает на вход модуля 2, 2 изаписывается в регистры 31,2, 29.2,а Ь,г - в Р 1 блока 41,2, Ь переписывается в Р 2 блока 42,2, бз записывается в триггер 36.2, д поступает на вход модуля 2.1 и записываетсяв Р 1 блока 42.1 (Ь переписываетсяв Р 2 блока 42.1), ш = -а,/а, поступает на умножитель 28,1 на втоФ 25рой вход сумматора 39, 1 поступает Ь4 гги результат Ьг +шг Ь =Ъг, принимается в Р 1 блока 40.1, а шпереписывается в регистр 38,1. В этом же такте -С поступает на вход вычислительного моцуля 1.3 и записывается в ЗО Р 1 блока 14.3, ш поступает на блок4.3, который выполняет умножение, навход сумматора 13,3 поступает а и13результат а+ш,1 а =а принимается%5в Г 1 блока 27.3, а переписываетсяв Р 2 блока 27.3, ш , - в регистр26.3. В этом же такте -С переписывается в Р 2 блока 14.2 ш 4 = С /а4 11 Рпоступает на блок 4.2, который.выполняет умножение, на вход сумматора13.2 поступает -С,г нз Р 2 блока 14.2и результат -С, +ш 4 тазг= С принимается в Р 1 блока 27.2 а принимаф згется в Р 2 блока 27.2, а 2 из Р 2 блока 27,2 через коммутатор 10.2 посту, пает на входы коммутаторов 8.2 и 6.2и записывается в регистр 7.2 ш пе"ф У сЦреписывается в регистр 26.2 -С по-,в густупает на блок 4.1, с выхода которог о значение Сг, /а = ш принимаетсяв регистр 26,1.В восьмом такте триггеры 20.3,21.2 устанавливают в нуль, триггеры21.3, 15. 1 -. в единицу, счетчик 24.2уменьшает своезначение на единицу,и на его инверсном выходе появляетсянуль, единица с выхода триггера 21.3записывается в (и+1)-й разряд Р 1 бло-ка 14,3, й поступает на вход модуля 2.2 и записывается в Р 1 блока1735868 51015 42,2, Ь переписывается в Р 2 блока 42.2, ш , поступает на умножитель 28,2, Ь - на второй вход сумматораггю 2 39.2, результат Ь +в,. Ь: Ь 2 принимается в Р 1 блока 40.2, в пе, реписывается в регистр 38. 2. В этом же такте Й поступает на вход моду(ля 21 и записывается в Р 1 блока 42.1, й переписывается в Р 2 блока 42.1, шэ( поступает на умножитель 28.1, на сумматор поступает Ь ( и результат Ь +в, Ьэ 1 = Ь 2 принимается в Р 1 блока 40,1, в( переписывается в регистр 38,1. В этом же ,такте -Сг переписывается в Р 2 блока 14.3, т 4( поступает на блок 4,3, который выполняет умножение, на сумматор 13.3 поступает -С(эВи результат -С +в,(азу = С 2 принимается в Р 1 блока 27,3, а через. коммутатор 10.3 поступает на входы коммутаторов 8,3 и 6.3 и записывается в регистр 7.3, в 4, переписывается в регистр 26.3, ш, - в регистр 26,2, а также поступает на блок 4.2, который выполняет умножение, на сумматор 13,2 постУпает -Сг и РезУльтат -Сгг+ +в( азу = С принимается.в Р 1 блока 27,2, С, переписывается в Р 2 блока 27,2, а через коммутатор 10.3 поступает на входы схемь 1 9.2 сравнения, где сравнивается с аПусть а 2( а. Тогда единицагг м0 = 1 с выхода схемы 9.2 управляетг2 коммутаторами 8.2 и 6.2 так, что азаписывается в регистры 7.2 и 5.2, а - в Р 1 блока 14.2. 1 роме того,ггсчетчик 23.1 уменьшает свое значение на единицу, и длина блока 14.1 становится равной единице.В девятом такте Й с входа модуля 2.2 записывается в Р 1 блока 42,2,3д(г переписывается в Р 2 блока 42. 2,с вьмода сумматора 39.2 результатЬ +ш, Ъ( = Ъ, принимается в Р 1Сблока 40,2, ш( переписывается в регистр 38.2, (1, переписывается в Р 2блока 42.1, с вьмода сумматора 39.1= йг 2 принимается в Р 1 блока 40.2,Ь 2 принимается в регистры 31.2,29,2, с выхода сумматора 39.1 результат Ьг 2 +шаг-Ь 21 = Ьэ 2( прини аетсЯ вР 1 блока 40.1, й ц йереписывается вР 1 блока 42.1, а. - в Р 2 блока 27.3,С - в Р 1 блока 14.3, с вьмода сумматора 13.3 результат С 2 +в 4 га 2= 1 принимается в Р 1 блока 40.1,гЬ, - в регистр 31.1, длина блока50 14.3 уменьшается на единицу и стано.вится равной нулю (т.е. данные проводят с его входа на вьмод без задержки), Сф поступает на вход блока 4.3,Йон выполняет деление, и результат55 455 в 4 - Сщ/а принимается в регистр26. 3.В четырнадцатом такте с выхода= й принимается в Р 1 блока 40;2, 173Ь - в регистр 31.2, длина блока эг42.1 становится равной нулю, и с выхода сумматора 39.1 значение с 1 + +шл Ъ Хпринимается в Р 1 блока4 Ъ Э 1 И44.1 и в регистр 37, 1 и появляется на перйом выходе устройства, С" поступает на вход блока 4.3 и результат ш= -С /а принимается в регистр%9 2 Э ЗЭ26.3, а ш,1 э - в регистр 38,1.В пятнадцатом такте длина блока 42,2 становится равной нулюс выхода сумматора 39.2 значение й,2+шЭ Ь.Х принимается в регистр 37,2 ил 1появляется на втором выходе устрой" ства, с 1 переписывается в Р 2 блока 44.2, с выхода сумматора 39.1 значение сР + шЬз, = Хг, пРинимаетсЯгв регистр 37.1 и появляется на первом выходе устройства,В последнем шестнадцатом такте свыхода сумматора 39.2 значение йз ++ш Ь = Х принимается в регистрХЭ Эа гг37.2 и появляется на втором выходеустройства. На этом вычисление элементов результируюцтей матрицы Х == СА я В + 0 заканчивается, Таким образом, полное время реализации алгоритма Т =- п(п) /2+п(р+1)+р+2+И тактов, причем элементы результирующей матрицы Х вьдаются на выходы устройства последние р+Итактов, причем с г-го выхода устройства вьдаетсяг-й столбец матрицы Х (г 1,И) аналогично поступлению исходных элементов матриц В и Э на соответствующиевходы устройства. Однако в случае решения потока аналогичных задач периодработы устройства составляет С = Т -+1)+11-1.тактов. Это означает, чтопервый элемент ан очередной объеди,ненной матрицы можно подавать черезтактов после подачи элемента апредыдущей объединенной мгтрицы. Внашем случае Т = 16, й = 12 тактов,следовательно, элементы следующейматрицы можно начинать подавать навход устройства (вместе с импульсомзапуска) с тринадцатого такта,Формула и з о б р е т е н и яУстройство для операций над матрицами, содержащее блок синхронизации и.п вычислительных модулей (п - поря- ДОК ВХОДНой МаТРИЦЫ)е КажДЫЙ ИЗ КОТО" рых содержит пять триггеров, два счетчика, два элемента ИЛИ, блок умножения-деления, сумматор, шесть ком 5868 16мутаторов, два блока элементов задержки, три регистра и элемент И,причем вход запуска устройства подключен к одноименному входу блокасинхронизации, выход которого соеди- .нен с синхровходом первого вычисли"тельного модуля, выход синхронизации,выход признака перестановки строк и 10информационный выход К-го вычислительногй модуля (К = 1, ,о) лоднлючены соответственно к синхровходу,входу признака перестановки строк ипервому информационному входу,(К+1)- 15го вычислительного модуля, второй информационный вход Р-го вычислительного модуля (Р = 1,п) является Р-м информационным входом устройства, вкаждом вычислительном модуле первыйи второй разряды синхровхода соединены соответственно с информационнымивходами второго и третьего триггеров,выходы которых являются соответственно первым и вторым разрядами выходасинхронизации вычислительного модуля,вход и выход признака перестановкистрок которого соединены соответственно с первым информационным входомшестого коммутатора и выходом четвертого триггера, информационный вход З 0 которого подключен к выходу шестогокоммутатора и первому входу второгоэлемента ИЛИ, второй вход и выход которого подключены соответственно квыходу третьего триггера и объединенным входам управления первого и вто. рого коммутаторов, объединенные первые информационные входы которых подключены к выходу второго регистра ипервому входу схемы сравнения, вто рой вход которой подключен к объединенным вторым информационным входампервого и второго коммутаторов и выходу третьего коммутатора, вход управления которого подключен к выходувторого триггера и входам разрешениясчета первого и второго счетчиков,декрементирующие входы которых подключены соответственно к входам обнуления и установки пятого триггера, щ выход которого соединен с первымивходами первого элемента ИЛИ и элемента И, второй вход и выход которого подключены соответственно к выходусхемы сравнения и второму информационному входу шестого коммутатора,вход управления которого подключен квыходу второго счетчика и второмувходу первого элемента ИЛИ, выход коМгторого подключен к входам управления17четвертого и пятого коммутаторов и1 входу выбора режима блока умножения- деления, первый и второй информационные входы которых подключены соответственно к выходам четвертого коммутатора и первого регистра, информационньп вход которого соединен с информационным входом второго регистра и выходом первого коммутатора, первый и второй информационные входы вычислительного модуля подключены к первым информационным входам соответственно четвертого и третьего коммутаторов, вторые информационные входы которых подключены соответственно к выходам второго и первого блоков элементов задержки, входы управления которых подключены соответственно к выходу первого счетчика и входу Р устройства, информационный выход вычислительного модуля соединен с выходом тре- . тьего регистра, информационный вход которого подключен к выходу пятого коммутатора, первьп и второй информационные входы которого соединены соответственно с первым информационным входом четвертого коммутатора и объединенными первым входом сумматора и выходом блока умножения-деления, выход сумматора подключен к информационному входу первого блока элементов задержки, входы установки, первого н второго счетчиков подключены соответ ственно к входам ии Р"1 устройства, отличающееся. гем, что, с целью расширения Функциональных возможностей за счет вычисленияг(выражений вида Х = СА В + О, в устройство введены .И вычислительных модулей (И - число столбцов матрицы В); каждый из которых содержит умножитель, сумматор, два блока элементов задержки, счетчик, элемент ИЛИ, четыре триггера, четыре регистра и два коммутатора, причем синхровход, вход признака перестановки строк и первый информационный вход г-го вычислительного модуля 1 г - ое 1, юН 1) лоднлюоены к одноименным выходам (г) вычислительного модуля, вторые информационные вход и выход г-го вычислительного модуля являются соответственно (и+ +г)-м информационным входом и г-м выходом устройства,. причем в каждом г-и вычислительном модуле первый и второй разряды синхровхода подключены соот. ветственно к информационным входам первого и второго триггеров, выходы которых являются соответственно пер 35868вым и вторым разрядами выхода синхронизации вычислительного модуля,вход и выход признака перестановки5строк которого подключены соответственно к индюрмационному входу и выходу третьего триггера, первые информационные вход и выход вычислительного модуля подключены соответственно кинформационноь 1 у входу и выходу четвертого регистра, вторые информационные вход и выход вычислительного модуля подключены соответственно к первому информационному входу третьегокоммутатора и выходу третьего регистра, информационный вход которого подключен к выходу сумматора и информационному входу первого блока элементов задержки, выход которого подключен к второму информационному входутретьего коммутатора, выход которогоподключен к объединенным первьм информационным входам первого и второгокоммутаторов, объединенные вторые информационные входы которых подключенык выходу второго регистра, информационный вход которого подключен к выходу первого коммутатора и информационному входу первого регистра, выходкоторого подключен к первому входуумножителя, второй вход и выход которого подключены соответственно к инФормационному входу четвертого регистра и первому входу сумматора, второй вход которого подключен к второмувыходу второго блока элементов задержки, первый и второй информационные входы которого подключены соответственно к выходам второго триггераи второго коммутатора, управляющий 4 ф вход которого подключен к управляюще"му входу первого коммутатора и выходуэлемента ИЛИ, первый и второй входыкоторого подключены соответственно кинформационному входу третьего триг гера и выходу второго триггера, выходпервого триггера подключен к управ-;ляющему входу третьего коммутатора ивходу разреыения счета счетчика, выход которого подключен к управляющему 50 входу второго блока элементов задержки, первый выход которого подключенгк инйормационному входу четвертоготриггера, выход которого подключен ксинхровкоду первого регистра и декрементирующему входу счетчика, вход установки которого соединен свходом(п)-го устройства, вход управленияпервого блока элементов задержки подключен к входу Р устройства.