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

 

ОП ИСАНИЕ изоь етиния

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

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

Социалистических республик

17777 (5E ) Дополнительное к авт. саид-вуМ. Кл. (22) Запвлено03.10.77 (21) 2529914/18-24 с присоединением заявки М06 F 15/20

Ьвуаеретвапвй квинтет

СССР

Io aeaat имвретвнив и втхрмтвв (23}ПриоритетОпубликоваио25.02.80. Бюллетень М 7

УДК 681,325 (088,8 }

Дата опубликования описания 28.02.80

I (72) Авторы изобретении

А. Г. Додонов, Я, Я. Фенюк и H. В. Федотов

Институт электродинамики АН Украинской ССР

{71) Заявитель (54} МОДЕЛЬ УЗЛА ГРАФА

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

5 на графах.

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

Однако это устройство обладает невы- сокой надежностью и имеет ограниченную

f область применения.

3S

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

I которого соединен с единичным входом триггера, единичный выход которого соединен с первым входом элемента индикации, второй вход которого подключен к полюсу режима индикации модели, один выход элемента индикации соединен с индикацион / ным выходом модели, а его другой выход через первый резделительный диод соеди нен с входным полюсом модели и одним выводом токового резистора, другой вывод которого соединен с управляюшим полюсом модели, выходной полюс которой соединен с одним выводом второго разделительного диода (2).

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

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

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

3 717777

И-НЕ, элемент ИЛИ и инвертор, вход ко- наруженному признаку моделей других ком торого пбйключен к выходному полюсу мо«понент структуры, дели, а выход соединен с третьим входом 3) передачи сигнала нулевого логичеспервого элемента И и первым входом вто- кого уровня в режиме индикации с выходрого элемента И, второй вход которого 5 ного полюса 17 на входной полюс 16; подключен к входному полюсу модели, а 4) индикации цепей различной конфигувыход соединен с четвертым входом эле- рации, начинающихся с данного узла струк» мента индикации, единичный и нулевой вы- туры графа; ходы триггера соединены соответственно 5) индикации своего состояния; с первыми входами элемента И-НЕ и тре- 0 6) диагностики неисправности в модетьего элемента И, вторые входы которых ли узла графа; подключены к полюсу опроса модели, сиг- 7) формирования логической функции нальный выход которой соединен с выхо- на входном полюсе 16. дом третьего элемента И и первым входом элемента ИЛИ, второй вход которого под- Перечисленные режимы 1-6 являются .15 ключен K единичному выходу триггера, а взаимоисключаемыми. Режимы 1 и 7 мовьасод соединен с выходйым полюсом мо- . гут выполняться одновременно. Тактовые дели, выход элемента И HE соединен с импульсы подаются на вход 18 тактовых свободным выводом второго разделитель». импульсов модели узла графа.. ного диода. о В режиме 1 формирования функциональНа фиг. 1 представлена блок-схема мо- ной задержки в исходном состоянии моде- дели узла графа на фиг. 2 приведен при- ли узла графа сигналом единичного логимер исследуемого графа; на фиг. 3 приве» ческого уровня с полюса 19 настройки дена модель графа, соответствующая гра- триггера 2 установлен в нулевое состояфу H& фнг. 2, .в которой модель узла ние, а в функциональном формирователе 1 графа работает в режиме функциональной : установлено начальное значение моделирузадержки; на фиг. 4 приведено дерево крат емой функции. На полюсах 19-22 в течечайших путей графа на фиг. 2; на фиг. 5 ние режима 1 необходимо присутствие приведена модель дерева кратчайших путей сигналов нулевого логического уровня, а на фиг. 4.

30 на вход 18 подаются тактовые импульсы

