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

 

Изобретение относится к вычислительной технике и может Ьыть использовано в специализированных вычислительных машинах для умножения разреженных и сверхрэзреженных матриц Цель изобретения - сокращение аппаратурных затрат Устройство содержит два блока памяти для хранения ненулевых элементов разреженных матриц, блок памяти для хранения ненулевых элементов i-й строки одной из исходных матриц со значениями индексов строк, вычислительный блок, регистры, блоки элементов ИЛИ И, элементы ИЛИ, НЕ, элемент И. Цель изобретения достигается за счет хранения и обработки только ненулевых элементов перемножаемых матриц, что позволяет использовать один вычислительный блок независимо от порядка перемножаемых матриц. 3 ил

союз соВетских

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)5 G 06 F 15/347

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ... ) .ц(Q, Я!,1 Я!4 )-Т--, (21) 4498372/24 (22) 24,10,88 (46) 15.06.91. Бюл, ¹ 22 (71) Институт кибернетики им.В.M.Ãëóøêîâà (72) Л.Д.Елфимова, В.В.Коломейко, И.Г.Мороз-Подворчан и В,Д.Петущак (53) 681.3(088.8) (56) ТИИЭР, 1984, т.72, ¹ 7, с.142, рис.10б.

Зарубежная радиоэлектроника, 1987, № 7, с.38, рис.5. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ РАЗРЕЖЕННЫХ МАТРИЦ (57) Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных маИзобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах для умножения разреженных матриц одного порядка.

Цель изобретения — сокращение аппаратурных затрат.

На фиг.1 изображена структурная схема устройства; на фиг,2 — схема вычислительного блока; на фиг.3 — функциональная схема блока управления, Устройство (фиг.1) содержит первый 1, второй 2 и третий 3 блоки памяти, первый 4, четвертый 5, пятый 6, второй 7, шестой 8 и седьмой 9 регистры, вычислительный блок

10, третий 11, восьмой 12 и девятый 13 регистры, четвертый 14, пятый 15, шестой 16, седьмой 17, первый 18, второй 19, третий 20, восьмой 21 и девятый 22 блоки элементов И, . Ж 1656560 А1 шинах для умножения разреженных и сверхразреженных матриц. Цель изобретения — сокращение ап паратурных затрат. Устройство содержит два блока памяти для хранения ненулевых элементов разреженных матриц, блок памяти для хранения ненулевых элементов i-й строки одной из исходных матриц со значениями индексов строк, вычислительный блок, регистры, блоки элементов ИЛИ, И, элементы ИЛИ, НЕ, элемент И, Цель изобретения достигается за счет хранения и обработки только ненулевых элементов перемножаемых матриц, что позволяет использовать один вычислительный блок независимо от порядка перемножаемых матриц. 3 ил. первый 23, второй 24 и третий 25 блоки элементов ИЛИ, элемент И 26, второй 27, третий 28 и первый 29 элементы ИЛИ, первый 30 и второй 31 элементы НЕ, блок 32 уп равления, первую (33 — 35) и вторую (36 — 38) группы информационных входов устройства, вход 39 управления записью и тактовый вход 40 устройства, а также группу выходов

41 — 43, Вычислительный блок (фиг.2) включает умножитель 44 и накапливающий сумматор 45.

Блок управления (фиг. 3) образуют счетчик 46 адреса, триггеры 47-49 и элементы И

50-53.

