Устройство для операций над матрицами Советский патент 1993 года по МПК G06F15/347 

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

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

На фиг. 1 представлена структурная схема предлагаемого устройства; на фиг. 2 - структурная схема вычислительного модуля; на фиг. 3 - структурная схема блока задержки; на фиг. 4 - структурная схема делителя импульсов.

Устройство содержит вычислительные модули 1.I.J. где I 1, 2.....N - 1,J i,...,N - 1. делитель импульсов 2, блоки задержки 3.I.

Вычислительный модуль 1.I.J (фиг. 2) содержит регистры 4.1, 4.2, схему сравнения 5, коммутаторы 6.1-6.4, делитель 7, умножитель 8, сумматор 9, регистр 10.

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

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

00

о ю со с

СА)

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

Блок задержки 3.I содержит инвертор 11, вход которого является первым входом устройствЭ;формиррватель импульсов 13,1, первый вход которого является первым входом устройства 3.I, второй вход которого является вторым входом устройства 3.I, а выход которого является первым выходом устройства 3.1, формирователь импульсов 13.2, первый вход которого подключен к выходу элемента 11, второй вход которого является вторым входом устройства, а выход является вторым выходом устройства D-триггер 12.1, входом которого является первый вход устройства, синхров.ходом С, является второй вход устройства D-триггер 12.2, вход которого подключен к выходу D- триггера 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 являются выходом устройства.

Устройство для Ш-разложения матриц предназначено для разложения квадратной матрицы А размерности N на две треугольные: нижнюю левую L и верхнюю правую U такие, что Ш А, причем на главной диагонали матрицы L стоят единицы. Преобразование матрицы A aij выполняется по алгоритму исключения Гаусса с локальным выбором элемента, в процессе которого получаются элементы hj и Uij

аК /а&Г 1 при Л af.K 1

lik

аГГ /а Лприар-Л ГГ1, где

аГ - i | - (ai - Л / ) з . пои aF- t y S alt

npH-aF- iV ali

..о

,2...N, l,j K- 1...N, аць аи

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

0 1.I.J. Условимся, что на первый вход ПЭ поступает строка А ai,Ha второй вход - строка В bi, где I 1...М.ПЭ работает в двух режимах: первый режим: - управление происходит по

5 первому управляющему входу. В этом режиме в конце такта информация, поступающая на первый и второй входы ПЭ,записывается в регистры 4.1 и 4.2 соответственно, в ре- гистр4.1 записывается элементам в регистр

0 4.2 -Ы;

второй режим: - управление происходит по второму управляющему входу. В этом режиме в течение такта-схема 5 выполняет сравнения элементов ai и bi и на его выходе

5 получен сигнал.

(О, npnlbil. I ai I S

1,при Ibi l I ail. этот сигнал является управляющим сигна0 лом блоков 6.1, 6.2, 6.3, 6.4, причем по сигналу 5 0 информация со входов блоков поступает на первые выходы, по сигналу S 1 - на вторые выходы.

Блок 7 выполняет операцию деления и

5 на его выходе получаем bi/ainpHS 0

L

ai/bi при S 1 .

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

. при S 1 1 Блок 9 выполняет операцию суммирования 5 и на его выходе получаем fb2 - К при 5 0

И

|а-2 - К при 5 1.

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

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

1.1.} выполняет операции вычисления IH-U и

аи-1.и-1К, где + т, т 1, 2...N - I количество тактов по второму управляюще5 му входу.

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

К

Поступление исходных данных организова- нб следующим образом: на первый вход эле- мфнта 1.1.J поступает j строка, на второй вйод элемента 1.1 ,j поступает j + 1 строка. В каждом 1-м такте на входы устройства посту- па|ют элементы 1-го столбца.

При поступлении на первый вход уст- Р9йства управления 2 сигнала Начало ра- бдты триггер 14 устанавливается в 1, сметчик 15 устанавливается в О на выходе схемы 16 устанавливается значение 1 поступающее на первый вход блока задержки 3.JI.

; В первом такте на входы вычислительного модуля 1.1.1,1.1.2,1.1.3 поступают эле- aii. 321, аз1. 341 и записываются во вводные регистры. Одновременно триггер 12.1 блока задержки устанавливается в 1, счртчик 15 принимает значение 1, на выходе схимы 16 устанавливается значение О, на третьем выходе вычислительного модуля 1 1.JI.1 появится значение Un.

Во втором такте на входы вычислитель- ньх модулей ,1.1.1. 1.1.2,, 1.1.3 поступают значения ai2, 322, аз2, 342, в выходные реги- стэы вычислительных модулей 1.1.1, 1.1.2. 1. -.3 записываются элементы Э221, аз21.342 . одновременно на третьем выходе вычислительного модуля 1.1.1 появится значение иф, на вторых выходах вычислительных мо- дублей 1.1.1.1.1.2,1.1.3 появляются значения 121;. 1з1.141. Кроме-того триггер 12.2 устройства 3.1 устанавливается в 1, триггер 12,1 блрка 3.1 устанавливается в О, счетчик 15 принимает значение 2.

