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

(51) Е РЕТЕНИЯ У СВИДЕТЕЛЬСТВ ВТО а А,Лиходед 3101 С Аггд1978, Яосе1979, р. 26 86. 1 ОЖЕНИЯ 1 числительльзовано о циализирох и устрой а ааа к вычислитель- использовано в ециализированх и устройствах множения двух ГОСУДАРСТВЕ 11 НЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(54) УСТРОЙСТВО ДЛЯ ПЕРЕЛЕНТОЧНЫХ МАТРИЦ(57) Изобретение относится кной технико и может быть испвысокопроизоодительных спванных вычислительных маши Изобретение относится ной технике и может быть оысокопроизводительных с ных оычислительных машин обработки сигналоо для пер ленточных матриц. Цель изобретения - повышение быстродействия устройства.На фиг. 1 представлена структурная схема устройства для перемножения ленточных матриц; на фиг. 2 - пример схемы вычислительного модуля.Устройство для перемножения ленточных матриц (фиг. 1) содержит группу 1 информационных входов, первый 2 и второй 3 информационные входы, вход 4 задания рествах обработки сигналов для перемножения двух ленточных матриц А и 8. Цель изобретен ия - повышен ие быстродействия устройства. Цель достигается тем, что устройство содержит ра+цавычислительных модулей, где ра и ца - соответственно число ненулевых элементов в первой строке и первом столбце ленточной матрицы А, причем каждый вычислительный модуль содержит три регистра, два узла задержки на Лтакта, где Л=2 ра+2 ца+рь+ць/рь и ць в число ненулевых элементов соответственно в первой строке и первом столбце ленточной матрицы В/, умножитель, сумматор, Лтриггеров и элемент И. В основу работы устройства положена параллельно-поточная организация вычислений. 2 ил. жима, синхровход 5, вычислительные модули 6 =, раада 1) и выход 7. 3 ыВычислительный модуль 6 (фиг. 2) со- ( ) держит первый 8, второй 9 и третий 10 ин- р формационные входы, вход 11 задания режима, синхровход 12, умножитель 13, сумматор 14, регистр 15, 16 и 17, злы 18 и 19 задержки, регистры 201 (1=1, Л) узла 18 задержки, регистры 211(1=1, Л -2) узла 19 ф задержки, триггеры 221 (1=1, Л), элемент И 23, первый 24, второй 25, третий 26 и четвертый 27 информационные выходы.В основу работы устройства положен алгоритм перемножения двух (пхп) ленточных матриц А и В с шириной лент соответственно 1 а=ра+цаи 1 ь=рь+ць, где ра и рь - число ненулевых элементов в первой строкесоответственно матриц А и В; ца и Чь - число ненулевых элементов в первом столбце соответственно матриц А и В, основанный на рекуррентных соотношениях1 :- 1,и, 1-Ра-РЬ1) с г 1 а+ЯЬ 1;сц(о):О;сцй=сг("+а;1,Ьц; К=1, ац;ац=п 11 п(п,1+ра; )+ЦЬ).п 11 п(0,) Рь 1-ца)в)Ясц=сцВычислительный модуль 6 обладаетвозможностью реализации функции(+Л - 1ьеых - йехгде а вх, Ь вх и с вх - значения соответственно на первом, втором и третьем информационных входах вычислительного модуля на 1-м такте;гвх - значение на настроечном входе вычислительного модуля на 1-м такте;)+1твы, - значение на втором информационном выходе вычислительного модуля на (1+1)-м такте;а вых, с вых - значение соответственнона первом и третьем информационных выходах вычислительного модуля на 1-м такте;)+Л гвых - значение на настроеь)ном выходе вычислительного модуля на (1+ Л)-м такте;ра и рь - число ненулевых элементов впервой строке соответственно. матриц А и В; Ца и с 1 Ь - число ненУлевых элементов в пЕР- вом столбце соответственно матриц А и В,О,если тЬ=11,если то=О, ц=1,(Го, Г 1,)=2, если го= т 1=0, 72=1Л,если то =й ==.т -1 =О,гл -- 1.Вь)числительный модуль 6 работает следу)ощим образом.На 1-м такте элементы а, Ь и с матрицпода)отся соответственно на входы 8, 9 и 10 и записываются соответственно в регистры201, 16 и 17, Кроме того, при подаче на вход 11 единичного сигнала тоткрывается элемент И 23, который разрешает запись элемента а в регистр 15. На выходе сумматора 5 14 формируется значение (с)а Ь), которое выдается на выход 26 с задержкой на Лтакта, Элемент а выдается на выход 24 с задержкой на Лтакта, элемент Ь выдается навыход 25 с задержкой на один такт, а 10 управляющий сигнал выдается на выход 27 с задержкой на Лтакт. Организация потоков входных элеглен(о) тов аа, Ьц и сц, управля)ощих сигналов и выходных элементов сц следующая.Элементы аа подаются )(а вход 1 в моменты времени Юпа 1( Л.1).(Л -2)(ца.1)а 1,1=1,цв вць.1,К=1+1-(1 а, 1+Ра; 20 та(= 10 в 1 аа 1 Л (Л .1)(ав.1) ЦЬа 1, 1=2 вацьп,1=1+1-С 1 аа )+Ра, в остальные моменты времени на вход 1 подаются нулевые значения (полагаем а(к=О 25 в слУчае К - О и 1 цп), Возьмем 10= Л 1 а)-Ца Элементы Ьц подаются на вход 2 в моменты времени 1 Ь),1 = Л К+)-ра+1 .со, 1=1,п, /=3(+1-сь, К+рь, в остальные моменты времени на вход 2 ЗО подаются нулевые значения.Элементы сц 1) подаются )(а вход 3 в мо, менты времени(0)Сц( =Л 1 а 1(Л 1)(аа 1)+ац 1=1 п,)=ав 2 ца Ць, 35 (+ра+рь, На вь)ходе 7 устройства формируютсяЫ) элементы сц=.сц в моменты времени1 сц = Л.1+1+ра( Л)+10-1; 40 1=1,п, )=1+2-с 1 а-с 1 Ь, 1+ра+рь,На вход 4 управляющий сигнал г=1 подается в ломенты времени .ь=(0+ Л 1+2-( Л)(Ца) а 1=0 а Ча+С 1 Ь; тпа( Ла 1)1+ Л(Ць а 1)аааь 1, 1=й, и-Цв аЬ, 4 г а в остальные моменты времени на вход 4 подается г=О,Рассмотрим работу устройства для случая п=5, ра=с 1 Ь=З, рь=с 1 а=2 и Л=9, Запись соответствуюших значений в триггеры и регистры, формируемые значения на выходе сумматора в вычислительных модулях, осуществляется в соответствии с выполняемыми функциями вычислительными модулями и заданной организацией входного потока элементов аа, Ьк 1, с)1 ь") и управляющих сип 1 алов т. Формируемые(м )11 значения сц=с " на выходе 26 вычислительного модуля 64 подаются на выход 7 устройства, Последний элемент спп формируется в момент времени, определяемый выражением1774348 Фиг.1 Л (и+ра)+и-раф 0-1.В данном случае последний элемент скформируется на 72-м такте,Время перемножения двух ленточныхматриц предлагаемым устройством равно 5( Л.1)(п+ра+ца)+2(п),Период подачи элементов для очередного перемножения матриц равен (Л 41)(п)тактов.Формула изобретения 10Устройство для перемножения ленточных матриц, содержащее (р+с) вычислительных модулей (р и о - соответственночисло ненулевых элементов в первой строкеи первом столбце матрицы), причем первый 15информационный вход устройства подключен к первому информационному входу первого вычислительного модуля, первый выход1-го вычислительного модуля (где 1=1,, р+с) подключен к первому информационному входу (+1)-го вычислительного модуля, второй информационный входустройства подключен к второму информационному входу (р+о)-го вычислительногомодуля, второй информационный вход 1-го 25вычислительного модуля подключен к второму выходу (+1)-го вычислительного модуля. синхровход устройства подключен ксинхровходам всех вычислительных модулей, отл ич а ю щ ее с я тем, что, с целью 30повышения быстродействия, третий информационный вход устройства подключен ктретьему информационному входу первоговычислительного модуля, третий выход 1-говычислительного модуля подключен к третьему информационному входу (1+1)-го вычислительного модуля, вход задания режимаустройства подключен к входу задания режима первого вычислительного модуля, четвертый выход 1-го вычислительного модуля 40 подключен к входу задания режима (+1)-го вычислительного модуля, причем каждый вычислительный модуль содержит три регистра, умножитель, сумматор, элемент И и три сдвигающих регистра, причем в каждом вычислительном модуле первый информационн ы й вход вы числ ител ь ного модуля подключен к информационным входам первого регистра и первого сдвигающего регистра. выход переноса которого подключен к первому выходу вычислительного модуля, второй информационный вход которого подключен к информационному входу второго регистра, выход которого подключен к первому информационному входу умножителя и к второму выходу вычислительного модуля, третий информационный вход которого подключен к информационному входу третьего регистра, выход которого подключен к первому информационному входу сумматора, второй информационный вход и выход которого подключены соответственно к выходу умножителя и к информационному входу второго сдвигающего регистра, выход переноса которого подключен к третьему выходу вычислительного модуля, вход задания режима которого подключен к информационному входу третьего сдвигающего регистра и к первому входу элемента И, выход которого подключен к входу записи/считывания первого регистра, выход которого подключен к второму информационному входу умножителя, выход переноса третьего сдвигающего регистра подключен к четвертому выходу вычислительного модуля, синхровход которого подключен к входам сдвига всех сдвигающих регистров, к входам записи/считывания второго и третьего регистров и к второму входу элемента И..ти 6Г д Составитель В. ЯкуТехред М,Моргентал Редактор Корректор И. Шмакова мбинат "Патент", г. Ужгород, ул.Гагарина,водственно-издэтельс Заказ 3928 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС 113035, Москва, Ж, Раущская наб., 4/6