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

 

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

„„SU„„1.024932

СОЮЗ COBETCHHX

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

Q 06 F 15/324

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (61). 813445 (21) 33992 53/18-24 (22) 22.02.82 (46) 23.06.83. Бюл. No 23 (72) Б. Г. Фрадкин. (71) Таганрогский радиотехнический инс-. титут им. В. Д. Калмыкова (53) 681.3 (088.8) (56) 1. Авторское свидетельство СССР

K 813445, кл. Ci 06 F 15/324, 1978.. (54) (57) УСТРОЙСТВО ПЛЯ РЕШЕНИЯ СИСТЕМЫ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ по авг. св. % 813445, о г л ич а ю ш е е с я тем, что, с цельюповышения быстродействия, в него введен грегий блок памяти, управлякзций вход которого подключен к мяходу блока управления, чнформационный tacoma - к выходу первого блока памяти, а выход - к третьему входу коммутатора, четвер1 ый вход которого соединен с выходом второго блока памяти, информационный вход которого подключен к выходу второго регистра и информационному жоду первого блока памяти.

4932

= О„Ч (2) Р 4 р - г к=0 (3) 1 102

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

По основному авт. св. % 813445 известно устройство для решения системы алгебраических уравнений, содержащее два блока памяти, выход первого иэ которых через первый регистр подключен к входам блоков умножения, соединенных другими входами с выходом второго регистра, а вьводами через буферный регистр с первым входом сумматора, подключенного выходом к накопителю, соединенному входом с выходом второго блока памяти, а выходом - с вторым, входом сумматора и входом второго регистра, подключенного равно как и другие блоки устройства управляющим входом к выхо« ду блока управления.

Известное устройство предйазначено для решения системы алгебраических уравнений Р -го порядка методом итерации где "(— матрица перехода от k - и к

