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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспублик 1 ц 962968(22) Заявлено 26.02. 81 (21) 3250523/18-24с присоединением заявки Нов(ИМ.Кл.з С 06 Г 15/20 Государственный комитет СССР по дедам изобретений н открытий(71) Заявитель БИ в,Д-.";-,(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КРИТИЧЕСКОГО ПУТИ В ГРАФЕИзобретение относится к вычислительной технике и может быть использовано при исследовании парамет- ров сетевых графов.Задача определения максимального критического пути в графе заключается в определении значения величины, а также идентификации вершин, образующих максимальный критический путь в графе.Известно устройство для определения критического пути в графе, со-, держащее генератор тактовых импульсов, выход которого подключен к входу первого элемента И, управляеьый вход которого подключен к выходу элемента НЕ, вход которого подключен к выходу второго элемента И, по числу строк и столбцов матричной модели графа цепочки из последовательно соединенных счетчиков и триггера, по числу столбцов матричной модели графа группы элементов И, дополнительный элементы НЕ, первый и вторые группы элементов И, регистрирующие счетчики, входы каждого из которых подключены к выходу третьего элемента И, управляемый вход которого подключен к выходу дополнительного элемента НЕ, выходы триггеров одноименного стоЛбца матричной модели графа подключены к одноименным входам группы элементов И, выход которой подключен к входу дополнительного элемента НЕ и управляемому входу четвертого элемента И, выход которого подключен к одноимейному входу второго элемента И и входам счетчиков одноименной строки матричной модели графа, информационные входы третьего и четвертого элементов И подключены к выходу первого элемента И 1).Существенным недостатком известного устройства является низкое быстродействие, так как определение максимального критического пути осуществляется последовательно в три этапа, первые два из которых связаны с занесением исходной информации о топологии и весов дуг моделируемого графа и подсчета импульсов в регистрирующих счетчиках весов дуг, а третий этап - со сравнением результатов двух подсчетов в схемах сравнения.Наиболее близким к предлагаемому является устройство для определения максимальных путей в графах, содержащее триггеры по числу, строк и стол 96296845 50 55 60 65 бцов матричной модели графа, группуэлементов ИЛИ-НЕ по числу строк матричной модели графа, первую, вторуютретью группы элементов И, группусчетчиков веса вершины, группу триггеров управления, элемент ИЛИ, элементы И, генератор тактовых импульсов, блок выбора кода максимальногочисла, дешифратор 2),Устройство характеризуется недостаточно высоким быстродействием.Цель изобретения - повышение быстродействия.Укаэанная цель достигается тем,что в устройство для определения критического пути в графе, содержащеепервую, вторую, третью и четвертуюгруппы элементов И, группу элементов ИЛИ, группу регистрирующих счетчиков, блок выбора кода максимального числа, группу триггеров, дешифратор, счетчик, первый и второй элементы И, генератор тактовых импульсов,. матричную модель сети, включающую элементы И, и формирователидуг, каждый из которых содержит триггер, причем выход генератора тактовьгх импульсов подключен к информационному входу первого и второгоэлементов И, выход второго элементаИ соединен с информационными входами элементоВ И первой и второй групп, З 0выходы элементов И второй группыподключены соответственно к входамрегистрирующих счетчиков группы,выходы которых соединены соответственно с информационными входами элементов И третьей группы, выходы которых подключены к соответствующимвходам блока выбора кода максимального числа, выходы которого соединены с входами триггеров группы сост ветственно, выход каждого из которыхподключен к информационному входусоответствующего элемента И четвертой группы, управляющие входы которых соединены с выходами дешифратора, вход которого подключен к выходусчетчика, вход которого соединен свыходом второго элемента И, выходкаждого элемента И четвертой группыподключен к информационным входамэлементов И одноименной строки матричной модели сети, в каждой строкематричной модели сети триггер формирователя дуг соединен с управляющимвходом элемента И матричной моделисети соответственно, выходы элементов И каждого столбца матричной модели сети подключены к входам соответствующего элемента ИЛИ группы,выходы элементов ИЛИ группы соединены с управляющими входами элементов И третьей группы соответственно,введены третий элемент И, элементНЕ, пятая группа элементов И, группа элементов НЕ, а в каждый формирователь дуг матричной модели сети введен счетчик, выход которого подключен к входу триггера, выходы триггеров Формирователей дуг одноименного столбца матричной модели сети соединены с входами соответствующих элементов И пятой группы, выход каждого элемента И пятой группы подключен через соответствующий элемент НЕ группы к управляющему входу соответствующего элемента И второй группы, выходы элементов И первой группы соединены с входами третьего элемента И и с входами соответствующих счетчиков формирователей дуг матричной модели сети, выход третьего элемента И через элемент НЕ подключен к управляющему входу первого элементаИ,На фиг.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 и 234Блок 15 выбора кода максимального числа (фиг.2) содержит поразрядные узлы 24, 24 24 переноса, где щ - максимальная разрядность кода критического пути, которая совпадает с разрядностью счетчиков 11,входные шины 2511, 25, 25, элементы ИЛИ 26 и элементы И 27, элементы ИЛИ-НЕ 28, 28 ,, 28 входные шины 29, 292 ., 291, , выходные шины 30.130 ур 30Модель 1 сети представляет собой матрицу однородных ячеек - формирователей дуг размером п п,где и - максимальное число узлов моделируемого графа.Устройство работает следующим образом.В исходном состоянии все триггеры 13, счетчика 3,11 и 21 находятся в нулевом состоянии, а триггеры 4 в единичном состоянии . Первоначально в модель 1 заносится информация о топологии моделируемого графа в транспонированном виде относительно неглавной диагонали матрицы. При этом триггеры 4 Формирователей 2, моделирующих ветви графа,. устанавливаются в нулевое состояние, Соответствующий формирователь 2 определяется пересечением строки с номером, равным номеру начального узла моделируемой ветви, и столбца с номером, равным номеру ееконечного узла. В счетчики 3 соответ ствующих Формирователей 2 заносятся числа импульсов, дополнпющие длительности ветвей до полной емкости счетчиков. После занесения исходной информации на входах элементов Иб,объединяющих вхоую формирователей 2 в столбцах, соответствующих конечным узлам моделируемого графа, появляются высокие потенциалы. Это объясняется тем, что в однонаправленном графе без циклов и петель конечные узлы не содержат выходящих ветвей, поэтому триггеры 4 формирователей 2, находяшихся в этом столбце, находятся в единичном состоянии. Определение вершин граФа, образующих критический путь, осуществляется в три этапа.На первом этапе осуществляется определение максимальных времен от данной вершины до конечной в моделируемом графеПри этом с появлением пускового сигнала на входе 23 счетные импульсы с выхода генератора 16 через первый элемент И 17 поступают на информационные входы первых 8 и вторых 9 групп элементов И. Первоначально эти импульсы проходят через элементы И 9; (1 = 1, и) на входы счетчиков 11; (через элемент И 9 счетные импульсы не проходят,мтак как он закрыт низким потенциалом с выхода элемента НЕ 1 О). Одновременно счетные импульсы проходят через элемент И 8 на входы счетчиков Зи (3 = 1,п) и-ой строки матричной модели графа, а также на и-ый вход элемента И 18.Отсчитав число импульсов, пропорциональное весу моделируемой дуги, счетчик 3 одного из Формирователей и-ой строки переполняется, устанавливается в единичное состояние соответствующий триггер 4, и на вход соответствуюцего элемента И б поступает высокий потенциал с единичного выхода этого триггера. Если на остальных входах этого элемента И б присутствуют высокие потенциалы, то на его выходе появляется разрешающий потенциал . Это свидетельствует о том, что веса дуг, входящих в узел, номер которого соответствует номеру столбца Формирователей 2, объединенных этим элементом И б, сформированы. При этом формируется разрешение поступления импульсов на входы счетчиков 3 формирователей 2 ветвей графа, исходяших из сформированного узла. Одновременно с выхода элемента НЕ 10 одноименного столбца снимается низкий потенциал, который прекращает подачу счетных импульсов на входсчетчика 11, где Фиксируется максимальное от данной вершины до конечной в моделируемом графе время,Вычисленный процесс продолжаетсядо тех пор, пока на входах элементовИ б будут присутствовать высокие потенциалы . Это свидетельствует о том,что все узлы моделируемого графасформированы, При этом на выходе эле мента И 18 появляется высокий потенциал, который поступает на выход 23 зустройства и свидетельствует об окончании первого этапа вычислений, атакже через элемент НЕ 19 прекраща ет подачу счетных импульсов с генератора 16 через элемент И 17. Наэтом первый этап работы устройствазаканчивается.На втором этапЕ заносится только 20 информация в виде матрицы смежностимоделируемого графа, при этом в единичное состояние устанавливаютсятриггеры 3, моделируюшие ветви граФа, а также 13 и 13, соответствую щие конечной и начальной вершинам.После занесения исходной информациина вход 23 (начинается третий этапработы устройства) подается разрешающий сигнал, в Результате чего счетные импульсы с выхода генератора16 поступают на вход счетчика 21,первый выход которого подключен квходу дешифратора 22, выходные шины.которого подсоединены к одноименнымуправляющим входам элементов И 14.35 Е при этом соответствующ,й триггер13 находится в единичном состоянии,то высокий потенциал с его выходачерез элемент И 14 поступает на управляемые входы элементов И 5 одно именной строки матричной модели сетии далее через элемент ИЛИ 7 толькона те управляемые входы элементовИ 12, которым в данной строке матричной модели сети соответствует дуга 45 гРафа, т.е. единичное состояние триггера 4. Наличие высоких потенциаловна управляемых входах элементов И 12с выходов элементов И 5 обеспечивает поступление кодов с выходов счет,И чиков 11 на входы блока 15, который,в свою очередь, обеспечивает выбормаксимального из поступивших кодов,при этом соответствующие триггеры13 перебрасываются в единичное состояние и т.д. Процесс поиска максимального критического пути заканчивается при появлении единичного сигнала на втором выходе счетчика 21(выход 234).Блок 15 обеспечивает поиск максиф мального када из множества кодов,зафиксированных на счетчиках 11.Дляэтого на входы 29 блока 15 через открытые элементы И 12 поступают кодыс единичных выходов счетчиков 11. В 65 первый момент анализируются старшие962968 разряды. Если хотя бы один из старших разрядов чисел равен "1", то на выходе элемента ИЛИ-НЕ 28 Формируется "0", который служит сигналом запрета для каждого иэ остальных чисел. При этом, если старший разряд 5 1-го числа равен "0 ф, то все 1-ые разряди не проходят через элементы И 27 1-ой группы первого поразрядного узла переноса. Если старший разряд 1-го числа равен "1", то 10 1-ое число проходит через элементы И 27 1-ой группы первого поразрядного узла 24 переноса.Если старшие разряды всех чисел равны 0 , то на выходе элемента 15 ИЛИ-НЕ 281 формируется "1", которая дает разрешение на прохождение всех и чисел через элементы И 27 узла 24,1 0 1 1 1 0 0 0 0 0 0 0 1 1 0 2 оо оо оо со оо 0 0 0 0 1 1 О 0 0 0 1 0 4 оо оо ао оо сю 3 оо оо оо Оо оо оо 2 3 оо оо оо оо 3 4 5 оо оо оф оо о о 7 2 0 0 Т 0 О 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 О, если нет дуги из 1-ой вершины в 3-ую;где а.:1, если есть дуга из 1-ой вершины в 3-ую;1,3= 1 7;С " - время длительности дуги из 1-ой вершинй в З-ую. 36 , ЗС 4 и 37., перебрасываются в единичное состояние соответствующие триггеры 4, после чего появляются высокие потенциалы на выходах эле ментов И 6 и 64 , счетные импульсыдалее поступают на счетчики 3 четвертой и пятой строк, и прекращается поступление импульсов на счетчики 114 и 11 ,. где фиксируются коды числа 7 и т.д. Переходной процесс продолжается до тех пор, пока на выходах всех элементов И 6 не появятся высокие потенциалы. В результате на счетчиках 11 фиксируются следующие значения: 14; 9; 10; 7; 7; 2; О.Эти значения соответствуют максимальным временам от данной вершины до конечной для всех вершин моделируемого графа.Далее заносится информация о топо логии граФа в матричную модель сетив ниде матрицы А смежности, при этом также устанавливаются в единичное состояние триггеры 13 и 13 т. После подачи разрешающего сйгнала на вход 65 232 импульсы с генератора 16 постуПосле занесения исходной информации и подачи разрешающего сигнала на вход 234 на выходе элемента И б присутствует высокий потенциал, поэтому через элемент И 87 проходят счетные импульсы от генератора 16 через элемент И 17 на входы счет,чиков 3 седьмой строки матричной сети, а через элементы И 9 (1=1;6) на.входи счетчиков 11, Через й С = 2, т.е. с приходом второго импульса переполняется счетчик 3 седьмой строки шестого столбца, импульс переполнения которого перебрасывает в единичное состояние соответствующий триггер 47 б, поэтому на выходе элемента И 66 появляется высокий потенциал, который разрешает подачу импульсов через элементы И 8 на входы счетчиСков 3 шестой строки матричной модели. Одновременно элемент НЕ 10 С пре-. кращает подачу импульсов на счетчик 11, показания которого в данный момент времени равны с= 2.Аналогично с приходом пятого импульса переполняются счетчики Зсъ переноса. Вторым элементом ИЛИ-НЕ 28 совместно с элементами ИЛИ 26 поразрядного узла 24 переноса анализируются вторые по старшинству разряды чисел таким же образом, как и старших разрядов и т.д. Позиционный код номера экстремального числа получается путем совпадения всех сигналов запрета, сформированных в каждом 1-ом поразрядном узле переноса. При сигналах запрета, равных "1", на выходе блока 15 формируется позиционный код с "1" в разряде, соответствующем максимальному коду.П р и м е р . Пусть задан гРаФ, описываемый матрицей А смежности и транспонированной относительно неглавной диагонали матрицей Т длин дуг:пают на вход счетчика 21, где фикси. -руется код числа 1, поэтому на выходе дешифратора 22 возбуждаетсяпервая выходная шина, и на управляемяй вход элемента И 14 подаетсяразрешающий сигнал. Поскольку триггер 13. находится в единичном состояний, то на управляемых входахэлементов И 5 первой строки присутствуют высокие потенциалы, благодарячему высокие потенциалы с выходовэлементов И 5, 5, 54 через эле менты ИЛИ 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.Таким образом, предлагаемое устройство обеспечивает повышение быстродействия при определении максимального пути в графе,Формула изобретенияУстройство для определения критического пути в графе, содержащее первую, вторую, третью и четвертую группы элементов И, группу элементов ИЛИ, группу регистрирующих счетчиков, блок выбора кода максимального числа, группу триггеров, дешифратор, счетчик, первый и второй элементы И, генератор тактовых импульсов, матричную модель сети, включающую элементы И, и формирователи дуг, каждый из которых содержит триггер, причем выход генератора тактовых импульсов подключен к информационному входупервого и второго элементов И, выходвторого элемента И соединен с информационными входами элементов И первой и второй групп, выходы элементовИ второй группы подключены соответственно к входам регистрирующих счетчиков группы, выходя которых соединены соответственно с информационными входами элементов И третьейО группы, выходы которых подключенык соответствующим входам блока выбора кода максимального числа, выходыкоторого соединены с входами триггеров группы соответственно, выход15 каждого из которых подключен к информационному входу соответствующегоэлемента И четвертой группы, управ,ляющие входы которых соединены свыходами дешифратора, вход которого2 О подключен к выходу счетчика, входкоторого соединен с выходом второгоэлемента И, выход каждого элементаИ четвертой группы подключен к инФормационным входам элементов И одноименной строки матричной моделисети, в каждой строке матричной мо"дели сети триггер формирователя дугсоединен с управляющим входом элемента И матричной модели сети соответственно, выходы элементов И каждого столбца матричной модели сетиподключены к входам соответствующегоэлемента ИЛИ группы, выходы элементов ИЛИ группы соединены с управляющими входами элементов И третьей груп 35 пы соответственно, о т л и ч а ю -щ е е с я тем, .что, с целью повышения быстродействия, в него введенытретий .элемент И, элемент НЕ, пятаягруппа элементов И, группа элемен 40 тов НЕ, а в каждый формирователь дугматричной модели сети введен счетчик,выход которого подключен к входутриггера, выходы триггеров формирователей дуг одноименного столбца мат 45 ричной модели сети соединены с входами соответствующих элементов И пятой группы, выход каждого элемента Ипятой группы подключен через соответствующий элемент НЕ группы к управ 5 О ляющему входу соответствующего элемента И второй группы, выходы элементов И первой группы соединены свходами третьего элемента И и с входами соответствующи счетчиков формирователей дуг матричной модели сети,55 выход третье, элемента И через элемент НЕ подключен к управляющему входу первого элемента И.Источники информации,принятые во внимание при экспертизефф 1. Авторское свидетельство СССРпо заявке 9 2683352/24,кл.С 06 Р 15/20, 1978.2. Авторское свидетельство СССРпо заявке 9 3007322/24,5 .кл.С 06 Р 15/20, 1980 (прототип), 9629689 б 296 8 ие з 7515/70 Тираж 731 По ВНИИПИ Государственного комитета СС по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., Зак ое д.4 ППП "Патент", г.ужгород, ул.Проектная Фил Составитель И.Дубинина Редактор И.Михеева Техред А.Ач Корректор Е.Рошко