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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и позволяет уменьшить , примерно на порядок, время решения задачи компоновки электронных схем. Цель изобретения - повышение быстродействия и упрощение устройства . Оно содержит последовательно соединенные регистр 1 блокировки подграфов , генератор 2 случайн1з1х сочетаний, первый буферный регистр 3, коммутатор СА: Q ел о СО Фиг1

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

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

РЕСПУБЛИК (5у 4 G 06 F 15/20

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

2 395

Фиг 1

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

Н А BTOPCKOMV СВИДЕТЕЛЬСТВУ (21) 3925349/24-24 (22) 08.07.85 (46) 23.04.87. Бюл. У 15 (71) Таганрогский радиотехнический институт им. В.Д.Калмыкова (72) В.M.Глушань, В.И.Курейчик, И.П.Левин и Л.И.Щербаков (53) 681. 333 (088.8) (56) Авторское свидетельство СССР и 656073, кл. G 06 F 15/36, 1979.

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

9 1086434, кл. G 06 F 15/20,. 1983.

„„Я0„„1305703 A 1 (54 ) УСТРОЙСТВО ДЛЯ РАЗБИЕНИЯ ГРАФА

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

СО

CO

С

1 (САР

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 — с входом синfO хронизации записи регистра 3, выходы

15.6 и 15.7 с первым и вторым управляющими входами коммутатора 4, выходы 15.8, 15.9, 15.10, 15.11 — с входами синхронизации записи соответст15 венно регистров 7,8,10 и 12, выход

15.12 — с входом разрешения работы вычитателя 9, выходы 15.13 — с входами разрешения блока 14 регистров индикации, вход 15.14 соединен с вы20 ходом 2.5 генератора 2, входы 17 предназначены для записи информаций о структуре графа.

Преобразователь 6 (на фиг.3 приве2- дена схема преобразователя на пять входов) содержит компандер, состоящий из десяти двухвходовых элементов ИЛИ и И, образующих четыре линейки и соединенных соответствующим образом. В первую линейку входят четыре элемента 18,19,20 и 21, во вторую — три элемента 22,23 и 24, в третью — два элемента 25 и 26 и в четвертую — один элемент 27. Кроме компандера преобра— зователь 6 содержит комбинационную

13057

3 схему, состоящую из элементов 28-31 запрета и элементов ИЛИ 32 и 33, входами соединенных с выходами элементов 28-31.

Блок 15 управления содержит первую

34 и вторую 35 группы элементов И, группу счетчиков 36, выходы которых подключены к первым входам элементов

И второго блока 35, вторые входы которых объединены с вычитающими входа— ми соответствующих счетчиков и соедииены с выходами элементов И первого блока 34, первые входы которых объединены и образуют вход 15. 14 блока, первый 37, второй 38, третий 39 и четвертый 40 триггеры, элемент И 41, 15 входами соединенный с выходами второro 38 и третьего 39 триггеров, с первого по восьмой элементы 42-49 задержки соответственно, соединенные так, что выход каждого из элементов, . кроме последнего 49, соединен с входом предыдущего, а вход первого элемента 42 задержки соединен с выходом

25 элемента И 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.

Принцип работы устройства состоит в следующем.

Разбиение графа С(Х, U), состоящего из /Х/=и вершин и /U/=Ч ребер,на

К подграфов G„= (X„, U „), G = (X, U,), G,= (Х ., U ) с числом вершин в каждом подграфе соответственно /Х,/=

=и„, /Х„/=п,...,/Х /=пк, где и +

+ n „ + ... + n, = n осуществляется за К этапов на каждом z-м этапе производится Q случайных назначений и; вершин i é подграф.

Число случайных назначений (розыгрышей) определяется заданными точ— ностью и достоверностью разбиения графа на подграфы, а все и. вершины в каждом

i назначении выбираются одновременно (параллельно).

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

Так на первом этапе производится

Q случайных назначений вершин в первый подграф. Число внешних связей подсчитывается после каждого назначения между выбранным множеством вершин Х1с- Х (здесь H далее знак .w оз- начает не окончательное, а текущее множество) и оставшимися вершинами

Х1Х . После проведения всех G слу1 чайных назначений будет сформирован

5 13057 первый полиграф С„ =(Х,, U„}, имеющий локально-минимальное число связей с оставшимся множеством вершин Х Х,.

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

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

Х вЂ” Х Х, и оставшимся множеством вершин Х Х, 0 Х

После проведения всех Q случайных назначений будет сформирован второй подграф 4 =(X>, L" ), имеющий локаль— но-минимальное число внешних связей с оставшимся множеством вершины

Х Х, U Х2. Аналогичным образом про— цесс формирования подграфов продолжается до последнего К-го этапа,после которого осавшееся множество вер кшин Х, 0 Х включится в К-й подграф.

1=1

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

В предлагаемом устройстве топология исходного графа задается с помощью блока 5. Случайный выбор заданно.го числа вершин осуществляется с помощью генератора 2 случайных сочетаний. С помощью регистра 1 блокировки подграфов осуществляется блокировка подграфов, сформированных на предыдущих этапах. В блок 14 регистров 40 индикации заносится вариант формирования подграфа (номера вершин), лучший относительно предыдущих вариантов. Блок 6 осуществляет преобразование различных сочетаний на его вхо- 45 дах в соответствующий двоичный код на выходах.

Этот код соответствует числу ребер между вершинами, на которые в блоке 5 формирования топологии графа поданы единичные сигналы.

В регистр 7 заносится общее число ребер исходного графа, с помощью вычитателя 9 регистров 8, 10 и 11 производится определение числа внешних связей каждого из назначений и сравнение этого числа с лучшим из рассмотренных вариантов, Если в данном назначении число внешних связей мень03 ше ранее достигнутого локального минимума, оно запоминается регистром

11, а само назначение — регистром 13.

После выполнения заданного числа назначений в блок 14 заносится лучшее из рассмотренных назначений. Регистры 3,8,10 и 12 обеспечивают возможность параллельной работы наиболее медленно действующих узлов устройства: генератора 2, преобразователя 6, вычитателя 9, регистров 7,8,10,11.

Блоком 15 управления задается число подграфов, число вершин в каждом подграфе и число случайных назначений, а также формируются все управляющие cигнaлы.

Подготовка устройства к работе про;;зводится заданием исходной топологии графа в блоке 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 в регистр

13 записывается новое сочетание, а в регистр 11 — число внешних связей нодграфа. Счетчик 57 осуществляет подсчет рассмотренных сочетаний.Ког3 8 да их число достигнет заданного, по сигналу с его выхода переключится счетчик 58 и дешифратор 59 подаст сигнал записи сочетания из регистра

13 в соответствующий регистр блока

14, подключит к входу 15. 14 вход следующего счетчика блока 36, подаст сигнал записи на управляющий вход регистра 1 и сигнал записи "1" a регистр 11.

Во избежание сбоя сигнал записи

"1" будет подаваться до тех пор, пока минимум одно новое сочетание не пройдет обработку во всех узлах устройства. Затем, аналогично описанному, устройство перейдет к формированию следующего подграфа.

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

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

9 1305703 10!

20

35

45 ния, вход синхронизации записи перво- 50 вятого элемента задержки блока управ- 55 ления, вход синхронизации записи втовходы всех счетчиков блока управления объединены между собой, объединены с первыми входами пятого и шестого элементов ИЛИ, блока управления, с входом девятого элемента задержки блока управления, с входом установки в "0" регистра внешних ребер, с первым входом установки нуля генератора случайных сочетаний, с входом установки в 0" блока регистров индикации и являются входом установки начальных значений устройства, выход второго счетчика блока управления подключен к счетному входу первого счетчика блока управления и к входам разрешения записи регистра блокировки подграфа и регистра внешних ребер, выход первого триггера блока управления подключен к входу блокировки генератора случайных сочетаний, выход первого элемента задержки блока управления подключен к первому входу второго элемента ИЛИ блока управления, к входам установки в "0 второго и третьего триггеров блока управления, к входу установки в "1" четвертого триггера блока управления и к второму входу установки в "0 генератора случайных сочетаний, выход последовательного кода генератора случайных сочетаний подключен к первым входам элементов И первой группы, второй вход каждого i-ro

1,2,...,n ) элемента И первой груп— пы подключен к 1-му выходу группы выходов дешифратора, каждый i — и вы— ход группы выходов дешифратора блока управления подключен к входу раз— решения записи i-го регистра индикации блока, группа выходов параллельного кода генератора случайных сочетаний подключена к группе информационных входов первого буферного регистра, группа выходов которого подключена к группе информационных входов коммутатора, первый и второй уп— равляюшие входы которого подключены соответственно к выходам пятого и шестого элементов ИЛИ блока управлего буферного регистра подключен к выходу элемента И блока управления, вход синхронизации записи регистра остатка ребер подключен к выходу дерого буферного регистра подключен к выходу третьего элемента ИЛИ блока управления, вход синхронизации запи5 !

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

i-ro элемента И первой группы блока управления подключен к вычитаюшему входу i-го счетчика группы блока управления и к первому входу i-го элемента И второй группы блока управления, второй вход которого подключен к выходу 1-го счетчика группы, выход каждого i-го элемента И второй группы подключен к i-му входу первого элемента ИЛИ блока управления, выход которого подключен к входам установки в "1" первого и второго триггеров, вход установки в "0" первого триггера подключен к выходу второго элемента ИЛИ блока управления, второй вход которого объединен с первым вхо— дом седьмого элемента ИЛИ и подключен к выходу девятого элеменra задержки блока управления, выход седьмого эле— мента ИЛИ подключен к входу установки в "1" третьего триггера блока управ1305703!

2 ления, выходы второго и третьего триггеров подключены соответственно к первому и второму входам элемента

И, выход которого подключен к входу первого элемента задержки, выход которого подключен к входу второго эле— мента задержки, выход которого подключен к входу третьего элемента задержки и к первому входу третьего элемента ИЛИ, выход третьего элемен- !О та задержки подключен к входу уста— новки в 0 четвертого триггера, к первому входу четвертого элемента

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

1305703

1305703 оэ ч

Составитель Т.Сапунова

Редактор С.Пекарь Техред А.Кравчук

Корректор Т. Колб

Заказ 1453/47 Тираж 673 Подписное

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

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

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