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

(Л

С

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

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

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

Наиболее элизким по функциональному назначению и конструктивно является устройство для обращения матриц 2J, содержащее информационные входы элементов

матрицы, сумматоров константы, коммутатор, содержащий пять блоков мультиплексора, вычислитель, буферный блок памяти, ключ выдачи, блок памяти констант и блок управления. Элементы исходной матрицы 3i) образуют первые информационные входы сумматоров констант, выход первой константы блока памяти констант подключен к вторым входам сумматоров константы, выход п сумматоров константы и информаци. онные входы элементов матрицы (. n; , п; 1 5 j) образуют первый информационный вход коммутатора, выход буферного блока памяти подключен к второму информационному входу коммутатора и к информационному входу ключа выдачи, третий и четвертый информационные входы коммутатора подключены к выходам второй и третьей константы блока памяти констант, входы промежуточных результатов уменьшаемых, первых и вторых сомножителей

VJ VI

00

VI

О Ю

вычислителя подключены к одноименным выходам коммутатора, вход кода управления и вход выбора которого подключены к одноименным выходам блока управления, выход выдачи результата которого подключен к входу стробирования информации ключа выдачи, выходы первой и второй константы блока памяти констант подключены к одноименным входам вычислителя соответственно, выход которого подключен к информационному входу буферного блока памяти, первый и второй входы записи которого подключены к прямому и инверсному выходам записи блока управления, вход константы которого подключен к выходу четвертой константы блока памяти констант. В данном устройстве для вычисления n-разрядной матрицы выполняется п шагов повторных вычислений, Для получения результата одного шэга необходимо выполнить три операции умножения, две операции сложения и операцию нахождения обратной величины. При этом для коммутации используется большое количество мультиплексоров. До начала пошаговых вычислений выполняется операция сложения на п сумматорах константы.

Недостатком устройства-прототипа является большое количество элементов и низкое быстродействие.

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

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

Изобретение обладает существенными

отличиями по сравнению с известными техническими решениями, поскольку совокупность отличительных признаков с известными признаками и их взаимосвязь

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

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

фиг. 5 -функциональная схема умножителя; на фиг. 6 - функциональная схема блока управления; на фиг. 7 - функциональная схема блока, объединяющего узел вычисления обратной величины числа, первый умножитель и группу умножителей; на фиг. 8 - функциональная схема второго умножителя; на фиг. 9 - функциональная схема группы сумматоров; на фиг. 10 - функциональная схема формирователя сигнала выбора; на фиг, 11 - временная диаграмма работы блока управления; на фиг. 12 - таблица результатов вычислений на выходах блоков на каждом шаге вычислений.

Устройство для обращения матриц (фиг. 1) содержит первый информационный вход 1 элементов матрицы, мультиплексор 2, вычислительный блок 3, блок 4 памяти, умножитель 5, ключ 6 выдачи, блок 7 памяти

констант, блок управления 8, выход 9 элементов обращенной матрицы, второй информационный вход 10 мультиплексора 2 и вход умножителя 5, вход 11 ключа выдачи 6, вход 12 вычислительного блока 3 (вход 12.а

узла вычисления обратной величины числа, вход 12.Ь умножителей группы, вход 12.с второго умножителя, вход 12.d сумматоров группы), шину 13 первой Константы, выход 14 вычислительного блока 3, шину 15

второй константы, выход 16 формирователя сигнала выбора, прямой и инверсный входы 17 и 18 записи блока 4 памяти, вход 19 выдачи результата ключа б выдачи и синх- ровход умножителя 5, разрешающий инвертировать результат.

Мультиплексор 2 выполнен по схеме, представленной на фиг. 2 с использованием мультиплексоров 45.

Вычислительный блок 3 (фиг. 3) содержит узел 46 вычисления обратной величины числа, первый умножитель и группу умножителей, объединенных в блок 20, второй умножитель 21, группу сумматоров 22, вход

23- первый вход первого умножителя, вход

24- первый вход умножителей группы, вход

25- первый вход второго умножителя, вход

