Вероятностное устройство для решения уравнения Лапласа Советский патент 1983 года по МПК G06F17/11 

устройства, а выход соединен с управлякс им входом управляемого счетчика, о тличаюцее с я тем, что, с целью повышения быстродействия, оно дополнительно содержит блок сравнения, группу блоков сравнения, счетчик, группу регистров, четвертый пятый и шестой элементы Н, второй элемент ШВ1, элемент НЕ, причем третий вход блока задания координат узлов подключен к пусковому входу устройства, а третий выход соединен с первым входом блока сравнения, второй вход котррого соединен с первым входом первого блока сравнения группы и в.ыхОном счетчика, а выход соединен со счетным входом счетчика, входы регистров группы и счетчика являются входом запуска устройства, выход кавдого Из регистров группы соединен с первым входом последуйдаго блока сравнения группы, выходы блоков сравнения группы соединены с входами пятого элемента Н, выход которого соединен с входом элемента НЕ, и первым входом четвертого элемента Н, второй вход четвертого элемента И подключен к выходу первого элемента И, а выход соединен с первым входом второго элемента Ш01, второй вход которого соединен с третьим выходом блока оперативной памяти, а выход с«третьим входом управляемого вероятнортного (l-n)-полесника, выход регистра блуждания соединен с вторыми входами блоков сравнения группы и первым входом гаест/ого элемента И, второй вход которого соединен с выходом элемента НЕ, а выход соединен с третьим входом блока оперативной памяти.

2.. Устройство по П.1, о т л и ч аю DI е е с я тем, что блок задания координат узлов, содержащий первый, второй и третий счетчики, первый и второй регистры и элемент Н, причем выход первого счетчика является первым выходом блока, а первый вход соединен с входом первого регистра и является первым входом блока, выход первого регистра соединен с первым входом второго регистра, выход которого соединен с вторым входом первого счетчика и первыми входами третьего счетчика и элемента И, первый вход второго счетчика является вторым входом блока, второй вход соединен с выходом элемента И, а выход является вторым вькодом блока, второй вход третьего счетчика соединен с вторым входом элемента И и является третьим взсодом блока, а выход соединен с вторым входом второго счетчика и является третьим выходом блока.

3. Устройство по п.1, о т л и ч аю щ е ее я тем, что блок определения требуемого- числа испытаний содержит дисперсиометр и умножитель, выход которого является выходом блока, а первый вход соединен с выходом дисперсиометра, nepBi ril и второй входы дисперсиометра являются соответственно первым и вторым входами блока, а второй вход угдаожителя является третьим входом блока.

