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

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

Иллюстрации

Показать все

Реферат

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛ ИСТИЧЕСНИХ

РЕСПУБЛИН (дц 4 С 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

И АВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4 1.26154/24-.24 (22) 24.06.86 (46) 23.02.88. Бюл. У 7 (72) М.П.Медиченко, Г.В.Буряк и С.В.Артюшенко (53) 681.325 (088 ° 8) (56) Авторское свидетельство СССР

N 716043, кл. С 06 F 15/20, 1977 °

Авторское свидетельство СССР .1Ф 959090, кл. С 06 Р 15/20, 1981.

ÄÄSUÄÄ 1376099 А1 (54) УСТРОЙСТВО ДЛЯ РАЗБИЕНИЯ ГРАФОВ1

НА СЛОИ (57) Изобретение относится к вычислительной технике и может быть использовано при исследовании сетевых графов, а также при решении задач организации вычислительного процесса и мультипроцессорных вычислительных системах. Изобретение позволяет расширить функциональные возможности

1376099 за счет разбиения связного ориентированного графа без контуров на слои.

Для этого в устройство, содержащее матрицу 1 моделей дуг 5, счетчик 15, дешифратор 16, группу элементов ИЛИ

4, элементы И 11, 14, триггер 13, генератор 12 тактовых импульсов, причем каждая модель дуги содержит триг

rep 2 и элемент И 3, дополнительно

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

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

Устройство содержит матрицу 1 о моделей дуг, каждая из которых состоит из триггера 2 и элемента 3.

Устройство содержит также группу эле- 20 ментов ИЛИ 4, модель дуги 5, группу сумматоров 6, первый элемент ИЛИ 7, элемент 8 задержки, группу элементов

ИЛИ-НЕ 9, вход 10 пуска устройства, первый элемент И 11, генератор 12 тактовых импульсов, триггер 13, второй элемент И 14, счетчик 15, дешифратор 16, третий элемент И 17, группу элементов HE 1 8, элементы НЕ 19 и И 20, составляющие узел 21 управ- 30 ления группы, и регистров 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. Появление управляющих сигналов на входах моделей дуг обеспечивает считывание информации, поступающей на входы групп сумматоров 6 со всех столбцов матрицы 1. На выходах сумматоров 6 формируются суммарные числа дуг, выходящих из соответствующих вершин моделируемого графа, которые образуют и-мерный. вектор V

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

1376099

Второй этап функционирования устройства начинается с появлением сигналов, поступающих с выходов регистра 22, слоя, которые дают управляюI

5 щую информацию для группы элементов

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

1, которые соответствуют вершинам, составляющим первый слой исследуемого графа.

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

25, а регистром 24 не может быть принят из-за отсутствия управляющего сигнала. Содержимое регистров 24 и

25 подается на входы блока 26 вычитания кодов, в результате чего на выходе получается новый и-мерный вектор

V =V,-U, который поступает по информационной шине на вход регистра

24 и записывается в него при наличии управляющего сигнала. Сигнал управления формируется в результате переключения триггера 13 в единичное состояние, который переключается по переднему фронту поступающего на его единичный вход сигнала с выхода эле40 мента ИЛИ 23. Сигнал с выхода триггера 13 разрешает прохождение импульсов с генератора 12 через элемент

И 11 на вход счетчика 15 и на вход элемента 8 задержки. Время зажержки импульса в элементе 8 задержки выбрано такйм образом, что задерживаемый импульс поступает к тому моменту времени, когда завершено вычитание содержимого регистров 24 и 25.

Одновременно с записью в регистр

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

00000000001

10010000001

00100001000

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

Первый импульс, поступивший с выхода генератора 12 на вход счетчика

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

Сигналы с выходов групйы элементов ИЛИ-НЕ 9 записываются в соответствующие разряды регистра 22 слоя.

Управление записью осуществляют выходные сигналы группы элементов НЕ

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

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

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

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

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

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

Первый этап функционирования устройства обозначается появлением пускового импульса на входе 10 пуска устройства. Этот сигнал обнуляет груп5 пу регистров 22 слоя и счетчик 15.

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

1,1,1,1,0,1,3,1,2}.

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

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

Содержимое регистров 24 и 25 поступает по информационным шинам на входы блока 26 вычитания кодов, где происходит вычитание содержимого регистра. 24 и содержимого регистра 25.

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

24, но отсутствие управляющего сигнала записи в регистр 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,, присутствуют высокие потенциалы, нулевые потенциалы с выходов элементов HE 18 и 18, запрещают запись в соответствующие разряды регистра 22 слоя.

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

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

6. Суммарные сигналы, полученные на выходах группы сумматоров 6, формируют и-мерный вектор U, (0,0, 1, 1,0, 1, 0,1,0,0,03 который записывается толь ко в регистр 25, а регистром 24 не может быть принят из-за отсутствия

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

25.

Одновременно с записью в регистр

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

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

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

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

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

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

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

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

И, выходы первого регистра слоя подключены к входам соответствующих элементов НЕ группы, выходы которых подключены к входам разрешения запи1376099

10 си второго регистра слоя и первым входам узлов управления первой группы, выходы которых подключены к входам разрешения записи третьего регистра слоя и первым входам узлов уп5 равления второй группы, выходы узлов управления t, n-2)-й группы подключены к входам разрешения записи и-го регистра слоя, выходы одноименных разрядов всех регистров слоя объединены и подключены к входам второго элемента ИЛИ и первым входам соответствующих элементов ИЛИ группы, выход второго элемента ИЛИ подключен к вхо-15 ду установки в "1" триггера, вход установки в "0" которого соединен с выходом третьего элемента И, выход первого элемента И подключен к входу элемента задержки, выход которого со-20

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

И ка;кдой модели дуги является управляющим входом этой модели дуги, вход пуска yñòðîéñòâà соединен с входами установки в "0" счетчика и всех регистров слоя и с вторыми входами элементов ИЛИ группы, выходы которых подключены к управляющим входам всех моделей дуг соответствующего столбца матрицы и к входам второго элемента

И устройства, выход второго элемента

И подключен к второму входу первого элемента ИЛИ, выход которого соединен с входом разрешения записи первого регистра.

1376099

Составитель И.Ершов

Техред А.Кравчук

Редактор .Тупица

Корректор В.Бутяга

Заказ 789/48

Производственно-полиграфическое предприятие, г.Ужгород, ул.Проектная,4

l !

l !

Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5