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

 

Изобретение относится к вычислительной технике, может быть использовано для исследования сетевых графов без контуров и петель и позволяет находить IИнимaльнyro и максимальную массу дуг, соединенньвс с вершинами графа, определять критические пути в .графе и свободные резервы времени исполнения вершин графа, что расширяет; функциональные возможности устройства . С этой целью устройство для исследования путей в графе содержит наддиагональную матрицу моделей дуг, содержащую в своих узлах регистры, на которых записана масса дуг графа, и блоки элементов И. Критический путь определяется путем анализа на схемах сравнения группы экстремальных кодов массы дуг. Результаты анализа запоминаются на регистрах одной.из двух групп, входящих в состав устройства. Затем при помощи двух групп сумматоров и двух групп вычитателей определяются максимальные и минимальные массы дуг всех вершин графа, а также резерв свободного времени исполнения вершин графа. 1 ил. С/) С

1325500

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

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

На чертеже представлена функциональная схема устройства °

Устройство содержит наддиагональную матрицу 1 моделей 2 дуг, состоящих из регистра 3 и бпока 4 элемен- 1Б тов И, генератор 5 тактовых импульсов, распределитель 6 импульсов, две группы блоков 7 и 8 элементов ИЛИ, блок

9 выбора максимального кода, блок 10 элементов НЕ, две группы регистров 2р

11 и 12, две группы сумматоров 13 и

14, две группы вычитателей 15 и 16, наддиагональную матрицу 17 опроса, каждый узел которой содержит блок 18 элементов И, два счетчика 19 и 20, 25 группу схем 21 сравнения и переключатель 22.

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

Б матрицу 1 заносят информацию о З0 топологии графа, загружая в соответ.ствующие регистры 3 веса дуг. Обнуляют распределитель 6, счетчики 19 и

20 и регистры 11 и 12.

После подачи сигнала пуска импульсы с выхода генератора 5 поступают на вход распределителя 6, который поочередно выдает импульсы на свои выходы.

Импульс с первого выхода распределителя 6 открывает блок 4 элементов И 40 модели 2 (М-I Ì) — го узла матрицы 1 между (М-1)-й и М-й вершинами графа„ через соответствующий блок 7 элементов ИЛИ поступает на соответствующий вход блока 9, который выдает его на выход в инверсном коде, а блок 10— в прямом коде. Через переключатель 22 подвес дуги поступает на информационные входы регистров ll. Задним фронтом импульса с первого выхода распре- делителя 6 вес этой дуги, равный величине максимального пути из (М-1)-й в М-ю вершину графа, записывается в соответствующий регистр 11.

При поступлении импульса с второго выхода распределителя 6 открываются блоки 4 моцелей 2 (М-2)-й строки матрицы 1 и вес дуги (N-2,M) с выхода соответствующего регистра 3 через соответствующий блок 4 элементов И и блок 7 элементов ИЛИ поступает на соответствующий вход блока 9, а вес дуги (М-2; М-1) через соответствующий блок 7 элементов ИЛИ вЂ” на вход первого слагаемого сумматора 13, на вход второго слагаемого которого поступает вес дуги (M-l,M) с выхода соответствующего регистра 11. Суммарный вес дуги (M-2,М-l) и дуги (М-l,М) с выхода соответствующего сумматора 13 поступает на вход блока 9, который выбирает наибольший из двух поступивших кодов и выдает его на выход в инверсном, а блок 10 — в прямом коде через переключатель 22 на информационные входы регистров 11, из которых лишь (M-2)-й регистр 11 записывает его, при поступлении на его вход признака записи заднего фронта импульса с второго выхода распределителя 6.

Далее устройство работает аналогично, и после прохождения импульса с последнего выхода распределителя 6 в регистрах 11 оказываются записанными величины Т максимальных путей иэ вершин графа в его конечную М-ю вершину.

Импульс (М-1)-го выхода распределителя 6 поступает на вход счетчика 20, содержимое которого становится равI ным "1". Единичный сигнал с выхода младшего разряда счетчика 20 поступает на выход устройства как сигнал на съем величин Т и на входы признака записи регистров 12, которые запоминают поступающие с выходов соответствующих вычитателей 16 наиболее поздние времена Т, выполнения вершин графа, получаемые путем вычитания из величины Т, поступающей на входы вычитателей 16 с. выхода первого регистра 11, величин максимальных путей, поступающих на входы вычитателей 16 с выходов соответствующих регистров

