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

 

УСТРОЙСТВО ДНЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ ГРАФИКОВ по авт.св. № 422002, отличающееся тем, что, с целью расширения класса решаемых . задач, в устройство введен блок памяти , в блок формирования топологии введены два Ч:четчика, сдвиговый регистр, два дополнительйьй элемента И и элемеш НЕ, причем первый вход первого дополнительного элемента И соединен с выходом первого элемента ИЛИ блока формирования топологии, с первьм входом сдвигового регистра и с входом первого счетчика, выходы которого подключены к информационным входам блока памяти, адресные входы которого соединены с выходами второго счетчика, управляющий вход блока памяти подклазчен к выходу первого дополнительного элемента И и входу элемента НЕ, ыход которого соединен с входом второг о счетчика и с первым входом второго дополнительного элемента И, выход которого подключен к второму входу сдвигового, регистра, выход которого соединен с вторыми входами первого и второго | дополнительных элементов И блока Фор мированйя топологии, третий вход первого дополнительного элемента И блока формирования топологии соединен с выходом третьего элемента И блока формирования топологии, выход блока памяти является выходом устройства .

СО1ОЭ СОВЕТСНИХ

ОСЦ4ЧЯО

РЕСПУБЛИН заев G 06 G 7/48

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЭОБРЕТЕНИЙ И О 7НРЫТИЙ (6!) 422002 (21) 3619402/24-24 (22) 01.06.83 (46) 07.12.84. Бюл. У 45 (72) А;И.Варанов, В.В.Васильев и О.Н.Голованова (71) Институт проблем моделирования в энергетике AH Украинской CCP (53) 681.333(088.8) (56) 1. Авторское свидетельство СССР

