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

 

О П И С А Н И Е, 940167

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских.

Социалистических

Республик (61) Дополнительное к авт. свид-ву(22) Заявлено 18. 12. 80 (21) 3219253/18-24 с присоединением заявки №вЂ” (23) Приоритет— (51)М. Кл.

G 06 F 1У324

3Ьвударстванный «еинтат

СССР ао двлаи иэабретеннк к отхрыткй

Опубликовано 30. 06.. 82. Бюллетень № 24 (53) ДК 681 «325. . 5 (088, 8) Дата опубликования описания 30. 06. 82

Л. Я. Нагорный, Г. М. Луцкий, А.Н. Долголенко;

А. В. Корочкин и А. Г. Кофто

Киевский ордена Ленина политехнический йй тмтут.-==-. —,. им.50-летия Великой Октябрьской социалистической революции (72) Авторы изобретения (71) Заявитель (54) УСТРОЙСТВО ДЛЯ РЕИЕНИЯ СИСТЕМ ЛИНЕЙНЫХ

АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ чиков (1 1.

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

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

По объему составляющей аппаратуры указанное устройство является довольно громоздким и представляет собой, по существу, специализированную ЭВМ для матричных вычислений;

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

Наиболее близким по технической сущности к предполагаемому является устройство, содержащее: Р каскадов (P - разрядность чисел), причем каждый каскад состоит из двух регистров частичного результата, двух регистров сомножителя, двух регистров переносов, двух регистров делителя, двух

:=vMHBT0poB ° двух блоков постоянной памяти, двух преобразователей прямого кода в дополнительный, двух управляющих триггеров, элемента ИЛИ, двенадцати триггеров и двух шин тактовых импульсов.

30

3 9401

Это устройство позволяет совмес- тить во времени выполнение множества операций вида а/Ь и с-de - двух групповых операций, к которым сводится решение системы линейных алгебраических уравнений любым из- прямых методов. Тем самым при помощи

его возможно значительное уменьшение времени решения системы уравнений по сравнению с предыдущим 1О устройством (2 ), К недостаткам известного устройства следует отнести то, что перед подачей операндов последующей групповой операции необходим такт считы- !5 вания результата выполнения предыдущей групповой операции. Это увеличивает количество тактов работы устройства в два раза. Кроме того, результаты деления невозможно использовать в групповой операции второго типа до их выхода с последнего каскада устройства, что в процессе преобразования матрицы исходных коэффициентов приводит к дополнительным простоям устройства. Так, например, решение при помощи известного устройства системы и линейных алгебраических уравнений с и неизвестным методом Гаусса потребует

M. =и +л+ Рп+ -(P-2.)

Г 2. пн ф тактов работы устройства для выполнения прямого хода и М = — п(n+1)N.

ГЪ

P 0Х 2

+ -(P-3) тактов для обратного хода.

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

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

P-1 старших разрядов, начиная с второго, первого регистра следующего каскада, к входам двух старших разрядов которого подключены выходы первой группы элементов 2-2И-ИЛИ, первые, вторые, третьи и четвертые входы которых соединены соответственно с P-ым и (Р+1)-м выходами сумматоравычитателя, с прямым выходом управляющего триггера, с инверсным выходом управляющего триггера, с третьим и четвертым выходами блока постоянной памяти, первый выход которого подключен к первому входу элемента ИЛИ, к второй группе входов всех разрядов сумматора, кроме младшего, и к первому входу первого элемента второй группы элементов 2-2И-ИЛИ, к второму, третьему и четвертому входам которого подключены соответственно прямой выход управляющего триггера, выход первого триггера и инверсный выход управляющего триггера,. второй выход блока постоянной памяти соединен с вторым входом элемента ИЛИ и с первым входом второго элемента второй группы элементов

2-2И-ИЛИ, второй, третий и четвертый входы которого подключены соответственно к прямому выходу управляющего триггера, к выходу второго триггера и к инверсному выходу управляющего триггера, а выходы второй группы элементов 2-2И-ИЛИ соединены с управляющими входами сумматора-вычитателя, выход элемента ИЛИ соединен с входом младшего разряда второй группы сумматора, тактовые входы первого и второго триггеров соединены с выходом первого элемента И, первый вход которого подключен к входу тактовых импульсов устройства, вто7 6 ! этой rpynw соединены соответственно с прямым и инверсным выходами управ.ляющего триггера 5.i, а третий вход первого и третий вход второго элементов в группе 10. 1 связаны соответственно с выходом первого триггера 7.i и выходом второго триггера

8. 1. 8 каждый каскад устройства входит также второй элемент И 11,i„ первый и второй входы которого подключены соответственно. к прямому выходу управляющего триггера 5. 1 и к выходу старшего разряда второго регистра

3. i, а выход его:связали со старшим входом блока постоянной памяти 9. 1 к четырем другим входам которого подсоединены выходы второй группы элементов 2-2И-ИЛИ 4. i, а третий и четвертый выходы блока 9. I постоянной памяти связаны с входами элементов первой группы из 2-х элементов

2-2И-ИЛИ 12.i, к четвертым, вторым. и первым входам которых подключены соответственно инверсный выход управляющего триггера 5. i, прямой выход управляющего триггера .1, Р-й и (Р+1)-й выходы сумматора-вычитателя 2.i, выходы же P-1 младших разрядов сумматора-вычитателя 2.i связаны с второго по P-й входами первого регистра следующего каскада 1.i„ к двум старшим разрядам которого под" соединены выходы первой группы элементов 2-2И-ИЛИ 12.i. Кроме того, каждый каскад устройства содержит разрядный регистр 13. I результата (i"номер каскада), выходы которого соединены с 1 старшими первыми входами (i+1)-разрядного сумматора . 14. i к старшим вторым входам которого подключен первый выход блока

