Устройство для определения критического пути в графе Советский патент 1982 года по МПК G06F15/173 

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

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

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

10 моде.пи графа, информационные входы третьего и четвертого элементов И подключены к выходу первого элемента И 1.

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

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

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

Устройство характеризуется недостаточно высоким быстродействием.

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

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

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

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

Устройство содержит матричную модель 1 сети, по числу строк и столбцов матрицы формирователи 2 дуг, включающие счетчики 3 и триггеры 4, элементы И 5, по числу столбцов матрицы пятую группу элементов И б, группу элементов ИЛИ 7, первую 8 и вторую 9 группы элементов И, группу элементов НЕ 10, группу регистрирующих счетчиков 11, третью группу элементов И 12, группу триггеров 13, четвертую группу элементов И 14, блок 15 выбора кода максимального числа, генератор 16 тактовых импульсов, первый элемент И 17, третий элемент И 18, элемент НЕ 19, второй элемент И 30, счетчик 21 и дешифратор 22, входы 23 и 23 устройства и выходы 23 и 23 .

Блок 15 выбора кода максимального числа (фиг.2) содержит поразрядные узлы 24, 24 J,..., 24у„ переноса, где m - максимальная разрядность кода критического пути, которая совпадает с разрядностью счетчиков 11,входные шины 25, , , , 25ц, элементы ИЛИ 26 и элементы И 27, элементы ИЛИ-НЕ 28, 28j,..., 28, входные шины 29 , 29, . . ., 29у,, выходные шины 30, 30,, . . ., 30 .

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

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

В исходном состоянии все триггеры 13, счетчика 3,11 и 21 находятся в нулевом состоянии, а триггеры 4 в единичном состоянии. Первоначально в модель 1 заносится информация о топологии моделируемого графа в транспонированном виде относительно неглавной диагонали матрицы. При этом триггеры 4 формирователей 2, моделирующих ветви графа,, устанавливаются IB нулевое состояние. Соответствующий формирователь 2 определяется пересечением строки с номером,равным номеру начального узла моделируемой ветви,и столбца с номером, равным номеру ее конечного узла. В счетчики 3 соответствующих формирователей 2 заносятся числа импульсов, дополняющие длительности ветвей до полной емкости счетчиков. После занесения исходной информации на входах элементов И6, объединяющих входы формирователей 2 в столбцах, соответствующих конечным узлам моделируемого графа, появляются высокие потенциалы. Это объ ясняется тем, что в однонаправленном графе без циклов и петель конечные узлы не содержат выходящих ветвей, поэтому триггеры 4 формирователей 2, находящихся в этом столбце, находятс в единичном состоянии. Определение вершин графа, образующих критический путь, осуществляется в три этапа. На первом этапе осуществляется определение максимальных времен от данной вершины до конечной в модели.руемом графе. При этом с появлением пускового сигнала на входе 23//счетные импульсы с выхода генератора 16 через первый элемент И 17 поступают на информационные входы первых 8 и вторых 9 групп элементов И. Первоначально эти импульсы проходят через элементы И 9,- (i 1, п-1) на входы счетчиков 11 (через элемент И 9j, счетные импульсы не проходят, так как он закрыт низким потенциалом свыхода элемента НЕ lOy,) . Одновременно счетные импульсы проходят через элемент И 8 на входы счетчиков Зил (J 1|П) п-ой строки матричной модели графа, а также на п-ый вход элемента И 18.

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

подачу счетных импульсов на вход счетчика 11, где фиксируется максимальное от данной вepши cы до конечной в моделируемом графе время,

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

