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

ОП ИСАНИЕИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских.СоциалистическихРеспублик и 940167(51) М Г 1 У 32 т соединением запек 3 ЬвударстевнныЯ винтвт СССР ао двлаи иэабрвтеннЯ к открытЯ(23) Приоритет -убликовано 30 . 06. 82. Бю ата опубликования описан етень2 тт 30.0682й, А Коф 2) Авторы изобретения Киевский ордена Лен им.50-летия Великой(5 Ц) УСТРОЙСТВО ДЛЯ РЕИЕНИЯ СИСТЕМ ЛИНЕЙН АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙИзобретение тельной техник нению арифмети горегистровых ствах, выполне шой степенью и использовано в ме в качестве 5 лока 1 О относится к вычислив частности к выполеских операций в мнорифметических устройных на узлах с больтеграции, и может быть вычислительной систе- ысокопроизводительного Известны устроиства, с помощью которых можно решать системы линейных алгебраических уравнений прямыми методами, обеспечивающими решение системы эа конечное число шагов, независящее от матрицы исходных коэффициентов. Например, устройство, состоящее из двух матриц решающих блоков, арифметического блока, блока управления, блока вывода и индикации, двух программных блоков, 2 о блока сравнения, блока вводг коэффициентов, блока постоянной памяти, блока оперативной памяти и двух .счетчиков 1,1 . а политехнический ийсттттут-=-.Октябрьской социалистической революции По объему составляющей аппаратуры указанное устройство является довольно громоздким и представляет собой, по существу, специализирован. ную ЭВМ для матричных вычислений; Однако арифметический блок укаэанного устройства может осуществлять одновременную обработку только двух операндов, что определяет низкое быстродействие всего устройства.Наиболее близким по технической сущности к предполагаемому является устройство, содержащее. Р каскадов (Р - разрядность чисел), причем каждый каскад состоит из двух регистров частичного результата, двух регистров сомножителя, двух регистров переносов, двух регистров делителя, двух умматоров, двух блоков постоянной памяти, двух преобразователей прямого кода в дополнительный, двух управляющих триггеров, элемента ИЛИ двенадцати триггеров и двух шин тактовых импульсов.67 3 9 ч 01Это устройство позволяет совмес-тить во времени выполнение множества операций вида а/Ь и с-де - двухгрупповых операций, к которым сводится рещение системы линейных алгебраических уравнений любым из. прямых методов, Тем самым при помощиего возможно значительное уменьшение времени решения системы уравнений по сравнению с предыдущим 1 оустройством 2 ,К недостаткам известного устройства следует отнести то, что передподачей операндов последующей групповой операции необходим такт считывания результата выполнения предыдущей групповой операции, Это увели.чивает количество тактов работы устройства в два раза. Кроме того, результаты деления невозможно использовать в групповой операции второготипа до их выхода с последнего каскада устройства, что в процессе преобразования матрицы исходных коэффициентов приводит к дополнительнымпростоям устройства. Так, например,решение при помощи известного устройства системы и линейных алгебраических уравнений с и неизвестнымметодом Гаусса потребуетИ. =и +л+ Рп+ -(Р.)Г2.ПХтактов работы устройства для выполнения прямого хода и М = - п(п+1)+Г ЪР ОХ 2+ -(Р) тактов для обратного хода.Цель изобретения - увеличениескорости решения системы линейных алгебраических уравнений и уменьшениеаппаратурных затрат.Поставленная цель достигается тем,аочто в каждый каскад устройства, содержащего Р каскадов (,Р-разрядностьчисел), каждый иэ которых содержитпервый и второй регистры, регистррезультата, сумматор, блок постоянной памяти, управляющий триггер,элемент ИЛИ, два триггера, причемвыходы второго регистра соединеныс входами второго регистра следующего каскада, а входы первого и второго регистров первого каскада являются входами постоянных коэффициентов устройства, выход управляющеготриггера каждого каскада соединен сустановочным входом управляющеготриггера следующего каскада, выходырегистра результата подключены к первой группе входов сумматора, первыйи второй выходы блока постоянной памяти соединены соответственно сустановочными входами первого и второго триггеров, а тактовые входы регистров и управляющего триггера соединены с входом тактовых импульсовустройства, введены сумматор-вычитатель, два элемента И и три группыэлементов 2-2 И-ИЛИ, причем выходыпервого регистра связаны с первойгруппой входов сумматора-вычитателя,к входам второй группы которого подключены выходы второго регистра, приэтом выход старшего разряда второго регистра соединен с входами трех старших разрядов второй группы сумматоравычитателя, выходы Рмладших разрядов которого подключены к входамРстарших разрядов, начиная с второго, первого регистра следующегокаскада, к входам двух старших разрядов которого подключены выходы первой группы элементов 2-2 И-ИЛИ, первь 1 е, вторые, третьи и четвертые входы которых соединены соответственнос Р-ым и (Р+1)-м выходами сумматоравычитателя, с прямым выходом управляющего триггера, с инверсным выходом управляющего триггера, с третьим и четвертым выходами блока постоянной памяти, первый выход которого подключен к первому входу элемента ИЛИ, к второй группе входов всехразрядов сумматора, кроме младшего,и к первому входу первого элементавторой группы элементов 2-2 И-ИЛИ,к второму, третьему и четвертомувходам которого подключены соответственно прямой выход управляющего триггера, выход первого триггераи инверсный выход управляющего триг"гера,. второй выход блока постояннойпамяти соединен с вторым входом элемента ИЛИ и с первым входом второгоэлемента второй группы элементов2-2 И-ИЛИ, второй, третий и четвертый входы которого подключены соответственно к прямому выходу управляющего триггера, к выходу второготриггера и к инверсному выходу управ.ляющего триггера, а выходы второйгруппы элементов 2-2 И-ИЛИ соединеныс управляющими входами сумматора-вы.читателя, выход элемента ИЛИ соединен с входом младшего разряда второйгруппы сумматора, тактоеые входы первого и второго триггеров соединеныс выходом первого элемента И, первый вход которого подключен к входутактовых импульсов устройства, втоУ 6этой группы соединены соответственно с прямым и инверсным выходами управ.- ляющего триггера 5,1, а третий вход первого и третий вход второго элементов в группе 10. 1 связаны соответственно с выходом первого триггера 7. 1 и выходом второго триггера 8. 1. В каждый каскад устройства входит также второй элемент И 11.1, первый и второй входы которого подключены соответственно. к прямому выходу управляющего триггера 5. 1 и к выходу старшего разряда второго регистра 3. 1,а выход его:связан со старшим входом блока постоянной памяти 9.к четырем другим входам которого подсоединены выходы второй группы элементов 2-2 И-ИЛИ 4. 1, а третий и четвертый выходы блока 9. 1 постоянной памяти связаны с входами элементов первой группы из 2-х элементов2-2 И-ИЛИ 12.1, к четвертым, вторым. .и первым входам которых подключенысоответственно инверсный выход управляющего триггера 5. 1, прямой выход управляющего триггера 5.1,Р-й и (Р+1)-й выходы сумматора-вычитателя 2.1, выходы же Рмладшихразрядов сумматора-вычитателя 2.1 связаны с второго по Р-й входами первого регистра следующего каскада 1.1,к двум старшим разрядам которого под" соединены выходы первой группы элементов 2-2 И-ИЛИ 12,1. Кроме того, каждый каскад устройства содержит разрядный регистр 13. 1 результата ("номер каскада), выходы которого соединены сстаршими первыми входами (1+1)-разрядного сумматора , 14. 1, к старшим вторым входам которого подключен первый выход блока 9. 1 постоянной памяти, соединенный также и с входом элемента ИЛИ 15.1, к второму входу которого подведен второй выход блока 9, 1 пос" тоянной пмяти, а его выход соединен с вторым входом младшего разряда сумматора 14.1, при этом пер" вый вход этого разряда сумматора связан с логическим нолем, а выходы сумматора связаны с входами регистра 13. 1+1 результата следующего каскада, и, наконец, выходы третьей группы элементов 2-2 И-ИЛИ 10.соединены с управляющими входами сумматора-вычитателя 2.1, а тактовые входы регистров и управляющего триг гера связаны с шиной тактовых им" лульсов. 5 94016 рой вход - к прямому выходу управляющего триггера и к первому входу второго элемента И, второй вход которого соединен с выходом старшего разряда второго регистра, а выход 5 второго элемента И соединен с выходом старшего разряда блока постоянной памяти, к входам других четырех разрядов которого подключены выходы третьей группы элементов 2-2 И-ИПИ, 0 первые, вторые, третьи и четвертые входы которых соединены соответственно с выходами четырех старших разрядов сумматора"вычитателя, с инверсным выходом управляющего триг-15 гера, с выходами четырех старших разрядов первого регистра и с прямым выходом управляющего триггера.На.чертеже показана структурная схема 1-го и (+1)-го каскадов уст ройства.Каждый каскад устройства состоит из(Р+2)-разрядного первого регистра 11, выходы которого соединены с первыми входамиР+2)-разрядного 5 сумматора-вычитателя 2. 1, к вторым входам которого подключены выходы Р-разрядного второго регистра 3 , 1 соединенные также и с входами второго регистра следующего каскада З 0 3, 1+1,причем выход старшего разряда регистра 3,соединен с входами трех старших разрядов сумматора-вычитателя 2, 1, четыре старшие выходы которого связаны с первыми входами третьей35 группы из 4-х элементов 2-2 И-ИЛИ 4.к вторым, третьим и четвертым входам которой подведены соответственно инверсный выход управляющего триггера 5. 1, четыре старшие выходы первого регистра 1. и прямой выход управляющего триггера 5. 1, соединенный также с входом управляющего триггера следующего каскада 5. 1+1 и с входом первой схемы И 6. 1, другой вход которой подключен к шине тактовых импульсов, а выход ее связан с тактовыми входами первого триггера 7.и второго триггера 8. 1, к установочным входам которых подведе 50 ны соответственно первый выход блока 9.постоянной памяти, соединен" ный также и с первым входом первого элемента второй группы из 2-х элементов 2-2 И-ИЛИ 10. 1, и второй вы 55 ход блока 9. постоянной памяти, соед иненный также и с первым входом второго элемента группы 1 О. 1, при этом вторые и четвертые входы элементов67 8постоянной памяти в зависимости отзнакового разряда регистра 3.1, атакже от значений четырех старшихразрядов регистра 1,1 выделяетсяпервая старшая цифра частного, представленная избыточным квазиканоническим кодом с цифрами ( 1,0,1), причем цифра Т будет соответствоватьналичию кода "1" на первом выходеблока постоянной памяти, а цифрана втором выходе, если выделеннаяцифра - 1, то сумматор"вычитатель2. 1 осуществляет вычитание содержимого регистра 3,1 от содержимого регистра 1. 1, если 1, то содержимоерегистра 3,1 будет прибавлено сумматором-вычитателем 2.1 к содержимомурегистра 1. 1, если О, то через 2,1будет передано просто удвоенное со"держимое регистра 1.1, Выделеннаяцифра частного на втором такте записывается в триггер 7. и 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.заносятся соответственно дополнительный код а, имеющий три знаковые разряда, дополнительный кодад, и код "0". При этом записанноена третьем такте в регистр 1.2 число,представлет собой частичное произведение от умножения содержимого регистра 3,1 на старший разряд частного от деления а на а , записанный во втором такте в триггеры7.1 и 8.1, вычтенное от содержимогорегистра 1,1, дополнительно поделенное на и удвоенное, Отличие в.,работе первого каскада при выполне"нии этой групповой операции от предыдущей заключается в том, что суправляющими входами сумматора-вычитателя 2. 1 связаны выходы триггеров7. и 8. 1, входами блока постояннойпамяти 9.1 являются выходы четырехстарших разрядов сумматора-вычитате" 7 91101Выполнение арифметических операций в устройстве происходит в двоич"ной системе счисления, начиная состарших разрядов, с промежуточнымпредставлением результатов внутриустройства избыточным квазиканоническим кодом с цифрами 1 1,0,17,Все каскады устройства однотипны,при этом первый каскад может не содержать регистра 13, 1, тогда пер Овые входы сумматора 1 М.должныбыть соединены с логическим нолем,Во всех каскадах, кроме первого,регистр 1.может быть (Р+1)-разряд.,ным. При этом первый вход младшего , 1 ьразряда сумматора-вычитателя 2, должен быть также подсоединен к логи"ческоиу нолю,Рассмотрим работу устройствана примере решения системы алгебра- щических линейных уравнений А хВ методом Гаусса, где А - матрица коэффициентов размерности и"и; В - вектор правыхчастей; х - вектор неизвестных. Как известно, метод Гауссасостоит из последовательности и преобразований расширенной матрицы сис",темы А, Ь и сводится к последовательному исключению неизвестных. Врезультате получается эквивалентнаясистема уравнений с верхней т"реугольной матрицей У, имеющей единицы наглавной диагонали, и преобразованным столбцом свободных членов У.На первом такте работы устройствауправляющий триггер 5.1 устанавли"вается в "1", на регистр 3.записывается,дополнительный код коэффициента а , а на регистр 1. 1 заносится коэффициент а, представленный дополнительным двоичным кодом с фОтремя знаковыми разрядами.На втором этапе содержимое регистра 3.1 и триггера 5.1 передается соответственно в регистр 32 итриггер 5.2, содержимое регистра 1. 145через сумматор"вычитатель 2.переписывается в регистр 1,2, а на ре"гистр 1, 1, регистр 3, 1 и триггер5.1 заносятся соответственно дополнительный код а , имеющии три знаю 50ковые разряда, дополнительный кода и код "0". При этом записанноеана втором такте в регистр 1.2 числопредставляет собой удвоенный первыйчастичный остаток от деления содержимого регистра 1.1 на содержимоерегистра 3,1. Деление осуществляет,ся следующим образом. Блоком 9.111 9401 каждого каскада соединен с установочным входом управляющего триггера сле дующего каскада, выходы регистра ре- зультата подключены к первой группе входов сумматора, первый и второй выходы блока постоянной памяти соединены соответственно с установочными входами первого и второго триггеров, а тактовые входы регистров и управляющего триггера соединены с 10 входом тактовых импульсов устройства, о т л и ч а ю щ е е с я тем, что, с целью увеличения скорости вы" числения системы линейных алгебраицеских уравнений и уменьшения аппа ратурных затрат, каждый каскад устройства дополнительно содержит сумматор-вычитатель, два элемента И и три группы элементов 2-2 И-ИЛИ, причем выходы первого регистра свя заны с первой группой входов сумматора-вычитателя, к входам второй группы которого подключены выходы второго регистра, при этом выход старшего разряда второго регистра 25 соединен с входами трех старших разрядов второй группы сумматора-вычитателя, выходы Рмладших разрядов которого подключены к входам Рстарших разрядов, начиная с второго, зо первого регистра следующего каскада, к входам двух старших разрядов которого подключены выходы первой группы элементов 2-2 И-ИЛИ, первые, вторые, третьи и четвертые входы которых соединенЪ соответственно с Р-м и Р+1)-м выходами сумматоравычитателя, с прямым выходом управляющего триггера, с инверсным выхо; дом управляющего триггера, с третьим и четвертым выходами блока постоянной памяти, первый выход которого подключен к первому входу элемен" та ИЛИ, к второй группе входов всех разрядов сумматора, кроме младшего, и к первому входу первого элемента второй группы элементов 2-2 И"ИЛИ, к второму, третьему и четвертому 67 12входам которого подключены соответственно прямой выход управляющеготриггера, выход первого триггера иинверсный выход управляющего триггера, второй выход блока постояннойпамяти соединен с вторым входом элемента ИЛИ и с первым входом второгоэлемента второй группы элементов2-2 И"ИЛИ, второй, третий и четвертыйвходы которого подключены соответственно к прямому выходу управляющеготриггера, к выходу второго триггераи к инверсному выходу управляющеготриггера, а выходы второй группыэлементов 2-2 И-ИЛИ соединены с управляющими входами сумматора-вычитателя, выход элемента ИЛИ соединен с входом младшего разряда второй группы сумматора, тактовые входы первого и второго триггеров соединены с выходом первого элемента И,первый вход которого подключен квходу тактовых импульсов устройства,второй вход - к прямому выходу управляющего триггера и к первому входу второго элемента И, второй входкоторого соединен с выходом старшего разряда второго регистра, а выход второго элемента И соединен свыходом старшего разряда блока пос"тоянной памяти, к входам других четырех разрядов которого подключенывыходы. третьей группы элементов2-2 И-ИЛИ,первый, вторые, третьи и четвертые входы которых соединены соответственно с выходами четырех старших разрядов сумматора-вычитателя, синверсным выходом управляющего триггера, с выходами четырех старшихразрядов первого регистра и с прямымвыходом управляющего триггера. Источники информациипринятые во внимание при экспертизе1, Авторское свидетельство СССРМф 624234, кл, С 06 Г 15/32, 1976.2. Заявка Нф 2721505/18-25,кл. О 06 Г 7/38, 02.02,79.940167Составитель Л, ЛогачеваРедактор С. Крупенина Техред М. Гергель Корректор М. Коста,Заказ 4669(71 Тираж 733, ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Я, Раушская наб., д. 4/5юФилиал ППП "Патент", г. Ужгород, ул. Проектная, 4