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

 

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

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК (19) (11) (51) 4 G 06 F 15 32 ф ) < .ryg <

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

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 406407)j24-24 (22) 28,04.86 (46) 15.01.88. Бюп. 1(- 2 (71) Одесский технологический институт холодильной промышленности (72) Л.А.Волощук, И.Д.Коноплев и И.А.Чмырь (53) 681.325 (088.8) (56) Кохонен Т. Ассоциативные запоминающие устройства. - М.:Мир, 1982, с.364.

Авторское свидетельство СССР

В 826360, кл. G 06 F 15/32, 1977. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ

ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ (57) Изобретение относится к цифро.вой вычислительной технике и может быть использовано при построении спе" циализированных вычислительных систем для решения уравнений математической физики. Целью изобретения является увеличение быстродействия.

Устройство содержит блок 1 управления, блоки 3,4 памяти, регистр 5, блок 6 ввода-вывода, блок 7 доступа, блок 8 буферной памяти,. входы и выходы устройства. Устройство обеспечивает решение систем линейных алгебраиМавс ческих уравнений вида Ь „= . Т Ъ.,„U,.„+

1 =!

+ F „, где i = 1,2,3; k = 1,2; n— момент времени, для которого производится расчет. Решение с; стемы урав- д нений выполняется методом итераций, 3 з.п. ф-лы, 6 ил.

/Ю

1Г

1 136

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

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

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

Устройство содержит блок 1 управления, блок 2 обработки, первый 3 и второй 4 блоки памяти, регистр 5, блок 6 ввода-вывода, блок 7 доступа, блок 8 буферной памяти, информационные входы (выходы) 9, управляющие входы (выходы) 10, входы ll режима блока управления. Блок 2 обработки образуют регистр 12 произведений, узел 13 проверки окончания интеграционного процесса, узел 14 анализа, арифметико-логический узел 15. Блок 8 буферной памяти содержит первый 16 и второй 17 сдвнгающие регистры 16 и 17, коммутатор 18.è мультиплексор 19.

Каждый из блоков 3 и 4 памяти выполнен на узлах 20 оперативной памяти (БИС ОЗУ). Блок 7 доступа содержит дешифратор 21, элементы И 22 и 23 и. счетчик 24, Блок 1 управления включает в себя узел 25 постоянной памяти (ППЗУ), элемент И 26 и узел 27 адресации.

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

i макс ..Е Ьi„„V,„+ Г ., (1)

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

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

Решение системы уравнения выполняется методом итераций. При этом блок обработки использует на j-й итерации значения U; „, определенные в ()-1)-м приближении. Таким образом, уравнение

7021 2 (1) для вычисления U „в 1-и приближении можно записать макс (V„„) = С1;„(U, „); „+

+ F (2)

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