И 422002,. кл. G 06 G 7/48, 1972 (прототип). (54){57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

СЕТЕВЫХ ГРАФИКОВ но авт.св. У 422002, отличающееся тем, что, с целью расширения класса решаемых эадач, в устройство введен блок памяти, в блок формирования топологии . введены два счетчика, сдвиговый регистр, два дополнительнйй элемента И и элемен НЕ, причем первый вход первого дополнительного элемента И соединен с выходом первого элемента ,.SU„„3128272 А

ИЛИ блока формирования топологии, с первым входом сдвигового регистра и с входом первого счетчика, выходы которого подключены к информационным входам блока памяти, адресные входы которого соединены с выходами второго счетчика, управляющий вход блока памяти подключен к выходу первого дополнительного элемента И и входу элемента HE,:óüìîä которого соединен с входом второго. счетчика и с первым входом второго дополкительного элемента И, выход которого подключен к второму входу сдвигового . регистра, выход которого соединен с вторыми входами первого и второго Я дополнительных элементов И блока формированйя топологии, третий вход первого дополнительногэ элемента И блока формирования топологии соединен с выходом третьего элемента И блока формирования топологии, выход блока памяти является выходом устройст- laeL . ва. М

272 устройства.

S 1 128

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

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

И, к второму входу которого и к

35 третьему входу первого элемента И подключены выходы второго триггера, входы задатчиков адресов каждой модели ветви соединены с выходом первого элемента. ИЛИ блока формирова40 ния топологии, содержащего второй элемент ИЛИ, подключенный через инвертор к второму элементу И, и последовательно соединенные третий элемент И и третий элемент ИЛИ, вы45 ход и вход которого подключены соот-. ветственно к входу и второму выходу блока управления, причем первый выход генератора импульсов соединен с вторым входом второго элемента И блока формирования топологии, выход которого подключен к входу формирователя временных интервалов каждой модели ветви, вход блока управления соединен с четвертым входом первого элемента И каждой модели ветви, выход первого триггера каждой модели ветви. подключен к входу второго элемента ИЛИ блока формирования топологии, выход второго элемента ИЛИ каждой модели ветви соединен с входом третьего элемента И блока формирования топологии (1$ .

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

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

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

На фиг.1 приведена функциональная схема предлагаемого устройства; на фиг. 2 — пример работ, требующих упорядочения; на фиг. 3 — сеть специального вида для работ, требующих упорядочения; на фиг. 4 — формирователь временных интервалов; на фиг.5 блок управления.

272

3 1.128

Схема устройства включает блок 1 моделей ветвей, блок 2 формирования топологии, блок 3 управления, генератор 4 импульсов, блок 5 памяти. Некоторые связи, относящиеся к блоку управления и обеспечивающие начало и окончание работы устройства, рассмотрены на фиг.5. Назначение и работа блока управления (фиг.5) в предлагаемом устройстве абсолютно. те же, что l0 и в известном.

Каждая модель ветви содержит формирователь 6 временных интервалов, задатчик 7 адреса начального узла, задатчик 8 адреса конечного узла, триггеры 9 и 10, элементы И 11 и 12, элемент ИЛИ 13, инвертор 14. Блок формирования топологии содержит счетчики 15 и 16, сдвиговый регистр 17, элемент И 18-22, элементы ИЛИ 23-25, инвертор 26, элемент НЕ 27. ,Формирователь 6 временных интервалов фиг.4 включает счетчик 28, три гер 29, элементы И 30 и 31, входы 32 и 33, выход 34. 25

Вход 32 соединен с выходом элемента И 19 (фиг.1), вход 33 †. с выходом элемента И 11 (фнг.1), выход 34— с входом триггера 9 (фиг.1) .

Блок управления содержит счетчики 35-37, триггеры 38-40, элементы

И 41-44, элемент Не 45, элемент

ИЛИ 46.

Блок 3 управления предназначен 35 для выдачи .сигналов начала и окончания работы устройства, а также для определения длины критического пути сетевого гоафика. Генератор 4 импульсов предназначен для выдачи .40 импульсов двух серий - . и 6 сдвинутых один относительно другого.

Элементы каждой модели ветви соединены между собой таким образом, что обе .печивают моделирование длины со- 45

1 ответствующей ветв-» сетевого графика. Эта длина отображается временным интервалом, кратным числу импульсов серии Д . Собственно длина ветви мо. дулируется формирователем 6 временных50 интервалов, остальные злементш модели. ветви и блок 2 формирования топологии обеспечивают выдачу разрешающего сигнала на модель ветви в нужный момент времени. При решении saдачи упорядочения работ блоки 1 и 2 предназначены для определеня той работы, которая должна быть поставлена на следующее место В формируемой очереди работ.

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

В последнем случае этот набор работ представляется сетью специального вида, при моделировании которой устройство обеспечивает запись номеров работ в блок памяти в порядке, определяемом длительностью работ.

В том и в другом случае элементы и блоки устройства работают одинаково, отличие состоит только в содержании вводимой и, следовательно, накапливаемой в блоке памяти информации, значит данное устройство в том и другом случае моделирует сеть (либо сетевой график, либо сеть специапьного вида). Блок 5 памяти и дополнительные элементы: счетчики 15. и 16, элементы И 21 и 22, элемент НЕ 27, обеспечивают последовательную запись в ячейках блока памяти упорядоченной последовательности. номеров работ при решении задачи упорядочения. Номера работ, требующих упорядочения, при вводе и формации в устройство отмечаются единицами в соот- ветствующих разрядах регистра 17.

При моделировании сетевого графика содержимое регистра 17 равно нулю и запись информации в блок памяти не производится.

Во время работы формирователя временных интервалов {фиг.4), по входу

33 на него подается разрешающий сигнал, устанавливающий триггер 29 в единицу. В счетчик вначале заносится число N — 1 — 1 где N — емкость счетчика, 1 — длина соответствующей . ветви. Единичный выход каждого разря- да счетчика 28 соединен с соответствующим входом элемента И 31. Таким образом, на выходе 34 появляется единичный сигнал, когда в счетчике saписано число N-l, и триггер 29 находится в единичном состоянии (т.е. единичный выход триггера также соединен с одним из входов элемента И

31) . Выход элемента h 31 соединен с входом установки в нуль счетчика. 28.

Рассмотрим работу формирователя на примере моделирования ветви длиной .1, начиная с момента, когда на вход 33 подан разрешающий единичный сигнал.

По этому сигналу триггер 29 устанавливается в единицу и импульсы се45

11282 рии Д начинают поступать через элемент И 30 на вход счетчика 28.. Эти импульсы увеличивают содержимое счет.чика, которое вначале равно N — 1 — 1.

После поступления шипульсов серии содержимое счетчика становится равным 0-1, т.е. в каждом разряде счетчика имеется единица (например при И !6, N-1!5, т.е. в двоичном коде это 1111 и т.д.) . Единичный !О сигнал поступает на выход элемен-. та И 31,. на вьасод 34 формирователя а оттуда - на триггер 9 (фиг.1), устанавливая его в единицу. Этот же сигнал сбрасывает в куль счетчик 28, снимая тем самым сигнапы с входов элемента И 31. Если О,- то исходное содержимое счетчика равно N-l.

Тогда после поступления на вход 33 разрешающего сигнала (и поспе уста- 20 новки в единицу триггера 29 появляется единичный сигнал на выходе элемента И 31 и на выходе 34 формирователя, т.е. ветвь нулевой длины смоделирована сразу после поступления разрешающего сигнапа.

Рассмотрим решение устройством задачи упорядочения на конкретном .примере. Пусть дан набор из пяти работ (фиг.2), калдая из которых характеризуется своим номером (обозначен справа латинской буквой) и длительностью выполнения (указана над иэображением работы). Требуется . упорядочить эти работы по длитель35 ности их выполнения, исходя из принятой дисциплины их выполнения на одной машине. Например, принятая дис. циплина выбора кратчейшей работы.

Это означает, что требуется получить 4 такую последовательность номеров работ, в которой на первом месте стоит номер самой короткой работы, длительность каждой поспедующей рабаты не убывает и последним стоит номер самой длительной работы.

Для. решения этой задачи строится . сеть специального вида (фиг.3) сле дующим образом. Все работы иэ исходного набора представляются ветвями.

50 сети, выходящими из начального узла 5 сети. Длина этой ветви равна длительности соответствующеи работы, а конечный узел ветви имеет номер (адрес):, равный номеру этой работы. Так, ветвь 8 а сети соответ1 . «/» ствует работе 4 и т.д. Конечные узлы ветвей, выходящих иэ началь72 ного узла, соединены с конечным узлом К сети ветвями единичной длины. Длины ветвей сети проставлены над изображениями этих ветвей;

Номера узлов 3, ), a, b c

J., 5 могут быть любыми, но не превышающими адреса N-l,ãäå (N-l) — максимальный адрес узла, который мо-. жет быть записан в задатчик адреса.

Информация об этой сети кодиру" ется и вводится так же, как и в известном устройстве, отличие состоит только в том, что в N разрядный регистр 17 заносятся единицы в разряды а1, Ь, С, J, f (схемы начального ввода информации не показаны). Исходные состояния счетчиков 15 и 16 нулевые, емкость каждого счетчика равна N. Управляющий вход блока памяти является входом разрешения записи, далее он именуется входом эаписие

Моделирование сети как в предла гаемом устройстве, так и в известном выполняется посредством чередования двух периодов: периода моделирования длин ветвей и периода формирования топологии сети.. В первый период на модели ветвей через элемент И 19 поступают импульсы серии во второй период через элементы

И !8 и ИЛИ 23 на модели ветвей поступают импульсы серии 0 . Введенные дополнительно элементы устройства работают только на этапах формирования топологии сети, поэтому основное внимание уделяется периодам формирования топологии сети.

В начале работы .блок 3 управления выдает на вход элемента ИЛИ 23 последовательность из 8 импульсов, которые поступают на входы всех задатчиков 7 и 8 адресов и изменяют их содержимые. Эти же импульсы поступают на вход счетчика 15 и на вход регистра 17, сдвигая его содержимое. Поскольку все триггеры моделей ветвей находятея в нулевом состоянии, на выкоде элемента И 20 блока формирования топологии присутствуют нулевые сигналы в то время, когда на выходе хотя бы одного задатчика 8 присутствует единичный сигнап, а значит и в то время, когда на выходе регистра 17 появляется единичный сигнал. Таким образом. во Время поступления 8 импульсов на выходе элемента И 21 бпока формирования топологии

I.128272 8 все время имеется нулевой сигнал, который через ннвертор 27 и элемент . И 22 разрешает запись единиц с выхода регистра 17 в его первый разряд.

Таким образом, в рассматриваемый отрезок времени происходит только циклический сдвиг содержимого регистра 17, длина этого цикла равна N, содержимые задатчиков н счетчика 15 также циклически повторяются с той же!а длиной И цикла. .После выдачи 5 импульсов появляются единичные сигналы на выходах задатчиков 7 моделей ветвей sa, sb, sc, sd, sf. Блок 3 управления прекращает подачу импульсов на вход элемента

ИЛИ 23 и выдает единичный сигнал на вход элемента ИЛИ 25, по которому через элементы И 11 моделей ветвей sa, sb, sc, sd, sf поступают единичные сигналы, подготавливая их формирова-. тели к отсчету импульсов серии

Содержимое счетчика 16 равно нулю, счетчика 15 — s, На модели других ветвей единичные сигналы от элементов И II не поступают,,так как отсутствуют единичные сигналы на выходах задатчиков .7. С этого момента начинается моделирование длин ветвей, выходящих из начального узла. В течение всего периода моделирования

30 длин ветвей на выходах элементов И

20 и ИЛИ 24 присутствуют нулевые сигналы. Нулевой сигнал на выходе элемента ИЛИ 24 через ннвертар 26 и элемент И 19 разрешает поступление импульсов серии на формирова тели 6 моделей ветвей, выходящих из начального узла сети. Этот нулевой сигнал через элемент И .1 8 запрещает поступление импульсов серии 8 через 40

- элемент И 23 на эадатчнки 7 и 8 моделей ветвей.

После поступления трех импульсов серии Й на выходе формирователя в модели ветви sb появляется единич- 45 иый сигнал, который устанавливает

s единицу триггеры 9 и 10 этой модели ветви. На выходе элемента ИЛИ 24 .появляется единичный сигнал, по которому через инвертор 26 и элемент So

И 19 прекращается выдача импульсов серии А и через элементы И 18 и

ИЛИ 23 разрешается выдача имнульсов серии 6

Эти импульсы поступают на входы 55 всех задатчиков 7 и 8, а также йа

I счетчик 15 и сдвиговый вход регист-, ра 17. После тогр, как на выходе задатчика 8 модели ветви sb появился единичный сигнал, в счетчике 15 записывается число ь, а на выходе ре,гистра 17 присутствует единичный сиг1 нал. Сигнал на выходе эадатчика 8 модели ветви Gь появляется после поступления на этот задатчик (NiN +

+ Ь) импульсов, где М О, I, 2, Счетчик 15 после поступления того же числа импульсов будет в состоянии Ь .

Назначение элементов И 21 и И 22, элемента НЕ 27 и регистра !7 состоит в том, чтобы обеспечить однократную запись каждого номера узла из числа выбранных в ячейки блока памяти. Номера выбранных узлов отмечаются единицами в соответствующих разрядах регистра. Единичный сигнал на выходе элемента И 20 появляется каждый раз при просчете номера свершившегося узла,. так как триггер IО мо дели окончившейся ветви все время находится в единичном состоянии. Единичный сигнал с выхода элемента И 21 через элемент НЕ 27 и И 22 запрещает перезапись единицы с выхода регистра 17 на его вход, которая разрешается теми же элементами только для несвершившихся узлов, т.е. при нулевом сигнале с выхода элемента

И 20.

Единичный сигнал с выхода задатчика 8 модели ветви sb поступает через элемент И 12 на вход и выход элемента ИЛИ 13. Поскольку ветвь

sb .единственная, входящая.в узел то на выходах инверторов 14 всех моделей ветвей кроме sb присутствуют единичные сигналы. Таким образом, на выходе элемента И 20 появляется единичный сигнал. На выходе регистра 17 также есть единич" ный сигнал. Таким образом, на всех входах элемента И 21 есть единичные сигналы. Единичный сигнал с выхода элемента И 21 поступает на вход записи блока 5 па1чяти и в ячейку с . нулевым адресом записывается содержимое счетчика 15, т.е. число

Узел Ь свершился, номер (адрес)- его записан. Единичный сигнал с выхода элемента И 21 через элемент НЕ 27 и элемент.И 22 запрещает злись единицы с выхода регистра 17 на его вход.

Таким образом, в ь -м разряде регистра 17, начиная с этого момента, записан нуль. Нуль на выходе регистра 17 запрещает появление единично40

И

После следующего импульса серии устанавливаются в единицу триггеры 9 и 10 моделей ветвей sd u sf. Ha9 11282

ro сигнала на выходе элемента И 21, поэтому при появлении следующего (И О+ Ь)-го импульса серии р сигнал записи не вьдается и повторной записи номера 0 не будет. Одновременно триггер 9 модели ветви sb сбрасываетс я в нуль, нулевой сигнал на выходе элемента ИЛИ 24 разрешает поступление следующего импульса серии ф на модели ветвей sa, sd, sc, sf, которые 10 еще не окончили свою работу. Разрешающий сигнап поступает также на формирователь 6 модели ветви bk, так как на всех входах элемента И 11 этой модели ветви есть единичные сигналы.

После окончания упомянутого импульса серии g с выхода элемента И 21 исчезает единичный сигнал. Это состветствует появлению единичного сигнала на выходе элемента НЕ 27, который поступает на вход счетчика 16, увеличивая его содержимое на единицу.

Единица прибавляется к содержимому счетчика 16 всякий раз, когда сигнал на выходе элемента И 21 переходит иэ единичного на нулевой уровень. Таким образом, формируется адрес следующей ячейки блока памяти сразу же после записи информации в предьдущую ячейку, Если записи информации по предьдущему импульсу серии f н е б6ы ло, то содержимое счетчика 16 не меняется.

После первого в данном периоде импульса .серии я оканчивается ветвь

Lk. Поскольку К-й узел не свершился, то при подаче (М Я + К)-го импульса серии б на модели ветвей на выходе элемента И 20 будет нулевой сигнал. (так как на выходах) элементов ИЛИ 13 моделей ветви аК, сК, dK, fK нулевые сигналы).

Упомянутый импульс серии Ь сбрасывает в нуль триггер 9 в Ьк -й модели ветви и устройство вновь переходит к периоду моделирования длин ветвей. Состояния дополнительных элементов устройства не изменяются, так как в К-м разряде регистра 17 стоит нуль. После окончания моделирования всех остальных ветвей, входящих в К-й узел, эа исключением последней происходит то же самое, что описано для ветви Ы .

10 чинается период формирования топологии. Поскольку длины ветвей sd u sf одинаковы, любой из номеров и и 1 может занимать второе место в формируемой очереди, а именно тот, который будет просчитан раньше. Это определяется суммарным числом импульсов серии б, поступивших на задатчики с момента начала решения данной задачи, да данного периода формирования топологии..Например, это суммарное число импульсов (И N + Z) таково, что в данный период формирования топологии первый появляется сигнал на .выходе задатчика 8 адреса конечного узла модели ветви sf.

Аналогично описанному для ветви

sb номер 4 записан в ячейку, но,ер которой определяется содержимым счетчика 16, т.е. в первую ячейку. После окончания импульса серии 6 к содержимому счетчика 16 прибавляется единица, в результате формируется адрес следующей ячейки второй). Сброс в нуль триггера 9 модели ветви sf.íå вызывает начала периода моделирования длин ветвей, так как триггер 9 с модели ветви 54 па-прежнему в единичном состоянии. После появления единичного сигнала на выходе задатчика 8 модели ветви sd номер d записывается во вторую ячейку памяти после чего в счетчике 16 формируется адрес следующей ячейки.

