Модель узла графа

ОП ИСАНИЕизоветинияК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическикреспублик 17777 Ифс с.г(21) 2529914/18 2М(22)Заявлено с присоединен 3,10 ем за 5/ 0 уйэрстВФВВЙ квннтвт СССР 3) Приори 2,80, Бюллетень М теник УД (088 публиковало 1,325 вщщтв Дата опубликования описания 28,02,80(72) Авторы изобретен фенюк и Н. В, федотов А, Г нов,/ктродинам аинской 71) Заявител нст. (54) МОДЕЛЬ УЗЛА А с ации,пюсуд элеац выход соеди" дним ыводпюсоминеи аниче т",ребу- прои тс фу тем, чтопо а ттель 1Изобретение относится к области вы- которого соединен с единичным входочислительной техники и может быть исполь триггера, единичный выход которогоэовано при построении специализированных нен с первым входом элемента индиквычислительных устройств, предназначен- второй вход которого подключен к поных дл моделирования и решения задач режима индикации модели, один выхоя5мента индикации соединен с индик ина графах,7Известно специализированное вычисли- ным выходом модели, а ег друо о ли а его гойтельное устройство, предназначенное для через первый резделительный диодрешения задач на графах, модели узлов нен с входным полюсом модели и о.которых содержит счетчики и логические выводом токового резистора, другойкоторого соединен с управляюшим поэлементы , 1Однако это устройство обладает невы- модели, выходной полюс которой соедс окой надежностью и имеет ограниченную . с одним выводом второго разделительню диода 2 .область применения, ю диода 1 3.Однако это устройство имеет огрНаиболее близким техническим решени- ные функциональные в з1о ьнь е возможност ием к данному изобретению являетсяуст- ет большого количества времени длязла афа, содержит первый элемент И, Белью данного изобретения являепервый вход которой торою подключен к заодно- повышение надежности и расширение20м полюсу модели,. вход тактовых импуль циональных воем й.иональных воэможностей.сов которой соединен с вторым входом пер Указанная цУказанная цель достигаетсявого элемента И, выход которого соединен м де ь уэ рафмодель эла г афа содержит доно вто ой и третий элементы И, элемс функциональным формирователем, выход н Р Р3 .7177774 И-НЕ, элемент ИЛИ и инвертор, вход ко-наруженному признаку моделей других ком торого выключен к выходному полюсу мопонент структуры, дели, а выход соединен с третьим входом 3) передачи сигнала нулевого логичеспервого элемента И и первым входом вто- кого уровня в режиме индикации с выход- рого элемента И, второй вход которого 5 ного полюса 17 на входной полюс 16 р подключен к входному полюсу модели, а 4) индикации цепей различной конфигувыход соединен с четвертым входом эле- рации, начинающихся с данного узла струк мента индикации, единичный и нулевой вы- туры графа;ходы триггера соединены соответственно 5) индикации своего состояния; с первыми входами элемента И-НЕ и тре- О 6) диагностики неисправности в модетьего элемента И, вторые входы которых ли узла графа; подключены и полюсу опроса модели, сиг) формирования логической функции нальный выход которой соединен с выхо- на входном полюсе 16. дом третьего элемента И и первым входомэлемента ИЛИ, второй вход которого под- Перечисленные режимы 1-6 являются.15ключен к единичному выходу триггера, а взаимоисключаемыми. Режимы 1 и 7 мовьасод соединен с выходйым полюсом мо- . гут выполняться одновременно. Тактовые дели, выход элемента И-НЕ соединен с импульсы подаются на вход 18 тактовых свободным выводом второго разделитель-, импульсов модели узла графа ного диода, ;о В режиме 1 формирования функциональНа фиг. 1 представлена блок-схема мо- ной задержки в исходном состоянии моде- дели узла графа на фиг. 2 приведен при- ли узла графа сигналом единичного логимер исследуемого графа; на фиг. 3 приве ческого уровня с полюса 19 настройки дена модель графа, соответствующая гра- триггера 2 установлен в нулевое состоя 2 Яфу на фнг, 2, в которой модель узлание, ав функциональном формирователе 1 графа работает в режиме функциональнойустановлено начальное значение моделирузадержки; на фиг. 4 приведено дерево крат, емой функции. На полюсах 19-22 в течечайших путей графа на фиг. 2; на фиг. 5 ние режима 1 необходимо присутствие приведена модель дерева кратчайших путей сигналов нулевого логического уровня, а на фиг. 4.30на вход 18 подаются тактовые импульсыМодель узла трафа содержит функцио-, от внешнего генератора. Запуск модели узнальный формирователь 1, триггер 2, пер- ла графа в режиме 1 производится сигнавый диод 3, второй диод 4, первый эле- лом логической единицы, подаваемым на мент И 5, третий элемент И 6, второй входной полюс 16. При этом открывается элемент И 7, элемент 8 индикации, эле- элемент И 5 и сигналы настройки от внеш 35мейт ИЛИ 9 элемент И-НЕ 10, токовый него генератора поступают на вход функ- резистор 11 и инвертор 12, ционального формирователя 1, который,отЭлемент 8 индикацйисодержит элемент работаь, соответственно установленному И 13, элемент ИЛИ 14 и инвертор 15.начальному значению моделируемой весоМодель узла графа предйазначена для вой функции, временную задержку, выдает работы в составевычислительных струк- с своего выхода сигнал логической единитур, моделирующих различные задачи на ци на единичный вход триггера 2, Тригграфах. Модели узла графа соединяются гер 2 устанавливается в единичное состомежду собой, или с моделями других ком- яние, Сигнал логической единицы с еди 45понент графа,как, например, модели ветвей; пичного выхода триггера 2 через элемент модели стоков или истоков, и др., входны- ИЛИ 9 подается на выходной полюс 17, ми полюсами 16 и выходными полюсами где он присутствует до тех пор, пока не 17 согласно топологии графавычислитель происходит сброс триггера 2 сигналом лоной структуры. При этом заявляемая мо гической единицы с полюса 19, Сигнал, Ядель узла графа може 1 работать в жеду-логической единицы с выходного полюса ющих режимах; 17 передается дальше на входные полюса1) функциональной задержки, соответ- моделей других компонент графа, соединен- ственной весовой функции узла графа систе ных согласно топологии вычислительной мы при передаче сигнала логической еди- структуры с ним. Таким образом, происхоФ 55ницы с входного полюса 16 на выходной; днт формирование, согласно весовой функ-. полюс 17 уции узла, временной задержки сигнала ло2) опроса состояний моделей узлов вы гической единицы, поступающего на входчислительной структуры и запуска по об- ной полюс 16.5 717777 6Модели узла графа, соединенные сог- рабочим в режиме индикации, на выходнойласно топологии графа вычислительной полюс 17 модели узда графа, присутствуструктуры, могут находиться в одном иэ ет сигнал логической единицы на выходе,двух состояний, определяемых триггером инвертора 12. Если триггер 2 находится2. В режиме 2 опроса состояния модели 5 в единичном состоянии, на выходе элеменузла графа на полюсах 18 и 19 должны та И 15 в элементе 8 индикации присутбыть сигналы нулевого логического уров- ствует сигнал нулевого логического уровня, На входных полюсах 16 и выходных ня. При этом, сигнал единичного логичесполюсах 17 могут быть сигналы логичес- кого уровня на входном полюсе 16 черезкою нуля или логической единицы, хаак диод 3, работающий в режиме вентиля, потер которых определяется состоянием мо- нижается до нулевою уровня на эксодеделей узлов графа вычислительной струк- элемента И 15. Сигнал логической единитуры, На полюс 20 опроса подается си цы на индикационном выходе 23 моделинал логической единицы. Если на входном узла графа свидетельствует о том, чтополюсе 16 присутствует сигнал логичес она принадлежит индицируемой цепи, и накого нуля, то триггер 2 находится в нуде- . оборот, когда триггер 2 находится в нувом состоянии, Сигнал логической еди . левом состоянии, на индикацйонном выхо"ницы с нулевого плеча триггера 2 подает- де 23 и выходе элемента И 15 присутстся на вход элемента И 6 и с его выхода . вуют соответственно сигналы логическогона внешний сигнальный выход 21 посту- .0 нуля и логической единицы, то на входнойпает сигнал единичного логического уров- полюс 16 не передается сигнал нулевогоня, который свидетельствует о том, что логического уровня.модель узла графа не сработала и не ":Для работы модели узла графа в режисформировала временную задержку.:. ме 4 индикации цепей, начинающихся сПри этом, с выхода элемента И 6 че- данного узда графа структуры, когда на25реэ элемент ИЛИ 9 на ьыходной полюс .,входном 16 и выходном 17 полюсах в ис 17 поступает сигнал логической единицы, ходном состоянии присутстсвуют сигналыкоторый может быть сигналом пуска логической единицы, необходимо присутдля моделей других компонент графа, йод-ствие сигналов логического нуля на полюключенных в составе вычислительной струк сах 18 и 19, а на подюсы 22 и 2 натуры к вь нт ы к выходному полюсу 17 модели уз до подавать сигналы логической единицы.вкяла графа. Работа модели узла графа в ре- Сигнал единичного логического уровкжиме 2 дает возможность автоматическо- с единичного выхода триггера 2, обеспего подключения в опрашиваемые узлы"гра чивающий в этом режиме сигнал логичесфа вычислительной структуры и подачив кой единицы в исходном состоянии на вы 35них сигнала логической единицы, ддитель- ходком полюсе 14, поступает на вход эленость которого определяется длительностью мента И-НЕ 10, на выходе которого появсигнала на полюсе 20 опроса, ,:. ляется сигнал логического нуля при пода,В др гом состоянии модели узла графа, че сигнала логической единицы на полюсУ ф 40когда на выходном полюсе 17 будет сиу 20 опроса. Сигнал логической единицы нанал логической единицы и триггер 2 "нахо- выходном полюсе 17 через диод 4, рабодится в единичном состоянии, на выходетающий как вентиль, понижается до логиэдемента И 6 и внешнем сигнальномвы- ческого нулевою уровня, и дальше, анало-ходе 21 присутствует сигнал нулевою ло-" "аничко тому, как это описано ддя режимагического уровня, Сигналы с внешнею 3, передается на входной полюс 16, откусигнального выхода 21, свидетельствуй." да он-поступает как сигнал индикации на щие о состоянии модели узла графа по- модели других компонент графа вычисли- ступают для анализа на внешнее опрашк- тельной структуры, Принципиальная разнивающее устройство.ца между режимами 3 и 4 заключается50В исходиом состоянии модели узла гра- в том, что в первом случае сигнал гифа в режиме 3 на входных полюсах 16 и ческого нуля подается на выходной полюс выходных полюсах 17 присутствуют сигна модели узда графа извне или от моделы логической единицы. На полюс 22 ре-лей других компонент графа, а во второмжима индикации подается сигнал единично- случае сама модель графа уэ"а " го логического уровня, а на остальные источником сигнала логического нуля, входные полюсы 18-20 - сигналы нулевого логического уровня, При поступлении ме 5 индикациикации своего состояния нв полюсах 19 и 18 необходимо присутствие , сигнала логического нуля, являющегося7 7177 "сигйала логического нуля, а на полюс 20 опроса подается сигнал логической единицы. Если триггер 2 находитсяв единичном состоянии,то аналогично тому, как это имеет место в режиме 4, на выходном полюсе 17 присутствует сигнал логического нуля, на индикационнсм выходе 23 - сигнал логической единицы. В другом состоянии модели узла графа,когда триггер 2 находится в нулевом состоянии, 1 О нв индикационном выходе 23 присутству ет сигнал логического нуля, так как нет разрешающего сигнала с единичного выхода. триггера 2 на вход элемента И 13. Разница между режущими 3, 4 и режимом 5 состоит в том, что при применейии моделей узлов графа в вычислительной струк-туре в режиме 5 сигналы логической еди- ницы подаются одновременно на пЬлюсй 20 опроса всех моделей узлов графа, а в режимах 3 и 4 они подаются последовательно. Для профилактической диагностики ис- правности имеется признак отказа в предлагаемой модели узла графа - наличие вустановившемся режиме нв выходном .полюсе 17 сигнала логического нуля присигнале единичного,логического уровня навходйом полюсе 16. В режиме 6 диагнос; Зотики неисправности на полюсах 19, 20 и2 2 йеобходимо присутствйе сигналов логического нуля, Твк как нв -выходном полюсе 17 присутствует сигнал нулевого "логического уровня, то с выхода Инверто-, З 5рв 12 на вход элемента И 7 поступаетсигнал логической единицы, Сигнал логического единичного; уровня с выхода элемента И 7 подается на вход элементаИЛИ 14 в элементе 8 индикации,.который40выдает сигнал логйческой единицы на индикационный выход 23, сигналиэирующийо том что модель узла графа неисправна.Очень часто в узлах вычислительной15структуры требуется реализовать логические функции конъюнкцйй или дизьюнкций.Для этой цели модель узла, графа снабже-на резистором 11, который подключен квходному полюсу 16, Вторым концом резистор 11 подключен через полюс 24 кисточнику питания, В зюиЖмости"бт вида логической функции, на выходных полю;сах моделей компонент графа вычислитель-ной структуры, подключаемых к входному55полюсу 16, ставятся диоды, которые приподаче соответствующего напряжения навторой конец резистора 11, образуютвместе с ним логические схемы И или 77 8ИЛИ,Модель узла графа может работатьодновременно в режимах 7 и 1, При этомбудет реализована сложная логико-временная функция,Управление подачей сигналов на полюса 18-20 и 22 модели узла графа можетпроизводиться внешним устройством вычислительной структуры, как, например,блоком управления, распределителем импульсов, и т,д. Причем, вследствие однородности и взаимозаменяемости моделейузлов графа, эти сигналы поступают одновременно и в одинаковых сочетаниях наполюса 18, 19 и 22 всех моделей узлаграфа, что определяет простоту управляющих цепей и устройств. На фиг. 5 приведен фрагмент модели графа, фиг. 3, соответствующий дереву кратчайших путей нафиг. 4,Для лучшего понимания назначения ипринципа работы модели узла графа нвфиг. 2 приведен пояснительный пример.Граф на фиг. 2 изображает систему, состоящую из узлов (кружочки) и ветвей(стрелки). Каждый узел графа этой системы имеет разлинные функциональные веса,которые в данной системе, например, совпадают с номерами этих узлов. Для простоты считаем, что ветви структуры неимеют веса, а только указывают ориентацию связей между узлами. На фиг, 3 приведена вычислительная структура, моделирующая задачу изображенную на фиг, 2,В качестве модели ветви возьмем, например, вентильные ключи, хотя в общем случае модель ветви выполняет более сложные функции, Модели узлов графа и модели ветвей в устройстве, изображенном нафиг. 3, соединяются между собой в соответствии с топологией графа моделируемойзадачи на фиг. 2. В исходном состоянии вмоделях узла графа функциональные формирователи 1 настроены на величину соответствующего моделируемого веса, атриггера 2 находятся в нулевом состоянии,Вычислительная структура на фиг. 3,в которой модель узла графа работает вреж. 1 функциональной задержки, при подаче сигнала логической единицы нв входной полюс 16 одной из этих моделей узлов моделирует распространение сигналовиз данного узла. При таком включении вентильных схем в моделях ветвей, как показано на фиг. 3, вычислительная структурамоделирует дизьюнктивную сеть, Подачейсигнала логической единицы в режиме 1на входной полюс 16 какой-либо моделиузла графа определяют величины кратчай103 аявляемая, модель узла графа выгодно отличается от указанного прототипа тем, что она в составе вычислительных структур позволяет, наряду с ранее реша,емой задачей, решать и другие задачи, как, например, нахождение экстремальных путей в сетевых задачах, в которых ветви и узлы имеют функциональные веса, на.хождения ошибок в ориентированном графе, нахождения оптимального рельефа в сети, и т,д. Для модели узла графа характерно, то, что она легко стыкуется с другими цифровыми моделями и может применяться в составе известных к настоящему времени вычислительных структур на основе цифровых моделей. При этом вследствие расширения круга решаемых задач, загрузка спедиализиров вццых вычислительных устройств, квк, например, ЭВМ "Ритм увеличится в двв рвзв, что дает значительный зкономический эффект от прима кения настоящего изобретения. Кроме того, модель узла графа имеет самостоятель. цое значение и может применятьсй при создании новых специализированных вычислительных устройств. Вследствие .разделения входного и выходного полюсов увеличивается цагруэочцвя способность модели узла графа по количеству соединяемых в одной точке элементов. Для построения модели узла графа используются известные элементы диокретной вычислительной техники. Поэтому надежность устройства, по срввцецию с известными аналогами, увеличиввется приблизительно на 20%, в если откез в работе модели узла графа все же произойдет,9 7177ших путей из этой точки во все остальные узлы графа, Величина кратчайшегопути из какого-либо начального узла влюбой-й узел графа будет определяться временем от начала подачи сигнала логической единицы нв входной полюс 16 модели начального узла графа до появления,сигнала того же значения на входном полюсе 16 модели выбранного с, -го узлаграфа, функциональный формирователь 1каждой модели узла графа отрабатывает,в соответствии с заданным функционвльным весом, задержку появления сигналалогической единицы на выходном полюсе17 при поступлении сигнала логической15единицы на входной полюс 16. Сигналом свыходного полюса 17 одновременно запускаются все модели узлов графа, подключен,ные своими входными полюсами 16 к вышеуказанному выходному полюсу 17 Вен 20тильные ключи в моделях ветвей определяют направление распространения сйгнвлов логической единицы. Так, например,кратчайший путь из узла О и узел ь гра-.25фа на фиг. 2 будет равен 12 единицам,Если в момент появленич сигнала логической единицы на входном. полюсе 17 модели ь -го узла графа в вычислительнойструктуре нв фиг. 3 убрать сигналы так 30товых импульсов с входов 18 всех моделей узлов графа, то этим мы фиксируемсостояние графа на момент :12. Поочередной подачей сигналов логической единицы на полюса 20 моделей узла графа35в режиме 2 определяем, что модели узлов О, 1-6 графа в момент=12 окончили формирование своих функциональныхвесов, и в эти узлы графа определеныкратчайшие пути. При этом подачей сигнала логической единицы на полюс 20 опроса мы выбираем любую модель узлаграфа, которая еще не сформировала свойфуйкциональный вес, и подаем в нее сигналы пуска, что цвет возможность автоматического подключения в любой узелвычислительной структуры,Дерево кратчайших путей для момента= 12, определенное распространениемсигналов логической единицы, показано нафиг. 4, Ключи моделей ветвей, на выходыкоторых сигнал логической единицы приходит раньше, чем нв входы, закрыты, Нввходных полюсах 16 и выходных полюсах17 моделей узлов графа, показанныхнафиг. 5, после момента , =12 присутствуют сигналы логической единицы, При подаче в режиме 3 сигнала логического нуля.на входной полюс 16 модели-го узла графа, этот сигнал автоматически передается через модели узлов 6, 3, 2, 1 и Она входной полюс 16 Модели узла О графа в вычислительной структуре, т.е, этотсигнал индицирует кратчайший путь от узладо узла О в графе, изображенномна фиг. 2, Подача сигнала логическогонуля в модели того или иного сформированного узла графа вычислительной структуры для индикации кратчайшего пути изэтого узлав начальный узел производится в режиме 4. В режиме 5 производитсяиндикация состояний одновременно всехмоделей узлов графа вычислительной структуры. В. режиме 6, если какая-ао модельузла графа после запуска вычислительного устройства дает отказ, на ее индикационном полюсе 23 присутствует сигналлогической единицы.11 . 717777 12,то имеется признак его профилактическо-менты И, элемент И-НЕ, элемент ИЛИ иго "опрздмения." . инвертор, вход которого подключен к вы,ходному полюсу модели, а выход соединенс третьим входом элемента индикации,Ф о р м у л а и з о б р е т е н и я, третьим входом первого элемента И и первым входом второго элемента И, второйМодель узла графа, содержащая первый вход которого подключен к входиому полюэлемент И, первый вход которого подклю- су модели, а выход соединен с четвертым:чен к входному полюсу модем, вход так- входом элемента индикации, единичный и-товых"ймйульсов которой соедийен.с вто. нулевой выходы триггера соединены сооврьм входом первого элемента И, выход ветственно с йервьва входами элементакоторого соединен с функциональным фор- И-НЕ и третьего элемента И,"вторые. вхо-,мирователэм, выход которого соединен с " дыкоторых подключены к полюсу опросаединичнйм входом триггера, единичный вы, модели, сигнальный вйход которой соедиход которого соединен с первым входомнен с выходом третьего элемента И иэлемента индикации, второй вход"которогопервым входом элемента ИЛИ, второй входйбдключен к полюсу рейима индикации ма которого подключен к единичному выходу- дели, один выход элемента йндйкации соек триггера, а выход соединен с выходным" диненс инднкациощЫм" выходбм модели,. полюсом модели, выход элемента И-НЕа его другой выход через первый разде О соединен с свободным выводом второголительный элемент соединен свходнымразделительного элемента.полюсом модели и одним выводом токово-,го резисгора, другой вывод котоРою сое-Источники информации,диненс управляющим полюсом модели,принязЪю во внимание при экспертизевыходной полюс которой соединен с одним1, Авторское свидетельство СССРвЪводомвторого рааделйтел 4 ноб алеман . М 433504, кл. О 06 С 7/48, 1970.та, о т л и ч а ю щ а я с я тем, что, 2, .Авторское свидетельство СССРс целью повышения надежности, она сздеР М 367431, кл, 6 06 О 7/48, 1970