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

 

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

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

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

РЕСПУБЛИК (50 4 С 06 Г 15/20

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

Н А BTOPCKOMY СВИДЕТЕЛЬСТВУ

117

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4210274/24-24 (22) 13.03.87 (46) 28.02.89. Бюл. Р 8 (72) П.А.Ефимов и П.П.Лебедев (53) 681.333(088.8) (56) Авторское свидетельство СССР

N- 1065858, кл. С 06 F 15/20, 1982.

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

N- 1251099, кл. G 06 F 15/20, 1984. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

СЕТЕВЫХ ГРАФОВ (57) Изобретение относится к вычислительной технике и может быть использовано для исследования параметров надежности систем, описываемых графами. Целью изобретения является повышение надежности устройства.

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

45 и заносят коды-числа "1" в остальные регистры. На входы 46- 49 устройства подают сигналы синхронизации в соответствии с временной диаграмной работы устройства, при этом в блоке 39 формируется путь с макси-. мальным произведением весов ветвей.

6 ил.

1462346

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

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

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

> формирования пути; на фиг. 4 — функциональная схема блока выбора максиI

:. мального кода; на фиг. 5 — структура устройства; на фиг. 6 — временная диаграмма работы устройства.

Устройство содержит (фиг. 1) генератор 1 импульсов, триггер 2, счет- 20 чик 3, первый 4 и второй 5 элементы

И, первый 6 и второй 7 распределители уровней, матрицу 8 КИ (К = 1...,  — 1, H = 3, ..., В,  — число вершин графа) моделей дуг, которые в первой строке матрицы выполнены в виде регистров 9 памяти, а в остальных строках — в виде сдвигающихся регистров 10, группу элементов ИЛИ 11, блок 12 формирования пути, первую 13 30 и вторую 14 группы регистров, группу сумматоров 15, элемент 16 задержки; блок 17 выбора максимального кода.

Блок 12 содержит (фиг. 3) регистр

18, группу триггеров 19

19 B- 8 первую 20, вторую 21 и

I третью ?2 группы элементов И, первую

23 и вторую 24 группы элементов ИЛИ, группу опросных входов 25з, ..., 25< группу входов 26 „ ..., 26 а, пози- 40 ционного кода, вход 27 поиска вершин.

Узлы в виде одноименных элементов

И 21, 22, 20 и триггера 19 образуют напдиагональную матрицу размерностью

КИ. Блок 17 содержит (фиг. 4) группу элементов ИЛИ 28, группу элементов

HL 29, группу поразрядных узлов

30,. ..., 30 p (P — разрядность кодов входных чисел), состоящих каждый из блоков 31 переноса, каждый из которых состоит из элемента ИЛИ 32 и одного или нескольких элементов И 33, груп.пу информационных входов 34 „,, 341е ° 34 в, ° ° ° 34вР синхронизирующий вход 35, выходы 36

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

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

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

HE 29, чтобы обеспечить выдачу максимального числа в прямом коде, а третьи входы элементов И 33 последнего поразрядного узла 30 р объединеHbl и являются синхронизирующим входом блока 17 с тем, чтобы выдача позицибнного кора производилась лишь во время прохождения импульсов синхронизации. Блок 12 выполнен аналогично одноименному блоку прототипа.

В общем виде устройство может быть представлено совокупностью блока 38 определения идентичных дуг графа, блока 39 определения связных вершин графа, преобразователя 40 кода, блока 41 приоритетов, блока 42 выбора максимального кода, первого блока 43 регистров, блока 44 умножителей и второго блока 45 регистров.

Кроме того, на фиг. 5 обозначены первый тактовый вход 46 устройства, второй тактовый вход 47 устройства, входы 48 синхронизации первой группы устройства, входы 49 синхронизации второй группы устройства, входы 50 опроса К-ой вершины графа устройства, выходы 51 признаков принадлежности вершин графа пути с максимальным произведением весов дуг устройства.

В исходном статическом состоянии обнуляются распределители 6 и 7, регистры 13 и 14 (кроме 14z), сумматоры 15, тригеры 19 (кроме 19 ) . В единичное состояние устанавливаются триггеры 2, 19, в регистр 14> зано" сится".вес дуги между первой и второй вершинами графа, а веса остальных его дуг заносятся в соответствующие регистры 9 и 10 согласно матрице смежности графа

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

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

9,, и тот выдает вес дуги (1, 3) через элемент ИЛИ 1.1 на первый ин1 формационный вход блока 17, на управляющий вход регистра 10, разрешая выдачу информации, на управляющий вход регистра 143, разрешая запись информации, а через вход 25 блока

12 - на входы элементов И 21 третье1462346 го столбца; импульс с выхода элемента

И 5 проходит, во-вторых, на вход распределителя 7, который вьщает по первому выходу импульс на вход считывания регистра 14, который вьщает

5 на информационный вход регистра 13

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

И 5 и открывая элемент И 4 для прохождения следующих импульсов генера-. тора 1.

Второй прямоугольный импульс ге» нератора 1 проходит через элемент И 4 на тактовые входы регистров 1.0 и 13. 20

Так как "1" подана на управляющий вход только регистра 102э, то за»п»санный в нем код 101 (вес дуги между

2-й и 3-й вершинами, фиг. 2) сдвигается на один разряд влево, поэтому 25

"1" с выхода регистра 10 из младше1 о разряда перезаписывается в старший третий разряд (в соответствии с условиями примера для записи весов руг в регистрах 9, 10 достаточно иметь З0 три разряда) так что в регистре

10 будет записи код 011, а через . элемент ИЛИ 11 она поступает на вход синхронизации сумматора 15, который прибавляет к хранящемуся числу "0" поступающий с выхода регистра 13 код 001, образуя сумму

001. Задним фронтом тактового импульса, поступающего с выхода элемента И 4 на тактирующие входы регистров 40 13, записанный в регистре 13» код

001 сдвигается на один разряр влево, что образует код 0010 (для взятого, ïðèìåðà регистры 13 и сумматоры 15 имеют четыре разряда). Задним 45 фронтом каждого прямоугольного импульса генератора 1, поступающего на

1 ход счетчика 3, его содержимое увеличивается на 1. Применительно к рассматриваемому примеру будем полагать, что емкость счетчика 3 Е=4, разрядность кода, которым записываются веса дуг, Р=З, поэтому исходное состояние счетчика 3 нулевое, а после прохождения второго импульса генератора 1 его содержимое равно 2; в общем случае в исходном состоянии в счетчик 3 заносят количество импульсов Е-P-1, Третий импульс генератора 1 опять проходит через элемент И4 на тактирующие входы регистров 10 и 13, так что "0" с выхода регистра 10 перезапись»вается н старший разряд (в регистре оказывается код 110) и поступает на вход синхронизации сумматора 15,в котором сохраняется код 001. Задним фронтом тактового импульсасодержимое регистра 13 сдвигается влево на один разряд, так, что записанный код имеет вид

0100; при прохождении этого же заднего фронта содержимое счетчика 3 становится равным 3. Четвертый импульс генератора 1 проходит через элемент И 4 на тактирующий вход регистра 10, и с его выхода "1" пере-

23 записывается в старший разряд (так что в этом регистре вновь записывается исходный код 101) и через элемент ИЛИ 11 поступает íà вход син2 хронизации сумматора 15, который прибавляет к хранящемуся коду 001 поступающий с выхода регистра 13 код 0100, образуя сумму 0101 поступающую на второй информационный вход блока 17. Последний выбирает максимальный из поступающих на первый и второй информационные входы кодов 0100 и 0101 и вьщает на выход максимального числа код 0101 и единичный потенциал по второму выходу (37 ) позиционного кода (37 ) в момент поступления на третьи входы элементов И 33 узла 30 через вход

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

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

1462 выход, обеспечивая подачу сигнала считывания на вход считывания регистра 9, (в данном примере код О, так как при отсутствии дуги в соответ5 ствующий регистр 9 или 10 заносится О), подачу управляющего потенциала на соответствующие входы регистров 10<<, 10, 14, а через вход

25 — HR BxQpbl элементов И 21 четФ вертого столбца. Импульс с выхода

Элемента И 5 проходит также на вход распределителя 7, который, продолжая

Выдавать потенциал "1" по первому

Выходу, начинает выдавать еrо и по

Второму выходу на вход считывания регистра 14>, так что записанные в регистрах 14, 14 > коды 0001 и 0101

Поступают на информационные входы регистров 13 и 13> соответственно, 20 которые записывают эти коды при поступлении на их входы записи импульса с выхода элемента И 5. Задним фронтом этого импульса перебрасыва.ется в нулевое состояние триггер 2, 25 закрывая элемент И 5 и открывая элемент И 4, а задним фронтом импульса, поступающего на вход счетчика 3, он сбрасывается из состояния переполнения в состояние с записанной "1". ЗО б-й, 7 — и и 8-й импульсы генератора 1 проходят через элемент И 4 на тактирующие входы регистров 10 и 13. С выходов регистров 10 «, 1О последовательно поступают сигналы "1", "1", "О" (соответственно коду числа

3, записанному в регистре 10, причем выдача идет с младшего разряда) и "1", "О", "О" (соответственно записанному в регистре 109 коду числа 1) 40 через элементы ИЛИ 11 и 11> на входы синхронизации сумматоров 15, 15 . Б результате в сумматоре 152 образуется сумма в виде кода 0011 числа 3, а в сумматоре 15 — в виде 45 кода 0101 числа 5. Эти коды поступают на второй (34,, ..., 34 ) и третий (34,, 34 ) информационные входы блока 17, который выбирает максимальный код, каким является код 0101, 5р и выдает его на выход 36(36,, 36„) максимального числа и единичный потенциал по третьему выходу (37 ) позиционного кода в момент поступления на третьи входы элементов И 33 узла

30 сигнала синхронизации с выхода счетчика 3, который переполняется при поступлении на его вход заднего фронта восьмого импульса генератора 1. Этот

346

6 единичный потенциал через вход 26 поступает на входы элементов И 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. Он выбирает из них максимальный код 1 !11 и выдает,его на выход 36 максимального числа; этот код будет записан в регистр 14 . Блок

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

И 4 и открывая элемент И 5, а через элемент 16 задержки сигнал поступает на установочные .входы регистров 1.3, сумматоров 15 и обнуляет их.

Следующий тринадцатый импульс генератора 1 проходит через элемент

И 5 на вход распределителя 6, который по своему (n+1)=y, а в данном примере по четвертому, выходу выдает единичный потенциал на вход останова генератора 1, прекращая работу устройства,. а также на вход 27 опроса вершин блока 12.

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

1 зом.

Когда на первом цикле единичный потенциал с первого выхода распре1462346 делителя 6 поступает через вход 25

3 на входы элементов И 21 третьего столбца, а с выхода 37 блока 17 единичный потенциал поступает на

5 входы 26> и далее на входы элементов

И 21 второй строен матрицы, то единичный потенциал возникает на выходе элемента И 211 и перебрасывает в единичное состояние триггер 19

На втором цикле единичный потенциал через вход 25 поступает на входы элементов И 21 четвертого столбца, а через вход 26 — на входы элементов И 21 третьей строки матрицы. По- .15 этому единичный потенциал появляется на выходе элемента И 21, обуславливая переброс в единичное состояние триггера 19 . Наконец, на третьем

М цикле единичный потенциал появляется 2р на входах 25» 26> блока 12, обуславливается переброс в единичное состояние триггера 19, который нулевым потенциалом с инверсного выхода закрывает элемент И 20, а единичным 25 потенциалом с прямого выхода открывает элемент И 22 . Поэтому при поступлении с последнего выхода распределителя 6 опросного сигнала на вход 27 он проходит через эле- ЗО менты Vt 20,, 20, 22з,, элемент

ИЛИ 24 на информационный вход пя5

; того разряда регистра 18, в котором запйсывается "1". Кроме того, импульс с выхода элемента И 22 прохо" дит через элементы ИЛИ 22, Й 20

И 22,, ИЛИ 24 на информационный вход третьего разряда регистра 18, в котором записывается "1". Импульс с.выхода элемента И 22 зпроходит так-.. 4p же через элемент ИЛИ 23, И 20, ИЛИ 23 „ на информационные входы первого и второго разрядов регистра

18, в которых также записывается

1lt Эти ll1It записанные в первом, 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.

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

Перед началом работы исключают все дуги, входящие в.начальную величину, и топологию полученного графа заносят в блок 38. Обнуляют тот регистр блока 45, номер которого совпадает с номером начальной вершины графа, в остальные регистры блока 45 заносят коды числа "1", На входы 46, ..., 49 устройства подают сигналы синхронизации в соответствии с временной диаграммой работы устройства. При этом в (H+K}-ый регистр 45 (Н вЂ” номер начальной вершины пути) заносится максимальное из произведений весов дуг путей в (Н+К)-ую вершину графа из Н-ой вершины, а в блок 39 — номера вершин этого пути. По достижению конечной вершины (т.е. Н+В), на Н-ый вход 50 устройства подают импульс опроса. При этом на выходах 50 формируется состав вершин исходного пути.

1462346

Временная диаграмма работы устройства (фиг. 6) составлена для случал определения пути из первой в

В-ую вершину графа. Однако, начальной и конечной, в общем случае, могут быть любые вершины графа. ДЛя поис- ка пути в этом случае следует (нап;ример, при помощи наборного поля

1

:преобразователя кода или при помощи ,.::упорядочения (перенумерации) вершин (,графа обеспечить выдачу сигналов синхронизации на соответствующие новой нумерации входы 48 и 49 устройства, На временной диаграмме Т1, время формирования произведений на

; выходе блока 44; Т2 — время записи информации в регистры блока 43; ТЗ время выбора максимального кода;

Т4 — время записи информации в ре"

::гистры блока 45. формула изобретения

Устройство для моделирования сетевых графов, содержащее блок определения инцидентных дуг графа из

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

M-ой вершины графа (И=1, ..., В) подключен к входу первого сомножителя

М-го умножителя блока, выход которого подключен к информационному входу

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

10 кода подключен к M-му входу блока приоритетов, выход позиции с М-ым приоритетом которого подключен к

И-му входу первой группы преобразователя кодов, К-ый вход синхронизации

15 первой группы устройства подключен к входу опроса веса дуг, входящих в

К-тую вершину графа, к входу разрешения записи К-ro регистра второго блока и к К"му входу второй . группы

20 преобразователя кода, (К, М)-й выход . которого подключен к входу признака добавления дуги из Ы-й в К-тую вершину графа блока определения связных вершин графа, M-й вход синхронизации

25 второй группы устройства подключен к входу признака чтения М-го регистра второго блока, первый тактовый вход устройства подключен к входам признаков записи всех регистров пер;

З0 вого блока, второй тактовый вход устройства подключен к входам приэнаков записи всех регистров второго блока и к .входу опроса преобразователя кода, вход опроса К-й вершины

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

1462346

Фиг. 2

253

i282 !

26 !

462346

25л 27

371

- 1462346

Составитель А. Иишин

Редактор Т. Парфенова Техред JI.Îëèéíûê Корректор О. Кравцова

Заказ 715/49 Тира)к 667 Подписное

ВИИИПИ Государственного комитета по изобретениям и открытиям прн ГКНТ СССР

113035, Москва, Ж"35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Укгород, ул. !агарнна,101