9. i постоянной памяти, соединенный также и с входом элемента

ИЛИ 15.i, к второму входу которого подведен второй выход блока 9.i постоянной п*мяти, а его выход соединен с вторым входом младшего разряда сумматора 14.1 при этом первый вход этого разряда сумматора связан с логическим нолем, а выходы сумматора связаны с входами регистра 13. 1+1 результата следующего каскада, и, наконец, выходы третьей группы элементов 2-2И-ИЛИ 10, i соединены с управляющими входами сумматора-вычитателя 2.1, а тактовые входы регистров и управляющего триг гера связаны с шиной тактовых импульсов.

5 94016 рой вход - к прямому выходу управляющего триггера и к первому входу второго элемента И, второй вход которого соединен с выходом старшего разряда второго регистра, а выход s второго элемента И соединен с выходом старшего разряда блока постоянной памяти, к входам других четырех разрядов которого подключены выходы третьей группы элементов 2-2И-ИЛИ, 10 первые, вторые, третьи и четвертые входы которых соединены соответственно с выходами четырех старших разрядов сумматора"вычитателя, с инверсным выходом управляющего триг- 15 гера, с выходами четырех старших разрядов первого регистра и с прямым выходом управляющего триггера.

На.чертеже показана структурная схема i-го и (i+1)-ãî каскадов уст- 20 ройства.

Каждый каскад устройства состоит из(Р+2)-разрядного первого регистра I ° i, выходы которого соединены с первыми входами (Р+2)-разрядного zs сумматора-вычитателя 2. i, к вторым входам которого подключены выходы

Р-разрядного второго регистра 3. i„ соединенные также и с входами второго регистра следующего каскада З0

3. 1+1,причем выход старшего разряда регистра 3. 1 соединен с входами трех старших разрядов сумматора-вычитателя

2. i, четыре старшие выходы которого связаны с первыми входами третьей

