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

(51)с 0 06 34 ГОСУДАРСТВЕННОЕ ПАТЕНТНОВЕДОМСТВО СССР(ГОСПАТЕНТ СССР) ПИСАНИЕ ИЗОБРЕТЕНИЯ СВИДЕТЕЛЬСТВУ К АВТОРСК МасФ%абай жно посгроить , сумматор 10 и строить на мик 1, коммутаторы ные(71)Киевский политехнический институт им.50-летия Великой Октябрьской социалистической революции(56) Копд Н.Т. апбезеззоп С.Е. Яумос аггауз аког НЯи Ярагзе Масгх Ргосеебпд.1978, р. 256-282 Зосету аког пбвзтга апб Арреб Майеп 1 атсз (1979).Авторское свидетельство СССР М 1;354206, кл, 0 06 Г 15/347, 1987.(54) УСТРОЙСТВО ДЛЯ ОПЕРАЦИЙ НАД МАТРИЦАМИ(57),Изобретение относится к автоматике и вычислительной технике и может быть исполЬзовано при построении специализирозобретение относится к автоматике и ыч 1 слительной технике и может быть исолЬэовано при построении специализироанных, в том числе и систолических стройств.для решения систем линейных равнений. Целью изобретения является повышение быстродействия,На фиг, 1 представлена структурная схема предлагаемого устройства; на фиг. 2 -структурная схема вычислительного модуля; на фиг. 3 - структурная схема блока задержки; на фиг, 4 - структурная схемаделителя импульсов,Устройство содержит вычислительмодули 1.Ц, где= 1, 2М - 1, ) =1йделитель импульсов 2, блоки задержки ванных устроиств, предназначенных для решения систем линейных алгебраических уравнений. Устройство позволяет повысить быстродействие и точность вычислений, Устройство содержит вычислительные модули, делитель импульсов, блоки задержки, причем входы устройства управления являются управляющими входами устройства. Сущность работы устройства состоит в том, что оно осуществляет разложение данной квадратной матрицы А = а 1) размерности М на две треугольные: нижнюю левуюи верхнюю правую О, такие что О = А, причем на главной диагонали матрицыстоят единицы. Преобразование матрицы А выполняется по алгоритму исключения Гаусса с локальным выбором ведущего элемента, в процессе которого вычисляются элементы ; и В. 1 з.п. ф-лы, 4 ил. Вычислительный модуль 1.Ц (фиг. 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схему сравнения 5 можно поросхемах К 155 ИПЗ и К 155 СП5 10 О-триггер 12,1, входом которого является 15 20 6.1, 6,2, 6.3, 6.4 могут быть построены, например, на микросхемах 155 ЛМ 1, 155 ЛИ 1,Блок задержки 3.1 содержит инвертор 11, вход которого является первым входом устройства, формирователь импульсов 13,1, первый вход которого является первым входом устройства 3,1, второй вход которого является вторым входом устройства 3,1, а выход которого является первым выходом устройства 3.1, формирователь импульсов 13,2, первый вход которого подключен к выходу элемента 11, второй вход которого является вторым входом устройства, а выход является вторым выходом устройства первый вход устройства, синхровходом С является второй вход устройства О-триггер 12,2, вход которого подключен к выходу О- триггера 12,1, а синхровход С является вторым входом устройства, выход является третьим выходом устройства.Формирователи 13,1, 13,2 могут быть построены нэ микросхеме К 155 ЛИ 1, триггера 12.1, 12.2 могут быть построены на микросхеме К 155 ТМ 2.Делитель импульсов 2 содержит схему "И" 17, первый вход которой является вторым входом устройства, второй вход кото-. рой подключен к выходу переполнения счетчика 15, В-Я-триггера 14, Я-вход которого является входом признака начала устройства, а В-вход подключен к выходусхемы 17, счетчик 15, счетный в вход которого подключен к прямому выходу триггера 14, вход сброса подключен.к выходу переполнения счетчика и одновременно является первым входом устройства, а синхровход является третьим входом устройства, схему иИЛИ- НЕ" 16, первый вход которой подключен к инверсному выходу й-Я-триггера 14, а остальные входы и информационные выходы счетчика 15, выход схемы 16 являютсявыходом устройства,Устройство дляО-разложения матриц предназначено для разложения квадратной матрицы А размерности й на две треугольные: нижнюю левуюи верхнюю правую О такие, чтоО = А, причем на главной диагонали матрицыстоят единицы, П реобразование матрицы А = а(Д выполняется по алгоритму исключения Гаусса с локальным выбором элемента,в процессе которого получаются элементы (1 и О) аК:1./ЭКк при а - 1,ра( 1(Ок =а э к с) - 1,к при а - 1.ка(кК - 1 ( - 1 где 25 30 35 40 45 50Г:ц - (а": /а 1) а",при аГ: 5 аГк1- (аГк /аГ-Д)аГ - , приа(-фа)ааа К=1,2 И, Ц= К+1 й, э 1 =а(Рассмотрим работу устройства, Для простоты описания предварительно рассмотрим работу процессорного элемента 1.Ц. Условимся, что на первый вход ПЭ поступает строка А = а(,на второй вход - строка В = Ь, где= 1 М.ПЭ работает в двУх режимах: первый режим: - управление происходит по первому управляющему входу. В этом режиме в конце такта информация, поступающая на первый и второй входы ПЭ,записывается в регистры 4.1 и 4:2 соответственно, в регистр 4.1 записывается элемент а 1, в регистр 4.2 - Ь 1; второй режим: - управление происходит по второму управляющему входу. В этом режиме в течение такта схема 5 выполняет сравнения элементов а 1 и Ь 1 и на его выходе получен сигналО, приЬ 1 са 1 Я=1, при Ь 1э 11, этот сигнал является управляющим сигналом блоков 6.1, 6.2, 6,3, 6.4, причем по сигналу Я = 0 информация со входов блоков поступает на первые выходы, по сигналу Я = 1 - на вторые выходы.Блок 7 выполняет операцию деления и на его выходе получаемЬ 1/а 1 при Я =01 а 1/ь 1 при а = 1, Блок 8 выполняет операцию умножения и на его выходе получаема 2 при Я =О К=1 Ь 2 при Я = 1 1 Блок 9 выполняет операцию суммирования и на его выходе получаемЬ 2- К при Я=О С=а 2- К при Я = 1. Элемент С по заднему фронту тактирующего импульса принимается в регистр 10.Таким образом вычислительный модуль1.Ц выполняет операции вычисления 11+1,1 и а+1.н 1, где К= + и), в = 1, 2.М - 1 -к количество тактов по второму управляющему входу.Для простоты описания работы всего устройства без потери общности положим размерность матрицы й = 4. Условимся, что прием информации во все регистры происходит по заднему фронту синхроимпульса.Поступление исходных данных организовано следующим образом; на первый вход элемента 1.1.) поступает ) строка, нэ второйвМод элемента 1.1, поступает) + 1 строка. Вкэ)ждом 1-м такте на входы устройства поступают элементы 1-го столбца.При поступлении на первый вход устройства управления 2 сигнала нНэчало рабОты" триггер 14 устанавливается в и 1",советчик 15 устанавливается в иО", на выходе 10схемы 16 устанавливается значение и 1", поступающее на первый вход блока задержки3,1.В первом такте на входы вычислительного модуля 1.1,1, 1,1.2, 1,1.3 поступают элемнты а 11, а 21, аз 1. аа 1 и записываются вов одн ые регистры. Одновременно триггер1,1 блока задержки устанавливается в н 1",сч, тчик 15 принимает значение 1, на выходесхемы 16 устанавливается значение иО", на 20третьем выходе вычислительного модуля 11,)1.1 появится значение О 11,Во втором такте на входы вычислительнь 1 х модулей 1,1.1, 1.1.21.1.3 поступаютз ачения а 12, а 22, аз 2, аа 2, в выходные регист ы вычислительных модулей 1,1.1, 1.1.2,13 записываются элементы а 22, аз 2, аа 2,1 1 1одновременно на третьем выходе вычислительного модуля 1.1.1 появится значениеО 12, на вторых выходах вычислительных модурей 1.1.1, 1.1.2, 1.1,3 появляются значения121, 1 з 1, 141, Кроме,того триггер 12.2 устройства 3.1 устанавливается в и 1", триггер 12,1блока 3.1 устанавливается в иО", счетчик 15принимает значение н 2". 35В третьем такте на входы вычислительньрмодулей 1.1.1,1.1.2,1,1, 3 поступают, соОт)аЕтСтВЕННО, ЭЛЕМЕНТЫ а 1 З, а 2 З, аЗЗ, ааЗ ИВ)выходные регистры записываются элементы а 2 з, азз, а 4 з, одновременно на третьем 40выходе вычислительного модуля 1,1,1 появлятся значение О 1 з. На входы вычислительных модулей 1.2,2, 1,2,3 поступаютэлементы а 22, аз 2, а 42 и записываются во1входные регистры данных вычислительного 45модуля. Одновременно триггер 12.2 блока3. 1 устанавливается в мО", триггер 12,1 блока3.2 устанавливается в н 1", счетчик 15 принимайт значение н 3", на третьем выходе вычислительного модуля 1,2.2 появляется 50зндчение О 22.В четвертом такте на входы вычислитель-,нь 1 х модулей 1.1,1, 1,1,2, 1.1.3 поступают элемеггы а 14,а 24, аза, а 44 и в ) выходные регистры1заг 1 исываются элементы а 24, аза, ааа, одновременно на третьем выходе вычислительного модуля 1. 1,1 появляется значение Ом. На входы вычислительных модулей 1.2,2, 1.2.3 поступают элементы а 2 з . азз, ааа, в выходные регистры вычислительных модулей 1.2.2, 1.2.3 записываются значения азз, ааз, на третьем2выходе вычислительных модулей 1,2.2 появляется значение О 2 з. на вторых выходах вычислительных модулей 1,2,2, 1.2. 3 появляются значения з 2, 142. Кроме того, триггер 12,2 блока 3,2 устанавливается в и 1", триггер 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 поступают элементы а 24, аза, а 44, в выхорные регистры записываются элементы аз 4, а 442, на третьем выходе вычислительного модуля 1.2,2 появляется значение О 24. На вход вычислительного модуля 1,3.3 поступают значения азз, ааз и записываются во входных реги 2 2страх, одновременно на третьем выходе вычислительного модуля появляется значение Озз. Кроме того триггер 12.2 элемента 3,2 устанавливается в иО".В шесто.м такте на вход вычислительного модуля 1.3.3 поступают элементы аз 42. а 44, в выходной регистр записывается значение а 44 = О 44, одновременно.на третьем3выходе появляется значение Оз 4, на втером выходе появляется значение 14 З.На этом разложение матрицы А=а),1) размерности И = 4 заканчивается,Отметим, что данная структура позволяет производить Ш-разложение потока матриц, причем каждую следующую матрицу можно начинать подавать с М+ 1 та кта после начала подачи предыдущей матрицы,Формула изобретения 1. Устройство для операций над матрицами, содержащее Я(й - 1)/2 вычислительных модулей (М - размерность входной матрицы) и делитель импульсов, входы установки и обнуления которого подключены соответственно к входам признака начала и окончания вычислении устроиства )-и ин. формационныи вход которого 0 = 1, "г) . 1) подключен к первому информационному входу (1, 1)-го вычислительного модуля, о тл и ч а ю щ е е с я тем, что, с целью повышения быстродействия, устройство содержит М - 1 блоков задержки, объединенные синхровходы которых подключены к синхровходам устройства и делителя импульсов, выход которого подключен к информэцион 1802363ному входу первого блока зааеожки, первый выход К го блока задержки(К=-1, М) подключен к информационному входу (К+ 1)-го блока задержки, -й информационный вход устройства Ц = 1, М - 1) подключен к второму информационному входу (1 - 1)-го вычислительного модуля, второй и третий выходы 1-го блока задержки подключены соответственно к объединенным входам разрешения ввода и объединенным входам разрешения вывода по первому выходу (1, 1)-х х (1 = 1, й - 3) вычислительных модулей, вторые выходы всех вычислительных модулей образуют первую группу выходов устройства, вторую группу выходов которого образуют третьи выходы (1, 1)-х вычислительных модулей и первый выход(И -), К -и-го вычислительного модуля, первый выхо К, )-го вычислительного модуля (д = К+ 1, М - 1 подключен к второму информационному входу (К+ 1, д)- го вычислительного модуля, первый информационный;ход которого подключен к первому выходу (К, д -1)-го вычислительного модуля,2. Устройство поп.1, отл и ч э ю щеес я тем, что каждый вычислительный модуль содержит три регистра, схему сравнения, четыре коммутатора, делитель, умножитель и сумматор, причем первый и второй информационные входы вычислительного модуля подключены к информационным входам соответственно первого и второго регистров,объединенные синхровходы которых подключены к входу разрешения ввода вычислительного модуля, вход разрешения вывода по первому выходу которого под ключен к синхровходу третьего регистра,выход и информационный вход которого подключены соответственно к первому выходу вычислительного модуля и выходу сумматора, первый вход которого подключен к 10 объединенным первым выходам третьего ичетвертого коммутаторов, объединенные вторые выходы которых подключены к первому входу умножителя, выход и второй вход которого подключены соответственно 15 к второму входу сумматора и выходу делителя, обьединенного с вторым выходом вычислительного модуля, третий выход которого подключен к информационным входам первого регистра и четвертого коммутатора, ин формационный вход третьего коммутатораподключен к информационному входу второго регистра, выход которого подключен к информационному входу первого коммутатора и первому входу схемы сравнения, вто рой вход которой подключен к выходупервого регистра и информационному входу второго коммутатора, выход схемы сравнения подключен к управляющим входам всех коммутаторов, первый вход делителя 30 подключен к объединенным первым выходам первого и второго коммутаторов, объединенные вторые выходы которых подключены к второму входу делителя.1802363 Составитель Ю,КаневскийТехред М.Моргентал Корректор П, Гереши Редактор С,Кулакова Производственно издэтельскии комбинат "Патент", г. Ужгород, ул,(агарина, 101 Заказ 849 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035. Москва, Ж, Раушская наб., 4/5