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

(5) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

1

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

Известны устройства, с помощью которых можно решать системы лимейных алгебраических уравнений прямыми методами, обеспе ивающими решение системы за конечное число шагов, независящее от матрицы исходных коэффициентов. Например, устройство, состоящее из двух матриц решающих блоков, арифметического блока, блока управления, блока вывода и индикации, двух программных блоков, блока сравнения, блока вводе, коэффициентов, блока постоянной памяти, блока оперативной пймяти и двух .счетчиков С JПо объему составляющей аппаратуры указанное устройство является довольно громоздким и представляет собой, по существу, специализированную ЭВМ для матричных вычислений. Однако арифметический блок указанного устройства может осуществлять одновременную обработку только двух операндов, что определяет низкое быстродействие всего устройства.

to

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

IS частичного результата, двух регистров сомножителя, двух регистров переносов, двух регистров делителя, двух сумматоров, двух блоков постоянной памяти, двух преобразователей прямо20го кода в дополнительный, двух управляющих триггеров, элемента ИЛИ, двенадцати триггеров и двух шин тактовых импульсов. Это устройство позволяет совместить во времени выполнение множества операций вида а/Ь и c-de - двух групповых операций, к которым сводится решение системы линейных алгебраических уравнений любым из-пря мых методов. Тем самым при помощи его возможно значительное уменьшение времени решения системы уравнений по сравнению с предыдущим устройством 2. К недостаткам известного устройства следует отнести то, что перед подачей операндов последующей групповой операции необходим такт считы вания результата выполнения предыдущей групповой операции. Это увели чивает количество тактов работы уст ройства в два раза. Кроме того, результаты деления невозможно использовать в групповой операции второго типа до их выхода с последнего каскада устройства, что в процессе пре образования матрицы исходных коэффи циентов приводит к дополнительным простоям устройства. Так, например, решение при помощи известного устройства системы п линейных алгебраических уравнений с п неизвестным методом Гаусса потребует м + (Р-2.} пх 4 тактов работы устройства для выполнения прямого хода и М1. 1-п( )-« р, (Р-3) тактов для обратного хода. Цель изобретения - увеличение скорости решения системы линейных ал гебраических уравнений и уменьшение аппаратурных затрат. Поставленная цель достигается тем что в каждый каскад устройства, содержащего Р каскадов (.Р-разрядность чисел), каждый из которых содер чит первый и второй регистры, регистр результата, сумматор, блок постоянной памяти, управляющий триггер, элемент ИЛИ, два триггера, причем выходы второго регистра соединены с входами второго регистра следующе го каскада, а входы первого и второго регистров первого каскада явля ются входами постоянных коэффициентов устройства, выход управляющего триггера каждого каскада соединен с установочным входом управляющего триггера следующего каскада, выходы регистра результата подключены к пе вой группе входов сумматора, первый и второй выходы блока постоянной па мяти соединены соответственно с установочными входами первого и второго триггеров, а тактовые входы регистров и управляющего триггера соединены с входом тактовых импульсов устройства, введены сумматор-вычитатель, два элемента И и три группы элементов 2-2И-ИЛИ, причем выходы первого регистра связаны с первой группой входов сумматора-вычитателя, к входам второй группы которого подключены выходы второго регистра, при этом выход старшего разряда второго регистра соединен с входами трех старших разрядов второй группы сумматоравычитателя, выходы Р-1 младших разрядов которого подключены к входам Р-1 старших разрядов, начиная с второго, первого регистра следующего каскада, к входам двух старших разрядов которого подключены выходы первой группы элементов 2-2И-ИЛИ, первые, вторые, третьи и четвертые входы которых соединены соответственно с Р-ым и (Р+1)-м выходами сумматоравычитателя, с прямым выходом управляющего триггера, с инверсным выходом управляющего триггера, с третьим и четвертым выходами блока постоянной памяти, первый выход которого подключен к первому входу элемента ИЛИ, к второй группе входов всех разрядов сумматора, кроме младшего, и к первому входу первого элемента второй группы элементов 2-2И-ИЛИ, к второму, третьему и четвертому входам которого подключены соответственно прямой выход управляющего триггера, выход первого триггера и инверсный выход управляющего триггера,- второй выход блока постоянной памяти соединен с вторым входом элемента ИЛИ и с первым входом второго элемента второй группы элементов 2-2И-ИЛИ, второй, третий и четвертый входы которого подключены соответственно к прямому выходу управляющего триггера, к выходу второго триггера и к инверсному выходу управляющего триггера, а выходы второй группы элементов 2-2И-ИЛИ соединены с управляющими входами сумматора-вычитателя, выход элемента ИЛИ соединен с входом младшего разряда второй группы сумматора, тактовые входы первого и второго триггеров соединены с выходом первого элемента И, первый вход которого подключен к входу тактовых импульсов устройства, второи вход - к прямому выходу управляющего триггера и к первому входу второго элемента И, второй вход которого соединен с выходом старшего разряда второго регистра, а выход второго элемента И соединен с выходом старшего разряда блока постоянной памяти, к входам других четырех разрядов которого подключены выходы третьей группы элементов 2-2И-ИЛИ, первые, вторые, третьи и четвертые входы которых соединены соответственно с выходами четырех старших ра рядов сумматора-вымитателя, с инверсным выходом управляющего тригГера, с выходами четырех старших ра рядов первого регистра и с прямым выходом управляющего триггера. На.чертеже показана структурная схема |-го и (4-1)-го каскадов устройства. Каждый каскад устройства состоит из(.Р+2)-разрядного первого регистра 1. i, выходы которого соединены с первыми входами (Р+2)-разрядного сумматора-вычитателя 2. 1, к вторым входам которого подключены выходы Р-разрядного второго регистра З-. i, соединенные также и с входами второго регистра следующего каскада 3.1+1 .причем выход старшего разряда регистра 3. i соединен с входами тр старших разрядов сумматора-вычитате 2. i, четыре старшие выходы которог связаны с первыми входами Т-ретьей группы из 4-х элементов 2-2И-ИЛИ . к вторым, третьим и четвертым входам которой подведены соответственно инверсный выход управляющего три гера 5. 1 четыре старшие выходы пе вого регистра 1.i и прямой выход уп равляющего триггера 5. i соединенный также с входом управляющего три гера следующего каскада 5. +t и с входом первой схемы И 6. I, другой вход которой подключен к шине тактовых импульсов, а выход ее связан с тактовыми входами первого триггера 7- i и второго триггера 8. i, к установочным входам которых подведе ны соответственно первый выход бло ка 9. i постоянной памяти, соединен ный также и с первым входом первого элемента второй группы из 2-х элементов 2-2И-ИЛИ 10. 1, и второй выход блока 9. i постоянной памяти, со диненный также и с первым входом вт рого элемента группы 10. I, при это вторые и четвертые входы элементов ЭТОЙ группы соединены соответственно с прямым и инверсным выходами управг ляющегр триггера 5.1 а третий вход первого и третий вход второго элементов в группе 10. I связаны соответственно с выходом первого триггера 7.1 и выходом второго триггера 8.i. В каждый каскад устройства входит также второй элемент И 11.1, первый и второй входы которого подключены соответственно, к прямому выходу управляющего триггера 5. I и к выходу старшего разряда Егторого регистра 3.1 ,а выход его/связгги со старшим входом блока постоянной памяти9.Ijк четырем другим входам которого подсоединены выходы второй группы элементов 2-2И-ИЛИ t. i, а третий и четвертый выходы блока 9.i постоянной памяти связаны с входами элементов первой группы из 2-х элементов 2-2И-ИЛИ 12.1, к четвертым, вторым и первым входам которых подключены соответственно инверсный выход управляющего триггера 5. прямой выход управляющего триггера 5.1 Р-й и (Р+1)-й выходы сумматора-вычитателя 2.1, выходы же Р-1 младших разрядов сумматора-вычитателя 2.1 связаны с второго по Р-й входами первого регистра следующего каскада 1.i j к двум старшим разрядам которого подсоединены выходы первой группы элементов 2-2И-ИЛИ 12.1. Кроме того, каждый каскад устройства содержит разрядный регистр 13. I результата (i-номер каскада), выходы которого соединены с 5 старшими первыми входами (5+1}-разрядного сумматора 1. i, к старшим вторым входам которого подключен первый выход блока 9.i постоянной памяти, соединенный та.кже и с входом элемента ИЛИ 15.1,к второмувходу которого подведен второй выход блока 9.f постоянной памяти, а его выход соединен с вторым входом младшего разряда сумматора 1. этом первый вход этого разряда сумматора связан с логическим нолем, а выходы сумматора связаны с входами регистра 13. 5+1 результата следующего каскада, и,наконец, выходы третьей группы элементов 2-2И-ИЛИ 10. I соединены с управляющими входами сумматора-вычитателя 2., а тактовые входы регистров и управляющего триг /ера связаны с шиной тактовых импульсов. 7 Выполнение арифметических операций в устройстве происходит в двоич ной системе счисления, начиная со старших разрядов, с промежуточным представлением результатов внутри устройства избыточным квазиканонмческим кодом с цифрами 1,0,0. Все каскады устройства однотипны при этом первый каскад может не содержать регистра 13. , тогда первые входы сумматора 1. I должны быть соединены с логическим нолем. Во всех каскадах, кроме первого, регистр 1, i может быть (Р+1)-разря ным. При этом первый вход младшего разряда сумматора-вычитателя 2.1 до жен быть также подсоединен к логическому нолю. Рассмотрим работу устройства на примере решения системы алгебраических линейных уравнений ме тодом Гаусса, где А - матрица коэффициентов размерности В -век тор правыхчастей; х - вектор неизвестных. Как известно, метод Гаусса состоит из последовательности п пре образований расширенной матрицы сие темы А, bj и сводится к последовательному исключению неизвестных. В результате получается эквивалентная система уравнений с верхней треугол ной матрицей V, имеюцей единицы на главной диагонали, и преобразованным столбцом свободных членов Y. На первом такте работы устройства управляющий триггер 5.5 устанавливается в 1, на регистр 3. i записывается .дополнительный код коэффициента а , а на регистр 1. I зано.сится коэффициент а, представленный дополнительным двоичным кодом с тремя знаковыми разрядами. На втором этапе содержимое регистра 3.1 и триггера 5.1 передается соответственно в регистр 3.2 и триггер 5.2, содержимое регистра 1. через сумматор-вычитатель 2.1 перепись1вается в регистр 1.2, а на регистр 1.1, регистр 3.1, и триггер 5.1 заносятся соответственно дополнительный код а . имеющий три знаковые разряда, дополнительный код а и код О. При этом записанное на втором такте в регистр 1.2 число представляет собой удвоенный первый частичный остаток от деления содержимого регистра 1.1 на содержимое регистра 3.1. Деление осуществляет.ся следующим стразом. Блоком 9.1 б постоянной памяти в зависимости от регистра 3.1, а знакового разряда также от значений четырех старших 1.1 выделяется разрядов регистра первая старшая цифра частного, представленная избыточным квазиканоническим кодом с цифрами (1,0,1 Л причем цифра 1 будет соответствовать наличию кода 1 на первом выходе блока постоянной памяти, а цифра 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 передается в регистр 1.2, а содержимое триггера 5.1 - в триггер 5.2, а на регистр 1.1, регистр 3.1 и триггер 5.1 заносятся соответственно дополнительный код , имеющий три знаковые разряда, дополнительный код а. , и код О. При этом записанное на третьем такте в регистр 1.2 число .представлет собой частичное произведение от умножения содержимого регистра 3.1 на старший разряд частного от деления а на а, записанный во втором такте в триггеры 7.1 и 8.1, вычтенное от содержимого регистра 1.1, дополнительно поделенное на 1 и удвоенное. Отличие в работе первого каскада при выполнении этой групповой операции от предыдущей заключается в том, что с управляющими входами сумматора-вычитателя 2.1 связаны выходы триггеров 7.1 и 8.1, входами блока постоянной памяти 9.1 являются выходы четырех старших разрядов сумматора-вычитателя 2.1, выделенная старшая цифра ре зуяьтата не меняет содержимого триг геров 7«1 и 8.1, а входами двух ста ших разрядов регистра 1.2 являются два старших выхода блока постоянной памяти, представляющие собой значение двух старших разрядов удвоенног частного от дополнительного деле ния содержимого сумматора-вычитател 2.1 на единицу, необходимого для перевода его в избыточный квазикано нический код. Все эти отличия определяются нолевым состоянием управляющего триггера 5.- осуществляет ся благода{ я наличию групп элементов 2-2И-ИШ с соответствующими свя зями. В дальнейшем описанные преобразо вания -повторяются для из каскадов устройства для всех п прео разований исходной матрицы коэффициентов. При этом на 1-ом преобразовании исходной матрицы эле менты строки, содержащей ведущий элемент., определяются по формуле , 1 ,а остальные элементы матрицы - по формуле оу .f-ci|jaVV / i j-ir+H,M - Определение коэффициентов в устройстве происходит в квазиканоничес ком избыточном коде с цифрами (t,0, Т . Для перевода коэффициентов в дополнительный двоичный код служит сумматор Т, i, обеспечивающий прибавление к содержимому регистра , 13. i половины значения его младшего разряда, если очередная цифра коэффициента, выделенная при помощи блока 9.1 постоянной памяти,, и прибавление к содержимому регистра 13. i дополнител.ьного кода половины его младшего разряда, если нТи Всего для преобразования матрицы А, Ь к матрице v, Y потребуется . . и )« тактов. Решение системы с треугольной ма рицей V осуществляется аналогично ранее описанному с той лишь разницей, что на первом такте на регистре 1,1 записывается дополнительный двоичный код числа X Yj,, имеющий три знаковые разряда, а на регистр 3.1 подается код 0,111...1, тем самым осуществляется операция X /1 . В течение следующих тактов на входы регистра 1.1 и регистра 3.1 подаются соответственно и U самым выполняются операции . Y;. (Y,- - и,-„-х„) /1. После получения, на выходе устройства дополнительного кода.Х, его можно подавать на входы устройства для получения следующего компонента вектора х и значений Y/(Y. - и,-„.Ли)/1 Всего для выполнения обратного хода алгоритма Гаусса требуется г Vl И 1 тактов, ох Т .124 Таким образом, решение системы п линейных алгебраических уравнений с п неизвестными может быть осуществлено за Ь (-h |)н-к4:1Р-1)Р тактов, в то время как для достижения этой же цели при помощи известного устройства требуется иП.|-У1Ч(р-ь)и4(|-р,)р тактов. Тем самым, решение системы линейных алгебраических уравнений при помощи предлагаемого устройства осуществляется Ha-r-v +- y , тактов быстрее, чем известном, а его аппаратурные затраты составляют приблизительно 5/6 аппаратурных затрат известного. формула изобретения Устройство для решения систем линейных алгебраических уравнений, содержащее Р каскадов (Р Разрядность чисел)каждый из которых содержит первый и второй регистры, регистр результата, сумматор, блок постоянной памяти, управляющий триггер, элемент ИЛИ, два триггера, причем выходы второго регистра соединены с входами второго регистра следующего каскада, а входы первого и второго регистров первого каскада являются входами постоянных коэффициентов усТ ройства, выход управляющего триггера 11 каждого каскада соединен с установо ным входом управляющего триггера сл дующего каскада, выходы регистра ре зультата подключены к первой группе входов сумматора, первый и второй выходы блока постоянной памяти соединены соответственно с установочными входами первого и второго триг геров, а тактовые входы регистров и управляющего триггера соединены с входом тактовых импульсов устройства, отличающееся тем, что, с целью увеличения скорости вы числения системы линейных алгебраических уравнений и уменьшения аппаратурных затрат, каждый каскад устройства дополнительно содержит сумматор-вычитатель, два элемента И и три группы элементов 2-2И-ИЛИ, причем выходы первого регистра связаны с первой группой входов сумматора- вычитателя, к входам второй группы которого подключены выходы второго регистра, при этом выход старшего разряда второго регистра соединен с входами трех старших раз рядов второй группы сумматора-вычитателя, выходы Р-1 младших разрядов которого подключены к входам Р-1 старших ра:зрядоВ; начиная с второго, первого регистра следующего |Аскада к входам двух старших разрядов которого подключены выходы первой группы элементов 2-2И-ИЛИ, первые, вторые, третьи и четвертые входы которых соединены соответственно с Р-м и (Р+1 )-и выходами сумматоравычитателя, с прямым выходом управляющего триггера, с инверсным выходом управляющего триггера, с третьим и четвертым выходами блока постоянной памяти, первый выход которо го подключен к первому входу элемен та ИЛИ, к второй группе входов всех разрядов сумматора, кроме младшего, и к первому входу первого элемента второй группы Элементов 2-2И-ИЛИ к второму, третьему и„четвертому входам которого подключены соответственно прямой выход управляющего триггера, выход первого триггера и инверсный выход управляющего триггера, второй выход блока постоянной памяти соединен с вторым входом элемента ИЛИ и с первым входом второго элемента второй группы элементов 2-2И-ИЛИ, второй, третий и четвертый входы которого подключены соответственно к прямому выходу управляющего триггера к выходу второго триггера и к инверсному выходу управляющего триггера, а выходы второй группы элементов 2-2И-ИЛИ соединены с управляющими входами сумматора-вычитателя, выход элемента ИЛИ соединен с входом младшего разряда второй группы сумматора, тактовые входы первого и второго триггеров соединены с выходом первого элемента И, первый вход которого подключен к входу тактовых импульсов устройства, второй вход - к прямому выходу управляющего триггера и к первому входу второго элемента И, второй вход которого соединен с выходом старшего разряда второго регистра, а выход второго элемента И соединен с выходом старшего разряда блока постоянной памяти, к входам других четырех разрядов которого подключены.. выходы третьей группы элементов 2-2И-ИЛИ,первый,вторые, третьи и четвёртые входы которых соединены соответственно с выходами четырех старших разрядов сумматора-вычитателя, с инверсным выходом управляющего три|- гера, с выходами четырех старших разрядов первого регистра и с прямым выходом управляющего триггера. Источники информации, принятые во внимание при экспертизе 1,Авторское свидетельство СССР № , кл. G 06 F 15/32, 1976. 2.Заявка № 2721505/18-25, кл, G 06 F 7/38, 02.02.79.