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

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

Иллюстрации

Показать все

Реферат

 

союз советских

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

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

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

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

«Ъ

ыг. (21) 4808761/24 (22) 02.04.90 (46) 30.05.92. Бюл. N 20 (72) И.Г. Кириллов и Д.И. Леховицкий (53) 681,3(088,8) (56) Авторское свидетельство СССР

¹ 1325507, кл. G 06 F 15/324, 1987, Авторское свидетельство СССР

N 1443003, кл, G 06 F 15/347, 1988, (54) УСТРОЙСТВО ДЛЯ ОПЕРАЦИЙ НАД

M ATP И ЦАМ И (57) Изобретение относится к области вычислительной техники и может быть использовано в составе специализированных матричных вычислителей . Цель изобретения — расширение функци(нальных возможностей за счет вычисления определителей исходной матрицы, обратной матрицы и их сомножителей при одновременном сокра„.,5U, Ä 1737461 А1 щении аппаратурных затрат при обработке симметричных теплицевых матриц. Цель достигается тем, что в устройство, содержащее блок 1 синхронизации, первый вычислительный блок 3, блок 10 памяти констант, первый коммутатор 11, первые входной 13 и выходной 14 буферные блоки памяти, введены (! = М/2 для М-четных или (М+ 1)/2 для М-нечетных, М-порядок входной матрицы) блоков 2 предварительных вычислений, второй вычислительный блок 3, блок 4 вычисления диагональных элементов, группу коммутаторов 5 и 6, входных 7 и выходных 8 и 9 блоков памяти, второй коммутатор 12, вторые входной 13 и выходной 14 буферные блоки памяти, что позволило модифицировать алгоритм с учетом специфики обрабатываемых матриц. 1 з.п, ф-лы, 2 ил.

1737461

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

Цель изобретения — расширение функциональных воэможностей за счет вычисления определителей исходной матрицы, обратной матрицы и их сомножителей при одновременном сокращении аппаратурных затрат при обработке симметричных теплицевых матриц.

На фиг. 1 приведена структурная схема устройства для операций над матрицами; на фиг. 2 — структурная схема блока вычисления диагональных элементов.

Устройство для операций над матрицами содержит блок 1 синхронизации, I (I =

М/2 для M четных и (М + 1)/2 для М нечетных) блоков 2 предварительных вычислений, первый и второй вычислительные блоки 3, блок 4 вычисления диагональных элементов, коммутаторов группы 5 и 6,! входных 7 и I выходных 8 и 9 блоков памяти, блок 10 памяти констант, первый и второй коммутаторы 11 и

12, первый и второй входные буферные блоки 13 памяти, первый и второй выходные буферные блоки 14 памяти, Блок 4 вычисления диагональных элементов содержит первый и второй мультиплексоры

15 и 16, первый узел 17 деления, элемент

HE 18, первый регистр 19, первый умножитель 20, вычитатель 21, с третьего по пятый мультиплексоры 22 — 24, второй и третий регистры 25 и 26 второй умножитель 27, второй узел 28 деления, первый выходной регистр 29, чегвертый и пятый регистры 30 и 31, третий умножитель 32, второй выходной регистр 33, Блок 1 синхронизации содержит триггеры запуска и состояния, генератор тактовых импульсов, три одновибратора, элемент И, элемент НЕ, два счетчика, схему сравнения, формирователь, четыре линии задержки, четыре узла мультиплексоров. Вход запуска блока синхронизации подключен к объединенным входам установки триггера запуска, сброса первого и второго счетчиков. Выход триггера запуска подключен к информационному входу триггера состояния, выход которого подключен к первому входу элемента И, выход которого подключен к входу элемента HE и через первый одновибратор к счетному входу первого счетчика, первому выходу инверсного сигнала записи, объединенным первым ин— формационным входам первого и четвертого узлов. мультиплексоров и входу первой линии задержки, выход которой подключен к второму выходу инверсного сигнала записи, 5 второму информационному второго узла мультиплексоров и входу второй линии задержки, выход которой подключен к третьему выходу инверсного сигнала записи и второму информационному входу четверто10 ro узла мультиплексоров. Выход элемента

НЕ подключен через второй одновибратор к счетному входу второго счетчика, первому выходу прямого сигнала записи, объединенным первым информационным входам вто15 рого и третьего узлов мультиплексоров и входу третьей линии задержки, выход которой подключен к второму выходу прямого сигнала записи, второму информационному входу первого узла мультиплексо20 ров и входу четвертой линии задержки, выход которой подключен к второму информационному входу iðåòüåãî узла мультиплексоров и третьему выходу прямого сигнала записи. Выход генера25 тора тактовых импульсов подключен к входу синхронизации триггера состояния и через третий одновибратор к второму входу элемента И. Выход первого счетчика подключен к объединенным

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

35 триггеров запуска и состояния. Выходы второго счетчика подключены к выходам группы кода выбора и входам формирователя, выход которого подключен к выходу сигнала выбора, r-й (r = 1, М-1)

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

45 выбора подключены к выходу блока 1 синхронизации.

Каждый i-й (i = 1, I) блок 2 предварительных вычислений содержит i первых и i вторых умножителей, i первых и i вторых

50 сумматоров. и-й (и = 1, ) вход первой группы

i-го блока предварительных вычислений подключен к первому входу и-ro второго сумматора и первому входу п-го первого умножителя, выход которого подключен к вто55 рому входу и-го первого сумматора. выход которого подключен к и-му выходу первой группы i-ro блока предварительных вычислений, и-й вход второй группы которого подключен к первому входу и-го первого

1737461 сумматора и первому входу и-го второго умножителя, выход которого подключен к второму входу п-ro второго сумматора, выход которого подключен к и-му выходу второй группы i-ro блока предварительных вычислений, третий вход которого подключен к объединенным вторым входам i первых и i вторых умножителей, Каждый о-й (о = 1,2) вычислительный блок 3 содержит (М вЂ” 1) первых и (М-.1) вторых умножителей, (М вЂ” 1) первых и (М-1) вторых сумматоров; r-1 вход первой группы о-го вычислительного блока подключен к первому входу r-го второго сумматора и первому входу r-го первого умножителя, выход которого подключен к второму входу r-ro первого сумматора, выход которого подключен к r-му выходу первой группы о-го вычислительного блока, r-й вход второй группы которого подключен к первому входу r-го первого сумматора и первому входу r-го второго умножителя, выход которого подключен к второму входу r-го второго сумматора, выход которого подключен к r-му выходу второй группы о-го вычислительного блока, r-й входтретьей группы которого подключен к объединенным вторым входам r-ro первого и r-го второго умножителей. Первый и второй входы о-го вычислительного блока подключены к первому и второму входам третьео умножителя, выход которого подключен к первому выходу о-го вычислительного блока.

Первый коммутатор 5 группы содержит мультиплексор, первый и второй информационные входы которого подключены к соответствующим информационным входам коммутатора 5, выход которого подключен к выходу мультиплексора, адресный вход которого через адресный вход коммутатора 5 подключен к выходу сигнала выбора блока

1 синхронизации.

Каждый j-й (j = 2, I) коммутатор 6 группы содержит два мультиплексора входо в j-го блока предварительных вычислений. Первый и второй информационные входы j-го коммутатора 6 подключены соответственно к объединенным первым и объединенным вторым информационным входам мультиплексоров первого и второго входов j-го блока предварительных вычислений; k é (k=

2, j) информационный вход первой группы мультиплексора второго входа j-го блока предварительных вычислений подключен к

k-му информационному входу второй группы j-го коммутатора 6, m-1. j) информационный вход первой группы которого подключен к m-му информационному входу первой группы мультиплексора первого входа j-го блока предварительных вычислений, m-й выход группы которого подключен к m-му выходу первой группы j-ro коммутатора 6 группы, m-й выход второй группы которого подключен к m-му выходу группы

