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

 

Изобретение относится к вычислительной технике, в частности к специализированным вычислительным устройствам , и может быть использовано для обработки информации в реальном. масштабе времени. Цель изобретения - повышение быстродействия. Поставленная цель достигается тем, что устройство содержит и (где п - порядок линейной алгебраической системы уравнений ) входов 1 коэффициентов и свободных членов систем 1 линейных алгебраических уравнений, п выходов 2 результата , k блоков 3 вычислений (где k - число итераций), первый и , второй входы 4 и 5 синхронизации, причем каждый блок 3 вычислений содержит п операционных узлов 6.1 з.пф-лы, 2 ил, 1 табл. i (Л

1> 4 С 06 Р !5/32

ВСЕСРФйлР} }}1 Я

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

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

}} 3 М!

Д ..Л1}}р Ф",!, ф

}}, } . СООЗ СОВЕТСНИХ .

М1 .»;:- = СОЦИАЛИСТИЧЕСКИХ

-".з. -Я РЕСПУБЛИК

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4152593/24-24 (22) 26.11. 86 (46) 07.05.88. Бюл. 1!} 17 (72) М.Б. Сергеев, А.В. Вавилов и В.Д. Байков (53) 681.3 (088.8) (56) Kung Н.Т. Why systolic arithmetic — IEEE Computer, Tan., 1982, р. 37-46, f ig. 12.

Berzinc М.,Buckley Т.F.,Dew P.М.

Systolic matrix itterative algorithms.

Int. Conf. Parallel Computing 83, 1984, р. 438-488, Гхд. 1,2. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ

ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ (57) Изобретение относится к вычислительной технике, в частности к спеÄÄSUÄÄ 1394218 А1 циализированным вычислительным устройствам, и может быть использовано для обработки информации в реальном масштабе времени. Цель изобретения— повышение быстродействия. Поставленная цель достигается тем, что устройство содержит и (где и —. порядок линейной алгебраической системы уравнений) входов 1 коэффициентов и свободных членов системы линейных алгебраических уравнений, и выходов 2 результата, k блоков 3 вычислений (где k — число итераций), первый и второй входы 4 и 5 синхронизации, причем каждый блок 3 вычислений содержит и операционных узлов 6.1 s.пф-лы, 2 ил, 1 табл.

l 394218

Х =Х -Н;(АХ вЂ” В) или х =x -н;е где E =АХ -В

40 вектор невязок на

i-й итерации; вектор i-х.приближений неизвестных системы;

45 линейный оператор вида

Н»

