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

), С 06 Е 15/20 РЕЖДЕНИЯ ОПИСАН АВТОРСКОМ йдетельст(5 ния и подключен узла определк входам коблоков сраврых соединещих блоковблоков сравчены к разр вого второго элем выходу генер ке рангов ве столбцов мат нтов И под тора импул ла р егис тра гистров сое первыми вхо ю ныв б шин выходы ицы соедине ующих злеме подключены о игге узла опред и выходами И второй г ны одами соответст выходы которых ГОСУДАРСТВЕННЫЙ КОМИТЕТ СПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ(72) А.И. Багрич и В.Н. Кустов (53) 681.333(088.8)6) Авторское свидетельство СССР 716043, кл. С 06 Р 15/20, 1977.Авторское свидетельство СССР У 1070560, кл. С 06 Р 15/20, 1984. (54)(57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ ГРАФОВ, содержащее узел регистрации, состоящий из счетчика, блока элементов И и сумматора, блок управления, состоящий из двух элементов ИЛИ, триггера и двух элементов И, узел определения длительности яруса, состоящий из группы блоков элементов И и элемента ИЛИ, блок рангов вершин, состоящий из матрицы ь и (где Ь - число вершин граФа) триггеров, группы элементов ИЛИ, первой группы элементов И и группы счетчиков, и генератор импульсов, вход пуска которого является пусковым входом устройства, причем в узле регистрации первый вход и выход блока элементов И соединены соответственно с разрядным выходом счетчика и информационным входом сумматора, в блоке управления выход первого элемента ИЛИ подключен к единичному входу триггера, прямой выход которого соединен с первым входом первого элемента И, а вторые входы к первым входам одноименных элементов И первой группы, выходы которых соединечы с информационными входами одноименных счетчиков группы, установочные входы которых соединены с установочным входом сумматора, первым входом первого элемента И блока управления и являются установочным входом устройетва, выходы элементов ИЛИ блока рангов вершин подключены к входам второго элемента ИЛИ блока управления, выход первого элемента И блока управления соединен с вторыми входами элементов И первой группы блока рангов вершин, о т л и ч а ю щ е е с я ем, что, с целью упрощения устройства и повышения его быстродействия, в узел определения длительности яруса введены группа регистров и группа блоков сравнения, в блок рангов вершин - вторая группа элементов И, пер вые входы которых соединены с управляющим входом блока элементов И узла регистрации, вторым входом первого элемента ИЛИ блока управле к выходу элемента ИЛИения длительности яруса,орого подключены выходыения, первые входы котоы с выходами соответствуюл:моментов И, вторые входыения соединены и подклюдному выходу счетчика узции, выходы и входы реинены соответственно сами блоков элементов Иения длительности ярусаоответствующих элементовппы блока рангов вершин, 1203534вторые входы элементов И второй груп- шин, выход второго элемента ИЛИ блопы блока рангов вершин соединены с ка управления подключен к входу осинверсными входами соответствующих танова генератора импульсов, выход блоков элементов И узла определения первого элемента И блока управления Г,пительности яруса и подключены к вы- соединен с установочным входом счет- ходам соответствующих элементов ИЛИ чика узла регистрации, информационгруппы блока рангов вершин, выходы ный вход которого подключен к выходу элементов И второй группы блока ран- второго элемента И блока управления, гов вершин соединены с нулевыми вхо- первый вход которого соединен с индами триггеров одноименных строк версным выходом триггера блока упматрицы триггеров блока рангов вер- оавленияИзобретение относится к вычислительной технике и может быть применено при решении задач определения длительности поярусного выполнения сетевого графа.Цель изобретения состоит в упрощении устройства и повышении его быстродействия.На чертеже представлена функциональная схема предлагаемого устройства.Устройство содержит узел 1 регистрации, блок 2 управления, узел 3 определения длительности яруса, блок 4 рангов вершин, генератор 5 импульсов, установочный 6 и пусковой 7 входы. Узел 1 содержит блок 8 элементов И, сумматор 9 и счетчик 10, блок 2 - первый 11 и второй 12 элемента ИЛИ, первый 13 и второй 14 элементы И и триггер 15, узел 3 группу регистров 16, группу блоков 17 элементов И, элемент ИЛИ 18, группу блоков 19 сравнения, Блок 4 содержит матрицу и П ( о - число вершин граФа) триггеров 20, группу элементов ИЛИ 21, вторую группу элементов И 22, группу счетчиков 23 и первую группу элементов И 24.Устройство работает следующим образом. В блок 4 заносят информацию о топологии графа путем установки тригге- ров 20 в единичное состояние, соответствующий триггер 20 определяется пересечением строки с номером начального узла ветви и столбца с номером конечного узла, На выходах элементов ИЛИ 21, соответствующих,столбцам начальных узлов, присутствуют низкие потенциалы, посколькув однонаправленном графе без циклови петель ветви в начальные узлы не5 входят,. и триггеры 20 в этих столбцах находятся в нулевом состоянии,В регистры 16 заносят коды длительностей узлов графа,Сигнал начальной установки с вхо 1 О да 6. устройства подается на установочнь 1 е входы сумматора 9, счетчиков 23, обнуляя их и через элементИЛИ 11 на единичный вход триггера15, устанавливая его в единичное15 состояние, С поступлением пусковогосигнала с входа 7 на вход пуска генератора 5 на его выходе появляютсясигчалы, синхронизирующие работуустройства. Единичный потенциал на2 О прямом выходе триггера 15 разрешаетпрохождение первого импульса генератора 5 через элемент И 13 на установочный вход счетчика 10, устанавливая "1" во всех его разрядах, на25 нулевой вход триггера 15 и на управляющие входы элементов И 24. Последующие импульсы генератора5 через элемент И 14, открытый еди- ЗОничным сигналом с инверсного выхода триггера 15, поступают на вычитаюший вход счетчика 10, уменьшая на единицу его код. Этот код поступает на входы блоков 19 для сравнения с содержимым регистров 16. Сравнение производится только с содержимым тех регистров 16, коды которых поступают через блоки 17 элементов И, открытые нулевыми потенциалами с выходов соответствующих элементов ИЛИ 21. Присовпадении кодов в одном из блоков19 сигнал с его выхода через элемент ИЛИ 18 поступает на управляющийвход блока 8 элементов И, разрешаяпрохождение на сумматор 9 со счетчика 10 кода, соответствующего длительности выполнения нулевого яруса, ичерез элемент ИЛИ 11 на вход установки триггера 15 в единичное состояние.Этот же сигнал с выхода блока 19через элементы И 22, которые открытынулевыми потенциалами с выходов элементов ИЛИ 21, сбрасывает в нулевоесостояние триггеры 20 соответствующей строки матрицы и соответствующие 03 534регистры 16. Этим заканчивается определение вершин нулевого ранга и определение длительности яруса, в который ени входят.Аналогичным образом последователь- но определяются вершины следующих рангов и длительности каждого яруса, подсуммируемые к содержимому сумматора 9. 11 роцесс продолжается до 10 тех пор, пока все триггеры 20 небудут обнулены. Тогда нулевые сигналы с выходов элементов ИЛИ 21 поступают на входы элемента ИЛИ 12, нулевой потенциал с выхода которого пос тупает на вход останова генератора 5,