Устройство для решения систем линейных алгебраических уравнений с треугольной матрицей Советский патент 1993 года по МПК G06F15/347 

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

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

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

1 базовую операцию у (b-х) - , группу 5 из

3

(Н-1) операционных блоков 6, операционный блок 7, выполняющий базовую операцию у (b-х) - информационный выход 8,

3

информационный выход 9, информацион- н&1й выход 10 и вход 11 соответственно.

Операционный блок 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 ячейки соответственно.

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

В операционных блоках хранятся элементы матрицы lik по диагонали, причем в

СО

с

оо

О CJ

SQ

to

ячейке ЗЯ хранятся элементы главной диагонали матриц Li и La т.е. {In ,...,lnn } и {Iii2,...,bui2}. В общем случае в ячейке ЗЯ у 1,п. хранятся элементы likm, i j,n, k 1,(n-j+1), m 1,2, причем элементы матриц Li и L-2 в ячейках памяти каждой ЗЯ расположены следующим образом

1л(1); л(2); lj+i,2(1); lj+i A..J

Элементы матриц и Ц расположены в ячейках ЗЯ, j n+1,2, аналогично элементам матриц Li и L2 отличие заключается в том, что элементы диагоналей матриц загружаются, начиная с правого конца линейки т.к. в ячейку 3 ЗЯп+1 загружаются элементы главной диагонали, в ячейку 3 ЗЯП

элементы Р likw, i 2,rT; k ТГгН и т.д. Каждая ячейка 3 ЗЯ, j 1, п+1 представляет собой дуальный буфер, что позволяет загружать элементы матриц Li-L4 в ячейки 3 матрицы 2 на фоне решения СЛАУ для четырех матриц, загруженных ранее.

Рассмотрим организацию вычислительного процесса на примере решения СЛАУ 1)1. В устройстве для решения СЛАУ с треугольной матрицей элементы вектора решений формируются в соответствии с формулой:

Х| (Ь|-у|(и))-1 .у/° 0, (2)

lie

где уг - вычисляется по рекуррентному соотношению

У2(1)121(1)Х1, (у2™ 0)

10

15

25

30

35

который в конце микротакта ti записывается в регистр 14 блока 6. В микротакте t3 промежуточный параметр у2 из регистра 14 блока 6 ВЯ и выход 6.7 передается в блок 4, в котором по формуле (2) формируется координата Х2 вектора решений, а координата xi в этом микротакте записывается в регистр 12 и передается через выход 6.3 блока 6 на вход 6.6 блока 6, в котором формируется по формуле (3) промежуточный параметр уз

В дальнейшем элементы х вектора решений, распространяясь слева направо вдоль линейки блока 6 (по шине, образованной входом регистром 12 и выходом 6.2 блока , 2,п), участвуют в формировании промежуточных параметров у/Ч причем в 20 ячейке 6 ВЯ формируется параметр уг л в блоке 6 - у. и т.д. Параметр yik формируется по формуле (3), причем параметр уг1 поступает на вход 6.3 блока 6.i-k+1. В блоке с помощью мультиплексоров 10 и 11, умножителя 8 и сумматора 9 формируется параметр yrk л который через регистр 14, выход 6.7 блока 6 передается на вход 6.3. блока 6i-k-n.

Аналогичным образом в микротактах t2, t4,.j, t2m формируется решение СЛАУ L.2X D2. Решение СЛАУ з Ј3 и U5 Ъц производится аналогично СЛАУ Lix kfi и L2 D2, отличие заключается в следующем:

1. Потоки элементов векторов решений хг , хр4 и промежуточных параметров уг

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

.M y.fr-1Mlkxk.

(3)

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

Х1

bi/ln(1)

т.к.У1(0) 0.

В этом микротакте на один из входов блока 41 с информационного выхода 9 передаются координаты bi вектора свободных членов, а на другой вход блока 4i с выхода ячейки 3 поступает элемент матрицы hr . Вычисленная в миротакте to координата xi записывается в конвейерный регистр ячей и 4 и в микротакте ti передается на вход 6.6 блока 6: в этом же микротакте на вход 6.1 из ячейки ЗЯ поступает элемент гт матриц L. В микротакте ti с помощью мультиплексора 10, умножителя 8 и сумматора 9 блока 6 ВЯ

,(D

формируется промежуточный параметр у2 по формуле

,(

40

45

50

55

распространяются по шинам, образованным входом 6.5, регистром 13, выходом 6.9 и входом 6.,8, регистром,выходом 6.4 каждой ячейки 6 ВЯ, п.2 в направлении, противоположном направлению распространения соответствующих потоков для СЛАУ Lix и Цх .

Временная диаграмма, поясняющая функционирование устройства приведена на фиг. 3 и в таблице.

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

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

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

9U2&

-I1 , I I . I - I Ч/4 . j Vt ЈJ Ufc , + - -|-- - Т- -|- р Синхротактт

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

Вход 6.6

Выход 6.2

Вход 6.5