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

Изофе- еште относится к цифровой вычиспигепьной технике и может быть пользовано при решении систем алгебраических уравнений итерационными метода ми. По основному авт. св. fe 813445 известно устройство для решения системы алгебраических уравнений, содержащее дв блока памяти, выход первого из которых через первый регистр подключен к входам блоков умножения, соединенных другими входами с выходом второго регистра, а выходами через бз ерный регистр с первым входом сумматора, под ключенного выходом к накопителю, соединенному входом с выходом второго бло ка памяти, а выходом - с вторым .входом сумматора и входом второго регистра, подключенного равно как и другие блоки устройства управляющим входом к выходу блока управления. Известное устройство предназначено для решения системы алгебраических уравнений п -го порядка методом итерацииU..,--4UK(, К+Н - ts - . где -4 - матрица перехода от k -и к k- 1 -и итерации размером и П ; 11 - векгор неизвестных; tp - вектор правой части l . Недостатком известного устро тва является невозможность ускорения итера ционного процесса за.счет предварительного прео азования исходной матрицы перехода от k -и к k -И-й итерации в матрицу, перехода от k-и к К+р -иитера ции Р д). Цель изобретения - повьшгение быстро действия. Поставленная цель достигается тем, что в устройство введен третий блок памяти, вход которого подключен к выходу блока памяти , а выход - к третьему входу коммутатора, четвертый вход которого соединен с выходом второго блока памяти, информационный вход которого подключен к выходу второго регистра, соединенному с информационным входом первого блока памяти. Введенные блок памяти и связи позво ют осуществить итерационный процесс решения системы алгебраических уравне НИИ по формуле . K.p-- Uu4r, F r -f (2) (3) Формула (2) тождественна формуле (1), но позволяет за счет предварительь ного вычисления Р -и степени матрицы Аи нового векторИ части F исключить при при каждом вычислении очередного приближения к решению расчет (р-1) промежу точных итераций, что асимптотически, т.е. для достаточно больших К, в Cf раз повышает быстродействие устройства. На фиг, 1 изображена структурная схема предлагаемого устройства; на на фиг. 2 -структурная схема блока управления; на фиг. 3 - структурная схема модуля управления входом коммутатора; на фиг. 4 - структурная схема модуля управления блоком памяти. Устройство содержит блок 1 управления, первый блок 2 памяти, первый регистр 3, tl блоков 4 -4| умножения, буферный регистр 5, сумматор 6, накопитель 7, второй блок 8 памяти, коммутатор 9, второй регистр Ю, третий блок 11 памяти, вкод 12 и выход 13 устройства. Блок 1 управления синхронизирует и управляет работой всех блоков устройства. Первый блок 2 памяти служит для накслления р -и степени матрицы Ч , записываемой по строкам, и имеет емкость . Первый регистр 3 предназначен для хранения строки матрицы из блока 2 памяти и, соответственно, имеет число разрядов, необходимое для размешения слов. : Второй блок 8 памяти служит для хранения элементов матрицы А, записанной по столбцам, а также вектора пра вой части и вектора нулевой итерации решения UQ и имеет емкость П (И +2) слов. Второй регистр 10 предназначен для хранения столбца матрицы из блока 7 ann блока 8 до начала в устройстве итерационного процесса, на каждой k-й итерации которого в регистре 10 хранятся компоненты вектора Uf,. Число разрядов регистра 10 позволяет разместить в нем И слов. Блоки 4 .J - 4(умножения служат для одновременного умножения слов из регистра 3 на на h слов из регистра 10. Буферный регистр 5 предназначен для хранения результатов перемножения и их в сумматор б, в котором суммируются полученные произведнния. Накопитель 7 имеет емкость слов и служит на каждой k -и итерации рабо3102ты .устройства для хранения компонент вектора правой части F и послед5 кщего Гнакотпения компонент вектора U ц+рочередного приближения к решению. KoMKiyraTop 9 предназначен для селекции подачи во второй регистр Ю той или иной информации в процессе работы устройства. Третий блок 11 памяти служит для накопления р -и степени матрицы - , записываемой по столбцам, и -имеет емкость Послов. Блок управления содержит генератор 14 тактовых импульсов, выход которого подключен к тактовым входам модулей 15 - 155 управления входом коммутатора и модулей 16;| - 16.з управления блоком памяти. Выходы этих узлов являются выхоаом 17 блока 1 управления причем выход модуля 15 подключается в устройстве к -му входу коммутатора 9, выход модуля 16 - к ч -му блоку памяти, выход генератора, 14 -ко всем блокам устройства. В блоке 1 управления модуль 15 пред назначен для выдачи в соответствующем такте на коммутатор 9, вьшолненный, например, в виде схемы И И/ИЛИ сигна-. лов, открывающих () или запирающих (О) 1 -и из его п входов. Модуль 15 управления входом ком мутатора содержит регистр 18, вход кото рого подключен к тактовому входу 19, а выход - к счетному входу триггера 20, единичное состояние выхода 21 которого соответствует открьтанию входа коммутатора 9. Программа его работы записывае ся в циклическом регистре 19 сдвига в виде последовательности нулей и единиц, по которым также происходит смена состояния триггера 20 и переключение входа коммутатора 9. Модули 16 i в блоке 1 управления предназначены для вьздачи управляющих сигналов на соответствующие блоки памяти устройства. При реализации блоков памяти с помощью БИС ОЗУ необходимо обеспечить выдачу адреса логических сиг налов режима (запись или чтение) и вттбо ра кристалла,, обеспечивающего доступ к -данному блоку памяти. Модуль 16 управления блоком памяти, содержит регистр 22, выход которого через и триггер 23 подключен к выходу 24 модуля 16, соединенному также с регистром 25 через триггер 26, выход которого подключен к логическому элемен ту И 27, другой вход которого подключен к тактовому входу 28 модуля 16, , а 24 выход - к входам блоков 29 и 30 магаэинной памяти, выходы которых соединены с информационными входами счетчиков 31 и 32 соответственно, выходы счетчика 32 подключены к логическому элементу ИЛИ 33, выход которого соединен с инверсным входом логического элемента И 27 и входом логического элемента ( И 34, другой вход которого подключен к тактовому входу 28 модулей 16/ , соединенному также с регистрами 22 и 25, а выход - к управляющему входу счетчика 32 и счетчика 31, выход которого соецинен с выхоаом 24 модуля 16 . Регистры 22 и 25 являются циклическими регистрами сдвига и служат для хранения программы формирования с. помощью счетных триггеров 23 и 26 логическюс сигналов режима и выбора, кристалла, соответственно. При этом при появлении с выхода соответствующего регистра логической 1 соответствующий триггер меняет свое состояние и хранит его до появления следующей I. Сигнал единичного состояния триггера 26, означакшхий, что кристалл данногх блока памяти выбран; разрешает прохождение через элемент И 27 синхроимпульса с входа 28, который сдвигает информацию в блоках 29 и 30 магазин- ; ной памяти так,что сих выходоввсчетчики 31 и 32 записывается сответственно базовый адрес и количество ячеек памяти, для которых в зависимости от состояния триггера 23 осуществляется запись или чтение информации. В любом из разрядов счетчика 32 1 фиксируется элементом ИЛИ 33, с выхода которого в блоках 29 и ЗО, и открывает элемент И 34, через который проходят синхроимпульсы, которые сумьлируются в счетчике 31, формируется тем самым текущий адрес, поступающий на выход 24, и вычитаются в счетчике 32, фиксируя момент окончания опроса заданного количества ячеек памяти, совпадающий с обнулением содержимого счетчика. 32. При этом на выходе элемента ИЛИ 33 появится логический О, запрещающий прохождение через элемент И 34 синхроимпульсов на счетчики 31 и 32 и разрешающий прохождение синхроимпульса через элемент Н 27 на входы блоков 29 и 30 магазинной памяти, по которому на ИХ выходах появляется новый базовый адрес и копичесгво ячеек памяти, подлежащее опросу. Таким образом, необxoдJiмaя программа работы для блоков памяти устройства хранится в регистрах 22 V 25 К блоках 29 и ЗО модуля управления блоком 16 памяти. Устройство работает следукицим образом. По сигналу с блока 1 управления из первого блока 2 памяти в первый регистр 2 записывается первая строка матрицы А, а из второго блока памяти 8в накопитель 7 поступают компоненты исходного вектора правой части f, . которые одновременно через от1фытый по четвертому входу сигналом с блока 1 управления коммутатор 9 поступают во второй регистр 10, после чего сигналом с блока 1 управления на управляющем входе коммутатора открьшается его вто- рой вход, по которому происходит hepeзапись информации в регистр 10. Первая строка матрицы умножается в П блоках 4 - 4 умножения на вектор (f , получен ные произведения поступают в буферный регистр 5, а затем на сумматор 6, где суммируется с поступающей на второй . вход сумматора из накопителя 7 первой компонентой, вектора правой части(Р. На выходе сумматора 6 образуется при этом первая компонента вектора Cj) f ф, поступающая по открытому . управлякяцим сигналом первому входу а накопитель 7 взамен первой компоненты вектора (f . в первый регистр 3 из первог блока 2 памяти записывается вторая стр ка матрицы , которая умножается в блоках 4, - 4 умножения на вектор .(р , поступающий из второго регистра , J- 10, и аналогично предыдущему образуется вторая компонента вектора tf t ф , поступающая в накопитель 7, в котором аналогичным образом накапливаются все И компонент вектора (() + of ф . Затем по управлякшему сигналу коммутатор 9по своему пропускает информацию с выхода накопителя 7 во второй регистр 10, причем по второму входу накопителя 7 в нем восстанавливаются значения вектора С| , поступающие с выхода, второго блока 8 памяти. Далее аналогично пре дыдущему из первого блока 2 памяти в регистр 3 поступает первая строка матрицы А, которая с выхода регистра 3приходит на первью вдсоды блоков 4 4 углножения, на вторые входы которых с выхода регистра 10 .поступают компоненты вектора ( (/- Полученные произведения суммируются на сумматоре б с первой компонентой вектора ср и между собой, образуя первую компоненту BeKTopaq) 4- tp , остальные компонен ТЫ которого вычисляются аналогично, после чего поступают через коммутатор 9 в регистр 10. Подобные вычисления повторяются в устройстве ( р -1) раз, после чего во втором регистре 10 получается сумма (ft-jfcpf-f tp-t- jf f , кото-т рая в соответствии с формулой (3) является новым вектором правой части F , поступакяцим по управляющему сигналу с выхода регистра 10 во второй блок 8 памяти взамен вектора ( . Далее работа устройства состоит в определении р -и степени матрицы jf в соЪтветствии с бинарным методам, который состоит в возведении матрицьг, являющейся степеныр исходной матрицы. , в квадрат или в ее умножении на матрицу . 8частности, для нахождения матрицы бинарным методом (для Р 7) устройство последовательно вычисляет матрицы- , И -f следуияцим образом. По ;. управляющему сигналу с блока1 управления открывается -третий вход коммутатора 9 и во второй регистр 10с выхода третьего блока 11 памяти записывается первый столбец матрицы А, а в первый регистр 3 с выхода блока 2 записывается первая строка матрицы А. Информация с выходов регистров 3 и 10 поступает на входы блоков 4( умножения, с выхода которых полученные И произведений через буферный регистр 5 поступают в сумматор 6, с выхода которого полученная сумма записывается в накопитель 7 в качестве перй.ого элемента первой строки матрицы jf . Затем без изменения информации в, регистре 3 с выхода третьго блока 11 памяти через коммутатор 9 во второй регистр 10 записывается второй столбец матрицы А и аналогично предыдущему устройство вычисляет второй элемент первой строки матрицыjf, после вычисления всех И элементов которой по управлякапему сигналу открь1вается первый вход коммутатора 9 и через регистр 10 первая строка матриш 1 jf поступает в первый блок 2 памяти взамен первой строки матрицы А, с выхода которого в регистр 3 записывается вторая строка матрицы А и аналогично предыдущему умножается «а столбцы матрицы А, поступающие в блоки 4 р 4 умножения из третьего блока 11 памяти через коммутатор 9и .второй регистр 10. При этом образуются И элементов второй строки матрицы - , которые через коммутатор 9 и регистр 1О по управляющему сигналу из блока 1 управления поступают в первый блок 2 памяти взамен второй строки матрицы А. После вычисления в устройстве всех строк матрицы А ее элементы по управ 5 ляюшему сигналу поступают с выхода первого блока 2 памяти в третий блок 11 памяти. Далее устройство осушест- вляет перемножение строк матрицы . на столбцы матрицы , которые поступают во второй регистр 10 путем подключения к его выходу коммутатором 9 выхода вто рого блока 8 памяти, .а не третьего блока 11 памяти, как было в случае вычисления матрицы , аналогично .которому теперь происходит вычисление матрицы f. Далее точно так же, как вычисля.ются вторая и третья степени матрииыл( , устройство вычисляет соответственно шес ,тую и седьмую степени ( матрицы и jf7).. При этом управлякяиим сигналом соответственно открыты третий и четвертый входы коммутатора 9 и чеоез второй регистр на вторые входы блоков 4 -4 ; умножения поступают соответственно столбцы матрицы из третьего блока ,11 памяти и стобцЫ матрицы А из второ го 8блока памяти, а на первые входы блоков 4 ,| - 4ц через первый регистр 3 из пер вого блока 2 памяти соответственно приходят строки матрицы и затем строки матрицы А . Следующий этап работы устройства состоит в вычислении соответствующих приближений к рещению по формуле (2). По сигналу с блока 1 управления открывается четвертый вход коммутатора 9, через который во второй регистр Ю из Второго блока 8 памяти поступает век.тор нулевой итерации рещения ичэ .Затем иэ блока 8 в накопитель 7 записываетс вектор правой части Г, а в первый регистр 3 выхода первого блока 2 памяти записываю ся в блок 4 - 4 на соответствукшие компоненты вектора Цд , поступающие с выхода второго регистра 10, Полученные про.изведения поступают через бу|; 1ерный регистр 5 на первый вход сумматора 6, где суммируются с первой компонентной вектора F , поступакяцей на торой вход сумматора 6 с выхода накопителя 7, взамен которой в накопитель 7 поступает полученная сумма в качестве первой компоненты вектора р -и итерации рещения Up, остальные (ц -1) компонент которого получаются аналогично. Далее по управляющему сигналу открывается первый вход коммутатора 9 и вектор Up поступает во .второй регистр 10 из накопителя 7, в который одновременно с выхода второго блока 8 памяти вновь записывается вектор правой части Р и работа устройства повторяется аналогично предыдущему ( S / р )-1 раз, где 5 - необходимое для рещения системы алгебраических уровнений число итераций. При этом последовательно вычисляются векторы Ujn U-jp,.,., . Реализацию предлагаемого устройства можно осуществить на основе микросхемы серии К155. Введение в устройство третьего блока памяти, подключенного к первому блоку памяти и коммутатору 9, и соединенные вькода второго регистра 10 с информационными входами первого 2 и второго 8 блоков памяти позволяет существенно повысить быстродействие за счет вычисления рещения по формуле (2), на каждом щаге реализации которой исключается по сравнению с формулой (1), выполняемой известным устройством, расчет (р-1) промежуточных итераций, что и определяет экономический эффект устройства. В частности, при р 2 требуется одно умножение матрицы на вектор для нахождения вектора правой части F Cf Ц, составляющее Л последовательных умножений с помощью блоков 4 j - 4 п. умножение матриць на матрицу, составлзяющее П умножений и 5/2 ут гножений матрицы на вектор U для вычисления S -го приближения к рещению, составлякацих Sn/i умножений. В известном устройстве требуется 5 умножений матрицы А на вектор л . Следовательно, при порядке системы алгебраических уравнений h 5 и числе итераций S ЮО в известном устройстве требуется S,, 500 умножений, «а в предлагаемом - (у+п + ( )tt 28О умножений,,что вполне характеризует выигрьш в быстродействии.

УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМЫ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ по авт. св. № 813445. о т л и чающееся тем, что, с целью повь шения быстродействия, в него введен третий блок памяти, управляющий вход которого подключен к всдходу блока управления, информационный вход - к выходу первого блока памяти, а выход - к третьему входу коммутатора, четвертый вход Kiaroporo соединен с выходом второго блока памяти, информационный вход которого подключен к выходу второго регистра и информационному входу первого блока памяти. Ю Ф 00 ьэ