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

(5) УСТРОЙСТВО для ОБХОДА УЗЛОВ СЕТОЧНОЙ ОБЛАСТИ

1

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

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

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

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

В этом известном устройстве осуществляется последовательный обх(Яч точек по одной координате при фик- сированном значении другой координаты. При достижении первой координатой максимального значения фиксируется следующее соседнее значение второй

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

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

Поставленная цель достигается тем что в устройство, содержащее три счет3gsчика, блок задержки, первый и второй элементы И, первый и второй элементы ИЛИ, первый и второй регистры, группы входов которых являются соответственно первой и второй группами входов устройства, выход первого регистра подключен к первому входу первого блока сравнения, введены второй и третий блоки сравнения, третий, четвертый и пятый элементы ИЛИ, третий, четвертый, пятый и шестой элементы И и два формирователя импульсов, выходы которых подключены соответственно к первым и вторым входам первого и второго элементов ИЛИ, выходвторого регистра подключен к первому входу второго блока сравнения, выход первого элемента ИЛИ соединен с установочными входами первого и второго счетчены соответственно к вторым входам первого и второго блоков сравнения и являются соответственно первой и второй группами выходов устройства, первый вход которого подключен к первому входу третьего элемента И и к установочному входу третьего счетчика, первый выход которого является первым выходом устройства, второй и третий входы которого соединены соответственно с первым и вторым входаг и треть его элемента ИЛИ, выход которого подключен к счетным входам первого и вто рого счетчиков, информационные входы которых соединены соответственно с выходами четвертого и пятого элементов ИЛИ, выход второго элемента ИЛИ подключен к входу блока задержки и к счетному входу третьего счетчика, второй выход которого соединен с первыми входами четвертого и пятого элементов И и с первым входом третьего блока сравнения, первый и второй выходы которого подключены соответственно к первым входам первого и второго элементов И, вторые входы которых соединены с выходом блока задержки, выход первого регистра подключен « второму входу третьего блока сравнения, к первому входу шестого элемента И и к второму входу третьего элемента И, выход первого элемента И соединен с вторыми входами четвертого и шестого элементов И, выходы которых подключены соответственно к первым входам четвертого и пятого Цементов ИЛИ, вторые входы которых соединены с выходом третьего элемента И, выход второго элемента И подключен t к второму входу пятого элемента И, выход которого соединен с третьим входом пятого элемента ИЛИ, третий выход третьего счетчика является вторым выходом устройства. На фиг. 1 представлена блок-схема устройства; на фиг, 2 - сеточная область произвольной формы. Устройство содержит вход 1 Начало счета, формирователь 2 импульсов, элементы ИЛИ 3 и k, вход 5 Установка максимального значения первой координаты, регистр 6, блок 7 сравнения, счетчик 8, элемент ИЛИ 9, элементы И 10--12, блок 13 задержки, выход Ц, Текущее значение первой координаты, вход 15 Конец цикла испытаний, вход 16 Внешняя или граничная точка, элемент ИЛИ 1/, блок 18 сравнения, счетчик 19, выход20 Текущее значение второй координаты, вход 21 Установка максимального значения второй координаты, регистр 22, блок 23 сравнения, счетчик 2, элемент ИЛИ 25, элементы И 26-28, формирователь 29, выход 30 Конец счета, выход 31 Задание алгоритма. В данном устройстве реализуется последовательное применение кода координаты, т.е. обход сеточной области в той последовательности, как показано на фиг. 2. Такой обход области условно будем называть обходом По диагоналям шахматного поля, клетки которого являются узлами сеточной области. Это позволяет осуществить двухступенчатую процедуру вычисления зна чения функции в узлах сеточной области. На первой ступени И1цется решение в узлах области, лежащих, например,на черных диагонаяях шахматного поля, вероятностным методом с заданной точностью. На второй ступени ищется решение в узлах области, лежащих на белых диагоналях шахматного поля, путем усреднения значений решений в соседних (черных) узлах. Кроме того, черные диагонали последовательно рассекают исходную область на подобласти, 4to в свою очередь позволяет на первой ступени вычислительной процедуры значительн( уменьшить среднюю ,длину траектории. Таким образом,общее время решения задачи будет определяться следующим выражением ср. N-t4U,4.i.t |t(Kcp,j- N -t-ft); Р.Ч Отсюда оценка эффективности применения данной процедуры решения задачи без учета уменьшения дисперсии будет определяться выражением n.Kcp..N. т т, сро Поскольку Кср , --frT и Кср/ N то Эф Л; Z-jrT. Уменьшение дисперсии можно оценить только эксперименталь но. Учет уменьшения дисперсии позво ляет на порядок повысить полученную оценку эффективности. Устройство работает следующим об разом. Рассмотрим работу на примере решения задачи для сеточной области, показанной на фиг. 2, где сплошной линией показана граница сеточной области, а пунктирной линией показан прямоугольник, построенный по минимальным и максимальным координатам предграничных узлов области. При этом с целью упрощения устройства максимальную координату меньшей сто роны прямоугольника делаем четной. Предварительно по входу 5 в регистр 6 заносится максимальное значе ние первой координаты (меньшая сторо на прямоугольника), а по входу 21 в регистр 22 заносится сумма максималь ных значений первой и второй (большая сторона прямоугольника) координат. Это позволяет осуществить после довательный выбор диагоналей по всем прямоугольнику, причем, если значе ние счетчика 19 меньше максимального значения первой координаты, то начальная точка диагонали находится на меньшей стороне прямоугольника, в противном случае - на большей стороне прямоугольника. Для формирования значений координат начальных точек диагоналей предлагается использовать последовательности двоичных чисел, равномерно распределенных винтервале (), где m - положительное целое число, m tog(a+b+1), где а и Ь - стороны прямоугольника. Фор мирование такой последовательности можно осуществить с помощью двоичного счетчика, у которого старшие разряды являются младшими и наоборот, а число разрядов равно т, например счетчик 19 (фиг. 1). По импульсу Начало счета по входу 1 счетчик 19 устанавливается в нулевое состояние. Одновременно из регистра 6 в счетчики 8 и 2 заносится максимальное значение первой координаты (точка 1 на фиг. 2). На выходе счетчиков 8 и 2 формируются текущие значения соответственно первой (внешний выход } и второй (внешний выход 20) координат, которые сравниваются схемами 7 и 23 сравнения с их максимальными значениями. Если текущие значения пер- . вой или второй координаты больше максимальных, то на выходе соответствующей схемы cpaвнe tt я появляется ef ничный потенциал, преобразуемый фор мирователями 2 и 29 в импульс. По этому импульсу счетчики 8и 2 устанавливаются в нулевое состояние. Кроме того, этот импульс подается на счетный вход счетчика 19 и через линию 13 задержки разрешает перезапись состояния счетчика 13 в один из счетчиков 8 или 2А в зависимости от результата сравнения схемой 18, Двоичное число счетчика 19 сравнивается с максимальным значением первой координаты схемой 18 сравнения, и, если двоичное число счетчика 19 меньше максимального значения первой координаты, то единичный потенциал появляется на первом выходе схемы 18 сравнения, в противном случае - на ее о втором выходе. Формирование значе-, ния координат следующей точки области осуществляется по импульсу Конец цикла испытаний (внешний вход 15) Или Внешняя или граничная точка (внешний выход 16), поступающего соответственно с выхода счетчика числа испытаний или с выхода блока анализа признаков вероятностного устройства 1, Этот импульс яоступает одновременно на счетные входы счетчиков 8 и 2k, Второй выход счетчика 19 является старшим разрядом и соединен с внешним выходом 31 Задание алгоритма. Появление на этом выходе единичного потенциала соответствует второй ступени, процедуры вычислений. Третий вы-ход счетчика 19 является выходом по переполнению и соединен с внешним выходом 30 Конец счета ; Таким образом осуществляется последовательное изменение кода коорди нат, что позволяет в данном устройст ве реализовать описанный выше способ обхода вычисляемых точек двумерной сеточной области По диагоналям шахматного поля, и мто выгодно отличает данное устройство от прототипа, так как в 2 - раз уменьшается обще среднее время решения задачи во всех точках исследуемой области, где п число вычисляемых точек сеточной области. Это позволяет значительно повысить производительность устройства при решении конечно-разностных уравнений. Так, например, при п 100 производительность вероятностного устройства возрастает в 20 раз. Формула изобретения Устройство для обхода узлов сеточ ной области, содержащее три счетчика блок задержки, первый и второй элементы И, первый и второй элементы ИЛИ, первый и второй регистры, групп входов которых являются соответственно первой и второй группами входов устройства, выход первого регист ра подключен к первому входу Лервого блока сравнения, отличающее с я тем, что, с целью повышения быстродействия, в него введены второй и третий блоки сравнения, третий четвертый и пятый элементы ИЛИ, третий, четвертый, пятый и шестой элементы И и два формирователя импульсов , выходы которых подключены соответственно к первым и вторым входам первого и второго элементов ИЛИ, выход второго регистра по ллючен к пер вому входу второго блока сравнения, выход первого элемента ИЛИ соединен с установочными входами первого и второго счетмиков, выходы которых подключены соответственно к вторым входам первого и второго блоков срав нения и являются соответственно первой и второй группами выходов устройства, первый вход которого подключен к первому входу третьего элемента И и к установочному входу третьего счетчика, первый выход которого является первым выходом устройства, второй и третий входы которого соединены соответственно с первым и вторым входами третьего элемента ИЛИ, выход которого подключен к счетным входам первого и второго счетчиков, информационные входы которых соединены соответственно с выходами четвертого и пятого элементов ИЛИ, выход второго элемента ИЛИ подключен к входу блока задержки и к счетному входу третьего счетчика, второй выход которого соединен с первыми входами четвертого и пятого элементов И и с первым входом третьего блока сравнения, первый и второй выходы которого подключены . соответственно к первым входам первого и второго элементов И, вторые входы которых соединены с выходом блока задержки, выход первого регистра подключен к второму входу третьего блока сравнения, к первому входу шестого элемента И и к второму входу третьего элемента И, выход первого элемента И соединен с вторыми входами четвертого и шестого элементов И, выходы которых подключены соответственно к первым входам четвертого и пятого элементов ИЛИ, вторые входы которых соединены с выходом третьего элемента И, выход второго элемента И подключен к второму входу пятого элемента И, выход которого соединен с третьим входом пятого элемента ИЛИ, третий выход третьего счетчика является вторым выходом устройства. Источники информации, .принятые во внимание при экспертизе 1.Авторское свидетельство СССР № 369580, кл. G 06 G , 1970. 2.Авторское свидетельство СССР № , кл. G 06 F 15/32, 1972, (прототип).

(риг. i