5. мультиплексора второго входа j-ro блока предварительных вычислений. Через адресный вход)-ro коммутатора 6 группы объединенные адресные входы мультиплексоров входов j-ro блока предварительных вычис10 лений подключены к выходу сигнала выбора блока 1 синхронизации.

Каждый i-й входной блок 7 памяти содержит первый и второй блоки памяти; п-е информационные входы первой и второй

15 групп i-го входного блока 7 памяти подключены соответственно к и-м информационным входам групп первого и второго блоков памяти, и-е выходы групп которых подключены соответственно к и-м выходам первой

20 и второй групп i-ro входного блока 7 памяти, через синхровход которого синхровходы первого и второго блоков памяти подключены к первому выходу инверсного сигнала записи блока 1 синхронизации; о-й блок па25 мяти содержит и регистров; п-й информационный вход первой группы входов о-го блока памяти подключен к информационному входу п-го регистра, выход которого подключен к и-му выходу группы выходов о-го

30 блока памяти, синхровход которого подключен к объединенным синхровходам регистров.

Первый выходной блок 8 памяти содержит первый и второй блоки памяти;

35 и-е информационные входы первой и второй групп первого выходного блока 8 памяти подключены соответственно к и-м информационным входам групп входов первого и второго блоков памяти, и-е вы40 ходы групп которых соответственно подключены к и-м выходам первой и второй групп первого выходного блока 8 памяти, через синхровход которого синхровходы первого и второго блоков памяти подклю45 чены к первому выходу прямого сигнала записи блока 1 синхронизации; о-й блок, памяти содержит и регистров; п-й информационный вход первой группы входов о-ro блока памяти подключен к информа50 ционному входу и-го регистра, выход которого подключен к и-му выходу группы о-го блока памяти, синхровход которого подключен к объединенным синхровходам регистров.

