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

Оп ИСАНИЕ ИЗОБРЕТЕНИЯ Союз Советских Социапистическик Республик(6 ) Дополнительное к авт. свид-ву 9 608169 (22) Заявлено 110180 (21) 2872430/18-24 с присоединением заявки Нов(23) ПриоритетОпубликовано 230781,Бюллетень М 27 Р 1)М, Х,з С 06 6 7/122 Государствеиный комитет СССР по делам изобретений и открытийДата опубликования описания 2307,81.Г.Додоно 1) Заявитель нститут электродинамики АН нско 54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВОГО ГРАФИКАмента И, второй вход элемента ИЛИчерез элемент НЕ подключен к выходусоответствующего задатчика адресов,а выход элемента ИЛИ блока Формирования топологии, который состоит изэлементов И и элементов ИЛИ,причемвыход второго элемента ИЛИ непосредственно и через элемент НЕ подключенк одним входам элементов И, другиевходы которых соединены с выходамигенератора импульсов, выход третьегоэлемента И подключен к первомувходу третьего элемента ИЛИ, второйвход которого соединен с первым выходом блока управления, второй выходкоторого подключен к первому входупервого элемента ИЛИ блока формирования топологии, второй вход которогосоединен с выходом второго элементаИЛИ, выходы первого и третьего эле"ментов ИЛИ подключены соответственнок входам задатчиков адресов и второго элемента И блока моделей ветвей,кроме того, в блок Формирования топологии и блок моделей ветвей введеныдополнительно триггеры, элемент НЕи элементы И и ИЛИ, причем в блокеформирования ветвей первый вход первого дополнительного элемента И подключен к выходу соответствующего Изобретение относится к вычислительной технике, а именно к устройствам для моделирования сетевого графика.5По основному .авт.св. 9 608169 известно устройство для моделирования .сетевого графика, содержащее блок управления, генератор импульсов, блок формирования топологии и блок моделей 10 ветвей по числу работ, каждая из которых состоит из задатчиков адресов, выходы которых подключены соответственно к первым входам первого и второго элементов И, второй вход первого эдемента ИЛИ блока формиро вания топологии, выход второго элемента И подключен к одному входу формирователя временных интервалов, другой вход которого соединен с выходом первого элемента И блока форми .рования топологиивыход формирователя временных интервалов подключен к первым входам триггеров, второй вход второго триггера соединен с выходом соответствующего задатчика ад 25 ресов, выход второго триггера подключен к входу второго элемента ИЛИблока формирования топологии, первый вход элемента ИЛИ блока моделей ветвей соединен с выходом первого элеСРг10 20 25 30 40 45 50 55 60 65 задатчика адресов, а второй вход через дополнительный элемент НЕ соединен с выходом первого элемента ИЛИблока формирования топологии, выходпервого дополнительного элемента Иподключен.к первому входу первого до.полнительного триггера, второй входкоторого соединен с выходом формирователя временных интервалов, а выход - с одним входом второго дополни. тельного элемента И, другие входыкоторого подключены соответственнок выходам одного задатчика адресови первого дополнительного элементаИЛИ блока формирования топологии,выход второго дополнительного элемента И блока моделей ветвей черезвторой дополнительный триггер соединен с одним входом третьего дополнительного элемента И, другой входкоторого соединен с выходом другогозадатчика адресов, а выход - черезвторой дополнительный элемент ИЛИблока формирования топологии подключен к одному входу дополнительногоэлемента И блока формирования топологии, а другой вход которого соединен с третьим выходом блока управления, четвертый выход которого ивыход дополнительного. элемента ИЛИподключены к входам первого дополнительного элемента ИЛИ блока Формирования топологии, выход которого соединен с вторым входом блока управления, третий вход которого подключен к выходу генератора импульсов.Известное устройство, позволяет определить величину и конфигурацию длиннейшего пути и максимальные пути сетевого графика 1.Однако устройство не позволяет решать задачу определения одного пути из множествадлиннейших:путей сетевого графика, котораявозникает при оптимальном целочисленном распределении ограниченных ресурсов на сетевых графиках.Цель изобретения - расширение класса решаемых задач устройства путем обеспечения возможности определения одного критического пути из множества длиннейших путей сетевого графикаУкаэанная цель достигается тем, что в каждый блок моделирования ветвей дополнительно введены шестой седьмой, восьмой, девятый и десятый элементы И, пятый, шестой и седьмой триггеры, третий элемент НЕ и блок индикации, в каждый. блок формирования топологии дополнительно введены пятый элемент И, шестой и седьмой элементы ИЛИ, причем в блоке формирования топологии выход пятого элемента И подключен к первому входу шестого элемента ИЛИ, второй вход которого соединен с четвертым выходом блока управления, четвертый вход которого подключен к выходу шестого элемента ИЛИ, выход седьмого элемента ИЛИ соединен с первым входомпятого элемента И, второй вход которого подключен к пятому выходублока управления, в блоке моделирования ветвей выход третьего элементаНЕ подключен к первому входу седьмого элемента И, выход которого соединен с первым входом пятого триггера, первый выход которого подключенк первому входу девятого элемента И,выход которого соединен с первым. входом шестого триггера, выход которого подключен к первому входу десятого элемента И, выход которогосоединен с входом седьмого триггера,выход которого подключен к входублока индикации, выход одного задатчика адресов соединен с входом третьего элемента. НЕ блока моделированияветвей и первым входом шестого элемента И блока моделирования ветвей,выход которого подключен к второмувходу пятого триггера, второй выходкоторого соединен с первым входомвосьмого элемента И блока моделирования ветвей, выход которого подключенк второму входу пятого триггера,второй выход которого соединен спервым входом восьмого элемента Иблока моделирования ветвей, выходкоторого подключен к второму входушестого триггера, выход второгодополнительного триггера соединен свторым входом шестого элемента И,выход другого задатчика адресовподключен к второму входу десятогоэлемента И, выход которого подключенк входу седьмого элемента ИЛИ блокаформирования топологии, выход шестого элемента ИЛИ блока формированиятопологии соединен с вторым входомседьмого и третьим входом шестогоэлементов И блока моделирования ветвей, шестой выход блока управленияподключен к вторым входам восьмого идевятого элементов И блока моделирования ветвей,На фиг.1 приведена функциональнаясхема устройства; на фиг.2 - блокуправления.Устройство состоит из блока моделей 1 ветвей, блока 2 формированиятопологии, блока 3 управления и генератора 4 импульсов,В каждую, модель 1 ветви, содержащую задатчики 5 и б адресов, формирователь 7 временных интервалов,триггеры 8-11, элементы 12-16 И,элементы 17 и 18 НЕ и элемент 19 ИЛИ,дополнительно введены триггеры 2022, элементы 23-27 И, элемент 28 НЕи блок 29 индикации.В качестве задатчиков 5 и б адресов используются счетчики импульсов. Формирователь 7 временных интервалов выполняется на основе счетчико-регистровых структур, Каждаямодель ветви предназначена для моделирования одной работы исследуемогосетевого графика.В блок 2 формирования топологии,содержащий элементы 30-33 И, элементы 34-38 ИЛИ, элемент 39 НЕ, дополнительно введены элемент 40 И и элементы 41-42 ИЛИ. Блок 2, соединенный5с блоком моделей 1 ветвей, обеспечивает взаимодействие моделей 1 ветвейсетевого графика по временному принципу на основании адресов начальногои конечного событий, занесенных в задатчики 5 и б,Блок 3 управления может быть выполнен различным образом и один изего вариантов изображен на фиг.2.Он состоит из задатчиков 43 и 44 начального и конечного узлов сетевогографика, соответственно, выполненныханалогично задатчика 5 и б; триггеров 45-48, элементов 49-60 И; элементов 61-63 ИЛИ и элемента 64 задержки. Блок 3 предназначен для осуществления первоначального запускавсего устройства и организации взаимосвязанной работы блоков устройства25Устройство работает следующимобразом.Предварительно в задатчики 5 и бзаносятся соответственно адреса начального и конечного узлов ветвейсетевого графика. В формирователь 7заносится длительность ветви, атриггеры 8-11 и 20-22 устанавливаются в нулевые состояния.В блоке 3 управления предварительно в задатчики 43 и 44 заносятся35соответственно адреса начального иконечного узлов сетевого графика,триггеры 45-48 устанавливаются в нулевые состояния. Для запуска всехмоделей 1 ветвей на полюс .65 блока 403 подается разрешающий сигнал. Сигнал Пуск, поступающий на полюсбб блока 3, проходит через элемент59 И и устанавливает триггеры 45 и47 в единичные состояния, Последнее 45состояние триггера 45 выдает разрешение через элемент 61 ИЛИ на входэлемента 50 И, импульсы с выходагенератора 4 проходят на выход блока 3 (полюс 78) и через элемент 50И на входы задатчиков 43 и 44.Кроме того, импульсы с выходаэлемента 50 И проходят через элемент51 И, на втором входе которого присутствует разрешение с выхода триггера 47, далее через элемент 62 ИЛИна выход блока 3 (полюс 67), гдепоступают на вход элемента 35 ИЛИблока 2 формирования топологии.Импульсы с выхода элемента 35 ИЛИпоступают на входы задатчиков 5 и б бОдо тех пор, пока на выходах графика не появляется сигнал переполнения. В этот же момент времени на выходе задатчика 43 начального узласетевого графика в блоке 3 появляет ся сигнал переполнения, который проходит через элемент 53 И, так какна втором входе элемента присутствует разрешение с выхода триггера 45,на выход блока управления (полюс 68)и далее поступает на вход элемента36 ИЛИ блока 2,Кроме того, сигнал переполненияс выхода задатчика 43 поступает навход триггера 47 и устанавливает егов нулевое состояние. В результатепрекращается подача импульсов навход элемента 35 ИЛИ блока 2, Сигнал с выхода элемента 36 ИЛИ поступает на вход элемента 12 И моделей1 и на вход блока 3 (полюс 73). Разрешающий сигнал появляется на выходах тех элементов 12 И, на остальныхвходах которых присутствует разрешение с нулевого выхода триггера 9и задатчика 5. В результате, формирователи 7 этих моделей подготовленысигналами с выходом элементов 12 И котсчету импульсов, поступающих изблока 2, Отсчитав число импульсов,пропорциональное длительности даннойветви, формирователь 7 выдает сигнал, который устанавливает в единичное состояние триггеры 8-10. Сигналс единичного выхода триггер 8 поступает на вход элемента 34 ИЛИ и черезэлемент 39 НЕ запрещает прохождениеимпульсов через элемент 32 И, а также разрешает прохождение импульсовчерез элементы 30 И и 35 ИЛИ на входы моделей 1.Серию импульсов с генератора 4 начинают считать одновременно задатчики 5 и б. Сигнал с выхода задатчика б, в котором записан адрес конечного узла ветви, устанавливаетв нулевое состояние триггер 8 и поступает на входы элементов 13-15 Ии 18 НЕ.Если ветвь, в которой появляетсяимпульс на выходе задатчика 6, закончила формирование временного интервала, сигнал с выхода триггера9 проходит через элементы 13 И и19 ИЛИ к одному,из входов элемента31 И.В тех случаях, когда импульсына выходе задатчика адресов б отсутствуют, на вход элемента 31 И разрешающий сигнал поступает с выходаэлемента 18 НЕ. Таким образом, запрет на входах 31 И только в техмоделях ветвей, которые входят врассматриваемый узел, но не сформиРовали свою длительность. В этомслучае запрещающий сигнал проходитна выход элемента 31 И и через элемент 36 ИЛИ на полюсы всех моделей1. Этот сигнал запрещает подготовкусоответствующих формирователей 7 котсчету импульсов с генератора 4.На выходе элемента 17 НЕ возникаетпри этом разрешающий сигнал, который поступает на второй вход элемента 14 И и, так как на первомего входе присутствует выходнойсигнал задатчика 6, триггер 10 устанавливается в нулевое состояние.Если все ветви, входящие в рассматриваемый узел, формировали временной интервал, на выходе элемента31 И блока 2 появляется разрешающийсигнал, который поступаетчерез элемент 36 ИЛИ на полюсы моделей ветвейРазрешающий сигнал запрещаетчерез элемент 17 НЕ установку триггера 10 в нулевое состояние и такжепроходит на выход элемента 12 И техмоделей, которые выходят из рассматриваемого узла, т.е. тех ветвей,где в данный момент времени естьсигнал на выходе задатчька 5.Импульсы с генератора 4 поступают на входы задатчиков 5 и 6 дотех пор, пока хотя бы на одном извходов блока 2 присутствует сигнал 2с выхода триггера 8 какой-либо модели 1. После того, как все триггеры 8 установлены в нулевое состояние выходными сигналами соответствующих задатчиков адресов, блок 2запрещает прохождение импульсов этойсерии на входы задатчиков адресови разрешает поступление импульсовпервой серии на входы Формирователей вРеменных интеРвалов. Когда сфоР- Змирован конечный узел сетевого графика, все триггеры 8 моделей 1 устанавливаются в нулевые состояния.После этого сигнал с выхода элемента 36ИЛИ блока 2 поступает в блок 3 навход элемента 55 ИЛИ итак как сфор.мирован конечный узел сетевого граФика, импульс переполнения с выходазадатчика 44 проходит через элемент55 И и устанавливает триггер 45в нулевое состояние.Суммарное количество импульсов,поступившие на входы блока формирования топологии с начала счета, равновеличине длиннейшего пути, а единичные состояния триггера 10 указывают, какие ветви принадлежат деревумаксимальных путей.Для определения конфигурации длиннейших путей между начальным и конечным узлами сетевого графика в блоке 3 предварительно в задатчики 43 и43 заносятся соответственно адресаначального и конечного узлов сетевогографика, триггеры 45-48 устанавливаются в нулевые состояния и на полюс69 подается разрешающий сигнал,Сигнал Пускф, поступающий наполюс 66 блока 3, проходит через элемент 49 И и устанавливает триггер 46в единичное состояние. Последнеесостояние триггера 46 выдает разрешение на выход (полюс 70) блока 3,соединенного с входом элемента 33 И,а также сигнал с выхода триггера 46проходит через элемент 61 ИЛИ и разрешает прохождение импульсов с выХо да генератора 4 через элемент 50 И на входы задатчиков 43 и 44. Кроме того, импульсы с выхода элемента 50 И проходят через элемент 52 И, на втором входе которого присутствует разрешение через элемент 63 ИЛИ с выхода триггера 46, далее через элемент 62 ИЛИ на выход блока 3 (полюс 67), где поступают на вход элемента 35 ИЛИ. Импульсы с выхода элемента 35 ИЛИ поступают на входы задатчиков 5 и 6 до тех пор, пока на выходах задатчиков 6, в которых записан ацрес конечного узла сетевого графика, не появляется сигнал переполнения. В этот же момент времени на выходе задатчика 44 появляется сигнал переполнения, который проходит через элемент 56 И, так как на втором входе элемента присутствует разрешение с выхода элемента 63 ИЛИ, на вход блока управления (полюс 71) и далее поступает на вход элемента 37 ИЛИ блока 2. Сигнал с выхода элемента 37 ИЛИ поступает на первый вход элемента 15 И.На втором входе в этот момент времени присутствует сигнал с выхода задатчика 6. Если на третьем входе этого элемента есть разрешение с выхода триггера 10, т.е. если ветвь сформировала свою длительность последней в конечном узле сетевого графика, выходной сигнал элемента 15 И устанавливает в единичное состояние триггер 11. Единичный выход триггера 11 разрешает прохождение импульсов с выхода задатчика 5 через элемент 16 И на вход элемента 38 ИЛИ блока 2, Остальные входы этого элемента разделения подключены к аналогичным выходам остальных моделей ветвей. Сигнал с выхода элемента 38 И поступает на второй вход элемента 33 И и через элемент 37 ИЛИ на входы элементов 15 И, При этом устанавливаются в единичное состояние триггеры 11 тех моделей ветвей, которые последними формируют длительность в начальном узле рассмотренной ветви. Подобный процесс продолжается до тех пор, пока на входах блока формирования топологии не появляется сигнал с выхода задатчиков 5, соответствующих начальному узлу сетевого графика. Это говорит об окончании процесса выделения длиннейшого пути.При этом выработанный сигнал с выхода элемента 37 ИЛИ поступает в блок 3 (полюс 72) на вход элемента 54 И и,так как сформирован начальный узел сетевого графика, он проходит через элемент 54 И и устанавливает триггер 46 в нулевое состояние.Блок управления при этом прекращает подачу импульсов на элемент 35ИЛИ и подает запрет на элемент 33 И.849232 10 25 ЗО 3540 45 Затем вновь происходит установка триггера 21 в состояние, поДобное положению триггера 20, и определяется начальный узел хотя бы одной ветви, у которой на единичном выходе триггера 21 присутствует разрешение.Подобный процесс продолжается до тех пор, пока на входах блока не появляется сигнал с выхода задатчиков 5, соответствующих начальному узлу сетевого графика. Это говорит об окончании процесса выделении одного критического пути из множества длиннейших путей сетевого графика.При этом выработанный сигнал с выхода элемента 42 ИЛИ поступает в блок 3 (полюс 77) на вход элемента 58 И и, так как сФормирован начальный узел сетевого графика, он проходит через элемент 58 И и устанавливает триггер 48 в нулевое состояние. Единичные состояния триггеров 11 указывают на принадлежность ветвей длиннейшему пути сетевого графика. При этом в графике возможно существование нескольких равнокритичных путей, хотя для распределения ресурсов необходимо иметь только один из них.Для определения одного критического пути из множества длиннейших путей сетевого графика в блоке 3 предварительно в задатчики 43 и 44 заносятся соответственно адреса начального и конечного узлов сетевого графика, триггеры 45-48 устанавливаются в нулевые состояния,и на полюс 74 подается разрешающий сигнал.Сигнал Пуск, поступающий на полюсбб блока 3, проходит через элемент60 И и устанавливает триггер 48 вединичное состояние. Последнее состояние триггера 48 выдает разрешениена выход (полюс 75) блока 3, соединенного с входом элемента 40 И блока 2, а также разрешает прохождение импульсов с выхода генератора 4 через элемент 57 И на вход элемента 64. Элемент 64 производит сдвиг основной серии тактовых импульсов генератора 4 и выдает синхронизирующую серию импульсов на выход(полюс 76) блока 3, которая поступает на входы элементов 25 и. 26 Ивсех моделей 1,Кроме того, сигнал с выхода триггера 48 поступает через элемент 61ИЛИ и разрешает прохождение импульсов с выхода генератора 4 через элемент 50 И на входы задатчиков 43и 44. Как и прежде импульсы с выхода элемента 50 И проходят через элемент 52 И, на втором входе которогоприсутствует разрешение через элемент 63 ИЛИ с выхода триггера 48 далее через элемент 62 ИЛИ на выход (полюс 76) блока 3, где поступают на вход элемента 35 ИЛИ. Импульсы с выхода элемента 35 ИЛИ поступают на входы задатчиков 5 и б до тех пока на выходах задатчиков б, в которых записан адрес конечного узла сетевого граФика, не появляется сигнал переполнения.В этот же момент времени на выходе задатчика 44 в блоке 3 появляется сигнал переполнения, который проходит через элемент 56 И, так как,на втором входе элемента присутствует разрешение с выхода элемента63 ИЛИ, на выход (полюс 71) блока управления и далее поступает на вход элемента 42 ИЛИ. Выходной сигналс элемента 42 ИЛИ поступает на входы элементов 23 и 24 И, Разрешающийсигнал проходит через элемент 23 И,если триггер 11 находится в единичном состоянии и присутствует сигнал с выхода задатчика б, т.е. если ветвь сформировала свою длитель 5 1 О 15 2050 55 бО 65 ность последней в конечном узле сетевого графика. Навыходе элемента 24 И появляется разрешающий сигнал в моделях ветвей, где имеется разрешение с выхода элемента 26 НЕ, т.е. ветвь не оканчивается в конечном узле сетевого графика.Сигнал. с выхода элемента 23 И устанавливает триггер 20 в одних моделях ветвей в единичное состояние, а в других с выхода элемента 24 И подтверждает нулевое состояние триггера 20. Таким образом, в единичном состоянии находятся триггеры 20 тех моделей 1 ветвей, которые Формируют моделируемую длительность последними в конечном узле сетевого графика. Вслед за этим синхронизирующий импульс (сдвинутый относительно основной серии тактового генератора 4) поступает из блока 3 на входы элементов 25 и 26 И и устанавливает триггер 21 в состояние, аналогичное триггеру 20. В тех моделях ветвей, где триггеры 21 находятся в единичном состоянии, разрешается прохождение импульсов с выхода задатчика начального узла через элемент 27 И. Как только это происходит в одной из моделей 1, сигнал с выхода элемента 27 И устанавливает триггер 22 своей модели в единичное состояние и поступает через элемент 41 ИЛИ на вход элемента 40 И. Сигнал с выхода элемента 40 И поступает через элемент 42 ИЛИ на входы элементов 23 и 24 И, При этом устанавливается в единичные состояния триггеры 20 тех моделей ветвей, которые последними сформируют длительность в начальном узле рассмотренной ветви. А остальные триггеры 20 устанавливаются в нулевые состояния, тем самым из множества критических путей всегда выбирается один.Блок управления при этом прекращаетподачу основной серии импульсов наполюс 67 и синхронизирующей серииимпульсов на полюс 76 и подает запретна полюс 75.Единичные состояния триггеров 22указывают на принадлежность ветвейодному из критических путей сетевогографика, а блоки 29 индикации позволяют проиндицировать полученный путь-,В устройстве обеспечивается поступление необходимых сигналов управления и предварительного установа(не показаны),Технико-экономическая эффективность изобретения заключается в расширении класса решаемых задач. 15Формула изобретенияУстройство для моделирования се Отевого графика по авт,св. Р 608169,о т л и ч а ю щ е е с я тем, что,с целью расширения класса решаемыхзадач, в каждый блок моделированияветвей дополнительно введены шестой, седьмой, восьмой, девятый идесятый элементы И, пятый, шестой иседьмой триггеры, третий элемент НЕи блок индикации, в каждый блок формирования топологии дополнительновведены пятый элемент И, шестой иседьмой элементы ИЛИ, причем в блоке формирования топологии выходпятого элемента И подключен к первому входу шестого элемента ИЛИ, второй вход которого соединен с четвертым выходом блока управления, четвертый вход которого подключен квыходу шестого элемента ИЛИ,выход седьмого элемента ИЛИ соединен с первым входом пятого элемента И, второй вход которого подключен к пятому выходу блока управления, в блоке моделирования ветвей выход третьего элемента НЕподключен к первому входу седьмогоэлемента И, выход которого, соединенс первым входом пятого триггера,первый выход которого подключен кпервому входу девятого элемента И,выход которого соединен с первымвходом шестого триггера, выходкоторого подключен к первому входудесятого элемента И, выход которогосоединен с входом седьмого триггера,выход которого подключен к входублока индикации, выход одного задатчика адресов соединен с входомтретьего элемента НЕ блока моделирования ветвей и первым входом шестого элемента И блока моделированияветвей, выход которого подключен квторому входу пятого триггера,второй выход которого соединен с первым входом восьмого элемента И блокамоделирования ветвей, выход которогопбдключен к второму входу шестоготриггера, выход второго дополнительного триггера соединен с вторым входом шестого элемента И, выход другого задатчика адресов подключен квторому входу десятого элемента И,выход которого подключен к входуседьмого элемента ИЛИ блока формирования топологии, выход шестого элемента ИЛИ блока формирования топологии соединен с вторюм входом седьмого и третьим входом шестого элементов И блока моделирования ветвей,шестой выход блока управления подключен к вторым входам восьмого.и девятого элементов И блока моделированияветвей,Источники информации,принятые во внимание при экспертизе 1. Авторское свидетельство СССРР 608169, кл. 6 06 6 7/122, 1975 (прототип).Патент, г.ужгород, ул,Проектная лиал Заказ 6095/64 Тираж 745 ВНИИПИ Государственного ко по делам изобретений и о 113035, Москва, Ж, Рауш