Однородная вычислительная структура

 

Изобретение относится к области вычислительной техники и может быть исЛользовано для оперативного разложения квадратной симметричной матрицы на две треугольные, решения систем алгебраических уравнений, вычисления определителей матриц. Цель изобретения - увеличение быстродействия . Устройство содержит п треугольных матриц вычислительных ячеек. Однофазная структура имеет параллельную организацию5 благодаря чему время решения равно задержке сигнала между входом и выходом.структуры, 4 ил. § (Л

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

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

РЕСПУБЛИК (51) 4 G 06 F 15/324

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

ПО ДЕЛАМ ИЗОбРЕТЕНИЙ И ОТКРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ ) " .!

tj

1 В ч с

Elf

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3857437/24-24(22) 20. 02, 85 (46) 15.08.86, Бюл, К 30 (71) Институт проблем моделирования в энергетике АН.УССР и Киевский ордена Трудового Красного Знамени институт инженеров гражданской авиации им. 60-летия СССР (72} Л.Я.Нагорный, А.И.Стасюк, Ф.Е.Лнсник и Н.АНолевой (53} 681. 32 (088. 8) (56) Авторское свидетельство СССР

N 648987, кл. G 06 F 15 /324,1976, Авторское свидетельство СССР

1". 647687, кл. G 06 F 15/324, 1974, Пухов Г.Е., Евдокимов В,Ф., Синьков N.Â. Разрядно аналоговые вычислительные системы. М.: Сов. радио, 1978.

ÄÄSUÄÄ 1251104 А 1 (54) ОПНОРОДНАЯ ВИЧИСЛИТЕЛЬНАЯ СТРУК-.

ТУРА (57) Изобретение относится к области вычислительной техники и может быть использовано для оперативного разложения квадратной симметричной матрицы на две треугольные, решения систем алгебраических уравнений, вычисления определитеЛей матриц. Цель изобретения — увеличение быстродействия. Устройство содержит и треугольных матриц вычислительных ячеек.

ОдноАазная структура имеет параллельную организацию, благодаря чему время решения равно задержке сигнала между входом и выходом структуры, 4 ил.

II 1251

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

Цель изобретения — увеличение быстродействия.

На фиг. 1 приведена схема одно в I0 родной вычислительной структуры для случая, когда число и треугольных матриц вычислительных ячеек равно четырем (n=4),1 на фиг. 2 — схема вычислительных ячеек, начиная с второй строки каждой треугольной матрицы устройства, на фиг. 3 — введена схема вычислительных ячеек первой строки, начиная с второго столбца каждой треугольной матрицы, представляющие >0 собой параллельный делитель, на фиг. 4 — схема вычислительных ячеек первой строки первого столбца каждой треугольной матрицы устройства, представляющие собой параллельный корнеизвлекатель.

Однородная вычислительная структура содержит и треугольных матриц вычислительных ячеек, каждая треугольная матрица содержит вычисли- 30 тельную ячейку 1, представляющую собой параллельный корнеизвлекатель, треугольные матрицы, начиная с первой по (п-l)-ю, содержат вычислительную ячейку 2, представляющую собой параллельный делитель, вычислительные ячейки 3, информационные входы 4, выходы 5 результата устройства, параллельный умножитель 6, параллельный сумматор 7, одноразрядные сумматоры 8, сумматоры 9 по модулю два, выходы 10 параллельного делителя, вторые ll и первые 12 входы параллельного делителя, элементы НЕ 13, элемент ИЛИ 14, выходы 15 корнеиэ- 45 влекателя, входы 16 корнеизвлекателя.

Работа однородной вычислительной стРуктуры для вычисления элементов

50 нижней треугольной матрицы L„ формируемой из элементов симметричной матрицы А как A=LL, где L — транс% понированная по отношению к L матрица, осуществляется следующим образом, 55

Вычисление элементов матрицы 1 реализуется методом квадратного корI04 ня по следующим рекуррентным выражениям

=)а 1 а, 11 Ii 1 Е 1

Н (8 ) I) °

1 1-1 2

Кс1

° J

15 (I(i п, ) сs), где 1(6 — элементы матрицы L; а„. — элементы матрицы A.

Лля п=4 выражения 1», 11, 1;;, 1; в развернутом виде np)4 i=-1,2,3,4 будут иметь вид а1э

l — °

1Э

II ат

12 1 !

1 а<4 а1 -«1121)Э

122

i=2 а 21 112 1-14

122

23 аэ1 113114+12э124 °

) 1ээ

i=3

i=4

l4 1 (iI,, r1) а-11 =1 а-1 с I2 22 а2э IZ I3 23 1

