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

(50 4 О 06 Р 15 20 ОПИСАНИЕ ИЗОБРЕТЕНИЯ Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) Авторское свидетельство СССРР 656073, кл. С 06 Р 15/36, 1976.Авторское свидетельство СССРУ 1086434, кл. С 06 Г 15/20, 1982.(54) УСТРОЙСТВО ДЛЯ РАЗБИЕНИЯ ГРАФАНА ПОДГРАФЫ(57) Изобретение относится к области вычислительной техники и может бытьиспользовано при автоматизированномрешении задачи компоновки электронных схем. Целью изобретения являетсяупрощение устройства. Эта цель достигается тем, что в блок управлениявведены группа элементов И, группасчетчиков, элементы ИЛИ, элементы задержки и элемент запрета, а каждыйканал генератора случайных сочетанийсостоит из источника пуассоновскогопотока импульсов, элемента И, элемента запрета, элемента ИЛИ, триггера и элемента 2 И-ИЛИ. 1 з.п, ф-лы,4 ил.Изобретение относится к вычислительной технике и может быть использовано при автоматизированном решении задачи компоновки электронных схем.Цель изобретения - упрощение устройства.На фиг. 1 приведена структурная схема устройства; на фиг, 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.Сущность и принцип работы предлагаемого устройства состоят в следующем. Разбиение графа С = (Х, 11), состоящего из 1 Х = п и вершин и 111= Ч ребер, на 1 подграфов С, = (ХЦ,), С, : (Х Ц,) С = (Х11 о ) с числом вершин в каждом подграфе соответственно 1 Х,1 = и 1 Х,=и о Х 1 = п 1 Где п + п +)+ п = и осуществляется за 2 этапов,На каждом -ом этапе производится 0случайных назначений п; веригин в 1-йподграф. Число случайных назначенийО (розыгрышей) определяется заданными точностью и достоверностью разбиения графа на подграфы, а все и вершин в каждом назначении выбираютсяодновременно (параллельно), Послекаждого случайного назначения определяется число внешних связей, т.е.число связей между вершинами, выбранными в подграф, и всеми оставшимися(не выбранными ни в какой подграф),Если в результате текущего случайного назначения получен вариант подграфа с меньшим числом внешних свя 25зей, чем в предыдущем назначении,то он запоминается. Таким образом,сформированный после -го этапа 1-йподграф имеет локально-минимальноечисло внешних связей. Вершины, вошедшие в 1-й подграф, блокируютсяи исключаются из дальнейшего розыг рьппа,Так, на первом этапе производится Я случайных назначений и, вершин35 в первый подграФ. Число внешних связей подсчитывается послекаждогослучайного назначения между выбранным множеством вершин Х,с Х (здесь идалее знак " над соответствующей бук 40 вой означает не окончательное, а текущее множество) и оставшимися вершинами Х Х После проведения всехслучайных назначений формируетсявторой подграф С = (Х Б 1), имеющий45 локально-минимальное число связей составшимся множеством вершин ХХ 1.На втором этапе формируется второйподграф путем выполнения очереднойсерии из Ц случайных назначений. При50 этом и вершин выбираются случайнымобразом из оставшегося после первогоэтапа множества ХХ, вершин, а числовнешних связей определяется послекаждого случайного назначения междуг55 выбранным множеством вершин Х Ы Хфги оставшимся множеством вершин Х(Х, .ЦХ). После проведения всех Я случайных назначений формируется второй273941 4 связей. Блок 11 индикации преднаэна 55 3 1 подграф О = (Х , П ), имеющий ло 7кально-минимальное число внешних связей с оставшимся множеством вершин Х (Х 1 Х ), Аналогичным образом.процесс формирования подграфов продолжается до последнего 1-го этапа, после которого оставшееся множество:вершин Х,( 0 Х;) включается в .-й1:подграф. Поскольку на каждом этапе формируется подграф с локально-минимальным числом внешних связей, то и суммарное число связей между подграфами также локально-минимально,В предлагаемом устройстве топология исходного графа за ается с помощью блока 3 отображения топологии графа. Случайный выбор заданного числа вершин осуществляется с помощью генератора 2 случайных сочетаний, С помощью регистра 1 блокировки кода сочетаний осуществляется блокировка подграфов, сформированных на предыдуших этапах. В регистр 4 индикации заносится вариант формирования подграфа (номера вершин),лучшии относительно предыдущих вариантов. Преобразователь 6 осуществляет преобразование различных сочетаний единичных сигналов на его входах в соответствующий двоичный код навыходах. Код соответствует числу ребер между вершинами, на которые вблоке 3 отображения топологии графаподаны единичные сигналы. Регистр 7предназначен для хранения в течение каждого этапа формирования подграфав кода остатка ребер, инцидентных вершинам, не включенных к данному этапу ни в один из подграфов. С помодью вычитателя 8 производится подсчет числа внешних связей. Блок 9 сравнения производит после каждого случайного назначения сравнение числавнешних связей, получившихся в результате данного назначения, с числом внешних связей, полученных отлучшего варианта всех предыдущихслучайных назначений, В буферныйрегистр 1 О заносится после сравнения лучшее текущее число внешних чен для визуализации номеров вершин каждого подграфа после оптимального разбиения исходного графа. Блоком 5 управления задается число подграфов,число вершин в каждом подграфе ичисло случайных назначений, а такжеформируются все управляющие сигналы,5 10 15 20 25 30 35 40 45 50 Подготовка устройства к работе производится заданием исходной топологии графа в блок 3 отображения топологии графа путем подачи единичных сигналов на соответствующие входы 13, установкой емкостей счетчиков 30, соответствующих размерностям формируемых подграфов, емкости счетчика 32, соответствующей числу назначений и емкости счетчика 33, соответствующей заданному числу подграфов.Работа устройства (фиг, 1) начинается с подачи на вход 12 сигнала установки исходного состояния, По этому сигналу в нулевое состояние устанавливаются регистр 1, триггеры 18 в генераторе 2 регистры блока 11 индикации, счетчики 30, 32, 33 и триггер 48 в блоке 5 управления, регистр 1 О устанавливается в единичное состояние. Кроме того, по этому же сигналу на все входы блока 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 а 5 0 1520253035404550 55 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 вначале был записан максимальный код, то после первого слу 127394140 чайного назначения он всегда больше кода числа внешних ребер вычитателя 8, Поэтому схема 9 сравнения вырабатывает сигнал (этот сигнал по времени появления является шестым), по 5 которому происходит перепись кода из вычитателя 8 в регистр 10, Этот же сигнал поступает на вход буферного регистра 4 индикации, а через элемент ИЛИ 48 блока 5 - на вход 50 ге О нератора 2, Вследствие этого к регистру 4 подключаются прямые выходы триггеров 19 и в него записывается первый вариант сформированного первого подграфа. 15Затем седьмой импульс, сформированный на выходе элемента 43 задержки, через элементы ИЛИ 17 сбрасывает триггеры 18 и через элементы 46 запрета и ИЛИ 47 триггер 48 в исходное состояние. При этом открываются все элементы И 15 и все устройство готово к формированию нового случайного назначения. Аналогично укаэанному в генераторе 2 формируется второе случайное назначение, в вычитателе 8 определяется число внешних ребер между вторым вариантом первого подграфа и всеми оставшимися вершинами, а схемой 9 сравнения определяется из 30 двух вариантов первого подграфа тот вариант, который имеет меньшее число внешних ребер, Если оказывается, что первый вариант первого подграфа "лучше", то схема 9 сравнения на 35 своем выходе сигнала не вырабатывает и в регистре 4 и регистре 10 остается прежняя информация (в регистре 4 номера вершин первого варианта подграфа, а в регистре 10 число его внешних ребер), Если второй вариант подграфа оказывается "лучше", то на выходе схемы 9 сравнения вырабатывается сигнал, в результате чего в регистр 4 иэ генератора 2 переписыва ются номера вершин второго варианта первого подграфа, а в регистр 10 переписывается из вычитателя 8 число его внешних ребер, Так продолжается до тех пор, пока генератором 2 не 50 сформируется заданное число назначений, Тогда на выходе счетчика 32 появляется единичный сигнал, который открывает элемент И 45 и закрывает элемент 46 запрета и через время, 55 задаваемое элементом 41 задержки, появляется на его выходе. Задержка необходима для того, чтобы последнее назначение успело обработаться в соответствии с указанной последовательностью управляющих импульсов с первого по седьмой.Сигнал с выхода элемента 41 задержки поступает на управляющие входы регистров 1, 7 регистров блока 11 и через элемент ИЛИ 42 на входы верхних элементов И 19, При этом "лучший вариант первого подграфа (т.е. номера соответствующих вершин) из буферного регистра 4 переписываются в первый регистр блока 11 регистров индикации, так как сигнал разрешения с дешифратора 34 поступает на первый регистр блока 11 и в регистр 1 блокировки кода сочетаний, поэтому соответствующие выходы регистра 1 оказываются в нулевом состоянии, а в регистр 10 записывается исходный максимальныи код.Поскольку к этому времени все триггеры 18 установлены единичным сигналом с выхода элемента 43 задержки в исходное состояние (на всех инверсных выходах триггеров 18 находятся единичные сигналы), то к блоку 3 подключены входы генератора 2 или инверсные выходы регистра 1 (фиг. 2). Поэтому в блоке 3 возбуждаются те выходы, которые соответствуют ребрам, связывающим вершины, не вошедшие в первый подграф. Преобразователь 6 преобразует число возбужденных выходов в двоичный код, и он записывается в регистр 7.Сигнал с выхода элемента 41 задержки, задержавшись на элементе 44 задержки записывает единицу в счетчик 33, в результате чего единичный сигнал появляется на втором выходе дешифратора 34 и открывает для приема информации второй счетчик 30. Этот сигнал с выхода элемента 44 задержки через открытый элемент И 45 (на выходе счетчика 32 единичный сигнал еще действует) и элемент ИЛИ 47 устанавливает триггер 48 в исходное (нулевое) состояние, который разблокирует элементы И 15. После этого все устройство готово для формирования второго подграфа.Аналогично указанному формируется "лучший" вариант второго подграфа и номера его вершин записываются во второй регистр блока 11 индикации, а в регистр 1 к номерам вершин первого подграфа добавляются номера вершин второго подграфа. Соответственноэтому уменьшается число инверсных вЫ-,ходов регистра 1, на которых остаются единичные потенциалы, т.е, уменьшается число вершин, не вошедших ни водин из подграфов. Третий подграфуже формируется из этих оставшихсявершин и т,д, до тех пор, пока несформируются все подграфы. Признакомокончания формирования подграфов является появление сигнала на выходесчетчика 33. Формула изобретения15 1, Устройство для разбиения графа на подграфы, содержащее регистр блокировки кода сочетаний, генератор случайных сочетаний, первая группа управляющих входов которого соедине на с инверсными выходами регистра блокировки кода сочетаний, блок отображения топологии графа, регистр кода остатка ребер, преобразователь сочетание - код, входы которого соединены с выходами блока отображения топологии графа, вычитатель, схему сравнения, регистр кода числа внешних ребер, выходы которого соединены с первой группой входов схемы срав- З 0 нения, выход которой подключен к входу считывания регистра кода числа внешних ребер, информационные входы которого соединены с второй группой входов схемы сравнения и вы ходами вычитателя, первая группа входов вычитателя подключена к выходам регистра кода остатка ребер, вторая группа соединена с выходами преобразователя сочетание - код и информационными входами регистра кода остатка ребер, буферный регистр индикации, блок регистров индикации и блок управления, включающий два счетчика, дешифратор, входы которого 45 соединены с выходами второго счетчика, триггер, пять элементов ИЛИ, пять элементов задержки и элемент И, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, в со став блока управления введены группа из Б элементов И (11 - число вершин графа), группа из И счетчиков, шестой элемент ИЛИ, шестой и седьмой элементы задержки и элемент запрета, 55 при этом информационные выходы генератора случайных сочетаний соединены с входами блока отображения топо 1213941 1 Ологии графа и информационными входами буферного регистра индикации,управляющие выходы генергтора случайных сочетаний соединены с входамипервого элемента ИЛИ, выходы буферного регистра индикации подключенык информационным входам регистровблока индикации и регистра блокировки кода сочетаний, выход первого эле.мента ИЛИ соединен с первыми входами элементов И группы блока управления, вторые входы которых подключены к выходам дешифратора и входамразрешения записи регистров блокаиндикации, выходы элементов И группы блока управления соединены сосчетными входами соответствующихсчетчиков группы блока управления,выходы которых подключены к входамвторого элемента ИЛИ, выход которого соединен с входом первого счетчика, входом первого элемента задержкии первым входом третьего элементаИЛИ, второй вход которого соединенс входом второго элемента задержкии подключен к выходу схемы сравнения и входу разрешения записи буферного регистра индикаций, выходпервого счетчика соединен с входомтретьего элемента задержки, первымвходом элемента И и запрещающим входом элемента запрета, информационный вход которого подключен к выходувторого элемента задержки выход первого элемента задержки соединен свходом четвертого элемента задержкии первым входом четвертого элементаИЛИ, выход четвертого элемента задержки подключен к входу пятого элемента задержки и первому входу пятого элемента ИЛИ, второй вход которого соединен с выходом третьего и входом шестого элементов задержки, выход которого соединен с входом второго счетчика и вторым входом элемента И, выход пятого элемента задержки подключен к входу седьмого элемента задержки и второму входу четвертого элемента ИЛИ, выходы элемента И и элемента запрета соединенысоответственно с первым и вторым входами шестого элемента ИЛИ, выход которого подключен к единичному входутриггера, нулевой вход которого соединен с выходом второго элементаИЛИ, выходы третьего и пятого элементов ИЛИ, второго элемента задержки и нулевой выход триггера соедине 1273ны с второй 1 руппой управляющих входов генератора случайных сочетаний, выход четвертого элемента ИЛИ соединен с управляющим входом вычитателя, выход третьего элемента задержки соединен с управляющими входами регистра блокировки кода сочетаний, регистра кода остатка ребер, регистра кода числа внешних ребер и регистров блока индикации, выхОд седьмого элемен та задержки подключен к управляющему входу схемы сравнения, вход установки исходного состояния устройства соединен с третьим входом шестого элемента ИЛИ и входами установки в 15 нуль регистра блокировки кода сочетаний, генератора случайных сочетаний, блока отображения топологии графа, регистра кода остатка ребер, регистра кода числа внешних ребер, пер вого, второго счетчиков и группы счетчиков блока управления, а информационные входы блока отображения топологии графа являются информационными входами устройства, 252, Устройство по п. 1, о т л и ч а ю ш е е с я тем, что генератор случайных сочетаний содержит 11 каналов, каждый из которых состоит из источника пуассоновского потока им- З 0 пульсов, элемента И, элемента запрета, элемента ИЛИ, триггера и элемента 2 И-ИЛИ, первые входы элементов И образуют первую группу управляющих входов генератора случайных сочета 15 941 1 2ний, вторые входы элементов И соединены с выходами источников пуассонов- ского потока импульсов, выходы элементов И 1-го канала (1 = 1, М) подключены к информационным входам элементов запрета -го канала и запрещающим входам элементов запрета остальных каналов, выходы элементов запрета соединены с единичными входами триггеров соответствующих каналов и образуют управлявшие выходы генератора случайных сочетаний, нулевые входы триггеров каждого канала соединены с выходами соответствующих элементов ИЛИ, первые входы элементов 2 И-ИЛИ каждого канала соединены с первыми входами соответствующих элементов И, вторые и третьи входы элементов 2 И-ИЛИ каждого канала подключены соответственно к нулевым выходам триггеров и третьим входам элементов И и единичным выходам триггеров соответствующих каналов, выходы элементов 2 И-ИЛИ образуют информационные выходы генератора случайных сочетаний, объединенные (по одноименным элементам) четвертые входы элементов И, первые входы элементов ИЛИ, третьи и четвертые входы элементов 2 И-ИЛИ образуют вторую группу управляющих входов генератора случайных сочетаний, а объединенные вторые входы элементов ИЛИ являются входом установки в исходное состояние генератора случайных сочетаний.127394 Ют йока У Оиг. 4 Составитель С. НазаровРедактор С. Лисина Техред Л.Сердюкова Корректор Т. Колб Заказ 6478/47 Тираж 671 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская цаб., д, 4/5