35 группы из 4-х элементов 2-2И-ИЛИ 4. i к вторым, третьим и четвертым вхо1 дам которой подведены соответственно инверсный выход управляющего триггера . i, четыре старшие выходы первого регистра 1.i и прямой выход управляющего триггера 5. i, соединенный также с входом управляющего триггера следующего каскада 5. i+1 и с входом первой схемы И 6. 1, другой вход которой подключен к шине тактовых импульсов, а выход ее связан с тактовыми входами первого триггера 7. i и второго триггера 8. i, к установочным входам которых подведе50 ны соответственно первый выход блока 9. i постоянной памяти, соединенный также и с первым входом первого элемента второй группы из 2-х элементов 2-2И-ИЛИ 10. i и второй вы55 ход блока 9.1 постоянной памяти, соединенный также и с первым входом второго элемента группы 10. 1, при этом вторые и четвертые входы элементов

67 8 постоянной памяти в зависимости от знакового разряда регистра 3.1, а также от значений четырех старших разрядов регистра 1.1 выделяется первая старшая цифра частного, представленная избыточным квазиканоническим кодом с цифрами (1,0,1 ), причем цифра Т будет соответствовать наличию кода "l" на первом выходе блока постоянной памяти, а цифра 1 на втором выходе, если выделенная цифра - 1, то сумматор"вычитатель

2. 1 осуществляет вычитание содержимого регистра 3.1 от содержимого регистра 1. 1, если 1, то содержимое регистра 3.1 будет прибавлено сумматором-вычитателем 2.1 к содержимому регистра 1. 1, если О, то через 2,1 будет передано просто удвоенное со" держимое регистра 1.1. Выделенная цифра частного на втором такте записывается в триггер 7.1 и 8.1.

На третьем такте содержимое регистра 3.2 передается в регистр 3.3, содержимое триггера 5.2 — в триггер 5.3, а в регистр 1.3 записывается второй частичный остаток от деления а„ на а„„, причем в триггеры

7,2 и 8.2 записывается код второй старшей цифры, полученный аналогично первому.

Одновременно с этим содержимое регистра 3.1 переписывается на ре" гистр 3.2, содержимое регистра 1.1 через сумматор-вычитатель 2.1 IlB редается в регистр 1.2, а содержимое триггера 5. 1 - e триггер 5.2, а на регистр 1.1, регистр 3.1 и триггер

5.! заносятся соответственно дополнительный код а, имеющий три знаковые разряда, дополнительный код а<<, и код "0". При этом записанное на третьем такте в регистр 1.2 число

;представлет собой частичное произведение от умножения содержимого регистра 3.1 на старший разряд частного от деления а„ на а„, записанный во втором такте в триггеры

7.1 и 8.1, вычтенное от содержимого регистра 1.1, дополнительно поделенное на "!" и удвоенное. Отличие в .,работе первого каскада при выполнении этой групповой операции от предыдущей заключается в том, что с управляющими входами сумматора-вычитателя 2. 1 связаны выходы триггеров

7. 1 и 8. 1, входами блока постоянной памяти 9.1 являются выходы четырех старших разрядов сумматора-вычитате7 9401

Выполнение арифметических операций в устройстве происходит в двоич" ной системе счисления, начиная со старших разрядов, с промежуточным представлением результатов внутри устройства избыточным квазиканоническим кодом с цифрами (1,0,T).

Все каскады устройства однотипны, при этом первый каскад может не содержать регистра 13, i, тогда пер- t0 вые входы сумматора 14, I должны быть соединены с логическим нолем, Во всех каскадах, кроме первого, регистр 1. i может быть (Р+1)-разряд-, ным. При этом первый вход младшего, 15 разряда сумматора-вычитателя 2.! дол жен быть также подсоединен к логическоиу нолю.

Рассмотрим работу устройства на примере решения системы алгебра- щ ических линейных уравнений А х В методом Гаусса, где А - матрица коэффициентов размерности n"n; В - вектор правых частей; х - вектор неизвестных. Как известно, метод Гаусса состоит из последовательности п преобразований расширенной матрицы сис", темы (А, Ь) и сводится к последовательному исключению неизвестных. В результате получается эквивалентная 30 система уравнений с верхней т реугольной матрицей V, имеющей единицы на главной диагонали, и преобразованным столбцом свободных членов Y.

