Устройство для обхода узлов сеточной области

 

институт им. А.И. Туполева (54) УСТРОЙСТВО ДЛЯ ОБХОДА УЗЛОВ СЕТОЧНОЙ

ОБЛАСТИ

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

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

Однако это известное устройство реализует малоэффективный способ обхода узлов сеточной области.

Наиболее близким по технической сущности к изобретению является вероятностное устройство для решения конечно-разностных уравнений, содержащее триггер, регистры, счетчики генератор тактовых импульсов, weменты ИЛИ, элементы И, блок задержки, блок сравнения, ВВОЗУ, арифметический блок, процессор, дешифратор и, переключатель (2) .

В этом известном устройстве осущест вляется последовательный обх®

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

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

Поставленная цель достигается тем, что в устройство, содержащее три счет3 95508 чика, блок задержки, первый и второй элементы И, первый и второй элементы

ИЛИ, первый и второй регистры, группы входов которых являются соответственно первой и второй группами входов устройства, выход первого регистра подключен к первому входу первого блока сравнения,. введены второй и третий блоки сравнения, третий, четвертый и пятый элементы ИЛИ, третий, 1о четвертый, пятый и шестой элементы И и два формирователя импульсов, выходы которых подключены соответственно к первым и вторым входам первого и второго элементов ИЛИ, выход второго регистра подключен к первому входу второго блока сравнения, выход первого элемента ИЛИ соединен с установочными входами flepBQI и второго счетчиков, группы выходов которых подключены соответственно к вторым входам первого и второго блоков сравнения и являются соответственно первой и второй группами выходов устройства, первый вход которого подключен к первому gg входу третьего элемента И и к установочному входу третьего счетчика, первый выход которого является первым выходом устройства, второй и третий входы которого соединены соответственно с первым и вторым входа«1и треть" его элемента ИЛИ, выход которого подключен к счетным входам первого и второго счетчиков, информационные входы которых соединены соответственно с выходами четвертого и пятого элемен35 .тов ИЛИ, выход второго элемента ИЛИ подключен к входу блока задержки и к счетному входу третьего счетчика, второй выход которого соединен с пер4О выми входами четвертого и пятого элементов И и с первым входом третьего блока сравнения, первый и второй выходы которого подключены соответственно к первым входам первого и второго элементов И, вторые входы кото45 рых соединены с выходом блока задержки, выход первого регистра подключен к второму входу третьего блока сравнения, к первому входу шестого weмента И и к второму входу третьего элемента И, выход первого элемента И соединен с вторыми входами четвертого и шестого элементов И, выходы кото" рых подключены соответственно к первым входам четвертого и пятого элементов ИЛИ, вторые входы которых соединены с выходом третьего элемента И, выход второго элемента И подключен к второму входу пятого элемента И, выход которого соединен с третьим входом пятого элемента ИЛИ, третий выход, третьего счетчика является вторым выходом устройства.

На фиг. 1 представлена блок-схема устройства; на фиг, 2 - сеточная областЬ произвольной формы.

Устройство содержит вход 1 "Начало счета", формирователь 2 импульсов, элементы ИЛИ 3 и 4, вход 5 "Установка максимального значения первой координаты", регистр 6, блок 7 сравнения, счетчик 8, элемент ИЛИ 9, элементы И 10-12, блок 13 задержки, выход 14, "Текущее значение первой координаты", вход 15 "Конец цикла испытаний", вход 16 "Внешняя или граничная точка", элемент ИЛИ 17, блок

18 сравнения, счетчик 19, выход 20

"Текущее значение второй координаты", вход 21 "Установка максимального значения второй координаты", регистр 22, блок 23 сравнения, счетчик 24, элемент ИЛИ 25, элементы И 26-28, формирователь 29, выход 30 "Конец счета", выход 31 "Задание алгоритма"."

