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

(Г 9) П 1) 51)5 6 06 Р 15/34 ЕТЫТИЯМ ИСАН ИЗО И.)ТЕК,о,Б 5 Д ЕЛЬСТВ м.В.М.Глушкова омейко, И,Г.Мо- щак с.142, рис.10ктроника, 198 НОЖЕНИ я к вычислительиспользовэно в ислительных мапервь элеме трети вычислительпользовано в ительных маенных матриц упра груп вэ, в вход 41 - 4 ение аппатурная схема вычислитель ональная схе жит первый 1, яти, первый 4, 7, шестой 8 и тельный блок евятый 13 ре, шестой 16, 19, третий 20, элементов И,чик 50 ГОСУДАРСТВЕННЫЙ КОМПО ИЗОБРЕТЕНИЯМ И ОТПРИ ГКНТ СССР К АВТОРСКОМУ С(54) УСТРОЙСТВО ДЛЯ УМРЕЖЕННЫХ МАТРИЦ(57) Изобретение относитсной технике и может бытьспециализированных выч Изобретение относится к ной технике и может быть ис специализированных вычисл шинах для умножения раэреж одного порядка.Цель изобретения - сокра ратурных затрат,На фиг.1 изображена струк устройства; на фиг,2 - схема ного блока; на фиг,З - функци ма блока управления,Устройство (фиг.1) содер второй 2 и третий 3 блоки пам четвертый 5, пятый 6, второй седьмой 9 регистры, вычисли 10, третий 11, восьмой 12 и д гистры, четвертый 14, пятый 1 седьмой 17, первый 18, второй восьмой 21 и девятый 22 блоки шинах для умножения разреженных и сверхразреженных матриц, Цель изобретения - сокращение аппаратурных затрат, Устройство содержит два блока памяти для хранения ненулевых элементов разреженных матриц, блок памяти для хранения ненулевых элементов 1-й строки одной из исходных матриц со значениями индексов строк, вычислительный блок, регистры, блоки элементов ИЛИ, И, элементы ИЛИ, НЕ, элемент И, Цель изобретения достигается за счет хранения и обработки только ненулевых элементов перемножаемых матриц, что позволяет использовать один вычислительный блок независимо от порядка перемножаемых матриц. 3 ил. й 23, второй 24 и третий 25 блоки нтов ИЛИ, элемент И 26, второй 27, й 28 и первый 29 элементы ИЛИ. пер и второй 31 элементы НЕ, блок 32 ления, первую (33 - 35) и вторую (36 - 38) ы информационных входов устройстод 39 управления записью и тактовый 40 устройства, а также группу выходов ычислительный блок (фиг,2) включает итель 44 и накапливающий суммаок управления (фиг. 3) образуют сче адреса, триггеры 47-49 и элементы В основу работы устроиства положен горитм умножения матрицы А = (а)Д на трицу В = (ЬД. определяющий матрицуС = с) ( = 1, п; ) = 1 п, где и - порядокматрицы);ис= ; ажЬц. (1)1=15В случае плотных матриц ог 1 ределениелюбого элемента Сл потребовало бы и-кратного выполнения операции накопленияпарных произведенийСл =С 11 +а Ь .1-1(2)В случае разреженных и сверхразреженных матриц произвольной структурыопределение любого элемента с 1 потребуетне более -кратного выполнения операцийнакопления, а в общем случае , где ф -,максимальное количество ненулевых элементов в перемножаемых строке и столбцеисходных матриц, и п, Величина отражает степень разреженности строки и столбца исходных матриц,20Кроме того, в разреженных матрицахобщего аида ненулевые элементы распределены произвольно в строках и столбцахматриц, и при определении любого элемента сл результирующей матрицы необходимонаходить парные сомножители. Из формулы(1) видно, что величина индекса для парных элементов аа и Ьц матриц А и В одинакова, Таким образом, если переписатьненулевые элементы аа -й строки разреженной матрицы А со значениямиих индекса строки в блок памяти по адресу,равному значению индекса 1 при этом элементе, то для получения парного сомножителя их этой строки для элементов столбцовЬц матрицы В будем обращаться к этомублоку памяти по адресу, равному значениюиндекса 1 при элементе Ьц, При этом элементы 1-й строки сл результирующей матрицы С будут иметь индекс строки, равный 40индексу 1 элемента аа, и индекс столбца,равный индексу ) элемента Ьц,В данном случае будем рассматриватьразреженную матрицу В с одним ненулевымэлементом в столбце при любой степени 45разреженности матрицы А,Устройство работает следующим образом,По сигналу с первого выхода блока управления последовательно формируютсяадреса, в соответствии с которыми производится запись чисел первого и второго трехмерных массивов, представляющихсоответственно разреженные матрицы А иВ, в блоки 1 и 2 памяти, Одновременно осуществляется запись ненулевых элементоваа 1-й строки матрицы А с их значениямииндекса строки и индекса столбца в регистры 4 - 6 через блоки 14-16 элементов И, Приэтом блок управления по второму выходу выдает тактовые импульсы, которые открывают блоки 14" 16 элементов И, и через блоки 23-25 элементов ИЛ И производится запись значений чисел, записанных в регистрах 4 и 5, в блок 3 памяти по адресу, значение которого записано в регистре 6, Окончание -й строки первого массива чисел определяется появлением в регистре б нулевого кода, который фиксируется блоком управления по входу признака окончания строки, и по второму выходу блока управления запрещается передача чисел чеоез блоки 14-16 элементов И. После записи чисел обоих массивов в блоки 1 и 2 памяти и 1-й строки первого массива в блок 3 памяти блок управления по первому выходу формирует адрес первой ячейки,8 соответствии с первым адресом из второго блока памяти в регистры 7 - 9 считываются соответственно значение элемента Ьц, значение индекса 1 и значение индекса ),Блок управления сигналом по третьему выходу открывает блок 17 элементов И, и через блок 25 элементов ИЛИ осуществляется передача содержимого регистра 8 в регистр б. По этому адресу из третьего блока 3 памяти считываются значение аа и значение его индекса 1 в регистры 4 и 5 соответственно, При этом значения элементов аа и Ьц одновременно передаются в вычислительный блок 10 через блоки 18 и 19 элементов И.Если числа по этому адресу не оказалось в блоке 3 памяти, о чем свидетельствует нулевое значение кода в регистре 5, то сигнал с выхода регистра 5 через элемент ИЛИ 28 запирает блоки 18 и 19 элементов И. Из блока 2 памяти считывается следующий элемент массива чисел в регистры 7 - 9. Окончание первого столбца массива чисел, записанного в блоке 2 памяти, определяется появлением нулевого кода в регистре 8, сигналы с выхода которого, проходя через элемент ИЛИ 27 и элемент НЕ 31, открывает блоки 20 - 22 элементов И, и осуществляется передача числа с из вычислительного блока в регистр 11 через блок 20 элементов И, значения индекса строки 1 элемента с 1 из регистра 5 в регистр 12 через блок 21 элементов И, значения индекса столбцаэлемента сл из регистра 9 в регистр 13 через блок 22 элементов И. Таким образом. с выходов 41 - 43 устройства снимается элемент результирующей матрицы с 11, образующейся путем получения парных сомножителей в умножителе 44 и накопления их в сумматоре 45, При этом накапливающий сумматор 45 обнуляется,Таким образом, в каждом такте работы устройства в регистры 7-9 из блока 2 памятисчитываются элементы всех столбцов матрицы В, которые умножаются на элементы 1-й строки матрицы А, и с выходов 41 - 43 устройства снимается элемент результирующей матрицы сл, Аналогичным образом осуществляется умножение всех столбцов матрицы В на следующую, (1+)-ю строку матрицы А, которая считывается из блока 1 памяти по сигналу, поступающему с четвертого выхода блок управления, фиксирующему сигнал по входу признака последнего столбца, поступающему с выхода последнего разряда регистра 8 через элемент И 26. 5 10 15 Формула изобретения Устройство для умножения разрежен ных матриц, содержащее два блока памяти, вычислительный блок, три блока элементов И, три регистра, блок управления, причем первые информационные входы первого и второго блоков памяти соединены соответ ственно с первыми информационными входами первой и второй групп входов устройства, первый выход блока управления соединен с входами адреса первого и второго блоков памяти, первый выход пер вого регистра соединен с первым входом первого блока элементов И, выход которого с соединен с первым информационным входом вычислительного блока, информационный вход второго регистра соединен с 35 первым выходом второго блока памяти, выход второго регистра соединен с первым входом второго блока элементов И, выход которого соединен с вторым информационным входом вычислительного блока, выход 40 которого соединен с первым входом третьего блока элементов И, выход которого соединен с информационным входом третьего регистра, выход которого является первым выходом устройства, о т л и ч а ю щ е е с я 45 тем, что, с целью сокращения аппаратурных затрат, устройство содержит третий блок памяти, четвертый - девятый регистры, четвертый - девятый блоки элементов И, три блока элементов ИЛИ три элемента ИЛИ, 50 два элемента Н Е, элемент И, причем первыйинформационный вход первой группы входов устройства соединен с первым входом четвертого блока элементов И, второй и третий информационные входы первого блока 55 памяти объединены с первыми входами соответственно пятого и шестого блоков элементов И и являются соответственно вторым и третьим информационными входами первой группы устройства, вторые входы четвертого, пятого и шестого блоков элементов И соединены с вторым выходом блока управления, выходы четвертого, пято- го и шестого блоков элементов И соединены соответственно с первыми входами первого, второго и третьего блоков элементов ИЛИ, вторые входы которых соединены соответственно с первым, вторым и третьим выходами первого блока памяти, выход первого, второго и третьего блоков элементов ИЛИ соединены соответственно с первым информационным входом первого регистра, информационными входами четвертого и пятого регистров, второй выход первого регистра и первый выход четверто. го регистра соединены соответственно с первым и вторым информационными входами третьего блока памяти, первый и второй выходы которого соединены с вторыми информационными входами первого и четвертого регистров, выход пятого регистра соединен с входом адреса третьего блока памяти и входами первого элемента ИЛИ. выход которого соединен с входом элемента НЕ, выход которого соединен с входом признака окончания строки блока управления, вход управления записью и тактовый вход которого соединены с одноименными входами устройства, третий выход блока управление соединен с первым входом седьмогоблока элементов И выход которогосоединентретьим входом третьего олока элементов ИЛИ, четвертый выход блока управления соединен с входом управления записью-чтением первого блока памяти, второй и третий информационные входы второго блока памяти соединены соответственно с вторым и третьим информационными входами второй группы устройства, второй и третий выходы второго блока памяти соединены соотвественно с информационными входами шестого и седьмого регистров, выход шестого регистра соединен с вторым входом седьмого блока элементов И и входами второго элемента ИЛИ, выход которого соединен с входом второго элемента НЕ, выход которого соединен с вторым входом третьего блока элементов И, первыми входами восьмого и девятого блоков элементов И и первым входом элемента И, второй вход и выход которого соединены соответственно с выходом последнего разряда седьмого регистра и входом признака последнего столбца блока управления, выход седьмого регистра соединен с вторым входом девятого блока элементов И, второй вход восьмого блока элементов И соединен с вторым выходом четвертого регистра и входом третьего элемента ИЛИ, выход которого соединен с вторыми входами первого и второго блоковэлементов И, выходы восьмого и девятого блоков элементов И соединены с информационными входами соответственно восьмого и девятого регистров, .выходы которыхявляются соответственно вторым и третьимвыходами устройства,16565 б 0 Редактор А. Ога Составитель К. Кухаренко ехред М,Моргентал Корректор С, Шевкун Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 Заказ 2054 Тираж 417 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СС 113035, Москва, Ж, Раушская наб 4/5