11, начиная с второго„ задним фронтом импульса с (M-1)-ro выхода .распределителя 6, поступающим на вход останова генератора 5. Завершается работа устройства на первом этапе °

Перед вторым этапом устройство приводят в исходное состояние, однако в матрицу l весов дуг графа транспонируют относительно неглавной диагонали. Счетчик 20 и регистры 12 не обнуляют.

После подачи пускового сигнала импульсы генератора 5 вновь поступают на вход распрецелителя 6, и далее устз 1Зг ройство работает так же, KGK на первом этапе. В регистрах ll оказываются записанными величины максимальных путей инвертированного графа, которые в прямом графе соответствуют наиболее ранним временам Т выполнения вершин.

При этом номера регистров 11 также должны инвертироваться, т.е. в первом регистре 11 записывается наиболее раннее время выполнения M — и вершины, а в (M-1)"м регистре 11 — наиболее раннее время выполнения первой вершины.

При поступлении импульса с последнего выхода распределителя 6 содержимое счетчика 20 становится равным "2". Единичный сигнал с выхода

его второго разряда поступает на выход устройства как сигнал на съем с выходов регистров ll величин Т наиР более ранних времен выполнения вершин . и на входы опроса схем 21 сравнения.

Схемы 21 сравнения сравнивают поступающие на их входы величины Тр (с выходов регистров 11) и Т (с выходов регистров 12) и выдают на выходы устройства единичные сигналы только при равенстве Т и Т, что имеет место лишь для вершин, лежащих на критическом пути. Таким образом, единичные сигналы на выходах тех или иных схем

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

На третьем этапе для каждой дуги графа определяется свободный резерв времени Р, =Тр †(Т„+Т), где Т вЂ” вес данной дуги. Для этого устройство вновь приводят в исходное состояние, не обнуляя, счетчик 20, регистры 11 и 12 и сохраняя записанную в матрице

1 информацию о топологии инвертированного графа. Переключатель 22 переводят в другое положение, подключая счетчик 18, в который заносят "1".

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

5500

5

50 блок 7 посту :ает на вход соответствующего сумматора 15, на другой вход которого через (М-2,М)-й блок 18, открытый импульсом с первого выхода распределителя 6, и соответствующий блок 8 элементов ИЛИ поступает значение Т (2) времени выполнения второй вершийы. На выход устройства с выхода вьгчитателя 15 выдается величина

Р (1,2) свободного резерва времени дуги (1,2) между первой и второй вершинами графа, при этом номер вычитателя 15 (в данном случае этот номер 1) указывает номер начальной вершины дуги, а код на выходе счетчика 19 (в данном случае после поступления одного импульса с первого выхода распределителя 6, это код "2") — номер конечной вершины дуги.

Импульсы с второго, третьего и т.д. выходов распределителя 6 открывают блоки 18 элементов И соответствующих строк матрицы 17 для прохождения на входы соответствующих вычитателей Т с выходов соответствующих регистров 11, на другие входы вычитателей 15 с выходов соответствующих сумматоров 14 (для первого вычитателя 15 с выхода M-го блока 7 элементов ИЛИ) — суммы значений Тп и весов дуг Т. Например, импульс с второго выхода распределителя 6, открыв блоки 4 элементов И моделей 2 (М-2)-й строки матрицы l, обусловливает поступление веса дуги, записанного в (М-2,М-1)-м регистре 3, через блок 7 элементов

ИЛИ на вход второго сумматора 14, на другой вход которого поступает значение Т (2) с выхода второго регистра

12 так, что на вход второго вычитате". ля 15 поступает величина Тп(2)+Т(2,3).

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

Причем, величина P тогда указывает о свободный резерв времени, когда она больше О. Импульс с (М-1)-ro выхода распределителя 6, поступая на вход останова генератора 5, прекращает работу устройства.

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

