Устройство для операций над матрицами Советский патент 1992 года по МПК G06F15/347 

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

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

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

Устройство для операций над матрицами содержит блок 1 синхронизации, 1 (I М/2 для М четных и (М + 1)/2 для М нечетных) блоков 2 предварительных вычислений, первый и второй вычислительные блоки 3, блок 4 вычисления диагональных элементов, I коммутаторов группы 5 и 6, I входных 7 и I выходных 8 и 9 блоков памяти, блок 10 памяти констант, первый и второй коммутаторы 11 и 12, первый и второй входные буферные блоки 13 памяти, первый и второй выходные буферные блоки 14 памяти. Блок 4 вычисления диагональных элементов содержит первый и второй мультиплексоры 15 и 16, первый узел 17 деления, элемент НЕ 18, первый регистр 19, первый умножитель 20, вычитатель 21, с третьего по пятый мультиплексоры 22 - 24, второй и третий регистры 25 и 26 второй умножитель 27, второй узел 28 деления, первый выходной регистр 29, четвертый и пятый регистры 30 и 31, третий умножитель 32, второй выходной регистр 33.

Блок 1 синхронизации содержит триггеры запуска и состояния, генератор тактовых импульсов, три одновибратора, элемент И, элемент НЕ, два счетчика, схему сравнения, формирователь, четыре линии задержки, четыре узла мультиплексоров. Вход запуска блока синхронизации подключен к объединенным входам установки триггера запуска, сброса первого и второго счетчиков. Выход триггера запуска подключен к информационному входу триггера состояния, выход которого подключен к первому входу элемента И, выход которого подключен к входу элемента НЕ и через первый одновибратор к счетному входу первого счетчика, первому выходу инверсного

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

второму информационному второго узла мультиплексоров и входу второй линии задержки, выход которой подключен к третьему выходу инверсного сигнала записи и второму информационному входу четвертого узла мультиплексоров. Выход элемента НЕ подключен через второй одновибратор к счетному входу второго счетчика, первому выходу прямого сигнала записи, объединенным первым информационным входам второго и третьего узлов мультиплексоров и входу третьей линии задержки, выход которой подключен к второму выходу прямого сигнала записи, второму информационному входу первого узла мультиплексоров и входу четвертой линии задержки, выход которой подключен к второму информационному входу третьего узла мультиплексоров и третьему выходу прямого сигнала записи. Выход генератора тактовых импульсов подключен к входу синхронизации триггера состояния и через третий одновибратор к второму входу элемента И. Выход первого счетчика подключен к объединенным

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

0 входам первых групп мультиплексоров первого и второго входов второго вычислительного блока. Второй информационный вход коммутатора 12 подключен к первому информационому входу мультиплексо5 ра второго входа второго вычислительного блока, r-й выход первой группы которого подключен к r-му выходу третьей группы второго коммутатора 12. r-й и первый информационные входы вто0 рой группы которого подключены соответственно к r-му информационному входу второй группы мультиплексора второго входа второго вычислительного блока и второму информационному входу мульти5 плексора третьего входа второго вычислительного блока, к r-му выходу первой группы второго коммутатора 12, (j + 2)-й информационный вход которого подключен к j-му информационному входу мульти0 плексора второго входа второго вычислительного блока, m-й информационный вход 0 + 1)-й группы которого подключен к m-му информационному входу (j + 2)-й группы второго коммутатора 12. Пер5 вый информационный вход мультиплексора третьего входа второго вычислительного блока подключен к третьему информационному входу второго коммутатора 12, через адресный вход которого объединенные адресные входы

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

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

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

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

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

Первый узел мультиплексоров блока 1 синхронизации содержит (М-1) мультиплексоров и элемент И. Первый информационный вход первого узла мультиплексоров подключен к объединен- ным s-му (s 1, M-q-1, q 1, М-2) информационному входу q-ro мультиплексора и первому входу элемента И. Второй информационный вход первого узла мультиплексоров подключен к объединенным s-му (s M-q, F/f-1) информационному входу (q + 1)-го мультиплексора и второму входу элемента И, выход которого подключен к (М- г)-му информационному входу г-го мультиплексора, выход которого подключен к r-му выходу первой группы первого узла мультиплексоров, к адресному входу которого подключены объединенные адресные входы (М-1) мультиплексоров.