55 Каждый J-й выходной блок 9 памяти содержит первый и второй блоки памяти; m-й (m = 1, j) информационный вход первой группы входов /-го выходного блока 9 памяти подключен к m — му информационному входу группы первого блока памяти, k-й выход

1737461 первой группы и первый выход которого подключены соответственно к k-му выходу второй группы и первому выходу J-ro выходного блока 9 памяти, m-й выход первой группы которого подключен к m-му выходу группы второго блока памяти, m-й информационный вход группы которого подключен к m-му информационному входу второй группы j-го выходного блока 9 памяти, через синхровход которого синхровходы и первого и второго блоков памяти подключены к первому выходу прямого сигнала записи блока 1 синхронизации; о-й блок памяти содержит m регистров;

m-й информационый вход группы второго блока памяти подключен к информационному входу m-ro регистра, выход которого подключен к m-му выходу группы второго блока памяти; m-й информационный вход группы первого блока памяти подключен к информационному входу m-го регистра.

Выход первого регистра подключен к первому выходу первого блока памяти, k-й выход первой группы которого подключен к выходу k-ro регистра. Синхровход р-го блока памяти подключен к объединенным синхровходам m регистров, Первый коммутатор 11 содержит мультиплексор, три мультиплексора входов первого вычислительного блока. Второй информационный вход коммутатора 11 подключен к первому информационному входу мультиплексора, выход которого подключен к первому выходу коммутатора 11, г-й информационный вход второй группы которого подкл ючен к (M-г+1)-му входу мультиплексора и r-му информационному входу третьей группы мультиплексора второго входа первого вычислительного блока, r-й выход группы которого подключен к

r-му выходу группы коммутатора 11, р-й (р

= 1, M) информационный вход третьей группы которого подключен к р-м информационным входам первых групп мультиплексоров второго и первого входов первого вычислительного блока, г-й выход первой группы которого подключен к г-му выходу тртьей группы первого коммутатора 11, четвертый и пятый информационный входы которого соответственно подключены к первому информационному входу мультиплексора первого входа первого вычислительного блока и первому информационному входу мультиплексора второго входа первого вычислительного блока, г-й информационный вход второй группы которого подключен к r-му информационному входу первой группы первого коммутатора 11, r-й информационный вход четвертой группы которого подключен к

r-му информационному входу второй группы мультиплексора первого входа первого вычислительного блока.

Первый и третий информацион5 ные входы первого коммутатора 11 подключены соответственно к первому и второму информационным входам мультиплексора третьего входа первого вычислительного блока, r-й выход первой группы

10 которого подключеч к r-му выходу второй группы первого коммутатора 11, через адресный вход которого адресные входы мультиплексоров подключены к выходам группы кода выбора блока 1 синхрониза15 ции, Второй коммутатор 12 содержит три мультиплексора входов второго вычислительного блока; r-й информационный вход третьей группы и первый информацион20 ный вход второго коммутатора 12 соответственно подключены к r-му информационному входу второй группы и первому информационному входу мультиплексора первого входа второго вычисли25 тельного блока, r-й выход первой группы которого подключен к r-му выходу второй группы второго коммутатора 12, р-й информационный вход первой группы которого подключен 5 р-м информационным

30 входам первых групп мультиплексоров первого и второго входов второго вычислительного блока, Второй информационный вход коммутатора 12 подключен к первому информационому входу мультиплексо35 ра второго входа второго вычислительного блока, r-й выход первой группы которого подключен к r-му выходу третьей группы второго коммутагора 12.

r-й и первый информационные входы вто40 рой группы которого подключены соответственно к r-му информационному входу торой группы мультиплексора второго входа второго вычислительного блока и второму информационному входу мульти45 плексора третьего входа второго вычислительного блока, к r-му выходу первой группы второго коммутатора 12, (j + 2)-й информационный вход которого подключен к j-му информационному входу мульти50 плексора второго входа второго вычислительного блока, m-й информационный вход (j + 1)-й группы которого подключен к m-му информационному входу (j

+2)-й группы второго коммутатора 12, Пер55 вый информационный вход мультиплексора третьего входа второго вычислительного блока подключен к третьему информационному входу второго коммутатора 12, через адресный вход которого объединенные адресные входы