26- первый вход сумматоров группы. Первый, второй умножители и группа умножителей содержат умножители 47, группа сумматоров содержит сумматоры 48.Блок памяти 4 (фиг. 4) содержит первый и второй регистры 27.

Блок управления 8 (фиг. 6) содержит генератор 28 тактовых импульсов, первый од- новибратор 29, триггер 30.1 запуска, триггер 30.2 выдачи, триггер 31 состояния, элемент И 32, элемент НЕ 33, второй одно- вибратор 34, счетчик 35, схема 36 сравнения и формирователь 37 сигнала выбора, вход 38 запуска блока 8 и устройства, выход 39 генератора 28, информационный вход 40 триггера 31, первый и второй входы 41, 42 элемента И 32, выход 43 схемы 36, счетный вход 44 счетчика 35, выход 51 счетчика 35,

Формирователь 37 сигнала выбора (фиг. 10) содержит элемент НЕ 49 и элемент И-НЕ 50.

В устройстве реализован алгоритм обращения матрицы на основе Ш-разложе- ния по методу цифра за цифрой. Пусть требуется обратить матрицу порядка п

А -

an ai2 ... ain

Э21 322 ... Э2п

Эп1 3П2 ... Эпп

Согласно алгоритму вычислительная определения имеет вид: VM x,j

z) Vik nriKj 2 V k

« 1k max {ij}

или для ,2... , n

..W :

..W,

X|Cn x«vftf ° (ii j -t);

xij() xij(t) - Vnmtj (i, j t);

Xij - Х,/П+1).

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

А

1 2 3 589 623

Покажем, что обратная ей матрица А будет вида

-0,2 00,2

-1.3 0.5 -0,2 1,27 -0,335 0.067

Работа устройства начинается с того, что исходная матрица А в виде последовательности ее элементов

156282393 поступает на первый информационный вход 1 мультиплексора 2. По сигналу на вход 38 внешнего запуска (фиг. 11) блока 8 управления счетчик 35 сбрасывается в нулевое состояние, переводится в нулевое состояние триггер 30.2 выдачи, закрывая ключ 6 выдачи и умножитель 5, который запрещает вывод информации из блока 4 памяти во время

вычислений, а также переводится в единичное состояние триггер 30.1 запуска, обеспе - чивая появления 1 на информационном входе триггера 31 состояния (фиг. 11). Перевод триггера 31 в единичное состояние происходит в момент появления на его счетном входе тактового импульса от генератора 28 тактовых импульсов. С выхода триггера 31 состояния 1 поступает на первый вход элемента И 32, обеспечивая происхождение

синхроимпульсов, поступающих на второй вход от первого одновибратора 29.

С выхода элемента И 32 синхроимпульсы поступают на вход второго одновибратора 34, формирующего импульсы по заднему

Фронту синхроимпульсов, которые являются счетными импульсами счетчика 35 Период следования синхроимпульсов выбирается из условия полного завершения одного шага вычислений. На первом шаге

вычислений с выхода счетчика 35 поступает в двоичном коде 1 на вход формирования 37 сигнала выбора, в соответствии с законом работы которого (фиг, 10) на его выходе на первом шаге формируется О. На последующих шагах на выходе 16 присутствует 1. Выход 16 является управляющим для мультиплексора 2, поэтому в соответствии с законом работы на его выход передается последовательность чисел с шины 1 присигнале на выходе 16, равном О (первый шаг вычислений), или последовательность чисел с шины 10 при сигнале на выходе 16, равном 1 (фиг. 2), т.е. на первом шаге на выходе мультиплексора 2 будет сформирована по

следовательность чисел

156282393, которая распределяется следующим образом: на вход 12.а узла вычисления обратной величины числа поступает элемент аи, на вход 12.Ь умножителей группы поступают

из которых выбираются числа.экий и складываются с числами aij (,n; ), постуэлементы 321, аз1аП1, на вход 12.с второго умножителя поступают элементы ai2. aia, ..., ain, на вход 12.d сумматоров группы поступают элементы aij(,n).

По входу 12.а узла вычисления обратной величины числа элементы матрицы ani, который для данного примера на первом шаге равен 1, преобразуется в обратную величину, поступает по входу 23 на первый умножитель и умножается , поступающую по шине 12 первой константы.