Модель узла трафа содержит функцио-,, от внешнего генератора. Запуск модели узнальный формирователь 1, триггер 2, пер- ла графа в режиме 1 производится сигнавый диод 3, второй диод 4, первый эле- .лом логической единицы, подаваемым на мент И 5, третий элемент И 6, второй входной полюс 16. При этом открывается элемент И 7, элемент 8 индикации, эле- элемент И 5 и сигналы настройки от внеш35 мейт ИЛИ 9, элемвнт И HE 10, токовый него генератора поступают на вход функрезистор 11 и инвертор 12. ционального формирователя 1, который,отЭлемент 8 индикации содержит элемент работаь, соответственно установленному

И 13, элемент ИЛИ 14 и инвертор 15. начальному значению моделируемой весоМодель узла графа предназначена для вой функции, временную задержку, выдает работы в составе вычислительных струк- с своего выхода сигнал логической единитур, моделирующих различные задачи на цы на единичный вход триггера 2. Тригграфах. Модели узла графа соединяются гер 2 устанавливается в единичное состомежду собой или с моделями других ком- яние, Сигнал логической единицы с еди3

45 понент графа,как, например, модели ветвей; пичного выхода триггера 2 через элемент модели стоков или истоков, g др., входны- ИЛИ 9 подается на выходной полюс 17, ми полюсами 16 и выходными полюсами где он присутствует до тех пор, пока не

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

1) функциональной задержки, соответ- моделей других компонент графа, соединенственной весовой функции узла графа систе ных согласно топологии вычислительной мы при передаче сигнала логической еди- структуры с ним. Таким образом, происхо55 ницы с входного полюса 16 на выходной; дит формирование, согласно весовой функ-. полюс 1 jg ции узла, временной задержки сигнала ло«

2) опроса состояний моделей узлов вы гической единицы, поступающего на входчислительной структуры и запуска по об- ной полюс 16, 5 717777 6

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

2. В режиме 2 опроса состояния модели 5 в единичном состоянии, на выходе элеменузла графа на полюсах 18 и 19 должны та И 15 в элементе 8 индикации присутбыть сигналы нулевого логического уров- ствует сигнал нулевого логического уров ня. На входных полюсах 16 и выходных ня. При этом, сигнал единичного логичесполюсах 17 могут быть сигналы логичес- кого уровня на входном полюсе 16 через кого нуля или логической единицы, xepaK- o диод 3, работающий в режиме вентиля, потер которых определяется состоянием мо- нижается до нулевого уровня на эксоде делей узлов графа вычислительной струк- элемента И 15. Сигнал логической единитуры. На полюс 20 опроса подается си1 цы на индикационном выходе 23 модели нал логической единицы. Если на входном узла графа свидетельствует о том, что полюсе 16 присутствует сигнал логичес- 15 она принадлежит индицируемой цепи, и накого нуля, то триггер 2 находится в нуле- оборот, когда триггер 2 находится в нувом состоянии. Сигнал логической еди - . левом состоянии, на индикацйонном выхо ницы с нулевого плеча триггера 2 подает" де 23 и выходе элемента И 15 присутстcs на вход элемента И 6 и с его выхода . вуют соответственно сигналы логического на внешний сигнальный выход 21 посту- . 6. нуля и логической единицы, то на входной

° пает сигнал единичного логического уров- . полюс 16 не передается сигнал нулевого ня, который свидетельствует о том, что логического уровня. модель узла графа не сработала и не ": Для работы модели узла графа в режисформировала временную задержку.: . Ме 4 индикации цепей, начинающихся с

При этом, с выхода элемента И 6 че- данного узла графа структуры, когда на

