Устройство для lu-разложения матриц

 

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

СОЮЗ СООЕТСНИХ

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

РЕСПУБЛИК

А1

„.SU„„154 7 (5! )5 0 06 F 15/347

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

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

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

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

ПРИ ГКНТ СССР

1 (21 ) 4447049/24-24 (22) 23.06.88 (46) 07,03.90, Бюл. N - 9 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) 10.С.Каневский, С,Э.Котов, М,К.Клименко и Л,М.Логинова (53) 681.325 (088 ° 8) (56) Авторское свидетельство СССР

У 1401778, кл. G 06 F 15/347, 1986.

Kai Hvang and Jen — Hend Cheng.

Partitioned Algorithms and VLSI

Structures for Large - Scale matrix

computations, — Proceedings of the

5-th Symposium on Computer Arithmetic) 1981.

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных устройств, предназначенных для решения систем линейных уравнений, Целью изобретения является снижение аппаратурных затрат, На фиг.l представлена структурная 1 схема устройства для LU-разложения матриц; на фиг. 2 — структурная схема множительно-вычитающего блока; на фиг.3 — структурная схема блока синхронизации; на фиг, 4 — структурная схема одного из вариантов построения формирующего узла; на фиг, 5 — временная диаграмма работы блока синхронизации.

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

2 (54) УСТРОЙСТВО ДЛЯ LU-РАЗЛОЖЕНИЯ

МАТРИЦ (57) Устройство для LU-разложения матриц относится к области вычислительной техники и может быть использовано при построении специализированных устройств, предназначенных для матричных вычислений, Цель изобретения — снижение аппаратурных затрат, Цель достигается новой организацией связей между элементами устройства, Особенностью работы устройства является распараллеливание .процесса вычислений в сочетании с высоким коэффициентом использования элементов устройства. Размерность раэлагаемых матриц 4х4. 5 ил, 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, входы которого являются входами первого и второго сомножителей, 1548795 и вычитатель 40, первый вход которого соединен с выходом умножителя 39, второй вход является входом слагаемого, а выход — выходом всего множительно-вычитающего блока, 5

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

d. = а — Ь с, где а — число на входе слагаемого; b и с — чистка на входах первого и второго сомножителей; d - число на выходе множительно-вычитающего блока. 15

Блок 38 синхрониз ации, нап риме р, содержит (фиг,3) эл емент И 41, выход которого подключен к счетному входу трехразрядного счетчика 42 адреса, выходы которого подключены к входам регистра 43 адреса, синхровход приема информации которого объединен с первым входом элемента И 41 и является вхоцом 44,1 блока синхронизации, Вход установки нуля счетчика 42 объединен с вторым входом элемента

И 41 и является входом 44.2 запуска блока синхронизации. Выходы регистра 43 адреса подключены к входам постоянного запоминающего устройства (ПЗУ) 45 микрокоманд, Выход элемента

И 41 является первым выходом 46 блока 38 синхронизации, Выходы 47-57 за поминающего устройства 45 микрокоманд являются соответственно с второго по двенадцатый выходами блока синхронизации.

Блок деления имеет вход делимого и вход делителя и выполняет вычисления по формуле 1 = f/q где f — чис9 40 ло на входе делимого; q — число на входе делителя; 1 — число на выходе блока деления, При одноканальном пот ок е исходных данных для формирования требуемой последовательности исходных данных и записи получаемых результатов в одноканальную память можно использовать преобразователь последовательного потока данных в параллельный

50 и параллельного в последовательный.

Подобный формирующий узел можно построить множеством различных способов °

Формирующий узел, представленный на фиг.4, содержит шесгь входных блоков

