Устройство для моделированияСЕТЕВОгО гРАфиКА Советский патент 1981 года по МПК G06G7/122 

(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВОГО ГРАФИКА

1

Изобретение относится к вычислительной технике, а именно к устройствам для моделирования сетевого графика.

По основному .авт.св. 608169 известно устройство для моделирования .сетевого графика, содержащее блок управления, генератор импульсов,блок формирования топологии и блок моделей ветвей по числу работ, каждая из которых состоит из задатчиков адресов, выходы которых подключены соответственно к первым входам первого и второго элементов И, второй вход первого элемента ИЛИ блока формирования топологии, выход второго элемента И подключен к одному входу формирователя временных интервалов, другой вход которого соединен с выходом первого элемента И блока форми.рования :топологии,.выход формирователя временных интервалов подключен к первым входам триггеров, второй вход второго триггера соединен с выходом соответствукадего зёщатчика адресов, выход второго триггера подключен к входу второго элемента ИЛИ блока формирования топологии первый вход элемента ИЛИ блока моделей ветвей соединен с выходом первого элемента И, второй вход элемента ИЛИ через элемент НЕ подключен к выходу соответствукяцего задатчика адресов, а выход элемента ИЛИ блока формирования топологии, который состоит из элементов И и элементов ИЛИ,причем выход второго элемента ИЛИ непосредственно и через элемент НЕ подключен к одним входам элементов И, другие

10 входы которых соединены с выходами генератора импульсов, выход третьего элемента И подключен к первому входу третьего элемента ИЛИ, второй вход которого соединен с первым выходом блока управления, второй выход которого подключен к первому входу первого элемента ИЛИ блока формирования топологии, второй вход которого соединен с выходом второго элемента

20 ИЛИ, выходы первого и третьего элементов ИЛИ подключены соответственно к входам задатчиков адресов и второго элемента И блока моделей ветвей, кроме того, в блок формирования топо25логии и блок моделей ветвей введены дополнительно триггеры, элемент НЕ и элементы И и ИЛИ, причем в блоке формирования ветвей первый вход первого дополнительного элемента И под30 ключей к выходу соответствующего

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

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

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

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

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

На фиг.1 приведена функциональная схема устройства; на фиг.2 - блок управления.

Устройство состоит из блока моделей 1 ветвей, блока 2 формирования топологии, блока 3 управления и генератора 4 импульсов.

В каждую,модель 1 ветви, содержащую задатчики 5 и 6 адресов, формирователь 7 временных интервалов, триггеры 8-11, элементы 12-16 И, элементы 17 и 18 НЕ и элемент 19 ИЛИ дополнительно введены триггеры 2022, элементы 23-27 И, элемент 28 НЕ и блок 29 индикации.

В качестве задатчиков 5 и 6 адресов используются счетчики импульсов . Формирователь 7 временных интервалов выполняется на основе счетчико-регистровых структур. Каждая модель ветви предназначена для моделирования одной работы исследуемого сетевого графика. В блок 2 формирования топологии, содержащий элементы 30-33 И, элемен ты 34-38 ИЛИ, элемент 39 НЕ, дополнительно введены элемент 40 И и эле менты 41-42 ИЛИ. Блок 2, соединенны с блоком моделей 1 ветвей, обеспечи вает взаимодействие моделей 1 ветве сетевого графика по временному прин ципу на основании адресов начальног и конечного событий, занесенных в з датчики 5 и б, Блок 3 управления может быть выполнен различным образом и один из его вариантов изображен на фиг.2. Он состоит из задатчиков 43 и 44на чального и конечного узлов сетевого графика, соответственно, выполненны аналогично задатчика 5 и б; триггеров 45-48, элементов 49-60 И; элементов 61-63 ИЛИи элемента 64,задержки. Блок 3 предназначен для осу ществления первоначального запуска всего устройства и организации взаимосвязанной работы блоков устройства. Устройство работает следующим образом. Предварительно в задатчики 5 и б заносятся соответственно адреса начального и конечного узлов ветвей сетевого графика. В формирователь 7 заносится длительность ветви, а триггеры 8-11 и 20-22 устанавливают ся в нулевые состояния. В блоке 3 управления предварител но .в задатчики 43 и 44 заносятся соответственно адреса начального и конечного узлов сетевого графика, триггеры 45-48 устанавливаются в ну левые состояния. Для запуска всех моделей 1 ветвей на полюс -65 блока 3 подается разрешающий сигнал. Сигнал Пуск, поступающий на полюс 66 блока 3, проходит через элемент 59 И и устанавливает триггеры 45 и 47 в единичные состояния.. Последнее состояние триггера 45 выдает разрешение через элемент 61 ИЛИ на вход элемента 50 И, импульсы с выхода генератора: 4 проходят на выход блока 3 (полюс 78) и через элемент 50 И на входы задатчиков 43 и 44. Кроме того, импульсы с выхода элемента 50 И проходят через элемен 51 И, на втором входе которого присутствует разрешение с выхода триггера 47, далее через элемент 62 ИЛИ на выход блока 3 (полюс 67), где поступают на вход элемента 35 ИЛИ блока 2 формирования топологии. Импульсы с выхода элемента 35 ИЛИ поступают на входы задатчиков 5 и б до тех пор, пока на выходах графика не появляется сигнал переполнения. В этот же момент времени на выходе задатчика 43 начального узла сетевого графика в блоке 3 появляется сигнал переполнения, который проходит через элемент 53 И, так как на втором входе элемента присутствует разрешение с выхода триггера 45, на выход блока управления (полюс 66) и далее поступает на вход элемента 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 и 6. Сигнал с выхода задатчика 6, в котором записан адрес конечного узла ветви, устанавливает в нулевое состояние тпиггер 8 и поступает на входы элементов 13-15 И и 18 НЕ. Если ветвь, в которой появляется импульс на выходе задатчика 6, закончила формирование временного интервала, .сигнал с выхода триггера 9 проходит через элементы 13 И и 19 ИЛИ к одному,из входов элемента 31 И. В тех случаях, когда импульсы на выходе задатчика адресов 6 отсутствуют, на вход элемента 31 И разрешающий сигнал поступает, с выхода элемента 18 НЕ. Таким образом, запрет на входах 31 И только в тех моделях ветвей, которые входят в рассматриваемый узел, но не сформировали свою длительность. В этом случае запрещающий сигнал проходит на выход элемента-31 И и через элемент 36, ИЛИ на полюсы всех моделей 1. Этот сигнал запрещает подготовку соответствующих формирователей 7 к отсчету импульсов с генератора 4., На выходе элемента 17 НЕ- возникает при этом разрешающий сигнал, котоый поступает на второй вход элеента 14 И и, так как на первом го входе присутствует выходной игнал задатчика 6, триггер 10 устаавливается в нулевое состояние.

Если все ветви, входящие, в расматриваемый узел, формировали , вреенной интервал, «а выходе элемента 31 И блока 2 появляется разрешающий сигнал, который поступает через элеент 36 ИЛИ на полюсы моделей ветвей. Разрешающий сигнал запрещает через элемент 17 Н-Е установку триггера 10 в нулевое состояние и также проходит на выход элемента 12 И тех моделей, которые выходят из рассматриваемого узла, т.е. тех ветвей, где в данный момент времени есть сигнал на выходе задатчька 5.

Импульсы с генератора 4 поступают на входы задатчиков 5 и б до тех пор, пока хотя бы на одном из входов блока 2 присутствует сигнал с выхода триггера 8 какой-либо модели 1. После того, как все триггеры 8 установлены в нулевое состояние выходными сигналами соответствующих задатчиков адресов, блок 2 запрещает прохождение импульсов этой серии на входы задатчиков адресов и разрешает поступление импульсов первой серии на входы формирователей временных интервалов. Когда сформирован конечный узел сетевого графика, все триггеры 8 моделей 1 устанавливаются в нулевые состояния.После этого сигнал с выхода элемента 36 ИЛИ блока 2 поступает в .блок 3 на вход элемента 55 ИЛИ как сформирован конечный узел сетевого графика, импульс переполнения с выхода задатчика 44 проходит через элемент 55 -И и устанавл ивает триггер 45 в нулевое состояние.

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

Для определения конфигурации длиннейших путей между начальным и конечным узлами сетевого графика в блоке 3 предварительно в задатчики 43 и 43 заносятся соответственно адреса начального и конечного узлов сетевого графика, триггеры 45-48 устанавливаются в нулевые состояния и на полюс G9 подается разрешающий сигнал.

Сигнал Пуск, поступающий на полюс 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 через элемент 1 И на вход элемента 38 ИЛИ блока 2. Остальные входы этого элемента разделения подключены к аналогичным выходам остальных моделей ветвей. Сигнал с выхода элемента 38 И поступает на второй вход элемента 33 И и через элемент 37 ИЛИ на входы элементов 15 И. При этом устанавливаются в единичное состояние триггеры 11 тех моделей ветвей, которые последними формируют длительность в начальном узле рассмотренной ветви.

Подобный процесс продолжается до тех пор, пока на входах блока формирования топологии не появляется сигнал с выхода задатчиков 5, соответствующих начальному узлу сетевого графика. Это об окончании процесса выделения длиннейшого пути.

При этом выработанный сигнал с выхода элемента 37 ИЛИ поступает в блок 3 (полюс 72) на вход элемента 54 И и,так как сформирован начальный узел сетевого графика, он проходит через элемент 54 и и устанавливает триггер 46 в нулевое состояние.

Блок управления при этом прекращает подачу импульсов на элемент 35 ИЛИ и подает запрет на элемент 33 И. Единичные состояния триггеров 1 указывают на принадлежность ветвей длиннейшему пути сетевого графика. При этом в графике возможно существование нескольких равнокритичных путей, хотя для распределения ресу сов необходимо иметь только один из них. . Для определения одного критического пути из множества длиннейших путей сетевого графика в блоке 3 предварительно в задатчики 43 и 44 заносятся соответственно адреса начального и конечного узлов сетевого графика, триггеры 4.5-48 устанавлива ются в нулевые состояниями на полюс 74 подается разрешающий сигнал.Сиг нал Пуск, поступающий на полюс 66 блока 3, проходит через элемент 60 И и устанавливает триггер 48 в единичное состояние. Последнее сое тояние триггера 48 выдает разрешен на выход (полюс 75) блока 3, соединенного с входом элемента 40 И бл ка 2, а также разрешает прохождени импульсов с выхода генератора 4 чег рез элемент 57 И на вход элемента Элемент 64 производит сдвиг основной серии тактовых импульсов.генератора 4 и выдает синхронизирующую серию импульсов на выход (полюс 76) блока 3, которая поступает на входы элементов 25 и.26 И всех моделей 1. Кроме того, сигнал с выхода триг гера 48 поступает через элемент 61 ИЛИ и разрешает прохождение импульсов с выхода генератора 4 через эле мент 50 И на входы задатчиков 43 и 44. Как и прежде импульсы с выхода элемента 50 И проходят через эле мент 52 И, на втором входе которого присутствует разрешение через элемент 63 ИЛИ с выхода триггера 48 далее через элемент 62 ИЛИ на выход (полюс 76) блока 3, где поступают на вход элемента 35 ИЛИ. Импульсы с выхода элемента 35 ИЛИ поступают на входы задатчиков 5 и 6 до тех пока на выходах задатчиков 6, в которых записан адрес конечного узла сетевого графика, не появляется сигнал переполнения. В этот же момент времени на выходе задатчика 44 в блоке 3 появляется сигнал переполнения, который проходит через элемент 56 И, так как,на втором входе элемента присут ствует разрешение с выхода элемента 63 ИЛИ, на выход (полюс 71) блока управления и далее поступает на вхо элемента 42 ИЛИ. Выходной сигнал с элемента 42 ИЛИ поступает на входы элементов 23 и 24 И. Разрешающий сигнал проходит через элемент 23 И, если триггер 11 находится в единичном состоянии и присутствует си1- нал с выхода задатчика 6, т.е. если ветвь сформировала свою длительность последней в конечном узле сетевого графика. На выходе элемента 24 И появляется разрешающий сигнал в моделях ветвей, где имеется разрешение с выхода элемента 2Ь НЕ, . т.е. ветвь не оканчивается в конечном узле сетевого графика. Сигнал- с выхода элемента 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 устанавливаются в нулевые состояния тем самым из множества критических путей всегда выбирается один. Затем вновь происходит установка триггера 21 в состояние, подобное положению триггера 20, и определяется начальный узел хотя бы одной ветви, у которой на единичном выходе триггера 21 присутствует разрешение. Подобный процесс продолжается до тех пор, пока на входах .блока не появляется сигнал с выхода задатчиков 5, соответствующих начальному узлу сетевого графика. Это говорит об окончании процесса выделении одного критического пути из множества длиннейших путей сетевого.графика. При этом выработанный сигнал с выхода элемента 42 ИЛИ поступает в блок 3 (полюс 77) на вход элемента 58 И и, так как сформирован начальный узел сетевого графика, он проходит через элемент 58 И и устанавливает триггер 48 в нулевое состояние. Блок управления при этом прекращает подачу основной серии импульсов на полюс 67 и синхронизирующей серии импульсов на полюс 76 и подает запр на полюс 75. Единичные состояния триггеров 22 указывают на принадлежность ветвей одному из критических путей сетевог графика, а блоки 29 индикации позво ляют проиндицировать полученный путь В устройстве обеспечивается поступление необходимых сигналов управ ления и предварительного установа (не показаны). Технико-экономическая эффективность изобретения заключается в рас ширении класса решаемых задач. Формула изобретения Устройство для моделирования сетевого графика по авт.св. № 608169, отличающееся тем, что, с целью расширения класса решаемых задач, в каждый блок моделирования ветвей дополнительно введены шеетой, седьмой, восьмойf девятый и десятый элементы И, пятый, шестой и седьмой триггеры, третий элемент НЕ и блок индикации, в каждый блок фор мирования топологии дополнительно введены пятый элемент И, шестой и седьмой элементы ИЛИ, причем в блоке формирования топологии выход пятого элемента И подключен к перво му входу шестого элемента ИЛИ, -второй вход которого соединен с четвер тым выходом блока управления, четве тый вход которого подключен к выходу шестого- элемента ИЛИ, выход седьмого элемента ИЛИ соединен с первым входом пятого элемента И, второй вход которого подключен к пятому выходу блока управления, в блоке моделированияветвей выход третьего элемента НЕ подключен к первому входу седьмого элемента И, выход которого .соединен с первым входом пятого триггера, первый выход которого подключен к первому входу девятого элемента И, выход которого соединен с первым входом шестого триггера, выход которого подключен к первому входу десятого элемента И, выход которого соединен с входом седьмого триггера, выход которого подключен к входу блока индикации, выход одного задатчика адресов соединен с входом третьего элемента НЕ блока моделирования ветвей и первым входом шестого элемента И блока моделирования ветвей, выход которого подключен к второму входу пятого триггера,второй выход которого соединен с первым входом восьмого элемента И блока моделирования ветвей, выход которого подключен к второму входу шестого триггера, выход второго дополнительного триггера соединен с вторым входом шестого -элемента И, выход другого задатчика адресов подключен к второму входу десятого элемента И, выход которого подключен к входу седьмого элемента ИЛИ блока формирования топологии, выход шестого элемента ИЛИ блока формирования топологии соединен с вторым входом седьмого и третьим входом шестого элементов И блока моделирования ветвей, шестой выход блока управления подключен к вторым входам восьмого.и девятого элементов И блока моделирования ветвей. Г Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР № 608169, кл. G 06 G 7/122, 1975 (прототип).