Устройство для обхода сеточной области Советский патент 1984 года по МПК G06F17/13 

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

Известно устройство обхода сеточной области, которое содержит два регистра, три схемы сравнения, три счетчийа, два формирователя, пять элементов ИЛИ, шесть зяементов И и элемент задержки. Это устройство реа лизует так называелелй обход по диагоналям шахматного поля, клетки которого являются узлами сеточной области. Вычисление значения функций в узлах сеточной области осуществляется в два этапа: не первом этапе вероятностным методом ищется решение в узлах области, лежащих например, на черных диагоналях шахматного поля, на втором этапе детерминированным методом ищется решение на белых диагоналях путем усреднения значений функции в соседних черных узлах. Кроме этого, при решении задачи черные диагонали последова.тельно рассекают исходную область на примерно равные подобласти, что, в свою очередь, позволяет значительно сократить общее время решения задали М

Недостатками данного устройства

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

Наиболее близким по технической сущности к данному изобретению является устройство обхода сеточной области, которое содержит два регистра, два блока сравнения, два счетчика, два формирователя импульсов, переключатель режима работы, три элемента ИЛИ, два элемента задержки, при этом первый, второй и третий входы устройства соединены соответственно со входом установки в нуль первого счетчика, со входом первого элемента задержки, со вторым входом третьего элемента ИЛИ; первый второй и третий выходы устройства подключены соответственно к выходу переполнения первого счетчика, че :рез;второй контакт переключателя режима работы - к выходу первого бло ка сравнения, через четвертый контак переключателя режима работы - к выходу второго счетчика и ко второму входу втррого блока сра:внения; выход первого регистра подключен к пер вому контакту переключателя режима работы и к первому входу первого блока сравнения, выход которого соединен со входом первого формирователя импульсов, а выход последнего с первым входом первого элемента ИЛИ} выход второго регистра подключен к третьему контакту переключателя режима работы и к первому входу второго блока сравнения, выход которого соединен со входом второго формирователя импульсов, а выход последнего - со вторым входом первого элемента ИЛИ и с первым входом второго элемента ИЛИ; выход первого элемента задержки подключен ко второму входу второго элемента ИЛИ и к третьему входу первого элемента ИЛИ, выход которого соединен со счетным входом первого счетчика; выход второго элемента задержки подключен к первому входу третьего элемента ИЛИ, выход которого соединен со счетным входом второго счетчика, а вход установки в нуль последнего - с выходом второго элемента ИЛИ.

Это устройство характеризуется |Простотой схемной реализации и сравнительно малым объемом оборудования. В нем осуществляется последовательный обход узлов сеточной области. При этом исходная область, вписанная в прямоугольник, рассекается по меньшей стороне последовательно на равные независимые подобласти, деля каждый раз предыдущую подобласть пополам. Это достигается использованием счетчика по меньшей координате, реализующего последовательность Холтона, равномерно распределенную на интервале , где m - число разрядов счетчика, b - меньшая сторона прямоугольника 2 .

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

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

