Устройство для анализа больших регулярных сетей Советский патент 1980 года по МПК G06G7/122 

(54) УСТРОЙСТВО ДЛЯ АНАЛИЗА БОЛЬШИХ РЕГУЛЯРНЫХ СЕТЕЙ Изобретение относится к вычислите ной технике и можедг быть использовано при построении специализиров.анных цифровых устройств для определения путей на больших регулярных сетях. Известна вычислительная машина для расчета сетевых графиков содержащая соединенные мехду собой устройства ввода и вывода, устройство . управления, генератор импульсов, наборное поле, блок моделей работ, вы полненных в виде счетчиков, дифферен цирующей цепи, триггера и диоды, сое диненных мехэду собай последовательно Однако ввиду сложности конструкции за счет большого количества необходимого оборудования вычислительная машина не может быть использована для анализа больших сетей. Наиболее близким техническим решением является устройство для анализа больших регулярных сетей, содер жащее блок моделей ветвей с началь1 ыми и конечными граничными узлами, внешнее запоминающее устройство, ..блок элементов памяти, устройство управления,первый выход которого соединен с первым входом модели регулярной сети, второй выход - с первым , входом внешнего запоминающего устройства, первый выход которого соединен со вторым входом модели регулярной сети , первый выход которой - со вторым входом внешнего запоминающего устройства, Процесс расчета больших сетей на этом устройстве предполагает предварительное разбиение исходной сети на фрахгменты, у которых количество ветвей не превышает количества элементарннк моделей ветвей блока моделей ветвей. 1Информация о сети: топология соединений моделей ветвей и их,, веса хранится во внешнем запоминающем устройстве и вводится при расчё.те соответствующего фрагмента. Все модели ветви моделируются количеством импульсов, дополняющих емкость счетчика до переполнения. К конечным граничным узлёи.1 подключается блок элементов памяти, в качестве которых используют счетчики. При расчете первого фрагмента разница величин путей из начальных в конечные граничные узлы запоминается в блоке элементов памяти. Эта разница определяет начальные условия начальных граничных узлов последующего фрагмента. При расчете второго фрагмента импульсы измерительной серии поступают на счетчики блока памяти, которые переключаются на вычихание. По переполнении счетчиков блока элементов памяти импульсы измерительной серии поступают в модели ветвей, исходящих из соответствующих начальных граничных узлов. Разница ве личинпутей в конечные граничные узлы второго фрагмента заносится во вторую группу счетчиков блока .элементов памяти. Рассмотренные циклы расчета повторяются от фрагмента к фрагменту ту 2.: Основной недостаток данного устройства, ограничивающий его применение для рас-чета больших сетей, рост времени решения при постоянном размере сети за счет пetlecтpoJйки вычислительного устройства от фрагмента к фрагменту,которая производится вручную, а также за счет двойного просчета разницы.величин путей в граничные узлы для двух смежных . фрагментов... Цель изобретения - упрощение и повышение быстродействия -устройства, Указанная дель достигается тем, что в устройства для анализа больших регулярных сетей, содержащее модель регулярной сети, запоминающий блок и микропрограммный блок управления, ПгВрвый информационный выход которого Соединен с первым входом модели регулярной сети, второй .вход которой соединен с-первым выходом запоминающего блока, первый вход которого подключе ко второму информационному выходу микропрограммного блока управления, второй вход запоминающего, блока соединен с первым выходом мсздели регулярной сет.и, введены блок анализа ко нечных узлов, первый и второй входы .которого подключены соответственно к третьему и четвертому выходам;запоми нающего блока, второй вы}foд которого соединен с адресным входом микропрограммного блока управления, управляю щий вход которого подключен к выходу блока анализа конечных узлов, третий вход которого .соединен с треть.им ин;формацйонным выходом микропрограммно го блока управления, первый, и второй информационные входы подклю чены ко второму и третьему выходам модели регулярной сети .А также Teiy что блок .анализа конечных узлов содержит блоки сравнения, счетмик циклов и элемент НЕ, выход которого через счетчик циклов подключен к пер-, вому входу первого блока сравнения, выход которого соединенсо входом элемента НЕ и является выходом блока анализа конечных узлов, выход вто рого блока сравнения подключен ко второму входу первого блока сравнени третий вход которого является вторым входом блока анализа конечных узлов, первым-входом которого является первый вход второго блока с|Ьавнения, второй вход которого есть третьим входом блока а.нализа конечных узлов. Кроме тоГ.о, тем, что микропрограммный блок управления содержит счетчик адреса, управляемый генератор импуль-г сов, регистр сдвига и блок задания режима, выход которого подключен к первому входу управляемого генератогра импульсов, выходы которого соответственно под1слючены ко входам первого счетчика адреса, и реги.стра сдвига, выход первого счетчика адреса соединен со входом второго счетчика адреса, выход которого подключен ко второму входу управляемого генератора импульсрв, входы которого являются соответственно адресным,, управляющим, первым и вторым информационными входами микропрограммного блока управления, разрядные выходы счетчиков адреса и регистра сдвига являются первым, вторым и третьим информационными выходами микропрограммного блока управления. На фиг.1 приведена блок-схема устройства на фиг. 2 - схема блока анали-эа конечных узловJ на фиг. 3 схема регулярной сети для примера, иллюстрирующего работу устройства; на.фиг. 4 - микропрограммный блок управления. . УСТРО.ЙСТВО содержит модель регулярной сети 1, запоминающий блок 2, микропрограммный блок 3 управления, в состав которого входят микропро- . граммный автомат 4 и счетчики 5,6 адреса по координатам X,У, блок 7 анализа конечных узлов. Блок 7 анализа конечных узлов (фиг. 2) содержит двухступенчатую схему 8 сравнения с первым и вторым блоками 9, 10 сравнения, элемент НЕ 11 и счетчик 12 циклов. Модель регулярной сети 1 состоит из жестко соединенных согласно топологии сети моделей узлов и моделей ветвей. Модели узлов служат для моделирования весовых коэффициентов модели ветвей - для выполнения логических -функций передачи информации по регулярной сети. Весовые коэффициенты как и в известном устройстве , моделируются количеством импульсов, дополняющих емкость счетчика моделей узлов до :переполнений. Запоминаю1ций блок 2 предназначен для кранения массива исходной информации в весовых коэффициентах моделей,узлов и ихадресов по координатам X, У, адреса конечного узла и номера фрагмента, которому он принадлежит, а также промежуточной информации о дереве о.птимальных путей и .результате решения - оптимальном пути в виде адресов моделей узлов, через которые он проходит. Микропрограммный автомат 4 блока 3 управления служит для управления непрерывно протекающим вы-числительным процессом, состоящим из двух этапов: первого - определение дерева оптимальных путей и второго - вьщаление единственного пути между начальной и конечной точками исходной сети, и включает регистр 13 сдвига, управляемый генератор 14 импульсов и блок 15 задания режима.

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

