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

ND

DO

CD 4;ib Изобретение относится к вычислительной технике и может быть использовано при автоматизированном решении задачи компоновки электронных схем. Цель изобретения - упрощение устройства. На фиг. 1 приведена структурная схема устройства; на фиг. 2-4 - возможные варианты функциональных схем генератора случайных сочетаний, преобразователя сочетание - код и блока управления Устройство содержит регистр 1 блокировки кода сочетаний, генератор 2 случайных сочетаний, блок 3 отображения топологии графов, буферный регистр 4 индикации, блок 5 управления, преобразователь 6 сочетаниекод, регистр 7 кода остатка ребер, вычитатель 8, схему 9 сравнения, регистр 10 кода числа внешних ребер, блок 11 регистров индикации, вход 12 установки исходного состояния и вхо ды 13 задания топологии исходного графа. Каждый канал генератора 2 (фиг. 2) состоит из источника 14 пуассоновского потока импульсов, элемента И 15, элемента 16 запрета, элемента ИЛИ 17, триггера 18 и элемента 2И-И1ТИ 19о Преобразователь сочетание - код (на фиг. 3 приведена схема преобразователя на пять входов) содержит десять двухвходовых элементов ИЛИ 20 и 21, образующих че тыре линейки и соединенных соответст вующим образом, В nepBjrio линейку вхо дят четыре элемента ИЛИ 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. Сущность и принцип работы предлагаемого устройства состоят в следую41 . 2 щем. Разбиение графа G (Х, U), состоящего из (х| п и верщин и |Ul V ребер, на подграфов G, - (Х(, и,), G - (X.J, и),..., Gg (Xj, Uj ) с числом вершин в каждом подграфе соответственно jxj п,, п,.. lXj| Tij, где п, + Пг +,оо., + По п осуществляется за этапов. На каждом i-ом этапе производится 0. случайных назначений п| верпгин в i-й подграф. Число случайных назначений Q (розыгрышей) определяется заданными точностью и достоверностью разбиения графа на подграфы, а все п верщин в каждом назначении выбираются одновременно (параллельно). После каждого случайного назначения определяется число внешних связей, Тое. число связей между вершинами, выбранными в подграф, и всеми оставшимися (не выбранньми ни в какой подграф). Если в результате текущего случайного назначения получен вариант подграфа с меньшим числом внешних связей, чем в предыдущем назначении, то он запоминается. Таким образом, сформированный после i-ro этапа i-й подграф имеет локально-минимальное число внешних связей. Вершины, вошедшие в i-й подграф, блокируются и исключаются из дальнейшего розыгрыша . Так, на первом этапе производится Q случайных назначений п, вершин в первый подграф. Число внешних связей подсчитывается после каждого случайного назначения между выбранным множеством вершин Х X (здесь и далее знак над соответствующей буквой означает не окончательное, а текущее множество) и оставшимися вершинами , . После проведения всех Q случайных назначений формируется второй подграф G (Х,, U,), имеющий локально-минимальное число связей с оставшимся множеством вершин . На втором этапе формируется второй подграф путем выполнения очередной серии из Q случайных назначений При этом п вершин выбираются случайным образом из оставшегося после первого этапа множества , вершин, а число внешних связей определяется после каждого случайного назначения между выбранным множеством вершин X ( и оставщимся множеством вершин Х(Х, . UXj,). После проведения всех Q случайных назначений формируется второй

3

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

739414

Подготовка устройства к работе производится заданием исходной топологии графа в блок 3 отображения топологии графа путем подачи единич5 ных сигналов на соответствующие входы 13, установкой емкостей счетчиков 30, соответствуюшд1х размерностям формируемых подграфов, емкости счетчика 32, соответствующей числу назначений 10 и емкости счетчика 33, соответствующей заданному числу подграфов.

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

5 этому сигналу в нулевое состояние устанавливаются регистр 1, триггеры 18 в генераторе 2, .регистры блока 11 индикации, счетчики 30, 32, 33 и триггер 48 в блоке 5 управления, ре20 гистр 10 устанавливается в единичное состояние. Кроме того, по этому же сигналу на все входы блока 3 подаются единичные сигналы, поэтому в регистр 7 записывается суммарное чис5 ло ребер, соединяющих все вершины исходного графа. После этого в генераторе 2 случайных сочетаний начинают формироваться случайные сочетания, т.е. на заданном числе его выходов,

0 но в случайном сочетании, появляются единичные сигналы. Происходит это следующим образом. На выходах источников 14 импульсов (фиг. 2) в случайные моменты времени вырабатывают ся импульсы, интервалы времени между которыми удовлетворяют пуассоновскому потоку. Случайный импульс, появившийся на выходе любого из источников 14, проходит через соответствую0 Ш51Й элемент И 15 и элемент 16 запрета, на один из триггеров 18. Поскольку выход каждого элемента И 5 соединен с прямым входом своего элемента 16 запрета и с инверсными входами всех

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

0 других источников 14 через все остальные элементы 16 запрета. Это предотвращает слияние нескольких импульсов на выходах элементов запрета в один на выходе элемента ИЛИ 28.

5 На прямом выходе того триггера 18, на который прошел случайный импульс, появляется единичный потенциал, а нулевой потенциал с его инверского выхода закрывает соответствующий элемент И 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 приведен пример реализации преобразо-55

вателя на пять входов и соответственно на три выхода, так как число в пределах- от О до 5 представляется 3-х

регистра 10. Ввиду таго, что в регистр 10 вначале был записан максимальный код, то после первого слу4163-х разрядным двоичным кодом. В этом преобразователе пирамидальная схема пар элементов И, ИЛИ 20, 2 компандирует выходной сигнал, т.е, любое сочетание единиц на входах преобразует в то же самое число единиц, но расположенныхна подряд следующих выходах пирамидальной схемы, начиная С верхнего выхода. На фиг. 3 приведен пример поступления на входы преобразователя 6 трех единичных сигналов на второй, четвертый и пятый входы соответственно. На выходе пирамидальной схемы единичные сигналы появляются на первом, втором и третьем вьгходах. Далее сжатый сигнал пирами-дальной схемы преобразуется комбинационной схемой, состоящей из элементов 22 - 25 запрета в двоичный код числа ребер, инцидентных возбужденным верщинам. Код поступает на вычитатель 8.и по второму по времени выработки сигналу с выхода 51 блока 5, вычитается -из кода суммарного числа ребер исходного графа, записанного в регистр 7, сигналом установки исходного состояния. В результате этого в вьгчитателе В получают число ребер, представляющих сумму внещних ребер выделенного подграфа после первого назначения, и всех внутренних ребер, соединяющих оставшиеся вершины, т.е. вершины не вьщеленные в подграф. Для получения только внешних ребер из полученного числа необходимо вычесть число ребер, соединяющих оставшиеся верщины. Это осуществляется подключением третьего по времени появления импульса, формируемого иа выходе 52 блока 5. При этом единичный сигнал с выхода 52 поступает на вход генератора 2, т.е. на все верхние входы элементов 2И-ШШ 19. Затем на вычитатель 8 с выхода 51 блока 5 поступает четвертый по времени единичный сигнал (и второй на выходе 51), в результате чего в вычитателе 8 остается число внещних ребер выделенного подграфа после первого случайного назначения. После этого на схему 9 сравнения с выхода 49 блока 5 поступает пятый по времени формирования импульс, по которому происходит сравнение кодов вычитателя 8. и буферного

7

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

Затем седьмой импульс, сформированный на выходе элемента 43 задержки, через элементы ИЛИ 17 сбрасывает триггеры 18 и через элементы 46 запрета и ИЛИ 47 триггер 48 в исходное состояние. При этом открываются все элементы И 15 и все устройство готово к формированию нового случайного назначения. Аналогично указанному в генераторе 2 формируется второе случайное назначение, в вычитателе 8 определяется число внешних ребер между вторым вариантом первого подграфа и всеми оставшимися вершинами, а схемой 9 сравнения определяется из двух вариантов первого подграфа тот вариант, который имеет меньшее число внешних ребер. Если оказывается, что первый вариант первого подграфа лучше, то схема 9 сравнения на своем выходе сигнала не вырабатывает и в регистре 4 и регистре 10 остается прежняя информация (в регистре 4 номера вершин первого варианта подграфа, а в регистре 10 число его внешних ребер). Если второй вариант подграфа оказывается лучше, то на выходе схемы 9 сравнения вырабатывается сигнал, в результате чего в регистр 4 из генератора 2 переписываются номера вершин второго варианта первого подграфа, а в регистр 10 переписывается из вычитателя 8 число его внешних ребер. Так продолжается до тех пор, пока генератором 2 не сформируется заданное число назначений. Тогда на выходе счетчика 32 появляется единичный сигнал, который открывает элемент И 45 и закрьгаает элемент 46 запрета и через время, задаваемое элементом 41 задержки, появляется на его ввлходе. Задержка необходима для того, чтобы послед739418

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

5 с дешифратора 34 поступает на первый регистр блока 11 и в регистр 1 блокировки кода сочетаний, поэтому соответствующие выходы регистра 1 оказываются в нулевом состоянии, а в ре20 гистр 10 записывается исходный максимальный код.

Поскольку к этому времени все триггеры 18 установлены единичным сигналом с выхода элемента 43 задерж5 ки в исходное состояние (на всех инверсных выходах триггеров 18 находятся единичные сигналы), то к блоку 3 подключены входы генератора 2 или ин версные выходы регистра 1 (фиг, 2).

0 Поэтому в блоке 3 возбуждаются те

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

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

Аналогично указанному формируется лучший вариант второго подграфа и

5 номера его вершин записываются во второй регистр блока 11 индикации, а в регистр I к номерам вершин первого подграфа добавляются номера вершин второго подграфа. Соответственно этому уменьшается число инверсных вы ходов регистра 1, на которых остаются единичные потенциалы, т„е. уменьшается число вершин, не вошедших ни в один из подграфов. Третий подграф уже формируется из этих оставшихся вершин и т.д. до тех пор, пока не сформируются все подграфы. Признаком окончания формирования подграфов является появление сигнала на выходе счетчика 33. Формула изобретени Г. Устройство для разбиения графа на подграфы, содержащее регистр блокировки кода сочетаний, генератор случайных сочетаний, первая группа управляюш.их входов которого соединена с инверсными выходами регистра блокировки кода сочетаний, блок отображения топологии графа, регистр кода остатка ребер, преобразователь сочетание - код, входы которого соединены с в гходами блока отображения топологии графа, вычитатель, схему сравнения, регистр кода числа внешних ребер, выходы которого соединены с первоц группой входов схемы сравнения, выход которой подключен к входу считывания регистра кода числа внешних ребер, информационные входы которого соединены с второй группой входов схемы сравнения и выходами вьиитателя, первая группа входов вычитателя подключена к выходам регистра кода остатка ребер, вторая группа соединена с выходами преобразователя сочетание - код и ин формационными входами регистра кода остатка ребер, буферный регистр индикации, блок регистров индикации и блок управления, включаюш 1й два счетчика, дешифратор, входы которого соединены с выходами второго счетчика, триггер, пять элементов ИЛИ, пять элементов задержки и элемент И отличающееся тем, что с целью упрощения устройства, в состав блока управления введены группа из N элементов И (N - число вершин графа), группа из N счетчиков, шес той элемент ИЛИ, шестой и седьмой элементы задержки и элемент запрета при этом информационные выходы генератора случайных сочетаний соединены с входами блока отображения топологии графа и информационными входами буферного регистра индикации, управляющие выходы генератора случайных сочетаний соединены с входами первого элемента ИЛИ, вьгходы буферного регистра индикации подключены к информационным входам регистров блока индикации и регистра блокировки кода сочетаний, выход первого элемента ИЛИ соединен с первьтми входами элементов И группы блока управления, вторые входы которых подключены к выходам дешифратора и входам разрешения записи регистров блока индикации, выходы элементов И группы блока управления соединены со счетными входами соответствующих счетчиков группы блока управления, выходы которых подключены к входам второго элемента ИЛИ, выход которого соединен с входом первого счетчи ка, входом первого элемента задержки и первым входом третьего элемента ИЛИ, второй вход которого соединен с входом второго элемента задержки и подключен к выходу схемы сравнения и входу разрешения записи буферного регистра индикаций, выход первого счетчика соединен с входом третьего элемента задержки, первым входом элемента И и запрещающим входом элемента запрета, информационный вход которого подключен к выходу второго элемента задержки, выход первого элемента задержки соединен с входом четвертого элемента задержки и первым входом четвертого элемента ИЛИ, выход четвертого элемента задержки подключен к входу пятого элемента задержки и первому входу пятого элемента ИЛИ, второй вход которого соединен с выходом третьего и входом шестого элементов задержки, выход которого соединен с входом второго счетчика и вторым входом элемента И, вьгход пятого элемента задержки подключен к входу седьмого элемента задержки и второму входу четвертого элемента ИЛИ, выходы элемента И и элемента запрета соединены соответственно с первым и вторым входами шестого элемента ИЛИ, выход которого подключен к единичному входу триггера, нулевой вход которого соединен с выходом второго -элемента ИЛИ, выходы третьего и пятого элементов Ш1И, второго элемента задержки и нулевой выход триггера соедине1 1 иы с второй группой управляюцщх входов генератора случайных сочетаний, выход четвертого элемента Hjrf соединен с управляющим входом вычитателя, выход третьего элемента задержки соединен с управляющими входами регист ра блокировки кода сочетаний, регист ра кода остатка ребер, регистра кода числа внешних ребер и регистров блока индикации, выход седьмого элемента задержки подключен к управляющему входу схемы сравнения, вход установки исходного состояния устройства соединен с третьим входом щестого элемента ИЛИ и входами установки в нуль регистра блокировки кода сочетаний, генератора случайных сочетаний, блока отображения топологии гра фа, регистра кода остатка ребер, регистра кода числа внешних ребер, пер вого, второго счетчиков и группы счетчиков блока управления, а информационные входы блока отображения топологии графа являются информационными входами устройства. 2, Устройство по п. 1, отличающееся тем, что генератор случайных сочетаний содержит N каналов, каждый из которых состоит из источника пуассоновского потока импульсов, элемента И, элемента запрета, элемента ИЛИ, триггера и элемента 2И-Ш1И, первые входы элементов И образуют первую группу управляющих входов генератора случайных сочета4112НИИ, вторые входы элементов И соединены с выходами источников пуассоновского потока импульсов, выходы Элементов И i-го канала (i 1, N) подключены к информационным входам элементов запрета i-ro канала и запрещающим входам элементов запрета остальных каналов, выходы элементов запрета соединены с единичными входами триггеров соответствующих каналов и образуют управляющие выходы генератора случайных сочетаний, нулевые входы триггеров каждого канала соединены с выходами соответствующих элементов ИЛИ, первые входы элементов 2И-1-ШИ каждого канала соединены с первыми входами соответствующих элементов И, вторые и третьи входы элементов 2И-Ш1И каждого канала подключены соответственно к нулевым выходам триггеров и третьим входам элементов И и единичным выходам триггеров соответствующих каналов, выходы элементов 2И-РШИ образуют информационные выходы генератора случайных сочетаний, объединенные (по одноименным элементам) четвертые входы элементов И, первые входы элементов lilMy третьи и четвертые входы элементов 2И-ИЛИ образуют вторую группу управляющих входов генератора случайных сочетаний, а объединенные вторые входы элементов ИЛИ являются входом установки в исходное состояние генератора случайных сочетаний.

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

ф1/г.7

-i