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

(Л

00

Од

о со со

за счет разбиения связного ориентированного графа без контуров на слои. Для этого в устройство, содержащее матрицу 1 моделей дуг 5, счетчик 15, дешифратор 16, группу элементов ИЛИ 4, элементы И 11, 14, триггер 13, генератор 12 тактовых импульсов, причем каждая модель дуги содержит гер 2 и элемент И 3, дополнительно

введены группа сумматоров 6, регистры 22 слоя, группа элементов НЕ 18, группа элементов ИЛИ-НЕ 9, элемент 8 задержки, элементы ИЛИ 7,23, элемент И 17, регистры 24, 25, блок 26 вычитания кодов, группа узлов 21 управления, причем каждый узел управления содерзкит элемент НЕ 19 и элемент И 20. 3 ил.

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

f

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

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

На фиг, 1 представлена структурная схема устройства; на фиг.2 - граф, подлежащий разбиению на слои; на фиг.З - то же, после распределения вершин по слоям.

Устройство содержит матрицу 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 устанавливаются в единичное состояние, если соответствующие вершины графа соединены дугой.

. 5

Ю

5

0 0

5

0

5

Первый этап функционирования устройства обозначается появлением пускового сигнала (импульса) на входе 10 пуска устройства. Этот сигнал производит обнуление регистров 22 слоя и счетчика 15. Этот же сигнал через вторые входы группы элементов ИЛИ 4 поступает на группу входов элемента И 14 (в результате чего формируется управляющий сигнал записи информации в регистр 24) и на управляющие входы моделей дуг соответствующего столбца матрицы 1. Появление управляющих сигналов на входах моделей дуг обеспечивает считьшание информации, поступа- ющер на входы групп сумматоров 6 со всех столбцов матрицы 1. На выходах сумматоров 6 формируются суммарные числа дуг, выходящих из соответствующих вершин моделируемого графа, которые образ тот п-мерный. вектор V.

Полученная информация передается на входая регистров 24 и 25. Прием информации регистром 25 осуществляется беспрепятственно, а прием регистром 24 только при н.аличии сигнала разрешения записи на его управляющем входе. Одновременно с записью в регистр 24 с его группы выходов на входы группы элементов ИЛИ-НЕ 9 поступают сигналы о количестве выходящих дуг для каждой вершины. На выходах элементов ИЛИ-НЕ 9 формируются сигналы высокого потенциала, соответству- ющие вершинам, не имеющим выходящих дуг, которые составят набор вершин, входящих в первый слой. Эти сигналы аписьюаются в тот регистр 22 слоя, на отдельном управляющем входе кото-, iporo присутствует высокий потенциал, поступающий с выхода дешифратора 16.

Второй этап функционирования устройства начинается с появлением сигналов, поступакнцих с выходов регистра 22 слоя, которые дают управляющую информацию для группы элементов НЕ 18 (вырабатывающих сигналы управления записью в регистр 22 слоя с целью избежать повторов записи сигналов высокого потенциала, соответствующих вершинам, которые ранее распределены по слоям), формируют сигна на выходе элемента ИЛИ 23 и вызывают считывание информации с моделей дуг, принадлежащих тем столбцам матрицы 1, которые соответствуют вершинам, составляющим первьш слой исследуемого графа.

Информация с моделей дуг поступает на входы сумматоров 6, на выходах которых формируется п-мерный вектор и, (характеризующий суммарное количество дуг, входящих в вершины первого слоя), После этого п-мерный вектор и записывается только в регистр 25, а регистром 24 не может быть принят из-за отсутствия управляющего сигнала. Содержимое регистров 24 и 25 подается на входы блока 26 вычитания кодов, в результате чего на выходе получается новый п-мерный векто ,-U, которьй поступает по информационной шине на вход регистра 24 и записывается в него при наличии управляющего сигнала. Сигнал гуправ- ления формируется в результате пере ключения триггера 13 в единичное состояние, который переключается по переднему фронту поступающего на его единичный вход сигнала с выхода элемента ИЛИ 23. Сигнал с вьпсода триггера 13 разрешает прохождение импульсов с генератора 12 через элемент И 11 на вход счетчика 15 и на вход элемента 8 задержки. Время зажержки импульса в элементе 8 задержки выбрано таким образом, что задерживаемый импульс поступает к тому моменту времени, когда завершено вычитание содержимого регистров 2 к 25.

Одновреме;1но с записью в регистр 24 с его группы выходов на входы группы элементов ИЛИ-НЕ 9 поступают сигналы о количестве выходящих дуг вершин, еще не распределенных по слоям исследуемого графа. В резуль- тате выявляются новые вершины, не имею1цие выходящих дуг, которые образованы в результате вычитания п-мер0

5

0

5

0

5

0

5

0

5

ных векторов , что создает на выходах элементов ШШ-НЕ 9 высокие потенциалы, соответствующие вершинам, ранее распределенным по слоям, и новым вершинам, составляющим второй слой.

Первый импульс, поступивший с выхода генератора 12 на вход счетчика 15, увеличивает его содержимое на единицу, вследствие чего на выходе дешифратора 16 формируется позиционный двоичный код, разрешающий запись информации в регистр 22 слоя. : Сигналы с выходов rpynmi элементов ИЛИ-НЕ 9 записьюаются в соответствующие разряды регистра 22 слоя. Управление записью осуществляют выходные сигналы группы элементов НЕ 18, которые разрешают запись в те разряды регистра, которые ранее не участвовали при фиксировании вершин предыдущего слоя. Таким образом, определяются вершины, составляющие новый слой исследуемого графа.

Последующие вычислительные этапы функционирования устройства аналогичны предыдущему.

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

После останова устройства в соответствующих регистрах 22 слоя запи- сьшаются вершины, распределенные по слоям исследуемого графа.

Рассмотрим работу устройства при разбиении связного графа без контуров на слои.

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

00010100000 00000000000 00000010000 01000000000 00000000001 00000010000 00000000000 01000000000 10010000001 10000000000 00100001000

Первый этап функционирования устройства обозначается появлением пускового импульса на входе 10 пуска устройства. Этот сигнал обнуляет груп пу регистров 22 слоя и счетчик 15. Этот же импульс поступает на вторые входы группы элементов ИЛИ 4, с выходов которых подаются сигналы на входы элемента И 14 и на управляющие входы моделей дуг, разрешая считывание информации со всех столбцов матрицы 1. На выходе соответствующего сумматора группы формируется в двоичном параллельном коде число дуг, выходящих из соответствзтащей вершины, образующее п-мерный вектор V,,i,0, 1,1,1,1,0,1,3,1,2.

Так, в соответствии с топографией графа на выходе сумматора 6, будет число два, на выходе сумматора 6 ноль, сумматора 6 один и т.д. Эта информация беспрепятственно записывается в регистр 25, а в регистр 24 записьшается после поступления на его управляющий вход импульса с выхода элемента ИЛИ 7, на первый вход которого поступает импульс с выхода элемента И 14. После записи информации в регистр 24 импульс.с вькода элемента ИЛИ 7, а следовательно, и пусковой импульс заканчиваются. Таким образом, во втором и седьмом разрядах регистра 24 записыЪаются нули. Это свидетельствует о том, что соответствующие вершины не имеют исходящих дуг. Одновременно с .записью в регистр 24 с его группы выходов на входы группы элементов ИЛИ-НЕ 9 поступает в параллельном двоичном коде информация о количестве дуг, выходящих из соответствующих вершин

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

Q

5

0

5

0

5

0

5

0

5

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

Второй этап функционирования устройства начинается с момента, когда на втором и седьмом выходах регистра 22, слоя появляются сигналы высокого потенциала, поступающие на первые входы элементов ИЛИ 4 , и 4, элементов НЕ 18, и 18, вторые и седьмые оды элемента ИЛИ 23, Сигнал с выхода элемента ИЛИ 23 поступает на единичный в,ход триггера 13, устанавливая его в единичное состояние. Выходной сигнал триггера через элемент И 11 разрешает прохождение-импульсов с генератора 12, Первый импульс с генератора 12 поступает на счетчик

15,увеличивая его содержимое на единицу, и на вход элемента 8 задержки. Сигналы с выходов элементов НЕ

18 поступают на управляющие входы регистра 22 2 слоя и на первые входы первой группы узлов 21 управления. На выходах всех элементов НЕ 18, кроме элементов НЕ 18, и 18-,, присутствуют высокие потенциалы, нулевые потенциалы с выходов элементов НЕ 18 и 18-1 запрещают запись в соответствующие разряды регистра 22 слоя.

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

16,разрешает запись в регистр, так как поступает на управляющий вход регистра 222 слоя. В это же время сигналы высокого потенциала с выходов элементов ИЛИ 4 и 4 поступают на . управлякшще входы моделей дуг второго и седьмого столбца матрицы 1, разрешая считьтание информации с этих столбцов на выходы группы сумматоров 6, Суммарные сигналы, полученные на выходах группы сумматоров 6, формиру-, ют п-мерный вектор U,0,0,1,1,0,1, 0,1,0,0,01, который записьгоается толь- ко в регистр 25, а регистром 24 не может быть принят из-за отсутствия

управляющего сигнала записи. Содержимое регистров 24 и 25 поступает на входы блока 26 вычитания кодов, в результате чего на выходе получается- новый п-мерный вектор 2,0, 0,0,1,0,0,0,3,1,2}, который проходит по информационной шине на вход регистра 24 и записьтается в него при наличии управляющего сигнала. Сигнал управления формируется в результате переключения триггера 13 в единичное состояние. Это переключение происхо- .дит по переднему фронту поступакщего на единичный вход триггера импульса с выхода элемента 23. Сигнал с выхода триггера 13 разрешает прохождение импульсов с генератора 12 через элемент И 11. Импульс, задержанный в элементе 8 задержки, приходит к тому моменту времени, когда завершено вычитание содержимого регистров 24 и 25.

Одновременно с записью в регистр 24 с его группы выходов на входы элементов ИЛИ-НЕ 9 поступают сигналы о количестве выходяш х дуг для вершин, еще не распределенных по слоям исследуемого графа. В результате на выходе элементов ИЛИ-НЕ и 94.-9g по являются сигналы высокого пoтeнJiиaлa запись которых происходит во все разряды регистра 222 слоя, за исключением второго и .седьмого разрядов. Таким образом, в регистре 22д с;лоя в

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

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

Формула изобретения

Устройство для разбиения графов на слои, содержащее матрицу пип мо10

15

60998

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

0

5

5

0

5

0

5

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

си второго регистра слоя и первым входам узлов управления первой группы, выходы которых подключены к входам разрешения записи третьего регистра слоя и первым входам узлов управления второй группы, выходы узлов управления (п-2)-й группы подключены к входам разрешения записи п-го регистра слоя, выходы одноименных раз- рядов всех регистров слоя объединены и подключены к входам второго элемента ИЛИ и первым входам соответствующих элементов ИЛИ группы, выход второго элемента ИЛИ подключен к входу установки в 1 триггера, вход установки в О которого соединен с выходом третьего элемента И, выход первого элемента И подключен к входу элемента задержки, выход которого соФи.2

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