1737461

10 мультиплексоров подключены к выходам группы кода выбора блока синхронизации.

Первый (второй) входной буферный блок 13 памяти содержит два блока памяти и регистр; r-e информационные входы первой и второй групп первого (второго) входного буферного блока 13 памяти подключены соответственно к r-м информационным входам групп первого и второго блоков памяти, r-e выходы групп которых подключены соответственно к r-м выходам первой.и втОрой групп первого (второго) входного буферного блока 13 памяти, первый информационный вход которого подключен к информационному входу регистра, выход которого подключен к первому выходу первого (второго) входного буферного блока 13 памяти, через синхровход которого синхровходы первого и второго блоков памяти подключены к выходам четвертой (первой) групп синхронизаци и синхровход регистра подключен к третьему выходу инверсного сигнала записи (второму выходу прямого сигнала записи) блока 1 синхронизации; о-й блок памяти содержит r; r-й информационный вход первой группы входов о-го блока памяти подключен к информационному входу г-го регистра, выход кото рого и одкл ючен к г-му выходу группы выходов о-го блока памяти, r-й синхровход группы которого подключен к синхровходу r-го регистра и r-му выходу четвертой (первой) группы синхронизации блока

1 синхронизации.

Первый (второй) выходной буферный блок 14 памяти содержит два блока памяти и регистр; r-e информационные входы первой и второй групп первого (второго) выходного буферного блока 14 памяти подключены соответственно к r-м информационным входам групп первого и второго блоков памяти, r-e выходы групп которых подключены соответственно к гм выходам первой и второй групп первого (второго) выходного буферного блока

14 памяти, первый информационный вход которого подключен к информационному входу регистра, выход которого подключен к первому выходу первого (второго) выходного буферного блока

14 памяти, через синхровход которого синхровходы первого и второго блоков памяти поключены к выходам третьей (второй) групп синхронизации и синхровход регистра подключен к третьему выходу прямого сигнала записи (второму выходу инверсного сигнала запис) блока 1 синхронизации; о-й блок прамяти содержит r регистров; r-1 информационный вход первой группы входов о-го блока памяти подключен к информационному входу r-го регистра, выход которого под5 ключен к г-му выходу группы выходов о-го блока памяти, r-й синхровход группы которого подключен к синхровходу r-го регистра и г-му выходу третьей (второй) группы синхронизации блока 1 синхронизации.

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

15 которой подключены к соответствующим входам схемы сравнения.

