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

ttr-Hm

(Л

с

«а.т

4 о

О1

о

со

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

A(t).5c-y(t); |A(t)|/0;

telo,Tl,(1)

матрица типа тепли- цевых, составленная из численно опреде- ляемых коэффициенто

где A(t)-{nvn) A(t) lla;.

ao(t)a.,(t).,.a,.|(t) a,(t)ao{t),,.a2-h{t).

;(t) 25

30

35

an,i(t)a.5(t),..aj,(t)

(2)

y(t) - вектор-столбец с заданными компонентами y(t):Cyi(t), 20 y2{-t),...,yp{t() вектор неизвестных x(t)Cxi(t(),

Xi(t),..,,Xf,(t) .

Предполагается, что .a(j и y-Ct) изменяются во времени дискретно, че- рез некоторые промежутки времени Лto и 4t, причем dt «4tot.

Цель изобретения - довышение быстродействия устройства,

.На фиг. 1 дриведена функциональная схема устройства; на фиг„ 2 и 3 - схема блока управления} на фиг. 4 состояние сдвигающих регистров в процессе вычисления; на фиг. 5 - алгоритм работы устройства. Устройство содержит блок 1 памя- ти, первый сумматор 2, регистр 3, блок 4 управления, второй сумматор 5, р мультиплексоров 6, р сдвигающих ре-дд гистров 7, р групп по Ы блоков 8 памяти, группу изр сумматоров 9. Блок. 4 управления содержит первый регистр 10, первый 11 и второй 12 счетчики, второй регистр 13, триггер 14, пер- 45 вый 15 и второй 16 дешифраторы, сумматор 17э третий дешифратор 18, пер- вьй 19, второй 20, третий 21, четвертый 22, пятый 23, шестой 24, седьмой 25, восьмой 26 и девятый 27 элементы И, первтлй 28, второй 29, третий 30 и четвертый 31 элементь НЕ, элемент 32 задержки, группа из И элементов И 33, элемент ЧЙ-ИЛИ 34.

Блок 1 памяти имеет разрядность р и емкость N слов, необходимую для хранения заданного массива значений у, Сумматор 2 служит для формирования результата вычислений неизвестных х.

50

Q

5

0

5

0

д 5

0

как разности между значением у и суммами слагаемых выражений.

Регистр 3 представляет р-разряд- ный регистр для хранения текущего результата вычислений х..

Сумматор 5 суммирует числа, представляющие суммы коэффициентов, вычисленные в каждом канале обработки информации.

Регистр 7 предназначен для хранения и сдвига вычисляемых и вычисленных ранее компонент вектора и имеет количество разрядов, не меньшее числа коэффициентов a.j.

Блоки 8 памяти предназначены для хранения сумм слагаемых. Его разрядность определяется требуемой точностью вычислений и может быть различной в зависимости от границ области значений коэффициентов а,- . Адрес ячейки, к которой происходит обращение, определяется кодом, находящимся в соответствующих триггерах регистра 7.

Сумматор 9 предназначен для суммирования чисел, считьшаемых с блоков 8 памяти суммы коэффициентов.

Регистр 10 хранит код выполняемой микрооперации. Счетчик 11 формирует: код адреса того блока, в который осуществляется запись сумм коэффициен- тов. Регистр 13 хранит код требуемого числа циклов вычислений. Триггер 14 формирует признак занятости устройства. Дешифратор 15 формирует сигнал вьтолняемой микрооперации. Дешифратор 16 формирует сигнал выбора : блоков 8 памяти при вводе суммы коэф-. фициентов. Сумматор 17 определяет количество невыполненных циклов итераций Дещифратор 18 формирует признак равенства кодов, хранящихся в счетчике циклов и регистре циклов,

Рещение системы уравнений {1) ос- .новано на итерационном методе Гаус- са-Зейделя

N

ах..)

1 т

-

- L

а,., - J-.1 -I J

W1

,

где i

(3)

порядковый номер компоненты вектора х (он же порядковый номер уравнения в системе);

j - индекс суммирования;

N - число уравнений в системе, совпадающее с размерностью вектора х.

С учетом характера матрицы (2) процесс (З) можно представить в виде

()

. Х

I

i-1

И

Сл)) ГТ W+i)v

- p-lf- i-; i

а„

5 1

4j-i

КХ

())

W- J У,-

или

1-1

HL J-ry а a

. Н J

(-J)

J

Xi() в двоичном

Н.

j