25 рез элемент ИЛИ 9 на ьыходной полюс .; входном 16 и выходном 17 полюсах в ис17 поступает сигнал логической единицы, ходном состоянии присутстсвуют сигналы который может быть сигналом пуска .. логической единицы, необходимо присутдля моделей других компонент графа, йод- ствие сигналов логического нуля на полюключенных в составе вычислительной струк- сах 18 и 19, а на полюсы 22 и 2 натуры к вь н т ы к выходному полюсу 17 модели уз до подавать сигналы логической единицы. вкя ла графа. Работа модели узла графа в ре- Сигнал единичного логического уровк жиме 2 дает возможность автоматическо- с единичного выхода триггера 2, обеспего подключения в опрашиваемые узлы" гра чивающий в этом режиме сигнал логичесфа вычислительной структуры и подачи в кой единицы в исходном состоянии на вы35 них.сигнала логической единицы, длитель ходном полюсе 14, поступает на вход эле« ность которого определяется длительностью мента И-НЕ 10, на выходе которого появ сигнала на полюсе 20 опроса. -,:. ляется сигнал логического нуля при пода,В др гом состоянии модели узла графа, че сигнала логической единицы на полюс

У 4P когда на выходном полюсе 17 будет сиу 20 опроса. Сигнал логической единицы на нал логической единицы и триггер 2 нахо- выходном полюсе 17 через диод 4, рабодится в единичном состоянии, на выходе - тающий как вентиль, понижается до логиэлемента И 6 и внешнем сигнальном "вы - ческого нулевого уровня, и дальше, аналоходе 21 присутствует сигнал нулевого ло-" - ично тому, как это описано для режима гического уровня. Сигналы с внешнего 3, передается на входной полюс 16, откусигнального выхода 21, свидетельствуй - да он -поступает как сигнал индикации на щие о состоянии модели узла графа по- модели других компонент графа вычислиступают для анализа на внешнее опращи- тельной структуры. Принципиальная разнивающее устройство. ° . ца между режимами 3 и 4 заключается

В исходиом состоянии модели узла гра- в том, что в первом случае сигнал гифа в режиме 3 на входных полюсах 16 и ческого нуля подается на выходной полюс выходных полюсах 17 присутствуют сигна- 17 модели узла графа извне или от моделы логической единицы. На полюс 22 pe- лей других компонент графа, а во втором жима индикации подается сигнал единично- случае сама моде граф узла Ыяе го логического уровня, а на остальные источником сигнала логического нуля. входные полюсы 18-20 - сигналы нулевого логического уровня. При поступлении ме 5 индикации капни своего состояния на полюсах 19 и 18 необходимо присутствие, сигнала логического нуля, являющегося

7 7177

" сигйала логического нуля, а на полюс 20 опроса подается сигнал логической единицы. Если триггер 2находитсяв единичном состоянии то аналогично тому, как это имеет место в режиме 4, на выходном полюсе 17 присутствует сигнал логического нуля, на индикационнсм выходе

23 - сигнал логической единицы. B аругом состоянии модели узла графа, когда триггер 2 находится в нулевом состоянии, на индикационном выходе 23 присутству ет сигнал логического нуля, так как нет разрешающего с игнала с единичного выхода триггера 2 на вход элемента И 13.

Разница между режущими 3, 4 и режимом,, 5 состоит в том, что при применейии моделей узлов графа в вычислительной струк-

/ туре в режиме 5 сигналы логической еди- ницы подаются одновременно на июлей

20 опроса всех моделей узлов графа, а в режимах 3 и 4 они подаются последовательно.

Llama профилактической диагностики ис-

--правности имеется признак отказа в предлагаемой модели узла графа - наличие в установившемся режиме на выходном полюсе 17 сигнала логического нуля при сигнале единичного,логического уровня на входйом полюсе 16. В режиме 6 диагнос; ЗО тики неисправности на полюсах 19, 20 и

22 йеобходимо присутствйе сигналов логического нуля. Так r.àK на выходном по люсе 17 присутствует сигнал нулевого логического уровня, то с выхода Инверто- ; З5 ра 12 на вход элемента И 7 поступает сигнал логической единицы. Сигнал логическо1.о единичного; уровня с выхода эле40 мента И 7 подается на вход элемента

ИЛИ 14-в элементе 8 индикации, который . выдает сигнал логйческой едийицы на индикационный выход 23, сигналиэирующий о том; что модель узла графа неисправна.

