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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСГМЬЛИН ае 01>

3Ю С 06 F 15/20

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

Х ABTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 3602967/24-24 (22) 07.06.83 (46) 15. 10.84. Бюл. И- 38 (72) А.И. Баранов, В.В. Васильев, О.H. Голованова, Л.О. Иакогонюк и Я.Я. Фенюк (7 1) Институт .проблем моделирования в энергетике АН УССР (53) 681.333(088.8) (56) 1. Авторское свидетельство СССР

Ф 652566, кл. С 06 F 15/20., 1975.

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

У 708367, кл. G 06 G 7/48, 1977.

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

В 583439, кл. С 06 F 15/20, 1976.

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

У 556460, кл. G 06 G 7/48, 1976 (прототип). каждая модель ветви включает триггеры, формирователь временных интервалов, элементы И, элемент НЕ и задатчики адресов начального и конечного узлов, входы которых объединены и соединены с входом счетчика блока формирования топологии,. в каждой модели ветви выход первого триггера подключен к первому входу первого элемента И, второй и третий входы которого соединены соответственно с выходом задатчика адреса начального узла и с первым входом формирователя управляющих импульсов, выход формирователя временных интервалов модели ветви под- Я ключен к первым входам первого и второго триггеров, второй вход первого триггера соединен с выходом второго элемента И модели ветви, выход задатчика адреса конечного узла подключен к входу элемента НЕ и к первому входу третьего элемента И модели ветви, выход второго элемента И блока формирования топологии соединен с первым входом формирователя временных интервалов модели ветви, выход второго триггера модели ветви подключен к соответствующему входу первого элемента ИЛИ бло" ка формирования топологии, о т л ич а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет моделирования альтернативных и мажоритарных сетей, в него введен счетчик импульсов, кроме того, формирователь управляющих импульсов содержит счетчик и элемент И, выход которого является выходом формирователя управляющих импульсов, выход счетчика подключен к первому входу (54) (57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ ГРАФИКОВ, содержащее генератор импульсов, формирователь управляющих импульсов, блок моделей . ветвей, блок формирования топологии, включающий счетчик, сдвиговый регистр, триггер, элементы И, элементы ИЛИ, первый элемент НЕ, причем выход первого элемента ИЛИ соединен с первым входом первого элемента И и через первый элемент НŠ— с первым входом второго элемента И, вторые входы первого и второго элементов И соединены соответственно с первым и вторым выходами генератора импульсов,вход счетчика подключен к сдвиговому входу сдвигового регистра, выход счетчика соединен с единичным входом триггера, единичный и нулевой выходы которого подключены соответственно к первым входам третьего элемента И и первого элемента ИЛИ, ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

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

19024 модели ветви подключен к второму входу формирователя временных интервалов, выход второго триггера модели ветви соединен с соответствующим входом записи сдвигового регистра блока формирования топологии, выход третьего элемента И блока формирования топологии подключен к нулевому входу триггера, к входу управления записью сдвигового регистра блока формирования топологии, к второму входу второго триггера модели ветви, выход сдвигового регистра бло" ка формирования топологии соединен с вторым входом элемента И формирователя управляющих импульсов, являющимся первым входом формирователя управляющих импульсов, вход счетчика формирователя управляющих импульсов соединен с выходом перв oro элемента И блока формирования топологии,. выход второго элемента И

I блока Формирования; топологии подключе н к входу .счетчика импуль сов.

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

