Матричный вычислитель

) 4 С 06 Р 15/347 Т СССРОТНРЫТИЙ САНИЕ ИЗОБРЕТЕ ЛЬСТИ У 8 п к и СССР1979ССР1975. о47 Ь я к вычисл ыть исполь изведения ои длины трицу, сто ОСУДАРСТВЕННЫЙ НОМИ ПО ДЕЛАМ ИЗОБРЕТЕНИЙ ВТОРСИОМУ СВИ(57) Изобретение относиттельной технике и можетзовано для вычисления прцепочки матриц проиэвольпроизведения строки на м ЯО 141364 ца на матрицу, возведения матрицыв степень. Матричный вычислитель содержит блок 1 ввода, умножитель 2,блок 3 синхронизации и матрицу РкРвычислительных блоков 4. Найденныезакономерности при вычислении произведения цепочки матриц, представляемого как произведение ядра результирующей матрицы, вычисляемого в умножителе 2 и общего для всех элементоврезультирующей матрицы, на соответствующую строку первой матрицы справаи столбец последней матрицы слевапозволили осуществить вычисление всеэлементов результирующей матрицы затри такта работы блока 3 синхронизации, 1 з,п.ф-лы, 7 ил.Изобретение относится к вычислительной технике и может быть использовано для вычисления произведенияцепочки матриц произвольной длины,произведения строки на матрицу, столбца на матрицу, возведения матрицы встепень.Цель изобретения - повышение быстродействия устройства при вычисле 10нии произведения нескольких матриц.На фиг.1 представлена Функциональ- ная схема устройства, на фиг.2 -Функциональная схема блока умноженияна Фиг.3 - функциональная схема вы 15числительного блока; на Фиг.4 - Функциональная схема блока ввода; нафиг,5 - Функциональная схема коммутатора; на фиг,б - Функциональная схемаблока синхронизации на Фиг, " вре 920менная диаграмма работы вычислителя,Устройство содержит блок 1 ввода,умножитель 2, блок 3 синхронизации иматрицу из Р 1 Р вычислительных блоков25Умножитель 2 имеет группу блоковумножения, каждый из которых содержитсоединенные последовательно узлы 5умножения и группу блоков б элементов И.Вычислительный блок 4 образуюткоммутатор 7, группа блоков 8 элементов ИЛИ, группа узлов 9 умножения игруппа регистров 10, сумматор 11.Коммутатор 7 состоит из групп элементов И 12 и 13 и группы элементов 35ИЛИ 14,Блок 3 синхронизации содержитсчетчик 15, дешифратор 16, элемент17 задержки и элемент 18 ИЛИ.Устройство работает следующим образом.В блок 1 вводятся элементы перемножаемых матриц. С выхода блока 1элементы перемножаемых матриц подаются в умножитель 2.и вычислительные 45блоки 4 матрицы. В умножителе 2 Формируются соответствующие сомножители1 х,(а; а 1, х а; ), 1.=1Р, 3=1Р, где Р - порядок перемножаемых матриц, Я - количество перемножаемьиматриц. После Формирования сомножителей в умножителе 2 на вход пуска блока 3 подается сигнал, по которому спервого выхода блока 3 поступает импульс на вход синхронизации умножите- -5ля 2 и на первый вход синхронизацииблоков 4. На первые грутгпы информационных входов блоков. 1 н коммутатора 7 поступают элементы -й строки первой матрицы а " а,а 1На выходах блоков 12 Формируются соответствующие элементы, согласноалгоритму представления любого элемента результирующей матрицы С, ко"торые поступают через элементы ИЛИ14 , на первые входы соответствующихузлов 9, .на вторые входы которых поступан)т соответствующие сомножителихЙ(а,.а х а, ), На выходах узлов1) )9 формируются соответствующие сомножители (а .а .а,а ), кото"1 , 3 1 х1 1 1) 1) ф ф1)рые записываются в регистры 1 0 . Запис ь в регистры 1 О осуществляетсяпо заднему Фр онту импульса , к оторыйподается на вход разрешения записирегистра 1 0 ; через элемент ИЛИ 20 ,П о окончании первого тактового импульса , второй так то вый импульс подается на вход элемента ИЛИ 20 с эа"держкой, где, - время пер еключ ения триггера , Задержка 1 - осуществля ет ся элементом 1 7 задержки распределения 5 импульсов . По второму т акт ов ому сигналу элементы 1 -г о столбца И-й матрицы поступают на входывторой группы блока 4и коммутатор а 7 , при этом элементы И б и 1 2блокируются , т ак как на вход синхр ониз ации умножит еля 2 и на первый упр авляющнй вход коммутатора 7 импульсне подается . При этом с выходов р егистр ов 1 О через элементы ИЛИ 8 уподаются соответствующие сомножит ели(а. х а ха, хха ) на вторые вхо-З 11-11) 1)1)ды узлов 9 умножения, на первыевходы которых с выходов коммутатора7 поступают соответствующие элементы1-го столбца И-й матрицы, На выходахузлов 9, формируются соответствующиесомножители (а,; х аха ", а . ), конторые записываются в регистры 10 ис выходов которых поступают на. 1-евходы сумматора 11 соответствующеговычислительного блока 4 1) . На выходесумматора 24 блока 4; Формируютсязначения элементов С; результирующей матрицы.Таким образом, в основу работыпредлагаемого устройства положен метод точного определения любого изэлементов результирующей матрицы, нетребующий использования известнойпроцедуры перемножения матриц,йОпределение С -го элемента результирующей матрицы, где И - числоперемножения матриц, эквивалентноумножению матрицы Д являющейсяпроизведением с второй по предпослед1413644 слева насправа натрицы А, т,нюю матрицу,матрицы А,строкустолбец 11(1) 1и аа12 1 ф 21 фффф 1 я а 1 Таким обр матрицы С=А часть, пред нх различие, строки перв ца последнеи 15 ементы С,бщуюйД, аМ 2-йго стол А 2 Атавленопредел имеют о ую матрице ено выборо цы А, и 1-. цы А. а х И22 мат атр из выявленных з жения элементов позволяет указа м представления ономерност еремножаемых следующии юбого элем, мат алг рво тся юбого кроме влятьстол- ведепень я перемо ре" ть как сомножи го стол.е. элеменждый из ко 4 ф ставлен четырех наглядносе линии, ряемостиобведены группыпунктирной ментов (яд работы ременные дна трой На вв момен ввода,ветстве всех эле- ультирую 11 Ф я соот у 7 в 1. В пе м столбце сомножителей располагаю элементы д-й строки первой матрицы А, т.е. а,а11119;2 й " й а, а затем вся эта группа из г элементов повторяется г ф 2 раз.2, В каждом последующем Р-м столбце сомножителей, кроме последнего, т.е. Р=2, 3, , М, располагаются последовательно элементы столбцов матрицы А, т.е, элементы а , а 21, .Оа, а 11, а, , ат 2 а а 2, , а, причем каждый элемент1 Г 2повторяется г2 раз, затем вся этаруппа из г элементов повторяется, И Р+1)раз. 3. В последнем столбце 2 ей располагаются элементь ца последней матрицы А, т И й тыа., ааг;, ка Нторых повторяется г ра В качестве примера пред элемент С 12 перемножаемых матриц С=А, А А, А, Для ти проведены горизонтальн определяющие границы повт по вертикали сомножителей повторяющиеся по вертикал сомножителей, Кроме того,линией обведена группа эл ро), являющаяся общей для. ментов соответствующей ре щей матрицы С, ЮОДля вычисления любого элемента С,необходимо сформировать Н столбцовэлементов, которые подвержены в каждом столбце указанным выше двум процессам повторения элементов и группэлементов, а затем осуществить последовательное перемножение соответствующих элементов каждого сформированного столбца. Поскольку часть сомножителей (обведенная пунктирной линией)одна и та же для всех элементов ре- .зультирующей матрицы С, а меняются,только элементы в крайних столбцах,в зависимости от Ц-го номера элемента результирующей матрицы, то необходимо осуществить соответствующий5 выбор элементов при формировании этихдвух столбцовМетод точного определения аэлемента матрицы С позволяет,перемножения И матриц, осущестО перемножение матриц на матрицубец или на матрицу строку, возние матрицы в произвольную стеот второй до И-й. Например, длмножения двух матриц, необходи5 зультирующую матрицу представиС=А,А 1 1 , где- единичнаяматрица, для возведения матрицы А вН-ю степень - С=АА А" а в (М 1;%степень - С=АА фА " 1 еменных диаграммах показановремени Г с выходов блока а которых сформированы соот"но элементы матриц;. а 1, а.Э1а , сигналы йодаютетственно на входы кокмутатоычислительном блоке 4 и на,входы умножнтеля 2, в момент временина вход 11 умножителя 2 и на вход блока 2 подается единичный сигнал, на выходах 14 формируются значения3 И 1аа ., х а которые подаются на13входы элементов ИЛИ 8 и соответственног на первые входы узлов 9, значения аФормируются на выходах коммутатора 7, которые подаются на вторые входы узлов 9, по заднему фронту единичного сигнала произведения а .а . хй.1 1 1( а , записываются в регистрй 10;11в момент Тна вход блока 4 подается единичный сигнал, на выходах формируются значения а;, которые подаютсяИна вторые входы узлов 9 умчожения, на первые входы которых с выходов регистров 10 через элементы ИЛИ 8 подаются значения аа . ха, в момент. вреФ Ф Фмени С по заднему фройту единичного сигнала в регистры 10 записываются произведения, с выходов регистров 10 эти произведения подаются на соответствующие входы сумматора 11, На выхо" дах сумматора 24 в блоке 4м формируется г.,г-й элемент результирующей матрицы. Формула изобретения 1. Матричный вычислитель, содержащий матрицу из Р Р вычислительных блоков, где Р - порядок результирующей матрицы, о т л и ч а ю щ и й - с я тем, что, с целью повышения быстродействия вычислителя при вычислении произведения Е матриц, в него введены группа из Рблоков умножения, где Е - количество перемножаемых матриц, блок синхронизации и группа блоков элементов И, причем первая группа информационных входов всех вычислительных блоков К-й строки матрицы является входом для задания К-й строки первой матрицы устройства, вторая группа информационных входов всех вычислительных блоков является входом для задания М-го столбца Е-й матрицы, Т-й информационный вход Н-го блока умножения группы (7=1.Е, Н. , Р ), является входом задания Т-го злемен 25 ЗО 35 40 45 50 та Н-й строки ядра результирующейматрицы, выход Н-го блока умноженияподключен к первому входу Н-го блокаэлементов И группы, выход которогоподключен к Н-му информационному входу третьей группы всех вычислительных блоков матрицы, тактовый входустройства подключен к тактовомувходу блока синхронизации, с первогопо третий выходь 1 синхронизации которого подключены соответственно к вторым входам всех блоков элементов Игруппы, первому входу синхронизациивсех вычислительных блоков матрицы ивторому входу синхронизации всех вычислительных блоков матрицы, выходМ-го вычислительного блока К-й строкиматрицы является выходом М-го элемента К-й строки результирующей матрицыо 2. Матричный вычислитель по п.1, о т л и ч а ю щ и й с я тем, что каждый вычислительный блок содержит4 е коммутатор, группу из г элементов ИЛИ, группу умножителей, группу регистров и сумматор, причем первая и вторая группы информационных входов сумматора подключены к первой и второй группам информационных входов коммутатора соответственно, первый и второй входы синхронизации вычислительного блока подключены к первому и второму управляющим входам коммутатора, Н-й информационный выход которого подключен к входу первого сомножителя Н-го умножителя группы, Н-й информационный вход третьей группы вычислительного блока подключен к первому входу Н-го элемента ИЛИ группы, выход которого подключен к входу второго сомножигеля Н-го умно- жителя группы, выход которого подключен к информационному входу Н-го регистра группы, выход которого подключен к второму входу Н-го элемента ИЛИ группы и входу Н-го слагаемого сумматора, выход которого является выходом вычислительного блока, третий вход синхронизации вычислительного блока подключен к входам признаков записи всех регистров группы.Составитель А,Ии Техред Л.Олийнык рректор Ы Пвкв тор Л.Пчелинская ираж 704 Йз 37 ого коний и аушск Проектная, 4 лиграфическое предприятие, г. Ужгор енн оизв ВНИИ и 3035, Государстведелам изобре осква, ЖПодписноитета СССРткрытийнаб., д, 4/5