Устройство для lv-разложения матриц
Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для Ш-разложения ( Н х Н )-матриц. Цель изобретения - сокращение аппаратурных затрат . Поставленная цель достигается тем, что устройство содержит М вычислительных модулей (М - фиксированное число, ОД Н), причем вычислительный модуль резлпт арифметические операции умножения, вычитания и вычисление обратной вели« ы числа.3 ил.
C0IO3 СОВЕТСКИХ
C(I ИАЛИСТИЧЕСКИХ, РЕСПУБЛИК (sl)s 6 06 F 15/347
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ())»;
)М (21) 4911241/24 (22) 03,01.91 (46) 23.11.92. Бюл, N. 43 (72) B.Ï.ßêóuj, Н.А,Лиходед, В.В»Косьянчук и П.И.Соболевский (56) Авторское свидетельство СССР
N. 1534470, кл. G 06 F 15/347, 1987.
Авторское свидетельство СССР
¹ 1509933, кл, G 06 F 15/347, 1989 (прототип). (54) УСТРОЙСТВО ДЛЯ LU-РАЗЛОЖЕНИЯ
МАТРИЦ
Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для треугольного разложения матриц.
Целью изобретения является сокращение аппаратурных затрат устройства.
На фиг.1 представлена структурная схема устройства для разложения матриц; на фиг.2 — структурная схема устройства для
LU-разложения матриц для случая M = 2 и Н = 4; на фиг.3 — пример схемы вычислительного модуля 6.
Устройство для LU-разложения матриц (фиг.1) содержит информационный вход 1, первый 2, второй 3 и третий 4 управляющие входы, синхровход 5, вычислительные модули 6! (1 = 1, М), первый 7, второй 10, третий 9 и четвертый 8 узлы задержки, группу элементов ИЛИ 11, элементы ИЛИ 12, 13 и 14 и выход 15. (1)) Я„Ц ()1) 1 777 1 сз ..) я (57) Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для
LU-разложения (Н х Н )-матриц. Цель изобретения — сокращение аппаратурных затрат. Поставленная цель достигается тем, что устройство содержит M вычислительных модулей(М вЂ” фиксированное число, М < Н), причем вычислительный модуль реали", от арифметические операции умнож"-ния, вычитания и вычисление обратной вели !!- bl числа. 3 ил.
Вычислительный модуль 6 (см,фиг.31 содержит информационный вход 16. первь!й
17, второй 18 и третий 19 управляющие входы, синхровход 20, умножитель 21, вычитатель 22, узел вычисления обратной величины числа 23, регистры 24 и 26, тр.,ггеры29,30,31,32,33и34, первый25, второй
28 и третий 27 узлы задержки, группы элементов И 35 — 42, группы элементов ИЛИ 43 — 45, элементы И 46 — 52, элементы ИЛИ 53 — 57, элементы HE 58 — 60, информационный выход 61, первый 62, второй 63 и тре ий 64 управляющие выходы.
В основу работы устройства для LU-разложения матрицы А = {а!!}, I,j = 1, Н на нижнюю треугольную с единицами по главной диагонали L = {l )} и верхнюю треугольную матрицу U = {щ!} положены следующие рекуррентные соотношения:
a.i =а!, i, =1. Н; k=1, Н:usa=a! "i=k, .Ю .. Щ
i=), ц))=а))!" . )=!.k<) Н, ) )=ам))-") о)), i (H, j = k a>i k i а!! к - !к uki k< j (H, k 1777155 Предполагается, что фиксированное число М может принимать значения в пределах от 2 до Н и соотношение Н/M — целое число. Если Н/M не целое число, то следует рассматривать матрицу А размером (Н х 1 1 Н ), где Н = Мг Н/М !(обозначение! !— означает наибольшее сверху целое). Матрица А получается добавлением к матрице А Н вЂ” Н вЂ” новых строк и столбцов, все элемен1 ты которых равны нулю, за исключением л ежа щих на диагонали, ра вных единице. После LU-разложения в матрицах L u U элементы строк и столбцов с номерами большими Н не принимаются во внимание. Каждый вычислительный модуль обладает возможностью реализации следующих функций ij j+H+2 j+H+2 îi (1,если у = О и (а1,p) = = «, 1) (0,1) (.О) 1, если ) = 1, О, если у = О и (а! ф ) = (0,0) где а!Р и y — значения соответственно на I первом, втором и третьем управляющих входах вычислительного модуля на J-м такте, и, ч, o) — значения соответственно на первом, втором и третьем управляющих выходах вычислительного модуля на J-м такте, а!, если (а, /У, ) !) =(1.1,0)1(0,1,0) (*, *. 1), Aj = aj1/а!, если(а,P . y)=(1, О, 0), а( а( если (а!, P, y) ) = (О, О, О) где а — значение на информационном входе вычислительного модуля на J-м такте, А — значение на информационном вы! +1 ходе вычислительного модуля Hà (J+1)-м такте, !, i, р, q — параметрь1,определяемые алгоритмом. Рассмотрим работу вычислительного модуля 6. Вычислительный модуль 6 работает в пяти режимах. которые задаются управляющими сигналами а,Р иу, подаваемыми соответственно нэ управляющие входы 17. 18 и 19, Соответствую10 a ij" = ri! j= (а!, /1, y) = 1,5, где — номер режима работы, которые подаются на соответствующие логические элементы вычислительного модуля .6. Причем управляющий сигнал обеспечивает запись в регистр или триггер на J-м такте, а управляющий сигнал а!j íà (J+1)-м такте, ! +1 Во всех режимах работы на информационный вход 16 подается элемент а, который записывается в регистр 24, информация задерживается узлом задержки 25 на Н тактов (узел задержки 25 содержит Н последовательно соединенных регистров), управляющие сигналы а!,p, yi подаются соответственно на входы 17, 18 и 19 и записываются соответственно в триггеры 27, 28 и 34, Управляющие сигналы а! и Р выдаются соответственно на выходы 62 и 63 с задержкой на (Н + 2) тактов, Регистры 24 и 25! (! = 1, Н) построены на двухтактных триггерах и в них запись информации осуществляется по заднему фронту тактового импульса. Регистр 26 построен на однотактных триггерах и информация в него записывается по переднему фронту тактового импульса. В первом режиме подаются управляющие сигналы (а1, P, y) = (1, 1, О). При этом формируются сигналы г1= а1 =1. Открыг ваются группы элементов 37, 40 и элемент И 52. Элемент а! с выхода регистра 24 через группы элементов И 40 и ИЛИ 45 подается на выход 61, На выходе узла вычисления обратной величины числа 23 формируется значение 1/а!, которое через группы элементов И 37 и ИЛИ 43 записывается в регистр 251 íà (J+1)-м такте. Управляющий сигнал yi = 0, подаваемый íà вход 19, устанавливает триггер 34 в нулевое состояние и с его инверсного выхода единичный сигнал через элементы И 52 и ИЛИ 56 выдается на выход 64, т.е, на выход 64 выдается ) =1, Во втором режиме (c j, P, ) ) = (О, 1. О). Открываются группы элементов И 36, 40 и элемент И 52. Элемент а! с выхода регистра 24 через группы элементов И 36 и ИЛИ 43 записывается в регистр 251 и через группы элементов И 40 и ИЛИ 45 подается на выход 61, На выход 64 выдается управляющий сигнал ) = 1. щ и е з н а ч е н и я у и р а в л я ю щ и" сигна лов (а1, P, y) íà J-ì такте определяют управляющие сигналы 1777155 Ъ =((-1)Н+) -1. В третьем режиме (а(„P, P) = (1, О, О). Открываются группы элементов И 35, 38, 39 и элементы И 46. 52. На выходе умножителя 21 формируется значение Il = а(и((а()подается на первый вход умножителя 21 через группы элементов И 38 и ИЛИ 44, на второй вход и подается с выхода регистра 25н), которое через группы элементов И 39 и ИЛИ 45 подается на выход 61. В регистр 25 записывается содержимое и регистра 25н через группы элементов И 35 и ИЛИ 43. В регистр 26 значение ((= а(и записывается на (I+1)-м такте, т.к. по управляющему сигналу аз1 = 1 элемент И 46 открыт и по переднему фронту тактового импульса, про.ходящего через элемент И 46 на синхровход регистра 26, разрешается запись в регистр "6 на (j+1}-м такте. На выход 64 выдается управляющий сигнал = 1. В четве атом режиме (а(, p, y ) = (О, 0, 0). Открываются группы элементов И 35, 41, 42 и элемент И 51. На первый вход умножителя 21 через группы элементов И 41 и ИЛИ 44 подается содержимое ((регистра 26, на второй вход — содержимое и(регистра 25, на выходе каторсго формируется значение!(и(, которое подается на второй вход вычитателя 22. На первый вход вычитателя 22 подается элемент а(, на выходе которого формируется значение а(- ll ul, которое подается через группы элементов И 42 и ИЛИ 45 на выход 61. B регистр 251 записывается содержимое и(регистра 25н, Управляющий сигнал() = О устанавливает триггер 34 в нулевое состояние, нулевой сигнал с его прямого выхода через элементы И 51 и ИЛИ 56 подается на выход 64 (у(= О). В пятом режиме (а(,,У, y ) = (*, *, 1), где обозначение принимает значение О или 1. Открываются группы элементов И 35, 40 и элемент И 51. В регистр 25 записывается содержимое регистра 25н, На выход 61 подается с выхода регистра 24 элемент а(. Управляющий сигнал у = 1 устанавливает триггер в единичное состояние, единичный сигнал с его прямого выхода через элементы И 51 и ИЛИ 56 подается на выход 64 (P = 1). Рассмотрим работу устройства (фиг.1). Элементы а» подаются на вход в моменты времени На входы 2 и 3 подаются комбинации управляющих сигналов д1 =- (и. 3) =- (1, 1), д2 = (а, P ). = (О, 1), дз =- (к./У ) = (1, О) и 1ц 50 д4 = (Q, Pl = (О, О) в виде следующей и с довательности: Д 0 gt д 2 Д н-1 г1 н он+1 yEHt-2 d H.H-1 где е= 1,ТГ1, На вход 4 постоянно подается нулевой сигнал, На выходе 15 устройства формируются u»((»)-1 элементы в моменты времени t„»(»»=((-1)Н -) -(Н М-1)Н + М-1. На фиг.2 приведены для Н == 4 и M = 2 организация входных и выходных потоков данных. Таким образам, и редлагаемае устройство па сравнению с прототипам содержит меньший объем оборудования, т,е. осуществляет LU-разложение (l-(x H)-матрицы с помощью М вычислительных л1адулей (M < Н), а прототип — с помощью Н вычислительных модулей. Формула изобретения Устройство для LU-разложения матриц, содержащее с первого по M-й операционные блоки (где Н/М вЂ” целое числа, M Н, Н вЂ” размерность разлагаемай матрицы), причем выходы группы а-га операционного Слака (где а = 1,...,M- i) подключены соответственна к информационным входам (а + 1)-ro операционного блока, первый и второй выходы а-го операционного блока подключены соответственна к первому и второму управляющим входам (а+ 1)-га oëåрационного блока, вход синхронизации устройства подключен к входам синхронизации операционных блоков с перваго поМ й, отл ича ю щее с ятем, что, с целью сокращения аппаратурных затрат, оно содержит с первого па третий элементы И, с первого по четвертый узлы задержки и группу элементов ИЛИ, причем входы коэч(фициентов разлагаемой матрицы устройства подключены соответственна к первым входам элементов ИЛИ группы, выходы которых подключены к информационным входам группы первого операционного блока, выходы группы M-ro операционного блока подключены соответственно к выходам результата устройства и соответственно к информационным входам первого узла задержки, выходы которого подключены соответственно к вторым входам элементов ИЛИ группы, с первого по третий входы режима работы устройства подключены соответственно к первым входам первого, второго и третьего элементов И, выходы которых подключены соответственно к первому, второму и третьему управляющим вха1777155 20 45 55 дам первого операционного блока, третий выход а-го операционного блока подключен к третьему управляющему входу (а+1)-ro операционного блока, первый, второй и третий выходы M-ro операционного блока подключены соответственно к информационным входам второго, третьего и четвертого узлов задержки, выходы которых подключены соответственно к вторым входам первого, второго и третьего элементов И, вход синхронизации устройства подключен к входам синхронизации первого, второго, третьего и четвертого узлов задержки, при этом каждый операционный блок содержит узел вычисления обратной величины, вычитатель, умножитель, два регистра, шесть триггеров, три узла задержки, с первой по восьмую группы элементов И, с первого по седьмой элементы И, с первой по третью группы элементов ИЛИ, с первого по пятый элементы ИЛИ, с первого по третий элементы НЕ, причем в каждом операционном блоке информационные входы группы операционного блока подключены соответственно к информационным входам первого регистра, выходы которого подключены к первым входам элементов И первой, второй и третьей групп, к информационным входам nepsoA группы вычитателя и к информационным входам узла вычисления обратнаи величины, выходы которого подключены к первым входам элементов И четвертой группы, выходы которых подключены соответственно к первым входам элементов ИЛИ первой группы, выходы которых подключены к информационным входам первого элемента задержки, выходы которого подключены соответственно к информационным входам первой группы умножителя, выходы которого подключены соответственно к первым входам элементов И шестой группы, соответственно к информационным входам второй группы вычитателя и соответственно к информационным входам второго регистра, выходы которого подключены соответственно к первым входам элементов И седьмой группы, выходы которых подключены соответственно к первым входам элементов ИЛИ второй группы, выходы которых подключены соответственна к информационным входам второй группы умножителя, выходы вычитателя подключены соответственно к первым входам элементов И восьмой группы, выходы которых подключены соответственно к первым входам элементов ИЛИ третьей группы, выходы которых подключены соответственно к выкодам группы операционного блока, первый управляющий вход которого подключен к входу первого элемента НЕ, к информационным входам первого и второго триггеров и к первому входу первого элемента ИЛИ, выход которого подключен к вторым входам элементов И пятой группы, выходы которого подключены соответственно к вторым входам элементов ИЛИ первой группы, выход первого триггера подключен к первым входам второго и третьего элементов ИЛИ, выход второго элемента ИЛИ подключен к вторым входам элементов И второй группы, выходы которых подключены соответственно к вторым входам элементов ИЛИ третьей группы, выход третьего элемента ИЛИ подключен к первому входу первого элемента И, выход которого подключен к первому входу четвертого элемента ИЛИ, выход которого подключен к первому выходу операционного блока, второй управляющий вход которого подключен к входу второго элемента НЕ, к информационному входу второго узла задержки и к первым входам второго и третьего элементов И, выход второго элемента И подключен к информационному входу третьего триггера, выход которого подключен к вторым входам элементов И четвертой группы, к второму входу второго элемента ИЛИ и к первому входу пятого элемента ИЛИ, выход которого подключен к первому входу четвертого элемента И, выход которого подключен к второму входу четвертого элемента И, выход которого подключен к второму входу четвертого элемента ИЛИ. прямой и инверсный выходы второго триггера подключены соответственно к вторым входам первого и четвертого элементов И, выход третьего элемента И подключен к информационному входу четвертого триггера и к вторым входам элементов И первой группы, выходы которых подключены соответственно к третьим входам элементов ИЛИ первой группы, выход четвертого триггера подключен к третьему входу второго weмента ИЛИ и к второму входу пятого элемента ИЛИ, выход первого элемента НЕ подключен к вторым входам второго и третьего элементов И и к первым входам пятого и шестого элементов И, выход пятого элемента И подключен к второму входу первого элемента ИЛИ и к информационному входу пятого триггера, выход которого подключен к вторым входам элементов И третьей группы, к третьему входу пятого элемента ИЛИ, к первому входу седьмого элемента И и вторым входам элементов И шестой группы, выходы которых подключе- ны соответственно к третьим входам элементов ИЛИ третьей группы, выход второго элемента НЕ подключен к вторым входам пятого и шестого элементов И, выход шес1777155 10 того элемента И подключен к третьему входу первого элемента ИЛИ и к информационному входу шестого триггера. выход которого подключен к вторым входам элементов И седьмой и восьмой групп и к второму входу третьего элемента ИЛИ. третий управляющий вход операционного блока подключен к входу третьего элемента НЕ. к третьим входам второго и пятого элементов И и к информационному входу третьего узла задержки, выход которого подключен к второму выходу операционного блока, третий выход которого подключеч к Выходу второ ".: узла задержки, выход тра ьего элемента НЕ подключен к третьим входам третьего и шестого элементов И, вход синхронизации 5 операционного блока подключен к входам синхронизации первого, второго и третьего узлов задержки и к входам "Запись-чтение" первого — шестого триггеров и первого регистра и к второму входу седьмого элемента 10 И, выход которого подключен к входу "Запись-чтение" второго регистра. 1777155 17771",5 BLL2. 3 Составитель В. Якуш Техред М.Моргентал Корректор Н. Ревская Редактор Г. Бельская Производственно-издательский комбинат Патент", r. Ужгород. ул.Гагарина, 101 Заказ 4123 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., 4/5