Формирователь блока 1 синхронизации содержэит(з-1) элементов Н Е (s = (logs

М), где (1 — обозначение ближайшего боль20 шего целого), элемент И вЂ” НЕ. Первый вход группы формирователя подключен к пеовому входу элемента.И вЂ” НЕ; q-й (q = 2, s) вход формирователя подключен к входу (q — 1)-го э лемента НЕ, выход которого под25 ключен к р-му входу элемента И вЂ” НЕ, выход которого подключен к выходу формирователя и выходу сигнала выбора блока 1 синхронизации, Первый узел мультиплексоров блока 1

30 синхронизации содержит (М вЂ” 1) мультиплексоров и элемент И. Первый информационный вход первого узла мультиплексоров подключен к объединением в-му (в = 1, M-q — 1, р = 1, М вЂ” 2) инфор35 мационному входу q-го мультиплексора и первому входу элемента И. Второй информационный вход первого узла мультиплексоров подключен к объединенным s-му (s

= M — q, М вЂ” 1) информационному входу (q +

40 1)-го мультиплексора и второму входу элемента И, выход которого подключен к (Мr)-му и н форма цион ному входу r-го мультиплексора, выход которого подключен к r-му выходу первой группы первого

45 узла мультиплексоров, к адресному входу которого подключены объединенные адресныее входы (М вЂ” 1) мультиплексоров, Каждый h-й (h = 2, 4) узел мул ьтиплексоров блока 1 синхронизации содержит (М вЂ” 1)

50 мультиплексоров. Первый информационный вход h-го узла мультиплексоров подключен к s-му (s = М вЂ” r + 1, M) информационному входу -co мультиплексора. Второй информационный вход h-го узла

55 мультиплексоров подключен к s-му (s = 1, M-r) информационному .входу г-го мультиплексора, выход которого подключен к r-му выходу первой группы h-го узла мультиплексоров, к адресному входу которого подклю1737461

12 чены объединенные адресные входы (М-1) блока подклю е чен к объединенным (r + 1)-м мультипле р м льтиплексоров, информационным входам (М вЂ” 1)-го мультиМультиплекор первого входа j-го блока плексора, Выход r-ro муль хо г-го м льтиплексорэ подпредварительных вычислений j-го коммута- кл юч е н к г- у ду р г-м выхо первой группы то а 6 г ппы содержит j мультиплексоров, 5 мультиплексора первого выхода первого выЕго пе вый информационный вход подклю- числительногоблока, адр ь д р чен к объединенным первым информацион- подключен к объединенным адресным вхоным входам s-x(s = 1., j — 1) мультиплексоров, дам (M-1) мультиплексоров. а вто ой информационный вход подключен к первому информационному входу j-го 10 вычислительного блока первого коммутамультиплексора; в-и информ в-й информационный тора 11 содержит(М вЂ” 1) мультиплексоров. вход первой группы мультиплексора перво- Его q-й информационный вход второй

ro входа j-го блока предварительных вы- группы подключен к объединенным з-м(з числений подключен к второму = 2, M — Q) информационным входам ц-Io а (r + 1)-й информационинформационномувходу в-гомультиплеко- 15 мультиплексора; (r )ра, выход которого подключен к т-му выхо- ный вход пер ру у вой r ппы м льтиплексора ду первой группы мультиплексора первого второ о д р г вхо а пе ваго вычислительного вхо а -го блока предварительных вычисле- блока подключен к первому информацивхода )-го л ний, к адресному входу которого подключе- онному входу - у х г-го м льтиплексора; h-й (h ны объединенные адресные входы j 20 = 2, М вЂ” 1) информационный вход третьей группы мультиплексора BTopor G входа мультиплексоров. т льного блока подклюМ льтиплексорвтороговхода)-гоблока первого вычислительног л предварительных вычислений j-го коммута- чен к (g — ).- у (g = ультипл тора 6 группы содержит (j + 1) мультиплек- ному входу (M-ц+1}-ro мультиплексора, со ов и линию задержки, Первый 25 Первый информационный вход мультиинформационный вход мультиплексора вто- плексора втор соров и линию задержк т ого вхо а пе aoi o вычислид р блока предварительных Bbl тельного блока подключен к (I + 1}-му вхо М вЂ” г -го м льтичислений подключен к объединенным информационному входу(— )- у первым информационным входам s-x (s = 1, плексора, выход которого подключен к

) — 2) мультиплексоров и входу линии задер- 30 (М вЂ” r)-му выходу первой группы мультижки, а вто ой инфо мационный вход под- плексора второго входа первого вычислиключен к первому информационному входу тельного блока, адресный вход которого

; k- информацион- подключен к объединенным адресным ный вход первой группы мультиплексора входам (М вЂ” 1) мультиплексоров. второго входа j-ro лока предв б редварительных 35 Мультиплексор третьего входа первовычислений подключен к вт ен к второму информа- ro (второго) вычислительного блока первоионном входу (k — 1)-го мультиплексора, ro (второго} коммутатора () выход которого подключен к(к — 1)-му выходу содержит (— ) мул ит (M — I) м льтиплексоров. Его первой группы мультиплексор в е сора второго вхо- первый информационный вход подключен да j-ro лока предв б редварительных вычислений, 40 к объединенным s-м (s = 1, М-r) информао ор — - " бьj-й выход первой группы котор о орого подклю- ционным входам r-ro мультиплексора, о ь и = М вЂ” г+1, М) чен к выходу линии задержки, Объединен- единенные h-e (h = Ivi-г+1, ные адресные входы ц- ) мульти (j — 1) типлексоров информационные входы которого подклюподключены к адресном в ному входу мультиплек- чены к второму информационному входу сора второго входа j-ro лок б ока предваритель- 45 мультиплексора третьего входа первого (второго) вычислительного блока первого ных вычислений.

11 (12), г-й выход

