Устройство для операций над матрицами

 

,Изобретение относится к автоматике и вычислительной технике и может быть исполйовано при построении специализированных устройств, предназначенных для решения систем линейных алгебраических уравнений. Устройство позволяет повысить быстродействие и точность вычислений. Устройство содержит вычислительные модули, делитель импульсов, блоки задержки, причем входы устройства управления являются управляющими входами устройства. Сущность работы устройства состоит в том, что оно осуществляет разложение данной квадратной матрицы А aij размерности N на две треугольные: нижнюю левую L и верхнюю правую U. такие что U А, причем на главной диагонали матрицы L стоят единицы . Преобразование матрицы А выполняется по алгоритму исключения Гаусса с локальным выбором ведущего элемента, в процессе которого вычисляются элементы Ijj и Uij. 1 з.п. ф-лы, 4 ил. Ё

СОКЛ .:..1-. ВСКИХ

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

РЕ(;ПУБЛИК

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4782501/24 (22) 16.01,90 (46) 15.03.93, Бюл, М 10 (71) Киевский политехнический институт им.

50-летия Великой Октябрьской социалистической революции (72) Ю,С.Каневский, В.Л.Лепеха и О.В.Масленников (56) Kung Н.Т. and Lelsesson С.E. Systolic аггауз for VISlln Sparse Matrix Proceeding.

1978, р. 256-282 Society for Industrial and

AppilIed Mathematics (1979).

Авторское свидетельство СССР

N. 1,:354206, кл. G 06 F 15/347, 1987. (54) УСТРОЙСТВО ДЛЯ ОПЕРАЦИЙ НАД

МАТРИЦАМИ (57),Изобретение относится к автоматике и вычислительной технике и может быть исполЬзовано при построении специализироИзобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных, в том числе и систолических устройств.для решения систем линейных уравнений.

Целью изобретения является повышение быстродействия.

На фиг, 1 представлена структурная схема предлагаемого устройства; на фиг. 2— структурная схема вычислительного модуля; на фиг. 3 — структурная схема блока задержки; на фиг. 4 — структурная схема делителя импульсов, Устройство содержит вычислительные мод ли 1.Ц, где i = 1, 2,...,N - 1. J =I....,N - 1, делитель импульсов 2, блоки задержки З.i

„., .Ж „„1802363 А1 ванных устройств, предназначенных для решения систем линейных алгебраических уравнений. Устройство позволяет повысить быстродействие и точность вычислений, Устройство содержит вычислительные модули, делитель импульсов, блоки задержки, причем входы устройства управления являются управляющими входами устройства. Сущность работы устройства состоит в том, что оно осуществляет разложение данной квадратной матрицы А = (а11) размерности N на две треугольные: нижнюю левую L и верхнюю правую U, такие что U = А*, причем на главной диагонали матрицы L стоят единицы. Преобразование матрицы А выполняется по алгоритму исключения Гаусса с локальным выбором ведущего элемента, в процессе которого вычисляются элементы l1I и U1l. 1 з.п. ф-лы,4 ил.

Вычислительный модуль 1.Ц (фиг. 2) содержит регистры 4.1, 4.2, схему сравнения

5, коммутаторы 6.1 — 6.4, делитель 7, умножитель 8, сумматор 9. регистр 10.

Делитель 7 и умножитель 8 могут быть построены по любой известной схеме и содержать, например, сумматор и несколько регистров для хранения операндов. промежуточных и окончательных результатов (см. например, К.Г.Самофалов, В.И.Корнейчук, В.П.Тарасенко "Цифровые электронные вычислительные машины", Киев, издательское объединение "Вища школа", 1983 r., рис, 5.36 или рис. 5.38 стр. 351 — 354).

Регистры 4.1, 4.2, 10 можно посгроить на базе микросхем К155ИР1, сумматор 10 и схему сравнения 5 можно построить на микросхемах К155ИПЗ и К155СП1, коммугя горы

1802363

10

О-триггер 12.1, входом которого является 15

55

6.1. 6.2, 6.3, 6.4 могут быть построены, например, на микросхемах 155ЛМ1, 155ЛИ1.

Блок задержки З.i содержит инвертор

11, вход которого является первым входом устройства, формирователь импульсов 13,1, первый вход которого является первым входом устройства 3,l, второй вход которого является вторым входом устройства З,i, а выход которого является первым выходом устройства З.i, формирователь импульсов

13.2, первый вход которого подключен к выходу элемента 11, второй вход которого является вторым входом устройства, а выход является вторым выходом устройства первый вход устройства, синхровходом С является второй входустройства D-триггер

12.2, вход которого подключен к выходу 0триггера 12.1, а синхровход С является вторым входом устройства, выход является третьим выходом устройства.

Формирователи 13,1. 13,2 могут быть построены на микросхеме К155ЛИ1, триггера 12.1, 12.2 могут быть построены на микросхеме К155ТМ2.

Делитель импульсов 2 содержит схему

"И" 17, первый вход которой является вторым входом устройства, второй вход кото= рой подключен к выходу переполнения счетчика 15, R-S-триггера 14, S-вход которого является входом признака начала устройства, à R-вход подключен к выходу схемы 17, счетчик 15, счетный в вход которого подключен к прямому выходу триггера 14, вход сброса подключен .к выходу переполнения счетчика и одновременно является первым входом устройства, а синхровход является третьим входом устройства, схему иИЛИНЕ" 16, первый вход которой подключен к инверсному выходу R-S-триггера 14, а остальные входы и информационные выходы счетчика 15, выход схемы 16 являютсявыходом устройства, Устройство для LU-разложения матриц предназначено для разложения квадратной матрицы А размерности N на две треугольные: нижнюю левую L и верхнюю правую Uтакие,,что LU = А*, причем на главной диагонали матрицы L стоят единицы. П реобра зова н ие матрицы А = (ay) выполняется по алгоритму исключения Гаусса с локальным выбором элемента,в процессе которого получаются элементы !л и U)I ак — 1 p/a! k — при ai — 1.k al.й

Uk =а с). — 1,к при àt:1.K >а (к

1 )(— 1 1 где

F:> — (а,"- Л /A ) а.", при аГ:4 s aFy

1I — (а1к |iàF-Д)а,": . приз(-4)@FAN а

K=1, 2...N, Ц = К+ 1...N, а(! =а(!

Рассмотрим работу устройства. Для простоты описания предварительно рассмотрим работу процессорного элемента

1.Ц. Условимся, что на первый вход ПЭ поступает строка А = (a(),на второй вход— строка В = (bi), где i = 1...N.ÏÝ работает в двух режимах: первый режим: — управление происходит по первому управляющему входу. В этом режиме в конце такта информация, поступающая на первый и второй входы ПЭ,записывается в регистры 4.1 и 4:2 соответственно, в регистр 4.1 записывается элемент ai, в регистр

4.2 — Ь1, второй режим: — управление происходит по второму управляющему-входу. B этом режиме в течение такта-схема 5 выполняет сравнения элементов а! и Ь1 и на его выходе получен сигнал !

О, при Ь1I < à1!

S=

1,при !Ь1 !> а!!. этот сигнал является управляющим сигналом блоков 6.1, 6.2, 6,3. 6.4, причем по сигналу $ = 0 информация со входов блоков поступает на первые выходы, по сигналу

S = 1 — на вторые выходы.

Блок 7 выполняет операцию деления и на его выходе получаем

b>/а1 при $ = 0

L(a i lb> при S = 1 .

Блок 8 выполняет операцию умножения и на его выходе получаем

L*a2 при S =0

К=

L*bz при $ = 1

Блок 9 выполняет операцию суммирования и на его выходе получаем

bz- К при S=O

С=

az-КприS=1.

Элемент С по заднему фронту тактирующего импульса принимается в регистр 10.

Таким образом вычислительный модуль

1.Ц выполняет операции вычисления II+>.) и а)+1.н-, где K=i + m, m = 1, 2.„N — I— к количество тактов по второму управляющему входу.

Для простоты описания работы всего устройства без потери общности положим размерность матрицы N = 4. Условимся, что прием информации во все регистры происходит по заднему фронту синхроимпульса.

1802363

Поступление исходных данных организовано следующим образом; на первый вход элемента 1.1.j поступает j строка. на второй в)!од элемента 1.1,j поступает j+ 1 строка. В ка)ждом I ì такте на входы устройства посту- 5 пвют элементы I-го столбца.

При поступлении на первый вход устройства управления 2 сигнала нНачало рабОтын триггер 14 устанавливается в и1", сч1етчик 15 устанавливается в и0", на выходе 10 схемы 16 устанавливается значение и1", поступающее на первый вход блока задержки

3.1.

В первом такте на входы вычислительного модуля 1.1.1, 1.1.2, 1,1.3 поступают эле- 15 м нты 811, а21, а31. а41 и записываются во в одные регистры. Одновременно триггер

1 .1 блока задержки устанавливается в н1", сч, тчик 15 принимает значение 1, на выходе схемы 16 устанавливается значение и0", на 20 третьем выходе вычислительного модуля 1

1, I.1 появится значение U11, Во втором такте на входы вычислительнь!х модулей 1.1.1, 1.1.2„1.1.3 поступают

3 ачения 812, 822, 832, а42, в выходные реги- 25 ст ы вычислительных модулей 1,1.1, 1.1.2, 1..3 записываются элементы 822 а32, 842

1 1 1 одновременно на третьем выходе вычислительного модуля 1.1.1 появится значение

012, на вторых выходах вычислительных мо- 30 дурей 1.1.1, 1.1.2, 1.1,3 появляются значения

I21, I31, !41. Кроме,того триггер 12.2 устройства 3.1 устанавливается в и1", триггер 12,1 блока 3.1 устанавливается в и0", счетчик 15 принимает значение н2". 35

B третьем такте на входы вычислительныхх модулей 1. 1. 1, 1. 1. 2, 1. 1. 3 поступают, соответственно, элементы 813, а23, азз, 843 и в

) выходные регистры записываются элеменTbl 823 а33, а43, одновременно на третьем 40

1 1 1. выходе вычислительного модуля 1.1.1 появля тся значение U13. На входы вычислительных модулей 1.2,2, 1,2.3 поступают элементы 822, 832, 842 и записываются во

1 1 1 входные регистры данных вычислительного 45 модуля. Одновременно триггер 12.2 блока

3. 1 устанавливается в м0", триггер 12,1 блока

3.2 устанавливается в н1", счетчик 15 принимает значение н3", на третьем выходе вычислительного модуля 1,2.2 появляется 50 значение U22.

В четвертом такте на входы вычислитель- . нь!х модулей 1.1.1, 1.1,2, 1.1.3 поступают элеме ггы 814,824, 834, а44 и в ) выходные регистры

