Устройство для операций над матрицами
Изобретение относится к вычислительной технике и может быть исполь зовано для выполнения матричных one- раций. Целью изобретения является ; расширение функциональных возможностей . Устройство содержит N операци - онньгх блоков 1, N- элементов 2 держки и распределитель 3 импульсов Операционный блок 1 ,1 . j содержит вход ной регистр и блок деления J ,N, операционный блок 1.i.j(,N, j r/N) содержит два регистра сомножителей , умножитель, вычитатель, выходной регистр. Поставленная цель достигается за счет введения новых элементов и связей. 8 ил.
СОЮЗ СОЕЕТСНИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК
А1
<5i! q G 06 F 15 347
ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР
ПО.ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ
H АВТОРСКОМ,Ф СВИДЕ ГЕЛЬСТВУ (21) 4191972/24-24 (22) 04,02,87 (46) 07.12.88. Бюл. У 45 (71) Киевский политехнический институт им.50-летия Великой Октябрьской социалистической революции (72) IO.Ñ.Êàíåâñêèé и С.3.Котов (53) 681.32 (088.8) (56) Седухин С.Г. Параллельная интерпретация прямых методов линейной алгебры. — Программирование, 1984, У 4.
Авторское свидетельство СССР
O 1401478, кл. G 06 Р 15/347, 1986. (54) УСТРОЙСТВО ДЛЯ ОПЕРАЦИЙ НАД
МАТРИЦАМИ
„„SU„„1 443ОО (57) Изобретение относится к вычисли. тельной технике и может быть использовано для выполнения матричных опе-; раций. Целью изобретения является; расширение функциональных возможностей. Устройство содержит N операци— а онных блоков 1, N-? элементов 2 за держки и распределитель 3 импульсов
Операционный блок 1,ll.j содержит входной регистр и блок деления 1,М, операционный блок 1.i.j(i 2,N
=Г,??) содержит два регистра сомножителей, умножитель, вычитатель, выходной регистр. Поставленная цель дос- < тигается за счет введения новых элементов и связей. 8 ил.
1443003
Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных устройств, " редназначенных для решения систем лиl нейных уравнений, Цель изобретения — расширение функциональных возможностей эа счет решения систем линейных уравнений и обращения матриц.
На фиг.l представлена структурная схема устройства для операций над матрицами; на фиг.2 - функциональная схема операционного блока 15
I.j(j-1,2,...,N); на фиг.3 — функциональная схема операционного блока
i. j(i=2,3,...,N; j 1,2»...»И);на фиг,4 — функциональная схема элемента задержки К(К=1,2,...,N-I); 20 на фиг.5 — схема распределителя импульсов; на фиг.б — 8 — блок-схема алгоритма функционирования устройства, и
Устройство содержит N операционных блоков I.i,j(i,j =I,N), N-1 элементов 2 задержки, распределитель 3 импульсов.
Операционный блок ° !.j(j I,N) содержит входной регистр 4, блок 5 30 деления, синхровход 6.
Операционный блок I.i j (i 2,N;j
= l . N) содержит регистр 7 первого сомножителя,умножитель З,вычитатель 9, регистр 10 второго сомножителя, выходной регистр ll, синхровходы 12—
l4. Элемент 2.К (K=I,N-I) содержит регистры 15 и 16 и синхровходы !7 и 18 °
Распределитель 3 содержит генератор 19 синхроимпульсов, элемент И 20 счетчик 21 тактов, блок 22 памяти микрокоманд, выходы 23-29 распредели. теля.
Выход 23 подключен к управляющим входам 6,1.1 и 6.1.3, выход 24 — к управляющим входам 12.2.1 и 12.2.3, выход 25 — к входам 12.3.1 и 12„3.3, выход 26 — к входу 6,1..2, выход 27 к входу 12.2.2, выход 28 — к входу
12. 3, 2, выход 29 — к управляющим входам 13.2.1, 13,3.1, 13.2.2, 13,3.2, 13.2,3, 13.3,3, 14.2.1, 14,3.1, 14,2.2,.14,2.3, 14.3.3, 17.1, 17.2, l8,l, 18.2.
Устройство для операций над матрицами может выполнять LU-раэложе:чие, вычислять обратную матрицу, решать систему N линейных уравнений методом
Гаусса-Жордана. Вычисления основаны на преобразовании исходной матрицы в треугольную для LU-разложения либо в единичную.Для получения LU-разложения устройство обрабатывает исходную матрицу размерности N » N. При решении системы линейных уравнений и при вычислении обратной матрицы выполняется обработка расширенной матрицы размерности И » М, которая представляет собой исходную матрицу размерности
N » N, к которой справа дописана матрица размерности И»(М-N).
При вычислении обратной матрицы к исходной матрице справа дописывается единичная матрица размерности
N»N (в этом случае М=2 N) и после того, как исходная матрица будет преобразована в единичную, на месте приписанной. справа единичной получим обратную.
При решении системы линейных уравнений к исходной матрице (И»N) справа дописывается S столбцов свободных членов (в этом случае If=N+S) и после того, как исходная матрица будет преобразована в единичную, на месте столбцов свободных членов получим семейство решений данной системы линейных уравнений ° Число S при данной организации вычислений может быть любым натуральным, Все перечисленные алгоритмы объединяют идентичность базовой операции преобразования: !
< -! (- (к-! (o) а„= а; ; (х (K-1) (y, y) а„» а „ /а„„, К = 1,2...,,N, ij = K+I,Ê+2,...,N, При этом для LU-разложения (»- ) (»-
К = 1,2,...,И, ij = K,K+I, К+2,...,N.
Поскольку все вычисления выполняются аналогично, для примера рассмотрим работу устройства при вычислении обратной матрицы размерности 3 3.
Условимся, что информация в регистры принимается в конце такта!
443003 а«а„а, 2< 22 13
3< 32 ь«ь ь„ ь1z ь23 ь» b yz ьз
l 0 0
0 1 0
0 0 1 с«с, с„! с„с„с„!
C,C С„!
С<«С < С<
С С С, с„с„с
25 а< а! 1 0 0
gz gzz абаз а„а, а» 0 0 !
55 и определитель исходной матрицы не равен нулю. Итак, имеется исходная матрица
)О
Допишем к ней справя единичную матрицу и получим расширенную матрицу С, под которой будет выполняться пре- 20 образование
Элементы матрицы С поступают на входы операционных блоков построчно со сдвигом на один такт, т,е, первая
35 строка поступает на первый вход операционного блока 1.1.1, начиная с первого такта, вторая строка поступае т на первый вход операционного бло40 ка 1,2.1, начиная с второго такта, третья — на вход блока 1. 3. 1, начиная с третьего такта. (а)
В первом такте элемент С„ = 1„ принимается в регистр 4.1.1. Во вто(о) 45 ром такте элемент С, поступает на вход блока 1.1.1 на выходе которого получается частное С « /С „ = о, (о) < (o) (<)
= С, .Это частное в конце такта прини<<( мается в регистр 10. 2. 1 блока 2. 1, -. 50 а элемент С, = 1, принимается в (о) регистр 7,2.1.
В третьем такте элемент С<> поступает на вход блока 1.1.1, на выходе которого получается частное
С, /С „ = U = С,з . Элемент поступает на первый вход блока 1.2,1. На выходе умножителя 8.2.1 получается (o) (о) (о) произведение С,„ / С, С ;, которое по с т уп а е т на вход вычи тателя 9 . 2 . 1, и н а е г о выходе получается выраже(<) (о) (о) (о) (о) ние С, = C — С< /С«С < 1 . (o) (о)
В конце такта частное С,> /С (<)
С„принимается в регистр 10,2,1, (о) (о) (<) частное С, /С„= С, — в ре(<) гистр 10.3,1, С записывается в (o) в регистр l 1 . 2 . I, элемент С )< 1» в регистр 7, 3 . 1 . (а)
В четвертом такте элемент С<,) подается на вход блока 1,1.1, на выхоце которого получается частное (о) (о) (<)
С / С = С, н а выходе умножи те14 «<4 (0) (а> ля 8,2.1 — произведение С, /С„ «
« С которое подается на вход (о)
< вычитателя 9.2 ° 1. На второй вход вычитателя поступает элемент (Î)
С, и на выходе вычитателя 9.2.1 (<) (а) (o) (о) (o) получается С z> = С вЂ” С,< /С«с <.
На выходе умножителя 8.3.1 получа(о) (о) (о) ется произведение С < /C «С,, на первый вход блока 1.3.1 поступает (o) элемент С)< и на выходе вычитателя (<) (о) (о)
9 . 3, 1 получается C > = С -С< /
/С «C, = 1 . В конце такта част(о) (о) ное С /С = С принимается в ре(о) (о) (<)
<4 « <4 (o) (o) гистр 10. 2. 1, частное С < /С „ (<)
<Ъ
С вЂ” в регистр 10.3.1, частное
С < /С„= С,, — в регистр 15.1, (o) (о) (<) и)
С записывается в регистр 4.1.2, ы ()
С z) — в регистр 11.2.1 С, — в регистр 11.3.1. (а)
В пятом такте элемент С, подается на вход блока 1, l . !, н а выходе (о) (а) (< ) которого получается С < /С „ C « на выходе умножителя 8.2.1 — произведение С<4 /С „ ° С,, на выходе вычи(о) (о) (а), (<) (о) тателя 9 . 2 . 1 — выражение С 4 С 4С / С С на выходе умножителя (а) (о) (о)
« (а) (о) (а)
8, 3. 1 — произведение С, /С „С ><, а на выходе вычитателя 9,3.1 — выраже(<) (о} (о) (о) (а) ние С з = C» С,>/С„, ° Сз
43003
5 1Д
С выхода регистра 11,2.1 С, поступает на вход блока 1,1.2, на выходе которого получается частное (!) (1} (2}
Г 2З /С гг )}гз = Сгз ° В конце такта (a) (o) (1) частное С, -/С и = С1 принимается в регистр 10.2, 1, частное С 14 /С„ (1)
С14 — в регистр 10.3.1, частное, (О) (о}, (1)
С, /Г и = С, — в РегистР 15, 1, ча(о) (o) (1) с тно е С, / Г „ = Г, г — в Р е гистр (1) (1) (z) частное Сг /С = Сг — в РегистР 10,2,2, (1)
С записывается в регистр 11,.2.1, С вЂ” в регистр 11.3.1 С г — в ре(1) (4) гистр 7,2.2. (o}
В шестом такте элемент С,б поступает на вход блока !.1.), на выходе которого получается частное (o) (о) {1)
С(а /С„= {:,б, на выхоДе Умножитела
8.2.1 получается произведение (0) (0) . (о)
С < /С, С 2,, а на выходе . вычитателя
{1) (о) (о)
9. 2. 1 — выражение С = С 2 — С, /
{o), (o)
/С н С,, на выходе вычитателя 9. 3. 1 (1} (о) (о) (а) (o) выРажение С >q = Г,4 — C « /C «C и
С выхода регHcTpR 1 1, 2, 1 С 24 (1) тупает на вход блока 1,1.2, на выходе которого получается частное (1) p (<} (2)
С,q (С =- С„, На выходе умножителя 8.2,2 получается произведение (1) (1 } (1}
Сг,/С, С, а на выходе вычитате(2) (1) (11 ля 9.2.2 — выражение С = С -С / (1} ()
/С 22 С qz = 1з . В конце такта част(а), (а) но е С, / С „, = С, принимается в регистр 1 0 . 2 . 1, ч а с тн о е „ С / С (1>
С,q- — в регистр 1 0 . 3 . 1, ч ас тн:о е (о) (а) (1)
С, /С н = С,4 — в регистр 15 ° I, част(а) {a) ное С 1 /С „ = С1 — в регистр !6.1, (а) jo) (о) частное С, /С „= С, — в регистр (1) (1) (2)
7.3.2, частное С 24/С = С ., — в регистр 10.2,2, частное С2)/С 2 = Сг (<} (1) (2)
И в регистр 10.3,2, С г — в регистр
11 (1) .2,1, С. — в регистр 11.3.1, ЪФ
С вЂ” в регистр 11.2.2 °
В седьмом такте на выходе вычитателя 9.2 ° 1 получается выражение (1) (n) {o) 1о) 1а)
С 2„. = С zg — С 1 /С „С 22, на выходе сумматора 9. 3. — выражение (1) (о) (о) (о) (o)
С = Гqy- С 1 /С и С 1 . С выхода регистра 11,2,1 С подается на вход (1} блока 1.1,2,,на выходе которого полу(1) (1} (2) чается частное С 2
С 1 — С z> /Czz {:,2, В конце так(а) (р) (1}
}5 та частное С,,/С„ = С,6 принимается в
Регистр 10.3,1, частное С 1-/С, . (1} (а)
С, - — в регистр 15.1, частное C q / (о} (11
/С11 = С {q — в регистр 16 ° 1, частное
{1) «) (г )
С г /C 22 = С гу — в Регистр 10. 2. 2р
«),(1) (г) частное С 24/Ñz = С 24 — в регистр (1} (1) (2} !
0.3.2, частное С ./C = C — a peгр гг 23
25 гистр 15.2. С выхода регистра 11,2.2 (21
С г принимается в регистр 4.1.3, С выхода вычитателя 9,2.1 Сгб принима(1) ется в регистр 11,2. 1, С вЂ” в Ðå(1 1" (21 гистр 11.3.1, С >q — в регистр
Ю (z) ,2.2 С, — в регистр 11.3.2.
В восьмом такте на выходе вычитателя 9.3.1 получается выражение (1) (о} (о) (а} (а)
С а= С 6 — С1 /С „С.,, на выходе
35 блока 1.1.2 — частное Сг /Сгг= Сг
{.1) (1} (2}
Ы1 на выходе вычитателя 9. 2. 2 — выраже(2) {1) (1) (1) (1)
35 = C» — С 2 /С гг С 32 на выходе вычитателя 9.3.2 — выражение (2) (1) (1), (1) (1}
40 С14 — С 4 Сzq/Czz С;2 С вьптда Ре (z } гистра 11.2.2 С 4 подается на вход блока 1,1,3, на выходе которого получается частное С) /Сэ = Сqq . Б кон(2) <г) (1 ) (o) ., {о) (1} це такта частное С 1 /C,ö,= С1 принимается в регистр 15,1, частное (o) (o) (1)
C« /C н = С1 — в регистр ) 6.!,. час-.— (1) (г) ное Сгб /С 22 = Сг — s регистр 10,2.2, (1) (1) (. P
5О частное Сг /С. Сг — в регистр
10,3,2, частное С /Г = С (1) {1} в регистр 5 ° 2, частное С 2 / С (2) (z}
= Сг — в регистр 16.2, частное C 4 / (2) (q)
/C > = С q4 — в регистр 10, 2. 3. С вы— (2) хода регистра 11.3.2 С 1 принимается в регистр 7,2.3. C выхоца вычита-(1) теля 9.3.1 С „ записывается в Ре7 !4733003 8 (3) 4, <33 74 75, 32 < 3)
"34 34
А гистр ) 1. 3. 1, С (, — в регистр
4 в per>(c p
В девятом такте на выходе вычитателя 9.2.2 получается выражение (2) (3) (<) 3 (<) (3)
C„= С вЂ” C„-/Сz, С)г, на выходе вычитателя 9.3.2 — выражение С, (г) (3) (3) (3) (4)
С,< — С г /С z С3z на выходе (г 2 (z) (3) блока 1.1,3 — частное С) /С ) / С на выходе вычитателя 9,2.3 — выраже(3) (г) (z) (г) (z) ние С,4 = С << — С 34/С 33 — С 0) (3) (z) Сг /Сгг = Сгб в регистр 10.3,2, (3) (2 (Z) частное Cz /С . = С < — в регистр (s) () (И 15,2, частное Сг /Сг = Сг4 — в ре(<) (3) (Z) гистр 16.2, частное Сг3/С = С (z) (z) в регистр 7.3.3, частное С /С (М С 31- — в регистр 10. 2. 3, частное «) (г) (3) С44/С >> = С „— в регистр !0.3.3 ° (1 ) С выхода сумматора 9. 2. 2 С зя(z) писывается в регистр 11,2.2, С,. в регистр 11.3.2, (. — в регистр -(3) 11.2.3. В десятом такте на выходе вычитателя 9.3.2 получается выражение (г) (3) (3) (i 2 (0 С, = С, - С гя /С гг С, г, на выходе блоИ 2 () (3) ка 1,! .3 — частное С 3 /С 3 С, на выходе сумматора 9.2.3. — выраже(3) (z) (z) (г) (tl ние С,q = С, — С3, /С33 С,3, на выходе сумматора 9.3 ° 3 — выражение (32 () (z) (г) (г) Cz4= Сг4 С34 /С g Сг) ° В KQHIJ0 (S) (3) такта частное С«/С = С q принимается в регистр 15.2, частное Сг /= = С вЂ” в регистр 16.2, ча(г) (2) (3)стное С /С = С вЂ” в регистр 3 (г) (г) (3) 10,2,3, частное С „/Ñ 3 = С3 — в () регистр 10.3.3. С, записывается в регистр 11.3.2, С, — в регистр (3) 11.2.3, С(3 †в регистр 11.3.3: В одиннадцатом такте на выходе вычитателя 9.2.3 получаем выражение (3) (z) () (z ) (z) С, = С, — С /С33. С1>, на выходе (И вычитателя 9.3.3 — выражение С (z) (z) (z) (z) С)р/Сэ3 С 3 . В конце такта (3) (3) (Z) частное С гя/(:iz = С принимается (г) (z) в регистр 16,2, частное с +/с44 С . — в регистр 10.3.3, С, запи(3) (3) )о "(3) « сывяется в регистр 11.2.3, С вЂ” в регистр !!.3.3. 5 В двенадцатом такте на выходе вычитателя 9.3.3 получается выражение .33) (г) „(2, () (<) Cz = С« — С4*/(,, Г г„, которое в . KoнIjp. тякTA принимяpòñÿ в регистр lI 3, . 11р; 3том вы шсление обратной матрицы зяк янч ивяе тс я . Иячиная с восьмого тяктя ня первых выходах блоков I.l.3, 1.2, 3, 1 ° 3.3 появляются эле15 менты обратно(матрицы Па выходах устройства получаются элементы обрятной матрицы по строкам, т.е. ня выходе блока 1.1.3 по25 являются элеме3г3ы третьей строки, т.е. ня выходе блока 1.2.3 — первой, ня выходе блока 1.3.3. — второй. Для общего случая !) выходов распределение строк следующее: i-я строка результата выдается с (i+1)30 ro выходя (для i = 1,...,N-I), М-я строка — с 1-го выходя. Сразу же после ввода первой строки исходной матрицы, т ° е. в данном примере с седьмого такта, можно начинять вводить следующую исходную матрицу яналогичным образом: каждая следующяя строка подается со сдвигом на один, такт. При решении системы линейных урав40 некий в качестве элементов матрицы В подаются свободные члены заданной системы уравнений. Тогда на выходе получается семейство решений этой 45 сис темы уравнений, Столбец С, Сг4 С3 является решением сис(32 (3) (3) темы при столбце свободных членов » j T Г () (3) (3) -) » Ь(, bz, Ь»Д, столбец С „С . С. )50 Решением свободных членов (bÄz Ьг ЬЗД и т.д. Ф о р м у л а и з о б р е т е н и я Устройство для операций над мат55 рицами, содержащее N(N+1)/2 операционных блоков и распределитель импульсов, выходы которого подключены к синхровходам операционных блоков, 9 1 ОО"= 10 где N — размерность матрицы, о т— (i=1,N, j l N),ïåðâûA вход i,j-го операционного блока подключен к перцельв Расширенин ФУнкциональных воз- вому выходу (i+1) (j-1)-го операционможностей за счет решения систем линейных Уравнений и обРа@ениЯ матРиц, вход операционного блока N,j подклюв него введены N (Ы-1)/2 операцион- чен к выходу (j-1)-ro элемента заных блоков и Н-1 элементов задерж- держки, (j 2,N), вход которого подки, причем первый вход 1.l-ro опера кл чен к второму выходу Я (j )) ro ционного блока подключен к i"ìó вхо- 10 операционного блока (j=g,N), второй ду устройства, (i=1,N), первые выхо- вход,j-го операционного олока подды .N-х и 1 ° 3-х операционньгх блоков клычен к второму выходу (i-l),j-г подключены к выходам устройства, операционного блока (i=2,N; j I,N) °
