Устройство для операций над матрицами

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК 4 б 17 606 Р 15/3 ЫЙ КОМИТЕТИЯМ И ОТКРЫТИЯ ГОСУДАРСТВПО ИЗОБРЕТЕПРИ ГКНТ СС ОПИСАНИЕ ИЗОБРЕТЕН ел лаЕРАЦИЙ Н 54) УСТРОЙСТВО ДМАТРИЦАМИ вода ин ование изм жност(Ы жат двумероков и, сленедостатки, воляют вью алгоритму для вы пол неимер систоь.атричных инеику опеолее эффекВТОРСКОМУ СВИДЕТЕЛЬСТ(56) Авторское свидетельство СССРМ 1401478, кл. О 06 Р 15(347, 1986.Кухарев Г.А, и др. Систолическицессы для обработки сигналов, Минскрусь, 1988, с. 29,Изобретение относится к области вычислительной техники и может быть использовано в специализированных системах цифровой обработки информации,Известен ряд устройств, реализующих операции над матрицами, например однородная параллельная вычислительная структура для вычисления произведения матрицы на вектор матричный вычислитель; устройство для выполнения матричных операций.Указанные устройства содержат двумерную матрицу операционных блоков и средства организации вычислительного процесса (регистры, триггеры, блоки синхронизации), Все эти устройства позволяют выполнять операции над матрицами (умножение матрицы на вектор и т.д.) и имеют следующие недостатки, бол ьшие ап па ратные затраты при реализации двумерных матриц операционных блоков; сложности(57) Изобретение относится к вычислительной технике и может быть использовано в специализированных системах цифровой обработки информации. Цель изобретения - расширение функциональных возможностей за счет решения задачи разложения Холецкого симметричных матриц. Цель достигается тем, что в устройство, содержащее и блоков памяти и (и - 1) вычислительных блоков, введен дополнительный п-й вычислительный блок, позволяющий выполнять операции деления и извлечения квадратного корня и организовать вычислительный процесс, в котором на каждой итерации матрица представляется в факторизованной форме. 1 з,п, ф-лы, 5 ил.Ж органиэации многомерного в ции; неэффективное использ лительного ресурса при размерностизадачи;невозмо нения разложения матриц.Известны устройства, пр ные для 0-разложения матри систолические процессоры дл вычислений.Эти устройства также содер ные матрицы операционных бл довательно, имеют указанные Кроме того, устройства не поз полнять разложение матриц и Холецкого.Известен ряд устройств ния матричных операций, напр лические процессоры для операций.Эти устройства содержат л рационных блоков. позволяют бтивно использовать вычислительный ресурс, но не позволяют выполнять разложение Холецкого симметричных матриц.Наиболее близким к данному являетсяустройство, содержащее две матрицы из пзапоминающих ячеек и п вычислительныхячеек соответственно, причем каждая запоминающая ячейка представляет собой дуальный буфер из памяти типа Я РО, а каждаявычислительная ячейка содержит регистры,умножитель и сумматор.Устройство обеспечивает аффективнуюобработку многомерных сигналов, в частности спектральный анализ, Недостатком этого устройства являются ограниченныефункциональные возможности в задачахцифровой обработки сигналов, не позволяющие выполнить целый ряд алгоритмов,связанных с разложением Холецкого симметричных матриц,Целью изобретения является расширение функциональных возможностей устройства путем выполнения разложенияХолецкого симметричных матриц.Поставленная цель достигается тем, чтов устройство введена дополнительная вычислительная ячейка с соответствующимисвязями, позволяющая выполнять операции извлечения квадратного корня и деления, а также новые архитектурные решениявычислительных ячеек, входящих в матрицувычислительных ячеек,Для обеспечения вычисления разложения Холецкого симметричных матриц в известное устройство введенадополнительная вычислительная ячейка, которая позволяет на каждом шаге итерационного процесса вычислять одинвектор-столбец нижней треугольной матрицы в разложении Холецкого. Кроме того,новые а рхитектурн ые решен ия вы числ ительных ячеек позволили организовать вычислительный процесс таким образомчтобы на каждой итерации матрица А(представлялась в факторизованной формеф) ,.+ В 1) рт;+1 Гдв ,+ - МатрИца фрОбЕниуса, ( + 1)-й столбец которой совпадает с( + 1)-м столбцом нижней треугольной матрицы в разложении Холецкого, а матрицаВ) имеет видОт(+г0А(фц В(н.1) На фиг, 1 представлена функциональная схема предлагаемого устройства как пример конкретной реализации; на фиг, 2 - функциональная схема п-й вычислительной ячейки; на фиг. 3 - функциональная схема)-й вычислительной ячейки ) = 1, и = 1); на фиг. 4 - организация потоков информации в вычислительных ячейках; на фиг. 5 - временная диаграмма работы вычислительных ячеек.5 Устройство (фиг, 1) для разложения Холецкого симметричных матриц содержит информационный вход 1, матрицу 2 из п запоминающих ячеек (ЗЯ) 3, информационный выход 4, и-ю вычислительную ячейку 10 (ВЯ) 5, матрицу 6 из(п - 1 ВЯ, причем первыевход и выход)-й ) = 2, и) ВЯЗ соединены с первыми выходом и входом соответственно 0 - 1)-й ВЯ 7, а первые вход и выход первой ЗЯЗ соединены с первыми выходом и вхо дом и-й ВЯ 5; второй выход)-й 0 = , и - 1) ЗЯЗподключен к второму выходу 0 + 1)-й ЗЯЗ, второй выход и-й ЗЯЗ является информационным выходом 4 устройства, а второй вход первой ЗЯЗ является информационным вхо дом 1 усттройствавторой и третий выходы)-й ) = 1, и - 2) ВЯ 7 подключены соответственно к второму и третьему входу 0+ 1)-й ВЯ 7, а второй и третий выходы и-й ВЯ 7 подключены к второму и третьему входам первой 25 ВЯ 7; четвертый вход )-й 0 = 1, и - 2) ВЯ 7соединен с четвертым выходом ) + 1)-й ВЯ 7, а четвертый выход первой ВЯ 7 подключен к второму входу и-й ВЯ 5.Вычислительная ячейка с номером п со держит (фиг. 2) первый вход 5,1, первый выход 5,2, третий выход 5.3, второй вход 5.4, второй выход 5.5, регистр 8, блок 9 вычисления квадратного корня, мультиплексор 10, блок 11 вычисления обратной величины, 35 сумматор 12, регистр 13, умножитель 14,блок 15 изменения знака числа, регистр 16, причем вход 5,1 соединен с первым входом сумматора 12 и входом блока 9 вычисления квадратного корня, выход которого соеди нен с входом блока 11 вычисления обратнойвеличины и первым входом мультиплексора 10; второй вход мультиплексора 10 подключен к выходу сумматора 12, а выход мультиплексора 10 соединен с входом регистра 8, 45 выход которого является выходом 5.2 п-йВЯ 5; выход блока 11 вычисления обратной величины соединен с входом регистра 13, выход которого является выходом 5.5 и-й ВЯ 5; второй вход сумматора 12 соединен с 50 выходом умножителя 14, первый вход которого объединен с входом блока 15 изменению знака числа и является входом 5,4 и-й ВЯ 7, а второй вход умножителя 14 соединен с выходом блока 15 изменения знака числа 55 и входом регистра 16, выход регистра 16является выходом 5,3 и-й ВЯ 5.Вычислительная ячейка 7 с номером(5) 10 А(о) ),) т тий выход 7.4, четвертый вход 7,5, второй выход 7,6, второй вход 7,7, четвертый выход 7,8, мультиплексоры 17 - 19, умножитель 20, сумматор 21, регистры 22 - 25 и мультиплексор 26, причем вход 7,2 подключен к первым входам мультиплексоров 17 - 18, выходы которых соединены с первыми входами умножитепя 20 и сумматора 21, Второй вход мультиплексора 17 объединен с вторым входом мультиплексора 26 и является входом 7,5 ВЯ 7, а второй вход мультиплексора 18 соединен с входом константы "0". Первый вход мультиплексора 26 подключен к выходу умножителя 20 и второму входу сумматора 21, выход которого соединен с входом регистра 22. Выход регистра 22 является выходом 7.3 ВЯ 7. Выход мультиплексора 26 соединен с входом регистра 25, выход которого является выходом 7,8 ВЯ 7, Второй вход умножителя 20 подключен к выходу мультиплексора 19, первый вход которого объединен с входом регистра 23 и является входом 7.7 ВЯ 7, а второй вход мультиплексора 19 объединен с входом регистра 24 и является входом 7.1 ВЯ 7. Выходы регистров 23 - 24 являются соответственно выходами 7.6 и 7,4 ВЯ 7,Устройство работает следующим образом.Симметричная положительно определенная матрица А(0) может быть единственным способом разложена на множители где ( - нижняя треугольная матрица.Матрица ( может быть представлена ввиде 1 = ( 1 1.2 " Ь (2) где,1 = Е+ т 1 1, Е - единичная матрица;т 7(, - единичный вектор, вектор 4 определяется из первого столбца матрицы А( которая формир(уется слеующим образом. Если матрицу А),= О, и - 1 представить в виде где В - матрица) порядка (и -- 1),то матрица А порядка (и - 1 - 1) формируется в соответствии с выражением 15 20 25 30 35 40 45 50 55 Элементы вектораопределяются из выражения где а ) - )-й элемент первого столбца мат(ь 1)рицы А( Таким образом, столбцы матрицы ( совпадают с векторами К т.е, 1 = 1 к где 1 - )-й столбец матрицы ( Формирование матрицы (. производится за и итераций, На каждой итерации формируется один вектор-столбец матрицы (., причем на 1-й итерации ( =1, и) формируется -й вектор- столбец матрицы. Так как 1-й вектор-столбец матрицы ( содержит (и - (+ 1) отличных от нуля элементов, то в формировании элементов (-го вектор-столбца матрицы ( участвуют (и -+ 1) вычислительная ячейка ВЯ. причем-й элемент вектор-столбца формирует ячейка ВЯ 0, а элемент с номером+ )= 1, и - ) формирует )-я ячейка ВЯ. Организация потока данных на входе матрицы ячеек ВЯ показана на фиг. 5. Рассмотрим организацию вычислительного процесса на одной из итераций, например первой, в результате которой формируется первый вектор-столбец матрицы ( и матрица А , В устройстве реализуется конвей(-1)ерный принцип обработки информации. формирование первого. вектор-столбца начинается с ввода в) микротакте т 0 в ячейку ВЯо элемента а(0 матрицы А, В микротакте то в ячейке ВЯп формируются с помощью блока 9 вычисления кваДратного корня и блока 11 вычисления обратной величины два параметра. Первый параметр, равный (а 0) ) , является вычисленным значением первой координаты вектор- столбца 1,1 и через мультиплексор 10 и регистр 8 передается в ячейку ЗЯ 1,Второй параметр, равный ( аф участвует в формировании остал ьн ых кос рдинат вектор-столбца 1,1 в соответствии с выражением (5). Этот параметр с помощью регистра 13 ячейки 5 ВЯп и регистров 23 ячеек 7 ВЯ)= 1, и - 1) распространяется по матрице 6 ячеек 7 ВЯ). Параметр (а) )в микротакте тк (к = 1, и = 1) поступает на вход 7.7 ячейки 7 ВЯ) и далее через мультиплексор 19 на вход умножитепя 20 ячейки 7 ВЯ, на второй вход умножителя 20 в этот момент подается элемент ат матрицы А. Произведение э(,а)- через сумматор 21 и регистр 22 в следующем микротакте будет передано в ячейку 3 ЗЯь Мультиплексор 18 в этом микротакте (Ъ) на второй вход сумматора 21 подключает код иО", Это же произведение через мультиплексор 26 поступает на вход регистра 25, Таким образом, в ячейке 7 ВЯ в микротакте с информационные потоки коммутируются следующим образом;Выход мультиплексора 19 - вход 7.7 Выход мультиплексора 18- иОи Выход мультиплексора 26 - выход умно- жителя 19Выход мультиплексора 17 - вход 7.2 В остальных микротактах на выходы мультиплексоров ячейки ВЯ коммутируются вторые входы мультиплексоров. В ячейке 5 ВЯП на выход мультиплексора 10 в микро- такте т подключается блок 9 вычисления квадратного корня. Управление мультиплексора ячеек ВЯ; (1 = 1, и) производится с помощью управляющих битов, которые сопровождают элементы матриц А.Таким образом на первых и микротактах (ь, к = О, и - ф формируются элементь вектор-столбца 1.1. Элементы матрицы А формируются начиная с микротакта с 2 по столбцам, причем формируются только элементы нижнего треугольника и главной диагонали, так как матрица А симметрична(1)Элементы в-го вектор-столбца матрицы А начинают формироваться с микротакта тг(т-ц, причем в ни б = 1, и-т) ячейке 7 формируется б + лт-и элемент гп-го вектор- столбца матрицы А . Из выражениями) имерем где 1 а тк = 1, л) определяется из )Ьц - элементы матрицы А в клеточном представлении (3),Элементы вектор-столб 1,1, участвующие в вычислениях по формуле (6), распространяются по матрице 6 вычислительных ячеек 7 в двух направлениях. Конвейер, образованный мультиплексорами 26 и регистрами 25, предназначенрля передачи элементов вектор-столбца 1,1 справо налево до ячейки 5. Вычислительной ячейке 5 с помощью блока 15 изменения знака числа производится умножение каждого элемента вектор-столбца 1,1 на, и элементы вектор- столбца -1 л пересылаются в вычислительные ячейки 7 по конвейеру, образованному регистром 16 ячейки 5 и регистрами 24 ячеек 7. В каждой вычислительной ячейке 7 через микротакт с помощью умножителя 20 и сумматора 21 производятся вычисления в соответствии с выражением (6),Элементы 1 р поступают на вход умноЯ.жителя 20 каждой вычислительной ячейки 7 с входа 7,1 через мультиплексор 19, а элементы 11)о - с входа 7.5 через мультиплексор 17. На сумматоре 21 каждой вычислительной ячейки 7 формируется элемент а " б 1,1)который через регистр 22 передается в со 5 ответствующую запоминающую ячейку 3,Временная диаграмма, поясняющая органиэацию потоков данных в матрице 6 вычислительных ячеек 7, приведена на фиг. 5 дляслучая = 4, На остальных итерациях процес 10 сор работает аналогичным образом. Отличие заключается в том, что на каждойследующей итерации в работу включаетсячисло вычислительных ячеек на единицуменьше, чем на предыдущей итерации (пра 15 вая вычислительная ячейка, участвующая вданной итерации в следующей участие непринимает).Каждая запоминающая ячейка 3 представляет собой дуальный буфер ОЗУ, кото 20 рый позволяет на фоне разложения текущейматрицы загружать в матрицу 2 запоминающих ячеек 3 следующую матрицу через шину1, Одновременно с загрузкой следующейматрицы из матрицы 2 запоминающих ячеек25 3 выводятся элементы матрицы 1, полученной в результате разложения предыдущейматрицы. Вывод производится через выход4,Таким образом, введением в известное30 устройство дополнительной вычислительной ячейки, новых архитектурных решенийвычислительных ячеек, объединенных в матрицу, и особой организации вычислительного процесса достигается расширение35 функциональных возможностей за счет решения задачи разложения Холецкого симметричных матриц,Формула изобретенияУстройство для операций над матрица 40 ми, содержащее и - 1 вычислительных блоков (и - размерность обрабатываемыхматриц) и п блоков памяти, причем первыеинформационный вход и выход -го блокапамяти Ц = 2, и) соединены соответственно45 с первыми выходом и информационным входом Ц - 1)-го вычислительного блока, второйвыход 1-го ( = 1, и) блока памяти подключен к второму информационному входу (1+1)- го блока памяти, второй информационный50 вход первого и второй выход и-го блоковпамяти являются соответственно информационным входом и выходом устройства, второй и третий выходы к-го блока памяти (к =1, и - 2) соединены соответственно с вторым55 и третьим информационными входами (К+1)-го вычислительного блока, о т л и ч а ющ е е с я тем, что, с целью расширенияфункциональных возможностей за счет разложения матриц Холецкого, в него введени-й вычислительный блок, первые информационный вход и выход которого подключены соответственно к первым выходу и информационному входу первого блока памяти, второй и третий выходы п-го вычисл ител ьн ого блока подключены соответственно к второму и третьему информационным входам первого вычислительного блока, четвертый информацион.ный вход к-го вычислительного блока подключен к четвертому выходу (К + 1)-го вычислительного блока, четвертый выход первого вычислительного блока - к второму информационному входу п-го вычислительного блока.2. Устройство по и. 1, о тл и ч а ю щ е,ес я тем, что -й вычислительный блок содержит умножитель, сумматор, четыре регистра и четыре мультиплексора, причем первые информационные входы первого и второго мультиплексоров объединены и подключены к первому информационному входу вычислительного блока, а выходы первого и второго мультиплексоров - к первым входам умножителя и сумматора соответственно, второй информационный вход первого мультиплексора соединен с вторым информационным входом третьего мультиплексора и является четвертым информационным входом вычислительного блока, второй информационный вход второго мультиплексора - с входом нуля устройства, выход третьего мультиплексора подключен к информационному входу первого регистра, выход которого является четвертым выходом вычислительного блока, первый информационный вход третьего мультиплексора соединен с выходом умножителя и вторым входом сумматора, выход которого подключен к информационному входу второго регистра, выход которого является первым выходом вычислительного блока, второй вход умножителя соединен с выходом четвертого мультиплексора, первый и второй информационные входы которого соединены соответственно с информационными 5 входами третьего и четвертого регистров,выходы которых являются соответственно вторым и третьим выходами вычислительного блока, вторым и третьим информационными входами которого являются 10 информационные входы третьего и четвертого регистров соответственно.3, Устройство по и. 1, отл и ч а ю ще ес я тем, что и-й вычислительный блок содержит узел вычисления квадратного корня, 15 узел вычисления обратной величины числа,три регистра, умножитель, сумматор, мультиплексор, узел изменения знака числа, причем первый информационный вход вычислительного блока соединен с первым 20 входом сумматора и входом узла вычисления квадратного корня, выход которого подключен к входу узла вычисления обратной величины числа, выход которого подключен к информационному входу первого регист ра, первый выход вычислительного блокаподключен к выходу второго регистра, информационный вход которого подключен к выходу мультиплексора, первый и второй информационные входы которого подклю чены соответственно к выходам узла вычисления квадратного корня и сумматора, второй вход которого соединен с выходом умножителя, первый вход которого соединен с входом узла изменения знака числа и 35 информационным входом третьего регистра, выход которого является третьим выходом и-го вычислительного блока, второй выход которого подключен к выходу первого регистра, второй вход и-го вычислительного 40 блока подключен к входу узла изменениязнака и второму входу умножителя,абаз 0 и О(щ оставитель В. Грачевехред М,Моргентал ректор С,Черни акто есивых каз 1893 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ С 113035, Москва, Ж, Раушская наб., 4/5 оизводственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 101