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

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

Иллюстрации

Показать все

Реферат

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных матричных вычислителей. Целью изобретения является расширение функциональных возможностей устройства за счет выполнения умножения матриц, вычисления определителя и элементов присоединенной матрицы. Устройство содержит матрицу N х N вычислительных модулей, где N - размерность обрабатываемых матриц, коммутатор, блок управления и N-1 регистров. Работа устройства основана на преобразовании исходной либо расширенной матрицы в единичную методом Гаусса-Жордана (в режиме обращения матриц и решения систем линейных уравнений) или в треугольную по алгоритму исключения Гаусса (в режиме LV-разложения матриц). К особенностям работы устройства следует отнести систолическую организацию процесса вычислений и возможность простого наращивания размерности вычислительной среды. 3 з.п.ф-лы, 6 ил.

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

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

РЕСПУБЛИК

„„SU „„1575205

А1 (g1)5 G 06 F 15/347

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н А ВТОРСНОМ,Ф СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (21) 4475790/24-24 (22) 18.08.88 (46) 30.06.90, Бюл. 9 24 (7!) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) Ю.С. Каневский, И.К. Клименко, С.Э, Котов, Л.11, Логинова и Н.Е. Куц (53) 681.32(088,8) (56) Авторское свидетельство СССР

Ф 1401478, 1986.

Авторское свидетельство СССР

Р 1443003, кл. С 06 Р 15/347, 1987, (54) УСТРОЙСТВО ДЛЯ ОПЕРАЦИЙ НАЦ МАТ-

РИЦАМИ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных матричных вычислителей. Целью изобретения является расИзобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных устройств, предназначенных для решения систем линейных уравнений.

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

На фиг. 1 представлена структурная схема предлагаемого устройства для операций над матрицами; на фиг.2 вЂ” схема (1,i)-ro вычислитель2 ширение функциональных возможностей устройства за счет выполнения умножения матриц, вычисления определителя и элементов присоединенной матрицы..

Устройство содержит матрицу ИяЯ вычислителымх модулей, где И вЂ” размерность обрабатываемых матриц, коммутатор, блок управления и Я-1 регистров. Работа устройства основана на преобразовании исходной либо расширенной матрицы в единичную методом Гаусса-Жордана (в режиме обращения матриц и решения систем линейных уравнений) или в треугольную по алгоритму исключения Гаусса (в режиме и-разложения матриц). К особенностям работы устройства следует отнести систолическую организацию процесса вычислений и воэможность простого наращивания размерности вычислительной среды. 3 з.п, ф-лы, 6 ил. ного модуля; на фиг.- 3 вЂ” схема (j, К)-го вычислительного модуля; на фиг. 4 вЂ” схема (j A)-го вычислительного модуля (° вЂ” 2,Ь; К вЂ” 1„П 1р 1-1рЯ, N вЂ” размерность обрабатываемых матриц); на фиг.5 вЂ” блок управления, один из вариантов построения; на фиг,б вЂ” диаграммы состояний выходов .блока управления в режимах решения систем линейных уравнений и обращения матриц (a), вычисления элементов присоединенной матрицы (б) перемножения матриц (в), LH-разложения матриц (г), вычисления определителя и элементов присоединенной матрицы (д).

15!5205

Устройство для операций над матрицами (фиг.l) содержит матрицу N N (N вЂ” размерность обрабатываемых матриц) вычислительных модулей 1, коммутатор 2, N-1 регистров 3, блок 4 управпения. (l,i)-й (i=1,N) вычислительный модуль содержит первый 5 и второй 6 регистры, первый 7 и второй 8 информационные входы, третий 9, четвеРтые

10 и пятый 11 регистры, третий информационный вход 12, первый коммутатор

13, делитель 14, второй 15 и третий