Поставленная цель достигается тем, что в устройство для обхода сеточной области, содержащее первый регистр, информационный выход которого подключен к первому входу первого блока сравнения, выход которого соединен со входом первого формирователя импульсов, выход которого подключен к первому входу первого элемента ИЛИ, выход которого соединен со счетным входом первого счетчика, информационный выход которого соединен со вторым входом перво.го блока сравнения, информационный выход второго регистра подключен к первому входу второго блока сравнения, выход которого соединен со входом второго формирователя импульсов выход которого подключен ко второму :входу первого элемента ИЛИ и первому входу второго элемента ИЛИ, выход ко торого соединён со входом установки в ноль второго счетчика, информацион ный выход которого является первым информационным выходом устройства и подключен ко второму входу второго блока сравнения, выход первого элемента згщержки соединен с первым входом третьего элемента или, выход которого подключен к счетному входу второго счетчика, информационные .входы первого и второго регистров .являются соответственно первым и вторым информационными входами устройства, вхо; первого элемента задержки и второй вход третьего элемеята ИЛИ являются соответственно входом Конца цикла испытаний и входом Внешнего или граничного узла устройства, выход переноса первого счетчика является выходом Конца счета устройства, а второй вход второго элемента ИЛИ объедийен со входом установки в ноль первого счетчика и является входом начала счета устройства, второй элемент задержки, введены элемент И, элемент НЕ, третий счетчик и триггер, выход которого подключен ко вх ду второго элемента задержки, выход которого соединен со счетным входом третьего счетчика, установочйый вход которого подключен к выходу элемента И, первый вход которого соедииен с выходом элемента НЕ, вход кото рого подключен к выходу первого бло сравнения, второй вход элемента И объединен со счетным входом триггера и подключен к выходу третьего эл мента ИЛИ, выход второго элемента ИЛИ соединен со входом установки в ноль триггера, третий вход элемента И подключен к информационному выходу первого счетчика, выход младшего ра ряда которого является выходом смены алгоритма устройства, а информационный выход третьего счетчика является вторым информационным выходом устройства. На фиг. 1 изображена функциональ ная схема устройства для обхода сеточной области; на фиг. 2 - обход у лов сеточной области произвольной формы. : Схема содержит вход Начало счета 1, выход Конец, счета 2, выход Смена алгоритма 3, информационные входы устройства 4, регистр 5, блок сравнения 6, счетчик 7, элемент И 8 счетчик 9, формирователь импульсов 10, -.элемент ИЛИ 11, элемент НЕ 12 элемент задержки 13, информационные выходы устройства 14, информационные входы устройства 15, регистр 16 блок сравнения 17, формирователь им пульсов 18, счетчик 19, элемент ИЛИ 20, триггер 21, информационные выхо- ды устройства 22, вход Конец цикла испытаний 23, вход Внешний или граничный узел 24, элемент задержки 25 и элемент ИЛИ 26. Устройство реализует обход узлов сеточной области, который обеспечивает двухступенчатую вероятностно.детерми21ированную процедуру роаения конечно-разностных уравнений во всех узлах области. Устройство работает следукяцкм образом. Перед началом работы входом устройства 4 и 15 в первый 5 и второй 16 регистры заносятся значения координат соответственно меньшей и большей стороны прямоугольника, описанного вокруг исследуемой области. По сигналу Начало счета со входа 1 счетчик 7 устанавливается в нуле-; вое состояние. Этот сигнал через элемент ИЛИ 20 поступает на входы установки в нуль счетчика 19 и триггера 21, устанавливая их в нулевое состояние. Нулевые координаты первого узла (фиг.2) поступают на первые 14 и вторые 22 выходы устройства в вероятностное вычислительное устройство, которое анализирует данный узел. Если узел области внутренний, то после цикла из N испытаний вероятностное устройство выдает запрос по входу Конец цикла испытаний 23 на следующий узел. При этом элемент задержки.25 задерживает сигнал запроса на время, необходимое для записи информации по текущему узлу в память вероятностного устройства. ЕСЛИ же узел - граничный или внешний, то вероятностное устройство вы- дает запрос на следующий узел,по входу Внешний или граничный узел 24. (. . В обоих случаях сигнал запроса, проходя через элемент ИЛИ 26, во-первых , поступает на счетный вход счет-/ чика 19, увеличивая его содержимое на единицу, во-вторых, разрешает перепись состояния счетчика 7 при условии, что узел находится в пределах описанного вокруг области прямоугольника, в счетчик 9, в-третьих, этот сигнал поступает на счетный вход триггера 21, изменяя его состояние. Единичный перепад (переход из О в 1) счетного триггера 21 через элемент задержки 13, который задерживает этот перепад на время, необходимое для переписи состояния счетчика 7, в счетчик 9, поступают на счетный вход счетчика 9, увеличивая его содержимое на единицу. Таким образом осу111ествляется . переход из пер- вого узла во вторбй узел .и т.д., ре-. ализуя ступенчатый последовательный выбор координат узлов области (1, 2 3, 4,..., см. фиг.2), которые поступают на первый 14 и вторые 22 выходы устройства. В случае, когда состояние счетчи ка 19 (значение большей координаты) больше или равно состоянию регистра 16 (максимальное значение больиюй координатьт , на выходе блока сравнения 17 появляется единичный по. тенциал, преобразуемый формирователем импульсов 18 в одиночный импульс Он поступает одновременно через элементы ИЛИ 11 и 20 соответственно на счетный вход сЧетчика 7 и на вход установки в нуль счетчика 19. Счетчик 19 устанавливается в нулевое состояние, а счетчик 7, который реализует последовательность Холтона, уве личивает своесодержимое на единицу. Состояние счетчика 7 переписывается по сигналу запроса в счетчик 9 и затем повторяется процесс, который был описан вьшлё. Старшие разряды счетчика 7 переписываются в младшие разряды счетчика 9. На фиг. 2 по казан переход из узла 7 в узел 8, иллюстрирующий этот случай. При изменении состояния счетчика 7 (значения меньшей координаты) на его выходе может появиться не более одного раза подряд значение числа, превышающее максимальное значение меньшей координаты, хранящегося в регистре 5. В этом случае на выходе блока сравнения 6 появляется единичный потенциал, преобразуемый формирователем импульсов 10 в одиночный импульс, который поступает через элемент ИЛИ 11 на счетный вход счетIчика 7, изменяя его состояние. Кроме этогоу единичный потенциал, проходя через элемент НЕ 12, запрещает перепись состояния счетчика 7 в счетчик 9. При появлении в младшем разряде счетчика 7 единицы на выход 3 устройства подаете сигнал Смена алгоритма. Это значит, что обход узлов для первого этапа решения задачи вероятностным методом закончился и начался второй этап решения крнеЧно-разностных уравнений путем усреднения значений функции в соседних (пройденных на первом этапе) узлах. При переполнении счетчика 7 с выхода 2 устройства обхода области подается сигнал Конец счета в вероятностное устройство. Таким образом, данное устройство позволяет при сохранении двухступенчатой вероятностно-детерминированной процедуры решения конечно-разностных уравнений и сокращения оборудования повысить быстродействие в 2 раза. При двухступенчатой процедуре решения на, первом этапе конечно-разностные уравнения решаются в черных узлах вероятностным методом, а на втором этапе в белых узлах путем усреднения значений функции в черных узлах. Известно, что время решения конечно-разностных уравнений на первом этапе значительно больше времени решения на втором этапе, откуда следует, что время решения конечно-разностных уравнений во всех узлах области с применением двухступенчатой процедуры уменьшается примерно в 2 раза по сравнению с изв естными методами. .

УСТРОЙСТВО ДЛЯ ОБХОДА СЕТОЧНОЙ ОБЛАСТИ, содержащее первый регастр, информационный выход которого подключен к первому BXOflir первоrd блока сравнения,выход которого соединен со входом первого формирователя импульсов, выход которого подключен к первому входу первого элемента ИЛИ, выход которого соединен со счетным входом первого счетчика, информационный выход которого соединен со вторым входом первого блока сравнения, информационный выход второго регистра подключен к первому входу второго блока . сравнения, выход которого соединен со входом второго формирователя импульсов, выход которого подключен ко йторому входу первого элемента или и первому входу второго элемента ИЛИ, выход которого соединен со входом установки в ноль второго счетчика, информационный выход которого является первым информационным выходом устройства и подключен ко вторр)му входу, второго блока сравнения, выход первого элемента задержки соединен с первым входом третьего элемента ИЛИ, выход которого подключен к счетному входу второго счетчика, информационные входы первого и второго регистров являются соответственно первым и вторым информационными входами устройства, вход первого элемента задержки и второй вход третьего Элемента ИЛИ являются соот, ветственно входом Конца цикла испйтаний и входом Внешнего или граничного узЛа устройства, выход переноса первого счетчика является выходом Конца счета устройства, а второй вход второго элемента ИЛИ объединен со входом установки в ноль первого счетчика и является входом начала счета устройства,, второй эле-1 мент задержки, отличающеес я тем, что, с целью повышения быстродействия, в него введены элемент И, элемент НЕ, третий счетчик и триггер, выход которого подключен ко входу второго э темента задержкн, выход которого соединен со счетным входом третьего счетчика, установочный вход которого подключен к выходу элемента И, первый вход которо00 го соединен с выходом элемента НЕ, ,вход которого подключен к выходу первогр блока сравнения, второй вход элемента И объединен со счетным i входом триггера и подключен к выходу третьего элемента ИЛИ, выход второго элемента ИЛИ соединен со входом установки в ноль триггера, третий вход элемента И подключен к ин.формационному выходу первого счетчи,ка, выход младшего разряда которого является выходом смены алгоритма устройства, а информационный выход третьего счетчика является вторым . информационным выходом устройства.

fry

гз 14

5

th

909

/7

0Uf.f