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

 

Изобретение относится к области электронного моделирования для обработки информации специального назначения и может быть использовано при построении специализированных вычислительных устройств для решений задач на сетях. Целью изобретения является сокращение объема оборудования. Поставленная цель достигается изменением связей между элементами, что позволило сократить объем оборудования на m элементов ИЛИ и m элементов И, где m - количество моделей ветвей, используемых в устройстве. 2 ил.

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

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

РЕСПУБЛИК

1837315 Al (я)5 G 06 F 15/20, 15/419

Г (СУДАРСТВЕННОЕ ПАТЕНТНОЕ

ЕДОМСТВО СССР

ОСПАТЕНТ СССР) -.@МАЙ

aQ%3NO: ,, ". .:-19 ИйА

ПИСАНИЕ ИЗОБРЕТЕНИЯ

К! ( ( ( (ABT0PCКОМУ СВИДЕТЕЛЬСТВУ

1) 4922805/24

2) 29.03.91

6) 30.08.93. Бюл. М 32

2) П.Л, Прокопьев, В.П. Бубнов и В.И. Саонов (6) Авторское свидетельство СССР

717787, кл. G 06 G 7/122, 1977.

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

1138806, кл. G 06 G 15/20, 1985. (4) УСТРОЙСТВО ДЛЯ У4ОДЕЛИРОВАНИЯ

С ЕТЕ Й

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

Целью изобретения является сокращен е объема оборудования.

На фиг, 1 приведена блок-схема модели в тви устрсиства, на фиг. 2 — функциснапвная схема блока управления, Модель 19 ветви устройства содержит с и рвого по десятый элементы И 1-10, с перв ro по четвертый триггеры 11 — 14, первый и в орой элементы ИЛИ 15, 16, элемент 17 и дикации, формирователь 18 временного и тервала, вход 21 модели ветви. Блок 22 у равления содержит третий, первый, втор и и четвертый триггеры 23 — 26, счетчик 27 и пульсов, четвертый, второй, третий, шестой, первый, пятый и седьмой элементы И (57) Изобретение относится к области электронного моделирования для обработки информации специального назначения и может быть использовано при построении специализированных вычислительных устройств для решений задач на сетях, Целью изобретения является сокращение обьема оборудования, Поставленная цель достигается изменением связей между элементами, что позволило сократить объем оборудования на m элементов ИЛИ и m элементов И, где m — количество моделей ветвей, используемых в устройстве. 2 ил.

