Устройство для разбиения матриц
Изобретение относится к вычислительной технике, и может быть использовано при построении специализированных устройств, предназначенных для решения систем линейных уравнений . Целью изобретения является сокращение аппаратурных затрат. Устройство содержит вычислительный блок 1 и блок 2 синхронизации и позволяет разбить квадратную матрицу А на две треугольные: нижнюю левую L и верхнюю правую и, такие, что L U А, причем на главной диагонали матрицы и стоят единицы. Преобразование осуществляется по алгоритму исключения Гаусса. Устройство может быть использовано и для разложения потока матриц . 2 з.п. ф-лы, 5 ил. (Л 00 сд 4 ю о а:
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (51) 4 G 06 Р 15/347
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
Н А BTOPCH0MV СВИДЕТЕЛЬСТВУ
ГОСУДАРСТ8ЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTHA (21) 4088796/24-24 (22) 10.07.86 (46) 23.11.87. Бюл. Ф 43 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) P. Выжиковски (Р?.), Ю.С. Каневский и С.Э, Котов (SU) (53) 681.333(088.8) (56) Games Tawcelt, Partitioning апй
tearing applied to cellular array
processing. The 5th Symposium on Real
Time Signal Prgcessing. 1982.
Kung Н.Т. and Leiserson С.E. Systolic arrays for VLSI Sparse Matrix
Proceedings, 1978, рр. 256-282, Society for Industrial and Applied
Mathematics, 1979.
„„SU„„1354206 А1 (54) УСТРОЙСТВО ДЛЯ РАЗБИЕНИЯ МАТРИЦ (57) Изобретение относится к вычислительной технике, и может быть использовано при построении специализированных устройств, предназначенных для решения систем линейных уравнений. Целью изобретения является сок- ращение аппаратурных затрат. Устройство содержит вычислительный блок 1 и блок 2 синхронизации и позволяет разбить квадратную матрицу А на две треугольные: нижнюю левую Ь и верхнюю правую U такие, что L U = А, причем на главной диагонали матрицы
U стоят единицы. Преобразование осуществляется по алгоритму исключения
Гаусса. Устройство может быть исполь-. зовано и для разложения потока матриц. 2 з.п. ф-лы, 5 ил.
С:
1354206
Изобретение относится к вычислительной технике и может быть использовано при построении специализированных устройств, предназначенных для решения систем линейных уравнений.
Цель изобретения — сокращение аппаратурных затрат.
На фиг. 1 представлена функциональная схема устройства; на фиг. 2 и 3 примеры функциональных схем вычислительных блоков; на фиг. 4 функциональная схема блока управле- ния; на фиг, 5 — блок-схема алгоритма функционирования устройства.
Устройство содержит вычислительный блок 1 и блок 2 синхронизации.
Вычислительный блок 1, представленный на фиг. 2, содержит первый 3 и второй 4 регистры, арифметическое устройство 5, коммутатор 6, сумматор
7, третий регистр 8 и группу с первого по четвертый входов 9-12 синхронизации. Вычислительный блок 1, представленный на фиг. 3, содержит регистр 13 и вход 1.4 синхронизации.
Блок 2 синхронизации, представленный на фиг, 4, содержит генератор
15 импульсов, элемент И 16, счетчик
17, блок 18 постоянной памяти и входы 19-23 синхронизации.
Устройство работает следующим образом.
Устройство предназначено для разбиения квадратной матрицы А размерности P на две треугольные: нижнюю левую L и верхнюю правую U такие, что LU = а, причем на главной диагонали матрицы U стоят единицы. Преобразование матрицы А = Га 1 выполняето <).( ся по алгоритму исключения Гаусса, в процессе которого получаются элементы 1; и П;
<) а - < к () к« i, j =К+1, К+ 2,..., Р; где К=1,2,...,P, (к-<) а к) а(к-о кк 1 =а. <к <к Для простоты описания работы без потери общности положим P = 4. Условимся, что прием информации во все регистры осуществляется по заднему фронту синхроимпульса, т.е. в конце такта. Поступление исходных данных организовано следующим образом. На первый вход M-ro вычислительного блока 1 первой строки поступает M-й столбец разбиваемой матрицы А. Столбцы подаются со сдвигом на один такт, т.е. элементы второго столбца подаются, начиная с второго такта, третьего столбца, начиная с третьего такта, и т.д. В первом такте элемент а« прини- (о) 10 мается в регистр 13. 1. 1, причем а = 1 а„—,<. (о) Во втором такте элемент а прини(о) мается в регистр 4.1.2, элемент а< в регистр 3.1.2, элемент а, = 1,— 15 в регистр 13.1.1. (а) В третьем такте элемент ап прини(о) мается в регистр 4.1.3, элемент а, в регистр 3.1.3 ° Арифметическое устройство 5.1.2 выполняет деление и на (о) (о) 20 е го выходе получают частное а < / а <, <г = U<, которое в конце такта записывается в регистр 8. 1.2, В конце такта в регистр 4.1.2 принимается элемент а, в регистр 3. 1.2 — элемент а (о) (о) z< (о) а в регистр 13.1.1 — элемент а„= 1,. В четвертом такте на выходе сумматора 7.1.2 получают величину а а — а<г /а„а, =,, котоРаЯ в (о) (о) I (о) (о) гг конце такта будет принята в регистр ЗО 13.2.2. Элемент а „ будет записан в (>) (о) регистр 4.1.4, элемент а,4 — в ре(о) гистр 3.1,4, элемент а, в регистр 4.1.3, элемент а, — в регистр 3 ° 1.3. (о) Арифметическое устройство 5.1.3 выполняет деление и с его выхода частное а<) /a« = U<> принимается в ре(о) о ги с тр 8 . 1 . 3 . В регистры 4 . 1 . 2 и и 3 . 1 . 2 будут приняты элементь) а„ о и а, соответственно, а в регистр 40 13.1.1 — элемент а, = 1„. В пятом такте элемент а прини< zz мается в регистр 4.2.3, элемент а,, (о) (о) i (о) (o) а, — а„ /а „° az„,с выхода сумматора 3. 1. 3 — в регистр 3. 2. 3. На выхо45 де сумматора 7.1.2 получают величи(<) (о) (о) I o (о) ну а г = а г — а< /ан . а< = 1г которая в конце такта принимается в регистр 13. 2. 2. На выходе арифметического устройства 5.1.4 получают (о) (о) частное а<4 /а „ = U(g которое записывается в регистр 8.1.4. Элемент (o) а принимается в регистр 4.1,4, эле(о) ме нт а г 4 — в регистр 3 . 1 . 4, элемент (о) (о) а „вЂ” в регистр 4. 1. 3, элемент а в Регистр 3.1.3, элементы а„, и а4г (о) (о) в регистры 4.1.2 и 3.1.2 соответственно. (<) В шестом такте элемент а, принимается в регистр 4 . 2 . 4, в регистр 1354206 15 25 55 нимается в регистр 4.3.4, а элемент (2) (i) (<) 2 (<) (1) 44 44 24 22 42 дя сумматора 7.2.4 — в регистр 3.3.4. В десятом такте с выхода сумматора 7.3.4 элемент а() = а(1- а2) /а х (2) 44 44 34 33 яа4 = 1 4 принимается в регистр 13.4.4. На этом разложение квадратной матрицы А = (а;Д размерности N - =4 заканчивается, Элементы матрицы L последовательно принимались в регистры 3.2.4 принимается элемент я(" (о) (О1 (О1 <о) я 24 д 14 /я 1, а 24 с ВыхОдя сумма тара 7.1.4. Арифметическое устройство 5.2.3 выполняет деление и частное а23 /а„ = U23 записывается в регистр (1l I (1) (а) 8.2.3. Элемент а принимается в регистр 4.2.3, а в регистр 3.2.3 с выхода сумматора 7.1,3 принимается элемент а, = a» — a„ /a„, à, . На (() (o) (0) г (О) выходе сумматора 7.1.2 получают эле(<) (а) (o1 у (o) ° (ol МЕНТ Я42 = Я4 Я12 /Я 1, Я 4 = 1.42 q КО тарый принимается в регистр 13.2.2. (о1 (01 Элементы а, и а,„ записываются в регистры 4 ° 1.4 и 3.1.4 соответственно, а элементы а4, и а, — в регист(о) (ol ры 4.1 ° 3 и"3.1.3 соответственно, В седьмом такте на выходе сумматора 7.2.3 получают элемент а (2) (1) (i) I () И) = а — а2 3/а а,32 = 1„, который будет принят в регистр 13.3,3. Арифметическое устройство 5.2.4 выполняет деление и частное а24/а, = U24 запи(1) () сывается в регистр 8.2.4, элемент (11 а 3 — в регистр 4.2.4. В регистр 3.2.4 с выхода сумматора 7.1.4 принимается элемент а „, = а — а, /à„ i (i) (a) (o (о) а,, в регистр 4.2.3 — элемент а() а в регистр 3.2.3 — элемент а4(,) (о1 - (ol g (о> (ol " (o) 43 а <3 /a1 Я41 Элементы Я41 и а принимаются в регистры 4.1.4 и (o\ 3.1.4. В восьмом такте элемент а ) прини(к) мается в регистр 4 ° 3.4 а элемент (2) (<) (<) I (1) (<) а 34 я 34 Я 24 /a 22 я 32 с ВыхОдя сум матора 7. 2. 4 принимается в регистр 3.3.4. На выходе сумматора 7.2.3 получяют элемент a43 = a 43 а 23 /a22 а = 143, который записывается в регистр 13.3.3. Элемент а принима(s) 42 ется в регистр 4.2.4, а элемент а 4 (ol (М t (о) (a22 а42 с выхода сумма тора 7.1 ° 4 — в регистр 3.2.4. В девятом такте арифметическое устройство 5.3.4 выполняет деление и частное а /а„ = U 4 принимает(2) ся в регистр 8,3.4. Элемент а, при-, 13.р.q. а элементы матрицы U хранятся в регистрах 8.р,q. Поскольку каждый элемент входной матрицы А используется в каждом данном процессорном элементе только один раз, можно выполнять LU-разложение потока матриц. Каждую следующую матрицу можно начинать подавать с N+1-го такта после начала подачи предыдущей матрицы. Блок 2 синхронизации работает следующим образом. По сигналу пуска счетчик 17 устанавливается в нулевое состояние и открывается элемент 16, -пропуская импульсы с выхода генератора 15 на счетный вход счетчика 17, содержимое счетчика 17 поступает на адресный вход блока 18, с информационных выходов которого сигналы синхронизации подаются на входы синхронизации всех блоков 1 ° Формула изобретения 1. Устройство для разбиения матриц, содержащее матрицу йз P строк по (Р+1-К) вычислительных блоков в каждой строке (где Р— порядок разбиваемой матрицы, К = 1,..., Р— порядковый номер строки матрицы)и блок синхронизации, выходы синхронизации К-й группы которого подключены к группе входов синхронизации всех вычислительных блоков К-й строки матрицы, о т л и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат, первый информационный вход (M+1)-го вычислительного блока (К+1)-й строки матрицы (К 3(P) подключен к первому информационному выходу М-ro вычислительного блока К-й строки матрицы, второй информационный выход M-го вычислительного блока (M Ф P + 1 — К) К-й строки матрицы подключен к второму информационному входу (М + 1)-ro вычислительного блока К-й строки матрицы, причем первый информационный вход М-го вычислительного блока первой строки является M-м информационным входом устройства, а первый информационный выход первого вычислительного блока К-й строки является К-м информационным выходом устройства, вход блока синхронизации является входом пуска устройства. 2. Устро)(ство по п.1, о т л и— ч а ю щ е е с я тем, что M-й вычи5 13542 слительный блок (М 1 1) К-й строки матрицы содержит три регистра, арифметическое устройство, коммутатор и сумматор, причем первый вход синхронизации группы вычислительного блока подключен к входам признака записи первого и второго Регистров, первый информационный вход вычислительного блока подключен к информационному входу первого регистра, выход которого подключен к первому информационному, входу коммутатора и к входу первого слагаемого сумматора, выход которого является первым информационным 15 выходом вычислительного блока, второй информационный вход вычислительного блока подключен к информационному входу второго регистра, выход которого подключен к входу первого операнда арифметического устройства и является вторым информационным выходом вычислительного блока,.второй вход синхронизации группы вычислительного блока подключен к входу признака записи ре- 25 гистра, третий вход синхронизации 06 группы вычислительного блока подключен к управляющему входу коммутатора, четвертый вход синхронизации группы вычислительного блока подключен к входу управления режимом (умножениеделение) арифметического устройства, выход которого подключен к входу второго слагаемого сумматора и к информационному входу третьего регистра, выход которого подключен к второму информационному входу коммутатора, выход которого подключен к входу второго операнда арифметического устройства. 3. Устройство по п.1, о т л и— ч а ю щ е е с я тем, что первый вычислительный блок К-й строки матрицы содержит регистр, причем вход синхронизации вычислительного блока подключен к входу признака записи регистра, первый информационный вход вычислительного блока подключен к информационному входу регистра, выход которого подключен к первому и второму выходам вычислительного блока ° 1354206 22. p. g 1354206 <Рг tg.0 4.ъ:=а =аЮ цп)у,рЮ,<(el М 4О- ç4 и Фз* 4ч Риа 5 ВНИИПИ Закаэ 5695/44 Тираж 671 Подписное Проиэв.-полигр. пр-тие, г. Ужгород, ул. Проектная, 4
