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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик

<1>962968 (61) Дополнительное к авт. саид-ву— (22) Заявлено 26.02. 81 (21) 3250523/18-24 с присоединением заявки ¹â€” (23) Приоритет—

Опубликовано 3009.82. Бюллетень ¹ 36

Дата опубликования описания 3009.82

f51)hA Кл з

G 06 Г 15/20

Государственный комитет

СССР ио делам изобретений н открытий (53) УДК 681. 333 (088.8) (72) Авторы изобретения

В.A.Òèòoâ, В.Л.Гайдуков, Е.В.Кислински

В.М. Крикунов и В. В. Мачули н (7I ) Заявитель (54) УСТРОЙСТВО,ППЯ ОПРЕДЕЛЕНИЯ КРИТИЧЕСКОГО

ПУТИ В ГРАФЕ

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

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

Известно устройство для определения критического пути в графе, со-, держащее генератор тактовых импульсов, выход. которого подключен к входу первого элемента И, управляеьый вход которого подключен к выходу элемента НЕ, вход которого подключен к выходу второго элемента И, по числу строк и столбцов матричной мо дели графа цепочки из последовательно соединенных счетчиков и триггера, по числу столбцов матричной модели графа группы элементов И, дополнительный элементы НЕ, первый и вторые группы элементов И, регистрирующие счетчики, входы каждого из которых подключены к выходу третьего элемента И, управляемый вход которого подключен к выходу дополнительного элемента НЕ, выходы триггеров одно именного стоЛбца матричной модели графа подключены к одноименным входам группы элементов И, выход которой подключен к входу дополнительного элемента НЕ и управляемому входу четвертого элемента И, выход которого подключен к одноимейному входу второго элемента И и входам счетчиков одноименной строки матричной модели графа, информационные входы третьего и четвертого элементов И подключены к выходу первого элемента И f1).

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

Наиболее близким к предлагаемому является устройство для определения максимальных путей в графах, содержащее триггеры по числу. строк и стол962968 бцов матричной модели графа, группу элементов ИЛИ-НЕ по числу строк матричной модели графа, первую, вторую третью группы элементов И, группу счетчиков веса вершины, группу триггеров управления, элемент ИЛИ, элементы И, Генератор тактовых импульсов, блок выбора кода максимального числа, дешифратор (2), Устройство характеризуется недостаточно высоким быстродействием.

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

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

И соединен с информационными входами элементов И первой и второй групп, ЗО выходы элементов И второй группы подключены соответственно к входам регистрирующих счетчиков группы, выходы которых соединены соответственно с информационными входами эле- 35 ментов И третьей группы, выходы которых подключены к соответствующим входам блока выбора кода максимального числа, выходы которого соединены с входами триггеров группы сост- gg ветственно, выход каждого из которых подключен к информационному входу соответствующего элемента И четвертой группы, управляющие входы которых соединены с выходами дешифратора, вход которого подключен к выходу счетчика, вход которого соединен с выходом второго элемента И, выход каждого элемента И четвертой группы подключен к информационным входам элементов И одноименной строки матричной модели сети, в каждой строке матричной модели сети триггер формирователя дуг соединен с управляющим входом элемента И матричной модели сети соответственно, выходы элементов И каждого столбца матри.-HoA модели сети подключены к входам соответствующего элемента ИЛИ группы, выходы элементов ИЛИ группы соединены с управляющими входами элементов И третьей группы соответственно, введены третий элемент И, элемент

НЕ, пятая группа элементов If, группа элементов НЕ, а в каждый формирователь дуг матричной модели сети

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

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

На фиг.1 гокаэана структурная схема устройства для определения критических путей в графах; на фиг.2 структурная схема блока выбора кода максимального числа.

Устройство содержит матричную модель 1 сети, по числу строк и столбцов матрицы формирователи 2 дуг, включающие счетчики 3 и триггеры 4, элементы И 5, по числу столбцов матрицы пятую группу элементов

И б, группу элементов ИЛИ 7, первую

8 и вторую 9 группы элементов И, группу элементов HE 10, группу регистрирующих счетчиков 11, третью группу элементов И 12, группу триггеров 13, четвертую группу элементов И 14, блок 15 выбора кода максимального числа, генератор 16 тактовых импульсов, первый элемент И

17, третий элемент И 18, элемент НЕ

19, второй элемент И 30, счетчик 21 и дешифратор 22, входы 23 и 23 устройства и выходы 23> и 234