На первом такте работы устройства управляющий триггер 5. i устанавливается в "1", на регистр 3. i записывается .дополнительный код коэффициента а„, а на регистр 1. i зано. сится коэффициент а4, представленный дополнительным двоичным кодом с тремя знаковыми разрядами.

На втором этапе содержимое регистра 3.1 и триггера 5.! передается соответственно в регистр 3.2 и триггер 5.2, содержимое регистра 1. 1

45 через сумматор" вычитатель 2. переписывается в регистр 1,2, а на регистр 1, 1, регистр 3. 1 и триггер

5.! заносятся соответственно дополнительный код а, имеющии три знаv 50 ковые разряда, дополнительный код а и код "0". При этом записанное

ы на втором такте в регистр 1.2 число представляет собой удвоенный первый частичный остаток от деления содер- 55 жимого регистра 1.1 на содержимое регистра 3.1. Деление осуществляет,ся следующим образом. Блоком 9.1

0167 10 ре 1;1 записывается дополнительный двоичный код числа Х © Y, имеющий ю три знаковые разряда, а на регистр

3.1 подается код 0,111...1, тем самым осуществляется операция Х > /1.

В течение следующих 1п-1 тактов на входы регистра 1.1 и регистра 3„1 подаются соответственно Y„ U „ „ ем самым выполняются операции

10 У„=(У, - 0„,„ К„) /1."

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

Всего для выполйения обратного хода алгоритма Гаусса требуется

И И 1

М = — + — 4 — фР430

4в тактов. ОХ

Таким образом, решение системы и линейных алгебраических уравнений с и неизвестными может быть осуществлено за я. Ъ

Ъ

+1 +(9+-)1 - (Р-1)1

Ъ тактов, в то время, как для достижения этой же цели при помощи извест"

ЭО ного устройства требуется

N + 11 -+ (p.+ — )1„+ 6 р )р тактов.

Тем самым, решение системы линейных алгебраических уравнений при помощи предлагаемого устройства осу2. ъ ъ - 5 ) p2. ществляется на -и + > H 4 »-.1 такl тов быстрее, чем известном., а его

46" .аппаратурные затраты составляют приблизительно 5/б аппаратурных затрат известного.

„55

Решение системы с треугольной мат.рицей Ч осуществляется аналогично ранее описанному с той лишь разницей, что на первом такте на регист9 94 ля 2. 1, выделенная старшая цифра ре- зультата не меняет содержимого триггеров 7. 1 и 8.1, а входами двух старших разрядов регистра 1.2 являются два старших выхода блока постоянной памяти, представляющие собой значение двух старших разрядов удвоенного частного от дополнительного деления содержимого сумматора-вычитателя

2.1 на единицу, необходимого для перевода его в избыточный квазиканонический код. Все эти отличия îïðåделяются нолевым состоянием управляющего триггера g..1 и осуществляются благодаря наличию групп элементов 2-2И-ИЛИ с соответствующими связями.

В дальнейшем описанные преобразо" вания повторяются для каждого из каскадов устройства для всех и прео6 разований исходной матрицы коэффициентов. При этом на каждом i-ou преобразовании исходной матрицы эле менты строки, содержащей ведущий элемент, определяются по формуле сР. =a(а " i=5 )=1+,щ+, 15. Ц 11 i

1, а остальные элементы матрицы - no формуле

I< (1 ) И-Ю <1 > (-1) p / ,«3- Ч,4 1/ = СИ,11М.

Определение коэффициентов в устройстве происходит в кваэиканоническом избыточном коде с цифрами (1,0, 1) . Для перевода коэффициентов в дополнительный двоичный код служит сумматор 14. i, обеспечивающий прибавление к содержимому регистра ..

13. i половины значения его младше" го разряда, если очередная цифра коэффициента, выделенная при помощи блока 9.i постоянной памяти,"1", и прибавление к содержимому регистра 13. i дополнительного кода половины его младшего разряда, если

