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

 

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

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

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

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

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР)

ОПИСАНИЕ ИЗОбРЕТЕНИЯ/;;"l,,:-:::-:-;:," ;....

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4858103/24 (22) 09.08.90 (46) 23.03.93. Бюл, М 11 (71) Центральный научно-исследовательский институт "Морфизприбор" (72) В.А,Грачев (56) Авторское свидетельство СССР

М 1324036, кл. G 06 F 15/347, 1989

Патент США Nã 4493048, кл. G 06 F 7/38, опублик, 1989. (о4) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ,00

О ,(л)

О

ЬЭ

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

Целью предложения является повышение быстродействия, На фиг. 1 представлена функциональная схема предлагаемого устройства; на фиг. 2 — функциональная схема j-й вычислительной ячейки (j = 2, и); на фиг, 3 — временная диаграмма работы вычислительных ячеек; на фиг. 4 — функциональная схема э поминающих ячеек.

Устройство для решения СЛАУ с треугОльной матрицей содержит информационн и вход 1, матрицу 2 запоминающих ячеек

3(ЗЯД, операционный блок 4, выполняющую

1 базовую операцию у = (о-x) —, группу 5 из а (Н вЂ” 1) операционных блоков 6, операционный блок 7, выполняющий базовую операцию у = (Ь вЂ” х) — информационный выход 8, 1 а информационный выход 9, информационнь и выход 10 и вход 11 соответственно.

„„. Ы„, 1803921 А1

УРАВНЕНИЙ С ТРЕУГОЛБНОЙ МАТРИЦЕЙ (57) Изобретение относится к вычислительной технике и может быть использовано в специализированных системах цифровой обработки информации, Целью изобретения является повышение быстродействия.

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

Операционный блок 6 с номером j = 2.п содержит (фиг,2) первый вход 6.1, первый выход 6,2, второй вход 6.3, третий выход 6.4, четвертый вход 6.5, третий вход 6.6, второй выход 6,7, пятый вход 6.8, четвертый выход

6,9, умножитель 8, сумматор 9, мультиплексоры 10 и 11, регистры 12 — 15, причем входы умножителя 8 соединены с входом 6.1 ячейки и выходом мультиплексора 10, один вход которого объединен с входом регистра 12 и является входом 7,6 ячейки, другой вход первого мультиплексора 10 объединен с входом регистра 13 и является входом ячейки, выход умножителя 8 соединен с первым входом сумматора 9, выход которого подключен к входам регистров 14 и 15, а второй вход к выходу мультиплексора 11, входы которого подключены к входам 6.3 и 6.8 ячейки. Выходы регистров 12 — 15 подключены к выходам 6.2, 6.9. 6.7 и 6.4 ячейки соответственно.

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

B операционных блоках хранятся злементы матрицы I a по диагонали, причем в

1803921 ячейке ЗЯ хранятся элементы главной диаГОНаЛИ МатрИц L1 И (2 т,Е. {I11,...,lnn } И

{111 „...Inn ). В ОбщЕМ СЛуЧаЕ В яЧЕйКЕ г

ЗЯ у = 1,п. хранятся элементы Ilk, i = J,п, k = Тчп- чЭэ m = 1,2, причем эпемеиты метриц L1 и L2 в ячейках памяти каждой ЗЯ) расположены следующим образом

Р (): ()1(): )+1,2(); ))+1,2();.") (1)

Элементы матриц (з и (4 расположены в ячейках ЗЯ), J = и+1,2, аналогично элементам матриц L1 и (2 отличие заключается в том, что элементы диагоналей матриц загружаются, начиная с правого конца линейки

ЗЯ1; т.к, в ячейку 3 ЗЯБ+1 загружаются элементы главной диагонали, в ячейку 3 ЗЯ элементы !и< ), а ), i = 2,п; k = 1, п-1 и т.д.

Каждая ячейка 3 ЗЯ), j = 1, и+1 представляет собой дуальный буфер, что позволяет загружать элементы матриц L1 — L4 в ячейки 3 матрицы 2 на фоне решения СЛАУ для четырех матриц, загруженных ранее.

