Устройство для умножения матриц
Изобретение относится к вычислительной технике и может быть использовано в задачах обработки информации для перемножения матриц исследуемого и опорного сигналов. Цель изобретения - сокращение аппаратурных затрат за счет снижения объема памяти. Устройство содержит Р блоков 1 памяти. Две группы по Р регистров 2 и 4, Р двухвходовых сумматоров 3, многовходовые сумматоры 5, мультиплексоры 6 и блок 7 управления, Устройство выполняет перемножение матриц табличным способом. Снижение объема памяти достигнуто за счет записи в блоки памяти не всевозможных произведений элементов матриц А и В, как в аналогичных известных устройствах,, а лишь только результатов умножения каждого элемента матрицы В на 2Г операндов, где г - разрядность элементов матрицы А. Причем указанные 2Г операндов равны для всех элементов матрицы В. 3 ил.
COIO3 СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК
ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4919127/24 (22) 13,03.91 (46) 07.04.93. Бюл. ¹ 13 (71) Радиотехнический институт им. акад. А,Л,Мин ца (72) Г,Р.Аванесян, В.Б,Антоненков и . Г.А,Айдаров (56) Авторское свидетельство СССР N 1471201, кл. G 06 F 15/347, 1987. Авторское свидетельство СССР ¹ 1418749, кл. G 06 F 15/347, 1987. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТРИЦ (57) Изобретение относится к вычислительной технике и может быть использовано в задачах обработки информации для перемножения матриц исследуемого и опорного аФ ау/ „„5U ÄÄ 1807499 А1 сигналов. Цель изобретения — сокращение аппаратурных затрат за счет снижения объема памяти. Устройство содержит Р блоков 1 памяти, две группы по P регистров 2 и 4, P двухвходовых сумматоров 3, многовходовые сумматоры 5, мультиплексоры 6 и блок 7 управления, Устройство выполняет перемножение матриц табличным способом. Снижение объема памяти достигнуто за счет записи в блоки памяти не всевозможных произведений элементов матриц А и В, как в аналогичных известных устройствах, а лишь только результатов умножения каждого элемента матрицы В на 2" операндов, где r — разрядность элементов матрицы А. Причем указанные 2" операндов равны для всех элементов матрицы В, 3 ил. айаг r74S ал а. . 1807499 Изобретение относится к вычислительной технике и может быть использовано в задачах обработки информации для перемножения матриц исследуемого и опорного сигналов. 5 Цель изобретения — сокращение аппаратурных затрат устройства за счет снижения объема памяти. На фиг. 1 приведена функциональная схемаустройства(при Ед =3 и Lg=2); на фиг. "0 2 — функциональная схема блока управления; на фиг. 3 — временные диаграммы, иллюстрирующие работу устройства. Устройство для умножения матриц (фиг. 1) содержит P блоков памяти 1.1-1.6, Р ре- 15 гистров 2.1-2,6 второй группы, P двухвходовых сумматоров 3.1 — 3.6, P регистров 4.1-4.6 первой группы, Lg многовходовых сумматоров 5.1, 5.2, Ед мультиплексоров G,1-6.3 и блок 7 памяти. 20 Блок 7 (фиг, 2) управления содержит триггеры 8 и 9, счетчик 10, элемент ИЛИ 11, элемент И 12, генератор 13 тактовых импульсов, элементы 14 и 15 задержки. Временные диаграммы (фиг. 3) содер- 25 жат: текущий код Si (фиг. 3a) на выходе счетчика 10„ импульсы (фиг. Зб) на четвертом выходе блока 7, 30 импульсы (фиг. Зв) на выходе элемента И 12, импульсы (фиг. Зе) на первом выходе блока 7, Принцип действия устройства состоит в следующем (фиг. 1). Перед началом вычисления произведения матриц A u B в регистры 2 записывают элементы матрицы В. В примере. показанном на фиг, 1, матрица А содержит три стол- 40 бца, а матрица  — два столбца, и согласно правилу сцепления матриц три строки: всего шесть элементов. Элементы каждого столбца Ь11, Ь21, Ьз1 и b12, b22, b32 записывают sрегистры 2 второй группы,,Запись осу- 45 ществляют по фронту импульса WR c управляющего входа устройства, также в блоки 11 — 16 по п-му адресу записывают числа nb>>, nba, пЬз), nbiz. пЬ22 и пЬз2 соответственно, причем п = О, N - 1, N — число 50 адресов блоков 1 памяти. В свою очередь, N = 2", где r — разрядность операндов А (элементов, представленных B двоичном коде, матрицы А. Например. в блок 1.1 памяти записывают числа О. b1>. 2bii 3b»....„(2" - 55 - 1)Ь, Всего 2" слов. Осуществляют указанное следующим образом. По импульсу записи WR блок 7 уп равления подает на управляющие входы мультиплексоров 6 сигнал высокого логического уровня, приводящий к коммутации на выход ° мультиплексоров 6 их обьединенные информационные входы, на которые стого же блока 7 подается код текущего адреса (фиг. 2 и За) блоков 1 памяти. Функции адресного счетчика выполняет счетчик 10 блока 7, В исходном состоянии на адресных шинах блоков 1 выставлен нулевой адрес и блоки 1 находятся в режиме чтения, Управление режимом Запись/чтение осуществляет также блок 7, кроме того, предполагается, что блоки 1 памяти обнулены, Т.о. в рассматриваемом.примере на входы сумматора 8.1 подаются операнды: нуль и Ь 1; их сумма Ь11 по переднему фронту импульса с выхода генератора 13 (фиг, 2 и 3) записывается в регистр 4.1 и подается затем на информационный вход блока 1.1 памяти, Через время туказанный импульс, пройдя элемент 14 задержки, поступает на счетный вход счетчика 10 и формирует код адреса с номером один (фиг. 3а, в), Блок 1.1 памяти, все еще находящийся в режиме чтения, через время тпосле смены состояния счетчика 10 переходит в режим записи (фиг. 2б). В результате по первому адресу записывается ранее вычисленная сумма b11, Далее, после того как вершина импульса на выходе элемента 15 (фиг. 2б) полностью сформируется, блок 1.1 переходит в режим чтения, причем по прежнему адресу, Считанный операнд Ь просуммируется также с Ь и результат 2Ь с приходом следующего тактового импульса зафиксируется в регистре 4.1, а позже через время т запишется в блок 1.1 по второму адресу. Аналогично вычисляются и записываются величины ЗЬ|1, 4Ь, ..., (2 - 1)Ь, Рассмотренные операции совершаются параллельно для всех блоков 1 памяти над соответствующими элементами матрицы B. В итоге через (2" - 1) тактов в блоки 1 будут записаны возможные произведения элементов-матрицы А на определенные согласно правилу умножения матриц элементы матрицы В, После записи последнего произведения импульс переполнения счетчика 10 переводит в нулевое состояние триггер 8, в связи с чем прекращается формирование текущих адресов S; и на адресные входы блоков 1 памяти мультиплексируются входы элементов матрицы А. Устройство готово к умножению матриц. Элементы матрицы А подают построчно через мультиплексоры 6 на адресные входы блоков 1 памяти. Извлекаемые при этом из памяти ранее записанные произведения суммируются сумматорами 5 и 5, вычис1 ляя один элеменг матрицы произведения С, Структурная организация устройства тако1807499 1 к!! к пепкп7иппекее еп К &окал 7 WE/гЭ ва, что при поступлении на входы устройства m-ой строки матрицы А на выходах устройства формируется m-ая строка матрицы произведения С. Отмеченное иллюстрируется показанным у входов и выходов устрой- 5 ства порядком элементов матриц А и С, Так, строке с элементами а,11, а12, а1з отвечает строка С11, С12, строке а21, а22, а2з — строка с21 ° .С22 и т д Время задержки элемента 14 не должно 10 быть меньше длительности переходного процесса, связанного с записью информации в регистры 14; время задержки элемента 15 должно быть достаточным для завершения переходных процессов в бло- 15 ках 1 памяти при смене адресов (время выборки). Например. в случае ТТЛШ т может быть выбрано как 50 и 150 нс для элементов 14 и 15 соответственно. Технико-экономическая эффективность 20 объекта состоит в значительном снижении объема памяти. Действительно, для вычисления произведения двух целых r-разрядных двоичных чисел в устройстве-прототипе требуется иметь блоки памяти, в каждом из 25 которых содержится 2 " произведений. В заявляемом же устройства в блок памяти записывают всего 2" произведений. Несложно видеть, что выигрыш на один блок составляет 2" раз. 30 Формула изобретения Устройство для умножения матриц, содержащее P блоков памяти (P = LA х Lp, где Lg — число столбцов матрицы А, Lg — число столбцов матрицы В), две группы по P реги- 35 стров каждая, P двухвходовых сумматоров и блок управления, причем первый вход i-го двухвходового сумматора (i = 1, P) соединен с выходом i.го блока памяти, а выход — с информационным входом 1-го регистра первой группы, информационный вход i-го регистра второй группы соединен с входом соответствующего элемента матрицы устройства, синхровходы всех регистров первой и второй групп объединены и соединены с первым выходом блока управления, о т л ич а ю щ е е с я тем, что. с целью сокращения аппаратурных затрат за счет снижения объема памяти, в него введены Lg многовходовых сумматоров и LA мультиплексоров, причем блоки памяти объединены в Lg групп no LA блоков памяти в каждой, при этом информационный вход i-го блока памяти соединен с выходом i-го регистра первой группы. второй вход i-ro двухвходового сумматора соединен с выходом 1-ro регистра второй группы, входы j-го многовходоваго сумматора 0 = 1, ..., La) соединены соответственно с выходами k-х блоков памяти (k = =1..... (д) )-й группы, адресный вход k ro блока памяти в каждой j-й группе соединен соответственно с выходом k-ro мультиплексора, первый информационный вход которого соединен с входом соответствующего элемента матрицы А устройства, выходы результата которого соединены с выходами Lp многовходовых сумматоров, второй выход блока управления соединен с вторыми информационными входами всех LA мультиплексоров, управляющие входы которых соединены с третьим выходом блока управления, четвертый выход которого соединен с входом режима работы всех P блоков памяти, управляющий вход и вход сброса устройства соединены соответственно с входами установки и сброса блока управления. 1807499 5 су) О dJ () Я/ Составитель Е,Мурзина Техред M.Ìîðãåíòàë Корректор Е,Папп Редактор Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина. 101 Заказ 1381 Тираж . Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГК1-IT СССР 113035. Мбсква, Ж-35, Раушская наб.. 4/5