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

СП

С5 СО 00 Ј 05

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

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

На фиг.1 представлена схема устройства; на фиг.2 - схема операцией- ного блока первого столбца матрицы; на фиг.З - схема операционного блока первой строки с второго по N-й столбцов матрицы; на фиг.4 - схема операционного блока первой с.троки (N+1)- го столбца матрицы; па фиг.З - схема операционного блока с второго по N-й столбцов и с второй по N-ю строк матрицы; на фиг.6 - схема операционного блока (N-H)-ro столбца и с второй по N-ю строк матрицы (N - порядок решаемой системы линейных алгебраических уравнений).

Устройство содержит матрицу размером N(N+1) операционных блоков 1J вход 2 режима устройства, вход 3 синх чониэации устройства, входы 4 коэффициентов устройства, выходы 5 операци- - и . X блоког матрицы, выходы 6A-6N vr-тройства. Каждый операционный блок 1 первого столбца матрицы содержит мупьтилчексор 7 и регистр 8. Каждый операционный блок 1 первой строки с

0

второго по N-й столбцов матрицы содержит мультиплексор 7, регистр 8 и делитель 9.

Каждьй операционный бЛок 1 с второго по N-й столбцов и с второго по N-ю строк матрицы содержит мультиплексор 7, регистр 8, умножитель 10, сумматор 1 1 . К.аждый операционный блок 1 (N+1)-ro столбца с второй по N-ю строк матрицы содержит регистр 8, умножитель 10 и сумматор 11. ч

Устройство осуществляет решение системы из N линейных алгебраических уравнений вида , где - матрица коэффициентов, ,,..., - вектор-столбец неизвестных, , ,.,. , - вектор-столбец свободных членов, на основе метода исключения. Решение системы из N линейных алгебраических уравнений с -N неизвестными происходит за N итераций. На каждой итерации вычисляется новая

(М

матрица С.,, , , где ,N, причем

С) г -1 исходная матрица См,(ц.ц-) A:Bj, т.е.