В третьем такте на входы вычислительны модулей 1.1.1,1.1.2.1 1,3 поступают, со от етственно, элементы aia, Э23, азз. 343 и в выходные регистры записываются элементы Э2з1, азз1, 3431, одновременно на третьем вЦходе вычислительного модуля 1.1.1 появ- значение Ui3. На входы вычислитель- нь)х модулей 1.2.2, 1.2.3 поступают элементы 322 , аз2 , 342 и записываются во вхЬдные регистры данных вычислительного модуля. Одновременно триггер 12.2 блока 3.1 устанавливается в О, триггер 12,1 блока 3.5 устанавливается в 1, счетчик 15 прини- ма|эт значение 3, на третьем выходе вычислительного модуля 1.2.2 появляется значение U22.

б четвертом такте на входы вычислительнь)х модулей 1.1.1, 1.1.2, 1.1.3 поступают эле- ме|ггы a1i4.a24, аз4, 344 и в (выходные регистры записываются элементы 324, 334 344, одновремен- но ;на третьем выходе вычислительного модуля J. t.1 появляется значение Ui4. На входы вычис- ли-|ельных модулей 1.2.2, 1.2.3 поступают элементы 3231. азз1, , в выходные регистры вычислительных модулей 1.2.2, 1.2.3 записываются значения азз2, адз2, на третьем выходе вычислительных модулей 1.2.2 появляется значение U23. на вторых выходах вы- числительных модулей 1.2.2, 1.2.3 появляются значения 1з2, 142. Кроме того, триггер 12.2 блока 3,2 устанавливается в Г, триггер 12.1 блока 3.2 устанавливается в О, счетчик 15 принимает значение 4, т.е. переполняется, сигнал переполнения поступает на вход счетчика 15 и обнуляет его, одновременно сигнал переполнения поступает на вход элемента 17 и в случае наличия на входе устройства 2 сигнала Конец работы триггер 14 устанавливзется в О, в противном случае на выходе схемы 16 устанавливается 1, на входы вычислительных модулей 1/1.1, 1.1.2. 1.1.3 можнб-подавать следующую матрицу.

В пятом такте на входы вычислительных модулей 1.2.2, 1.2.3 поступают элементы 3241,3341, Э441, в выходные регистры записываются элементы аз4 ,344 , на третьем выходе вычислительного модуля 1.2.2 появляется значение U24. На вход вычислительного модуля 1.3.3 поступают значения азз2, 3432 и записываются во входных регистрах, одновременно на третьем выходе вычислительного модуля появляется значение 1)зз. Кроме того триггер 12.2 элемента 3.2 устанавливается .

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

выходе появляется значение U34, на втбром выходе появляется значение 143.

На этом разложение матрицы ,jj размерности N 4 заканчивается.

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

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

1. Устройство для операций над матрицами, содержащее N(N - 1)/2 вычислительных модулей (N - размерность входной матрицы) и делитель импульсов, входы установки и обнуления которого подключены соответственно к входам признака начала и окончания вычислений устройства. 1-й ин- формационный вход которого (I 1, N - 1) подключен к первому информационному входу (1, i)-ro вычислительного модуля, отличающееся тем, что, с целью повышения быстродействия, устройство содержит N - 1 блоков задержки, объединенные синх- ровходы которых подключены к синхровхо- дам устройства и делителя импульсов, выход которого подключен к информациейному входу первого блока задержки,первый выход К-то блока задержки (К-1, N-2) подключен к информационному входу (К + 1)-го блока задержки, J-й информационный вход устройства (J 1, N -1) подключен к второму информационному входу Q - 1)-го вычислительного модуля, второй и третий выходы 1-го блока задержки подключены соответственно к объединенным входам разрешения ввода и объединенным входам разрешения вывода по первому выходу (i, 1)-х х (I I, N -1) вычислительных модулей, вторые выходы всех вычислительных модулей образуют первую группу выходов устройства, вторую группу выходов которого образуют третьи выходы (I, }-х вычислительных модулей и первый выход (N - j, N - j)-ro вычислительного модуля, первый вь1ход(К.д)-го вычислительного модуля (д К + V. NI - 1) подключен к второму информационному входу (К + 1, д)- го вычислительного модуля, первый информационный аход которого подключен к первому выходу (К, g - 1)-ro вычислительного модуля.

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

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

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

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

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

f

I

I

9

IVi

33

о

fO

Ф/г4

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