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

 

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

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК (19) (I () (s()s G 06 F 15/347

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4767451/24 (61) 1656560 (22) 27.09.89 (46) 07.10.92, Бюл, М 37 (71) Институт кибернетики им. В,М.. Глушкова (72) Л.Д. Елфимова, В.В. Коломейко, И.Г.

Мороз-Подворчан и В.Д. Петущак (56) Авторское свидетельство СССР

М 1656560, кл. G 06 F 15/347, 1988. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ РАЗРЕЖЕННЫХ МАТРИЦ (57) Изобретение относится к вычислительной технике, может быть использовано в специализированных вычислительных машинах для умножения разреженных и сверхразреженных матриц, умножения разреженной и плотной матриц, умножения разреженной матрицы на заполненный векИзобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах для умножения разреженных матриц, умножения разреженной и плотной матриц, умножения разреженной матрицы на вектор. Такие ситуации возникают при решении следуюших классов матричных задач: прямого решения разреженной системы линейных алгебраических уравнений, разреженных обычных и обобщенных спектральных задач, алгебры разреженных матриц и др.

В данном случае рассмотрим неструктурированные разреженные матрицы, т. е, матрицы общего вида с произвольным расположением ненулевых элементов. тор-столбец и является усовершенствованием изобретения по авт, св, СССР М 1656560.

Цель изобретения — расширение функциональных возможностей за счет умножения матриц общего вида, Устройство для перемножения матриц содержит два блока памяти для хранения нулевых элементов разреженных матриц, блок памяти для хранения нулевых элементов i-й строки одной из исходных матриц со значением их индексов строки, процессорный блок, регистры индексов строки и столбца перемножаемых матриц, буферные регистры индексов строки и столбца элементов результирующей матрицы, выходные регистры индексов строки и столбца результирующей матрицы, регистры элементов исходных и результирующей матриц, группы элементов И, группы элементов ИЛИ, НЕ, элемент И, 2 ил, Известны линейные и ортогональные процессоры для умножения матриц, матрицы на вектор, ленточных матриц (Зарубеж-;Од, ная радиоэлектроника, N. 7, 1987, М.: Радио и связь, с. 8-9, рис, 1а, б. рис, 3, рис. 5, Гунь ц

Суньюань, Систологические волновые матричные процессоры для высокопроизводи- тельных вычислений, — ТИИЭР, т. 72, 1984, N- 7, с, 142, рис. 10б. Достоинствами аналогов являются высокая лроизаодителвноств. зф- ) ° фективная загрузка процессорных блоков при умножении плотных матриц.

Обработка неструктурированных разреженных матриц на таких систологических структурах является черезвычайно неэкономичной, поскольку такие структуры на учитывают степень разреженности и сходных

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

В качеСтве прототипа выбрано устройство для у ножения разреженных матриц по авт. св. СССР KL 1656560, кл. G 06 F

15/347, 1988. НедостаткоМ прототипа является. ограничение функциональных возможностей, так как устройство перемножает матрицы, одна из которых может быть любой степени разреже",ности, а другая — с одним ненулевым элементом в столбце (диагональная и др.).

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

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

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

20

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

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

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

На фиг. 1 представлена функциональная схема предлагаемого устройства; на фиг, 2 — блок-схема процессорного блока.

Устройство содержит запоминающий блок 1 и запоминающий блок 2, обеспечивающие хранение ненулевых элементов перемножаемых разреженных матриц А и B.

Каждый ненулевой элемент матриц сопровождается индексной информацией о его местоположении в матрице. Причем ненулевые элементы первой разреженной матрицы хранятся в запоминающем блоке 1 по

1767502

10

45

55 строкам, и строки между собой разделены нулевым кодом, а ненулевые элементы второй разреженной матрицы вводятся в запоминающий блок 2 по столбцам, которые тоже разделены нулевым кодом. Признаком конца всех столбцов, т, е, признаком конца матрицы В, является нулевой код, в последнем разряде которого записана единица.

Запоминающий блок 3 служит для х, .анения ненулевых элементов i-й строки матрицы А с их значениями индекса строки, где

i 1 - и, n — порядок матрицы. Регистры 4 и

5 служат для приема соответственно значений элементов строк матрицы А и значений их индексов строк для последующей их записи в запоминающий блок 3 по адресу, равному значению индекса столбца этого элемента, записанного в регистре 6. Таким образом, регистр 6 является адресным регистром запоминающего блока 3, Числовой регистр 7 служит для приема числовых значений ненулевых элементов столбцов матрицы В, индексный регистр 8— для приема числовых значений индексов стирок элементов матрицы В, индексный регистр 9 — для приема числовых значений индексов столбцов элементов матрицы В, В устройство входит процессорный .блок 10, который производит формирование элементов результирующей матрицы С путем выполнения операции умножения с накоплением, и содержит блок умножения и накапливающий сумматор. Устройство содержит также числовой регистр 11, служащий для приема числовых значений элементов результирующей матрицы С, буферные индексные регистры 12 и 13, обеспечивающие временное хранение числовых значений индексов соответственно строки и столбца элементов результирующей матрицы С, выходные регистры 14 и 15, обеспечивающие прием числовых значений индексов соответственно строки и столбца элементов результирующей матрицы С, группы элементов И 16 — 26, группы элементов ИЛИ 2729, элемент И 30, элементы ИЛИ 31 — 33, элементы НЕ 34, 35, блок 36 управления.

Устройство содержит информационные входы 37 — 39 первой матрицы А, информационные входы 40 — 42 второй матрицы В, входы 43, 44 блока управления, соединенные соответственно с управляющей шиной записи и тактовой шиной устройства, информационныее выходы 45-47 результирующей матрицы С.

Блоки устройства соединены следующим образом.

Входы 37 — 39 устройства соединены соответственно с первым, вторым, третьим входами первого запоминающего блока 1 и с первыми входами соответственно групп элементов И 16, 17, 18, вторые входы которых соединены с вторым выходом блока 36 управления, Первый, второй, третий выходы первого запоминающего блока 1 и выходы групп элементов И 16, 17, 18 объединены соответственно группами элементов ИЛИ 27, 28, 29, выходы которых соединены соответственно с первым входом регистра 4 элементов первой матрицы, первым входом регистра 5 индекса строки элементов первой матрицы и входом регистра 6 индекса столбца элементов первой матрицы. Выходы регистров 4, 5, 6 соединены соответственно с первым, вторым, третьим входами запоминающего блока 3, первый и второй выходы которого соединены соответственно с вторым входом регистра 4 элементов первой матрицы и вторым входом регистра

5 индекса строки элементов первой матрицы. Кроме того, выход регистра 6 соединен через элемент ИЛИ 33 и элемент НЕ 34 с третьим входом блока 36 управления. Входы 40-42 устройства соединены соответственно с первым, вторым, третьим входами второго запоминающего блока 2, первый, второй, третий выходы которого соединены соответственно с входами регистра 7 элементов второй матрицы, регистра 8 индекса строки элементов второй матрицы, регистра

9 индекса столбца элементов второй матрицы.

Второй выход регистра 4 и выход регистра 7 соединены соответственно через группы элементов И 20 и 21 с первым и вторым входами процессорного блока 10, выход которого соединен с первым входом груп и ы элементов И 24. В ыход последнего соединен с входом регистра 11 результирующей матрицы, выход которого соединен с выходом 45 устройства. Выход регистра 8 индекса строки второй матрицы соединен с первым входом группы элементов И 19, второй вход которой соединен с третьим входом блока 36 управления, а выход — с третьим входом группы элементов ИЛИ 29.

Кроме того, выход регистра 8 индекса строки второй матрицы соединен через элементы ИЛИ 31 и элемент НЕ 35 с вторыми входами групп элементов И 24, 25, 26 и первым входом элемента И 30, второй вход которого соединен с выходом последнего разряда регистра 9 индекса столбца второй матрицы, а выход — c четвертым входом блока 36 управления. Выход регистра 5 индекса строки первой матрицы соединен с входом элемента ИЛИ 32, выход которого соединен с первыми входами групп элементов И 22 и

23 и вторыми входами групп элементов И 21 и 20. Кроме того, выход регистра 5 индекса

1767502 строки первой матрицы и выход регистра 9 индекса столбца второй матрицы соединены соответст енно с первыми входами групп элементов И 22 и 23, выходы которых соединены соответственно с входами бу- 5 ферного регистра 12 индекса строки результирующей матрицы и буферного регистра 13 индекса столбца результирующей матрицы.

Выходы последних соединены соответственно с пе".;выми входами групri элементов 10

И 25 и 26, выходы которых соединены соответственно с входами выходных регистров

14 и.15 индексов строки и столбца элементов результирующей матрицы, выходы которых являются соответственно выходами 46 15 и 47 устройства, Первый выход блока 36 управления соединен с четвертыми входами соответственно первого и второго запоминающих блоков 1 и 2, четвертый выход блока

36 управления соединен с пятым входом 20 первого запоминающего блока.

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

В основу работы устройства положен алгоритм умножения матрицы А.= (а1) на 25 матрицу В = (Ь;Д, определяющий матрицу С

= (cij) (i = 1, ..., и; j = 1, ..., n, где n — порядок матрицы):

cij = g аи Ьц.

k=1

Под управлением первого выхода блока

36 управления последовательно формируются адреса ячеек первого и второго запо35 минающих блоков 1 и 2, в соответствии с которыми производится запись чисел первого и второго трехмерных массивов, представляющих соответственно разреженные матрицы А и В, в запоминающие блоки 1 и

2, Ненулевые элементы матриц со значениями их индексов (трехмерные массивы) поступают в блоки 1 и 2 непрерывно с ин- 45 тервалом в один такт, Первая поступающая в блок 1 строка матрицы А, а именно ее ненулевые элементы с индексом строки, одновременно поступает и в блок 3 по адресу, равному индексу столбца этих ненулевых элементов, По50 скольку разреженная матрица А может содержать строки, в которых отсутствуют ненулевые элементы (особенно сверхразреженная матрица) и порядок поступления строк может быть произвольным, обозна55 чим первую строку матрицы А, поступающую в блок 1 и блок 3, i-й строкой с ненулевыми элементами ац и индексами i u

К где i = 1 - п, п — порядок матрицы.

Таким образом, ненулевые элементы первой строки матрицы А со значениями. индексов строки и столбца поступают в регистры 4, 5, 6 через группы элементов И 16, 17, 18. При этом блок 36 управления по второму выходу выдает тактовые импульсы, которые открывают группу элементов И 16, 17, 18, и через элементы ИЛИ 27, 28, 29 производится запись значений чисел в регистры

4, 5, 6. Значения чисел, записанных в регистрах 4 и 5, записываются далее в запоминающий блок З.по адресу, записанному в регистре 6. Поступление остальных строк матрицы А в блок 3 блокируется, а именно при появлении в регистре 6 адреса нулевого кода, отделяющего первую строку от следующей, сигнал с выхода этого регистра, и ройдя через элемент ИЛИ 33 и элемент НЕ 34, поступает на третий вход блока 36 управления, по второму выходу которого запрещается передача чисел через элементы И 16, 17, 18. После записи чисел обоих массивов в запоминающем блоке 1 и 2 и первой строки первого массива в запоминающий блок 3 блок 36 управления по первому выходу управляет формированием адреса первой ячейки.

В соответствии с,первым адресом из второго запоминающего блока 2 в регистры

7, 8, 9 считываются соответственно значения элемента bki, его индекса k и индекса j, блок 36 управления по третьему выходу открывает группу элементов И 19 и через группы элементов И 19 и ИЛИ 29 осуществляется передача содержимого регистра 8 в регистр 6 адреса.

Если по второму адресу существует парный сомножитель а в запоминающем блоке 3, то значение элемента alk и значение его индекса i считываются из запоминающего блока 3 в регистры 4 и 5 соответственно.

После этого значения элементов Bik и t)ik одновременно передаются в процессорный блок 10 при помощи управляющего сигнала, поступающего с выхода регистра 5 через элемент ИЛИ 32 и открывающего группы элементов И 20 и 21, Этот же сигнал разрешает прохождение значений индекса! и индекса j соответственно в буферные индексные регистры 12 и 13 через группы элементов И 22 и 23 соответственно, Сигнал, открывающий группы элементов И 24, 25, 26 и разрешающий прохождение чисел в регистры 11, 14, 15, поступает только по окончании очередного столбца матрицы В.

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

35, открывает группы элементов И 24, 25, 26.

1767502

10 и осуществляется передача элеменга cii результирующей . трицы С из процессорного блока 10 в регистр 11 через группу элементов И 24, а также его значения индекса строки i из буферного регистра 12 в регистр 14 через группу элементов И 25 и значения его индекса столбца j из буферного регистра 13 и регистр 15 через группу элементов И 26.

Таким образом, с выходов 45, 46, 47 устройства снимается ненулевой элемент результирующей матрицы С - с, образующийся путем умножения парных сомножителей строки матрицы А и столбца матрицы

В в умножителе 48 и накопления их в сумматоре 49. При этом накапливающий сумматор

49 обнуляется.

Если ненулевые элементы очередного столбца матрицы не находят себе парных сомножителей в запоминающем блоке 3, о чем свидетельствует нулевое значение кода в регистре 5, то сигнал с выхода регистра 5 через элемент ИЛИ 32 запирает группу элементов И 20, 21, 22, 23 и по окончании этого столбца матрицы В с выходов 45, 46, 47 устройства снимается нулевой элемент результирующей матрицы С.

Таким образом, в каждом такте работы устройства в регистры 7, 8, 9 из запоминающего блока 2 считываются ненулевые элементы всех столбцов матрицы В, которые умножаются на парные сомножители i-й строки матрицы А, а с выходов 45, 46, 47 устройства снимаются все элементы i-й

37 38 39 строки результирующей разреженной матрицы С.

Аналогично осуществляется умножение всех столбцов матрицы В на следующую (i+

5 1)-ю строку матрицы А, которая считывается из запоминающего блока 1 по сигналу, поступающему с четвертого выхода блока 36 управления, фиксирующему сигнал по четвертому входу, поступающему по окончании

10 всех столбцов матрицы В с выхода последнего разряда регистра 8 через элемент И 30.

Таким образом, предлагаемое устройство перемножает матрицы с любой степенью

" разреженности, что расширяет функцио15 нальные возможности.

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

Устройство для умножения разреженных матриц по авт, св. СССР hL 1656560, о т л и ч а ю щ е е с я тем, что, r. целью

20 расширения функциональных возможностей за счет умножения матриц общего вида, в устройство дополнительно введены десятый и одиннадцатый регистры и десятый и одиннадцатый блоки элементов И, 25 причем второй вход восьмого блока элементов И соединен с выходом четвертого регистра через десятый регистр и десятый блок элементов И, второй вход которого подключен к выходу третьего элемента ИЛИ, а вто30 рой вход девятого блока элементов И соединен с выходом седьмого регистра через одиннадцатый регистр и одиннадцатый блок элементов И, второй вход которого соединен с выходом третьего элемента ИЛИ, 1767502

РыР

40 --.

50

Составитель Ю.Кривонос

Техред М.Моргентал Корректор М,Максимишинец

Редактор Л.Волкова

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

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

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

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

ЭЯРМВн

Ndmpug

3xe eaivi i

Авиа,ы 3,:

Зллюлюы

wumpii4u Р

С