Устройство для LU-разложения матриц Советский патент 1990 года по МПК G06F17/16 

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

Целью изобретения является снижение аппаратурных затрат.

На фиг.1 представлена структурная ) схема устройства для Ш-разложения матриц; на фиг0 2 - структурная схема множительно-вычитающего блока; на фиг.З - структурная схема блока синхронизации; на фиг. 4 - структурная схема одного из вариантов построения формирующего узла; на фиг. 5 - временная диаграмма работы блока синхронизации.

Устройство для LU-разложения матриц (фиг.1) содержит первьй 1,второй

2у третий 3, четвертый 4, пятый 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 регистры, седьмой 30, восьмой 31, девятый 32, десятый 33,одиннадцатый 34, двенадцатый 35,тринадцатый 36 и четырнадцатый 37 коммутаторы, блок 38 синхронизации,

Множительно-вычитающий блок, например, содержит (фиг.2) умножитель 39, входы которого являются входами первого и второго сомножителей,

сл

J

со сл

и вычитатель 40, первый вход которого соединен с выходом умножителя 39, второй вход является входом слагаемого, а выход - выходом всего множи- тельно-вычитающего блока.

Множительно-вычитающий блок имеет вход слагаемого, вход первого сомножителя и вход второго сомножителя и выполняет вычисления по формуле d а - Ъ-с, где а - число на входе слагаемого; b и с - числа на входах первого и второго сомножителей; d - число на выходе множительно-вычитаю- щего блокао

Блок 38 синхронизации, например, содержит (фиГоЗ) элемент И 41 , выход которого подключен к счетному входу трехразрядного счетчика 42 адреса, выходы которого подключены к входам регистра 43 адреса, синхровход приема информации которого объединен с первым входом элемента И 41 и является входом 44,1 блока синхронизации, |Вход установки нуля счетчика 42 объединен с вторым входом элемента И 4 и является входом 44„2 запуска блока синхронизации. Выходы регистра 43 адреса подключены к входам постоянного запоминающего устройства (ПЗУ) 45 микрокоманд. Выход элемента И 41 является первым выходом 46 блока 38 синхронизации,, Выходы 47-57 запоминающего устройства 45 микрокоманд являются соответственно с второго по двенадцатый выходами блока синхронизации.

Блок деления имеет вход делимого и вход делителя и выполняет вычисления по формуле 1 f/q, где f - число на входе делимого; q - число на входе делителя; 1 - число на выходе блока деления,

При одноканальном потоке исходных данных для формирования требуемой последовательности исходных данных и записи получаемых результатов в од ноканальную память можно использовать преобразователь последовательного потока данных в параллельный и параллельного в последовательный,, Подобный формирующий узел можно построить множеством различных способов. Формирующий узел, представленный на фиг.4, содержит шесть входных блоков 58-63 регистров, входы которых объединены и являются входом узла, а выходы подключены к входам устройства для Ш-разложения матриц. Выходы

устройства для LU-разложения соединены с входайи шести выходных блоков 64-69 регистров, выходы которых объединены и являются выходом формирующего узла.

Устройство для Ш-разложения матриц выполняет вычисление по формуле

U

И

-

а

fci

при k 4 j,

1;

ik

