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

(5 Й) УСТРОЙСТВО ДЛЯ ОБХОДА УЗЛОВ СЕТОЧНОЙ ОБЛАСТИИзобретение относится к вычислительной технике и может быть использовано в вероятностных устройствахдля решения конечно-разностных уравнений,Известно устройство для моделирования гидрофизических полей, содержащее блок памяти, регистры, счетчики, триггеры, блоки ввода и вывода,.генератор тактовых импульсов, переключатель режима работы, сумматор,элементы И и ИЛИ 1 .Однако это известное устройствореализует малоэффективный способ обхода узлов сеточной области.Наиболее близким по техническойсущности к изобретению является вероятностное устройство для решенияконечно-разностных уравнений, содержащее триггер, регистры, счетчикигенератор тактовых импульсов, элементы ИЛИ, элементы И, блок задержки, блок сравнения, ВВОЗУ, арифметический блок, процессор, дешифратор и,переклочатель 2 .В этом известном устройстве осуществляется последовательный обход 5точек по одной координате при фик-,сированном значении другой координаты. При достижении первой координатоймаксимального значения фиксируетсяследующее соседнее значение второйкоординаты и вновь последовательноизменяется значение первой координаты,Данная процедура повторяется до техпор, пока вторая координата не достигает своего максимального значе ния. Такой способ обхода области существенно увеличивает время решенияконечно-разностных управнений длявсех точек области.Цель изобретения - сокращение вре мени решения конечно-разностных уравнений для всех точек области.Поставленная цель достигается тем,что в устройство, содержащее три счет3 95508 цика, блок задержки, первый и второй элементы И, первый и второй элементы ИЛИ, первый и второй регистры, группы входов которых являются соответственно первой и второй группами входов устройства, выход первого регистра подключен к первому входу первого блока сравнения,. введены второй и третий блоки сравнения, третий, четвертый и пятый элементы ИЛИ, третий, 1 о четвертый, пятый и шестой элементы И и два формирователя импульсов, выходы которых подключены соответственно к первым и вторым входам первого и второго элементов ИЛИ, выход второго 1 Б регистра подключен к первому входу второго блока сравнения, выход первого элемента ИЛИ соединен с установочными входами первого и второго счетчиков, группы выходов которых подключены соответственно к вторым входам первого и второго блоков сравнения и являются соответственно первой и второй группами выходов устройства, первый вход которого подключен к первомувходу третьего элемента И и к установочному входу третьего счетчика, первый выход которого является первым выходом устройства, второй и третий входы которого соединены соответственно с первым и вторым входа 4 и треть" его элемента ИЛИ, выход которого подключен к счетным входам первого и второго счетчиков, информационные входы которых соединены соответственно с выходами четвертого и пятого элемен 35 тов ИЛИ, выход второго элемента ИЛИ подключен к входу блока задержки и к счетному входу третьего счетчика, второй выход которого соединен с пер 4 О выми входами четвертого и пятого элементов И и с первым входом третьего блока сравнения, первый и второй выходы которого подключены соответственно к первым входам первого и второго элементов И, вторые входы кото 43 рых соединены с выходом блока задержки, выход первого регистра подключен к второму входу третьего блока сравнения, к первому входу шестого элемента И и к второму входу третьего элемента И, выход первого элемента И соединен с вторыми входами четвертого и шестого элементов И, выходы кото" рых подключены соответственно к первым входам четвертого и пятого элементов ИЛИ, вторые входы которых соединены с выходом третьего элемента И, выход второго элемента И подключен к второму входу пятого элемента И,выход которого соединен с третьимвходом пятого элемента ИЛИ, третийвыход, третьего счетчика является вторым выходом устройства,На фиг. 1 представлена блок-схема устройства; на фиг, 2 - сеточная область произвольной формы. Устройство содержит вход 1 "Начало счета", формирователь 2 импульсов, элементы ИЛИ 3 и ч, вход 5 "Установка максимального значения первой координаты", регистр 6, блоксравнения, счетчик 8, элемент ИЛИ 9, элементы И 10-12, блок 13 задержки, выход 1, "Текущее значение первой координаты", вход 15 "Конец цикла испытаний", вход 16 "Внешняя или граничная точка", элемент ИЛИ 17, блок 18 сравнения, счетчик 19, выход 20 "Текущее значение второй координаты", вход 21 "Установка максимального значения второй координаты", регистр 22, блок 23 сравнения, счетчик 2, элемент ИЛИ 25, элементы И 26-28, формирователь 29, выход 30 "Конец счета", выход 31 "Задание алгоритма". В данном устройстве реализуется по" следовательное применение кода координаты, т.е. обход сеточной области в той последовательности, как показано на фиг2. Такой обход области условно будем называть обходом "По диагоналям шахматного поля", клетки которого являются узлами сеточной области, Это позволяет осуществить двухступенчатую процедуру вычисления зна" чения функции в узлах сеточной области. На первой ступени ищется решение в узлах области, лежащихнапример,на "черных" диагоналях "шахматного поля", вероятностным методом с заданной точностью. На второй ступени ищется решение в узлах области, лежащих на "белых" диагоналях "шахматного поля", путем усреднения значений решений в соседних (черных) узлах. Кроме того, "черные" диагоналипоследовательно рассекают исходнуюобласть на подобласти, что в своюочередь позволяет на первой ступенивычислительной процедуры значительнуменьшить среднюю, длину траектории.Таким образом, общее время решения5 9550задачи будет определяться следующимвыражениемТ = - К М с - 41и л П л,сК мирование такой последовательностиможно осуществить с помощью двоичного счетчика, у которого старшие разряды являются младшими и наоборот, а число разрядов равно а, например= 2" (сР+4)1 1КР Рт К РОтсюда оценка эффективности примене ния данной процедуры решения задачи без учета уменьшения дисперсии будет определяться выражениемн Ксрл2р пЬ 1,кср НФ 4, Кср 41 ср с)ПосколькУ КсрЛср Р и К ср 1 1то Эф2.1 п. Уменьшение дисперсииможно оценить только эксперименталь Оно. Учет уменьшения дисперсии позволяет на порядок повысить полученнуюоценку эффективности.Устройство работает следующим об: разом, 25Рассмотрим работу на примере решения задачи для сеточной области,показанной на фиг. 2, где сплошной линией показана граница сеточной . области, а пунктирной линией показан прямоугольник, построенный по минимальным и максимальным координатам предграничных узлов области, При этом с целью упрощения устройства максимальную координату меньшей сто 35 роны прямоугольника делаем четной,Предварительно по входу 5 в регистр б заносится максимальное значение первой координаты (меньшая сторона прямоугольника), а по входу 21 врегистр 22 заносится сумма максимальных значений первой и второй (большая сторона прямоугольника) координат. Это позволяет осуществить последовательный выбор диагоналей по всемупрямоугольнику, причем, если значе-ние счетчика 19 меньше максимальногозначения первой координаты, то начальная точка диагонали находится наменьшей стороне прямоугольника, в противном случае - на большей сторо" не прямоугольника. Для формированиязначений координат начальных точек диагоналей предлагается использовать последовательности двоичных чисел,55 равномерно распределенных в интерва" ле (0-2 -1), где ш - положительное целое число, щ =1 од (а+Ь+1), где а и Ь - стороны прямоугольника. Форсчетчик 19 (фиг. 1). По импульсу "Начало счета" по входу 1 счетчик устанавливается в нулевое состояние.Одновременно иэ регистра 6 в счетчики 8 и 24 заносится максимальное значение первой координаты (точка 1 на фиг. 2). На выходе счетчиков 8 и 24 формируются текущие значения соответственно первой (внешний выход 14) и второй (внешний выход 20) координат, которые сравниваются схемами 7и 23 сравнения с их максимальными значениями . Если текущие значения первой или второй координаты больше максимальных, то на выходе соответствующей схемы сравнения появляется единичный потенциал, преобразуемый формирователями 2 и 29 в импульс. Поэтому импульсу счетчики 8 и 24 устанавливаются в нулевое состояние. Кроме того, этот импульс подается на счетный вход счетчика 19 и через линию 13 задержки разрешает перезапись состояния счетчика 19 в один из счет чиков 8 или 24 в зависимости от результата сравнения схемой 18. Двоичное число счетчика 19 сравнивается смаксимальным значением первой координать 1 схемой 18 сравнения, и, если двоичное число счетчика 19 меньше максимального значения первой.координаты, то единичный потенциал появляется на первом выходе схемы 18 сравнения, в противном случае - на ее о втором выходе. Формирование значе-, ния координат следующей точки области осуществляется по импульсу "Конец цикла испытаний" (внешний вход 15) ,или "Внешняя или граничная точка" (внешний выход 16), поступающего соответственно с выхода счетчика числа испытаний или с выхода блока анализапризнаков вероятностного устройстваЭтот импульс поступает одновременно на счетные входы счетчиков 8 и 24. Второй выход счетчика 19 является старшим разрядом и соединен с внеш" ним выходом 3 1 "Задание алгоритма". Появление на этом выходе единичного потенциала .соответствует второй ступени процедуры вычислений. Третий выход счетчика 19 является выходом попереполнению и соединен с внешним выходом 30 "Конец счета", 955084Таким образом осуществляется последовательное изменение кода координат, что позволяет в данном устройстве реализовать описанный выше способ обхода вычисляемых точек двумерной 3 сеточной области "По диагоналям шахматного поля", и что выгодно отличает данное устройство от прототипа, так как в 2 п раз уменьшается общее среднее время решения задачи во всех точках исследуемой области, где и число вычисляемых точек сеточной области. Это позволяет значительно повысить производительность устройства при решении конечно-разностных урав ф нений, Так, например, при и = 100 производительность вероятностного устройства возрастает в 20 раз.формула изобретенияУстройство для обхода узлов сеточной области, содержащее три счетчика, блок задержки, первый и второй эле- Ф 5 менты И, первый и второй элементы ИЛИ, первый и второй регистры, группы входов которых являются соответственно первой и второй группами входов устройства, выход первого регист- ЗО ра подключен к первому входу первого блока сравнения, о т л и ч а ю щ е е-: с я тем, что, с целью повышения быстродействия, в него введены второй и третий блоки сравнения, третий, з четвертый и пятый элементы ИЛИ, третий, четвертый, пятый и шестой элементы И и два формирователя импульсов, выходы которых подключены соответственно к первым и вторым входам первого и второго элементов ИЛИ, выход второго регистра под ключен к первому входу второго блока сравнения, выход первого элемента ИЛИ соединен с установочными входами первого и 4 второго счетчиков, выходы которых подключены соответственно к в 1 орым входам первого и второго блоков сравнения и являются соответственно первой и второй группами выходов устройства, первый вход которого подключенк первому входу третьего элемента Ии к установочному входу третьегосчетчика, первый выход которого является первым выходом устройства, второй и третий входы которого соединенысоответственно с первым и вторым входами третьего элемента ИЛИ, выход которого подключен к счетным входам первого и второго счетчиков, информационные входы которых соединены соответственно с выходами четвертого и пятого элементов ИЛИ, выход второгоэлемента ИЛИ подключен к входу блоказадержки и к счетному входу третьегосчетчика, второй выход которого соединен с первыми входами четвертогои пятого элементов И и с первым входом третьего блока сравнения, первыйи второй выходы которого подключены .соответственно к первым входам первого и второго элементов И, вторыевходы которых соединены с выходомблока задержки, выход первого регистра подключен к второму входу третьего блока сравнения, к первому входушестого элемента И и к второму входутретьего элемента И, выход первогоэлемента И соединен с вторыми входами четвертого и шестого элементов И,выходы которых подключены соответственно к первым входам четвертого ипятого элементов ИЛИ, вторые входыкоторых соединены с выходом третьегоэлемента И, выход второго элемента Иподключен к второму входу пятого элемента И, выход которого соединен стретьим входом пятого элемента ИЛИ,третий выход третьего счетчика является вторым выходом устройства. Источники информации,,принятые во внимание при экспертизе1. Авторское свидетеЛьство СССРй 369580, кл. С 06 С 7/48, 1970.2. Авторское свидетельство СССРМ 477418, кл, О 06 Г 15/32, 1972,955084 АЮ йЮ Составитель В. Рыби Техред М,Тепер Редак 1 ор С. нен орректор А. Гриценк Заказ 643;.)/5 ил ППП "Патент", гужгород, ул, Проектная 4 Тираж 731НИИПИ Государствепо демам изобрет035, Москва, Жого комий и отРаушска Подписноеета СССРытийнаб., д, 4/