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

J

О)

ю

00 4аь О)

25

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

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

На фиг. 1 представлена функциональная .схема предлагаемого устройства; на фиг. 2 - граф со взвешенными JQ дугами, на примере которого рассматривается работа устройства; на фиг. 3 - функциональная схема блока формирования пути; на фиг. 4 - функ- циональная схема блока -выбора макси- 15 мального кода; на фиг. 5 - структура устройства; на фиг. 6 - временная диаграмма работы устройства.

Устройство содержит (фиг. 1) генератор 1 импульсов, триггер 2, счет- 20 чик 3, первый 4 и второй 5 элементы И, первый 6 и второй 7 распределители уровней, матрицу 8 КМ (К 1..., В - 1, М 3, ..., В, В - число вершин графа) моделей дуг, которые в первой строке матрицы вьшолнены в виде регистров 9 памяти, а в остальных строках - в виде сдвигаюпщхся регистров 10, группу элементов ИШ1 11, блок 12 формирования пути, первую 13 30 и вторую 14 группы регистров, группу сумматоров 15, элемент 16 задержки, блок 17 выбора максимального кода. . Блок 12 содержит (фиг. 3) регистр 18, группу триггеров 9, ..., 35 В-1 В первую 20, вторую 21 и третью 22 группы элементов И, первую 23 и; вторую 24 группы элементов ИШ1, группу опросных входов 25э, ..., 25g , группу входов 26,, ..., 26 g., пози- 40 ционного кода, вход 27 поиска вершин. Узлы в виде одноименных элементов И 21, 22, 20 и триггера 19 образуют наддиагональную матрицу размерностью КМ. Блок 17 содержит (фиг. 4) группу дз элементов ИЛИ 28, группу элем ентов НЕ 29, группу поразрядных узлов 30,. ..., 30 р (Р - разрядность кодов входных чисел), состоящих каждый из блоков 31 переноса, каждый из которых Q состоит из элемента ИЛИ 32 и одного или нескольких элементов И 33, груп- .пу информационных входов 34 , , ...,

1р

., 34в,,

34цр, сйнхро., . -.

низирующий вход 35, выходы 36, ..., 55

36р максимального числа, выходы

37,, ..., 376 позиционного кода.

В блоке 17 каждый из элементов ИЛИ-НЕ

разбит на элемент ИЛИ 28 и элемент

5

Q 5

0 0 5 0 з Q

55

НЕ 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, 192, регистр 14 заносится -вес дуги между первой и второй вершинами графа, а веса остальных его дуг заносятся в соответствующие регистры 9 и 10 согласно матрице , смежно с т-и графа.

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

С подачей пускового сигнала генератор 1 начинает выдачу импульсов, первый из которых проходит через открытый элемент И 5, во-первых, на вход распределителя 6, который вьщает единичный потенциал по первому выходу на вход считывания регистра 9, , и тот выдает вес дуги (1, 3) через элемент ИЛИ 11, на первый информационный вход блока 17, на управляющий вход регистра Ю разрешая выдачу информации, на управляющий вход регистра 14.j, разрешая запись информации, а через вход 25з блока 12 - на входы элементов И 21 третье

31

го столбца; импульс с выхода элемент И 5 проходит, во-вторых, на вход распреде 1ителя 7, который выдает по первому выходу импульс на вход считывания регистра 14 который выдает на информационный вход регистра 13, вес дуги (1,2), в-третьих, на входы записи регистров 13, и регистр 13 записывает вес дуги (1,2). Задним фронтом импульса, поступающего с выхода элемента И 5 на нулевой вход триггера 2, он перебрасывается в нулевое состояние, закрывая элемент И 5 и открывая элемент И А для прохождения следующих импульсов генерат тора 1.

Второй прямоугольный импульс ге- нератора 1 проходит через элемент И 4 на тактовые входы регистров 10 и 13. Так как 1 подана на управляюш 1й

ратора 1 опять проходит через элемент И 4 па тактирующие входы регистров 10 и 13, так что О с выхода регистра 0 гз перезаписывается в старший разряд (в регистре оказывается код 110) и поступает на вход синхронизации сумматора 15,,в котором сохраняется код 001 .Задним фронтом тактового импульса содержимое регистра 13 сдвигается влево на один разряд, так, что записанный код имеет вид 0100; при прохождении этого же заднего фронта содержимое счетчика 3 становится равным 3. Четвертьш импульс генератора 1 проходит через элемент И 4 на тактирующий вход регистра 10- , и с его выхода Г пере- записывается в старший разряд (так что в этом регистре вновь записывается исходный код, 101) и через эле

