Устройство для моделирования сетевого графика Советский патент 1978 года по МПК G06G7/122 

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

1

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

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

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

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

подключен к .одному входу формирователя временных интервалов, другой вход которого соединен с выходом первого элемента К блока формирования топологии, выход формирователя временных интервалов подключен к первым входам триггеров., второй вход второго триггера соединен с выходом соответствующего задатчика адресов, выход второго триггера подключен к входу второго элемента ИЛИ блока формирования топологии, первый вход элемента ИЛИ блока моделей ветвей соединен с выходом первого элемента И, второй вход элемента ИЛИ через элемент НЕ подключен к выходу соответствующего задатчика адресов, а выход элемента ИЛИ соединен с входом второго элемента ИЛИ блока формирования топологии, который состоит из элементов И и элементов ИЛИ, причем выход второго элемента ИЛИ непосредственно и через, элемент . НЕ подключен к одним входам элементов И, другие входы которых соединены .с выходами генератора импульсов, выход третьего элемента И подключен к первому входу третьего элемента ИЛИ, второй вход которого соединен с nepsiJM выходом блока управления, второп которого подключен к первому входу первого ИЛИ блока формирования топологии, второй вход которого соеди нён с выходом второго элемента ИЛИ, выходы первого и третьего элементов ИЛИ подключены соответственно к входа задатчиков адресоВ и второго элемента И блока моделей ветвей 21. Недостатком известного устройства также является невозможность определе ния конфигурации длиннейшего пути, т.е. совокупности ветвей, принадлежа щих максимальному среди возможных пу тей между узлами сетевого графика. Кроме того, здесь отсутствует возмож ность определения дерева максимальных путсЛ - совокупности ветвей, принадле жащих длиннейшим путям к каждой из вершин сетевого графика. Цель изобретения - расширение клас са решаемых задач устройства путем обеспечения возможности определения конфигурации длиннейшего пути и максимальных путей сетевого графика. Это ДОС игается тем, что в устройстве для моделироваки сетевого графика в блок формирования топологии и в блок моделей ветвей введены дополнительно триггеры, элемент НЕ и элеМэнты И и ИЛИ, причем в блоке формиро вания ветвей первый вход первого дополнительного элемента И подключен к выходу соответствующего задатчика адресов, а второй вход через дополнительный элемент НЕ соединен с выходом первого элемента ИЛИ блока формирования тоаологии, выход первого дополнительного элемента И подключен к пер ,0 му входу первого дополнительного триг гера, второй вход которого соединен с выходом формирователя временных интервалов, а выход - с одним входом второгодополнительного элемента И, другие входы которого подключены соот ветственно к выходам одного задатчика адресов и первого дополнительного эле мента ИЛИ блока формирования топологж., выход второго дополнительного элемента И блока моделей ветвей через второй дополнительный триггер соедине с одним входом третьего дополнительно го э-лемента И, другой вход которого .соединен с выходном.другого задатчика адресов, а выход - через второй допол нительный элемент ИЛИ блока формирования топологии подключен к ОДЬОГТУ входу дополнительного элемента И бло ка формирования топологии, а другой вход которого соединен с третьим вы. ходом блока управления, четвертый вы ход которого и выход дополнительного элемента И подключен к входам первог дополнительного элемента ИЛИ блока формирования топологии, выход которо го соединен с вторым входом блока управления, третий вход которого под ключен к выходу генератора импульсов На чертеже приведена функциональна:Я схема устройства. Оно состоит из блока 1 моделей ветвей, блока 2 формирования топологии, блока 3 управления и генератора 4 импульсов . Каждая модель ветви 1 содержит элементы задатчики адресов 5, 6, формирователь 7 временных интервалов, триггефы 8-11; элементы И 12-16; элементы НЕ 17, 18; элемент ИЛИ 19. В качестве задатчиков адресов 5 и 6 используются счетчики импульсов. Блок 2 формирования топологии содержит элементы И 20-23; элементы ИЛИ 24-28; элемент НЕ 29. Устройство работает следующим . Предварительно в задатчики адресов 5,, б заносятся соответственно адреса начального и конечного узлов ветвей сетевого графика. В формирователь 7 временных интервалов заносится длительность ветви, а триггеры 8, 9, 10 и11 устанавливаются в нулевое состояние. Для запуска всех моделей ветвей 1, исходящих из начального.узла сетевого графика, блок 3 управления разрешает прохождение импульсов генератора 4 импульсов через элемент ИЛИ 25 блока 2 формирования топологии на входы задатчиков адресов 5 и б всех моделей ветви 1. Импул: сы будут поступать до тех пор, пока на выходах задатчика 5 адресов, р которых записан гщрес начального узла сетевого графика, не появится сигнал. В этот момент времени блок управления прекращает подачу импульсов на входы задатчиков адресов и подает пусковой сигнал. Во всех моделях ветвей, исходящих из начального узла графика, на входах элементов И 12 будут разрешающие сигналы с выхода задатчика 5 адресов и нулевого выхода триггера 9. В результате формирователи 7 временных интервалов этих моделей будут подготовлены сигналами с выходов элементов И 12 к отсчету импульсов, поступающих из блока 2 форг мирования топологии. Отсчитав число импульсов, пропорциональное длительности данной ветви, формирователь 7 временных интервалов выдаст сигнал, который установит в единичное состояние триггеры 8, 9 и 10. С единичного в)ахода триггера 8 сигнал поступает, в блок 2 формирования топологии на один из входов элемента ИЛИ 24, к остальHirOM входам которого подключены одноименные входы остальных моделей ветвей 1. Пройдя через элемент ИЛИ 24, сигнал поступает на вход элемента НЕ 2:9, который вырабатывает запрет на одном из входов элемента И 22, в ре;|ультате чего прекращается поступление импульсов на входы всех моделей ветвей 1. Одновременно сигнал с выхода элемента ИЛИ 2, поступая на вход элемента И 20, разрешает прохождение импульсов со второго входа этого элемента через элемент ИЛИ 25 на входы моделей ветвей 1. Серию импульсов с генератора 4 импульсов начинают считать одновременно эадатчики адресов 5 и 6. Сигнал с выхода эадатчика адресов б, в котором записан адрес конечного узла ветви, устанавливает в нулевое состояние триггер 8, поступает на первые входа элементов И 13, 14 и 15 и на вход элемента НЕ 18. Если ветвь, в которой появится импульс на выходе эадатчика адресов 6, закончила формирование временного интервала, то сигнал с выхода триггера 9 пройдет через элемент И 13 и далее через элемент ИЛИ 19 к одному из входов элемента И 21, Остальные входы этого элемента подключены к аналогичным выходам других моделей ветвей. Если временной.интервал в данной ветви еще не сформирован, то триггер 9 находится в нулевом состоянии, и на входе элемента И 13 присутствует запрет с его единичного выхода. Выход ной сигнал задатчика адресов & в этом случае не пройдет через этот элемент, и иа выходе элемента ИЛИ 19 в этот момент появится запрещающий сигнал, который и поступит на соответствующий вход блока 3 формирования топологии. В тех случаях, когда импульсы на выходе задатчика адресов б отсутствуют, на этом входе присутствует разрешающий сигнал с выхода элемента НЕ 18. Таким образом, запрет на этом вхо де будет только в тех моделях ветвей. которые входят в рассматриваемый узел но не сформировали свою длительность. В этом случае запрещающий сигнал прой дет на выход элемента и 21 и через элемент ИЛИ 26 на полюсы всех моделей ветвей 1. Этот сигнал запретит подготовку соответствующих формирователей 7 временных интервалов к отсчету импульсов с генератора импульсов. На выходе элемента -НЕ 17 возникает при этом разрешающий сигнал, который поступает на второй вход элемента И 14, и так как на первом его входе присутствует выходной сигнал задатчика адресов 6, триггер 10 устанавливается в нулевое состояние.Если все ветви, входящие в рассмат риваемый узел, сформировали временной интервал, то на входкх элемента И 21 блока 2 формирования топологии будут отсутствовать запрещающие сигналы, и на выходе этой схемы появ-ится сигнал, который поступит через элемент ИЛИ 26 на полюсы моделей ветвей. Этот сиг нал пройдет на выход элемента И 12 тех моделей ветвей, которые выходят из рассматриваемого узла, т.е. в тех ветвях, где в данный момент времени есть сигнал на выходе задатчика адресов 5. Кроме того, этот сигнал апретит с помощью элемента НЕ 17 установку в нулевое состояние триггера 10 в моделях ветвей, последними сформировавших временной интервал в этом узле. Импульсы с генератора 4 импульсов поступают на входы задатчиков адресов 5 и б до тех пор, пока хотя бы на одном из входов блока 2 формирования топологии присутствует сигнал с выхода триггера 8 какой-либо модели ветви 1. После того, как все триггеры 8 установлены в нулевое состояние выходными сигналами соответствующих задатчиков адресов, блок формирования 2 топологии запрещает прохождение импульсов этой серии на входы задатчиков адресов и разрешает, поступление импульсов первой серии на входы формирователей временных интервалов. Суммарное количество импульсов, поступившее на входы блока формирования топологии с начала счета, равно величине длиннейшего пути, а единичные состояния триггера 10 укажут, какие ветви принадлежат дереву максимальных путей. Для определения конфигурации длиннейшего пути между начальным и конечным узлами сетевого графика блок 3 управления выдает разрешение на первый вход элемента И 23, а также разрешает прохождение импульсов через элемент ИЛИ 25 на входы задатчиков адресов 5 и б всех моделей ветвей i. В момент переполнения задатчиков адресов б, в которых записан конечный узел сетевого графика, блок 3 управления выдает импульс на вход элемента ИЛИ 27, выходной сигнал с которого поступит на первый вход элемента И 1.51 На второй входе в этот момент времени будет присутствовать сигнал с выхода задатчика адресов конечного узла 6 Если на третьем вхоле этого элемента будет разрешение с выхода триггера 10, т.е. если ветвь сформировала свою длительность последней в конечном узле сетевого графика, то выходной сигнал элемента И 15 установит в единичное состояние триггер 11. Единичный выход триггера 11 разрешит прохождение импульсов о выхода задатчика адресов начального узла 5 через элемент И 16 на вход элемента ИЛИ 28 блока 2 формирования топологии. Остальные входы этого элемента разделения подключены к аналогичным входам остальных моделей ветвей. Сигнал с выхода элемента ИЛИ 28 поступит на второй вход элемента И 23 и через элемент ИЛИ 27 на входы элемента И 15. При этом устанавливаются в единичные состояния триггеры 11 тех моделей ватвей, которые последними сформировали длительность в начальном узле рассмот ренной ветви. Подобный процесс продолжается до тех пор, пока на входах блока Формирования топологии не появится сигнал с выхода залатчиков адресов 5, соответствукнаий начальному узлу сетевого графика. Это говорит об окончании процесса выделения длиннейшего пути. Блок управления при этом прекращает подачу импульсов на элемент ИЛИ 25 и подает запрет на элемент И 23. Единичные состояния триггеров 11 укажут на принадлежность ветвей длиннейшему пути сетевого графика. Использование изобретения позволяет расширить класс решаемых устройством задач/ так как оказывается возмож ным определять конфигурацию длиннейшего пути между узлами сетевого графика и дерево максимальных путей. Формула изобретения Устройство ДЛЯ моделирования сетевого графика/ содержащее блок управления, генератор импульсов, блок формирования топологии и блок моделей ветвей по числу работ, каждая из кото рых состоит из зайатчиков адресов, вы ходы которых подключены соответственно к первым входам первого и второго элементов И, второй вход первого элемента И соединен с. одним выходом первого триггера, другой выход которого подключен к второму входу второго эле мента И, третий вход которого соедине с выходом первого эл1емента ИЛИ блока формирования топологии, выход второго элемента И подключен к одному входу формирователя временных интервалов, другой чход которого соединен с выходом первого элемента И блока формирования топологии, выход формирователя временных интервалов подключен к первым входамтриггеров, второй вход вто рого триггера соединен с выходом соответствующего задатчйка адресов, выход второго триггера подключен к входу второго элемента ИЛИ блока формирования топологии, первый вход элемен та ИЛИ блока моделей ветвей соединен с выходом первого элемента И, второй вход элемента ИЛИ через элемент НЕ подключен к выходу соответствующего задатчйка адресов, а выход элемента ИЛИ соединен с входом второго элемента ИЛИ блока формирования топологии, который состоит из элементов И и элементов ИЛИ, причем выход второго элемента ИЛИ непосредственно и через эле мент НЕ подключен к одним входам элементов И, другие входы которых соединены с выходами генератора импульсов, выход третьего элемента И подключен к первому входу третьего элемента ИЛИ второй вход которого соединен с первым выходом блока управления, второй выход которого подключен к первому входу первого элемента ИЛИ блока формирования топологии второй вход которого соединен с выходом второго элемента ИЛИ, выходы первого и третьего элементов ИЛИ подключены соответственно к входам задатчиков адресов и второго элемента И блока моделей ветвей, о т л и ч а ю щ е ее я тем, что, с целью расширения класса решаемых задач путем обеспечения возможности определения максимальных путей, в него,в блок формирования Топологии и в блок моделей ветвей введены дополнительно триггеры, элемент НЕ и элементы И и ИЛИ, причем в блоке формирования ветвей первый вход первого дополнительного элемента И подключен к выходу соответствующего згшатчика адресов, а второй вход через дополнительный элемент НЕ соединен с выходом первого элемента ИЛИ блока формирования топологии, выход первого дополнительного элемента И подключен к первому входу первого дополнительноготриггера, второй вход которого соединен с выходом формирователя временных интервалов, а выход - с одним входом второго дополнительного элемента И, другие входы которого подключены соответственно к выходам одного задатчйка адресов и первого дополнительного элемента ИЛИ блока формирования топологии, выход второго дополнительного элемента И блока моделей ветвей через второй дополнительный триггер соединен с одним входим третьего дополнительного элемента И, другой вход которого соединен с выходом другого задатчйка адресов, а выход - через второй дополнительный элемент ИЛИ блока формирования топологии подключен к одному входу дополнительного элемента И блока формирования топологии, а другой вход которого соединен с третьим выходом блока управления, четвертый выход которого и выход дополнительного, элемента И подключены к входам первого дополнительного элемента ИЛИ блока формирования топологии, выход которого соединен с вторым входом блока управления, третий вход которого подключен к выходу генератора импульсов . Источники информации, принятые во внимание при экспертизе: 1-. Авторское свидетельство СССР № 305484, кл. G- 06 G- 7/34 -1969. 2. Авторское свидетельство СССР № 422002, кл. G-06 G-7/48, 1972. Ti гг- -ton-O -