M ксор первого входа первого (второго) коммутатора (), ультиплексо вычислительного блока первого коммутато- первой группы которого подклю чен к выра 11 соде жит (М вЂ” 1) мультиплексо ра д (iMi — 1) ексоров, Его ходу r-ro мультиплексора, объециненные г-й информационный вход первой группы 50 адресные входы которых подключены кадподключен к первому инфор ф мационному ресному входу мультиплексора третьего входу r-го мультиплексора; q-й и (q

q-й и (q + 1)-й входа первого (второго) вычислительного

11 информационные входы вто орой группы блока первого (второго) коммутатора мультиплексора первого входа первого вы- (). (12). числительного блока подключ ючены соответт- 55 Мультиплексор первого входа второго внено к объединенным s-м (s = (= 2 M — q) и вычислительного блока второго коммутатообъединенным h-м . = — q ин (h = М вЂ” +1, M) информа- ра 12 содержит (M-1) мультиплексоров. Его ционным входам q-го мультипл

-го мультиплексора. Пер- r-й информационный вход первой группы вый информационныи вход м входмультиплексора подключен к первому информационному первого входа первого вычи слительного входу r-ro мультиплексора, ооьединенные

1737461

s-e (s = М вЂ” г+1, М) информационные входы которого подключены к первому информационному входу мультиплексора первого входа второго вычислительного блока, q-й информационный вход второй группы подключен к объединенным h-м (h = 2, М вЂ” q) информационным входам q-ro мультиплексора. Выход г-го мультиплексора подключен к r-му выходу первой группы мультиплексора епрвого входа второго вычислительного блока, адресный вход которого подключен к объединенным адресным входам (М вЂ” 1) мультиплексоров.

Мультиплексор второго входа второго вычислительного блока второго коммутатора 12 содержит (М вЂ” 1) мультиплексоров. Его (г+1)-й информационный вход первой группы подключен к первому информационному входу г-го мультиплексора; s-й (s =

2, M — 1) информационный вход второй группы мультиплексора второго входа второго вычислительного блока (I = h, h =

) М/2 (, т.е. М вЂ” четное, где ) (— обозначение ближайшего меньшего целого) подключен к объединенным я-м (о = 2, M — в+1) информационным входам (з — 1)-го мультиплексора. М-й информационный вход первого мультиплексора подключен к первому информационному входу мультиплексора второго входа второго вычислительного блока, m-й информационный вход (j +1)-й группы которого подключен к (М вЂ” m + 1)-Му входу)-го мультиплексора;

j-й информационный вход мультиплексора второго входа второго вычислительного блока подключен к объединенным

s-м (s = j, M) информационным входам (M — )+1)-го мультиплексора; s-й (s = 1, h+1) информационный вход (I+1)-й (I =

=h+1, т.е, М вЂ” нечетное) группы входов мультиплексора второго входа второго вычислительного блока подключен к (М вЂ” s+1)-му входу I-го мультиплексора.

I-й информационный вход мультиплексора второго входа второго вычислительного блока подключен к . объединенным s-м (s = I, M) входам (h+1)-го мультиплексора (использование I-го и (h+1)-го мультиплексоров при I = h+1 равнозначно, что будет показано при описании работы устроиства). Выход r-ro мультиплексора подключен к r-му выходу первой группы мультиплексора второго входа второго вычислительного блока, адресный вход которого подключен к объединенным адресным входам (М вЂ” 1) мул ьти плексоров.

Устройство для операций над матрицами предназначено для вычисления определения det Ф исходной М М симметричной жения матрицы ф обратной к исходной матрице Ф, такой что ф Ф, на две треугольные (верхнюю V и нижнюю V) и диагональную О, такие что 1 V DV (без

15 формирования матрицы ф),. решения системы линейных алгебраических уравнений

ФУ =Х.

Алгоритм формирования элементов 1;> матрицы 1 = (Iij } i-1. 1-1 и элементов бц м i

20 = б диагональной матрицы О имеет вид:

k=0;

k=1, M-1, 40

=0;

k=1,...,М вЂ” 1:

j=1,...,п, = М-),...,М-1

k = 1,..., М вЂ” 1

Ь +1= р1;

10

55 теплицевой положительно определенной матрицы Ф, т.е, матрицы, элементы fir которОй удОВЛЕтВОряЮт раВЕНСтВаМ f+1, к+1 = f;k (i, k = 1, „., М-1), fik = fki (i = 2, ..., М; k = 1, ..., i — 1) и которая может быть однозначно задана первач столбцом (строкой) R, таким что

R = (111} -1 = (p} -1, разложения ее на две треугольные (нижнюю L и верхнюю LT, где т обозначает транспонированную матрицу) и диагональную О, такие что А = LDL, разлоIi1, р;,qi= p;i=1...„М;

d1 = 1/Р,

Ск+1=1/(1 — &+1 )б+1=бк — Ск+1:

pi = рн-1 + а K + 1+ qi

qi = qi+ ак+1 pi+1, i=1,...,M-K; к+Цс+1 = Ц1; где р., qi ак+1, Ск+1 — промежуточные переменные, k = 0 момент подачи исходных данных на входы устройства, k — номер такта вычислений.

Для вычисления элементов vijматрицы

V = (Vij } i-ц-1 реализован алгоритм, М который имеет вид

qi - =0; i = --1, ..., j-1;

pi =0; i =1,...,j+1; р, qj =1; v» = р1;

Pi=A 1+ а к +1 ц =1...„