Изобретение относится к вычислительной технике и может быть использовано для исследования парамет-. ров надежности систем, описываемых графами. Целью изобретения является повышение надежности устройства. Устройство содержит блок 38 определения инцидентных дуг графа, блок 39 определения связных вершин графа, преобразователь 40 кода, блок 41 приоритетов, блок 42 выбора максимального кода, первый блок 43 регистров, блок 44 умножителей, второй блок 45 регистров, тактовые входы 46 и 47 устройства, входы 48 и 49 синхронизации, входы 50 опроса устройства, выходы 51 признаков принадлежности вершин пути с максимальным произведением весов дуг устройства. Перед началом работы исключают все дуги, входящие в начальную вершину графа, и топологию полученного графа заносят в блок 38. Обнуляют 11-й регистр блока 45 и заносят коды-числа 1 в остальные регистры. На входы 46-49 устройства подают сигналы синхронизации в соответствии с временной диаграм- ной работы устройства, при зтом в блоке 39 формируется путь с макси- мальным произведением весов ветвей. 6 ил. с сл

вход только регистра , то записанный в нем код 101 (вес дуги между 2-й и 3-й верщинами, фиг. 2) сдвигается на один разряд влево, поэтому 1 с выхода регистра из младшего разряда перезаписывается в старший третий разряд (в соответствии с условиями примера для записи весов дуг в регистрах 9, 10 достаточно иметь три разряда) так что в регистре будет записи код 011, а через элемент ШШ 11 она поступает на вход синхронизации сумматора 15, который прибавляет к хранящемуся числу О поступающий с выхода регистра 13ькод 001, образуя сумму 001. Задним фронтом тактового импульса, поступающего с выхода элемента И 4 на тактирующие входы регистров 13, записанный в регистре 13 код ,-. 001 сдвигается на один разряд влево, что образует код 0010 (для взятого {примера регистры 13 и сумматоры 15 имеют четыре разряда). Задним фронтом каждого прямоугольного импульса генератора 1, поступающего на {вход счетчика 3, его содержимое увеличивается на 1. Применительно к рассматриваемому примеру будем полагать, что емкость счетчика 3 , разрядность кода, которым записываются веса дуг, , поэтому исходное состояние счетчика 3 нулевое, а после прохождения второго импульса генератора 1 его содержимое равно 2; в общем случае в исходном состоянии в счетчик 3 заносят количество импульсов Е-Р-1.Третий импульс генемент ИЛИ 112 поступает на вход синхронизации сумматора 15, который прибавляет к хранящемуся коду 001

поступающий с выхода регистра 13 код 0100, образуя сумму 0101, поступающую на второй информационный вход блока 17. Последний выбирает максимальный из поступающих на первый и второй информационные входы кодов 0100 и 0101 и выдает на выход максимального числа код 0101 и единичный потенциал по второму выходу (37) позиционного кода (37.) в момент поступления на третьи входы элементов И 33 узла 30 д, через вход 35 синхронизации сигнала переполнения с выхода счетчика 3 после поступления на его вход заднего фронта четвертого импульса генератора 1. Сигнал переполнения счетчика 3 проходит также на входы записи регистров 14, и регистр 14j, на управляющий вход которого подан потенциал 1, записывает

поступающий на его информационный вход код 0101. Сигнал переполнения перебрасывает в единичное состояние триггер 2, что приводит к закрытию элемента И 4 и открытию элемента И 5, а через элемент 16 задержки сигнал поступает на установочные входы регистров 13, сумматоров 15 и обнуляет их.

Далее на инается второй цикл работы устройства. Следующий пятый импульс генератора 1 через элемент И 5 проходит на вход распределт1теля 6, который снимает потенциал 1 с пер- вого выхода и выдает его на второй

выход, обеспечивая подачу сигнала (гчитывания на вход считывания регистра 9. (в данном примере код О, так как при отсутствии дуги в соответствующий регистр 9 или 10 заносится 0), подачу управлдаощего потенци- 4ла на соответствующие входы регист- зов 102,10, 144 , а через вход 5. - на входы элементов И 21 четвертого столбца. Импульс с выхода Элемента И 5 проходит также на вход |)аспределителя 7, которьй, продолжая выдавать потенциал 1 по первому . ВЫХОДУ, начинает вьщавать его и по {второму выходу на вход считывания , регистра 14, так что записанные в регистрах 14, 14g коды 0001 и 0101 Поступают на информационные входы эегистров 13, и 13j соответственно, которые записывают эти коды при поступлении на их входы записи импульса с выхода элемента И 5. Задним (фронтом этого импульса перебрасывается в нулевое состояние триггер 2, закрывая элемент И 5 и открывая элемент И 4, а задним фронтом импульса, поступающего на вход счетчика 3, он сбрасывается из состояния переполнения в состояние с записанной 1. 6-й, 7-й и 8-й импульсы генератора 1 проходят через элемент И 4 на тактирующие входы регистров 10 и 13. С выходов регистров после- довательно поступают сигналы 1, 1, О (соответственно коду числа 3, записанному в регистре 10, причем выдача идет с младшего разряда) и 1, О, О (соответственно записанному в регистре Ю коду числа 1)

14623466

единичный потенциал через вход 26, поступает на входы элементов И 21 третьей строки блока 12. Сигнал переполнения проходит также на входы за10

15

20

25

30

45

через элементы ИЛИ 11 и 11з на входы синхронизации сумматоров 5, ISj. В результате в сумматоре 15-2: образуется сумма в виде кода ООП числа 3, а в сумматоре 15 j- в виде кода 0101 числа 5. Эти коды поступают на второй (34,,,, ..., ) и третий (34д, , ..., 343) информационные входы блока 17, который выбирает максимальный код, каким является код 0101, и выдает его на выход 36(36, ..., 36) максимального числа и единичный потенциал по третьему выходу (373) позиционного кода в момент поступления на третьи входы элементов И 33 узла 55 30м сигнала синхронизации с выхода счетчика 3, который переполняется при поступлении на его вход заднего фронта восьмого импульса генератора 1. Этот

писи регистров 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 максимального числа; этот код будет записан в регистр 145- Блок 17 вьщает единичный потенциал и по третьему выходу 37 позиционного кода в момент поступления сигнала синхронизации на вход 35, через вход 26,, указанный потенциал поступает на входы элементов И 21 третьей строки блока 12. Сигнал переполнения счетчика 3 перебрасывает в единичное состояние триггер 2, закрывая элемент И 4 и открывая элемент И 5, а через элемент 16 задержки сигнал поступает на установочные входы регистров 1.3, сумматоров 15 и обнуляет их.

СледуК) тринадцатый импульс генератора 1 проходит через элемент И 5 на вход распределителя 6, который по своему (п+1)у, а в данном пример по четвертому,выходу вьвдает единичны потенциал на вход останова генера-. тора 1, прекращая работу устройства а также на вход 27 опроса вершин

блока 12.

Блок 12 работает следующим обра-

зом.

Когда на первом цикле единичный потенциал с первого выхода распре40

50

5

0

5

0

45

55

писи регистров 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 максимального числа; этот код будет записан в регистр 145- Блок 17 вьщает единичный потенциал и по третьему выходу 37 позиционного кода в момент поступления сигнала синхронизации на вход 35, через вход 26,, указанный потенциал поступает на входы элементов И 21 третьей строки блока 12. Сигнал переполнения счетчика 3 перебрасывает в единичное состояние триггер 2, закрывая элемент И 4 и открывая элемент И 5, а через элемент 16 задержки сигнал поступает на установочные входы регистров 1.3, сумматоров 15 и обнуляет их.

СледуК) тринадцатый импульс генератора 1 проходит через элемент И 5 на вход распределителя 6, который по своему (п+1)у, а в данном примере по четвертому,выходу вьвдает единичный потенциал на вход останова генера-. тора 1, прекращая работу устройства,., а также на вход 27 опроса вершин

блока 12.

Блок 12 работает следующим обра-

зом.

Когда на первом цикле единичный потенциал с первого выхода распре40

50

делителя 6 поступает через вход 25 на входы элементов И 21 третьего столбца,а с выхода 37 блока 17 единичный потенциал поступает на входы 262 и далее на входы элементов И 21 второй строеи матрицы, то единичный потенциал возникает на выходе элемента И 21- и перебрасывает в единичное состояние триггер 192j. На втором цикле единичный потенциал через вход 254 поступает на входы элементов И 21 четвертого столбца, а через вход 26 j - на входы элементов И 21 третьей строки матрицы. Поэтому единичный потенциал появляется на выходе элемента И 21, обуславливая переброс в единичное состояние триггера 19. . Наконец, на третьем цикле единичный потенциал появляется на входах 25j, 26, блока 12, обуславливается переброс в единичное состояние триггера , который нулевым потенциалом с инверсного выхода

10

15

мальнын из поданных на входы кодов, работая следующим образом. Па его разрядные входы 34 поступают коды (фиг. 4). В первый момент анализируются старшие разряды чисел. Если хотя бы в одном старшем разряде есть 1, то на выходе 36 старшего разряда выходного кода формируется 1, а О с выхода элемента НЕ 29, поступает на входы элементов ИЛИ 32 узла 30. Если в старшем разряде какого-либо числа О, то на выходе элемента liTIH 32 соответствующего блока 31 узла формируется О,

и все разряды этого числа через соответствуюш 1е элементы И 33 не проходят. Если же в старшем разряде числа 1, то число проходит на спе- 20 дующий узел 30, где анализируются вторые по старшинству разряды чисел, прошедших через узел 30, т.д. На выходах 36 появляется код максимального из входных чисел, а 1 появлязакрывает элемент И 20 , а единичным 25 ется на том выходе 37 позиционного

35

потенциалом с прямого выхода открывает элемент И . Поэтому при поступлении с последнего выхода распределителя 6 опросного сигнала на вход 27 он проходит через эле- 30 менты К 20 ,j , , , элемент ШШ 24г на информационный вход пя- ; того разряда регистра 18, в котором записывается 1. Кроме того, импульс с выхода элемента И 22 npoxoi- дит через элементы ИЛИ 22 j, И 20 , И , ИЛИ 24J на информационный вход третьего разряда регистра 18, в котором записывается 1. Импульс

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

В общем виде описание работы устройства можно представить следующим образом.

Перед началом работы исключают все дуги, входящие в-начальную величину.

с.выхода элемента И 22 зПроходит так- 40 топологию полученного графа заносят

же через элемент ИЛИ 23, И 20, ИЛИ 23 на информационные входы первого и второго разрядов регистра 18, в которых также записывается 1. Эти 1, записанные в первом, втором, третьем и пятом разрядах регистра 18, указывают номера вершин графа (фиг. 2), через которые проходит путь максимального произведения длин дуг. Таким образом, с помощью блока 12 идентифицируются вершины искомого пути графа между его начальной и конечной вершинами.

Пара одноименных регистров 13, сумматоров 15 выполняет роль блока умножения; результаты перемножения соответствующих весов дуг путей к той или иной вершине графа поступают в блок 17, который выбирает максив блок 38. Обнуляют тот регистр блока 45, номер которого совпадает с номером начальной вершины графа, в остальные регистры блока 45 заносят 45 коды числа 1, На входы 46, ..., 49 устройства подают сигналы синхрони- зации в соответствии с временной диаграммой работы устройства. При этом в (Н+К)-ый регистр 45 (Н - номер gQ начальной вершины пути) заносится

максимальное из произведений весов дуг путей в (Н+К)-ую вершину графа из Н-ой вершины, а в блок 39 - номера вершин этого пути. По достижению косе нечной вершины (т.е. Н+В), на Н-ый вход 50 устройства подают импульс опроса. При этом на выходах 50 формируется состав вершин исходного пути.

5

мальнын из поданных на входы кодов, работая следующим образом. Па его разрядные входы 34 поступают коды (фиг. 4). В первый момент анализируются старшие разряды чисел. Если хотя бы в одном старшем разряде есть 1, то на выходе 36 старшего разряда выходного кода формируется 1, а О с выхода элемента НЕ 29, поступает на входы элементов ИЛИ 32 узла 30. Если в старшем разряде какого-либо числа О, то на выходе элемента liTIH 32 соответствующего блока 31 узла формируется О,

и все разряды этого числа через соответствуюш 1е элементы И 33 не проходят. Если же в старшем разряде числа 1, то число проходит на спе- 0 дующий узел 30, где анализируются вторые по старшинству разряды чисел, прошедших через узел 30, т.д. На выходах 36 появляется код максимального из входных чисел, а 1 появляется на том выходе 37 позиционного

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

В общем виде описание работы устройства можно представить следующим образом.

Перед началом работы исключают все дуги, входящие в-начальную величину.

топологию полученного графа заносят

в блок 38. Обнуляют тот регистр блока 45, номер которого совпадает с номером начальной вершины графа, в остальные регистры блока 45 заносят коды числа 1, На входы 46, ..., 49 устройства подают сигналы синхрони- зации в соответствии с временной диаграммой работы устройства. При этом в (Н+К)-ый регистр 45 (Н - номер начальной вершины пути) заносится

максимальное из произведений весов дуг путей в (Н+К)-ую вершину графа из Н-ой вершины, а в блок 39 - номера вершин этого пути. По достижению конечной вершины (т.е. Н+В), на Н-ый вход 50 устройства подают импульс опроса. При этом на выходах 50 формируется состав вершин исходного пути.

Временная диаграмма работы устройства (фиг. 6) составлена для случая определения пути из первой в В-ую вершину графа. Однако, началь- ной и конечной, в общем случае, могу ;быть любые вершины графа. ДЛя поис- ;ка пути в этом случае следует (нап- ;ример, при помощи наборного поля, преобразователя кода или при помощи iупорядочения (перенумерации) вершин I графа обеспечить выдачу сигналов iсинхронизации на соответствующие новой нумерации входы 48 и 49 уст- ройства. На временной диаграмме Т1 - время формирования произведений на |выходе блока 44; Т2 - время записи iинформации в регистры блока 43; ТЗ - время выбора максимального кода; :Т4 - время записи информации в ре- |гистры блока 45. . .

25

Формула изобретения

Устройство для моделирования сетевых графов, содержащее блок определения инцидентных дуг графа из В регистров, где В - количество вершин графа, блок из В умножителей, блок выбора максимального кода и блок определения связных вершин .графа, причем выход веса дуги исходящей из М-ой вершины графа (, ..., В) подключен к входу первого сомножителя М-го умножителя блока, выход которого

подключен к информационному входу 35 М-го perHCTpk первого блока, выход которого подключен к М-му информационному входу блока выбора макси-- мального кода, информадаонный выход которого подключен к информационным 40 входам всех регистров второго блока, информационный выход Ктго регистра

0

5

5 0

второго блока подключен к входу второго сомножителя К-го умножителя блока, отличающееся тем, что, с целью повышения надежности устройства, в него введены блок приоритетов и преобразователь кодов, причем М-й выход позиции максимального кода блока выбора максимального кода подключен к М-му входу блока приоритетов, выход позиции с М-ым приоритетом которого подключен к М-му входу первой группы преобразователя кодов, К-ый вход синхронизации первой группы устройства подключен к входу опроса веса дуг, входяп1их в К-тую вершину графа, к входу разрешения записи К-го регистра второго блока и к К-му входу второй , группы преобразователя кода, (К, М)-й выход которого подключен к входу признака добавления дуги из М-й в К-тую вершину графа блока определения связных вершин графа, М-й вход синхронизации второй группы устройства подключен к входу признака чтения М-го регистра второго блока, первый тактовый вход устройства подключен к входам признаков записи всех регистров пер-п вого блока, второй тактовый вход устройства подключен к входам признаков записи всех регистров второго блока и к входу опроса преобразователя кода, вход опроса К-й вершины графа устройства подключен к одноименному входу блока определения связных вершин графа, выход признака связности М-й вершины графа которого является выходом признака принадлежности М-й вершины графа пути с максимальным произведением весок дуГ устройства.

36

- Пг

/32

Н 15z К

/7

i

/jj

-Ч ш

i

I Ь

/5

17П 35

/2

27

5

hi

LJU

I

LM

I

Ш

Т

f/2

S±

--47a2

V

7/7V l/ /y/yWJ Фиг.1

фиг. 2

2G

36,

36z

Щг

пт

25п 27

Фиг.З

36т

35

i37,

,

п

фиг.