l IT!I

Всего для преобразования матрицы (А, Ь) к матрице (V, У)потребуется Ъ

М вЂ” + — +(Р+ )и

Э я. тактов. формула изобретения устройство для решения систем линейных алгебраических уравнении, содержащее Р каскадов (Р-разрядность чисел) каждый иэ которых содержит nept вый и второй регистры, регистр ре"

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

11 9401 каждого каскада соединен с установочным входом управляющего триггера сле дующего каскада, выходы регистра ре- зультата подключены к первой группе входов сумматора., первый и второй выходы блока постоянной памяти соединены соответственно с установочными входами первого и второго триг= геров, а тактовые входы регистров и управляющего триггера соединены с 1о входом тактовых импульсов устройства, о т л и ч а ю щ е е с я тем, что, с целью увеличения скорости вы" числения системы линейных алгебраических уравнений и уменьшения аппа- 15 ратурных затрат, каждый каскад устройства дополнительно содержит сумматор-вычитатель, два элемента И и три группы элементов 2-2И-ИЛИ, причем выходы первого регистра свя- m заны с первой группой входов сумматора-вычитателя, к входам второй группы которого подключены выходы второго регистра, при этом выход старшего разряда второго регистра zs соединен с входами трех старших разрядов второй группы сумматора-вычитателя, выходы Р-1 младших разрядов которого подключены к входам Р-1 старших разрядов, начиная с второго, зо первого регистра следующего к вскада, к входам двух старших разрядов которого подключены выходы первой группы элементов 2-2И-ИЛИ, первые, вторые, третьи и четвертые входы которых соединенЪ соответственно с

Р-м и (Р+1 )-м выходами сумматоравычитателя, с прямым выходом управляющего триггера, с инверсным выхо; дом управляющего триггера, с третьим и четвертым выходами блока постоянной памяти, первый выход которого подключен к первому входу элемента ИЛИ, к второй группе входов всех разрядов сумматора, кроме младшего, и к первому входу первого элемента второй группы элементов 2-2И"ИЛИ, к второму, третьему и„ четвертому

67 12 входам которого подключены соответственно прямой выход управляющего триггера, выход первого триггера и инверсный выход управляющего триггера, второй выход блока постоянной памяти соединен с вторым входом элемента ИЛИ и с первым входом второго элемента второй группы элементов

2-2И"ИЛИ, второй, третий и четвертый входы которого подключены соответственно к прямому выходу управляющего триггера, к выходу второго триггера и к инверсному выходу управляющего триггера, а выходы второй группыэлементов 2-2И-ИЛИ соединены с управляющими входами сумматора-вычитателя, выход элемента ИЛИ соединен с входом младшего разряда второй группы сумматора, тактовые входы первого и второго триггеров соединены с выходом первого элемента И, первый вход которого подключен к входу тактовых импульсов устройства, второй вход — к прямому выходу управляющего триггера и к первому входу второго элемента И, второй вход которого соединен с выходом старшего разряда второго регистра, а выход второго элемента И соединен с выходом старшего разряда блока постоянной памяти, к входам других че тырех разрядов которого подключены выходы. третьей группы элементов

2-2И-ИЛИ,первый, вторые, третьи и четвертые входы которых соединены соответственно с выходами четырех стар« ших разрядов сумматора-вычитателя, с инверсным выходом управляющего триггера, с выходами четырех старших разрядов первого регистра и с прямым выходом управляющего триггера.

Источники информации, принятые во внимание при экспертизе

1, Авторское свидетельство СССР

N 624234, кл, G 06 F 15/32, 1976.

2. Заявка Н 2721505/18-25, кл. G 06 F 7/38, 02.02 ° 79 °

940167

Составитель Л. Логачева

Редактор С. Крупенина Техред И. Гергель Корректор М. Коста, Заказ 4669/71 Тираж 733 Подписное

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

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

Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4