Для иллюстрации Заботы устройства рассмотрим пример (фиг, 3) для случая, когда задана регулярная сеть S размером произвольной конфигурации (прямоугольной, трехугольной и т.д.). Подобные сети используют в задачах определения оптимальных путей в неоднородных средах, при этом элементам регулярной сети - узлам приписываются весовые коэффициенты, характеризующие соответствующие участки неоднородной среды. Чем меньше шаг, т.е. чем больше размер регулярной сети, покрывающей исследуемую Область неоднородной среды,тем точне решение.Решение больших регулярных сетей в данном устройстве сводится к решению в каждый момент времени t, Ц..Л , фрагмента регулярной сети F перемещающегося по данной сети при условии сохранения процесса решения непрерывнЕлм. Для организации непрерывного процесса рашения в предлагаемом устройстве конечные граничные узлы фрагмента F соединяются с начальными граничными узлами, не нарушая регулярности сети, В результате .образуется замкнутая-цилиндрическая

регулярная сеть, на которой вычислительный процесс развивается по спирали.

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

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

свое действие, если на Р -1-of. спирали, т.е. при решении F.фрагмента, то производится сброс в О всех моделей узлов, смежных с данным 4 тработанным, и ввод весовых коэффициентов в эти модели узлов f; фрагмента. Функционирование устройства по данной микропрогракаде происходит следующим образом. По пуску с выхода 16 блока 3 управления на вход запоминающего блока 2 (фиг.1) поступает призОнак считывания адреса начального узла. По этому признаку с выхода 17 запоминающего блока 2 ч;ерез вход 18 блока 3 в счетчики 5,-6 адреса записывается адрес начального узла. По дан5ному адресу, поступающему через выход 19 блока 3 управления на вход модели регулярной сети 1, определяется адрес модели начального узла. Микропрограммный автомат 4 переключается в режим ввода информации, ha выходах

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

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

0 автомат 4 переключается в режим решения, при этом признак решения через выход 19 блока 3 поступает на вход 1 модели регулярной сети, 1 разрешая поступать импульсам измерительной

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

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

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

0 еще не работали, и не был сформирован запрет на их пуск, то на выходе модеди регулярной сети 1 появляется требование на ввод, по которому микропрограммный автомат 4 переключается в

5 режим ввода инфсрмац 1И в те модели

