УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ Советский патент 1995 года по МПК G06F17/13 G06F17/16 

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

Цель изобретения повышение быстродействия и расширение функциональных возможностей устройства за счет решения систем вида А₁Х=А₂, где А₁=a_ij} А₂= а_i,n+k} Х=Х{_ik} i,j=i,j , k k=1,m (n порядок системы, m число столбцов в правой части).

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

Устройство (фиг. 1) содержит информационный вход 1, первый 2 и второй 3 управляющие входы, синхровход 4, вычислительные модули 5_i (i=(i )) и выход 6.

Вычислительный модуль 5 (фиг.2) содержит информационный вход 7, первый 8 и второй 9 управляющие входы, синхровход 10, первый 11, второй 12 и третий 13 регистры, узел задержки на n тактов 14, регистры 15_i(i ) узла задержки, узел вычисления 16 обратной величины числа, умножитель 17, вычитатель 18, первый 19 и второй 20 триггеры, первую 21 и вторую 22 группы триггеров, триггеры 23_i(i ) первой группы, триггеры 24_i(i=1,n+2) второй группы, первую 25, вторую 26, третью 27, четвертую 28, пятую 29, шестую 30, седьмую 31, восьмую 32 и девятую 33 группы элементов И, первую 34, вторую 35, третью 36 и четвертую 37 группы элементов ИЛИ, первый 38, второй 39, третий 40, четвертый 41, и пятый 42 элементы И, первый 43, второй 44 элементы НЕ, информационный выход 45, первый 46 и второй 47 управляющие выходы.

В основу работы устройства положен метод Гаусса-Жордана для решения СЛАУ, который представляется следующими рекуррентными соотношениями:
a(0ij

Логика работы вычислительного модуля 5 приведена в табл.1.

Вычислительный модуль работает в четырех режимах. В первом режиме на входы 8 и 9 подаются единичные сигналы, которые устанавливают триггеры 19 и 20 в единичное состояние. Кроме того, сигналы подаются на входы элемента И 37, на выходе которого формируется единичный сигнал, который открывает группу элементов И 25. При этом элемент а_i, подаваемый на вход 7, через группу элементов И 25 и группу элементов ИЛИ 34 подается на вход регистра 12. По заднему фронту тактового импульса элемент а _i записывается в регистр 12, содержимое регистра 12 (элемент а_i-1) записывается в регистр 15₁, а содержимое регистра 15_i(i= ) -записывается в регистр 15_i+1. Во втором режиме работы на входы 8 и 9 подаются соответственно единичный и нулевой сигналы, устанавливающие триггеры 19 и 20 соответственно в единичное и нулевое состояние. На выходе элементов И 41, НЕ 43 и НЕ 44 формируются единичные сигналы, которые открывают группы элементов И 26, И 27, И 31, И 32 и элемент И 42. При этом элемент b, подаваемый на вход 7 по заднему фронту тактового импульса, записывается в регистр 11, в регистрах 15_i происходит циклическая перезапись элементов аi, на выходе умножителя 17 формируется значение c b · которое подается на вход регистра 13 и записывается в него на следующем такте. В третьем режиме работы на входы 8 и 9 подаются нулевые сигналы, которые устанавливают триггеры 19 и 20 в нулевое состояние. На выходе элементов И 38, НЕ 43 и НЕ 44 формируются единичные сигналы, которые открывают группы сигналов И 26, И 28, И 29, И 31 и И 33. При этом в регистрах 15_i циклически перезаписывается информация, в регистр 11 записывается элемент d, подаваемый на вход 7, в регистре 31 хранится элемент C, на выходе умножителя 17 формируется значение е=C<Р₂12>, на выходе вычитателя 18 значение f=d-1, которое подается на выход 45. В четвертом режиме на входы 8 и 9 подаются соответственно нулевой и единичный сигналы, которые устанавливают триггеры 19 и 20 соответственно в нулевое и единичное состояния. На выходе элементов И 40 и НЕ 43 формируются единичные сигналы, которые открывают группы элементов И 30 и И 31. При этом в регистрах 15_i осуществляется циклическая перезапись информации и содержимое регистра 13 через группу элементов И 30 и группу элементов ИЛИ 35 подается на выход 45.

Управляющие сигналы τ₁ и τ₂ подаваемые соответственно на входы 8 и 9, задерживаются соответственно триггером 19, группой триггеров 23_i и триггером 20, группой триггеров 24_i на (n+3) тактов и выдаются соответственно на выходы 46 и 47.

Рассмотрим работу устройства для случая n=3 и m=2. На вход 1 подаются элементы а_ij в моменты времени
ta_ij=i+(m+1)j-n-2
(для n=3 и m=2ta_ij=i+4_j-5).

Значения х_ij снимаются с выхода 6 в моменты времени
tх_ij=i+(n+1)j+n²+2n-2
(для n=3 и m=2 tх_ij=i+4_j+13)
Управляющие сигналы ( τ₁τ₂ ) подаются на входы 2 и 3 в следующие моменты времени (1,1)^о(1,1)1,(1,1)ⁿ,(1,0)ⁿ⁺¹,
(0,0)ⁿ⁺²,(0,0)²ⁿ, (0,1)²ⁿ⁺¹.

(1,0)^(n+1)(n+m-1), (0,0)(^{n+1)(n+m-1)+1}.

(0,0)^{(n+1))n+m-1)+n-1}, (0,1)^{(n+1)(n+m-1)+n}
Организация входного и выходного потоков данных, управляющих сигналов, содержимое триггеров, регистров, формируемые значения на выходах умножителя, вычитателя и вычислительных модулей для n=3 и m=2 приведены в табл.2. Элементы а_ij, подаваемые с единичными управляющими сигналами τ₁ и τ₂ записываются в соответствующие регистры 15_i вычислительных модулей (табл.2). При подаче элементов а_ij с управляющими сигналами (1,0), (0,0) и (0,1) в вычислительных модулях осуществляется вычислительный процесс в соответствии с приведенными выше рекуррентными соотношениями. На выходе 6 устройства выдаются элементы а₄₄⁽³⁾= Х₁₁, а₅₄⁽³⁾=Х₂₁, а₆₄⁽³⁾=Х₃₁, а₄₅⁽³⁾=Х₁₂, а₅₅⁽³⁾=Х₂₂, а₆₅⁽³⁾= Х₃₂ соответственно на семнадцатом, восемнадцатом, девятнадцатом, двадцать первом, двадцать втором и двадцать третьем тактах.

