Устройство для разбиения графов на слои

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 1 9) (11) 1)4 СО 6 Р 15 У ПИСАНИЕ ИЗОБРЕТЕНИЯ РОЙСТВО ДЛЯ РАЗБИЕН АФО ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРБ)ТИЙ К АВТОРСКОМУ СВИДЕТЕЛЬСТ(57) Изтельнойзованофов, анизациимультипсистемаширить бретение относится к вычисли- технике и может быть испольри исследовании сетевых граакже при решении задач оргавьчислительного процесса в оцессорных вычислительныхИзобретение позволяет расункциональные возможности1376099 за счет разбиения связного ориентированного графа без контуров на слои,Для этого в устройство, содержащеематрицу 1 моделей дуг 5, счетчик 15,дешифратор 16, группу элементов ИЛИ4, элементы И 11, 14, триггер 13,генератор 12 тактовых импульсов, причем каждая модель дуги содержит триггер 2 и элемент И 3, дополнительно 1Изобретение относится к вычислительной технике и может быть использовано при исследовании сетевых графов, а также при решении задач организации вычислительного процесса в 5мультипроцессорных вычислительныхсистемах,Цель изобретения - расширение функциональных возможностей за счет разбиения связного ориентированного 1 Ографа без контуров на слои,На фиг,1 представлена структурнаясхема устройства; на фиг.2 - граф,подлежащий разбиению на слои; нафиг.3 - то же, после распределениявершин по слоям,Устройство содержит матрицу 1Омоделей дуг, каждая из которых состоит из триггера 2 и элемента 3.Устройство содержит также группу элементов ИЛИ 4, модель дуги 5, группусумматоров 6, первый элемент ИЛИ 7,элемент 8 задержки, группу элементовИЛИ-НЕ 9, вход 10 пуска устройства,первый элемент И 11, генератор 12тактовых импульсов, триггер 13, второй элемент И 14, счетчик 15, дешифратор 16, третий элемент И 17, группу элементов НЕ 18, элементы НЕ 19и И 20, составляющие узел 21 управления группы, и регистров 22 слоя,второй элемент ИЛИ 23, первый регистр24, второй регистр 25 и блок 26 вычитания кодов,Устройство работает следующим образом. В матрицу 1 заносится информация о топологии моделируемого графа сети. При этом триггеры 2 устанавливаются 40 в единичное состояние, если соответ- ствующие вершины графа соединены дугой. введены группа сумматоров 6, регистры 22 слоя, группа элементов НЕ 18,группа элементов ИЛИ-НЕ 9, элемент8 задержки, элементы ИЛИ 7,23, элемент И 17, регистры 24, 25, блок 26вычитания кодов, группа узлов 21 управления, причем каждый узел управления содержит элемент НЕ 19 и элемент И 20. 3 ил,.2Первый этап фуйкционирования устройства обозначается появлением пускового сигнала (импульса) на входе 10 пуска утоойства. Этот сигнал производит обнуление регистров 22 слоя и счетчика 15. Этот же сигнал через вторые входы группы элементов ИЛИ 4 поступает на группу входов элемента И 14 (в результате чего формируется управляющий сигнал записи информации в регистр 24) и на управляющие входы моделей дуг соответствующего столбца матрицы 1. Появление управляющих сигналов на входах моделей дуг обеспечивает считывание информации, поступающей на входы групп сумматоров б со всех столбцов матрицы 1. На выходах сумматоров 6 формируются суммарные числа дуг, выходящих из соответствующих вершин моделируемого графа, которые образуют и-мерный. вектор 7,Полученная информация передается на входы регистров 24 и 25. Прием информации регистром 25 осуществляется беспрепятственно, а прием регистром 24 только при наличии сигнала разрешения записи на его управляющем входе. Одновременно с записью в регистр 24 с его группы выходов на входы группы элементов ИЛИ-НЕ 9 поступа" ют сигналы о количестве выходящих дуг для каждой вершины, На выходах элементов ИЛИ-НЕ 9 формируются сигналы высокого потенциала, соответству- ющие вершинам, не имеющим выходящих дуг, которые составят набор вершин, входящих в первый слой. Эти сигналы записываются в тот регистр 22 слоя,на отдельном управляющем входе которого присутствует высокий потенциал, поступающий с выхода дешифратора 16.Второй этап функционирования устройства начинается с появлением сигналов, поступающих с выходов регистра 22, слоя, которые дают управляю 5щую информацию для группы элементовНЕ 18 (вырабатывающих сигналы управления записью в регистр 22 слоя сцелью избежать повторов записи сигналов высокого потенциала, соответствующих вершинам, которые ранее распределены по слоям), формируют сигнална выходе элемента ИЛИ 23 и вызываютсчитывание информации с моделей дуг,принадлежащих тем столбцам матрицы1, которые соответствуют вершинам,составляющим первый слой исследуемого графа.Информация с моделей дуг поступает на входы сумматоров б, на выходахкоторых формируется и-мерный вектор(характеризующий суммарное количество дуг, входящих в вершины первого слоя). После этого и-мерный вектор П, записывается только в регистр 2525, а регистром 24 не может бытьпринят из-за отсутствия управляющегосигнала, Содержимое регистров 24 и25 подается на входы блока 2 б вычитания кодов, в результате чего на выходе получается новый и-мерный векторЧ=Ч,-11 который поступает по информационной шине на вход регистра24 и записывается в него при наличииуправляющего сигнала. Сигнал управления формируется в результате переключения триггера 13 в единичное сос"тояние, который переключается по переднему фронту поступающего на егоединичный вход сигнала с выхода эле 40мента ИЛИ 23, Сигнал с выхода триггера 13 разрешает прохождение импульсов с генератора 12 через элементИ 11 на вход счетчика 15 и на входэлемента 8 задержки, Время зажержкиимпульса в элементе 8 задержки выбрано такйм образом, что задерживаемыйимпульс поступает к тому моментувремени, когда завершено вычитаниесодержимого регистров 24 и 25,Одновременно с записью в регистр24 с его группы выходов на входыгруппы элементов ИЛИ-НЕ 9 поступаютсигналы о количестве выходящих дугвершин, еще не распределенных послоям исследуемого графа. В резуль"тате выявляются новые вершины, неимеющие выходящих дуг, которые образованы в результате вычитания и-мер А = 00010100000 00000000000 00000010000 01000000000 00000000001 00000010000 00000000000 01000000000 10010000001 10000000000 00100001000 ных векторов Ч,-Б что создает навыходах элементов ИЛИ-НЕ 9 высокиепотенциалы, соответствующие вершинам,ранее распределенным по слоям, и новым вершинам, составляющим второйслой.Первый импульс, поступивший с выхода генератора 12 на вход счетчика15, увеличивает его содержимое наединицу, вследствие чего на выходедешифратора 1 б формируется позицион"ный двоичный код, разрешающий записьинформации в регистр 22 слоя,Сигналы с выходов групйыэлементов ИЛИ-НЕ 9 записьваются в соответствующие разряды регистра 22слоя,Управление записью осуществляют выходные сигналы группы элементов НЕ18, которые разрешают запись в теразряды регистра, которые ранее неучаствовали при фиксировании вершинпредыдущего слоя. Таким образом, определяются вершины, составляющие новый слой исследуемого графа.Последующие вычислительные этапыфункционирования устройства аналогичны предыдущему.Останов устройства происходит после распределения всех вершин моделируемого графа по слоям, чему соответ"ствуют высокие потенциалы на выходахвсех элементов ИЛИ-НЕ 9, которые по"ступают на входы элемента И 17, сигнал высокого потенциала с выхода которого устанавливает триггер 13 внулевое состояние, запрещая тем самым прохождение импульсов с генератора 12 через элемент И 11,После останова устройства в соответствующих регистрах 22 слоя записьваются вершины, распределенные послоям исследуемого графа,Рассмотрим работу устройства приразбиении связного графа без контуров на слои,Пусть задан граф, описываемый матрицей связности А, 1376099Первый этап функционирования устройства обозначается появлением пускового импульса на входе 10 пускаустройства, Этот сигнал обнуляет груп 5пу регистров 22 слоя и счетчик 15,Этот же импульс поступает на вторыевходы группы элементов ИЛИ 4, с выходов которых подаются сигналы навходы элемента И 14 и на управляющие 10входы моделей дуг, разрешая считывание информации со всех столбцов матрицы 1. На выходе соответствующегосумматора группы Формируется в двоичном параллельном коде число дуг, выходящих из соответствующей вершиныобразующее и-мерный вектор Ч =2,0,1,1,1,1,0,1,3,1,2,Так, в соответствии с топографиейграфа на выходе сумматора 6, будетчисло два, на выходе сумматора 6ноль, сумматора 6 один и т,д. Этаинформация беспрепятственно записывается в регистр 25, а в регистр 24записывается после поступления на 25его управляющий вход импульса с выхода элемента ИЛИ 7, на первый входкоторого поступает импульс с выходаэлемента И 14. После записи информации в регистр 24 импульс с выхода 30элемента ИЛИ 7, а следовательно, ипусковой импульс заканчиваются. Таким образом, во втором и седьмомразрядах регистра 24 записываютсянули, Это свидетельствует о том, что35соответствующие вершины не имеют исходящих дуг, Одновременно с,записьюв регистр 24 с его группы выходовна входы группы элементов ИЛИ-НЕ 9поступает в параллельном двоичномкоде информация о колйчестве дуг,выходящих из соответствунзцих вершин.Содержимое регистров 24 и 25 поступает по информационным шинам навходы блока 26 вычитания кодов, гдепроисходит вычитание содержимого регистра. 24 и содержимого регистра 25.Так как в них содержится одинаковаяинформация, то результат, равный нулю во всех разрядах, по информационной шине поступает на вход регистра5024, но отсутствие управляющего сигнала записи в регистр 24 запрещаетзапись вновь поступившей информации,тем самым оставляя неизменным содержимое этого регистра. В то же времяна выходах элементов ИЛИ"НЕ 9 и 97формируются сигналы высокогопотенциала, которые записываются в регистр 22 по разрешающему сигналу на управляющем входе, поступающему с первого выхода дешифратора 16. Сигналы высокого потенциала, записанные во второй и седьмой разряды регистра 22, слоя, соответствуют тому, что данные вершины образуют первый слой моделируемого графа.Второй этап функционирования устройства начинается с момента, когда на втором и седьмом выходах регистра 22, слоя появляются сигналы высокого потенциала, поступающие на первые входы элементов ИЛИ 4и 4, элементов НЕ 18, и 18 , вторые и седьмые входы элемента ИЛИ 23. Сигнал с выхода элемента ИЛИ 23 поступает на единичный вход триггера 13, устанавливая его в единичное состояние. Выходной сигнал триггера через элемент И 11 разрешает прохождение импульсов с генератора 12, Первый импульс с генератора 12 поступает на счетчик 15, увеличивая его содержимое на единицу, и на вход элемента 8 задержки. Сигналы с выходов элементов НЕ 18 поступают на управляющие входы регистра 22слоя и на первые входы первой группы узлов 21 управления. На выходах всех элементов НЕ 18, кро" ме элементов НЕ 18, и 18 присутствуют высокие потенциалы, нулевые потенциалы с выходов элементов НЕ 18 и 18, запрещают запись в соответствующие разряды регистра 22 слоя,Когда счетчиком 15 принят первый импульс с генератора 12, который увеличивает его содержимое на единицу, на его.выходе формируется двоичный код, который вызьвает появление сигнала высокого потенциала на втором выходе дешифратора 16. Сигнал, поступающий с второго выхода дешифратора 16, разрешает запись в регистр, так как поступает на управляющий вход регистра 22слоя. В это же время сигналы высокого потенциала с выходов элементов ИЛИ 4 и 4, поступают на . управляющие входы моделей дуг второго и седьмого столбца матрицы 1, разрешая считывание информации с этих столбцов на выходы группы сумматоров 6. Суммарные сигналы, полученные на выходах группы сумматоров 6, формируют а-мерный вектор Б, 0,0, 1, 1,0, 1, О, 1, О, О, О , который записьвается толь ко в регистр 25, а регистром 24 не может быть принят из-за отсутствияуправляющего сигнала записи, Содержимое регистров 24 и 25 поступаетна входы блока 26 вычитания кодов, врезультате чего на выходе получается.новый и-мерный вектор 7=7,-0 = Р О0,0,1,0,0,0,3,1,2 , который проходитпо информационной шине на вход регистра 24 и записывается в него при наличии управляющего сигнала, Сигналуправления формируется в результатепереключения триггера 13 в единичноесостояние. Это переключение происхо,дит по переднему фронту поступающегона единичный вход триггера импульса 15с выхода элемента 23. Сигнал с выхода триггера 13 разрешает прохождениеимпульсов с генератора 12 через элемент И 11. Импульс, задержанный вэлементе 8 задержки, приходит к тому 20моменту времени, когда завершено вычитание содержимого регистров 24 и25,Одновременно с записью в регистр24 с его группы выходов на входы элементов ИЛИ-НЕ 9 поступают сигналы околичестве выходящих дуг для вершин,еще не распределенных по слоям исследуемого графа, В результате на выходе элементов ИЛИ-НЕ 9-9и 9-9 появляются сигналы высокого потенпиала,запись которых происходит во все разряды регистра 22 слоя, за исключением второго и седьмого разрядов, Таким образом, в регистре 22 я слоя в35третьем, четвертом, шестом и восьмомразрядах записываются сигналы высокого потенциала, определяющие вершинывторого слоя.В дальнейшем выполняются два последующих этапа распределения вершинисследуемого графа по слоям, аналогичных второму этапу, где в результате производимых вычислений получаются новые и-мерные векторы, которые45определяют окончательное распределение оставшихся вершин моделируемогографа по слоям. По окончании вычислительного процесса, производимогоустройством, в соответствующих разрядах регистров 22-22 слоя записываются сигналы высокого потенциала,которые указывают, какие вершины составляют тот или иной слой моделируемого графа при его разбиении на слои.55Формула изобретенияУстройство для разбиения графовна слои, содержащее матрицу пкп моделей дуг, где и - число вершин графа, счетчик, дешифратор, группу элементов ИЛИ, первый и второй элементыИ, триггер и генератор тактовых импульсов, выход которого подключен кпервому входу первого элемента И, авыход триггера соединен с вторымвходом первого элемента И, выход которого соединен со счетным входомсчетчика, выход которого соединен синформационным входом дешифратора,а каждая модель дуги состоит из триггера и элемента И, причем в кажцоймодели дуги выход триггера подключенк первому входу элемента И, о т л ич а ю щ е е с я тем, что, с цельюрасширения функциональных возможностей за счет разбиения связного ориентированного графа без контуров наслои, в него. введены группа из псумматоров, п регистров слоя, группа из и элементов НЕ, группа из иэлементов ИЛИ-НЕ, элементзадержки,первый и второй элементы ИИ, третийэлемент И, первый и второй регистры,блок вычитания кодов и игруппыиз и узлов управления, причем каждый узел управления содержит элементИ и элемент НЕ, выход которого соединен с первым входом элемента Итого же узла управления, выход элемента И является выходом узла управления, второй вход элемента И является первым входом узла управления,вход элемента НЕ является вторымвходом узла управления, выходы моделей дуг каждой строки матрицы соединены с информационными входами соответствующего сумматора группы, выходы которых подключены к информаци.онным входам первой группы первогорегистра и к информационным входамвторого регистра, выходы первой группы первого регистра и выходы второгорегистра соединены соответственно свходами уменьшаемого и вычитаемогоблока вычитания кодов, выходы которого подключены к информационнымвходам группы первого регистра, входы второй группы первого регистра со"единены с входами элементов ИЛИ-НЕгруппы, выходы которых подключены кинформационным входам всех регистровслоя и к входам третьего элементаИ, выходы первого регистра слоя подключены к входам соответствующихэлементов НЕ группы, выходы которыхподключены к входам разрешения запи 1376099 1 Оси второго регистра слоя и первым входам узлов управления первой группы, выходы которых подключены к входам разрешения записи третьего регистра слоя и первым входам узлов уп 5 равления второй группы, выходы узлов управления (и)-й группы подключенык входам разрешения записи и-го регистра слоя, выходы одноименных разрядов всех регистров слоя объединены и подключены к входам второго элемента ИЛИ и первым входам соответствующих элементов ИЛИ группы, выход второго элемента ИЛИ подключен к входу установки в "1" триггера, вход установки в "О" которого соединен с выходом третьего элемента И, выход первого элемента И подключен к входу элемента задержки, выход которого соО 1 единен с первым входом первого элемента ИЛИ, выходы дешифратора подключены к входам разрешения записи всех регистров слоя, второй вход элемента И ка;кдой модели дуги является управляющим входом этой модели дуги, вход пуска устройства соединен с входами установки в "О" счетчика и всех регистров слоя и с вторыми входами элементов ИЛИ группы, выходы которых подключены к управляющим входам всех моделей дуг соответствующего столбца матрицы и к входам второго элемента И устройства, выход второго элемента И подключен к второму входу первого элемента ИЛИ, выход которого соединен с входом разрешения записи первого ре гистра.1376099 Ф ффь СоставиТехред едактор Н.Тупи Тираж 704НИИПИ Государственного комитетапо делам изобретений и открытий3035, Москва, Ж, Раушская и ка дписнР В 4/5 дприяти зводственно-полиграфическ ель ИЛршов .Кравчук Корректор В.Бутяга Ужгород, ул.Проектная,4