k+) -й итерации размером vl ° Fl; р — вектор неизвестных; (p — вектор правой части (11

Недостатком известного устройства является невозможность ускорения итерационного процесса за.счет предваритель-ного преобразования исходной матрицы перехода or k -й к +1-й итерации в матрицу перехода от k -й к К+р -йщера ции (P> q), Uemü изобретения — повышение быстродействияя.

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

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

uê,ð=1 0„ F, Формула (2) тождественна формуле (1), но позволяет эа счет предварительного вычисления Р -й степени матрицы .

А и нового вектора части F исключить при при каждом вычислении очередного приближения к решению расчет (р-1) промежу+ точных итераций, что асимптотически, т.е. для достаточно больших К, в (р раз повышает быстродействие устройства.

На фиг. 1 изображена структурная схема предлагаемого устройства; на на фиг. 2 -структурная схема блока управления; на фиг. 3 — структурная схема

15 модуля управления входом коммутатора; на фиг. 4 - структурная схема модуля управления блоком памяти.

Устройство содержит блок 1 управления, первый блок 2 памяти, первый регистр 3, fl блоков 4 -4, умножения, 20 буферный регистр 5, сумматор 6, накопитель 7, второй блок 8 памяти, коммутатор 9, второй регистр 10, третий блок 11 памяти, вход 12 и выход 13

25 устройства.

Блок 1 управления синхронизирует и управляет работой всех блоков устройства.

Первый блок 2 памяти служит для накопления Р»й степени матрицы (, эа0 писываемой по строкам, и имеет емкость

fl слов, Первый регистр 3 предназначен для хранения строки матрицы из блока 2 памяти и, соответственно, имеет число

35 разрядов, необходимое для размещения слов.

Второй блок 8 памяти служит для хранения элементов матрицы А, записанной по столбцам, а также вектора пра40 вой части и вектора нулевой итерации решения Uo и имеет емкость и (0+2) слов.

Второй регистр 10 предназначен для хранения столбца матрицы.из блока 7

45 или блока 8 до начала в устройстве итерационного процесса, на каждой k.-й итера-. ции которого в регистре 10 хранятся .компоненты вектора Ол, Число разрядов регистра 10 позволяет разместить в нем

50 и слов °

Блоки 4 < - 4,умножения сл жат для одновременного умножения слов иэ регистр ра 3 на на g слов из регистра 10.

Буферный регистр 5 предназначен для

55 хранения результатов перемножения и передачи их в сумматор 6, в котором суммируются полученные произведнния.

Наклпитель 7 имеет емкость q слов и служит на каждой t, -й итерации рабо3 10249 ты устройства дпя хранения компонент вектора правой части F и послед ращего йакопления компонент вектора0ц, очередного прибпижения к решению.

Коммутатор 9 предназначен дпя селек5 цни подачи во второй регистр 10 той или иной информации B процессе работы устройства.

Третий блок 11 памяти служит для накопления р -й степени матрицы записываемой по столбцам, и имеет емкость 0 слов.

Блок управления содержит генератор

14 тактовых импульсов, выход которого подключен к тактовым входам модулей

15 - 15 управления входом коммутатора и модулей 16 — 16.g управле ния блоком памяти. Выходы этих узлов являются выхоцом 17 блока 1 управления, причем выход модуля 15; подключается в устройстве к 1 -му входу коммутатора

9, выход модуля 16; — к -му блоку памяти, выход генератора. 14 -ко всем блокам устройства.

В блоке 1 управления модуль 15 пред- 5 назначен для выдачи в соответствующем такте на коммутатор 9, выполненный, например, в виде схемы П И/ИЛИ сигна-. лов, открывающих (1) или запирающих (О) (-й иэ его п входов.

Модуль 15 управления входом коммутатора содержит регистр 18, вход которого подключен к тактовому входу 19, а выход - к счетному входу триггера 20, единичное состояние выхода 21 которого соответствует открыванию входа коммута35 тора 9. Программа его работы записывается в циклическом регистре 19 сдвига в виде последовательности нулей и единиц, по которым также происходит смена сос40 тояния триггера 20 и переключение входа коммутатора 9.

Модули 161 в блоке 1 управления предназначены для выдачи управляющих сигналов на соответствующие блоки памяти устройства. При реализации блоков

45 памяти с помощью БИС ОЗУ необходимо обеспечить выдачу адреса логических сигналов режима (запись или чтение) и в ;бора кристалла, обеспечивающего доступ к .-данному блоку памяти.

Модуль 161 управления блоком памяти, содержит регистр 22, выход которого через триггер 23 подключен к выходу

24 модуля 16, соединенному также с регистром 25 через триггер 26, выход которого подключен к логическому элементу И 27, другой вход которого подключен к тактовому входу 28 модуля 16;, а

32 4 выход - к входам блоков 29 и 30 магазинной памяти, выходы которых соединены с информационными. входами счетчиков 31 и 32 соответственно, выходы счетчика 32 подключены к логическому элементу

ИЛИ 33, выход которого соединен с инверсным входом логического элемента

И 27 и входом логического элемента

И 34, другой вход которого подключен к тактовому входу 28 модуля 16 о соединенному также с регистрами 22 и

25, а выход - к управляющему входу счетчика 32 и счетчика 31, выход которого соепинен с выхоцом 24 модуля

Х,6 . Регистры 22 и 25 являются циклическими регистрами сдвига и служат для хранения программы формирования с. помощью счетных триггеров 23 и 26 логических сигналов режима и выбора. кристалла, соответственно. При этом при появлении с выхода соответствующего регистра логической "1" соответствующий триггер меняет свое состояние и хранит его до появления следукицей

"1". Сигнал единичного состояния триггера 26, означающий, что кристалл данного блока памяти выбран; разрешает прохождение через элемент И 27 синхроимпульса с входа 28, который сдвигает информацию в блоках 29 и 30 магазин- ", ной памяти так, что с их выходов всчетчики 31 и 32 записывается сответственно базовый адрес и количество ячеек памяти, для которых в зависимости от состояния триггера 23 осуществляется запись или чтение информации. В любом из разрядов счетчика 32 1" фиксируется элементом ИЛИ 33, с выхода которого в блоках 29 и 30, и открывает элемент И 34, через который проходят синхроимпупьсы, которые суммируются в счетчике 31, формируется reM самым текущий адрес, поступающий на выход

24, и вычитаются в счетчике 32, фиксируя момент окончания опроса заданного количества ячеек памяти, совпадающий с обнулением содержимого счетчика. 32.

При этом на выходе элемента ИЛИ 33 появится логический "0 ", запрещающий прохождение- через элемент И 34 синхроимпульсов на счетчики 31 и 32 и раэрешаюший прохождение синхроимпупьса через элемент И 27 на входы блоков

29 и 30 магазинной памяти, по которому на их выходах появляется новый базовый адрес и количество ячеек памяти, подлежащее опросу. Таким образом, необходимая программа работы для блоков памяти устройства хранится в регистрах

10249

Ф

22 и 25 и блоках 29 и 30 модуля управления блоком 16 памяти.

Устройство работает следующим образом.

По сигналу с блока 1 управления

Э из первого блока 2 памяти в первый регистр 2 записывается первая строка матрицы А, а иэ второго блока памяти

8 в накопитель 7 поступают компоненты исходного вектора правой части (p, . которые одновременно через открытый по четвертому входу сигналом с блока

1 управления коммутатор 9 поступают во второй регистр 10, после чего сигналом с бпока 1 управления на управляющем входе коммутатора открывается его второй вход, по которому происходит hepe«, запись информации в регистр 10. Первая строка матрицы g умножается в П блоках

41 4„умножения на вектор g, получен20 ные произведения поступают в буферный регистр 5, а затем на сумматор 6, где суммируегся с поступающей на второй вход сумматора из накопителя 7 первой компопе вектора правой части< . На выходе сумматора 6 образуется при этом первая компонента вектора (+ (p, поступающая по открытому . управляющим сигналом первому входу в накопитель

7 взамен первой компоненты вектора 3© (p . Далее в первый регистр 3 из первого блока 2 памяти записывается вторая стро-. ка матрицы -(-, которая умножается в блоках 41 -. 4п умножения на вектор .(, поступающий из второго регистра, 35

10, и аналогично предыдущему образуется вторая компонента вектора q + g (p поступающая в накопитель 7, в котором аналогичным образом накапливаются все

П компонент вектора((> + g (p . Затем

° по управляющему сигналу коммутатор

9 по своему пропускает информацию с вь1хода накопителя 7 во второй регистр

10, причем по второму входу накопителя 7 в нем восстанавливаются значения вектора (, поступающие с выхода.второго блока 8 памяти. Далее аналогично предыдущему из первогo блока 2 памяти в регистр 3 поступает первая строка матрицы А, которая с выхода регистра

3 приходит на первые входы блоков 4 —

4 „умножения, на вторые входы которых с выхода регистра 10,поступают компоненты вектора g + g. Полученные произведения .суммируются на суммато- И ре 6 с первой компонентой вектора (p и между собой, образуя первую компоненту вектора(аф су а (p, остальные компонен1

32 гы которого, вычисляются аналогично, после чего поступают через коммутатор 9 в регистр 10. Подобные вычисления повторяются в устройстве (р .-1) раэ, после чего во вгором регистре 10 получается сумма Ц) + f(g y g y + f P : q, кот рая в соответствии с формулой (3) является новым вектором правой части F поступающим по управляющему сигналу с выхода регистра 10 во второй блок 8 памяти взамен вектора q .

Далее работа устройства cocronr в . определении р-й степени матрицы в со ответствии с бинарным методом, когорый состоит в возведении матрицы, являющейся степенью исходной матрицы, в квадрат или в ее умножении на матрицу .

В частности, для нахождения матрицы бинарным методом (для P 7) устройство последовательно вычисляег ма грицы -, -.Р следующим образом. По „ управляющему сигналу с блока 1 управления открывается третий вход коммугаго1 ра 9 и so второй регистр 10 с выхода третьего блока 11 памяти записывает- ся первый столбец матрицы А, а в первый регистр 3 с выхода блока 2 записывается первая строка матрицы А. Информация с выходов регистров 3 и 10 поступает на входы блоков 4 - 4п умножения, с выхода которых полученные И произведений через буферный регистр 5 поступают в сумматор 6, с выхода которого полученная сумма записывается в накопитель 7 в качестве первого элемента первой строки матрицы -. .

Затем без изменения информации в, регистре 3 с выхода третьго блока 11 памяти через коммутатор 9 во второй

I регистр 10 записывается второй столбец матрицы А и аналогично предыдущему устройство вычисляет второй элемент первой строки матрицы, после вычисления всех И элементов которой по управляющему сигналу открывается первый вход KoMMyTaropa 9 и через регистр 10 первая строка матрицы поступает в первый блок 2 памяти взамен первой строки матрицы А, с выхода которого в регистр 3 записывается вторая строка матрицы А и аналогично предыдущему умножаегся .на столбцы матрицы А, поступающие в блоки 4-1- 4п умножения из .третьего бпока 11 памяти через коммугагор

9 и .второй регистр 10, flpm этом образуются И элементов второй строки магрицы, которые через коммутатор 9 и регистр 10 по управляющему сигналу

7 1024 из блока 1 управления поступают в первый блок 2 памяти взамен второй строки матрицы А.

После вычисления в устройстве всех строк матрицы А ее элементы по управ-$ .; ляющему сигналу поступают с выхода первого блока 2 памяти в третий блок

11 памяти. Далее устройство осушесг вляет перемножение строк матрицы . на столбцы матрицы g, которые поступают 10 во второй регистр 10 путем подключения к его выходу коммутатором 9 выхода второго блока 8 памяти, .а не третьего блока 11 памяти, как было в случае вычисления матрицы, аналогично .которо- iS п2 му теперь происходит вычисление магрицы . Далее точно так же, как вычисля 9 .ются вторая и третья степени матрицы., устройство вычисляет соответственно шес.тую и сеаьмую степени (матрицы:(и 20 ).. При этом управляющим сигналом со-. ответственно.открыты третий и четвертый входы коммутатора 9 и через вгорой регистр на вторые входы блоков 41 -4„ умножения поступают соответственно столбцы матрицы 4 из третьего блока .,11 памяти и сгобцы матрицы А иэ второго 8блока памяти, а на первые exoabr блоков 4 - 4п через первый регистр.З из первого бпока 2 памяти соответственно при- 3О ходят строки матрицы и затем строки матрицы А-6 .

Следующий этап. работы устройства состоит в вычислении соответствукхцих приближений к решению по формуле (2).

По сигналу с блока 1 управления DFKpbl-. вается четвертый вход коммутатора 9, через который во второй регистр 10 из

Йторого блока 8 памяти поступает век- тор нулевой итерации решения U.o . Затем иэ блока Be накопитель 7 эаписываетс вектор правой части Г, а в первый регистр 3 с выхода первого блока 2 памяти записывают ся в блок 41 — 4 < на соогветствукицие компоненты вектора Цо, поступающие с

4S выхода второго регистра 10. Полученные произведения поступают через буферный регистр 5 на первый вход сумматора 6, где суммируются с первой компонентной вектора F, поступающей на второй вход сумматора 6 с выхода накопителя 7, 932 8 взамен которой в накопитель 7 поступа- ет полученная сумма в качестве первой компоненты вектора р -й итерации решения Up, остальные (д -1) компонент которого получаются аналогично. Далее по управляющему сигналу открывается первый вход коммутатора 9 и вектор Up поступает во.второй регистр 10 из накопителя

7, в который одновременно с выхода второго блока 8 памяти вновь записывается вектор правой части и работа устройства повторяется аналогично предыдущему (б / р )-1 раз, где 5 — необходимое для решения системы алгебраических уровнений число итераций. При этом последовательно вычисляются векторы 0 happ ц,,...; и . еалиэацию предлагаемого. устройства можно осуществить на основе микросхемы серии К155.

Введение в устройство третьего блока памяти, подключенного к первому блоку памяти и коммутатору 9, и соединенные выхода второго регистра 10 с информационными входами первого 2 и второго

8 блоков памяти позволяет существенно повысить быстродействие за счет вычисления решения по формуле (2), на каждом шаге реализации которой исключается по сравнению с формулой (1), выполняемой известным устройством, расчет (p-1) промежуточных итераций, что и определяет экономический эффект устройства.

В частности, при p =2 требуется одно умножение матрицы на вектор для нахождения вектора правой части F = q + (, составляющее и п оследовательных умножений с помощью блоков 4 - 4 и, умножение матрицы на матрицу, составляющее и умножений и 5/2 умножений магри2 цы-т на вектор 0 для вычисления б -го

2 прибпижения к решению, составлякзцих

6„t2. умножений. В известном устройстве требуется 5 умножений матрицы А на вектор д . Следовательно, при порядке системы алгебраических уравнений И 5 и числе итераций б = 100 в известном устройстве требуется бп = 500 умножений, а в предлагаемом .— (— + п+ 3 )И =

2

=280 умножений,, что вполне характеризует выигрыш в быстродействии.

1024932

2f

Составитель И, Пчелинцев р a„rop Г Безвершенко Техред С, Михнов

Заказ 4397/46 Тираж 706 П офисное

ВНИИПИ Государственнм о комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб„д. 4/5

Филиал ЛПП "Патент", ).. Ужгород, ул. Проектная, 4