Устройство для анализа больших регулярных сетей

 

Союз Советских

Социалистических

Республик

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

«!790000 (61) Дополнительное к авт. саид-ву (22) 3аявлено 301078 (21) 2678385/18-24 (51)М. КЛ.З с присоединением заявки Мо

G 06 Q 7/122

Государственный комитет

СССР по делам изобретений н открытий (23) Приоритет (53) УДК 681.333 (088. 8) Опубликовано 23.1280,:бюллетень ¹ 47

Дата опубликования описания 23.12.80 (72) Авторы изобретения

В,В.Васильев, A,Ã.Äoäoíoâ и А;И.Левина

Институт электродинамики AH Украинской CCP и Опытноконструкторское технологическое бюро Института металлофизики АН Украинской CCP (71) Заявитель (54) УСТРОЙСТВО ДЛЯ АНАЛИЗА БОЛЬШИХ

РЕГУЛЯРНЫХ СЕТЕЙ

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

Изнестна вычислительная машина для расчета сетевых графиконе содержащая соединенные между собой устройства ввода и вывода, устройство управления, генератор импульсов „на- 10 борное поЛе, блок моделей работ, выполненных н виде счетчиков, дифференцирующей цепи, триггера и диоды, соединенных между собой последовательно (11 . 15

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

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

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

79000.0

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

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

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

:которого подключены соответстэенно к третьему и четвертому выходам запоми нающего блока, второй выход которого соединен с адресным входом микропрограммного блока управления, управляющий вход которото подключен к выходу блока анализа конечных узлов, третий вход которого. соединен с третьим информационным выходом микропрограммного блока управления, первый и второй информационные входы которого подключены ко второму и третьему выходам модели регулярной сети. А также тем„ что блок анализа конечных узлов со- держит блоки сравнения, счетчик циклов и элемент НЕ, выход которого через счетчик циклов подключен к первому входу первого блока Сравнения, выход которого соединен со входом элемента HE и является выходом блока анализа конечных узлов, выход второго блока сравнения подключен ко второму входу первого блока сравнения, третий вход которого является вторым входом блока анализа конечных узлов, первым входом которого является первый вход второго блока сравнения, второй вход которого е гь третьим входом блока анализа конечных узлов.

Кроме того, тем, что микропрограммный блок управления содержит счетчик ад- реса, управляемый генератор импуль-. сов, регистр сдвига и блок задания режима, выход которого подключен к первому входу управляемого генерато ра импульсов, выходы которого соответственно подключены ко входам первого счетчика адреса,и регистра. сдвига, выход первого счетчика адреса соединен со входом второго счетчика адреса, выход которого подключен ко Второму входу управляемого гене- ратора импульсов, входы которого яв15 ляются соответственно адресным,. Управляющим, первым и вторым информационными входами микропрограммного е блока управления, разрядные выходы счетчиков адреса и регистра сдвига являютс я первым, вторым и третьим информационными выходами микропрограммного блока управления.

На фиг. 1 приведена блок-схема устройства на фиг. 2 — схема блока анализа конечных узлов, на фиг. 3 схема регулярной сети для примера, иллюстрирующего работу устройства; на.фиг. 4 — микропрограммный блок управления, Устройство содержит модель регулярной сети 1, запоминающий блок 2, микропрограммный блок 3 управления, в состав которого входят микропрограммный автомат 4 и счетчики 5,6. адреса по координатам Х,У, блок 7 анализа конечных узлов. Блок 7 анализа конечных узлов (фиг, 2) содержит двухступенчатую схему В сравнения с первым и вторым. блоками 9, 10 сравнения, элемент НЕ 11 и счетчик 12 циклов. Модель регулярной сети 1 состоит из жестко соединенных согласно топологии сети моделей узлов и моделей ветвей. Модели узлов служат для моделирования весовых коэффициентов, модели ветвей — для выполнения логических функций передачи информации по регулярной сети. Весовые коэффициенты как и в известном устройстве, моделируются количеством импульсов, 50 дополняющих емкость счетчика моделей узлов до .переполнения., Запоми-нающий блок 2 предназначен для хране ния массива исходной информации в ве,совых коэффициентах моделей узлов и их адресов по координатам Х, У, адреса конечного узла и номера фрагмента, которому он принадлежит, а также промежуточной информации о дереве оптимальных путей и.результате решения — оптимальном пути в виде адресов моделей узлов, через которые он проходит. Микропрограммный автомат

4 блока 3 управления служит для управления непрерывно протекающим вычислительным процессом, состоящим из двух этапов: первого — определе. 790000 ние дерева оптимальных путей и второго — выделение единственного пути между начальной и конечной точками исходной сети, и включает регистр. 13 сдвига, угравляемый генератор 14 импульсов и блок 15 задания режима.

Счетчики 5,6 адреса блока 3 управления предназначены для определе ния адресов моделей узлов и его исходящих ветвей по координатам Х, У.

Для иллюстрации работы устройства рассмбтрим пример (фиг. 3) для слу чая, когда задана регулярная сеть G размером н произвольной конфигурации (прямоугольной, трехугольной и т.д.) . Подобные сети используют в задачах определения оптимальных путей в неоднородных средах, при этом элементам регулярной сети — yaлам приписываются весовые коэффициенты, характеризующие соответствующие участки неоднородной среды. Чем меньше шаг, т,е. чем больше размер регулярной сети, покрывающей исследуемую область неоднородной среды,тем точнее решение. Решение больших регулярных сетей в данном устройстве сводится к решению в каждый момент времени t, фрагмента регулярной сети

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

Работает устройство в следующей последовательности.

На первом этапе при определении дерева оптимальных путей между заданными точками А, В исходной регулярной сети вычислительный процесс распространяется по спиралИ в одном направлении, например, цо часовой стрелке. Решение на данном этапе протекает ло следующей микропрограмме: ввод информации по данному адресу, промужуточное решение, продолжительность которого опре (еляется временем до переполнения одного или одновременно нескольких счетчиков моделей узлов, вывод результатов промежуточного решения и анализ информации, содержащейся в моделях узлов, смежных с данным. Известно, что отработанные узлы формируют запрет на их повторный пуск от окружающих моделей узлов. При протекании вычислительного процесса в замкнутых устройствах по спирали появляется необходимость анализа этого запрета, Если запрет сформирован.на 1 -ой спирали, т.е. при решении фрагмента, он сохраняет свое действие, если на Г -1-ой спирали, т.е. при решении,, фрагмента, то производится сброс в 0 всех моделей узлов, смежных с данным отработанным, и ввод весовых коэффициентов в эти модели узлов С; фрагмента.

Функционирование устройства по данной микропрограмме происходит следующим образом. По пуску с выхода 16 блока 3 управления на вход запоминающего блока 2 (фиг.l) поступает признак считывания адреса начального узла. По этому признаку с выхода 17 запоминающего блока 2 через вход 18 блока 3 в счетчики 5;6 адреса записывается адрес начального узла. По дан15 ному адресу, поступающему через вы- ход 19 блока 3 управления на вход модели регулярной сети 1, определяется адрес модели начального узла. Иикропрограммный автомат 4 переключается

2О в режим ввода информации. ha выходах

16 и 19 блока 3 появляется признак ввода, который поступает на вход модели регулярной сети l и на вход запоминающего блока 2. В этом режиме по адресу начального узла с выхода 20 запоминающего блока 2 на вход модели регулярной сети 1 поступает информация о весовом коэффициенте, которая записывается в модель начального узла в обратном коде. Микропрограммный автомат 4 переключается в режим решения, при этом признак решения через выход 19 блока 3 поступает на вход

1 модели регулярной сети, 1 разрешая поступать импульсам измерительной серии в счетчик модели начального узла, по переполнению которой на выходе модели 18 регулярной сети 1 появляется требование на вывод промежуточной информации, которое поступает на вход блока 3 управления. Микропрограммный автомат 4 переключается в режим вывода. На вход модели регулярной сети 1 с выхода 19 блока 3 и на вход запоминающего бло-. ка 2 с выхода 16 блока 3 поступает признак вывода информации. При этом на вход запоминающего блока 2 с выхода 21 модели регулярной сети 1 поступает результат промежуточного реше5о. иия в виде адреса отработанной модели начального узла и исходящих из данного узла моделей ветвей, через которые передается требОвание на пуск смежных узлов. По концу вывода признак вывода на выходе 22 модели регулярной сети 1 исчезает, и микропрограммный автомат 4 переключается в режим анализа информации, содержащейся в моделях узлов, смежных с начальньщ узлом.Так как эти модели узлов бО еще не работали, и не был сформирован запрет на их пуск, то на выходе модеПи регулярной сети 1 появляется требование на ввод, по которому микропрограммный автомат 4 переключается в б5 режим ввода информации в те модели

790000 узлов, на которые поступает требование с модели начального узла, На выходе 19 блока 3 управления появляется признак ввода, который поступает на аход модели регулярной сети 1.. На.выходе 22 модели регулярной сети 1 формируется требование на ввод, Это требование присутствует на все время вво да, Ввод информации осуществляется по адресу. Определение адресов моде-: лей узлов, на которые поступило требование, и ввод осуществляются за один цикл просчета счетчиков 5,6 а;— реса. Микропрограммный автомат 4 пред» варительно сбрасывает счетчики 5,6 адреса в 0, а затем разрешает поступление на их вход импульсов так- 15 тового генератора ГИ (на чертеже на показан) до совпадения с первым адресом модели узла модели регулярной сети 1, на которую поступило требова ние на запуск от начального узла. По 2р совпадению адресов на выходе 23 модели регулярной сети 1 появляется сигнал, который поступает на вход блока 3 управления. По этому сигналу микропрограммный автомат 4 запрещает поступление импульсов тактового генератора ГИ в счетчики 5,6 адреса и переключается в режим обращения к запоминаюцему блоку 2, С выхода

16 блока 3 на вход запоминающего блока 2 поступает признак считывания О и адрес модели узла, По данному адресу через выход 20 запоминающего блока 2 и вход модели регулярной сети

1 н модель узла записывается весовой коэффициент в обратном коде, IIo кон- 35 цу ввода эта модель узла убирает свое требование на нвод. Если требование на решение поступает на несколько моделей узлов, то на выходе

22 модели регулярной сети 1 присутст- 40 вует требование на ввод информации, Далее определяется адрес следуюцей модели узла. Микропрограммный автомат 4 снова разрешает поступление импульсов тактового генератора ГИ 45 на вход. счетчиков 5;6 адреса до совпадения со вторым адресом модели уз.ла, на которую поступило требование с начального узла. По второму адресу осуцествляется ввод информации и так далее. Как только осуцествляется ввод информации в последнюю модель узла, на выходе 22.модели регулярной сети .1 исчезает требование на ввод.

Микропрограммный автомат 4 прекращает .просчет счетчиков адреса и переключается в режим решения, На выходе 19 блока 3 управления появляетcÿ призйак решения, по которому импульсы измерительной серии поступают на входы тех моделей узлов, в кото- ф9 рые произведен ввод. Далее процесс решения развивается аналогично. Параллельно с выводом информации в запоминающий блок 2 производится сравнение на блоке 9 сравнения схемы 8 45 сравнения передаваемого адреса и адреса конечного узла. Fla вход блока

9 сравнения подается информация об адресе конечного узла с выхода 24 запоминаюцего блока 2 и об адресе выводимой модели узла с ныхода 25 блока 3. Сонпадение адресов в блоке 9 сравнения позволяет перейти к сравнению информации в блоке 10 сраннения, где сраннивается номер фрагмента, поступающего с выхода 26 запоминающего блока 2, и содержимое счетчика циклов ° Если нет совпадения, т ° е ° на выходе элемента E 11 появляется высокий потенциал, то в счетчик 12 циклов присчитывается единица. Процесс решения продолжается до совпадения информации на блоках 9 и 10 сравнения. При совпадении сигнал с выхода схемы 8 сравнения запрещает процесс решения задачи, протекающий в модели регулярной сети по направлению часовой стрелки. Микропрограммный автомат

4 переходит в режим выделения единственного оптимального пути из полученного дерева оптимальных путей. Устройст,о переходит ко второму этапу решения.. Вывод промежуточных решений совмещен во времени с окончанием счета соответствующих моделей узлов.

Запись их адресов в запоминающем блоке 2 производится последовательно.

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

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

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

2 адресов моделей узлов и информации об исходящих .ветвях, принадлежащих дереву оптимальных путей, и переда«ча в модель регулярной сети 1 до тех пор, пока через модель узла по данному адресу не замкнется участок цепи для передачи нулевого потенциала с выхода модели узла на вход. После передачи информации с выхода на вход адрес модели узла ныводится снова из запоминающего блока 2, затем снова считываются адреса моделей узлов, принадлежащих дереву оптимальных путей и т.д. Функционирование устройства по данной микропрограмме происходит следующим образом: микропрограммный автомат 4 организовывает режим считывания адреса конечного..9

790000 узла В. Признак считывания, появляю щийся на выходе 16 блока 3 управления, поступает на вход запоминающего блока 2. Адрес конечного узла В через выход 17 запоминающего блока

2, вход 18 блока 3 параллельным кодом записываются в счетчики 5,6 адреса. Микропрограммный автомат 4 переходит в режим выделения пути.

На вход модели регулярной сети 1 с выхода 19 блока 3 подается адрес конечного узла и разрешение на передачу с выхода на. вход нулевого потенциала. По концу передачи на выходе

22 модели регулярной сети 1 появля— ется требование, поступающее на вход блока 3. По этому требованию в запо- 15 минающем блоке 2 запоминается адрес узла, через который произошла передача информации, а затем продолжается считывание адресов узлон и исходящих ветвей, записанных в запоминаю- gp щем блоке 2 на первом этапе решения, Режим считывания организуется аналогично описанному ранее. Микропрограммный автомат 4 вырабатывает признак считывания, который с выхода 16 блока 3 поступает на вход запоминающего блок 2. Адреса узлов считываются последовательно параллельным кодом с выхода 17 запоминающего блока 2 и записываются н счетчики 5,6 адреса через выход 18 блока 3. Эти адреса через выход 19 блока 3 поступают на вход 1 модели регулярной сети 1.

Как только считывается адрес узла и

его ветвей, которые позволяют продлить участок пути, идущего от конечного узла, считывание адресов прекращается, и микропрограммный автомат

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

Величина оптимального пути может быть измерена обычным образом IHa первом этапе протекания вычислительного процесса. Параллельно модели регулярной сети 1 импульсы измерительной се- 5$ рии поступают в счетчик измерения.

Тогда по концу определения дерева оптимальных путей в счетчике измере-, ний (на фиг. 1 не показан) будет получена величина оптимального пути между ,заданными узлами A„B„

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

1, Устройство для анализа больших регуляторных сетей, содержащее Модель регулярной сети, запоминающий блок, микропрограммный блок управления, первый информационный выход которого соединен с первым входом модели регулярной сети, второй вход которой соединен с первым выходом запоминающего блока, первый вход которого подключен ко второму информационному выходу микропрограммного блока управления, второй вход запоминающего блока соединен с первым выходом модели регулярной сети, о т л и ч а— ю щ е е с я тем, что, с целью упрощения устройства и повышения его быстродействия, в него введены блок анализа конечных узлов,. первый и. второй входы которого подключены соответственно к третьему и четвертому выходам запоминающего блока, второй выход которого соединен с адресным входом микропрограммного блока управления, управляющий вход которого подключен к выходу. блока налива конечных узлов, третий вход которого соединен с третьим,информационным выходом микропрограммного блока управления, первый и второй информационные входы которого подключены ко второму и третьему выходам модели регулярной сети.

790000 .2

2. Устройство по п. 1, о т л и ч а ю щ е е с я. тем, что блок анализа конечных узлов содержит блоки сравнения, счетчик циклов и элемент

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

3, Устройство по . и. 1, о т л и ч а ю щ е е с я тем, что микпропрограммный блок управления содержит счетчики адреса, управляемый генератор имплуьсов,. регистр сдвига и блок задания режима, выход которого подключен .к первому входу управляемого генератора импульсов, выходы которого соответственно подключены ко входам первого счетчика адреса и регистра сдвига выход первого счетчика адреса соединен со входом второго счетчика адреса, выход которого подключен ко второму входу управляемого генератора импульсов, входы которого являются соответственно адресным, управляющим, первым и вторым информационными входами микропрограммного блока управления, разрядные выходы счетчиков адреса и регистра сдвига являются первым, Broðûì и третьим информационными выходами микропрограммного блока управления.

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

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

Ф 367 431, кл. G 06 0 .7/122, 1968.

2. Додонов А.Г., Хаджинов В.B.

QQ Об одном методе решения больших сетей на цифровых аналогах. В сб. Гибридные„вычислительные машины и комплексы. Еиев, Наукова думка, 1975, с. 5 (прототип) .

Составитель И,Дубинина

РедактоР Ъ.ПаРасюн ТехРед М.Петко КоРРектоР1 B.МакаРенко

Заказ 9041/50 Тираж 751 Подписное

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

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

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