В данном устройстве реализуется по" следовательное применение кода координаты, т.е. обход сеточной области в той последовательности, как показано на фиг ° 2. Такой обход области условно будем называть обходом "По диагоналям шахматного поля", клетки которого являются узлами сеточной области. Это позволяет осуществить двухступенчатую процедуру вычисления зна" чения функции в узлах сеточной области. На первой ступени ищется решение в узлах области, лежащих,,например,на "черных" диагоналях "шахматного поля", вероятностным методом с заданной точностью. На второй ступени ищется решение в узлах области, лежащих на "белых" диагоналях "шахматного поля", путем усреднения значений решений в соседних ("черных«) узлах.

Кроме того, "черные" диагонали последовательно рассекают исходную область на подобласти, что в свою очередь позволяет на первой ступени вычислительной процедуры значительн< уменьшить среднюю, длину траектории.

Таким образом, общее время решения

5 9550 задачи будет определяться следующим выражением

Т = — К . М-с — 4 1 и л и, и.

cd

=-,"ь(К,И М+4); переполнению и соединен с внешним выходом 30 "Конец счета".

К,,==, К,, Отсюда оценка эффективности примене- 10 ния данной процедуры решения задачи без учета уменьшения дисперсии будет определяться выражением

> 1 срл М " 2

"/1(1 сР М 41", "ср 4

1 ср "cp» М

Поскольку Ксг„ /К р -(и и К р„° М >р 4, то Эф 2 п. Уменьшение дисперсии можно оценить только эксперименталь- 2О но. Учет уменьшения дисперсии позволяет на порядок повысить полученную оценку эффективности.

Устройство работает следующим об: разом. 25

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

Предварительно по входу 5 в регистр 6 заносится максимальное значение первой координаты (меньшая сторона прямоугольника), а по входу 21 в регистр 22 заносится сумма максимальных значений первой и второй (большая сторона прямоугольника) координат. Это позволяет осуществить последовательный выбор диагоналей по всему прямоугольнику, причем, если значе ние счетчика 19 меньше максимального значения первой координаты, то начальная точка диагонали находится на меньшей стороне прямоугольника, в противном случае — на большей стороне прямоугольника. Для формирования значений координат начальных точек диагоналей предлагается использовать последовательности двоичных чисел, 55 равномерно распределенных в интерва" ле (0-2 -1), где m — положительное целое число, m = J f,од (a+b+1)(, где а и Ь вЂ” стороны прямоугольника. Формирование такой последовательности можно осуществить с помощью двоичного счетчика, у которого старшие разряды являются младшими и наоборот, а число разрядов равно m например счетчик 19 (фиг. 1). По импульсу "Начало счета" по входу 1 счетчик l9 устанавливается в нулевое состояние.

Одновременно иэ регистра 6 в счетчики 8 и 24 заносится максимальное значение первой координаты (точка 1 на фиг. 2) . На выходе счетчиков 8 и 24 формируются текущие значения соответственно первой (внешний выход 14) и второй (внешний выход 20) координат, которые сравниваются схемами 7 и 23 сравнения с их максимальными значениями. Если текущие значения первой или второй координаты больше максимальных, то на выходе соответствующей схемы сравнения появляется единичный потенциал, преобразуемый фор мирователями 2 и 29 в импульс. По этому импульсу счетчики 8 и 24 устанавливаются в нулевое состояние. Кроме того, этот импульс подается на счетный вход счетчика 19 и через линию 13 задержки разрешает перезапись состояния счетчика 19 в один из счет. чиков 8 или 24 в зависимости от результата сравнения схемой 18. Двоичное число счетчика l9 сравнивается с максимальным значением первой координать1 схемой 18 сравнения, и, если двоичное число счетчика l9 меньше максимального значения первой.координаты, то единичный потенциал появляется на первом выходе схемы 18 сравнения, в противном случае - на ее о втором выходе. Формирование значе-, ния коорди на т следующей точки обла сти осуществляется по импульсу "Конец цикла испытаний" (внешний вход 15) ,или "Внешняя или граничная точка" (внешний выход 16), поступающего соответственно с выхода счетчика числа испытаний или с выхода блока анализа признаков вероятностного устройства

Этот импульс поступает одновременно на счетные входы счетчиков 8 и 24.

Второй выход счетчика 19 является старшим разрядом и соединен с внеш" ним выходом 3 1 "Задание алгоритма".

Появление на этом выходе единичноГо потенциала .соответствует второй ступени процедуры вычислений. Третий вы- ° ход счетчика 19 является выходом по

955084

Таким образом осуществляется последовательное изменение кода координат, что позволяет в данном устройстве реализовать описанный выше способ обхода вычисляемых точек двумерной 5 сеточной области "По диагоналям шахматного поля", и что выгодно отличает данное устройство от прототипа, так как в 2 п раз уменьшается общее среднее время решения задачи во всех точках исследуемой области, где и число вычисляемых точек сеточной области. Это позволяет значительно повысить производительность устройства при решении конечно-разностных уравнений. Так, например, при n = 100 производительность вероятностного устройства возрастает в 20 раз.

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

Устройство для обхода узлов сеточной области, содержащее три счетчика, блок задержки, первый и второй эле- ФЗ менты И, первый и второй элементы

ИЛИ, первый и второй регистры, группы входов которых являются соответственно первой и второй группами входов устройства, выход первого регист- Зр ра подключен к первому входу Oepaoro блока сравнения, о т л и ч а ю щ е е-: с я тем, что, с целью повышения быстродействия, в него введены второй и третий блоки сравнения, третий, з четвертый и пятый элементы ИЛИ, тре тий, четвертый, пятый и шестой элементы И и два формирователя импульсов, выходы которых подключены соответственно к первым и вторым входам первого и второго элементов ИЛИ, выход второго регистра под ключен к первому входу второго блока сравнения, выход первого элемента ИЛИ соединен с установочными входами перво -о и 4 второго счетчиков, выходы которых подключены соответственно к в1орым входам первогo и второго блоков сравнения и являются соответственно первой и второй группами выходов устройства, первый вход которого подключен к первому входу третьего элемента И и к установочному входу третьего счетчика, первый выход которого является первым выходом устройства, второй и третий входы которого соединены соответственно с первым и вторым входами третьего элемента ИЛИ, выход которого подключен к счетным входам первого и второго счетчиков, информационные входы которых соединены соответственно с выходами четвертого и пятого элементов ИЛИ, выход второго элемента ИЛИ подключен к входу блока задержки и к счетному входу третьего счетчика, второй выход которого соединен с первыми входами четвертого и пятого элементов И и с первым входом третьего блока сравнения, первый и второй выходы которого подключенысоответственно к первым входам первого и второго элементов И, вторые входы которых соединены с выходом блока задержки, выход первого регистра подключен к второму входу третьего блока сравнения, к первому входу шестого элемента И и к второму входу третьего элемента И, выход первого элемента И соединен с вторыми входами четвертого и шестого элементов И, выходы которых подключены соответственно к первым входам четвертого и пятого элементов ИЛИ, вторые входы которых соединены с выходом третьего элемента И, выход второго элемента И подключен к второму входу пятого эле. мента И, выход которого соединен с третьим входом пятого элемента ИЛИ, третий выход третьего счетчика является вторым выходом устройства.

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

1. Авторское свидетельство СССР

N 369580, кл. G 06 G 7/48, 1970.

2. Авторское свидетельство СССР

М 477418, кл, G 06 F 15/32 1972, (прототип) .

955084

0 rout num

Составитель В. Рыбин редак ор С. Тараненко Техред М.Тепер

Корректор А. Гриценко

Тираж 731 Подписное

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

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

Филиал ППП "Патент", г..ужгород, ул. Проектная, 4