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

 

Изобретение относится к вычислительной технике и может быть использовано в специализированных системах цифровой обработки информации. Цель изобретения - расширение функциональных возможностей за счет решения задачи разложения Холецкого симметричных матриц. Цель достигается тем, что в устройство, содержащее п блоков памяти и (п - 1) вычислительных блоков, введен дополнительный n-й вычислительный блок, позволяющий выполнять операции деления и извлечения квадратного корня и организовать вычислительный процесс, в котором на каждой итерации матрица представляется в факторизованной форме. 1 з.п. ф-лы, 5 ил.

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

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

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

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

4 ! (АЭ ф

10с, (Ы (21) 4810759/24 (22) 06,04.90 (46) 30.05.92. Бюл. N. 20 (71) Центральный научно-исследовательский институт "Морфизприбор" (72) В.А. Грачев и Г,А. Кухарев (53) 681.3(088.8) (56) Авторское свидетельство СССР

М 1401478, кл. G 06 F 15/347, 1986.

Кухарев Г.А, и др. Систолические процессы для обработки сигналов, Минск, Беларусь, 1988, с. 29, (54) УСТРОЙСТВО ДЛЯ ОПЕРАЦИЙ НАД

МАТРИЦАМИ

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

Известен ряд устройств, реализующих операции над матрицами, например однородная параллельная вычислительная структура для вычисления произведения матрицы на вектор матричный вычислитель; устройство для выполнения матричных операций.

Указанные устройства содержат двумерную матрицу операционных блоков и средства организации вычислительного процесса (регистры, триггеры, блоки синхронизации), Все эти устройства позволяют выполнять операции над матрицами (умножение матрицы на вектор и т.д.) и имеют следующие недостатки, большие an паратные затраты при реализации двумерных матриц операционных блоков; сложности

- Ы 1737462 А1 (57) Изобретение относится к вычислительной технике и может быть использовано в специализированных системах цифровой обработки информации. Цель изобретения — расширение функциональных возможностей за счет решения задачи разложения

Холецкого симметричных матриц. Цель достигается тем, что в устройство, содержащее и блоков памяти и (и — 1) вычислительных блоков, введен дополнительный п-й вычислительный блок, позволяющий выполнять операции деления и извлечения квадратного корня и организовать вычислительный процесс, в котором на каждой итерации матрица представляется в факторизованной форме. 1 з,п, ф-лы, 5 ил. органиэации многомерного ввода информации; неэффективное использование вычислительного ресурса при изменении размерности задачи; невозможность выполнения разложения матриц.

Известны устройства, предназначенные для LU-разложения матриц, например, систолические процессоры для матричных вычислений.

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

Кроме того, устройства не позволяют выполнять разложение матриц по алгоритму

Холецкого.

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

Эти устройства содержат линейку операционных блоков. позволяют более эффек1737462

От

p д (I+ 2

B(1+1) =

На фиг. 1 представлена функциональная схема предлагаемого устройства как пример конкретной реализации; на фиг, 2— функциональная схема п-й вычислительной ячейки; на фиг. 3 — функциональная схема тивно использовать вычислительный ресурс, но не позволяют выполнять разложение Холецкого симметричных матриц.

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

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

Холецкого симметричных матриц.

Поставленная цель достигается тем, что в устройство введена дополнительная вычислительная ячейка с соответствующими связями, позволяющая выполнять операции извлечения квадратного корня и деления, а также новые архитектурные решения вычислительных ячеек, входящих в матрицу вычислительных ячеек, Для обеспечения вычисления разложения Холецкого симметричных матриц в известное устройство введена дополнительная вычислительная ячейка, которая позволяет на каждом шаге итерационного процесса вычислять один вектор-столбец нижней треугольной матрицы в разложении Холецкого. Кроме того, новые архитектурные решения вычислительных ячеек позволили организовать вычислительный процесс таким образом чтобы на каждой итерации матрица А( представлялась в факторизованной форме

А ) = F;+<8()FT(+>, где F1+) — матрица Фробениуса, (i + 1)-й столбец которой совпадает с (i + 1)-м столбцом нижней треугольной матрицы в разложении Холецкого, а матрица (i+1) имеет вид

j-й вычислительной ячейки (j = 1, n = 1); на фиг. 4 — организация потоков информации в вычислительных ячейках; на фиг. 5 — временная диаграмма работы вычислительных ячеек.

5 Устройство (фиг. 1) для разложения Холецкого симметричных матриц содержит информационный вход 1, матрицу 2 из п запоминающих ячеек (ЗЯ) 3, информационный выход 4, и-ю вычислительную ячейку

10 (ВЯ) 5, матрицу 6 из(п — 1) ВЯ, причем первые вход и выход j-й (J = 2, n) ВЯЗ соединены с первыми выходом и входом соответственно (j — 1)-й ВЯ7, а первые вход и выход первой

ЗЯЗ соединены с первыми выходом и вхо15 дом и-й ВЯ5; второй выход)-й () = Гn — 1) ЗЯЗ подключен к второму выходу (j + 1)-й ЗЯЗ, второй выход и-й ЗЯЗ является информационным выходом 4 устройства, а второй вход первой ЗЯЗ является информационным вхо20 дом 1 усттройства„второй и третий выходы

j-й (j = 1, n — 2) ВЯ7 подключены соответственно к второму и третьему входу (j + 1)-й ВЯ7, а второй и третий выходы и-й ВЯ7 подключены к второму и третьему входам первой

25 ВЯ7: четвертый вход j-й (j = 1, n — 2) ВЯ7 соединен с четвертым выходом (j + 1)-й ВЯ7, а четвертый выход первой ВЯ7 подключен к второму входу и-й ВЯ5.

Вычислительная ячейка с номером п со30 держит (фиг. 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 вычисления квадратного корня, выход которого соеди40 нен с входом блока 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 с номером

J (j = 1, n — 1) содержит (фиг, 3) третий вход

7.1, первый вход 7.2, первый выход 7,3, тре1737462

{5) 10

A(o) ),) т тий выход 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) может быть единственным способом разложена на множители где L — нижняя треугольная матрица.