В основу работы устройства положен алгоритм умножения матрицы А =- (a!i) на матрицу В = (Ь|Д. определяющий матрицу

1656560

С = (с ) (I = 1, „п; j = 1...„n, где n — порядок матрицы); и

cij = . аи Ьц. (1)

k =1

В случае плотных матриц определение любого элемента Сл потребовало бы и-кратного выполнения операции накопления парных произведений

+ aIt bkq

k k-1 (2)

В случае разреженных и сверхразреженных матриц произвольной структуры определение любого элемента с1 потребует не более -кратного выполнения операций накопления, а в общем случае «(, где — ,максимальное количество ненулевых элементов в перемножаемых строке и столбце исходных матриц, и («n, Величина (отражает степень разреженности строки и столбца исходных матриц, 20

Кроме того, в разреженных матрицах общего аида ненулевые элементы распределены произвольно в строках и столбцах матриц, и при определении любого элемента cij результирующей матрицы необходимо находить парные сомножители. Из формулы (1) видно, что величина индекса I< для парных элементов Blk u bkj матриц А и В одинакова, Таким образом, если переписать ненулевые элементы aik i-й строки разре- 30 женной матрицы А со значениями i их индекса строки в блок памяти по адресу, равному значению индекса k при этом элементе, то для получения парного сомножителя их этой строки для элементов столбцов

bkj матрицы В будем обращаться к этому блоку памяти по адресу, равному значению индекса k при элементе bkj. При этом элементы 1-й строки cjj результирующей матрицы С будут иметь индекс строки, равный индексу I элемента aik, и индекс столбца, равный индексу j элемента Ьц, В данном случае будем рассматривать разреженную матрицу В с одним ненулевым элементом в столбце при любой степени 45 разреженности матрицы А, Устройство работает следующим образом, По сигналу с первого выхода блока управления последовательно формируются адреса, в соответствии с которыми производится запись чисел первого и второго трехмерных массивов, представляющих соответственно разреженные матрицы А и

В, в блоки 1 и 2 памяти. Одновременно осуществляется запись ненулевых элементов

ajk I-й строки матрицы А с их значениями индекса строки и индекса столбца в регистры 4 — 6 через блоки 14-16 элементов И, При этом блок управления по второму выходу выдает тактовые импульсы, которые открывают блоки 14--16 элементов И. и через блоки 23-25 элементов ИЛ И производится запись значений чисел, записанных в регистрах 4 и 5, в блок 3 памяти по адресу, значение которого записано в регистре 6.

Окончание I-й строки первого массива чисел определяется появлением в регистре 6 нулевого кода, который фиксируется блоком управления по входу признака окончания строки, и по второму выходу блока управления запрещается передача чисел чеоез блоки 14-16 элементов И. После записи чисел обоих массивов в блоки 1 и 2 памяти и I-й строки первого массива в блок 3 памяти блок управления по первому выходу формирует адрес первой ячейки, В соответствии с первым адресом из второго блока памяти в регистры 7 — 9 считываются соответственно значение элемента bkj, значение индекса k и значение индекса j.

Блок управления сигналом по третьему выходу открывает блок 17 элементов И, и через блок 25 элементов ИЛИ осуществляется передача содержимого регистра 8 в регистр 6. По этому адресу из третьего блока

3 памяти считываются значение ал< и значение era индекса i в регистры 4 и 5 соответственно, При этом значения элементов а; < и

bkj одновременно передаются в вычислительный блок 10 через блоки 18 и 19 элемент ов И.

Если числа по этому адресу не оказалось в блоке 3 памяти, о чем свидетельствует нулевое значение кода в регистре 5, то сигнал с выхода регистра 5 через элемент

ИЛИ 28 запирает блоки 18 и 19 элементов

И. Из блока 2 памяти считывается следующий элемент массива чисел в регистры 7 — 9.

Окончание первого столбца массива чисел, записанного в блоке 2 памяти, определяется появлением нулевого кода в регистре 8, сигналы с выхода которого, проходя через элемент ИЛИ 27 и элемент НЕ 31, открывает блоки 20 — 22 элементов И, и осуществляется передача числа с1из вычислительного блока в регистр 11 через блок 20 элементов И, значения индекса строки 1 элемента с из регистра 5 в регистр 12 через блок 21 элементов И, значения индекса столбца j элемента сл из регистра 9 в регистр 13 через блок 22 элементов И. Таким образом. с выходов 41 — 43 устройства снимается элемент результирующей матрицы c j, образующейся путем получения парных сомножителей в умножителе 44 и накопления их в сумматоре

45, При этом накапливающий сумматор 45 обнуляется.

Таким образом, в каждом такте работы устройства в регистры 7-9 из блока 2 памяти

1656560

6 считываются элементы всех столбцов матрицы В, которые умножаются на элементы

i-й строки матрицы А, и с выходов 41 — 43 устройства снимается элемент результирующей матрицы сл. Аналогичным образом осуществляется умножение всех столбцов матрицы В на следующую, (i+j)-ю строку матрицы А, которая считывается из блока 1 памяти по сигналу, поступающему с четвертого выхода блок управления, фиксирующему сигнал по входу признака последнего столбца, поступающему с выхода последнего разряда регистра 8 через элемент И 26.

Формула изобретения

Устройство для умножения разрежен- 20 ных матриц, содержащее два блока памяти, вычислительный блок, три блока элементов

И, три регистра, блок управления, причем первые информационные входы первого и второго блоков памяти соединены соответ- 25 ственно с первыми информационными входами первой и второй групп входов устройства, первый выход блока управления соединен с входами адреса первого и второго блоков памяти, первый выход пер- 30 вого регистра соединен с первым входом первого блока элементов И, выход которого с соединен с первым информационным входом вычислительного блока, информационный вход второго регистра соединен с 35 первым выходом второго блока памяти, выход второго регистра соединен с первым входом второго блока элементов И, выход которого соединен с вторым информационным входом вычислительного блока, выход 40 которого соединен с первым входом третьего блока элементов И, выход которого соединен с информационным входом третьего регистра, выход которого является первым выходом устройства, о т л и ч а ю щ е е с я 45 тем, что, с целью сокращения аппаратурных затрат, устройство содержит третий блок памяти, четвертый — девятый регистры, четвертый — девятый блоки элементов И, три блока элементов ИЛИ три элемента ИЛИ, 50 два элемента Н Е, элемент И, причем первый информационный вход первой группы входов устройства соединен с первым входом четвертого блока элементов И, второй и третий информационные входы первого блока 55 памяти объединены с первыми входами соответственно пятого и шестого блоков элементов И и являются соответственно вторым и третьим информационными входами первой группы устройства, вторые входы четвертого, пятого и шестого блоков элементов И соединены с вторым выходол„ блока управления, выходы четвертого, пятого и шестого блоков элементов И соединены соответственно с первыми входами первого, второго и третьего блоков элементов

ИЛИ, вторые входы которых соединены соответственно с первым, вторым и третьим выходами первого блока памяти, выход первого, второго и третьего блоков элементов ИЛИ соединены соответственно с первым информационным входом первого регистра, информационными входами четвертого и пятого регистров, второй выход первого регистра и первый выход четвертого регистра соединены соответственно с первым и вторым информационными входами третьего блока памяти, первый и второй выходы которого соединены с вторыми информационными входами первого и четвертого регистров, выход пятого регистра соединен с входом адреса третьего блока памяти и входами первого элемента ИЛИ. выход которого соединен с входом элемента

НЕ, выход которого соединен с входом признака окончания строки блока управления, вход управления записью и тактовый вход которого соединены с одноименными входами устройства, третий выход блока управление соединен с первым входом седьмого блока элементов И.выход которогосоединен третьим входом третьего олока элементов

ИЛИ, четвертый выход блока управления соединен с входом управления записью-чтением первого блока памяти, второй и третий информационные входы второго блока памяти соединены соответственно с вторым и третьим информационными входами второй группы устройства, второй и третий выходы второго блока памяти соединены соотвественно с информационными входами шестого и седьмого регистров, выход шестого регистра соединен с вторым входом седьмого блока элементов И и входами второго элемента ИЛИ, выход которого соединен с входом второго элемента НЕ, выход которого соединен с вторым входом третьего блока элементов И, первыми входами восьмого и девятого блоков элементов И и первым входом элемента И, второй вход и выход которого соединены соответственно с выходом последнего разряда седьмого регистра и входом признака последнего столбца блока управления, выход седьмого регистра соединен с вторым входом девятого блока элементов И, второй вход восьмого блока элементов И соединен с вторым выходом четвертого регистра и входом третьего элемента ИЛИ, выход которого соединен с вторыми входами первого и второго блоков

1656560 элементов И, выходы восьмого и девятого блоков элементов И соединены с информационными входами соответственно восьмого и девятого регистров, .выходы которых являются соответственно вторым и третьим выходами устройства.

16565б0

Составитель К. Кухаренко

Техред M.Моргентал Корректор С. Шевкун

Редактор А. Orap

Производственно-издательский комбинат "Патент". г. Ужгород, ул.Гагарина. 101

Заказ 2054 Тираж 417 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб.. 4/5