По шине 24 выхода первого умножителя число -1 поступает на группу умножителей и умножается с числами

5 б ...,

поступающими по входу 12.b из мультиплексора 2. На первом шаге на шину 25 входа второго умножителя поступают числа

-5 -6 -1 ....

где производится их взаимное перемножение с числами

2 3 ...

На шину 26 входа сумматоров группы поступает последовательность чисеЯ

-10 -12 -2 -15 -18 -3 -5 -6 -1, i числа ai-ij-i i (,n; ), лающими по шине 12.d из мультиплексора 2

На выходе группы сумматоров на первом шаге формируется последовательность чисел

-2 -10 -2 -6 -15 -3 -5 -6 -1, которая по шине 14 поступает на входы первого регистра 27 блока 4 памяти (фиг. 4), который служит для развязки между собой шагов вычислений и устранения эффекта гонок. Во время вычисления на каком-либо шаге на первый регистр 27 по выходу 17 поступает управляющий сигнал О с выхода элемента И 32 блока управления 8 (фиг. 5), разрешающий запись информации в данный регистр, в то время как по выходу 18 на второй регистр 27 поступает 1 с выхода элемента И-НЕ 33 блока управления 8, разрешая чтение информации из этого регистра. Период следования синхроимпульсов с выхода первого одновибратора 29 выбирается таким образом, чтобы за время существования низкого перепада напряжения на его выходе полностью завершилось вычисление на данном шаге и запись результата в первый регистр 27 (фиг. 11). При появле- нии высокого потенциала на выходе элемента И 32 на первый регистр 27 поступает 1, а на второй регистр - О, т.е. происходит перезапи&ь-ин фо рмации с первого регистра на второй. При появлении следующего синхроимпульса выдается разрешение на чтение результата из второго регистра 27.и на

запись результата следующего шага вычисления в первый регистр 27. Количество шагов вычислений равно порядку обращаемой матрицы (п). Результаты на выходах отдельных блоках для каждого шага приведены в таблице (фиг. 12).

На каждом шаге вычисления в схеме сравнения 36 происходит сравнение номера шага вычисления, поступающего с выхо0 да счетчика 35 и числа 4 (в общем случае п+1), поступающего по шине третьей константы 51 из блока 7 памяти констант. По окончании последнего третьего шага вычисления во второй регистр 27, блока 4 памяти

5 записывается последовательность чисел

0,2 1,3 -1,27 0 -0,5 0,335 -0,2 0,2 -0,067.

При появлении следующего четвертого

синхроимпульса на выходе элемента И 32

блока 8 управления на управляющий вход

0 второго регистра 27 блока 4 памяти поступает сигнал 1 разрешения чтения. Номер четвертого синхроимпульса поступает также на вход схемы сравнения 36, в результате чего на ее выходе формируется управляю5 щий импульс, который переводит триггер 30.2 в единичное состояние, тем самым разрешая открытие ключа 6 выдачи вместе с умножителем 5 (инвертирующим результат) и, соответственно, вывод результата, а так0 же перебрасывает в нулевое состояние триггеры 30 1 и 31, что соответствует запиранию блока 8 управления и окончанию вычисления.

Устройство решает задачу обращения

5 для матриц произвольной размерности.

Экспериментальные исследования устройства для обращения матриц показали, что по сравнению с устройством аналогичного назначения (прототип) оно упрощено

0 конструктивно и быстродействие повышается в 1.5 раза.

Формула изобретения 1. Устройство для обращения матриц, содержащее блок управления, ключ выдачи

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

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

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

/

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

Фиг. 1.

Q-nn

/2.a {2.6/2. с

Ul J

/3

an

f2 {&7#, c, cfj Фиг, 2.

J

25

26

0«g.J.

/4

/7

19

41

фш.5.

45

m

N

4

u

b

s

ч

Ci

lie

-g

-j

oo -j

CD tvj

fij

4v -NJ

kh

u

N

ft

5

л

JUULJLJLJULJI

Т-П-П П Л Л П Г