Матрица L может быть представлена в виде

1 = L1 1-2 ". ° (-и (2) где = Е+ Tj ij, Š— единичная матрица; т (; — единичный вектор, вектор 4 определяется из первого столбца матрицы А(, которая формируется сле1рющим образом.

Если матрицу А ), i = О, и — 1 представить в виде т (, ) o(; b ;

Д = — — —, (3) b; i 5, где Bi — матрица порядка (n — i — 1), то матрица А порядка (и — i — 1) формируется в соответствии с выражением Т

А() = B {4)

Элементы вектора т определяются из выражения

oj<1

n(j) =.,(-1) ((-1),) 1/2 .а. ((й где а ) — j-é элемент первого столбца MBT(1-1) рицы А(Таким образом, столбцьi матрицы L совпадают с векторами К т.е, I; = 5, где 1 — i-й столбец матрицы L. Формирование матрицы L производится за и итераций. На каждой итерации формируется один вектор-столбец матрицы L, причем на i-й итерации (I =1, n) формируется I-й ВеКТОостолбец матрицы L. Так как i-й вектор-столбец матрицы L содержит (n — i + 1} отличных от нуля элементов, то в формировании элементов i-ro вектор-столбца матрицы Lучаствуют (и — i + 1) вычислительная ячейка BR. причем i-й элемент вектор-столбца формирует ячейка ВЯ, а элемент с номером I + j (j = 1, n — i) формирует j-я ячейка

ВЯ. Организация потока данных на входе матрицы ячеек ВЯ показана на фиг. 5. Рассмотрим организацию вычислительного процесса на одной из итераций, например первой, в результате которой формируется первый вектор-столбец матрицы L и матрица А, В устройстве реализуется конвей(-1) ерный принцип обработки информации.

Формирование первого вектор-столбца начинается с ввода в микротакте т0 в ячейку ВЯо элемента a„M Tp Ltb A, В микротакте to в ячейке ВЯп формируются с помощью блока 9 вычисления кваДратного корня и блока 11 вычисления обратной величины два параметра. Первый параметр. равный (а О) ), является вычисленным значением первой координаты векторстолбца i 1 и через мультиплексор 10 и регистр 8 передается в ячейку ЗЯ1, Второй параметр, равный (а(,,) )1 . участвует в формировании остал ьн ых кос рдинат вектор-столбца 1,1 в соответствии с выражением (5). Этот параметр с помощью регистра 13 ячейки 5 ВЯ и регистров 23 ячеек 7 ВЯ) (j = 1, n — 1) распространяется по матрице 6 ячеек 7 ВЯ). Параметр (а,, ) ) в микротакте tK (к = 1, n = 1) поступает на вход

