Однородная вычислительная структура для @ разложения матриц Советский патент 1986 года по МПК G06F17/16 

1249531 2

Изобретение относится к вычисли- житель 4, сумматор 5, одноразрядный тельной технике и может быть исполь- сумматор 6, сумматор 7 по модулю два. зёвано автономно или в комплексеРабота устройства для разложения

с цифровой вычислительной машиной для прямоугольной неособенной матрицы А разложения квадратной матрицы на две 5 s виде произведения левой L и пра- треугольные.вой U треугольных матриц, т.е.

Цель изобретения - увеличениеA LU,

быстродействия. происходит на основе рекуррентных

На фиг. 1 показана схема однород- соотношений вида: ной вычислительной структуры для LU- 10 . j-t разложения матриц для случая, когда на фиг. 2 - схема вычислительной ячейки, осуществляющей операцию вида a+lu; на фиг. 3 - схема вычислительной ячейки, осуществляющей операцию ts деления.

Однородная вычислительная структу- ра для LU-разложения матриц содержит где - элементы матрицы А; U матриц, состоящих из вычислитель- X,-j - элементы матрицы L; ных ячеек 1 k ( ,2,3 ,. . . ,п-1) , вход-20 ij элементы матрицы U. ную шину 2ij (,2,3,...,п, ,2, В развернутом виде при элемен- 3,.,.,п-1) и выходную шину 3ij, умно- ты матриц L и U представляются как:

и (j ,5 s. ; (

i-i

ij - ,. ,

4, -г ; ();

-i 1

bra j 1,m.

j l

j 3

Организация параллельного вычисления элементов матрицы LU может быть представлена в виде следующих

тношений вида: . j-t

- элементы матрицы А; X,-j - элементы матрицы L; ij элементы матрицы U. В развернутом виде при матриц L и U представляются

и (j ,5 s. ; (

i-i

ij - ,. ,

4, -г ; ();

-i 1

bra j 1,m.

j-4

40 четырех слоев. В первом слое производятся вычисления:

В третьем слое производятся еле- дуюпще вычисленияjj

в четвертом слое производятся следующие вычисления:

Реализация вычисления в слоях производится путем параллельного осуществления операций умножения с алгебраическим суммированием и деления.

При реализации операции деления частное X деления делимого Z на дели- тель Y реализует по выражению , представленному в разрядной форме

V V 1 у

,

V17l-ivtl2ц

где , Х,...,Х, ,Z,...Z,

V 1 22(1

,0,...,0,

р азрядные векторы, представляющие собой разрядные изображения X,Z и соответственно:

разрядная матрица, представляющая собой изоб- 50 ражение делителя у при .

Процесс определения К-го (.К-1, 2,...,п) разряда искомого вектора .реализуется на основании зависимости вида:

j

(К+1)

при f

О, при 0, где - значение переноса из

старшего .разряда вектора Z

(Ktl)

определяемого по выражению Z

,f

;(к)

(К)

. - величина принимающая значения :

ь-I к

1

,/к|

,„-К-(К)

2 , при г

е

5

.(К)

при f 0.

, Z . Например,

0

1-2 .

V (1) V

При , Z Z

пусть У 0,6875,Z 04296875, -тогда в разрядной форме имеем , Z 01101110

М )

При 0 1101

при z 0 010 1

е , 10101

л /о

3 10101

5

при при

0

ie

5

0

,.j „ О О 1 О х 1 Z 1 1010

V (i)

Z 10101 0000 01011

10101

0000 x- 1

V f SI

Z 1 0101 x 0 Таким образом x 1010, что соответствует 0,625.

Однородная вычислительная система для LU-разложения матриц работает следующим образом.

В исходном состоянии на входные шины 2 ,..., , 2,2,,,

977777

31 V 3S 1,1 ЦВ 51 ЪВ

подаются соответственно значения элементов а,, ,....,а,5 , a,j, а ,

3 11 51 55

ИСХОДНОЙ матрицы, после чего в схеме протекает переходной процесс . , После окончания переходного процесса в вычислительных ячейках 1, пер15OIT строки и первого столбца первой матр1- цы по выражению образуются значения элементов U, ,. . , ,U,,,. , ,,, ,. . , i- перво й строки и столбца искомых элементов матриц LU, которые поступают на выходные шины 3.,

11

соответственно. Далее

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

, г (, т

и,, ,... ,Uj, ; lj, ,., . .Ijs которые поступают на вторые входы соответствующих ячеек 1 второй матрицы. На выходах ячеек 1 первой строки и,первого столбца второй матрицы образуются искомые значения U,., ,U,.,,, ,U,,5 и f.,3 п ь . поступающие на выходные шины 3,, , 3,, , ЗУ у и Ззз J 3;, , , 3,

ii

7, 9 /

соответственно.

На выходах ячеек 1,, первого и второго столбцов, второй, третьей и четвертой строк второй матрицы обра,.(71 .тСг.) т.СЗ)

зуются значения и.. , U , и,,.

„171

Чи t-:, -ss которые подаются

на nejjBiiie входы соответствующих ячеек 1з третьей матрицы.

На выходах ячеек 1 первой строки

и первого столбца третьей матрицы образуются .искомые значения U, ,U,,5 и (,1, ) , третьей строки и столбца элементов матриц L и U, которые поступают на выходные шины 3, , 3,,g и 3,, , 3,, соответственно. На всех остальных ячейках 1 третьей матрицы образуются промежуточные значения , (V которые. )1оступают на вторые входы ячеек Ь четвертой матриды Наконец, на выходах двух последних ячеек 1,, четвертой матрицы образуются искомые значения Цд и -Sj элементов матриц L и U, которые по- ступают на выходные шины и 3, соответственно. Таким образом, за время, равное длительности переходного процесса в схеме, на выходных шинах 3,-j устройства образуются искомые значения элементов LU матриц. Однородная вычислительная структура для LU-разложения матриц является однородной и глобально параллельной. Время вычисления элемен- тов .. и и, I на ней равно задержке сигнала между входом и выходом элементов схемы. Процесс вычисления

элементов

f

представлен в виде слоев с гг.ельк1 распараллеливания вычислений до уровня двух типов

операций: a+fu и деления. Это позволяет строить вычислительную структу- ру из существующих интегральных

схем ограниченной номенклатуры или в виде отдельной СБИС. Благодаря организации логической структуры вычислителя в виде однородных слоев, она является параллельной (комбинационной), вычислительный процесс в ней,начинается с момента подачи исходных данных на входные шины, результат вычислений снимается из выходных шин после окончания переходного процесса в схеме, которьй длится, например, 4 мкс, если каждая из идентичных ячеек 1 выполнена на базе одного типа интегральных схем К155ИПЗ серии 155 при

и т 16 .

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

Однородная вычислительная структура для LU-разложения матриц, содержащая первую матрицу из п вычислительных ячеек, отличающаяся тем, что, с целью увеличения быстродействия, в устройство введены с второй по (п-1)-ю матрицы вычислительных -ячеек, при этом k-H матрица ,2,„..п-1) содержит (n+1-k) строк и (n-k) столбцов, первые информационные входы вычислительных ячеек i-й строки (,2,...n) первой матрицы подключены соответственно к информационным входам элементов первого столбца i-й строки разлагаемой матрицы устройства, вторые информационные входы вычислительных ячеек i-й строки j-ro столца (,2,.,.,п-1) матрицы вычислительных ячеек подключены соответственно к входам записи элементов разлагаемой матрицы устройства, выходы вычислительных ячеек первой строки f-.ro столбца (, 2,.,.,n-k) k-й .матрицы подключены к выходам считывания элементов k-й строки и-матрицы результата и к третьим информационным входам вычисли- тепьных ячеек -го столбца k-й матрицы, выходы вычислительных ячеек первого столбца S-й строки (,3,..., n-k+1) k-й матрицы подключены к выходам считывания элементов k-ro столбца L-матрицы матрицы результата и к первым информационным входам вычислительных ячеек (3-1)-й строки () й матрицы, выходы вычислитель7 12495318

ных ячеек р-й строки q-ro столбцаонный вход (т+1)-го одноразрядного (, 3. . . ,, ,n-f 1-k, ,3 , . .. ,n-k)сумматора первой группы подключены k-матрицы подключены к вторым инфор-к шине единичного сигнала устройст- мационным входам соответствующих вы- ва, информационные выходы г-х сумма- числительных ячеек (р-1)-й строкиторов по модулю два группы (q-1)-го столбца (k + 1)-й матрицы,(,2,...,т) подключены к первым при этом вычислительная ячейка р-й.информационным входам (г+1)-х одно- строки q-ro столбца k-й матрицы со-разрядных сумматоров V-й группы, держит умножитель и сумматор, первыйJQ второй информационный вход г-го и второй информационные входы вычис-. разряда делимого ячейки первой стро- лительной ячейки р-й строки q-ro ки k-й матрицы подключен к вторым столбца k-матрицы являются информа-информационным входам г-го однораз- ционными входами первых операндовряднопо сумматора первой группы, а умножителя и сумматора соответствен-tS второй информационньй вход f-ro но, а третий информационньй вход вы-разряда делимого (, .., ,2г) ячей- числительной ячейки р-й строки q-roки первой строки k-й. матрицы подклюет олбца k-й матрицы - информацион-чен к вторым информационным входам ным входом второго операнда умножите-(in+1)-x одноразрядных сумматоров ля, выход которого подключен к инфор-20 г-и группы, выходы переноса пербых мационному входу второго операндаодноразрядных сумматоров J -и группы сумматора, выход которого является(N| I ,... ,т-1) подключены к первому выходом вычислительной ячейки, вы- информационному входу первого одно- числительная ячейка первой строкиразрядного сумматора, к третьему ин- k-й матрицы содержит ш групп однораз-25L формационному входу (т+1)-го однорядных сумматоров по (т+1) сумматоруразрядного сумматора, к вторым инфор- в каждой из m групп сумматоров помационным входам сумматоров по моду- модулю два по m сумматоров в каждой,лю два (у + О-й группы и соответствен- где m - разрядность представления ин-но к выходу г-гр разряда результата, формации, первьй информационный входЗО информационный выход (-го ,.,., г-го разряда (,2,.. . ,т) делителят+1) одноразрядного сумматора ) -и ячейки первой строки k-й матрицы под-группы подключен к второму информа- ключен к первым информационным входамционному входу (Р-1)-го сумматора г-х сумматоров по модулю два с пер-() + 1)-и группы, выход переноса/ч-го вой по т-ю группы, вторые информаци- s однообразного сумматора V-й гру- онные входы сумматоров по модулю дваппы подключен к третьему ин- первой группы, первьй информационньйформационному в ходу fj 4-О - го вход, первого одноразрядного суммато-одноразрядного сумматора V-й ра первой группы и третий информаци-группы.

Фиь. {

Нзобретение относится к вычислительной техйике и может быть испдль- зовано автономно или в комплексе с ЦВМ для разложения квадратной матрицы на две треугольные. Цель изобретения - увеличение быстродействия. Это достигается тем, что устройство содержит (п-1) матриц кз п вычислительных ячеек, реализуюпр1х операции вида и a/f. Разложение исходной матрицы в устройстве осуществляется на основе рекур рентных соотношений. Увеличение быстродействия достигается за счет параллельной организации логической структуры при реализации рекуррентных соотношений. Время форМи- ЬЬвания решения в устройстве определяется временем переходного процесса в схеме. 3 ил, 6 табл. I (Л 4 ;о ел со

Фиг.2.

Фиг.З