16 коммутаторы, первый 17 и второй 18 информационные выходы, умножитель 19, четвертый коммутатор 20, третий 21 и четвертый 22 информационные входы, семиразрядный регистр 23 управления, первый 24, второй 25, третий 26, четвертый 27, пятый 28, шестой 29, седь- 2{1 мой 30 входные и первый 31, второй

32, третий 33, четвертый 34, пятый 35, шестой 36, седьмой 37 вь!ходные разряды регистра управления, образующие управляющие вход и выход вычислитель- 25 ного модуля. (j,Ê)-и вычислительный модуль (фиг. 3) (j=2 N- K=1 N-1) содержит первый 38 и второй 39 регистры, первый 40 и второй 41 информа-. ционные входы, третий 42, четвертый ур

43 и пятый 44 регистры, третий 45 и четвертый 46 информационные входы, шестой регистр 47, первый коммутатор

48, умножитель 49, второй коммутатор

50, сумматор-вычитатель 51, первый

52, третий 53, второй 55 и четвертый

56 информационные выходы, четырехразрядный регистр 57 управления, первый

58, второй 59, третий 60, четвертый

61 разряды управляющего входа, пер- 10 вый 62, второй 63, третий 64 и четвертый 65 разряды управляющего выхода. (j,N)-A (j=2,Ы) вычислительный модуль (фиг.4) содержит первый 66 и второй 67 регистры, первый 68 и второй 69 информационные. входы, третий

70, четвертый 71, пятый 72 регистры, третий 73 и четвертый 74 информационные входы, шестой регистр 75, первый коммутатор 76, первый умножитель 77, второй коммутатор 78, сумматор"вычи". татель 79, второй умножитель 80, третий 81 и четвертый 82 коммутаторы, 55 первый 83, второй 84, третий 85 и четвертый 86 информационные выходы, регистр 87 управления, первый 88, второй 89, третий 90, четвертый 91, пятый 92 разряды управляющего входа, первый 93, второй 94, третий 95, четвертый 96 и пятый 97 разряды управляющего выхода.

Блок управления (фиг.5) содержит элемент И 98„ счетчик 99, синхровход

100, ПЗУ микрокоманд 101, первый !02, второй 103, третий 104-110, ° четвертый 111-113, пятый 114-117 и шестой

ll8-122 выходы. Синхровходами всех вычислительных модулей (не обозначены) являются входы разрешения записи регистров управления, Устройство для операций над матрицами преднаэчено для решения систем Ы линейных уравнений методом Гаусса-Жордана, умножения матриц размерности N N,, выполнения LU-разложения, вычисления обратной матрицы, определителя и присоединенной матрицы. При решении систем линейных уравнений, при вычислении обратной матрицы и элементов присоединенной матрицы выполняется обраоотка расширенной матрицы, размерности N<М, которая представляет собой исходную матрицу размерности N N к которой справа дописана матрица размерности N<(M-N) . Вычис- . ление определителя и LU-разложение основаны на преобразовании исходной матрицы в треугольную, При вычислении системы линейных уравнений к исходной матрице (N N} справа дописывается S столбцов свободных членов (в этом случае М=М+$) и после того, как исходная матрица преобразована в единичнул, на месте столбцов свободных членов получаем семейство решений данной системы уравнений. Число S при данной организации вычислений может быть любым натуральным. Вычисления производятся по следующим формулам: (e (к-<) (к-<) а„а„; /а „„, K=1 2...,,N; х,3 =К+1, K+2...,Ч, (к1 (к- ) (к-i) (k- ) (q i) а; à, à„„„„° а(1 =а", 11 ij

При вычислении обратной матрицы к исходной матрице справа дописывается единичная матрица размернос-. ти N>N (a этом случае 11=2N) и после того, как исходная матрица преобразована в единичную, ка месте приписанной справа единичной получаем обрат5 15 ную, Вычисления выполняются по тем же формулам, что и решение систем линейных уравнений.

При LU-разложении матриц выполняется разложение данной квадратной матрицы А размерности N на две треугольные: нижнюю левую L и верхнюю правую

U„ aKHe To LU=A, причем на главной диагонали одной из треугольных матриц состоят единицы. Преобразование матрицы А=(а; выполняется по алгоритму исключения Гаусса, в процессе которого получаются элементы 1

H V<1< (к) (к-<) (к- ) / (к- ) (к-<)

« к«<<< а(o) =а", <1 <1

k=1,2,...,N; j, i=K+1, К+2, ° ..,1<1, а кк > <1 к

k=1,2,...,N, i,j=K, К+) ...,,N. а <» а, а<>

az2. ага

А = а < айаг аз а

25 допишем рицу

1 О О

О 1 О

О О 1 ь„ь, ь, ьг< ьг2 ь 23 ьи ьм ьзз

С< С<6

Сг Cz<

С < С<4!

Сг, < Сы l

< с„, с„

c„c«

;с= с с

Сз< См

С С>6

I щим сигналам "11" поступающим с шес того и седьмого разрядов регистра управления 23.1,1, через коммутатор

16.1.1 поступает на первый 17.1.1 вы45 ход, а через коммутатор 15.1,1 по нулевому сигналу, поступающему с четвертого разряда регистра управления

23.1.1, поступает на второй информационный выход вычислительного модуля

50 (о)

1 8 . 1 . 1 . Элемент С г< принимается в регистр 38.2.1 через коммутатор

48. 7 . .1 . По единичному сигналу элемент

55 С поступает на первый вход умно(о) г< жителя 49.2.1. (о)

В третьем такте элемент С па

Режим вычисления определителя отличается от режима LU-разложения тем, что в процессе преобразования матрицы перемножаются элементы а„„, т.е. (<)

det= g а„ (<1

«-Вычисление элементов присоединенной матрицы является объединением режимов вычисления обратной матрицы и определителя, так как А =det А

+ -<

Элементы матрицы С поступают на входы вычислительных модулей построчно со сдвигом на один такт, т.е. первая строка поступает на первый вход вычислительного модуля 1.1.1, начиная с первого такта; вторая строка поступает на первыи вход вычислительного модуля 1,2,1, начиная с второго такта; третья вЂ” на вход вычислительного модуля 1.3,1, начиная с третьего такта. В первом такте элемент (o)

С « =1, принимается в регистр 5. 1 ..1 ..

<0)

Во втором такте элемент С, принимается в регистр 6.1.1, на выход- дели (о) теля 14.1.1 получаем частное С, / (о) (<1

/С„ =U, С,, которое по управляю75205 6 т .е. вычисляется обратная матрица н параллельно определитель (det), а затем выдаваемые элементы обратной матрицы умножаются íà det.

При умножении матриц С=А В элементы матрицы-произведения вычисляются по формуле

10 с;; = ;„ь„,.

<<= i

Рассмотрим работу устройства при вычислении обратной матрицы размерностью 3«3.

Условимся, что информация в регистры принимается в начале такта по заднему фронту синхроимпульса и определитель исходной матрицы не равен нулю. Итак исходная матрица к ней справа единичную мати получим расширенную матрицу С, над которой выполняется преобразование а а а<э 1 О О

«<г

I а, а,г агз I

1 О

О О а, азг азъ 1 ступает в регистр 6.1.1. На выходе

15752 делителя !4.1.1 получаем частное (о) <о) (s)

С, С „=!1, =С „,, которое по управ ляишим сигналам "11" через коммута5 тор 16.1.1 поступает на первый выход

17.1.1, а через коммутатор 15.1.1 по нулевому сигналу поступает на второй информационный выход вычислительного модуля 18.1.1. Элемент. (o)

С принимается в регистр 39.2;1, (о) а в регистр 42.2.1 принимается С /

<о)

/С ц . На выходе умножителя 49.2.! (о),(о) (a) получаем произведение С „ /С „ С которое поступает на вход сумматоравычитателя 51.2.1 и íà его выходе по() (о) (0) (O) лучаем выражение С -"С -С, /С„ « 2О (о)

«С „=!. (о)

° В четвертом такте элемент С приикается в регистр 6.1.1. На первом

17.1.1,.и на втором 18.1.1 информа25 ционных выходах вычислительного моду(о) (о) ля 1.1.1 получаем частное (:« /C« (6 .С . В регистр 42.2.1 поступает (o) (о)

ЗО

С„ /С..„, в регистр 39.2.1 вЂ” элемент С . На выходе умножителя (о)

4 9 . 2 . 1 получаем .произведение С „ / (о) (о)

/C « . С,, которое поступает на 35 второй вход сумматора-вычитателя

51.2.1, на первый вход которого по-. (о) ступает элемент Сд . На выходе сумматора-вичитателя 51. 2. 1 получаем 4О (о) (о) (о) (о) (q)

С -С, /С „, С, =С з, В регистр (o) (о)

42.3.1 поступает С „ /С „,, в регистр (о)

3 9 . 3 . 1 вЂ” элемент С, на. выходе ум- 45 ножителя 4 9 . 3 . 1 получаем произведение (о) (о) (о)

С /С и С,, на выходе сумматора() вычитателя .51. 3. 1 получаем С (о) (о) (о) (o)

С -С !С „° С .„1уг, Элемент (4)

С =1 поступает в регистр 5 . 1 ° 2 . (о)

В пятом такте элемент С, принимается в регистр 6.1.1 вычислительного 55 модуля 1.1.1 На первом 17.1.!.и втором 18.1.1 информационных выходах ко(о) (о) торого получаем частное С,о /С, 05 8 (i)

=С,> . В регистр 42.;?.! принимается (о) (о)

С С ц, в регистр 39. 2. 1 вЂ” элемент (о)

С, на выходе умножителя 4 9 . 2 . 1 (о) (о) (о) получаем произведение С,« /С д„С которое поступает на второй вход сумматора-вычитателя 51.2,1, на первый вход которого поступает элемент (о)

С . На выходе сумматора-вычитателя (о) (о) (o) (о)

5 I 2. 1 получаем С < -С „ /С щ ™ С (i)

=С . В регистр 4 2 . 3 . 1 принимается (о) (о)

С „ / С ц, в регистр 3 9 . 3 . i вЂ” элемент

С, на выходе умножителя 49 . 3 . 1 поФ (о) (о) лучаем произведение С „ /С „; С на выходе сумматора вычитателя 51,3. 1(О) (o) (o) . (0) (o)

-С =С -С„ /С„,,С,, =1 . B регистр 6. 1. 2 принимается элемент (<)

С д. вычислительного модуля 1 . 1 ..2, на первом 17.1.2 и втором 18.1.2 информационных выходах которого полу() (i) чаем частное С /С =1 э . Элемент . (q)

С принимается в регистр 38.2.2, (i) а элемент С„ вЂ” в регистр 2.1.

В шесток такте С принимается в (о) регистр. 6.1. 1 вычислительного модуля 1,1.1, на первом 17.1.1 и втором

18.1.1 информационных выходах которо(о) (о) (<) го получаем час гное С „ь /С ц =С,о

На выходе умножителя 49.2.1 получаем (o) (о) (0) произведение С „ /С, С, которое оступает на второй вход сумматора° ° ° ° ° ° вычитателя 51.2.1, на первый вход ко,торого поступает элемент С . На вы(о). ходе сумматора-вычитателя 51.2.1 по(a) (о) (о) (о)

Мучаем выражение Со =Со -С, /С, x (0)

«С „. На выходе умножителя 49.3.1 (о) (о) (o) получаем произведение С„ /С и ° С, которое поступает на второй вход сумматора-вычитателя 51 3.1, на первый (о) вход. которого поступает С . На выходе сумматора-вычитателя 51.3.1 получаем С > =С. + -С„ /С „° С, . На

i ) (о) (о) (о) () первом 17 1.2 и втером 18,1.2 информационных выходах вычислительного

9 15 модуля 1 - получаем частное С2Ф /

2 (1) (1) (z)

/Сгг =С zq . На выходе сумматора-яычи(2) (1) тателя 51.2.2 получаем С =C

„(e) И (1) . (1), гз /C zz С г =1-зз ° Элемент С rz принимается в регистр 38.3.2, а элемент (1)

С, вЂ” в регистр 2.1. В седьмом такте на выходе умножителя 49. 2. 1 получаем произведение, (о) (о) (o)

С, /С,1< С,, которое поступает на второй вход сумматора-вычитателя

51.2.1, на первый вход которого по(0) ступает элемент С < . На выходе сумматора-вычителя 51 . 2. 1 получаем выра(о) (о) (1) (о) С 16 С г1 жение Сг =Сгб (о) на выхоС 11 де умножителя 49.3.1 получаем произ(о) (о) (о) ведение С,. /С1, ° C,, которое поступает на второй вход сумматора-вычитателя 51.3.1, на первый вход кото(о) рого поступает С . На выходе сумматора-вычитателя 51..3.1 получаем (1) (о) (о) (о) (о)

С =С >< -С,з /С „С 1 . На первом

17.1.2 и втором 18.1.2 информационных выходах вычислительного модуля 1.1.2 (1) (1) (г) получаем частное С /С =C . На выходе сумматора-нычитателя 51.2.2 (г) (1) (1) (1) (<) получаем Г, + =С, -С, /С z ° С зг

На выходе сумматора-вычитателя 51.3.2 (Z) (1) (1) (1) (1) получаем С1 =С, -С г /С г С „ (z)

Элемент С принимается в регистр (1)

5,1.3, а элемент С вЂ” в регистр 2.1.

В восьмом такте на выходе умножи(а) (о) (o) теля 49.3.1 получаем с, Г. 1g /с 11 которое поступает на второй вход сумматора-вычитателя 51,3.1, на пер(о) вый вход которого поступает С,, На выходе сумматора-вычитателя получаем (1), (о) (о} (о) (о) выражение С. =С 6 -Г„ /C „С З1 которое поступает на первый информационный выход вычислительного модуля

1.3.1. На первом 17.1.2 и втором

18.!.2 информационных выходах вычис75205 лительного модуля 1.!.2 получаем ча(<) (<) (г) стное С /Г zz Г 26, Ни выходе сум матора-вычитателя 51.2.2 получаем

Ф И) (1) (S) ()

С =С -С г /С г С г . На выходе сумматора-вычитателя 5 .3.2 получаем.(г) (1) (1) (1) (1) выражение С1а Г 1о -С zy /С гг С 1z

10 которое поступает на первый информационный выход 52.3.2. На выходе дели(г) теля 14.1.3 получаем частное С / (z) (3)

/С =С, которое поступает на первый 17.1.3 и второй 18.1.3 информационные выходы вычислительного моду(z 1 ля !.1.3. Элемент C„> принимается

20 в регистр 66.2.3 вычислительного мо() дуля l . 2. 3, элемент С, вЂ” в регистр (г)

2.1; а элемент С „ вЂ” в регистр 2.2.

25 В девятом такте на,выходе сумматора вычитателя 51.3.2 получаем выраже(z) () () . (1) (1) ние С =С -Сг /Сг . С.г, которое поступает на первый информационный

30 выход 5?.2.2. На выходе сумматоравычитателя 51.3.2 получаем выражение (1) (i) ((1) (i) (Z)

С С /(С з =C у которое по ступает на первый информационный выход 52.3.2 вычислительного модуля

1.3.2. На выходе делителя 14.1 ° 3 по(L) (g) (3) лучаем частное С /С = :, которое поступает на первый 17 ° 1.3 и вто40 рой 18.!.3 информационные выходы вычислительного модуля 1.1.3. На выходе сумматора-вычитателя 79,2.3 полу(z) (г) (г) (z) чаем выражение С « -С /С С 1г

45 которое поступает на первый информационный выход.83.2.3. Элемент Сг

1 принимается в регистр 66.3.3, элемент (e) (z)

С„ вЂ” в регистр 2.1, элемент С

50 16 в регистр 2.2, В десятом такте на выходе сумматора-вычитателя 5!.3.2 получаем"выраже(i) C1) (1)

55 ние. С, -С /С, которое поступает на первый информационный выход 52.3.2 вычислительного модуля 1.3.2. На выходе делителя 14.1.3 получаем частll 157 (=) <2) (Ь) ное С /С >> -С, которое поступает на первый 17.1.3 и второй-18.1.3 информационные выходы вычислительного модуля 1.1.3. На выходе сумматора-вычителя 79.?.3 получаем вь<ражение (2) (2) (22 (22 (Ъ)

С < С < /С зз С12 =С,, которое поступает на первый информационный выход 83,3.3. На выходе сумматора-вычитателя 79.3.3 получаем выражение (2) (2) (2) (2)

С, -С „, /C „r, „, которое поступает на первь<й информационный выход

83.3,3 вычислительного модуля l 3.3, (22

Элемент С принимается в регистр

2.2, В одиннадцатом такте на выходе сумматора-вычитателя 79.?.3 получаем (2) (z) Cz) (2) (ъ) выражение С 1ь -С 6 /С С „, =С 1 которое поступает на первый информационный выход 83.2.3 вычислчтельного модуля 1.2.3. На выходе сумматоравычитателя 79.3.3 получаем выражение

<2) (22 (2) (2)

С -С . /С . С з, которое поступает на первый информационный выход

83.3,3 вычислительного модуля 1,3 ° 3. (г)

Элемент С принимается в регистр 2.2.

В двенадцатом такте на выходе сумматора вычитателя 79.3.3 получаем (z) (2) 6 /С >> С > =Сг .

На этом вычисление обратной матрицы заканчивается. Начиная с восьмого такта на первых информационных выходах вычислительных модулей 1.1.3, !.2.3 и 1.3.3 появляются элементы обратной матрицы (2 <з)

С, С„

С С гц 2б

<М Ь)

С, с6

На выходах устройства получаются элементы обратной матрицы по строкам, т ° е. на выходе вычислительного модуля 1,1.3 появляются элементь< третьей строки, на выходе вычислительного модуля 1,2.3 вЂ” первой, на выходе вычислительного модуля 1.3.3 вЂ” второй строки.

)1ля общего случая N выходов распределение строк следующее: i-я

12 строка результата выдается с +1 выхода (для =1,2,...,И-1}, а М-я стро"1 ка вЂ” с первого выхода, 5

Сразу же после ввода первой строки исходной матрицы, т.е. в данном примере с седьмого такта, можно начинать вводить следующую исходную матрицу D, При решении систем линейных уравнений в качестве элементов матрицы В подаются свободные члены заданной системы уравнений. Тогда на выходе получаем семейство решений этой сис<з) темы уравнений. Столбец С, ) явля15 ется решением системы при столбце т свобоцннх членов (о,J, столбец

<М

С. вЂ” решением при столбце свободlg т. ных иленов Ь и т д

Гассмотрим работу устройства при

LU-разложении матриц размерности 3 3.

В гервом такте элемент а< „2 =). ц -<<

25 принимается в регистр 5.1.1 вычислительного модуля ) .1.1. Во втором такте элемент а„ принимается в регистр

6,1.1. На выходе делителя 14.1.1 по

3 лучаем частное а /а =Н кото

16,1.1 и нулевому сигналу через коммутатор 15.1.1 поступает соответственно на первый 17.1.1 и второй 18.1.1

35информационные выходы вычислительного модуля 1.1,1, Элемент а =1 (а)

2! -2< принимается в регистр 38.2.1.

40 В третьем такте элемент а при

19 нимается в регистр 6.1.1, на выходе делителя 14.1.1 получаем частное (о)

45 первый 17,1.1 и второй 18.1 ° 1 информационные выходы вычислительного модуля 1,1.1. Элемент а . принимается

Со2 в регистр 39.2.1 и через коммутатор

50еl.l подается на первый вход сумматора 51.1.1. В регистр 42.2.1 при(с) (о) нимается а, /а „, на выходе умножителя 49.2.1 получаем произведение й), (о) (о) а, /а ц а,, которое поступает на второй вход сумматора-вычитателя

51.2,1, на выходе которого получаем

13 !

575205 выражение а, =а -а /а, а =1 (q (о) (о1 (о) (о)

22 22 Ы 1! 1 22 которое поступает на первый информационный выход 52.2 ° 1 вычйслительного модуля !.2.1. Элемент а., =1, прини(о) мается в регистр 38.3.1.

В четвертом такте элемент а (о)

2 5 принимается в регистр 3 9 . 2 . 1, а в регистр 42 . 2 ., принимается а, /а

1, (01 (0)

На выходе умножителя 49.2.1 получаем (o) (o) (o) произведение а „ /а ц а,, которое поступает на второй вход сумматоравычитателя 51.2.1, на выходе которого получаем выражение à -à,, /a„ x (o) (о) (o) (о) (1) к а, =а, которое поступает íà первый информационный выход 52.2.1 вычислительного модуля 1.2.1. Элемент (о) а принимается в Регис тр 3 9 . 3 . 1, а в регистр 4 О . 3 . принимается а „ / (о)

/a . На выходе умножителя 49.3,1 (о) и (о) (о) (o) получаем произведение а, /a ц, а которое поступает на второй вход .сумматора-вычитателя 51 .3. 1, на выходе которого получаем выражение (1) (o) (о), (о) (o) а =а -а „ /а н а з,, которое поступает на первый информационный выход 52.3.1 вычислительного модуля

1.3.1. Элемент а =1 принимается в регистр 5.1,2, (о)

В пятом такте элемент а приниИ мается в регистр 39.3.1, а в регистр

42.3.1 принимается выражение а,> /а „ . (о) (o)

На выходе умножителя 49.3.1 получаем (о) (o) (о) произведение а „ а „- ° а,, которое поступает на второй вход сумматора-вычитателя 51.3.1, на выходе кото(о) рого получаем выражение а -а (о) / я 1з

{о) (о) ()

/a; a> =а,, которое поступает на первый информационный выход 52.3.1 вычислительного модуля !,3,1 Элемент (1) а принимается в регистр 6.1.2 ° На выходе делителя 14.1.2 получаем частИ !<),Ф яое à z> /а =U з, кото. ое поступает на первый 17.1.2 и второй 18.1,? информационные выходы вычислительного

1 при() м дчля 1 1 2 Элемент à yz 1

5 нимается в регистр 38.2.2.

В иестом такте элемент а иринимается в регистр 39 ? ? а в регистр () (() l 0 4 2 . 2 . 2 принимается а /а . Н а выходе умножителя 49.?.2 получаем про(1) (i) () иэведение я 23 /я zz. я sz которо ступает на второй вход сумматора-вы15 читателя 51.2.2, на выходе которого (2) (1) (с) получаем выражение а =а „-а з

Я ()

/ а а » = 1, которое поступает на

z2 первый выход вичислительного модуля 1.2.2. (z)

Б седьмом такте элемент а =) о

25 принимается в регистр 5.1.3 и через коммутатор 16.1.3 поступает на первый информационный выход 17.1.3 вычислительного модуля 1,1.3. Начиная с четвертого такта, можно подавать элемен30 ты следувщей матрицы, обработка котоРой выполняется аналогично.

В режиме вычисления определителя работа устройства выполняется аналогично режиму LU-разложения матриц.

Отличие заклвчается в том, что при

35 вьгчисленин определителя, в четвертом такте в регистр 1! 1.2 с четвертого информационного выхода 22.1.1 вычислительного модуля 1.1.1 принимается (о) (o)

4р а„=det которое поступает на второй вход умножителя 19,1.2, на первый вход которого через коммутатор

C1) из Регистра 5.1.2 поступает а

На выходе умножителя 19.1.2 получаем (1) (о) () произведение à det =det ко1 торов поступает на первый информационный выход 17.1.2 вычислительного моду50;ля 1.!.2. В седьмом такте в регистр

11.1.3 с четвертого информационного выхода 22.1.? вычислительного моду.ля l.!.2 принимается бег.(, который поступает на второй вход умножителя

55,19.1.3, на первый вход которого по сигналам "ОО" через коммутатор 13.1.:3 .с выхода регистра 5.1.3 поступает (Е) элемент а . На выходе умножителя

19 . .1 . 3 получаем произведение а, Йе (zy (1) (z)

=det, которое по нулевому сигналу через коммутатор 20.1,3 поступает на четвертый информационный выход 22.1.3 вычислительного модуля 1.1.3.

Р> режиме вычисления элементов присоединенной матрицы работа устройства выполняется аналогично режиму вычисления обратной матрицы. Отличие заключается B том, что при вычислении элементов присоединенной матрицы в четвертом такте в вычислительном модуле 1.1.2 элемент,С, по управ-!! ляющему сигналу 00, поступающему с четвертого и пятого разрядов регистра управления 23.1.2, через коммутатор 13.1.2 поступает на первый вход умножителя 19.1,2, где умножается на det )» поступающий на второй вход, умножителя 19.1.2. С входного регистра 11.1 2 и на выходе умножителя

19.1.2 получаем det("), который по. нулевому сигналу через коммутатор

20.1.2 поступает на четвертый инфор мационный выход 22.1.2 вычислительного модуля 1.1.2. В седьмом такте (z) йлемент С» по управляющим сигналам

"00" через коммутатор 13.1.3 поступает на первый вход умножителя 19.1.3, где умножается íà det(") и получаем

det » который поступает на третий

21.1.3 и по сигналам "10" через коммутатор 16,1.3 вЂ” на первый 17.1.3 информационный выход вычислительного модуля 1.1.3. В восьмом такте на выходе умножителя 80.2,3 получаем про(з) (г) (2) изведение С 1 =С 1 det, которое чсрез коммутатор 82.3.3 по нулевому

75205 1î сигналу поступающему с четвертого выхода регистра 87.2.3 управления поступает на первый информационный выход 83.2.3 вычислительного модуля

1.2.3. В девятом тайте на выходе сумматора-вичитателя 79.2.3 получаем выражение С,q -С /С» С, =-С,+ (z) (z) (z) (z) (ъ) которое поступает на первый. вход ум10 ножителя 80.2.3, на выходе которого (z) (z) (г) получаем выражение (C1q, -С !C !! (z) 2 (+) ! (С, )det =C <<» которое по нулевому

1 .сигналу через коммутатор 82,2.3 поступает на первый информационный выход 83.?,3 вычислительного модуля 1 2 3 На выходе умножителя 80 3 3 в девятом такте получаем С, кото20 рое по нулевому сигналу поступает на первый информационный выход 83.3.3 вычислительного модуля 1.3.3. В десятом такте на выходе умножителя 80 ° 2.3 (2) (2) (2) получаем выражение (С „-С /С» (г) (2) () !!С, ) ° det =С „, которое поступает на первый информационный выход 83,2,3 вычислительного модуля 1.2.3. На выходе сумматора"вычитателя 79.3.3 поЗО (2) (i) (г) (г) лучаем выражение Сг -С /Сse Сг = (3)

=С 2.»» которое поступает на первый информационный вход умножителя 80,2.3, на выходе которого получаем выражение (z) (z) (2) (г) (z) (5) (С !(-Сз /С >> С z> ) det =С z<, которое поступает на первый информационный выход 83.3.3 вычислительного модуля 1.3.3.

Рассмотрим работу устройства при умножении матриц размерности 3 13.

C«C12 C„

С, Cz«С

С»! С»2 Си ь!! ь, ь, >zz а(! а 2 а1> ая» агг аг х

).!»2 1» ЭЗ

) а»! аЗ2 аЗ»

В первом такте на второй информационный вход 8.1.1 вычислительного модуля 1.1.1 поступает элемент а 11, который принимается во входной регистр 10.1.1 и по нулевому сигналу, поступающему с четвертого разряда регистра 23.1.1 управления, через коммутатор 15.1.1 поступает на информационный выход 18.1,1.

Во втором такте элемент а1 принимается в регистр 43.2.1, элемент

Л.. а - в регистр 10 1.1 и по нулевому

5() сигналу через коммутатор 15.1.1 поступает на информационный выход

18.2.1, а элемент а< поступает на информационный выход: 18.1.2.

55 В третьем такте элемент а1 пересылается в вычислительный модуль

1.3.1 и принимается в регистр 42.3.1, элемент а 12 - в регистр 42. ". 1, элемент а вЂ” в регистр 9.1.1. Элемент

15752 а, принимается в регистр 43 2. 2, элемент а вЂ” в регистр 9.1.2, а элемент азэ вЂ” в регистр 10.1,3, В четвертом такте на третий информационный вход 12.1.! вычислительно5 го модуля 1.1.1 поступает элемент Ь «, который принимается в регистр 11.1.1. 1!а выходе умножителя 19.1.1 получаем произведение a,« b«, которое поступает на третий информационный выход

21.1.1 вычислительного модуля 1.1.1.

Элемент Ъ« через коммутатор 20.1.1 поступает на четвертый выход 22.1.1 вычислительного модуля 1.1.1. Элемент а 2, принимается в регистр 9.1.2, элемент а22 принимается в регистр

42.2.2, элемент а2 принимается в регистр 42.3.2. Элемент а » принимается в регистр 43.2,3, а элемент 20 а,2 вЂ” в регистр 10. 1 ° 3, В пятом такте элемент b„2 принимается в регистр 11.1.1, на выходе умножителя 19.1.1 получаем произведение а„, Ь,2, которое поступает на тре- 25 тий информационный выход 21,1.1 вычислительного модуля 1.1.1. Элемент

Ь2, принимается в регистр 44.2.1 ° На выходе умножителя 49.2,! получаем произведение а„2Ь,, которое поступает на второй вход сумматора-вычитателя 51.2.1. Произведение а « Ь „ принимается в регистр 47.2.1 и через коммутатор 50.2.1 подается йа первый вход сумматора-вычитателя 51.2.1, на выходе которого получаем выражение а «h «+а„2 Ь2,, которое поступает на третий информационный выход 53.2.1 вычислительного модуля 1.2.1 На выходе умножителя 19.1.2 получаем про-. 4p изведение а2, Ь«, которое поступает на третий. информационный выход 21.!.2, вычислительного модуля 1.1.2. Элемент а, принимается в регистр 9.1.3, элемент а 2 вЂ” в регистр 70.2.3 а эле- 45 мент а вЂ” в регистр 70.3,3.

В жестом такте элемент b > принимается в регистр 11.1.1. На выходе умножителя 19.1.1 получаем произведение a« h„>, которое поступает на третий информационный выход 21.1.1 вычислительного модуля 1.1.1. Элемент Ь22 принимается в регистр

44.2.1. На выходе умножителя 49.2.1 получаем произведение а < b«которое поступает на второй вход суммато-, ра-вычитателя 51.2.1, на первый вход которого через регистр 47.2.1 поступает произведение а„,Ъ,<. На выходе

05 I8 сумматора-вычитателя 51, 2, 1 получаем выражение а „Ь, +а,2Ь 2, которое поступает на третий информационный выход 53.2,1. Элемент h>< поступает в регистр 44.3.1. На выходе умножителя 49.3.1 получаем произведение а Ь,, которое поступает на второй вход сумматора-вычитателя 51.3.1, на первый вход которого поступает вы- ражение а и Ь„, +а, b2„ ° На выходе сум" матора-вычитателя 5!.3.1 получаем выражение a «b «+a,2 b2, +а „ Ьз, =Г «, которое поступает на третий информационный выход 53.3.! вычислительного модуля 1.3,1. На выходе умножителя

19.1.2 получаем произведение a«b«, которое поступает на третий информационный выход 21.1,2 вычислительного модуля 1 ° 1.2, На выходе умножителя

49.2.2 получаем произведение à22b2, которое посту. пает на второй вход сумматора-вычитателя 51.2,2, на первый вход которого через регистр 47.2.2 поступает произведение а 2,Ь « . На вы-. ходе сумматора-вычитателя 51.2.2 по-, лучаем выражение а, Ь„, +а22Ь2,, которое поступает на третий информационный выход 53.2.2 вычислительного модуля 1,2.2. На выхсде умножителя

19.!.3 получаем произведение а „Ъqq которое поступает на третий информа- ционный выход 21.1.3 вычислительного модуля 1.1.3.

В седьмом такте элемент Ь2 принимается в регистр 44,2.I. .На выходе умножителя 49.2.1 получаем произведение а,.2 Ь, которое поступает на второй вход сумматора-вычитателя

51,2.1 на первый вход которого через регистр 47.2. 1 поступает произведение а «b|q . На выходе сумматора-вычитателя 51, 2. получаем выражение а „, Ь, + а Ъ, которое поступает на третий информационный выход 53.2.1 вычислительного модуля 1.2.1, Элемент Ьз2 поступает в регистр 44.3.1. На выходе умножителя 49.3.! получаем произведение,, Ьз,, которое поступает на второй вход сумматора-вычитателя 51,3.1, на первый вход которого поступает выражение а, Ь, +a«b2q. На выходе сумматора-вь читаетля i . 3, получаем выражение а,< Ь,2 +а,2 b22 +а, Ь э =С 2, которое поступает на третий информационный выход 53.".1 вычислительного модуля 1 . 3. 1 . На выходе умножит еля

19.1.? получаем произведение aq

1О

ll5

50.19 157 цио нный выход 2 1 ° 1, 2 вычи слит ел ьно гомодуля 1.1.2. На выходе умножителя

49,2.2 получаем произведение а Ь которое поступает на второй вход сумматора-вычитателя 51.2,2, на пер- . вый вход которого через регистр

47.2.2 поступает произведение а« Ь .

На выходе сумматора-вычитателя 51.2.2 получаем выражение а „Ъ 1 +а,Ь, которое поступает на третий информационный выход 53.2,2 вычислительного модуля 1.2 ° 2. На выходе умножителя

49,3.2 получаем произведение а Ь j, которое поступает на.второй вход сум; матора-вычитателя 51.3.2, на первый вход которого через регистр 47.3.2 поступает выражение а,Ъ„1 +аczb 1.

На выходе сумматора-вычитателя 51.3.2 получаем выражение ад Ъ, +а zbz<+

+а » =С е< которое поступает на третий информационный выход 53.3.2 вычислительного модуля 1,3. 2. На выходе умножителя 19.1.3 получаем произведение а> Ь1, которое поступает на третий информационный выход

21.1,3 вычислительного модуля 1.1.3.

На выходе умножителя 77.?.3 получаем произведение а b « которое поступает на первый вход сумматора-вьиитателя 79,2.3, на второй вход которого через регистр 75.2.3 и коммута,тор 78.2.3 поступает произведение а.

В восьмом такте элемент Ъ поступает в регистр 44.3.1. На выходе умножителя 49.3.1 получаем произведение а, Ь, которое поступает на второй вход сумматора-вычитателя 51.3.1, на первый вход которого поступает выражение ац Ъ„ +а„ Ь . На выходе сумматора-вычитателя 51.3.1 получаем аи Ь„ +а byy+a

l.. 3.. 1. .На выходе умножителя 49.2.2 получаем произведение а Ъ >, которое поступает на второй вход сумматора:вычитателя 51.2.2, на первый вход которого через регистр 47.2.2 поступает проИзведение а«Ь.„ .Ha выходе сумматора-вычитателя 51.2,2 получаем а,Ь„ +а Ь, которое поступает на третий информационный выход 53.2.2вычислительного модуля 1.2.2. На вы-.

5205 20 ходе умножителя 49.3.2 получаем произведение а„ Ь, которое поступает на второй вхпд сумматора-вычитателя

51.3.2, на первый вход которого через регистр 47.3.7. поступает выражение а Ь1 +а Ь . На выходе сумматора« вычитателя 51.3.2 получаем а Ь „z+

+а Ь +а,b>z.=qz, которое поступает на третий информационный выхоп 53.3.2 вычислительного модуля 1„3.2, На выходе умножителя 19.1.3 получаем произведение а,Ь,, которое поступает на третий информационный выход 31.1.3 вычислительного модуля 1.1.3, На выходе умножителя 77.2.3 получаем произведение à zb«, которое поступает на первый вход сумматора-вычитателя

79,2.3, на второй вход которого через регистр 75.2.3 поступает произведение а <Ь . Па выходе сумматора-вычитателя 79.2.3 получаем выражение а,Ь„ +a> Ь, которое поступает на третий информационный выход 85,2,3 вычислительного модуля 1.3,2, На выходе умножителя 77.3.3 получаем произведение а Ь,, которое поступает на первый вход сумматора-вычитателя

79 ° 3.3, на второй вход которого через регистр 75.3.3 поступает выражение а>, Ь,„+а Ь „. На выходе сумматоравычитателя 79,3 ° 3 получаем а,Ь +

+аэ Ь«:+а b» =Сэ,, которое поступает на третий информационный выход

85.3.3 вычислительного модуля -1.3.3.

В девятом такте на выходе умножителя 49.3.2 получаем произведение а b, которое. поступает на второй

Ь- А вход сумматора-вычитателя 51.3.2, g0 на первый вход которого через регистр 47.3.2 поступает выражение а Ь1 +а Ь >. На выходе сумматоравьиитателя 51, 3.? получаем а Ъ „ +

+а Ьэ ьа Ъэз =С, которое поступает на третий информационный выход 53.3.2 вычислительного модуля 1.3.2. На выходе умножителя 77.2.3 получаем произведение а Ь, которое поступает на первый вход сумматора-вычнтателя

79.2.3, на второй вход которого через регистр 75.2,3 поступает произведение а> Ъ1 . На выходе сумматоравычитателя 79.2.3 получаем выражение а,Ь +а b, которое поступает на третий информационный выход 85.2.3 вычислительного модуля 1.2.3. На выходе умножителя 77.3.3 получаем произведение а Ь, которое поступает на первый вход сумматора-вьиитателя

21 .1575205

79,3.3, на второй вход которого через регистр 75.3.3 поступает выражение а, b, +а Ь z, На выходе сумматора-вычитателя 78.3.3 получаем а,Ь<г, +a»b-,г+аээЬэг =Сээ> которое поступает на третий информационный выход 85.3.3 вычислительного модуля 1.3.3.

В десятом такте на выходе умножителя 77.3.3 получаем произведение аэ Ьээ, которое поступает на первый вход сумматора-вычитателя 79,3.3, на второй вход которого через регистр

75.3.3 поступает выражение аэ,Ь,э +

+аэ Ьгэ. На выходе сумматора-вычитателя 79.3.3 получаем аэ, b, +à h + эг гэ

+аээ Ь q =C зэ, которое поступает на третий информационный выход 85.3.3 вычислительного модуля 1,3.3.

Дальнейная работа устройства в данном режиме аналогична указанной„

Начиная с четвертого такта, на входы

18,1.j начинает подаваться следующая матрица Э=(й:,Д аналогично действиям матрицы А.=.-1а 1. При наращиваI) ) нии размерности предлагаемое устройство не требует увеличения количества связей с блоком управления.

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

1. Устройство для операций над г матрицами, содержащее N вычислительных модулей {N вЂ” размерность обрабатываемых матриц), N-1 регистров и блок управления, причем первый инАормационный вход (i,l)-го вычислительного модуля является 1.-м информационным входом устройства (i=1 Н), первый информационный выход (i,M)-ro вычислительного модуля является i-м выходом устройства, первый инАорма(1, 1 ) -I o вычислитель кого модуля (j =2,N) является (j+N-1)- м выходом устройства, первый информационный вход {l,j)-го вычислительного модуля {1=1,V-1) подключен к первому информационному выходу (1+1, j-1)-го вычислительного модуля, первый информационный вход (N,j)-го вычислительного модуля подключен к выходу (j-1)-го регистра, второй информационный вход (j,i)-го вычислительного модуля подключен к второму информационному выходу (j-l,i)-ro вычислительного модуля, первый выход блока управления подключен к синхровходам всех регистров и к синхровхадам всех вычислительных модулей, о т ° л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет выполнения операций умножения матриц, вычисления

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

Патент 1575205