Устройство для моделирования сетевых графов Советский патент 1988 года по МПК G06F15/173 

/7

(Л

00 00

со со

00

г

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

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

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

Устройство содержит матрицу 1 триггеров 2, группу элементов ИЛИ-НЕ 3b...,3N, первую группу триггеров 4i,...,4N, вторую групцу элементов И 5i,...,5N, вторую группу триггеров 6i,...,6N, первую группу элементов И 7,..., 7N, группу счетчиков 8i,...,8N; группу элементов 9i,...,9N задержки, элемент И 10, вычитающий счетчик II, элемент НЕ 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 и входы эле0

0

5

0

5

0

5

0

5

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

Каждый элемент И 5,- имеет i-|-l входов, причем j-й вход (где j 3,..., i-f 1) для элемента И 5.1, любого элемента И 5.i соединен с инверсным выходом триггера 4.i-2. При таком соединении сигнал с выхода элемента 10 проходит только через один из элементов И 5 (на S-вход соответствующего триггера 6) и устанавливает его в единичное состояние.

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

Единичный сигнал с выхода элемента И 5.1 устанавливает в единичное состояние триггер 6.i, инверсный выход которого подсоединен к второму входу одноименного элемента И 7.i, запрещая тем самым прохождение последующих счетных импульсов на вход счетчика 8.i. Единичный сигнал с прямого выхода триггера 6.i через элемент 9.i задержки поступает на R-вход триггера 4.i, на (Ы4-1)-й вход элемента ИЛИ-НЕ 3.i, на R-входы триггеров 2 i-й строки матрицы 1. Триггер 4.i переходит в нулевое состояние. Кроме того, единичный сигнал с прямого выхода триггера 6.1 (i 1...N) поступает на i-й вход элемента И - НЕ 14.

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

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

С приходом очередного тактового импульса работа устройства происходит аналогично, т.е. устанавливается в единичное состояние очередной тр-иггер 6.1, сбрасывается в нулевое состояние триггер 4.1, увеличивается содержимое счетчиков 8 (кроме счетчика 8.1) и триггеры 2 одноименной соответствуюидей строки матрицы 1 сбрасываются в нуль.

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

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

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

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

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

5

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

5 элемента ИЛИ-НЕ группы соединены с прямыми выходами триггеров i-ro столбца матрицы триггеров, выходы элементов ИЛИ- НЕ группы соединены с входами установки в «1 соответствующих триггеров первой группы, входы установки в «О кото0 рых соединены с выходами соответствующих элементов задержки группы, а прямые выходы триггеров первой группы соединены с вторыми входами элементов И второй группы, j-e входы (,...,N, где N - размер матрицы триггеров) соединены соответствен5 но с инверсными выходами (j - 1)-х триггеров первой группы, третий вход элемента И является входом признака разрешения работы устройства, а выход признака равенства нулю вычитающего счетчика является выходом признака окончания цикла работы

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

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