На втором этапе заносится только информация в виде матрицы смежности моделируемого графа, при этом в единичное сос ояние ycтaнaвJ ивaютcя триггеры 3, моделирукяцие ветви графа, а также 13 и 13 , соответствующие конечной и начальной вершинам. После занесения исходной информации на вход 23/2 (начинается третий этап работы устройства) подается разрешающий сигнал, в результате чего счетные импульсы с выхода генератора 16 поступают на вход счетчика 21, первый выход которого подключен к входу де1 фратора 22, выходные шиНы jcoToporo подсоединены к одноименным управляющим входам элементов И 14. Если при этом соответству рщий тригге 13 находится в единичном состоянии, то высокий потенциал с его выхода через элемент И 14 поступает на управляемые входы элементов И 5 одноименной строки матричной модели сети и далее через элемент ИЛИ 7 только на те управляемые входы элементов И 12, которым в данной строке матричной модели сети соответствует дуга графа, т.е. единичное состояние триггера 4. Наличие высоких потенциалов на управляемых входах элементов И 12 с выходов элементов И 5 обеспечивает поступление кодов с выходов счетчиков 11 на входы блока 15, который, в свою очередь, обеспечивает выбор максимального из поступивших кодов, при этом соответствующие триггеры 13 перебрасываются в единичное состояние и т.д. Процесс поиска максимального критического пути заканчивается при появлении единичного сигнала на втором выходе счетчика 21 (выход 234.) .

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

разряды. Если хотя бы один из старших разрядов чисел равен 1, то на выходе элемента ИЛИ-НЕ 28 формируется О, который служит сигналом запрета для каждого иэ остальных чисел. При этом, если старший разряд i-ro числа равен О, то все i-ые разряды не проходят через элементы И 27 i-ой группы первого поразрядного узла переноса. Если старший разряд i-ro числа равен 1, то i-oe число проходит через элементы И 27 i-ой группы первого поразрядного узла 24 переноса.

Если старшие разряды всех чисел равны О, то на выходе элемента ИЛИ-НЕ 28 формируется 1, которгш дает разрешение на прохождение всех п чисел через элементы И 27 узла 24;j

А

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

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

i,j 1; 7;

- время длительности дуги из i-ой вершины в j-ую.