Блок 15 выбора кода максимального числа (фиг.2) содержит поразрядные узлы 24, 24>,..., 24„„переноса, где

m — максимальная разрядность кода критического пути, которая совпадает с разрядностью счетчиков 11,входные ши 2511/ 25411 25rtwr элементы ИЛИ 26 и элементы И 27, элементы

ИЛИ-НЕ 28„, 28,..., 28,„, входные шины 29, 292,..., 291,, выходные шины 301, 30,...,30„.

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

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

В исходном состоянии все триггеры 13, счетчика 3,11 и 21 находятся в нулевом состоянии, а триггеры 4 в единичном состоянии . Первоначально в модель 1 заносится информация о топологии моделируемого графа в транспонированном виде относительно неглавной диагонали матрицы. При этом триггеры 4 формирователей 2, модели962968 рующих ветви графа,. устанавливаются

is нулевое состояние. Соответствующий формирователь 2 определяется пересечением строки с номером, равным номеру начального узла моделируемой ветви, и столбца с номером, равным номеру ее конечного узла. В счетчики 3 соответ. ствующих формирователей 2 заносятся числа импульсов, дополнпющие длительности ветвей до полной емкости счетчиков. После занесения исходной информации на входах элементов Иб, объединяющих входы формирователей 2 в столбцах, соответствующих конечным узлам моделируемого графа, появляются высокие потенциалы. Это объясняется тем, что в однонаправленном графе без циклов и петель конечные узлы не содержат выходящих ветвей, поэтому триггеры 4 формирователей 2, находящихся в этом столбце, находятся в единичном состоянии. Определение вершин графа, образующих критический путь, осуществляется в три этапа.

На первом этапе осуществляется определение максимальных времен от данной вершины до конечной в моделируемом графе. При этом с появлением пускового сигнала на входе 23 счетные импульсы с выхода генератора 16 через первый элемент И 17 поступают на информационные входы первых 8 и вторых 9 групп элементов И. Первоначально эти импульсы проходят через элементы И 9; (i = 1, и-1) на входы счетчиков 11; (через элемент

И 9 счетные импульсы не проходят, м так как он закрыт низким потенциалом с выхода элемента НЕ 1О„). Одновременно счетные импульсы прсходят через элемент И 8 на входы счетчиков

3« (j = 1,n) п-ой строки матричной модели графа, а также на и-ый вход элемента И 18. Отсчитав число импульсов, пропорциональное весу моделируемой дуги, счетчик 3 одного из Формирователей и-ой строки переполняется, устанавливается в единичное состояние соответствующий триггер 4, и на вход соответствуюцего элемента И б поступает высокий потенциал с единичного выхода этого триггера. Если на остальных входах этого элемента И б присутствуют высокие потенциалы, то на его выходе появляется разрешающий потенциал . Это свидетельствует о том, что веса дуг, входящих в узел, номер которого соответствует номеру столбца формирователей 2, объединенных этим элементом И б, сформированы. При этом формируется разрешение поступления импульсов на входы счетчиков 3 формирователей 2 ветвей графа, исходяших из сформированного узла. Одновременно с выхода элемента НЕ 10 одноименного столбца снимается низкий потенциал, который прекращает подачу счетных импульсов на вход счетчика 11, где фиксируется максимальное от данной вершины до конечной в моделируемом графе время.

Вычисленный процесс продолжается до тех пор, пока на входах элементов

И 6 будут присутствовать высокие потенциалы . Это свидетельствует о том, что все узлы моделируемого графа сформированы. При этом на выходе эле10 мента И 18 появляется высокий потенциал, который поступает на выход 23> устройства и свидетельствует об окончании первого этапа вычислений, а также через элемент HE 19 прекращаt5 ет подачу счетных импульсов с генератора 16 через элемент И 17. На этом первый этап работы устройства .заканчивается.

На втором этапЕ заносится только

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

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

16 поступают на вход счетчика 21, первый выход которого подключен к входу дешифратора 22, выходные шины .которого подсоединены к одноименным управляющим входам элементов И 14.

Если при этом соответствующий триггер

13 находится в единичном состоянии, то высокий потенциал с его выхода через элемент И 14 поступает на управляемые входы элементов И 5 одно40 именной строки матричной модели сети и далее через элемент ИЛИ 7 только на те управляемые входы элементов

И 12, которым в данной строке матричной модели сети соответствует дуга