Очень часто в узлах вычислительной 5 структуры требуется реализовать логические функции конъюнкцйй или дизьюнкций.

Для этой цели модель узла, графа снабже- на резистором 11, который подключен к входному полюсу 16, Вторым концом резистор 11 подключен через полюс 24 к источнику питания. В зЮиМФмости "от вида логической функции, на выходных полю сах моделей компонент графа вычислительной структуры, подключаемых к входному

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

77 8

ИЛИ. Модель узла графа может работать одновременно в режимах 7 и 1. При этом будет реализована сложная логико-времен1 ная функция.

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

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

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

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

Вычислительная структура на фиг. 3, в которой модель узла графа работает в реж. 1 функциональной задержки, при подаче сигнала логической единицы на входной полюс 16 одной из этих моделей узлов моделирует распространение сигналов из данного узла. При таком включении вентильных схем в моделях ветвей, как показано на фиг. 3, вычислительная структура моделирует дизьюнктивную сеть. Подачей . сигнала логической единицы в режиме 1 на входной полюс 16 какой-либо модели узла графа определяют величины кратчайгими цифровыми моделями и может применяться в составе известных к настоящему времени вычислительных структур на основе цифровых моделей. При этом вследствие расширения круга решаемых задач, загрузка специализированных вычислительных устройств, квк, например, ЭВМ "Ритм2 увеличится B двв рвзв, что дает знвчительный зкономический эффект от приме кения настоящего изобретения. Кроме того, модель узла графа имеет свмостоятель ное значение и может применяться при создании новых специализированных вычислительных устройств.

Вследствие .разделения входного и выходного полюсов увеличивается нвгруэочнвя способность модели узла графа по количеству соединяемых в одной точке элементов. Для построения модели узла графа используются известные элементы диокретной вычислительной техники. Поэтому ! надежность устройства, по сравнению с известными аналогами, увеличивается приблизительно на 20%, в если откез в рвбоТе модели узла графа все же произойдет, 9 7177 ших путей из этой точки во все остальные узлы графа. Величина кратчайшего пути из какого-либо начального узла в любой -й узел графа будет определять ся временем от начала подачи сигнала ло- 5 ! гической единицы нв входной полюс 16 модели начального узла графа до появления ,сигнала того же значения на входном полюсе 16 модели выбранного -го узла графа. Функциональный формирователь 1 каждой модели узла графа отрабатывает, в соответствии с заданным функционвль ным весом, задержку появления сигнала логической единицы на выходном полюсе

17 при поступлении сигнала логической

15 единицы на входной полюс 16. Сигналом с выходного полюса 17 одновременно запускаются все модели узлов графа, подключен,ные своими входными полюсами 16 к вышеуказанному выходному полюсу 17. Вен20 тильные ключи в моделях ветвей определяют направление распространения с!йгнв лов логической единицы. Так, например, кратчайший путь из узла 0 и узел ь гра-.

25 фа на фиг. 2 будет равен 12 единицам.

Если в момент появленич сигнала логической единицы на входном. полюсе 17 модели L -го узла графа в вычислительной структуре нв фиг. 3 убрать сигналы твк30 товых импульсов с входов 18 всех моделей узлов графа, то этим мы фиксируем состояние графа на момент t. =12, Поочередной подачей сигналов логической единицы на полюса 20 моделей узла графа

35 в режиме 2 определяем, что модели узлов О, 1-6 графа в момент t =12 окончили формирование своих функциональных весов, и в эти узлы графа определены кратчайшие пути. При этом подачей сигнала логической единицы на полюс 20 опроса мы выбираем любую модель узла графа, которая еще не сформировала свой фуйкциональный вес, и подаем в нее сит налы пуска, что пает возможность автоматического подключения в любой узел вычислительной структуры.

