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

Изобретение относится к вычислительной технике и может быть использовано при исследовании параметров сетевых графов, а также при аппаратной реализации в специализированных процессорах макрокоманды определения вершин/ образующих транзитивное и обратное транзитивное замыкание для всех вершин моделируемого графа. I Известно устройство для моделиров ния сетевых графов, содержащее блок управления, первый вход которого сое динен с выходом генератора тактовых импульсов, счетчик импульсов, тригге ры формирователей дуг по числу строк и столбов матричной модели сети, по числу столбцов матричной модели сети элементы ИЛИ,| элементы И, регистрирующие счетчики, схемы сравнения, выходы каждой из которой подключены к нулевым входам триггеров одноименной со столбцом строки матричной модели сети, а первые входы - к Bfcixoдам регистрирующих счетчиков, вторые входы схем сравнения подключены к выходу счетчика импульсов, вход кото рого подключен к выходу блока управления, первые входы элементов И подключены к выходу блока управления, вторые входы элементов И подключены к выходам элементов ИЛИ, входы которых подключены к выходам триггеров формирователей дуг одноименного столбца матричной модели сети ij . Известное устройство обеспечивает только возможность распределения вершин графа по рангам и не позволяет определять вершины, образующие транзитивное и обратное транзитивное замыкания для отдельных вершин моделируемого графа. Наиболее близким к изобретению является устройство для моделирования сетевых графов, содержащее блок управления, первый вход которого Соединен с выходом генератора тактовых импульсов, счетчик импульсов, триггеры формирователей дуг по числу строк и столбцов матричной модели сети,по числу столбцов матричной модели сети первые элементы ИЛИ, элемен ты-И, регистрирующие счетчики, схемы сравнения, входы каждой из которых подключены к нулевым входам триггеров одноименной со столбцом строки матричной модели сети, а первые входы - к выходам регистрирующих счетчиков, вторые входы схем сравнения подключены к выходу счетчика импульсов , вход которого подключен к выходу блока управления, первые входы элементов И подключены к выходу блока управления, вторые входы элементов И подключены к выходам соответствующих первых элементов ИЛИ, входы которых подключены к выходам триггеров формирователей дуг одноименного столбца матричной модели сети, элемент НЕ, элемент И, выход которого через элемент НЕ подключенк управляемому входу блока управления, по числу столбцов матричной модели сети вторые и третьи элементы ИЛИ, триггеры прямого и обратного отображения, управляющие триггеры, по числу строк и столбцов матричной модели сети первые и вторые элементы И, информационные входы каждого из которых подключены к входу соответствующего триггера формирователя дуг, входы каждого второго элемента ИЛИ подключены к выходам первых элементов И одноименного столбца матричной модели сети, а выходы - к входам соответствуюцих триггеров прямого отображения, выходы которых подключены к управляемым входам первых элементов И одноименной строки матричной модели сети, входы каждоготретьего элемента ИЛИ подключены к выходам вторых элементов И одноименной строки матричной модели сети, а выходы - к входам соответствующих триггеров обратного Отображения, выходы которых подключены к управляемым входам вторых элементов И одноименного столбца матричной модели сети, входы каждого управляющего триггера подключены к выходам соответствующей схемы сравнения, а выходы - к одноименным входам первого элемента И 2 . Недостатком известного устройства является низкое быстродействие при определении вершин, образующих транзитивное и обратное транзитивное замыкания для всех вершин моделируемого графау из-за необходимости дополнительного сбрасывания триггеров прямого и обратного отображения, а также установки триггеров очередной вершины в единичное состояние. Целью изобретения явлйется повышение быстродействия. Поставленная цель достигается тем, что в устройство для моделирования сетевых графов, содержащее матричную модель графа, ij -и узел которой включает триггер, первый и второй элементы И, причем выход триггера подключен к первым входам первого и второго элементов И, первую и вторую группы элементов ИЛИ, первую и вторую группы триггеров, элемент И, генератор тактовых импульсов, счетчик, причем выход i -го (, ...,п) триггера первой группы подключен ко вторым входам первых элементов И i-и строки матричной модели графа, выход -го триггера второй группы соединен со вторыми входами вторых элементов И -го столбца матричной модели графа, выход первого

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

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