1 заг1исываются элементы 824, 834, 844, одновременно на третьем выходе вычислительного модуля

1. 1,1 появляется значение U14. На входы вычислительных модулей 1.2.2, 1.2.3 поступают элементы 823 . 833, 844, в выходные регист1 1 1 ры вычислительных модулей 1.2.2, 1.2.3 записываются значения а33, а43, на третьем

2 выходе вычислительных модулей 1,2.2 появляется значение U23. на вторых выходах вычислительных модулей 1,2,2, 1.2. 3 появляются значения !32, !42. Кроме того, триггер 12.2 блока 3,2 устанавливается в и1", триггер 12.1 блока 3.2 устанавливается в и0". счетчик 15 принимает значение 4. т,е. переполняется, сигнал переполнения поступает на вход счетчика 15 и обнуляет его, одновременно сигнал переполнения поступает на вход элемента 17 и в случае наличия на входе устройства 2 сигнала "Конец работы" триггер 14 устанавливается в и0", в противном случае на выходе схемы 16 устанавливается и1", на входы вычислительных модулей 1.1.1, 1.1.2. 1.1,3 можно. подавать следующую матрицу.

В пятом такте на входы вычислительнь)х модулей 1.2.2, 1.2.3 поступают элементы

824, 834, а44, в выходные регистры записы1 1 1 ваются элементы а34, 8442, на третьем выходе вычислительного модуля 1.2,2 появляется значение U24. На вход вычислительного модуля 1,3.3 поступают значения азз, а43 и записываются во входных реги2 2 страх, одновременно на третьем выходе вычислительного модуля появляется значение