45 графа, т.е. единичное состояние триггера 4. Наличие высоких потенциалов на управляемых входах элементов И 12 с выходов элементов И 5 обеспечивает поступление кодов с выходов счет, чиков 11 на входы блока 15, который, в свою очередь, обеспечивает выбор максимального из поступивших кодов, при этом соответствующие триггеры

13 перебрасываются в единичное состояние и т.д. Процесс поиска максимального критического пути заканчивается при появлении единичного сигнала на втором выходе счетчика 21 (выход 234).

Блок 15 обеспечивает поиск макси6О мального када из множества кодов, зафиксированных на счетчиках 11.Для этого на входы 29 блока- 15 через открытые элементы И 12 поступают коды с единичных выходов счетчиков 11. В

65 первый момент анализируются старшие

962968 разряды. Если хотя бы один из старших разрядов чисел равен "1", то на выходе элемента ИЛИ-HE 28„ формируется "О", который служит сигналом запрета для каждого иэ остальных чисел. При этом, если старший разряд

i-го числа равен "О", то все i-ые разряди не проходят через элементы

И 27. i-ой группы первого поразрядного узла переноса. Если старший разряд i-ro числа равен "1", то 10

i-oe число проходит через элементы

И 27 i- îé группы первого поразрядного узла 24 переноса.

Если старшие разряды всех чисел равны "О", то на выходе элемента

ИЛИ-HE 281 формируется "1", которая дает разрешение на прохождение всех и чисел через элементы И 27 узла 24

О 1 1 1 О О О

0 О О О 1 1 О

2 оо оо оо со оо

О 0

0 0

О 0 1 1 0

О О 0 1 О

4 оо оо оо оо оо

3 оо оо оо Оо оо оо 2 3 оо оо оо оо 3 4 5 оо ао

7 2

0 0 О 0 О 0 1

0 . 0 О 0 0 О 1

0 О О 0 О О 0

О, если нет дуги из i-ой вершины в j-ую, где а. =

1, если есть дуга из i-ой вершины в j-ую;

i,j=1; 7; время длительности дуги из i-ой вершинй в j-ую.

36 3 36 4 и 37.6, перебрасываются в единичное состояние соответствующие триггеры 4, после чего появляются высокие потенциалы на выходах эле4 ментов И 6 и 64, счетные импульсы далее поступают на счетчики 3 четвертой и пятой строк, и прекращается поступление импульсов на счетчики 11 и 11,. где фиксируются коды числа 7 и т.д. Переходной процесс продолжается до тех пор, пока на выходах всех элементов И 6 не появятся высокие потенциалы. В результате на счетчиках 11 фиксируются следующие значения: 14; 9; 10; 7; 7; 2; О.

Эти значения соответствуют максимальным временам от данной вершины до конечной для всех вершин моделируемого графа.

Далее заносится информация о топо® логии графа в матричную модель сети в ниде матрицы A смежности,:при этом также устанавливаются в единичное состояние триггеры 13 и 13> После подачи разрешающего сйгнала на вход

65 232 импульсы с генератора 16 постуПосле занесения исходной информации и подачи разрешающего сигнала на вход 23 на выходе элемента И 6> присутствует высокий потенциал, поэтому через элемент И 87 проходят счетные импульсы от генератора 16 через элемент И 17 на входы счет,чиков 3 седьмой строки матричной сети, а через элементы И 9 (i=1;6) на.входи счетчиков 11. Через „ 6 = 2, т.е. с приходом второго импульса переполняется счетчик 3 седьмой строки шестого столбца, импульс переполнения которого перебрасывает в единичное состояние соответствующий триггер 41, поэтому на выходе элемента

И 66 появляется высокий потенциал, который разрешает подачу импульсов через элементы И 86 на входы счетчиков 3 шестой строкй матричной модели. Одновременно элемент HE 10e npе-кращает подачу импульсов на счетчик

116, показания которого в данный момент времени равны = 2.

Аналогично с приходом пятого импульса переполняются счетчики 36, переноса. Вторым элементом ИЛИ-НЕ

28 совместно с элементами ИЛИ 26 поразрядного узла 24 переноса анализируются вторые по старшинству разряды чисел таким же образом, как и старших разрядов и т.д. Позиционный код номера экстремального числа получается путем совпадения всех сигналов запрета, сформированных в каждом 1-ом поразрядном узле переноса.

При сигналах запрета, равных "1", на выходе блока 1S формируется позиционный код с "1" в разряде, соответствующем максимальному коду.