(.(01

C;j a, j , где i,j 1,N ,b;, i

(«-,

1,N. Элементы матриц СН1 )вычисляются следующим образом:

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

(1

ijH

(и-И

,(гьЛ i.jvt

CU,J4. -С,Ч -. i 1,N-1,j 1,N+1-n;

с 1 1С л

j

Р «и

, , ,N+1-n.

In) Ha N-й итерации матрица С N l( ц V(n1 вы

t N

рождается в вектор-столбец

rJN № (1T

, С2,, . . . ,С у , J , являющийся решением системы линейных алгебраичес

(N1 NM

ких уравнений, т.е.

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

С синхровхода 3 на входа: записи- чтения регистров 8 поступает первый тактовый импульс, а на вход 2 устройства подается единица, откуда она поступает на управляющий вход муль- типлекгора 1 операционного блока 1, j , гд.° i,j 1,N и, таким образом, с ин- формлгиочною входа 4 ;. на выход мультиплексора 7 ппгтупает ичформа1 н 5

0

,-

и записывается в регистр 8. В операционном блоке 1 ,,4, информация записывается в регистр 8 непосредственно с входа 4; Nv, . Таким образом,в регистрах 8 операционных блоков где ,N, ,N+1., будут записаны элементы С; . исходной матрицы

(

CN«(N + il с выхода блока 1М элемент

(С)

С поступает на одни информационные

входы делителей 9 операционных блоков 1(i , где ,N-M, на другие информационные входы которых из регистров 8 поступают гоответствуюшие элементы С (° . На выход делителя 9 операционного блока 1,. поступает частное

(С) , (01 (.)

С , , /г- 1 С н ; , , и- орор дачее погт.)

пает на соответствующий информационный вход умножителя ТО операционного блока 1 , где ,N, и на выход 5tj операционных блоков. С выхода операционного блока 1 , , элемент С ;. поступает на информационный вход умножителя 10 операционного блока 1J . С выхода умножителя 10 операционного блока 1,;: произведение С 1в| /С°

поступает на один информационный вход сумматора 11, на другой информационн вход которого с выхода регистра 9 поступает элемент с{°| . На выход сумматора 11 операционного блока 1« 1 и далее на выход 6 поступает элемент

J f I

,«1 i..,j-i

,(о) Ч

-С

йЧ

ДО) м

На втором такте на вход 12 подается ноль, который позволяет пропустить на выход мультиплексора 7 операционного блока 1;: , где ,N-f, j 1,N, информацию с информационного выхода 5 , + :+, операционных блоков и на выход мультиплексора 7 операционного блока 1N информацию с информационного выхода 5 .,, операционных блоков На последующих тактах ня выход мультиплексора 7 информация пропускается только с информационных выходов 5{ . С выхода мультиплексора 7 информация з ии ывается в регистр 8. Таким образом, в регистрах 8 операционных блоков 1;:, где i,,N, записаны элементы Г. Лалре устройство работает аналогично первому такту. В конце такта на информационные выходы 5;:, где ,N, j 2,поступают элементы

(1) С ; , : , и на информационные выходы

е

-(,;, поступают элементы CN :,.

На n-м такте в регистры 8 операционного блока 1, , где ,N, j 1,N+1-n 45 ключей к первым информационным входам

записываются элементы С . Далее устройство работает аналогично предыдущим тактам. В конце n-го такта, на информационные выходы 5; , где ,N, j 2, N+1 -п, поступают элементы С {Г, , 5С и на информационные выходы поступают элементы с|Л , .

На N-м такте в регистры 8 операционного блока 1;: , где .N, ,2, записываются элементы С После аналогичных действий, как на предадут ь,ях тактах, в конце такта на информа- цконные выходы 5;г , где ,N, поступают элементы , и на информацион55

операционных блоков с третьгго по (N+D-й столбцов 1-й строки матрицы, первые входы коэффициентов групп с второй по N-ю устройства подключены соответственно к первым информационным входам операционных блоков первого столбца строк с второй по N-ю матрицы, j-й вход коэффициентов к-и группы (где ,...,N) устройства подключен к второму информационному входу операционного блока k-й строки j-ro столбца матрицы, первый выход операционного блока первой строки j-ro столбца матрицы подключен к rpt , ( W. I

ный выход Ь.„ поступает элемент

j u i / и |

Затем элементы столбца С,, с ,

где ,N, поступают на информационные пыходы 6j устройства, являющиеся решением системы линейных алгебраических уравнений.

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

0

5

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

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

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

С

5

операционных блоков с третьгго по (N+D-й столбцов 1-й строки матрицы, первые входы коэффициентов групп с второй по N-ю устройства подключены соответственно к первым информационным входам операционных блоков первого столбца строк с второй по N-ю матрицы, j-й вход коэффициентов к-и группы (где ,...,N) устройства подключен к второму информационному входу операционного блока k-й строки j-ro столбца матрицы, первый выход операционного блока первой строки j-ro столбца матрицы подключен к rpt тьим информационным входам операционных блоков j-ro столбца с третьей по N-IO строк матрицы, третий информационный вход операционного блока первой строки k-го столбца матрицы подключен к выходу операционного блока второй строки (k+1)-ro столбца матрицы, четвертый информационный вход операционного блока k-ro столбца 1-й строки (где ,...,N-1) матрицы подключен к выходу операционного блока (1+1)-й строки (k+1)-ro столбца матрицы, второй выход4операционного блока первой строки т-го столбца (где га 3,... ,N+1) подключен к четвертому информационному входу операционного блока N-й строки (т-1)-го столбца матрицы, выход операционного блока второго столбца k-й строки матрицы подключен к второму информационному входу операционного блока первого столбца (k-O-й строки матрицы и к (k-D-му выходу -устройства, второй выход операционного блока первой строки второго столбца матрицы подключен к второму информационному входу операционного блока первого столбца N-й i троки матрицы и к N-му выходу устройства, при этом каждый операционный блок первого столбца матрицы содержит мультиплексор и регистр, причем в каждом операционном блоке первого столбца матрицы управляющий вход,вход синхронизации, первый и второй инфор- мационные входы-операционного блока первого столбца матрицы подключены соответственно к управляющему входу мультиплексора, к входу записи-чтения регистра, к первому и второму инфор- мационным входам мультиплексора, выход которого подключен к информационному входу регистра, выход которого подключен к выходу операционного блок первого столбца матрицы, при этом каждый операционный блок первой строки с второго по N-й столбцов матрицы содержит мультиплексор, регистр и делитель, причем в каждом операционном блоке первой строки с второго по N-й столбцов матрицы первый, второй и третий информационные входы, вход синхронизации и управляющий вход операционных блоков первой строки с второго по N-й столбцов матрицы подключены соответственно к первому информационному входу делителя, к первому и второму информационным входам мультиплексора, к входу записи-чтения ре

0 0 5 0 5 Q

5

гистра и к управляющему входу мультиплексора, выход которого подключен к информационному входу регистра, выход которого подключен к второму информационному входу делителя, выход которого подключен к первому и второму выходам операционных блоков первой строки со. второго по N-й столбцов матрицы, при этом операционный блок первой строки (N+0-го столбца матрицы содержит регистр и делитель, причем Б операционном блоке первой строки (N+1)-ro столбца матрицы первый и второй информационные входы и вход синхронизации операционного блока первой строки (N+1)-ro столбца матрицы подключены соответственно к первому информационному входу делителя, к информационному входу регистра и к входу записи-чтения регистра, выход которого подключен к второму информационному входу делителя, выход которого подключен к первому и второму выходам операционного блока первой строки (N+1)-ro столбца матрицы, причем каждый операционный блок с второго по N-й столбцов и с второй по N-ю строк матрицы содержит мультиплексор, регистр, сумматор и умножитель, причем в каждом операционном блоке с второго по N-й столбцов и с второй по N-io строк матрицы первый, второй, третий и четвертый информационные входы, вход синхронизации и управляющий вход операционного блока с второго по N-й столбцов и с второй по N-ю строк матрицы подключены соответственно к первым и вторым информационным входам умножителя и мультиплексора, к входу записи-чтения регистра и к управляющему входу мультиплексора, выход которого подключен к информационному входу регистра, выходы регистра и умножителя подключены к первому и второму информационным входам сумматора, выход которого подключен к выходу операционного блока с второго по N-й столбцов и с второй по N-ю строк матрицы, примем каждый операционный блок (N+1)-ro столбца с второй по N-ю строк матрицы содержит регистр, умножитель и сумматор, причем в операционном блоке (N-H)-ro столбца с второй по N-ю строк матрицы первый, второй и третий информационные входы и вход синхронизации операционного блока (N-H)-ro столбца с второй по N-ю строк матрицы подключены соответственно к первому информационному входу умножителя, к информационному входу регистра, к второму информационному входу умножителя и к входу записи-чтения регистра, выходы стра и умножителя подключены соответственно к первому н второму информационны входам сумматора, выход которого подключен к выходу операционного блока (М-Н)-го столбца с второй по N-ю строк матрицы.