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

 

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

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

РЕСПУБЛИК

„„SU„„.12035 4 д1„. С 06 F 15/20 ф(«с !

/ ю

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

К АВТОРСКОМУ СВйДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (2i) 3763203/24-24 (22) 25.06.84 (46) 07.01.86. Бюл. И- 1 (72) А.И. Багрич и В.Н. Кустов (53) 681.333(088.8) (56) Авторское свидетельство СССР

N- 716043, кл. G 06 F 15/20, 1977.

Авторское свидетельство СССР

¹ 1070560, кл. С 06 F 15/20, 1984. (54)(57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЪ|Х ГРАФОВ, содержащее узел регистрации, состоящий из счетчика, блока элементов И и сумматора, блок управления, состоящий из двух элементов ИЛИ, триггера и двух элементов И, узел определения длительности яруса, состоящий из группы блоков элементов И и элемента ИЛИ, блок рангов вершин, состоящий из матрицы и (где h — число вершин графа) триггеров, группы элементов ИЛИ, первой группы элементов И и группы счетчиков, и генератор импульсов, вход пуска которого является пусковым входом устройства, причем в узле регистрации первый вход и выход блока элементов И соединены соответственно с разрядным выходом счетчи— ка и информационным входом сумматора, в блоке управления выход первого элемента ИЛИ подключен к единичному входу триггера, прямой выход которого соединен с первым входом первого элемента И, а вторые входы первого и второго элементов И подключены к выходу генератора импульсов, в блоке рангов вершин выходы триггеров столбцов матрицы соединены с, входами соответствующих элементов ИЛИ, выходы которых подключены к первым входам одноименных элементов И первой группы, выходы которых соединены с информационными входами одноименных счетчиков группы, установочные входы которых соединены с установочным входом сумматора, первым входом первого элемента И блока управления и являются установочным входом устройетва, выходы элементов ИЛИ блока рангов вершин подключены к входам второго элемента ИЛИ блока управления, выход первого элемента И блока управления соединен с вторыми входами элементов И первой группы блока рангов вершин, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства и повышения его быстродействия, в узел определения длительности яруса введены группа регистров и группа блоков сравнения, в блок рангов вершин — вторая группа элементов И, первые входы которых соединены с управляющим входом блока элементов И узла регистрацич, вторым входом первого элемента ИЛИ блока управления и подключены к выходу элемента ИЛИ узла определения длительности яруса, к входам которого подключены выходы блоков сравнения, первые входы которых соединены с выходами соответствующих блоков эл:моментов И, вторые входы блоков сравнения соединены и подключены к разрядному выходу счетчика узла регистрации, выходы и входы регистров соединены соответственно с первыми входами блоков элементов И узла определения длительности яруса и выходами соответствующих элементов

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

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

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

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

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

i7 элементов И, элемент ИЛИ 18, группу блоков 19 сравнения. Блок 4 содержит матрицу И П (И вЂ” число вершин графа) триггеров 20, группу элементов ИЛИ 21, вторую группу элементов И 22, группу счетчиков 23 и первую группу элементов И 24.

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

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

5 входят,. и триггеры 20 в этих столбцах находятся в нулевом состоянии.

В регистры 16 заносят коды длительностей узлов графа.

Сигнал начальной установки с входа 6. устройства подается на установочные входы сумматора 9, счетчиков 23,. обнуляя их„ и через элемент

ИЛИ 11 на единичный вход триггера

15, устанавливая его в единичное

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

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

Последующие импульсы генератора

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

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

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

0353

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

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

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