Изобретение относится к области вычислительной техники и может быть использовано в высокопроизводительных специализированных вычислительных машинах для решения систем линейных алгебраических уравнений. Цель изобретения - повышение быстродействия и расширение функциональных возможностей устройства за счет решения систем линейных уравнений вида A₁X=A₂, где A₁={a_n}, A₂={a_1n+k}, X={X_k}, i, , где n - порядок системы, m - число столбцов в правой части. Устройство содержит линейку из n вычислительных модулей, информационный вход, два управляющих входа, синхровход и выход устройства. В основу работы устройства положен метод Гаусса-Жордана решения систем линейных алгебраических уравнений. 2 ил., 2 табл.

УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ, содержащее n вычислительных модулей (n порядок системы), причем первый управляющий вход устройства подключен к первому управляющему входу первого вычислительного модуля, первый управляющий вход p-го вычислительного модуля (p=2, n подключен к первому управляющему выходу (p-1)-го вычислительного модуля, синхровход устройства подключен к синхровходам всех вычислительных модулей, отличающееся тем, что, с целью повышения быстродействия и расширения функциональных возможностей за счет решения систем вида
A₁X=A₂,
где A₁={a_ij};
A₂={a_i,n+k};
X={X_ik};
(ij) 1,n;
k 1,m,m число столбцов в правой части системы),
информационный и второй управляющий входы устройства подключены соответственно к информационному и второму управляющему входу первого вычислительного модуля, информационный и второй управляющий входы p-го вычислительного модуля подключены соответственно к информационному и второму управляющему выходам (p-1)-го вычислительного модуля, информационный выход n-го вычислительного модуля является выходом устройства, причем каждый вычислительный модуль выполнен с возможностью реализации следующих функций:
U^j+n+3=α^j;
V^j+n+3=β^j;

где b^j+1 a^j / a^j-z при (α^j, β^j)=(1,0), z h-1
α^j и β^j значения соответственно на первом и втором настроечных входах вычислительного модуля на j-м такте,
U¹ и V¹ значения соответственно на первом и втором настроечных выходах вычислительного модуля на j-м такте,
a¹ и W¹ значения соответственно на информационных входе и выходе вычислительного модуля и j-м такте.