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

 

Изобретение относится к области вычислительной техники и может быть использовано при автоматизированном решении задачи компоновки электронных схем. Целью изобретения является упрощение устройства„ Эта цель достигается тем, что в блок управления введены группа элементов И, группа . счетчиков, элементы ИЛИ, элементы задержки и элемент запрета, а каждый канал генератора случайных сочетаний состоит из источника пуассоновского потока импульсов, элемента И, элемента запрета, элемента ИЛИ, триггера и элемента 2H-IiIBi. 1 з.п. ф-лы, 4 ил.

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

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

РЕСПУБЛИК (19) (И) (5D 4 G 06 Р 15 20

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3808733/24-24 (22} 31,10.84 (46) 30.11.86. Бюл. У 44 (71) Таганрогский радиотехнический институт им. В. Д. Калмыкова (72) В. М. Глушань, Л. И. Щербаков и И. П. Левин (53) 681.333(088.8) (56) Авторское свидетельство СССР

Р 656073, кл. G 06 F 15/36, 1976.

Авторское свидетельство СССР

1 1086434, кл. G 06 F 15/20, 1982. (54) УСТРОЙСТВО ДЛЯ РАЗБИЕНИЯ ГРАФА

НА ПОДГРАФЫ (57) Изобретение относится к области вычислительной техники и может быть использовано при автоматизированном решении задачи компоновки электронных схем. Целью изобретения является упрощение устройства. Эта цель достигается тем, что в блок управления введены группа элементов И, группа счетчиков, элементы ИЛИ, элементы задержки и элемент запрета, а каждый канал генератора случайных сочетаний состоит из источника пуассоновского потока импульсов, элемента И, элемента запрета, элемента ИЛИ, триггера и элемента 2И-ИЛИ. 1 s.ï. ф-лы, 4 ил.

1273941

Изобретение относится к вычислительной технике и может быть использовано при автоматизированном решении задачи компоновки электронных схем.

Цель изобретения — упрощение устройства.

На фиг. I приведена структурная схема устройства; на фиг. 2-4 — возможные варианты функциональных схем генератора случайных сочетаний, преобразователя сочетание — код и блока управления.

Устройство содержит регистр 1 блокировки кода сочетаний, генератор

2 случайных сочетаний, блок 3 отображения топологии графов, буферный регистр 4 индикации, блок 5 управления, преобразователь 6 сочетание— код, регистр 7 кода остатка ребер, вычитатель 8, схему 9 сравнения, регистр 10 кода числа внешних ребер, блок 11 регистров индикации, вход 12 установки исходного состояния и входы 13 задания топологии исходного графа. Каждый канал генератора 2 (фиг. 2) состоит из источника 14 пуассоновского потока импульсов, элемента И 15, элемента 16 запрета, элемента ИЛИ 17, триггера 18 и элемента 2И-ИЛИ 19. Преобразователь сочетание — код (на фиг. 3 приведена схема преобразователя на пять входов) содержит десять двухвходовых элементов ИЛИ 20 и 21, образующих четыре линейки и соединенных соответствующим образом. В первую линейку входят четыре элемента ИЛИ 20 и И 21, во вторую — три элемента ИЛИ 20 и

И 21, в третью — два элемента ИЛИ 20 и 21 и в четвертую — один элемент

ИЛИ 20 и 21. Кроме того, преобразователь 6 содержит комбинационную схему, состоящую из элементов 22-25 запрета и элементов ИЛИ 26 и 27, Блок 5 управления (фиг. 4) содержит элемент ИЛИ 28, группу элементов

И 29, группу счетчиков 30, элемент

ИЛИ 31, счетчики 32 и 33, дешифратор

34, последовательно соединенные элементы 35-38 задержки, элементы ИЛИ

39, 40, элемент 41 задержки, элемент

ИЛИ 42, элементы 43, 44 задержки, элемент И 45, элемент 46 запрета, элемент ИЛИ 47, триггер 48 и выходы

49-55.

Сущность и принцип работы предлагаемого устройства состоят в следующем. Разбиение графа G = (Х, U), состоящего из (Xl = п и вершин и !Ul

= V ребер, на 1 подграфов G, = (Х<, З ), G — (X„ U ),..., r-. — (Х

U ) с числом вершин в каждом подграфе соответственно )X,j = n,, 1 Х,1=

= п,... (Х = п1, где n, + п +,..., + n = n осуществляется за 2 этапов, На каждом i-ом этапе производится Q случайных назначений п; верп ин в i-й подграф. Число случайных назначений

О (розыгрышей) определяется заданными точностью и достоверностью разбиения графа на подграфы, а все и вершин в каждом назначении выбираются одновременно (параллельно). После каждого случайного назначения определяется число внешних связей, т.е. число связей между вершинами, выбранными в подграф, и всеми оставшимися (не выбранными ни в какой подграф), Если в результате текущего случайного назначения получен вариант подграфа с меньшим числом внешних свя25 зей, чем в предыдущем назначении, то он запоминается, Таким образом, сформированный после i-ro этапа i-й подграф имеет локально-минимальное число внешних связей. Вершины, вошедшие в i-й подграф, блокируются и исключаются из дальнейшего розыг рьппа.

Так, на первом этапе производится Q, случайных назначений и вершин

35 в первый подграф. Число внешних связей подсчитывается после каждого случайного назначения между выбранным множеством вершин Х,с Х (здесь и далее знак над соответствующей бук40 вой означает не окончательное, а текущее множество) и оставшимися вер Ъ шинами Х 1,Х,, После проведения всех случайных назначений формируется второй подграф G = -(Х,, U ) имеющий

45 локально-минимальное число связей с оставшимся множеством вершин Х Х 1.

На втором этапе формируется второй подграф путем выполнения очередной серии из Q случайных назначений. При

50 этом и вершин выбираются случайным образом из оставшегося после первого этапа множества Х1Х, вершин, а число внешних связей определяется после каждого случайного назначения между г

SS выбранным множеством вершин Х Ы Хф, 2 и оставшимся множеством вершин Х1,(Х, lfX ). После проведения всех Q случайных назначений формируется второй

273941 4 связей. Блок 11 индикации преднаэна55

3 1 подграф С = (Х, U ), имеющий ло2 кально-минимальное число внешних связей с оставшимся множеством вершин Х (Х! U X ), Аналогичным образом.процесс формирования подграфов продолжается до последнего E†- ro этапа, после которого оставшееся множество

=! вершин Х!,(0 Х;) включается в E-й

1:! подграф. Поскольку на каждом этапе формируется подграф с локально-минимальным числом внешних связей, то и суммарное число связей между подграфами также локально-минимально.

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

4 индикации заносится вариант формирования подграфа (номера вершин), лучшии относительно предыдущих вариантов. Преобразователь 6 осуществляет преобразование различных сочетаний единичных сигналов на его входах в соответствующий двоичный код на выходах. Код соответствует числу ребер между вершинами, на которые в блоке 3 отображения топологии графа поданы единичные сигналы. Регистр 7 предназначен для хранения в течение каждого этапа формирования подграфав кода остатка ребер, инцидентных вершинам, не включенных к данному этапу ни в один из подграфов. С помощью вычитателя 8 производится подсчет числа внешних связей. Блок 9 сравнения производит после каждого случайного назначения сравнение числа внешних связей, получившихся в результате данного назначения, с числом внешних связей, полученных от лучшего варианта всех предыдущих случайных назначений, В буферный регистр 10 заносится после сравнения лучшее текущее число внешних чен для визуализации номеров вершин каждого подграфа после оптимального разбиения исходного графа. Блоком 5 управления задается число подграфов, число вершин в каждом подграфе и число случайных назначений, а также формируются все управляющие сигналы, 5 t0

Подготовка устройства к работе производится заданием исходной топологии графа в блок 3 отображения топологии графа путем подачи единичных сигналов на соответствующие входы 13, установкой емкостей счетчиков

30, соответствующих размерностям формируемь|х подграфов, емкости счетчика

32, соответствующей числу назначений и емкости счетчика 33, соответствующей заданному числу подграфов.

Работа устройства (фиг. 1) начинается с подачи на вход 12 сигнала установки исходного состояния. По этому сигналу в нулевое состояние устанавливаются регистр 1, триггеры

18 в генераторе 2, .регистры блока 11 индикации, счетчики 30, 32, 33 и триггер 48 в блоке 5 управления, регистр 10 устанавливается в единичное состояние. Кроме того, по этому же сигналу на все входы блока 3 подаются единичные сигналы, поэтому в регистр 7 записывается суммарное число ребер, соединяющих все вершины исходного граФа ° После этого в генераторе 2 случайных сочетаний начинают формироваться случайные сочетания, т.е. на заданном числе его выходов, но в случайном сочетании, появляются единичные сигналы. Происходит это следующим образом. На выходах источников 14 импульсов (фиг. 2) в случайные моменты времени вырабатываются импульсы, интервалы времени между которыми удовлетворяют пуассоновскому потоку. Случайный импульс, появившийся на выходе любого из источников 14, проходит через соответствующий элемент И 15 и элемент 16 запрета, на один из триггеров 18. Поскольку выход каждого элемента И 15 соединен с прямым входом "своего" элемента 16 запрета и с инверсными входами всех

"чужих" элементов запрета, то случайный импульс, появившийся на выходе любого из источников 14, первым запрещает на время своей длительности прохождение случайных импульсов с других источников 14 через все остальные элементы 16 запрета, Это предотвращает слияние нескольких импульсов на выходах элементов запрета в один на выходе элемента ИЛИ 28.

На прямом выходе того триггера

18, на который прошел случайный импульс, появляется единичный потенциал, а нулевой потенциал с его ин5 12 версного выхода закрывает соответствующий элемент И 15, Это обеспечивает прохождение через элементы

И 15 и элементы запрета только одного случайного импульса на период формирования одного случайного сочетания.

Случайные импульсы с выходов элементов 16 запрета одновременно поступают и в блок 5 управления на входы элемента ИЛИ 28 (фиг. 4). При этом сначала они проходят через первый (верхний по схеме) элемент И группы 29 на первый счетчик группы

30, так как единичным потенциалом с нулевого выхода дешифратора 34 открыт именно этот элемент И группы

29. После того, как на первый счетчик 30 поступает число случайных импульсов, равное его емкости, формируется первое сочетание. При этом первый счетчик устанавливается в исходное состояние, а сигнал с его выхода через элемент ИЛИ 31 поступает на входы счетчика 32, первого элемента 35 задержки, элемента ИЛИ 39 и единичный вход триггера 48, Нулевой сигнал с инверсного выхода триггера 48 блокирует все элементы И 15, что необходимо для предотвращения возможного прохождения случайных импульсов через эти элементы во время выполнения вычислительных операций в других блоках устройства. В это же время импульс с выхода элемента ИЛИ 39 появляется на выходе 50 и поступает на нижние элементы И 19, подключив тем самым прямые выходы триггеров 18 к входам блока 3. В результате этого единичные сигналы подаются на элементы, соответствующие вершинам графа, а на выходах блока

3, отображающих ребра графа, инцидентные тем элементам вершин, на которые поданы единичные сигналы, так же появляются единичные сигналы.

Для получения информации о числе связей (т.е. о числе выходов блока

3, на которых появились единичные сигналы) необходимо число выходов с единичными сигналами, расположенных в произвольном порядке, преобразовать в двоичный код. Это выполняется с помощью преобразователя 6. На фиг. 3 приведен пример реализации преобразователя на пять входов и соответственно на три выхода, так как число в пределах от 0 до 5 представляется 3-х

73941 а

3-х разрядным двоичным кодом. В этом преобразователе пирамидальная схема пар элементов И, ИЛИ 20, 21 компандирует выходной сигнал, т ° е„ любое сочетание единиц на входах преобразует в то же самое число единиц, но расположенных на подряд следующих выходах пирамидальной схемь|, начиная с верхнего выхода, На фиг. 3 приведен пример поступления на входы преобразователя 6 трех единичных сигналов на второй, четвертый и пятый входы соответственно. На выходе пирамидальной схемы единичные сигналы появляются на первом, втором и третьем выходах. Далее сжатый сигнал пирами- . дальной схемы преобразуется комбинационной схемой, состояшей из элементов 22 — 25 запрета в двоичный код числа ребер, инцидентных возбужденным вершинам. Код поступает на вычитатель 8 и по второму по времени выработки сигналу с выхода 51 блока 5, вычитается из кода суммарного числа ребер исходного графа, записанного в регистр 7, сигналом установки исходного состояния.

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

Для получения только внешних ребер из полученного числа необходимо вычесть число ребер, соединяющих оставшиеся вершины, Это осуществляется подключением третьего по времени появления импульса, формируемого на выходе 52 блока 5. При этом единичный сигнал с выхода 52 поступает на вход генератора 2, т.е. на все верхние входы элементов 2И-ИЛИ 19. Затем на вычитатель 8 с выхода 51 блока 5 поступает четвертый по времени единичный сигнал (и второй на выходе 51), в результате чего в вычитателе 8 остается число внешних ребер выделенного подграфа после первого случайного назначения. После этого на схему 9 сравнения с выхода 49 блока 5 поступает пятый по времени формирования импульс, по которому происходит сравнение кодов вычитателя 8 и буферного регистра 10. Ввиду того, что в регистр 10 вначале был записан максимальный код, то после первого слу1273941

25 чайного назначения он всегда больше кода числа внешних ребер вычитателя

8. Поэтому схема 9 сравнения вырабатывает сигнал (этот сигнал по времени появления является шестым), по 5 которому происходит перепись кода из вычитателя 8 в регистр 10. Этот же сигнал поступает на вход буферного регистра 4 индикации, а через элемент ИЛИ 48 блока 5 — на вход 50 генератора 2. Вследствие этого к регистру 4 подключаются прямые выходы триггеров 19 и в него записывается первый вариант сформированного первого подграфа. 15

Затем седьмой импульс, сформированный на выходе элемента 43 задержки, через элементы ИЛИ 17 сбрасывает триггеры 18 и через элементы 46 запрета и ИЛИ 47 триггер 48 в исходное состояние. При этом открываются все элементы И 15 и все устройство готово к формированию нового случайного назначения. Аналогично указанному в генераторе 2 формируется второе случайное назначение, в вычитателе

8 определяется число внешних ребер между вторым вариантом первого подграфа и всеми оставшимися вершинами, а схемой 9 сравнения определяется из 3О двух вариантов первого подграфа тот вариант, который имеет меньшее число внешних ребер. Если оказывается, что первый вариант первого подграфа

"лучше, то схема 9 сравнения íà 35 своем выходе сигнала не вырабатывает и в регистре 4 и регистре 10 остается прежняя информация (в регистре 4 номера вершин первого варианта подграфа, а в регистре 10 число его 40 внешних ребер). Если второй вариант подграфа оказывается "лучше", то на выходе схемы 9 сравнения вырабатывается сигнал, в результате чего в регистр 4 иэ генератора 2 переписыва- 45 ются номера вершин второго варианта первого подграфа, а в регистр 10 переписывается из вычитателя 8 число его внешних ребер. Так продолжается до тех пор, пока генератором 2 не 50 сформируется заданное число назначений. Тогда на выходе счетчика 32 появляется единичный сигнал, который открывает элемент И 45 и закрывает элемент 46 запрета и через время, 55 задаваемое элементом 41 задержки, появляется на его выходе. Задержка необходима для того, чтобы последнее назначение успело обработаться в соответствии с указанной последовательностью управляющих импульсов с первого по седьмой.

Сигнал с выхода элемента 41 задержки поступает на управляющие входы регистров 1, 7 регистров блока 11 и через элемент ИЛИ 42 на входы верхних элементов И 19, При этом "лучший вариант первого подграфа (т.е. номера соответствующих вершин) из буферного регистра 4 переписываются в первый регистр блока 11 регистров индикации, так как сигнал разрешения с дешифратора 34 поступает на первый регистр блока 11 и в регистр 1 блокировки кода сочетаний, поэтому соответствующие выходы регистра I оказываются в нулевом состоянии, а в регистр 10 записывается исходный максимальный код, Поскольку к этому времени все триггеры 18 установлены единичным сигналом с выхода элемента 43 задержки в исходное состояние (на всех инверсных выходах триггеров 18 находятся единичные сигналы), то к блоку 3 подключены входы генератора 2 или инверсные выходы регистра 1 (фиг. 2).

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

Сигнал с выхода элемента 4) задержки, задержавшись на элементе 44 задержки записывает единицу в счетчик 33, в результате чего единичный сигнал появляется на втором выходе дешифратора 34 и открывает для приема информации второй счетчик 30. Этот сигнал с выхода элемента 44 задержки через открытый элемент И 45 (на выходе счетчика 32 единичный сигнал еще действует) и элемент ИЛИ 47 устанавливает триггер 48 в исходное (нулевое) состояние, который разблокирует элементы И 15. После этого все устройство готово для формирования второго подграфа.

Аналогично указанному формируется

"лучший" вариант второго подграфа и номера его вершин записываются во второй регистр блока ll индикации, а в регистр 1 к номерам вершин первого подграфа добавляются номера вершин второго подграфа. Соответственно этому уменьшается число инверсных вЫ-, ходов регистра 1, на которых остаются единичные потенциалы, т.е, уменьшается число вершин, не вошедших ни в один из подграфов. Третий подграф уже формируется из этих оставшихся вершин и т,д. до тех пор, пока не сформируются все подграфы. Признаком окончания формирования подграфов является появление сигнала на выходе счетчика 33.

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

1. Устройство для разбиения графа на подграфы, содержащее регистр блокировки кода сочетаний, генератор случайных сочетаний, первая группа управляющих входов которого соедине- 20 на с инверсными выходами регистра блокировки кода сочетаний, блок отображения топологии графа, регистр кода остатка ребер, преобразователь сочетание — код, входы которого соединены с выходами блока отображения топологии графа, вычитатель, схему сравнения, регистр кода числа внешних ребер, выходы которого соединены с первой группой входов схемы срав- 30 нения, выход которой подключен к входу считывания регистра кода числа внешних ребер, информационные входы которого соединены с второй группой входов схемы сравнения и вы- 3S ходами вычитателя, первая группа входов вычитателя подключена к выходам регистра кода остатка ребер, вторая группа соединена с выходами преобразователя сочетание — код и ин-40 формационными входами регистра кода остатка ребер, буферный регистр индикации, блок регистров индикации и блок управления, включающий два счетчика, дешифратор, входы которого 45 соединены с выходами второго счетчика, триггер, пять элементов ИЛИ, пять элементов задержки и элемент И, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, в со- 50 став блока управления введены группа из N элементов И (N — число вершин графа), группа из N счетчиков, шестой элемент ИЛИ, шестой и седьмой элементы задержки и элемент запрета, SS при этом информационные выходы генератора случайных сочетаний соединены с входами блока отображения топо1273941 1О логии графа и информационными входами буферного регистра индикации, управляющие выходы генергтора случайных сочетаний соединены с входами первого элемента ИЛИ, выходы буферного регистра индикации подключены к информационным входам регистров блока индикации и регистра блокировки кода сочетаний, выход первого элемента ИЛИ соединен с первыми входами элементов И группы блока управления, вторые входы которых подключены к выходам дешифратора и входам разрешения записи регистров блока индикации, выходы элементов И группы блока управления соединены со счетными входами соответствующих счетчиков группы блока управления, выходы которых подключены к входам второго элемента ИЛИ, выход которого соединен с входом первого счетчи ка, входом первого элемента задержки и первым входом третьего элемента

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

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

ИЛИ, выходы третьего и пятого элементов ИЛИ, второго элемента задержки и нулевой выход триггера соединеt

1273 ны с второй 1 руппой управляющих входов генератора случайных сочетаний, выход четвертого элемента ИЛИ соеди— нен с управляющим входом вычитателя, выход третьего элемента задержки соединен с управляющими входами регистра блокировки кода сочетаний, регистра кода остатка ребер, регистра кода числа внешних ребер и регистров блока индикации, выход седьмого элемен- 10 та задержки подключен к управляющему входу схемы сравнения, вход установки исходного состояния устройства соединен с третьим входом шестого элемента ИЛИ и входами установки в 15 нуль регистра блокировки кода сочетаний, генератора случайных сочетаний, блока отображения топологии графа, регистра кода остатка ребер, регистра кода числа внешних ребер, пер†20 вого, второго счетчиков и группы счетчиков блока управления, а информационные входы блока отображения топологии графа являются информационными входами устройства. 25

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

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

1273941

12 S3 фис. Ю

)27394!

Ют Едока У

glue. 4

Составитель С. Назаров

Редактор С. Лисина Техред Л.Сердюкова Корректор Т. Колб

Заказ 6478/47

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

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

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

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