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

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

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

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

Устройство для умножения матриц (фиг. 1) содержит Р блоков памяти 1.1-1.6, Р регистров 2.1-2.6 второй группы, Р двухвходо- вых сумматоров 3.1-3.6, Р регистров 4.1-4.6 первой группы, LB многовходовых сумматоров 5.1, 5.2, LA мультиплексоров б, 1-6.3 и блок 7 памяти.

Блок 7 (фиг, 2) управления содержит триггеры 8 и 9, счетчик 10, элемент ИЛИ 11, элемент И 12, генератор 13 тактовых импульсов, элементы 14 и 15 задержки.

Временные диаграммы (фиг. 3) содержат:

текущий код Si (фиг. За) на выходе счетчика 10,

импульсы (фиг, 36) на четвертом выходе блока 7,

импульсы (фиг. Зв) на выходе элемента И 12,

импульсы (фиг. Зе) на первом выходе блока 7.

Принцип действия устройства состоит в следующем (фиг. 1).

Перед началом вычисления произведения матриц А и В в регистры 2 записывают элементы матрицы В. В примере, показанном на фиг. 1, матрица А содержит три столбца, а матрица В - два столбца, и согласно правилу сцепления матриц три строки: всего шесть элементов. Элементы каждого столбца bn, 021, Ьз1 и bi2. b22, Ьз2 записывают а регистры 2 второй группы. Запись осуществляют по фронту импульса WR с управляющего входа устройства, также в блоки 11 - 16 по n-му адресу записывают числа nbti, nbai, пЬзь nbi2. nb22 и пЬз2 соответственно, причем п 0. N - 1. N - число адресов блоков 1 памяти. В свою очередь, N 2Г, где г - разрядность операндов А (элементов, представленных в двоичном коде, матрицы А. Например, в блок 1.1 памяти записывают числа 0. bn, 2bn 3bn-. .... (2Г - - 1)Ьц. Всего 2Г|слов. Осуществляют указанное следующим образом.

По импульсу записи WR блок 7 управления подает на управляющие входы мультиплексоров 6 сигнал высокого логического

уровня, приводящий к коммутации на выход мультиплексоров 6 их объединенные информационные входы, на кото рые с того же блока 7 подается код текущего адреса (фиг. 2 и

За) блоков 1 памяти. Функции адресного счетчика выполняет счетчик 10 блока 7. В исходном состоянии на адресных шинах блоков 1 выставлен нулевой адрес и блоки 1 находятся в режиме чтения. Управление режимом Запись/чтение осуществляет также блок 7, кроме того, предполагается, что блоки 1 памяти обнулены. Т.о. в рассматриваемом, примере на входы сумматора 8.1 подаются операнды: нуль и bn: их сумма bn

по переднему фронту импульса с выхода генератора 13 (фиг, 2 и 3) записывается в регистр 4.1 и подается затем на информационный вход блока 1.1 памяти. Через время туказанный импульс, пройдя элемент 14

задержки, поступает на счетный вход счетчика 10 и формирует код адреса с номером один (фиг. За. в). Блок 1.1 памяти, все еще находящийся в режиме чтения, через время г после смены состояния счетчика 10 переходит в режим записи (фиг. 26). В результате по первому адресу записывается ранее вычисленная сумма Ь11. Далее, после того как вершина импульса на выходе, элемента 15 (фиг. 26) полностью сформируется, блок 1.1

переходит в режим чтения, причем по прежнему адресу, Считанный операнд bn про- суммируется также с bn и результат 2Ьц с приходом следующего тактового импульса зафиксируется в регистре 4.1, а позже через

время г запишется в блок 1.1 по второму адресу. Аналогично вычисляются и записываются величины ЗЬц, 4bn, ..., (2r- 1)bn,

Рассмотренные операции совершаются параллельно для всех блоков 1 памяти над

соответствующими элементами матрицы В. В итоге через (2Г - 1) тактов в блоки 1 будут записаны возможные произведения эле- ментов-матрицы А на определенные согласно правилу умножения матриц элементы

матрицы В. После записи последнего произведения импульс переполнения счетчика 10 переводит в нулевое состояние триггер 8, в связи с чем прекращается формирование текущих адресов Si и на адресные входы

блоков 1 памяти мультиплексируются входы элементов матрицы А. Устройство готово к умножению матриц.

Элементы матрицы А подают построчно через мультиплексоры 6 на адресные входы

блоков 1 памяти. Извлекаемые при этом из памяти ранее записанные произведения суммируются сумматорами 51 и 52, вычисляя один элемент матрицы произведения С. Структурная организация устройства такова, что при поступлении на входы устройства пл-ой строки матрицы А на выходах устройства формируется m-ая строка матрицы произведения С. Отмеченное иллюстрируется показанным у входов и выходов устройства порядком элементов матриц А и С. Так, строке с элементами а.и, aia, 313 отвечает строка Си, Ci2. строке агт. ааа, агз - строка

С2.1..С22ИТ.Д.

Время задержки элемента 14 не должно быть меньше длительности переходного процесса, связанного с записью информации в регистры 14; время задержки элемента 15 должно быть достаточным для завершения переходных процессов в блоках 1 памяти при смене адресов (время выборки). Например, в случае ТТЛ Ш т может быть выбрано как 50 и 150 не для элементов. 14 и 15 соответственно.

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

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

Устройство для умножения матриц, содержащее Р блоков памяти (Р LA x LB. где LA - число столбцов матрицы A, LB - число столбцов матрицы В), две группы по Р регистров каждая, Р двухвходовых сумматоров и блок управления, причем первый вход 1-го двухвходового сумматора 0 1, Р) соединен

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

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

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

этом информационный вход i-ro блока памяти соединен с выходом i-ro регистра первой группы, второй вход i-ro двухвходового сумматора соединен с выходом 1-го регистра второй группы, входы j-ro многовходового

сумматора (j 1, .... LB) соединены соответственно с выходами k-x блоков памяти (k 1, .... LA) j-й группы, адресный вход k-ro блока памяти в каждой J-й группе соединен соответственно с выходом k-ro мультиплексора, первый информационный вход которого соединен с входом соответствующего элемента матрицы А устройства, выходы результата которого соединены с выходами LB многовходовых сумматоров, второй выход

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

входом режима работы всех Р блоков памяти, управляющий вход и вход сброса устройства соединены соответственно с входами установки и сброса блока управления.

Изобретение относится к вычислительной технике и может быть использовано в задачах обработки информации для перемножения матриц исследуемого и опорного сигналов. Цель изобретения - сокращение аппаратурных затрат за счет снижения объема памяти. Устройство содержит Р блоков 1 памяти. Две группы по Р регистров 2 и 4, Р двухвходовых сумматоров 3, многовходо- вые сумматоры 5, мультиплексоры 6 и блок 7 управления, Устройство выполняет перемножение матриц табличным способом. Снижение объема памяти достигнуто за счет записи в блоки памяти не всевозможных произведений элементов матриц А и В, как в аналогичных известных устройствах,, а лишь только результатов умножения каждого элемента матрицы В на 2Г операндов, где г - разрядность элементов матрицы А. Причем указанные 2Г операндов равны для всех элементов матрицы В. 3 ил.

Г

cpus.Z

Т

J

фи&З