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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСН ИХРЕСПУБЛИК А 2493( 06 Р 15/324 ОБРЕТЕНИЯТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ ПИСАНИЕ ИЗАВТОРСКОМУ СВИДЕ(71) Таганрогский радиотехнический инс титут им, В. Д. Калмыкова(56) 1, Авторское свидетельство СССР М 813445, кл. Й 06 Г 15/324, 1978 (54) (57) УСТРОЙСТВО ПЛЯ РЕШЕНИЯ СИСТЕМЫ АЛГЕБРАИЧЕСКИХ УРАВ НЕНИИ по авг. св. % 813445, о г л ич а ю ш е е с я тем, что, с цельюповышения быстродействия, в него введен третий блок памяти, управляюший вход кото. рого подключен к всходу блока управления, чнформационный вход - к выходу первого блока памяти, а выход - к третьему входу коммутатора, четвер 1 ый вход которого соединен с выходом второго блока памяти, инФормационный вход которого подключен к выходу второго регистра и инФормационному жоду первого блока памяти.(3) 1 102Изобреенме относится к цифровой вычислительной технике и может быть использовано при решении систем алгебраических уравнений итерационными методами.По основному авт. св. % 813445 известно устройство для решения системыалгебраических уравнений, содеркашее дваблока памяти, выход первого иэ которых через первый регистр подключен квходам блоков умножения, соединенныхдругими входами с выходом второго регистра, а выходами через буферныйрегистр с первым входом сумматора, подключенного выходом к накопителю, соединенному входом с выходом второго блока памяти, а выходом - с вторым, входомсумматора и входом второго регистра,подключенного равно как и другие блокиустройства управляюшим входом к выходу блока управления,Известное устройство предйазначенодля решения системы алгебраическихуравнений Р -го порядка методом итерации где 4 - матрица перехода от-й к1 -й итерации размером ИО;р - вектор неизвестньх;( - вектор правой части 1Недостатком известного устройстваявляется невозможность ускорения итерационного процесса за,счет предваритель ного преобразования исходной матрицыпереходе от 1 -й к +1-й итерации вматрицу перехода от К-й к К+р -йитереции ( 4).Цель изобретения - повышение быстродействияя.Поставленная цель достигается тем,что в устройство введен третий блок памяти, вход которого подключенк выходублоке памяти, а выход - к третьемувходу коммутатора, четвертый вход кото-,рого соединен с выходом второго блокапамяти, информационный вход которогоподключен к выходу второго регистра,соединенному с информационным входомпервого блока памяти,Введенные блок памяти и связи позволяют осуществить итерационный процессрешения системы алгебраических уравнений по формулеОГ,Формула (2) тождественна формуле(1), но позволяет эа счет предваритель- ного вычисления Р -й степени матрицы .А и нового вектора части Р исключить припри каждом вычислении очередного приближения к решению расчет (р) промежу+точных итераций, что асимптотически,т.е. для достаточно больших К, в (у разповышает быстродействие устройства.На фиг, 1 изображена структурнаясхема предлагаемого устройства; нана фиг. 2 -структурная схема блока управления; на фиг. 3 - структурная схема15модуля управления входом коммутатора;на фиг, 4 - структурная схема модуляуправления блоком памяти,Устройство содержит блок 1 управления, первый блок 2 памяти, первый регистр 3, И блоков 44 -4 умножения,20буферный регистр 5, сумматор 6, накопитель 7, второй блок 8 памяти, коммутатор 9, второй регистр 10, третийблок 11 памяти, вход 12 и выход 1325устройства.Блок 1 управления синхронизируети управляет работой всех блоков устройства,Первый блок 2 памяти служит длянакопления рй степени матрицы , эаЗ 0 писываемой по строкам, и имеет емкостьй слов,Первый регистр 3 предназначен дляхранения строки матрицы из блока 2 памяти и, соответственно, имеет число35 разрядов, необходимое для размещенияслов,Второй блок 8 памяти служит дляхранения элементов матрицы А, записанной по столбцам, а также вектора пра 40 вой части и вектора нулевой итерациирешения Оо и имеет емкость и (И+2)слов.Второй регистр 10 предназначен дляхранения столбца матрицы,из блока 745 или блока 8 до начала в устройстве итерационного процесса, на каждой К;й итерации которого в регистре 10 хранятся.компоненты вектора 0 п, Число разрядоврегистра 10 позволяет разместить в нем50 й слов.Блоки 4- 4,умножения служат дляодновременного умножения слов иэ регистра 3 на наслов из регистра 10.Буферный регистр 5 предназначен для55 хранения результатов перемножения и передачи их в сумматор 6, в котором суммируются полученные произведнния,Накопитель 7 имеет емкостьслови служит на каждой-й итерации рабо310249 ты.устройства дпя хранения компонент вектора правой части Г и последующего Гйакопления компонент вектора 0 ц, очередного прибпижения к решению.Коммутатор 9 предназначен дпя селек 5 ции подачи во второй регистр 10 той или иной информации в процессе работы устройства.Третий блок 11 памяти служит дпя накопления р -й степени матрицы " записываемой по столбцам, и имеет емкость и слов.Блок управления содержит генератор 14 тактовых импульсов, выход которого подключен к тактовым входам модулей 15 - 15 управления входом коммутатора и модулей 16- 16. управления блоком памяти. Выходы этих узлов являются выхопом 17 блока 1 управления, причем выход модуля 15; подключается в устройстве к 1 -му входу коммутатора 9, выход модуля 16; - к-му блоку памяти, выход генератора, 14 -ко всем блокам устройства.В блоке 1 управления модуль 15 предназначен для выдачи в соответствующем такте на коммутатор 9, выполненный, например, в виде схемы П И/ИЛИ сигна-. лов, открывающих (1) или запиравших (О) ( -й иэ его п входов.30Модуль 15 управления входом коммутатора содержит регистр 18, вход которого подключен к тактовому входу 19, а выход - к счетному входу триггера 20, единичное состояние выхода 21 которого соответствует открыванию входа коммута 35 тора 9. Программа его работы записывается в циклическом регистре 19 сдвига в виде последовательности нулей и единиц, по которым также происходит смена сос 10 тояния триггера 20 и переключение входа коммутатора 9.Модули 161 в блоке 1 управления предназначены для выдачи управляющих сигналов на соответствующие блоки памяти устройства. При реализации блоков45 памяти с помощью БИС ОЗУ необходимо обеспечить выдачу адреса логических сигналов режима (запись или чтение) и вт;бора кристалла, обеспечивающего доступ к.данному блоку памяти.50Модуль 161 управления блоком памяти, содержит регистр 22, выход которого через триггер 23 подключен к выходу 24 модуля 16, соединенному также с регистром 25 через триггер 26, выход 55 которого подключен к логическому элементу И 27, другой вход которого подключен к тактовому входу 28 модуля 16;, а 32 4выход - к входам блоков 29 и 30 магазинной памяти, выходы которых соединены с информационными. входами счетчиков 31 и 32 соответственно, выходы счетчика 32 подключены к логическому элементу ИЛИ 33, выход которого соединен с инверсным входом логического элемента И 27 и входом логического элементаИ 34, другой вход которого подключен к тактовому входу 28 модуля 16осоединенному также с регистрами 22 и 25, а выход - к управляющему входу счетчика 32 и счетчика 31, выход которого соединен с выхоаом 24 модуля 1,6, Регистры 22 и 25 являются циклическими регистрами сдвига и служат для хранения программы формирования с. помощью счетных триггеров 23 и 26 логических сигналов режима и выбора, кристалла, соответственно. При этом при появлении с выхода соответствующего регистра логической "1" соответствующий триггер меняет свое состояние и хранит его до появления следующей "1". Сигнал единичного состояния триггера 26, означающий, что кристалл данного блока памяти выбран, разрешает прохождение через элемент И 27 синхроимпульса с входа 28, который сдвигает информацию в блоках 29 и 30 магазин- ", ной памяти так, что с их выходов всчетчики 31 и 32 записывается сответствен-" но базовый адрес и количество ячеек памяти, для которых в зависимости от состояния триггера 23 осуществляется запись или чтение информации. В любом из разрядов счетчика 32 1" фиксируется элементом ИЛИ 33, с выхода которого в блоках 29 и 30, и открывает элемент И 34, через который проходят синхроимпупьсы, которые суммируются в счетчике 31, формируется тем самым текущий адрес, поступающий на выход 24, и вычитаются в счетчике 32, фиксируя момент окончания опроса заданного количества ячеек памяти, совпадающий с обнулением содержимого счетчика. 32, При этом на выходе элемента ИЛИ 33 появится логический "0", запрещающий прохождение через элемент И 34 синхроимпульсов на счетчики 31 и 32 и разрешающий прохождение синхроимпупьса через элемент И 27 на входы блоков 29 и 30 магазинной памяти, по которому на их выходах появляется новый базовый адрес и колцчесгво ячеек памяти, подлежащее опросу. Таким образом, необходимая программа работы для блоков памяти устройства хранится в регистрах10249 Ф22 и 25 и блоках 29 и 30 модуля управления блоком 16 памяти.Устройство работает следующим образом.По сигналу с блока 1 управленияЭ из первого блока 2 памяти в первый регистр 2 записывается первая строка матрицы А, а иэ второго блока памяти 8 в накопитель 7 поступают компоненты исходного вектора правой части (, . которые одновременно через открытый по четвертому входу сигналом с блока 1 управления коммутатор 9 поступают во второй регистр 10, после чего сигналом с блока 1 управления на управляющем входе коммутатора открывается его второй вход, по которому происходит пере , запись информации в регистр 10, Первая строка матрицыумножается вблоках 414 умножения на вектор (, получен 26 ные произведения поступают в буферный регистр 5, а затем на сумматор 6, где суммируется с поступающей на второй вход сумматора из накопителя. 7 первой компонентой. вектора правой частиу . На выходе сумматора 6 образуется при этом первая компонента вектора ( поступающая по открытому, управляющим сигналом первому входу в накопитель 7 взамен первой компоненты вектора Зй ( . Далее в первый регистр 3 из первого блока 2 памяти записывается вторая стро- . ка матрицы (, которая умножается в блоках 41 -4 и умножения на вектор.Я, поступающий из второго регистра, 35 10, и аналогично предыдущему образуется вторая компонента вектора+ ( ( поступающая в накопитель 7, в котором аналогичным образом накапливаются все 11 компонент вектора +ф . Затем по управляющему сигналу коммутатор 9 по своему пропускает информацию с выхода накопителя 7 во второй регистр 10, причем по второму входу накопителя 7 в нем восстанавливаются значения 4 ф вектора (, поступающие с выхода, второго блока 8 памяти. Далее аналогично предыдущему из первого блока 2 памяти в регистр 3 поступает первая строка матрицы А, которая с выхода регистра фф 3 приходит на первые входы блоков 4 - 4 умножения, на вторые входы которых с выхода регистра 10,поступают компоненты вектора ф + (, Полученные произведения .суммируются на суммато- И ре б с первой компонентой вектора ( и между собой, образуя первую компоненту векторафс -р, остальные компонен 32ты которого, вычисляются аналогично, после чего поступают через коммутатор 9 врегистр 10. Подобные вычисления повторяются в устройстве ( р .-1) раэ, послечего во втором регистре 10 получаетсясумма Ц).ду +. , которая в соответствии с формулой (3) является новым вектором правой части г,поступающим по управляющему сигналу свыхода регистра 10 во второй блок 8 памяти взамен вектора ,Далее работа устройства состоит вопределении р-й степени матрицыв соответствии с бинарным методом, которыйсостоит в возведении матрицы, являющейся степенью исходной матрицы . , в квадрат или в ее умножении на матрицу . .В частности, для нахождения матрицыбинарным методом (для Р = 7) устройствопоследовательно вычисляет ма трицы.-РИследующим образом. Поуправляющему сигналу с блока 1 управления открывается третий вход коммутато 1ра 9 и во второй регистр 10 с выходатретьего блока 11 памяти записывает-ся первый столбец матрицы А, а в первыйрегистр 3 с выхода блока 2 записываетсяпервая строка матрицы А. Информация свыходов регистров 3 и 10 поступает навходы блоков 4,(- 4 п умножения, с выхода которых полученные И произведенийчерез буферный регистр 5 поступают всумматор 6, с выхода которого полученная сумма записывается в накопитель 7в качестве первого элемента первой строки матрицы - .Затем без изменения информации в,регистре 3 с выхода третьго блока 11памяти через коммутатор 9 во второй1регистр 10 записывается второй столбецматрицы А и аналогично предыдущемуустройство вычисляет второй элементпервой строки матрицы., после вычисления всех И элементов которой по управляющему сигналу открывается первыйвход коммутатора 9 и через регистр 10первая строка матрицы . поступает в первый блок 2 памяти взамен первой строки матрицы А, с выхода которого в регистр 3 записывается вторая строка матрицы А и аналогично предыдущему умножается на столбцы матрицы А, поступающие в блоки 41- 4 п умножения из .третьего бпока 11 памяти через коммутатор9 и .второй регистр 10, При этом образуются И элементов второй строки магрицы., которые через коммутатор 9и регистр 10 по управляющему сигналу7 1024из блока 1 управления поступают в первый блок 2 памяти взамен второй строкиматрицы А.После вычисления в устройстве всехстрок матрицы А ее элементы по управ-.; ляюшему сигналу поступают с выходапервого блока 2 памяти в третий блок11 памяти. Далее устройство осушесгвляет перемножение строк матрицынастолбцы матрицы , которые поступают 10во второй регистр 10 путем подключенияк его выходу коммутатором 9 выхода второго блока 8 памяти, .а. не третьегоблока 11 памяти, как было в случае вычисления матрицы , аналогично .которо%вму теперь происходит вычисление магрицы , Далее точно так же, как вычисляаЯ)., При этом управляющим сигналом со-.ответственно.открыты третий и четвертый входы коммутатора 9 и через вгорой регистр на вторые входы блоков 41 -4умножения поступают соответственно Истолбцы матрицы 4из третьего блока.,11 памяти и сгобцы матрицы А иэ второго 8 блока памяти, а на первые аховы блоков4- 4 П через первый регистр.З из первого блока 2 памяти соответственно при- Заходят строки матрицы и затем строкиматрицы Аф,Следующий этап работы устройствасостоит в вычислении соответствукхцихприближений к решению по формуле (2).По сигналу с блока 1 управления откры-.вается четвертый вход коммутатора 9,через который во второй регистр 10 извторого блока 8 памяти поступает век-тор нулевой итерации решения Од . За-тем иэ блока 8 в накопитель 7 эвписывветсьвектор правой части Г, в в первый регистр 3 свыхода первого блока 2 памяти записываются в блок 41 - 4 и на соогветствуквциекомпоненты вектора Ц , поступающие с43выхода второго регистра 10, Полученныепроизведения поступают через буферныйрегистр 5 на первый вход сумматора 6,где суммируются с первой компонентнойвектора Г, поступающей на второй входсумматора 6 с выхода накопителя 7,932 8 взамен которой в накопитель 7 поступа- ет полученная сумма в качестве первой компоненты вектора р -й итерации решения 0, остальные (И -1) компонент которого получаются аналогично. Далее по управляющему сигналу открывается первый вход коммутатора 9 и вектор Ор поступает во.второй регистр 10 из накопителя 7, в который одновременно с выхода второго блока 8 памяти вновь записывается вектор правой частии работа устройства повторяется аналогично предыдущему ( б/р )-1 раз, где 5 - необходимое для решения системы алгебраических уровнений число итераций. При этом последовательно вычисляются векторы 0 р, ц,; Н,.еалиэацию предлагаемого устройства можно осуществить на основе микросхемы серии Е 155.Введение в устройство третьего блока памяти, подключенного к первому блоку памяти и коммутатору 9, и соединенные выхода второго регистра 10 с информационными входами первого 2 и второго 8 блоков памяти позволяет сушесгвенно повысить быстродействие за счет вычисления решения по формуле (2), на каждом шаге реализации которой исключается по сравнению с формулой (1), выполняемой известным устройством, расчет (р)промежуточных итераций, что и определяет экономический эффект устройства. В частности, при р =2 требуется одно умножение матрицы на вектор для нахождения вектора правой части Г: ц + (, составляющее И последовательных умножений с помощью блоков 4 - 4 и, умножение матрицы на матрицу, составляющее й умножений и 5/2 умножений магри 2цы т на вектор 0 для вычисления б -го2приближения к решению, состввлякзцих Я/й умножений. В известном устройстве требуется 5 умножений матрицы А на вектор И . Следовательно, при порядке системы алгебраических уравнений И 5 и числе итераций б = 100 в известном устройстве требуется бп = 500 умножений, а в предлагаемом . - ( - + И+ 1 ) й =б2=280 умножений;, что вполне характеризует выигрыш в быстродействии.Составитель И, Пчелиниевдактор Г. Безвершеико Техред С Мигунова Корректор В, Гирняаказ 4397/46 Тираж 706 П однисное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская набд. 4/5 лиал ЛПП "Патент", , Ужгород, ул. Проектная, 4