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

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

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

Ка фиг.1 приведена схема устройст на; на фиг.2 - схема блока обработки; на фиг.З - схема блока буферной памяти; на фиг.4 - схема первого и второго блоков памяти; на фиг.З - схема блока доступа; на фиг.6 - схе- ма блока управления.

Устройство содержит блок 1 управления, блок 2 обработки, первый 3 и второй 4 блоки памяти, регистр 5, блок 6 ввода-вывода, блок 7 доступа, блок 8 буферной памяти, информационные входы (выходы) 9, управляющие входы (выходы) 10, входы J1 режима блока управления. Блок 2 обработки образуют регистр 12 произведений, узел 13 проверки окончания интеграционного процесса, узел J4 анализа, арифметико-логический узел J3. Блок буферной памяти содержит первый 16 и второй J7 сдвигающие регистры J6 и 17, коммутатор 8.и мультиплексор Каждый из блоков 3 и 4 памяти выполнен на узлах 20 оперативной памяти (вис ОЗУ). Блок 7 доступа содержит дешифратор 2J, элементы И 22 и 23 и счетчик 24. Блок 1 управления включает в себя узел 25 постоянной памяти (ППЗУ), элемент И 26 и узел 27 адресации ..

Устройство обеспечивает решение систем линейных алгебраических уравнения (СЛАУ) вида

макс

Т

,,и,,„+

,, , ,.„ wv.ni I

1 1 v

где i l,2,3;.k 1,2; n - момент времени, для которого производится расчет.

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