После занесения исходной информации и подачи разрешающего сигнала на вход 23 на выходе элемента И 6 присутствует высокий потенциал, поэтому через элемент И 87 проходят счетные импульсы от генератора 16 через элемент И 17 на входы счет.чинов 3 седьмой строки матричной сети, а элементы И (i 1;6) на. входы счетчиков 11. Через t;., 2, т.е. с приходом второго импульба переполняется счетчик 3 седьмой строки шестого столбца, импульс переполнения которого перебрасывает в единичное состояние соответствукядий триггер 4-j, поэтому на выходе элемента И 6(| появляется высокий потенциал, который разрешает.подачу импульсов через элементы И 8 на входы счетчиков 3 шестой строки матричной модели. Одновременно элемент НЕ 10 прекреицает подачу импульсов на счетчик ll(j , показания которого в данный момент времени равны t;-j 2.

Аналогично с приходом пятого импульса переполняются счетчики 3tг

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

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

со00

ОО00(ЮОО

200ое ОоОООО 400ООООООсо

300ООООООСХЗ

ОО23ОООООО

со34500«о

оо0000ОО72

.3 и 3-J.5, перебрасываются в единичное состояние соответствующие триггеры 4, после чего появляются высокие потенциалы на выходах элементов И 65 и 6 ; счетные импульсы далее поступают на счетчики 3 четвертой и пятой строк, и прекращается поступление импульсов на счетчики 11д и llj., где фиксируются коды числа 7 и т.д. Переходной процесс продолжается до тех пор, пока на выходах всех элементов И 6 не пойвятся высокие потенциалы. В результате на счетчиках 11 фиксируются следующие значения: 14; 9; 10; 7; 7; 2; 0. Эти значения соответствуют максимальным временам от данной вершины до конечной для всех вершин моделируемого графа.

Далее заносится информация о топологии графа в матричную модель сети в виде матрицы А смежности, -при этом также устанавливаются в единичное состояние триггеры 13 и 137 После подачи разрапающего сигнала на вход 5 232. импульсы с генератора 16 поступают на вход счетчика 21, где фикси руется код числа 1, поэтому на выходе дешифратора 22 возбуждается первая выходная шина, и на управляемый вход элемента И 14 подается разрешающий сигнал. Поскольку триггер 13, находится в единичном со- стоянии, то на управляемых входах элементов И 5 первой строки присутствуют высокие потенциалы, благодар чему высокие потенциалы с выходов элементов И 5, 5 , 5 через элементы ИЛИ 7j|, 7 и 7; поступают науправляемые входы элементов И 12j, 12, 12;, через которые коды с единичных выходов счетчиков 11, Из 11 поступают на входы блока 15. На выходе блока 15 появляется позиционный код, соответствующий максимальному коду из поступивших, в дан ном случае в единичное состояние пе ребрасывается триггер 13з. После этого на вход счетчика 21 поступает очередной импульс, и в счетчике фик сируется код числа 2. Так как на вы ходе дешифратора возбуждается втора шина и триггер 13 находится в нулевом состоянии, то низкий потенци ал поступает на управляемые входы . элементов И 5 второй строки матричной модели сети, поэтому на вхрд блрка 15 не поступают коды с выходов Счетчиков 11. Далее с приходом очередного счетного импульса на вхо счетчика 21 на выходе дешифратора 22 возбуждается третья выходная шина, по которой подается высокий потенциал на элемент И 14. Следовательно, высокий потенциал поступает на управляемые входы элементов И 5 третьей строки матричной модели сет В результате только на выходах элементов ИЛИ 7 и 7 появляются высокие потенциалы, которые поступают н управляетиые входы элементов И групп 12g , и т.д. В результате кри тический путь моделируемого графа составляет вершины 1; 3; б и 7. Таким образом, предлагаемое устройство обеспечивает повышение быстродействия при определении максимального пути в графе. Формула изобретения Устройство для определения крити ческого пути в графе, содержащее первую, вторую, третью и четвертую группы элементов И, группу элементо ИЛИ, группу регистрирующих счетчико блок выбора кода максимального числ группу триггеров, дешифратор, счетчик, первый и второй элементы И, ге нератор тактовых импульсов, матричную модель сети, включающую элемент И, и формирователи дуг, кгикдый из . которых содержит триггер, причем выход генератора тактовых импульсов подключен к информационному входу первого и второго элементов И, выход второго элемента И соединен с информационными входами элементов И первой и второй групп, выходы элементов И второй группы подключены соответственно к входам регистрирующих счетчиков группы, выходы которых соединены соответственно с информационными входами элементов И третьей группы,- выходы которых подключены к соответствующим входам блока выбора кода максимального числа, выходы которого соединены с входами триггеров группы соответственно, выход каждого из которых подключен к информационному входу соответствующего элемента И четвертой группы, управляющие входы которых соединены с выходами дешифратора, вход которого подключен к выходу счетчика, вход которого соединен с выходом второго элемента И, выход каждого элемента И четвертой группы подключен к информационным входам элементов И одноименной строки матричной модели сети, в каждой строке матричной модели сети триггер формирователя дуг соединен с управляющим входом элемента И матричной модели сети соответственно, выходы элементов И каждого столбца матричной модели сети подключены к входам соответствующего элемента ИЛИ группы, выходы элементов ИЛИ группы соединены с управляющими входами элементов И третьей группы соответственно, отличающееся тем, что, с целью повышения быстродействия, в него введены третий элемент И, элемент НЕ, пятая группа элементов И, группа элементов НЕ, а в каждый формирователь дуг матричной модели сети введен счетчик, выход которого подключен к входу триггера, выходы триггеров формирователей дуг одноименного столбца матричной модели сети соединены с входами соответствующих элементов И пятой группы, выход каждого элемента И пятой группы подключен через соответствующий элемент НЕ группы к управляющему входу соответствующего элемента И второй группы, выходы элементов И первой группы соединены с входами третьего элемента И и с входами .соответствующих счетчиков формирователей дуг матричной модели сети, выход третьего элемента И через элемент НЕ подключен к управляющему входу первого элемента И. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР по заявке 2683352/24, кл.С 06 F 15/20, 1978. 2.Авторское свидетельство СССР по заявке 3007322/24, кл.С 06 F 15/20, 1980 (прототип). ./ r-lfr f