Н;=diag((, g(l,..., (j) . (3) 50 формируются таЗдесь (,l -(j=l,n) ким образом, чтобы приращения неизвестных íà i-й итерации были кратны степени основания системя счисления, в которой работает устройство, и следовательно обеспечивали отсутствие операций умножения в {1) и (2) Изобретение относится к вычислительной технике и может быть применено при построении специализированных и проблемно-ориентированных процессоров для решения систем линейных уравнений.

Цель изобретения — повышение быстродействия.

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

Устройство содержит и входов 1 коэффициентов и свободных членов, где n - порядок системы линейных 15 алгебраических уравнений, и выходов

2 результата, k блоков 3 вычислений, где k — число итераций, первый 4 и второй 5 входы синхронизации. Каждый блок 3 вычисления содержит и опера- 20 ционных узлов 6, причем каждый операционный узел 6 содержит (n+1) регистров 7, выходной регистр 8, регистр 9 невязки, сумматор 10, первый 11 и второй 12 мультиплексоры, (п+2)-й регистр 13, элемент И 14, три группы элементов И 15 — 17, управляющий вход 18, первый 19 и второй

20 выходы.

Алгоритм работы устройства для ре- 30 шения систем линейных уравнений АХ=В порядка и основывается на линейном одношаговом интерационном нестационарном методе, который представляется следующим образом: 35 (1!

Таким образом соответствует значению старшего значащего разряда

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

С частотой следования импульсов на входе 4 синхронизации на входы

1 подаются коэффициенты системы уравнений и свободные члены в последовательности, приведенной в таблице.

При этом последовательность расположения коэффициентов в регистрах 7 узлов 6 и передачах их между блоками

3 вычи спеки и сохр аня ет ся .

После каждого импульса на входе

5 синхронизации, на входах 1 начинается ввод коэффициентов следующей системы, а в узлах 6 i-ro (i=1 Ê) блока вычисления 3 — итерации, вычисляющие i-e приближения неизвестных по соотношению (2). Для этого в каждом узле 6 осуществляется синхронное продвижение коэффициенттов уравнений системы по конвейеру регистров 7 и подача через мультиплексор 1! с входа 18 цифр приращений соответствующих неизвестных. Через группы элементов И 15 и 16 коэффициенты с соответствующими знаками подаются на входы сумматора 10, а на другие его входы через элементы И 17 группы подаются частичные суммы из регистра 9 невязок. Результат суммирования записывается в регистр 9 невязок. Коэффициенты через мультиплексор 12 передаются по конвейеру в вы> ходной регистр 8 и далее в соответствующий узел 6 следующего (i+1)-го блока 3 вычисления.

При появлении импульса на входе 5 синхронизации итерации в блоках

3 вычисления завершаются. Вычисленные невязки в каждом узле 6 из регистра 9 невязок через мультиплексор 12 передаются в выходной регистр 8 со сдвигом влево на один разряд. Аналогично передаются приближения неизвестных, которые формируются следующим образом. Так как длительность импульса на входе 5 синхронизации равна трем тактам входа 4 синхронизации, то при поступлении в каждый узел 6 з

13942

i-го блока 3 вычисления новой невязки через элемент И 14 и мультиплексор 11 в регистре 13 формируется приращение неизвестного, которое в следующем такте.на входе 4 синхронизации записывается через элемент И 14 в свободный младший разряд (i-1)-ro приближения неизвестного, передаваемого из предыдущего блока 3 (для 10 первого блока неизвестные равны нулю) .

После Р импульсов на входе 4 синхронизации в i-м (i=1,K) блоке 3 вычислен вектор i-х приближений решения 15

P-й системы линейных уравнений.

Таким образом, задержка в вычисле-. нии вектора очередных приближений неизвестных системы уравнений, а также в появлении решений систем на вхо- 20 дах 2, составляет один такт входа

5 синхронизации.

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

25 ! . Устройство для решения систем ли-, нейных алгебраических уравнений, содержащее k блоков вычислений, где

k — число итераций, с первого по и-й (где и-порядок системы линейных алгеб-З0 раических уравнений), входы коэффициентов и свободных членов системы уравнений устройства подключены к

- информационным входам с первого по и-й первого блока вычислений, соответственно с первого по и-й выходы результатов устройства подключены к выходам с первого по п-й Ы-гo блока, вычислений, соответственно выходы с первого по и-й i-ro блока вычислений 40 (д =2,...,k-1) подключены к информационным входам с первого по и-й (i+1)-го блока вычислений соответственно, о т л и ч а ю щ е е с я тем, что, с целью увеличения быстродейст-. 45 вия устройства, первый и второй входы синхронизации устройства подключены к первым и вторым входам синхронизации блоков вычислений с первого по k-й соответственно, причем каждый 50 блок вычислений содержит и операцион ных узлов, в каждом блоке вычислений

j-й (j 1,...,n) информационный вход подключен к информационному входу

j-ro операционного узла, первый и . второй входы синхронизации подключены к первым и вторым входам синхронизации операционных узлов с первого по и-й соответственно, j-й выход подключен к первому выходу j-го операционного узла, второй выход 1-ro операционного узла (1=1, ° ..,n-1) подключен к управляющему входу (1+1)-ro операционного узла, второй выход (п-ro операционного узла подключен к управляющему входу первого операционного узла.

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

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

Ь-ro регистра (где b=2 п-1) подключен к информационному входу (Ь+1)-ro регистра, выход n-ro регистра подключен к информационному входу (и+1)-го регистра и первому информационному входу второго мультиплексора, выход которого подключен к информационному. входу выходного регистра, выход которого подключен к первому выходу операционного узла, выход первого мультиплексора подключен к информационному входу (n+2)-ro регистра, выход которого подключен к первым входам элементов И второй и третьей групп, а также к второму выходу операционного узла, первый и

1394218 второй выходы (и+1)-rо регистра подключены к вторым входам элементов И второй и третьей групп соответственно, выходы элементов И первой, второй и третьей групп подключены к информационным входам сумматора, выНомер входной шины

1 ° ° и

0

n+3

0 и+2

0 ь, Ь 2

° ° ° b n

n+ l а . +, а „, а2З

f7 а„„;+, 2 п-1+3 а, „;+7

° а П 0-7

jj z

a7n а

1 n-< а n n-i аjj- t а„„ а7>

Номер такт на входе 4

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

) 394218

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

Техред И. Дидык Корректор С.Черни

Редактор А. Ворович

Заказ 2221/45

Тираж 704

Подписное

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

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

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4