Каждый h-й (h 2, 4) узел мультиплексоров блока 1 синхронизации содержит (М-1) мультиплексоров. Первый информационный вход h-ro узла мультиплексоров подключен к s-му (s W-r +1, М) информационному входу r-го мультиплексора. Второй информационный вход h-ro узла мультиплексоров подключен к s-му (s 1, М-г) информационному «ходу r-го мультиплексора, выход которого подключен к г-му выходу первой группы h-ro узла мультиплексоров, к адресному входу которого подключены объединенные адресные входы (М-1) мультиплексоров.

Мультиплекор первого входа j-ro блока предварительных вычислений j-ro коммутатора 6 группы содержит j мультиплексоров. Его первый информационный вход подключен к объединенным первым информационным входам s-x (s 1 „ j-1) мультиплексоров, а второй информационный вход подключен к первому информационному входуJ-ro мультиплексора; m-й информационный вход первой группы мультиплексора первого входа j-ro блока предварительных вычислений подключен к второму информационному входу т-го мультиплеко- ра, выход которого подключен к m-му выходу первой группы мультиплексора первого входа j-ro блока предварительных вычислений, к адресному входу которого подключе- ны объединенные адресные входы j мультиплексоров.

Мультиплексор второго входа j-ro блока предварительных вычислений j-ro коммутатора 6 группы содержит (j + 1) мультиплексоров и линию задержки. Первый информационный вход мультиплексора второго входа j-ro блока предварительных вычислений подключен к объединенным первым информационным входам s-x (s 1, j-2) мультиплексоров и входу линии задержки, а второй информационный вход подключен к первому информационному входу (j-1)-ro мультиплексора; k-й информационный вход первой группы мультиплексора второго входа j-ro блока предварительных вычислений подключен к второму информационному входу (к-1)-го мультиплексора, выход которого подключен к (к-1)-му выходу первой группы мультиплексора второго входа j-ro блока предварительных вычислений, j-й выход первой группы которого подключен к выходу линии задержки, Объединенные адресные входы () мультиплексоров подключены к адресному входу мультиплексора второго входа j-ro блока предварительных вычислений.

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

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

Мультиплексор второго входа первого

0 вычислительного блока первого коммутатора 11 содержит (М-1) мультиплексоров. Его q-й информационный вход второй группы подключен к объединенным s-м (s 2, M-q) информационным зходам q-ro

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

0 2, М-1) информационный вход третьей группы мультиплексора второго входа первого вычислительного блока подключен к (М + д-Ь)-му (д 2, h) информационному входу ()-го мультиплексора.

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

0 (М-г)-му выходу первой группы мультиплексора второго входа первого вычислительного блока, адресный вход которого подключен к объединенным адресным входам (М-1) мультиплексоров.

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

0 к объединенным s-м (s 1, М-r) информационным входам r-ro мультиплексора, объединенные h-e (h lvi-r+1, M) информационные входы которого подключены к второму информационному входу

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

0 адресные входы которых подключены к адресному входу мультиплексора третьего входа первого (второго) вычислительного блока первого (второго) коммутатора 11 (12).

5 Мультиплексор первого входа второго вычислительного блока второго коммутатора 12 содержит (М-1) мультиплексоров. Его4 r-й информационный вход первой группы подключен к первому информационному входу r-го мультиплексора, объединенные

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

Мультиплексор второго входа второго вычислительного блока второго коммутато- ра 12 содержит (М-1) мультиплексоров. Его (г+1)-й информационный вход первой группы подключен к первому информационному входу r-го мультиплексора; s-й (s 2, М-1) информационный вход второй группы мультиплексора второго входа второго вычислительного блока (I h, h М/2 , т.е. М - четное, где -.обозначение ближайшего меньшего целого) подключен к объединенным g-м (д 2, M-s+1) информационным входам (s-1)-ro мультиплексора. М-й информационный вход первого мультиплексора подключен к первому информационному входу мультиплексора второго входа второго вычис- лительного блока, m-й информационный вход (j +1)-й группы которого подключен к (М-пл + 1)-му входу j-ro мультиплексора; j-й информационный вход мультиплексора второго входа второго вычислительно- го блока подключен к объединенным s-м (s j, M) информационным входам (M-j+1)-ro мультиплексора; s-й (s 1, h+1) информационный вход (1+1)-й (I h+1, т.е. М - нечетное) группы входов мультиплексора второго входа второго вычислительного блока подключен к (М-з+1)-му входу 1-го мультиплексора. 1-й информационный вход мультиплексора второго входа второго вычисли- тельного блока подключен к объединенным s-м (s I, М) входам (h+1)-ro мультиплексора (использование 1-го и (h+1)-ro мультиплексоров при I h+1 равнозначно, что будет показано при описа- нии работы устройства). Выход г-го мультиплексора подключен к r-му выходу первой группы мультиплексора второго входа второго вычислительного блока, адресный вход которого подключен к объеди- ненным адресным входам (М-1) мультиплексоров.

