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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК 12545 6 Р 15/324 ОБРЕТЕ ДЕТЕЛЬСТ ГОСУДАРСТВЕННЫЙ НОМИТЕТ ССПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫ ОПИСАНИ Н АВТОРСКОМУ(71) Институт проблем моделирования в энергетике АН УССР(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ(57) Изобретение относится к цифровойвычислительной технике и может бытьиспользовано для быстрого решениясистем линейных алгебраических уравнений, Цель изобретения - повышениепроизводительности устройства. Устройство содержит матрицу пхп умножителей, п регистров, и сумматоров,и блоков приоритетного формированиянулей и элементов задержки, и элементов сравнения, элемент И, элементИЛИ, элемент НЕ, два одновибратора.Увеличение производительности устройства обеспечивается в .результатеуменьшения интервала времени междудвумя последовательными записямиприближений в регистр за счет определения моментов окончания формирования результатов. 2 ил.(Х юох 1-1 о т(а"-. имеем Изобретение относится к циФровойвычислительной технике и может бытьиспользовано в составе универсальных или специализированных машин, атакже автономно для быстрого решения системы линейных алгебраическихуравнений (СЛАУ).Цель изобретения - повышение производительности устройстваНа Фиг.1 представлена блок-схемаустройстйа для решения СИЛУ порядкадва; на Фиг.2 - схема одного разряда блока приоритетного Формированиянулеи,Устройство содержит первый и второй регистры 1.1 и 1.2, умножители2.1.1, .1.2, 2,2,1, 2.2,2 матрицыумножителей, первый и второй сумматоры 3,1 и 3.2, первый и второй блоки 4,1 и 4.2 приоритетного Формироваия нулей, первый и второй элементы 5,1 и 5.2 задержки, первый и Второй элементы 6.1 и 6.2 сравнения,элемент ИЛИ 7 первый и второй одноВибратор 8, элемент НЕ 9 элементИ 10. ОДНО 11 ибратор 11, входы 12-15задаия коэфФиццентов уравнений,Входы 16 ц 17 задания Величин правыхчастей уравцеий, вход 18 зат 1 ускаустройства, Выходы 19 и 20 результата устройства, Выход 21 сигналаокончания репеия. Блок приоритетного Формирования нулей содержит шидентичных схем, где ш = разрядностьустройства каждая из которых содержит одковцбратор 2, элемент 23 заДРржки, элРмент И 2 1, ВХОД 25, выход 26,Устройство работает следу 10111 имобразом.1В блоке приоритетного формирования нулей в стационарном режиме "0"или "1" ца входе 25 повторяется наего выходе 26. При перек 1 почении "1"в "0" йа входе 25 одновибратора 22последний запускается и на его Выходе имеет место "1", на выходе 26Формируется 0". При переключении"О" в "1" ца Входе 25 одновибратор22 запускается, На его выходе Формируется отрицательный импульс длительностью с , после Окончания которого на выходе 26 Формируется значение " 1 . Таким ОбОЯзом значение "1"ня Выходе устройства Формируется сзадержкой на регулируемое время 7в то время, хак значение "0" сразуже поступает на Выход. 2Перед началом решения в исходнойСЛАУ Ах=Ь осуществляется замена переменнойх = 2 - хгпа х5 где х - вектор компоненты которот" ахЭго положительные и не меньше максимального по модулю решения х. СЛАУАх = Ь, такой, что выполняются неравенства10 ОЫ =Ах +НЕ =А й,З.па хВ результате приходим к СЛАУ.вида АЕрешение которой неотрицательное, так какЕ = х +х О,КтохУказанное преобразование осуществляется, если компоненты матрицы А удовлетворяют условиямОа;1, а, (О, а,.)1 а,1 х ФВ этом случае значение х , должах 1 но удовлетворять неравенству где тах 11 Ь 1- наибольшая по модулюкомпонента вектора Ь.Из перавенств ч0(а (1, асО, а .ъ , а 1-1(АЕ - 1). На входы 12-17 задаютсясоответственно значения компонент55 (1-р а), ра рр, (1-рс,), р ЯрГ ,На вход 18 поступает сигнал пуска устройства, по которому запускается одновибратор 11, на выходе кото04 4Таким образом, в устройстве имеетместо вычислительный процесс, обеспечивающий монотонную сходимостьтпоследовательностиЕ 1) к решению2 СЛАУ вида А Г = Е,Сигнал готовности на выходе 21формируется следующим образом, Призапуске одновибратора 8 на его выходе формируется импульс, длительность которого не меньшая, чем максимальное время задержки информациив каждой строке от входа регистрадо выхода элемента сравнения. Призаписи любого последовательногоприближения в регистры 1 по сигналуот элемента сравнения одновременноповторно запускается одновибратор8, импульс на выходе которого длится до тех пор, пока в регистрах неустанавливается решение (повторныезапуски прекращаются и на выходе21 формируется единичный сигнал,указывающий на то, что решение найдено). Элемент НЕ 9 необходим длятого, чтобы блокировать сигнал готовности на время запуска одровибратора. После формирования сигналаготовности определяется решениех системы Ах = Ь по формуле х= 2 - х6 а ХУвеличение производительностиустройства обеспечивается в результате уменьшения интервала временимежду двумя последовательными заййсямиприближений в регистр за счет определения с помощью элементов сравнения моментов окончания формированиярезультатов,Формула и э обретения Устройство для решения систем линейных алгебраических уравнений, содержащее и регистров, матрицу и х и умножителей, и сумматоров, выход -го регистра (д=1,и) подключен к входу первого сомножителя умножителей д-го столбца матрицы, входы второго сомножителя умножителей матрицы подключены к входам задания коэффициентов уравнений устройства, выходы ;х (1=1 и) умножителей -й строки матрицы умножителей подключены к -м информационным входам д-го сумматора, (и+1)-е информационные входы сумматоров подключены к входам задания величин правых частей уравнений устройства, о т л и ч а ю щ е е с я тем, что, с целью увеличения произвоц 1(2 м Е с Е н 1 Р (АЕ ц 1) ) т т откуда 2 = А Г. Запись значения Е ("1)Е невозможна, так как ЕтЬ"=г - ). (Аг" -) = г3 1 2).рого формируется короткий отрицательный импульс, поступающий на К-входырегистров 1. В результате значенияна выходах регистров обнуляются,на выходах сумматоров 3 формируютсязначения 11., и рГ , которые .через1 1устройства приоритетного формирования нулей и элементы задержки поступают на Р-входы регистров 1 и по сигналу от элемента сравнения записываются в регистры. Таким образомустанавливаются значения компонентвектора начального приближения Е:рВ дальнейшем на выходе сумматора3.1 будет формироваться значениеЕ = 2 -р(а Е +а Е -Й ),1 1 11 1Ьа на выходе сумматора второй строки - значение20аВремя задержки включения 1 вь.-м (=1,2) устройстве приоритетного формирования нулей не меньше значенияО, = шах (о)11 Со 1)1, (10)1 (о 1)1 25где ). - наибольшее и наимень 1 Д 11 О 1)1шее время переключениязначения разрядов из11 О 11 11 О 11"1" на выходе умножителя -й строки )-гостолбца.Это обеспечивает формирование навыходе -го устройства приоритетногоформирования нулей значения у,1 35удовлетворяющего неравенствуу,2. - р (а Е +а Е - Е ),1 11 1 И 2 11= 1,2.Поступление информации с выходаустройств приоритетного формирования40нулей на 0-входы регистров через линии задержки исключает возможностьзаписи значений, которые меньше значений, хранимых регистрами, во времяотключения сигналов записи в регистр,45формируемых элементами сравнения.В последующие моменты времени ТТ Тн в силу изотонности отоб-,1ражения 2 - )11(АЕ-Г) в регистры будут записываться значения последовательных приближений50т т тЕ о ( Е 1 ( 2 о )Ч(АЕ О-)Е"2221 - /л(АЕ-Я)т т т т254504 Дцг,2ставитель В. Смирнохред И.Попович дактор И. Ка Корректор Е. Сирохма Заказ 472В 3/54 . Т НИИПИ Государствпо делам изобре 113035, Москва, Ж раж 671нного комитета СССРений и открытий35, Раушская наб., д. 4/5 одписно Производственно-полиграфическое предприяти е, г. жгород, ул. Проектная,У 3 1 дительности устройства, оно содержит и блоков приоритетного формирования нулей, и элементов задержки, и элементов сравнения, элемент ИЛИ, элемент И, элемент НЕ, первый и второй одновибраторы, выход -го сумматора подключен к информационному входу 1"го блока приоритетного формирования нулей, выход которого подключен к первому входу -го элемента сравнения и входу ь-го элемента задержки, второй вход -го элемента сравнения подключен к выходу -го регистра, выход -го элемента сравнения подключен к входу считывания -го регистра и к -му входу элемента ИЛИ, выход х-го элемента задержки подключен к информационному входу х-го регистра, выход элемента ИЛИ подключен к входу первого одновибратора и входу элемента НЕ, выходы первого одновибратора и элемента НЕ подключены соответственно к первому Ьи второму входам элемента И, выходкоторого подключен к выходу сигналаокончания рещения уравнения устройства, вход запуска устройства подключенк входу второго одновибратора, выход которого подключен к входам установки в "О" и регистров, выходыкоторых подключены к выходам результата устройства, при этом блок при оритетного формирования нулей содержит щ одновибраторов (ш - оазрядность устройства), в элементов И,(1 с=1т) разряда блока приори тетного формирования нулей подключенк информационному входу к-го одновибратора и входу к-го элемента задержки, выходы К-х одновибратораи элемента задержки подключены соот ветственно к первому и второму входам Е-го элемента И, выход которогоподключен к выходу 1-го разряда блока приоритетного формирования нулей.