Устройство для решения систем линейныых алгебраических уравнений Советский патент 1988 года по МПК G06F17/17 

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

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

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

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

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

Алгоритм работы устройства для ре- шенкч систем линейных уравнений порядка in основывается на линейном одношаговом интерационном нестационарном методе, который представляется следующим образом:

(1)

-- -н.-САХ - -в)

или

г. 1 ::; - 1

,(2)

где - вектор невязок на

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

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

( J c(i)

(ib

Hpdiag(7. ri - - Tn)- (3)

Здесь -(,n) формируются таким образом, чтобы приращения неизвестных на i-й итерации были кратны степени основания системы счисления, в которой работает устройство, и следовательно обеспечивали отсутствие операций умножения в (1) и (2)

0

5

0 05

0

5

0

5

.() 2 ,, I ,

,Ь --тгг,-., u,i- ,

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

,(,; j

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

С частотой следования импульсов на входе 4 синхронизации на входы 1 подаются коэффициенты систеьы уравнений и свободные члены в последовательности, приведенной в таблице. При этом последовательность расположения коэффициентов в регистрах 7 узлов 6 и передачах их между блоками 3 вычислений сохраняется.

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

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

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

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

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

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

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

,вычислений, соответственно выходы с первого по п-й i-ro блока вычислений (,...,k-l) подключены к информа- 1ЩОННЫМ входам с первого по n-g (i+l)-ro блока вычислений соответственно, отличающееся тем, что, с целью увеличения быстродейстВИЯ устройства, первый и второй входы синхронизации устройства подключены к первым и вторым входам синхронизации блоков вычислений с первого по k-й соответственно, причем каждай блок вычислений содержит п операционных узлов, в каждом блоке вычислений j-й (,...,n) информационный вход подключен к информационному входу j-ro операционного узла, первый и

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

g 0

5

0

5

0 5

0 5 0 5

18

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

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

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

513942186

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

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

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

i rt-U2

2 n- i Э jn- i+j+1

1 n-1

4n

11

ajn

ajj

n n-i-n

n n-5

a,

n n-1

a

fi n

(Puz.2