Устройство для операций над матрицами предназначено для вычисления определения det Ф исходной симметричной

теплицевой положительно определенной матрицы Ф, т.е. матрицы, элементы fik которой удовлетворяют равенствам fj+i, K+1 fik

(I, k 1M-1), fik fki(i 2M;k 1

i-1) и которая может быть однозначно задана первым столбцом (строкой) R, таким что R { fn}i-i {/и} i-1, разложения ее на две треугольные (нижнюю L и верхнюю , где т обозначает транспонированную матрицу) и диагональную D, такие что А LDLT, разложения матрицы ij) обратной к исходной матрице Ф, такой что 1р , на две треугольные (верхнюю VT и нижнюю V) и диагональную D, такие что tp VTDV (без формирования матрицы $,. решения системы линейных алгебраических уравнений ФУ Х.

Алгоритм формирования элементов ц матрицы L { Ijj } м M.j-i и элементов dn di диагональной матрицы D имеет вид:

., М; 1

1и, pi. qi 1М; | k 0;

di 1//3,;

«K + 1 -p2/qi;

Ски-1/( + 1 )сЫ- Ь-Ски; ,M-1, pi pi+1 + «к +i + qi;

qi qi+ a K+1 pi+i: i 1M-K;

1к+и+1 qi;J

где pi, qi, «к + 1, Ск+1 - промежуточные переменные, k 0 момент подачи исходных данных на входы устройства, k - номер такта вычислений.

Для вычисления элементов vij матрицы V { Vij } м M.j-1 реализован алгоритм, который имеет вид

qi 0; i 1j-1;

pi-0:1-1J+1: k 0;

Pj,qj 1;vij pi;

B-PW+ j

-tox+iqi; Nj;

qi qi+ f

+#K + ipi+ljJk 1M-1;j 1n,

VK+I.J pi;

VK+LM-J+I

qM-K:k M-jM-1;

где j - номер предварительного вычислителя, n e(M+1)/2XЈ(x) целая часть х).

Для вычисления элементов ty проме, жуточного вектора В VX (В bi)-.i/X /xj) реализован алгоритм, который имеет вид рС

