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

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

Ц50 G 06 F 15/32

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTHA (21) 3544237/18-24 (22) 13.01.83(46) 15.03 ° 84. Бюл, 9 10 (72) С.Г.Гришкин и П.Г.Струнская (71) Казанский ордена ТРудового

Красного Знамени и ордена. Дружбы народов авиационный институт им.. A.Í.Tóïîëåâà (53) 681.32(088 ° 8) (56) 1. Авторское свидетельство СССР

9 955084, кл. Q 06 Р 15/32, 1976. е

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

Р 951319, кл. Q 06 F 15/32, 1980 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ ОБХОДА СЕТОЧНОЙ ОБЛАСТИ, содержащее первый регистр, информационный выход которого подключен к первому входу первогб блока сравнения, выход которого соединен со входом первого формирователя импульсов, выход которого подключен к первому входу первого элемента ИЛИ, выход которого соединен со счетным входом первого счетчика, информационный выход которого соединен со вторым входом первого блока сравнения, информационный выход второго регистра подключен к первому входу второго блока сравнения, выход которого соединен со входом второго формирователя импульсов, выход которого подключен ко второму входу первого элемента ИЛИ и первому входу второго элемента

ИЛИ, выход которого соединен со входом установки в ноль второго счетчика, информационный выход которого является первым информационным выходом устройства и подключен -ко второ-,,му входу, второго блока сравнения, выход первого элемента задержки сое,.SU„47 A динен с первым входом третьего элемента ИЛИ, выход которого подключен к счетному входу второго счетчика, информационные входы первого и второго регистров являются соответственно первым и вторым информационными входами устройства, вход первого элемента задержки и второй вход третьего элемента ИЛИ являются соот.ветственно входом "Конца цикла испы.таний" и входом "Внешнего нли граничного узла" устройства, выход переноса первого счетчика является выходом "Конца счета" устройства, а второй вход второго элемента ИЛИ объединен со входом установки в ноль первого счетчика и является входом g начала счета устройства, второй элемент задержки, о т л и ч а ю щ е ес я тем, что, с целью повышения быстродействия, в него введены элемент И, элемент НЕ, третий счетчик и триггер, выход которого подключен Я ко входу второго элемента задержки, выход которого соединен со счетным входом третьего счетчика, установочный вход которого подключен к выходу элемента И, первый вход которо,го соединен с выходом элемента НЕ,,вход которого подключен к выходу первого блока сравнения, второй вход элемента И объединен со счетным входом триггера и подключен к выхо° ду третьего элемента ИЛИ, выход второго элемента ИЛИ соединен со входом установки в ноль триггера, третий вход элемента И подключен к информационному выходу первого счетчи.ка, выход младшего разряда которого является выходом смены алгоритма устройства, а информационный выход третьего счетчика является вторым ийфсрюищионным выходом устройства. "

1080147

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

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

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

I на примерно равные подобласти, что, в свою очередь>позволяет значительно сократить общее время решения задачи j1) ..

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

Наиболее близким по технической сущности к данному изобретению яв-. ляется устройство обхода сеточной 40 области, которое содержит два регистра, два блока сравнения, два счетчика, два формирователя импульсов, переключатель режима работы, три эле нта ИЛИ два элемента за- 45 держки, при этом первый, второй и третий входы устройства соединены соответственно со входом установки в нуль первого счетчика, со входом первого элемента задержки, со вторым входом третьего элемента ИЛИ первый,50 второй и третий выходы устройства подключены соответственно к выходу переполнения первого счетчика, че .Рез второй контакт переключателя режима работы — к выходу первого бло-55 ка сравнения, через четвертый контакт переключателя режима работы — к выходу второго счетчика и ко второму входу второго блока сравнения, выход первого регистра подключен к пер-60 вому контакту переключателя режима работы и к первому входу первого блока сравнения, выход которого сое-. динен со входом первого формирователя импульсов, а выход последнего - 65 с первым входом первого элемента

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

ИЛИ.

Это устройство характеризуется простотой схемной реализации и

:сравнительно малым объемом оборудования. В нем осуществляется последовательный обход узлов сеточной области. При этом исходная область, вписанная в прямоугольник, рассекается по меньшей стороне последовательно на равные независимые подобласти, деля каждый раз предыдущую подобласть пополам. Это достигается использованием счетчика по меньшей координате, реализующего последовательность Холтона, равномерно распределенную на интервале 0-2 -1, И где м )fog bf. — число разрядов счетчи ка, Ъ вЂ” ме н ьшая сторона п рямоугольника t2J .

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

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

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

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

"Конца счета" устройства, а второй вход второго элемента ИЛЙ объединен со входом установки в ноль пер-, вого счетчика и является входом начала счета устройства, второй элемент .задержки, введены элемент И, элемент НЕ, третий счетчик и триггер, выход которого подключен ко входу второго элемента задержки, выход которого соединен со счетным входом третьего счетчика, установочный вход которого подключен к выходу элемента И, первый вход которого соединен с выходом элемента НЕ, вход которого подключен к выходу первого блока сравнения, второй вход элемента И объединен со счетным входом триггера и подключен-к выходу третьего элемента ИЛИ, выход второго элемента

ИЛИ соединен со входом установки в ноль триггера, третий вход элемента

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

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

Схема содержит вход "Начало счета" 1, выход "Конец. счета" 2, выход