qi = ql +

+«к+1 Рн.1

Чк+14 = P1:

VK+1,м-i+1 =

= Цм-к, где ) — номер предварительного вычислителя, п =e (М+1)/2)(я (х) — целая часть х).

Для вычисления элементов Ь; пром —, I жуточного вектора В = VX (В = bi- ., X Exi .

-в =1 А i+/ реализован алгоритм, который и еет вид pi, qI=х;;l 1...„м; k-0;

Ь1= р1; р =рн-1+ак -1qj (i=1,...,M — k;

qi = qi + а к + 1 pi+1, ) 16

1737461

15 м

der Ф = 1/П di.

i =1

20

45

Определитель матрицы Ф вычисляется по формуле

Для вычисления элементов Yi векторарешения системы линейных алгебраических уравнений

У(" Ук= О;

k= 1„...М; у )1 = чц Ь б + У.(j; |=

= 1„...k

Yl = YI(M)i; i 1;...м.

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

На i-e информационные входы первой и второй групп устройства (i = 1„„,М, М вЂ” порядок входной матрицы) подаются 1-е компоненты соответственно х; исходного вектора-столбца Х правой части системы уравнений ФУ = Х и р первого векторастолбца (строки) R исходной теплицевой симметричной положительно определенной матрицы Ф, полностью задающего эту матрицу.

После подачи на входы устройства векторов Х и R к началу первого такта его работы имеем ч11 = 1, Ь1 = н11 x1 = х1 и Ii1 =

=p (i = 1,...,3).

Блок 1 синхронизации управляет работой устройства в соответствии с алгоритмом.

Первый такт. В первой половине такта р и код н1", поступившие соответственно на первый информационный вход первой группы и первый вход блока 4 вычисления диагональных элементов, с выходов третьего 22 и четвертого 23 мультиплексоров записываются во второй 25 и третий 26 регистры, Во втором умножителе 27 и втором блоке 28 деления вычисляется d1 = 1/

Р, а в первом блоке 17 деления и элементе НЕ 18 — о = — pr//г (элемент НЕ используется для получения обратного кода числа), куда р иpz подаются с первого и второго информационных входов первой группы блока 4 соответственно через второй 16 и первый 15 мультиплексоры. Во второй половине такта значение рг записывается в первый регистр 19, d1 — в первый выходной регистр 29, р,= =1/d1 и код н1", который подается через пятый мультиплексор 24, записываются соответственно в четвертый 30 и пятый 31 регистры, и в третьем умножителе 32 блока 4 вычисления диагональных элементов начинается процесс поэтапного вычисления определителя det Ф матрицы Ф.

На первый и второй информационные входы первого входного блока 7,1 памяти через первый предварительный коммутатор 5 с второго выхода блока 10 памяти констант и непосредственно с третьего выхода блока 10 памяти констант соответственно подаются и запоминаются в нем коды и1и и иО". С первого и второго выходов блока 7.1 памяти коды н1н и нОн поступают на соответствующие входы первого блока 2.1 предварительного вычисления, в котором начинается вычисление промежуточных переменных р и q в соответствии с алгоритмом.

К = 0; р1. q1 = 1: рг = 0; v11 = p1 = 1; = "° P1 = P2+ Wq1 21 = P1

q1 = q1 + ХХгрг

На третьи входы первого 2,1 и второго 2.2 блоков предварительного вычисления подается щ с первого регистра 19 блока

4 вычисления диагональных элементов, На первый и второй информационные входы первой и второй групп второго входного блока 7.2 памяти через второй предварительный коммутатор 6 подаются соответственно с третьего, второго и второго, третьего выходов блока 10 памяти констант и запоминаются коды нО", н1н и н1", нО", С первого, второго выходов первой и второй групп второго входного блока 7,2 памяти информация поступает на соответствующие входы первой и второй групп входов второго блока 2.2 предварительного вычисления, в котором начинается вычисление промежуточных переменных в соответствии с алгоритмом, М = 0; р1,2 = 0; р1...з = 0; рг, цг = 1: и 12 = р1;

k = 1; pi = p2 + ГхгЦ1, v22 = p1 Ц1 = q1 + Гхгрг

Р2 = Рз+ Гхгцг; чг = Цг+ ГХ2Рз; чгг = q2 °

На первый, второй информационные входы первой и второй групп первого входного буферного блока 13.1 памяти через первый коммутатор 11 подаются и запоминаются соответственно пары значений р, à и/Ж,рз, На первый, второй информационные входы первой и второй групп входов второго входного буферного блока 13.2 памяти через второй коммутатор 12 подаются и запоминаются соответственно пары значений х1, хг и х2, хз, Первый, второй выходы первых и

18

1737461

17 вторых групп выходов первого 13.1 и второго 13.2 входных буферных блоков памяти подаются на соответствующие входы вторых и третьих групп соответственно первого 3.1 и второго 3.2 вычислительных блоков, на первый и второй входы первых групп которых подается аг из первого регистра 19 блока 4 вычисления диагональных элементов. В вычислительных блоках

3,1 и 3.2 начинаются вычисления в соответствии с алгоритмом.

В вычислительном блоке 3.1:

k=0;!и= р; i=1,...,3;

k=1, p1= p2+ агЦ1= рг+агр1, Q1=Q1+

+ а2Р2 p1 + <2p2 l22 Ц1

Рг = Рз + агЦг = Рз + <2P2: Цг = Ц2 + а2РЗсс = P2+ агрЗ;!32 = Ц2.

В вычислительном блоке 3.2:

k= 0; Ь1= Х1;

k = 1; p1 = p2 + а2Ц1 = х2 + а2х1, b2 = р1, Ц1=

= Ц1 + <2p2 >

Через первый коммутатор 11 с первого входа первой группы устройства на первый информационный вход первого входного буферного блока 13.1 памяти поступает и запоминается х1, которое с первого выхода блока 13.1 поступает на второй информационный вход первого вычислительного блока 3.1, на первый информационный вход которого подается d> из первого выходного регистра 29 блока 4 вычисления диагональных элементов. В блоке 3.1 вычисляется у " =. Ь d1= Xld1.

Второй такт. B первой половине такта в первом выходном блоке 8 памяти запоминаются p> = ч21 и q>, поступающие соответственно на его первый и второй информационные входы, во втором выходном блоке 9 памяти — р1 = чгг, р2 и ц1, ц2 = чгг, поступающие соответственно на его первый, второй информационные входы первой и второй групп, в первом выходном буферном блоке 14,1 памяти — р, р2 и q = =!22, Цг

= l32, поступающие соответственно на его первый, второй информационные входы первой и второй групп, во втором выходном буферном блоке 14.2 памяти — р = Ьг, рги q, цг, поступающие соответственно на его первый, второй информационные входы первой и второй групп.

Во второй 25 и третий 26 регистры блока 4 вычисления диагональных элементов записываются соответственно 1 — аг и

1/d>, поступающие с выходов мультиплексоров 22 и 23. Начинается вычисление d2 =

d1/(1 — -а3) во втором умножителе 27 и втором блоке 28 деления. Во второй выходной регистр 33 записывается промежуточное значение определителя исходной матрицы det© =1/d1. С выходов мульти(1) плексоров 15 и 16 блока 4 вычисления диагональных элементов соответственно рг и q подаются на входы делимого и делителя первого блока 17 деления, где вычисляется аз = -рг/q>, формируемое на выходе элемента НЕ 18, Значение p> = чг поступает с первого выхода первого выходного блока 8 памяти на первый вход второго входного буферного блока 13.2 памяти и запоминается в нем.

Через коммутатор 12 на вторые информаци25 онные входы первой и второй групп второго входного буферного блока 13.2 памяти подаются и запоминаются в нем код нОы с третьего выхода блока 10 памяти констант и р1 = чгг с первого выхода первой группы второго выходного блока 9 памяти, которые подаются на вторые информационные входы второй и третьей групп входов второго вычислительного блока 3,2, на второй информационный вход первой группы, первый и второй информационные входы которого подаются соответственно с первого выхода первой группы блока 14,2 через коммутатор 12 значение Ьг, непосредственно из блока 14.2 — Ьг и с

40 первого выхода блока 13.2 — v21. Начинаются вычисления v22 b2 + 0 и чгl ° Ь2.

Значение у 1 = ч11 bi б1 с первого выхода первого вычислительного блока 3,1 поступает на первый информационный

45 вход первого выходного буферного блока

14,1 памяти и запоминается в нем, Во второй половине такта аз записывается в первый регистр 19, dz = dг/(1 — ах/ в первыи выходной регистр 9. 1/dz — в

50 четвертыи регистр 30, det Ф = 1/О1 — в (1 пятый регистр 31 блока 4 вычисления диагональных элементов.

На первые входы первых и вторых групп всех входных блоков 7 и 13 памяти поступа55 ет и запоминается информация из соответствующих выходных блоков 8, 9 и 14 памяти, т.е. соответственно значения q> и рг, На первые информационные входы первых групп вычислительных блоков 3 и на третьи

1737461

20 информационные входы блоков 2 предварительного вычисления подается аз. В первом блоке 2.1 предварител