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

(21) 4 (22) 16 2 фф 2 фУ ОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ВТОРСКОМУ СВИДЕТЕЛЬСТ 210274/24-243.03.87(56) Авторское свидетельство СССР У 1065858, кл. С 06 Р 15/20, 1982.Авторское свидетельство СССР У 1251099, кл. С 06 Р 15/20, 1984. (54) УСТРОЙСТВО ДЛЯ 110 ДЕЛИРОВА 11 ИЯ СЕТЕВЫХ ГРАФОВ(57) Изобретение относится к вычислительной технике и может быть использовано для исследования парамет-. ров надежности систем, описываемых графами. Целью изобретения является повышение надежности устройства, Устройство содержит блок 38 определения инцидентных дуг графа, блок 39 определения связных вершин графа, преобразователь 40 кода, блок 41 приоритетов, блок 42 выбора максимального кода, первый блок 43 регистров,блок 44 умножителей, второй блок 45регистров, тактовые входы 46 и 47устройства, входы 48 и 49 синхронизации, входы 50 опроса устройства,выходы 51 признаков принадлежностивершин пути с максимальным произведением весов дуг устройства. Передначалом работы исключают все дуги,входящие в начальную вершину графа,и топологию полученного графа заносяв блок 38. Обнуляют Н-й регистр блок45 и заносят коды-числа "1" в остальные регистры. На входы 46-49 устройства подают сигналы синхронизациив соответствии с временной диаграмной работы устройства, при этом вблоке 39 формируется путь с макси-.мальным произведением весов ветвей.6 ил.Изобретение относится к вычислительной технике и может быть исполь"зовано для исследования параметровнадежности сложных систем,Целью изобретения является повы 5шение надежности устройства.На фиг. 1 представлена функциональная.схема предлагаемого устройства; на фиг. 2 - граф со взвешенными 10дугами, на примере которого рассматривается работа устройства; .нафиг. 3 - функциональная схема блокаформирования пути; на фиг. 4 - функциональная схема блока выбора макси. мального кода; на фиг. 5 - структураустройства; на фиг. 6 - временнаядиаграмма работы устройства.Устройство содержит (фиг. 1) генератор 1 импульсов, триггер 2, счетчик 3, первый 4 и второй 5 элементыИ, первый 6 и второй 7 распределители уровней, матрицу 8 КИ (К = 1,В - 1, И = 3, , В, В - число вершин графа) моделей дуг, которые в 25первой строке матрицы выполнены ввиде регистров 9 памяти, а в остальных строках - в виде сдвигающихсярегистров 10, группу элементов ИЛИ 11,блок 12 формирования пути, первую 13 30и вторую 14 группы регистров, группусумматоров 15, элемент 16 задержки;блок 17 выбора максимального кода.Блок 12 содержит (фиг. 3) регистр18, группу триггеров 19 ,3519 , первую 20, вторую 21 и1третью 22 группы элементов И, первую23 и вторую 24 группы элементов ИЛИ,группу опросных входов 25 з, , 25,группу входов 26, 26 , позиционного кода, вход 27 поиска вершин.Узлы в виде одноименных элементовИ 21, 22, 20 и триггера 19 образуютнапдиагональную матрицу размерностьюКМ. Блок 17 содержит (фиг. 4) группУэлементов ИЛИ 28, группу элементовНЕ 29, группу поразрядных узлов30,.30 р (Р - разрядность кодоввходных чисел), состоящих каждый изблоков 31 переноса, каждый из которыхсостоит из элемента ИЛИ 32 и одногоили нескольких элементов И 33, груп.пу информационных входов 3434 , 34 , 34 ар, синхронизирующий вход 35, выходы 36,36 максимального числа, выходы37 , 37позиционного кода.В блоке 17 каждый иэ элементов ИЛИ-НЕразбит на элемент ИЛИ 28 и элемент НЕ 29, чтобы обеспечить выдачу максимального числа в прямом коде, атретьи входы элементов И 33 последнего поразрядного узла 30 р объединены и являются синхронизирующим входомблока 17 с тем, чтобы выдача позиционного кора производилась лишь вовремя прохождения импульсов синхронизации. Блок 12 выполнен аналогичноодноименному блоку прототипа,В общем виде устройство можетбыть представлено совокупностью блока 38 определения идентичных дуг графа, блока 39 определения связныхвершин графа, преобразователя 40 кода, блока 41 приоритетов, блока 42выбора максимального кода, первогоблока 43 реГистров, блока 44 умножителей и второго блока 45 регистров.Кроме того, на фиг. 5 обозначеныпервый тактовый вход 46 устройства,второй тактовый вход 47 устройства,входы 48 синхронизации первой группыустройства, входы 49 синхронизациивторой группы устройства, входы 50опроса К-ой вершины графа устройства, выходы 51 признаков принадлежности вершин графа пути с максимальнымпроизведением весов дуг устройства.В исходном статическом состоянииобнуляются распределители 6 и 7,регистры 13 и 14 (кроме 14), сумматоры 15, тригеры 19 (кроме 19), Вединичное состояние устанавливаютсятриггеры 2, 19, в регистр 14 зано"сится .вес дуги между первой и второйвершинами графа, а веса остальныхего дуг заносятся в соответствующиерегистры 9 и 10 согласно матрицесмежности графа. Устройство работает циклами следующим образом,С подачей пускового сигнала генератор 1 начинает выдачу импульсов,первый из которых проходит черезоткрытый элемент И 5, во-первых, навход распределителя 6, который выдаетединичный потенциал по первому выходу на вход считывания регистра9, , и тот выдает вес дуги (1, 3)очерез элемент ИЛИ 11 на первый информационный вход блока 17, на управляющий вход регистра 10 , разрешаявыдачу информации, на управляющийвход регистра 14 З, разрешая записьинформации, а через вход 25 з блока12 - на входы элементов И 21 третье 1462346го столбца; импульс с.выхода элемента И 5 проходит, во-вторых, на вход распределителя 7, который вьщает по первому выходу импульс на вход считывания регистра 142, которь 1 й вьщает5 на информационный вход регистра 132 вес дуги (1,2), в-третьих, на входы записи регистров 13, и регистр 132записывает вес дуги (1,2). Задним фронтом импульса, поступающего с выхода элемента И 5 на нулевой вход триггера 2, он перебрасывается в нулевое состояние, закрывая элемент И 5 и открывая элемент И 4 для прохождения следующих импульсов генера-, тора 1.Второй прямоугольный импульс ге . нератора 1 проходит через элемент И 4на тактовые входы регистров 1.0 и 13. Так как "1" подана на управляющий вход только регистра 102 э, то записанный в нем код 101 (вес дуги между 2-й и 3-й вершинами, фиг. 2) сдвигается на один разряд влево, поэтому 25 "1" с выхода регистра 102 из младшего разряда перезаписывается в старший третий разряд (в соответствии с условиями примера для записи весов дуг в регистрах 9, 10 достаточно иметь 30 три разряда)так что в регистре 10 2 будет записи код 011, а через . элемент ИЛИ 112 она поступает на вход синхронизации сумматора 152, который прибавляет к хранящемуся числу О" поступающий с выхода регистра 13код 001, образуя сумму 001. Задним фронтом тактового импульса, поступающего с выхода элементаИ 4 на тактирующие входы регистров 4013, записанный в регистре 132 код 001 сдвигается на один разряд влево, что образует код 0010 (для взятого ,примера регистры 13 и сумматоры 15 имеют четыре разряда), Задним 45 фронтом каждого прямоугольного импульса генератора 1, поступающего наход счетчика 3, его содержимое увеличивается на 1. Применительно к рассматриваемому примеру будем полагать, что емкость счетчика 3 Е=4, разрядность кода, которым записываются веса дуг, Р=З, поэтому исходное состояние счетчика 3 нулевое, а после прохождения второго импульса генератора 1 его содержимое равно 2; в общем случае в исходном состоянии в счетчик 3 заносят количество импульсов Е-Р, Третий импульс генератора 1 опять проходит через элемент И 4 на тактирующие входы регистров 10 и 13, так что "0" с выхода регистра 10 2 перезаписьвается н старший разряд (в регистре оказывается код 110) и поступает на вход синхронизации сумматора 152,в котором сохраняется код 001. Задним фронтом тактового импульсасодержимое регистра 13 сдвигается влево на один разряд, так, что записанный код имеет вид 0100; при прохождении этого же заднего фронта содержимое счетчика 3 становится равным 3. Четвертый импульс генератора 1 проходит через элемент И 4 на тактирующий вход регистра 10, и с его выхода "1" пере-23 фзаписьвается в старший разряд (так что в этом регистре вновь записывается исходный код 101) и через элемент ИЛИ 11 поступает на вход син 2хронизации сумматора 15, который прибавляет к хранящемуся коду 001 поступающий с выхода регистра 132 код 0100, образуя сумму 0101, поступающую на второй информационный вход блока 17. Последний выбирает максимальный из поступающих на первый и второй информационные входы кодов 0100 и 0101 и вьщает на выход максимального числа код 0101 и единичный потенциал по второму выходу (372) позиционного кода (372) в момент поступления на третьи входы элементов И 33 узла 30 , через вход 35 синхронизации сигнала переполнения с выхода счетчика 3 после поступления на его вход заднего фронта четвертого импульса генератора 1. Сигнал переполнения счетчика 3 проходит также на входы записи регистров 14, и регистр 14, на управляющий вход которого подан потенциал 1, записывает поступающий на его информационный вход код 0101. Сигнал переполнения перебрасывает в единичное состояние триггер 2, что приводит к закрытию элемента И 4 и открытию элемента И 5, а через элемент 16 задержки сигнал поступает на установочные вхопы регистров 13, сумматоров 15 и обнуля- ет их.Далее начинается второй цикл рабо" ты устройства. Следующий пятый импульс генератора 1 через элемент И 5 проходит на вход распределителя 6, который снимает потенциал1" с первого выхода и выдает его вд второй346 462 выход, обеспечивая подачу сигналасчитывания на вход считывания регистра 9, (в данном примере код О, таккак при отсутствии дуги в соответ 5ствующий регистр 9 или 1 О заносится 0), подачу управляющего потенциала на соответствующие входы регистров 10 , 10 , 14 , а через вход25 - на входы элементов И 21 четвертого столбца. Импульс с выходаЭлемента И 5 проходит также на входраспределителя 7, который, продолжаявыдавать потенциал "1" по первомуВыходу, начинает выдавать его и по 15Второму выходу на вход считываниярегистра 14, так что записанные врегистрах 14, 14 з коды 0001 и 0101Поступают на информационные входырегистров 13 и 13 соответственно, 20которые записывают эти коды при поступлении на их входы записи импульса с выхода элемента И 5. ЗаднимФронтом этого импульса перебрасывается в нулевое состояние триггер 2, 25закрывая элемент И 5 и открывая элемент И 4, а задним фронтом импульса,поступающего на вход счетчика 3, онсбрасывается из состояния переполнения в состояние с записанной 1, 30б-й, 7 - й и 8-й импульсы генератора 1проходят через элемент И 4 на тактирующие входы регистров 10 и 13, Свыходов регистров 10 , 1 О последовательно поступают сигналы "1","1", "О" (соответственно коду числа3, записанному в регистре 10 , причем выдача идет с младшего разряда)и "1", "0", "0" (соответственно записанному в регистре 109 коду числа 1) 40через элементы ИЛИ 11 и 11 на входы синхронизации сумматоров 15,15, В результате в сумматоре 15образуется сумма в виде кода 0011числа 3, а в сумматоре 15 ь - в виде 45кода 0101 числа 5. Эти коды поступаютна второй (34 , 34 ) и третий(34, , 34) информационные входы блока 17, который выбирает максимальный код, каким является код 0101, 50и выдает его на выход 36(3636) максимального числа и единичныйпотенциал по третьему выходу (37 )позиционного кода в момент поступленияна третьи входы элементов И 33 узла 5530 сигнала синхронизации с выходасчетчика 3, который переполняется припоступлении на его вход заднего фронтавосьмого импульса генератора 1. Этот 6единичный потенциал через вход 2 бз поступает на входы элементов И 21 третьей строки блока 12. Сигнал переполнения проходит также на входы записи регистров 14, и регистр 14 , на управляющем входе которого присутствует единичный потенциал, записывает код 0101 числа 5. Сигнал переполнения перебрасывает также в единичное состояние триггер 2, обуславливая закрытие элемента И 4 и открытие элемента И 5, а через элемент 16 задержки поступает на установочные входы регистров 13, сумматоров 15, обнуляя их.Затем начинается третий цикл работы устройства, в процессе которого после прохождения девятого импульса генератора 1 единичный потенциал появляется и на третьем выходе распре-.,:. делителя 7, а распределитель 6 снимает единичный потенциал с второго выхода и выдает его по третьему выходу. После прохождения десятого, одиннадцатого и двенадцатого импульсов в сумматорах 15, 15 з, 15 будут записаны коды 0000, 1111, 1010 чисел О, 15, 10, которые поступают на соответствующие информационные входы 34 блока 17. Он выбирает из них максимальный код 1111 и выдает,его на выход 36 максимального числа; этот код будет записан в регистр 14. Блок 17 выдает единичный потенциал и по третьему выходу 37 позиционного кода в момент поступления сигнала синхронизации на вход 35, через вход 26 з указанный потенциал поступает на входы элементов И 21 третьей строки блока 12, Сигнал переполнения счетчика 3 перебрасывает в единичное состояние триггер 2, закрывая элемент И 4 и открывая элемент И 5, а через элемент 16 задержки сигнал поступает на установочные .входы регистров 1.3, сумматоров 15 и обнуляет их.Следующий тринадцатый импульс генератора 1 проходит через элемент И 5 на вход распределителя 6, который по своему (и+1)=у, а в данном примере по четвертому, выходу выдает единичный потенциал на вход останова генератора 1, прекращая работу устройства,. а также на вход 27 опроса вершин блока 12.Блок 12 работает следующим обра"1 зом.Когда на первом цикле единичный потенциал с первого выхода распре 1462346делителя 6 поступает через вход 253 на входы элементов И 21 третьего столбца, а с выхода 37 блока 17 единичный потенциал поступает на5 входы 26 и далее на входы элементов И 21 второй строен матрицы, то единичный потенциал возникает на выходе элемента И 211 и перебрасывает в единичное состояние триггер 19. 10 На втором цикле единичный потенциал через вход 25 поступает на входы элементов И 21 четвертого столбца, а через вход 26- на входы элементов И 21 третьей строки матрицы. По- .15 этому единичный потенциал появляется на выходе элемента И 21 , обуславливая переброс в единичное состояние триггера 19 . Наконец, на третьемМцикле единичный потенциал появляется 20 на входах 25, 26 блока 12, обуславливается переброс в единичное состояние триггера 19 , который нулевым потенциалом с инверсного выхода закрывает элемент И 20 , а единичным 25 потенциалом с прямого выхода открывает элемент И 22 . Поэтому при поступлении с последнего выхода распределителя 6 опросного сигнала на вход 27 он проходит через эле менты И 20, , 20 , 22 , элемент ИЛИ 24 на информационный вход пя 5; того разряда регистра 18, в котором запйсывается "1". Кроме того, импульс с выхода элемента И 22 прохо" дит через элементы ИЛИ 22 , Й 20 И 22, , ИЛИ 24 на информационный вход третьего разряда регистра 18, в котором записывается "1". Импульс с.выхода элемента И 22 проходит так же через элемент ИЛИ 23, И 20 , ИЛИ 23на информационные входы первого и второго разрядов регистра 18, в которых также записывается1. Эти л 1 л, записанные в первом, 45втором, третьем и пятом разрядах регистра 18, указывают номера вершин графа (фиг. 2), через которые проходит путь максимального произведения длин дуг. Таким образом, с бО помощью блока 12 идентифицируются вершины искомого пути графа между его начальной и конечной вершинами.Пара одноименных регистров 13, сумматоров 15 выполняет роль блока умножения; результаты перемножения соответствующих весов дуг путей к той или иной вершине графа поступают в блок 17, который выбирает максимальный из поданных на входы кодов, работая следующим образом. На его разрядные входы 34 поступают колы (фиг. 4). В первый момент анализируются старшие разряды чисел. Если хотя бы в одном старшем разряде есть "1", то на выходе 36 старшего разряда выходного кода формируется "1", а "0" с выхода элемента НЕ 29, поступает на входы элементов ИЛИ 32 узла 30,. Если в старшем разряде какого-либо числа "0", то на выходе элемента ИЛИ 32 соответствующего блока 31 узла 30формируется "0", и все разряды этого числа через соответствующие элементы И 33 не проходят. Если же в старшем разряде числа "1", то число проходит на следующий узел 30, где анализируются вторые по старшинству разряды чисел, прошедших через узел 30 т.д. На выходах 36 появляется код максимального из входных чисел, а "1" появляется на том выходе 37 позиционного кода, который соответствует входу, на который подан максимальный код. Но выдача производится только в момент поступления на вход 35 сигнала синхронизации, ибо до того элементы И 33 последнего узла переноса закрыты нулевым потенциалом, поступающим с входа 35.1Б общем виде описание работыустройства можно представить следующим образом.Перед началом работы исключают вседуги, входящие в начальную величину,и топологию полученного графа заносятв блок 38. Обнуляют тот регистр блока 45, номер которого совпадает сномером начальной вершины графа, востальные регистры блока 45 заносяткоды числа "1", На входы 46, , 49устройства подают сигналы синхронизации в соответствии с временнойдиаграммой работы устройства. Приэтом в (Н+К)-ый регистр 45 (Н - номерначальной вершины пути) заноситсямаксимальное из произведений весовдуг путей в (Н+К)-ую вершину графаиз Н-ой вершины, а в блок 39 - номеравершин этого пути. По достижению ко"нечной вершины (т.е. Н+В), на Н-ыйвход 50 устройства подают импульсопроса. При этом на выходах 50 формируется состав вершин исходногопути, 1462346 10Временная диаграмма работы устройства (фиг. 6) составлена для случаю определения пути из первой в В-ую вершину графа. Однако, начальной и конечной, в общем случае, могут быть любые вершиныграфа. ДЛя поис-ка пути в этом случае следует (нап;ример, при помощи наборного поля1 :преобразователя кода или при помощи ,упорядочения (перенумерации) вершин ,графа обеспечить выдачу сигналов синхронизации на соответствующие новой нумерации входы 48 и 49 устройства, На временной диаграмме Т 1 ,.время формирования произведений на ;выходе блока 44; Т 2 - время записи информации в регистры блока 43; ТЗ время выбора максимального кода;.Т 4 - время записи информации в ре ;:гистры блока 45. Формула изобретенияУстройство для моделирования сетевых графов, содержащее блок определения инцидентных дуг графа из В регистров, где В - количество вершин графа, блок из В умножителей, блок выбора максимального кода и блок определения связных вершин .графа, причем выход веса дуги исходящей из М-ой вершины графа (М=1, , В) подключен к входу первого сомножителя М-го умножителя блока, выход которого подключен к информационному входу М-го регистра первого блока, выход которого подключен к М-му информационному входу блока выбора макси- мального кода, информационный выход которого подключен к информационным входам всех регистров второго блока, информационный выход К-.го регистра второго блока подключен к входу второго сомножителя К-го умножителяблока, о т л н ч а ю щ е е с я тем,что, с целью повышения надежностиустройства, в него введены блокприоритетов и преобразователь кодов,причем М-й выход позиции максимального кода блока выбора максимального 10 кода подключен к М-му входу блокаприоритетов, выход позиции с М-ьюприоритетом которого подключен кИ-му входу первой группы преобразователя кодов, К-ый вход синхронизации 15 первой группы устройства подключен квходу опроса веса дуг, входящих вК-тую вершину графа, к входу разрешения записи К-го регистра второгоблока и к К"му входу второй, группы 20 преобразователя кода, (К, М)-й выход. которого подключен к входу признакадобавления дуги из И-й в К-тую вершину графа блока определения связныхвершин графа, 14-й вход синхронизации 25 второй группы устройства подключенк входу признака чтения М-го регистра второго блока, первый тактовыйвход устройства подключен к входампризнаков записи всех регистров пер 30 вого блока, второй тактовый входустройства подключен к входам приэнаков записи всех регистров второго блока и к .входу опроса преобразователя кода, вход опроса К-й вершины 35 графа устройства подключен к одноименному входу блока определения связных вершин графа, выход признака связности И-й вершины графа которого является выходом признака принадлеж ности М-й вершины графа пути с максимальным произведением весов дуг устройства.роивводственно-издательский комбинат "Патент", г. Укгород, ул. Гагарина,101 аказ 715/49 Тираа 667ЯИИПЯ Государственного комитета по113035, Москва, Ж"3 Подписноеобретениям и открытиям при ГКНТ СССРРаущская наб д. 4/5