В режиме J из магистрали на информационный вход 9-1 блока 8 поступает программно Задаваемая последовательность значений bj , F . Каждому значению соответствует, сигнал 11-2 Обращение, который запускает опреде- ленную микропрограмму (Режим 1) блока 1 управления, согласно которой осуществляется накопление части массива на одном буферном регистре блока 8 и считывание разрядных столбцов в блок 3 памяти с другого. После приема очередного слова устройство устанавливается в ожидании следующего сигнала Обращение. Запись последнего данного массива сопровождается управляющим сигналом 11-3 Коискомой функции и(, получаемые в соседних блоках обработки.

нец обращения. Микропрограмма про-.

Решение системы уравнения выполня- 55 изводит деформирование незаполненно- ется методом итераций. При этом блок го буферного регистра блока 8 нуле- обработки использует на j-й итерации выми значениями, считвание последних значения U,-, определенные в (j-l)-M разрядных столбцов в блок 3 памяти приближении. Таким образом, уравнение автоматически переводит устройство

Um,nB j-M приближе t,n

(и;,„ ):

+ F.

(2)

Условие окончания итерационного процесса, обеспечивающего вычисление, следующее:

KU.Jj - (U.Jj., (3) где Е - заданная точность результата.

Устройство работает в следующих режимах: в режиме записи пословно последовательности коэффициентов Ъ., и правых частей F СЛАУ в бпоки памяти из магистрали (режим 1); в режиме

считывания всех значений .- и..,..

Ik

поразрядно из блоков памяти с одновременной обработкой их всеми блоками обработки (режим 2); в режиме счи-. тывания значений U,- поразрядно из блоков обработки в блок памяти с одновременной проверкой условия окончания итерационного процесса (режим 3); в режим читывания значений U {и пословно в магистраль (режим 4); в режим попеременного считывания значений

и

У пословно в магистраль и записи

перерассчитанных значений Ъ;,F пословно из магистрали в блок памяти (режим 5).

Каждому режиму соответствует микро- программа, записанная в узле 25 ППЗУ блока 1 управления.

В режиме J из магистрали на информационный вход 9-1 блока 8 поступает программно Задаваемая последовательность значений bj , F . Каждому значению соответствует, сигнал 11-2 Обращение, который запускает опреде- . ленную микропрограмму (Режим 1) блока 1 управления, согласно которой осуществляется накопление части массива на одном буферном регистре блока 8 и считывание разрядных столбцов в блок 3 памяти с другого. После приема очередного слова устройство устанавливается в ожидании следующего сигнала Обращение. Запись последнего данного массива сопровождается управляющим сигналом 11-3 Ко

в режим 2. Далее соответствующая микропрограмма (режим 2) реализует поразрядное считывание значений коэффициентов, правых частей, узловых функций и их обработку в блоках 2. При этом на все БИС ОЗУ блоков 3 и 4 памяти из блока 7 доступа подаются сигналы выборки и последовательно пеЗначение этой функции на каждой итерации формируется на регистре 12 произведения и во время проверки условия окончания итерационного процесса блоком J3 проверки окончания итерационного процесса через узел 14 анализа записывается поразрядно в блок 4 памяти, откуда также поразрядно посту

Изобретение относится к цифро- .вой вычислительной технике и может ма9исггтасг тб бы ци те че ля Ус ни бл бл ды ет че + мо ди не быть использовано при построении специализированных вычислительных систем для решения уравнений математической физики. Целью изобретения является увеличение быстродействия. Устройство содержит блок 1 управления, блоки 3,4 памяти, регистр 5, блок 6 ввода-вывода, блок 7 доступа, блок 8 буферной памяти,. входы и выходы устройства. Устройство обеспечивает решение систем линейных алгебраитб ческих уравнений вида U А + F,, где i 1,2,3; k 1,2; n - момент времени, для которого производится расчет. Решение системы уравнений выполняется методом итераций. 3 з.п. ф-лы, 6 ил. с & (Л

рёбираются адреса внутри БИС ОЗУ.Оче-ю пает на входы определенных блоков 2

редные разрядные столбцы массивов при каждом считывании фиксируются на регистре 5 и в блоке 6 ввода-вывода, откуда поступают на соответствующие входы блоков 2 обработки. Закрепление значений b. ,F за определенными блоками обработки обеспечивается программно при формировании структуры последовательности записи этих данных из магистрали в блоки памяти, Все блоки 2 обработки работают параллельно. Когда микропрограмма режима 2 завершается (а это соответствует получению значений , на одной

15

20

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

управления блоком 3 памяти используются управляющие сигналы блока управления: 10-J4 Считывание, 10- 15 Запись разрядного-столбца Ь,- , Fp, , и адресные сигналы, поступающие из блока 7 доступа; с первого выхода блока 7 поступает адрес однобитовой ячейки внутри БИС ОЗУ, с второго его выхода - адрес группы БИС ОЗУ для всего разрядного столбца. Для за-

итерации), устройство переходит в ре- 25 писи разрядного столбца из блока 8 жим 3, в котором происходит поразряд- используется вход 9-3, а для считыва- ная перезапись всего массива значе- ния в блоки 2 обработки - выходы 9-5 НИИ U; в блок 4 памяти с одновремен- и 9-10,

ной проверкой условия сходимости, ЕС- Дпя управления блоком 4 памяти ис- ли это условие не выполнено, реализу- ЗО пользуются сигналы JO-J6 Управление

ется возврат в режим 2, в противном случае - в режим 4 либо в режим 5, Последнее определяется исходным управляющим сигналом из магистрали 1J-4 Режим,

В режиме 4 по сигналу 11-5 Запрос организуется выдача в магистраль (выход 9-4) поочередно всех полученных значений U, , Последовательность считывания значений U,- всегда неизменна. Каждому запросу соответствует одно значение. Считывание завершается дри сигнале JJ-6 Конец задроса. Ортогональное преобразование разрядных столбцов в слова производится в блоке 8 буферной памяти, путем пред-т варителъного накопления на сдвигающих регистрах.

Режим 5 может быть использован при решении нестационарных, нелинейных задач.

Управляющий сигнал 1J-J Пуск устанавливает блок 1 управления в исходное состояние (адрес ППЗУ О) и производит сброс (очистку) всех операционных узлов.

Арифметико-логический узел 15 обеспечивает получение функций суммирования парных произведений поразрядно.

5

0

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

управления блоком 3 памяти используются управляющие сигналы блока управления: 10-J4 Считывание, 10- 15 Запись разрядного-столбца Ь,- , Fp, , и адресные сигналы, поступающие из блока 7 доступа; с первого выхода блока 7 поступает адрес однобитовой ячейки внутри БИС ОЗУ, с второго его выхода - адрес группы БИС ОЗУ для всего разрядного столбца. Для за-

0

записью, 10-17 Управление считыванием, адрес однобитовой ячейки в БИС ОЗУ и сигналы выбора БИС ОЗУ для разрядного столбца, поступающие с с третьего выхода блока 7 доступа,

Для записи разрядных столбцов значений блока обработки используется вход 9-6, для считьшания в блок 8 вход 9-2, для считывания в блок обработки - выход .9-7,

В режиме записи Ь F последовательно по словам и параллельно по разрядам работает первый канал коммутатора 18,

Последовательность слов записывается попеременно в сдвигающие регистры J6 и 17, Когда в одном регистре происходит накопление слов, в дру гом реализуется считывание одноименных разрядов накопленного массива.

По управляющему сигналу 10-J для регистра 16 (либо JO-3 для регистра 17) производится прием одного слова и сдвиг предыдущего вверх на всю длину слова. После полного заполнения регистра 16 (либо 17) по управляющему сигналу JO-2 (либо 10-4) начинается поразрядный сдвиг всех слов вверх и считьгоание одноименных разря-

5

0

5

5136702J

дов через первый канал комматутора J8 (либо второй канал для коммутатора 18) на информационньш выход 9-3.

Б режиме считывания значений U.j, последовательно по словам в магистраль в отличие от режима записи значто,

ВИЯ ,

чений Ь., и F работает второй ка i1c

нал коммутатора 18 и считывание прос целью увеличения быстродейст- ., в него введены блок доступа, блок буферной памяти, второй блок памяти и регистр, причем с первого по шестой входы режимов блока управления подключены соответственно к входам запуска, признака обращения, признака конца обращения, режима, приз- изводится на информационный выход 9-4. ю нака запроса и признака конца запроБлок 6 ввода-вывода может быть ре- са устройства, выход режима с седь- ализован, например, в виде регистров . мого по (Ъ+7)-й блока управления под- для фиксации считьшаемого либо запи- ключены соответственно к выходам сьшаемого разрядного столбца в момент признака завершения итерационного обращения к блоку 4 памяти, Дпя обес- 15 процесса блоков обработки с первого печения работы блока необходимы два управляющих сигнала: 10-8 - прием на регистр считываемого разрядного столбца, 10-9 - прием на регистр записываемого разрядного столбца.20

Блок 7 доступа реализует доступ к задаваемой ячейке запоминающего массива в соответствии со сдвиговым (последовательным) способом адресации.

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

По счетному управляющему сигналу 10-11 счетчик 24 последовательно увеличивает абсолютный адрес, младшие

па, с четырнадцатого по семнадцатьш

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

ные входы всех БИС ОЗУ блоков 3 и 4 памяти, образуя доступ к однобитовой

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

-jr блока памяти, выход регистра подключен к первым информационным входам всех блоков обработки, первый информационный выход блока ввода-вьшода подключен к вторым информационным вхо40 дам всех блоков обработки, выходы с восемнадцатого по (Ъ+18)-й блока управления подключены соответственно к входам кода операции блоков обработки с первого по Ъ-й, информационные которого управляют магистральные сиг- 45 выходы которых объединены и подключе(либо четырехбитовой) ячейке внутри модуля, а старшие дешифрируются в сигналы выбора необходимых модулей для всего разрядного столбца. В зависимости от режима,, в котором работает устройство (сигналы 10-12 и 10-13) открьшаются группы элементов И 22 и 23.

Микропрограммы, соответствующие пяти возможным режимам работы устройства, записаны в ПШУ 25. Обращение к той либо иной микропрограмме обеспечивается узлом 27 адресации, работой

налы IJ-l - 1J-6, сигнал признака сходимости процесса решения, а также ряд сигналов состояния устройства с выхода ППЗУ 25.

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

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

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

что,

ВИЯ ,

., блок мяти шесто ния п дам з знака нака

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

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

па, с четырнадцатого по семнадцатьш

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

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

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

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

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

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

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

чены соответственно к информационным входам с первого по шестой узел адресации, с седьмого по (Ъ+7)-й входы режима блока подключены соответственно в первому по Ь-й входам элементов И, выход которого подключен к первому управляющему входу узла адресации, выход которого подключён к адресному входу узла постоянной памяти, выходы с первого по семнадцатый

которого подключены соответственно к выходам с первого по семнадцатый блока, выходы с восемнадцатого по (Ъ+18)-й блока подключены соответственно к выходам с восемнадцатого по

(Ъ+18)-й узлов постоянной памяти, (Ъ+19) и (Ъ+20)-й выходы которого подключены соответственно к второму и третьему управляющим входам узла ад- адресации.

ffSn.6

15

15

Jc

LJL

Ul.

фие.г

9-1

«M

9-Z

19-5

13

17

9

-V

фигЛ

io-ti

V

т

1Q 13

21

2Ъ

фие.З