Рассмотрим организацию вычислительного процесса на примере решения

СЛАУ L, х = b1. В устройстве для решения

СЛАУ с треугольной матрицей элементы вектора решений формируются в соответствии с формулой;

x; = (bl — yl ) —, i = 1 и yI = О, (2) (ь1) 1,,(о) IIC где yl — вычисляется по рекуррентному соотношению у1() = у1() + Ilkxk, k = 1,(i-1). (3)

Процесс вычисления элементов вектора решений начинается с формирования элемента х1 в микротакте to, по формуле

- x1 = b1/i11(1) т.к. у1() = 0, B этом микротакте на один из входов блока 41 с информационного выхода 9 передаются координаты b1 вектора свободных членов, а на другой вход блока 41 с выхода ячейки 3 поступает элемент матрицы!11 ).

Вычисленная в миротакте t, координата х1 записывается в конвейерный регистр ячей и

4 и в микротакте t1 передается на вход б,б блока 6; в этом же микротакте на вход 6.1 из ячейки ЗЯ поступает элемент 121 матриц L.

В микротакте t1 с помощью мультиплексора

10, умножителя 8 и сумматора 9 блока 6 ВЯ формируется промежуточный параметр у2() (1) по формуле

„(1) = I21(1)х1 ((о) = 0) который в конце микротакта о1 записывается в регистр 14 блока 6. В микротакте t3 промежуточный параметр у2(из регистра (1)

14 блока 6 ВЯ и выход 6.7 передается в блок

4, в котором по формуле (2) формируется координата х2 вектора решений, а координата х1 в этом микротакте записывается в регистр 12 и передается через выход 6.3 блока 6 на вход 6.6 блока б, в котором формируется 1о формуле (3) промежуточный параметр уз )

1).

В дальнейшем элементы х вектора решений, распространяясь слева направо вдоль линейки блока 6 (по шине, образованной входом 6.6 регистром 12 и выходом 6.2 блока J, j = 2,п), участвуют в фоомировании промежуточных параметров у), причем в

20 ячейке 6 ВЯ формируется параметр у(), в блоке 6 — у; ) и т.д. Параметр у; форми y(k- ) k ется по формуле (3), причем параметр уг" поступает на вход 6,3 блока б. k+1. В блоке б - +1 с помощью мультиплексоров 10 и 11, 25 умножителя 8 и сумматора 9 формируется параметр у, который через регистр 14, .(к-1) выход 6,7 блока 6 передается на вход 6.3. блака 6Ь +1.

Аналогичным образом в микротактах

t2, t4...„ t2m формируется решение СЛАУ

