Устройство для определения максимальных путей в графах Советский патент 1986 года по МПК G06F15/173 

14) 11 Изобретение относится к области вычислительной техники и может быть использовано при исследовании параметров сетевых графиков. Цель изобретения - расширение области применения устройства путем обеспечения возможности исследования графов на наличие циклов и петель в них и повышение точности определения максимальных путей. На фиг. 1 приведена функциональная схема устройства для определения максимальных путей в графах; на фиг. 2 - алгоритм работы блока микропрограммного управления; на фиг.Зструктурная схема блока микропрограм много управления; на фиг. 4 - функциональная схема узла памяти блока микропрограммного управления; на фиг. 5 - функциональная схема узла формирования сигналов перехода блока микропрограммного управления; на фиг. 6 - функциональная схема узла формирования сигналов управления бло ка микропрограммного управления; на фиг. 7 - функциональная схема бло ка формирования топологии исследуемого графа; на фиг. 8 - функциональная схема- блока выделения циклов; на фиг. 9 - функциональная схема пер вого узла памяти блока вьщеления циклов; на фиг. 10 - функциональная схема второго узла памяти блока выделения циклов; на фиг. 11 - функци ональная схема третьего узла памяти на фиг. 12 - функциональная схема блока формирования адреса; на фиг.13 функциональная схема коммутатора; на фиг. 14 - функциональная схема блока сравнения. Устройство для определения максимальных путей в графах содержит матричную модель 1 сети, группу элементов ИЛИ-НЕ 2, генератор 3 тактовых импульсов, элемент И 4, группу элементов И 5, группу счетчиков 6 весов дуг, группу триггеров 7 управления, группу элементов И.8, группу регист рирующих счетчиков 9, элемент РШИ 10, триггеры 11 матричлой модели се ти, блок 12 микропрограммного управ ления, коммутатор 13, блок 14 форми рования топологии исследуемого графа, блок 15 формирования адреса, блок 16 сравнения и блок 17 вьщеления циклов. Блок 12 микропрограммного управления образуют узел 18 памяти, узел 0 19 формирования сигналов перехода и узел 20 формирования сигналов управления . Узел 18 памяти содержит первую группу элементов ИЛИ 21, вторую группу элементов ИЛИ 22, первую группу элементовИ 23, вторую группу элементов И 24, группу триггеров 25 основной памяти, вход запуска триггеров 26, группу триггеров 27 вспомогательной памяти, дешифратор 28 алфавита состояний, триггер 29 управления, элемент И 30 и генератор 31 тактовых импульсов. Узел 19 формирования сигналов перехода состоит из первой группы элементов И 32, группы элементов И-ИЛИ 33, группы элементов ИЛИ 34, шифратор 35. Узел 20 формирования сигналов управления выполнен на элементах ИЛИ 36. Блок 14 формирования топологии исследуемого графа образуют матрица триггеров 37 и группа элементов И 38. Блок 17 вьщeJfeния циклов содержит первый 39, второй 40 и третий 41 узлы памяти, а также первую группу элементов ИЛИ 42 и вторую группу элементов ШШ 43. Первый узел памяти 39 состоит из дешифратора 44 адреса, первой группы элементов И 45, группы регистров 46, второй группы элементов И 47, счетчика 48 адреса и регистра 49. Второй узел памяти 40 образуют первая группа элементов И 50, вторая группа элементов И 51, группа регистров 52, дешифратор 53 адреса, регистр 54 и счетчик 55 адреса. Третий узел 41 памяти содержит первую группу элементов И 56, вторую группу элементов И 57, группу регистров 58, дешифратор 59 адреса, группу элементов ИЛИ 60, регистр 61 и счетчик 62 адреса. Блок 15 формирования адреса выполнен на счетчике 63 строк, счетчике 64 столбцов, счетчике 65, буферном регистре 66, первой группе элементов ИЛИ 67, второй группе элементов ИЛИ 68, дешифраторе 69 столбцов, дешифраторе 70 строк, третьей группе 55 элементов ИЛН 71, триггере 72 признака и триггере 73 управления, Коммутатор 13 состс т из п групп по п элементов И 74 в каждой и группы выходных элементов И 75. Блок 16 сравнения содержит элемент ИЛИ 76, группу элементов И 77 и триггер 78 сравнения. Матричная модель сети 1 содержит i, j триггеров 1I по числу строк и столбцов (где i, j l,n; n - число вершин моделируемого графа), выходы которых в строках подключены к входам соответствующих элементов ИЛИ-НЕ 2, выходы которых подключены к управляющим входам соответствующих элементо И 5 второй группы, а входы i, j три геров 11 в столбцах подключены к вы ходам соответствующих счетчиков 6 весов дуг. Выходы элементов И 5 второй группы подключены к входам соответствуюш|1х счетчиков 6 весов дуг. Количество элементов И 8 первой группы, элементов И 5 второй группы регистрирующих счетчиков 9, счетчиков 6 весов дуг и триггеров 7 управления определяется количеством столб цов матричной модели сети 1. Выход блока 12 микропрограммного управлени соединен с соответствующими входами коммутатора I3, блока I4 формирования топологии исследуемого графа,, блока 15 формирования адреса, блока 16 сравнения и блока 17 выделения цик лов. Блок 12 микропрограммного управл ния (фиг. 3) служит для выработки , последовательности управляющих единичных сигналов, распределенных во времени для управления работой с блоков устройства. Программа работы бло ка 12 приведена на фиг. 2. Узел 18 памяти (фиг. 4) служит для задания алфавита состояний памяти С -С j . Узел 19 формирования сигналов перехода (фиг. 5) предназначен для выработки единичных сигналов, необходимых для перехода блока управления в одно из состояний алфавита состояний памяти С,-С . Узел 20 формирования сигналов управления (фиг. 6) применяется i для выработки последовательности управления единичных сигналов. Коммутатор 13 (фиг. 13) обеспечивает доступ к выходу каждого триггера (ячейки) блока 14 формирования топологии исследуемого графа Коммутатор 15 состоит из n групп по п элементов И 74 в каждой (где п - число вершин графа), каждый элемент И 7,4 представляет собой трех1204 входовый элемент И и элементы И 75 , по числу выходов элементов И 74. . Для обращения к каждому триггеру (ячейке) блока 14 необходимо задать адрес строки и столбца, на пересечении которых находится данная ячейка. Поэтому каждый элемент И 74 содержит два адресных и один информационный входы. Элементы И 75 служат для стробирования выходов элементов и 74. Стробирование осуществляется единичным сигналом Yjg с управляющего входа коммутатора.Блок 14 формирования топологии исследуемого графа (фиг. 7) записывает и хранит информации о топологии исследуемого графа. Блок состоит из матрицы триггеров (ячеек) 37 и группы двухвходовых элементов И 38. Триггеры 37 являются формирователем дуг и устанавливаются в единичное состояние, если есть дуга из i-й вершины в j-ю вершину, или в нулевое состояние, если вершины исследуемого графа дугой не связаны. Элементы И 38 -38 служат для стробирования выходов триггеров 37. Стробирование осуществляется единичным сигналом Yj . Блок 15 формирования адреса (фиг. 12) обеспечивает выработку значений адреса строк и адресастолбцов g;(-gri с целью осуществления доступа к выходу каждого триггера (ячейки) 37 блока 14 через коммутатор 13. Блок сравнения 16 (фиг. 14) осуществляет сравнение значений триггеров (ячеек) 37 блока 14 со значением, определенным триггером 78 сравнения, который устанавливается в единичное состояние единичным сигналом. Блок 17 выделения циклов служит для хранения значений счетчика строк 63 и счетчика столбцов 64 блока формирования адреса 15. Первый узел 39 памяти предназначен для хранения значений счетчика строк 63 блока 15 регистры 46,, дешифратор 44 адреса и для осуществления доступа к каждому регистру На один вход элементов И 45 подается значение с выхода дешифратора адреса 44 (выборка регистра по адресу), а на другой единичный сигнал У блока 12, разрешающий запись информации в один из регистров 46f-46я. Выходы злемен тов и 45 подключены к входам, стробирующим запись информации в соответствующий регистр (адрес каторого выбраь. На один вход элементов И 47 7 подается значение с выхода дешифратора 44 адреса (выборка регистра по адресу), а на дру гой - единичный сигнал блока 12 разрешающий чтение информации из регистров 46д-46|. Выходы элементов И 47 подключены к входам, стро бирующим чтение информации из соответствующего регистра 46 (п (ад рес которого выбран). Счетчик 48 ад реса служит для выработки позиционного кода адреса регистра из группы регистров , регистр 49 - для хранения текущих значений счетчика 48 адреса. Второй узел 40 памяти обеспечивает хранение значений счетчика 64 столбцов блока 15 формирования адре са. Третий узел 41 памяти служит для дублирования второго узла 40 памяти Назначение элементов узлов 40 и 41 памяти аналогично назначению элемен тов узла 39 памяти. I Принцип работы предлагаемого уст ройства заключается в следующем. Путь в графе можно определить как последовательность вершин от данной вершины до конечной, связанных дугами. Если какой-либо путь в графе содержит несколько одинаковых вершин, значит в графе существует цикл. Предлагаемое устройство при отсутствии циклов в исследуемых графа работает в два этапа.- На первом эта пе происходит исследование графа на наличие циклов и в случае их отсутствия начинается второй этап, в результате которого вырабатывается единичный потенциал, разрешающий ра боту устройства. Граф описьюается матрицей смежности А отображающей его топологию. Матрица имеет размерность пдп (где п - число вершин в графе). Если существует дуга из i-й вершины в j-ю вершину графа, то на пересечении строки с номером i (i-я вершина) и столбца с номером j (j-я вершина гр фа) записьгоается единица. Если дуга отсутствует, записывается нуль. Если в строке с номером i существует несколько единиц (выходящие 806 цуги), значит из i-й вершины выходит несколько путей. Если в столбце с номером j существует несколько единиц (входящие дуги) значит в j-ю вершину входит несколько путей в графе. Чтобы иметь информации о связях i-й вершины, необходимо в результате просмотра i-й строки выявить выходятдие дуги, а в результате просмотра столбца с номером выявить входящие дуги. Если в i-ю вершину нет входящих дуг (столбец с номером - нулевой), значит такая вершина в путях графи не может быть звеном цикла. Поиск циклов в графах производится следующим способом. а). Последовательно, начиная с первой вершины в графе путем просмотра столбца матрицы смежности А с номером j (j l,n, где п - число вершин графа), определяют входящие в j-ю вершину графа связи. Номера этих вершин заносятся в одномерный массив S. В качестве элементов S (К1) массива S выступают значения номеров строк, на пересечении с которыми в столбце с номером j записана единица (S(Kl)i, где , - число единиц в J-м столбце матрицы смеж ности А). Максимальное З11ачение т равно (числу вершин графа). Технической реализацией одномерного массива S является первый узел 39 памяти блока 17 выделения циклов. . б). Если входящие связи отсутствуют, рассматривают следующую вершину на наличие входящих дуг переходят к пункту (а) и рассматривают следующий столбец , если нет - переходят к пункту (в). в). Проверяют нет ли непосредственной связи из i-й вершины () в одну из вершин, являющихся элементами массива S. Если такая связь существует, то элемент матрицы смежлости (A,g{,(,j 1 равен единице CA,-stK,) , где К1 1,т. г). Если вьтолняется хотя бы одно равенство пункта (в), значит существует цикл. д). Если ни одно равенство пункта (в) не выполняется, необходимо в результате просмотра строки с номером выявить выходящие из i-й вершины дуги и зафиксировать номера вершин в одновременном массиве МЗ. Элементами массива МЗ являются значения номеров j столбцов, в которых на пересечении с i-й строкой записа ны единицы (M3(K2)j, ,Г), где t - число дуг, выходящих из i-й вершины. Максимальное число /j. равн (п - число вершин в графе) . Зна чение элементов массива МЗ (К2) необходимо переписать в аналогичный одномерный М4 (КЗ)Ю (К2) , где . Технической реализацией массивов МЗ и М4 служат соответственно второ 40 и третий 41 узлы памяти блока 17 выделения циклов. е). Для .каждого элемента массива МЗ необходимо проверить нет ли непосредственной связи из вершин с но мерами МЗ (К2) где К2Н , f в одну из вершин S(K1), ,mg. AM3(K2),S(K1) 1 . Если выполняется хотя бы одно равен ство, значит существует цикл. ж). Если ни одно равенство пункта (е) не вьшолняется необходимо в результате просмотра строк с номерами М4 (КЗ), где ,1 , выявить выходящие из этих вершин связи и зафиксировать номера вершин в одномерном массиве МЗ, а затем после вы явления всех исходящих дуг-из вершин с номерами, равными значениям элементов массива М4, переписать значения элементов массива МЗ в мас сив М4. Затем переходят к пункту (е), если в пункте (ж) не получают нулевой массив МЗ (т.е. находятся в конечной вершине, из которой не существует исходящих дуг). Если массив МЗ ненулевой, просмотрены не все вершины графа на пред мет наличия входящих дуг и не обнаружено циклов в пунктах (в) и (е), переходят к пункту (а), в другом случае вырабатывается единичный сигнал о том, что в графе не существует циклов, разрешающий работу устройства. В этом случае начинается второй этап работы и вычисление максимальны путей в графах. Блок 12 микропрограммного управле ния выполнен в виде конечного автома та ура по модели Уилкса-Стринджера, структура которого определяется структурой алгоритма работы блока 12 Блок 12 характеризуется алфавитом входных сигналов Р. -Р (признаков) , 808 алфавитом выходных сигналов алфавитом состояний памяти , функцией выходов Л и функцией перехог дов о : c(t)(c(t-l),p(t)) - функция переходов ; У(t) (c(t)) - функция выходов. Для задания алфавита состояний памяти Cp-c,j входят отметки на входах всех с 1-й по 44-ю операторных и условных вершин алгоритма работы блока 1 2. Символы У, , записанные в операторные вершины, являются выходными 12. сигналами блока Работа блока 12 стробируется генератором тактовых импульсов 31. Тактовые импульсы с генератора тактовых импульсов 31 поступают вместе с сигналом алфавита входных сигналов Р -Р. если он существует. Пока действует . синхроимпульс, состояние триггеров 25 основной памяти не изменяется, хотя состояние триггеров 27 вспомо- гательной памяти может изменяться. Состояние триггеров 25 основной памяти изменяется, когда синхроимпульс прекращается. Этим обеспечивается устойчивость работы блока 12, так как пока действует синхроимпульс, триггеры основной памяти 25 не переходят в новое состояние. Алфавит состояний памяти кодируется двоичным кодом, снимаемым с выходов триггеров 25 основной памяти. Входы триггеров 27 вспомогательной памяти связаны с выходами шифратора 35, на выходах которого формируется двоичный код, устанавливающий триггеры 27 вспомогательной памяти в новое состояние алфавита состояний памяти с -С- . Импульсы генератора 31 тактовых импульсов поступают на триггер 29 управления через элемент И 30, на выходы которого подается информация о том, что блок 12 находится в начальном состоянии с (устанавливается перед началом работы подачей сигнала на вход Уст.О)- Для инициации работы блока управления необходима подача единичного пускового импульса на вход Пуск узла 18 памяти блока 12. Дешифратор 28 алфавита состояний памяти преобразует позиционный код на выходе триггеров 25 основной памяти в унитарный код. Выходные управляющие сигналы Уалфавита выходных сигналов вырабатываются в зависимости от состояния алфавита состояний памяти , , в которое перешел блок 12 управления. Если один и тот же сигнал вырабатывается в различных состояниях алфави та состояний памяти Сд-с. блока 12 то соответствующие выходы дешифратора 28 алфавита состояний памяти долж ны объединяться схемой ИЛИ. Например, согласно алгоритму рабо ты блока 2 единичный сигнал Yj выра батывается, когда блока 12 переходит в состояние с. или с алфавита состояний памяти. Поэтому соответствующие выходы дешифратора 28 алфавита объедисостояний памяти (сд и няют элементом ИЛИ 36. Блок 12 переходит в новое состояние в зависимости от состояния в пре дьщущий момент времени и от сигналов алфавита входных сигналов (Р -Р-). Закон перехода блока 12 в новое состояние алфавита состояний памяти определяется алгоритмом работы блока управления (фиг. 2). Например, для перехода в состояние Cg алфавита состояний памяти необходимо находиться в состоянии С, алфавита состояний памяти. Такой переход осуществляется из состояния С на очередном такте работы блока 12 микропрограммного управления при наличии сигнала алфавита входных сигналов Р.. ,Цля выполнения тактового услови необходимо объединить выход С. дешифратора 28 алфавита состояний памяти и вход Р элементом И 32. Сигналы входного алфавита поступают ка первый и второй информационные зходь блока 1 2 . Выход элемент И 32 обозначен буквой Ь,.. Соединив выход элемента И 32 с пятым входом шифратора 35, на выходе шифратора 35 получают позиционный код 00101,. 5y,,Qi Блок 16 сравнения работает следую щим образом. Предположим, что на выходе элемен та ИЛИ 76 блока 16 сравнения имеется ноль, т.е. значение триггера (ячейки) 37.j блока 14 равно нулю, на выходе элемента И-НЕ 77 присутствует значение единицы. Если на выходе триггера 78 сравнения установлено значение единицы, на выходе элемента 77 находится нулевое значение. На выходе элемента И-НЕ имеется значение равное единице, следовательно на выходе элемента И-НЕ 72 появляетс значение, равное нулю. Признак Р равен нулю. Предположим, что на выходе элемента ИЛИ 20 блока 16 сравнения имеется единичное значение, т.е. значение триггера (ячейки) 37 блока 14 равно единице. Если на выходе элемента И-НЕ 77 присутствует единичное значение, признак Р, равен единице. Работа предлагаемого устройства осуществляется в два этапа., Предварительно на вход Уст.О узла 18. памяти блока 12 микропрограммного управления подается единичный сигнал, устанавливающий триггеры 27 вспомогательной памяти и триггеры 25 основной памяти в нулевой состояние , устанавливая блок 2 в исходное состояние алфавита состояний памяти Сдо Этот же ..сигнал поступает в блок 15 формирования адреса и устанавливает триггер 73 управления в нулевое состояние, устанавливая на управляющем выходе блока 15 нулевой потенциал . На первом этапе работы устройства в блок 14 и в матричную модель сети 1 заносится информация о топологин исследуемого гра,фа, отображаемая матрицей смежности А. В счетчики весов дуг 6 занесены числа импульсов, дополняющие веса вершин до полной емкости счетчиков информации о том, что блок 12 находится в начальном состоянии (единичный потенциал на выходе С,, дешифратора 28 алфавита состояний памяти) поступает на вход С узла 8 памяти блока 2. С появлением единичного пускового сигнала на входе Пуск узла 8 памяти блока I2 начинается работа устройства. Работа блока 12 синхронизируется генератором 31 тактовых импульсов, тактовые импульсы которого определяются максимально возможным временем срабатывания схемных элементов устройства и через элемент И 30 при наличии единичных потенциалов на входах Пуск и С поступают на триггер 29 управления, управляя работой блока микропрограммного управления 12. Работу устройства проследим по алгоритму работы устройства. 1. На первом такте генератора тактовых импульсов 31 блок I2 переходит в состояние С. алфавита состояний памяти, и одновременно вырабатывается последовательность единичных сигналов Уд , Yg. , У. (оператор 1) . С нал У. поступает в блок 15 и устан ливает счетчик 65 в нулевое состоя ние . , Сигнал Ура поступает в блок 16 сравнения и устанавливает триггер 78 сравнения в единичное состояние Сигнал У, поступает в блок 17. и обнуляет регистры 46 узла 39 пам ти, регистры 58 узла 40 памяти, ре гистры 50 -50„„ узла 41 памяти. 2, Блок 12 микропрограммного уп равления переходит в состояние С алфавита состояний памяти, и одновременно вырабатьшается последовательность единичных сигналов У (оператор 2).. У У зв -le М-д д поступает в блок 15 Сигнал X на счетчик 65 и увеличивает его зн чение на единицу (СТ ). Сигнал y,j поступает в блок 15 н триггер 72 признака, устанавливая признак Р,. в нулевое состояние. ; Сигналы , У,. , поступают блок 17 и обнуляют соответственно счетчик 62 адреса узла 41 памяти (СТ .д 0) , счетчик 55 адреса узла .40 памяти (CTjj 0) и счетчик 48 адреса узла 39 памяти (). Сигнал У. поступает в блок 15, обнуляя значение счетчика 63 строк (). 3.Блок 12 переходит в состояние С,, и одновременно вьфабатывается последовательность единичных сигналов У , .У, УЙ (оператор 3). Сигнал У2 поступает в блок 15 на счетчик 63 строк, увеличивая его значение на единицу (CTg CTjg+l) Сигнал У поступает в блок 15, стробируя выход счетчика 65. Сигнал Уд поступает в блок 15, стробируя вход счетчика 64 столбцов При одновременной выработке сигналов У. , У,, счетчику 64 столбцов 8 к присваивается значение счетчика Ь5 блока 15 ( ). 4,На следующем такте блок 12 пе реходит в состояние С алфавита соетояний памяти, и одйовременно выраба тывается последовательность единичных сигналов У 20 -ЗО y,g (оператор 4) Сигнал У поступает в блок 15, стробируя выход счетчика 63 строк, Сигнал Xj поступает в блок 15, стробируя выход счетчика 64 столбцов . Сигналы У, поступают в блок 15, стробируя соответственно выходы дешифраторов 70 и 69. Сигнал поступает на коммутатор 13, стробируя его выход. Сигнал поступает в блок 14, стробируя выходы триггеров 37. Таким образом, при одновременной выработке сигналов в регистре из группы регистров 46 первого узла 39 памяти блока 17 записывается значение счетчика 63 строк блока 15 согласно значению адреса первого узла 39 памяти (счетчик 48 адреса). 8 На следующем такте блок 12 переходит в состояние С., и одновременно вырабатываются единичные сигналы (оператор 8). Сигнал поступает в блок 17 на первый узел 39 памяти, стробируя выход счетчика 42 адреса. Сигнал УЗ поступает в блок 17 на первый узел памяти 39, стробируя вход регистра 49. При одновременной вьфаботке сигналов в регистр 49 блока 17 первого узла 39 памяти записывается значение счетчика 48 адреса ( СТ,, ) . 9. На следующем также блок 12 переходит в следующее состояние алфавита состояний памяти в зависимости от значения сигнала алфавита входных сигналов. Если признак Р , вырабатываемый в блоке 15 (значение счетчика строк 63 равно п), равен нулю переходят к пункту 3, если нет - к пункту 10. 10. Блок 12 (оператор 10) переходит в следующее состояние в зависимости от сигнала алфавита входных сигналов. Если признак Р , вырабатываемый в блоке 17 (значение счетчика 48 адреса равно нулю), равен нулю, переходят к пункту 2, в другом случае к пункту 11. В пунктах 2-10 происходит просмотр столбца матрицы смежности А (техническая реализация матрицы смежности блок 14) с номером, определяемым счетчиком 65 блока 15., и выявление связей, входящих в вершину с номером, определяемым счетчиком 65. Номера ЭТИХ вершин заносятся в одномерный массив S (техническая реализация массива S - первый узел 39 памяти блока 17). Для обеспечения возможности обращения к каждому регистру 46 с целью хранения номеров вершин первого узла 39 памяти, в него введен счетчик 48 адреса, дешифратор 74 адреса и регистр 49 для оперативного хранения значений счетчика 48 адреса. Счетчик 48 адреса является технической реализацией переменной К1. Когда весь столбец просмотрен (значение счетчика строк 63 бло ка 15 равно п), в регистрах первого узла 39 памяти блока 17 находится информация о всех связях, входящих в вершину с номером,- определяемым счетчиком 65 блока 15, а в регистре 49 содержится значение, характеризующее число элементов массива S. i1. Блок микропрограммного управ ления 12 переходит в следующее состо и одновременно выраба яние У тьшается последовательность единичУ., (оператор 11). ных сигналов У, Сигнал У поступает в блок 15, стробируя выход счетчика 65. Сигнал поступает в блок 15, стробируя вход буферного регистра 6 При одновременной выработке этих сигналов в буферный регистр 66 запи сывается значение счетчика 65 блока 15. 12.Блок 12 переходите состояние С алфавита состояний памяти, и одновременно вырабатывается последовательность единичных сигналов У / (оператор 12). Сигнал У, поступает в блок 15, стробируя вход счетчика строк 63. Сигнал У , поступает в блок 15, стробируя выход буферного регистра 66 . При одновременной выработке сигналов значение буферного регистра 66 записывается в счетчик строк 63 блока формирования 15 адреса, 13.На следующем такте блок микропрограммного управления 12 переходит в состояние С алфавита состояний памяти и одновременно выраба тывается последовательность единичУ (опе ных сигналов ратор 13). Сигнал У,,| поступает в блок 17 выделения циклов на первый узел 39 памяти, стробируя выход счетчика 48 адреса. блок 17 Сигнал У„ 2g поступает в на первый узел памяти 39, стробируя выход дешифратора 74 адреса. Сигнал X поступает в блок 15 формирования адреса, стробируя вход счетчика 64 столбцов. Сигнал У стробирует выход дешифратора 70 строк. Таким образом, при одновременной вьгработке сигналов значение регистра 46 первого узла 39 памяти блока 17 (согласно адресу, вырабатьшаемому счетчиком 48 адреса), посылается в блок 15 на счетчик 64 столбцов. 14.Блок 12 переходит в состояние С алфавита состояний памяти и одновременно вырабатывается последовательность единичных сигналов 4 т. ав. У,9 V УЗО (оператор 14). Действие оператора аналогично действию оператора пункта 4 (значение триггера (ячейки) 37 блока 14 формирования топологии (согласно адресу) посылается в блок 16 сравнения). 15.На следующем такте (оператор 15) блок 12 переходит в следующее состояние алфавита состояний памяти в зависимости от значения сигнала алфавита входных сигналов. Если признак Р (признак срабатывания блока сравнения на равенство, т.е. значение ячейки блока 14 равно единице) равен нулю, переходят к пункту 16, в противном случае - к пункту 30. 16.Блок 12 переходит в состояние алфавита состояний памяти (оператор 16) и одновременно вырабатывается единичный сигнал (оператор 16), поступающий в блок 17 на счетчик 48 адреса первого узла 39 памяти и уменьшающий значение счетчика адреса 48 на единицу. 17.На следующем также происходит переход по сложному условию. Если признак Р (вьфабатывается в первом узле 39 памяти блока 17 и характеризует нулевое состояние счетчика адреса 48 блока) равен нулю, переходят к пункту 14, если нетк пункту 18. 18, Если признак Р (вырабатывается во втором узле памяти 40 блока 17 и характеризует нулевое значение счетчика адреса 55 блока) равен нулю, переходят к пункту 43, в другом случае - к пункту 19 . 19. Если признак (вьфабатывается в блоке 15 триггером 72; признак Pg О можно харакг ризовать как признак начала работы, т.е.-просмотра новой вершины на наличие входящих дуг) равен нулю, переходим к пункту 22, если нет - к пункту 20. В пунтках 11-18 npoHcxoAH следующее действие. В буферный регистр 66 блока 15 записывается либо значение счетчика 65, характеризующее номер очередной вершины, исследуемой на наличие дящих дуг, либо значение массива МЗ (техническая реализация массива МЗ второй узел 40 памяти блока 17) и проверяется по пункту 15, нет ли непосредственной связи из вершины с номером, характеризуемым значение буферного, регистра 66 с одной из вершин массива S (первый узел 39 па мяти) блока 17. Обозначим буферный регистр 66 условно буквой т. Происходит следующая проверка. Значение элемента s(tn} матри смежности равно единице. По пункту 12 значение буферного регистра 66 записывается в счетчик строк 63 блока 15, по пункту 13 оче редное значение элемента массива S (содержание одного из регистров 46 первого узла 39 памяти блока 17) согласно значению счетчика 48 адреса блока 17 (К1) записьгоается в сче чик 64 столбцов блока 15. По пункту 14 согласно значениям счетчиков строк 63 и столбцов 64 блока 15 выбирается значение тригге ра (ячейки) 32 блока 14, поступающее в блок 16 сравнения. Если такая связь существует (при нак Р 1), следовательно существует цикл (пункт 15), если нет, уменьщаю значение счетчика 48 адреса на едини цу и повторяют проверки до тех пор, пока не просмотрят весь массив S. Признаком этого является равенство нулю значения счетчика 48 адреса первого узла 39 памяти блока 17 (Р Проверка признака Р происходит в пункте 17 . Если в буферный регистр 66 записываются элементы массива МЗ (второй узел 40 памяти блока 17), то критерием перебора всех элементов массива МЗ служит .равенство нулю значения счетчика 55 адреса второго узла 40 памяти. Это характеризует признак Р- (пункт 18). 20. Блок 12 переходит в состояние С , алфавита состояний памяти, и одновременно вырабатывается последовательность единичных сигналов , У, У (оператор 20). Сигнал g поступает в блок 17 на третий узел 41 памяти, стробируя выход счетчика 62 адреса. Сигнал поступает в блок 17 на третий узел 41 памяти, стробируя выход дешифратора 59 адреса. Сигнал У поступает в блок 17 на третий узел 41 памяти, разрешая чтение информации из регистров 58.. Сигнал поступает в блок 15, стробируя вход буферного регистра 66. Таким образом, при одновременной выработке последовательности сигналов значение регистра 58 третьего узла 41 памяти блока 17 согласно адресу, вырабатываемому счетчиком адреса 62, посылается в буферный регистр 66 блока 15. 21. На следующем такте блок управления переходит в состояние алфавита состояний памяти. Одновременно вырабатьшается сигнал У., (оператор 21), поступающий в блок 17 на третий узел 41 памяти и уменьшающий значение счетчика 49 адреса 49 на единицу. 22. Блок переходит в состояние С, .j- алфавита состояний памяти, и одновременно вырабатывается единичньй сигнал У} (оператор 22), поступающий в блок 15 и обнуляющий счетчик 64 столбцов. 23.Блок 12 переходит в состояние С. алфавита состояний памяти, и одновременно вырабатывается единичный сигнал У (оператор 23) , поступающий в блок 15 и увеличивающий значение счетчика столбцов 64 блока 15 на единицу. 24.Блок 12 переходит в состояние С алфавита состояний памяти, и одповременно вырабатывается последовательность единичных сигналов У, (оператор 24). Сигнал У, поступает в блок 15, стробируя вход счетчика 63 строк. Сигнал У,, поступает в блок15, стробируя выход буферного регистра 66 блока. Таким образом значение буферного регистра 66 блока 15 записывается счетчик 63 строк. 25. Блок 12 переходит в состояние алфавита состояний памяти и одновременно вырабатывается последовательность единичных сигналов У , У , 17 У (оператор 25). 19 го 30 ствие оператора 25 аналогично дейст вию оператора 14 (пункт 14) (значен триггера (ячейки) 37 блока 14 согла но адресу) посылается в блок сравн ния 16. 26, Блок 12 переходит в следующе состояние. Если признак Р- (вырабатывается в блоке 16 сравнения и является кри терием срабатывания блока сравнения на предмет равенства) равен единице (значение триггера (ячейки) 37 блок 14 равно единице), переходят к пунк ту 27, в другом случае - к пунту 30 27..Блок 12 переходит в состояние С,- , и одновременно вырабатывае ся единичный сигнал (оператор 2 который поступает в блок 17 на второй узел 40 памяти и увеличивает на единицу значение счетчика адреса 55 блока. 28. Блок 12 переходит в состояни Cjg , и одновременно вырабатывается последовательность единичных сигна 33 лов У,, , УОС , у,, , У 41 3S Сигнал У поступает на второй узел 40 памяти блока 17, стробируя выход счетчика 55 адреса. Сигнал Уз5 поступает на второй узел 40 памяти блока 17, -стробируя выход дешифратора 53 адреса. Сигнал У поступает на второй узел 40 памяти, разрешая запись информации в регистры 52. Сигнал УТ поступает в блок 15, стробируя выход счетчика 64 столбцов . Таким образом, при одновременной выработке такой последовательности в регистр из группы регистров 52 второго узла 40 памяти блока 17 сог ласно адресу СТ 55 (значение счетчи ка 55 адреса служит адресом выбираемого регистра) записывается значение счетчика столбцов 64 блока 15. 29. Блок 12 переходит в состояни , и одновременно вырабатывается последовательность единичных сигналов У , У, . Сигнал У, поступает на второй узел 40 памяти блока 17, стробирул выход счетчика 55 адрес а. Сигнал У. поступает на второй узел 40 памяти блока 17, стробируя вход регистра 54. При одновременной выработке сигналов значение счетчика 55 адреса 0 второго узла 40 памяти блока 17 запи сывается в регистр 54 блока. Блок 12 переходит в состояние,С при этом последовательности единичных сигналов не вырабатываются. Блок 12 переходит в следующее состояние алфавита состояний памяти в зависимости от сигналов входного алфавита. Если признак Р (вьфабатывается в блоке 15 и говорит о том, что значение счетчика столбцов 64 блока 15 равно п) равен нулю, переходят к пункту 23, если нет - к пункту 31. 31.Если признак Pg вырабатывается в блоке 15 (триггер 72) и характеризуется как признак начала работы, т.е. просмотра новой вершины на наличие уходящих дуг) равен нулю, переходят к пункту 32, если нет к пункту 33. 32.Блок 12 переходит в состоя2g, и одновременно вьфабатьшается единичный сигнал у. g , поступающий в блок 15 на триггер 72 и устанавливающий триггер 77 в единичное состояние Р 1, переходят к пункту 34. 33. Если признак Р. (вырабатывается в блоке 17 в третьем узле 41 памяти и информирует о том, что значение счетчика адреса 62 равно нулю) равен нулю, переходят к пункту 20, в другом случае - к пункту 34. 34. Если признак Р (вьфабатывается во втором узле 40 памяти блока 17 и информирует о том, что значение счетчика адреса 55 равно нулю) равен нулю, переходят к пункту 35, если нет - к пункту 36. . 35. Блок 12 переходит в состояние Сд, и одновременно вьфабатывается последовательность единичных сигналов , У. Сигнал У поступает на второй узел 40 памяти блока I7, стробируя выход регистра 54. Сигнал поступает на третий узел 41 памяти блока 17, стробируя вход регистра 61. При одновременной выработке сигналов У,,, в регистр 61 блока 17 (третий узел памяти записывается значение регистра 54 (второй узел 40 памяти). 37. Блок 12 переход-«г в состояние C.jj алфавита состояний, и одновременно вырабатывается последовательность единичных сигналов У , (оператор 37). Сигнал поступает в блок 17 на третий узел 41 памяти, стробиру вход счетчика 62 адреса. Сигнал У поступает в блок 17 на третий узел 4) памяти, стробиру выход регистра 61. 39. Блок 12 переходит в состоян С-,, , и одновременно вырабатывается 6 последовательность единичных сигна лов , У, У, У, , УЗ (опера тор 39) . Сигнал y.j поступает в блок 17 на третий узел 41 памяти 41, строб руя выход счетчика 62 адреса. Сигнал Уг2 стробирует выход дешиф ратора адреса третьего узла 41 памяти. Сигнал разрешает запись информации в регистры 58 блока 17 (тр тий узел 41 памяти) Сигнал У поступает в блок 17 на второй узел 40 памяти, стробируя выход счетчика 55 адреса. Сигнал У-1С поступает в блок 17 на второй узел 40 памяти, стробируя выход дешифратора 53 адреса. Сигнал У поступает в блок 17 на второй узел памяти 40 и разрешает чтение информации из регистров 52. Лри одновременной выработке этой последовательности в один из регист ров 58 третьего узла 4 памяти блока 17 согласно адресу счетчика 61 адреса (значение счетчика 61 служит адресом выбираемого регистра) записывается значение одного регистра 5 согласно адресу счетчика адреса 55 (значение счетчика 55 служит адресо выбираемого ре1 истра) . 40.Блок 12 переходит в состояние С алфавита состояний, и одновременно вырабатывается последовательность единичных сигналов У , Сигнал поступает на второй узел 40 памяти блока i 7, уменьшая значение счетчика адреса 55 на единицу . Сигнал . поступает на третий узел памяти 41 блока 17 и уменьшает значение счетчика адреса 62 на единицу. 41.Блок 12 переходит в следующе состояние в зависимости от сигнала входного гОтфавита. 8020 Если признак Рд (вырабатывается во втором узле памяти 40 блока 17 и информирует о том, что значение счетчика адреса 55 равно нулю) равен нулю, переходят к пункту 39, если нет - к пункту 42. 42. Управляющий автомат переходит в состояние , и одновременно вырабатьшается последовательность единичных сигналов , , У , . Сигнал Уду поступает в блок 17 на второй узел 40 памяти, стробируя выход регистра 72. Сигнал поступает в блок 17 на второй узел 40 памяти, стробируя вход счетчика 55 адреса. Сигнал УС. поступает в блок 17 на третий узел 41 памяти, стробируя выход регистра 61. Сигнал поступает в блок 17 на третий узел 41 памяти, стробируя вход счетчика 62 адреса. При одновременной выработке такой последовательности сигналов значение регистра 54 записывается в счетчик адреса 55 второго узла 40 памяти блока 17, а значение регистра 61 записывается в счетчик 62 адреса третьего узла 41 памяти блока 17., 43. Блок 12 переходит в состояние , И одновременно вырабатьшается последовательность единичных сигналов У. , У , У , У (оператор 43). Л5 л ,} Сигнал У,, поступает в блок 17 на второй узел 40 памяти, стробируя выход счетчика 55 адреса. Сигнал поступает в блок 17 на второй узел 40 памяти, стробируя выход дешифратора адреса 53. Сигнал У,с поступает в блок 17 на второй узел 40 памяти, разрешая чтение информации из регистров 52. Сигнал У|, поступает в блок 15, стробируя вход буферного регистра 66. Таким образом, при одновременной выработке этой последовательности сигналов в буферный регистр 66 блока I5 записьшается значение одного из регистров 52 второго узла 40 памяти блока 17 согласно адресу выби- раемого регистра, в качестве которого принимается значение счетчика 55 адреса. 44. Блок 12 переходит в состояние Cj , и одновременно вырабатьшается последовательность единичных сигнал Сигнал У.у уменьшает значение сче чика 55 адреса во втором узле 40 па мяти блока 17 на единицу. Сигнал У-,2 поступает в блок 17 на первый узел 39 памяти, и стробируя вход счетчика 48 адреса. Сигнал поступает в блок 17 на первьлй узел 39 памяти, и стробируя выход регистра 49. Таким образом, при одновременной выработке сигналов значение счетчика 55 адреса второго узла 40 памяти блока 17 уменьшается на единицу и в счетчик 48 адреса записьтается зн чение регистра 49 в блоке 17; переходят к пункту 12. 36. Управляющий автомат переходи в следующее состояние. Если признак Pj (вырабатывается в блоке 15 и информирует о том, что значение счетчика 65 равно п) равен нулю, переходят к пункту 2, если нет - к пункту 38. 38. Блок 12 переходит в состояни и одновременно вырабатывается единичный сигнал У , поступающий в блок 15 и устанавливающий триггер управления 73 в единичное состояние Происходит переход блока 12 в следующее состояние и работа блока управления заканчивается (процесс выявления циклов окончен). На этом завершается первый зтап работы устройства. Если в графе нет циклов, то в результате первого зтапа работы устройства триггер управления ус танавливается в единичное состояние и единичный потенциал на выходе три гера управления 73 служит пусковым сигналом на входе элемента И 4. Начинается второй этап работы устройства, на котором, в случае отсутствия циклов происходит вычисление максимальньпс путей с помощью известного устройства. Если циклы существуют, и триггер 73 управления блока 15 не устанавливается в единичное состояние и второй этап работы отсутствует, т.е. в циклических графах максимальные пути не вычисляются. В пунктах I9-30 происходит следующее . Если до пункта 19 (пункт 15) цик лов не обнаружено, необходимо выя0-22вить выходящие связи (дуги) из i-й вершины. Если признак Р (пункт 19)равен нулю, значит рассматривается следующая вершина на наличие входящих дуг (начала нового этапа обработки информации) . В этом случае массив М4 еще не- сформирован (техническая реализация массива М4 - третий- узел 41 памяти блока 17) и в качестве номера (т) i-й вершины принимается значение счетчика 65 блока 15. Если массив М4 сформирован (признак Р 1) значит необходимо в качестве номера i-й вершины просмотреть все значения массива М4. Для этого в пункте 20 очередное значение элемента массива М4 (один из регистров 58) согласно адресу счетчика адреса 49 (КЗ) записывается в буферный регистр 66 (т) блока 15. Затем начинается просмотр строки матрицы смежности (техническая реализация - блок 14 формирования топологии исследуемого графа). В пункте 21 происходит уменьшение значения счр.тчика адреса 62 (КЗ) на единицу. Необходимо просмотреть строки с номером та (в качестве значения m служит значение регистра 65 блока 15 или значение элемента массива М4 (третий узел 41 памяти блока 17). Для этого счетчика 64 столбцов блока 15 обнуляется в пункте 22, а в пункте 23 увеличивается значение счетчика 64 столбцов блока 15. В пунктах 24-26 происходит выборка значения триггера (ячейки) блока 14 и в блоке 16 сравнения происходит сравнивание значения ячейки 37ij с единичным значением триггера 78 сравнения блока 16. Если значение триггера (ячейки) 37,-j блока 14 равно единице (обнаружили очередную дугу), выходящую из вершины), происходит заполнение очередного элемента массива МЗ. Для этого в пункте 27 устанавливается новое значение счетчика 55 адреса (К2), согласно этому значению адреса 55 в Здин регистр 52 записывается значение счетчика 64 столбцов блока 15 (пункт 28), а в пункте 29 значение счетчика 55 адреса второго узла 40 памяти блока 17 записывается в регистр 54 блока. Если просмотрена вся строка {признак Р) равен единице оператор 30), и регистре 54 второго 23 блока памяти записано количество связей, выходящих из i-й вершины (число элементов массива МЗ). Операция просмотра строк продолжается в зависимости от числа элементов массива М4 (элементы массива М4 служат нумерацией строк) или просматривается одна строка с номером, равным значению RG, блока 15, если признак Р равен нулю.Если все элементы массива просмотрены (признак Р. 0), т.е. значение КЗ равно ну лю (счетчик 62 адреса), значит сформирован новый массив МЗ (второй узел 40 памяти блока 17). Если вновь сфор мированный массив МЗ нулевой, выявленные выходящие из i-й вершины связи приходят в конечную, и, следовательно, если не все вершины в графе исследованы на наличие входящих дуг (признак (пункт 36), переходят к пункту 2 и процесс повторяется. Если массив МЗ ненулевой, его значения переписываются в массив М4 (второй узел 40 памяти блока 17) в пунктах 35-41 и после необходимых вспомогательных операций 42-44 переходят к пункту 12. Формула изобретения Устройство для определения максимальных путей в графах по авт.св. № 862145, отличающееся тем, что, с целью расширения области применения устройства путем обеспечения возможности исследования графов на наличие циклов и петель в них и повышения точности определения максимальных путей, в него введены блок сравнения, блок формирования адреса, коммутатор, блок вьщеления циклов и блок микропрограммного управления, блок формирования топологии исследуемого графа, содержащий группу элементов И и матрицу триггеров, блок выделения циклов содержит три узла памяти и две группы элементов ИЛИ, установочные входы триггеров являются установочными входами устройства, вход каждого i-ro триггера матрицы подключен к первому вхо ду i-ro элемента И группы блока формирования топологии исследуемого гра фа {где , 2, . . . , п п) , выходы элементов И группы блока формирования топологии исследуемого графа подключены к соответствующим информа 8024 ционным входам первой группы коммутатора, второй вход каждого i-ro эле мента И группы блока формирования топологии исследуемого графа подключен к i-му выходу группы выходов блока микропрограммного управления,информационные входы первого и второго узлов памяти объединены и подключены к выходу массива номеров вершин блока формирования адреса, первый и второй информационные выходы второго узла памяти подключены соответственно к первому и второму информационным входам третьего узла памяти, алоды разрешения записи всех узлов памяти объединены и подключены к выходу микроопераций блока микропрограммного управления, каждый i-й выход группы выходов первого узла памяти подключен к первому входу i-ro элемента ИЛИ первой группы блока выделения цикла, каждый i-й выход второй группы информационных выходов второго узла памяти подключен к первому входу i-ro элемента И второй группы блока выделения циклов, . второй вход которого подключен к i-му выходу группы выходов третьего узла памяти, выход каждого i-ro элемента ИЛИ второй группы блока вьщеления циклов подключен к второму входу i-ro элемента ИЛИ первой группы блока выделения циклов, выход которого подключен к одноименному входу группы информационных входов блока формирования адреса, выход формирования адреса которого подключен к второму информационному входу коммутатора, управляющий выход которого подключен к выходу микроопераций блока микропрограммного управления, выход коммутатора подключен к первому информационному входу блока сравнения, второй информационный вход которого подключен к выходу микроопераций блока микропрограммного управления, выход блока сравнения подключен к входу логического условия блока микропрограммного управления, вход комавды которого подключен к выходу формирования признака блока формирования адреса, вход микрокоманд которого подключен к выходу микроопераций блока микропрограммного управления, выход формирования пускового сигнала блока формирования адреса подключен к третьему входу элемента И.

//

у//

Изобретение относится к области вычислительной техники, в частности, может быть использовано при исследовании параметров сетевых графов и является усовершенствованием устройства для определения максимальных путей в графах по авт. св. № 862145. Целью изобретения является расширение области применения устройства за счет обеспечения возможности исследования графов на наличие циклов и петель в них и повьппение точности определения максимальных путей. Поставленная цель достигается тем, что в устройство по авт. св. № 862145 дополнитепьно вводятся блок формирования топологии исследуемого графа, блок сравнения, блок формирования адреса, коммутатор, блок вьщеления циклов и блок микропрограммного управления. Предварительное исследование графов на наличие петель и циклов а позволяет избежать вычисления макси(Л мальных путей в циклических графах, что повышает достоверность работы устройства, а следовательно, повышает точность определения максимальных путей в графах. 14 ил. ю 00 со 00

/

У/у

.

/J

ЙДР

А.

////

У/.

/f

/

yV.

///лЯУ/7/

JL

©

@1

. IPuf.5

Фиг.7

Фие. 3