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

 

Изобретение относится к вычислительной технике и может быть использовано при построении специализированных устройств, предназначенных для решения системы линейных уравнений . Целью настоящего изобретения является упрощение. Поставленная цель достигается тем, что благодаря изменению организации вычислений и числа межпроцессорных связей устройство содержит 1/2N(N+1) операционных блоков, N входов и N выходов . 2 з.п. ф-лы, 4 ил.

СОКИ СОВЕТСНИХ

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

РЕСГ1УЬЛИН (511 4 С 06 F 15/347

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

Н ASTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАЮ ИЗОБРЕТЕНИЙ И OTHPblTWI (21) 4159878/24-24 (22) 10. 12. 86 (46) 07.06.88. Бюл. 1Ф 21 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) Ю.С.Каневский, С.Э.Котов и Ф.В.Самофалова (53) 681.32(088.8) (56) Европейский патент У 0144123, кл. G 06 F 15/347, опублик. 12.06.85.

Кинд Н.Т„ и др. Systolic arrays

for VLSI. Sparse Matrix Proceedings.

1978, р. 256-282.

„.SU„„1401478 A1 (54) УСТРОЙСТВО ДЛЯ LU-РАЗЛОЖЕНИЯ

МАТРИЦ (57) Изобретение относится к вычислительной технике и может быть использовано при построении специализированных устройств, предназначенных для решения системы линейных урав-. нений. Целью настоящего изобретения является упрощение. Поставленная цель достигается тем, что благодаря изменению организации вычислений и числа межпроцессорных связей устройство содержит 1/2N(N+1) операционных блоков, N входов и N выходов. 2 з.п. ф-лы, 4 ил.

1401478

:ным правилам. Ф

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

Устройство для LU-разложения матриц предназначено для разложения данной квадратной матрицы А размер- 40 ности N на две треугольные: нижнюю левую Ь и верхнюю правую U,òàêèå,êàê

LU А, причем на главной диагонали одной из треугольных матриц соят единицы. Преобразование матрицы А = (a; (45 выполняется по алгоритму исключения

Гаусса, в процессе которого получаются элементы 1; и (); (к) (к-<) (к-<)/ (k-<) (к-<)

1) <) к) кк <к а,. =а)1 k=1,2,...,N, ij (о)

) ю

1 +1 э ° ° ° < )» (к-<) i (к-<) (к-<)

U«j аК a I

1(1у2у ° ° 4у)))1<) — 1 < ° ° ° ф)) °

Устройство работает следующим образом.

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

Целью изобретения является упрощение устройства.

На фиг. 1 представлена функцио- 10 нальная схема устройства; на фиг.2 функциональная схема (k,k)-го операционного блока (k = 1,N), на фиг. 3 — функциональная схема (k,p)— го операционного блока (P = 1,2..., 15

k-1); на фиг. 4 — блок-схема алгоритма работы устройства.

Устройство содержит 0 5N (N+1) операционных блоков 1 (ОБ) и распределитель 2 импульсов, (k,k)-й ОБ со- 2() держит входной регистр 3, блок 4 деления и вход 5 синхронизации, (Е,Р)-й

ОБ содержит регистр 6 первого сомно-. жителя, умножитель 7, вычитатель 8, выходной регистр 9, регистр 10 вто- 25 рого сомножителя, первый 11, второй

12 и третий 13 входы синхронизации.

Распределитель 2 импульсов реализован на базе ПЗУ согласно известДля краткости описания без потери общности положим )) = 3. Условимся, что прием информации во все регистры осуществляется по заднему фронту синхроимпульса, т.е. в конце такта.

Исходные данные поступают на входы устройства для LU-разложения матриц построчно со сдвигом на один такт, т.е. первая строка исходной матрицы А, а,; подается на вход операционного блока 1.1.1, вторая строка, а;) — с задержкой на такт на вход ПЭ 1,2,1, третья строка, а на вход ОБ 1.3.1 и т.д.

