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

 

Изобретение относится к вычислительной технике и может быть использовано в устройствах для исследования сетевых графов . Цель изобретения - расширение функциональных возможностей устройства за счет определения наличия циклов в графе и упорядочивания его вершин в соответствии с правилом предшествования. Устройство содержит матрицу 1 триггеров 2, первую группу элементов И 7, группу счетчиков 8, элемент И 10, вычитаюший счетчик 11, генератор импульсов 13. Кроме того, в устройство введены первая 4 и вторая 6 группы триггеров, вторая группа элементов И 5, груп па элементов задержки 9, группа элементов ИЛИ-НЕ 3, элемент И-НЕ 14, элемент НЕ 12. 1 ил.

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

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

РЕСПУБЛИК дц 4 G 06 F 15 20

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

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4161151/24-24 (22) 04.10.86 (46) 23.03.88. Бюл. № 11 (72) А. B. Герасименко, В. П. Неверов, О. И. Русанова, С. Н. Сластихин и В. А. Титов (53) 681.325 (088.8) (56) Авторское свидетельство СССР № 1005066, кл. G 06 F 15/20, 1984.

Авторское свидетельство СССР № 716043, кл. G 06 F 15/20, 1980. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ ГРАФОВ (57) Изобретение относится к вычислительной технике и может быть использовано

„„SU,» 1383389 А 1 в устройствах для исследования сетевых графов. Цель изобретения — расширение функциональных возможностей устройства за счет определения наличия циклов в графе и упорядочивания его вершин в соответствии с правилом предшествования. Устройство содержит матрицу 1 триггеров 2, первую группу элементов И 7, группу счетчиков 8, элемент И 10, вычитающий счетчик 11, генератор импульсов 13. Кроме того, в устройство введены первая 4 и вторая 6 группы триггеров, вторая группа элементов И 5, груп па элементов задержки 9, группа элементов ИЛИ вЂ” НЕ 3, элемент И вЂ” НЕ 14, элемент НЕ 12. 1 ил.

1383389

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

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

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

Устройство содержит матрицу 1 триггеров

2, группу элементов ИЛИ вЂ” НЕ 3,...,3ы, первую группу триггеров 4i,".,4, вторую группу элементов И 5ь...,5, вторую группу триггеров 6i,...,6i, первую группу элементов И 7i,..., 7i, группу счетчиков 8i,...,8i; группу элементов 9,...,9к задержки, элемент И 10, вычитающий счетчик Il, элемент НЕ 12, генератор 13 импульсов, элемент И вЂ” НЕ 14, выход 15, на котором появляется сигнал окончания работы устройства, вход 16, где при наличии сигнала на выходе 15 единичный сигнал означает наличие цикла (циклов) в графе, а нулевой — отсутствие циклов в графе, пусковой вход 17.

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

Первоначально в матрицу 1 заносится информация о топологии моделируемого графа. При этом триггеры 2, моделирующие ветви графа, устанавливаются в единичное состояние. Соответствующий триггер 2 определяется пересечением строки с номером, равным номеру ее начального узла моделируемой ветви, и столбца с номером, равным номеру ее конечного узла. В вычитающий счетчик 11 заносится код числа (вершин в графе), а счетчики 8, триггеры 6 и 4 устанавливаются в нулевое состояние. При этом информация о топологии моделируемого графа заносится в произвольном порядке.

При таком занесении исходной информации на выходе элемента ИЛИ вЂ” НЕ 3; (i =

1... N), в одноименном столбце которого все триггеры 2;; (j = 1... N) находятся в нулевом состоянии (начальная вершина), появляется высокий потенциал, который устанавливает триггер 4 в единичное состояние. В том случае, если начальных вершин несколько, то в единичное состояние устанавливаются соответствующие триггеры.

С появлением пускового сигнала на входе 17 устройства элемент И 10 обеспечивает прохождение счетных импульсов с выхода генератора 13 на первые входы элементов И 7, вход счетчика 11 и входы эле5

2 ментов И 5, так как на втором входе элемента И 10 присутствует единица счетчика 11 — сигнал отсутствия на счетчике 11 нулевого кода (при наличии на счетчике 11 какого-либо кода на выходе 15 устройства будет нулевой сигнал, а на выходе элемента НЕ 12 — единичный) . Первый счетный импульс проходит через все элементы И 7 на входы счетчиков 8, так как вторые входы элементов И 7 подсоединены к инверсным выходам соответствующих триггеров 6, находящихся после занесения исходной информации в нулевбм состоянии, Одновременно единичный сигнал с выхода элемента И 10 подается на первые входы всех элементов И 5, вторые входы которых подсоединены к прямым выходам соответствующих триггеров 4, а последующие К-е входы (К=З...N, N+I).