Дерево кратчайших путей для момента = 12, определенное распространением сигналов логической единицы, показано на фиг. 4. Ключи моделей ветвей, на выходы которых сигнал логической единицы приходит раньше, чем нв входы, закрыты. Нв входных полюсах 16 и выходных полюсах

17 моделей узлов графа, показанных нв фиг. 5, после момента ф. =12 присутствуют сигналы логической единицы, При подаче в режиме 3 сигнала логического нуля. на входной полюс 16 модели -го узла

77 10 графа, этот сигнал автоматически передается через модели узлов 6, 3, 2, 1 и 0 на входной полюс 16 Модели узла 0 графа в вычислительной структуре, т.е. этот сигнал индицирует кратчайший путь от узла до узла 0 в графе, изображенном на фиг. 2. Подача сигнала логического нуля в модели того или иного сформированного узла графа вычислительной струк туры для индикации кратчайшего пути из этого узла в начальный узел производится в режиме 4. В режиме 5 производится индикация состояний одновременно всех моделей узлов графа вычислительной структуры. В. режиме 6, если какая-ч о модель узла графа после запуска вычислительного устройства дает отказ, на ее индикационном полюсе 23 присутствует сигнал логической единицы.!

Заявляемая, модель узла графа выгодно отличается от указанного прототипа тем, что она в составе вычислительных структур позволяет, наряду с ранее реша,емой задачей, решать и другие задачи, квк, например, нахождение экстремальных путей в сетевых задачах, в которых ветви и узлы имеют функциональные веса, на хождения ошибок в ориентированном графе, нахождения оптимального рельефа в сети, и т.д. Для модели узла графа характерно, то, что она легко стыкуется с дру11 . 717777 12. то имеется признак его профилактическо- менты И, элемент И-НЕ, элемент ИЛИ и го "опрздИхений.. инвертор, вход которого подключен к вы ,ходному полюсу модели, а выход соединен с третьим входом элемента индикации, Ф о р м у л а и з о б р е т е н и я,g третьим входом первого элемента И и Esp-. вым входом второго элемента И, второй

Модель узла графа, содержащая первый вход которого подключен к входиому полю-! элемент И, первый вход которого подклю- су модели, а выход соединен с четвертым: чен к входному полюсу моде щ вход так- входом элемента индикации, единичный и - товых ймпульсов которой- соедийен. с вто- 1з. нулевой выходы триггера соединены coom рьян входом первого элемента И, выход ветственно с йервыми входами элемента которого соединен с функциональным фор- И-НЕ и третьего элемента И, вторые вхо-; мирователем, выход которого соединен с " ды котоpых подключены к полюсу опроса ° единичнЫм входом триггера, единичный вы, модели, сигнальный sHxog которой соедиход которого соединен с первым входом i>> нен с выходом третьего элемента И и элемента индикации, второй вход".которого первым входом элемента ИЛИ, второй вход йодключен к полюсу режима индикации ма . которого подключен к единичному выходу - дели, один выход элемента йндйкации сое триггера, а выход соединен с выходным

" дийен с индикационным выходом модели, . полюсом модели, выход элемента И-НЕ а его другой выход через первый разде- о соединен с свободным выводом второго лительный элемент соединен с входным разделительного элемента. полюсом модели и одним выводом блоково го резистора, другой sbIBo+ котЬРою сое.- Источники информации, динен с правляющим полюсом модели, принятие во внимание при экспертизе выходной полюс которой соединен с одним 2" 1. Авторское свидетельство СССР

° - - в дводом второго разделительного алеман . М 433504, кл. G 06 С 7/48, 1970. та, отличающаяся тем, что, 2..Авторское свидетельство СССР с целью повышения надежности, она содер М 367431, кл. G 06 G 7/48, 1970 жит дополнительно второй и третий эле- (прототип).й !

717777 иг.

Составитель Г. Сорокин ,редактор А. Герден Техред N. Келемеш КорректоР Г азарова

Paias 9849/67 Тираж 751 Подписное

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

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

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