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

(51) 4 6 06 Р 15 2 ТЕНИЯ ИСАНИЕ ИДЕТЕЛЬС ВТОРСКО Неверои В. А. Т А ельОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОНИЯ СЕТЕВЫХ ГРАФОВ(57) Изобретение относится к вычислиной технике и может быть использо в устройствах для исследования сетевых графов. Цель изобретения - расширение функциональных возможностей устройства за счет определения наличия циклов в графе и упорядочивания его вершин в соответствии с правилом предшествования. Устройство содержит матрицу 1 триггеров 2, первую группу элементов И 7, группу счетчиков 8, элемент И 10, вычитающий счетчик 11, генератор импульсов 13. Кроме того, в устройство введены первая 4 и вторая 6 группы триггеров, вторая группа элементов И 5, груп па элементов задержки 9, группа элементов ИЛИ - НЕ 3, элемент И - НЕ 14, элемент НЕ 12. 1 ил.40 45 50 55 Изобретение относится к вычислительнойтехнике и может быть использовано в устройствах исследования сетевых графов, а также в процессорах при аппаратной реализации микрокоманды упорядочивания вершин графа в соответствии с правилом предшествования с одновременной проверкой наличия циклов в графе.Целью изобретения является расширение функциональных возможностей устройства за счет определения наличия циклов в графе и упорядочивании его вершин в соответствии с правилом предшествования,На чертеже приведена структурная схема устройства.Устройство содержит матрицу 1 триггеров 2, группу элементов ИЛИ - НЕ 33 ы, первую группу триггеров 414, вторую группу элементов И 5 ь,5, вторую группу триггеров бь,б, первую группу элементов И 71 7, группу счетчиков 818; группу элементов 919 к задержки, элемент И 10, вычитающий счетчик 11, элемент НЕ 12, генератор 13 импульсов, элемент И - НЕ 14, выход 15, на котором появляется сигнал окончания работы устройства, вход 16, где при наличии сигнала на выходе 15 единичный сигнал означает наличие цикла (циклов) в графе, а нулевой - отсутствие циклов в графе, пусковой вход 17.Устройство работает следующим образом.Первоначально в матрицу 1 заносится информация о топологии моделируемого графа. При этом триггеры 2, моделирующие ветви графа, устанавливаются в единичное состояние. Соответствующий триггер 2 определяется пересечением строки с номером, равным номеру ее начального узла моделируемой ветви, и столбца с номером, равным номеру ее конечного узла. В вычитающий счетчик 11 заносится код числа (вершин в графе), а счетчики 8, триггеры 6 и 4 устанавливаются в нулевое состояние. При этом информация о топологии моделируемого графа заносится в произвольном порядке. При таком занесении исходной информации на выходе элемента ИЛИ - НЕ 3; (1 =1 Х), в одноименном столбце которого все триггеры 2 (1 = 1 М) находятся в нулевом состоянии (начальная вершина), появляется высокий потенциал, который устанавливает триггер 4 в единичное состояние. В том случае, если начальных вершин несколько, то в единичное состояние устанавливаются соответствующие триггеры.С появлением пускового сигнала на входе 17 устройства элемент И 10 обеспечивает прохождение счетных импульсов с выхода генератора 13 на первые входы элементов И 7, вход счетчика 11 и входы эле 5 10 5 20 25 30 35 2ментов И 5, так как на втором входе элемента И 10 присутствует единица счетчика 11 - сигнал отсутствия на счетчике 11 нулевого кода (при наличии на счетчике 11 какого-либо кода на выходе 15 устройства будет нулевой сигнал, а на выходе элемента НЕ 12 - единичный) . Первый счетный импульс проходит через все элементы И 7 на входы счетчиков 8, так как вторые входы элементов И 7 подсоединены к инверсным выходам соответствующих триггеров 6, находящихся после занесения исходной информации в нулевбм состоянии, Одновременно единичный сигнал с выхода элемента И 1 О подается на первые входы всех элементов И 5, вторые входы которых подсоединены к прямым выходам соответствующих триггеров 4, а последующие К-е входы (К=ЗМ, И+1).Каждыйэлемент И 5; имеет 1+1 входов, причем 1-й вход (где 1 = 3 1+1) для элемента И 51, любого элемента И 51 соединен с инверсным выходом триггера 4 1 - 2. При таком соединении сигнал с выхода элемента 10 проходит только через один из элементов И 5 (на 5-вход соответствующего триггера 6) и устанавливает его в единичное состояние.Если в единичном состоянии находятся несколько триггеров 4, единичный сигнал появляется только на выходе одного, с меньшим порядковым номером, элемента И 5 благодаря тому, что нулевой сигнал с инверсного выхода триггеров 4, находящихся в единичном состоянии, запрещает прохождение сигнала с выхода элемента И 10 через элементы И 5 последующих столбцов,Единичный сигнал с выхода элемента И 5 1 устанавливает в единичное состояние триггер 6.1, инверсный выход которого подсоединен к второму входу одноименного элемента И 71, запрещая тем самым прохождение последующих счетных импульсов на вход счетчика 81. Единичный сигнал с прямо го выхода триггера 6.1 через элемент 91 за держки поступает на К-вход триггера 4.1,на ( И+1) -й вход элемента ИЛИ - НЕ 3 1, на К-входы триггеров 2 1-й строки матрицы 1. Триггер 41 переходит в нулевое состояние. Кроме того, единичный сигнал с прямого выхода триггера 6.1 (1 = 1 Х) поступает на 1-й вход элемента И - НЕ 14.Величина задержки сигнала элементом 9 и частота следования сигналов генератора 13 выбираются такими, чтобы очередной импульс генератора 13 поступал на входы элементов И 7 и 5 после того, как соответствующий триггер 6,1 перебросится в единичное состояние, а триггер 4 л установится в нулевое состояние.Одновременно счетный импульс с выхода генератора 13 поступает через элемент И 10 на вход вычитающего счетчика 11.С приходом очередного тактового импульса работа устройства происходит анало1383389 формула изобретения ства. Составитель О. Гречл кина Редактор Н.Лазаренко ТехредИ. Верес Корректор И. Муска Заказ 9549 Тираж 704 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж - 35, Раушская наб., д. 45 Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4гично, т.е. устанавливается в единичное состояние очередной триггер 6.1, сбрасывается в нулевое состояние триггер 4 1, увеличивается содержимое счетчиков 8 (кроме счетчика 8.1) и триггеры 2 одноименной соответствующей строки матрицы 1 сбрасываются в нуль.Вычислительный процесс продолжается до тех пор, пока код на вычитающем счетчике 11 не станет нулевым, после чего единичный сигнал, свидетельствующий об окончании работы, появляется на выходе 15 устройства. Этим же сигналом через элемент НЕ 12 осуществляется прекращение подачи сигналов с выхода генератора 13 через элемент И 10.В результате, при отсутствии циклов в графе на счетчиках 8 фиксируются коды номеров вершин, упорядоченных в соответствии с правилом предшествования.При наличии циклов в графе задача упорядочивания вершин графа в соответствии с правилом предшествования не имеет смысла, и в этом случае вместе с сигналом на выходе 15 появляется также единичный сигнал и на выходе 16 элемента И - НЕ 14, свидетельствующий о наличии циклов в графе. При этом вершинам, образующим циклы в графе, а также вершинам, информационно зависящим от вершин цикла, соответствуют максимальный код в счетчиках 8. Устройство для моделирования сетевых графов, содержащее матрицу триггеров, группу счетчиков, первую группуэлементов И, вычитающий счетчик, элемент И и генератор импульсов, выход которого соединен с первым входом элемента И, выход которого соединен со счетным входом вычитающего счетчика и первыми входами элементов И первой группы, выходы которых соединены со счетчиками входов соответствующих счетчиков группы, отличающееся тем, что, с целью расширения функциональных возможностей.устройства за счет определения наличия циклов в графе и упорядочивания вершин в соответствии с правилом предшествования, в него введены первая и вторая группы триггеров, вторая группа элементов И, группа элементов задержки, группа элементов ИЛИ - НЕ, элемент И - НЕ и элемент НЕ, вход которого соединен с выходом признака равенства нулю вычитающего счетчика, а выход соединен с вторым входом элемента И, выход которого соединен с первыми входами элементов И второй группы, выходы которых соединены с входами установки в 1 соответствующих триггеров второй группы, инверсные выходы которых соединены с вторыми входами соответствующих элементов И первой группы, а прямые вы ходы триггеров второй группы соединены с входами соответствующих элементов задержки группы, входами соответствующих элементов ИЛИ - НЕ группы, с входами установ ки в О триггеров соответствующей строкиматрицы триггеров и соответствующим входом элемента И - НЕ, выход которого является выходом признака существования циклов в графе устройства, входы 1-го 25элемента ИЛИ - НЕ грл ппы соединены с прямыми выходами триггеров 1-го столбца матрицы триггеров, выходы элементов ИЛИ - НЕ группы соединены с входами установки в 1 соответствующих триггеров первой группы, входы установки в О которых соединены с выходами соответствующих элементов задержки группы, а прямые выходы триггеров первой группы соединены с вторыми входами элементов И второй группы, 1-е входы (1=3М, где Х - размер матрицы триггеров) соединены соответственно с инверсными выходами (1 - 1)-х триггеров первой группы, третий вход элемента И является входом признака разрешения работы устройства, а выход признака равенства нулю вычитающего счетчика является выходом признака окончания цикла работы 40 устройства, выходы счетчиков группы являются информационными выходами устрой