Устройство для операций над матрицами Советский патент 1992 года по МПК G06F15/347 

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

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

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

организации многомерного ввода информации; неэффективное использование вычислительного ресурса при изменении размерности задачи; невозможность выполнения разложения матриц.

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

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

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

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

СО

VI

N а ND

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

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

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

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

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

Для обеспечения вычисления разложения Холецкого симметричных матриц в известноеустройствовведенадополнительная вычислительная ячейка, которая позволяет на каждом шаге итерационного процесса вычислять один вектор-столбец нижней треугольной матрицы в разложении Холецкого. Кроме того, новые архитектурные решения вычисли тельных ячеек позволили организовать вычислительный процесс таким образом, чтобы на каждой итерации матрица А представлялась в факторизованной форме Aw F,+iB{H %Vi, где F,+i - матрица Фробе- ниуса, (i + 1)-й столбец которой совпадает с (i + 1)-м столбцом нижней треугольной мат- ы в разложении Холецкого, а матрица

-

-

В1 имеет вид

вГ в 1 11--- -0--, о 1 )

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

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

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

10 (ВЯ)5, матрицу 6 из(, причем первые вход и выход j-й 0 2, п) ВЯЗ соединены с первыми выходом и входом соответственно (j - 1)-й ВЯ7, а первые вход и выход первой ЗЯЗ соединены с первыми выходом и вхо15 дом n-й ВЯ5; второй выход j-й Q ТГгРОЗЯЗ подключен к второму выходу (j + 1)-й ЗЯЗ, второй выход n-й ЗЯЗ является информационным выходом 4 устройства, а второй вход первой ЗЯЗ является информационным вхо20 дом 1 устройства; второй и третий выходы j-й (j 1, п-2) ВЯ7 подключены соответственно к второму и третьему входу Q + 1)-й ВЯ7, а второй и третий выходы n-й ВЯ7 подключены к второму и третьему входам первой

25 ВЯ7; четвертый вход j-й (j 1, п-2) ВЯ7

соединен с четвертым выходом 0 + 1)-й ВЯ7, а четвертый выход первой ВЯ7 подключен к второму входу n-й ВЯ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 n-й ВЯ5.

Вычислительная ячейка 7 с номером j (j 1, п-1) содержит (фиг. 3) третий вход 7.1, первый вход 7.2, первый выход 7,3, третий выход 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 соединен с входом константы О. Первый вход мультиплексора 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.

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

Симметричная положительно определенная матрица может быть единственным способом разложена на множители

A(°) L.LT