Устройство .содержит матричную модель 1 графа, триггеры 2 (формирователей дуг), первые 3 и вторые 4 элементы И, по числу столбцов матричной модели графа первые 5 j, ..., 5 п и вторые 6f, ..., 6п элементы ИЛИ, первые ,l , , . . , 7 и и вторые 8 I, . . ., 8 ц триггеры, дешифратор 9, счетчик 10, элемент 11 задержки, элемент И 12, генератор 13 тактовых импульсов, вход 14 запуска, выходы 15, ..., 15,1, 16i , . .., 1б„ и 17. .

Матричная модель 1 графа представляет собой матрицу п ХЦ, где п - максимальное число вершин в графе, однородных ячеек в составе триггера 2, первого 3 и второго 4 элементов И.

Устройство для моделирования сетевых графов работает следующим образом.

Первоначально в нулевое положение, устанавливаются все триггеры 7, 8 и счетчик 10. Информация о топологии моделируемого графа заносится путем установки соответствующих триггеров 2 в единичное состояние. Соответствующий триггер 2jj (i,j l, ...,n) формирователя дуги опред еляется пересечением -и строки ( i - номер начальной вершины моделируемой ветви грифа) с J-м столбцом (j - номер конечной вершины моделируемой ветви графа).

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

на соответствующие триггеры 2 и обнуления триггеров 7 и 8, а также счетчика 10. После подачи управляющего сигнала на вход 14 импульсы с генератора 13 начинают поступать через элемент И 12 на вход счетчика 10 и элемента .11 задержки. С выхода счетчика 10 код (первоначально 0...01) поступает на вход дешифратора 9, на выходе которого возбуждается только одна шина (вначале первая), после чего единичный сигнал через элементы ИЛИ 5 и 6 перебрасывает в единичное состояние соответствующие триггеры 7 и В (вначале триггеры 7 и 8с) .

Единичный сигнал с выхода триггера 7 (,-,П ) поступает на вторые входы элементов. И 3 i -и строки матричной модели, вторые входы которых подсоединены к выходу одноименного триггера 2, а выход - к одноименному входу элемента ИЛИ 5j, (j-l,...,n) единичным сигналом с выхода которого устанавливается в единичное состояние триггер 7J, и т.д. Так определяются все вершины, образующие транзитивное замыкание для 1 -и вершины. Таким вершинам соответствует единичное состояние тригеров 7, и соответствунвдий код снимается с выходов 15 устройства. В этом коде единица в j -м разряде соответствует номеру вершины, входящей в транзитивное замыкание для jj-й вершины моделируемого графа.

Одновременно единичный сигнал с выхода триггера 8| (-1,.,,,п поступает на вторые входы элементов И 4 I -го столбца матричной модели, вторые входы которых подсоединены к выходу одноименного триггера 2, а выход - к одноименному входу элемента б (j-l,...,n), единичным сигналом с выхода которого устанавливается в единичное состояние триггер 8J, и т.д. Так определяются все вершины, образующие обратное транзитивное замыкание для -и вер шины. Таким вершинам соответствует единичное состояние триггеров 8, а соответствующий код снимается с выходов 16 устройства.

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

На вход счетчика 10 поступает оч едной импульс, и транзитивное и обратное транзитивное замыкания определяются для второй вершины моделируемого графа и так далее, до тех пор, пока на счетчике не зафиксируется код числа И, после чего с приходом очередного импульса счетчик 10 переполняется, о чем свидетельствует единичный сигнал наBbf-; ходе 17 устройства.

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

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

i«r;.. js