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

ОПИСАНИЕ ИЗОБРЕТЕНИЯ Союз Советскиа Социалистических ваеспублик(5 с присоединением заявки РЙ(45) Дата опубликования описания 050578 Гащврвтввааий аваатвт6 ввата Мааавтров 666 Раа ававв авобрвтваааа втарытаа 53) У 1.33 88,8(72) Авторы изобретения А.Г.Додонов, В.В,Хаджинов и И.В.Федо Заявитель Институт электродинамики АН УССР(5 СТРОИСТВО ДЛЯ МОДЕ 5 Изобретение относится к электронному моделированию и может быть использовано при построении специализированных вычислительных устройств,Известно устройство для моделирования экстремальных путей на графе,содержащее соединенные в соответствиис топологией граФика модели ветвей насчетчиках, триггерах.и логических схемах И, ИЛИ и НЕ 1.10Недостатком известного устройстваявляется невозможность определенияконфигурации длиннейшего пути.Наиболее близким по техническойсущности к рассматриваемому является 18устройство для моделирования сетевогографика, содержащее блок управления,генератор импульсов, блок формированиятопологии и блок моделей ветвей почислу работ, каждая иэ которых состоит 20из задатчиков адресов, выходы которыхподключены соответственно к первымвходам первого и второго элементов И;второй вход первого элемента И соединен с одним выходом первого триггера, Фдругой выход которого подключен к второму входу втОрого элемента И, третийвход которого соединен с выходом первого элемента ИЛИ блока формированиятопологии, выход второго элемента И ОВАНИЯ СЕТЕВОГО ГРАФИКА подключен к .Одному входу формирователя временных интервалов, другой входкоторого соединен с выходом первогоэлемента И блока формирования топологии, выход формирователя временных интервалов подключен к первым входамтриггеров., второй вход второго триггера соединен с выходом соответствующего задатчика адресов, выход второготриггера подключен к входу второгоэлемента ИЛИ блока формирования топологии, первый вход элемента ИЛИ блокамоделей ветвей соединен с выходомпервого элемента И второй вход элемента ИЛИ через элемент яЕ подключенк выходу соответствующего эадатчикаадресов, а выход элемента ИЛИ соединен с входом второго элемента ИЛИ блока Формирования топологии, которыйсостоит иэ элементов И и элементовИЛИ, причем выход второго элементаИЛИ непосредственно и через, элементНЕ подключен к одним входам элементовИ, другие входы которых соединены .свыходами генератора импульсов, выходтретьего элемента И подключен к первому входу третьего элемента ИЛИ, второй вход которого соединен с первымвыходом блока управления, второй выходкоторого подключен к первом входу перного элемента ИЛИ блока формирования топологии, второй вход которого соединен с выходом второго элемента ИЛИ, выходы первого и третьего элементов ИЛИ подключены соответственно к входам задатчиков адресой и второго элемента И блока моделей ветвей Г 21Недостатком известного устройства также является невозможность определения конфигурации длиннейшего пути, 10 т.е. совокупности ветвей, принадлежащих максимальному среди возможных путей между узлами сетевого графика. Кроме того, здесь отсутствует возмож" ность определения дерева максимальных путей - совокупности ветвей, принадлежащих длиннейшим путям к каждой из вершин сетевого графика.Цель изобретения - расширение клас-,са решаемых задач устройства путем 20 обеспечения возможности определения конфигурации длиннейшего пути и максимальных путей сетевого графика.Это дос нгается тем, что в устройстве для моделировани- сетевого гра"фика в блок формирования топологии ив блок модеЛей ветвей введены допол"нительно триггеры, элемент НЕ и эле.менты И и ИЛИ, причем в блоке формиро-,вания ветвей первый вход первого дополнительного элемента И подключен квыходу соответствующего эадатчика адресов, а второй вход через дополнительный элемент НЕ "оединен с выходомпервого элемента ИЛИ блока формирова"ния топологии, выход первого дополнительного элемента И подключен к пер,ому входу первого дополнительного триггера, второй вход которого соединенс выходом формирователя временных интервалов, а выход - с одним входомвторого дополнительного элемента И,другие входы которого подключены соответственно к выходам одного задатчикаадресов и первого дополнительного элемента ИЛИ блока формирования тополо. гии, выход второго дополнительного элемента И блошка моделей ветвей через второй дополнительный триггер соединенс одним входом третьего дополнительного элемента И, другой вход которогосоединен с выходом.другого задатчикаадресов, а выход - через второй допол"нительный элемент ИЛИ блока формирования топологии подключен к од .о:увходу дополнительного элемента И бло"ка формироэания топологии, а другойвход которого соединен с третьим вы. ходом блока управления, четвертый выход которого и выход дополнительногоэлемента И подключен к входам первого дэполнительного элемента ИЛИ блокаформирования топологии, выход которого соединен с вторым входом блокауправления, третий вход которого подключен к выхсду генератора импульсов, 65 На чсртеже приведена функциональная схема устройства.Оно состоит из блока 1 моделей ветвей, блока 2 формирования топологии, блока 3 управления и генератора 4 импульсов.Каждая модель ветви 1 содержит элементы задатчики адресов 5, 6, формирователь 7 временных интервалов, триггеры 8-11 р элементы И 12-16 у элементы НЕ 17, 18; элемент ИЛИ 19.В качестве задатчиков адресов 5 и 6 используются счетчики импульсовБлок 2 формирования топологии содержит элементы И 20-231 элементы ИЛИ 24-28; элемент НЕ 29.Устройство работает следующим образом.Предварительно в задатчики адре"ов 5 6 заносятся соответственно адреса начального и конечного узлов ветвей сетевого графика.В формирователь 7 временных интервалов заносится длительность ветви, а триггеры 8, 9, 10 и 11 устанавливаются в нулевое состояние.Для запуска всех моделей ветвей 1, исходящих из начального. узла сетевого графика, блок 3 управления разрешает прохождение импульсов генератора 4 импульсов через элемент ИЛИ 25 блока 2 формирования топологии на входы задатчиков адресов 5 и 6 всех моделей ветви 1. Импул. сы будут поступать до тех пор, пока на выходах задатчика 5 адресов, Р которых записан адрес начального узла сетевого графика, не появится сигнал. В этот момент времени блок управления прекращает подачу импульсов на входы задатчиков адресов и подает пусковой сигнал. Во всех моделях ветвей, исходящих из начального узла графика, на входах элементов И 12 будут разрешающие сигналы с выхода задатчика 5 адресов и нулевого выхода триггера 9. В результате формирователи 7 временных интервалов этих моделей будут подготовлены сигналами с выходов элементов И 12 к отсчету импульсов, поступающих из блока 2 фор-. мирования топологии. Отсчитав число. импульсов, пропорциональное длительности данной ветви, формирователь 7 временных интервалов выдаст сигнал, который установит в единичное состояние триггеры 8, 9 и 10. С единичного выхода триггера 8 сигнал поступает.в блок 2 формирования топологии на один из входов элемента ИЛИ 24, к остальным входам которого подключены одноименные входы остальных моделей вет" вей 1, Пройдя через элемент ИЛИ 24, сигнал поступает на вход элемента НЕ 29, к,вторый вырабатывает запрет на одном из входов элемента И 22, в результате чего прекращается поступление импульсов на входы всех моделейветвей 1. Одновременно сигнал с выхода элемента ИЛИ 24, поступая на входэлемента И 20, разрешает прохождениеимпульсов со второго входа этого элемента через. элемент ИЛИ 25 на входымоделей ветвей 1,Серию импульсов с генератора 4 импульсов начинают считать одновременно .задатчики адресов 5 и б. Сигналс выхода задатчика адресов б, в котором записан адрес конечного узла ветви, устайавливает в нулевое состояниетриггер 8, поступает на первые входыэлементов И 13, 14 и 15 и на входэлемента НЕ 18.Если ветвь, в которой появится импульс на выходе задатчика адресов б,закончила формирование временного интервала, то сигнал с выхода триггера9 пройдет через элемент И 13 и далеечерез элемент ИЛИ 19 к одному из входов элемента И 21. Остальные входыэтого элемента подключены к аналогичным выходам других моделей ветвей,Если временной. интервал в даннойветви еще не сформирован, то триггер 259 находится в нулевом состоянии, ина входе элемента И 13 присутствуетзапрет с его единичного выхода. Выходной сигнал задатчика адресов б в этомслучае не пройдет через этот элемент, 30и на выходе элемента ИЛИ 19 в этотмомент появится запрещающий сигнал,который и поступит на соответствующийвход блока 3 формирования топологии.В тех случаях, когда импульсы навыходе эадатчика адресов б отсутствуют, на этом входе присутствует разрешающий сигнаЛ с выхода элемента НЕ18. Таким образом, запрет на этом входе будет только в тех моделях ветвей, 40которые входят в рассматриваемый узел,но не сформировали свою длительность.В этом случае запрещающий сигнал пройдет на выход элемента И 21 и черезэлемент ИЛИ 26 на полюсы всех моделейветвей 1. Этот сигнал запретит подго 45товку соответствующих формирователей7 временных интервалов к отсчету импульсов с генератора импульсов. Навыходе элемента .НЕ 17 возникает приэтом разрешающий сигнал, который поступает на второй вход элемента И 14,и так как на первом его входе присутствует выходной сигнал задатчика адресов б, триггер 10 устанавливаетсяв нулевое состояние, 55Если все ветви, входящие в рассмат"риваемый узел, сформировали временнойинтервал, то на входах элемента И 21блока 2 формирования топологии будут60отсутствовать запрещающие сигналы, ииа выходе этой схемы появится сигнал,который поступит через элемент ИЛИ26 на полюсы моделей ветвей. Этот сигнал пройдет на выход элемента И 12тех моделей ветвей, которые выходят65 иэ рассматриваемого узла, т.е, в техветвях, где в данный момент времениесть сигнал на выходе задатчика адресов 5. Кроме того, этот сигнал запретит с помощью элемента НЕ 17 установку в нулевое состояние триггера 10 вмоделях ветвей, последними сформировавших временной интервал в этом узле.Импульсы с генератора 4 импульсовпоступают на входы эадатчиков адресов5 и б до тех пор, пока хотя бы на одном из входов блока 2 формированиятопологии присутствует сигнал с выхода триггера 8 какой-либо модели ветви 1. После того, как все триггеры 8установлены в нулевое состояние выходными сигналами соответствующих задатчиков адресов, блок Формирования 2топологии запрещает прохождение импульсов этой серии на входы задатчиков адресов и разрешает. поступлениеимпульсов первой серии на входы формирователей временных интервалов.Суммарное количество импульсов, поступившее на входы блока формирования топологии с начала счета, равно величине длиннейшего пути, а единичныесостояния триггера 10 укажут, какиеветви принадлежат дереву максимальныхпутей.Для определения конФигурации длиннейшего пути между начальным и конечным узлами сетевого графика блок 3 управления выдает разрешение на первый вход элемента И 23, а также разрешает прохождение импульсов череЗ элемент ИЛИ 25 на входы задатчиков адресов 5 и 6 всех моделей ветвей 1, В момент переполнения задатчиков адресов 6, в которых записан конечный узел сетевого графика, блок 3 управления выдает импульс на вход элемента ИЛИ 27, выходной сигнал с которого поступит на первый вход элемента И 1.51 На второй ьходе в этот момент времени будет присутствовать сигнал с выхода задатчика адресов конечного узла б Если на третьем входе этого элемента будет разрешение с выхода триггера 10, т.е. если ветвь сформировала свою длительность последней в конечном узле сетевого графика, то выходной сигнал элемента И 15 установит в единичное состояние триггер 11, Единичный выход триггера 11 разрешит прохождение импульсов с выхода задатчика адресов начального узла 5 через элемент И 16 на вход элемента ИЛИ 28 блока 2 формирования топологии. Остальные входы этого элемента разделения подключены к аналогичным входам остальных моделей ветвей. Сигнал с выхода элемента ИЛИ 28 поступит на второй вход элемента И 23 и через элемент ИЛИ 27 на входы элемента И 15. При этом устанавливаются в единичные состояния триггеры 11 тех моделей ветвей, которые последними сформировали длительность в начальном узле рассмотренной ветви.Подобный процесс продолжается до тех пор, пока на входах блока формирования топологии не появится сигнал с выхода задатчиков адресов 5; соответствующий начальному узлу сетевого графика. Это говорит об окончании процесса выделения длиннейшего пути.Блок управления при этом прекращает подачу импульсов на элемент ИЛИ 25 и подает запрет на элемент И 23.Единичные состояния триггеров 11 укажут на принадлежность ветвей длиннейшему пути сетевого графика, 15Использование изобретения позволяет расширить класс решаемых устройством задач, так как оказывается возможным определять конфигурацию длиннейшего пути между узлами сетевого гра фика и дерево максимальных путей. Формула изобретения25Устройство для моделирования сетевого графика, содержащее блок управления, генератор импульсов, блок формирования топологии и блок моделей ветвей по числу работ, каждая из которых состоит из задатчиков. адресов, выходы которых подключены соответственно к первым входам первого и второго элементов И, второй вход первого элемента И соединен с,одним Выходом пер 15 ваго триггера, другой выход которого подключен к второму входу второго элемента И, третий вход которого соединен с выходом первого элемента ИЛИ блока формирования топологии, выход второго элемента И подключен к одному входу формирователя временных интервалов, другой Вход которого соединен с выходом первого элемента И блока формирования топологии, выход формирователя временных интервалов подключен к первым входам триггеров, второй вход второго триггера соединен с выходом соответствующего задатчика адресов, выход второго триггера подключен к входу второго элемента ИЛИ блока форми рования топологии, первый вход элемента ИЛИ блока моделей ветвей соединен с выходом первого элемента И, второй вход элемента ИЛИ через элемент НЕ подключен к выходу соответствующего 5 задатчика адресов, а выход элемента ИЛИ соединен с входом второго элемента ИЛИ блока формирования топологии, который состоит из элементов И и элементов ИЛИ, причем выход второго элемента ИЛИ непосредственно и через элемент НЕ подключен к одним входам элементов И, другие входы которых соедниены с выходами генератора импульсов, выход третьего элемента .И подключен к первому входу третьего элемента ИЛИ, второй вход которого соединен с первым выходом блока управления, второй выход которого подключен к первому входу первого элемента ИЛИ блока формирования топологии, второй вход которого соединен с выходом второго элемента ИЛИ, выходы первого и третьего элементов ИЛИ подключены соответственно к входам задатчиков адресов и второго элемента И блока моделей ветвей, о т л и ч а ю щ е е с я тем, что, с целью расширения класса решаемых задач путем обеспечения возможности определения максимальных путей, в него,в блок формирования топологии и в блок моделей ветвей введены дополнительно триггеры, элемент НЕ и элементы И н ИЛИ, причем в блоке формирования ветвей первый вход первого дополнительного элемента И подключен к выходу соответствующего задатчика адресов, а второй вход через дополнительный элемент НЕ соеДинен с выходом первого элемента ИЛИ блока формирования топологии, выход первого дополнительного элемента И подключен к первому входу первого дополнительного триггера, второй вход которого соединен с выходом формирователя временных интервалов, а выхОД - с одним входом второго дополнительного элемента И, другие входы которого подключены соответственно к выходам одного задатчика адресов и первого дополнительного элемента ИЛИ блока формирования топологии, выход второго дополнительного элемента И блока моделей ветвей через второй дополнительный триггер соединен с одним входом третьегодополнительного элемента И, другой вход которого соединен с выходом другого задатчика адресов, а выход - через второй дополнительный элемент ИлИ блока формирования топологии подключен к одному. входу дополнительного элемента И блока формирования топологии, а другой вход которого соединен с третьим выходом блока управления, четвертый выход которого и выход дополнительного элемента И подключены к входам первого дополнительного элемента ИЛИ блока формирования топологии, выход которого соединен с вторым входом блока управления, третий вход которого подключен к выходу генератора импульсов.Источники информации, принятые во внимание при экспертизе:1, Авторское свидетельство СССР Р 305484, кл. 6 06 6 7/34, 1969.2. Авторское свидетельство СССР Р 422002, кл, 6 06 0 7/48, 1972.6081 б 9 Составитель,И; ЗагорбинйнаРедактор Н.Раэумова ТехредЕ. Давидович КорректорН.Ковалев 804/34ЦИНИПИ Госуда Ва 1130 тентф, г. Ужгород, ул ектнан, 4 ж 926 ета Со ений и Раушск Тирвенного комиделам изобросква, ЖПодписноета Иинистров СССРткрытийнаб., д. 4/5