7.7 ячейки 7 ВЯ) и далее через мультиплексор 19 на вход умножитепя 20 ячейки 7 ВЯ), на второй вход умножитепя 20 в этот МоМеНТ подается элемент а(< матрицы А(). Произведение а() (а,,) )- через сумматор 21 и регистр 22 в следующем микротакте будет передано в ячейку 3 ЗЯь Мультиплексор 18 в этом микротакте (t ) на второй вход сумма1737462 тора 21 подключает код и0", Это же произведение через мультиплексор 26 поступает на вход регистра 25, Таким образом, в ячейке 7 ВЯ в микротакте ti информационные потоки коммутируются следующим образом:

Выход мультиплексора 19 = вход 7.7

Выход мультиплексора 18 - иОи

Выход мультиплексора 26 - выход умножителя 19

Выход мультиплексора 17 - вход 7.2

В остальных микротактах на выходы мультиплексоров ячейки ВЯ коммутируются вторые входы мультиплексоров. В ячейке 5

ВЯ, на выход мультиплексора 10 в микротакте to подключается блок 9 вычисления квадратного корня. Управление мультиплексора ячеек ВЯ; (I = 1, n) производится с помощью управляющих битов, которые сопровождают элементы матриц A(i).

Таким образом на первых и микротактах (t<, к = О, и — 1) формируются элементь вектор-столбца 1.1. Элементы матрицы А( формируются начиная с микротакта t2 по столбцам, причем формируются только элементы нижнего треугольника и главной диагонали, так как матрица А симметричная (1)

Элементы m-го вектор-столбца матрицы А начинают формироваться с микротакта тгги-ij, причем в j-и (j = 1. и — mi ячейке 7 формируется jj + m -и элемент m-го векторстолбца матрицы Д . Из выражения (б) име1j ем а("Ikj = bÛOIkj — 0 1(о)ji, к = 1, n — 1, (6) где 1„g тк = 1, nj определяется из );

Ь ц — элементы матрицы А в клеточном представлении (3), Элементы вектор-столб I.1, участвующие в вычислениях по формуле (6), распространяются по матрице 6 вычислительных ячеек 7 в двух направлениях. Конвейер, образованный мультиплексорами 26 и регистрами 25, предназначен„рля передачи элементов вектор-столбца I,1 справо налево до ячейки 5. Вычислительной ячейке 5 с помощью блока 15 изменения знака числа производится умножение каждого элемента вектор-столбца I.1 на -1, и элементы векторстолбца -!.1 пересылаются в вычислительные ячейки 7 по конвейеру, образованному регистром 16 ячейки 5 и регистрами 24 ячеек

7. В каждой вычислительной ячейке 7 через микротакт с помощью умножителя 20 и сумматора 21 производятся вычисления в соответствии с выражением (6), Элементы I р поступают на вход умножителя 20 каждой вычислительной ячейки 7 с входа 7.1 через мультиплексор 19, а элементы 1("4 — с входа 7.5 через мультиплексор 17. На сумматоре 21 каждой вычислительной ячейки 7 формируется элемент а " ц, 1) который через регистр 22 передается в со5 ответствующую запоминающую ячейку 3, Временная диаграмма, поясняющая органиэацию потоков данных в матрице 6 вычислительных ячеек 7, приведена на фиг. 5 для случая = 4. На остальных итерациях процес10 сор работает аналогичным образом. Отличие заключается в том, что на каждой следующей итерации в работу включается число вычислительных ячеек на единицу меньше, чем на предыдущей итерации (пра15 вая вычислительная ячейка, участвующая в данной итерации в следующей участие не принимает).

Каждая запоминающая ячейка 3 представляет собой дуальный буфер 03У, кото20 рый позволяет на фоне разложения текущей матрицы загружать в матрицу 2 запоминающих ячеек 3 следующую матрицу через шину

1, Одновременно с загрузкой следующей матрицы из матрицы 2 запоминающих ячеек

25 3 выводятся элементы матрицы L, полученной в результате разложения предыдущей матрицы. Вывод производится через выход

4, Таким образом, введением в известное

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

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

Формула изобретения (,Устройство для операций над матрица40 ми, содержащее n — 1 вычислительных 6поков (и — размерность обрабатываемых матриц) и п блоков памяти, причем первые информационный вход и выход j-l.o блока памяти (= 2, n) соединены соответственно

45 с первыми выходом и информационным входом (j — 1)-го вычислительного блока, второй выход i-ro (i = 1, п 1) блока памяти подключен к второму информационному входу (i+1)го блока памяти, второй информационный

50 вход первого и второй выход и-го блоков памяти являются соответственно информационным входом и выходом устройства, второй и третий выходы к-ro блока памяти (к =

1, n — 2) соединены соответственно с вторым

55 и третьим информационными входами (К +

1)-го вычислительного блока, о т л и ч а ющ е е с я тем, что, с целью расширения функциональных возможностей за счет разложения матриц Холецкого, в него введен и-й вычислительный блок, первые информа10

1737462 у ° Ф

° Ф °

° ° ° ционный вход и выход которого подключены соответственно к первым выходу и информационному входу первого блока памяти, второй и третий выходы и-го вычисл ител ьн ого блока подключены соответственно к второму и третьему информационным входам первого вычислительного блока, четвертый информацион.ный вход к-ro вычислительного блока подключен к четвертому выходу (К + 1)-ro вычислительного блока, четвертый выход первого вычислительного блока — к второму информационному входу п-ro вычислительного блока.

2. Устройство по и. 1, о т л и ч а ю щ е.ес я тем, что i-й вычислительный блок содержит умножитель, сумматор, четыре регистра и четыре мультиплексора, причем первые информационные входы первого и второго мультиплексоров объединены и подключены к первому информационному входу вычислительного блока, а выходы первого и второго мультиплексоров — к первым входам умножителя и сумматора соответственно, второй информационный вход первого мультиплексора соединен с вторым информационным входом третьего мультиплексора и является четвертым информационным входом вычислительного блока, второй информационный вход второго мультиплексора — с входом нуля устройства, выход третьего мультиплексора подключен к информационному входу первого регистра, выход которого является четвертым выходом вычислительного блока, первый информационный вход третьего мультиплексора соединен с выходом умножителя и вторым входом сумматора, выход которого подключен к информационному входу второго регистра, выход которого является первым выходом вычислительного блока, второй вход умножителя соединен с выходом четвертого мультиплексора, первый и второй информационные входы которого соединены соответственно с информационными

5 входами третьего и четвертого регистров, выходы которых являются соответственно вторым и третьим выходами вычислительного блока, вторым и третьим информационными входами которого являются

10 информационные входы третьего и четвертого регистров соответственно.

3, Устройство по и. 1, о т л и ч а ю щ е ес я тем, что и-й вычислительный блок содержит узел вычисления квадратного корня, 15 узел вычисления обратной величины числа, три регистра, умножитель, сумматор, мультиплексор, узел изменения знака числа, причем первый информационный вход вычислительного блока соединен с первым

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

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

40 блока подключен к входу узла изменения знака и второму входу умножителя, 1737462

Фиг 2

1737462,9,ю-(gQc!

О

) !

Ол!!

t а з

gu

0н

-Р р . Сi- ) -g< Р- К

Составитель В. Грачев

Редактор О. Спесивых Техред М,Моргентал Корректор С,Черни

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

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

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

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