"Смена алгоритма" 3, информационные входы устройства 4, регистр 5, блок сравнения 6, счетчик 7, элемент И 8., 60 счетчик 9, формирователь импульсов

10, .элемент ИЛИ 11, элемент НЕ 12, элемент задержки 13, информационные выходы устройства 14, информационные входы устройства 15, регистр 16, 65 блок сравнения 17, формирователь им пульсов 18, счетчик 19 элемент ИЛИ

I 20, триггер 21, информационные выхо ды устройства 22, вход "Конец цикла

5 испытаний" 23, вход "Внешний или граничный узел" 24, элемент задержки

25 и элемент ИЛИ 26..

Устройство реализует обход узлов сеточной области, который обеспечивает двухступенчатую вероятностно10 детерминированную процедуру решения конечно-разностных уравнений во всех узлах области.

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

15 Перед началом работы входом устройства 4 и 15 в первый 5 и второй

16 регистры заносятся значения координат соответственно меньшей и большей стороны прямоугольника, описанного вокруг исследуемой области.

По сигналу "Начало счета" со входа

1 счетчик 7 устанавливается в нулевое состояние. Этот сигнал через элемент ИЛИ 20 поступает на входы установки в нуль счетчика 19 и триггера 21, устанавливая их в нулевое состояние. Нулевые координаты первого узла (фиг.2) поступают на первые

14 и вторые 22 выходы устройства в вероятностное вычислительное устройство, которое анализирует данный узел. Если узел области внутренний, то после цикла из я испытаний вероятностное устройство выдает запрос по входу "Крнец цикла испытаний" 23

3 на следующий узел. При этом элемент задержки 25 задерживает сигнал запроса на время, необходимое для записи информации по текущему узлу в память вероятностного устройства.

40 Если же узел — граничный или внешний, то вероятностное устройство вы« дает запрос на следующий узел,по входу "Внешний или граничный узел"

24.

В обоих случаях сигнал запроса, проходя через элемент ИЛИ 26, во-первых, поступает на счетный вход счет-, чика 19, увеличивая его содержимое

5О,на ед н цу, во-втоРых, Разрешает перепись состояния счетчика 7 при условии, что узел находится в пределах .описанного вокруг области прямоугольника, в счетчик 9, в-третьих, этот сигнал поступает на счетный вход триггера 21, изменяя его состоя« ние. Единичный перепад (переход из

"0" в "1") счетного триггера 21 через элемент задержки 13, который задерживает этот перепад на время, необходиьюе для пЕреписи состояния счетчика 7, в счетчик 9, поступает иа счетный вход счетчика 9, увеличивая его содержимое иа единицу. Таким образом осуществляется .перехрд кз первого узла во второй узел .и т.д., ре-, 1080147

gy t4 ализуя ступенчатый последовательный в выбор координат узлов области (1, 2

3, 4,..., см. фиг.2), которые поступают на первый 14 и вторые 22 выходы устройства.

В случае, когда состояние счетчика 19 (значение большей координаты) больше или равно состоянию регистра

16 (максимальное значение большей координаты1, на выходе блока срав нения 17 появляется единичный по. тенциал, преобразуемый формирователем импульсов 18 в одиночный импульс.

Он поступает одновременно через элементы MJIH 11 и 20 соответственно на счетный вход счетчика 7 и на вход 15 установки в нуль счетчика 19. Счетчик 19 устанавливается в нулевое состояние, а счетчик 7, который реализует последовательность Холтона, увеличивает свое содержимое на едини- Щ цу. Состояние счетчика 7 переписывается по сигналу запроса в счетчик

9 и затем повторяется процесс, который был описан вьме. Старшие разря- ды счетчика 7 переписываются в млад- 25 шие разряды счетчика 9. На фиг. 2 показан переход из узла 7 в узел 8, иллюстрирующий этот случай.

При изменении состояния счетчика

7 (значения меньшей координаты) на 3() его выходе может появиться не более одного раза подряд значение числа, превышающее максимальное значение меньшей координаты, хранящегося-. в регистре 5. В этом случае на выходе блока сравнения 6 появляется единичный потенциал, преобразуемый формирователем импульсов 10 в одиночный импульс, который поступает через .! элемент ИЛИ.11 на счетный вход счет40 чика 7, изменяя его состояние ° Кроме этого, единичный потенциал, проходя через элемент НЕ 12, запрещает перепись состояния счетчика 7 в счетчик 9.

При появлении в младшем разряде счетчика 7 единицы на выход 3 устройства подается сигнал "Смена алгоритма". Это значит, что обход узлов для первого этапа решения задачи вероятностным методом закончился и начался второй этап решения конечно-разностных уравнений путем усреднения значений функции в соседних (пройденных на первом этапе) узлах.

При переполнении счетчика 7 с выхода 2 устройства обхода области подается сигнал "Конец счета" в вероятностное устройство.

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

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

1080147

Составитель А.Баранов

Редактор С.Тимохина ТехредЛ.Йикеш: корректор.Зимокосов

Ю»

« »»»т«Ю» »» «»

ЮЮ Ю

Закаэ 1339/49 Тираж 699 : . . Подписное

ВНИИПК Государственного комитета СССР

:по делам изобретений и открытий

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

Ф «Ю Ю ю«ююююююю»ю»юю»»

» «<Ф Ю

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