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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных , в том числе систолических, устройств для решения задач на собственные значения. Целью изобретения является сокращение аппаратурных затрат. Устройство для решения задач на собственные значения содержит блоки регистров 1,1 (i 1.NJ, блок 2 вычисления скалярных операций, вычислительные блоки 3.I, блок 4 управления, коммутатор 5 и регистр 6 обратной связи. 3 табл., 7 ил.

СОЮЗ СОВЕ(СКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (s()s G 06 F 15/347

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ПАТЕНТУ (21) 4908183/24 (22) 06.02.91 (46) 23.01.93. Бюл. N - 3 (71) Киевский политехнический институт им.

50-летия Великой Октябрьской социалистической революции (72) P.Выжиковский, Ю.C,ÊàíåBcêèé, В;Л,Лепеха и М.К.Клименко (73) Киевский политехнический институт (56) Авторское свидетельство СССР

¹ 11554455222299, кл. G 06 F 15/347.

В.А,Грачев, Г,А.Кухарев.Систолический процессор для решения задач на собственные значения, — Тезисы доклада конференции "Методы и микроэлектронные средства цифрового преобразования и обработки сигналов", Рига, 5 — 7 декабря 1989, т,1, е.

304-306 (прототип).

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных, в том числе систолических, устройств для решения задач на собственные значения.

Целью изобретения является сокращение аппаратурных затрат, На фиг.1 представлена функциональная схема устройства для решения задач на собственные значения; на фиг.2 — функциональная схема блока регистров; на фиг.З— функциональная схема блока вычисления скалярных операций; на фиг.4 — функциональная.схема вычислительного модуля; на фиг:5 — функциональная схема узла управления вычислительно модуля; на фиг.6 — функциональная схема арифметико-логического блока вычислительного модуля; на фиг.7— функциональная схема блока управления, Устройство для решения задачи на соб. ственные значения содержит блоки регист5U 1790787 АЗ (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

НА СОБСТВЕННЫЕ ЗНАЧЕНИЯ (57) Изобретейие относится к автоматике и вычислительной технике и может быть использовано при построении специализированных, в том числе систолических, устройств для решения задач на собственные значения. Целью изобретения является сокращение аппаратурных затрат. Устройство для решения задач на собственные значения содержит блоки регистров 1,((i = 1,N), блок 2 вычисления скалярных операций, вычислительные блоки З.i, блок 4 управления. коммутатор 5 и регистр 6 обратной связи, 3 табл., 7 ил. ров 1,i (где (= 1,N), блок 2 вычисления скалярных операций, вычислительные модули

3 (, блок 4 управления, коммутатор 5, регистр 6 обратной связи.

Блок регистров 1,((фиг,2),содержащий коммутатор 7, регистр 8, регистры 9.j (где j=

=. 1, (2N + 1), триггеры 10 и 11.

Блок 2 вычисления скалярных операций (фиг,З) содержит вычисления квадратного корня 12, делитель 13 и регистры 14 и 15.

Вычислительный модуль З.i (фиг,4) ссдержит узел управления 16, арифметико-floгический блок 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 и элемент И 37.

Блок 4 управления (фиг.7) содс ржит R-Sтриггер 38, злемент И 39, счетчик -10, 0-тригГ! 1 | -. !м|!"у1а!!ур «1;«, !x S три| гер 43, с!|етя: . 1 элементы ИЛ И 45, 46, элементы Н Е

1, |лемент ИЛИ 48, R-S-триггер 49, элемент

|1 ..0, счетчик 51, 0-триггер 52, элемент ИЛИ

53, счетчик 54, D-триггеры 55, 56, элемент И

57, D-триггеры 58-61, элемент И 62, элемент

ИЛИ 63, D-триггер 64, элемент И 65, D-триггеры 66, 67;счетчик 68, D-триггер 69.

Устройство для решения задач на собственные значения предназначено для нахождения собственных чисел и принадлежащих им собственных векторов матрицы А размерности N. Устройство реализует степенной метод с исчерпыванием. Метод (см.

Фадеев Д.К„Фадеева Д.Н. Вычислительные методы линейной алгебры. - M-.Ë.: Физматгиздат, 1963 r,) предполагает последовательное вычисление отдел ьн ых собственных значения и собственных векторов, причем для вычисления некоторого собственного значения il, и соответствуюk щего ему собственного вектора z (k

=1,2,...,N) используется степенной метод, который состоит в итерационном выполнении следующих операций:, К пу = AkUk ny

Л . щ = t l bК m! I (2)

Uk- m+1 = bk щ/ Л k m (3) где m = 1Л вЂ” номер итерационного шага;

b,U — векторы размера N, l I Б I l — номера вектора Ь;

А — исходная матрица;

1| k 1 — k.é столбец единичной матрицы.

В результате выполнения (1) — (3) при

|т|=1 получаем:

gk К 1

=(-,:„" 1 где U, Б — нормированный и ненормированный собственные векторы с номерами k; . t — параметр. задаваемый-из условия обеспечения сходимости.

После вычисления таким образом k-го собственного значения и k-го собственного вектора производится исчерпывания матрицы А, используя формулу

Ak+1 Ak Uk t(bk 1)Т 1 (N 1)

Рассмотрим работу устройства.

Устроиство обрабатывает одновременно две матрицы А = (А |) и В = (В |), размерности

N, Для простоты описания работы устройства

be> потери общности положим N = 3, Рассмотрим работу устройства при загрузке матриц в блок регистров, работу вычислительных модулей и блока вычисления скалярных операций в момент вычисления векторов (на примере двух итераций) и работу вычислительнгно мп«1ул» в к|гумен| и< черпывания, Условимся, что А| — элемен1 r.1атрицы А;

b, U, S, il. — параметры, используемые при обработке матрицы А; В|1-- элемент матрицы

В; с,d,r, y — параметры, используемые при обработке матрицы В.

-Работа устройства при загрузке матриц

А и В иллюстрируется в табл,1, Элементы матриц записываются по строкам (первая строка матрицы А, пробел, первая строка матрицы В, вторая строка матрицы А и т.д.).

При поступлении на первый вход блока

4 управления сигнала "Начало загрузки" триггер 38 устраиваются в "1" и дает разрешение на прохождения синхроси|налов на вход 40 и через элемент ИЛИ 46 на четвертый выход блока управления. Устанавливается в ноль счетчик 44, коммутатор 42 будет пропускать на первый выход блока 4 управления сигналы, поступающие по первому входу, Счетчик 40, триггеры 43 и 59 установлены первоначально в нуль, поэтому на втором и третьем выходах блока управления устанавливается комбинация "00", В первом такте по заднему фронту синхросигнала значение А11 записывается в регистр 1,1.9,1, во втором такте в регистр

1.1.9.1 записывается значение A1z, а в регистр 1.1,9.2 — значение А11 и т.д. В седьмом ((2N + 1)-м) такте на выходе переполнения счетчика 40 установится единица. В восьмом такте по переднему фронту синхросигнала установится триггер 41, по переднему фронту этого сигнала в триггеры 1.1.10 и

1.1.11 запишется комбинация "00", обнулится счетчик 40, установится триггер 43, на втором и третьем выходе блока управления

40 4 установится комбинация "10" (по этой команде в блоке регистров 1,1. будет производится циклическая перезапись данных) по заднему фронту значения А21 записывается в регистр 1.1.8. В девятом такте по переднему фронту синхросигнала сбрасывается в нуль триггер 41, по заднему фронту в регистр 1.1.8 запишется значение Ал, в регистр 1,2.9.1 — значение А„.1 и т.д. В шестнадцатом такте комбинация "10" будет записана в триггеры 1.1.10 и 1.1.11 (в блоке регистров 1.2 будет производится циклическая перезапись данных) в триг| еры 1.2.10 и

1.2.11 будет записана комбинация "00" (в блоке регистров 1.3, будет производится загрузка третьих строк матриц). В двадцать восьмом ((N+1)(2N+1)-м) такте по заднему фронту синхросигнала на выходе переполнения счетчика 44 установится "1, сбросятeq в нуль триггер 38 и счетчик 1!|

"011", устанавливается в единицу триггер

52, сбрасывается в нуль счетчик 51, устэнэвливэется в единицу триггер 66, по заднему фронту синхросигнэлэ в регистр 3.1.18 зэпишется значение "", =-. (bl ), в регистр 3.1,20- 55

12 значение b! . Нэ пятом, шестом и седьмом

1 выходэх блока 4 упрлвления устэновится комби1.эция "100", В пятом такте по переднему фронту синхрос>;гнэлэ в триггеры

3.1.26, 3.1.27, 3.1.28 запишется комбинация

1>Р .KPttTtt1 (.Я вь1дэ>1Л С.С.. Г нэ чет ве11 t t tA Et> I хпд блокэ 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 значение b = А llU 1. в регистр 3.1.19 — знэче1 1 1 ние U >, в регистры 3.2,21 и 3.3.21 запишется значение "О", во всех блоках регистров произойдет циклическая перезэпись. Во втором такте по переднему фронту синхросигнэлэ в триггеры 3,2.26 и 3.2,27 запишется комбинация "10", по заднему фронту синхросигнэлэ в регистр 3.1,21 зэпишется значение Ül = А 11Ul + A!2 U2 в

1= 1 1 1 1 регистр 3,1.19 — значение U2, в регистр

3,2.21 — b2 = A2! Ul, в регистр 3.2.19 — U 1, во всех блоках регистров произойдет циклическая перезапись. В дальнейшем запись информации в регистры 19 и 21 описывается только с помощью табл.2.

В третьем такте по заднему фронту нэ выходе переполнения счетчика 51 устэновится единица, нэ пятом, шестом и седьмом выходах блока управления устэновится комбинэция "011". В четвертом такте по переднему фронту синхросигнэлэ в триггеры

3,1.26, 3.1.27, 3.1.28 запишется комбинация

50 100, в ри >е1> 1,1 ?Р,, t > .>; » ", > .>1

tt три1геры 3.2.2tt, 3.2 .1:. . 11 1. »>1»1> кол бинэц11я "О! О, в pPttt<: р .?.!;.>О:,;>1»>

>вется значение b. по зэд» ему р«нти, tt

1 регистр 3.2,18 — знэчение s (!>z ) > (b! ), в

2 ) регистр 3.1.18 — значение b! . B дальнейl шем процесс работы вычислительных модулей 3 описывается только в табл.2.

В седьмом тэкте в регистр 14 зэпишется значение

2 2

1(Ь ) +(») +(b ) нэ выходе переполнения счетчикэ 51 установится единица, в восьмом такте в регистр

15 запишется значение U! =- bl /1, триг2 1 1 гер 52 установится в единицу, сбросится в ноль счетчик 51, установится в единицу триггер 67, установится единица нэ девятом выходе блока 4 управления (нэ выход коммутатора 5 будет поступать информация со второго входэ), В дальнейшем работа устройствэ иллюстрируется только табл.2.

В М-м такте, где (М = ((2t - 2)(N + 1) - 1) триггер 52 установится в единицу, нэ выходе переполнения счетчик 54 установится единица, единица устэновится нэ восьмом выходе блока 4 управления. В (М + 1)-м такте по переднему фронту, единица запишется в триггеры 3,1,29 и 56, в регистр 3.1.22 зэпишется значение Ull, íà восьл1ом выходе устэновится значение "О". В (М-2)-м такте единица запишется в триггер 3.1.29.1, В (M+3)-м такте единица запишется в триггер

3.2.29, в регистр 3.2.22 зэпишется значение

U2 . В (М+4)-м такте в единицу установятся триггеры 3,2.29.1, 52, 55 единица установится нэ восьмом выходе блока 4 управления.

В (М-5)-м такте в единицу установятся триггеры 3.1.29, 3,3.29, 61, одновременно в регистр 3.1.23 запишется значение 1), в

l регистр 3.1.22 — значение d, в регистр

3.3.22 — значение Оз, В (М+6)-м такте в единицу устэнэвливэется триггер 3.1.29.1, В (M+1)-м тэкте в единицу установится триггер

3.2.29, одновременно в регистр 3.2.23 зэпишется значение U2, в регистр 3.2.22 — знэчение d2, В (М+8)-м такте в единицу устанавливаются триггеры 52, 58, 3.2.29.1, нэ третьем пятом, шестол вы .одэх блока управления установятся единицы. Следовэтельно, блоки регистров будут устэновлены в режим приема информэции с вычислительных модулей, т.е. будут производиться операции исчерпывэния. i tD в>>хлп кол>мутэтора 5 поступает информэция (; третьего входэ. В Т-м тэкте (где Т: M 9 2t (N+ 1)) триггеры 3.1.26, 3.1.27, 3.1 31. 2.3 29 услэнзвливэются в еди>>ицу, в (;:>.:; р . >».тров

1.1. поступает знэ>е>ц . А>. ., Ut b .

1790787

15 в регистр 3,1.18 записывается значение а, в регистр 3.3.23 — значение Оз, в регистр

3,3,22 — значение бз .

В дальнейшем работа вычислительных модулей и блоков регистров при реализации исчерпывания иллюстрируются только с помощью табл.3

Формула изобретения

1, Устройство для решения задач на собственные значения, содержащее N вычислительных модулей (N — размерность обрабатываемой матрицы), каждый из ко- 20 торых содержит узел управления, регистры с первого по четвертый и первый коммутатор, N блоков регистров, блок вычисления скалярных операций, коммутатор и блок управления, причем первый информационный 25 выход j-го вычислительного модуля (j =

1„.„N-1) соедийен с первым информационным входом (j+1)-ro вычислительного модуля, второй информационный выход 1-го вычислительного модуля соединен с первым 30 информационным входом i-га блока регист.ра ()=1...„N), первый информационный выход которого соединен с вторым информационным входом i-го вычислительного модуля, второй информационный вы- 35 ход J-го блока регистров соединен с вторым информационным входом (j + 1)-го блока регистров, второй информационный вход пер. гого блока регистров соединен с первым информационным входом устройства, пер- 40 вый и второй выходы KQTopQIQ соединены соответственно с первым и вторым выхода., ми блока вычислений скалярных операций, ° а т л и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат, в него 45 введен регистр обратной связи, а каждый из

N вычислительных модулей введены пятый и шестой регистры, второй коммутатор и арифметика-логический блок, причем третий информационный выход )-го вычисли- 50 тельного модуля соединен с третьим информационным входом (j+1)-го вычислительного модуля, первый информационный вход первого вычислительного модуля соединен с выходом коммутатора, первый и второй информационные входы которого соединены соответственно с выходом регистра обратной связи и первым выходом блока вычисления скалярных операций, информационный вход которого соединен с третьим

По окончании исчерпывания в (T+7)-м такте установится в единицу триггер 60, сбросятся в ноль триггеры 55, 58, 59, счетчик

54, — схема готова к следующей итерации, По окончании всех итераций счетчик 68 установится в единицу, сбросит в ноль регистры 43, 49, и схема приводится в исходное положение, информационным выходом N-го вычислительного модуля и входом регис.гра обратной связи, управляющие выходы с первого по пятый j.-го вычислительного модуля соединены соответственно с управляющими входами с первого по пятый (j+1) ãо вычислительного модуля, управляющие входы с первого по пятый первого вычислительного модуля соединены соответственно с выходами с первого по пятый блока управления, шестой выход которого соединен с первым управляющим входом i-ro блока регистров, первый и второй управляющие выходы j-го блока регистров соединены соответственно с вторым и третьим управляющими, входами () + 1)-го блока регистров, второй и третий управляющие входы первого блока регистров соединены соответственно с седьмым и пятым выходами блока управления, восьмой выход которого соединен с четвертым управляющим входом I-го блока регистров, шестым управляющим входом i-га вычислительного, модуля и первым. управляющим входом блока вычисления скалярных операций, второй управляющий вход которого соединен с вторым управляющим входом N-ro вычислительного модуля, второй информационный вход устройства соединен с третьим информационным входом коммутатора, первый и второй управляющие входы которого соединены соответственно с девятым и пятым выходами блока управления, вход

* Начало загрузки", синхровход-и вход "Начало работы" которого соединены соответственно с первым, вторым и третьим управляющими входами устройства, а в каждом из N вычислительных модулей второй информационный вход модуля соединен с первым информационным входом арифметика-логического блока, второй информационный вход которого соединен с выходом первого регистра, информационный вход которого соединен с выходом второго регистра, информационный вход которого соединен с первым информационным входом

1790787

10 модуля, третьим информационным входом арифметико-логического блока и информационным входом третьего регистра, выход которого соединен с первым информационным входом модуля, третий информационный вход которого соединен с четвертым информационным входом арифметико-логического блока и первым информационным входом первого коммутатора, второй информационный вход которого соединен с первым информационным входом второго коммутатора, вторым информационным вы-. ходом модуля и выходом арифметика-логического блока, пятый информационный вход которого соединен с информационным входом четвертого регистра и выходом пятого регистра, информационный вход которого соединен с выходом второго коммутатора, второй информационный вход которого соединен с входом логического нуля модуля, управляющие входы с первого по пятый которого соединены соответственно с входами с первого по пятый узла управления, первый выход которого соединен с первым управляющим выходом модуля и первым управляющим входом арифметико-логического блока, второй управляющий вход которого соединен с вторым выходом узла управления, вторым управляющим выходом модуля, управляющим входом второго коммутатора, первым управляющим входом первого коммутатора и синхровходом четвертого регистра, выход которого соединен с третьим и информационным входом пер; вого коммутатора, второй управляющий вход которого соединен с третьим выходом узла управления и третьим управляющим выходом модуля, четвертый и пятый управ5 ляющие выходы которого соединены соответственно с четвертым и пятым выходами узла управления, шестой выход которого соединен с синхровходом первого и второго регистров, шестой управляющий вход моду10 ля соединен с шестым входом узла управления и синхровходами третьего, пятого и шестого регистров, выход первого коммутатора соединен с информационным входом шестого регистра, выход которого соединен

15 с третьим информационным выходом модуля, 2. Устройство по ri.1, о т л и ч а ю щ е ес я тем, что блок вычисления скалярных

20 операций содержит узел вычисления квадратного корня, делитель и два регистра, причем информационный вход блока соединен с входом узла вычисления квадратного корня и первым входом делйтеля, выход ко25 орого соединен с информационным входом первого регистра, выход которого соединен с первым выходом блока, второй выход которого соединен с вторым входоМ делителя и выходом второго регистра, ин30 формационный вход которого соединен с выходом блока вычисления квадратного корня, первый и второй управляющие входы блока соединены соответственно с синхровходами первого и второго регистров.

1790787

С 4

С4

С )

С4

С4

1790787

1790787

18

179078?

1790787

1790787

1790787 < () !Я7

1790787

Составитель Ю.Каневский

Техред М.Моргентал Корректор M.Càìáoðñêçÿ

Редактор

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

Заказ 376 Тираж Подписное . ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5