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

 

Оп ИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Социапистическик

Респуублик

< >849232

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (Щ 3аявлено . 110130 (21) 2872430/18-24 с присоединением заявки HP— (23) Приоритет

Опубликовано 230781.Бюллетень Н9 27 (51 )М. Кл.

G 06 G 7/1 22

Государствеиный комитет

СССР по делам изобретений и открытий (53) УДХ 681.333 (088.8) Дата опубликования описания 2307,81

А, Ã.Äîäoíîâ, В.В. Месяц, В; В. Хаджинов, В.М. Ш и A.М.Щетинин (72) Авторы изобретения

j,1,,, 1

Институт электродинамики AH Украинской ССР (71) Заявитель

I (г

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

СЕТЕВОГО ГРАФИКА

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

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

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

849232

20

30

45

55

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

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

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

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

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

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

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

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

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

В качестве задатчиков 5 и б адресов используются счетчики импульсов. Формирователь 7 временных интервалов выполняется на основе счетчико-регистровых структур. Каждая модель ветви предназначена для моде849232 лирования одной работы исследуемого сетевого графика.

В блок 2 формирования топологии, содержащий элементы 30-33 И, элементы 34-38 ИЛИ, элемент 39 НЕ, дополнительно введены элемент 40 И и элементы 41-42 ИЛИ. Блок 2, соединенный

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

Он состоит из задатчиков 43 и 44 на- 15 чального и конечного узлов сетевого графика, соответственно, выполненных аналогично задатчика 5 и б; триггеров 45-48, элементов 49-60 И; элементов 61-63 ИЛИ.и элемента .64 за- 2() держки. Блок 3 предназначен для осуществления первоначального запуска всего устройства и организации взаимосвязанной работы блоков устройства.

Устройство работает следующим образом.

Предварительно в задатчики 5 и б заносятся соответственно адреса начального и конечного узлов ветвей сетевого графика. В формирователь 7 заносится длительность ветви, а триггеры 8-11 и 20-22 устанавливаются в нулевые состояния.

В блоке.3 управления предварительно в задатчики 43 и 44 заносятся

35 соответственно адреса начального и конечного узлов сетевого графика, триггеры 45-48 устанавливаются в нулевые состояния. Для запуска всех моделей 1 ветвей на полюс .65 блока 40

3 подается разрешающий сигнал. Сигнал Пуск, поступающий на полюс

66 блока 3, проходит через элемент

59 И и устанавливает триггеры 45 и

47 в единичные состояния, Последнее 45 состояние триггера 45 выдает разрешение через элемент 61 ИЛИ на вход элемента 50 И, импульсы с выхода генератора 4 проходят на выход блока 3 (полюс 78) и через элемент 50

И на входы задатчиков 4 3 и 44.

Кроме того, импульсы с выхода элемента 50 И проходят через элемент

51 И, на втором входе которого присутствует разрешение с выхода триггера 47, далее через элемент 62 ИЛИ на выход блока 3 (полюс 67), где поступают на вход элемента 35 ИЛИ блока 2 формирования топологии.

Импульсы с выхода элемента 35 ИЛИ поступают на входы задатчиков 5 и б бО до тех пор, пока на выходах графика не появляется сигнал переполнения. В этот же момент времени на выходе задатчика 43 начального узла сетевого графика в блоке 3 появляет- 65 ся сигнал переполнения, который проходит через элемент 53 И, так как на втором входе элемента присутствует разрешение с выхода триггера 45, на выход блока управления (полюс 6B) и далее поступает на вход элемента

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. Сигнал с выхода задатчика б, в котором записан адрес конечного узла ветви, устанавливает в нулевое состояние триггер 8 и поступает на входы элементов 13-15 И и 18 НЕ.

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

9 проходит через элементы 13 И и

19 ИЛИ к одному,из входов элемента

31 И.

В тех случаях, когда импульсы на выходе задатчика адресов б отсутствуют, на вход элемента 31 И разрешающий сигнал поступает с выхода элемента 18 НЕ. Таким образом, запрет на входах 31 И только в тех моделях ветвей, которые входят в рассматриваемый узел, но не сформировали свою длительность. В этом случае запрещающий сигнал проходит на выход элемента 31 И и через элемент 36 ИЛИ на полюсы всех моделей 1. Этот сигнал запрещает подготовку соответствующих формирователей 7 к отсчету импульсов с генератора 4.

На выходе элемента 17 НЕ возникает при этом разрешающий сигнал, который поступает на второй вход эле849232 мента 14 И и, так как на первом его входе присутствует выходной сигнал задатчика 6, триггер 10 устанавливается в нулевое состояние.

Если все ветви, входящие в рассматриваемый узел, формировали временной интервал, на выходе элемента

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

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

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

55 И и устанавливает триггер 45 в нулевое состояние.

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

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

43 заносятся соответственно адреса начального и конечного узлов сетевого графика, триггеры 45-48 устанавливаются в нулевые состояния и на полюс

69 подается разрешающий сигнал.

Сигнал Пуск, поступающий на полюс 66 блока 3, проходит через элемент 49 И и устанавливает триггер 46 в единичное состояние. Последнее состояние триггера 46 выдает разре- 60 шение на выход (полюс 70) блока 3, соединенного с входом элемента 33 И, а также сигнал с выхода триггера 46 проходит через элемент 61 ИЛИ и разрешает прохождение импульсов с выХо- 65 да генератора 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

45

Единичные состояния триггеров 11 указывают на принадлежность ветвей длиннейшему пути сетевого графика.

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

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

74 подается разрешающий сигнал.Сигнал Пуск, поступающий на полюс

66 блока 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 и 6 до тех пока на выходах задатчиков 6, в которых записан адрес конечного узла сетевого граФика, не появляется сигнал переполнения.

В этот же момент времени на выходе задатчика 44 в блоке 3 появляется сигнал переполнения, который проходит через элемент 56 И, так как,на втором входе элемента присутствует разрешение с выхода элемента

63 ИЛИ, на выход (полюс 71) блока управления и далее поступает на вход элемента 42 ИЛИ. Выходной сигнал с элемента 42 ИЛИ поступает на входы элементов 23 и 24 И. Разрешающий сигнал проходит через элемент 23 И, если триггер 11 находится в единичном состоянии и присутствует сигнал с выхода задатчика 6, т.е. если ветвь сформировала свою длитель5

1О

20

55 бО

65 ность последней в конечном узле сетевого графика. Ha выходе элемента

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

Сигнал. с выхода элемента 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 в нулевое состояние.

849232

Блок управления при этом прекращает пода чу основной серии импульсов на полюс 67 и синхронизирующей серии импульсов на полюс 76 и подает запрет на полюс 75.

Единичные состояния триггеров 22 указывают на принадлежность ветвей одному из критических путей сетевого графика, а блоки 29 индикации позволяют проиндицировать полученный путь °

В устройстве обеспечивается поступление необходимых сигналов управления и предварительного установа (не показаны).

Технико-экономическая эффективность изобретения заключается в расширении класса решаемых задач. 15

Формула изобретения

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

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

9 608169, кл. G 06 G 7/122, 1975 (прототип).

849232

71

7 6

Составитель И.Дубинина

Редактор Г.Кацалап Техред M.Ãoëèíêà Корректор Л.Иван

Заказ 6095/64 Тираж 745 Подписное

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

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

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