Модель узла графа Советский патент 1980 года по МПК G06G7/122 G06F15/173 

(54) МОДЕЛЬ УЗЛА ГРАФА

Изобретение относится к области вычислительной техники и может быть испол аовано при построении спепиализирова аны вычислительньис устройств, предназначен- шлх для моделирования и решения задан на . Известно специализированное вычислительное устройство, предназначенное Для решения задач на графах, модели узлов которых содержит счетчики и логичесйе элементы 1 . Однако это устройство обладает невысокой надежностью и имеет ограниченную область применения. Наиболее близ1сим техническим решением к данному изобретению Является устройство, которое, как и данная модель узла графа, содержит первый элемент И, первый вход которого подключен к вХЬДному полюсу модели, вход тактовых HMitjotb- сов которой соединен с вторым входС) вого элемента И, выход которого соединен с функвдональным формирователем, которого соединен с единичным входом триггера, единичный вьссод которого соединен с входом элемента индикации, второй вход которого подключен к полюсу режима индикации модели, один выход эле мента индикации соединен с индикгщион- ным выходом модели, а его другой выход через первый рёзделительны15 диод соеди- нён с входным полюсом модели и одним выводом токового резистора, другой вывод которого соединен с утфавляющим полюсом модели, выходной полюс которой соединен с одним выводом второго разделительного Диода 2. Однако это устройство имеет ограниченные функциональные возможности и требует болылого количества времени для проверки работоспособности. Целью данного изобретения является повышение надежности и расширение функциональных возможностей. Указанная цель достигается тем, что модель узла графа содержит допоплитель- но второй и третий элементы И, элемент , .,,-... .. .- . У7 И-НЕ, элемент ИЛИ и инвертор, вход которого поШлнэчён к вьйсбдному nortidcy модели, а выход сюединен с третьим входом первого элемента И и первым входом второго элемента И, второй вход которого подключен к входному полюсу модели, а выход соединен с четвертым входом элемента индикации, единичный и нулевой выходы триггера соединены соответственно с первыми вход 19ми элемента И-НЕ и третьего элемента И, вторые входы которых подключены k полюсу опроса модели, сигнал1 ый выход которой соединен с выходом третьего элемента И в первым входом элемента ИЛИ, второй вход которого подключен к единичному выходу трйггерй, а вьоюд соединен с выходшдм полюсом модели, выход элемента И-НЕ соединен с свободным выводом второго разделител ного диода. На фиг. 1 щ)едставлена блок-схема мо дели узла графа; на фвг. 2 гцриведен пример исследуемого графа; на фиг. 3 приведена модель графа, соответствующая графу на фиг. 2, в которой модель узла: графа работает в режиме функциональной задержки; на г, 4 приведено дерево кра чайших путей графа на . 2; на фиг. 5 приведена модель дерева кратчайших путей на фиг. 4. Модель узла графа содержит функциональный формирователь 1, триггер 2, пер вый диод 3, второй диод 4, первый элемент И 5, третий элемент И 6, второй элемент И 7, элемент 8 нндикахшв, элемент ИЛИ 9, элемент И-НЕ 1О, токовый резистор 11 и инвертор 12. Элемент 8 йвдй1:Шяв ЬЬдёр кит элемен И 13, элемент ИЛИ 14 и штертор 15. Модель узла графа кфедааааачена для работы в состайе вьгаислительных структур, моделирующих различные задачи на графах. Модели узла графа соединяются между собой, или с моделями доугих компонент графа как, например, модели ветве модели стоков или ис5токов, и до., входны N01 полюсами 16 и выходными полюсе ли 17 согласно топологии графа бШйслителы ной структуры. При этом заявляемая мо-дель узла графа может работать в следующих режимах: 1)функциональной задержки, соответственной весовой функцйн узла графа сист мы. При передбне сигнала логической еди ницы с входного полюса 16 на выходной полюс 17; 2)огфоса состояний моделей узлов вы числительной структуры и запуска по об7наруженному признаку моделей других комПЬНёНТ структуру;: 3)передачи сигнала нулевого логического уровня в режиме индикации с выходного полюса 17 на входной полюс 16; 4)индикаций цепей различной конфигурации, начинающихся с данного узла структуры графа; 5)индикации своего состояния; 6)диагностики неисправности в модели узла графа; 7)формирования логической функции на входном полюсе 16. j --.- Перечисленные режимы 1-6 являются взаимоисключаемыми. - Режимы 1 и 7 могут вьшолняться одновременно. Тактовые импульсы подаются на вход 18 тактовых импульсов модели узла графа. В режиме 1 формирования функциональной задержки в исходном состоянии модели узла графа сигналом единичного логического уровня с полюса 19 настройки триггера 2 установлен в нулевое состояние, ав функциональном формирователе 1. установлено начальное значение моделируемой функции. На полюсах 19-22 в течение режима 1 необходимо присутствие сигналов нулевого логического уровня, а на вход 18 подаются тактовые импульсы от внешнего генератора. Запуск модели узла Грефа в режиме 1 производится сигналом логической единицы, подаваемым на входной полюс 16. При этом открывается элемент И 5 и сигналы настройки от внец него генератора поступают на вход функциональлого формирователя 1, который, от- работав, соответственно установленному нанальному значению моделируемой весовой функции, временную задержку, выдает с своего выхода сигнал логической единиЦЬ1 на единичный вход триггера 2, Триггер 2 устанавливается в единичное состояние. Сйгаал логической единицы с единичного выхода триггера 2 через элемент ИЛИ 9 подается на выходной полюс 17, где он щзисутствует до тех пор, пока не происходит сброс триггера 2 сигналом логической единицы с полюса 19. Сигнал логической единицы с выходного полюса 17 передается дальше на входные полюса моделей других компонент графа, соединенных согласно топологии вычислителыюй структуры с ним. Таким образом, происходит формирование, согласно весовой функции , временной задержки сигнала логической единицы, поступающего на входной полюс 16. Модели узла графа, соединенйые согласно топологии графа вычислительной структуры, могут находиться в одном из .двух состояний, определяемых триггером 2. В режиме 2 опроса состояния модели узла графа на полюсах 18 и 19 должны быть сигналы нулевого логического уровня. На входных полюсах 16 и выходных полюсах 17 могут быть сигналы логического нуля или логической единицы, х актер которых определяется состоянием моделей узлов графа вычислительной структуры. На полюс 20 опроьа подается сиг нал логической единицы. Если на входном полюсе 16 присутствует сигнал логического ну пи, то триггер 2 находится в нуле вом состоянии. Сигнал логической едй-i нишл с нулевого плеча триггера 2 подает ся на вход элемента Ибис его выхода на внеищий сигнальный выход 21 поступает сигнал единичного логического уровня, который свидетельствует о том, 4fo модель узла графа не сработала и не сформировала временную задержку. При этом, с выхода элемента И 6 через элемент ИЛИ 9 на выходной полвзр 17 поступает сигнал логической единиаы, который может быть сигналом пуска : для моделей других компонент графа, под- ключенных в составе вычислительной струк туры к выходному полюсу 17 модели узла графа. Работа модели узла графа в режиме 2 дает возможность автоматического подключения в опрашиваемые узлы графа вычислительной структуры и подачи в них сигнала логической единицы, длительность которого определяется длительность сигнала на полюсе 20 опроса. Э другом состоянии модели узла графа когда на выходном полюсе 17 будет сигнал логической единицы и триггер 2 находится в единичном состоянии, на выходе элемента И 6 и внешнем сигнальном вы- , - «К ходе 21 присутствует сигнал нулевого ло- гического уровня. Сигналы с внешнего сигнального выхода 21, свидетельстёу бщие о состоянии модели узла графа по- ступак т для анализа на внешнее опраипг- вающее устройство. В исходном состоянии модели узла графа в режиме 3 на входных полюсах 16 и выходных полюсах 17 присутствуют сигналы логической единицы. На полюс 22 режима индикации подается сигнал единичного логического уровня, а на остальные входные полюсы 18-20 - сигналы нулевого логического уровня, поступлении сигнала логического нуля, являющегося рабочим в режиме индикации, на выходной полюс 17 модели узла графа, присутствует сигнал логической единицы на выходе инвертора 12. Если триггер 2 находится в единичном состоянии, на выходе элемента И 15 в элементе 8 индикации присутствует сигнал нулевого логического уровня. При этом, сигнал единичного логического уровня на входном полюсе 16 через даод 3, работакаций в режиме вентиля, понижается до нулевого уровня на вькоде элемента И 15. Сигнал логической едини- цы на индикационном выходе 23 модели узла графа свидетельствует о том, что i она принадлежит индицируемой цепи, и Наоборот, когда триггер 2 находится в нулевом собтоянин, на индикационном выходе 23 и выходе элемента И 15 прйсутствуют соответственно сигналы логического нуля и логической единицы, то на входной :полюс 16 не передается сигнал нулевого логического уровня.Для работы модели узЛа графа в режиме 4 индикации цепей, начинающихся с данного узла графа структуры, когда на входном 16 и выходном 17 полюсах в исходном состоянии присутстсвуют сигналы логической единицы, необходимо присутствие сигналов логического нуля на полюсах 18 и 19, а,на полюсы 22 и 20 на- до подавать сигналы логической единицы. Сигнал единичного логического ypoBHk с единичного выхода триггера 2, обеспечивающий в этом режиме сигнал логической единицы в исходном состоянии на выходном полюсе 14, поступает на вход элемента И-НЕ 10, на выходе которого появляется сигнал логического йуля при подаче сигнала лозтичёской единицы на полюс 2О опроса. Сигнал логической единицы на выходном полюсе 17 через диод 4, работающий как вентиль, понижается до логического нулевого уровня, и дальше, аналогично тому, как это описано для режима 3, передается на входной полюс 16, откуда он ПОдтупает йаксйГнал индикации на модели других компонент графа вычислительной структуры. Принципиальная разница между режимами 3 и 4 заключается в том, что в первом случае сигнал логического нуля подается на выходной полюс 17 модели узла графа извне или от моделей других компонент графа, а во втором случае сама модель графа узла является сточником сигнала логического ну1Я. Для работы модели узла графа в режиме 5 индикации своего состояния на поюсах 19 и 18 необходимо присутствие SffНала логйческбгЪ нуля, а на полюс 20 опроса подается сигнал логической единицы. Если триггер 2 находится 6 единичном состоянииj то аналогично тому, как это имеет место в режиме 4, на выходном полюсе 17 присутствует сигнал логического нуля, на индикационном выходе 23 - сигнал логической единицы. В другим состоянии модели узла графа, когда триггер 2 находится в нулевом состоянии, на индикационном выходе 23 присутству -. ет сигнал логического нуля, так как нет разрешающего сигнала с единичного выхода, триггера 2 на вход элемента И 13. Разница между режущими 3, 4 и режимом , , 5 состоит Ё том, что при щ именении моделей узлов графа в вычислртельной струк туре в режиме 5 сигналь логической еди;ЕШЦЫПОД 1ЮТСЯ одновременно на ПОЛЮСЫ 20 опроса всех моделей узлов графа, а в режимах 3 и 4 она подаются последовательно. Для профилактической диагностики испрйвности имеется признак отказа в предлагаемой модели узла графа - наличие в установившемся режиме на выходном полюсе 17 сигнала логического Hyjm при сигнале ёдиничногнэ; логического уровня на вх:6дйом полюсе 16. В режиме 6 диагностики неисправности на полюсах 19, 2О и 22 необходимо присутствие сигналов логического нуля. Тек s еж на Шхбдйом полюсе 17 присутствует сигнал нулевого лйЬГИчёСкогчэ уровня, то с выхода инвертора 12 н вход элемента И 7 поступает сигнал логической единицы. Сигнал логи- ческо го ёшнйШОго: уровня с выхода элемента И 7 подается на вход элемента ИЛИ 14 в элементе 8 индикации, который вьйает сигнал логической-ед инйды на индиканионный выход 23, сигнализирующий о той, что модель узла графа неисправна Очень часто в узлах вычислительной структуры требуется реализовать логичес кие функции конъюнкций 1али дазъюцкций. Для этой цели модель узла, графа снабжена резистором 11, который подключен к входному полюсу 16. Вторым концом резистор 11 подключен через полюс 24 к источнику пнтанш. В §ШйШмости от вида логической функции, на выходных полю сах моделей компонент графа вычислитель ной структуры, подключаемых к входному полюсу 16, ставятся диоды, которые Щ)В подаче соответствующего, напряжения на второй конец резистора 11, образуют вместе с ним логические схемы И ила ИЛИ. Модедь узла графа может работать одновременно в режимах 7 и 1. При этом будет реализована сложная логико-временная функция. Уп1Ьавление гюдачей сигналов на полюса 18-20 и 22 модели узла графа может производиться внешним устройством вычислительной структуры, как, например, блоком управления, распределителем импульсов, и т.д. Причем, вследствие однородности и взаимозаменяемости моделей узлов графа, эти сигналы поступают одновременно и в одинаковых сочетаниях на полюса 18, 19 и 22 всех моделей узла графа, что ощэеделяет простоту управляющих цепей и устройств. На фиг. 5 приведен фрагмент модели графа, фиг. 3, соответствующий дереву кратчайших путей на фиг. 4. Для лучшего понимания назначения и принципа модели узла графа на фиг. 2 приведен пояснителы1ый пример. Граф на фиг. 2 изображает систему, состоящую из узлов (кружочки) и ветвей (стрелки). Каждый узел графа этой системы имеет различные функциональные веса, которые в данной системе, например, совпадают с номерами этих узлов. .Для простоты считаем, что ветви структуры не имеют веса, ia только указывают ориентацию связей между узлами. На фиг. 3 приведена вычислитёльн(ая структура, моделирующая задачу, изображенную на фиг. 2. В качестве модели ветви возьмем, например, вентильные ключи, хотя в общем случае модель ветви вьшолняет более сложные функции. Модели узлов графа и модели ветвей в устройстве, изофаженном на фиг. 3, соединяются между собой в соответствии с топологией графа моделируемой задачи на фиг. 2. В исходном состоянии в моделях узла графа функциональные формирователи 1 настроены на величину соответствующего моделируемого веса, а триггера 2 находятся в нулевом состоянии. Вычислительная структура на фиг. 3, .в которой модель узла графа работает в реж. 1 функциональной задержки, при подаче сигнала логической единицы на входной полюс 16 одной из этих моделей узлов моделирует распространение сигналов из данного узла. При таком включении вентильных схем в моделях ветвей, как показано на фиг. 3i вычислительная структура моделирует дизъюнктивную сеть. Подачей сигнала логической единицы в режиме 1 на. входной полюс 16 какойЧпибо модели узла графа определякэтр величины кратчайших путей иэ этой точки во все остальные узлы графа. Величина кратчайшего пути из какого-либо начального узла в любой t -и узел графа будет опрёШлят ся временем от начала подачи сигнала ло гической единицы на входной полюс 16 модели начального узла графа до появления .сигнала того же значения на входном полюсе 16 модели выбранного I -го узла графа. Функциональный формировйгелй. 1 каждой модели узла графа отрабатывает, в соответствии с заданным ф5гнкциональным весом, задержку появления сигнала логаческой единицы на выходном полюсе 17 при поступлении сигнала логической единицы на входной полюс 16. Сигналом с выходного полюса 17 одновременно запус каются все модели узлов графа, подключен .ные своими входными полюсами 16 к вышеуказа1шому вых:одному полюсу 17. Вен , тильные ключи в моделях ветвей определяют направление распространения сйгаа-лов логической единицы. Так, например, кратчайший путь из узла О и узел с графа на фиг. 2 будет равен 12 единицам. Если в момент появления сигнала ;10гичес кой единицы на входном, полюсе 17 модели 1 го узла графа в вычислительной структуре на фиг. 3 убрать сигналь тактовых импульсов с входов 18 всех моделей узлов графа, то этим мы фиксируем состояние графа на момент t 12. Пооче редной подачей сигналов логической единицы на полюса 20 моделей узла графа в режиме 2 определяем, что модели,уз лов О, 1-6 графа в момент t 12 окончили формирование своих функциональных весов, и в эти узлы графа определены кратчайшие пути. При этом подачей сигнала логической единицы на полюс 20 опроса мы выбираем любую модель узла графа, которая еще не сформировала свой функциональный вес, и подаем в нее сигналы пуска, что дает возможность автоматического подключения в любой узел вычислительной структуры. Дерево кратчайших путей для момента , определенное распространением сигналов логической единицы, показано на JQ фиг. 4. Ключи моделей ветвей, на выходы которых сигнал логической единицы гфихо- . дит раньше, чем на входы, закрыты. На входных полюсах 16 и выходных полюсах 17 моделей узлов графа, показанных на ,, фиг. 5, после момента t 12 присутствуют сигналы логической единицы При подаче Б режиме 3 сигнала логическозго нуля. на входной полюс 16 модели L -го узла графа, этот сигнал автоматически переда- ется через модели узлов 6, 3, 2, 1 и О на входной полюс 16 Модели узла О графа в вычислительной структуре, т.е. этот сигнал индицирует кратчайший путь от узла 1 до узла О в графе, изображв1шом на фиг. 2. Подача сигнала логического нуля в модели того или ирного сформированного узла графа вычислительной структуры для индикации кратчайшего пути из этого узла в начальный узел производится в режиме 4. В режиме 5 производится индикация состояний одновременно всех моделей узлов графа вычислительной структуры. В режиме 6, если какая-то мОдель узла графа после запуска вычислительного устройства дает отказ, на ее индикационном полюсе 23 присутствует сигнал логической единицы. 1. Заявляемая, модель узла графа выгодно отличается от указанного прототипа тем, что Она в составе вычислительных структур позволяет, наряду с ранее реша;емой задачей, решать и другие задачи, .как, например, нахождение экстремальных путей в сетевых задачах, в которых ветви |И узлы имеют функциональные веса, нахождения ошибок в ориентированном графе, нахождения оптимального рельефа в сети, и т.д. Для модели узла графа kapaKтерни, то, что она легко стыкуется с другими Цифровыми моделями и может применяться в составе известных к настоящему времени вычислительных структур на основе хшфровых моделей. При этом вследствие расширения круга решаемых задач, аагрузка специализированных вычислительных устройств, как, например, ЭВМ Ритм2 увеличится в два раза, что дает значительный экономический эффект от применения настоящего изобретения. Кроме то- , модель узла графа имеет самостоятелынОе значение и может применяться при создании новых специализированных вычислительных устройств. Вследствие .разделения входного и полюсов увеличивается нагрузочная способность модели узла графа по количеству соединяемых в одной точке элементов. Для построения модели узла графа используются известные элементы диокретной вычислительной техники. Поэтому надежность устройства, по сравнению с известными аналогами, увеличивается приблизительно на 20%, а если отказ в работе модели узла графа все же произойдет. то имеется признак его профилактическоW опрейШёнййГ ° Р У л а и 3 о б р е т е н и а Модель узла графа, содержащая первый элемент И, первый вход которого подклю.I. . вхой та ход которого соединен с первым входом , элемента индикации, второй вход которого Т oLl °. индикаши МОfi«S; TL . йндйкадий соединен с индикационным выходом модели, а его ФУГОЙ выход через первый разделительный элемент соединен с входным полюсом модели и одним выводом тохово- го резистора, другой вьюод обедйнёнй управляющим полюсом модели, выходной ПОЛИС которой соединен с однин )ЕШЬдой второго разделительного элемента, о т л и ч а ю щ ц я с я тем что, с целыо повышения надежности, она сЬдер .жит допо7П1Ительно второй и третий -- -Г-; - ;; - .. -. 71 77 менты И, элементИ-НБ, элемент иЛИ в инвертор, вход которого подключен к .ходному полнхзу модели, а выход соединен с третьим входом элемента индикации, третьим входом первого элемента И и первым входом второго элемента И, второй вход которого подключен к входному 1ЮЛЮ-, су модели, а в;ыход соединен с четвертым до„ элемента индикации единичный в входом элемента иншкации, единичный В сигналЗ с . «ен с выходом третье1х элемента иТ первым входом элемента ИЛИ, второй вход которого подклк чен к единичному одТ триггер а выход соединен с выходам мидели, элемента И-НЕ соединен с свободным выводом второго разде;шт ельного элемента. Источники информации, гфинятые во внимание при экспертизе 1.Авторсхбе свидетельство СССР N 433504, кл. О 06 G- 7/48, 1970. 2.Авторское сйидетельство СССР 367431, кл. G06 G 7/48, 1970 (прототип).

6

Фиг,.2

.фи1.

Фиг. 5