1(ц ) — (11,„„) „(- Е, (3) где Š— заданная точность результата.

Устройство работает в следующих режимах: в режиме записи пословно последовательности коэффициентов b. u

11с правых частей Р СЛАУ в блоки памяти из магистрали (режим I ); в режиме считывания всех значений Ь <,F

111 m> ik поразрядно из блоков памяти с одно- временной обработкой их всеми блоками обработки (режим 2); в режиме счи-. тывания значений 11;> поразрядно из блоков обработки в блок памяти с одновременной проверкой условия окончания итерационного процесса (режим 3); в режим читывания значений U;g пословно в магистраль (режим 4); в режим попеременного считывания значений пословно в магистраль и записи перерассчитанных значений Ь;„,F пословно из магистрали в блок памяти (режим 5).

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

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

3 13670 в режим 2. Далее соответствующая микропрограмма (режим 2 ) реализует поразрядное считывание значений коэффициентов, правых частей, узловых

5 функций и их обработку в блоках 2.

При этом на все БИС ОЗУ блоков 3 и 4 памяти из блока 7 доступа подаются сигналы выборки и последовательно перебираются адреса внутри БИС ОЗУ.Оче- 1ð редные разрядные столбцы массивов при каждом считывании фиксируются на регистре 5 и в блоке 6 ввода-вывода, откуда поступают на соответствующие входы блоков 2 обработки. Закрепление значений b,>,У„ за определенными блоками обработки обеспечивается программно при формировании структуры последовательности записи этих данных из магистрали в блоки памяти. 20

Все блоки 2 обработки работают параллельно. Когда микропрограмма режима 2 завершается (а это соответствует получению значений Ц на одной

1Кj итерации), устройство переходит в ре- 25 жим 3, в котором происходит поразрядная перезапись всего массива значений U „ в блок 4 памяти с одновременной проверкой условия сходимости. Если это условие не выполнено, реализу- З0 .ется возврат в режим 2, в противном случае — в режим 4 либо в режим 5.

Последнее определяется исходным управляющим сигналом из магистрали 11-4

"Режим" °

В режиме 4 по сигналу 11-5 "ЗапИ рос организуется выдача в магистраль (выход 9-4) поочередно всех полученных значений U;„ . Последовательность считывания значений U;> всегда неиз- 40 менна. Каждому запросу соответствует одно значение. Считывание завершается дри сигнале 11-6 "Конец запроса".

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

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

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

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

21 4

Значение этой функции на каждой итерации формируется на регистре 12 произведения и во время проверки условия окончания итерационного процесса блоком 13 проверки окончания итерационного процесса через узел 14 анализа записывается поразрядно в блок 4 памяти, откуда также поразрядно поступает на входы определенных блоков 2 обработки, на другие входы которых в ходе каждой итерации поразрядно поступают значения коэффициентов и свободных членов.

Для управления блоком 3 памяти используются управляющие сигналы блока управления: 10-14 "Считывание", 1015 "Запись разрядного столбца b;j,, F, и адресные сигналы, поступающие из блока 7 доступа; с первого выхода блока 7 поступает адрес однобитовой ячейки внутри БИС ОЗУ, с второго его выхода — адрес группы БИС ОЗУ для всего разрядного столбца. Для записи разрядного столбца иэ блока 8 используется вход 9-3, а для считывания в блоки 2 обработки — выходы 9-5 и 9-10.

Дпя управления блоком 4 памяти используются сигналы 10-16 "Управление записью", 10-17 "Управление считыванием", адрес однобитовой ячейки в

БИС ОЗУ и сигналы выбора БИС ОЗУ для разрядного столбца, поступающие с третьего выхода блока 7 доступа, Для записи разрядных столбцов значений 11; из блока обработки используется вход 9-6, для считывания в блок 8 вход 9-2, для считывания в блок обработки — выход .9-7.

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

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

По управляющему сигналу 10-1 для регистра 16 (либо 10-3 для регистра 17) производится прием одного слова и сдвиг предыдущего вверх íà всю длину слова. После полного. заполнения регистра 16 (либо 17) по управляющему сигналу 10-2 (либо 10-4) начинается поразрядный сдвиг всех слов вверх и считывание одноименных разрячто, с целью увеличения быстродействия, в него введены блок доступа, блок буферной памяти, второй блок памяти и регистр, причем с первого по шестой входы режимов блока управления подключены соответственно .к входам запуска, признака обращения, признака конца обращения, режима, признака запроса и признака конца запроса устройства, выход режима с седьмого по (b+7)-й блока управления подключены соответственно к выходам признака завершения итерационного процесса блоков обработки с первого по b-й, выходы с первого по седьмой блока управления подключены соответственно к управляющим входам с первого по седьмой блока буферной памяти, восьмой и девятый выходы блока управления подключены соответственно к первому и второму управляющим входам блока ввода-вывода, десятый выход блока управления подключен к входу записи регистра, с одиннадцатого по тринадцатый выходы блока управления подключены соответчтвенно к входам с первого по третий блока доступа, с четырнадцатого по семнадцатый выходы блока управления подключены соответственно к входу чтения первого блока памяти, входу записи первого блока памяти, к входу чтения второго блока памяти, входу записи второго блока памяти, выход регистра подключен к первым информационным входам всех блоков обработки, первый информационный выход блока ввода-вывода подключен к вторым информационным входам всех блоков обработки, выходы с восемнадцатого по (b+18) — é блока управления подключены соответственно к входам кода операции блоков обработки с первого по Ь-й, информационные выходы которых объединены и подключены к первому информационному входу блока ввода-вывода, первый выход блока доступа подключен к адресным вхо- дам первого и второго блоков памяти, 5 1367021 дов через первый канал комматутора 18 (либо второй канал для коммутатора 18) на информационный выход 9-3.

В режиме считывания значений U,. последовательно по словам в магистраль в отличие от режима записи значений Ь, и Р работает второй канал коммутатора 18 и считывание производится на информационный выход 9-4.)0

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

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

Адрес разрядного столбца образует- 25 ся следующим образом.

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

10-11 счетчик 24 последовательно увеличивает абсолютный адрес, младшие разряды которого поступают на адрес- 30 ные входы всех БИС ОЗУ блоков 3 и 4 памяти, образуя доступ к однобитовой (либо четырехбитовой) ячейке внутри модуля, а старшие дешифрируются в сигналы выбора необходимых модулей для всего разрядного столбца. В зависимости от режима,.в котором работает устройство (сигналы 10-12 и 10-13) открываются группы элементов И 22и 23.

Микропрограммы, соответствующие 40 пяти возможным режимам работы устройства, записаны в ППЗУ 25. Обращение к той либо иной микропрограмме обеспечивается узлом 27 адресации, работой которого управляют магистральные сиг- 45 налы 11-1 — 11-6, сигнал признака сходимости процесса решения, а также ряд сигналов состояния устройства с выхода ППЗУ 25.

55

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

1. Устройство для решения систем линейных алгебраических уравнений, содержащее Ь блоков обработки, где

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

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

3 ° УстрОйстВО пО па1р О т л и 40 ч а ю щ е е с я тем, что блок доступа содержит счетчик, дешифратор, первую и вторую группы из а элементов И каждая, где а — степень блочности

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

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

1367021

1367021

Составитель А.Ушаков

Техред А.Кравчук Корректор В.Бутяга

Редактор Ji.Ï÷îëèíñêàÿ

Заказ 6840/48

Тираж 704 Подписное

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

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

Производственно-полиграфическое предприятие, г.Ужгород, ул.Проектная,4