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

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

Цель изобретения состоит в упрощении устройства и повышении его быстродействия.

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

Устройство содержит узел 1 регисрации, блок 2 управления5 узел 3 определения длительности яруса, блок 4 рангов вершин, генератор 5 импульсов, установочный 6 и пусковой 7 входы. Узел 1 содержит блок 8 ;)лементов И, сумматор 9 и счетчик 1 блок 2 - первьш 11 и второй 12 элемента ИЛИ, первый 13 и второй 14 элементы И и триггер 15, узел 3 - группу регистров 16, группу блоков 17 элементов И, элемент ИЛИ 18, группу блоков 19 сравнения. Блок 4 содерзкит матрицу h h (и - число вершин графа) триггеров 20, группу элементов ИЛИ 21, вторую группу эле pieHTOB И 22, группу счетчиков 23 и первую группу элементов И 24.

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

I

В блок 4 заносят информацию о топологии графа путем установки тригг ров 20 в единичное состояниеj соответствующий триггер 20 определяется пересечением строки с номером начального узла ветви и столбца с номером конечного узла о На выходах элементов ИЛИ 21, соответствуюш ах

03534

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

|столбцам начальных узлов, присутствуют низкие потенциалы, поскольку в однонаправленном графе без циклов и петель ветви в начальные узлы не

входят, и триггеры 20 в этих столбцах находятся в нулевом состоянии. В регистры 16 заносят коды длительностей узлов графа.

Сигнал начальной установки с входа 6, устройства подается на установочные входы сумматора 9, счетчи- коБ 23, обнуляя их, и через элемент ИЛИ 11 на единичный вход триггера 15; устанавливая его в единичное

состояние. С поступлением пускового сигнала с входа 7 на вход пуска генератора 5 на его выходе появляются сигналы, синхронизирующие работу устройства. Единичный потенциал.на

прямом выходе триггера 15 разрешает прохождение первого импульса генератора 5 через элемент И 13 на уста- новочньй вход счетчика 10, устанавливая 1 во всех его разрядах, на

нулевой вход триггера 15 и на управляющие входы элементов И 24.

Последующие импульсы генератора 5 через элемент И 14, открытый единичным сигналом с инверсного выхода триггера 15, поступают на вычитающий вход счетчика 10, уменьшая на единицу его код. Этот код поступает на входы блоков 19 для сравнения с содер;кимым регистров 16. Сравнение

производится только с содержимым тех регистров 16, коды которых поступают через блоки 17 элементов И, открытые нулевьпчи потенциалами с выходов соответствующих элементов ИЛИ 21. При

1

совпадении кодов в одном из блоков 19 сигнал с его выхода через элемент ИЛИ 18 поступает на управляющий вход блока 8 элементов И, разрешая прохождение на сумматор 9 со счетчика 10 кода, соответствующего длительности выполнения нулевого яруса, и через элемент ИЛИ 11 на вход установки триггера 15 в единичное состояние Этот же сигнал с выхода блока 19 через элементы И 22, которые открыты нулевыми потенциалами с выходов элементов ИЛИ 21, сбрасывает в нулевое состояние триггеры 20 соответствующей строки матрицы и соответствующие

03534

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

5 Аналогичным образом последователь - но определяются вершины следующих рангов и длительности калодого яруса, подсуммируемые к содержимому сумматора 9. Процесс продолжается до

10 тех пор, пока все триггеры 20 не

будут обнулены. Тогда нулевые сигналы с выходов элементов ИЛИ 21 посту-. пают на входы элемента ИЛИ 12, нулевой потенциал с выхода которого пос15 тупает на вход останова генератора 5.