Однородная вычислительная структура для @ разложения матриц

 

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

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК

„.ЯО„„1249531

А1 (50 4 С 06 Г 15/32

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3737219/24-24 (22) 16..05.84 (46) 07.08,86. Бюл. У 29 (71) Киевский ордена Трудового Красного Знамени институт инженеров гражданской авиации им. 60-летия СССР (72) Г.Е.Пухов, Л.Я.Нагорный, А.И.Стасюк и Ф.Е.Лисник (53) 68 1.325(088.8) (56) Бахвалов Н,С. Численные методы.

М.: Наука, 1975, с. 324-330.

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

Ф 647687, кл. G 06 F 15/32, 1979.

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

N 648987, кл. G 06 F 15/32, 1979.

: (54) ОДНОРОДНАЯ ВЫЧИСЛИТЕЛЬНАЯ СТРУКТУРА ДЛЯ LU-РАЗЛОЖЕНИЯ МАТРИЦ (57) Изобретение относится к вычислительной техйике и может быть использовано автономно или в комплексе с ЦВМ для разложения квадратной матрицы на две треугольные, Цель изобретения — увеличение быстродействия.

Это достигается тем, что устройство содержит (и-1) матриц из n вычислительных ячеек, реализующих операции вида a+fu и а/4. Разложение исходной матрицы в устройстве осуществляется на основе рекуррентных соотношений.

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

3 12495

Изобретение относится к вычислительной технике и может быть испольтреугольные, Цель изобретения — увеличение быстродействия.

На фиг. 1 показана схема однородной вычислительной структуры для LU- !О разложения матриц для случая, когда

n=5; на фиг. 2 — схема вычислительной ячейки, осуществляющей операцию вида

a+lu; на фиг. 3 — схема вычислительной ячейки, осуществляющей операцию t5 деления.

Однородная вычислительная структура для LU-разложения матриц содержит матриц, состоящих из вычислительных ячеек 1 k (k=1,2,3...,,n-1), вход- 20 ную шину 2Ц (i=1,2,3,...,n, j=1,2, З,...,n-1) и выходную шину 3ij, умноj4

j=3

j=2

i=2

1. =4

i=5

40 четырех слоев. В первом слое производятся вычисления: й2 й1 " 2 зовано автономно или в комплексе с цифровой вычислительной машиной для разложения квадратной матрицы на две

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

31 3 житель 4, сумматор 5, одноразрядный сумматор 6, сумматор 7 по модулю два.

Работа устройства для разложения прямоугольной неособенной матрицы А в виде произведения левой L и правой U треугольных матриц,,т.е.

A=LU, происходит на основе рекуррентных соотношений вида:

=а Е4 ц (i> j); и11

i=1 т, j=1,m, где а,„— элементы матрицы А; г,,„- элементы матрицы L

u;„- элементы матрицы U.

В развернутом виде при m=5 элементы матриц L u U представляются как:

1249531

Во втором слое производятся вычисления: (К+1) при f =1

Х=

2, при f =1

<к) 5сс 45

30 Ф =0

Е =1

v (3) Z =1

Е(14)=0. 1 E = 1

0010 х=

1010 х =0

0101

1011

0101 при K=3 при К=4

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

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

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

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

ZWX=0

v 1 2 1 2 2п где Х=Х, Х,...,Х, Z=Z Z Z ч 1 2 >и

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

2 1

J Э

3 г ч < 3 з г

Ъ

Процесс определения К-го с К=1 ю Ы

2, и) разряда искомого вектора реализуется на основании зависимости вида: — разрядная матрица, представляющая собой изоб- 50 ражение делителя у при n=3. где f ) — значение переноса из (К .1) (К+1) старшего разряда вектора Z ,"

<к) — величина принимающая значения:

Ь

-К <к)

-2, при f =О.

Ч <1) V <1) -1

При )с=1, Z =Z, E. =Z НапРимеР, пусть "3 =О, 6875, Z=04296875, тогда в разрядной форме имеем

1=1011, Z=„01101110

При К=1 Z =0 1 1 0 1 при К=2 „ Z =0 0 1 0 1

ЗЕ =10101

ЪЕ =10101

Z =00000 x3=1

Z =10101 х"=0

Таким образом х =1010, что соответствует = 0,625.

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

В исходном состоянии на входные пины 2„„, .. °, 21, 2,..., 2 „, 21

245) 2 ° подаются соответственно значения элементов а,...,а, а21,...,а

11 15 21 25

Эа35Э 41 1 14595<) 1а55 исходной матрицы, после чего в схе)<е протекает переходной процесс.

После окончания переходного процесса в вычислительных ячейках 1, пер124<1531

1О

