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

 

Изобретение относится к области вычислительной техники и может быть использовано для оценки надежности сложных систем на этапе проектирования за счет определения топологической надежности графа системы. Цель изобретения - расширение функциональных возможностей за счет определения показателей топологической надежности графа системы. В устройство, содержащее матрицу элементов И, 4 наборное поле 9, дешифратор 3 и счетчик 2, дополнительно введены блок 1 управления, группа элементов ИЛИ, 5 блок 6 памяти параметров достижимости, группа блоков 7 памяти показателей топологической надежности, группа блоков 8 определения минимума, блок 10 перебора подмножеств, блок 11 подсчета количества разорванных друг. 5 ил.

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

СОЦИАЛ! <СТИЧЕСНИХ

РЕСПУБЛ <Н

А1 (19) (11) (5» 4 С 06 Р 15/20

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

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

ПРИ ГКНТ СССР (21) 4304960/24-24 (22) 08.09. 87 (46) 15.04. 89. Бюл, И- 14 (71) Институт проблем надежности и долговечности машин АН БССР (72) А. И, Волошаненко, А. А. Черняк, М.Ш. Фел ер и Н, Н. Рож ке вич (53) 681, 325 (088, 8) (56) Авторское свидетельство СССР

M- 843738, кл. С 06 F 15/20, 1978.

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

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

ГРАФОВ (57) Изобретение относится к вычис— лительной технике и может быть использовано для оценки надежности сложных систем на этапе проектирова- ния за счет определения топологической надежности графа систем|. Цель изобретения - расширение функциональных возможностей за счет определения показателей топологической надежности графа системы. В устройство, содержащее матрицу элементов И 4 на 1

9 борное поле 9, дешифратор 3 и счет-. чик 2, дополнительно введены блок управления, группа элементов ИЛИ 5, блок 6 памяти параметров достижимости, группа блоков 7 памяти показателей топологической надежности, группа блоков 8 определения минимума, блок 10 перебора подмножеств, блок

11 подсчета количества разорванных Я дуг. 5 ил.

1472915

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

Дешифратор 3 предназначен для преобр аз ования двоично ro кода номер а строки в унитарный код номера стро50

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

Цель изобретения — расширение функциональных возможностей устройства за счет определения показателей 1О топологической надежности (ПТН) графа систем .

Основным параметром ПТН дпя любой пары вершин графа является наименьшее число дуг графа, разрыв которых приводит к разрыву всех ориентированных маршрутов из первой вершины пары во вторую.

На фиг. 1 приведена функциональная схема устройства; на фиг. 2 — 20 функциональная схема блока управления; на фиг. 3 — функциональная схема блока памяти ПТН; на фиг. 4 — функциональная схема блока перебора подмножеств; на фиг. 5 — функциональная схема блока подсчета количества разорванных дуг.

Устройство состоит из блока 1 управления, счетчика 2, дешифратора

3, матрицы Р» Р элементов И 4, 30 группы элементов ИЛИ 5,блока 6 памяти параметров достижимо сти, группы блоков 7 памяти ПТН, блоков 8 определения минимума, наборного поля 9, рлока 10 перебора подмножеств, блока

11 подсчета количества разорванных дуг., Блок I управления предназначен дпя задания алгоритма работы устройства. Он формирует импульсы тактовой 40 частоты, поступающие на счетчик, импульсы частоты циклов, поступающие на блок пере бор а по дмноже ст в, и управляет занесением единиц в блоки памяти ПТН перед началом определения 45 этих параметров. ки, единичный разряд KQTopoFQ cooTветствует номеру опрашиваемой строки.

Элементы И 4 предназначены для моделирования дуг графа. Единичный уровень сигнала на втором входе элемента И 4 определяет наличие дуги из вершины, соответствующей номеру строки, в вершину, соответствующую Номеру столбца матрицы. Единичные уровни на третьих входах появляются при опросе элементов, принадлежащих соответствующим строкам в процессе определения параметров достижимости вершин„ а нулевые уровни на первых . входах этих элементов соответствуют разрываемлм дугам при определении ПТН.

Элементы ИЛИ 5 предназначены для объединения выходов трехвходовых элементов И по столбцам и, таким образом, обеспечивают возможность. моде» лирования достижимости по всем возможным задействованным маршрутам графа.

Блок 6 памяти параметров достижимости предназначен для хранения кодов, соот вет ст вующих пар аметр ам до ст ижимости между вершинами.

Блоки 7 памяти ПТН предназначены для хранения двоичных кодов, соответствующих максимальному количеству дуг, которые необходимо разорвать, чтобы потерялась достижнмость вершины

М из вершины К. При этом по адресу

К блока 7 М памяти ПТН хранится двоичный код соответствующий минимальному

Э количеству дуг, которые должны быть разорваны для того, чтобы была потеряна достижимость вершины M из вершины К.

Блоки 8 определения минимума предназначены дпя сравнения двоичных кодов, хранящихся в блоках памяти

ПТН и соответствующих текущим значениям ПТН для каждой пары вершин, с двоичными кодами, соответствующими количеству разорванных дуг. При этом, если количество разрываемых дуг, приводящее к потере достижимости из вершины К в вершину М, меньше текущего значения ПТН, то это текущее значение ПТН заменяется числом, соответствующим меньшему количеству дуг, разрыв которых приводит к потере достижимости из вершины K в вершину М.

Наборное поле 9 предназначено дпя формирования топологии графа. С помощью наборного поля 9 на вторых входах .элементов И 4 задаются единичные или нулевые уровни в соответствии с

14729 наличием или отсутствием дуг между вершинами графа. Блок 10 перебора подмножеств представляет собой специальный снет5 чик и предназначен для перебора всех возможных сочетаний разрываемых дуг при определении ПТН. Разрядность этого счетчика определяется количеством дуг в исследуемом графе и задается автоматически с наборного поля при формировании топологии графа, при этом количество нулей в его разрядах соот вет ст вует количест ву р аз рыв аемых дуг при определении ПТН. 15

Блок 1! подсчет а кол иче ств а р аз орванных дуг предназначены для подсчета количества нулей в блоке 10 перебора подмножеств и представления числа, со ответ ст вующе го этому коли- 20 честву, в двоичном коде.

При описании принципа работы устройства вводятся следующие понятия.

Такт - элементарная операция, в результате выполнения которой полу- 25 чаются параметры достижимости из одной вершины графа во все остальные.

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

Подготовительный цикл состоит из

P тактов, где P — количество вершин в исследуемом графе.

Рабочий цикл — последовательность операций, в результате выполнения которых в блоке памяти параметров до- 40 стижимо сти формируются коды, соот— ветствующие текущим достижимостям, а в блоках памяти ПТН формируются коды, соответствующие текущим ПТН.

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

Перед началом работы устройства на наборном поле 9 набирается топология исследуемого графа: если между вершиной К и вершиной M имеется дуга, то на второй вход соответствующего

15 элемента И 4 подается единичныи сигнал.

Работа устройства начинается после подачи команды Пуск" на первый вход блока 1 управления и формирования з апускающего импульса, по которому через блок управления устанавливается исходное состояние счетчика 2 и на его первый вход начинают поступать тактовые импульсы. После по ступления из блока 1 упр авления на счетчик 2 первого импульса счетчик 2 устанавливается в первое состояние, которое дешифрируется дешифратором 3, При этом на первый элемент ИЛИ 5 подается единичный сигнал, который проходит на его выход и подается на третьи входы элементов И 4, образующих первую строку матрицы. На первые входы элементов

И 4 этой строки подается единичный сигнал от блока 10 перебора подмножеств, а на вторые входы этих элеметов поступают единичные или нулевые сигналы от наборного поля 9 в соответствии с топологией графа. На тех выходах элементов И 4 первой строки, которые задействованы в структуре графа, формируются единичные сигналы.

С выходов элементов И 4 первой строки, на которых сформированы единичные сигналы, последние. поступают на соответст вующие входы соответствующих элементов ИЛИ 5. С выходов указанных элементов 5 ИЛИ сигналы поступают на третьи входы элементов И 4 соответствующих строк и проходят на выходы задействованных в структуре графа элементов И 4. В результате на выходах тех элементов ИЛИ 5, индексы которых соответствуют вершинам, имеющим достижимость из первой вершины, формируются единичные сигналы, которые записываются по первому адресу блока

6 памяти параметров достижимости.

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

По сл е лер ехода счетчика 2 во второе состояние такая же процедура выполняется по отношению к второй строке. После окончания Р-rn такта первый подготовительный у:кл завер1472915 шается, в результате чего в блоке 6 памяти параметров достижимости по всем адресам записана информация о достижимости всех вершин из каждой вершины, при этом номер адреса в блоке 6 памяти параметров достижимости определяет вершину, из которой определяется достижимость, а номер разряда в этом адресе — номер вершины, 10 в которую определяется достижимость из этой вершины.

На первом подготовительном цикле, как и на всех последующих, от блока

10 перебора подмножеств на первые 1б входы элемеитов И 4 поступают единичные сигналы, поэтому на всех подготовительных циклах достижимость определяется для исходного графа, т ° е. при всех неразорванных дугах. Кроме 20 того,на первом подготовительном цикле -по команде из блока 1 управления по всем адресам всех блоков 7 памяти ПТН записываются "1", которые являются исходными фиктивными I1TH. 25

На первом рабочем цикле на блок

10 перебора подмножеств от блока 1 управления подается импульс и на его выходе формируется двоичный код, нулевые разряды которого соответ ствуют 30 разрывам определенных дуг, при этом на первых входах соответствующих элементов И u — "0 . Дпя графа с разорванными дугами аналогично описанномуу о пр еделя ет ся со в оку пно ст ь пар аметров достижимости. При этом на

К-м такте каждого рабочего цикла информация в разрядах адреса К блока 6 памяти параметров достижимости может меняться, т. е. в определенных разря- 40 дах может прои сходит ь з амен а з аписанных туда "1" на "0". Разряд М адреса

К блока 6 памяти параметров достижимости соединен с пятым входом соответствующего блока 7 памяти ПТН, Ког- 45 да в разряде M адреса К блока 6 памяти параметров достижимости происходит замена "1" на "0", то при наличии разрешающего сигнала на четвер-, том входе соответствующего блока 7 б0 памяти ПТН производится перезапись содержимого блрка 11 подсчета количества разорванных дуг по адресу К этого блока 7 памяти ПТН. Разрешающий сигнал на четвертый вход блока 7 памяти ПТН подается тогда, когда число в блоке 11 подсчета количества разорванных дуг меньше числа, записанного в блоке 7 памяти ПТН.

Таким образом, на каждом такте каждого рабочего цикла по соответствующим адресам блоков 7 памяти I1TH происходит з апись содержимого блока

11 количества разорванных дуг. В результате происходит последовательная модификация ПТН в процессе перебора различных комбинаций разорванных дуг.

Блок 1 управления (фиг. 2) состоит из задающего генератора 1.1, формирователя 1.2, триггера 1.3, счетчика 1,4 циклов, триггера 1.5, элемента И 1.6. Генератор 1. 1 предназначен для синхронизации работы блока управления и устройства в целом.

Формирователь 1. 2 представляет собой одно в и бр ат ор и пр едназ наче н для у становки в исходное состояние счетчика 1.4 циклов, и триггера 1.5. Триггер 1.3 предназначен дпя запуска генератора 1,1 и формирователя 1.2 по команде "Пуск", подаваемой оператором с пульта управления, и остановки генератора после окончания работы устройства. Счетчик 1.4 циклов предназначен дпя подсчета количества циклов по команде с последнего выхода .дешифратора 3 и формирования команд на блок 10 перебора подмножеств.Триггер 1.5 предназначен для формирования интервала заполнения единицами блоков

7 памяти ПТН на первом подготовительном цикле. Элемент И 1.6 предназначен дпя формирования последовательности импульсов записи единиц в блоки 7 па" мяти ПТН на первом подготовительном цикле.

Блок управления работает следующим образом. После выдачи оператором команды "Пуск" на первый вход блока управления триггер . 3 по входу S устанавливается в единичное состояние

| и на его выходе формируется единич-! ный сигнал, который запускает формирователь 1.2 и разрешает работу генератора 1, 1. Дпительность импульса на выходе формирователя 1.2 приблизительно равна длительности импульса генератора, и по нему устанавливаются в нулевое состояние счетчик 1.4 циклов и триггер 1.5, Импульсы, формируемые генератором, через первый выход блока управления поступают на вход счетчика 2 (см, фиг. 1). После окончания одного цикла (подготовительного или рабочего) на последнем (п+1)-м выходе дешифратора 3 формируется сигнал, который по второму входу блока

1472915 управления запускает счетчик 1.4 циклов. После каждого нечетного цикла (подготовительного) на первом выходе счетчика 1. 4 циклов формируется сигнал, который через выход блока 1 управления поступает на блок 10 подсчета количества подмножеств. В течение первого подготовительного цикла с инверсного выхода триггера 1.5 10 единичный сигнал поступает на второй вход элемента И 1.6, В результате дается разрешение на прохождение по первому входу элемента И 1 ° 6 на выход блока 1 управления .импульсов, 15 которые поступают на первые входы блоков 7 памяти ПТН и дают разрешение на запись туда единиц на первом подготовительном цикле. После окончания первого подготовительного цикла по 20 команде с первого выхода счетчика

1. 4 циклов триггер 1.5 устанавливается в единичное состояние, при этом на его инверсном выходе устанавливается нулевой сигнал, который запреща- 25 ет прохождение импульсов через элемент И 1 ° 6. После формирования всех подготовительных циклов на соответствующем выходе счетчика 1. 4 циклов формируется сигнал, по которому триг- 30 гер 1.3 по входу R устанавливается в нулевое состояние и нулевым сигналом на своем выходе запрещает работу генератора 1;1. На этом работа устрой ст в а з аканчивает ся. 35

Блоки 7 памяти ПТН отличаются организацией записи. Когда на второй вход блока 7 памяти ПТН (фиг. 3) поступает адресный код, по соответствующему адресу производится выборка 40 информации, которая с задержкой на время выборки формируется на его первых выходах и подается на блок 8 определения минимума, где сравнивается с текущим значением содержимого бло- 45 ка 11 подсчета количества разорванных дуг. После задержки на время сравнения на выходе соответствующего блока 8 определения минимума может сформироваться сигнал разрешения эаписи (в зависимости от результата сравнения). Таким образом, сигнал разрешения записи на четвертом входе блока 7 памяти ПТН формируется с некоторой суммарной задержкой по отношению к сигналу адресного кода на первом входе этого же блока. Сигнал разрешения записи на входе блока .6 памяти параметров достижимости формируется после подачи адресного кода на первый вход блока 6 через время, требуемое на то, чтобы на одном или нескольких выходах блока 6 памяти параметров достижимости произошел переход единичного сигнала в нулевой.

Блок 10 перебора подмножеств (фиг. 4) представляет собой специальный счетчик, с прямых разрядных выходов которого подаются сигналы блокировки на те элементы И 4 матри цы, на вторые входы которых с наборного поля 9 подаются "0", подтверждая таким образом закрытое состояние этих элементов, а с инверсных разрядных выходов этого счетчика сигналы одаются на первые входы блока 11, ри подаче от наборного поля 9 на

1 входы блока 10 нулей запираются нижние вентили И элементов И/ИЛИ и открываются верхние. При этом сигнал переноса с инверсного выхода триггеа, предшествующего з аблокированной жней части элемента И/ИЛИ, блокиуется и на счетный вход следующего риггер а по ступает тот же сигнап > который поступает на счетный вход предшествующего триггера. Таким образом, те разряды счетчика, на которые от наборного поля 9 поступают

"0", оказываются блокированными и в работе счетчика не участвуют. Эти же нулевые блокирующие сигналы, поступакщие от наборного поля 9, подаются на разрешающие входы элеменгов И, которые включены после прямых и инверсных выходов триггеров. Эти элементы

И оказываются закрытыми, и на входы элементов И 4 и входы блока 11 подаются нулевые сигналы. Это означает, что соответствующие элементы И 4 и входы блока 11 в работе устройства не участвуют, поскольку они соответствуют йезадействованным в топологии графа дугам, а перебор дуг при моде; лировании их разрыва соответствует тем логическим элементам 4, на пер вые входы которых с наборного поля 9 пос тупают "1".

Блок 11 подсчета количества разорванных дуг (фиг. 5) состоит из формирователя 1 1. 1, предст авляюще го собой одновибратор, счетчиков 11.2 и 11,3, генератора 11.4 и мультиплексора 11,5. На первую группу входов блока 11 подсчета количества разорванных дуг подается код перебора подмножеств от блока 10 перебора подмно 1472915 жеств. По сигналу с выхода блока 1 управления на второй вход бло ка 1 1 подсчета количества разорванных дуг поступает з any ñêàþùèé сигнал. На каждом подготовительном цикле этот сигнал нулевой, а на каждом рабочем цикле — единичнь|й. При окончании каждого подготовительного цикла с помощью формирователя 11. 1 счетчики 11.2 10 и 11.3 сбрасываются и на генератор

l 1. 4 с выхода переполнения счетчика

11.2 поступает разрешающий сигнал.

Генератор 11..4 работает до заполнения счетчика 11.2. С помощью мультиплексора 11.5 íà его входе формируют ся импульсы, количество которых соответствует количеству единиц в коде, поступающем ° от блока 10 перебора подмножеств. Эти импульсы подсчитываются счетчиком 11.3, и на

его выходе формируется двоичный код, соответствующий количеству единиц в коде, поступающем от блока 1О перебора подмножеств, которое соответст25 вует количеству разорванных дуг.

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

Устройство дпя исследования гра- 30 фов, содержащее матрицу РФ Р элементов И (P — количество вершин в исследуемом графе) без диагональных элементов главной диагонали, наборное поле, дешифратор, счетчик, информа- 35 ционные выходы которого соединены с информационными входами дешифратора, отл и ч ающе е ся тем, что, с целью расширения функциональных возможностей з а счет определения 40 показателей топологической надежности графа системы, в него введены блок управления, группа элементов ИЛИ, блок памяти параметров достижимости, группа блоков памяти параметров топо- 45 логической надежности, группа блоков определения минимума, блок подсчета количества разорванных дуг, блок перебора подмножеств, первый выход блока управления соединен сб счетным 5О входом счетяика, второй выход соединен с пе р ными входами бло ка подсчет а количества разорванных дуг и блока перебора подмноже ст в, третий выход соединен с первыми входами блоков памяти показ ателей топологической надежности группы и вторыми входами блока перебор а подмноже ст в, выходы которого соединены с первыми входами соответствующих элементов И матрицы и вторыми входами блока подсчета количества разорванных дуг, а третьи входы блока перебора подмножеств соединены с соответствующими выходами наборного поля и вторыми входами соответствующих элементов И матрицы, информационные выходы счетчика соединены с первыми входами блока памяти параметров достижимости и вторыми входами блоков памяти параметров топологической надежности группы, информационные выходы которых соединены с первыми информационными входами соответствующих блоков определения минимума группы, вторые информационные входы которых соединены с выходами блока подсчета количества разорванных дуг и третьими входами блоков памяти показ ателей, то поло гиче ской надежности группы, четвертые входы которых соединены с выходами соответст вующих блоков определения минимума группы, а пятые входы соединены с соответствующими выходами блока памяти параметров достижимости, вторил входы которого соединены с выходами соответствующих элементов ИЛИ группы и третьими входами элементов И соответ ст вующей. строки, матрицы, выход (К,М)-ro элемента И матрицы (где К и N — номера строки и столбца матрицы соответственно, которым принадлежит элемент) соединен с (P-1)-м входом М-го элемента ИЛИ группы, К-й выход дешифратора (где К изменяется от 1 до Р) соединен с нулевым вхо-. дом К-го элемента ИЛИ группы, (Р+1)-й выход дешифратора соединен с вторым входом блока управления, первый вход которого является входом пуска устройства, ) й72915

„Руси

Фиг, 2 фиест

C(> >f AyoPg div u5, а гФ и а устанИка d искодное

СОО77УЯН Р

Х 4

СЮм.а, блокаЬ вЂ” + (мнись) Сбых. йоюаХ вЂ” + М (adpec, ц ки и dept«rr»

oar няпорой urrpeuenrrer

Ю достиникос ь) С бык. dnrr a 1f — + g (ноличест8о раьорбанн4 дде) Счет

f h Êþèó7

Cdpnp бторыи боем ид 10 и 11(счет диномесв8 и sun при rrpPcveyе личесеба ggypuway дуг) яретьав АпАХИ 7и 10 танобна д èñïîäспсгпаяуие) 1472915

Гбьи быкоо (Ф Ж(Оф я&7) )

Фиг.5

Составитель О. Гречухина

Редактор И.Рыбченко Техред M.Äèäûê Корректор Л. Пилипенко

Заказ 1712/48 Тираж 667 Подписное

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

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

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

5х.1

Dm наЬ ног паля

g бл. 1

re em) Умх,3 дИ(сбр дх. Г (с Ык, дЭока / .3апус<

6 1Х 017 и бхЯл.

K дх.24.