2S-34, элемент ИЛИ 35, элемент НЕ 36. Кро- (ме того, устройство содержит генератор 37 импульсов и многовходовой элемент ИЛИ

38, второй и третий выходы 39 и 40 модели

19 ветви, третий выход 41 блока 22 управления, а восьмой выход 42, второй вход 43 блока 22 Управления, первый выход 44 модели 19 ветви, входы 45 -45п элемента ИЛИ

38, первый вход 46 блока 22, второй выход

47 блока 22, второй вход 48 модели 19, первый выход 49 блока 22 первый вход 50 модели 19, пятый и четвертый выходы 51 и 52 блока 22 управления, третий вход 53 модели

19, шестой вход 54 модели 19 ветви, пятый вход 55 модели 19 ветви, седьмой и шестой выходы 56, 20 блока 22, четвертый вход 21 модели 19 ветви.

При описании устройства входы и выходы блока 22 управления и модели названы полюсами.

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

В исходном состоянии, перед решением задачи на устройстве, модели 19 ветви посредством полюсов 39 и 40 коммутируются между собой в соответствии с конфигурацией моделируемой сети, полюсами 41 и 42 блок 22 управления подключается к полюсам тех моделей; между которыми отыскивается указанный путь, и в счетчики 18 всех

Ь моделей ветвей заносится число импульсов (N-сщ) где N — емкость счетчика. Триггеры всех моделей ветвей, триггеры блока управления и счетчик 27 импульсов устанавливаются в нулевое состояние.

Работа устройства начинается с момента установки триггера 23 в единичное состояние, которое выдает разрешение на вход

15 элемента И 33, При этом импульсы генератора 37, поступающие на полюс 43 блока 22 управления, проходят через элемент И 33 и поступаютна входы элементов И 28,30и29. 20

Через элементы И 28 и 29 импульсы не пройдут, так как они заблокированы нулевыми состояниями триггеров 24 и 26, а через элемент И 30 импульсы пройдут. С выхода элемента И 30 импульсы поступают на вход 25 элемента ИЛИ 35 и на полюс 41 блока 22 управления. Импульсы через элемент И 32 не пройдут потому, что на другом его входе нет разрешения, снимаемого с единичного выхода триггера 25. 30

Импульсы с полюса 41 блока 22 управления поступают на полюса 39 или 40 моделей 19 ветвей, которые в результате коммутации этими полюсами между собой образуют вершину сети, из.которой отыски- 35 вается путь с наибольшей пропускной способностью.

В указанных моделях 19 ветвей импульсы с полюсов 39 или 40 поступят на входы элемента ИЛИ 15 и элементов И 1-4, 6 и 8. 40

Элементы И 1-4, 6 и 8 заблокированы, и через эти элементы импульсы проходить не будут. На одном из входов элемента ИЛИ 15 есть разрешение, и поэтому импульсы прой-. дут через этот элемент на вход элемента И 45

5. С выхода элемента И 5 импульсы поступят на вход элемента ИЛИ 16 и, пройдя его, поступят на единичный вход триггера 11. По первому импульсу из всей серии импульсов, поступивших в модель 19 ветви на полюса 50

39, 40 триггер 11 установится в единичное состояние. Все последующие импульсы будут подтверждать это состояние триггера

11.

Единичное состояние триггеров 11 вы- 55 дает разрешение на вход элемента И 9. Это разрешение поступит на полюс 44 модели, так как на другом входе элемента И 9 есть разрешение, снимаемое с нулевого выхода триггера 13.

С полюса 44 модели 19 ветви разрешение поступит на соответствующий вход 45145п многовходового элемента ИЛИ 38. На входы элемента ИЛИ 38 поступят разрешения только тех моделей ветвей, которые своим полюсом 39 или 40 связаны с полюсом 41 блока 22 управления. Единичное состояние триггеров 11 свидетельствует о том, что данная модель ветви принадлежит выбранному разрезу (х х1) из множества разрезов К. Это соответствует первому шагу решения задачи.

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

ИЛИ 38. Это разрешение поступает на полюс 46 блока 22 управления. С полюса 46 в блоке 22 управления разрешение поступает на вход элемента HE 36 и через элемент И

34 на единичный вход триггера 24. В результате элемент НЕ 36 снимает разрешение с полюса 47 блока 22 управления и, следовательно, с полюсов 48 всех моделей ветвей, что заблокирует вход элемента И 7 моделей ветвей, Разрешение поступившее на единичный вход триггера 24, установит его в единичное состояние. Единичное состояние триггера 24 запретит прохождение импульcos от генератора 37 импульсов через элементы И 30 и ИЛИ 35 на полюс 41 блока управления и разрешит прохождение импул ьсов через элемент И 28 на вход счетчика

27 импульсов и полюс 49. С полюса 49 блока

22 управления импульсы поступят на полюс

50 всех моделей 19 ветвей.

В моделях 19 ветвей импульсы с полюса

50 поступают на вход счетчика 18 импульсов до его переполнения, Импульс переполнения счетчика 18 модели ветви поступает на нулевые входы триггеров 12 и 11 и на единичный вход триггера 13. В результате триггер 11 установится в нулевое состояние, если ранее он был установлен в единичное состояние импульсами, поступившими на полюса 39 или 40 модели ветви.

Триггер 13, установленный в единичное состояние поступившим на его единичный вход импульсом переполнения счетчика 18, установится в нулевое состояние очередным импульсом, поступившим на полюс 50.

Это происходит потому, что триггер 14 находится в нулевом состоянии и есть разрешение на элемент И 10, 1837315

Установка в нулевое состояние триггеов 11 импульсов переполнения счетчика 18 роизводит выбор модели ветви, у которой аибольшая пропускная способность среди сех выделенных ветвей. Это происходит в езультате того, что триггер 11 снимет в оответствующих моделях ветвей разрешеие с полюса 44 и, следовательно, с входов

5 многовходового элемента ИЛИ 38, В тот момент, когда будет снято последее разрешение с входа 45, элемента ИЛИ

8, блок 22 управления выдаст разрешение а полюс 47. Это разрешение поступит на олюса 48 всех моделей 19 ветвей, При этом модели ветви с наибольшей пропускной пособностью из выбранного разреза тригер 14 установится в единичное состояние азрешением, снимаемым с единичного выода триггера 13.

В этом случае триггер 13 останется в диничном состоянии, так как единичное остояние триггера 14 запретит прохождеие очередного импульса с полюса 50 через лемент И 10 на нулевой вход триггера 13.

Единичное состояние триггера 14 модеи 19 ветви выдает разрешение на входы лементов И 1 и 2, что обеспечивает исклюение моделей ветвей из дальнейшего расмотрения и закорачивание полюсов 39 и

О..Таким образом, в моделях ветвей, у коорых пропускная способность максимальа на данном шаге, триггеры 14 и 13 будут становлены в единичное состояние и их олюс 39 будет закорочен с полюсом 40. онец этого шага работы устройства опрееляется моментом появления импульса пееполнения счетчика 27 блока 22 правления. К этому моменту в счетчиках 18 сех моделей 19 ветвей восстановится инормация о их пропускной способности, т.е. роизойдет регенерация, Роль регенерацинного счетчика для счетчиков 18 всех модеей 19 ветвей выполняет счетчик 27 блока

2 управления. Он начинает свой счет с и0", его емкость равна N, а счетчики 18 модеей 19 ветвей начинают счет с N— - цл.

Импульс переполнения счетчика 27 блоа управления поступит через элемент ИЛИ

5 на полюс 41 блока 22 управления, Далее, 1атот импул ас с полюса 41 поступит на полюс

9 и 40 исделаи 19 еетееи, и веса процесс ,работы повторится аналогично рассмотрен ному.

Такие итерационные процессы будут повторяться до тех пор, пока импульс переполнения счетчика 27 блока 22 управления, поступающий на полюс 41, не появится на полюсе 42.

1 В момент появления импульса на полю се 42 блока 22 управления все множество

35 ветвей моделируемой сети будет разбито на два подмножества. Одно подмножество содержит ветви, пропускная способность qi которых удовлетворяет условию, и в соответствующих их моделях 19 ветвей триггера

14 и 13 находятся в единичном состоянии.

Другое подмножество содержит ветви с пропускными способностями, которые не удовлетворяют условию, и их триггеры 14 и

13 останутся в нулевом состоянии. Эти модели ветвей из дальнейшего рассмотрения исключаются, так как их триггер 13 находится в нулевом состоянии.

Дальнейшая работа устройства состоит из формирования пути с наибольшей пропускной способностью и его индикации. Для этого в блоке 22 управления импульс, поступивший на полюс 42, установит триггер 24 в нулевое состояние, а триггер 26 — в единичное, Нулевое состояние триггера 24 запретит прохождение импульсов генератора 37 с полюса 43 через элемент И 28 на вход счетчика 27 и полюс 49 блока 22 управления.

Следовательно, на полюсе 50 всех моделей ветвей импульсы генератора 37 перестанут поступать, Единичное состояние триггера 26 снимает разрешение с полюса 51 и выдаст сиунал на полюс 52 блока 22 управления.

Съем разрешения с полюса 51 блока Р: управления соответствует сьему разрг иения с полюса 53 всех моделей 19 ветвей, что блокирует элемент И 5 этих моделей.

Сигнал, появившийся на полюсе 52 блока 22 управления, поступит на полюс 54 всех моделей ветвей и установит триггеры 14 моделей в нулевое состояние. Нулевое состояние триггера 14 модели 19 ветви разрывает закоротку полюсов 39 и 40, что осуществляется за счет снятия разрешения с входов элементов И 1 и 2. Одновременно с этим импульсы генератора 37 начнут опять поступать через полюс 43, элементы И 33, И 30, ИЛИ 35, полюс 41 на полюсе 39 или 40 моделей 19 ветвей. При этом, на полюс 50 моделей 19 ветвей импульсы поступать не будут, так как нет разрешения на входе элемента И 28 от триггера 24 блока 22 управления. В указанных моделях 19 ветвей импульсы с полюса 39 поступят на вход элемента И 6 тех моделей, триггера 13 которых находится в единичном состоянии, и пройдут через него. При этом на другом входе элемента И 6 есть разрешение, поступающее с полюса 55 модели ветви и, следовательно, через полюс 56 с нулевого выхода триггера 25 блока 22 управления.

В модели 19 ветви импульсы поступят через элемент ИЛИ 16 на единичный вход

1837315

10

45 триггера 11. По первому импульсу из всей серии импульсов, поступивших в модель 19 ветви на полюс 39, триггер 11 установится в единичное состояние. Единичное состояние триггера 11 выдает разрешение на элемент

И 4. Поэтому остальные импульсы из всей серии с полюса 39 через элемент И 4 поступят на полюса 40 модели 19 ветви. Это произойдет у тех моделей, у которых триггер 18 находится в единичном состоянии. Таким образом, импульсы будут распространяться по сети через модели ветвей, у которых триггеры 13 находятся в единичном состоянии, до тех пор, пока они не появятся на полюсе

42 блока 22 управления, Поступивший на полюс 42 блока 22 управления импульс пройдет через элемент И

31, так как триггер 26 находится в единичном состоянии, и установит триггер 25 в единичное состояние, Единичное состояние триггера 25 выдает разрешение на полюс

20, снимает разрешение с полюса 56, выдает разрешение на элементы и 32 и 29 и снимает разрешение с элемента И 30. При этом с полюсов 55 моделей 19 ветвей снимается разрешение, что заблокирует их элементы И 6, и на полюсах 21 появится разрешение, что разрешит прохождение сигналов через элемент И 8, Одновременно импульсы генератора 37 через элементы И

33 и 29 поступят на полюс 42 и далее на полюса 40 моделей 19 ветвей, к которым подключен полюсом 42 блок 22 управления.

С полюса 40 в модели 19 ветви импульсы через элементы И 8 поступят на единичный вход триггера 12, По первому импульсу из серии импульсов, поступивших на полюс

40, триггер 12 установится в единичное состояние, которое выдает разрешение на элемент И 3, Поэтому остальные импульсы пройдут через элемент И 3 и поступят на полюс 39. Это происходит только у тех моделей ветвей, у которых триггер 13 находится в единичном состоянии. Таким образом, импульсы будут распространяться по сети через модели ветвей с полюса 40 на полюс

39 до тех пор, пока не появится на полюсе

41 блока 22 управления.

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

Нулевое состояние триггера 23 сигнализирует о конце решения задачи. При этом модели 19 ветвей, у которых триггеры 12 и 11 находятся одновременно в единичном состоянии, принадлежат искомому пути, Эти модели индицируются элементом 17 индикации.

Изменение в устройстве для моделирования сетей связей между элементами позволяет сократить объем оборудования на m двухвходовых элементов ИЛИ и m трехвходовых элементов И, где m — число моделей ветвей, используемых в сети. При этом, результаты моделирования с помощью предлагаемого устройства будет адекватны результатам, получаемым с помощью устройства-прототипа, Формула изобретения

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

ыход которого подключен к второму входу едьмого элемента И, выход которого подючен к нулевому входу третьего триггера, 5 лок управления содержит четы ре триггера, емь элементов И, счетчик импульсов, элеент НЕ, четвертый элемент ИЛИ, выход оторого подключен к первому входу одинадцатого элемента И и является первым 10 олюсом блока управления, выход двенадатого элемента И является вторым полюс м блока управления и соединен с нулевым в одом пятого триггера, единичным входом естого триггера и первым входом тринад- 15 атого элемента И, второй вход которого с единен с первым входом двенадцатого, э емента И, является третьим выходом блок управления и подключен к единичному в ходу шестого триггера, нулевой выход ко- 20 т рого является четвертым выходом блока у равления и подключен к первым входам ч тырнадцатого и пятнадцатого элементов, первый вход шестнадцатого элемента И прдключен к единичному выходу седьмого 25 т иггера, нулевой вход которого подключен к выходу одиннадцатого элемента И, второй в од которого является пятым выходом блок управления и подключен к второму входу д енадцатого элемента И и к единичному 30 в ходу восьмого триггера, единичный вход к торого подключен к выходу тринадцатого э емента И, нулевой выход восьмого триггера является шестым выходом блока управления и подключен к первому входу семнадцатого элемента И, второй вход которого подключен к нулевому выходу пятого триггера, единичный выход которого подключен к второму входу четырнадцатого элемента

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

И блока управления, о т л и ч а ю щ е е с я тем, что, с целью сокращения обьема оборудования, в каждой модели ветви первый и второй полюсы подключены соответственно к первому и второму входам третьего элемента ИЛИ, выход которого подключен к первому входу девятого элемента И, ед ничный выход первого триггера подключ;-.-.1 к второму входу восьмого элемента И, вых,; шестого элемента И подключен к едини:ному входу второго триггера.

1837315

Составитель П,Прокопьев

Техред М,Моргентал Корректор М.Ткач

Редактор

Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101

Заказ 2867 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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