Далее процесс продолжается аналогично, происходит запись в ячейки памяти номеров а, С, как описано выше. Таким образом, в результате работы устройства в ячейках блока памяти с номерами нуль, один, четыре. разместится такая последовательность номеров работ (b,4 4, at

С), которая и является искомой очередью.

После завершения моделирования ветви sc начинается моделирование ветви СК,по окончании которого при поступлении (M N +К)-го импульса серии 6 на выходе элемента И 20 появляется единичный сигнал, который через элемент ИЛИ 25 поступает в блок 3 управления. По этому сигналу завершения К-га узла посл.дний блок останавливает рабату устройства.

Предлагаемое устройство позволяет организовать очередь па различным дисциплинам выбора работ. Например, 11 1 при дисциплине выбора заявки с минимальным временем дообслуживания в ,качестве длины ветви используется оставшаяся невыполненная часть

i каждой работы, при выборе заявки с максимальным приоритетом обслужи- . вания в качестве длины ветви выступает численное значение приоритета и т.д. Устройство позволяет также реализовать дисциплины типа "первый пришел — первый обслужен" и

128272 12

"последний пришел — первый обслужен".

В этих двух случаях в качестве длины ветви фигурирует ее номер в порядке поступления в систему. Тогда, например, при дисциплине "последний пришел — первый обслужен" работа, имеющая наибольший порядковый номер в последовательности поступления в систему, будет поставлена первой в .очередь на вьг. полнение .

1128272

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

Редактор Л.Гратипло Текред З,Палий

Корректор А. Тяско

Подписное

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

Заказ 9064/38 Тираж 698

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

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