24 12 14 24 Э ЭЭ IЭ 1Э 33 (1) (1) . аэ4-1, 1» 4= 1; а44-1141 4 1441

Вторая группа уравнений имеет вид

22 22 23 1 24

22 22

ЭЭ 23 23» 34 Э4 23 24 (2) (1)

44 4+ 24 24

Третья и четвертая группы уравнений имеют вид (2) 1 (2)

1 1 1 — °

Э4 зэ ээ 34

33 (э) ()

44 44 Э4 34

В соответствии с развернутым представлением при i=1 2,3,4, организацию параллельного вычисления элементов 1;зможно представить в виде и групп уравнений. При и 4 первая группа уравнений имеет вид

a, а)э

1 =„a 1. = -(3и "11 2 1 13

i1 A

)251 и соответственно

Г ()

1 =1144 .

104 4 мости вида Х.=- Й определяется на основании выражения

} 1 . 2

Х-Y }} Y при n=3 °

Процесс определения k-го (k=!

2,...,n) разряда искомого вектора

Х реализуется на основании зависимости вида 25

4 (»+1} х=

Г 1 при f =1; (»})

1 О при f =О, (»4}) где f -- значение переноса из старmего разряда вектора Zv(» 1, ЗО определяемого по выражению

1) » (») (»1 — величина,. принимающая значение

-» 6) а 2 при К =.1; (x)

2 при f =О.

В качестве примера рассмотрим вычисление выражения Z/Y, где Y-=

=0,96875, Z=0,4296875. Запишем 7, Е, Х в разрядной форме

V ч М

7 1011; Z=01111110 Х=1010;

V() vg)

1с=1 vZ 01101; k=2 „Z =00101;

7()=Р0010;

Z =1)010;

1 г

V(4) Х } V(4) x=С} к=3ÄZ =10101; k--4ÄZ. =00000;

7Е()=1 0101, Z =00000; Z -10101;

» х=» х

4.

Таким образом, ре}ьение равно

X=1010 . (Х=О, 625) . 55

Параллельный корнеизвлекатель работает следующим образом. Старший

1 V разряд Х искомого вектора Х зависи35

Группы уравнений являются основой для определения элементов 1ц с помо5 щью операций деления и извлечения корня, Частное Х от деления делимого Z на делитель У реализуется по выраже;. . )о нию Е-YX--0 ппедставленному в разряд}1 1/ 1 ной форме„Е-YX=q, где Х=Х...4

Z=F....E; 04...0 — разрядные векторы, представляющие собой разрядные изображения Х, Z и О соответственно, } у

7= у у у — разрядная матрица, c} L у у представляющая собой э у изображение делителя 20

Далее каждый носледуюший разряд

Х=-I,2,...,и искомого вектора Х определяется по выражению при f -I, (1 1)