58-63 регистров, входы которых объе55 динены и являются входом узла, а выходы подключены к входам устройства для LU-разложения матриц, Выходы (И 1Ц

11« = а;«/& ««9 где (Ь11 а..

iJ (iJ а.. =

iJ

k=1

< «! (И («1 («1 а,. — (а, «/а,„) а

B; ° °

ij ,2,...9n-1;

i 3 k9,k+1, Поскольку устройство предназначено для LU-разложения матриц размерностью 4х4, то вся обработка заключается в следующих вычислениях:

19 1 9 12 12 9 Ъ 13 (114 = а14 9 а ° 1

111- аг1/а„,, 131- а31/а „9 41= 4, /а,„;

22 z z j- 11 9(112 9

25 23 г1 139

U24 ай4 29 U94 9 (19з = аЗз — 19 U., — l3Z U23

U34 а34 „U 4 132 Uz4

U44 = а»4 — -41 (1 14 — -», 11 д Uzq—

4b 34 9 а за - 3-3 (119., 32 а44. — l49. U1z

149.

zz

S а,4з-з- «U,9 — 14z Uzs -4З (133

Рассмотрим подробно работу устройства при выполнении. LU-разложения матрицы а/1 а fz а13 а14 а г3 а24 а31 а«a„> а44 и получении матрицы 12 (13 21 Uzz U2.3 -31 l3t (1 ээ -41 . 41 - 43

U14

Ut4

U34

U«. устройства для Ю-разложения соединены с входами шести выходных блоков

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

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

= а,. при k4)

«j «) !

15

5 154 условимся, что прием в регистры осуществляется эадним фронтом синхроимпульса, т,е, в начале такта, и исходное состояние всех регистров

"0"

В момент времени t (начало пер1 вого такта) в регистры 1-6 по сигналу, поступающему с выхода 46 блока

38 синхронизации принимаются а „„,а, а,з "+ a> ° аз соответст"енИ

По нулевым сигналам, поступающим с выходов 47, 48, 50 и 51 блока 38 синхронизации, коммутаторы 7-12 подключают к множительно-вычитающим блокам и блокам деления выходы входных регистров 1-6, коммутатор 37 по сигналам 10, поступающим с выходов

47 и 49 блока 38 синхронизации подключает к входам делителя блоков 17 и 18 деления выход входного регистра

1, коммутаторы 30-36 могут находиться в произвольном состоянии, так как в качестве сомножителей в любом случае будут подаваться нули. Таким образом, в конце первого такта в момент t< по сигналам, поступающим с выходов 54-57 блока 38 синхронизации, в регистры 19-24 принж.аются соответственно IJ,,П,,1З,»IJ«,1,„, l „, а также в регистр 29 — коэффициент 1,.

8795 6 эации, принимаются в регистры 19 и

24 соответственно.

В момент времени t в начале третьего такта, в регистры 2-4 при5 нимаются соответственно а, а, а и по нулевому сигналу коммута47, торы 8-10 подают их на входы блоков

14-16 соответственно, Коммутатор 31 по нулевому сигналу подает на вход первого сомножителя блока 14 U т. е, содержимое регистра 21,коммутаторы 32 и 33 подают на входы первого сомножителя блоков 15 и 16 И т. е, содержимое регистра 20, выход регистра 23 (1, ) по нулевому сигналу коммутатор 35 подключает к входу второго сомножителя блока 14,выход регистра 29 (1 >,) по единичному сигналу коммутатор 36 соединяет с входом второго сомножителя блока 15, с выхода регистра 24 14,подается на вход второго сомножителя блока 16, К концу третьего такта на выходе блока 1 4 получают U, на выходе блоков 15 и 1 6 — числители соответственно 1 и 1, которые в момент t принимаются соответственно в регистры

20, 27 и 28.

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

В момент времени t < по сигналу, поступающему с выхода 46 блока 38 синхронизации, принимаются также а и а „в регистры 1 и 6 соответственно, по нулевым сигналам, поступающим с выходов 47 и 48 блока 38 синхронизации, коммутаторы 7 и 12 подключают к входам блоков 13 и 18 выходы регистров 1 и 6, по сигналам "01" ° поступающим с выходов 52 и 53 блока 38 синхронизации, коммутатор 30 подключает к входу первого сомножителя блока 13 выход регистра 20, т.е, JJ, По единичному сигналу, поступающему с выхода 51 блока 38 синхронизации, коммутатор 34 подает на вход второго сомножителя блока 13 1,, т.е. выход регистра 23. По сигналам .

"10", поступающим с выходов 47 и 49 блока 38 синхронизации, коммутатор

37 соединяет с входом делителя блока 18 выход регистра 19, т.е, Таким образом, к концу второго такта на выходе блока 13 появляется а на выходе блока 18 — 1 „кото1 1 рые в момент tz по сигналу, поступающему с выхода 55 блока 38 синхрониа, которые через коммутаторы 7-10 подаются на входы слагаемого блоков

13-16. Выход регистра 22 (И „,, ) через

35 коммутаторы 30 и 33 подключается к входам первого сомножителя блоков

13 и 16,,выход регистра 21 (U, ) через коммутаторы 31 и 32 подключается к входам первого сомножителя бло40 ков 14 и 15, выход регистра 23 (1+ ) по единичному сигналу через коммутатор 34 подается на вход второго сомножителя блока 13, выход регистра

29 (lз, ) по единичному сигналу через

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

50 вход блока 16 — непосредственно. Выход регистра 27 (числитель 1 ) по единичному сигналу через коммутатор

11 подключается к входу делимого блока 17, выход регистра 28 (числитель

1

12 — к входу делимого блока 18,выход регистра 19 (U ) по нулевым сигналам

1т через коммутатор 37 — к входам делителя блоков 17 и 18.

1548795

Таким образом, к концу четвертого такта на выходах блоков 13-18 получают соответственно П первую та разность !, первую разность числителя l пе;живую разность 1 1 аз 44 32>

1а . Б момент времени СХ 024

-зс

1 принимаются в регистры 19, 23 и

24 соответственно, а первые разности

per H43 44 f0 стры 26-28 соответственно.

В начале пятого такта (t ) в ре5 ги!" тр 1 принимается à за и через комму!гатор 7 подается на вход слагаемоrо блока 13, Коммутаторы 8 — 10 под15 качают выходы регистров 26-28 к входам слагаемого блоков 4-16 соответственно, Выход регистра 22 (!! а) через коммутатор 30 по сигналам "10" подключается к входу первого сомно20 жиТеля блока 13, выход регистра 20 (TJ ) через коммутаторы 31 и 32 — к вхОдам первого сомножителя блоков

14.и 15, выход регистра 19 (U« ) через коммутатор 33 — к входу первого 25 соМножителя блока 16, С выхода регистра 29 через коммутатор 34 1 „ подается на вход второго сомножителя блока 13, с выхода регистра 23 через коь мутатор 35 1>z подается на вход второго сомножителя блока 14, с выхода регистра 24 1 4 подается на вход второго сомножителя блока !5 через ком!мутатор 36, а на вход второго сомносителя блока 16 — непосредственно, К концу пятого такта на выходах

35 блохов 13-16 получают ьответственно о первую разность TJ, TJ> числитель

34 33

1 аз, BToP ) Раз но ст ь U4 . l3 MQMeHT

4а времени С первая разность П чис51 40 литель 143 и вторая разность П при44 нимаются в регистры 25, 27 и 28 Л принимается в регистр 20.

В шестом такте коммутатор 7 подключает выход регистра 25 (первая разность JJÄ ) к входу слагаемого блока 13. С выхода регистра 19 через коммутатор 30 Uz„ïîäàåòñÿ на вход первого сомножителя блока 13, с выхода;регистра 20 через коммутатор 37

50 по i игналам "01" П . подается на вход делителя блока 18, с выхода регистра 23 1 через коммутатор 34 подается на вход второго сомножителя блока 13, с выхода регистра 27 через коммутатор 2 по сигналам "01" чисЛитель 14 подается на вход делимого блока 8, К концу шестого такта на выходах блоков 3 и 18 получают коэффициенты !! и 1 соответственно, которые в момент времени t принимаются в 7 регистры 19 и 24 соответственно, В седьмом такте коммутатор 10 подает на вход слагаемого блока 16 вторую разность П44 с выхода регистра 28, с выхода регистра 19 lJ подаза ется на вход первого сомножителя блока 6 через коммутатор 33, с выхода регистра 24 на вход второго сомножителя блока 16 подается 1 К концу а ° седьмого такта на выходе блока 16 получают JJ«, которое в момент времени

t3 принимается в регистр 22.

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

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

ПЗУ 45 микрокоманд„, Емкость ПЗУ

45 микрокоманд — восемь девятиразрядных слов, Количество микрокоманд равно количеству тактов работы,, количество разрядов микрокоманды равно количеству различных управляющих сигналов, требуемых для элементов устройства, Формирующий узел (фиг,4) работает следующим образом, Элементы исходной матрицы принимаются в соответствующие входные блоки регистров, т,е ° в регистры 58.1-58.4 принимаются элементы а „„„ а, а а, аза, в Регистры 59.1 -59.3 — элементы а а

11> Z5 а, в регистры 60.1-60.3 — а а аь э э а, в регистры 61,1-6 1.3 — а а

14 42 и а«, в регистр 62 — а,, в регистры 63.1-63.2 — а з и а 4,, Элементы преобразованной матрицы LU принимаются в выходные блоки регистров следую1548795

J0 щим образом: в регистры 64, 1-64, 4

Ц,, 7д, tJ z, JJ><, стры 65.1-65.3 — элементы U,11, в регистр 66 — tf q, в регистры

67.1 и 67.2 — И 4 и 044 в регистры

68.1 и 68.2 — 1, и 3 „, в регистры ча элементов преобразованной матрицы из устройства может быть органиt0 эована в любой требуемой последовательности. Управление формирующим узлом осуществляет внешнее устройство управления, которое может быть, например, микропрограммным, 15

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

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

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

1548795

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

1548795

1 548795 1 4 tç t4

5! г

5Е

П Г 1. и

55 /

Я

Составитель К, Кухаренко

Редактор В,Петраш Техред А. Кравчук

КоРРектоР H.Муска

Заказ 142 Тираж 565 Подписное

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

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

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