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

 

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

Изобретение относится к области вычислительной техники и может быть использовано в высокопроизводительных специализированных вычислительных машинах для решения систем линейных алгебраических уравнений. Цель изобретения повышение быстродействия и расширение функциональных возможностей устройства за счет решения систем вида А1Х=А2, где А1=aij} А2= аi,n+k} Х=Х{ik} i,j=i,j , k k=1,m (n порядок системы, m число столбцов в правой части). На фиг.1 представлена структурная схема устройства; на фиг.2 функциональная схема вычислительного модуля. Устройство (фиг. 1) содержит информационный вход 1, первый 2 и второй 3 управляющие входы, синхровход 4, вычислительные модули 5i (i=(i )) и выход 6. Вычислительный модуль 5 (фиг.2) содержит информационный вход 7, первый 8 и второй 9 управляющие входы, синхровход 10, первый 11, второй 12 и третий 13 регистры, узел задержки на n тактов 14, регистры 15i(i ) узла задержки, узел вычисления 16 обратной величины числа, умножитель 17, вычитатель 18, первый 19 и второй 20 триггеры, первую 21 и вторую 22 группы триггеров, триггеры 23i(i ) первой группы, триггеры 24i(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)= aij,i , j ; k ; аkk(k)kk(k-1); a(kkj)= aa(kkk), j ; aik(k)=aik(k-1), i= ; аij(k)ij(k-1)ik(k)аkj(k), i=k+1,n+k-1, j ; a(k)n+k a(kkj), j , xij= a(n)n+i,n+j, i= , j= При описании работы устройства в обозначении а(k) индекс (k) указывает номер рекуррентного шага, а в обозначении а(t) индекс t номер такта работы устройства. Логика работы вычислительного модуля 5 приведена в табл.1. Вычислительный модуль работает в четырех режимах. В первом режиме на входы 8 и 9 подаются единичные сигналы, которые устанавливают триггеры 19 и 20 в единичное состояние. Кроме того, сигналы подаются на входы элемента И 37, на выходе которого формируется единичный сигнал, который открывает группу элементов И 25. При этом элемент аi, подаваемый на вход 7, через группу элементов И 25 и группу элементов ИЛИ 34 подается на вход регистра 12. По заднему фронту тактового импульса элемент а i записывается в регистр 12, содержимое регистра 12 (элемент аi-1) записывается в регистр 151, а содержимое регистра 15i(i= ) -записывается в регистр 15i+1. Во втором режиме работы на входы 8 и 9 подаются соответственно единичный и нулевой сигналы, устанавливающие триггеры 19 и 20 соответственно в единичное и нулевое состояние. На выходе элементов И 41, НЕ 43 и НЕ 44 формируются единичные сигналы, которые открывают группы элементов И 26, И 27, И 31, И 32 и элемент И 42. При этом элемент b, подаваемый на вход 7 по заднему фронту тактового импульса, записывается в регистр 11, в регистрах 15i происходит циклическая перезапись элементов аi, на выходе умножителя 17 формируется значение c b которое подается на вход регистра 13 и записывается в него на следующем такте. В третьем режиме работы на входы 8 и 9 подаются нулевые сигналы, которые устанавливают триггеры 19 и 20 в нулевое состояние. На выходе элементов И 38, НЕ 43 и НЕ 44 формируются единичные сигналы, которые открывают группы сигналов И 26, И 28, И 29, И 31 и И 33. При этом в регистрах 15i циклически перезаписывается информация, в регистр 11 записывается элемент d, подаваемый на вход 7, в регистре 31 хранится элемент C, на выходе умножителя 17 формируется значение е=C<Р12>, на выходе вычитателя 18 значение f=d-1, которое подается на выход 45. В четвертом режиме на входы 8 и 9 подаются соответственно нулевой и единичный сигналы, которые устанавливают триггеры 19 и 20 соответственно в нулевое и единичное состояния. На выходе элементов И 40 и НЕ 43 формируются единичные сигналы, которые открывают группы элементов И 30 и И 31. При этом в регистрах 15i осуществляется циклическая перезапись информации и содержимое регистра 13 через группу элементов И 30 и группу элементов ИЛИ 35 подается на выход 45. Управляющие сигналы 1 и 2 подаваемые соответственно на входы 8 и 9, задерживаются соответственно триггером 19, группой триггеров 23i и триггером 20, группой триггеров 24i на (n+3) тактов и выдаются соответственно на выходы 46 и 47. Рассмотрим работу устройства для случая n=3 и m=2. На вход 1 подаются элементы аij в моменты времени
taij=i+(m+1)j-n-2
(для n=3 и m=2taij=i+4j-5). Значения хij снимаются с выхода 6 в моменты времени
ij=i+(n+1)j+n2+2n-2
(для n=3 и m=2 tхij=i+4j+13)
Управляющие сигналы ( 12 ) подаются на входы 2 и 3 в следующие моменты времени (1,1)о(1,1)1,(1,1)n,(1,0)n+1,
(0,0)n+2,(0,0)2n, (0,1)2n+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, подаваемые с единичными управляющими сигналами 1 и 2 записываются в соответствующие регистры 15i вычислительных модулей (табл.2). При подаче элементов аij с управляющими сигналами (1,0), (0,0) и (0,1) в вычислительных модулях осуществляется вычислительный процесс в соответствии с приведенными выше рекуррентными соотношениями. На выходе 6 устройства выдаются элементы а44(3)= Х11, а54(3)21, а64(3)31, а45(3)12, а55(3)22, а65(3)= Х32 соответственно на семнадцатом, восемнадцатом, девятнадцатом, двадцать первом, двадцать втором и двадцать третьем тактах.


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

УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ, содержащее n вычислительных модулей (n порядок системы), причем первый управляющий вход устройства подключен к первому управляющему входу первого вычислительного модуля, первый управляющий вход p-го вычислительного модуля (p=2, n подключен к первому управляющему выходу (p-1)-го вычислительного модуля, синхровход устройства подключен к синхровходам всех вычислительных модулей, отличающееся тем, что, с целью повышения быстродействия и расширения функциональных возможностей за счет решения систем вида
A1X=A2,
где A1={aij};
A2={ai,n+k};
X={Xik};
(ij) 1,n;
k 1,m,m число столбцов в правой части системы),
информационный и второй управляющий входы устройства подключены соответственно к информационному и второму управляющему входу первого вычислительного модуля, информационный и второй управляющий входы p-го вычислительного модуля подключены соответственно к информационному и второму управляющему выходам (p-1)-го вычислительного модуля, информационный выход n-го вычислительного модуля является выходом устройства, причем каждый вычислительный модуль выполнен с возможностью реализации следующих функций:
Uj+n+3=j;
Vj+n+3=j;

где bj+1 aj / aj-z при (j, j)=(1,0), z h-1
j и j значения соответственно на первом и втором настроечных входах вычислительного модуля на j-м такте,
U1 и V1 значения соответственно на первом и втором настроечных выходах вычислительного модуля на j-м такте,
a1 и W1 значения соответственно на информационных входе и выходе вычислительного модуля и j-м такте.

РИСУНКИ

Рисунок 1, Рисунок 2



 

Похожие патенты:

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

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

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

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

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

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

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

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

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

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

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

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

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

Изобретение относится к цифровой вычислительной технике и может быть использовано для аппаратной поддержки вычислений в системах синтеза и анализа цифровых автоматов, диагностики цифровых устройств, сжатия данных, обработки изображений, управления роботами - манипуляторами, синтеза топологии БИС

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

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

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

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

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

Изобретение относится к способам численного решения системы дифференциальных уравнений (СДУ)
Наверх