qi xi,-i 1М;{. k 0;

bi pi;

р1 рн-1+«к +iqi; Li 1M-k; 1

qi qi +GK

:к +iqi; li +1 Pi+i:J

k 1

M-1

Ьк+i pi;

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

м det Ф 1/П di.

i 1

Для вычисления элементов YI вектора- решения системы линейных алгебраических уравнений ФУ X, где Y /У MKI, реализован алгоритм, который имеет вид

У(|СА 0;I k-1М;

y(k)j vkibkdk + Y(k-1)j..J

1k:

Y, Yj( i 1,...M.

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

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

После подачи на входы устройства векторов X и R к началу первого такта его работы имеем vn 1, bi vn xi xi и и

PO 13).

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

Первый такт. В первой половине такта р и код 1, поступившие соответственно на первый информационный вход первой группы и первый вход блока 4 вычисления диагональных элементов, с выходов третьего 22 и четвертого 23 мультиплексоров записываются во второй 25 и третий 26 регистры. Во втором умножителе 27 и втором блоке 28 деления вычисляется di 1/ ft, а в первом блоке 17 деления и элементе НЕ 18 ft,(элемент НЕ используется для получения обратного кода чмсла), куда ft/ и/92 подаются с первого и второго информационных входов первой группы блока 4 соответственно через второй 16 и первый 15 мультиплексоры. Во второй половине такта значение pi записывается в первый регистр 19, di - в первый выходной регистр 29, /3, 1/di и код 1, который подается через пятый мультиплексор 24, записываются соответственно в четвертый 30 и пятый 31 регистры, и в третьем умножителе 32 блока 4 вычисления диагональных элементов начинается процесс поэтапного вычисления определителя det Ф матрицы Ф.

На первый и второй информационные

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

котором начинается вычисление промежуточных переменных р и q в соответствии с алгоритмом.

k 0:pi.qi 1;p2 0;vii pi 1; k 1; pi р2 + ozqn vai pi, qi qi + «2P2.

На третьи входы первого 2.1 и второго 2.2 блоков предварительного вычисления

подается «г с первого регистра 19 блока 4 вычисления диагональных элементов. На первый и второй информационные входы первой и второй групп второго входного блока 7.2 памяти через второй

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

первой и второй групп второго входного блока 7.2 памяти информация поступает на соответствующие входы первой и второй групп входов второго блока 2.2 предварительного вычисления, в котором

начинается вычисление промежуточных переменных в соответствии с алгоритмом,

k 0;qi,2 0; pi ..з 0; Р2, q2 1: vi2 pi; к 1; pi p2+ «2qi; V22 pi; qi qi + «2ps

P2 P3 + «2q2, q2 Q2 + «2P3I V22 Q2

На первый, второй информационные входы первой и второй групп первого входного буферного блока 13.1 памяти через первый коммутатор 11 подаются и запоминаются соответственно пары значений р, pi ,рз , На первый, второй информационные входы первой и

второй групп входов второго входного буферного блока 13.2 памяти через второй коммутатор 12 подаются и запоминаются соответственно пары значений xi, ха и Х2, хз. Первый, второй выходы первых и

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

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

k 0; 1и ft: 1 13;

k 1; pi p2+ «aqi pi qi qi+ + «2P2 p +«2/02; 122 qi;

P2 P3 + CC2Q2 /03 + «2 pi , Q2 Q2 +

«2P3 pi + «2/03; I32 q2.

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

k 0; bi xi;

k- 1; pi p2 + «2qi X2+ O2xi;b2 pi; qi qi + «2P2 xi + 0:2x2;

P2 P3 + «2q2 хз + «2x2; q2 q2 + «2P3

X2 + «2X3.

Через первый коммутатор 11 с первого входа первой группы устройства на первый информационный вход первого входного буферного блока 13.1 памяти поступает и запоминается xi, которое с первого выхода блока 13.1 поступает на второй информационный вход первого вычислительного блока 3.1, на первый информационный вход которого подается di из первого выходного регистра 29 блока 4 вычисления диагональных элементов. В блоке 3.1 вычисляется

у( )1 virbrdi xrch.

Второй такт. В первой половине такта в первом выходном блоке 8 памяти запоминаются pi V21 и qi, поступающие соответственно на его первый и второй информационные входы, во втором выходном блоке 9 памяти - pi V22, Р2 и qi, q2 V22, поступающие соответственно на его перчый, второй информационные входы первой и второй групп, в первом выходном буферном блоке 14.1 памяти - pi, р2 и qi l22, q2 з2, поступающие соответственно на его первый, второй информационные входы первой и второй групп, во втором выходном буферном блоке 14.2 памяти Р1 Ь2, Р2И qi, q2, поступающие соответственно на его первый, второй информационные входы первой и второй групп.

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

записываются соответственно 1 - «2 и 1/di, поступающие с выходов мультиплексоров 22 и 23. Начинается вычисление d2

di/(1 - -ее 2) во втором умножителе 27 и

втором блоке 28 деления. Во второй выходной регистр 33 записывается промежуточное значение определителя исходной матрицы 1/di. С выходов мультиплексоров 15 и 16 блока 4 вычисления диатональных элементов соответственно Р2 и qi подаются на входы делимого и делителя первого блока 17 деления, где вычисляется Оз -p2/qt1 формируемое на выходе элемента НЕ 18.

Значение pi V2i поступает с первого выхода первого выходного блока 8 памяти на первый вход второго входного буферного блока 13.2 памяти и запоминается в нем. Через коммутатор 12 на вторые информационные входы первой и второй групп второго входного буферного блока 13.2 памяти подаются и запоминаются в нем код О с третьего выхода блока 10 памяти констант и P1 V22 с первого выхода первой группы

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

первый и второй информационные входы которого подаются соответственно с первого выхода первой группы блока 14.2 через коммутатор 12 значение Ь2, непосредственно из блока 14.2 - Ь2 и с

первого выхода блока 13.2 - V21. Начинаются вычисления V22 ba + 0 и V21 b2. Значениеу 1 vn bi di с первого выхода первого вычислительного блока 3.1 поступает на первый информационный

вход первого выходного буферного блока 14.1 памяти и Запоминается в нем.

Во второй половине такта «з записывается в первый регистр 19, d2 di/(1 - «5) - в первый выходной регистр 29, 1/d2 - в

четвертый регистр 30, det 1/di - в пятый регистр 31 блока 4 вычисления диагональных элементов.

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

информационные входы блоков 2 предварительного вычисления подается ссз. В первом блоке 2.1 предварительного вычисления вычисляются pi pa + «3 Q1, vai pi-qi qi + +«з р2, vsa qi. во втором блоке 2.2 предварительного вычисления - pi Р2 + CKyqi, V32 pi, qi qi + озр2, V32 qi, в первом вычислительном блоке 3.1 - pi р2 + оз qi, 91-rqi + Оз«р2, зз qi, во втором вычислительном блоке 3.2 - pi P2+ Gsqi, Ьз Pi, qi qi+ «з р2.

С второго выхода второй группы и с первого выхода второго вычислительного блока 3.2 соответственно значения V22D2 и V21D2 поступают соответственно на второй информационный вход второй группы и первый информационный вход второго выходного буферного блока 14.2 памяти и запоминаются в нем.

Затем значения V21 02 и V22b2 из второго 14.2 и из первого 14.1 выходных буферных блоков памяти, пройдя через коммутатор 11, поступают соответственно на второй информационый вход второй группы, первый информационный входи второй информационный вход первой группы первого входного буферного блока 13.1 памяти и запоминаются в нем. На первый и второй ин- формационные входы первого вычислительного блока 3.1 подаются d2H V22 02 и вычисляется у 2 V22 b2 d2. На вторые информационные входы первой, второй и третьей групп первого вычислительного блока 3.1 поступают соответственно d2. у 1,

V21, Ь2 И ВЫЧИСЛЯеТСЯ у 1 у I + V2l D2 d2.

Третий такт. В первой половине такта в выходные блоки 8, 9, 14.1 и 14.2 памяти осуществляется запись результатов, полученных на выходах соответствующих вычислителей 2 и 3. На первый и второй выходы первого выходного блока 8 памяти подаются соответственно pi V31 и qi УЗЗ, на первые выходы первой и второй групп второго выходного блока 9 памяти - pi V32 и qi V32, первого выходного буферного блока 14,1 памяти - pi и qi зз, второго выходного буферного блока 14.2 памяти - pi Ьз и qi.

Во второй 25 и третий 26 регистры блока 4 вычисления диагональных элементов записываются соответственно 1 -аз1 и 1/d2 с выходов мультиплексоров 22 и 23. Во втором умножителе 27 и втором блоке 28 деления вычисляется ds d2/(1 - О- з ). Во второй выходной регистр 33 записывается промежуточное значение определителя deto 2 1/(di d2) матрицы Ф. На входы второго буферного блока 13.2 памяти подаются и

запоминаются в нем следующие значения: Р1 - vsi на первый информационный вход с первого выхода блока 8, код О на первый и второй информационные входы первой группы через коммутатор 12с третьего выхода блока 10 памяти констант, qi УЗЗ и pi V32 соответственно на первый и второй информационные входы второй группы через коммутатор 12с второго выхода блока 8 памяти и с первого выхода первой группы блока 9 памяти. На первый, второй информационные входы второй и третьей групп второго вычислительного блока 3.2 с одноименных выходов соответственно первой и второй групп блока 13.2 подаются коды О, О и УЗЗ, V32. На первый и второй информационные входы первой группы, первый информационный вход блока 3.2 подается Ьз, на второй информационный вход которого подается V31. Во втором вычислительном блоке 3.2 вычисляются vss Ьз + О, V32 Ьз + О и vsi Ьз. Значения у и у подаются соответственно на второй информационный вход второй группы и первый информационный вход первого выходного буферного блока 14.1 памяти.

Во второй половине такта ds d2/(1 - « § ) записывается в первый выходной регистр 29,1/ds - в четвертый регистр 30, detO® 1/(drd2) - в пятый регистр 31 блока 4 вычисления диагональных элементов, в третьем умножителе 32 которого вычисляется detO deto 3 1 /(dfd2 ds). Значения УззЬз, vs, V32 Ьз и vsi Ьз подаются соответственно на первый, второй информационные входы второй группы и первый информационный вход второго выходного буферного блока 14.2 памяти и запоминаются в нем. Затем в соответствии с алгоритмом функционирования блока 1 синхронизации vsi 031, V32 Ьз и vss Ьз, поступающие через коммутатор 11 на первый и второй информационные входы второй группы, первый информационный вход первого входного буферного блока 13.1 памяти, запоминаются в нем. Значения и через коммутатор 11 подаются на первый и второй информационные входы первой группы блока 13.1 памяти и запоминаются в нем, В первом вычислительном блоке 3.1, на первый, второй информационные входы второй и третьей групп которого поданы значения с соответствующих выходов первой и второй групп первого входного буферного блока 13.1 памяти и на первый, второй информационные входы первой группы через коммутатор 11 и первый информационный вход подано d3 с второго выхода блока 4 вычисления диагональных элементов, вычисляются

,,( )п V32- J3 Ьз + У 2 У2,

2 : V

™- vss bs ds

:уз.

Четвертый такт. В первой половине такта во второй выходной регистр 33 блока А вычисления диагональных элементов записывается detO 1/(drd2 d3). На первом, втором выходах второй группы и первом выходе первого выходного буферного блока 14.1 памяти получены компоненты вектора решения системы уравнений yi, у2 и уз, поступившие на соответствующие информационные входы блока.

В результате сравнения кода 4 (в общем случае М+1), поступающего с первого выхода блока 10 памяти констант на информационный вход блока 1 синхронизации, с номером такта работы устройства в момент времени, определенный алгоритмом функционирования блока 1 синхронизации, формируется признак завершения работы устройства.

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

В рассмотренном варианте работы устройства что справедливо для любого нечетного М, имеется избыточность вычислений (каждое из значений V22 и V32 получаем одновременно на двух независимых выходах устройства), которая отсутствует при четных М.

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

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

синхронизации, выход которого подключен к адресному входу первого коммутатора и входам синхронизации первых входного и выходного буферных блоков памяти, отличающееся тем, что, с целью расширения функциональных возможностей путем вычисления определителей исходной матрицы, обратной матрицы и их сомножителей при одновременном сокращении аппаратурных затрат при обработке симметричных теплицевых матриц, устройство содержит группу коммутаторов, I входных и I выходных блоков памяти (I М/2 для М четных и (М + 1)/2 для М нечетных), I блоков предварительных вычислений, второй коммутатор, вторые входной и выходной буферные блоки памяти, второй вычислительный блок, блок вычисления диагональных элементов, причем объединенные первые информационные входы 1-х (,1) коммутаторов группы подключены к первому информационному входу блока вычисления диагональных эле- иментов и второму выходу блока памяти констант, третий выход которого подключен к первому информационному входу первого входного блока памяти, второму информационному входу j-ro коммутатора группы (J 2, I), первому информационному входу второго коммутатора, выход первого коммутатора группы подключен к второму информационному входу первого входного блока памяти, первый и второй выходы которого подключены к соответствующим информационным входам первого блока предварительных вычислений, первый и второй выходы которого подключены к соответствующим информационным входам первого выходного блока памяти, первый и второй выходы которого подключены соответственно к первому информационному входу второго входного буферного блока памяти, объединенному с первым выходом первой группы устройства, и второму информационному входу второго коммутатора, объединенному с вторым выходом первой группы устройства и вторым информационным входом первого коммутатора группы, m-й выход первой группы и к-й выход второй группы j-ro выходного блока памяти (т 1, j; к 2, j) подключены соответственно к m-му информационному входу первой группы и к-му информационному входу второй группы j-ro коммутатора группы, т-е выходы первой и второй групп которого подключены к соответствующим информационным входам первой и второй групп j-ro входного блока памяти, т-е выходы первой и второй групп которого подключены к соответствующим информационным входам первой и второй групп j-ro блока предварительных вычислений, т-е выходы первой и второй групп которого подключены к соответствующим информационным входам первой и второй групп j-ro выходного блока памяти, первый выход которого подключен к 0+1)-му выходу первой группы устройства и (j + 2)-му информационному входу второго коммутатора, m-й выход первой группы j-ro выходного блока памяти подключен к m-му выходу первой группы выходов устройства и m-му информационному входу (j + 2)-й группы второго коммутатора, объединенные третьи информационные входы i-x предварительных вычислителей подключены к первому выходу блока вычисления диагональных элементов, первому и третьему информационным входам соответственно первого и второго коммутаторов, первый информационный вход первой группы устройства подключен к второму информационному входу первого коммутатора, р-й (Р 1,...,М) информационный вход первой группы устройства подключен к р-му информационному входу первой группы входов второго коммутатора, r-й (г- 1, М-1) выход первой группы которого подключен к r-му информационному входу первой группы второго вычислительного блока, r-й выход первой группы которого подключен к r-му информационному входу первой группы второго выходного буферного блока памяти, первый выход и r-й выход первой группы которого подключен соответственно к первому информационному входу второго вычислительного блока и r-му информационному входу второй группы второго коммутатора, r-й информационный вход третьей группы которого подключен к r-му выходу второй группы второго выходного буферного блока памяти и r-му информационному входу второй группы первого коммутатора, г-й выход первой группы первого вычислительного блока подключен к r-му информационному входу первой группы первого выходного буферного блока памяти, р-й информационный вход второй группы устройства подключен к одноименному информационному входу третьей группы первого коммутатора, первый и второй информационные входы второй группы устройства подключены к одноименным информационным входами первой группы блока вычисления диагональных элементов, второй выход которого является первым выходом устройства, объединенный с первым информационным входом первого вычислительного блока и третьим информационным входом первого коммутатора, второй информационный вход первой группы входов которого подключен к второму информационному входу блока вычисления диагональных элементов, третий информационный вход которого подключен к первому выходу второй группы первого выходного буферного блока памяти, r-й выход второй группы которого подключен к r-му выходу (I + 1)-й группы устройства и r-му информационному входу четвертой группы первого коммутатора, четвертый информационный вход которого подключен к первому выходу первого выходного буферного блока памяти и второму выходу устройства, первый информационный вход первого входного буферного блока памяти подключен к первому выходу первого коммутатора, r-е выходы второй и третьей групп о-го (о 1, 2) коммутатора подключены к г-м информационным входам соответственно первой и второй групп о-го входного буферного блока памяти, г-й выход первой и второй групп и первый выход которого подключены соответственно к r-м информационным входам второй и третьей групп и второму информационному входу о-го вычислительного блока, r-й выход второй группы и первый выход которого подключены соответственно к г-му информационному входу второй группы и первому информационному входу о-го выходного буферного блока памяти, первый выход второго выходного буферного блока памяти подключен к пятому информационному входу первого коммутатора, третий выход блока вычисления диагональных элементов является третьим выходом устройства, выход блока синхронизации подключен к объединенным синхровходам i-x входных и выходных блоков памяти, входам синхронизации блока вычисления диагональных элементов, вторых входного и выходного буферных блоков памяти и адресным входам i-ro предварительного коммутатора и второго коммутатора, причем каждый блок предварительных вычислений выполнен с возможностью реализации следующих функций:

/ш

Х з.

вх

Y

/1+1

вых У вха + хЛх,

где X вх и У вх - значения соответствнено на информационных входах первой и второй групп на -ом такте;

Х +1вых и У +1вых - значения на выходах соответственно первой и второй групп на (j + 1)-м такте;

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

вых вх А + .Увх,

-

Ј

Увых УвХ А + Хвх,

а Ь-с,

-г -

где Хвх и Увх - значения на информационных входах блока соответственно второй и третьей групп;

Хвых и Увых - значения на выходах блока соответственно первой и второй групп; А значение на информационных входах первой группы;

a, b и с - значения соответственно на выходе, первом и втором информационных входах вычислительного блока.

2. Устройство поп. 1,отличающее- с я тем, что блок вычисления диагональных элементов содержит пять мультиплексоров, первый и второй узлы деления, элемент НЕ, пять регистров, три умножителя, вычита- тель, первый и второй выходные регистры, причем первый и второй информационные входы первой группы блока соединены соответственно с объединенными первыми информационными входами второго и третьего мультиплексоров и первым информационным входом первого мультиплексора, второй информационный вход которого соединен с вторым информационным входом блока, третий информационный вход которого соединен с вторым информационным входом второго мультиплексора, выход которого соединен с входом делителя первого узла деления, вход делимого которого соединен с выходом первого мультиплексора, выход первого узла деления - с входом элемента НЕ, выход которого соединен с информационным входом первого регистра, выход которого соединен с первым выходом блока и объединенными первым и вторым входами первого умножителя, выход которого соединен с входом вычитаемого вычитате- ля, вход уменьшаемого которого соединен с первым информационным входом блока.

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

7 HiaWis

20

TEHta

Jr

26

r-

%

П Пгп

14 - 32

L i