Вероятностное устройство для решения конечно-разностных уравнений

 

1.

ОП ИСАН И Е

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ i<1 4774l8

Союз Советских

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

Республик (б1) Зависимое от авт. свидетельства (22) Заявлено 18.10.72 (21) 1839144/18-24 с присоединением заявки № (32) Приоритет

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

Дата опубликования описания 15.10.75 (51) М. Кл. G 061 15/32

Государственный комитет

Сооета Министров СССР ео делам изобретений и от;Рытий (53) УДК 681.14(088.8) (72) Автор изобретения

В С Гладкий

Морской гидрофизический институт АН Украинской ССР (71) Заявитель (54) ВЕРОЯТНОСТНОЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ

КОН ЕЧ НО-РАЗНОСТН ЫХ УРАВНЕН И Й

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

Известно вероятностное устройство для решения конечно-разностных уравнений, содержащее линию задержки, триггер начала-останова работы, вход которого соединен с выходом регистра начального адреса, другой выход которого соединен с одним из входов первой схемы совпадения, выход последней подключен к первому входу регистра блуждания, второй вход которого подключен к управляемому вероятностному (1 — и) -полюснику, а выход — к магнитному оперативному запоминающему блоку; вход управляемого вероятностного (1 — n)-полюсника соединен с выходом второй схемы совпадения, первый выход— с одним из входов первой схемы «ИЛИ», второй выход — с первым переключателем, первый вход первой схемы cовпадения подключен к триггеру начала-останова работы, второй вход — к генератору тактовых импульсов, регистр числа, выходы которого соединены с первым переключателем, магнитным оперативным запоминающими блоком, суммирующим и усредпяющим блоком и блоком анализа признаков узла, а входы — с магнитным оперативным запоминающим блоком и выходом третьей схемы совпадения; суммирующий и усредняющий блоки, выходы которых подключены к первому входу третьей схемы совпадения и первому входу процессора, второй вход которого соединен с выходом первого управляемого счетчика-делителя, два входа которого .подключены соответственно к выходу второй схемы «ИЛИ» и процессору, блок изменения признака узла.

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

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

Цель достигается тем, что выход управляемого счетчика-делителя через линию задер>ккп, вторую схему «ИЛИ» и первую схему совпадения подключен ко входу регистра блуж20 дания, а также ко входу регистра начального адреса и через первую схему «ИЛИ» и блок изменения признака узла подключен ко входу регистра числа.

Блок-схема устройства приведена на черте25 же, где 1 — вход — начало счета; 2 — триггер начала-останова работы устройства; 3 — переключатель режима работы; 4 — выход — окончание счета; 5 — вход выборки начального адреса; б — регистр начального адреса, фпкси30 рует адрес исследуемого узла области; 7-—

477418 схема совпадения начального адреса, предназначена для занесения начального адреса в регистр блуждания; 8 — регистр блуждания, содержит реверсивные счетчики координат, при этом обеспечивается возможность решения задач в одно-, и двух- и трехмерных областях;

9 — управляемый (1 — и) -полюсник, предназначенный для вероятностного преобразования информации и реализующий закон блуждания частицы по узлам сеточной области;

10 — выход — тактовые импульсы для синхронизации работы устройства; 11 — выходная схема совпадения генератора тактовых импульсов; 12 — генератор тактовых импульсов;

13 — вход, по которому устанавливаются размерности исследуемой области путем переключения выходов (1 — п) -полюсника; 14— вход устройства для задания закона распределения — Р;; — блуждания частицы по узлам сеточной области; 15 — блок, запоминающий закон распределения блуждания частицы по узлам сеточной области; 16 — переключатель, предназначенный для задания режима управления (1 — п) -полюсника; 17 — логический элемент «ИЛИ»; 18 — линия задержки;

19- — вход тактовых импульсов, предназначенный для чтения содержимого МОЗУ; 20— вход в МОЗУ, предназначенный для занесения законов вероятностных переходов, начальных и граничных условий, признаков граничных или внутренних узлов; 21 — выход из

