Устройство для умножения разреженных матриц Советский патент 1991 года по МПК G06F15/347 

fe

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

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах для умножения разреженных матриц одного порядка.

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

На фиг.1 изображена структурная схема устройства; на фиг.2 - схема вычислительного блока; на фиг.З - функциональная схема блока управления.

Устройство (фиг.1) содержит первый 1, второй 2 и третий 3 блоки памяти, первый 4, четвертый 5, пятый 6, второй 7, шестой 8 и седьмой 9 регистры, вычислительный блок 10, третий 11, восьмой 12 и девятый 13 регистры, четвертый 14, пятый 15, шестой 16, седьмой 17, первый 18, второй 19, третий 20, восьмой 21 и девятый 22 блоки элементов И,

первый 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.

В основу работы устройства положен алгоритм умножения матрицы А faij на матрицу В bij, определяющий матрицу

О

ел о ел о о

С cij (I 1n; j - 1n, где п - порядок

матрицы):

n

cij 2 aik bkj(1)

k - 1

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

парных произведений cijk cij1 1 + aiK bkj

(2)

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

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

В данном случае будем рассматривать разреженную матрицу В с одним ненулевым элементом в столбце при любой степени разреженности матрицы А.

Устройство работает следующим образом.

По сигналу с первого выхода блока управления последовательно формируются адреса, в соответствии с которыми производится запись чисел первого и второго трех- мерных массивов, представляющих соответственно разреженные матрицы А и В, в блоки 1 и 2 памяти. Одновременно осуществляется запись ненулевых элементов aik 1-й строки матрицы А с их значениями индекса строки и индекса столбца в регистры 4-6 через блоки 14-16 элементов И. При этом блок управления по второму выходу

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

0 управления по входу признака окончания строки, и по второму выходу блока управления запрещается передача чисел через блоки 14-16 элементов И После записи чисел обоих массивов в блоки 1 и 2 памяти и i-й строки

5 первого массива в блок 3 памяти блок управления по первому выходу формирует адрес первой ячейки.

В соответствии с первым адресом из второго блока памяти в регистры 7-9 считыва0 ются соответственно значение элемента bkj. значение индекса k и значение индекса j.

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

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

Если числа по этому адресу не оказалось в блоке 3 памяти, о чем свидетельству5 ет нулевое значение кода в регистре 5, то сигнал с выхода регистра 5 через элемент ИЛИ 28 запирает блоки 18 и 19 элементов И. Из блока 2 памяти считывается следующий элемент массива чисел в регистры 7-9.

0 Окончание первого столбца массива чисел, записанного в блоке 2 памяти, определяется появлением нулевого кода в регистре 8, сигналы с выхода которого, проходя через элемент ИЛИ 27 и элемент НЕ 31, открывает

5 блоки 20-22 элементов И, и осуществляется передача числа cij из вычислительного блока в регистр 11 через блок 20 элементов И, значения индекса строки I элемента cij из регистра 5 в регистр 12 через блок 21 эле0 ментов И. значения индекса столбца J элемента Cij из регистра 9 в регистр 13 через блок 22 элементов И. Таким образом, с выходов 41-43 устройства снимается элемент результирующей матрицы cij, образующей5 ся путем получения парных сомножителей в умножителе 44 и накопления их в сумматоре 45. При этом накапливающий сумматор 45 обнуляется.

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

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

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

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

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

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

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

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

блока элементов И выход которогосоединен с третьим входом третьего олока элементов

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

0 второго блока памяти соединены соотвест- венно с информационными входами шестого и седьмого регистров, выход шестого регистра соединен с вторым входом седьмого блока элементов И и входами второго

5 элемента ИЛИ, выход которого соединен с входом второго элемента НЕ, выход которого соединен с вторым входом третьего блока элементов И, первыми входами восьмого и девятого блоков элементов И и первым вхо0 Д°м элемента И, второй вход и выход которого соединены соответственно с выходом последнего разряда седьмого регистра и входом признака последнего столбца блока управления, выход седьмого регистра сое5 динен с вторым входом девятого блока элементов И, второй вход восьмого блока элементов И соединен с вторым выходом четвертого регистра и входом третьего элемента ИЛИ, выход которого соединен с вторыми входами первого и второго блоков

элементов И, выходы восьмого и девятого блоков элементов И соединены с информационными входами соответственно восьмоJJ 31 35

Элементы матрицы В

ч

Элементы

матрицы А aih

Фиг. 2

го и девятого регистров, выходы которых являются соответственно вторым и третьим выходами устройства

36 J7 38

фиг.1

Элементы мотрицб/ с

Ц

v

фигЗ