L2x = Ь2. Решение СЛАУ (.зХ= Ьз и (4х = 54 производится аналогично СЛАУ L1x = b1 и

L2x = Ь2, отличие заключается в следующем:

1. Потоки элементов векторов решений

35 xl(3), х() и промежуточных параметров yl(k) распространяются по шинам, образованным входом 6.5, регистром 13, выходом 6,9 и входом 6.,8, регистром 5, выходом 6.4 каждой ячейки 6 ВЯ), j = n.2 в направлении, "0 противоположном направлению распространения соответствующих потоков для

СЛАУ L1x = Ь1 и L2x = Ь2.

2. Ввод элементов матрицы (з производится с задержкой на и микротактов по отношению к началу ввода элементов матрицы L1.

3. Ввод элементов матриц (з и L4 производится, начиная с ячейки 7 ВЯп+1, т.е. в эту ячейку передаются элементы главной диагоНаЛ1, В ЯЧЕЙКУ 6 BRn ЭЛЕМЕНТЫ ДИаГОНаЛИ (Ik+1 "), k), k = 1, и-1 и т д, Временная диаграмма, поясняющая функционирование устройства приведена на фиг. 3 и в таблице.

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

Устройство для решения систем линейных алгебраических уравнений с треугольной матрицей, содержащее Н+1 узлов

1803921 буферной памяти, где Н х Н вЂ” размерность треугольной матрицы, группу из (Н вЂ” 1)-ro операционного блока и первого операционного блока, причем первый и второй входы коэффициентов треугольной матрицы устройства подключены соответственно к информационному входу первого узла буферной памяти и к первому информационному входу первого операционного блока, первый и второй выходы которого подключены соответственно к первому информационному и первому управляющему входам первого операционного блока группы, первый и второй выходы а-ro операционного блока группы, где а = 1,..., Н-2, подключены соответственно к первому информационному и первому управляющему входам (а+1)-го операционного блока группы, первый и второй выходы (Н-1)-го операционного блока группы подключены соответственно к выходам результата первой группы устройства, первый выход первого узла буферной памяти подключен к второму информационному входу первого операционного блока, третий информационный вход которого подключен к третьему выходу первого операционного блока группы, второй информационный вход а-го операционного блока группы подключен к третьему выходу (а+1)-го операционного блока группы, первые выходы узлов буферной памяти с второго по Н-й подключены соответственно к третьему информационному входу операционных блоков с первого по (Н-1)-й группы, с первого по (Н+1)-й управляющий входы устройства подключены соответственно к входам чтениязаписи узлов буферной памяти с первого по

{Н+1) й, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, оно содержит второй операционный блок, причем третий и четвертый входы коэффициентов треугольной матрицы устройства подключены соответственно к первому информационному входу второго операционного блока второму информационному входу (Н-1)-го рперационного блока группы, четвертый вход коэффициентов треугольной матрицы и (Н+2)-й управляющий вход устройства подключены соответственно к четвертому

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

55 ному входу второго операционного блока, четвертый выход (Н-1)-го операционного блока группы подключен к третьему информационному входу второго операционного блока, выход которого подключен к пятому информационному входу (Н-1)-го операционного блока группы, пятый информационный вход а-го операционного блока группы подключен к шестому выходу (а+1)-го операционного блока группы, второй выход К-го узла буферной памяти (где К = 1,.„,Н) подключен к информационному входу (К+1)-ro узла буферной памяти, вход синхронизации устройства подключен к входам синхронизации операционных блоков группы, первого и второго операционных блоков, причем каждый операционный блок группы содержит умножитель, сумматор, два мультиплексора и четыре регистра в каждом операционном блоке группы первый информационный вход операционного блока группы подключен к информационному входу первого регистра и к первому информационному входу первого мультиплексора, первый управляющий вход операционного блока группы подключен к управляющему входу первого мультиплексора, второй и третий информационные входы операционного блока группы подключены соответственно к первым информационным входал. второго мультиплексора и умножителя, четвертый информационный и второй управляющий входы операционного блока группы подключены соответственно к второму информационному и управляющему входам второго мультиплексора, выход которого подключен к первому информационному входу сумматора, выход которого подключен к информационным входам второго и третьего регистров, пятый информационный входоперационного блока группы подключен к информационному входу четвертого регистра и второму информационному входу первого мультиплексора, выход которого подключен к второму информационному входу умножителя, выход которого подключен к второму информационному входу сумматора, первый и второй выходы первого регистра подключены соответственно к первому и второму выходам операционного блока группы, выход второго регистра подключен к третьему выходу операционного блока группы, первый и второй выходы третьего регистра подключены соответственно к четвертому и пятому выходам операционного блока группы, выход четвертого регистра подключен к шестому выходу операционного блока группы, вход синхронизации которого подключен к входам записи-считывания регистров с первого по четвертый, 1803921

1803921

Синхротактч

Вход 6.6

Выход 6.2

1 . I Ф и

Вход 6.6

Г

° ° & ЯМ Выход 6.9

Выход 6.7 и 6.4

k B57?

Составитель Г. Смирнова

Техред M.Ìîðãåíòàë Корректор Л.Филь

Редактор Т, Иванова

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

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

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

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

1 (Яй;Я @ Я МАМ В

Бит управления мультиплексорами