(D

где L- нижняя треугольная матрица.

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

... .U

(2)

где Е + л j , E - единичная матрица; Г| - единичный вектор, вектор fi опре ляется из первого столбца матрицы которая формируется следующим образом. Если матрицу A™, i 0, п-1 представить в виде

Ar, ь ,3,

Л - -, IJJ

Ь; В;

где Bj - матрица порядка (n-i-1), то матрица А порядка (n-i-1) формируется в соответствии с выражением

a-ir

а

.(4)

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

fi(j)

j

aj aJ:V/2

(5)

0

5

0

5

0

5

0

где - j-й элемент первого столбца матрицы А(И).

Таким образом, столбцы матрицы L совпадают с векторами ff, т.е. Т ff где и - i-й столбец матрицы L Формирование матрицы L производится за п итераций. На каждой итерации формируется один вектор-столбец матрицы L, причем на i-й итерации (I 1, п) формируется i-й вектоо- столбец матрицы L. Так как i-й вектор-столбец матрицы L содержит (n-i + 1) отличных от нуля элементов, то в формировании элементов i-ro вектор-столбца матрицы L участвуют (n-i + 1) вычислительная ячейка ВЯ. причем i-й элемент вектор-столбца формирует ячейка Вир, а элемент с номером i + j (j 1, n-i) формирует j-я ячейка ВЯ. Организация потока данных на входе матрицы ячеек ВЯ показана на фиг. 5. Рассмотрим организацию вычислительного процесса на одной из итераций, например первой, в результате которой формируется первый вектор-столбец матрицы L и матрица . В устройстве реализуется конвейерный принцип обработки информации. Формирование первого, вектор-столбца начинается с ввода в микротакте to в ячейку ВЯо элемента а;г матрицы В микротакте to в ячейке ВЯП формируются с помощью блока 9 вычисления кваДратного корня и блока 11 вычисления обратной величины два параметра. Первый параметр. равный ау , является вычисленным значением первой координаты вектор- столбца 1.1 и через мультиплексор 10 и ре(о)

т 1/2

гистр 8 передается в ячейку ЗЯь 5 Второй параметр, равный а

участвует в формировании остальных кооо- динат вектор-столбца 1.1 в соответствии с. выражением (5). Этот параметр с помощью регистра 13 ячейки J5 ВЯП и регистров 23 0 ячеек 7 ВЯ (j 1, п-1) распространяется по матрице 6 ячеек 7 ВЯЦПараметр а;, в микротакте т (к 1, п 1) поступает на вход 7.7 ячейки 7 ВЯ и далее через мультиплексор 19 на вход умножителя 20 ячейки 7 ВЯ, 5 на второй вход умножителя 20 в этот момент

а(°)/ иотп1Л111.1 д ° преподается элемент а

г 1.

mi матрицы изведение - 2 через сумматор 21

и регистр 22 в следующем микротакте будет передано в ячейку 3 ЗЯ|. Мультиплексор 18 в этом микротакте (ti) на второй вход сумматора 21 подключает код О. Это же произведение через мультиплексор 26 поступает на вход регистра 25, Таким образом, в ячейке 7 ВЯ в микротакте ti информационные потоки коммутируются следующим обра- зом:

Выход мультиплексора 19 вход 7.7 Выход мультиплексора О Выход мультиплексора 26 -выход умножителя 19 Выход мультиплексора 17 « вход 7.2 В остальных микротактах на выходы мультиплексоров ячейки ВЯ коммутируются вторые входы мультиплексоров. В ячейке 5 ВЯП на выход мультиплексора 10 в микро- такте to подключается блок 9 вычисления квадратного корня. Управление мультиплексора ячеек ВЯ| (I 1, п) производится с помощью управляющих битов, которые сопровождают элементы матриц A(i).

Таким образом на первых п микротактах (IK, к 0, n-Ц) формируются элементы вектор-столбца 1.1. Элементы матрицы А 1 формируются начиная с микротакта ta по столбцам, причем формируются только эле- менты нижнего треугольника и главной диагонали, так как матрица А симметричная. Элементы m-ro вектор-столбца матрицы А начинают формироваться с микротакта t2(m-i), причем в j-й (j 1, ) ячейке 7 формируется (J + гп)-й элемент m-ro вектор- столбца матрицы . Из выражения (5) имеем

А, b{o)kj-l(1)kil(o)ji, ,п-1,(6), 35

где 1к1 {к 1, п) определяется из (5);

tr° kj - элементы матрицы в клеточном представлении (3).

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

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

Каждая запоминающая ячейка 3 представляет собой дуальный буфер ОЗУ, который позволяет на фоне разложения текущей матрицы загружать в матрицу 2 запоминающих ячеек 3 следующую матрицу через шину 1. Одновременно с загрузкой следующей матрицы из матрицы 2 запоминающих ячеек 3 выводятся элементы матрицы L, полученной в результате разложения предыдущей матрицы. Вывод производится через выход 4.

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

Формула изобретения {.Устройство для операций над матрицами, содержащее п-1 вычислительных блоков (п - размерность обрабатываемых матриц) и п блоков памяти, причем первые информационный вход и выход j-ro блока памяти (j 2, п) соединены соответственно с первыми выходом и информационным входом (j - 1)-го вычислительного блока, второй выход i-ro (i 1, n-1) блока памяти подключен к второму информационному входу (1+1)- го блока памяти, второй информационный вход первого и второй выход n-го блоков памяти являются соответственно информационным входом и выходом устройства, второй j/i третий выходы к-ro блока памяти (к 1, п-2) соединены соответственно с вторым и третьим информационными входами (К + 1)-го вычислительного блока, отличающееся тем, что, с целью расширения функциональных возможностей за счет разложения матриц Холецкого, в него введен n-й вычислительный блок, первые информационный вход и выход которого подключены соответственно к первым выходу и информационному входу первого блока памяти, второй и третий выходы n-го вычислительного блока подключены соответственно к второму и третьему информационным входам первого вычислительного блока, четвертый информационный вход к-го вычислительного блока подключен к четвертому выходу (К + 1)-го вычислительного блока, четвертый выход первого вычислительного блока - к второму информационному входу n-го вычислительного блока.

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

Г

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

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

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

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

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

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

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

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

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

«

ЈД

Фиг 2.

.7

/

Г8

.Э

is -°

W

15

Ол

Јр«-.

dbf-i