2-X ,.

и

де р - разрядность двоичных чисел; значение разрядов в двоичном представлении. Обозначив

U)

-,.1)

а , . X ., 1-J Jf

(7)

имеют

W-1

i-1

2(Z:q7r -b

.п -) )

t:0

и

).

Слагаемые каждой из двух сумм, находящихся в (8), могут быть сгруппированы по d членов (значение о определяется количеством адресных входов в блоках памяти). Общее число таких групп равно N1/2, где N - число коэффициентов (Nl 2N-1). С учетом того, что переменные q принимают значение О при х и a, при

x.j l может быть вычислена сумма У слагаемых дпя любого из 2 возможных кодов в группе. Вычисления всех 2 сумм в каждой группе производится вне устройства (например, на универсальной ЭВМ), а результаты вычислений для всех возможных кодов вводить в блоки 8 памяти сумм коэффициентов.

В этом случае х; можно вычислить

как

(

М,Ы

В. о

2 5lQ,+x(f, (9)

С- 5

S«i

где

5о

e.s

ijf

J (S-l)ofM

(10)

10

15

20

25

30

35

Вычисление Xj по формуле (9) реализуется путем считывания кодов Qj из соответствующих ячеек блоков 8 памяти, определяемых кодом текущего приближения в сдвигающих регистрах 7, : формирования с помощью сумматора 9 ; сумм QJ в каждом разряде, суммирования в сумматорах 5 значений, полученных в сумматорах 9, считьшания величин Sy /BO и соответствующих блоков памяти и формирования результатов вычисления с помощью сумматора 2.

В результате выполнения требуемого количества тактов вычислений, определяемого числом разрядов в регистр 7, в последних записаны результаты вычислений неизвестных х-; на ()-й итерации. После выполнения необходи-; мого числа итераций, определяемого загруженными в блок 4 управления дан ными, в регистрах 7 сформирован рее, зультат рещения системы уравнений.

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

Реализация конкретного алгоритма вычислений основана на выполнении определенных операций, представленных : в табл. 1, и анализе формируемых в устройстве логических условий, приведенных в табл. 2.

Таблица 1

45

50

вкв

внп

Ввод приз нака окончания вычислений

Ввод начального приближения

010

100

ЗКФ

Запись коэффициентов 101

Продолжение табл. 1

Таблица2

Мнемоническое обозначение

Логическое условие

СЧИ-М1 Код счетчика ше или равен

СЧИ-М2 . Код счетчика вен М2

СЧИ-0 Код счетчика индекса равен О

СЧБ-МЗ Код счетчика адреса блоков 8 памяти суммы коэффициентов равен,МЗ

СЧЦ-Р15 Выполненное число циклов вычислений равно числу, записанному в регистре Р13

Примечание. Ml - число коэффициентов aj.j, М2 - число разрядов в регистрах 7, МЗ - число блоков 8 памяти суммы коэффициентов, Р15 - число итерационных циклов, заданное загружаемыми в регистр 13 данными.

На архитектурном уровне содержание операций состоит в следующем.

Ожидание. Никакие операции не выполняются.

Сброс. Блок 4 управления устанавливается в исходное положение,

Ввод начального приближения. Операция заключается в записи в регистры 7 данных, додаваемых на входы устройства Bl.l-Bl.m.

Ввод дризнака окончания вычисле- Одерация состоит во вводе данных с входов В1.1-В1,т в блок 4 управления (количество итераций вычислений ).

Запись коэффициентов. Осущестний

вляется после операций Еброс и

14050736

Ввод начального приближения. В результате в регистры 7 записывается информация об адресах ячеек блоков В памяти суммы коэффициентов. При поступлении на входы ВЗ, В4 и В5 кода 101 (код операции Запись коэффициентов) и на вход В9 импульса занесения код операции записывается в - 10 устройство (блок 4) и производится дешифрация кода операции 101. Соответственно выбирается в каждом канале только один блок 8 памяти суммы коэффициентов. При поступлении на

15 вход В6 импульса тактовой частоты информация о записываемой сумме коэф.- фициентов с входов В1,.1.т заиндекса боль- носится в один из выбранных блоков 8 Mlпамяти суммы коэффициентов. После

20 записи информации в выбранную ячейку индекса ра- блоком 4 управления активизируется другая цепь и информация с входов Bl.l-Bl.m записывается по тому же адресу, определяемому соответствующим

25 кодом регистра 7, но в другой блок В памяти суммы коэффициентов. Для за- .писи суммы коэффициентов в другую ячейку снова вьшолняется операция Ввод начального приближения, в ре30 зультате которой в регистрах 7 записан адрес новой ячейки.

Ввод правой части. Операция . состоит в записи данных в блок 1 памяти, которые поступают на его первый вход. Для этого блок 4 управления формирует стробирующие импульсу, поступающие на вход чтения блока 1 памяти.

Счет, Вьшолнению операции обыч40 но предшествует вьшолнение операций Запись коэффициентов, Запись начального приближения и Ввод правой части. При поступлении кода опера- : ции Счет на соответствующем выходе

45 яблока 4 управления формируется импульс, по которому результат, сформированный на выходе сумматора 2, записывается в регистр 3. На выходе сумматора 2 при этом формируется раз50 ность значения правой части, поступающей с блока 1 памяти, и значения, сформированного сумматором 5. Результат на выходе равен сумме слага- емыхр считываемых с сумматора 9, ко55 торые суммируют числа, поступающие с выходов блоков 8 памяти сумм коэффициентов и определяемые кодом, находящимся в соответствующих регистрах 7,

35

Далее информация в регистре 7 сдвигается на один разряд а в первый триггер регистра 7 записывается результат, хранящийся в соответствующем триггере регистра 3,

В каждый последующий такт вьтолняются аналогичные операции, в первые разряды регистра 7 записываются новые вычисленные значения х. После выполнения Ml сдвигов блок 4 управления формирует сигнал блокировки записи информации в регистры 7, в результате чего в регистр 7 записываются 0. Если вьшолняемый итерационный цикл последний, блок 4 управления на выводе В7 формирует признак последнего цикла. В конце последнего цикла триггер Работа переводится в нулевое состояние.

Работа блока 4 управления определяется содержанием операций, приве- .денных в табл. 1. Выполнение каждой операции начинается после появления на выходе В9 сигнала Занесение, в результате которого информация с входов В1.1-В1.т оказывается занесенной в регистр 10 (фиг. 2). При записи в регистр 10 кодов операции, которые вьтолняются более чем за оди такт (коды 100-111), триггер 14 Работа устанавливается в 1 с помощью элемента И 27. Далее выполнение операций происходит следуюшр м образом.

Сброс, Осуществляется сброс счетчика 11 кодом адреса блока 8 памяти счетчика 12 и триггера 14.

Ожидание. Импульсы тактовой частоты на выходах элементов 26, 23 и 32 не формируются, так как блокируются сигналами с выходов элемента 19 и дешифратора 15.

Ввод начального приближения, При этой мнкроопер ации сигнал с со- ответствзтощего выхода дешифратора 15 подается на управляющие входы мультиплексоров 6, а сигналы тактовой частоты с выхода элемента 26 подаются на вход регистров 7.

Запись коэффициентов. На выходе элемента 29 формируется сигнал, который подается на блоки 8 памяти в качестве признака записи. Запись осуществляется в блок 8, адрес кото- рого определяется кодом в счетчике 11 .

Ввод правой части. Сигнал с выхода дешифратора 15 через элемент

НЕ 29 поступает на вход элемента И 23,-на выходе которого формируется сигнал записи правой части в блок 1 памяти.

Ввод признака окончания вычислений .Информация с входов В1.1-В1.т записывается в регистр 13.

Счет. В каждый период тактовой частоты на выходе элемента 32 задержки формируется импульс, задержанный на время установления сигналов на сумматорах 5 и 9. При записи в ре- гистр 10 кода операции 111 все блоки 8 памяти суммы коэффициентов оказываются выбранными. В каждьй период тактовой частоты формируются также сигналы на выходе элемента 26, обеспечивающие запись информации из ре- : гистра 3 в регистры 7 и увеличивающие код счетчика Г2 на единицу ,

При формировании в счетчике кода Ml элемент И 22 формирует сигнал бло-г кировки записи информации в регистре 7. При поступлении последующих тактовых импульсов в регистрах. эапи- сываются нули. При равенстве значений кодов счетчика циклов и регистра 13 на выходе сумматора 17 формируется код, равный 0. При этом на нулевом выходе дещифратора 18 форьдаруется признак последнего цикла,

В нулевом такте регистра 7 находятся начальное приближение и вычис ляется первое итерационное приближение х,. В первом такте начальное . приближение сдвигается на один разряд вправо и в первьй разряд регистра 7 i записывается на один разряд вправо, ; и в первый разряд регистра 7 эаписы- вается вычисленное значение х,, В п-м такте в первый разряд ааписывает-г ся вычисленное значение х,. Итерационный цикл завершается после 2N сдвиг гов, в результате которых данные вЫ-; числений занимают исходное положение для выполнения следукнцёй итерации, Состояние устройства в процессе вычислений может характеризоваться кодами, хранящимися: в триггере Работа, в счетчике выбранных блоков памяти суммы коэффициентов, в триггерах регистров 7, соответствующих раз-- рядам адреса ячейки памяти суммы коэффициентов при выполнении микрооперации Ввод коэффициентов.

Загрузка кодов сумм коэффициентов в блоки 8 памяти и решение системы уравнений иллюстрируется блок-схемой

914

алгоритма работы устройства (фиг.5). Цифрами и соответствующей мнемоникой обозначены следующие действия и логические условия: 35 - Сброс, в ре- зульт ате которого блок 4 управления устанавливается в исходное положение; 36 - Ввод начального приближения, в результате чего в регистры 7 записываются адреса ячеек блоков 8 памя- ти,суммы коэффициентов (в последующем в эти ячейки записываются коды сумм коэффициентов); 37 - анализ логичес

73

10

54 - формирование сигнала Признак последнего цикла равен О,

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

Формула изобретения

Изобретение относится к вычислительной технике и может быть использовано для решения систем линейных алгебраических уравнений. Цель изобретения - повышение быстродейст ВИЯ устройства. Поставленная цель достигается тем, что устройство со- блок 1 памяти, первый сумма-. тор 2, регистр 3, блок 4 управления, второй сумматор 5, р мультиплексоров 6, где р - разрядность представления информации, р сдвигающих регистров 7, р групп по N блоков 8 памяти, где N - порядок системы уравнений, группу из р сумматоров 9. 1 з.п. ф- лы, 5 йл., 2 табл.

кого условия 3 са равен

Код счетчика индек- 38 - Запись коэффици- 15

ентоБ S код с входных шин В 1,1-В1 .т записьшается в адресуемую регистром 7 ячейку, выбранную дешифратором 16 кода счетчика 11 адреса блоков 8 памяти суммы коэффициентов; 39 - ана- ; ЛИЗ условия Код счетчика адреса ков памяти 8 суммы коэффициентов ра- вен 40 - анализ условия Код адреса выбранной ячейки равен М4 } где 4 - максимальное значение адреса ячейки в блоке 8 памяти суммы коэффициентов ; 41 - Ввод признака окончания вычисления, при котором код требуемого количества итераций запи сываётся в соответствующий регистр блока 4 управления; 42 - Ввод начального приближения,, данные начального приближения с входных шин устройства записьшаются в регистры 7| 43 - анализ логического условия Код счетчика индексов равен 44 - производится Ввод правой части (вектор вводится в блок 1 памяти); 45 анализ лоп ческого условия Код счетчика индексов равен 46 - Счет, за один такт осуществляется вычисление одного значения х, сдвиг содержимого регистров 7 на один разряд и запись вычисленного значения в освободившийся разряд; 47 - анализ логического условия Код счетчика индексов больше или равен 48 - формирование признака блокировки мультиплексора, равного 1| 49 - ана ЛИЗ условия Код счетчика индекса равен 50 - формирование признака блокировки мультиплексора5 равного О j 51 - анализ логического условия Выполненное число итерационных циклов вычислений равно числу, записанному в 52 - формирование сигнала Признак последнего цикла равен 53 - анализ логического условия Код счетчика индексов равен

5

0 кода операций и вход синхронизации устройства подключены соответственно к первому, второму, третьему входам режима и входу синхронизации блока у травления, вход признака занесения

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

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

5 к информационному входу регистра,

вход записи которого подключен к первому выходу блока управления, с первого по р-й йыходы регистра подключе ны соответственно к первому по р-й ;

0 информационным выходам устройства, отличающееся тем, что,с целью повьшения быстродействия устройства, в него введено р мультиплексоров, р сдвигающих регистров, груп5 па из р сумматоров, второй сумматор ИР групп по N блоков памяти, где Ш - порядок системы уравненийj при этом входы с первого по р-й свободных членов устройства подключены

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

С первого по р-й сдвигающих регистров, шестой выход блока управления подключен к входам чтения (записи) с первого по К-й блоков памяти с первой по р групп, с первого по р-й входы режима группы блока управления подключены соответственно к входам с первого по р-й свободных членов стройства, седьмой и восьмой выходы блока управления подключены соответственно к выходу признака занятости устройства и выходу признака последнего цикла устройства, а-й выход, где ,...,N, Ъ-го сдвигающего регистра, где ,...,р, подключен к адресному входу а-го блока памяти -й группы, выход которого подключен к а-му информационному входу Ъ-го сумматора группы, выход которого подключен к Ъ-му информационному входу второго сумматора, выход которого одключен к второму информационному

входу, первого сумматора, а-й выход группы блока управления подключен к синхровходам а-х блоков памяти с дер- вой по р-Ю групп. :

2, Устройство по п. 1, отличающееся тем, что блок управления содержит два регистра, три дешифратора, два счетчика, сумматор, триггер, девять элементов И, четыре элемента НЕ, элемент задержки, элемент 4И-ИПИ и группу из N элементов И, причем первый, второй и третий входы режима блока управления подключены соответственно к информациЪн- ным входам с первого по третий первого регистра, четвертый вход режима блока управления подключен к синхро- входу первого регистра, выход которого подключен к входу первого дещиф- ратора, первьй выход которого подключен к первому входу первого элемента И и первому входу второго элемента И, второй выход первого дешифратора подключен к второму входу первого элемента И, третий выход первого дешифратора подключен к входу записи считывания второго регистра,к третьему входу первого элемента И,

0

5

0

0

четвертьш выход первого дешифратора подключен к первому входу третьего элемента И, пятый выход первого дешифратора подключен к входу первого элемента НЕ, третьему выходу блока управления и первому входу четвертого элемента И, шестой выход первого дешифратора подключен к входу второго элемента НЕ, седьмой выход первого дешифратора подключен к входу третьего элемента НЕ, к первому входу пятого элемента И, восьмой выход первого дешифратора подключен к первому

5 входу шестого элемента И, первому входу седьмого элемента И, второму входу третьего элемента И и первым входам элементов И группы, вход синхронизации блока управления подключен к второму входу шестого элемента И, первому входу восьмого элемента И, второму входу пятого элемента И, синхровходу второго дешифратора, второму входу седьмого элемента И, входу синхронизации второго регистра и второму входу второго элемента И, выход которого подключен к входам установки в О первого и второго счетчиков, выходы с первого по (N- -I)-й второго дешифратора подключены к вторым входам соответственно элементов И с первого .по (К-1)-й группы, К-й выход второго дешифратора подключен к второму входу N-ro

(- элемента И группы и-третьему входу третьего элемента И, выход которого подключен к первому входу элемента 4И-ИЛИ, инверсный выход которого подключен к входу четвертого элемента

Q HE, выход которого подключен к входу . установки в О триггера, выход котог- рого подключен к седьмому выходу блока управления, выход первого элементй И подключен к второму входу восьмого

g элемента И, инверсный выход которого подключен к входу элемента задержки, пятому выходу блока управления и : счетному входу второго счетчика, вы- ход элемента задержки подключен к первому выходу блока управления и первому входу девятого элемента И, инверсный выход которого подключен к информационному входу триггера, выход четвертого элемента И подключен к

с второму выходу блока управления, ин- версньй выход пятого элемента И подключен к четвертому выходу блока управления и второму входу девятого элемента И, выход седьмого элемента И

подключен к счетному входу первого счетчика, выход которого подключен к информаи;ионному входу второго дешифратора,, выход первого элемента НЕ подклютген к второму входу элемента 4И-ИЛИ выход второго элемента НЕ подключен к шестому выходу блока управления, выход третьего элемента НЕ подключен к третьему входу элемента 4И-ИЛИ выход шестого элемента И подключен к четвертому входу элемента 4И-ИЛИ, выходы элементов И с первого по N-й группы подключены соответственно к выходам с первого по N-й группы блока управления, входы режима с первого по р-й группы которого

подключены к информационным входам соответственно с первого по р-й второго регистра, выход которого подключен к первому информационному входу сумматора, выход которого подключен к входу третьего дешифратора, выход которого подключен к восьмому выходу блока управления и пятому входу элемента 4И-ИЛИ, первый и второй выходы второго счетчика подключены соответственно к второму входу четвертого элемента И и второму информационному входу сумматора, третий выход второго счетчика подключен к шестому, седьмому, восьмому и девятому входам элемента Аи-ипи.

Фиг г