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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 9) (11) 3446 А 1 51)5 6 06 НИЕ ИЗОБРЕТМУ СВИДЕТЕЛЬСТВУ ДВТОРСКО К,скийво ССС47, 1989во ССС ОЖЕНИЯ МАТ- к вычислитель- использовано в лительных мастра,тель,л задержки на матор, триггер тактов, умножируппу элементов ОСУДАРСТВЕННОЕ ПАТЕНТНОЕВЕДОМСТВО СССРГОСПАТЕНТ СССР)(54) УСТРОЙСТВО ДЛЯ УМ(57) Изобретение относитсяной технике и может бытьспециализированных вычи Изобретение относится к вычислительной технике и может быть использовано вспециализированных вычислительных машинах и устройствах обработки сигналов.Известно устройство для умножения(пхп)-матриц, содержащее Зп(и - размерность перемножаемых матриц) вычислительных модулей, причем каждыйвычислительный модуль содержит четыререгистра, умножитель, сумматор и узел задержки на и+1 тактов,Недостатками этого устройства я вляются большой обьем оборудования (Зпвычислительных модуля) и низкоебыстродействие время перемножения двухматриц равно Зп +4 птактов),Наиболее близким по технической сущности к изобретению является устройстводля умножения лхп матриц, содержащее 2 п 1 вычислительных модулей. причем каждыйвычислительный модуль содержит три регишинах и устройствах обработки сигналов для умножения (пхп)-матрицы на вектор, Цель изобретения - сокращение аппаратурных затрат, Цель достигается тем, что устройство содержит и) вычислительных модулей первого типа и вычислительнь 1 й модуль второго типа, причем вычислительный модуль первого типа содержит пять регистров, умножитель, сумматор, триггер и элемент И, а вычислительный модуль второго типа содержит п+1 регистров, сумматор, триггер и группу элементов И, Умножение (пхп)-матрицы на вектор осуществляется с помощьюфиксированного числа Гп вычислительных модулей (Гпи). 2 ил. 1 табл,Недостатком такого устройства являет- Д ся большой объем оборудования за счет О большого числа вычислительных модулей - ( ) 2 п, а также большого числа выходов - (2 п- р1), и)-разрядных выходов, где гп - разрядность элементов матрйц.Цель изобретения - сокращение объема оборудования устройства.Цель достигается тем, что устройство для умножения матриц Аьа х Вах,) содержит 0 вычислительных модулей 7, причем первый 1, второй 2 и третий 3 информационные входы, первый 4 и второй 5 настроечные входы устройства подключены соответственно к первому, второму, третьему информационным входам, к первому и второму настроечным входам первого вычислительного модуля 71, первый, второй и третий информационные выходы, первый и второйнастроечные выходы 71-го вычислительного модуля ( = 1, 0-1) подключены соответственно к первому, второму и третьему информационным входам, к первому и второму настроечным входам 71 н)-го вычислительного модуля является выходом 8 устройства, синхровход которого подключен к синхровходам всех вычислительных модулей 7. Каждый вычислительный модуль 7 выполнен с возможностью реализации функцийн эвых = аЬхи +г Ьвых = Ььх г аьх Ььх если+г р, , Свыше = Сьх + аьх Ььх если,нэ первом, втором, третьем информационных входах вычислительного модуля на 1-м такте;твх и бвх - соответственно значения на первом и втором настроечных входах вычислительного модуля на 1-м такте;эвых, Ьвых, Свых - соответственно значения на первом, втором, третьем информационных выходах вычислительного модуля на 1-м такте;т"вх = 6 вх - соответственно значения на первом и втором настроечных выходах вычислительного модуля на 1-м такте;р - параметр, определяемый алгоритмом(р = б; 0-1);О = вэх (Л, СЦ - параметр, определяе мый размерностью матриц.Нэ фиг, 1 показана структурная схема устройства для умножения матриц; на фиг. 2 - пример вычислительного модуля,Устройство для умножения матриц (фиг. 1) содержит первый 1, второй 2 и третий 3 информационные входы, первый 4 и второй 5 настроечные входы, синхровход 6, вычислительные модули 7 ( = 1, С и выход 8,Вычислительный модуль 7 (фиг, 2) содержит первый 9, второй 10 и третий 11 информационные входы, первый 12 и второй 13 настроечные входы, синхровход 14, умножигель 15, сумматор 16, регистры 17, 18, 19, 20, 21 ( = 1, 0) и 22 (1: 1, О+2), триггеры 23, 24, 25 и 26, группы элементов И 27, 28 и 29, группу элементов ИЛИ 30, элемент НЕ 31, первый 32, второй 33 и третий 34 информационные выходы, первый 35и второй 36 настроечные выходы.В нову рабятц положен алгоритмС = О,= 1, 1,=- 1, );5 С=Ск )+аж Ьц, 1=1, 1,) =1,А==1, С 1;С 1)= С 1, 1=1,1,) =1,).Вычислительный модуль 7 работает вчетырех режимах, которые задаются значе 10 ниями управляющих сигналов т и тг, подаваемыми на настроечные входы 12 и 13соответственно. На выходах 35 и 36 управляющие сигналы й и тг выдаются с задержкой на два такта.В первом режиме работы т, Тг =(1,1)на входы 9, 10 и 11 подаются соответственно элементы С, а и Ь. При этом элемент Сзаписывается в регистр 17, элемент а - врегистры 18 и 19 (группа элементов И 2720 открыта при т 1 = 1) и элемент Ь - в регистры211 и 221 (группа элементов И 29 открытапри гг = 1), На выходе умножителя 15 формируется значение а Ь, на выходе сумматора 16 - значение (С+ а Ь), которое выдаетсяна выход 32 с задержкой на один такт. Элемент а выдается на выход 33 с задержкой наодин такт, а элемент Ь - на выход 34 сзадержкой на О+2 тактов,Во втором режиме работы т 1, тг = (0,1)аналогичным образом подаются элементыС, а и Ь, При этом элемент С записываетсяв регистр 17, элемент а - в регистр 18, элемент Ь - в регистры 211 и 221, из регистров21 и 22 ( = 1, О+1) элементы записьваютсяв регистры 21(н.) и 22(м) соответственно. Нэвыходе умножителя 15 формируется значение а Ь, где элемент а был записан в регистр 19 ранее при подаче т 1 = 1, на выходе40 сумматора 16 формируется значениеС + а Ь, которое выдается на выход 32 сзадержкой на один такт,В третьем режиме работы г 1,тг =(1,0)аналогично подаются элементы С, а и Ь. При45 этом элемент С записывается в регистр 17,элемент а - в регистры 18 и 19 (группа элементов И 27 открыта), элемент Ь - в регистр. 221, элемент Ь (записанный в регистре 21 о)переписывается через открытую группу эле 50 ментов И 28 и группу элементов ИЛИ 30 врегистр 211, элементы из регистров 21 и 22( = 1, 0-.1) переписываются соответственнов регистры 21 р+) и 22(н.), на выходе тумножителя 15 формируется значение (а Ь ), на вы 55 ходе сумматора 16 - значение С + а Ь.которое через регистр 20 выдается на выход 32.В четвертом режиме работы т, тг =1793446 гистре 19 при т =-1, подается на вход умножителя 15, на второй вход котоого подается через регистр 211 элемент Ь, На выходесумматора 16 формируется значение(С + а Ь ), Из регистров 21 и 22 осуществляется перезапись элементов соответственно в регистры 21(+1) и 2(н.),Организация входного потока элементов а 1, Ь и С( управляющих сигналовт и т 2 выходного потока элементов С задается известными выражениями.Элементы аа подаются на вход 2 в моменты временит, = О 1+ 1+2+ 1 о,1-1,1, 1=1,0,где то = (О - 2) О - 2, О = вах (,/, О).Элементы Ьц подаются на вход 3 в моменты временить,1=/-О 1+2 О+2+Ь,/=1,А М=1,0,Элементы С = О 1+ /+ 2+ то,1= 1,1, /=15Управляющий сигнал г 1 = 1 подаетсяна вход 4 в моменты времени1 г = О -+ 3 + то, 1- 2-0,1,в остальные моменты подаются т = О.20Управляющий сигнал т 2 - 1 подается на .вход 5 в моменты времени1 Г 2=/+ О+2+1 о,/ =1,0,в остальные моментыподаются т 2 = О.На выходе 8 устройства формируются 25элементы С в моменты временитс 1= О -1+/+ 20+ 1+ то,Рассмотрим работу устройства для случая=,/ = 2 и 0 =3. Состояния триггеров 2330 Формула изобретения Устройство для умножения матриц, содержащее 0 вычислительных модулей, где 0 - целое число, 0И, й - линейный размер квадратных матриц, причем первый и второй информационные входы и первый вход задания режима устройства подключены соответственно к первому и второму информационным входам и к первому входу задания режима первого вычислительного модуля, первый, второй и третий входы 1-го вычислительного модуля, где = 1, , 0-1, подключены соответственно к первому и второму информационным входам и к первому входу задания режима (1+1)-го вычислительного модуля, четвертый выход 0-го вычислительного модуля подключен к выходу результата устройства, синхровход которого подключен к синхровходам всех вычислительных модулей, о т л и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат,и 25, регистров 17, 18, 29, 20, 21, 21 з 22 и 225, значения на выходе сумматора 16 вычислительных модулей 7 ч, 72 и 7 з и значения на выходе 8 устройства приведены в таблице, В данном случае элементы аа, Ь и Сц подаются в моменты временитац= 31+ 1 с + 3, 1 = 1,2, 1 с = 1,3;1 ь,= / - 31 + 9, К = 1,3, / = 1 2;т/= 31+/+ 3,= 1,2, / = 1,2.Значения результирующей матрицы формируются в моменты временитс 1=3+/+ 8.Время вычисления последнего элемента Соо равно ( + 0 - 2) О + 20 +- 1 тактам, В данном случае элемент С 22 формируется на 16-м такте (см. таблицу),Период ввода элементов для умножения последующих матриц А и В равен ( + 0-1) Отактам.Таким образом, предлагаемое устройство содержит меньший объем оборудования по сравнению с прототипом, т.е. содержит и вычислительных модулей для=. = и), а прототип - 2 пвычислительных модулей (основу оборудования вычислительных модулей составляют умножитель и сумматор). Кроме того, предлагаемое устройство содержит меньшее число выводов (один а- разрядный выход, гп - разрядность элементов матриц), а прототип - (2 п) щразрядных выходов, что существенно при проектировании устройства на основе сверхбольших интегральных схем. третий информационный вход и второй вход задания режимаустройства подключены соответственно к третьему информационному и к второму входу задания режима первого вычислительного модуля, четвертый и пятый выходы 1-го вычислительного модуля подключенысоответственно к третьему информационному входу и к второму входу задания режима (+1)-го вычислительного модуля, причем каждый вычислительный модуль содержит четыре регистра, два сдвигающих регистра, умножитель, сумматор, четыре триггера, три блока элементов И, блок элементов ИЛИ и элемент НЕ, при этом в каждом вычислительном модуле первый информационный вход вычислительного мод,ля подключен к информационному входу первогО регистра, выход которого подключен к первому информационному входу сумматора, выход которого подключен х информационному входу второго регистра, вы1793446 ершист ход которого подключен к первому выходу вычислительного модуля, второй информационный вход которого подключен к информационному входу, третьего регистра и к первому входу первого блока элементов И, выход которого подключен к информационному входу четвертого регистра, выход которого подключен к первому информационному входу умножителя, выход которого подключен к второму инфор.мационному входу сумматора, выход третьего регистра подключен к второму выходу вычислительного модуля, третий информационный вход которого подключен к информационному входу первого сдвигаю- щего регистра и к первому входу второго блока элементов И. выход которого подключен к первому входу блока элементов ИЛИ, выход которого подключен к информационному входу второго сдвигающего регистра, информационный выход и выход переноса которого подключены соответственно к второму информационному входу умножителя и к первому входу третьего блока элементов И, второй вход и выход которого подключены соответственно к выходу элемента НЕ и к второму входу блока элементов ИЛИ, первый вход задания режима вычислительного модуля подключен к второму входу первого блока элементов И и к информационному входу первого триггера, выход которого подключен к информационному входу второго триггера, выход которого подключен к третьему выходу вычислительного модуля, четвертый выход которого подключен к выходу переноса первого сдвигающего регистра, второй вход задания режима вычислительного модуля подключен к второму входу второго блока элементов И, к входу элемента НЕ и к информационному входу третьего триггера, выход которого подключен к информационному входу четвертого триггера, выход которого подключен к пятому вьходу вычислительного модуля, синхровход которого подключен к входам синхронизации всех триггеров, к входам сдвига первого и второго сдвигающих регистров и к входам записи-считывания всех регистров.1793446 аФиг а;еиг.2Составитель В. Смирнов едактор С. Кулакова Техред М,Моргентал Корректор М, Ткач аказ 505 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб 4/5Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 1