Известны устройства для модели рования сетевых графиков. Каждое из этих устройств содержит генератор импульсов, блок управления, блок моделей ветвей, причем число моделей ветвей равно числу ветвей в моделируемой сети, и блок формирования топологии, при этом каждая модель ветви содержит эадатчики адресов начального и конечного узлов, которые совместно с блоком формирования топологии моделируют логические зависимости в узлах сетей. Моделирование длин ветвей и путей в устройствах выполняется одинаково, отличие состоит лишь в моделировании логических зависимостей в узлах сетей (13, С23 и Г33, Известные специализированные устройства для моделирования сетей характеризуются тем, что каждое из них позволяет моделировать сети с

5 ограниченным набором .логических зависимостей в узлах сетей. Здесь и далее будем понимать под сетью связный ориентированный взвешенный граф 6 = VnW, где V — множество ветвей сети, 9I — множество узлов сети. Через V+ (Ч ) будем обозначать множество входящих (соответственно множество выходящих) ветвей для узла а;; Е (Ч,() — двоич15 ный признак начала (окончания соответственно) ветви v+.

Рассмотрим известные устройства для моделирования сетей с точки зрения моделирования ими логических зависимостей в узлах сетей.

Так, устройство (11 позволяет моделировать дизъюнктивные, конъюнктивные и дизъюнктивно-конъюнктивные зависимости в узлах, которые описываются выражениями:

Vy v .eV.

Ч ч ., ч,... е Ч+. с(у Р"" 1

11 19Q24 иена в виде задатчиков адресов, выходами соединенных с элементами И, причем выход первого элемента И соединен с входом формирователя временных интервалов, вход второго элемента И соединен через инвертор с первым входом элемента ИЛИ, к второму

Устройство для моделирования сетевьгх графиков 2 позволяет моделировать в узлах сети зависимосt0 ти вида (1), (2) и выполнять ассоциа тинный поиск по совокупности признаков, т.е. реализовать зависимость вида t5

П лП ЛП Л.., (М где д, П, 11 — значения двоичЫ Р Х ных признаков, по которым ведется го поиск;

П = П, если если f1 = О.

Устройство 3 позволяет моделировать дизъюнктивные узлы с альтернативными и стохастическими выходами, т.е. реализовать зависимость

E»= (P

30

3, 0=1 Ч ч,Ч, BV (5) где Рс, — двоичный признак разрешения начала ветви ч после окончания ее начального узла 1; при этом существует лишь одна ветвь, для ко- 35 торой этот признак равен в данный момент единице, т.е. из всех выходящих ветвей реализуется лишь одна.

Для узла с альтернативными выходами значение признаков R, p>,... 40 задается заранее, до начала моделирования сети, для узла со стохастическими выходами значение признака

Рц связано с вероятностью реализации ветви чц и получается в процессе 45 моделирования сети.

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

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

1119024 топологии, а выход счетчика соединен с единичным входом триггера блока формирования топологии, единичный выход которого подключен к одному из входов третьего элемента И блока 5 формирования топологии, а нулевой выход триггера-соединен с одним из входов второго элемента ИЛИ блока формирования топологии„ а выход сдвигового регистра подключен к пер вому входу дополнительного элемента 4 каждой модели ветви, второй вход которого соединен с выходом задатчика адреса начального узла, а.выход подключен к единичному входу второго триггера ветви (4 ).

Устройство для моделирования сетевых графиков позволяет моделиро-. вать конъюнктивные сети с исключением ветвей, выходящих из запрещенных узлов 9lе.9/, т.е. реализовать зависимость вида „=E1,=...=V hЧ h...ËRi, d.å%,R.=P, 25 (Ь}

,„,<,...6V,, 4v,ч„...eV+

Ни одно .из известных устройств не может моделировать альтернативные и мажоритарные сети. Альтернативные

30 сети отличаются от обычных сетевых графиков широким набором логических зависимостей в узлах. А именно, в число узлов альтернативной сети входят дизъюнктивные и конъюнктивные с обычными выходами, а также дизъюнктивные и конъюнктивные с альтернативными и стохастическими выходами, Эти зависимости описываются соответственно выражениями (1), (2), (5) и (7)

Е =(V ЛЧ п )Лй, ЧЧ,Ч ЕЧ. К= Vv,ч„,,еЧ., Щ

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

Для такого узла число выходящих вет50 вей равно числу входящих, и каждой выходящей ветви соответствует единственная входящая ветвь, так что признак R принимает единичное значение только тогда, когда окончалась соответствующая ч входящая ветвь. °

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

Таким образом, сетевой график представляет собой альтернативную сеть частного вида. Альтернативные сети охватывают существенно более широкий класс объектов и задач планирования и управления, нежели сетевые графики, в связи с чем моделирование таких сетей имеет большое практическое значение.

Мажоритарные сети отличаются тем, что их узлы реализуют-мажори-; тарные функции. Важность моделирования таких сетей обусловлена широкими исследованиями по созданию вычислительных машин на мажоритарных элементах. Функция i-го мажоритарного узла с тремя входами описы% вается выражением

Ю =Х =-- "(; 9 1= Ь "Ь. " лУ ч ЛЧ

7 Р т

ЧЧ„,Ч1,...6V,, Ч,ч,ч )Y, (8) Цель изобретения — расширение функциональных возможностей за счет моделирования альтернативных и мажоритарных сетей.

Указанная цель достигается тем, что в устройство для моделирования сетевых графиков, содержащее гене1 ратор импульсов, формирователь управ ляющих импульсов, блок моделей ветвей, блок формирования топологии, включающий счетчик, сдвиговый регистр, триггер, элементы И, элементы ИЛИ, первый элемент НЕ, причем выход первого элемента ИЛИ соединен с первым входом первого элемента И, и через первый элемент НŠ— с первым входом второго элемента И вторые входы первого и второго элементов И соединены соответственно с первым и вторым выходами генератора импульсов, вход счетчика подключен к сдвиговому входу сдвигового регистра, выход счетчика соединен с единич» ным входом триггера, единичный и нулевой выходы которого подключены соответственно к первым входам третьего элемента И и первого элемен та ИЛИ, каждая модель ветви включает триггеры, формирователь временных интервалов, элементы И, элемент НЕ и задатчики адресов начального и ко11 19024

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

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

° дом формирователя управляющих импульсов, выход счетчика подключен к первому входу элемента И, вход счетчика является вторым входом формирователя управляющих импульсов, à 35 в каждую модель ветви введен счетчик, в блок формирования топологии введен второй элемент НЕ, выход которого подключен к второму входу третьего элемента И, третий вход которого соединен с выходом первого элемента ИЛИ блока формирования топологии, выходы генератора импульсов подключены к входам второго элемента ИЛИ блока формирования то- 45 пологии, выход которого соединен с входом второго элемента НЕ, выход первого элемента И блока формирования топологии, подключен к входу счетчика блока формирования тополо- 50 гии выход первого элемента И модели

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

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

Устройство содержит блок 1 моделей ветвей, блок 2 формирования топологии, формирователь 3 управляющих импульсов, генератор 4 импульсов.

Каждая модель ветви содержит формирователь 5 временных интервалов, задатчики 6, 7 конечного и начального адресов соответственно, триггеры 8, 9, счетчик 10, элементы И 11 — 13, элемент НЕ 14. Блок формирования топологии содержит счетчик 15, сдвиговый регистр 16, триггер 17, элементы И

18-20, элементы ИЛИ 21-22, второй и первый элементы НЕ 23, 24. На фиг. 1 обозначены входы 25, 26 формирователя 5, счетчик импульсов 27

° и выход 28 формирователя 3; на фиг. 2 — элемент И 29, счетчик 30.

Регистр 16 блока формирования топологии является сдвиговым регистром с параллельной записью информации.

Сдвиговый вход регистра соединен с выходом элемента И 18, а вход управления записью — с выходом элемента И

20. Последний вход регистра предназначен для записи в регистр информаI

1902С4

15

20!

40

50

9 11 ции, присутствующей на входах, записи, соединенных с единичными выходами триггеров 9 моделей ветвей. Сдвиговый вход регистра предназначен для сдвига содержимого регистра вправо. Триггер 17 и счетчик 15 предназначены для того, чтобы обеспечить постоянную длительность этапа моделирования логических зависимостей.

В качестве задатчиков 6, 7 конечного и начального адресов использованы кольцевые сдвиговые регистры. Эти регистры предназначены для записи информации о топологии моделируемой сети и о логических зависимостях в узлах сети. Выход каждого из этих регистров соединен с его же входом записи, за счет чего обеспечивается восстановление первоначально записанной информации через каждые Н импульсов сдвига, t4 — число разрядов регистра. При этом задатчик

7 предназначен для записи и хранения информации о логических зависимостях в узле (т.е. в разряде, соответствующем ветви ч, в задатчик

7 ветви ч занесена единица, если Y

Ь Ol входит в запись 1 ). Задатчик 6 предназначен для записи и хранения информации. о признаках выбора (либо запрета) той или иной ветви при условии реализации ее начального узла (т.е. признаки R,. ). При этом вся логическая информация представ-. лена через номера ветвей. А именно, "й ветви сети поставлен в соответствие j-й разряд регистра 16 задатчиков 6 и 7. Номера узлов в процессе подготовки сети к моделированию и в процессе моделирования не используются. Формирователь 5 временных интервалов включает в себя:. дискретную линию задержки, например счетчик (на фиг. 1 не показан).

Формирователь предназначен для отсчета импульсов, поступающих на

его вход, в том случае, если предварительно на другой его вход было подано разрешение. При этом временной интервал между поступлением на формирователь разрешения и окончанием работы формирователя находится в соответствии с длиной моделируемой ветви. Формирователь предназначен для выдачи сигнала окончания работы устройства. Счетчик 30 и элемент И 29 предназначены для выдачи сигнала останова.

Подробно его функционирование расмотрим на примере моделирования сети (фиг.8). Генератор 4 импульсов предназначен для выдачи двух серий импульсов — А и Б, сдвинутых друг относительно друга. Для выдачи этих серий предназначены соответственно второй и первый выходы генератора, Расмотрим работу устройства.

Моделирование сети выполняется посредством чередования двух этапов: этапа моделирования длин ветвей, когда на модели ветвей поступают,импульсы серии А, и этапа модели рования логических зависимостей, I когда на модели ветвей поступают импульсы серии Б. Рассмотрим вначале моделирование различных логических, зависимостей (фиг. 3-7), а затем моделирование сети в целом (фиг..8).

При этом полагаем, что N = 8 (N — число разрядов регистров 16, 6, 7, а также емкости счетчиков 10 всех моделей ветвей и счетчика 15).

Так, на фиг. 3 показано моделирование дизъюнкции. Отметим, что при моделировании узлов с обычными (неальтернативными) выходами содержимые регистров задатчиков 6 и 7 каждой модели ветви равны между собой, Рассмотрим работу устройства на примере фиг. 3, начиная с момента, когда окончилась ветвь а . Это означает, что на выходе триггера 9 модели ветви а появился единичный сигнал, который проходит на выход элемента ИЛИ 21 и через элемент НЕ 24 и элемент И 19 запрещает поступление на модели ветвей импульсов серии

А. Этот же сигнал через элемент И 18 разрешает поступление импульсов серии Б на регистры задатчиков 6, 7 моделей ветвей. В рассматриваемый момент триггер 17 находится в единичном состоянии. По окончании им" пульса серии А, который обусловил появление единичного сигнала на выходе триггера 9 модели ветви а на выходе элемента ИЛИ 22 появляется нулевой сигнал, а на выходе элемента НЕ 23 — единичный. Единичный сигнал на выходе элемента И 20 может появиться только тогда, когда на выходе элемента НЕ 23 присутствует единичный сигнал, т.е. в промежутках между импульсами серий А и Б. Поскольку на всех входах элемента И 20 присутствуют единичные сигналы, та11190 кой же сигнал появляется на выходе элемента И 20. Последний сигнал поступает на вход уплавления записью регистра 16, н в этот регистр записывается информация, присутствую- 5 щая íà его входах параллельной записи, в частности, в а-й разряд регистра 16 заносится единица. По этому же сигналу с выхода элемента И 20 триггер 17 и триггеры 9 всех моделей ветвей устанавливаются в нулевое состояние. Нулевой выход триггера 17 обеспечивает присутствие единичного сигнала на выходе элемента ИЛИ

21; по-прежнему импульсы серии А 15 на модели ветвей не поступают, а поступают лишь импульсы серии Б. Независимо от состояния триггеров 9

;моделей ветвей такое положение сохраняется до тех пор, пока триггер 20

17 не установится в единичное состояние сигналом с выхода счетчика 15, что происходит после подачи на . его вход (и на входы регистров задатчиков 6, 7 всех моделей ветвей)

8 импульсов серий Б с выхода элемента И 18. Таким образом, триггер

17 и счетчик 15 обеспечивают постоян-! ную длительность каждого этапа мо.делирования логических зависимостей. 30

° Те же И импульсов серии Б поступают на сдвиговый вход регистра 16.

В данном случае N = 8; примем, что a --й "ветви соответствует 1-й (слева) разряд сдвиговых регистров задатчиков 6, 7 и регистра 16; Ь-й ветви 2-й разряд. После поступления семи импульсов серии Б на входах регистров задатчиков 6, 7 моделей с -1 и д -й ветви появляются единич- 40 ные сигналы. Для определенности будем рассматривать только модель

С-Й ветви, для d-й ветви все аналогично. Единичный сигнал с выхода регистра задатчика,6 (7) поступает 45 на первый вход элемента И 13 (элемента И 11 соответственно). Однако поскольку в соответствующем разряде регистра 16 записан нуль (ветвь Ь не окончилась), на выходе регистра 16 после поступления семи импульсов серии Б нулевой сигнал, который поступает на второй вход элемента И 11 каждой модели ветви, в том числе и с-й, запрещая тем самым поступление сигнала на вход счетчика 10 с-й модели ветви. Поэтому состояние этого счетчика не меняется и на выходе эле24!

2 мента И 13 единичный сигнал не появляется. При поступлении следующего импульса серии Б на выходе регистра 16 появляется единичный сигнал, так как содержимое этого разряда, со ответствующего а-й ветви, равно 1.

Этот сигнал через элемент И 11 разрешает поступление единичного сигнала на вход счетчика 10 модели ветви с, так как на выходах регистров задатчичиков 6, 7 и в этом такте присутствуют единичные сигналы. По сигналу на входе счетчика 10 к его содержимому прибавляется единица и на выходе этого счетчика появляется сигнал переполнения, который разрешает поступо ление единичного сигнала на выход элемента И 13 с-й модели ветви. Этот сигнал поступает на вход формирователя 5 временных интервалов этой модели ветви, подготавливая его к отсчету импульсов серии А. Единичный сигнал на выходе регистра задатчика 6 этой модели ветви запрещает через.эле- мент НЕ 14 поступление единичного сиг-. нала на выход элемента И 12 и на единич-, ный вход триггера 8,поэтому триггер 8 остается в нулевом состоянии, То же происходит с моделью ветви 3 . Таким

I образом, обе эти модели ветвей могут моделировать свои временные интервалы. По тому же импульсу серии Б появляется сигнал переполнения на выходе счетчика 15, который устанавливает в единицу триггер 17.

Поскольку в рассмотренный период времени состояния триггеров 9 всех моделей ветвей не изменялись, на выходе элемента ИЛИ 21 присутствует нулевой сигнал, поэтому при появлении единичного сигнала на выходе элемента НЕ 23 единичный сигнал на выходе элемента И 20 отсутствует.

Нулевой сигнал с выхода элемента ИЛИ

21 через элемент НЕ 24 и элемент И

19 разрешает поступление на модели ветвей импульсов серии А, через элемент И 18 запрещает поступление им пульсов серии Б. Импульсы серии А поступают на те формирователи временных интервалов, на которые предварительно поданы единичные сигналы с выходов элементов И 13. В частности, эти импульсы поступают на формирователи 5 моделей ветвей с d, чем обеспечивается моделирование ветвейс и d . .То же произошло бы с моделями ветвей с и d, если

13

1119 ! бы первой окончилась ветвь Ь либо ветви а и Ь окончились одновременно.

Моделирование конъюнкции (фиг. 4) отличается тем, что в счетчики 10 с -й и d- é моделей ветвей заносится .число, равное в общем случае не и -1, а М-с, где с — число ветвей, входящих в узел, начальный для с и д

Конкретно для фиг. 4 о1= 2, т.е. в счетчиках 10 моделей с-й и d-й 10 ветвей Ъанесено число 6. Таким образом, сигнал переполнения на выходе счетчика 10 появляется после того, как к его содержимому прибавлены две единицы, т.е. после того, как 15 окончились обе ветви а и Ь, Этапы моделирования логических зависимостей после окончания ветвей а и Ь, если они окончились в разное время, выполняются так же,как указано. 20

В течение первого этапа к содержимым счетчиков 10 моделей с-й и а-й ветвей прибавляется по единице, после чего их содержимые становятся равными 7.

Сигнал переполнения появляется на 25 их выходах только после второго этапа, когда окончилась вторая ветвь (а либо Ъ ). Если же ветви а и Ь окончились одновременно, то в начале этапа моделирования логических за- щ0 висимостей присутствуют единичные ,сигнальг на выходах триггеров 9 а-й

1 и b-й моделей ветвей и по сигналу с выхода элемента И 20 записываются, единицы как в а-й, так и в Ь-й раэ- З ряды регистра 16. В этом случае прибавление двух единиц к содержимым счетчиков 10 моделей ветвей с и 3 выполняется в течение одного эта— па. В остальном устройство ра- 40 ботает, как указано.

Моделирование узлов с альтернативными выхОдами рассмотрим на примере узла типа временной различитель (фиг.5). Содержимые ре- 4g гистров задатчиков 6, 7 моделей ветвей d 1c, rn приведены на фиг.5, Ветви а (Ь, c) соответствуют 1-й (2-, 3-й соответственно) разряд регистра. Логические соотношения (фиг.5) означают, если первой окончилась ветвь а (Ь, c ), то начнется ветвь д (Ъ,в соответственно), остальные выходящие ветви запрещаются.

Пусть, например, перв ой окончилос ь. ветвь a . Начинается этап моделирования логических зависимостей, как указано. После 6 импульсов серии Б

024 появляются единичные сигналы на выходах регистров задатчика 7 моделей ветвей d, k,,т и на выходе регистра задатчика 6 модели ветви rn, Так как ветвь с не окончена, в соответствующем разряде регистра 16 записан нуль, и в рассматриваемом такте на выходе регистра 16 присутствует нулевой сигнал, запрещая поступление единичного сигнала на выходы эле. ментов И 11 моделей ветвей д, 1,tn.

Таким -образом, изменения содержимых счетчиков 10 не происходит. После поступления следующего импульса серии Б происходит то же. Наконец, после поступления 8-ro импульса серии Б на выходе регистра 16 появляется единичный сигнал, т.е. а -я ветвь окончена..Этот сигнал проходит на выходы элементов И 11 моделей ветвей d, lc., п и прибавляет по единице в счетчики 10 этих моделей ветвей, после чего на выходах этих счетчиков появляются сигналы переполнения. Поскольку в данный момент единичный сигнал присутствует на выходе регистра 6 лишь в одной ветви d, сигнал с выхода счетчика

10 через элемент И 13 проходит на формирователь 5 этой модели ветви, подготавливая его к отсчету импульсов серии А. Нулевые сигналы на выходах регистров задатчиков 6 моделей ветвей %, т через элементы НЕ 14 и. элементы И 12 устанавливают в еди" ницу триггеры 8 этих моделей ветвей, запрещая тем самым через элементы И

11 реализацию этих ветвей. Если признак разрешения ветви задан заранее, он заносится в регистр задатчика 6 ветви в виде соответствующего кода. Моделирование таких узлов выполн ется так же. Если начальный узел для ветвей d, 1с, в конъюнктивный, с альтернативными выходами, то меняется только содержимое счетчиков 10,, а именно вместо 7 там записывается число 5. Тогда сигналы переполнения в счетчиках 10 появляются после окончания всех трех ветвей. Запрет какой-либо ветви реализуется путем заполнения регистра задатчика 6 нулями.

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

15 11190 регистрах задатчиков 6 выходящих ве вей. А именно, единицы в регистр задатчика 6 заносятся случайным образом, с учетом вероятности реализации той или иной ветви. Реализация единственной из выходящих ветвей обеспечивается тем, что единица в любом разряде регистра задатчика

6 присутствует в единственной модели ветви из всех моделей ветвей, вы- 10 ходящих из узла со стохастическими выходами. Поясним это на примере.

Пусть после свершения дизъюнктивного узла должна начаться одна из двух выходящих ветвей, причем вероят 15 ности их реализации одинаковы и равны по 0,5. Тогда .в счетчики 10 за:носится число N --1; в регистр задат- чика 6 одной выходящей ветви заносится число, состоящее из 812 еди- ZO ниц и М/2 нулей, причем расположение единиц в числе случайно. В регистр задатчика 6 второй выходящей ветви заносится число, обратное первому (т.е. там, где в первом числе были 25 единицы, во втором стоят нули, и наоборот). В этом случае после реализации начального узла для этих ветвей начинает моделирование длины лишь одна модель ветви, а именно та, для которой сигнал переполнения счетчика 10 совпал с единичным сигналом на выходе регистра задатчика 6.

Равновероятный выбор ветвей обеспечивается одинаковым числом единиц в регистрах задатчиков 6.

После окончания моделирования сети (т.е. после получения одной реализации стохастической сети) содержимые регистров задатчиков 6 мо-. 4О делей ветвей, выходящих. из стохастических узлов, меняются случайным образом.

Конъюнктивный узел со стохасти.ческими выходами реализуется так 4> же, но в счетчики 10 заносится число H-d, где о — число ветвей, входящих в конъюнктивный узел.

Моделирование мажоритарного узла (фиг. 6) выполняется так же, как мо- 50 делирование конъюнктивного узла (фиг. 4), отличие состоит в том, что в счетчики 10 заносится число, 0L 1 равное М-р, где p = () +1, о — число входов мажоритарного узла. Для узла, изображенного на фиг. 6, смысл мажоритарной функции узла состоит в том, что ветви k,m

24 16 могут начаться, когда окончены любые две из входящих ветвей а, b c

В остальном устройство функционирует, как описано для фиг. 4. Устрой» ство может реализовать также сложные логические зависимости, например

И-ИЛИ (фиг. 7). Этот узел представляется в устройстве в виде трех узлов — двух конъюнктивных, с выходящими ветвями р. и Ъулевой длины, и одного дизъюнктивного, с выходящими ветвями k и в . Содержимые регистров и счетчиков приведены на фиг. 7; ветви а, Ь, c d p соответствуют разрядам регистров i

2, 3, 4, 7, 8 соответственно (считая слева).

Полученные три узла моделируются в устройстве так же, как описано для фиг. 3. Особенность состоит в том, что ветви р и <, — нулевой длины.

Это означает, что после реализации одного из конъюнктивных узлов на этапе моделирования логических зависимостей на формирователь 5 временных интервалов модели ветви, например р подается разрешающий сигнал, по которому ввиду нулевой длины этой ветви триггер 9 р-й модели ветви устанавливается в единицу. Поэтому по окончании текущего этапа моделирования логических зависимостей на выходе элемента ИЛИ 21 имеется единичный сигнал. После. установки триггера 17 в единицу в промежутке между импульсами А и Б, когда на выходе элемента НЕ 23 присутствует единичный сигнал, на выходе элемента И 20 также появляется единичный сигнал, по которому триггер 17 устанавливается в нуль, обеспечивая тем самым начало нового этапа моделирования логических зависимостей. По тому же сигналу в регистр

16 записывается информация, в частности в 7-й разряд записывается еди ница. Таким образом, сразу после окончания одного этапа моделирования логических зависимостей начинается второй такой же этап.

После поступления двух импуль/ сов серии Б на выходе регистра 16 появляется единичный сигнал, который через элементы И 11 моделей ве вей М и m поступает на счетчики 10 этих моделей; сигналы с выходов эт. счетчиков поступают через элементы

И 13 на формирователи 5, разрешая /

Рассмотрим процесс моделирова5 ния собственно сети (фиг. 8), Будем при этом также ссылаться на фиг. 1 и 2. Начальный узел ветви (фиг. 8) — дизъюнктивный, конечный узел сети конъюнктивный. Поскольку в остальные узлы сети входит по одной ветви, эти узлы реализуются после окончания входящей ветви. Длины ветвей проставлены в скобках. Организация устройства обуславливает необходимость введения в состав се- ти двух ветвей нулевой длины: начальной ю и конечной k, Предварительно в устройство заносится вся необходи« мая информация: в формирователи 5— длины ветвей, в регистры задатчиков

6, 7 и счетчики 10 — информация о топологии в логических зависимостях (фиг..8). Счетчик 27, триггеры 8, 9 всех моделей ветвей, кроме ю -й, и триггер 17 блока формирования топологии находятся в нулевом состоянии. Триггер 9 в -й модели ветви установлен в единицу, в счетчике 30 записано число N-К, 10

Рассмотрим работу устройства, начиная с момента, когда на генера-: тор 4 импульсов и на триггер 17 подается сигнал пуска (на фиг. 1 и 2 входы, по которым поступает сигнал пуска, не показаны). По этому сигналу триггер 17 устанавливается в единичное состояние, а генератор 4 на" чинает выдачу импульсов серий А и Б, эти импульсы выдаются до тех пор, по-4О ка на генератор не поступит сигнал останова. На выходе элемента ИЛИ 21 присутствует единичный сигнал, так как триггер 9 tn-й модели ветви, установлен в единицу; такой же сиг- 45 нал имеется на выходе элемента HE 23, поэтому после установки триггера 17 в единичное состояние на выходе элемента И 20 появляется единич ный сигнал,по которому в ш-й разряд. регистра 16 записывается единица.

Начинается этап моделирования логических зависимостей, который выполняется, как указано. Испульсы с выхода элемента И 18 поступают на вход 55

26, увеличивая содержимое счетчика 30.

Сигнал на выходе счетчика 30 появляется через каждые (А г1 + К ) им17 1190 делирование Ими.временных ййтервалов. В остальном работа устройства протекает аналогично.

l8 пульсов, поступающих с выхода элемента И 18, где А = О, 1, 2, 3,, После tn импульсов серии Б, поступивших на модели ветвей, разрешающие сигналы поступают на входы формирователей 5 моделей ветвей ы и, Ь

После окончания этапа моделирования логических зависимостей начинается этап моделирования длин ветвей. Триггер 17 находится в единичном состоянии, все триггеры 9 — нулевом, и единичный сигнал на выходе элемента

НЕ 24 разрешает поступление импуль-. сов серии А через элемент И 19 на формирователи 5 временных интервалов моделей ветвей ы, Ъ .

Те же импульсы с выхода элемента

И 19 поступают на вход счетчика

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

После поступления ы импульсов серии Б на модели ветвей с,d поступает сигнал, разрешающий формирование их временных интервалов. На втором этапе моделирования длин ветвей, после одного импульса серии А, оканчивает работу модель ветви Ь; на следующем этапе моделирования логических зависимостей разрешающий сигнал поступает на модель ветви

На следующем этапе моделирования длин ветвей, после одного импульса серии А, оканчивает работу модель ветви с.,На этапе моделирования логических зависимостей на модель ветви вновь посылается разрешающий сигнал, который не изменяет состояния q --й модели ветви, так как формирователь 5 этой модели: ветви уже считает импульсы серии А.

Далее процесс моделирования сети продолжается аналогично. Сигналы с выхода счетчика 30 не поступают на вход элемента. И 31, поскольку в

1 -м разряде регистра 16 имеется нуль.

После одного импульса серии А (считая с начала четвертого этапа моделирования длин ветвей) оканчивает работу модель ветви d, и в следующем этапе моделирования логических зависимостей к содержимому

19

1.! 19024 счетчика 10 модели ветви k прибавляется единица. После одного импульса серии А (поступившего в пятом этапе моделирования длин ветвей) оканчивается ветвь q,,и на модель k-й ветви поступает разрешающий сигнал.

Как описано для ветвей нулевой длины (см. фиг. 7), при поступлении этого сигнала триггер 9 модели ветви устанавливается в единицу, обеспе- 10 чивая начало седьмого этапа моделирования логических зависимостей сразу же за шестым. В начале седьмого этапа, в k-й разряд регистра 16 записывается единица. После пос- 15 туплейия 1с импульсов серии Б эта единица поступает на вход 25, поскольку на выходе счетчика 30 в этот мо-! мент также имеется единичный сигнал, то на выходе элемента И 31 по- 20 является единичный сигнал, который поступает на выход 28 формирователя 3 и оттуда на генератор 4 импульсов, останавливая его работу.

На этом работа устройства заканчивается. В счетчике 27 содержится число 7, равное числу импульсов серии А, поступивших на модели ветвей в процессе моделирования. Это число равно длине оптимального пути от начального до конечного узла данной альтернативной сети (оптимальный путь на альтернативной сети — это кратчайший путь, с учетом конъюнктивных зависимостей, если в составы данной альтернативной сети входят конъюнктивные узлы). Так, кратчайший (длиннейший) путь является частным случаем оптимального пути, когда соответствующая альтернативная сеть содержит только дизъюнктивные (толь -. ко конъюнктивные соответственно) узлы.

Таким образом расширяются функциональные возможности устройства.

I 119024! 11902é

4 «(Vvv < Vb v .) л gg .

1 ° (VgvVb vVñ)люк;

° (4 Я v Vó v Uc) д Rm; ф - 1 npll ф л " С 1;

Ю„1 ЛРО Чц Л f> С *1b д 1 при у л Р tq 1

1 119024

Iz Ущ * fz t> v Ур 4 Ур + Ур f Q;

Ч *,ф Урл ф;

Ф Ф

Ще. 7

Ща8 щщяЩ1 Заказ 7455/37 ТиРаж 698 . Подписное

Филиал

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