Вероятностное устройство для решения конечно-разностных уравнений Советский патент 1975 года по МПК G06F17/13 G06F17/11 

1

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

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

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

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

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

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

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

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

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

13 - вход, по которому устанавливаются размерности исследуемой области путем переключения выходов (I-д)-полюсника; 14 - вход устройства для задания закона распределения - Pi,i - блуждания частицы по узлам сеточной области; 15-блок, запоминающий закон распределения блуждания частицы по узлам сеточной области; 16 - переключатель, предназначенный для задания режима управления (1-)-полюсника; 17 - логический элемент 18 - линия задержки; 19-вход тактовых импульсов, предназначенный для чтения содержимого МОЗУ; 20 - вход в МОЗУ, предназначенный для занесения законов вероятностных переходов, начальных и граничных условий, признаков граничных или внутренних узлов; 21-выход из МОЗУ для выдачи результатов на печать; 22 - магнитный оперативный запоминающий блок; 23 - регистр числа, предназначенный для организации обмена анализируемой и результирующей информации; 24 - схема совпадения; 25 - суммирующий и усредняющий блок, предназначенный для получения среднего арифметического «веса по N траекториям, начинающимся с узла, для которого ищется решение; 26 - процессор, вычисляющий дисперсию «веса и затем определяющий требуемое число испытаний Лтреб, значение которого заносится в управляемый счетчик-делитель; 27 - блок изменения признака узла, предназначен для выработки кода 11, соответствующего признаку граничного узла и маркировки этим кодом узлов, для которых уже найдено решение; 28 - блок анализа признаков узла, представляет собой дешифратор содержимого последних двух разрядов регистра числа, фиксирует окончание построения одной траектории, когда последняя попадает на границу; 29 - логический элемент 30 - управляемый счетчик-делитель. Коэффициент делеПИЯ задается процессором 26. Счетчик-делитель обеспечивает построения точно Л траекторий из данного узла; 31 -вход, предназначенный для установки необходимой точности с заданной вероятностью; 32 вход управляемого счетчика-делителя для установки числа шагов - k при решении параболических задач; 33 - управляемый счетчик-делитель. Коэффициент деления задается по входу 32, включается переключатель 34 при решении

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

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

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

После занесения исходных данных в МОЗУ 22 по входам 20 и установки по входу 31 необходимой точности решения с заданной вероятностью,в процессор 26, а при решении параболических задач по входу 32 устанавливается число щагов в счетчик-делитель 33; по входу 5 устанавливается начальный адрес - в регистр 6. Ло начальному импульсу по входу 1 триггер 2 переходит в единичное состояние и через схемы 11 тактовые импульсы от генератора 12 тактовых импульсов поступают на блоки устройства и с выхода 10 на входы 19 и 35. По приходе начального импульса и начинается работа устройства. Координаты начального узла переносятся в регистр блуждания 8 и затем поступают в МОЗУ 22, где возбуждают соответствуюшую числовую линейку. Из МОЗУ в регистр числа 23 списываются все данные, относящиеся к данному узлу - ХоУо. При этом в сумматор 25 поступает начальное значение функции в данном узле (при решении уравнения Пуассона или параболических уравнений). Одновременно в управляемый вероятностный (1-я)-полюсник 9 списываются значения вероятностей ХоУо перехода из .узла в соседние узлы. В соответствии с этими вероятностями начинается построение случайной траектории - на одном из выходов (1-л)-полюсника 9 появляется импульс, определяюший направление перемещения траектории. В следующий тактовый момент времени в регистре 8, таким образом, будет новый адрес- адрес узла, соседнего с начальным. Далее процесс поворяется подобно описанному. При каждом переходе траектории в новый узел блок 28 анализирует последние два разряда числового регистра. Данная траектория заканчивается, если блоком 28 зафиксирован признак граничного узла (код 11). Траектория может закончиться не только на границе, но и в том случае, если она попала в условное поглощающее состояние непосредственно с внутреннего узла. Прн решении параболических уравнений по «явным схемам (переключатель 34 включен) траектории может закончр1ться после k шагов еще до попадания на границу. Во всех перечисленных случаях в счетчик 30 поступает импульс через схему «ИЛИ 29, увеличивающий его содержимое на единицу. Одновременно накопившаяся к концу траектории сумма в блоке 25 поступает Б процессор 26. Из регистра 6 затем в регистр блуждания 8 снова переносятся координаты начального узла - и подобно описанному выше строится новая случайная траектория. После первых TV испытаний процесссор 26 вычисляет, в соответствии с полученными оценками УИ (|), iD (g) и значениями §, б или А, требуемое число испытаний , которое округляет в большую сторону до числа 2™, где т - число целое. Это значение поступает в устройства 25 и 30. После переполнения счетчика - делителя 30 вычисление функции для узла заканчивается. При этом из блока 25 полученное значение функции записывается через схему совпадения 24 в первые девять разрядов регистра 23, одновременно последние два регистра 23 маркируются единичками, затем возбуждается адрес МОЗУ 22 и числовая информация из регистра 23 переписывается в МОЗУ по указанному адресу. В дальнейших вычислениях узел уже будет выступать в качестве граничного, а вычисленное значение функции в этом узле будет использоваться как граничное. Таким образом, в машине реализуется вероятностный вычислительный метод последовательного сокращения размерности системы. После выполнения всех указанных операций в счетчик 6 прибавляется единица и начинается вычисление значений функции для соседнего с Xot/o узлом. Задержанный линией задержки 18 импульс изменения начального адреса в регистре 6 через схему «ИЛИ 17 и схему совпадения 7 переписывает новый начальный адрес в регистр блуждания 8. Если этот узел окажется граничным, или вне сеточной области, что будет сразу же отмечено блоком анализа 28, состояние счетчика 6 изменяется до тех пор, пока поиск не приведет снова к внутреннему узлу области. После того, как решение будет найдено для всех узлов внутренной области, информация списывается с МОЗУ по выходу 21 на печать или в универсальную ЭВМ. Если решение отыскивается не для всех узлов, а только для части их, или для каждого узла, на триггер 2 подается сигнал «останов с регистра 6 или по цепи обратной связи через переключатель 3. (1-п)-полюсник 9 может управляться по входу 14 через блок 15, в котором запоминается закон распределения блуждания частицы но узлам сеточной области. При подключении блока 15 переключателем 16 на вход (1-д)-:нолюсника 9 переключатель 16 также служит для подключения на вход (1-/г)-полюсника регистра числа 23. По входу 13 на (1-п)-полюсник задаются размерности исследуемой сеточной области.

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

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

7J

51 35 32

19 20 21