МОЗУ для выдачи результатов на печать;

22 — магнитный оперативный запоминающий блок; 23 регистр числа, предназначенный для организации обмена анализируемой и результирующей информации; 24 — схема совпадения; 25 — суммирующий и усредняющий блок, предназначенный для получения среднего арифметического «веса» по N траекториям, начинающимся с узла, для которого ищется решение; 26 — процессор, вычисляющий дисперсию «веса» и затем определяющий требуемое число испытаний У,р,б, значение которого заносится в управляемый счетчик-делитель;

27 — блок изменения признака узла, предназначен для выработки кода 11, соответствующего признаку граничного узла и маркировки этим кодом узлов, для которых уже найдено решение; 28 — блок анализа признаков узла, представляет собой дешифратор содержимого последних двух разрядов регистра числа, фиксирует окончание построения одной траектории, когда последняя попадает на границу;

29 — логический элемент «ИЛИ»; 30 — управляемый счетчик-делитель. Коэффициент деления задается процессором 26. Счетчик-делитель обеспечивает построения точно N траекторий из данного узла; 31 — вход, предназначенный для установки необходимой точности с заданной вероятностью; 32 вход управляемого счетчика-делителя для установки числа шагов — k при решении параболических задач; 33 — управляемый счетчик-делитель. Коэффициент деления задается по входу 32, включается переключатель 34 при решении

4 параболических уравнений и определяет момент времени, для которого ищется решение;

34 — переключатель режима работы; 35— вход тактовых импульсов на счетчик-делитель 33.

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

«границу» по экспоненте, резко ускоряя процесс решения.

При решении сеточных уравнений устройство работает следующим образом.

После занесения исходных данных в МОЗУ

22 по входам 20 и установки по входу 31 необходимой точности решения с заданной вероятностью,в процессор 26, а при решении параболических задач по входу 32 устанавливается число шагов и в счетчик-делитель 33; по входу 5 устанавливается начальный адрес — хну в регистр 6. По начальному импульсу по входу 1 триггер 2 переходит в единичное состояние и через схемы 11 тактовые импульсы от генератора 12 тактовых импульсов поступают на блоки устройства и с выхода 10 на входы 19 и 35. По приходе начального импульса и начинается работа устройства. Координаты начального узла переносятся в регистр блуждания 8 и затем поступают в МОЗУ 22, где возбуждают соответствующую числовую линейку. Из МОЗУ в регистр числа 23 списываются все данные, относящиеся к данному узлу— харуо. При этом в сумматор 25 поступает начальное значение функции в данном узле (при решении уравнения Пуассона или параболических уравнений). Одновременно в управляемый вероятностный (1 — n)-полюсник 9 списываются значения вероятностей хоуо перехода из узла в соседние узлы. В соответствии с этими вероятностями начинается построение случайной траектории — на одном из выходов (1 — n)-полюсника 9 появляется импульс, определяющий направление перемещения траектории. В следующий тактовый момент времени в регистре 8, таким образом, будет новый адрес — адрес узла, соседнего с начальным. Далее процесс поворяется подобно описанному.

При каждом переходе траектории в новый узел блок 28 анализирует последние два разряда числового регистра. Данная траектория заканчивается, если блоком 28 зафиксирован признак граничного узла (код 11) . Траекто477418

15 рия может закончиться не только на границе, но и в том случае, если она попала в условное поглощающее состояние непосредственно с внутреннего узла. При решении параболических уравнений по «явным» схемам (переключатель 34 включен) траектории может закончиться после k шагов еще до попадания на границу. Во всех перечисленных случаях в счетчик 30 поступает импульс через схему

«ИЛИ» 29, увеличивающий его содержимое на единицу. Одновременно накопившаяся к концу траектории сумма в блоке 25 поступает в процессор 26. Из регистра б затем в регистр блуждания 8 снова переносятся координаты начального узла — хоуо и подобно описанному выше строится новая случайная траектория.