Пример . Пусть задан граф описываемый матрицей A смежности и транспонированной относительно неглавной диагонали матрицей Т длин дуг:

962968 пают на вход счетчика 21, где фикси.— руется код числа 1, поэтому на выходе дешифратора 22 возбуждается первая выходная шина, и на управляемяй вход элемента И 14 подается разрешающий сигнал. Поскольку триггер 13„. находится в единичном состояний, то на управляемых входах элементов И 5 первой строки присутствуют высокие потенциалы, благодаря чему высокие потенциалы с выходов элементов И 5«, 5„, 5 4 через элементы ИЛИ 7, 7 и 74 поступают на управляеьые входы элементов И 12, 12, 124, через которые коды с единичных выходов счетчиков 11, 11, 114. поступают на входы блока 15. На выходе блока 15 появляется позиционный код, соответствующий максимальному коду из поступивших, в данном случае в единичное состояние перебрасывается триггер 13з. После этого на вход счетчика 21 поступает очередной импульс, и в счетчике фиксируется код числа 2. Так как на выходе дешифратора возбуждается вторая шина и триггер 13 находится в ну«левом состоянии, то низкий потенци ал поступает на управляеьые входы . элементов И 5 второй строки матричной модели сети, поэтому на входы блока 15 не поступают коды с выходов счетчиков 11. Далее с приходом очередного счетного импульса на вход счетчика 21 на выходе дешифратора

22 возбуждается третья выходная шина, по которой подается высокий потенциал на элемент И 14 . Следовательно, высокий потенциал поступает на управляеьые входы элементов И 5 третьей строки матричной модели сети.

В результате только на выходах элементов ИЛИ 7 и 7 появляются высокие потенциалы, которые поступают на управляемые входы элементов И групп

12 и 12, и т.д. В результате критический путь моделируемого графа составляет вершины 1; 3; 6 и 7.

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

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

Устройство для определения критического пути в графе, содержащее первую, вторую, третью и четвертую группы элементов. И, группу элементов

ИЛИ, группу регистрирующих счетчиков, блок выбора кода максимального числа, группу триггеров, дешифратор, счетчик, первый и второй элементы И, генератор тактовых импульсов, матричную модель сети, включающую элементы

И, и формирователи дуг, каждый из которых содержит триггер, причем выход генератора тактовых импульсов подключен к информационному входу первого и второго элементов И, выход второго элемента И соединен с информационными входами элементов И первой и второй групп, выходы элементов

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

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

15 каждого из которых подключен к информационному входу соответствующего элемента И четвертой группы, управ.ляющие входы которых соединены с выходами дешифратора, вход которого

20 подключен к выходу счетчика, вход которого соединен с выходом второго элемента И, выход каждого элемента

И четвертой группы подключен к информационным входам элементов И одноименной строки матричной модели сети, в каждой строке матричной модели сети триггер формирователя дуг соединен с управляющим входом элемента И матричной модели сети соответственно, выходы элементов И каждого столбца матричной модели сети подключены к входам соответствующего элемента ИЛИ группы, выходы элементов ИЛИ группы соединены с управляющими входами элементов И третьей групЗ5 пы соответственно, о т л и ч а ю— щ е е с я тем, . что, с целью повышения быстродействия, в него введены третий .элемент И, элемент НЕ, пятая группа элементов И, группа элемен40 тов НЕ, а в каждый формирователь дуг матричной модели сети введен счетчик, выход которого подключен к входу триггера, выходы триггеров формирователей дуг одноименного столбца матg5 ричной модели сети соединены с входами соответствующих элементов И пятой группы, выход каждого элемента И пятой группы подключен через соответствующий элемент НЕ группы к управ, ляющему входу соответствующего элемента И второй группы, выходы элементов И первой группы соединены с входами третьего элемента И и с входами соответствующи счетчиков форми- рователей дуг матричной модели сети, 55 выход третье, элемента И через эле мент НЕ подключен к управляющему входу первого элемента И.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР по заявке В 2683352/24, кл.G 06 F 15/20, 1978.

2. Авторское свидетельство СССР по заявке 9 3007322/24, 65 кл.G 06 F 15/20, 1980 (прототип).

962968 г

Рие. 2

Составитель И.Дубинина

Редактор И.Михеева Техред A.йч Корректор E.Ðoøêî

Заказ 7515/70 Тираж 731 Подписное

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

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

Филиал ППП "Патент", r.Óærîðoä, ул.Проектная,4