Устройство для моделирования сетей

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИ 4 ЕСНИХРЕСПУБЛИН (19) ( 1)4 СО 5/20 Й ИЗОБ ЕНИ нюк,ания СССР1977,СР1984. 13 ГОСУДАРСТВЕННЫЙ НОМИТЕТ С ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКР К АВТОРСИОМУ СВИДЕТЕЛЬСТВ(71) Институт проблем моделирв энергетике АН УССР(56) Авторское свидетельствоР 717787 , кл. С 06 С 7/122,Авторское свидетельство СУ 1138806, кл, С 06 Р 15/20,(54) (57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕЙ, содержащее модели ветвей, соединенные согласно топологии сети, генератор импульсов, первый многовходозой элемент ИЛИ и блок управления, причемкаждая модель ветви содержит элементы И, триггеры, элемент индикации, Формирователь временного интервала и три элемента ИЛИ, блок управления содержит первый, второй,: третий ичетвертый триггеры, элементы И, элемент НЕ, первый элемент ИЛИ, счетчик импульсов, причем в:каждой модели ветви выход первого элемента И подключен к нулевому входу первого триггера, первые входы первого и второго элементов И являются соответственно первым и вторым входами модели ветви и подключены соответственно к первому и второму выходам блока управления, выход первого элемента ИЛИ блока управления по(ключен к первому зходу первого элемента И . модели ветви, выход второго элемента И блока управления соединен с нулевым входом первого триггера блока управления, нулевой выход которого подключен к первому входу третьего элемента И блока управления, единичный выход первого триггера блока управления соединен с первым входом четвертого элемента И блока управления, выход которого является первым выходом блока управления, единичный выход третьго триггера блока управления соединен с первым входом пятого элемента И блока уп- равления, единичнЫй выход второго триггера подключен к первому входу второго элемента И блока управления выход шестого элемента И блока упра ления соединен с единичным входом второго триггера блока управления, выход первого многовходового элемента ИЛИ подключен к первому входу седьмого элемента И и к входу элементаНЕ блока управления, вход эле- Я мента НЕ является первым входом блока управления, выход генератора импульсов соединен с вторым входой блока управления,.третьим выходом блока управления является выход первого элемента ИЛИ, выход четвертого элемента И блока управления подключен к входу счетчика импульсов, выход которого .соединен с первым входом первого элемента ИЛИ блока управления, второй вход которого подключен к выходу третьего элемента И блока уцравления, выход пятого элемента И блока управления соединен с вторыми входами второго, третьегои четвертого элементов И блока управления, выход второго элемента И блока управления подключен к первому входу шестого элемента И и едининичному входу четвертого триггера бло 79365ка управления, единичный выход которого соединен с вторым входом шестого элемента И блока управления, стретьим входом второго элемента Иблока управления и является четвертымвыходом блока управления, нулевойвыход четвертого триггера блока управления является пятым выходом блокауправления и подключен к третьемувходу четвертого элемента И блокауправления и к второму входу седьмого элемента И блока управления, выход которого соединен с единичным.входом первого триггера блока управления, единичный выход второготриггера является шестым выходомблока управления и соединен с вторымвходом первого элемента И, нулевойвыход второго триггера является седьмым выходом блока управления и подключен к третьему входу третьегоэлемента И блока управления, второйвход пятого элемента И является вторым входом блока управления, выходпервого элемента И блока управленияподключен к нулевому входу третьеготриггера блока управлениявыходвторого элемента И блока управленияявляется восьмым выходом блока управления, в каждой модели ветви выходФормирователя временного интервалаподключен к единичному входу первоготриггера и к нулевым входам третьегои четвертого триггеров модели ветви,нулевой выход третьего, триггерасоединен с первым входом третьегоэлемента И модели ветви, выход которого подключен к первому входу первого элемента ИЛИ модели ветви, выход которого соединен с единичнымвходом четвертого триггера моделиветви, единичный выход которого подключен к первым входам элемента индикации, второго элемента ИЛИ и четвертого элемента И модели ветви, выходчетвертого элемента И и выход пятогоэлемента И через проводное ИЛИ подключены к первым входам шестого,седьмого, восьмого и девятого элементом И модели ветви, выход восьмого элемента И и выход девятогоэлемента И через проводное ИЛИ соединены с вторыми входами третьегон четвертого .элементов И и с первымивходами пятого и десятого элементовИ модели ветви, выход второго элемента И модели ветви подключены к единичному входу второго триггера модели ветви, единичный выход которогсоединен с вторыми входами пятого и восьмого элементов И модели ветви, нулевой выход второго триггера модели ветви подключен к второму входу первого элемента И модели ветви, единичный выход первого триггера модели ветви соединен с вторыми входами второго, седьмого, девятого и десятого элементов И, а также - с третьим входом четвертого элемента И модели ветви, нулевой выход первого триггера подключен к первому входу одиннадцатого элемента И модели ветви, выходы шестого и седьмого элементов И модели ветви соединены соответственно с пеовым и вторым входами третьего элемента ИЛИ модели ветви, выход которого подключен к единичному входу третьео триггера модели ветви, единичный выход которого соединен с вторыми входами элемента индикации и второго элемента ИЛИ модели ветви, а также с третьим входом девятого элемента И моделиветви, нулевой выход четвертоготриггера модели ветви подключен квторому входу шестого элементаИ, третьи входы третьего и шестогоэлементов И модели ветви объединеныи являются третьим входом модели .ветви, второй вход первого элементаИЛИ модели ветви соединен с выходомдесятого элемента И модели ветви,третий вход которого является четвертым входом модели ветви, третий вход седьмого элемента И является пятым входом модели ветви, выход второго элемента ИЛИ модели ветви подключен к второму входу одиннадцатого элемента И, выход которого является первым выходом модели ветви и соединен с соответствующим входом первого многовходового элемента ИЛИ, первый вход первого элемента И модели ветви объединен с входом Формирователя временного интервала, нулевой вход второго триггера является шестым входом модели ветви, выходыпятого и восьмого элементов И модели ветви являются соответственно вторым и третьим выходами модели ветви, третий выход блока управления подключен к второму выходу модели ветви, третий выход которой соединен с восьмым выходом блока управления, четвертый выход которого подключен1179365 к шестому входу модели ветьи, третий вход которой соединен с пятымвыходом блока управления, шестойвыход которого подключен к четвертому входу модели ветви, пятый входкоторой соединен с седьмым выходомблока управления, второй и третийвыходы моделей ветви соответственнообъединены между собой, о т л и ч аю щ е е с я тем, что, с целью расширения функциональных возможностейэа счет определения в неориентированной сети пути с наименьшей пропускнойспособностью, в устройство введен второй многовходовой элемент ИЛИ, в каждую модель ветви введен двенадцатыйэлемент И,в блок управления введенывторой элемент ИЛИ, два триггера идва элемента И, причем в каждой моделиветви выход второго элемента ИЛИсоединен с первым входом двенадцатогоэлемента И, второй вход которогоподключен к выходу формирования вре 1Изобретение относится к цифровым вычислительным машинам для обработки информации специального назначениясс точки зрения конструкции вычислительного устройства, может бытьис пользовано при построении специализированных вычислительных устройств для решения задач на сетях.Цель изобретения - расширение функциональных возможностей эа 10 счет определения в неориентированной сети пути с наименьшей пропускной способностью.На фиг. 1 показана функциональная схема модели ветви устройства; 15 на фиг. 2 - функциональная схема блока управления.Модель 1 ветви (фиг.1) содержит третий, четвертый, первый, второй. триггеры 2- 5, формирователь 6 20 временного интервала, выполненный в виде счетчика импульсов, элемент 7 индикации, пятый, восьмой,. четвертый, девятый, шестой, седьмой, третий, десятый, одиннадцатый, 25 первый, второй и двенадцатый,элеменного интервала, выход двенадцатого элемента И является четвертым выходом модели ветви и соединен с соответствующим входом второго многовходового элемента ИЛИ, в блоке управления нулевой И единичный выходышестого триггера подключены к первымвходам соответственно восьмого и девятого элементов И, выходы которыхсоединены с входами второго элементаИЛИ, выход которого является вторымвыходом блока управления, выход первого элемента ИЛИ блока управленияподключен к единичному входу пятоготриггера блока управления, единичныйвыход которого соединен с вторымвходом девятого элемента И, выход элемента НЕ блока управления подключен квторому входу восьмого элемента Иблока управления, нулевой вход пятого триггера является третьим входомблока управления и соединен с выходомвторого многовходового элемента ИЛИ,2менты И 8 - 19, второй, первый и третий элементы ИЛИ 20 - 22. Блок 23 управления (фиг.2) содержит шестой, третий, первый, второй, четвертый, пятый триггеры 24 - 29, счетчик 30 импульсов, восьмой, девятый, седьмой, пятый, первый, четвертый, шестой, третий, второй, элементы И 31 - 39, второй и первый элементы ИЛИ 40 и 41, элемент НЕ 42. Кроме того, устройство содеркит генератор 43 импульсов, первый и второй многовходовые элементы ИЛИ 44 и 45, второй и третий выходы 46 - 47 модели ветви, третий выход 48 блока 23 управления, восьмой выход 49, второй вход 50, второй выход 51 блока 23 управления, второй вход 52 модели 1 ветви, первый выход 53 модели ветви, входы 541 - 54 элемента ИЛИ 44, первый вход 55 блока 22 управления, первый выход 56 блока 23 управления, первый вход 57 модели 1 ветви, четвертый выход.58 яодели ветви, входы 59 - 59 б элемента ИЛИ 45, третий вход 60блока 23 управления, пятый и, четвертый выходы 61 и 62 блока 23 управления, третий вход 63 модели 1, шестойвход 64 модели 1 ветви, пятый вход65 модели. 1 ветви, седьмой и шестойвыходы 66 и 67 блока 23 управления,четвертый вход 68 модели 1 ветви.При описании работы устройствавходы и выходы блока 23 управленияи модели 1 ветви названы полюсами, 1 ОПеред решением задачи определенияпути с наименьшей пропускной способностью соединяют модели 1 ветвеймежду собой посредством полюсов46 и 47 в соотвествии с конфигурацией моделируемой сети, подключают полюса 48 и 49 блока 23 управления кполюсам 46 или 47 тех моделей ветвей 1, между которыми отыскиваетсяуказанный путь, и заносят (М - Ч," ) Ючисло импульсов в счетчики импульсов6 всех моделей ветвей 1, где И -емкость счетчиков импульсов 6 всехмоделей ветвей 1 и счетчика 30 импульсов блока управления25Суть решения задачи определенияпути с наименьшей пропускной способностью заключается в нахождении(М- х ) разреза и множества разрезев К вюлелеиии ветви разреза 30(х;, х) с ттл С" , в исхлюзеиииветвей, у которых пропускная способность меньше или равна пропускнойспособности выбранной ветви. В дальнейшем полюса 46 и 47 этих моделейветвей 1 закорачиваются между собой,что исключает их из дальнейшего рас-.смотрения. Эти операции повторяютсядо тех пор, пока полюса, между которыми отыскивается путь, не будут 40закорочены (т.е, не совпадут). После этого производится формированиесамого пути и его индикация..Тип решаемой задачи определяетсясостоянием триггера 24 блока 23 управ.5ления, При нулевом состоянии этоготриггера устройство решает задачу определения пути с наибольшей пропускнойспособностью, Работа устройства при решении задачи определения пути с наибольшей пропускной способностью соответствует работе устройства - прототипа, При единичном состоянии триггера 24 решается задача определенияпути с наименьшей пропускной способкостью,Перед началом работы устройстватриггеры 2 - 5 всех моделей ветвей 1 и триггеры 25 - 29 и счетчик 30импульсов блока 23 управления устанавливаются в нулевое состояние. Триггер 24 блока 23 управления устанавливается в единичное состояние, Установочные шины на фиг. 1 и 2 не показаны.Работа устройства начинается сустановки триггера 25 в единичноесостояние. Единичное состояние триггера 25 вьдает разрешение на вход элемента И 34. При этом импульсы генератора 43 импульсов, поступающие наполюс 50 блока 23 управления, проходят через элемент И 34 на входы элементов И 36, 38 и 39. Через элементыИ 36 и 39 импульсы не проходят, таккак они заблокированы нулевыми состояними триггеров 26 и 28, а черезэлемент И 38 импульсы проходят. Далееэти импульсы через элемент ИЛИ 41 поступают на полюс 48 блока 23 управления и одновременно с этим устанавливают триггер 29 в единичное состояние,Единичное состояние триггера 29дает разрешение на вход элементаИ 32, Через элементы И 32 и ИЛИ 40разрешение поступает на полюс 51блока 23 управления и, соотьветственно, на полюса 52 всех моделей ветвей 1,Импульсы с полюса 48 блока 23управления поступают на полюса 46или 47 моделей ветвей 1, которыев результате коммутации этих полюсов между собой образуют вершинусети, из которой отыскивается путьс наименьшей пропускной способностью.В указанных моделях ветвей 1 импульсы с полюса 46 поступают навход элементов И 9, 11-13.Через эле-менты И 9, 11 и 13 импульсы не пройдут, так как на других входах нетразрешения. На всех входах элементаИ 12 разрешение есть, поэтому с выхода этого элемента импульс проходитчерез элемент ИЛИ 22 и устанавливает триггер 2 в единичное состояние.Аналогично, если импульсы поступят на полюс 47 модели 1 ветви онипроходят только через элементы И 14и ИЛИ 21 и устанвливают триггер 3в единичное состояние, Единичное состояние триггеров 2или 3 выдает разрешение на входэлемента И 16 через элемент ИЛИ 20,Это разрешение поступает на полюс53 модели ветви 1, Это возможнопотому, что на другом входе элемен20 После снятия разрешения с полюса51 блока 23 управления и, следова тельно, с полюса 52 модели 1 ветви триггер 4 устанавливается в нулевое состояние очередным импульсом, поступившим на полюс 57тех моделей 1 ветвей, триггер 5 ко торых находится в нулевом состоянии.Конец этого шага работы устройстваопределяется появлением импульсапереполнения счетчика 30 блока 23управления. К этому моменту в счет чиках 6 всех моделей 1 ветвей восстанавливается информация о их пропускной способности, т.е, происходит регенерация. Роль регенерационного счетчика для счетчиков.6 импуль сов всех моделей ветвей 1 выполняетсчетчик 30.импульсов блока 23 управления. Он начинает счет с "0" иемкость его равна М , Счетчики 6 имта И 16 есть разрешение, снимаемоес нулевого выхода триггера 4,С полюса 53 модели 1 ветви разрешение поступает на соответствующий5вход 541 - 54 многовходового элемента ИЛИ 44, Причем на входы 54 -54 многовходового элемента ИЛИ 44поступают разрешения только от техмоделей ветвей 1, триггеры 2 или 3 Окоторых находятся в единичном состоянии. Единичное состояние триггеров2 или 3 свидетельствует о том, чтоданная модель ветви 1 принадлежитразрезу (х, - х) из множества 15разрезов 1 . Это соответствует первому шагу решения задачи,Выбор модели ветви, принадлежащей сформированному разрезу, с наименьшей пропускной способностьюи исключение ее из дальнейшего рассмотрения, так же как и моделейветвей, пропускные способности которых меньше или равны пропускной способности выбранной ветви, происходит по разрешению многовходового элемента ИЛИ 44. Это разрешение поступаетна полюс 55 блока 23 управления, Сполюса 55 через элемент И 33 разрешение поступит на единичный вход ЗОтриггера 26 и установит его в единичное состояние,Единичное состояние триггера 26запрещает прохождение импульсовчерез элемент И 38 и ИЛИ 41 на по 35люс 48 блока управления 23 разрешает прохождение импульсов черезэлемент И 36 на вход счетчика 30импульсов ина полюс 56 блока 23управления. С полюса 56 блока 23управления импульсы поступают наполюс 57 всех моделей 1 ветвей.В моделях 1 ветвей импульсы сполюса 57 поступают на вход счетчика 6 импульсов до его переполнения.Импульс переполнения счетчика 6модели ветви устанавливает триггер4 в единичное состояние, поступаетна нулевые входы триггеров 2 и 3 ичерез элемент И 19 - на полюс 58тех моделей 1 ветвей, которые принадлежат выбранному разрезу.Единичное состояние триггера 4модели 1 ветви через элемент И 18устанавливает в единичное состояниетриггер 5. В этом случае триггер4 остается в единичном состоянии,так как единичное состояние триггера 5 запрещает прохождение очередного импульса с полюса 57 через элемент И 17 на нулевой вход триггера 4Импульс, поступивший на нулевой вход триггера 2 или 3 с выхода счетчика импульсов 6, устанавливает его в нулевое состояние.С полюса 58 модели 1 ветви импульс поступает на полюс 59 и, пройдя многовходовой элемент ИЛИ 45 и полюс 60 блока 23 управления, поступает -на нулевой вход триггера 29. Первый импульс, появившийся на полюсе 58 модели ветви, производит выбор модели ветви, у которой наименьшая пропускная. способность среди всех выделенных ветвей. Это происходит в результате того, что нулевое состояние триггера 29 снимает разрешение через элемент И 32 с полюса 51 блока 23 управления и, соответственно,с полюса 52 всех моделей 1 ветвей.Единичное состояние триггера 5 выдает разрешение на входы элементов И 8 и 9, что исключает модели ветвей из дальнейшего рассмотрения и закорачивает полюса 46 и 47 модели 1 ветви. Таким образом, в моделях 1 ветвей, у которых пропускная способность меньше или равна пропускной способности выбранной моделитриггеры 4 и 5 установлены в единичное состояние и их полюса 46 и 47 .закорочены.пульсов всех моделей ветвей 1 начинают счет с (И - с; ),Импульс переполнения счетчика 30импульсов блока 23 управления поступа 5ет через элемент ИЛИ 41 на полюс 48блока 23 управления 23 и затем -на полюса 46 и 47 моделей 1 ветвейи весь процесс работы повторяется аналогично описанному выше. 10Такие процессы будут повторятьсядо тех пор, пока импульс переполнениясчетчика 30 импульсов блока 23 управления,поступающий на полюс 48, непоявится на полюсе 49. Это происходит потому, что импульс с полюса 48поступает на полюс 46 или 47 моделей1 ветвей и, проходя соответственноэлементы И 8 или 9, появляется наполюсе 47 или, соответственно, 46 20модели 1 ветви,В момент появления импульса наполюсе 49 блока 23 управления всемножество ветвей моделируемой сетибудет разбито на два подмножества. 25Одно подмножетство содержит ветви,пропускная способность о которыхудовлетворяет условию (1),и в соответствующих им моделях 1 ветвейтриггеры 4 и 5 находятся в единичном З 0состоянии, Другое подмножество содержит ветви с пропускными спосдбностями, которые не удовлетворяютусловию (1), и их триггеры 4 и 5остаются в нулевом состоянии Эти 35модели ветвей из дальнейшего рассмотрения исключаются, что обеспечивается отсутствием разрешенийна одном из входов элементов И 13и 15. 40В дальнейшем устройство формирует путь с наименьшей пропускнойспособностью и индицирует его. Дляэтого в блоке 23 управления импульс,поступивший на полюс 49, устанавлива ет триггер 26 в нулевое состояние.а триггер 28 - в единичное.Нулевое состояние триггера 26запрещает прохождение импульсовгенератора 43 импульсов с полюса 56через элемент И 36 и, следовательно,на вход счетчика 30 импульсовПриэтом на полюса 57 всех моделей ветвей импульсы не поступают.Единичное состояние триггера 5528 снимает разрешение с полюса 61блока 23 управления и вьщает сигнална полюс 62, Соответственно с полюса 63 всех моделей ветвей разрешениебудет снято. Сигнал, появившийся наФполюсе 62 блока 23 управления поступает на полюс 64 всех моделей 1ветвей и устанавливает триггер 5в нулевое состояние, чем разрываетзакоротку полюсов 46 и 47Это происходит за счет того, что с входовэлементов И 8 и 9 снимается разрешение. Одновременно с этим импульсыгенератора 43 опять поступают черезполюс 50, элемента И 34, 38 и ИЛИ41 на полюс 48 блока 23 управления,С полюса 48 импульсы поступают наполюса 46 или 47 моделей 1 ветвей,к полюсам которых подключен полюс48 блока 23 управления. В указанныхмоделях 1 ветвей импульсы с полюса46 поступают на вход элемента И 13тех моделей, триггер 4 которых нахо-,дится в единичном состоянии, и проходят через него. При этом на другом входе элемента И 13 есть разрешение, поступающее с полюса 65 моделиветви через полюс 66 блока 23 управления, которое снимается с нулевоговыхода триггера 27 блока 23 управле"ния,В модели 1 ветви импульсы поступают через элемент ИЛИ 22 на единичныйвход триггера 2. По первому импульсуиз всей серии импульсов, поступившихв модель 1 ветви на полюс 46, триггер2 устанавливается в единичное состояние, Единичное состояние триггера 2выдает разрешение на элемент И 11.Поэтому остальные импульсы из всейсерии с полюса 46 через элемент И 11поступают на полюс 47 модели 1 ветви,Таким образом, импульсы распространяются по сети до тех пор, пока онине появятся на полюсе 49 блока 23управления,Поступивший на полюс 49 блока 23управления импульс проходит черезэлемент И 37, так как триггер 28 на- .ходится в единичном состоянии, иустанавливает триггер 27 в единичноесостояние. Единичное состояние триггера 27 выдает разрешение на полюс67 и снимает разрешение с полюса 66,выдает разрешение на элементы И 35и 39 и снимает разрешение с элемента И 38. При этом с полюсов 65 моделей 1 ветвей снимается разрешение,что заблокирует их элементы И 13, наполюсах 68 появляется разрешениена прохождение сигналов через элемент И 16. Одновременно импульсы генератора 43 импульсов через элементы И 34 и 39 поступают на полюс 49 и далее на полюса 47 моделей ветвей 1, к которым подключен полюсом 47 блок 23 управления.С полюса 47 в модели 1 ветви импуль. сы через элемент И 15 и ИЛИ 21 посту пают на единичный вход триггера 3. По первому импульсу из серии импульсов, поступивших на полюс 47, триггер 3 устанавливается в единичное состояние, которое выдает разрешение на элемент 15 И 10. Поэтому остальные импульсы проходят через элемент И 10 и поступают на полюс 46. Это происходит только в тех моделях ветвей 1, триггер 4 которых находится в единичном состоянии. Таким образом, импульсы распространяются по сети через модели 1 ветвей с полюса 47 на полюс 46 до техпор, пока не появятся на полюсе 48блока 23 управления,С полюса 48 блока 23 управления через элемент И 35 импульс поступает на нулевой вход триггера 25 и устанавливает его в нулевое состояние, Нулевое состояние триггера 25 сигнализирует о конце решения задачи,При этом модели 1 ветвей, у которых триггеры 2 и 3 находятся одновременно в единичном состоянии, принадлежат искомому пути. Эти модели индицируются элементом 7 индикации.1179365 Составитель И.Дубининар В.Ковальчук Техред З.Палий Корректор С,Черни е Патент", г. Ужгород, ул. Проектная,л каэ 568/52ВНИИПИ Государпо делам изо113035, Иосква, Ж Тираж 71 О Подписное твенного комитета СССР ретений и открытий 35,. Раушская наб, д, 4/5