В первом такте элемент а о пода11 ется на вход ПЭ 1.1.1 и в конце такта принимается в регистр 3.1,1, приЧЕМ а(01 = 1.<

1< (о)

Во втором такте элемент а пос12 тупает на вход ПЭ 1.1.1, на выходе которого получаем частное а(, )/а о, = U<г . Это частное в конце такта принимается в регистр 10.2.1 ПЭ 1.2.1 а элемент а г< = 1г< принимается регистр 6.2.1. (о)

В третьем такте элемент a » подается на вход ОБ 1.1. 1, на выходе которого получим частное а )а « (01 I (0)

= U<> . Элемент а подается на первый вход ОБ 1.2.1, на выходе умножителя 7.2.1 получаем произведение а(,,1/a ("1 а(1 которое поступает на вход вычитателя 8.2.1 и на его выходе получаем выражение а ) = а г — !

- а „,/а „„.a „= 1гг. В конце такта (о) (o) (о) частное a"< /а „ 1 принимается в рео1 гистр 10.2.1, частное а )г/а „ — в ре(о) (o) гистр 10,3.1, а 1 — в регистр 9.2.1, элемент а() = 1 „ — в регистр 6.3,1.

3< (o)

В четвертом такте элемент а подается на первый вход ПЭ 1.2.1.

На выходе умножителя 7.2.1 получаем произведение а(, 1/а(„1 а " „ которое поступает на вход вычитателя 8.2.1, и на его выходе получаем выражение агг = а гь а <з/а „,. а, . Элемент (<) (01 (o) (о) (o) а() поступает на первый вход ПЭ 3.

1.3.1. На выходе умножителя 7.3.1 появляется произведение а <г /а «) а 3< которое подается на вход вычитателя

8.3.1 и на его выходе получаем вь(<) (ю) (о) i (о) (о) ражение а = а, — а,q/à „ а,. В конце такта частное а ("/а о) принимается в регистр 10.3,1, а Д вЂ” из регистра 9.2.1 принимается в регистр

3.2.2, а г принимается в регистр (<)

9.2.-1, а,<г — в регистр 9.3.1.

1401» 78

В пятом такте отсчет z(o) подается

33 на первый вход ПЭ 1.3.1, на гыходе умножителя 7.3.1 получается произведение а,)/а(„, à (o) которое подается (о) на вход вычитателя 8.3.1 и на его выходе получаем выражение а = а

33 33

- аф /а(,", à(o . На первый вход ОБ

1,2.2 поступает а(из регистра

9.2.1, и на выходе ОБ 1.2.2 получаем частное а 3/а = () з . В конце так(1) (») та а = 1з записывается из регист(1) ра 9.3.1 в регистр 6.3.2, а() запи98 сывается в регистр 9.3.1, частное а(.)/а — в регистр 10,3.2 °

В шестом такте а поступает на (») первый вход ОБ 1.3.2, на выходе умножителя 7.3.2 получаем произведение а ) 3/а 22 ° а») KQTopoe подается на (») I (») (») вход вычитателя 8,3.2 и на его выходе получаем выражение а(= а() це такта записывается в регистр

9.3.2. (ю

В седьмом такте а = 1 прини- 25 мается в регистр 3.3.3.

На этом процесс LU-разложения мат.— рицы А завершается. Элементы верхней треугольной матрицы П : Uyg, (),3, (),3 выдаются с выходов ПЭ 1 ° 1.1 и 1,2.2.

Элементы нижней треугольной матриць»

L к концу вычислений находятся в регистрах процессорных элементов:

1», 1, 1зз — в регистрах 3,1.1, 3.2.2, 3.3.3 соответственно, 1 », 13,, 13 — в регистрах 6.2.1,6.3.1, 35

6.3.2 соответственно.

Поскольку каждый элемент исходной матрицы А используется в каждом данном процессорном элементе только один раз, можно выполнять LU-разложение потока матриц. Каждую следующую матрицу можно начинать подавать с N+1 такта после начала подачи предыдущей матрицы.

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

1. Устройство для LU-ðàçëoæåíèÿ матриц, содержащее 0,5N (N+1) операционных блоков и распределитель импульсов, где N — размерность матрицы, выходы которого подключены к синхровходам операционных блоков, о т л и ч а ю щ е е с я тем, что, с целью упрощения, первь»Й вход (К, 1) -го операционного блока подключен к К-му информационному входу устройства, где К = 1,N, первый выход (К,k)-го операционного блока подключен к К-му выходу устройства, второй выход mp-го операционного блока подключен к второму входу (m+1 q)-го операционного блока (m = 1,N-1, — 1,m) (первый выход ij-го операционного блока подключен к первому входу (i,j+1)-го операционного блока (i = 2,N, j = i,i-1).

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

3. Устройство по п. о т л и ч а ю щ е е с я тем, что (К,P)-й (P = 1, К-1) операционньп блок содержит регистры первого и второго сомножителя, выходной регистр, умножитель и вычитатель, причем первьп вход операционного блока подключен к информационному входу регистра первого сомножителя и выходу уменьшаемого вычитателя, выход которого подключен к информационному входу выходного регистра, выход которого подключен к первому выходу операционного блока, второй вход операционного блока подключен к информационному. входу регистра второго сомножителя, выходы регистров первого и второго сомножителей подключены соответственно к первому и второму входам умножителя, выход которого подключен к входу вычитаемого вычитателя, выход регистра второго сомножителя подключен к выходу операционного блока, первый, третий и второй входы синхронизации операционного блока подключены соответственно к синхровходам регистров первого и второго сомножителей и выходного регистра.

140! 478

Фиг.2

1401478

Составитель М.Силин

Техред М.Ходанич Корректор М.лароши

Редактор Н.Лазаренко

Тираж 704

Заказ 2786/48

Подписное

BHHHIIH Государственного комитета СССР по делам изобретений и открытий

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4i