20 вой строки и первого столбца первой матрицы по выражению образуются значения элементов 1,„,...,П„,, („ первой строки и столбца искомых элементов матриц Ы1, которые поступают на выходные шины 3„,...,3„.

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

9U„,; ° j -,5 о орые поступают на вторые входы соответст-. вующих ячеек 1 второй матрицы. На выходах ячеек 1, первой строки и,первого столбца второй матрицы образуются искомые значения U, U, U, 5 и поступающие на выход3„„ соответственно.

На выходах ячеек 1, первого и второго столбцов, второй, третьей и четвертой строк второй матрицы обра<т1 <11 зуются значения U,„, U, U, „.

У

lо) и,„,, (...,, („, которые подаются на первые входы соответствующих ячеек 1, третьей матрицы.

На выходах ячеек 1, первой строки и первого столбца ".ðåòüåé матрицы образуются, искомые значения U,,U и . „,, „, третьей строки и столбца элементов матриц Ь и U, которые поступают на выходные шины 3,„, 3,. и 3... 3„, соответственно. На всех остальных ячейках 1, третьей матрицы образуются промежуточные значения (3) <3>

U < „, к от орые. поступают на вт орые входы ячеек 1,, четвертой матрицы

Наконец, на выходах двух последних ячеек. 1, четвертой матрицы образуются искомые значения U u элементов матриц Ь и U которые поступают на выходные шины 3„ и 3,. соответственно. Таким образом, за время, равное,цлительности переходного процесса в схеме, на выходных шинах 3,Д устройства образуются искомые значения элементов LU матриц.

Однородная вычислительная структура для LU — разложения матриц является однородной и глобально параллельной. Время вычисления элементов Ф,. и U„, на ней равно задержке сигнала между входом и выходом элементов схемы. Процесс вычисления элементов 1,, U представлен в виде слоев с пенью распараллеливания вычислений д<. уровня двух типов

55 операций: a+fU и деления. Это позволяет строить вычислительную структуру из существующих интегральных схем ограниченной номенклатуры или в виде отдельной СБИС. Благодаря организации логической структуры вычислителя в виде однородных слоев, она является параллельной (комбинационной), вычислительный процесс в ней начинается с момента подачи исходных данных на входные шины, результат вычислений снимается из выходных шин после окончания переходного процесса в схеме, который длится, например, 4 мкс, если каждая из идентичных ячеек 1 выполнена на базе одного типа интегральных схем К155ИПЗ серии 155 при п=10 и m=16.

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

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

90 (1+1)-й группы, выход переноса р -го

З5 однообразного сумматора V-й группы подключен к третьему информационному входу(Р + 1) — го группы. нык ячеек р-й строки g-ro столбца (р=2,3 ° ° °,,n>1-k, q=2,3,...,n-k)

k-матрицы подключены к вторым информационным входам соответствующих вычислительных ячеек (р-1)-й строки (q — 1) — го столбца (k+1) é матрицы, при этом вычислительная ячейка р-й. строки q-го столбца k-й матрицы содержит умножитель и сумматор, первый и второй информационные входы вычислительной ячейки р-й строки q-ro столбца k-матрицы являются информационными входами первых операндов умножителя и сумматора соответственно, а третий информационный вход вычислительной ячейки р-й строки g-го столбца k-й матрицы — информационным входом второго операнда умножителя, выход которого подключен к информационному входу второго операнда сумматора, выход которого является выходом вычислительной ячейки„ вычислительная ячейка первой строки

k-й матрицы содержит m групп одноразрядных сумматоров по (m+1) сумматору в каждой из m групп сумматоров по модулю два по m сумматоров в каждой, где m — разрядность представления информации, первый информационный вход

r-го разряда (r=1,2,...,m) делителя ячейки первой строки k-й матрицы подключен к первым информационным входам

r-x сумматоров по модулю два с первой по m-ю группы, вторые информационные входы сумматоров IIO модулю два . первой группы, первый информационный вход, первого одноразрядного сумматора первой группы и третий информациoHHb1H вход (ш+1) -го одноразрядного сумматора первой группы подключены к шике единичного сигнала устройства, информационные выходы r-х сумматоров по модулю два Ч=й группы (V= 1,2,...,m) подключены к первым информационным входам (г+1)-х одноразрядных сумматоров V-й группы, второй информационный вход r-ro разряда делимого ячейки первой строки k-й матрицы подключен к вторым информационным входам r-ro одноразрядного сумматора первой группы, а второй информационный вход f-ro разряда делимого (f=r+1...,,2r) ячейки первой строки k-k матрицы подключен к вторым информационным входам (m+1)-х одноразрядных сумматоров

20» г-й группы, выходы переноса первых одноразрядных сумматоров 9 -й группы (4 =1,...,m-1) подключены к первому информационному входу первого одноразрядного сумматора, к третьему информационному входу (в+1)-го одноразрядного сумматора, к вторым информационным входам сумматоров по модулю два (I9+9)-й группы и соответственно к выходу r-гр разряда результата, информационный выход p -ro (У =2 ...,, в+1) одноразрядного сумматора 1 -й группы подключен к второму информационному входу (P-1)-ro сумматора одноразрядного сумматора V-й — 3. >31

1249531

Со с та вит ель В. Смирнов

Редактор С. Патрушева Техред О. Гортвай Корректор О. Луговая

Заказ 4326/50 7йраж б71 Подписное

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

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

Производственно-полиграфическое предприятие, r,Óæãîðîä, ул.Проектная, 4