1. ВЕРОЯТНОСТНОЕ УСТРОЙСТВО ДЛЯ 1 Е1:1ЕН11Я УРАВНЕНИЯ ЛАПЛАСА, содержав;ее триггер, единичный вхчц которого является пусковым входом устройства, первый элемент И, первый иход коi.Toporo соединен с вьтодом триггера, генератор тактовых (лмлульсов, выход . которого соединен с вторым входом первого элемента И, переключатель, выход котпвого соединен с входом сброса триггера, блок постоянной и.чмяти, вход которога является входом задания закона распределения устройства, блок- задания координат узлов, первый вход которого является входом установки начального адреса устройства, а первый выход соединен с нулевым входом триггера и является выходом окончания счета устройства, второй элемент И, первый вход которого соединен с вторым выходом блока задания координат узлов регистр блуждания, первый вхох; которого соединен с выходом ьторого элемента И, управляемый вероятностный

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

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

Недостатком устройства является низкое быстродействие,

Наиболее близким по технической супщости к предлагаемому является вероятностное устройство для решения конечно-разностных уравнений. содержащее линию задержки, выход которой подключен через первый элемент И к второму входу первого элемента Н, триггер начала-останова работы, вход которого соединен с выходом регистра стартового адреса, другой выход которого соединен с первым входом первого элемента И выход пос леднего подключен к первому входу ре гистра блуждания, второй в.ход кото- рого подключен к первому выходу упра ляемого вероятностного (1-п)-полюсника, а выход - к оперативному запоминаюо ему блоку, первый вход управляемого вероятностного |l f J noлюсника соединен с вторым переключателем, второй выход подключен к первому Входу второго элемента ШШ, первый вход второго элемента И подключен к триггеру начала-останова ра боты, второй вход - к генератору тактовых импульсов, регистр числа, в ходы которого с зон вероятностей перехода, начальных и гранйчяьгк условий, признаков узла и рё гистгра числа в целом подкл Яе4ш соответствен но к второму пёрёкЛючатгелю, пер /вому входу суямйрующе гЬ и: усредняю/вщто QnoKSk, к .блоку анализа признаkbs узла и к оперативйОмУ:запоминайщему блоку, а выхода} StiH начальных и граничш)1Х условий признаков узла и в:сего регистра в цейрм соединены Сботвётственйо е вуходой третьего эле.мента М,в,ыходом блока изменений признаков узла и дпера тивным з апоминаквдим блоком Ьуммйрунвдий и усред.няющий блок, йвтрвый и второй выходы ко торс го подкш че1Ш соо тветственно к иервоку входу третBeiO элемента И и niepBOMy входу вррцессгора, второй вхо которого соедйпжен с первым выходом ; nepsoro управляемого счетчика-делителя, rtepewft вход которого подключен к выходу процессора, а второй выход через первый переключатель - к триггеру начала останова, а также к входу регистра стартового адреса, постоянный запоминающий блок, выход которого подключен к второму переключателю, второй управляющий счетчикделитель, выход которого через трети переключатель подключен к третьему входу второго элемента ILTII, второй вход которой подключен к выходу блока анализа признаков узла .2j, В известном устройстве для решения уравнения Лапласа моделируются траектории случайного блуждания из исследуемого узла до попадания на границу сеточной области. При этом на каждом шаге блуждйния осувествляется обращение в блок оперативной памяти для того, чтобы проверить является ли очередной узел траектории граничным. Так как дйя считывания из памяти требуется несколько тактов работы устройства, то это существенно увеличивает время решения задачи и снижает быстродействие устройства. Цель изобретения - повышение бы стродействия. Поставленная цель дocтиfaeтcя тем, что вероятностное устройство для решения уравнения Лапласа, содержащее триггер, единичный вход которого является пусковым входом устройства, первый элемент И, первый вход которого соединен с выходом триггера, генератор тактовых импульсов, выход которого соединен с вторым входом Первого элемента И, переключатель, выход которого соединен с входом сброса триггера, блок постоянной памяти, вход которого является входом задания закона распределения устройства, блок задания координат узлов, первый вход которого является входом установки начального адреса устройства, а первый выход соединен с нулевым входом триггера и является выходом окончания счета устройства, второй элемент И, первый вход которого соединен с вторым выходом блока задания координат узлов, регистр блуждания, первый вход которога соединен d выходом второго элемента И, управляемый вероятностньА {1-п)-полюсник, первый вход которого является входом установки размерности области устройства, второй вход соединен с выходом блока постоянной памяти, а выход - с вторым входом регистра блуждания, первый элемент ШШ, первый вход которого подключен к пусковому входу устройства, а выход соединен с вторым входом второго элемента Н, элемент задержки, выход которого соединен с вторым входом первого элемента ИЛИ, блок оперативной памяти, первые вход и выход которого являются.соответственно информационным входом и информационным выходом устройства, а тактовый вход соединен с выходом первого элемента И, регистр информации, первые вход и выход которого соединены с вторьми соответственно выходом и входом бло- ка оперативной памяти, блок усреднения, вход которого соединен с вторым выходом регистра информации, тре тий элемент И, первый вход которого соединен с первым выходом блока усредкения, а выход - с вторым входом регистра информации, управляемый счетчик, счетный вход которого соединен с третьим входом первого элемента ИЛИ и подключен к третьему выходу регистра информации а выход переполнения соединен с входами переключателя и элемента задержки, с вторыми входами третьего элемента И и блока задания координат узлов и третьим входом регистра информации, блок определения требуемого числа ис пытаний, первый вход которого соединен с вторым выходом блока усреднения, второй вход - с информационным выходом управляемого счетчика, трети вход является входом установки степени точности устройства, а выход соединейс управляющим входом управляемого счетчика, дополнительно содержит блок сравнения, группу блоков сравнения, счетчик, группу регистров четвертый, пятый и шестой элементы И второй элемент ИЛИ, элемент НЕ, причем третий вход блока задания координат узлов подключен к пусковому входу устройства, а третий выход сое динен с первым входом блока сравнения, второй вход которого соединен с первым входом первого блока сравне НИН группы и выходом счетчика, а выход соединен со счетным входом счетчика, входы регистров группы и счетчики являются входом запуска устройства, выход каждого из регистров гру пы соединен с первым входом последую щего блока сравнения группы, выходы блоков сравнения группы соединены с входами пятого элемента И, выход которого соединен с входом элемента НЕ и дервым входом четвертого элемента И,, второй вход четвертого элемента И подключен к выходу первого элемента И, а выход соединен с цервым входом второго элемента ШЖ, вто рой вход которого соединен с третьим выходом блока оперативной памяти, а вь1ход - с третьим входом управляемог вероятностного (1-ь}-полюсника, выхо регистра блуждания соединен с вторыми входами блоков сравнения группы и первым входом шестого элемента И, второй вход которого соединен с выхо дом элемента НЕ, а выход соединен с третьим входом блока оперативной памяти. Блок задания координат узлов содержит первьш второй и третий счетчики, первый и второй регистры и элемент И, причем выход первого счетчика является первым выходом блока, а первый вход соединен с входом первого регистра и является первым входом блока выход первого регистра соединен с первым входом второго регистра, выход которого соединен с вторым входом первого счетчика и первыми входами третьего счетчика и элемента И, первый вход второго счетчика является вторым входом блока, вторс й вход соединен с выходом элемента И, а выход является вторым выходом блока, второй вход третьего счетчика соединен с вторым входом элемента И и является третьим входом блока. а выход соединен с вторым входом второго счетчика и является третьим выходом блока. Блок определения требуемого числа испытаний содержит дисперсиометр и умножитель, выход которого является выходом блока, а первый вход соединен с выходом дисперсиометра, первый и второй входы дисперсиометра являются соответственно первым и вторым входа1ми блока, а второй вход умножителя является третьим входом блока, На фиг. .1 приведена блок-схема устройства; на фиг. 2 - схема блока задания коор динат узлов; на фиг. 3 схема блока вычисления требуемого числа ист.1таний. Устройство содержит переключатель 1, пусковой вход 2, триггер 3, первый элемент И 4, генератор 5 тактовых импульсов, вход 6 задания закона распределения, блок 7 постоянной памяти, выход 8 окончания счета, вход 9 установки размерности области, четвертый элемент И 10, вход 11 установки начального адреса, блок 12 задания координат узлов, второй элемент И 13 регистр 14 блуждания, управляемый вероятностный (1-пJ-полюсник 15, второй элемент ШШ 16, вход 17 запуска устройства, блок-18 сравнения, счетчик 19, группу 20 регистров, группу 21 блоков сравнения, шестой элемент 22, элемент НЕ 23, пятый элемент И 24, первый элемент liflH 25, элемент 26 задержки, информационный выход 27 устройства, информационный вход 28 710 устройства, блок 29 оперативной памяти (liOII ), регистр 30 информации, блок 31 усреднения, третий элемент И 32, управляемый счетчик 33, блок 34 определения требуемого числа испытаний, вход 35 установки степеии точности устройства. Клок 12 задания координат узлов содержит первый счетчик 36, первый и второй регистры 37 и 38, второй 39 и третий 40 счетчики, элемент И 41, Клок 34 содержит дисперсиометр 42 и умножитель A3. Единичный вход триггера 3 соединен с пусковьм входом 2 устройства и с первым входом первого элемента . ИЛИ 25, а-нулевой вход - с первым вы ходом блока 12 и выходом 8 окончания счета устройства, первый вход блока 12 подключен к входу 11 установки начального адреса устройства, а второй вход соединен с третьим входом регистра 30 информации, с вторым вхо дом третьего Элемента Н 32, с выходо переполнения управляемого счетчика 33, с входом элемента 26 задержки и с входом переключателя 1, выход которого соединен с входом сброса триг гера 3, выход триггера соедршен с пе вым входом первого элемента И 4, к второму входу которого подключен генератор 5 тактовых импульсов. Выход первого элемента Н 4 подключен к так товому входу блока 29 оперативной па мяти. Вход блока 7 постоянной памяти соединен с входом 6 задания закона распределения устройства, а выход с .вторьи входом управляемого вероятнос него (1-.П )-полюсник 15, первый вхо которого подключен к входу 9 установки размерности области, а выход с вторым входом регистра 14 блуждани Второй выход блока 12 подключен к первому входу второго элемента , выход которого соединен с первым вхо дом регистра 14 блуждания, а второй вход - с выходом первого элемента ШБ1 25, второй вход первого элемента ИЛИ 25 подключен к выходу элемента 26 задержки, а третий вход соединен с третьим выходом регистра 30 информации и со счетным входом управляемо го счетчика 33, управляющий вход и информационный выход которого подключены соответственно к выходу и вт рому входу блока 34 определения требуемого числа испытаний. Первый вход блока 34 определения требуемого числа испытаний соединен с вторым выхо6дом блока 31 усреднения, а третий вход - С входом 35 установки степени точности устройства. Первые вход и выход блока 29 оперативной памяти подключены соответственно к информационному входу 28 и информационному выходу 27. устройства, а вторые вход и выход блока 29 оперативной памяти соответственно к первым выходу и.входу регистра 30 информации, второй выход которого соединен с входом блока 31 усреднения. Первый въ1ход блока 3I усреднения подключен к первому входу третьего элемента И 32, выход которого соединен с вторым входом регистра 30 информации. Второй вход четвертого элемента И 10 соединен с выходом первого элемента И 4, а выход с первым входом второго управляемого вероятностного (l-hj-полюсника 15, а второй вход - к третьему выходу блока 29 оперативной памяти. Третий вход блока 12 - соединен с единичным входом триггера 3, а третий выход - с первым входом блока 18 сравнения. Вход 17 устройства подключен к первым входам счетчика 19 и регистров группы 20. Выходы счетчика 19 и регистров группы 20 подключены к первым входам блоков сравнения группы 21, Выходная шина регистра 14 блуждания соединена с вторыми входами блоков сравнения группы 21 и с входной шиной шестого элемента И 22. Выходы блоков сравнения группы 21 подключены к входам пятого элемента И 24, выход которого соединен с первым .входом четвертого элемента И 10 и с входом элемента НЕ 23, а выход элемента НЕ 23 подключен к входу шестого элемента И .2, Выход шестого элемента И 22 соединен с третьим входом блока 29 оперативной памяти. Выход и второй вход блока 18 сравнения подключены соответственно к счетному входу и выходу счетчика 19. li блоке 12 задания координат узлов выход второго регистра 38 соединен с вторым входом первого счетчика 36 и первыми входами третьего счетчика 40 и элемента И 41. Выход элемента И 41 соединен с вторым входом второго счетчика 39, выход которого соединен с вторым входом второго регистра 38 и вьгходом третьего счетчика 40, Выход первого регистра 37 соединен с первым входом BTOpoixi регистрп 38. Входами блока 12 задания координат узлов являются соответственно: первым - первый вход первого счетчика 36 и вход первого регистра 37; вторым - первый вход второго счетчика 39; третьим - вторые входам третье го счетчика 40 и элемента И 41 Выходами блока 12 задания координат узлов являются соответственно: первым - выход первого счетчика 36; вторьМ - выход эторого счетчика 39; третьим - выход третьего счетчика40 .Предлагаемое устройство обеспечивает возможность быстрого построения случайного блуждания внутри прямоугольника, вписаниого в сёточную область произвольной форныу что позволяет значительно повысить быстродейств1 е решения уравнения Лапласа методом lfoHTfe-Карло, При решении уравнения Лапласа уст ройство работает следующим образом. Перед началом вычисления в блок 29 оперативной памяти (БОП) по входу 28 устройства заносятся исходные дан ные - признаки узла и значения функции в граничных узлах, по входу 6 в блок 7 постоянной памяти ХВЛП) заносятся вероятности перехода теку- . щего узла сеточной области в соседние в виде функции распределтенйя, по 9 устанавливается размерность исЬледуемой области, по входу 11 в бло/к 12 заносятся максимальнью координаты узлов сеточной области, по входу 35 в блоке 34 вычисления требуемого числа испытаний устанавливается необходимая точность решения (сГ)с заданной вероятностью ( (Ь)- По входу 17 в регистры группы 20 счетчик 19 заносятся координаты X, У границ прямоугольника, вписанного в сеточную область произвольной форм . В счетчик 19, У, (например У в регистр 20 т группы 20, , Х в регистры 20, 20, группы 20). Пус ковой импульс по входу 2 переводит триггер 3 в единичное состояние, устанавливает координаты начального уз ла блока 12, открывает элемент И 13, Тактовые импульсы с генератора 5 нач иают поступать на блоки устройства через открытый элемент Н 4. Координаты начального узла через открытый элемент Н 13 поступают на регистр 14 блуждания и затем поступают на вторые входы блоков сравнения группы 21 на первые входы которых поступают координаты вписанного прямоугольника Если координаты узла в регистре 14 находятся вне вписанного прямоугольника, то хотя бы на одном блоке сравнения появится сигнал логического О, которы1ч поступает на злемент И 24 и образует на его выходе логический О. Этот сигнал закрывает элемент И 10 и, проходя через элемент НЕ 23 открьшает злемент И 22. Координаты узла с регистра 14 блуждания через открытый элемент U поступают в блок 29, к по тактовым импульсам с выхода элемента И 4 осуществляется цикл считывания информации на регистр 30 информации. После окончания цикла чтения блок 29 выдает сигнал Конец чтения. Этот сигнал поступает через элемент ШЩ 16 на управляемый вероятностный (l-i)полюсник 15, на другой вход которого из блока 7 постоянной памяти поступают значения вероятностей перехода в соседние узлы - осуществляется розыг рьш очередного узла траектории случайного блуждания, т.е. на одном из выходов управляемого вероятностного {1-Г|)-полюсника 15 появляется импульс, определяющий направление перемещения траектории. Этот импульс вьпсода вероятностного {l-h)полюсника 15 поступает в регистр 14 блуждания, где образуются координаты нового узла. Эти координаты вновь поступают на блоки сравнения группы 21 ЕСЛИ они находятся внутри вписанного в сеточную область прямоугольника, то на выходах блоков сравнения зафиксируются сигналы логической 1 а значит иа вькоде элементов 21 и 24 образуется логИческий сигнал 1 который Проходя через элемент НЕ 23, закрывает элемент И 22 запрещая тем самым обращение в память. Этот же сигнал логической 1 откры;8ает элемент И 0, и тактовый импульс с выхода элемента 4 проходит Через элементы И 10 и ИЛИ 16 на вход управляемого вероятностноro(l-n) -полюсника 15 - осуществляется - розыгрьш очередного узла траектории и т,д, На фиг, 3 приведена временная диаграмма работы блоков 3,5 16, 22, 24, 25 устройств, f - время, иеобкоди$1ое для одного перехода из узла, находящегося виутри вписанного прямоугольника, а время, необходимое для одного перехода.траектории из узла, находящегося вне описанного прямоугольника. Из диаграммы видно, ЧТО время f равно периоду по торения тактовых импульсов, а нескольким тактам,например 6 Г . При чтении из блока 29 на регистр 30 информаш1И поступает следующая информация: признак узла (внутренний, внешний или граничный ) и значение функции, если узел граничный. В этом случае код граничного узла 1 посту пает в управляемый счетчик 33, увеличивая содержимое его на единицу. Этот сигнал проходит через элемент ШШ 25 и открьгоает элемент И 13. Одновременно граничное значение функции поступает в блок 31 усреднения. Затем из блока 12 через открытый элемент 13 в регистр 14 блуждания снова переписываются координаты начального узла и начинается построение новой траектории. После N пробных испытаиий блок 34 вычисления требуемого числа испытаний вычисляет в соответствии с полученными оцен ками математического ожидания и дисперсии функции и значениями сЛ и /3 требуемое число испытаний N, которое округляется в большую сторону до числа 2 , где m - целое число. Это значение поступает в управляемый сче чик 33, После переполнения управляемого счетчика 33 вычисление функции для узла заканчивается. По сигналу переполнения из блока 31 полученное значение функции записывается через элемент 32 в регистр 30 информации, в последний разряд регистра 30 Информации записывается код 1. Затем возбуждается адрес блока 29 и информация из регистра 30 переписывается в блок 29 по указанному адресу. Этот же сигнал поступает на вход блока 12, которуй реализует построчный обход области. Блок 12 работает следующим образом(фиг.2 ). Перед началом вычислений в счетчик 36 заносится максимал ;Иое значение ординаты вписанного во руг- исследуемой области прямоугольника в дополнительном коде, а, в регистр 37 заносится максимальное зна чеине абсциссы этого прямоугольника По сигналу Пуск с входа 2 устройства счетчики 39 и 40 устанавливают в исходное состояние (например, в н левое состояние ). С выходов этих .учетчиков выдаются координаты начал .кого узла траекторий. Эти выходы объединяются в шину, которая подключается к элементу 13. Кроме того, выход счетчика 40 соединяется с первым вхо дом блока 18 сравнения, на второй вход которого поступают значения минимальной, ординаты вписанного в сеточнум область прямоугольника (Vmm) со счетчика 19. Если У: больше то блок 18 сравнения вццает сигнал, . который увеличивает содержиьюе счетчика |9 на единицу, т.е. в .счетчике 19 образуется значение ординаты Такая процедура позволяет проводить построчное сокращение размерности исследуемой области. После того, как уже вычислено значение функции для одного узла, по сигналу от счетчика 33 увеличивается содержимое счетчика 39. Таким образом, образуются координаты следующего стартового узла и т.д. Как только абсцисса стартовых узлов превысит ее максимальное значение, которое хрв нится в регистре 37, так сразу же регистр 38 выдает сигнал, который, проходя через элемент 41 Н, устанавливает счетчик 39 в исходное (нулевое )состояние, увеличивает содержимое счетчика 40 на единицу (переход на следующую строку узлов сеточной области), а также увеличивает содержимое счетчика 36 на единицу и т.д. Завершение работы устройства происходит по сигналу переполнения со счетчика 36, по которому триггер 3 устанавливается в нулевое состояние. Блок 34 определения требуемого числа испытаний включает в себя (фиг.4 дисперсиометр 42 и умножитель 43. Требуемое число испытаний N-j-p вычисляется по формуле N. D t/3/cr Оценка дисперсии D находится с помощью дисперсиометра после построения первых 50-100 траекторий случайного бл гжда- НИН из стартового узла, которая затем умножается в умножителе 43 на коэффициент t /} надежности и точ- ности вычисления, задаваемый по внешнему входу устройства. Предлагаемое устройство, реализующее описанную выше процедуру репения уравнения Лапласа, отличается меньшим общим временем решения задачи. В устройстве реализуется общее время решения задачи,быстрое построение за один такт работы устройства траектории случайного блуждения внутри вписанного в сеточную область прямоугольника. От Н J

Н S/foHtf ЛЗ ф«г2

ф«гЗ Ьлона 33 2 /i блонд f 8 0