Устройство для определения максимальных путей в графах

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 128038 С 06 Р 15/2 Я У 862145. Црасширениества за счеисследовани наличие цикл ние точности графовх и пов и петель в ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ОПИСАНИЕ ИЗОБР АВТОРСКОМУ СВИ 4 ЕТЕЛЬСТВУ(71) Ленинградский институт авиационного приборостроения(56) Авторское свидетельство СССРР 862145, кл. С 06 Р 15/20, 1980.(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯИАКСИ 11 АЛЬНЫХ ПУТЕЙ В ГРАФАХ(57) Изобретение относится к области вычислительной техники, в частности, может быть использовано приисследовании параметров сетевыхграфов и является усовершенствованием устройства для определения максимальных путей в графах по авт. св. лью изобретения является бласти применения устрой обеспечения возможности определения максимальных путеи. Поставленная цель достигается тем, чтов устройство по авт. св. У 862145дополнительно вводятся блок формирования топологии исследуемого графа,блок сравнения, блок формирования адреса, коммутатор, блок выделения циклов и блок микропрограммного управления. Предварительное исследованиеграфов на наличие петель и цикловпозволяет избежать вычисления максимальных путей в циклических графах,что повышает достоверность работыустройства, а следовательно, повышает точность определения максимальных путей в графах. 14 ил.17 12803 У , У , У , У (оператор 25) . Дей 19 ф 20 30ствие оператора 25 аналогично действию оператора 14 (пункт 14) (значение триггера (ячейки) 37 блока 14 согласно адресу) посылается в блок сравнения 6.26. Блок 12 переходит в следующее Блок 12 переходит в состояние,Сд,при этом последовательности единичных сигналов не вырабатываются.Блок 12 переходит в следующее состояние алфавита состояний памяти взависимости от сигналов входного алфавита.Если признак Р (вырабатывается2в блоке 15 и говорит о том, что значение счетчика столбцов 64 блока 15равно и) равен нулю, переходят кпункту 23, если нет - к пункту 31.31; Если признак Р 9 вырабатывается в блоке 15 (триггер 72) и характеризуется как признак начала работы, т,е. просмотра новой вершины 20 на наличие входящих дуг) равен нулю,переходят к пункту 32, если нетк пункту 33.32. Блок 12 переходит в состояние С , и одновременно вырабатывается едйничный сигнал У , поступающийв блок 15 на триггер 72 и устанавливающий триггер 77 в единичное состояние Р =1, переходят к пункту 34.33, Если признак Р (вырабатыва 9ется в блоке 17 в третьем узле 41памяти и информирует о том, что зна-чение счетчика адреса 62 равно нулю)равен нулю, переходят к пункту 20,в другом случае - к пункту 34.35 34. Если признак Рь (вырабатывается во втором узле 40 памяти блока17 и информирует о том, что зйачениесчетчика адреса 55 равно нулю) равеннулю, переходят к пункту 35, если40 нет - к пункту 36. 35. Блок 12 переходит в состояниеС , и одновременно вырабатываетсяпоследовательность единичных сигна лов Уо ф ЗтСигнал У поступает на второй узел40 памяти блока 17, стробируя выходрегистра 54.Сигнал У поступает на третий узел41 памяти блока 17, стробируя входрегистра 61.При одновременной выработке сигналов Уз, УМ в регистр 61 .блока 171 третий узел памяти записывается значение регистра 54 (второй узел 40памяти).37. Блок 12 переход.т в состояниеСалфавита состоянии, и одновременно вырабатывается последовательсостояние.Если признак Рь, (вырабатываетсяв блоке 16 сравнения и является критерием срабатьдвания блока сравненияна предмет равенства) равен единице(значение триггера (ячейки) 37 блока14 равно единице), переходят к пункту 27, в другом случае - к пунту 30,27 Блок 12 переходит в состояние С , и одновременно вырабатываетНся единичный сигнал У (оператор 27)который поступает в блок 17 на второй узел 40 памяти и увеличивает наединицу значение счетчика адреса 55блока.28. Блок 12 переходит в состояниеС , и одновременно вырабатываетсяЯ Упоследовательность единичных сигналов Уд 1 9УУ.Сигнал У поступает на второйузел 40 памяти блока 17, стробируявыход счетчика 55 адреса,Сигнал Упоступает на второйузел 40 памяти блока 17, стробируявыход дешифратора 53 адреса.Сигнал У поступает на второйззузел 40 памяти, разрешая запись инФормации в регистры 52.Сигнал У поступает в блок 15,стробируя выход счетчика 64 столбцов,Таким образом, при одновременнойвыработке такой последовательностив регистр из группы регистров 52второгс узла 40 памяти блока 17 сог.ласно адресу СТ 55 (значение счетчика 55 адреса служит адресом выбираемого регистра) записывается значение счетчика столбцов 64 блока 15. 29. Блок 12 переходит в состояние С , и одновременно вырабатывается Я 1последовательность единичных сигналов .У 41УьСигнал У, поступает на второй узел 40 памяти блока 17, стробируя выход счетчика 55 адреса,Сигнал У поступает на второйЗьузел 40 памяти блока 17, стробируя вход регистра 54.При одновременной выработке сигналов значение счетчика 55 адреса 8018второго узла 40 памяти блока 17 записывается в регистр 54 блока,1280380 19 ность единичных сигналов У, У(оператор 37),Сигнал У поступает в блок 17на третий узел 41 памяти, стробируявход счетчика 62 адреса,Сигнал У поступает в блок 17на третий узел 41 памяти, стробируявыход регистра 61.39. Блок 12 переходит в состояниеС , и одновременно вырабатываетсяпоследовательность единичных сигналов У, У, У, У, У, У (оператор 39).Сигнал У поступает в блок 17на третий узел 41 памяти 41, стробируя выход счетчика 62 адреса. Сигнал У стробирует выход дешифратора адреса третьего узла 41 памяти.Сигнал У разрешает запись информации в регистры 58 блока 17 (третий узел 41 памяти)Сигнал У 4 поступает в блок 17на второй узел 40 памяти, стробируя выход счетчика 55 адреса.Сигнал У поступает в блок 17 на второй узел 40 памяти, стробируя выход дешифратора 53 адреса. Сигнал Упоступает в блок 17 на второй узел памяти 40 и разрешает чтение информации иэ регистров 52.При одновременной выработке этой последовательности в один из регистров 58 третьего узла 41 памяти блока 17 согласно адресу счетчика 61 адреса (значение счетчика 61 служит адресом выбираемого регистра) записывается значение одного оегистра 52 согласно адресу счетчика адреса 55 (значение счетчика 55 служит адресом выбираемого регистра).40. Блок 12 переходит в состояние С алфавита состояний, и одно 27времейно вырабатывается последовательность единичных сигналов Угф у,цСигнал У поступает на второй узел 40 памяти блока 7, уменьшая значение счетчика адреса 55 на единицу.Сигнал,У поступает на третий узел памяти 41 блока 17 и уменьшает значение счетчика адреса 62 на единицу.41. Блок 12 переходит в следующее состояние в зависимости от сигнала входного Йтфавита 20Если признак Р (вырабатываетсяво втором узле памяти 40 блока 17 иинформирует о том, что значение счетчика адреса 55 равно нулю) равеннулю, переходят к пункту 39, еслинет - к пункту 42,42. Управляющий автомат переходитв состояние С , и одновременно вырабатывается последовательность единич 10 ных сигналов У, У 4 д, У,Сигнал Упоступает в блок 17на второй узел 40 памяти, стробируявыход регистра 72,Сигнал У 4 д поступает в блок 1715 на второй узел 40 памяти, стробируявход счетчика 55 адреса,Сигнал Упоступает в блок 17на третий узел 41 памяти, стробируявыход регистра 61.Сигнал У 7 поступает в блок 17 натретий узел 41 памяти, стробируя входсчетчика 62 адреса,При одновременной выработке такой25последовательности сигналов значениерегистра 54 записывается в счетчикадреса 55 второго узла 40 памятиблока 17, а значение регистра 61 записывается в счетчик 62 адреса третьего узла 41 памяти блока 1743. Блок 12 переходит в состояние С , и одновременно вырабатывается последовательность единичныхсигналов У 4 У У У (оператор43) .35Сигнал У поступает в блок 17 навторой узел 40 памяти, стробируя выход счетчика 55 адреса.Сигнал поступает в блок 17 на вто рой узел 40 памяти, стробируя выходдешифратора адреса 53.Сигнал У поступает в блок 17на второй узел 40 памяти, разрешая чтение информации из регистров 52.45 Сигнал У поступает в блок 15,стробируя вход буферного регистра 66. Таким образом, при одновременной выработке этой последовательности сигналов в буферный регистр 66 блока 15 записывается значение одного из регистров 52 второго узла 40 памяти блока 17 согласно адресу выбираемого регистра, в качестве которого принимается значение счетчика 55 адреса.44. Блок 12 переходит в состояние С , и одновременно вырабатывается280380 22ов вить выходящие связи (дуги) из 1-йвершины,т. Если признак Р (пункт 19)равеннулю, значит рассматривается следующая вершина на наличие входящих дуг(начала нового этапа обработки информации), В этом случае массив М 4еще не. сформирован (техническая реализация массива М 4 - третий, узел10 4 памяти блока 17) и в качестве номера (ш) -й вершины принимаетсязначение счетчика 65 блока 15. Еслимассив М 4 сформирован (признак Р =1),значит необходимо в качестве номера15 1-й вершины просмотреть все значенияа- массива М 4. Для этого в пункте 20очередное значение элемента массиваМ 4 (один из регистров 58) согласнот адресу счетчика адреса 49 (КЗ) запи 20 сывается в буферный регистр бб (ш)блока 15. Затем начинается просмотрстроки матрицы смежности (техническая реализация - блок 14 формирования топологии исследуемого графа) .В пункте 21 происходит уменьшениее значения счетчика адреса 62 (КЗ) наединицу.Необходимо просмотреть строки сномером ш 1 в качестве значения ш30 служит значение регистра 65 блока15 или значение элемента массива М 4(третий узел 41 памяти блока 17),21 последовательность единичных сигнал у42 22 ф 21Сигнал У уменьшает значение сче чика 55 адреса во втором узле 40 па мяти блока 17 на единицу.Сигнал У поступает в блок 17 на первый узел 39 памяти, и стробируя вход счетчика 48 адреса.Сигнал У - поступает в блок 17 на первый узел 39 памяти, и стробируя выход регистра 49.Таким образом, при одновременной выработке сигналов значение счетчика 55 адреса второго узла 40 памяти ,блока 17 уменьшается на единицу и в счетчик 48 адреса записывается зн чение регистра 49 в блоке 17; переходят к пункту 12.36. Управляющий автомат переходив следующее состояние.Если признак Р (вырабатываетсяв блоке 15 и информирует о том, чтозначение счетчика 65 равно и) равеннулю, переходят к пункту 2, еслинет - к пункту 38.38. Блок 12 переходит в состояни С и одновременно вырабатываетсяединичный сигнал У , поступающий в7 фблок 15 и устанавлйвающий триггеруправления 73 в единичное состояниеПроисходит переход блока 12 в следующее состояние.и работа блока . управления заканчивается (процесс выявления циклов окончен). На этом завершается первый этап работы устройства. Если в графе нет циклов, то в результате первого этапа работы устройства триггер управления устанавливается в единичное состояние и единичный потенциал на выходе триг гера управления 73 служит пусковым сигналом на входе элемента И 4. Начинается второй этап работы устройства, на котором, в случае отсутствия циклов происходит вычислениемаксимальных путей с помощьюизвестного устройства. Если циклы существуют, и триггер 73управления блока 15 не устанавли" вается в единичное состояние и второй этап работы отсутствует, т.е. в циклических графах максимальные пути не вычисляются. В пунктах 19-30 происходит следующее.Если до пункта 19 (пункт 5) цик лов не обнаружено, необходимо выяДля этого счетчика 64 столбцовблока 15 обнуляется в пункте 22, ав пункте 23 увеличивается значениесчетчика 64 столбцов блока 15.В пунктах 24-26 происходит выборка значения триггера (ячейки) 40 37; блока 14 и в блоке 16 сравнения происходит сравнивание значенияячейки 37;1 с единичным значениемтриггера 78 сравнения блока 16.Если значение триггера (ячейки) 45 37; блока 14 равно единице (обнаружили очередную дугу), выходящую извершины), происходит заполнениеочередного элемента массива МЗ. Дляэтого в пункте 27 устанавливаетсяновое значение счетчика 55 адреса(К 2), согласно этому значению адреса55 в ьдин регистр 52 записываетсязначение счетчика 64 столбцов блока15 (пункт 28), а в пункте 29 значениесчетчика 55 адреса второго узла 40памяти блока 17 записывается в регистр 54 блока. Если просмотрена всястрока (признак Р) равен единицеоператор 30), в регистре 54 второгоблока памяти записано количество связей, выходящих из 1-й вершины (число элементов массива МЗ).Операция просмотра строк продолжается в зависимости от числа элементов массива М 4 (элементы массива М 4 служат нумерацией строк) или просматривается одна строка с номером, равным значению КС блока 15,Зоесли признак Р равен нулю. Если все элементы массива просмотрены (признак Р =О), т,е. значение КЗ равно нулю (счетчик 62 адреса), значит сформирован новый массив МЗ (второй узел 40 памяти блока 17). Если вновь сформированный массив МЗ нулевой, выявленные выходящие из д-й вершины связи приходят в конечную, и, следовательно, если не все вершины в графе исследованы на наличие входящих дуг (признак Р =0 (пункт 36), переходят к пункту 2 и процесс повторяется.Если массив МЗ ненулевой, его значения переписываются в массив М 4 (второй узел 40 памяти блока 7) в пунктах 35-41 и после необходимых вспомогательных операций 42-44 переходят к пункту 12.формула изобретенияустройство для определения максимальных путей в графах по авт.св.1 д 862145, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения устройства путем обеспечения возможности исследования графов на наличие циклов и петель в них и повышения точности определения максимальных путей, в него введены блок сравнения, блок формирования адреса, коммутатор, блок выделения циклов и блок микропрограммного управления, блок формирования топологии исследуемого графа, содержащий группу элементов И и матрицу триггеров, блок вьделения циклов содержит три узла памяти и две группы элементов ИЛИ, установочные входы триггеров являются установочными входами устройства, вход каждого -го трИггера матрицы подключен к первому входу 1.-го элемента И группы блока формирования топологии исследуемого графа (где 1.=1, 2, , и и), выходы элементов И группы блока формирования топологии исследуемого графа подключены к соответствующим информа 5 10 15 20 25 3040 4550 55 управления, выход формирования пускового сигнала блока формирования адреса подключен к третьему входу элемента И. ционным входам первой группы коммутатора, второй вход каждого 1-го эле мента И группы блока формирования топологии исследуемого графа подключен к 1-му выходу группы выходов блока микропрограммного управления,информационные входы первого и второго узлов памяти объединены и подключены к выходу массива номеров вершин блока формирования адреса, первый и второй информационные выходы второго узла памяти подключены соответственно к первому и второму информационным входам третьего узла памяти, входы разрешения записи всех узлов памяти объединены и подключены к выходу микроопераций блока микропрограммного управления, каждый 1-й выход группы выходов первого узла памяти подключен к первому входу 1-го элемента ИЛИ первой группы блока вьделения цикла, каждый -й выход второй группы информационных выходов второго узла памяти подключен к первому входу -го элемента И второй группы блока выделения циклов, второй вход которого подключен к 1-му выходу группы выходов третьего узла памяти, выход каждого 1-го элемента ИЛИ второй группы блока вьделе. ния циклов подключен к второму входу д-го элемента ИЛИ первой группы блока выделения циклов, выход которого подключен к одноименному входу группыинформационных входов блока формирования адреса, выход формирования адреса которого подключен к второму информационному входу коммутатора, управляющий выход которого подключен к выходу микроопераций блока микропрограммного управления, выход коммутатора подключен к первому информационному входу блока сравнения, второй информационный вход которого подключен к выходу микрооперацийблока микропрограммного управления, выход блока сравнения подключен к входу логического условия блока микропрограммного управления, вход ко-манды которого подключен к выходу формирования признака блока формирования адреса, вход микрокоманд которого подключен к выходу микро- операций блока микропрограммного1 128038Изобретение относится к областивычислительной техники и может быть использовано при исследовании параметров сетевых графиков.Цель изобретения - расширение 5 области применения устройства путем обеспечения возможности исследования графов на наличие циклов и петель в них и повышение точности определения максимальных путей, ЮНа фиг. 1 приведена функциональная схема устройства для определения максимальных путей в графах; на фиг. 2 - алгоритм работы блока микропрограммного управления; на Фиг.3- структурная схема блока микропрограммного управления; на Фиг. 4 - функциональная схема узла памяти блока микропрограммного управления; на фиг. 5 - функциональная схема узла формирования сигналов перехода блока микропрограммного управления; на фиг. 6 - функциональная схема узла формирования сигналов управления блока микропрограммного управления; на фиг. 7 - функциональная схема бло- ка формирования топологии исследуемого графа; на фиг. 8 - функциональ-ная схема блока вьщеления циклов; на фиг. 9 - функциональная схема первого узла памяти блока вьщеления циклов; на Фиг. 10 - функциональная схема второго узла памяти блока выделения циклов; на фиг. 11 - функциональная схема третьего узла памяти; 35 на фиг. 12 - функциональная схема блока формирования адреса; на фиг.13- Функциональная схема коммутатора; на Фиг. 14 - функциональная схема блока сравнения,Устройство для определения максимальных путей в графах содержит матричную модель 1 сети, группу элемен-тов ИЛИ-НЕ 2, генератор 3 тактовых импульсов, элемент И 4, группу элементов И 5, группу счетчиков 6 весов дуг, группу триггеров 7 управления, группу элементов И 8, группу регистрирующих счетчиков 9, элемент ИЛИ 50 1 О, триггеры 11 матрич.юй модели сети, блок 12 микропрограммного управления, коммутатор 13, блок 14 формирования топологии исследуемого графа, блок 15 формирования адреса, блок 55 16 сравнения и блок 17 вьщеления циклов.Блок 12 микропрограммного управления образуют узел 18 памяти, узел 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 вьщею 1 ения циклов содержитпервый 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 строк, третьей группе элементов ИЛИ, 71, триггере 72 признака и триггере 73 управления.Коммутатор 13 состс .т из и групп по и элементов И 74 в каждой и группы выходных элементов И 75.ИИПИ Госуд по делам 35, МоскванииРауш оиитета ССС открытий кая наб., дБлок 16 сравнения содержит элемент ИЛИ 76, группу элементов И 77и триггер 78 сравнения,Матричная модель сети 1 содержит1, 1 триггеров 11 по числу строк и 5столбцов (где 1, 3 = 1,и; п - числовершин моделируемого графа), выходыкоторых в строках подключены к входамсоответствующих элементов ИЛИ-НЕ 2,выходы которых подключены к управляющим входам соответствующих элЕментовИ 5 второй группы, а входы 1, 3 триггеров 11 в столбцах подключены к выходам соответствующих счетчиков 6весов дуг. Выходы элементов И 5 15второй группы подключены к входамеоответствующих счетчиков 6 весовдуг. Количество элементов И 8 первойгруппы, элементов И 5 второй группы,регистрирующих счетчиков 9, счетчиков 6 весов дуг и триггеров 7 управления определяется количеством столбцов матричной модели сети 1. Выходблока 12 микропрограммного управлениясоединен с соответствующими входамикоммутатора 13, блока 14 формирова"ния топологии исследуемого графа,блока 15 формирования адреса, блока16 сравнения и блока 17 выделения циклов.ЗО Блок 12 микропрограммного управления (фиг. 3) служит для выработки ,последовательности управляющих единичных сигналов, распределенных во времени для управления работой с блоков устройства. Программа работы бло ка 12 приведена на фиг. 2,Узел 18 памяти 1 фиг. 41 служит для задания алфавита состояний па О мяти С -СУзел 19 формирования сигналов перехода (фиг. 5) предназначен для выработки единичных сигналов, необходимых для перехода блока управле ния в одно из состояний алфавита состояний памяти С -С, .Узел 20 формирования сигналов управления (фиг. 6) применяется для выработки последовательности 50 управления единичных сигналов.Коммутатор 13 (фиг. 13) обеспечивает доступ к выходу каждого триггера (ячейки) 37; блока 14 формирования тополОГии исследуемоГО Графа 55Коммутатор 15 состоит иэ и групп по и элементов И 74 в каждой (где и - число вершин графа), каждый элемент И 74 представляет собой трехвходовый элемент И и элементы И 7575 по числу выходов элементовИ 74; . Для обращения к каждомутриггеру (ячейке) 37 блока 14необходимо задать адрес строки истолбца, на пересечении которых на"ходится данная ячейка. Поэтому каждый элемент И 74; содержит два адресных и один информационный входы..Элементы И 75 служат для стробирования выходов элементов И 74. Стробирование осуществляется единичнымсигналом У с управляющего входакоммутатора,Блок 14 формирования топологииисследуемого графа (фиг. 7) записывает и хранит информации о топологииисследуемого графа. Блок состоит изматрицы триггеров (ячеек) 37 и группы двухвходовых элементов И 38. Триг.геры 37 являются формирователем дуги устанавливаются в единичное состоя.ние, если есть дуга из 1-й вершиныв 3-ю вершину, или в нулевое состояние, если вершины исследуемого графадугой не связаны. Элементы И 38 -38служат для стробирования выходовтриггеров 37. Стробирование осуществляется единичным сигналом УБлок 15 формирования адреса(фиг. 12) обеспечивает выработку значений адреса строк ,-. и адресастолбцов я 1-д с целью осуществления доступа к выходу каждого триггера (ячейки) 37 блока 14 через коммутатор 13,Блок сравнения 16 (фиг. 14) осуществляет сравнение значений триггеров (ячеек) 37 блока 14 со значением,определенным триггером 78 сравнения,который устанавливается в единичноесостояние единичным сигналом,Блок 17 выделения циклов служитдля хранения значений счетчика строк63 и счетчика столбцов 64 блока формирования адреса 15,Первый узел 39 памяти предназначен для хранения значений счетчика строк 63 блока 15 регистры 46 - 46 дешифратор 44 адреса и для осуществления доступа к каждому регистру 46-46 п. На один вход элементов И 45 подается значение с выхода дешифратора адреса 44 (выборка регистра по адресу), а на другой - единичный сигнал У 7 блока 12, разрешающий запись информации в один из оегистров 46 -46 . Выходы элементов И 45 подключены к входам, стробирующим запись информации в соответствующий регистр 46, -64 адрескаторого выбран). На один вход элементов И 47, -47 подается значениес выхода дешифратора 44 адреса (выборка регистра по адресу), а на другой - единичный сигнал У блока 12,разрешающий чтение информации иэрегистров 46, в 46 . Выходы элементовИ 47 -47 подключены к входам, стробирующим чтение информации иэ соответствующего регистра 46 -46 (адрес которого выбран). Счетчик 48 ад-реса служит для выработки позиционного кода адреса регистра из группырегистров 46-46 , регистр 49 - дляхранения текущих значений счетчика48 адреса,Второй узел 40 памяти обеспечивает хранение значений счетчика 64столбцов блока 15 формирования адреса.Третий узел 41 памяти служит длядублирования второго узла 40 памяти.Назначение элементов узлов 40 и 41памяти аналогично назначению элементов узла 39 памяти. 1Принцип работы предлагаемого устройства заключается в следующем,Путь в графе можно определить как последовательность вершин от данной вершины до конечной, связанных дугами. Если какой-либо путь в графе содержит несколько одинаковых вершин, значит в графе существует цикл.Предлагаемое устройство при отсутствии циклов в исследуемых графах работает в два этапа, На первом эта-. пе происходит исследование графа на" наличие циклов и в случае их отсутствия начинается второй этап, в результате которого вырабатывается единичный потенциал, разрешающий работу устройства.Граф описывается матрицей смежности А отображающей его топологию. Матрица имеет размерность пхп (где и - число вершин в граре). Если существует дуга из д-й вершины в 1-ю вершину графа, то на пересечении строки с номером(х-я вершина) и столбца с номером 1 (1-я вершина гра фа) записывается единица. Если дуга отсутствует, записывается нуль.Если в строке с номером 1 существует несколько единиц (выходящиецуги), значит иэ -й вершины выходит несколько путей. Если в столбце с номером 1 суще. ствует несколько единиц (входящие дуги) значит в 1-ю вершину входит несколько путей в графе.Чтобы иметь информациЬ о связях д-й вершины, необходимо в результате просмотра 1-й строки выявить выходящие дуги, а в результате просмотра столбца с номером 1= выявить входящие дуги. Если в 1.-ю вершину нет входящихдуг (столбец с номером- нулевой), значит такая вершина в путях графа не может быть звеном цикла.Поиск циклов в графах производится следующим способом.а). Последовательно, начиная с 10 15 го первой вершины в графе путем просмотло единиц в 1-м столбце матрицы смежности А) . Максимальное значение ш равно(числу вершин графа). Техническойреализацией одномерного массива Бявляется первый узел 39 памяти блока 17 выделения цикловб), Если входящие связи отсутст- ,10 вуют, рассматривают следующую вершину на наличие входящих дуг переходят к пункту (а) и рассматриваютследующий столбец , если нет - переходят к пункту (в).д 5 в), Проверяют нет ли непосредственной связи из 1-й вершины (=1)в одиу из вершин, являющихся элементами массива Б. Если такая связьсуществует, то элемент матрицы смеж О ности (А; ,1 1 равен единице (А 1 ак 1 )=1 где К 1 1,шг). Если выполняется хотя бы одноравенство пункта (в), значит существует цикл.д). Если ни одно равенство пункта (в) не выйолняется, необходимов результате просмотра строки с номером 1 Ш 1 выявить выходящие нэ 1.-йвершины дуги и зафиксировать номера ра столбца матрицы смежности А с номером 1 ("1 и, где п - число вершин графа ), определяют входящие в 1-ю 25вершину графа связи. Номера этих вершин заносятся в одномерный массив Б. В качестве элементов Б (К 1) массива Б выступают значения номеров строк, на пересечении с которыми в столбце с номером 1 записана едини- ЗО ца (Б(К 1)=., где К 1=1,тп; тпр - чис1280 40 вершин в одновременном массиве МЗ,Элементами массива МЗ являются значения номеров 1 столбцов, в которыхна пересечении с з-й строкой записаны единицы (МЗ(К 2)=1, К 2=1,2), где ,51 - число дуг, выходящих из 1.-йвершины. Максимальное число 1 равнопп (и - число вершин в графе). Значение элементов массива МЗ (К 2) необходимо переписать в аналогичныйодномерный массив М 4(КЗ)=МЗ(К 2),где КЗ К 2=1, 2Технической реализацией массивовМЗ и М 4 служат соответственно второй40 и третий 41 узлы памяти блока 17выделения циклов.е). Для .каждого элемента массиваМЗ необходимо проверить нет ли непосредственной связи из вершин с номерами МЗ (К 2) где К 2=1, 0 в однуиз вершин Я(К 1), К 1=1,пАМЗ(К 2), Б (К 1) = 1.Если выполняется хотя бы одно равенство, значит существует цикл.ж). Если ни одно равенство пункта (е) не выполняется необходимо врезультате просмотра строк с номерами М 4 (КЗ), где К 3=1,1 , выявитьвыходящие иэ этих вершин связи и 30зафиксировать номера вершин в одномерном массиве МЗ, а затем после выявления всех исходящих дуг иэ вершин с номерами, равными значениямэлементов массива М 4, переписатьзначения элементов массива МЗ в массив М 4. Затем переходят к пункту(е), если в пункте (ж) не получаютнулевой массив МЗ (т,е. находятсяв конечной вершине, иэ которой несуществует исходящих дуг).Если массив МЗ ненУлевой, просмотрены не все вершины графа на предмет наличия входящих дуг и не обнаружено циклов в пунктах (в) и (е), 45переходят к пункту (а), в другомслучае вырабатывается единичный сигнал о том, что в графе не существуетциклов, разрешающий работу устройства. В этом случае начинается второй 50этап работы и вычисление максимальныхпутей в графах.Блок 12 микропрограммного управления выполнен в виде конечного автомата 1 ура по модели Уилкса-Стринджера,структура которого определяетсяструктурой алгоритма работы блока 12,Блок 12 характеризуется алфавитомвходных сигналов Р. - Р (признаков),380 8алфавитом выходных сигналов У -У"далфавитом состояний памяти С -Сэ 1,функцией выходов Л и функцией переходовс (г.) =Х (с (с),р (г.) ) - функция переходов;у(С)= )1(с(Г - функция выходов.Для задания алфавита состояний памяти с -с входят отметки на входахО 3(всех с 1-й по 44-ю операторных и условных вершин алгоритма работы блока 12, Символы У;, записанные в операторные вершины, являются выходными "игналами блока 12. Работа блока 12 стробируется генератором тактовых импульсов 31. Тактовые импульсы с генератора тактовых импульсов 31 поступают вместе с сигналом алфавита входных сигналов Р -РЭ если он существует. Пока действует синхроимпульс, состояние триггеров 25 основной памяти не изменяется, хотя состояние триггеров 27 вспомогательной памяти может изменяться, Состояние триггеров 25 основной памяти изменяется, когда синхроимпульс прекращается. Этим обеспечивается устойчивость работы блока 12, так как пока действует синхроимпульс, триггеры основной памяти 25 не переходят в новое состояние. Алфавит состояний памяти с -с кодируется двоичным кодом, снимаемым с выходов триггеров 25 основной памяти. Входы триггеров 27 вспомогательной памяти связаны с выходами шифратора 35, на выходах которого формируется двоичный код, устанавливающий триггеры 27 вспомогательной памяти в новое состояние алфавита состояний памяти с -с . Импульсы генератора 31 тако 31товых импульсов поступают на триггер 29 управления через элемент И 30, на выходы которого подается информация о том, что блок 12 находится в начальном состоянии с (устанавливаоется перед началом работы подачей сигнала на вход "Уст,0"), Для инициации работы блока управления необходима подача единичного пускового импульса на вход "Пуск" узла 18 памяти блока 12. Дешифратор 28 алфавита состояний памяти преобразует позиционный код на выходе триггеров 25 основной памяти в унитарный код.Выходные управляющие сигналы У; алфавита выходных сигналов вырабаты-. ваются в зависимости от состояния1280380 9алфавита состояний памяти с -с , вкоторое перешел блок 12 управления.Если один и тот же сигнал вырабатывается в различных состояниях алфавита состояний памяти с -с, блока 12,то соответствующие выходы дешифрато"ра 28 алфавита состояний памяти должны объединяться схемой ИЛИ.Например, согласно алгоритму работы блока 12 единичный сигнал У выра3батывается, когда блока 12 переходитв состояние сили с, алфавита состояний памяти. Поэтому соответствующие выходы дешифратора 28 алфавитасостояний памяти (с и с ) объедиз 17няют элементом ИЛИ 36.Блок 12 переходит в новое состояние в зависимости от состояния в пре.дыдущий момент времени и от сигналовалфавита входных сигналов Р -Р ) . 204 9Закон перехода блока 12 в новоесостояние алфавита состояний памятиопределяется алгоритмом работы блокауправления (фиг. 2). Например, дляперехоца в состояние С алфавитаЕ.состояний памяти необходимо находиться в состоянии С алфавита состояний памяти. Такой переход осуществляется из состояния С на очередном такте работы блока 12 микро- З 0программного управления при наличиисигнала алфавита входных сигналовР , Для выполнения тактового условия,необходимо объединить выход С дешифратора 28 алфавита состояний 35памяти и вход Р элементом И 32.Сигналы входного алфавита поступаютна первый и второй информационныевходы блока 12,40Выход элемент И 32 обозначен буквой Ь . Соединив выход элементаИ 32 с пятым входом шифратора 35,на выходе шифратора 35 получают позиционный код 00101 =51 45Блок 16 сравнения работает следующим образом.Предположим, что на выходе элемен"та ИЛИ 76 блока 16 сравнения имеетсяноль, т.е. значение триггера (ячей"ки) 37; блока 14 равно нулю, навыходе элемента И-НЕ 77 присутствуетзначение единипд; Если на выходетриггера 78 сравнения установленозначение единипы, на выходе элементаИ-НЕ 77 находится нулевое значение.На выходе элемента И-НЕ имеется значение равное единице, следовательно,на выходе элемента И-НЕ 72 появляется 10значение, равное нулю. Признак Р равен нулю, Предположим, что на выходе элемента ИЛИ 20 блока 16 сравнения имеется единичное значение, т.е. значение триггера (ячейки) 37 блока 14 равно единице. Если на выходе элемента И-НЕ 77 присутствует единичное значение, признак Ра равен единице.Работа предлагаемого устройства осуществляется в два этапа.Предварительно на вход Уст.О узла 18 памяти блока 12 микропрограммного управления подается единичный сигнал, устанавливающий триггеры27 вспомогательной памяти и триггеры 25 основной памяти в нулевой состояние, устанавливая блок 12 в исходное состояние алфавита состояний памяти С. Этот же,сигнал поступает в блок 15 формирования адреса и устанавливает триггер 73 управления в нулевое состояние, устанавливая на управляющем выходе блока 15 нулевой потенциал. На первом этапе работы устройства в блок 14 и в матричную модель сети 1 заносится информация о топологии исследуемого графа, отображае мая матрицей смежности А. В счетчикв весов дуг 6 занесены числа импульсов, дополняющие веса вершин до полной емкости счетчиков информации о том, что блок 12 находится в начальном состоянии единичный потенциал на выходе С, дешифратора 28 алфавита состояний памяти) поступает на вход С узла 18 памяти блока 12. С появлением единичного пускового сигнала на входе "Пуск" узла 18 памяти блока 12 начинается работа устройства. Работа блока 12 синхрониэируется генератором 31 тактовых импульсон, тактовые импульсы которого определяются максимально возможным временем срабатывания схемных элементов устройства и через элемент И 30 при наличии единичных потенциалов на входах "Пуск" и С поступают на триггер 29 управления, управляя работой блока микропрограммного управления 12. Работу устроиства проследим по алгоритму работы устройства.1. На первом такте генератора тактовых импульсов 31 блок 12 переходит в состояние С 1 алфавита состояний памяти, и одновременно вырабатывает" ся последовательность единичных сиг11 1280380налов У , У , У, (оператор 1). Сигнал У поступает в блок 15 и устанав8ливает счетчик 65 в нулевое состоядние.Сигнал У поступает в блок 16 .5 тсравнения и устанавливает триггер8 сравнения в единичное состояние.стСигнал У поступает в блок 17,и обнуляет регистры 46 узла 39 памя- вьти, регистры 58 узла 40 памяти, ре- О гргистры 50 -50 узла 41 памяти.па2. Блок 12 микропрограммного уп- ниравления переходит в состояние Слаалфавита состояний памяти, и одновременно вырабатывается последовательность единичных сигналов У 1,пе. У, У, У У,У (оператор 2),.меСигнал У поступает в блок 15нана счетчик 65 и увеличивает его значение на единицу (СТ =СТ +1).эо зрнаСигнал У поступает в блок 15 на вытриггер 72 признака, устанавливаяпризнак Р в нулевое состояние.наСигналы У , У , Уо поступают в вхблок 17 и обнуляют соответственносчетчик 62 адреса узла 41 памятин(СТ -О).от3. Блок 12 переходит в состояниесиС, и одновременно вырабатываетсяпоследовательность единичных сигналов У У У (оператор 3).Сигнал Уд поступает в блок 15пуна счетчик 63 строк, увеличивая егозначение на единицу (СТ э =СТ +1)рэ ЕдиСигнал У поступает в блок 15, 40мостробируя выход счетчика 65. 12. Сигнал У йоступает в блок 15, стробируя вход счетчика 64 столбцов.При одновременной выработке сигналов У, У, счетчику 64 столбцов присваивается значение счетчика 65 блока 15 (СТ =-СТ р ).4. На следующем такте блок 12 переходит в состояние С алфавита состояний памяти, и одновременно вырабатывается последовательность единичууъуу У (оператор 4)Сигнал У поступает в блок 15, стробируя выход счетчика 63 строк.Сигнал У поступает в блок 15, стробируя выход счетчика 64 столбцов. Сигналь У, У поступают в блок5, стробируя соответственно выходыешифраторов 70 и 69.Сигнал У поступает на коммута 3ор 3, стробируя его выход.Сигнал У поступает в блок 14,робируя выходы триггеров 37.Таким образом, при одновременной1 работке сигналов в регистре иэуппы регистров 46 первого узла 39мяти блока 17 записывается значее счетчика 63 строк блока 15 согсно значению адреса первого узлапамяти (счетчик 48 адреса).8 На следующем такте блок 12реходит в состояние С, и одновренно вырабатываются едйничные сиглы (оператор 8),Сигнал У поступает в блок 17первый узел 39 памяти, стробируяход счетчика 42 адреса.Сигнал У, поступает в блок 7первый узел памяти 39, стробируяод регистра 49.При одновременной выработке сигалов в регистр 49 блока 17 первогола 39 памяти записывается значениеетчика 48 адреса (КС, =СТ ).9. На следующем также блок 12реходит в следующее состояние алвита состояний памяти в зависимостизначения сигнала алфавита входныхгналов.Если признак Р, вырабатываемыйблоке 15 (значение счетчика строкравно п), равен нулю переходят кикту 3, если нет - к пункту О.1 О. Блок 12 (оператор 10) перехот в следующее состояние в эависисти от сигнала алфавита входныхсигналов,Если признак Р 7, вырабатываемыйв блоке 17 (значение счетчика 4845 адреса Равно нулю), равен нулю, переходят к пункту 2, в другом случаек пункту 11.В пунктах 2-О происходит просмотрстолбца матрицы смежности А (техни 50 ческая реализация матрицы смежности -блок 14) с номером, определяемымсчетчиком 65 блока 15., и выявлениесвязей, входящих в вершину с номером,определяемым счетчиком 65. Номера55 этих вершин заносятся в одномерныймассив Я (техническая реализация массива 8 - первый узел 39 памяти блока17). Для обеспечения возможности обращения к каждому регистру 46 с цельюхранения номеров вершин первого узла 39 памяти, н него введен счетчик 48 адреса, дешифратор 74 адреса и регистр 49 для оперативного хранения значений счетчика 48 адреса.Счетчик 48 адреса является технической реализацией переменной К 1.Когда весь столбец просмотрен Р =1 (значение счетчика строк 63 бло ка 15 равно и), н регистрах 40-40 Ю первого узла 39 памяти блока 17 находится информация о всех снязях, входящих в вершину с номером, определяемым счетчиком 65 блока 15, а в регистре 49 содержится значение, ха рактеризующее число элементов массива Б.11. Блок микропрограммного управления 12 переходит и следующее состояние У, У, и одновременно выраба тывается последовательность единичных сигналов У, У (оператор 11).Сигнал У поступает н блок 15, стробируя выход счетчика 65.Сигнал У поступает н блок 15, стробируя вход буферного регистра 66.При одновременной выработке этих сигналов в буферный регистр 66 записывается значение счетчика 65 блока 15. 3012. Блок 12 переходит .в состояние С алфавита состояний памяти, и одновременно вырабатывается последозательность единичных сигналов У, У (оператор 12). 35 Сигнал У поступает в блок 15,стробируя вход счетчика строк 63.Сигнал Упоступает в блок 15,44 1стробируя выход буферного регист- щра 66.При одновременной выработке сигналон значение буферного регистра66 записывается в счетчик строк 63блока формирования 15 адреса. 4513. На следующем такте блок микропрограммного управления 12 переходит в состояние С алфавита сосотаяний памяти и одновременно вырабатывается последовательность единичных сигналон У, У, У 19, У (оператор 13),Сигнал У поступает в блок 17выделения циклов на первый узел 39памяти, стробируя выход счетчика 48адр еса,Сигнал У поступает в блок 17на первый узел памяти 39, стробируявыход дешифратора 74 адреса. Сигнал У 7 поступает в блок 15 формированйя адреса, стробируя вход счетчика 64 столбцов. Сигнал У стро 79 бирует выход дешифратора 70 строк.Таким образом, при одновременной выработке сигналов значение регистра 46 первого узла 39 памяти блока 17 (согласно адресу, вырабатываемому счетчиком 48 адреса), посылается в блок 15 на счетчик 64 столбцов.14. Блок 12 переходит н состояние С алфавита состояний памяти и одновременно вырабатывается последовательность единичных сигналовф У 7 ф "Я9 ло 1,9 (оператор 14) .Действие оператора аналогично действию оператора пункта 4 (значение триггера (ячейки) 37 блока 14 Формирования топологии (согласно адресу) посылается н блок 16 сравнения).15. На следующем такте (оператор 15) блок 12 переходит в следующее состояние алфавита состояний памяти в зависимости от значения сигнала алфавита входных сигналов.Если признак Р (приэнак срабабтывания блока сравнения на равенство, т.е. значение ячейки 23 блокаО 14 равно единице) равен нулю, переходят к пункту 16, в противном случае - к пункту 30.16. Блок 12 переходит в состояние Салфавита состояний памяти (опегратор 16) и одновременно вырабатывается единичный сигнал (оператор 16), поступающий н блок 17 на счетчик 48 адреса первого узла 39 памяти и уменьшающий значение счетчика адреса 48 на единицу.17. На следующем также происходит переход по сложному условию. Если признак Р 7 (вырабатывается в первом узле 39 памяти блока 17 и характеризует нулевое состояние счетчика адреса 48 блока) равен нулю, переходят к пункту 14, если нет - к пункту 18.18, Если признак Р (вырабатывается во втором узле памяти 40 блока 17 и характеризует нулевое значение счетчика адреса 55 блока) равен нулю, переходят к пункту 43, н другом случае - к пункту 19.19, Если признак Рф (вырабатываетая в блоке 15 триггером 72; признак Р = 0 можно харак"риэовать как признак начала работы, т,епросмотра новой вершины на наличие входящихдуг) равен нулю, переходим к пункту 22, если нет - к пункту 20.В пунтках 11-18 происходи следующее действие.В буферный регистр 66 блока 15 .5 записывается либо значение счетчика 65, характеризующее номер очередной вершины, исследуемой на наличие входящих дуг, либо значение массива МЗ (техническая реализация массива МЗ второй узел 40 памяти блока 17) и проверяется по пункту 15, нет ли непосредственной связи из вершины с номером, характеризуемым значением буферного. регистра 66 с одной из вершин массива Я (первый узел 39 памяти) блока 17. Обозначим буферный регистр 66 условно буквой ш.Происходит следующая проверка.Значение элемента А,1 матрицы 20 смежности равно единице.По пункту 12 значение буферного регистра 66 записывается в счетчик строк 63 блока 15, по пункту 13 очередное значение элемента массива Б (содержание одного из регистров 46 первого узла 39 памяти блока 17) согласно значению счетчика 48 адреса блока 17 (К 1) записывается в счетчик 64 столбцов блока 15. 30По пункту 14 согласно значениям счетчиков строк 63 и столбцов 64 блока 15 выбирается значение триггера (ячейки) 32 блока 14, поступающее в блок 16 сравнения. 35Если такая связь существует (признак Р =), следовательно существует цикл (пункт 15), если нет, уменьшают значение счетчика 48 адреса на единицу и повторяют проверки до тех пор, 40 пока не просмотрят весь массив Б, Признаком этого является равенство нулю значения счетчика 48 адреса первого узла 39 памяти блока 17 (Р= 1). 45Проверка признака Р происходит в пункте 17. Если в буферный регистр 66 записываются элементы массива МЗ (второй узел 40 памяти блока 17), то критерием перебора всех элементов массива МЗ служит .равенство нулю значения счетчика 55 адреса второго узла 40 памяти. Это характеризует признак Р (пункт 18).20, Блок 2 переходит в состояние С алфавита состояний памяти, и одновременно вырабатывается последо 1 280380 16вательность единичных сигналов У 44 Ь 1У, У 44, У (оператор 20).Сигнал У 4 поступает в блок 17на третий узел 41 памяти; стробируявыход счетчика 62 адреса,Сигнал У поступает в блок 17 натретий узел 41 памяти, стробируя выход дешифратора 59 адреса.Сигнал У 4 поступает в блок 17на третий узел 41 памяти, разрешаячтение информации из регистров 58Сигнал У поступает в блок 15,стробируя вход буферного регистра 66.Таким образом, при одновременнойвыработке последовательности сигналов,значение регистра 58 третьего узла41 памяти блока 17 согласно адресу,вырабатываемому счетчиком адреса 62,посылается в буферный регистр 66 блока 15.21. На следующем такте блок управления переходит в состояние С 4алфавита состояний памяти. Одновременно вырабатывается сигнал У (оператор 21), поступающий в блок 17 натретий узел 41 памяти и уменьшающийзначение счетчика 49 адреса 49 наединицу.22, Блок 12 переходит в состоячиеС алфавита состояний памяти, и одновременно вырабатывается единичныйсигнал У (оператор 22), поступающийв блок 15 и обнуляющий счетчик 64столбцов.23, Блок 12 переходит в состояние С,. алфавита состояний памяти,и одновременно вырабатывается единичный сигнал У (оператор 23), поступающий в блок 15 и увеличивающийзначение счетчика столбцов 64 блока15 на единицу.24. Блок 12 переходит в состояниеС алфавита состояний памяти и од 47Эновременно вырабатывается последовательность единичных сигналов У , У(оператор 24).Сигнал У 3 поступает в блок 15,стробируя вход счетчика 63 строк.Сигнал У поступает в блок .15,50 стробируя выход буферного регистра66 блока.Таким образом значение буферногорегистра 66 блока 15 записываетсяв счетчик 63 строк.5525. Блок 12 переходит в состояниеС алфавита состояний памяти и од(6новременно вырабатывается последовательность единичных сигналов У, У,