Каждый элемент И 5; имеет i+1 входов, причем jй вход (где j = 3,..., i+I) для элемента И 51, любого элемента И 51 соединен с инверсным выходом триггера 41 — 2.

При таком соединении сигнал с выхода элемента 10 проходит только через один из элементов И 5 (на S-вход соответствующего триггера 6) и устанавливает его в единичное состояние.

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

Единичный сигнал с выхода элемента И

5 1 устанавливает в единичное состояние триггер 6.i, инверсный выход которого подсоединен к второму входу одноименного элемента И 71, запрещая тем самым прохождение последующих счетных импульсов на вход счетчика 81. Единичный сигнал с прямо го выхода триггера 6.1 через элемент 9л за держки поступает íà R-вход триггера 4.i, на (N+I)-й вход элемента ИЛИ вЂ” НЕ Зл, на R-входы триггеров 2 i-й строки матрицы 1. Триггер 4л переходит в нулевое состояние. Кроме того, единичный сигнал с прямого выхода триггера 6.1 (i = I...N) поступает на i-й вход элемента И вЂ” НЕ 14.

Величина задержки сигнала элементом 9 и частота следования сигналов генератора 13 выбираются такими, чтобы очередной импульс генератора 13 поступал на входы элементов И 7 и 5 после того, как соответствующий триггер 6.1 перебросится в единичное состояние, а триггер 4л установится в нулевое состояние.

Одновременно счетный импульс с выхода генератора 13 поступает через элемент И 10 на вход вычитающего счетчика 11.

С приходом очередного тактового импульса работа устройства происходит анало1383389

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

Составитель О. Греч кина

Редактор Н.Лазаренко ТехредИ. Верес Корректор И. Муска

Заказ 915/49 Тираж 704 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 гично, т.е. устанавливается в единичное состояние очередной триггер 6.1, сбрасывается в нулевое состояние триггер 4л, увеличивается содержимое счетчиков 8 (кроме счетчика 8.1) и триггеры 2 одноименной соответствующей строки матрицы 1 сбрасываются в нуль.

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

НЕ 12 осуществляется прекращение подачи сигналов с выхода генератора 13 через элемент И 10.

В результате, при отсутствии циклов в графе на счетчиках 8 фиксируются коды номеров вершин, упорядоченных в соответствии с правилом предшествования.

При наличии циклов в графе задача упорядочивания вершин графа в соответствии с правилом предшествования не имеет смысла, и в этом случае вместе с сигналом на выходе 15 появляется также единичный сигнал и на выходе 16 элемента И вЂ” HE

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

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

НЕ, вход которого соединен с выходом признака равенства нулю вычитающего счетчика, а выход соединен с вторым входом элемента И, выход которого соединен с первыми входами элементов И второй группы, выходы которых соединены с входами установки в «1» соответствующих триггеров второй группы, инверсные выходы которых соединены с вторыми входами соответствующих элементов И первой группы, а прямые вы ходы триггеров второй группы соединены с входами соответствующих элементов задержки группы, входами соответствующих элементов ИЛИ вЂ” НЕ группы, с входами установ20 ки в «О» триггеров соответствующей строки матрицы триггеров и соответствующим входом элемента И вЂ” НЕ, выход которого является выходом признака существования циклов в графе устройства, входы i-ro

25 элемента ИЛИ вЂ” НЕ грх ппы соединены с прямыми выходами триггеров i-ro столбца матрицы триггеров, выходы элементов ИЛИ—

НЕ группы соединены с входами установки в «1» соответствующих триггеров первой группы, входы установки в «О» которых соединены с выходами соответствующих элементов задержки группы, а прямые выходы триггеров первой группы соединены с вторыми входами элементов И второй группы, j e входы (j=3,...,N, где 11 — размер матрицы триггеров) соединены соответственно с инверсными выходами (j — 1) -x триггеров первой группы, третий вход элемента И является входом признака разрешения работы устройства, а выход признака равенства нулю вычитающего счетчика является выходом признака окончания цикла работы

40 устройства, выходы счетчиков группы являются информационными выходами устрой