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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

CoIo3 Советски и

Социалистических

Ввеспублик

0И 608169

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное.к авт. свид-ву (22} Заявлено &804.75 (2в) 2124288/24 с присоединением заявки Ph (51) М. Кл.

G Oe C 7/122

Гащврвтввввиб ввввтвт

Ввватв Мввввтров O(Gp вв 1вввв ввоврвтвввв в втврытвв (23) Приоритет (5З) УДК 681.333 (088. 8) (43) Опубликовано 250578. Бюллетень 36 19 (45) Дата опубликования описания050578 (72) Авторы изобретения

A. Г. Додонов, В. В. Хаджинов и И. В. Федотов

Pl) Заявитель

Институт электродинамики АН УССР (54) УСТРОИСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВОГО ГРАФИКА

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

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

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

ИЛИ, причем выход второго элемента

ИЛИ непосредственно и через, элемент

НЕ подключен к одним входам элементов

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

Во1о элемента ИЛИ блока формирования топологии, второй вход которого соединен с выходом второго элемента ИЛИ, выходы первого и третьего элементов

ИЛИ подключены соответственно к входам задатчиков адресой и второго элемента И блока моделей ветвей 521.

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

Кроме того, здесь отсутствует возможность определения дерева максимальных путей — совокупности ветвей, принадлежащих длиннейшим путям к каждой из вершин сетевого графика.

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

Это дос нгается тем, что в устройстве для моделировани- сетевого графика в блок формирования топологии и в блок модеЛей ветвей введены дополнительно триггеры, элемент НЕ и эле.и нты И и ИЛИ, причем в блоке формиро-, вания ветвей первый вход первого дополнительного элемента И подключен к выходу соответствующего эадатчика адресов, а второй вход через дополни тельный элемент HE оединен с выходом первого элемента ИЛИ блока формирова35 ния топологии, выход первого дополнительного элемента И подключен к пер,ому входу первого дополнительного триггера, второй вход которого соединен с выходом формирователя временных ин- 40 тервалов, а выход — с одним входом второго дополнительного элемента И, другие входы которого подключены соответственно к выходам одного задатчика адресов и первого дополнительного эле- 41 мента ИЛИ блока формирования тополо. гии, выход второго дополнительного элемента И блошка моделей ветвей через второй дополнительный триггер соединен с одним входом третьего дополнительно- 50 го элемента И, другой вход которого соединен с выходом.другого задатчика адресов, а выход — через второй дополнительный элемент ИЛИ блока формирования топологии подключен к од о: у входу дополнительного элемента И блока формироэания топологии, а другой вход которого соединен с третьим вы. ходом блока управления, четвертый выход кото ого и выход дополнительного элемента И подключен к входам первого дополнительного элемента ИЛИ блока формирования топологии, выход которого соединен с вторым входом блока управления, третий вход которого подключен к выходу генератора импульсов. 65

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

Оно состоит из блока 1 моделей ветвей, блока 2 формирования топологии, блока 3 управления и генератора 4 импульсов.

Каждая модель ветви 1 содержит элементы задатчики адресов 5, 6, формирователь 7 временных интервалов, триггеры 8-11; элементы И 12-16у элементы HE 17, 18; элемент ИЛИ 19.

В качестве задатчиков адресов 5 и

6 используются счетчики импульсов °

Блок 2 формирования топологии содержит элементы И 20-231 элементы ИЛИ

24-78; элемент НЕ 29.

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

Предварительно в задатчики адре"ов

5„ 6 заносятся соответственно адреса начального и конечного узлов ветвей сетевого графика.

В формирователь 7 временных интервалов заносится длительность ветви, а триггеры 8, 9, 10 и 11 устанавливаются в нулевое состояние.

Для запуска всех моделей ветвей 1, исходящих из начального. узла сетевого графика, блок 3 управления разрешает прохождение импульсов генератора 4 импульсов через элемент ИЛИ 25 блока

2 формирования топологии на входы задатчиков адресов 5 и 6 всех моделей ветви 1. Импул. сы будут поступать до тех пор, пока на.выходах задатчика 5 адресов, Р которых записан адрес начального узла сетевого графика, не появится сигнал. В этот момент времени блок управления прекращает подачу импульсов на входы задатчиков адресов и подает пусковой сигнал. Во всех моделях ветвей, исходящих из начального узла графика, на входах элементов И

12 будут разрешающие сигналы с выхода задатчика 5 адресов и нулевого выхода триггера 9. В результате Формирователи 7 временных интервалов этих моделей будут подготовлены сигналами с выходов элементов И 12 к отсчету импульсов, поступающих из блока 2 фор-. мирования топологии. Отсчитав число. импульсов, пропорциональное длительности данной ветви, Формирователь 7 временных интервалов выдаст сигнал, который установит в единичное состояние триггеры 8, 9 и 10. С единичного выхода триггера 8 сигнал поступает.в блок 2 формирования топологии на один из входов элемента ИЛИ 24, к остальным входам которого подключены одноименные входы остальных моделей ветвей 1. Пройдя через элемент ИЛИ 24, сигнал поступает на вход элемента НЕ

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

