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

Изобретение относится к вычислительной технике, может быть использовано в специализированных вычислительных машинах и позволяет вычислять произведения квадратных матриц.Пель изобретения - повышение быстродействия устройства.На фиг. 1 представлена функциональная схема предлагаемого устройства; на фиг. 2 - то же, вычислительного блока.Устройство содержит информационные входы 1 первой группы, информационные входы 2 второй группы, входы 3 для задания кода нуля, тактовый вход 4, матрицу вычислительных блоков 5 и информационные выходы 6.В состав каждого вычислительного блока 5 входят три регистра 7, 8 и 9, блок 1 О умножения, сумматор 11, триггер 12 и (Т+1) элементов И 13, где Т - разрядность кода представления числовых компонентов перемножаемых матриц.Устройство работает следующим образом.В основу работы устройства положен алгоритм умножения матрицы А= а;11 на матрицу В=Ь; , определяющий матрицу С=1 с; (1=1,п; 1=1, ,п, где п - порядок квадратной матрицы): а .,Ь.,l Определение любого элемента С 1 требует и-кратного выполнения операции накопления+а, Ь. Особенностями функционирования устройства являются сдвиг накапливаемых сумм С на очередном такте работы из 1 Р-го вычислительного блока 5 (1=1,и; Р=1, ,и) в 1(Р+1)-й блок 5 и неподвижность элементовматрицы В.В исходном состоянии триггеры 12 и регистры 7-9 блоков 5 устанавливаются в нулевое состояние. На информационные входы 1 подаются по тактам соответствующие Т-разрядные элементы (Ь,;, 1) матрицы В с доцолнитель. ным (Т+1)-м единичным разрядом, представленной на фиг, 1 в форме тре- ". угольника., где 1 - номер такта работы устройства. На первом такте элемент Ь, записывается в регистр 7иблока 5, . На втором такте элементыЬ, Ь записываются в регист 112 Ффги 5 . На третьем такте элементы Ь3 й фзаписываютсярегистры 7 соответственно блоков 551, 55 и 5 . На четвертомЬ Ьи Ь записываются в регис 4тры 7 блоков 555 з 5 и . 2 Фи 5 соответственно. Таким образом,для записи всех элементов матрицы В 1 г в соответствующие блоки 5 требуетсяи тактов работы устройства, где иразмерность матрицы В.Рассмотрим работу блока 5, призаписи в регистр 7 элемента Ь. Напервом такте Т-разрядный элемент Ьи (Т+1)-й единичный разряд поступают соответственно на Т-разрядный ин; формационный вход регистра 7 и установочный вход триггера 12. В исходномсостоянии с инверсного выхода триггера 12 подается единичный сигнал навход признака записи регистра 7 и1элемент Ь записывается в регистр 7.1На вход синхронизации триггера 12 поЗ 0 ступает тактовый сигнал, по заднемуфронту которого триггер 12 устанавливается в единичное состояние, запре- .щая запись в регистр 7 блока 5.При этом открываются элементы И 13.На последующих тактах работы устройства запись элементов матрицы Вв регистр 7 блока 5запрещена, исоответствующие Т-разрядные элементыматрицы (Ь;, 1) с дополнительнымР40 единичным разрядом проходя через открытые элементы И.13 в соседний диагональный блок 5 .На вторые информационные входы 2устройства подаются по тактам соот ветствующие Т-разрядные элементы а,.матрицы А, представленной на фиг. 11)в форме параллелограмма. На первомтакте элемент а записывается в регистр 8 блока 5, . На втором тактеэлемент а, записывается в регистр 8блока 5 а элементы а" и а запи 1 1 1сываются в регистры 8 блоков 5и51 соответственно. Закономерностьзаписи соответствующих элементов а.55 матрицы А сохраняется и на последующих тактах.Рассмотрим работу устройства приформировании Т-разрядных элементов Си С. На первом такте элементыз 136 а 11 и Ь записываются в регистры 8,11и 7 аоответственно блока 5, и подаются на входы блока 10 умножения. С выхода блока 10 умножения произведение а Ьпоступает на вход сумма 11 11тора 11, на второй вход которого поступают нули, так какрегистр 9 блока 5, постоянно находится в нулевом состоянии. В результате на первом такте на выходе сумматора 11 формиру 1 ется накапливаемая сумма С = 0 +11 + аЬ , . На втором . такте накапливаемая сумма Сзаписывается в ре 11гистр 9 блока 5, . В блоке 5, аналогично формируется накапливаемая сумма С 2, =О+а 2, Ь . Вблоке 5 с регистров 8 и 7 на входы блока 102 умножения подаются элементы а и12 Ь, соответственно. На выходе сумма 21тора 11 формируется накапливаемая сумма С = С, + а 12 Ь, . На треть-,.2ем такте в блоке 5 , аналогично формируется накапливаемая сумма С э 1э э.сумма С = Сэ 1+ а 4 Ь 4 в блоке 5 э - сУмма С 2, = С 21 + а яз Ь,у блоке 5, - сумма С , = С + аЬ 4,. На четвертом такте накапливаемая сумма С , является значением элемента Сматрицы произведения С и подается на выход 6 1. На последующих тактах работы устройства аналогичноР формируются Остальные элементы С, матрицы произведения С, представленной на фиг. 1 в форме параллелограмма.Формула изобретенияУстройство для перемножения матриц, содержащее матрицу из РкР вычис. лительных блоков, где Р - порядок матрицы, причем каждый вычислительный блок содержит три регистра, блок умножения и сумматор, о т л и ч а - ю щ е е с я тем, что, с целью повышения быстродействия устройства, в каждый вычислительный блок введены триггер и (Т+1) элементов И, где Т - разрядность кода представления числовых компонентов перемножаемых матриц,3247 4причем информационный вход первого регистра первого вычислительного блока первой строки матрицы является первым информационным входом первой группы устройства, информационный вход первого регистра К.-го вычислительного блока (К = 2 Р) первой4 строки матрицы является К-м информа-, ционным входом первой группы устройства, информационный вход первого регистра М-го выччслительного блока (М=2Р) первого столбца матрицы является (Р+М)-м информационным входом первой группы устройства, выходы с первого по (Т+1)-й элементов И (К)-го вычислительного блока (М)-й строки матрицы подключены к информационному входу первого регистра К-го вычислительного блока М-Й строки матрицы, информационный вход второго регистра Н-го вычислительного блока первой строки матрицы(Н=1Р) является Н-м информацион 25 ным Входом Второй группы устройстВа 1 выход второго регистра Н-го вычислительного блока (М)-й строки матрицыподключен к входу второго регистра Н-го вычислительного блока М-й строЗО ки матрицы, информационные входы третьих регистров всех вычислительных 1блоков первого столбца матрицы явля ются входами для задания кода нуляустройства, выход сумматора Н-го вьг35 числительного блока (К)-го столбцаматрицы подключен к информационному входу третьего регистра Н-го вычислительного блока К-го столбца матрицы, выход сумматора Н-го вычислитель 40 ного блока Р-го столбца матрицы является Н-м информационным выходом устройства, тактовый вход устройства ,подключен к входам признаков записивторых и третьих регистров и к входам45 синхронизации триггеров всех вычислительных блоков матрип 1,.С первого по (Т+1)-й разряды информационноговхода первого регистра каждого вычис. -лительного блока матрицы соединены с первыми входами с первого по (Т+1)-й , элементов,И соответственно того же вычислительного блока матрицы, первый вход (Т+1)-го элемента И каждого вычислительного блока матрицы соеди- .нен с информационным входом триггератого же вычислительного блока матрицы, инверсный и прямой выходы триггера каждого вычислительного блока матрицы подключены к входу признака за,Проектн оиэводственно-по писи первого регистра и к вторым входам всех элементов И соответственнотого же вычислительного блока матрицы, выходы первого и второго регистров каждого вычислительного блокаподключены к входам первого и второго сомножителей соответственно блока Тираж 671 ВНИИПИ Государстве по делам изобре 113035, Москва, Ж, 476умножения .того же вычислительного блока матрицы, входы первого и второго слагаемых сумматора каждого вычислительного блока матрицы подключены к выходу блока умножения и к выходу третьего регистра соответственно того же вычислительного блока матрицы. Подписноеного комитета СССРений и открытииРаушская наб д, 4/