Устройство для решения задач на собственные значения

(51) 5 САНИУ 3 ТЕНИ ПАТЕНТ ули реержащии 9.) (где )= Ц ние ап НаГОСУДАРСТВЕННОЕ ПАТЕНТНОВЕДОМСТВО СССР(71) Киевский политехнический институт им.50-летия Великой Октябрьской социалистической революции(73) Киевский политехнический институт (56) Авторское свидетельство СССР М 1545229, кл. 6 06 Р 15/347.В.А,Грачев, Г,А.Кухарев,Систолический процессор для решения задач на собственные значения, - Тезисы доклада конференции "Методы и микроэлектронные средства цифрового преобразования и обработки сигналов", Рига, 5 - 7 декабря 1989, т,1, е.304-306 (п рототип). Изобретение относится к автоматике ивычислительной технике и может быть использовано при построении специализированных, в том числе систолических,устройств для решения задач на собственные значения.елью изобретения является сокращепаратурных затрат,фиг.1 представлена функциональнаясхема устройствадля решения задач на собственные значения; на фиг,2 - функциональ-,ная схема блока регистров; на фиг.З -функциональная схема блока вычисленияскалярных операций; на фиг,4 - функцио.нальная.схема вычислительного модуля; нафиг;5 - функциональная схема узла управления вычислительно модуля; на фиг.6 - функциональная схегиа арифметико-логическогоблока вычислительного модуля; на фиг.7 -функциональная схема блока управления,Устройство для решения задачи на собственные значения содержит блоки регист(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ НА СОБСТВЕННЫЕ ЗНАЧЕНИЯ(57) Изобретейие относится к автоматике и вычислительной технике и может быть использовано при построении специализированных, в том числе систолических, устройств для решения задач на собствен:ые значения. Целью изобретения является сокращение аппарэтурных затрат. Устройство для решения задач на собственные значения содержит блоки регистров 1, ( = 1,Н), блок 2 вычисления скалярных операций, вычислительные блоки ЗЛ, блок 4 управления. коммутатор 5 и регистр 6 обратной связи, 3 табл 7 ил. ров 1 Л (где= 1,М), блок 2 вычисления скалярных операций, вычислительные мод 31, блок 4 управления, коммутатор 5, гистр 6 обратной связи.Блок регистров 1, (фиг,2),содкоммутатор 7, регистр 8, регистры=. 1, (2 й + 1), триггеры 10 и 11.Блок 2 вычисления скалярных операций (фиг,З) содержит вычисления квадоатного корня 12, делитель 13 и регистры 14 и 15.Вычислительный модуль 3,1 (фиг,4) ссдержит узел управления 16, арифметико-логический блок 17, регистры 18-23 и коммутаторы 24 и 25.Узел 16 управления (фиг.5) содержит триггеры 26, 27, 23.1, 28.2, 29,1, 29,2, коммутатор 30 и триггер 31.Арифметико-логический блок 17 (фиг.6) содержит коммутаторы 32, 33, улножитель 34, коммутатор 35, сумматор 36 и элел 1 ент И 37.Блок 4 управления (фиг.7) содержит Я- триггер 38, злемент И 39, счетчикО, О-триг 1790787 201790787 ректор М,Самборск дакто одственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 1 Заказ 376 , ВНИИПИ Го Составитель Ю. КаневскиТехред М.Моргентал Тираж . Подписноетвенного комитета по изобретениям и открытиям при ГКНТ С113035, Москва, Ж, Раушская наб., 4/5г1 и ;.;л 1 му 1 атор 4 Ь.Ь трит Гер 43, светя . 1 элементы ИЛИ 45, 46, элементы НЕ 1, цемент ИЛИ 48, В-Я-триггер 49, элемент 11",О, счетчик 51, О-триггер 52, элемент ИЛИ 53, счетчик 54, Р-триггеры 55, 56, элемент И 57, О-триггеры 58-61, элемент И 62, элемент ИЛИ 63, О-триггер 64, элемент И 65, Р-триггеры 66, 67; счетчик 68, О-триггер 69.Устройстводлярешения задач на собственные значения т 1 редназначено для нахождения собственных чисел и принадлежащих им собственньх векторов матрицы А размерности М. Устройство реализует степенной метод с исчерпыванием, Метод (см. Фадеев Д.КФадеева Д.Н. Вычислительные методы линейной алгебры. - М-.Л.: Физматгиздат, 1963 г,) предполагает последовательное вычисление отдельных собственных значения и собственных векторов, причем для вычисления некоторого собственного значения 1 и соответствующего ему собственного вектора г (М =1,2М) используется степенной метод, который состоит в итерационном выполнении следующих операций:к щ АЯ 1 щ (1)" щ =бтп (2) 1 щт 1щ(щ (3) где тп = 1 Л - номер итерационного шага;Ь 3 - векторы размера ,Б- номера вектора Б;А - исходная матрица;О - К-й столбец единичной матрицы.В результате выполнения (1) - (3) при тп=с получаем:ктгде О , Б - нормированный и ненормированный собственные векторы с номерами К;с - параметр. зада ваемы й -из условия обеспечения сходимости,После вычисления таким образом 1-го собственного значения и К-го собственного вектора производится исчерпывания матрицы А, используя формулуАсс+1 Ас Огас т( 3( т 1 т1 (1) Рассмотрим работу устройства,Устроиство обрабатывает одновременно две матрицы А = А, и В = (В 1, размерности К, Для простоты описания работы устройства без потери общности положим К = 3,Рассмотрим работу устройства при загрузке матриц в блок регистров, работу вычислительных модулей и блока вычисления скалярных операций в момент вычисления векторов (на примере двух итераций) и работу вычислительнспо модул в момен ит черпывания,Условимся, что А - элемен 1 т 1 атрицы А;Ь, О, Я, 1 - параметры, используемые при обработке матрицы А; В- элемент матрицы В; с,д,г, у - параметры, используемые при обработке матрицы В.Работа устройства при загрузке матрицА и В иллюстрируется в табл,1,Элементы матриц записываются построкам (первая строка матрицы А, пробел, первая строка матрицы В, вторая строка матрицы А и т,д,).При поступлении на первый вход блока 15 4 управления сигнала "Начало загрузкитриггер 38 устраиваются в "1" и дает разрешение на прохождения синхроситналов на вход 40 и через элемент ИЛИ 46 на четвертый выход блока управления, Устанавлива ется в ноль счетчик 44, коммутатор 42 будетпропускать на первый выход блока 4 управления сигналы, поступающие по первому входу, Счетчик 40, триггеры 43 и 59 установлень 1 первоначально в нуль, поэтому на втором и третьем выходах блока управления устанавливается комбинация "00",В первом такте по заднему фронту синхросигнала значение А 11 записывается в регистр 1,1.9,1, во втором такте в регистр 1,1,9.1 записывается значение А 12, а в регистр 1.1,9.2 - значение А 11 и т.д, В седьмом 2 М + 1)-м) такте на выходе переполнения счетчика 40 установится единица, В восьмом такте по переднему фронту синхросигнала установится триггер 41, по переднему фронту этого сигнала в триггеры 1.1,10 и 1.1.11 запишется комбинация "00", обнулится счетчик 40, установится триггер 43, на втором и третьем выходе блока управления 40 4 установится комбинация "10" (по этой команде в блоке регистров 1,1, будет производится циклическая перезапись данных) по заднему фронту значения А 21 записывается в регистр 1.1.8, В девятом такте по переднему фронту синхросигнала сбрасывается в нуль триггер 41, по заднел 1 у фронту в регистр 1,1.8 запишется значение А 22, в регистр 1,2.9.1 - значение А 21 и т.д, В шестнадцатом такте комбинация "10" будет 50 записана в триггеры 1.1.10 и 1.1,11 (в блокерегистров 1,2 будет производится циклическая перезапись данных) в триггеры 1,2,10 и 1.2,11 будет записана комбинация "00" (в блоке регистров 1.3, будет производится загрузка третьих строк матриц), В двадцать восьмом К+1)(2 М+1)-м) такте по заднему фронту синхросигнала на выходе перепол.нения счетчика 44 установится "1, сбросятся в нуль триггер 38 и счетчик 10Вюрпкраты г Гя еэьдача С,С.,Г., на чет вер г ьФИ гп Ф хпд блока 4 управления Заг рузка оконченаВ табл,2 описана работа вычислитель. ного модуля и блока вычисления скалярных операций во время первых двух итераций.Первоначально регистры 21 установлены в нуль, триггеры 27 и 43 - в единицу.При подаче на вход блока 4 управления сигнала "Начало работы" триггер 49 устанавливается в единицу, что разрешает прохождение синхросигнала через элемент И 50 на вход счетчика 51 и через элемент ИЛИ 46 на четвертый выход блока 4 управления, при этом на втором и третьем выходах блока управления установится комбинация "10" (в блоке регистров будет производится циклическая перезапись), на пятом и шестом выходах блока 4 управления установится комбинация "10" вычислительные модули работают в режиме вычисления вектора), на третьем и девятом выходах установится комбинация "00" (на первый вход 3.1. вычислительного модуля подается начальное значение векторов).В первом такте по переднему фронту синхросигнала в триггеры 3.1.26 и 3.1.27 запишется комбинация "10", по заднему фронту синхросигнала в регистр 3.1.21 значение Ь 1 = А цО , в регистр 3,1.19 - значе 1 1 1ние О 1, в регистры 3.2,21 и 3.3,21 запишется значение "0", во всех блоках регистров произойдет циклическая перезапись. Во втором такте по переднему фронту синхросигнала в триггеры 3,2.26 и 3,2,27запишется комбинация "10", по заднемуфронту синхросигнала в регистр 3,1,21 запишется значение Ь 1 = А 101 + А 12 02, в регистр 3,1,19 - значение 02, в регистр 3,2.21 - Ь 2 = А 21 01, в регистр 3.2.19 - О 1, во всех блоках регистров произойдет циклическая перезапись. В дальнейшем запись информации в регистры 19 и 21 описывается только с помощью табл,2,В третьем такте по заднему фронту на выходе переполнения счетчика 51 установится единица, на пятом,шестом и седьмом выходах блока управления установится комбинация "011". В четвертом такте по переднему фронту синхросигнала в триггеры3,1,26, 3.1.27, 3.1.28 запишется комбинация 5 10 15 20 25 304050"011", устанавливается в единицу триггер 52, сбрасывается в нуль счетчик 51, устанавливается в единицу триггер 66, по заднему фронту синхросигнала в регистр 3.1.18 запишется значение в:-(Ь )-, в регистр 3,1,20- 55значение Ь . На пятом, шестом и седьмом выходах блока 4 управления установится комбинация "100", В пятом такте по переднему фронту синхросигнлла в триггеры 3,1,26, 3,1,27, 3,1,28 заг ищется комбинация 100, Р гри ге 1) .1, 1,81 эн н;";в триггеры 3.2,26,;.3,l.3:1 ,.;. ппс, комбинация "ОО, в регис 1 .1 0;зпп шется значение Ь. по заднему рнти, в1регистр 3,2,18-значение в. (1., )(Ь), в27 регистр 3,1.18 - значение Ь . В дальнейшем процесс работы вычислительных модулей 3 описывается только в табл,2.В седьмом такте в регистр 14 запишетсязначение2 г1(Ь 1) +(Ь) +(Ы)на выходе переполнения счетчика 51 установится единица, в восьмом такте в регистр 15 запишется значение 01 =- Ь /Л, триг 2 1 1гер 52 установится в единицу, сбросится в ноль счетчик 51, установится в единицу триггер 67, установится единица на девятом выходе блока 4 управления (на выход коммутатора 5 будет поступать информация со второго входа), В дальнейшем работа устройства иллюстрируется только табл,2,В М-м такте, где (М = (21 - 2)(М + 1) - 1) триггер 52 установится в единицу, на выходе переполнения счетчик 54 установится единица, единица установится на восьмом выходе блока 4 управления. В (М+ 1)-м такте по переднему фронту, единица запишется в триггеры 3,1,29 и 56, в регистр 3.1.22 запишется значение 01, на восьмом выход)е установится значение "0". В (М)-м такте единица запишется в триггер 3.1.29.1, В (М+3)-м такте единица запишется в триггер 3,2,29, в регистр 3.2,22 запишется значение 02. В (М+4)-и такте в единицу установятся триггеры 3,2.29,1, 52, 55 единица установится на восьмом выходе блока 4 управления. В (М)-м такте в единицу установятся триггеры 3.1.29, 3,3.29, 61, одновременно врегистр 3,1.23 запишется значение 01, вс регистр 3,1,22 - значение с 1, в регистр 3,3.22 - значение Оз, В (М+6)-м такте в единицу устанавливается триггер 3.1.29.1, В (М+1)-м такте в единицу установится триггер 3.2.29, одновременно в регистр 3,2.23 запишется значение 02, в регистр 3.2,22 - значение с 12, В (М+8)-м такте в единицу устанавливаются триггеры 52, 58, 3,2.29.1, на третьем пятом, шестол выходах блока управления установятся единць,. Следовательно, блоки регистров будут установлены в режим приема информации с вычислительных модулей, т.е. будут производиться операции исчерпывания. 1 а вылп колмутатора 5 поступает информация с третьего входа, В Т-мтакте (где Т: М9 - 21 (1 ч + 1 триггеры 3.1,26, 3,1,27, 3,131, .3 29 усла. навливаются в единицу, в .; р. истров11 1.1, поступает зна ю и. А. ., 0 Ь.1790787 10 15 в регистр 3,1.18 записывается значение Ь,в регистр 3.3,23 - значение Оз, в регистр3,3,22 - значение бз. В дальнейшем работа вычислительных модулей и блоков регистров при реализации исчерпывания иллюстрируются только с помощью табл.З Формула изобретения1, Устройство для решения задач на собственные значения, содержащее И вычислительных модулей (К - размерность обрабатываемой матрицы), каждый из ко торых содержит узел управления, регистры с первого по четвертый и первый коммутатор, М блоков регистров, блок вычисления скалярных операций, коммутатор и блок управления, причем первый информационный 25 выход )-го вычислительного модуля ) = 1.И) соедийен с первым информационным входом )+1)-го вычислительного модуля, второй информационный выход 1-го вычислительного модуля соединен с первым 30 информационным входом 1-го блока регист.ра (1=1 Щ первый информационный выход которого соединен с вторым информационным входом 1-го вычислительного модуля, второй информационный вы ход)-го блока регистров соединен с вторым информационным входом О+ 1)-го блока ре- гистров, второй информационный вход пер. вого блока регистров соединен с первым информационным входом устройства, пер вый и второй выходы которого соединены соответственно с первым и вторым выходами блока вычислений скалярных операций, о т л и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат, в него 45 введен регистр обратной связи,а каждый из К вычислительных модулей введены пятый и шестой регистры, второй коммутатор и арифметико-логический блок, причем третий информационный выход )-го вычисли тельного модуля соединен с третьим информационным входом )+1)-го вычислительного модуля, первый информационный вход первого вычислительного модуля соединен с выходом коммутатора, первый и 55второй информационные входы которого соединены соответственно с выходом регистра обратной связи и первым выходом блока вычисления скалярных операций, информационный вход которого соединен с третьим По окончании исчерпывания в (Т+7)-м такте установится в единицу триггер 60, сбросятся в ноль триггеры 55, 58, 59, счетчик 54, - схема готова к следующей итерации,По окончании всех итераций счетчик 68 установится в единицу, сбросит в ноль регистры 43, 49, и схема приводится в исходное положение,информационным вь 1 ходом М-го вычислительного модуля и входом регисгра обратной связи, управляющие выходы с первого по пятый )-го вычислительного модуля соединены соответственно с управляющими входами с первого по пятый Ц+1)-го вычислительного модуля, управляющие входы с первого по пятый первого вычислительного модуля соединены соответственно с выходами с первого по пятый блока управления, шестой выход которого соединен с первым управляющим входом 1-го блока регистров, первый и второй управляющие выходы )-го блока регистров соединены соответственно с вторым и третьим управляющими, входами ) + 1)-го блока регистров, второй и третий управляющие входы первого блока регистров соединены соответственно с седьмым и пятым выходами блока управления, восьмой выход которого соединен с четвертым управляющим входом -го блока регистров, шестым управляющим входом 1-го вычислительного, модуля и первым. управляющим входом блока вычисления скалярных операций, второй управляющий вход которого соединен с вторым управляющим входом М-го вычислительного модуля, второй информационный вход устройства соединен с третьим информационным входом коммутатора, первый и второй управляющие входы которого соединены соответственно с девятым и пятым выходами блока управления, вход Начало загрузки", синхровход и вход "Начало работы" которого соединены соответственно с первым, вторым и третьим управляющими входами устройства, а в каждом из Й вычислительных модулей второй информационный вход модуля соединен с первым информационным входом арифметика-логического блока, второй информационный вход которого соединен с выходом первого регистра, информационный вход которого соединен с выходом второго регистра, информационный вход которого соединен с первым информационным входоммодуля, третьим информационным входом арифметико-логического блока и информационным входом третьего регистра, выход которого соединен с первым информационным входом модуля, третий информационный вход которого соединен с четвертым информационным входом арифметико-логического блока и первым информационным входом первого коммутатора, второй информационный вход которого соединен с первым информационным входом второго коммутатора, вторым информационным вы-. ходом модуля и выходом арифметика-логического блока, пятый информационный вход которого соединен с информационным входом четвертого регистра и выходом пятого регистра, информационный вход которого соединен с выходом второго коммутатора, второй информационный вход которого соединен с входом логического нуля модуля, управляющие входы с первого по пятый которого соединены соответственно с входами с первого по пятый узла управления, первый выход которого соединен с первым управляющим выходом модуля и первым управляющим входом арифметико-логического блока, второй управляющий вход которого соединен с вторым выходом узла управления, вторым управляющим выходом модуля, управляющим входом второго коммутатора, первым управляющим входом первого коммутатора и синхровходом четвертого регистра, выход которого соединен с третьим и информационным входом пер; вого коммутатора, второй управляющий вход которого соединен с третьим выходом узла управления и третьим управляющим выходом модуля, четвертый и пятый управ ляющие выходы которого соединены соответственно с четвертым и пятым выходами узла управления, шестой выход которого соединен с синхровходом первого и второго регистров, шестой управляющий вход моду ля соединен с шестым входом узла управления и синхровходами третьего, пятого и шестого регистров, выход первого коммутатора соединен с информационным входом шестого регистра, выход которого соединен 15 с третьим информационным выходом модуля,2. Устройство по п,1, о т л и ч а ю щ е ес я тем, что блок вычисления скалярных 20 операций содержит узел вычисления квадратного корня, делитель и два регистра, причем информационный вход блока соединен с входом узла вычисления квадратного корня и первым входом делйтеля, выход ко орого соединен с информационным входом первого регистра, выход которого соединен с первым выходом блока, второй выход которого соединен с вторым входоМ делителя и выходом второго регистра, ин формационный вход которого соединен свыходом блока вычисления квадратного корня, первый и второй управляющие входы блока соединены соответственно с синхровходами первого и второго регистров.35