608169 ветвей 1. Одновременно сигнал с выхода элемента ИЛИ 24, поступая на вход элемента И 20, разрешает прохождение импульсов со второго входа этого элемента через элемент ИЛИ 25 на входы моделей ветвей 1.

Серию импульсов с генератора 4 импульсов начинают считать одновременно .задатчики адресов 5 и 6 ° Сигнал с выхода задатчика адресов 6, в котором записан адрес конечного узла ветви, устайавливает в нулевое состояние триггер 8, поступает на первые входы элементов И 13, 14 и 15 и на вход элемента HE 18.

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

9 пройдет через элемент И 13 и далее через элемент ИЛИ 19 к одному из входов элемента И 21 ° Остальные входы этого элемента подключены к аналогичным выходам других моделей ветвей.

Если временной интервал s данной ветви еще не сформирован, то триггер 25

9 находится в нулевом состоянии, и на входе элемента И 13 присутствует запрет с его единичного выхода. Выходной сигнал задатчика адресов 6 в этом случае не пройдет через этот элемент, З0 и на выходе элемента ИЛИ 19 в этот момент появится запрещающий сигнал, который и поступит на соответствующий вход блока 3 формирования топологии.

В тех случаях, когда импульсы на выходе эадатчика адресов 6 отсутствуют, на этом входе присутствует разрешающий сигнал с выхода элемента HE

18. Таким образом, запрет на этом входе будет только в тех моделях ветвей, 40 которые входят в рассматриваемый узел, но не сформировали свою длительность.

В этом случае запрещающий сигнал пройдет на выход элемента И 21 и через элемент ИЛИ 26 на полюсы всех моделей ветвей 1. Этот сигнал запретит подго45 товку соответствующих формирователей

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

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

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

26 на полюсы моделей ветвей. Этот сигнал пройдет на выход элемента И 12 тех моделей ветвей, которые выходят

65 иэ рассматриваемого узла, т.е. в тех ветвях, где в данный момент времени есть сигнал на выходе задатчика адресов 5. Кроме того, этот сигнал запретит с помощью элемента HE 17 установку в нулевое состояние триггера 10 в моделях ветвей, последними сформировавших временной интервал в этом узле.

Импульсы с генератора 4 импульсов поступают на входы эадатчиков адресов

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

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

Для определения конфигурации длиннейшего пути между начальным и конечным узлами сетевого графика блок 3 управления выдает разрешение на первый вход элемента И 23, а также разрешает прохождение импульсов череЗ элемент ИЛИ 25 на входы задатчиков адресов 5 и 6 всех моделей ветвей 1. В момент переполнения задатчиков адресов 6, в которых записан конечный узел сетевого графика, блок 3 управления выдает импульс на вход элемента

ИЛИ 27, выходной сигнал с которого поступит на первый вход элемента И

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

6 Если на третьем входе этого элемента будет разрешение с выхода триггера

10, т.е. если ветвь сформировала свою длительность последней в конечном узле сетевого графика, то выходной сигнал элемента И 15 установит в единичное состояние триггер 11. Единичный выход триггера 11 разрешит прохождение импульсов с выхода задатчика адресов начального узла 5 через элемент И 16 на вход элемента ИЛИ 28 блока 2 формирования топологии. Остальные входы этого элемента разделения подключены к аналогичным входам остальных моделей ветвей. Сигнал с выхода элемента ИЛИ 28 поступит на второй вход элемента И 23 и через элемент ИЛИ 27 на входы элемента И 15.

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

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

Блок управления при этом прекраща- 10 ет подачу импульсов на элемент ИЛИ

25 и подает запрет на элемент И 23.

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

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

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

25 устройство для моделирования сетевого графика, содержащее блок управления, генератор импульсов, блок формирования топологии и блок моделей ветвей по числу работ, каждая из кото-30 рых состоит из задатчиков. адресов, выходы которых подключены соответственно к первым входам первого и второго элементов И, второй вход первого элемента И соединен с.одним выходом пер35 ваго триггера, другой выход которого подключен к второму входу второго элемента И, третий вход которого соединен с выходом первого элемента ИЛИ блока формирования топологии, выход второго элемента И подключен к одному входу формирователя временных интервалов, другой вход которого соединен с выходом первого элемента И блока формирования топологии, выход формирователя временных интервалов подключен к первым входам триггеров, второй вход второго триггера соединен с выходом соответствующего задатчика адресов, выход второго триггера подключен к входу второго элемента ИЛИ блока форми- 50 рования топологии, первый вход элемента ИЛИ блока моделей ветвей соединен с выходом первого элемента И, второй вход элемента ИЛИ через элемент HE подключен к выходу соответствующего 5 задатчика адресов, а выход элемента

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

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

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

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

9 305484, кл. & 06 G. 7/34, 1969.

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

Р 422002, кл. G. 06 & 7/48, 1972.

6081б9

Составитель,И; Загорбинйна

Техред Е. дащщовн Корректор Н. Ковалева

Редактор Н.Разумова

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

Заказ 2804/34 Тираж 926 Подписное

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

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