a(.w - k|

/a

fek

где

1a(fc jafcj

i,j k,k+l,.,.,п„

Поскольку устройство предназначено для Ш-разложения матриц размерностью 4x4, то вся обработка заключается в следующих вычислениях:

Ь

0

-41

- 1

L4i

42 Uij

U«

а- чз-l 41- U ,з „

Рассмотрим подробно работу уст- : ройства при выполнении Ш-разложения матрицы

и

11

1Ъ

ч

Условимся, что прием в регистры осуществляется задним фронтом синхроимпульса, т.е. в начале такта, и исходное состояние всех регистров - О.

В момент времени t (начало первого такта) в регистры 1-6 по сигналу, поступающему с выхода 46 блока 38 синхронизации принимаются а, ачз ai+ а21 азч соответственно;. По нулевым сигналам, поступающим с выходов 47, 48, 50 и 51 блока 38 синхронизации, коммутаторы 7-12 подключают к множительно-вычитающим блокам и блокам деления выходы входных регистров 1-6, коммутатор 37 по сигналам 10, поступающим с выходов 47 и 49 блока 38 синхронизации подключает к входам делителя блоков 17 и 18 деления выход входного регистра 1, коммутаторы 30-36 могут находиться в произвольном состоянии, так как в качестве сомножителей в любом случае будут подаваться нули0 Таким образом, в конце первого такта в момент ta по сигналам, поступающим с выходов 54-57 блока 38 синхронизации в регистры 19-24 принимаются соответственно U,, ,Un ,U

,1

1

31

30 В момент t 4 в регист

также в регистр 29 - коэффициент 13,. маются соответственно а

В момент времени t по сигналу, поступающему с выхода 46 блока 38 синхронизации, принимаются также а

г

на., в регистры 1 и 6 соответствен41

которые через коммутаторы 7-Ю подаются на входы слагаемого блоков 13-16. Выход регистра 22 (II1Ч) через коммутаторы 30 и 33 подключается к входам первого сомножителя блоков 13 и 16, выход регистра 21 (U,5) через коммутаторы 31 и 32 подключается к входам первого сомножителя блоно, по нулевым сигналам5 поступающим с выходов 47 и 48 блока 38 синхронизации, коммутаторы 7 и 12 подключают к входам блоков 13 и 18 выходы реги- 4Q ков 14 и 15, выход регистра 23 (llf) стров 1 и 6, по сигналам 01, посту- по единичному сигналу через коммута- пающим с выходов 52 и 53 блока 38 тор 34 подается на вход второго сомзации, принимаются в регистры 19 к 24 соответственно.

В момент времени t. , в начале третьего такта, в регистры 2-4 при

нимаются соответственно а а

10

33 а32

41 и по нулевому сигналу коммутаторы 8-10 подают их на входы блоков 14-16 соответственно. Коммутатор 31 по нулевому сигналу подает на вход первого сомножителя блока 14 U.3, т.е. содержимое регистра 21,коммутаторы 32 и 33 подают на входы первого сомножителя блоков 15 и 16 U ,2,

15 т.е. содержимое регистра 20, выход регистра 23 (l-j, ) по нулевому сигналу коммутатор 35 подключает к входу второго сомножителя блока 14,выход регистра 29 (1Э1) по единичному сиг20 налу коммутатор 36 соединяет с входом второго сомножителя блока 15, с выхода регистра 24 141 подается на вход второго сомножителя блока 16,

К концу третьего такта на выходе

25 блока 14 получают , на выходе блоков 15 и 16 - числители соответственно 1 ъг и 147, которые в момент t+ принимаются соответственно в регистры 20, 27 и 28.

30 В момент t 4 в регистры 1-4 принимаются соответственно а

14

133

4з

441

35

которые через коммутаторы 7-Ю подаются на входы слагаемого блоков 13-16. Выход регистра 22 (II1Ч) через коммутаторы 30 и 33 подключается к входам первого сомножителя блоков 13 и 16, выход регистра 21 (U,5) через коммутаторы 31 и 32 подключается к входам первого сомножителя бло4Q ков 14 и 15, выход регистра 23 (llf) по единичному сигналу через коммута- тор 34 подается на вход второго сом

Устройство для LU-разложения матриц относится к области вычислительной техники и может быть использовано при построении специализированных устройств, предназначенных для матричных вычислений. Цель изобретения - снижение аппаратурных затрат. Цель достигается новой организацией связей между элементами устройства. Особенностью работы устройства является распараллеливание процесса вычислений в сочетании с высоким коэффициентом использования элементов устройства. Размерность разлагаемых матриц 4^.4. 5 ил.

синхронизации, коммутатор 30 подключает к входу первого сомножителя блока 13 выход регистра 20, т0е. U По единичному сигналу, поступающему с выхода 51 блока 38 синхронизации, коммутатор 34 подает на вход второго сомножителя блока 13 1ц, т„е. выход регистра 23. По сигналам. 10, поступающим с выходов 47 и 49 блока 38 синхронизации, коммутатор 37 соединяет с входом делителя блока 18 выход, регистра 19, т.е. и.ц „ Таким образом, к концу второго такта на выходе блока 13 появляется Uj,, , а на выходе блока 18 - 1 41,которые в момент t3 по сигналу.поступающему с выхода 55 блока 38 синхрони-

ножителя блока 13, выход регистра 29 (131 ) по единичному сигналу через

коммутатор 35 подключается к входу второго сомножителя блока 14, с выхода регистра 24 141 подается на вход второго сомножителя блока 15 по нулевому сигналу через коммутатор 36, на

вход блока 16 - непосредственно. Выход регистра 27 (числитель 1зг) по единичному сигналу через коммутатор 11 подключается к входу делимого блока 17, выход регистра 28 (числитель

41

12 - к входу делимого блока 18,выход регистра 19 (U) по нулевым сигналам через коммутатор 37 - к входам делителя блоков 17 и 18.

Таким образом, к концу четвертого такта на выходах блоков 13-18 получают соответственно Ц

24

первую

разность II , первую рая ность числителя 1 , первую разность 144 э 14, . В момент времени t. U24,, 14г принимаются в регистры 19, 23 и 24 соответственно, а первые разности U33 числителя 143 и U 44 - в регистры 26-28 соответственно.

В начале пятого такта (tj) в ре- гиЈтр I принимается аэ«. и через ком- му|гатор 7 подается на вход слагаемого блока 130 Коммутаторы 8-10 подключают выходы регистров 26-28 к вхрдам слагаемого блоков 14-16 соответственно. Выход регистра 22 (и 14) чеЬез коммутатор 30 по сигналам 10 подключается к входу первого сомно- жифеля блока 13, выход регистра 20 (Ш ) через коммутаторы 31 и 32 - к входам первого сомножителя блоков 14 и 15, выход регистра 19 (U44) через коммутатор 33 - к входу первого сомножителя блока 16, С выхода регистра 29 через коммутатор 34 131 подается на вход второго сомножителя блока I3s с выхода регистра 23 черет коммутатор 35 1зг подается на вход второго сомножителя блока 14, с выхода регистра 24 142 подается на вход второго сомножителя блока 15 через коммутатор 36, а на вход второго сомножителя блока 16 - непосредственно,

К концу пятого такта на выходах блоков 13-16 получают соответственно первую разность UJ4, U33, числитель 1.3, вторую разность U44 „ В момент времени 11 первая разность U3l ,чис- литель 143 и вторая разность 11 принимаются в регистры 25, 27 и 28,U33 принимается в регистр 20.

В шестом такте коммутатор 7 подключает выход регистра 25 (первая разность U34) к входу слагаемого блока 13. С выхода регистра 19 через коммутатор 30 U14 подается на вход первого сомножителя блока 13, с выхода регистра 20 через коммутатор 37 по сигналам 01 U33 подается на вход делителя блока 18, с выхода регистра 23 15г через коммутатор 34 подается на вход второго сомножителя блока 13, с выхода регистра 27 черйз коммутатор 12 по сигналам 01 числитель 143 подается на вход делимого блока 18,

К концу шестого такта на выходах блоков 13 и 18 получают коэффициенты

U

4

14J соответственно, которые

в момент времени t принимаются в регистры 19 и 24 соответственно,

В седьмом такте коммутатор 10 подает на вход слагаемого блока 16 вторую разность U44 с выхода регистра 28, с выхода регистра 19 Пзч подается на вход первого сомножителя блока 16 через коммутатор 33, с выхода регистра 24 на вход второго сомножителя блока 16 подается 1

43

К концу

седьмого такта на выходе блока 16 получают U44, которое в момент времени tg принимается в регистр 22,

На этом разложение исходной матрицы А на коэффициенты L и TJ заканчивается. В момент времени t в регистры 1-6 принимаются исходные данные новой матрицы. Далее работа устройства аналогична описанной.

Блок 38 синхронизации работает следующим образом Синхроимпульсы от внешнего устройства через вход 44.1 поступают на синхровход приема информации регистра 43 адреса и на первый вход элемента И 41, на второй вход которого через вход 44,2 подается сигнал запуска. При единичном -значении сигнала запуска снимается сигнал установки в ноль счетчика 42 и синхроимпульсы начинают поступать на счетный вход счетчика 42 адреса.Выходы счетчика 42 адреса подаются на входы регистра 43 адреса, выходы которого поключены к адресным входам ПЗУ 45 микрокоманд,/ Емкость ПЗУ 45 микрокоманд - восемь девятиразрядных слов Количество микрокоманд равно количеству тактов работы, количество разрядов микрокоманды равно количеству различных управляющих сигналов, требуемых для элементов устройства .

Формирующий узел (фиг,4) работает следующим образом,Элементы исходной матрицы принимаются в соответствующие входные блоки регистров, т.е. в регистры 58.1-58,4 принимаются элементы a11s а га, а14 , а31 , в регистры 59,1-59„3 - элементы а 11Э a2J, азэ, в регистры 60,1-60.3 - а1Ъ,яьг, а4Э , в регистры 61 ,1-61 .3 - а 14, а42 и а44 в регистр 62 - аг(, в регистры 63о 1-63.2 - а зг и а 41. Элементы преобразованной матрицы Ш принимаются в выходные блоки регистров следующим образом: в регистры 64.1-64.4 элементы U(f , U22 , U14, tJj4 , в регистры 65о 1-65.3 - элементы U1Z ,П2Д, Uj3 5 в регистр 66 - U 13 в регистры 67,1 и 67.2 - U n и U44 , в регистры

1 и 68.2 - 1, 1-69.4 - 1.

.г, и Ij4, в регистры

-51 41 42 4э« Вьща- ча элементов преобразованной матрицы из устройства может быть организована в любой требуемой последовательности. Управление формирующим узлом осуществляет внешнее устройство управления, которое может быть, например, микропрограммным.

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

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

15

20

25

30

35

40

45

50

55

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

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

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

J

S6mSI

Фиг. 5