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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 51)5 0 06 Р 1 ИС Е ИЗОБРЕТЕНИЯ К АВТОРСКОМУ ЕТЕЛЬСТВ рная схея случая е схемы ОСУДАРСТВЕННЫЙ КОМИТЕТО ИЗОБРЕТЕНИЯМ И ОТКРЫТИРИ ГКНТ СССР(56) Авторское свидетельство СССР В 1462353, кл. 6 06 Г 15/324, 1989,Авторское свидетельство СССР М 1633422, кл. 6 06 Р 15/347, 1989.(54) УСТРОЙСТВО ДЛЯ ОПЕРАЦИЙ НАД МАТР И ЦАМ И(57) Изобретение относится к вычислительной технике и может быть использовано в высокоп роизводител ьн ых специализироИзобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для решения систем линейных алгебраических уравнений и вычисления первого собственного значения и первого собственного вектора матриц.Известно устройство для решения систем линейных алгебраических уравнений, содержащее 2 п - 1 вычислительных модулей (ВМ), где п - порядок системы линейных алгебраических уравнений, 2 п - 1 блоков памяти и блок вывода ;,Недостатком этого устройства является невозможность вычисления первых собственных значений и векторов и х п-матриц.Наиболее близким по технической сущности к предлагаемому является устройство(е Жал 1721612 А 1 ванных вычислительных машинах и устроиствах обработки сигналов для решения систем линейных алгебраических уравнений и вычисления первого собственного значения и вектора матрицы. Цель изобретения - расширение функциональных возможностей за счет вычисления первого собственного значения и соответствующего ему собственного вектора, Поставленная цель достигается тем, что устройство для операций над матрицами содержит и вычислительных модулей первого типа 9, где и - порядок систем линейных алгебраических уравнений, вычислительный модуль второго типа 10 и блок 11 вывода. 4 ил 2 табл,для решения систем линеиных алгебраических уравнений, содержащее и ВМ, блок вывода и регистр, причем каждый ВМ содержит три регистра, умножитель и сумматор, блок вывода - 2 п регистров, и вычислителей, п узлов сравнения, два элемента И и триггер 2,Недостатком известного устройства является невозможность вычисления первых собственных значений и векторов и х и- матрицы,Цель изобретения - расширение функциональных возможностей устройства путем вычисления первого собственного значения и первого собственного вектора матрицы.На фиг,1 представлена структума устройства; на фиг,2 - то же, дл и = 3; на фиг,3 и 4 - функциональнь вычислительных модулей,,к,(1 ( (к 1,(-(/ 1(к50у Ф55 Устройство (фиг.1) содержит группу информационных входов 1, первый 2, второй3 и третий 4 информационные входы, вход 5задания ошибки вычислений, синхровход 6,первый 7 и второй 8 настроечные входы,вычислительные модули 9 и 10, блок 11 вывода, информационные выходы 12 и выход13 признака окончания вычислений.Вычислительный модуль 9(фиг,З) содержит первый 14, второй 15 и третий 16 информационные входы, синхровход 17, первый18, второй 19 и третий 20 регистры, умножитель 21, сумматор 22, первый 23 и второй 24информационные выходы.Вычислительный модуль 10 (фиг,4) содержит первый 25, второй 26 и третий 27информационные входы, первый 28 и второй 29 настроечные входы, синхровход 30,первый 31 и второй 32 регистры, первый 33и второй 34 триггеры, узел 35 вычисленияобратной величины числа, первую - шестуюгруппы 36 - 41 элементов И, первую 42, вторую 43 и третью 44 группы элементов ИЛИ,первый - пятый элементы И 45 - 49, элементНЕ 50, умножитель 51, первый 52 и второй53 информационные выходы,В основу работы устройства при вычислении первого собственного значения Л 1 исоответствующего ему собственного вектора х 1 для некоторых начальных приближений компонент собственного вектора иСОбСтВЕННОГО ЗНаЧЕНИЯ Х 1, Х 2, , Х и и Л 1( ) положены формулы вида1и - 1х = (а(; х;+ а(и), хи = 1, ( = 1,2 п;1 ) -- 1и - 1Л 1= , аи;Х;+аии.) )Для вычисления значений х) и Л 1 используется итерационный метод Зейделярешения систем линейных алгебраическихуравнений, при котором значения х и Л 1определяются рекуррентными соотношениями; х (о),(о) хо) , .1 1, х (о),(о) х") = х ( ), ( = 1,л - 1, ) = 1,2 ;х,=1;Л 1)=хи)=хи )+аи)х)( ),) =1,п;Л) Лци) ),(и) точность вычисления значений х; и Л 1определяется величиной е. Если разности Ьх( = х 1) - х( ) ( = 1,п - 1) и ЛЛ 1== Л 1( 1)- Л 1( ) удовлетворяют условию5Л х(1е, 1 ЛЛ 1я, то можно принять+1) (К+1) +1)ПрИбЛИжрННО Х 1 =(Х 1, Х 2, Хи, 1)Л =Лф"),Рассмотрим работу вычислительногомодуля 10 (фиг,4), логика работы которого приведена в табл.1. Вычислительныймодуль 10 работает в четырех режимах,В первом режиме работы на настроечные входы 28 и 29 подаются нулевые сигналы, которые устанавливают двухтактныетриггеры 33 и 34 в нулевое состояние, навыходе элемента И 47 формируется единичный сигнал, который открывает группуэлементов И 37, При этом значение х, записанное в регистр 31, через группу элементовИ 37, группы элементов ИЛИ 42 и 44 подается на информационные выходы 52 и 53,Во втором режиме работы на настроечные входы 28 и 29 подаются соответственнонулевой и единичный сигналы, которые устанавливают триггеры 33 и 34 соответственно в нулевое и единичное состояния. Навходы 26 и 27 постоянно подаются соответственноЛ 1( и единичное число. Группа эле(О)ментов И 3 6 открывается, через н е езначение х, записанное в регистр 31, подается на вход группы элементов ИЛИ 42 исоответственно на выход 52. Кроме того,через открытую группу элементов И 39 единичное число подается на вход группы элементов ИЛИ 44 и на выход 53. На выходеэлемента И 46 формируется единичный сигнал, который открывает группу элементов И38. При этом по заднему фронту тактовогоимпульса значение Л = Л 1( ), поданное через(о)группу элементов И 38 и группу элементовИЛИ 43, записывается в регистр 32 (элемент И 48 открыт и разрешает прохождение тактового импульса на синхровходрегистра 32),45 В третьем режиме работы на настроечные входы 28 и 29 подаются соответственно единичный и нулевой сигналы, которые устанавливают триггеры 33 и 34 соответственно в единичное и нулевое состояния. При этом на выходе элемента И 49 формируется единичный сигнал, который открывает группу элементов И 40, На выходе узла вычисления обратной величины числа 35 формируется значение 1 И, на выходе умножителя 51 -1значение х, которое через группу элементов И 40, группы элементов ИЛИ 42 и 44 г одается на выходы 52 и 53,В четвертом режиме работы на настроечные входы 28 и 29 подаются единичные сигналы, которые устанавливают триггеры 33 и 34 в единичное состояние, На выходе элемента И 45 формируется единичный сигнал, который отк)оывает группу элементов И 41. Значение ЛФ, поданное на вход 25, че(Мрез группу элементов И 41 и группу элементов ИЛИ 43 подается на информационный вход регистра 32. Так как элемент И 48 открыт, значение Л по заднему фронту тактоф)ваго импула записывается в регистр 32, Значение Л с выхода регистра 31 через открытую группу элементов И Зб и через группу элементов ИЛИ 42 подается на выход 52, Единичное число через открытую группу элементов И 39 и группу элементов ИЛИ 44 подается на выход 53,При описании работы устройства в обозначении х )ф первый индекс в скобках(1) указывает. номер итерации, а второй индекс в скобках- номер рекуррентного шага дл я Е-й итерации, В обозначении х " индекс в скобках (К) указывает номер итерации, а индекс с без скобок - номер такта работы устройства.Рассмотрим работу устройства для с)оучая и = 3, На вход 2 подаются значения х 1 ), х 2 и 1 соответственно на нулевом, втором(о)и четвертом тактах, на последующих тактах подаются нулевые значения. На входы 3,4 и 5 постоянно подаются соответственно значения Л 1 ), 1 и е. Организация подачи вход(о)ного потока элементов на входы 1 ( = 1,2,3) и управляющих сигналов на входы 7 и 8 приведена на фиг,2, Работа устройства по тактам поясняется табл,2, в которой приведены значения на входах, состояния регистров, триггеров и значения на выходах вычислительных модулей 9 и 10,На девятом, одиннадцатом и тринадцатом тактах в вычислительном модуле 10 формируются соответственно х 1 , х 2 1 и(1, 1) Л 1 ), которые записываются в регистры блока 11 вывода. На пятнадцатом, семнадцатом и девятнадцатом тактах в вычислител ьном модуле 10 формируются соответственно хР, хР и ЛР, которые также записываются в регистры блока 11 вывода. На двадцатом такте в блоке 11 вывода выполняется проверка условия Лх 1 е и ЛЛ 1 е. Если условие для всех хлх значений, ( = 1,2) выполняется, то на выходе 13 выдается признак окончания вычислений а = 1 и с выходов 121 и 122 выдаются значения соответственно первой и второй компонент первого собственного вектора х 1 = (х 1,х 2,1), а с выхода 12 з - значение первого собствел ного значения Л 1, Если 5 10 15 20 25 30 35 40 45 50 55 признак окончания вычислений а= О, то итерационный процесс вычислений продолжается. Выдача верных результатов х 1 и Л 1 при а=1 обеспечивается блоком 11 вывода в моменты времени 1 = и + 2 п(1+1), где М = 1,2,3 В остальные моменты времени 1 Ф и + 2 п+1) съем информации с выходов 12 не производится,При решении систем линейных алгебраических уравнений на настроечные входы 7 и 8 подаются нулевые сигналы, вычислительный модуль 10 выполняет функцию задержки информации, поступающей на его первый информационный вход 25 на один такт. Значения корней уравнений х ( = 1,п) снимается с выходов 12 при а= 1 в моменты времени с = и + 2 п(+1), К = 1,2,3,.Формула изобретения Устройство для операций над матрицами, содержащее (и+1) вычислительный модуль (и - порядок системы линейных алгебраических уравнений) и блок вывода, причем первый информационный вход устройства подключен к первому информационному входу и-го вычислительного модуля, первый информационный вход -го вычислительного модуля ( = 1,п - 1) подключен к первому информационному выходу (+1)-го вычислительного модуля, первый информационный выход первого вычислительного модуля подключен к первому информационному входу (и+1)-го вычислительного моду.:я, первый информационный выход которого подключен к первому информационному входу блока вывода, второй информационный выход (и+1)-го вычислительного модуля подключен к второму информационному входу первого вычислительного модуля, второй информационный выход -го вычислительного модуля подключен к второму информационному входу (+1)-го вычислительного модуля;)-й информационный вход гоуппы входов устройства ) = 1,п) подключен к третьему информационному входу )-го вычислительного модуля, вход задания ошибки вычислений устройства подключен к второму информационному входу блока вывода, синхровход устройства подключен к синхровходам всех вычислительных модулей и блока вьвода, выход признака окончания вычислений которого подключен к одноименному выходу устройства /-й информационный выход блока вывода является одноименным выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства путем вычисления первого собственного значения и первого собственного вектора матрицы, второй и третий ин(к 1 45 50 55 формационные входы устройства подключены соответственно к одноименным входам (и+1)-го вычислительного модуля, первый и второй настроечные входы которого являются одноименными входами устройства, причем вычислительные модули с первого по и-й выполнены с возможностью реализа. ции следующих функций; где а 1, Ь и с - значения соответственно на третьем, втором и первом информационных входах вычислительного модуля на )-м такте;А и В 1 - значения соответственно на первом и втором информационных выходах вычислительного модуля на (-м такте;(и+1)-й вычислительный модуль выполнен с возможностью реализации следующих функций: 15а и Р 1 - значения соответственно напервом и втором настроечных входах вычислительного модуля на )-м такте;х и с 1 - значения соответственно напервом и втором информационных входах вычислительного модуля на)-м такте;А 1 и Ь 1 - значения;соответственно напервом и втором информационных выходах вычислительного модуля на (-м такте.и Фх локо тх хх Ю х о хх х х т х оОоО тх ооС 4Ях т сох офокох хх лх Ф з з-а-а- з- а;.с. сс с С С 3 Х сС 3 3 СР Г 41 1 Р 1 Зкм 3 143гъЕу еС 4 Ч ФЯ 1ф 4 С.з фЪ фЪ а-.щфщ р,1а 4 1 Чв)3 Гф Ф 1 Ч .ФС з :у ь вщО щща ФЧ + +ф з 1 б4 А . ц.з ф е лщ уа фщ уф)+л ва Рб еез фЪ фР 11 СЪ 9 ф 1 еа. С;:)еаа Свав,) ща11ф ффъе а а фав в%л аа еее Фф ф е с. с 91 Ъ ааа1 вв аае фОав Ц 1 ещаказ 954 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 х, 4