Патент ссср 826360

 

Союз Сометсккк

Соцкалнстическка

Республик

ОП ИСАНИЕ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополяи.пельное к авт. свмд-ву— (22) Заявлено 15.08.79 (21) 2814170/18-24 с присоединением заявки №вЂ” (51) М. Кл.э

G 06F 15/32

Гесударстееиимй комитет (23) Приоритет— с

Опубликовано 30.04.81. Бюллетень № 16

СССР по делам иэебретеиий и етермтий (53) УДК 681.323 (088.8) Дата опубликования описания 30.04.81 (72) Автор изобретения!

Q"

Ю. Я. Ледянкин .. I I .

Л, Ф pl

4

Ордена Ленина институт кибернетики Аг(Укрйив ) ой,ССР

1 (71) Заявитель (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ УРАВНЕНИЙ

МАТЕМАТИЧЕСКОЙ ФИЗИКИ

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

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

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

Наиболее близким техническим решением к предлагаемому является устройство для решения двумерных задач математической физики, содержащее группу микропроцессоров, блок вводa-вывода, блок управ2 ления, и бок задания краевых условий и правых частей, а также блок анализа, входы которого подключены к выходным шинам сумматоров, а выходы — ко входам блока управления. Граничные условия, введенные в контурные узлы, распространяются и на внутренние узлы, реализуя (за счет набора устройств и связей между узлами сетки) выражение (РЧ VLL

Блок анализа осуществляет сравнение значений сеточных функций в каждом узле на двух соседних итерациях, что и позволяет осуществить останов итерационного процесса ?J. едостатками устройства являются большой объем оборудования и невозможность решения уравнений с переменными коэффициентами, а также нестационарных уравнений, когда необходимо выполнять операцию умножения. А введение устройства умножения превратит сеточный узел в вычислительную машину с высоким расходом оборудования и большими временными затратами на выполнение операции умножения. Устройство обладает дополнительными недостат826360 ками, связанными с выполнением операции анализа значений сеточных функций во всех узлах, что ведет к увеличению связей и оборудования.

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

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

Цель изобретения — повышение быстродействия и упрощение устройства.

15 го

Зо

3S

55

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

Блок выделения приращения содержит группу элементов ИЛИ, входы которых соединены соответственно со входами блока, а выходы группы элементов ИЛИ объединены и подключены к выходу блока выделения прирашения.

Блок управления содержит схему сравнения на «О», дешифратор, счетчик, элемент И и генератор, причем выход генератора соединен с первым входом элемента И, второй вход которого является входом блока, группа входов счетчика является установочными входами блока, выходы счетчика соединены соответственно со входами схемы сравнения на «О» и входами дешифратора, выходы которого являются группой выходов блока, выход схемы сравнения является первым выходом блока, выход элемента И подключен к счетному входу счетчика и второму выходу блока.

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

Устройство содержит группу микропроцессоров 1, объединенных в сетку, блок 2 ввода-вывода, блок 3 управления, блок 4 задания краевых условий и правых частей, блок 5 выделения приращений.

Микропроцессор 1 состоит (см. фиг. 2) из узла 6 задания коэффициентов арифметико-логического узла 7 и триггера 8 приращений, вход которого подключен к выходу элемента И 9, а выход — к наружному выводу 10, вход арифметико-логического узла 7 соединен с выходом узла 6 задания коэффициентов, а выход подключен к первому входу элемента И 9, входу узла 11 накопления решения и наружному выводу 12

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

Блок 5 выделения прирашений содержит (фиг. 3) группу элементов ИЛИ, входы которых соединены соответственно со входами блока 5, а выходы группы элементов ИЛИ объединены и подключены к выходу блока 5.

826360

Блок 3 управления содержит (фиг. 4) счетчик 14, дешифратор 15, схему 16 сравнения на «0», генератор 17, элемент И 18.

Выход генератора 17 соединен с первым входом элемента И 18, второй вход которого является входом блока. Группа входов счетчика 14 является х ста новочны м и в хода м и блока, выходы счетчика 14 соединены соответственно со входами схемы 16 сравнения на «О» и входами. дешифратора 15, выходы которого являются группой выходов блока. Выход схемы 16 сравнения является первым выходом блока, выход элемента И 18 подключен к счетному входу счетчика 14 и второму выходу блока управления.

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

Первый выход блока 3 управления подключен к управляющему входу узла 11 накопления решения, второй выход — к управляющему входу арифметико-логического узла 7, а группа выходов блока 3 управления подключена к адресным входам узла 6 задания коэффициентов каждого микропроцессора 1. Информационные входы узла 6 задания коэффициентов каждого микропроцессора 1 соединены с соответствующими выходами блока 2 ввода-вывода, входы которого соединены соответственно с выходами узлов

ll накопления решения каждого микропроцессора l. Управляющие входы 13 узла 6 задания коэффициентов каждого микропроцессора 1 соединены соответственно с выходами 10 триггеров 8 приращений соседних микропроцессоров l. Информационный вход арифметико-логического узла 7 каждого микропроцессора подключен к выходу блока 4 задания коэффициентов.

Устройство может быть организовано из линейки микропроцессоров 1 (устройство векторного типа) или из группы линеек микропроцессоров 1 (устройство матричного типа).

Блок 5 выделения приращения содержит группу элементов ИЛИ по числу микропроцессоров 1, объединенных в сетку, а число входов блока равно числу элементов ИЛИ.

Блок 5 выделения приращения может быть построен на базе цифровой логической схемы И вЂ” НЕ и др. Основное назначение его— выделение первого отличного от нуля (т. е. равного «1») старшего разряда исходных данных в арифметико-логических узлах 7 всех микропроцессоров 1, объединенных в сетку; фиксация в триггерах 8 приращений значения 1-го разряда («О» или «1») исходных данных в арифметико-логических узлах 7 каждого микропроцессора i; остаzo

Зо

40 нов сдвига исходHhlx данных в сторону старших разрядов с помошью блока 3 управления (по второму выходу блока); фиксация

1-того номера позиции выделенного старшего разряда с помощью счетчика 14 и определение этого номера с помощью дешифратора 15 блока 3 управления; останов итерационного процесса, когда в пределах разрядной сетки исходных данных арифметикологического узла 7 всех микропроцессоров

1, объединенных в сетку, находятся только нули (с помощью схемы 16 сравнения на

«О» блока 3 управления по его первому выходу) . В этом случае на втором выходе блока сигнал останова сдвига не вырабатывается.

Блок 3 управления, кроме того, вырабатывает сигнал управления для сложения

«1» (или «О») полученного прирашения с

1-тым разрядом значения сеточной функции, храняшейся в узле l l накопления решения каждого микропроцессора 1. Этот сигнал по первому выходу блока 3 управления передаегся в узел 11 накопления решения.

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

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

Как только íà E-том микротакте, например в одном (или нескольких одновременно) микропроцессоре 1, в 8-том разряде кода исходных данных выделяют «1», по схеме

ИЛИ ее фиксируют блоком 5 выделения приращения. Блок выделения приращения вырабатывает сигнал, по которому: через второй выход блока 3 управления на управляющий вход арифметико-логического узла 7 каждого микропроцессора 1 поступает сигнал останова сдвига исходных данных в сторону старших разрядов и принудительного сброса 1-го разряда в «О»; счетчик 14 блока 3 управления фиксирует номер позиции выделенного 1-го разряда, дешифратор 15 определяет этот номер и через группы выходов блока 3 управления на адресные входы узла 6 задания коэффициентов поступает адрес 2-го разряда; в триггер приращений каждого микропроцессора записывают то значение, которое было в -том разряде исходных данных в момент останова процесса сдвига (до установки его в «О»)

После этого младшими разрядами вперед сдвигают код остатка (из арифметико-логического узла 7), полученного из прежнего

826360 значения исходных данных после принудительной установки в «О» P-го разряда, и коды тех коэффициентов (из узла 6 задания коэффициентов), на управляющие входы

l3 которых с выхода 10 триггера 8 приращения соседнего микропроцессора 1 устройства поступит разрешающий сигнал. Сдвиг коэфф»ц»снтов Hd 2 разрядов осуществляют с помощью адресных входов узла 6 задания коэффициентов. В арифметико-логическом узле 7 получают сумму коэффициентов, сдвинутых (умноженных на величину 2 ) на Й разрядов, с кодом остатка от предыдущей итерации. Полученная в каждом микропроцессоре 1 устройства сумма является новыми исходными данными для следующей итера ци».

Сложение коэффициентов и остатка от пре.сыдугцей итерации может осушествляться»араллельным, последовательным или

»араллель»о-последовательным кодом. Режим опрсделяется требованиями к быстродей«тв»ю системы, ее аппаратурными орга»»н«г»»ям», энергопотреблением и,T. д. 0

Выделенные во всех микропроцессорах устрой«тва приращения, взятые с учетом веса, «кладывак)т с суммой приращений, »олучсн»ых ранее в этом же микропроцессоре. С этой целью в узле 11 накопления решения каждого микропроцессора 1 суммиру от «!»»ли «О» приращения, выделенного в данном микропроцессоре, с 1-тым разрядом сеточной функции, пако»ленной ранее. Подсветку Я-того разряда осуществляют, например с помощью сигнала управления, который вырабатываст схема 16 сравнения на «О» блока 3 у»равления, и через первый

30 выход олока 3»осту»ает на управляюгций вход узла 1 накопления решения.

Далее итерационный процесс продолжак>т по аналогии с описанным., Процесс оста»авл»вают по сигналу управлс »»я из блока 3 управления после того, как во всех микро»ропе«сорах в диапазоне и«хо,сшых данных. »редставленных конеч»ой разрядной сеткой, исчезнут все «1», что равное»тельно коду 00...0 в счетчике 14

40 фиксации номера разряда приращений блока 3 управления. Но можно остановить итерационны»роцссс и раньше, например после тс;го, как прекратит выделяться к-тый разряд. Г!осле этого в узле 11 накопления решения каждого микропроцессора запоминается значение сеточной функции, опреде45 ленное размерностью сетки, которой покрыта ность представляемых чисел, и упрощении устройства за счет устранения операции умножения для уравнений с переменными кообласть решения, и методом аппроксимации.

Технико-экономический эффект предлагаемого устройства по сравнению с известным заключается в повышении быстродейюствия в п раз (— =- и) где и — разрядЯ 3

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

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

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

2. Устройство по п. l, отличающееся тем, что блок выделения приращения содержит группу элементов ИЛИ, входы которых соединены соответственно со входами блока, а выходы группы элементов ИЛИ объединены и подключены к выходу блока.

826360

3. Устройство по п. 1, отличающееся тем, что блок управления содержит схему сравнения на «О», дешифратор, счетчик, элемент И и генератор„причем выход генератора соединен с первым входом элемента И, второй вход которого является входом блока, группа входов счетчика является установочными входами блока, выходы счетчика соединены соответственно со входами схемы сравнения на «О» и входами дешифратора, выходы которого являются группой выходов блока, выход схемы сравнения является первым выходом блока, выход элемента И подключен к счетному входу счетчика и второму выходу блока.

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

1. Евреинов Э. В., Косарев iO. Г. Однородные универсальные вычислительные системы высокой производительности. Новосибирск, «Наука», 1966, с. 40, рис. 8.

2. Авторское свидетельство СССР № 610116, кл. G 06 F15/32,,1978 (прототип) .

1О

3. Авторское свидетельство СССР по заявке № 2630463, кл. G 06 F 15(32, 15. 12. 78.

826360

Составитель Н. Палеева

Редактор С. Шевченко Техред А. Бойкас Корректор В. Бутяга

Заказ 2501/71 Тираж 745 Подписное

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

113035, Москва, Ж вЂ” 35; Раушская наб., д. 4/5 филиал ППП «Патент», r. Ужгород, ул. Проектная, 4