U33. Кроме того триггер 12.2 элемента 3,2 устанавливается в и0".

В шесто.м такте на вход вычислительного модуля 1.3.3 поступают элементы а342. а44, в выходной регистр записывается значение а44 = U44, одновременно.на третьем

3 выходе появляется значение 034, на втором выходе появляется значение !43.

На этом разложение матрицы А=(а),!) размерности И = 4 заканчивается.

Отметим, что данная структура позволяет производить Ш-разложение потока матриц, причем каждую следующую матрицу можно начинать подавать с N+ 1 та кта после начала подачи предыдущей матрицы.

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

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

N - 1 блоков задержки, объединенные синхровходы которых подключены к синхровходам устройства и делителя импульсов, выход которого подключен к информацион1802363 ному входу первого блока задержки, первый выход К- го блока задержки (К=-1, N-2) подключен к информационному входу (К+ 1)-го блока задержки, -й информационный вход устройства (j = 1, N - -1) подключен к второму информационному входу Q - 1)-ro вычислительного модуля, второй и третий выходы

I-ro блока задержки подключены соответственно к объединенным входам разрешения ввода и объединенным входам разрешения вывода по первому выходу (i, 1)-х х (i =, N - 3) вычислительных модулей, вторые выходы всех вычислительных модулей образуют первую группу выходов устройства, вторую группу выходов которого образуют третьи выходы (1, i)-x вычислительных модулей и первый выход(М -j, N- -j)-ro вычислительного модуля, первый выхо К, )-ro вычислительного модуля (g = К+ 1, N - 1 подключен к второму информационному входу (К+ 1, g)го вычислительного модуля, первый информационный;ход которого подключен к первому выходу (К, g - 1)-ro вычислительного модуля, 2. Устройство по и. 1, о т л и ч э ю щ е ес я тем, что каждый вычислительный модуль содержит три регистра, схему сравнения, четыре коммутатора, делитель, умножитель и сумматор, причем первый и второй информационные входы вычислительного модуля подключены к информационным входам соответственно первого и второго регистров, объединенные синхровходы которых подключены к входу разрешения ввода вычислительного модуля, вход разрешения вывода по первому выходу которого под5 ключен к синхровходу третьего регистра, выход и информационный вход которого подключены соответственно к первому выходу вычислительного модуля и выходу сумматора, первый вход которого подключен к

10 объединенным первым выходам третьего и четвертого коммутаторов, объединенные вторые выходы которых подключены к первому входу умножителя, выход и второй вход которого подключены соответственно

15 к второму входу сумматора и выходу делителя, обьединенного с вторым выходом вычислительного модуля, третий выход которого подключен к информационным входам первого регистра и четвертого коммутатора, ин20 формационный вход третьего коммутатора подключен к информационному входу второго регистра, выход которого подключен к информационному входу первого коммутатора и первому входу схемы сравнения, вто25 рой вход которой подключен к выходу первого регистра и информационному входу второго коммутатора, выход схемы сравнения подключен к управляющим входам всех коммутаторов, первый вход делителя

30 подключен к объединенным первым выходам первого и второго коммутаторов, объединенные вторые выходы которых подключены к второму входу делителя.

18(32:с63

1807363

Составитель Ю.Каневский

Техред М.Моргентал Корректор П, Гереши

Редактор С.Кулакова

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

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

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

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