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

4СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК 09) (11) А 06 Г 15 ИСАНИЕ ИЗОБРЕ ТОРСКОМУ СВИДЕТЕЛЬСТВУ(22)46 вый выход первого триггера подключен ко второму входу четвертого элемента И, выход второго элемента НЕсоединен со вторым входом третьегоэлемента И, выход которого подключенко второму входу второго триггера,второй выход первого триггера соединен с вторым входом первого элемента И блока моделей ветвей по числуработ, в блоке формирования топологии выход первого элемента ИЛИподключен ко входу элемента НЕ и кпервому входу первого элемента И,выход которого соединен с первымвходом второго элемента ИЛИ, выходкоторого подключен к входам первогои второго задатчиков адресов блокамоделей ветвей по числу работ, выходэлемента НЕ блока формирования топологии соединен с первым входом второго элемента И блока Формированиятопологии, выход которого подключенко второму входу формирователя вре- Яменных интервалов блока моделей ветвей по числу работ, первый выход генератора импульсов соединен с вторымвходом второго элемента И блока Формирования топологии, второй выходгенератора импульсов подключен к второму входу первого элемента И блокаФормирования топологии и к первомувходу блока управления, первый выходкоторого соединен со вторым входомвторого элемента ИЛИ блока формирования топологии, выход третьего .элемента И которого подключен к первому,входу третьего элемента ИЛИ, выходкоторого соединен со входом второгоэлемента НЕ блока моделей ветвей почислу работ, с третьим входоМ первогоэлемента И блока моделей ветвей почислу работ и со вторым входом блокауправления, второй выход которогоподключен к первому входу четвертогоэлемента И блока формирования топологии, выход которого соединен с пер,вым входом четвертого элемента ИЛИ е ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ 3321300/18-2424.07.81(71) Институт проблем моделирования в энергетике АН Украинской ССР и Опытное конструкторско-технологическое бюро с опытным производством Института металлофизики АН Украинской ССР(56) 1. Авторс Р Р 422002, кл.2. Авторско кое свидетельство ССС 6 06 С 7/48, 1972.е свидетельство СССР Р 608169, кл. С 06 6 7/122, 1975 (прототип).(54)(57) УСТРОИСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВОГО ГРАФИКА, содержащее блок управления, генератор импульсов, блок Формирования топологии, включающий пять элементов ИЛИ, четыре элемента И и элемент НЕ, и блок моделей ветвей по числу работ, каждая из которых включает задатчики адресов, первый, второй и тр тий триггеры, элементы И, формирователь временных интервалов, элементы НЕ и элемент ИЛИ, причем выход первого задатчика адресов подключен к первому входу первого элемента И, выход которого соединен с первым входом формирователя временных интервалов, выход которого подключен ко входу первого триггера и к первому входу второго триггера, выход которого соединен с первым входом второго элемента И, выход второго з 4 датчика адресов подключен к первому входу третьего элемента И, ко второму входу второго элемента И, к первым входам первого элемента НЕ и четвертого элемента И, выходы которых соединены соответственно с входами элемента ИЛИ, перТЕНИЯ1012267 блока формирования топологии, выхоДкоторого подключен к третьему входувторого элемента И блока моделей ветвей по числу работ и к третьему входу блока управления, третий выходкоторого соединен со вторым входоытретьего элемента ИЛИ блока Формирования топологии, четвертый выходблока управления подключен ко второму входу четвертого элемента ИЛИ бло.ка формирования топологии, выходпятого элемента ИЛИ блока формирования топологии соединен со вторымвходом четвертого элемента И блокаФормирования топологии, выход третьего триггера блока моделей ветвей почислу работ подключен к соответствующему входу первого элемента ИЛИ бло-.ка формирования топологии, выходэлемента ИЛИ блока моделей ветвей почислу работ соединен с соответствую.щим входом третьего элемента И блокаформирования топологии, выход первогозадатчика адресов соединен с первым входом пятого элемента И блокамоделей ветвей по числу работ, выходкоторого подключен к соответствующему входу пятого элемента ИЛИ блокаФормирования топологии, о т л и ч аю щ е е с я тем, что, с целью повышения коэффициента использованияоборудования модели ветви, в каждую Изобретение относится к электронному моделированию, в частности ономожет быть использовано при построении специализированных вычислительных машин.Известно устройство для моделирования сетевого графика, содержащееблок управления, генератор импульсов, блок Формирования топологии иблок моделей ветвей по числу работ,каждая из которых содержит задатчики адресов, элементы И, инвертор,элемент ИЛИ, формирователь временных интервалов, триггеры, блок формирования топологии содержит элементы И, элементы ИЛИ, инвертор.1Недостатком устройства являетсяневозможность определения конфигурации длиннейшего пути,Наиболее близким по технической сущности к изобретению является устройство для моделирования сетевого графика, содержащее блок моделей ветвей, блок формирования топологии, блок управления, генератор импуль- . сов, каждая модель ветви содержит задатчики адресой, формирователь модель ветви введены дополнительныеэлементы ИЛИ, И и НЕ, выход третьегоэлемента НЕ подключен к первому входу дополнительного элемента И блокамоделей ветвей по числу работ, выходкоторого соединен с первым входомтретьего триггера блока моделей ветвей по числу работ, выход которогоподключен ко второму входу пятогоэлемента И блока моделей ветвей почислу работ, выход второго элемента И блока моделей ветвей по числуработ соединен с первым входом дополнительного элемента ИЛИ блока моделей ветвей по числу работ, второйвход которого подключен к выходуФормирователя временных интерваловблока моделей ветвей по числу работ.,выход дополнительного элемента ИЛИблока моделей ветвей по числу работсоединен со вторым входом третьеготриггера блока моделей ветвей по числу работ, выход второго задатчика адресов блока моделей ветвей по числу работ подключен ко второму входу дополнительного элемента И блокамоделей ветвей по числу работ, выходчетвертого элемента ИЛИ блокаФормирования топологии соединенс . входом дополнительного элемента НЕ блока моделей ветвей почислу работ. временных интервалов, триггерьР, элементы И; элементы НЕ, элемент ЙЛИ, блок формирования топологии содержит элементы И, элементы ИЛИ, элемент НЕ 2.,Недостатком данного устройства является низкий коэффициент использования оборудования модели ветви, 1 О обусловленный тем, что для индикации состояния принадлежности ветвисетевого графика длиннейшему путикаждая модель ветви устройствасодержит отдельный триггер, которыйблокируется в течение процесса определения величины длиннейшего путии дерева максимальных путей сетевого графика. Между тем, непосредственно в процессе формирования конфигурации длиннейшего пути сетевого 20 графика триггер прерывания моделиветви не выполняет каких-либо Функций и его состояние не влияет наход этого проЦесса, что создаетвозможноСть использования данного 25,триггера в качестве элемента индикации Принадлежности ветви длиннейшему пути.Цель изобретения - повышение коэффициента использования оборудования модели ветви.Укаэанная цель достигается тем, что в устройство для моделирования сетевого графика, содержащее блок управления, генератор импульсов, блок формирования топологии, включающий пять элементов ИЛИ, четыре элемента И и элемент НЕ, и блок моделей ветвей по числу работ, каждая йз которых включает задатчики адресов, первый, второй.и третий триггеры, элементы И, Формирователь временных интервалов, элементы НЕи элемент ИЛИ, причем выход первогозадатчика адресов подключен к первбму входу первого элемента И, выходкоторого соединен с первым входом формирователявременных интервалов, выход которого подключен ко входу первого триггера и к первому входу второго триггера, выход которого соединен с первым входом второго элемента И, выход второго задатчика адресов подключен к первому входу третьего элемента И, ко второму входу второго элемента И, к первым входам первого элемента НЕ и четвертого элемента И, выходы которых соединены соответственно с входами элемента ИЛИ, первый выход первого триггера подключен ко второму входу четвертого элемента И, выход второго элемента НЕ соединен со вторым входом третьего элемента И,выход которого подключен ко второму входу второго триггера, второй вы-ход первого туггера соединен с вторым входом первого элемента И блока моделей ветвей по числу работ,в блоке Формирования топологии выход первого элемента ИЛИ подключен ко входу элемента НЕ и к первому входу первого элемента И, выход которого соединен е первйм входом второго элемента ИЛИ, выход которого подключен к входам первого и второго задатчиков адресов блока моделей ветвей по числу рабоФ, выход элемента НЕ блока формирования топологии соединен с первым входом второго элемента И блока формирования топологии, выход которого подключен ко второму,входу Формирователя временных интервалов блока моделей .ветвей по числу работ, первый выход генератора импульсов соединен с вторым входом второгоэлемента И блока .Формирования топологии, второй выход генератора импульсов подключен к второму входу первого элемента И блока формирования топологии и к первому входу блока управления, первый выход которого соединен со вторым входом втдрого элемента ИЛИ блока формированиятопологии, выход третьего элемента И которого подключен,к первомувходу третьего элемента ИЛИ, выходкоторого соединен со входом второго элемента НЕ блока моделей ветвей по числу работ, с третьим вхо дом первого элемента И блока моделей ветвей по числу работ и со вторым входом блока управления, второйвыход которого подключен к первомувходу четвертого элемента И блока О Формирования топологии, выход котоого соединен с первым входом четвертого элемента ИЛИ блока формирования топологии, выход которогоподключен к третьему входу второгоэлемента И блока моделей ветвей почислу работ.и к третьему входублока управления, третий выход которого соединен со вторым входомтретьего элемента ИЛИ блока формирования топологии, четвертый выходблока управления подключен ко второму входу четвертого элемента ИЛИблока формирования топологии, выходпятого элемента ИЛИ блока формирования топологии соединен со .вторым входом четвертого элемента Иблока Формирования топологии, выходатретьего триггера блока моделей ветвей по числу работ подключен к соответствующему входу первого эле- ЗО мента .ИЛИ блока формирования топологии, выход элемента ИЛИ блока мо-.делей ветвей по числу работ соединен с соответствующим входом третьегоэлемента И блока формирования 35 топологии, выход первого задатчикаадресов соединен с первым входомпятого элемента И блока моделейветвей по числу работ, выход которого подключен к соответствующему вхо О ду пятого элемента ИЛИ блока Формирования топологии, в каждую модельветви введены дополнительные элементы ИЛ, И и НЕ, выход третьегоэлемента ЙЕ подключен к первому вхо ду дополнительного элемента И блокамоделей ветвей по числу работ, выход которого соединен с первымвходом третьего триггераблока мо-:делей ветвей по числу работ, выходкоторого подключен ко второму входу пятого элемента И блока моделейветвей по числу работ, выход второго элемента И блока моделей ветвейпо числу работ соединен с первымвходом дополнительного элемента ИЛИ 55 блока моделей ветвей по числу работ, второй вход которого подключен к выходу формирователя временных интервалов блока моделей ветвей почислу работ, выхор дополни О тельного элемента ИЛИ блока моделейветвей по числу работ соединен совторым входом третьего триггераблока мо,елей ветвей по числу работ,выход второго задатчика адресов 65 блока моделей ветвей по числу работподключен ко второму входу дополнительного элемента И блока моделей ветвей по числу работ, выход четвер- того элемента ИЛИ блока форми 1 ования топологии соединен с входом дополнительного элемента НЕ блока мо" 5 делей ветвей по числу работ.На фиг. 1 приведена функциональ" ная схема предложенного устройства; на фиг. 2 - одна из схем выполненияблока управления.Устройство для моделирования сетевого графика состоит из блока 1 моделей ветвей, блока 2 формирования топологии,. блока 3 управления игенератора 4 импульсов. 15Каждая модель 1 ветви содержит задатчики 5 и б адресов, формирователь 7 временных интервалов, триггеры 8 - 10, .элементы И 11-16, элементы НЕ 17-19, элементы ИЛИ 20-21.В качестве задатчиков 5 и б используются счетчики импульсов.Блок 2 формирования топологии содержит элементы И 22-25, элементы ИЛИ26-30, элемент НЕ 31.Блок 2, соединенный с блоком 1 мо- делей ветвей, обеспечивает взаимодействие моделей ветвей сетевого гра- фика по временному принципу на основании адресов начального и конечного событий для каждой ветви,. занесенных в задатчики 5 и б, Блок 3 управления состоит из задатчиков 32 и 33 начального и конечного узлов сетевого графика соответственно, выполненныханалогично задатчикам 5 и б, 3 триггеров 34-36, элементов И 37-41 и элементов ИЛИ 42 и 43, входы и выходы блока управления 44-51.Блок 3 управления предназначен для осуществления первоначального 40 запуска всего устройства и организации взаимосвязанной работы блоков устройства.Устройство работает следующим образом. 45Предварительно в задатчики 5 и б заносятся соответственно адреса начального и конечного узлов ветвей сетевого графика. В формирователи 7 временных интервалов заносятся длительности ветвей, а триггеры 8, 9 и 10 устанавливаются в состояние "О" соответствующие цепи не показаны).В блоке 3 управления предварительно в задатчики 32 и 33 заносятся соответственно адреса начального и конечного узлов сетевого графика, триггеры 34-36 устанавливаются в состояния "0", Для запуска всех моделей 1 ветвей на вход 51 блока 60 3 подается сигнал 1 Пуск", который устанавливает в состояния "1" триггеры 34 и 35. Последний через элемент 42 ИЛИ выдает разрешение на вход элемента И 37 и импульсы с ге- у нератора 4вход 50) через элемент И 37 начинают поступать на входы задатчиков 32 и 33. Импульсы также с выхода элемента И 37 проходят через элемент И,38, на втором входе которого присутствует разрешение, с единичного выхода триггера 34, далее через элемент ИЛИ 43 на выход 44 блока 3 управления и поступают на вход элемента ИЛИ. 27 блока 2 формирования .топологии. Импульсы с выхода элемента ИЛИ 27 поступают на входы задатчиков 5 и б всех моделей 1 ветвей до тех пор, пока на выходах задатчиков 5 адресов, в которых записан адрес начального уэла сете- ного графика, не появится сигнал переполнения. В этот же момент времени. на выходе задатчика 32 начальногоузла сетевого графика в блоке 3 такжепоявляется. сигнал переполнения, который через выход 45 блока 3 поступает йа вход элемента ИЛИ 28 блока 2. Кро-ме того, сигнал с. выхода задатчика 32 поступает на нулевой вход триггера 34 и устанавливает. его в состояние ."0" в результате этого со второго входа элемента И 38 снимается разрешение, а поэтому прекращается подача импульсов с блока 3 (выход 44) на. вход элемента 27 ИЛИ блока 2.Сигнал с выхода элемента ИЛИ 28блока 2 поступает на вход элемента И 12 моделей 1 и на вход блока 3 (вход48 у. Разрешающий сигнал появляетсяна выходах тех элементов И 12, наостальных входах которых присутствует разрешение с нулевого выхода триггера 9 и задатчика 5. В результате формирователи 7 этих моделей подготовлены сигналами с выходов элементов И 12 а отсчету импульсов, поступающих из блока 2. Отсчитав число импульсов, пропорциональное длительности данной ветви, формирователь 7 выдает сигнал, который устанавливает в состояние "1" триггеры 8-10, Сигйал с единичного выхода триггера 8 поступает на вход элемента ИЛИ 26 блока 2 и через элемент НЕ 31 запрещает прохождение импульсов через элементы И 22 и ИЛИ 27 на входы задатчиков 5 и б всех моделей 1.Сигнал с выхода задатчика б, в котором записан адрес конечного узла ветви, устанавливает в состояние "0" триггер 8 (через элемент И 11, на втором входе которого есть разрешение от элемента НЕ 19), а также поступает на входы элементов И 13-15 и НЕ 18.Если ветвь, в которой появляется импульс на выходе задатчика б, закончила формирование временного интервала, то сигнал с выхода триггера 9 пройдет через элементы И 13 и ИЛИ 20 к одному из входов .элемента И 23 блока 2. Остальные входы это-.го элемента подключены к аналогичным выходам других моделей 1 ветвей.Если временной интервал в данной ветви еще не сформирован, то триггер 9 находится в состоянии "О" .5 и на входе элемента И 13 присутствует запрет с его единичного, выхода, В этом случае сигнал с выхода задатчика б непройдет через эле мент И 13 и на выходе элемента ИЛИ Ю 20 в данный момент появится запрещающий сигнал, который поступит в .блок 2 на соответствующий вход элемента И 23.В случаях, когда импульсы на . 15 .выходе задатчика 6 адресов отсутствуют, на входе элемента ИЛИ 20 присутствует разрешающий сигнал с выхода элемента, НЕ 18. Таким обра- . зом, запрет на входах элемента И 23 только от тех моделей ветвей, которые входят в рассматриваемый узел но не сформировали свою длитель. ность. В этом случае запрещающий сигнал проходит иа выход элемента И 23 и через элементИЛИ 28 на входы всех моделей 1. Этот сигнал запрещает подготовку соответствующих формирователей 7 к отсчетуимпульсов с генератора 4. На выходе элемента НЕ 17 возникает при этом разрешающий сигнал, который поступает иа Второй вход элемента И 14, и так как на первом еговходе присутствует выходной сигнал задатчика б, триггер 10 устанавливается в состояние ф 1 ф.Если все ветви, входящие в рассматриваемый узел, сформировали временной интервал, то на выходе элемента И 23. блока 2 появляется 40 разрешающий сигнал, который поступает. Через элемент ИЛИ 28 на входы моделей ветвей. Этот сигнал.запрещает подготовку соответствующих Формирователей 7 к отсчету импуль. сов с генератора 4. На выходе элемента НЕ 17 возникает при этом раз-. решающий сигнал, который поступает на второй вход элемента И 14, и, так как на первом его входе присутствует выходной сигнал задатчика б, триггер 10 устанавливается,в состояние ф 1 ф.Если все ветви, входящие в рассматриваемый узел,.сформировали временной интервал, то на выходе Элемента. И 23 блока 2 появляеМся разрешающий:сигнал, который посту паетчерез элемент ИЛИ 28 на входы Моделей ветвей. Разрешающий сиг нал запрещаетчерез элемент НЕ 17 60 установку триггера .10, в состояние фОф и также проходит на выход эле" мента И 12 тех моделей, которые выходят из рассматриваемого узла, т.е. тех ветвей, где в данный мо-, Я мент времени есть сигнал на выходе задатчика 5.Импульсы с генератора 4 поступа-. ют на входы задатчиков 5 и .б адресов до тех пор, пока хотя бы на од- ном из входов блока 2 Формирования топологии присутствует сигнал с выхода триггера 8 какой-либо модели 1 ветви. После того, как все триггеры 8 установлены в состояние ,:"0" выходными сигналами соответст-вующих задатчиков адресов б, блок 2 формирования топологии запрещает прохождение импульсов этой серии на входы задатчиков адресов и разрешает поступление импульсов на входы формирователей временных интерваловКогда сформирован конечный узел сетевого графика, все.триггеры 8 . моделей 1 устанавливаются в состояние "0". После этого сигнал с выхода элемента ИЛИ 28 блока 2 поступает в блок 3 управления на вход элемента И 41, и, так как сформирован конечный узел сетевого графика, импульс переполнения с выхода задат-чика 33 через элемент И 41 устанавливает в,состояние фОф триггер 35.Суммарное количество импульсов, поступившее на входы блока формирования топологии с начала счета,: равно величине длиннейшего пути, а состояния "1" триггеров 10,укажут, какие ветви принадлежат дереву максимальных путей.для определения конФигурации длиннейших путей между начальным и . конечным узлами сетевого графика в блоке 3 предварительно в задатчики 32 и 33 заносятся соответственно адреса начального и ко" нечного узлов сетевого графика, триггеры 34-36 устанавливаются в сос- . тояние "О". На вход 52 блока 3 пОдается сигнал фПуск индикации", который устанавливает в состояние ".1 ф триггер 36. Последнее состояние триггера Зб выдает разрешение на выход 49 блока 3, соединенного со входом элемента И 25, а также сигнал с еднничного выхода триггера 36 проходит через элемент ИЛИ 42 и разрешает прохождение импульсов с выхода,генератора 4 через .элемент И 37 на входы задатчиков 32 и 33. Кройе того, импульсы с.выхода элемента И 37 проходят через элемент И 39, на втором входе которого присутствует разрешение с выхода триггера 36, далее через элемент ИЛИ 43 на выход блока 3выход 443, где посту" пают на вход элемента ИЛИ 27.Импульсы с выхода элемента ИЛИ 27 ,поступают на входы задатчиков 5 и 6 до тех пор, пока на выходах задатчиков 6, в которых записан адрес ко ,нечного узла сетевого графика, непоявится сигнал переполнения, В тотже момент времени на выходе задатчика 33 появляется сигнал переполнения, который поступает на выход блока 3 ( выход 47) и далее на элемент ИЛИ 29 блока 2,о,Сигнал с выхода элемента ИЛИ 29 поступит на первый вход элемента И 15, на втором входе которого в этот момент будет присутствовать сигнал с выхода задатчика 6 адресов конечного узла. Если на третьем входе этого элемента есть разрешение с выхода триггера 10, т,е, если.ветвь сформировала свою длительность последней в конечном узле сетевого графика, то .выходной сигнал элемен-. та И 15 установит через элемент ИЛИ 21 в состояние "1" триггер 8. При этом сигнал с выхода элемента НЕ 19 запретит прохождение сигнала с выхода задатчиков 6 через элемент И 11 на нулевой вход триггера 8 и тем са мым исключит неопределенность состояния этого триггера. Единичный выход триггера 8 разрешает прохождение импульсов с выхода задатчика 5 через элемент И 16 на вход элемента ИЛИ 30 блока 2. Остальные входы этого элемента подключены к аналогичным выходам остальных моделей ветвейСигнал с выхода элемента ИЛИ 30 поступает на второй вход элемента И 25 и через элемент ИЛИ 29 на входы элементов И15, При этом устанавливаются в состояние "1" триггера 8 тех моделей ветвей, которые последними формируютдлительность в начальном узле рас" 5 смотренной ветви.Подобный процесс продолжается дотех пор, пока на входах блока 2 формирования топологии не появляетсясигнал с выхода задатчиков 5, соот ветствующих начальному узлу сетевого графика. Это говорит об окончании процесса выделения длиннейшего пути.,При этом выработанный сигнал свыхода элемента 29 ИЛИ поступает вблок 3 вход 46) на вход элемента И40 и, так как сформирован начальный узел сетевого графика, он проходит через элемент И 40 и устанав ливает триггер 36 в состояние "0"Блок 3 управления при этом прекрацает подачу импульсов на элемент ИЛИ27 и подает запрет на элемент И 25.Состояния "1" триггеров 8 укажутна принадлежность ветвей длиннейшему пути сетевого графика.Введение в модели ветвей новыхэлементов и новых связей позволяетреализовать функции моделированиясетевого графика с использованиемменьшего числа триггеров в моДеливетви.1012267 Составитель . И. ДубининаРедактор М.Келемеы Техредй, Гергель КоррекИльинсное илнал ППП "Патент", г. Ужгород, ул. Проектная Заказ 2767/61 . Ти вНИИПИ Государ по делам изо 113035, Москва, ж-35, Рауш П омитета ССС открыти кая наб., д