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

СО 1 ОЭ СОВЕТСНИХОЭЮПИЮЮИСКИИРЕСПУБЛИН а) С 06 6 7/48 ЗОБРЕТЕНИ ОПИС И АВТОРС МОМУ СВИДЕТЕЛЬСТВУ В. Василь м моделирования ми аинской ССР в и идетельство СССР и 7 48 972 гФФвил ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЭОБРЕТЕНИЙ И ОТНРЫТИЙ(71) Институт проблв энергетике АН Укр(54)(57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ ГРАФИКОВ но авт.св. У 422002, о т л и ч а ю щ е е с я тем, что, с целью расширения класса решаемых эадач, в устройство введен блок памяти, в блок формирования топологии . введены два счетчика, сдвиговый регистр, два дополнительййй элемента И и элемен НЕ, причем первый вход первого дополнительного элемента И соединен с выходом первого элемента,.80,1128272 Д ИЛИ блока формирования топологии, с первым входом сдвигового регистра и с входом первого счетчика, выходы которого подключены к информационным входам блока памяти, адресные входы которого соединены с вьмодавторого счетчика, управляющий ход блока памяти подключен к выходу ервого дополнительного элемента И входу элемента НЕ,:вьмод котороо соединен с входом второго. счетчика и с первым входом второго дополкительного элемента И, выход которого подключен к второму входу сдвигового . регистра, выход которого соединен с вторыми входами первого и второго дополнительных элементов И блока формированйя топологии, третий вход первого дополнительногэ элемента И блока формирования топологии соединен с выходом третьего элемента И блока формирования топологии, выход блока памяти является выходом устройства.272 устройства. 1 1128Изобретение относится к области вычислительной техники, а именно к электронным моделирующим устройств ам.По основному авт.св. В 422002 известно устройство для моделирования сетевых графиков, содержащее блок управления, п .рвый выход которого подключен к первому входу первого элемента ИЛИ блока формирова ния топологии, блок моделей ветвей по числу работ сетевого графика, каждая из которых выполнена в виде задатчиков адресов, выходами соединенных с элементами И, причем вы код первого элемента И соединен с входом формирователя временных интервалов, вход второго элемента И соединен, через инвертор с первым входом элемента ИЛИ, к второму входу которого подключен выход второго элемента И, генератор импульсов, первый и второй выходы которого,подключены соответственно к второму входу первого элемента И каждой модели ветви и к первому входу первого элемента И блока формирования топологии, второй вход которого соединен с входом инвертора блока формирования топологии, каждая модель ветви содержит триггеры, входы которых соединены с формирователем временных интервалов, причем второй вход первого триггера подключен к первому входу второго элемента И, к второму входу которого и к35 третьему входу первого элемента И подключены выходы второго триггера, входы задатчиков адресов каждой модели ветви соединены с выходом первого элемента. ИЛИ блока формирова 40 ния топологии, содержащего второй элемент ИЛИ, подключенный через инвертор к второму элементу И, и последовательно соединенные третий элемент И и третий элемент ИЛИ, вы 45 ход и вход которого подключены соот-. ветственно к входу и второму выходу блока управления, причем первый выход генератора импульсов соединен с вторым входом второго элемента И блока формирования топологии, выход которого подключен к входу Формирователя временных интервалов каждой модели ветви, вход блока управления соединен с четвертым входом первого 55 элемента И каждой модели ветви, выход первого триггера каждой модели ветви. подключен к входу второго элемента ИЛИ блока формирования топологии, выход второго элемента ИЛИ каждой модели ветви соединен с входом третьего элемента И блока формирования топологии Я .Известное устройство позволяет определить величину критического пути сетевого графика, а также величину длиннейшего пути на сети на взвешенном ориентированном графе). Однако оно не позволяет решать задачу упорядочения работ для одной машины по длительности их выполнения. Между тем последняя задача имеет большой удельный вес в классе .- задач теории расписаний.Целью изобретения является расши-. рение класса решаемых задач.Эта цель достигается тем, что в устройство для моделирования сетевых графиков введен блок памяти, в блок формирования топологии введены два счетчика, сдвиговый регистр, два дополнительных элемента И и элемент НЕ, причем первый вход первого дополнительного элемента И соединен с выходом первого элемента ИЛИ блока формирования топологии, с первым входом сдвигового регистра и с входом первого счетчика, выходы которого подключены. к информационным входам блокапамяти, адресные входы которого соединены с выходами второго счетчика,управляющий вход блока памяти подключен к выходу первого дополнительногоэлемента И и входу элемента НЕ, выход которого соединен с входом второго счетчика и с первым входом второго дополнительного элемента И, выход которого подключен к второму входу сдвигового регистра, выход которого соединен с вторыми входами первого и второго дополнительных элементов И блока формирования топологии,третий вход первого дополнительногоэлемента И блока формирования топологии соединен с выходом третьего элемента И блока формирования топологии,выход блока памяти является выходом На фиг.1 приведена функциональная схема предлагаемого устройства; на фиг. 2 - пример работ, требующих упорядочения; на фиг. 3 - сеть специального вида для работ, требующих упорядочения; на фиг. 4 - формирователь временных интервалов, на фиг.5 блок управления.272 Э 1. 28Схема устройства включает блок 1моделей ветвей, блок 2 формированиятопологии, блок 3 управления, генератор 4 импульсов, блок 5 памяти. Некоторые связи, относящиеся к блокууправления и обеспечивающие начало иокончание работы устройства, рассмотрены на фиг.5. Назначение и работаблока управления фиг.5) в предлагаемом устройстве абсолютно. те же, что Ои в известном.Каждая модель ветви содержит формирователь 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 импульсов двух серий -и 0 , сдвинутых один относительно другого.Элементы каждой модели ветви соединены между собой таким образом, что обе печивгют моделирование длины со ответствующей ветви сетевого графика. Эта длина отображается временным интервалом, кратным числу импульсов серии й . Собственно длина ветви модулируется формирователем 6 временных 50 интервалов, остальные злементш модели. ветви и блок 2 формирования топологии обеспечивают выдачу разрешающего сигнала на модель ветви в нужный момент времени. При решении задачи упорядочения работ блоки 1 и 2 предназначены для определеня той работы, которая должна быть поставлена на следующее место В формируемой очереди работ.Предлагаемое устройство может моделировать сетевой график и решать задачу упорядочения набора работ. В последнем случае этот набор работ представляется сетью специального вида, при моделировании которой устройство обеспечивает запись номеров работ в блок памяти в порядке, определяемом длительностью работ. В том и в другом случае элементы и блоки устройства работают одинаково, отличие состоит только в содержании вводимой и, следовательно, накапливаемой в блоке памяти информации, значит данное устройство в том и другом случае моделирует сеть (либо сетевой график, либо сеть специального вида). Блок 5 памяти и дополнительные элементы: счетчики 15. и 16, элементы И 21 и 22, элемент НЕ 27, обеспечивают последовательную запись в ячейках блока памяти упорядоченной последовательности номеРов работ при решении задачи упорядочения. Номера работ, требующих упорядочения, при вводе иформации в устройство отмечаются единицами в соот- ветствующих разрядах регистра 17. При моделировании сетевого графика содержимое регистра 17 равно нулю и запись информации в блок памяти не производится.Во время работы формирователя временных интервалов (фиг.4), по входу 33 на него подается разрешающийсигнал, устанавливающий триггер 29в единицу. В счетчик вначале заносится число М - 1 - 1,где М - емкость счетчика, 1 - длина соответствующей .ветви. Единичный выход каждого разряда счетчика 28 соединен с соответствующим входом элемента И 31. Таким образом, на выходе 34 появляется единичный сигнал, когда в счетчике записано число 0-1, и триггер 29 находится в единичном состоянии т.е. единичный выход триггера также соединен с одним из входов элемента И 31) . Выход элемента Ь 31 соединен с входом установки в нуль счетчика. 28.Рассмотрим работу формирователя на примере моделирования ветви длиной .1, начиная с момента, когда на вход 33 подан разрешающий единичный сигнал.По этому сигналу триггер 29 устанавливается в единицу и импульсы се3 11282рии Д начинают поступать через элемент И 30 на вход счетчика 28 Этиимпульсы увеличивают содержимое счет.чика, которое вначале равно 0 - 1 - 1.После поступлениящапульсов сериисодержимое счетчика становится равным 0-1, т.е. в каждом разрядесчетчика имеется единица (напримерпри 0 б, 0-1 5, т.е. в двоичномкоде это 1111 и т.д.) . Единичный Осигнал поступает на выход элемента И 31,. на выход 34 формирователяа оттуда - на триггер 9 1,фиг.1),устанавливая его в единицу. Этот жесигнал сбрасывает в куль счетчик 28, 5снимая тем самым сигнапы с входовэлемента И 31. Если 1 О, то исходное содержимое счетчика равно 0-1.Тогда после поступпепия на вход 33разрешающего сигнала и поспе установки в единицу триггера 29 появ-.ляется единичный сигнал на выходеэлемента И 31 и на выходе 34 формирователя, т.е. ветвь нулевой длинысмоделирована сразу после поступления разрешающего сигнапа.Рассмотрим решение устройствомзадачи упорядочения на конкретном.примере. Пусть дан набор из пяти работ (фиг,2), калдая из которых характеризуется своим номером (обозначен справа латинской буквой) и длительностью выполнения (указана надиэображением работы). Требуется:упорядочить эти работы по длитель 35ности их выполнения, исходя из принятой дисциплины их выполнения наодной машине. Например, принятая дис. циплина выбора кратчейшей работы,Это означает, что требуется получитьтакую последовательность номеров работ, в которой на первом месте стоит номер самой короткой работы, длительность каждойпоспедующей работыне убывает и последним стоит номерсамой длительной работы.Для решения этой задачи строится .сеть специального вида (фиг.3) следующим образом. Все работы иэ исходного набора представляются ветвями50сети, выходящими из начального узла 5 сети. Длина этой ветви равнадлительности соответствующеи работы, а конечный узел ветви имеет номер (адрес), равный номеру этой работы. Так, ветвь 8.а сети соответ 1ствует работе 4 и т,д. Конечныеузлы ветвей, выходящих иэ началь 72ного узла, соединены с конечным узлом К сети ветвями единичной длины. Длины ветвей сети проставлены над изображениями этих ветвей; Номера узлов 3 , ) , о , р , с с 1., 1 могут быть любыми, но не превышающими адреса 0-1,где (0-) - максимальный адрес узла, который мо-, жет быть записан в задатчик адреса.Информация об этой сети кодиру" ется и вводится так же, как и в известном устройстве, отличие состоит только в том, что в 0 разрядный регистр 17 заносятся единицы в разряды О, Ь , С , д , 1 (схемы начального ввода информации не показаны). Исходные состояния счетчиков 15 и 16 нулевые, еикость каждого счетчика равна 0. Управляющий вход блока памяти является входом разрешения записи, далее он именуется входом записи.Моделирование сети как в предла гаемом устройстве, так и в известном выполняется посредством чередования двух периодов: периода моделирования длин ветвей и периода формирования топологии сети В первый период на модели ветвей через элемент И 1 9 поступают импульсы серииво второй период через элементы И 8 и ИЛИ 23 на модели ветвей поступают импульсы серии б . Введенные дополнительно элементы устройства работают только на этапах формирования топологии сети, поэтому основное внимание уделяется периодам формирования топологии сети.В начале работы блок 3 управления выдает на вход элемента ИЛИ 23 последовательность из 8 иипульеов, которые поступают на входы всех задатчиков 7 и 8 адресов и изменяют их содержимые, Эти же импульсы поступают на вход счетчика 15 и на вход регистра 17, сдвигая его содержимое, Поскольку все триггеры моделей ветвей находятея в нулевом состоянии, на выкоде элемента И 20 блока формирования топологии присутствуют нулевые сигналы в то время, когда на выходе хотя бы одного задатчика 8 присутствует единичный сигнап, а значит и в то время, когда на выходе регистра 17 появляется единичный сигнал. Таким образом, во время поступления 8 импульсов на выходе элемента И 21 бпока формирования топологиивсе время имеется нулевой сигнал, который через ннвертор 2 и элемент . И 22 разрешает запись единиц с выхода регистра 17 в его первый разряд. Таким образом, в рассматриваемый отрезок времени происходит только циклический сдвиг содержимого регистра 17, длина этого цикла равна Н, содержимые задатчиков н счетчика 15 также циклически повторяются с той же 0 длиной Б цикла..После выдачи б импульсов появляются единичные сигналы на выходах задатчиков 7 моделей ветвей за, зЬ, зс,зй, И. Блок 3 управления прекращает подачу импульсов на вход элемента ИЛИ 23 и выдает единичный сигнал на вход элемента ИЛИ 25, по которому через элементы И 11 моделей ветвей за,зЬ, зс, зй, зГ поступают единичные сигналы, подготавливая их формирова-. тели к отсчету импульсов серииСодержимое счетчика 16 равно нулю,счетчика 15 - з, На модели других ветвей единичные сигналы от элементов И 1 не поступают, так как отсутствуют единичные сигналы на выходах задатчиков .7С этого момента начинается моделирование длин ветвей, выходящих из начального узла. В течение всего периода моделирования30 длин ветвей на выходах элементов И 20 и ИЛИ 24 присутствуют нулевыесигналы. Нулевой сигнал на выходеэлемента ИЛИ 24 через ннвертар 26и элемент И 19 разрешает поступление импульсов сериина формирова тели 6 моделей ветвей, выходящих из начального узла сети. Этот нулевой сигнал через элемент И,1 8 запрещает поступление импульсов серии В через 40элемент И 23 на эадатчнки 7 н 8 моделей ветвей.После поступления трех импульсов серии я на выходе формирователя в модин ветви зЬ появляется единич иый сигнал, который устанавливаетв единицу триггеры 9 и 10 этой мо-дели ветви, На выходе элемента ИЛИ 24 .появляется единичный сигнал, по которому через инвертор 26 и элемент 0 И 19 прекращается выдача импульсовсерии А и через элементы И.18 и ИЛИ 23 разрешается выдача имнульсов серии 5Эти импульсы поступают на входы 55всех задатчиков 7 и 8, а также йа1счетчик 15 и сдвиговый вход регист-, ра 17. После тогр, как на выходе задатчика 8 модели ветви зЬ появился единичный сигнал, в счетчике 15 записывается число з , а на выходе ре,гистра 17 присутствует единичный сигнал. Сигнал на выходе эадатчика 8модели ветви бь появляется после поступления на этот задатчик (МН + + Ь) импульсов, где М О, 1, 2, Счетчик 15 после поступления тогоже числа импульсов будет в состоянии Б .Назначение элементов И 21 и И 22, элемента НЕ 27 и регистра 7 состоит в том, чтобы обеспечить однократную запись каждого номера узла изчисла выбранных в ячейки блока памяти. Номера выбранных узлов отмечаются единицами в соответствующих разрядах регистра. Единичный сигнал навыходе элемента И 20 появляется каждый раз при просчете номера свершившегося узла,. так как триггер 10 модели окончившейся ветви все время находится в единичном состоянии. Единичный сигнал с выхода элемента И 2через элемент НЕ 27 и И 22 запрещаетперезапись единицы с выхода регистра 17 на его вход, которая разрешается теми же элементами только для несвершившихся узлов, т.е. при нулевом сигнале с выхода элементаИ 20.Единичный сигнал с выхода задатчика 8 модели ветви зЬ поступает через элемент И 12 на вход и выход элемента ИЛИ 13. Поскольку ветвь зЬ единственная, входящая в узел то на выходах инверторов 14 всехмоделей ветвей кроме зЬ присутствуют единичные сигналы. Такимобразом, на выходе элемента И 20появляется единичный сигнал, На выходе регистра 17 также есть единич" ный сигнал. Таким образом, на всех входах элемента И 21 есть единичные сигналы. Единичный сигнал с выхода элемента И 21 поступает на входзаписи блока 5 памяти и в ячейку с .нулевым адресом записывается содержимое счетчика 15, т.е, число Узел 1 з свершился, номер (адрес) его записан. Единичный сигнал с выхода элемента И 21 через элемент НЕ 27 и элемент.И 22 запрещает злись единицы с выхода регистра 17 на его вход. Таким образом, в 1; -м разряде регистра 17, начиная с этого момента, записан нуль. Нуль навыходе регистра 17 запрещает появление единично40 55После следующего импульса серииустанавливаются в единицу триггеры 9 и 1 О моделей ветвей зд и Ы . На 9 11282го сигнала навыходе элемента И 21,поэтому при появлении следующего(М О+ Ь)-го импульса серии р сигналзаписи не вьдается и повторной записи номера 0 не будет. Одновременнотриггер 9 модели ветви зЬ сбрасывается в нуль, нулевой сигнал на выходеэлемента ИЛИ 24 разрешает поступление следующего импульса сериинамодели ветвей за, зй, зо, зЕ, которые 1 Оеще не окончили свою работу. Разрешающий сигнап поступает также на формирователь 6 модели ветви Ъ 1, таккак на всех входАх элемента И 11 этоймодели ветви есть единичные сигналы.После окончания упомянутого импульса серии 0 с выхода элемента И 21 исчезает единичный сигнал. Это состветствует появлению единичного сигналана выходе элемента НЕ 27, которыйпоступает на вход счетчика 16, увеличивая его содержимое на единицу,Единица прибавляется к содержимомусчетчика 16 всякий раз, когда сигнал на выходе элемента И 21 переходит иэ единичного на нулевой уровень. Таким образом, формируетсяадрес следующей ячейки блока памяти сразу же после записи информации в предьдущую ячейку, Если записи информации по предьдущему импульсу сериине было, то содержимоесчетчика 16 не меняется.После первого в данном периоде импульса серии Д оканчивается ветвьЙ. Поскольку К-й узел не свершился, то при подаче (М Н +К)-го импульса серии б на модели ветвейна выходе элемента И 20 будет нулевой сигнал. так как на выходах)элементов ИЛИ 13 моделей ветвиаК, сК, ЙК, ГК нулевые сигналы).Упомянутый импульс серии Ь сбрасыва"ет в нуль триггер 9 в Ц -й моделиветви и устройство вновь переходитк периоду моделирования длин ветвей. Состояния дополнительных элементов устройства не изменяются,так как в К-м разряде регистра 17стоит нуль. После окончания моделирования всех остальных ветвей, входящих в К-й узел, эа исключениемпоследней происходит то же самое, чтоописано для ветви й .72чинается период формирования топологии. Поскольку длины ветвей Ы и зйодинаковы, любой из номеров й и 1 1 О может занимать второе место в формируемай очереди, а именно тот, который будет просчитан раньше. Это определяется суммарным числом импульсов серии б, поступивших на задатчики с момента начала решения данной задачи, да данного периода формирования топологииНапример, этосуммарное число импульсов (М М + 2)таково, что в данный период формирования топологии первый появляетсясигнал на выходе задатчика 8 адреса конечного узла модели ветви зГ. чика 16, т.е. в первую ячейку. После окончания импульса серии Б к содержимому счетчика 16 прибавляется единица, в результате формируется адрес следующей ячейкивторой). Сброс в нуль триггера 9 модели ветви зй.не вызывает начала периода моделирования длин ветвей, так как триггер 9 с модели ветви 64 па-прежнему в единичном состоянии, После появления единичного сигнала на выходе задатчика 8 модели ветви зй номер й записывается во вторую ячейку памятипосле чего в счетчике 16 формируется адрес следующей ячейки,Далее процесс продолжается аналогична, происходит запись в ячейкипамяти номеров а, С , как описано выше. Таким образом, в результатеработы устрбйства в ячейках блокапамяти с номерами нуль, один,четыре. разместится такая последовательность номеров работ (1,1 , 4 , 4,С), которая и является искомой очередью. После завершения моделирования ветви зс начинается моделирование ветви СК,по окончании которого при поступлении (М Ю +К) "го импульса серии В навыходе элемента И 20 появляется единичный сигнал, который через элемент ИЛИ 25 поступает в блок 3 управления. Па этому сигналу завершения К-га узла послдний блок останавливает рабату устройства.Предлагаемое устроиство позволяет организовать очередь по различным дисциплинам выбора работ. Например,Аналогично описанному для ветвизЪ номер 1 записан в ячейку, номеркоторой определяется содержимым счет11при дисциплине выбора заявки с минимальным временем дообслуживания в ,качестве длины ветви используется оставшаяся невыполненная часть каждой работы, при выборе заявки с максимальным приоритетом обслужи- . вания в качестве длины ветви выступает численное значение приоритета и т.д. Устройство позволяет также реализовать дисциплины типа "первый пришел - первый обслужен" и 128272 12"последний пришел - первый обслужен".В этих двух случаях в качестве длины ветви фигурирует ее номер в порядке поступления в систему. Тогда, например, при дисциплине "последний пришел - первый обслужен" работа, имеющая наибольший порядковый номер в последовательности поступления в систему , будет постав- О лена первой в .очередь на вьгполнение .яско 113035, Иос раж 698венного комитета СССретений и открытийЖ, Раушская наб.,дписно Закаэ 9064/38 ТВНИИПИ Государспо делам изо 4/ нлиал ППП "Патент", г,ужгород, ул .Проектная Составитель И,ДубининаРедактор Л,Гратипло Текред З.Палий Коррект