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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК Р 15 20 ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ИСАНИ БРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВ 9/2485 7. Бюл . У 15гский радиотехническийВ.Д.Калмыковашань, В.М.Курейчик,Л.И.Щербаков(54 ) УСТРОЙСТВО ДЛЯ РАЗБИЕНИЯ ГРАФАНА ПОДГРАФЫ(57) Изобретение относится к вычислительной технике и позволяет уменьшить, примерно на порядок, время решения задачи компоновки электронныхсхем. Цель изобретения - повышениебыстродействия и упрощение устройства. Оно содержит последовательно соединенные регистр 1 блокировки подграфов, генератор 2 случайных сочетаний,первый буферный регистр 3, коммутатор1305703 схем. 4, блок 5 формирования топологии графа, преобразователь 6 сочетания вкод, регистр 7 остатка ребер, второйбуферный регистр 8, входами соединенный с выходами преобразователя 6, авыходами - с соответствующими входами вычитателя 9, соединенного с третьим буферным регистром 10, соединенного в свою очередь с регистром 11внешних ребер, выходами соединенногос соответствующими входами вычитателя 9, Кроме того, устройство содержит последовательно соединенные четвертый буферный регистр 12, пятыйбуферный регистр 13 и блок регистровиндикации 14, а также блок управлеИзобретение относится к вычислительной технике и может быть использовано при автоматизированном решении задачи компоновки электронных Целью изобретения является повышение быстродействия и упрощения устройства.На Фиг. 1 приведена структурная схема устройства; на фиг.2-4 - соответственно функциональные схемы генератора случайных сочетаний, преобразователя код - код и блока управления.Устройство для разбиения графа на подграфы содержит регистр 1 блокировки подграфов, генератор 2 случайных сочетаний (ГСС), содержащий входы 2. 1, соединенные с инверсными выходами регистра 1, входы 2.2, 2.3, 2.4, выходы 2.5 и 2.6, первый буферный регистр 3, коммутатор 4, блок 5 формирования топологии графа, преобразователь 6 непозиционного кода в позиционный, регистр 7 остатка ребер, второй буферный регистр 8, вычитатель 9, третий буферный регистр 10, регистр 11 внешних ребер, четвертый буферный регистр 12, пятый буферный регистр 13, блок 14 регистров индикации, блок 15 управления, который содержит вход 15.1, выходы 15.2-15,13, вход 15.14, вход 16 запуска, соединенный с входом 15,1 блока 15, с вхония 15. Информационные входы регистра 12 соединены с выходами регистра 3, выходы регистра 13 соединены с входами регистра 1. Выходы блока управления 15 соответственно соединены с входами регистра 1, генератора 2 случайных сочетаний, регистра З,коммутатора 4, регистров 7 и 8, вычитателя 9, регистров 10,12, 13 и блока индикации 14. Один из входов блока управления 15 объединен с входами генератора 2 случайных сочетаний, регистра 11 и блока регистров индикации 14, а другой - с выходом генератора 2 случайных сочетаний.ил. дом сброса регистра 1, входом 2.4генератора случайных сочетаний, входом записи "1" во все разряды регистра 11, выход 15.2 блока 15 соединенс входом записи "1" регистра 11 и свходом синхронизации записи регистра1, выходы 15,3 и 15.4 соединены соответственно с входами 2.2 и 2,3 генератора 2, выход 15.5 - с входом син О хронизации записи регистра 3, выходы15.6 и 15.7 с первым и вторым управляющими входами коммутатора 4, выходы 15.8, 15.9, 15.10, 15.11 - с входами синхронизации записи соответст венно регистров 7,8,10 и 12, выход15.12 - с входом разрешения работывычитателя 9, выходы 15.13 - с входами разрешения блока 14 регистровиндикации, вход 15.14 соединен с вы ходом 2,5 генератора 2, входы 17предназначены для записи информацийо структуре графа. Преобразователь 6 (на фиг,З приве дена схема преобразователя на пятьвходов) содержит компандер, состоящийиз десяти двухвходовых элементов ИЛИи И, образующих четыре линейки и соединенных соответствующим образом. Впервую линейку входят четыре элемента 18,19,20 и 21, во вторую - триэлемента 22,23 и 24, в третью - дваэлемента 25 и 26 и в четвертую - одинэлемент 27. Кроме компандера преобразователь 6 содержит комбинационную 3513057 3схему, состоящую из элементов 28-31 запрета и элементов ИЛИ 32 и 33, входами соединенных с выходами элементов 28-31. Блок 15 управления содержит первую 34 и вторую 35 группы элементов И,группу счетчиков 36, выходы которыхподключены к первым входам элементовИ второго блока 35, вторые входы которых объединены с вычитающими входами соответствующих счетчиков и соедииены с выходами элементов И первогоблока 34, первые входы которых объединены и образуют вход 15. 14 блока,первый 37, второй 38, третий 39 ичетвертый 40 триггеры, элемент И 41,15 входами соединенный с выходами второго 38 и третьего 39 триггеров, с первого по восьмой элементы 42-49 задержки соответственно, соединенные так, что выход каждого из элементов, . кроме последнего 49, соединен с входом предыдущего, а вход первого элемента 42 задержки соединен с выходом элемента И 41, девятый элемент 50задержки, второй элемент ИЛИ 51, первым входом объединенный с установочным входом четвертого 40 и входами сброса второго 38 и третьего 39 триг-З 0 ходами третьего 44, пятого 46 и седьмого 48 элементов задержки, а выходсоединен с выходом 15.6 блока 15, пятый 54 и шестой 55 элементы ИЛИ, выходы которых образуют выходы 15.12и 15.7 блока 15, одни входы которыхсоединены соответственно с прямым иинверсным выходами четвертого триггера 40, а другие объединены и соединены с входом 15. 1 блока 15.,седьмой элемент ИЛИ 56, выходом соединенный с входом установки в "1" третьего триггера 39, одним входом объединенный с входом второго элемента ИЛИ5 1 и выходом 15.8 блока 15 и соединенный с выходом девятого элемента50 задержки, вход которого соединенс входом 15.1 блока 15, первый счетгеров и соединенный с выходом первого элемента 42 задержки, а выходом подключенный к входу сброса первого триггера 37, третий элемент ИЛИ 52, выход которого образует выход 15.9 блока 15 управления, первый вход сое 35 динен с выходом второго элемента 43 задержки, а второй - с выходом четвертого элемента 45 задержки и выходом 15.11, четвертый элемент ИЛИ 53, входы которого соединены с вы 03чик 57 вычитающим входом соединенный с входом восьмого элемента 49 задержки, второй счетчик 59 суммирующим входом объединенный с выходом 15.2 и соединенный с выходом первого счетчика 57, дешифратор 59, входами соединенный с выходами второго счетчика 58, а выходами - с выходами 15.13 и вторыми входами элементов И первой группы 34 и первый элемент ИЛИ 60,Генератор 2 случайных сочетаний содержит (фиг.2) генераторы 61 пуассоновского потока импульсов, элементы И 62, элементы 63 запрета, триггеры 64,элемент ИЛИ 65 и элемент ИЛИ 66,Принцип работы устройства состоитв следующем.Разбиение графа С(Х,Щ, состоящего из /Х/=и вершин и /П/=Ч ребер,на К подграфов С=(Х,11), С =(ХЕ 1),, С,= (Х ., П ) с числом вершин в каждом подграфе соответственно /Х,/= =и, /Х/=п 2/Х/=пк, где и + + и++ и, = и, осуществляется за К этапов на каждом -м этапе производится Ц случайных назначений п вершин 1-и подграф.Число случайных назначений (розыгрышей) определяется заданными точностьюи достоверностью разбиения графа на подграфы,а все и вершиныв каждом назначении выбираются одновременно (параллельно).После каждого случайного назначения определяется число внешних связей, т.е число связей между вершинами, выбранными в подграф, и всеми оставшимися (невыбранными ни в какой подграф). Если в результате текущего случайного назначения получен вариант подграфа с меньшим числом внешних связей, чем в предыдущем назначении, то он запоминаеТся, Таким образом, сформированный после 1-го этапа -й подграф будет иметь локально-минимальное число внешних связей, Вершины, вошедшие в -й подграф, блокируются и исключаются из дальнейшего розыгрыша.Так на первом этапе производится Я случайных назначений вершин в первый подграф. Число внешних связей подсчитывается после каждого назначения между выбранным множеством вершин Х с- Х (здесь и далее знак . оз- начает не окончательное, а текущее множество) и оставшимися вершинами ХХ . После проведения всех С случайных назначений будет сформирован5 13057 первый подграф С =(Х Г), имеющий локально-минимальное число связей с оставшимся множеством вершин ХХ,.На втором этапе формируется второй подграф путем выполнения очередной серии из Ч случайных назначений. При этом и вершин выбираются случайным образом из оставшегося после первого этапа множества ХХ., вершин, а число внешних связей определяется 10 после каждого случайного назначения между выбранным множеством вершин ХХХ, и оставшимся множеством вершин ХХ, О ХПосле проведения всех Ц случайных 15 назначений будет сформирован второй подграф 5=(Х, П), имеющий локаль - но-минимальное число внешних связей с оставшимся множеством вершиныХХ, О Х. Аналогичным образом пров 20 цесс Формирования подграфов продолжается до последнего К-го этапа,после которого осавшееся множество вер, К шин Х,0 Х включится в К-й подграф, 25 Поскольку на каждом этапе Формируется подграф с локально-минимальным внешнимчислом связей,тои суммарное число связей между подграфами будет также локально-минимальным.В предлагаемом устройстве топология исходного графа задается с помощью блока 5. Случайный выбор заданно го числа вершин осуществляется с помощью генератора 2 случайных сочетаний, С помощью регистра 1 блокировки подграфов осуществляется блокировка подграфов, сформированных на предыдущих этапах. В блок 14 регистров 40 индикации заносится вариант Формирования подграфа (номера вершин), лучший относительно предыдущих вариантов. Блок 6 осуществляет преобразование различных сочетаний на его вхо дах в соответствующий двоичный кодна выходах.Этот код соответствует числу ребер между вершинами, на которые в блоке 5 формирования топологии графа поданы единичные сигналы.В регистр 7 заносится общее число ребер исходного графа, с помощью вычитателя 9 регистров 8, Ю и 11 производится определение числа внешних связей каждого из назначений и сравнение этого числа с лучшим из рассмотренных вариантов, Если в данном назначении число внешних связей мень 03ше ранее достигнутого локального минимума, оно запоминается регистром 11, а само назначение - регистром 13, После выполнения заданного числа назначений в блок 14 заносится лучшее из рассмотренных назначений, Регистры 3,8,10 и 12 обеспечивают возможность параллельной работы наиболее медленно действующих узлов устройства: генератора 2, преобразователя 6, вычитателя 9, регистров 7,8,10,11.Блоком 15 управления задается число подграфов, число вершин в каждом подграфе и число случайных назначений, а также формируются все управляющие сигналы.Подготовка устройства к работе прозводится заданием исходной топологии графа в блоке 5 путем подачи единичных сигналов на соответствующие входы 17, установкой емкостей счетчиков 36, соответствующих размерностям формируемых подграфов, емкости счетчика 57, соответствующей числу назначений, и емкости счетчика 58, соответствующей заданному числу подграфов. Работа устройства (фиг.1) начинается с подачи на вход 16 сигнала установки исходного состояния. По этомусигналу в нулевое состояние устанавливаются регистр 1, блок триггеровгенератора 2, регистры блока 14,счетчики 36,57 и 58 и триггер 37 в блоке15 регистр 11 устанавливается в единичное состояние. Кроме того, по этому же сигналу на все входы блока 5подаются единичные сигналы, поэтомув регистр 7 запишется суммарное числоребер, соединяющих все вершины исходного графа,После этого в генераторе 2 начинают формироваться случайные сочетания,т,е. на заданном числе его выходов,но в случайном сочетании появляютсяединичные сигналы. Происходит этоследующим образом, На выходах источников импульсов (Фиг,2) в случайныемоменты времени вырабатываются пуассоновские импульсы, Случайный импульс,появившийся на выходе любого из генераторов 61, проходит через соответствующий 4-входовой элемент И 62 и эле. -мент 63 запрета на один из триггеров64. Причем, поскольку выход каждогоэлемента И 62 соединен с прямым входом "своего" элемента 63 запрета и синверсными входами всех "чужих" эле 7 130570 ментов запрета, то случайный импульс, появившийся на выходелюбого из генера. торов 61,первым будет запрещать на время своей длительности прохождение случайных импульсов с других генераторов 61 через все остальные элементы 63 запрета. Это предотвращает слияние нескольких импульсов на выходах элементов запрета в один на выходе элемента ИЛИ 65, 10На прямом выходе того триггера 64, на который прошел случайный импульс, появится единичный потенциал, а нулевой потенциал с его инверсного выхода закроет соответствующий элемент И 62. Это обеспечивает прохождение через элементы И 62 и элементы 63 запрета только одного случайного импульса за период формирования одного случайного сочетания. 20Счетчики 36 блока 15 осуществляют подсчет числа пришедших импульсов и в нужный момент подают сигнал переключения на триггер 37, чем осуществляется блокировка всех элементов И 25 генератора 2. Если к этому времени предыдущее случайное сочетание уже обработано на модели графа в блок 5 и преобразователем 6, новое сочетание перепишется в регистр 3 и генератор 30 2 начнет формирование нового сочетания, а сочетание, записанное в регистре 3, будет обрабатываться в блоке 5 и преобразователе 6.Преобразователь 6 предназначен для преобразования совокупности импульсов, появляющихся на выходах блока 5 в двоичный код для последующей обработки в вычитателе 9. При этом число внешних связей данного подгра фа определяется как разность между общим числом связей графа, записанным в регистре 7, числом внутренних связей подграфа и числом внутренних связей остальной части графа. Для этого коммутатор 4 по приходу сигнала с выхода 15.7 блока 15 производит инвертирование кода, подаваемого из регистра 3 на входы блока 5. Регистры 8, 10 и 12 позволяют обеспечить 0 параллельную обработку информации в блоке 5, преобразователе 6 и вычитателе 9При получении отрицательного результата в вычитателе 9 в регистр 55 13 записывается новое сочетание, а в регистр 11 - число внешних связей нодграфа. Счетчик 57 осуществляет подсчет рассмотренных сочетаний.Ког 3 8да их число достигнет заданного, по сигналу с его выхода переключится счетчик 58 и дешифратор 59 подаст сигнал записи сочетания из регистра 13 в соответствующий регистр блока 14, подключит к входу 15. 14 вход следующего счетчика блока 36, подаст сигнал записи на управляющий вход регистра 1 и сигнал записи "1" в регистр 11.Во избежание сбоя сигнал записи "1" будет подаваться до тех пор, пока минимум одно новое сочетание не пройдет обработку во всех узлах устройства. Затем, аналогично описанному, устройство перейдет к формированию следующего подграфа.Формула изобретенияУстройство для разбиения графа на подграфы, содержащее регистр блокировки подграфов, генератор случайных сочетаний, блок формирования топологии графа, преобразователь непозиционного кода в позиционный, регистр остатка ребер, регистр внешних ребер, коммутатор, вычитатель, первый буферный регистр, блок регистров индикации и блок управления, содержащий первый элемент ИЛИ, первый и второй счетчики, дешифратор, первый триггер, первый, второй, третий, четвертый и пятый элементы задержки, второй, третий и четвертый элементы ИЛИ и элемент И, причем в блоке управления группа выходов первого счетчика подключена к группе входов дешифратора, кроме этого, в устройстве группа выходов регистра блокировки подграфов подключена соответственно к группе и входов запуска генератора случайных сочетаний, группа выходов блока формирования топологии графа подключена к группе входов преобразователя непозиционного кода в позиционный, группа выходов регистра остатка ребер подключена к первой группе информационных входов вычитателя, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия и упрощения устройства, в него введены четыре буферных регистра, а в блок управления введены первая и вторая группы элементов И, группа счетчиков, второй, третий и четвертый триггеры, шестой, седьмой, восьмой и девятый элементы задержки, пятый, шестой и седьмой элементы ИЛИ, установочные10 20 25 30 40 45 ния, вход синхронизации записи перво вятого элемента задержки блока управления, вход синхронизации записи втовходы всех счетчиков блока управления объединены между собой, объединены с первыми входами пятого и шестого элементов ИЛИ, блока управления,с входом девятого элемента задержкиблока управления, с входом установкив "О" регистра внешних ребер, с первым входом установки нуля генератора случайных сочетаний, с входомустановки в О блока регистров индикации и являются входом установкиначальных значений устройства, выходвторого счетчика блока управленияподключен к счетному входу первогосчетчика блока управления и к входам разрешения записи регистра блокировки подграфа и регистра внешних ребер,выход первого триггера блока управления подключен к входу блокировки генератора случайных сочетаний, выходпервого элемента задержки блока управления подключен к первому входувторого элемента ИЛИ блока управления, к входам установки в "О второго и третьего триггеров блока управления, к входу установки в "1" четвертого триггера блока управления ик второму входу установки в "О 1 генератора случайных сочетаний, выходпоследовательного кода генератораслучайных сочетаний подключен к первым входам элементов И первой группы, второй вход каждого 1-го 1,2п ) элемента И первой груп -пы подключен к -му выходу группывыходов дешифратора, каждый д - й вы -ход группы выходов дешифратора блока управления подключен к входу разрешения записи 1-го регистра индикации блока, группа выходов параллельного кода генератора случайных сочетаний подключена к группе информационных входов первого буферного регистра, группа выходов которого подключена к группе информационных входов коммутатора, первый и второй управляющие входы которого подключенысоответственно к выходам пятого ишестого элементов ИЛИ блока управлего буферного регистра подключен квыходу элемента И блока управления,вход синхронизации записи регистраостатка ребер подключен к выходу дерого буферного регистра подключен квыходу третьего элемента ИЛИ блокауправления, вход синхронизации запи 5 5 си третьего буферного регистра подключен к выходу шестого элемента задержки блока управления, вход синхронизации записи четвертого буферного регистра подключен к выходу четвертого элемента задержки блока управления, вход разрешения работы вычитателя подключен к выходу четвертого элемента ИЛИ блока управления, выход окончания работы вычитателя подключен к входу синхронизации записи пятого буферного регистра и к входу синхронизации записи регистра внешних ребер, группа выходов преобразователя непозиционного кода в позиционный подключена к группе информационных входов регистра остатка ребер, группа выходов которого подключена к второй группе информационных входов вычитателя, третья группа информационных входов подключена к группе выходов регистров внешних ребер, группа выходов вычитателя подключена к группе информационных входов третьего буферного регистра, группа выходов которого подключена кгруппе информационных входов регистра внешних ребер, группа выходов первого буферного регистра подключена к группе информационных входов четвертого буферного регистра, группа выходов которого подключена к группе информационных входов пятого буферного регистра, группа выходов которого подключена к группе информационных входов регистра блокировки и к группе информационных входов блока регистров индикации, выход каждого 1-го элемента И первой группы блока управления подключен к вычитаюшему входу -го счетчика группы блока управления и к первому входу ь-го элемента И второй группы блока управления, второй вход которого подключен к выходу х-го счетчика группы, выход каждого -го элемента И второй группы подключен к х-му входу первого элемента ИЛИ блока управления, выход которого подключен к входам установки в "1" первого и второго триггеров, вход установки в "О" первого триггера подключен к выходу второго элемента ИЛИ блока управления, второйвход которого ооъединен с первым входом седьмого элемента ИЛИ и подключенк выходу девятого элемента задержкиблока управления, выход седьмого элемента ИЛИ подключен к входу установкив "1" третьего триггера блока управ 1305703 2ления, выходы второго и третьеготриггеров подключены соответственнок первому и второму входам элементаИ, выход которого подключен к входупервого элемента задержки, выход которого подключен к входу второго элемента задержки, выход которого подключен к входу третьего элемента задержки и к первому входу третьегоэлемента ИЛИ, выход третьего элемен- Ота задержки подключен к входу установки в 0 четвертого триггера, кпервому входу четвертого элементаИЛИ и к входу четвертого элемента задержки, выход которого подключен к второму входу третьего элемента ИЛИ и к входу пятого элементазадержки, прямой выход четвертоготриггера подключен к второму входупятого элемента ИЛИ, инверсный выходчетвертого триггера подключен к второму входу шестого элемента ИЛИ, выход пятого элемента задержки подключен к вторым входам четвертого иседьмого элементов ИЛИ и к входу шестого элемента задержки, выход которого подключен к входу седьмого элемента задержки, выход которого подключен к третьему входу четвертого элемента ИЛИ и к входу восьмого элемента задержки, выход которого подключен к счетному входу второго счетчика.1 ЗО 57 ОЗ Составитель Т.СапуноваРедактор С.Пекарь Техред А,Кравчук орректор Т. Кол Заказ 1453/ 7 Тираж 673 ПодписВНЯПИ Государственного комитета СССРпо делам изобретений и открытий3035, Москва, Ж, Раушская наб д.4 изводственно-полиграфическое предприятие, г.ужгород, ул.Про