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

);,;);, ГДЕн) т Г 3. Н п ПИСА 30 им. В,М., ГлушкоКоломейко, И,Г.етущакво СССР47, 1988.НОЖЕНИЯ РАЗычислительльзовано в ельных маных и сверхмножения умножения ненный векГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИПРИ ГКНТ СССР АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(72) Л.Д. Елфимова, В,В.Мороз-Подворчан и В.Д. П (56) Авторское свидетельст М 1656560, кл. 0 06 Р 15/3 (54) УСТРОЙСТВО ДЛЯ УМ РЕЖЕННЫХ МАТРИЦ (57) Изобретение относится к в ной технике, может быть испо специализированных вычислит шинах для умножения разрежен разреженных матриц, у разреженной и плотной матриц разреженной матрицы на запол Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах для умножения разреженных матриц, умножения разреженной и плотной матриц, умножения разреженной матрицы на вектор. Такие ситуации возникают при решении следующих классов матричных задач: прямого решения разреженной системы линейных алгебраических уравнений, разреженных обычных и обобщенных спектральных задач, алгебры разреженных матриц идр,В данном случае рассмотрим неструктурированные разреженные матрицы, т. е, матрицы общего вида с произвольным расположением ненулевых элементов. тор-столбец и является усовершенствованием изобретения по авт, св, СССР М 1656560. Цель изобретения - расширение функциональных возможностей за счет умножения матриц общего вида, Устройство для перемножения матриц содержит два блока памяти для хранения нулевых элементов разреженных матриц, блок памяти для хранения нулевых элементов -й строки одной из исходных матриц со значением их индексов строки, процессорный блок, регистры индексов строки и столбца перемножаемых матриц, буферные регистры индексов строки и столбца элементов результирующей матрицы, выходные регистры индексов строки и столбца результирующей матрицы, регистры элементов исходных и результирующей матриц, группы элементов И, группы элементов ИЛИ, НЕ, элемент И, 2 ил,Известны линейные и ортогональные апроцессоры для умножения матриц, матрицы на вектор, ленточных матриц (Зарубеж-;Од,ная радиоэлектроника, йв 7, ) 987, М.: Радиои связь, с. 8-9, рис, 1 а, б. рис, 3, рис. 5, Гунь цСуньюань, Систологические волновые матричные процессоры для высокопроизводи- ( фтельных вычислений, - ТИИЭР, т. 72, 1984,М 7, с, 142, рис, 10 б. Достоинствами аналоговявляются высокая производительность. зф. )вфективная загрузка процессорных блоков Япри умножении плотных матриц,Обработка неструктурированных разреженных матриц на таких систологическихструктурах является чрезвычайно неэкономичной, поскольку такие структуры на учитывают степень разреженности и сходных5 10 15 20 25 30 40 45 50 55 матриц и рассчитаны на хранение и обработку всех членов матриц, что влечет за собой использование большого объема памяти, низкую производительность и низкую эффективность систологической матрицы, так как большую часть времени процессорные элементы выполняют умножение и сложение нулей.В качеСтве прототипа выбрано устройство для у ножения разреженных матриц по авт. св. СССР В 1656560, кл. 6 06 Р 15/347, 1988, НедостаткоМ прототипа является, ограничение функциональных возможностей, так как устройство перемножает матрицы, одна из которых может быть любой степени разреже",ности, а другая - с одним ненулевым элементом в столбце(диагональная и др,).Цель изобретения - расширение функциональных возможностей за счет умножения матриц общего вида.Цель достигается тем, что в устройство для умножения разреженных матриц, содержащее три запоминающих блока, процессорный блок, девять регистров, девять блоков элементов И, три блока элементов ИЛИ, один элемент И, три элемента ИЛИ, два элемента НЕ, причем первый, второй, третий входы устройства соединены соответственно с первым, вторым, третьим входами первого запоминающего блока и с первыми входами соответственно первого, второго, третьего блоков элементов И, вторые воды которых соединены с вторым выходом блока управления, первый, второй, третий выходы первого запоминающего блока и выходы первого, второго, третьего блоков элементов И объединены первым, вторым, третьим блоками элементов ИЛИ,выходы которых соединены соответственно с первыми входами первого и четвертого .регистров и входом восьмого регистра, выходы которых соединены соответственно с первым, вторым, третьим входами третьего запоминающего блока, первый и второй выходы которого соединены соответственно с вторыми входами первого и четвертого регистров, выход восьмого регистра соединен через первый элемент ИЛИ и первый элемент НЕ с третьим входом блока управления, четвертый, пятый., шестой входы устройства соединены соответственно с первым вторым, третьим входами второго запоминающего блока, первый, второй, третий выходы которого соединены соответственно с входами второго, пятого, седьмого регистров, выходы первого и второго регистров соединены соответственно через пятый и шестой блоки элементов И с первым и вторым входами процессорного блока,выход которого соединен с первым входом седьмого блока элементов И, выход которого соединен с входом третьего регистра, выход которого является первым выходом устройства, выход первого регистра соединен с вторым входом пятого блока элементов И, выход четвертого регистра соединен с входом третьего элемента ИЛИ, выход которого соединен с вторым входом шестого блока элементов И, выход пятого регистра соединен с первым входом. четвертого блока элементов И, второй вход которого соединен с третьим входом блока управления, а выход - с третьим входом третьего блока элементов ИЛИ, выход пятого регистра также соединен через второй элемент ИЛИ и второй элемент НЕ с вторыми входами седьмого, восьмого, девятого блоков элементов И и первым входом третьего элемента И, второй вход которого соединен с выходом последнего разряда седьмого регистра, а выход - с четвертым входом блока управления,первый выход блока управления соединен с четвертыми входами соответственно первого и второго запоминающих блоков, четвертый выход блока управления соединен с пятым входом первого запоминающего блока, выходы восьмого и девятого блоков элементов И соединены соответственно с входами шестого и девятого регистров, выходы которых являются соответственно вторым и третьим выходами устройства, первый и второй вхо-. ды блока управления соединены соответственно с управляющей шиной записи и тактовой шиной устройства, введены десятый и одиннадцатый регистры и десятый и одиннадцатый блоки элементов И причем второй вход восьмого блока элементов И соединен с выходом четвертого регистра через десятый регистр и десятый блок элементов И, второй вход которого подключен к выходу третьего элемента ИЛИ, а второй вход девятого блока элементов И соединен в выходом седьмого регистра через одиннадцатый регистр и одиннадцатый блок элементов И, второй вход которого соединен с выходом третьего. элемента ИЛИ.На фиг. 1 представлена функциональная схема предлагаемого устройства; на фиг, 2 - блок-схема процессорного блока.Устройство содержит запоминающий блок 1 и запоминающий блок 2, обеспечивающие хранение ненулевых элементов перемножаемых разреженных матриц А и В. Каждый ненулевой элемент матриц сопровождается индексной информацией о его местоположении в матрице. Причем ненулевые элементы первой разреженной матрицы хранятся в запоминающем блоке 1 по5 10 15 20 25 30 35 40 45 50 55 строкам, и строки между собой разделены нулевым кодом, а ненулевые элементы второй разреженной матрицы вводятся в запоминающий блок 2 по столбцам, которые тоже разделены нулевым кодом. Признаком конца всех столбцов, т, е, признаком конца матрицы В, является нулевой код, в последнем разряде которого записана единица.Запоминающий блок 3 служит для х,.анения ненулевых элементов 1-й строки матрицы А с их значениями индекса строки, где 1=1- и, и - порядок матрицы. Регистры 4 и 5 служат для приема соответственно значений элементов строк матрицы А и значений их индексов строк для последующей их записи в запоминающий блок 3 по адресу, равному значению индекса столбца этого элемента, записанного в регистре 6. Таким образом, регистр 6 является адресным регистром запоминающего блока 3,Числовой регистр 7 служит для приема числовых значений ненулевых элементов столбцов матрицы В, индексный регистр 8 - для приема числовых значений индексов стирок элементов матрицы В, индексный регистр 9 - для приема числовых значений индексов столбцов элементов матрицы В,В устройство входит процессорный блок 10, который производит формирование элементов результирующей матрицы С путем выполнения операции умножения с накоплением, и содержит блок умножения и накапливающий сумматор, Устройство содержит также числовой регистр 11, служащий для приема числовых значений элементов результирующей матрицы С, буферные индексные регистры 12 и 13, обеспечивающие временное хранение числовых значений индексов соответственно строки и столбца элементов результирующей матрицы С, выходные регистры 14 и 15, обеспечивающие прием числовых значений индексов соответственно строки и столбца элементов результирующей матрицы С, группы элементов И 16 - 26, группы элементов ИЛИ 27- 29, элемент И 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 индекса столбца второй матрицы, а выход - с четвертым входом блока 36 управления. Выход регистра 5 индексастроки первой матрицы соединен с входом элемента ИЛИ 32, выход которого соединен с первыми входами групп элементов И 22 и 23 и вторыми входами групп элементов И 21 и 20, Кроме того, выход регистра 5 индексастроки первой матрицы и выход регистра 9 индекса столбца второй матрицы соединены соответственно с первыми входами групп элементов И 22 и 23, выходы которых соединены соответственно с входами бу ферного регистра 12 индекса строки результирующей матрицы и буферного регистра 13 индекса столбца результирующей матрицы. Выходы последних соединены соответственно с пе".,выми входами групп элементов 10 И 25 и 26, выходы которых соединены соответственно с входами выходных регистров 14 и,15 индексов строки и столбца элементов результирующей матрицы, выходы которых являются соответственно выходами 46 15 и 47 устройства, Первый выход блока 36 управления соединен с четвертыми входами соответственно первого и второго запоминающих блоков 1 и 2, четвертый выход блока 36 управления соединен с пятым входом 20 первого запоминающего блока.Предлагаемое устройство работает следующим образом,В основу работы устройства положен алгоритм умножения матрицы А.= а на 25 матрицу В = Ь;Д, определяющий матрицу С = сД ( = 1, , и;= 1, ., и, где и - порядок матрицы):30с= аа Ьц. Под управлением первого выхода блока36 управления последовательно формируются адреса ячеек первого и второго запо 35минающих блоков 1 и 2, в соответствии скоторыми производится запись чисел первого и второго трехмерных массивов, представляющих соответственно разреженныематрицы А и В, в запоминающие блоки 1 и402,Ненулевые элементы матриц созначениями их индексов (трехмерные массивы)поступают в блоки 1 и 2 непрерывно с интервалом в один такт,Первая поступающая в блок 1 строкаматрицы А, а именно ее ненулевые элементы с индексом строки, одновременно поступает и в блок 3 по адресу, равному индексустолбца этих ненулевых элементов, По 50скольку разреженная матрица А может содержать строки, в которых отсутствуютненулевые элементы (особенно сверхразреженная матрица) и порядок поступлениястрок может быть произвольным, обозна 55чим первую строку матрицы А, поступающую в блок 1 и блок 3, -й строкой сненулевыми элементами аа и индексамииК где= 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 считываются соответственно значения элемента Ьц, его индекса М и индекса),Блок 36 управления по третьему выходу открывает группу элементов И 19 и через группы элементов И 19 и ИЛИ 29 осуществляется передача содержимого регистра 8 в регистр 6 адреса.Если по второму адресу существует парный сомножитель аа в запоминающем блоке 3, то значение элемента аа и значение его индексасчитываются из запоминающего блока 3 в регистры 4 и 5 соответственно. После этого значения элементов аа и Ьа одновременно передаются в процессорный блок 10 при помощи управляющего сигнала, поступающего с выхода регистра 5 через элемент ИЛИ 32 и открывающегогруппы элементов И 20 и 21, Этот же сигнал разрешает прохождение значений индексаи индекса ) соответственно в буферные индексные регистры 12 и 13 через группы элементов И 22 и 23 соответственно, Сигнал, открывающий группы элементов И 24, 25, 26 и разрешающий прохождение чисел в регистры 1114, 15, поступает только по окончании очередного столбца матрицы В. Как только нулевой код, отделяющий очередной столбец от следующего, поступит в регистр 8, сигнал с выхода этого регистра, пройдя через элемент ИЛИ 31 и элемент НЕ 35, открывает группы элементов И 24, 25, 26.и осуществляется передача элеменга с результирующей ,:трицы С из процессорного блока 10 в регистр 11 через группу элементов И 24, а также его значения индекса строки 1 из буферного регистра 12 в регистр 14 через группу элементов И 25 и значения его индекса столбца ) из буферного регистра 13 и регистр 15 через группу элементов И 26.Таким образом, с выходов 45, 46, 47 устройства снимается ненулевой элемент результирующей матрицы С - с, образующийся путем умножения парных сомножителей строки матрицы А и столбца матрицы В в умножителе 48 и накопления их в сумматоре 49. При этом накапливающий сумматор 49 обнуляется. Если ненулевые элементы очередного столбца матрицы не находят себе парных сомножителей в запоминающем блоке 3, о чем свидетельствует нулевое значение кода в регистре 5, то сигнал с выхода регистра 5 через элемент ИЛИ 32 запирает группу элементов И 20, 21, 22, 23 и по окончании этого столбца матрицы В с выходов 45, 46, 47 устройства снимается нулевой элемент результирующей матрицы С.Таким образом, в каждом такте работы устройства в регистры 7, 8, 9 из запоминающего блока 2 считываются ненулевые элементы всех столбцов матрицы В, которые умножаются на парные сомножители 1-й строки матрицы А, а с выходов 45, 46, 47 устройства снимаются все элементы 1-й37 ЗВ 39 строки результирующей разреженной матрицы С.Аналогично осуществляется умножениевсех столбцов матрицы В на следующую ( + 5 1)-ю строку матрицы А, которая считываетсяиз запоминающего блока 1 по сигналу, поступающему с четвертого выхода блока 36 управления, фиксирующему сигнал по четвертому входу, поступающему по окончании 10 всех столбцов матрицы В с выхода последнего разряда регистра 8 через элемент И ЗО.Таким образом, предлагаемое устройство перемножает матрицы с любой степенью " разреженности, что расширяет функцио нальные возможности.Формула изобретения Устройство для умножения разреженных матриц по авт, св. СССР М 1656560, о т л и ч а ю щ е е с я тем, что, с целью 20 расширения функциональных возможностей за счет умножения матриц общего вида, в устройство дополнительно введены десятый и одиннадцатый регистры и десятый и одиннадцатый блоки элементов И, 25 причем второй вход восьмого блока элементов И соединен с выходом четвертого регистра через десятый регистр и десятый блок элементов И, второй вход которого подключен к выходу третьего элемента ИЛИ, а вто рой вход девятого блока элементов Исоединен с выходом седьмого регистра через одиннадцатый регистр и одиннадцатый блок элементов И, второй вход которого соединен с выходом третьего элемента ИЛИ,1767502 3 0 Составитель Ю,КривоносТехред М.Моргентал Корректор М,Максимишинец актор Л.Вол аказ 3549 ТиражВНИИПИ Государственного комитет113035, Москва,тельский комбинат "Патент", г, Ужгород, ул.Гагарина, 10 оизводственн 3 ЛРИР тра ЗлемгюююАвжрй,ъу 3Ф Зллчллы жвраФь Р Подписноеизобретениям и открытиям при ГКНТ ССС , Раушская наб., 4/5