После первых N испытаний процесссор 26 вычисляет, в соответствии с полученными оценками М ((), D""(() и значениями Р, б или

Л, требуемое число испытаний %pea, которое округляет в большую сторону до числа 2 ", где m — число целое. Это значение поступает в устройства 25 и 30. После переполнения счетчика — делителя 30 вычисление функции для узла заканчивается. При этом из блока 25 полученное значение функции записывается через схему совпадения 24 в первые девять разрядов регистра 23, одновременно последние два регистра 23 маркируются единичками, затем возбуждается адрес МОЗУ 22 и числовая информация из регистра 23 переписывается в

МОЗУ по указанному адресу. В дальнейших вычислениях узел хну уже будет выступать в качестве граничного, а вычисленное значение функции в этом узле будет использоваться как граничное. Таким образом, в машине реализуется вероятностный вычислительный метод последовательного сокращения размерности системы. После выполнения всех указанных операций в счетчик 6 прибавляется единица и начинается вычисление значений функции для соседнего с хоуо узлом. Задержанный линией задержки 18 импульс изменения начального адреса в регистре б через схему «ИЛИ» 17 и схему совпадения 7 переписывает новый начальный адрес в регистр блуждания 8. Если этот узел окажется граничным, или вне сеточной области, что будет сразу же отмечено блоком анализа 28, состояние счетчика 6 изменяется до тех пор, пока поиск не приведет снова к внутреннему узлу области. После того, как решение будет найдено для всех узлов внутренной области, информация списывается с

МОЗУ по выходу 21 на печать или в универсальную ЭВМ. Если решение отыскивается не для всех узлов, а только для части их, или для каждого узла, на триггер 2 подается сиг20

55 нал «останов» с регистра 6 или по цепи обратной связи через переключатель 3. (1 — n)-полюсник 9 может управляться по входу 14 через блок 15, в котором запоминается закон распределения блуждания частицы по узлам сеточной области. При подключении блока 15 переключателем 16 на вход (1 — n) -полюсника

9 переключатель 16 также служит для подключения на вход (1 — и)-полюсника регистра числа 23. По входу 13 на (1 — и)-полюсник задаются размерности исследуемой сеточной областии.

Предмет изобретения

Вероятностное устройство для решения конечно-разностных уравнений, содержащее линию задержки, триггер начала-останова работы, вход которого соединен с выходом регистра начального адреса, другой выход которого соединен с одним из входов первой схемы совпадения, выход последней подключен к первому входу регистра блуждания, второй вход которого подключен к управляемому вероятностному (1 — и)-полюснику, а выход — к магнитному оперативному запоминающему блоку, вход управляемого вероятностного (1 — n) -полюсника соединен с выходом второй схемы совпадения, первый выход — с одним из входов первой схемы «ИЛИ», второй выход— с первым переключателем, первый вход первой схемы совпадения подключен к триггеру начала-останова работы, второй вход — к генератору тактовых импульсов, регистр числа, выходы которого соединены с первым переключателем, магнитным оперативным запоминающим блоком, суммирующим и усредняющим блоком и блоком анализа признаков узла, а входы — с магнитным оперативным запоминающим блоком и выходом третьей схемы совпадения, суммирующий и усредняющий блоки, выходы которых подключены к первому входу третьей схемы совпадения и первому входу процессора, второй вход которого соединен с выходом первого управляемого счетчика-делителя, два входа которого подключены соответственно к выходу второй схемы «ИЛИ» и процессору, блок изменения признака узла, отл ич а ю щееся тем, что, с целью повышения быстродействия устройства, выход управляемого счетчика-делителя через линию задержки, вторую схему «ИЛИ» и первую схему совпадения подключен «о входу регистра олуждания, а также ко входу регистра начального адреса и через первую схему «ИЛИ» и блок изменения признака узла подключен ко входу регистра числа.

477418 и 1ä

19 20 Z1

Составитель И. Фирсова

Техред M. Семенов Корректор Е, Хмелева

Редактор Б. Нанкина

Типография, пр. Сапунова, 2

Заказ 2498115 Изд. № 1591 Тираж 579 Подписное

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

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