УЗЛОВ, на которые поступает требование с модели начального узла. На выходе 19 блока 3 управления появляется признак ввода, который поступает на яход модели регулярной сети 1.. На. выходе 22 модели регулярной сети 1 формируется требование на ввод. Это требование присутствует на все время вво да. Ввод информации осуществляется по адресу. Определение адресов моделей узлов, на которые поступило требование, и ввод осуществляются за один цикл просчета счетчиков 5,6 адреса. Микропрограммный автомат 4 пред варительно сбрасывает с.четчики 5,6 адреса в О , а затем разрешает поступление на их вход импульсов тактового генератора ГИ (на чертеже на показан) до совпадения с первым адресом модели узла модели регулярной сети 1, на которую поступило требова ние на запуск от начального узла. По совпадению адресов на выходе 23 модели регулярной сети 1 появляется сигнал, который поступает на вход блока 3 управления. По этому сигналу микропрограммный автомат 4 запрещает поступление импульсов тактового генератора ГИ в счетчики 5,6 адреса и переключается в режим обращения к запоминающему блоку 2, С выхода 16 блока 3 на вход запоминающего блока 2 поступает признак считывания и адрес модели узла. По данному адресу через выход 20 запоминающего блока 2 и вход модели регулярной сети 1 в модель узла записывается весовой коэффициент в обратном коде. По концу ввода эта |уюдель узла убирает свое требование на ввод. Если требование на решение поступает на несколько моделей узлов, то на выходе 22 модели регулярной сети 1 присутствует требование на ввод информации. Далее определяется адрес следующей модели узла. Микропрограммный автомат 4 снова, разрешает поступление импульсов тактовбго генератора ГИ на вход, сч.етчиков адреса до совпадения со вторым адресом модели узла, на которую поступило требование с начального узла. По второму адресу осуществляется ввод информации и так далее. Как только осуществляется ввод информации в последнюю модель узла, на выходе 22.модели регулярной сети 1 исчезает требование на ввод. Микропрограммный автомат 4 прекращает просчет счетчиков- адреса и переключается в режим решения. На выходе 1.9 блока 3 управления появляется признак решения,., по которому импульсы измерительной серии поступаю на входы тех моделей узлов, в которые произведен ввод. Далее процесс решения развивается аналогично. Параллельно с выводом информации в зйпоминающий блок 2 производится сравнение на блоке 9 сравнения схемы 8

сравнения передаваемого адреса и адреса конечного узла. На вход блока 9 сравнения подается информация об адресе конечного узла с выхода 24 запоминающего блока 2 и об адресе выводимой модели узла с выхода 25 блока 3. Совпадение адресов в блоке 9 сравнения позволяет перейти к сравнению информации в блоке 10 сравнения, где сравнивается номер фрагмента, поступающего с выхода 26 запоминающего блока 2, и содержимое счетчика циклов. Если нет совпадения, т.е. на выходе элемента КЕ 11 появляется высокий потенциал, то в счетчик 12 -ЦИКЛОВ присчитывается единица. Процесс решения продолжается до совпадения и-нформации на блоках 9 и 10 сравнения. При совпадении сигнал с выхода схемы 8 сравнения запрещает процесс решения задачи, протекающий в модели регулярной сети по направлению часовой стрелки. Микропрограммный автомат 4 переходит в режим выделения единственного оптимального пути из полученного дерева Оптимальных путей. Устройство переходит ко второму этапу решения.. Вывод промежуточных решений совмещен -во времени с окончанием счета соответствующих моделей узлов. Запись их адресов в запоминающем блоке 2 производится последовательно. Поэтому если произвести считывание этих адресов с запоминающего блока 2 начиная с конца, то легко из полученного дерева оптимальных путей определить единственный оптимальный путь между заданными- точками. Выделение этого пути происходит также известным способом путем передачи сигнала из конечного узла в начальный, отмечая при этом те адреса, через которые проходит этот путь. Таким образом, на втором этапе работы устройства вычислительный процесс распространяется в противоположном направлении, т.е. по спирали против часовой стрелки.

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

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

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

0 первом этапе дерева оптимальных путей, В замкнутом устройстве исключается перестраивание устройства от фрагмента к фрагменту, которое в устройстве-прототипе производится

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

5

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

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

45 подключен ко второму информационному выходу микропрограммного блока управления, второй вход запоминающего блока соединен с первым выходом модели регулярной сети, о т л и ч а jQ ю щ е е с я тем, что, с целью упрощения устройства и повышения его быстродействия, в него введены блок анализа конечных узлов,, первый и, второй 9ХОДЫ которого подключены соответственно к третьему и четвертому выходам

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

60 третий вход которого соединен с третьим информационным выходом микропро rpcUHMHoro блока управления, первый и второй информационные входы которого подключены ко второму и третьему вы65 Ходам модели регулярной сети,

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

3.Устройство nd. п. I, отличающее с я тем, что микпропрограммный, блок управления содержит счетчики адреса, управляемый ге.нератор имплуьсов,. регистр сдвига и блок задания -режима, выход которого подключен .к первому входу управляемого генератора импульсов, выходы котороЗИЕЗПИЗ

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

5 Источники информации,

принятые во внимание при экспертизе

1,Авторское свидетельство СССР № 367431, кл. G Об G 7/122, 1968.

2.Додонов А.Г., Хаджинов В.В. 0 Об одном методе решения больших сетей на цифровых аналогах, В сб.гибридные вычислительные машины и комплексы. Киев, Ыаукова думка , 1975, с, 5, (прототип) .

U

.У

(Риг.2