0 при f =О, ((s}) где f — значение переноса из старшего разряда вектора Y(", определяемого на основании вь}ражения

Ч(,„) "(1) ) Ч (, ) )

1 (i) где K — величина, принимающая значения л!(2,при f -1; (i1

-2 при f =О, ° "(1) ", (11

X"=(Хd ... Хх 1)

В качестве примера рассмотрим вы2 числение выражения Y, где 7=Х =

=,0,4306640625. В разрядной форме

Y=(0110111001) и X=(10101) старший разряд Х=О} 1=1, V (}) V2 --) Ч4 Е

7 =(0110); 7 =(10111); Y =(001010) (Х" /6(=(101n»);

7 (1111) ; 7 =(00010); 7(=(1101 01), 1 Ф

2 з 4 х =() x-={ х=0 (4)

1, Y„= (1010101)

„X")Û = (0» 011);

Y =(0000000) (Х=0,65625).

1 х=(Однородная вычислительная структура работает следующим образом, На инфор,мационные входы 4„,4„,4„,4,„ячеек 1„2„пер-, вой строки первой матрицы подаются4соответственно значения а„, а„, а а„,на унформационные входы 4,4, 4 ячеек 3

АР ЬР 24

Ф второй строки первой матрицы подаются исходные значения а, a,a,äàëeå на вхо22 2} 24 ды 4,4 . ячеек З,третьей строки первой матрйцы подаются значения а а,на вход я 34

4 „ячейки 34 последней строки первой матрицы подается значение а После зтоМ

ro в схеме устройства протекает переходной процесс, по окончании которого на выходе ячейки I(перьой строки первой матрицы образуется значение 1}} элемента искомой матри125!!04 цы Ь, которое поступает на выход

5» и на входы ячеек 2» первой стр эки первой матрицы. В ячейках 2» первой строки первой матрицы образуются значения элементов первой строки I«, 1»> искомой матрицы 1-, которые поступают соответственно на выходы 5,, 51,9 5 <, на входь1 ячеек 3, ст лбца первой матрицы и входы ячеек 3, вто- !О рой,третьей и четвертой строк первой матрицы. В ячейках 3, второй,третьей и четвертой строк первой матри цы образуются значения: 12, Р 12"3 э

1 < (вторая стРока) 1<, 1" (тРетья I5 (2 строка), « (че т верт ая строка) . (,2 (|) (1)

Значения 1, 1 », » поступают н а входы ячеек !, 2 первой строки в т о2 (»2 (1) рой матрицы. Значения 1,, 1 и (tI э9

I << поступают на входы ячеек З вто- 20 рой строки и 3 третьей строки второй матрипь». На выходах ячеек 1,, 2 первой строки второй матрицы обт разуются значения элементов 1

1 второй строки искомой матрицы, 25 которые поступают на выходы 5, 3,., 5 и на соответствующие входы ячеек

3 второй и третьей строк второй матрицы. На выходах ячеек 3 второй и третьей строк второй матрицы образу- g0 (2 (г) ются значения 1 », 1 (вторая стро-ка) и 1 » (третья строка). Значения (22

1, I поступают на входы ячеек (и (.)"

1, 2 первой строки третьей матри(22 ць Ф а значение 144 — на вход ячейки 35

Зз второй строки третьей матрицы.

На выходах ячеек 1, 2 первой строки третьей матрицы образуются элементы 1, 1 + третьей строки искомой матрицы, которые подаются на выходы »0

5, 5 и на соответствующие входы ячеек 3 последующих строк третьей матрицы. В ячейке 3 второй строки т»)етьей матрицы формируется значение

О)

14, которое подается на вход ячейки

1 первой строки четвертой матриць», в которой образуется значение 1 последней строки матрицы L которое поступает на выход 34 . Управление работой однородйой вычислительной структуры осуществляется с помощью синхросигналов, поступающих на, все вычислительные ячейки.

Однородная вычислительная структура имеет параллельную организацию, благодаря чему время решения равно задержке сигнала между входом и выходом структуры, т,е. вычисле— ние элементов матрицы 1. и соответст

% венно представления A=LL происходит за время переходного процесса в схеме. Это позволяет использовать однородную вычислительную структуру в качестве спецпроцессора для организации вычислительного процесса в реальном масштабе времени.

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

Однородная вычислительная структура, содержащая первую верхнюю треугольную матрицу иэ п(п+1)/2 вычислительных ячеек, о т л и ч а ю— щ а я с я тем, что, с целью BQBblIIIe ния быстродействия, в нее введены с второй no n-ю треугольные матрицы вычислительных ячеек, первые информационные входы вычислительных ячеек первой треугольной матрицы подключены к информационным входам устройства, первые информационные вхо" ды вычислительных ячеек i-й строки

j-го столбца 1 -й треугольной матри" цы (m=2»n; j=lð295 ° ° 9п-ш i+2) подключены к выходам вычислительной ячейки i-й строки j-го столбца (m-1)-й треугольной матрицы, выход вычислительной ячейки первой строки первого столбца r-й (r=l,...„n-l) треугольной матрицы подключен к вто" рым информационным входам вычислительных ячеек первой строки с второго по (n-r+I)-й столбец г-й треугольной матрицы, выходы вычислительных ячеек первой строки 1"го (1=

=2,...,n-k) столбца k-й треугольной матрицы подключены к вторым информационным входам вычислительных ячеек столбцов с (1-!)-го по первый соответственно строк с второй по (n-k)-ю и к вторым ийформационнь»м входам ячеек 1-й строки k-треугольной матрицы, выход вычислительной ячейки (n-k+1)-ro столбца первой строки

k-й треугольной матрицы подключен к третьим информационным входам вычислительных ячеек (и-k-i+2)-го столбца с второй по (n-k)-ю строк и к второму информационному входу вычислительной ячейки первого столбца последней строки k-й треугольной матрицы, выходы вычислительных ячеек первых строк треугольных матриц подключены к выходам результата уст. ройства, при этом вычислительные ячейки, начиная с второй строки каж1251

10 дой треугольной, матрицы, содержат сумматор и умножитель, первый и второй входы умножителя подключены соответственно к второму и третьему информационным входам вычислитель- 5 ных ячеек, начиная с второй строки каждой треугольной матрицы, первый . ! и вто1ой входы сумматора подключены соответственно к выходу умйожителя и к первому информационному входу вычислительной ячейки, начиная с второй строки каждой треугольной матрицы, выход сумматора подключен к выходу вычислительной ячейки, начиная с второй строки каждой треугольной матрицы, причем вычислительные ячейки первой строки, начиная с второго столбца каждой треугольной матрицы, содержат N групп (где N— разрядность поступающих операндов) 20 по N+1 сумматоров и N групп по N сумматоров по модулю два, с первого по N-й разряды первого входа вычислительной ячейки первой строки, начиная с второго столбца каждой треугольной матрицы, являются входами делимого и подключены к первым входам сумматоров соответственно с первого по М-й первой группы, с (N+1)-го по 2N-1 разряды первого входа вычис- 30 лительной ячейки первой строки, начиная с второго столбца каждой треугольной матрицы, подключены также к третьим входам (N+1)-х сумматоров групп с первой по Б-ю, вторые входы; З5

9"ro разряда (=1,...,N) второго входа вычислительной ячейки первой строки, начиная с второго столбца каждой треугольной матрицы, являют ся входами делителя и подключены к перным входам 4 -го сумматора по моду— лю два групп с первой по N-ю, выход

4-ro сумматора по модулю два р -й группы (р=1,...,N) подключен к второму входу ((+I)-ro сумматора р -й груп-45 пы, второй вход первого сумматора первые входы (N+1)-х сумматоров первой группы, вторые входы сумматоров по модулю два первой группы подключены к шине единичного сигнала устройства, выход переноса (?+1)-го сумматора р-й группы подключен к третьему входу1 -го сумматора р -й группы, выходы переноса первых сумматоров f-й группы (f=I,...,N-I) подклю- 55 чены соответственно к вторым входам первых сумматоров, первым входам (N+l)-х сумматоров и к вторым входам

104. 8 сумматоров по модулю два (f+I)-й

Группы у Выход s 1 о (s 2- е о е, И+ 1 ) сумматора f-й группы подключен к первому входу (з-1)-ra сумматора (f+

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

У о первой строки первого столбца каждой треугольной матрицы содержат элемент ИЛИ, N групп сумматоров, при этом р-я (p=I И) группа сумматоров содержит р+2 сумматора, М-1 группу сумматоров по модулю два, при этом .а-я группа (q=l,... N-1) сумматоров по модулю два содержит q сумматоров по модулю двà, N элементов НЕ, первый разряд входа вычислительной ячейки первой строки первого столбца каждой треугольной матрицы подключен к первому входу элемента

ИЛИ и к первому входу первого сумматора первой группы, второй разряд входа вычислительной ячейки первой строки первого столбца каждой треугольной матрицы подключен к второму входу элемента ИЛИ и к второму входу второго сумматора первой группы, (2р+1)-е разряды входа вычислительной ячейки первой строки первого столбца каждой треугольной матрицы подключены к первым входам последнего сумматора р-й группы, (2р+2)-е разряды входа вычислительной ячейки первой строки первого столбца каждой треугольной матрицы подключены к вторым входам последнего суммато1 ра р-й группы и к входу (р+1)-ro элемента. НЕ, выход элемента ИЛИ подключен к входу первого элемента НЕ и к первым входам первых сумматоров по модулю два групп, выход переноса первого сумматора р-й группЫ подключен к первому входу первого сумматора (p+I)-й группы, к второму входу сумматоров по модулю два р-й группы, к первому входу последнего сумматора по модулю два (р+1) — и группы и к первому входу второго сумматора по модулю два третьей группы, третич вход второго сумматора и третьи входы последних сумматоров групп подключены к шине нулевого потенциала устройства„ выход первого элемента НЕ подключен к второму входу первого сумматора первой группы, 9 1 выходы перекоса (р+2)-х сумматоров р-й группы подключены к перным входам (p+1)-х сумматоров р-й группы, выходы переноса у-х сумматоров (ч2,...,р+1) р-й группы подключены к третьим входам (v-!)-х сумматорон, выходы и-х сумматоров (u--2,...,р+2) р-й группы подключены к вторым входам (u-1)-х сумматоров (р+1)-й rpynmr, выходы t-x элементов НЕ (t=2...„

251104 10 р) подключены к вторым входам (p+

+!)-х сумматорон t-й группы, выходы е х сумматоров по модулю два (g=1

q-1) q-й группы подключены к первым входам (g+1)-х сумматоров (q+1)-й группы, выходы переноса первых сумматорон групп подключены к ныходам

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

1251104 сия 4.

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

Редактор И.Рыбченко Техред N.Õoäàíè÷

Корректор С Черни

Закаэ 4413!47 Тираж 671 Подписное

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

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

Рроиэводственно-полиграфическое предприятие, г. ужгород. ул, Проектная, 4