Устройство для исследования путей в графе, содержащее две группы ре5 13 гистров, блок выбора максимального кода и наддиагональную матрицу моделей дуг из (М-1) строк и (М-1) столбцов, где M — - число вершин в графе, каждый узел которой содержит блок элементов И и регистр, выход которого подключен к первому входу блока элементов И, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения минимального и максимального веса ребер, соединенных с вершинами графа, в него введен распределитель импульсов, переключатель, блок элементов НЕ, две группы блоков элементов ИЛИ, две группы сумматоров, группа схем сравнения, два счетчика, две группы вычитателей, генератор так товых импульсов и наддиагональная мат рица опроса из (М-1) строк и (М-1) столбцов, каждый узел которой содержит блок элементов И, причем вход пуска генератора тактовых импульсов является входом пуска устройства, выход генератора тактовых импульсов подключен к первому информационному входу переключателя и входу распределителя импульсов, (M-К)-й выход которого (К-1,...М-1) подключен к вторым вхо— дам всех блоков элементов и К-й строки наддиагональной матрицы моделей дуг, к входу признака. записи К-ro регистра первой группы и к первым входам всех блоков элементов И К-й строки наддиагональной матрицы опроса, (М-1)-й выход распределителя импульсов подключен к входу останова генератора тактовых импульсов и к счетному входу первого счетчика, выхоц младшего разряда которого подключен к входам признаков записи всех регистров второй группы и является:выходом признака окончания первого этапа работы устройства, выходы всех блоков элементов И K-го столбца (К11) наддиагональной матрицы моделей дуг подключены к соответствукнцим входам

К-ro блока (КФ1) элементов ИЛИ первой группы, выход К-го блока элементов

ИЛИ первой группы (КФ1, М-1) подключен к входу первого слагаемого К-ro сумматора первой группы и к входу первого слагаемого (М-К)-ro сумматора второй группы, выход блока элементов

И первого столбца наддиагональной мат рицы моделей дуг подключен к входу первого слагаемого первого сумматора первой группы и к входу первого слагаемого (М-1)-го сумматора второй

25500 6 группы, выход К-го сумматора первой группы (К М-1) подключен к К-му информационному входу блока выбора максимального кода, выход (M-1)-ro блока элементов ИЛИ первой группы подключен к (M-1)-му информационному входу блока выбора максимального кода, выход которого подключен к входу блока элементов НЕ, выход которого подключен к

10 второму информационному входу переключателя, второй выход которого подключен к информационным входам всех регистров первой группы, выход К-ro регистра первой группы (КФl) подключен к вторым входам всех блоков элементов И К-й строки наддиагональной матрицы опроса, к входам вычитаемого (К-1)-ro вычитателя первой группы, к входу второго слагаемого К-го суммато2О ра первой группы, первому информационному входу (М-К)-9 схемы сравнения группы и является К-м информационным выходом первой группы устройства, выsoö первого регистра первой группы поцключен к вторым входам всех блоков элементов И первой строки наддиагональной матрицы опроса, к входам уменьшаемого всех вычитателей первой группы и является первым информационным выходом первой группы устройства, выход К-го вычитателя первой группы (КФМ-1)подключен к информационному входу К-ro регистра второй группы, выход которого подключен к входу второ35 го слагаемого (М-К) — ro сумматора второй группы и к второму информационному входу К-й схемы сравнения группы, выход признак равенства которой является К-м информационным выходом второй группы, выходы блоков элементов И

К-ro столбца (К 1) наддиагональной матрицы опроса подключены к соответствующим входам К-ro блока элементов

ИЛИ второй группы, выход которого под45 ключен к входу уменьшаемого (М-К)-го вычитателя второй группы, выход блока элементов И первого столбца подключен к;входу уменьшаемого (М-1)-ro вычитателя второй группы, выход К-ro сумма50 тора второй труппы (Кф1) подключен к входу вычитаемого К-го вычитателя второй группы, выход которого является

К-м информационным выходом третьей группы устройства, выход (М-1)-rо блока элементов ИЛИ первой группы

I подключен к входу вычитаемого первого вычитателя второй группы, информационный выход которого является пер1325500 8 ройства, первь:й выход переключателя подключен к счетному входу второго счетчика, информационный выход которого является информационным выходом устройства. вым информационным выходом третьей группы устройства, выход второго разряда первого счетчика подключен к входам опроса всех схем сравнения группы и является выходом признака окончания второго этапа работы устСоставитель А.11ишин

Техред И.Попович

Редактор В.Петраш

Корректор Н.Король

Заказ 3112/46 Тираж 672 Подписное

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

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

Производственно-полиграфическое предприятие,г.ужгород,ул.Проектная,4