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

13

4, блок 5 формирования топологии графа, преобразователь 6 сочетания в код, регистр 7 остатка ребер, второй буферный регистр 8, входами соединенный с выходами преобразователя 6, а выходами - с соот ветствующими входами вычитателя 9, соединенного с третьим буферным регистром 10, соединенного в свою очередь с регистром 11 внешних ребер, выходами соединенного с соответствующими входами вычитателя 9. Кроме того, устройство содержит последовательно соединенные четвертый буферный регистр 12, пятый буферньш регистр 13 и блок регистров индикации 14, а также блок управле

1

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

Целью изобретения является повышение быстродействия и упрощения устройства. SНа фиг. 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 случайных сочетаний, регистра 3,коммутатора 4, регистров 7 и 8, вычитателя 9, регистров 10,12,13 и блока индикадии 14. Один ит входов блока управления 15 объединен с входами генератора 2 случайных сочетаний, регистра 11 и блока регистров индикации 14, а другой - с выходом генератора 2 случайных сочетаний. 4 ил.

дом сброса регистра 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 (на фиг.З приве- дена схема преобразователя на пять входов) содержит компандер, состоящий из десяти двухвходовых элементов ИЛИ и И, образующих четыре линейки и соединенных соответствующим образом, В

30

35

первую линейку входят четыре элемента 18,19,20 и 21, во вторую - три элемента 22,23 и 24, в третью - два элемента 25 и 26 и в четвертую - один элемент 27. Кроме компандера преобразователь 6 содержит комбинационную

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

Блок 15 управления содержит, первую 34 и вторую 35 группы элементов И, группу счетчиков 36, выходы которых подключены к первым входам элементов И второго блока 35, вторые входы ко- торьгх объединены с вычитающими входами соответствующих счетчиков и соединены с выходами элементов И первого блока 34, первые входы которых объединены и образуют вход 15.14 блока, первый 37, второй 38, третий 39 и четвертый 40 триггеры, элемент И 41, входами соединенный с выходами второго 38 и третьего 39 триггеров, с первого по восьмой элементы 42-49 задержки соответственно, соединенные так, что выход каждого из элементов, - кроме последнего 49, соединен с входом предыдущего, а вход первого элемента 42 задержки соединен с выходом элемента И 41, девятый элемент 50 задержки, второй элемент ШШ 51, первым входом объединенный с установочным входом четвертого 40 и входами

сброса второго 38 и третьего 39 триг- п грышей) определяется заданными точгеров и соединенный с выходом первого элемента 42 задержки, а выходом подключенный к входу сброса первого триггера 37, третий элемент ИЛИ 52, выход которого образует выход 15.9 блока 15 управления, первый вход соединен с выходом второго элемента 43 задержки, а второй - с выходом четвертого элемента 45 задержки и выходом 15.11, четвертый элемент ИЛИ 53, входы которого соединены с выходами третьего 44, пятого 46 и седьмого 48 элементов задержки, а выход соединен с выходом 15.6 блока 15, пя35

40

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

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

ходы которых образуют выходы 15.12 и 15.7 блока 15, одни входы которых соединены соответственно с прямым и инверсным выходами четвертого триггера 40, а другие объединены и соединены с входом 15.1 блока 15-,седьмой элемент ИЛИ 56, выходом соединен- ньй с входом установки в 1 третьего триггера 39, одним входом объединенный с входом второго элемента ИЛИ „ 51 и выходом 15.8 блока 15 и соединенный с выходом девятого элемента 50 задержки, вход которого соединен с входом-15.1 блока 15, первьш счетпа 1-й подграф будет иметь локально-минимальное число внешних связей,Вершины, вошедшие в i-йподграф,блокируются и исключаются из дальнейшего розыгрьш1а . Так на первом этапе производится Q случайных назначений вершин в первый подграф. Число внешних связей подсчитывается после каждого назначения между выбранным множеством вершин Х X (здесь и далее знак .v означает не окончательное, а текущее множество) и оставшимися вершинами . После проведения всех С случайных назначений будет сформирован

чик 57 вычитающим входом соединенный с входом восьмого элемента 49 задержки, второй счетчик 59 суммирующим входом объединенный с выходом 15.2 и соединенный с выходом первого счетчика 57, депшфратор 59, входами соединенный с выходами второго счетчика 58, а выходами - с выходами 15.13 и вторыми входами элементов И первой

группы 34 и первый элемент ИЛИ 60. Генератор 2 случайных сочетаний содержит (фиг.2) генераторы 61 пуас- соновского потока импулъсов, элементы И 62, элементы 63 запрета, триггеры 64, элемент ИЛИ 65 и элемент Ш1И 66.

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

Разбиение графа G(X,U), состоящего из вершин и ребер,на К подграфов G, (X,U,), G2(X,,Uj, ..., G, (X|.., U|) с числом вершин в каждом подграфе соответственно п, , /Х,, ...,/Х,, где п, + + п 2 + ... + П| п, осуществляется за К этапов на каждом i-м этапе производится Q случайных назначений п. вершин подграф.

Число случайных назначений (розы0

5

5

0

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

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

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

51

первый подграф G (X , L ), имеющий локально-минимальное число связей с оставшимся множеством вершин .

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

После проведения всех Q случайны назначений будет сформирован второй подграф Q,,(X2, b j), имеюш;ий локально-минимальное число внешних связей с оставшимся множеством вершины . Аналогичным образом про- цесс формирования подграфов продолжается до последнего К-го этапа,после которого осавшееся множество верК-1 и х-включится в К-й подграф

шин X

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

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

ние различных сочетании на его входах в соответствующий двоичный код на выходах.

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

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

5

0

5

0

5

0

5

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

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

Подготовка устройства к работе производится заданием исходной топологии графа в блоке 5 путем подачи единичных сигналов на соответствующие входы 17, установкой емкостей счетчиков 36, соответствуюш 1х размерностям формируег-вых подграфов, емкости счетчика 57, соответствующей числу назначений, и емкости счетчика 58 J, соответствующей заданному числу подграфов.

Работа устройства (фиг.1) начинается с подачи на вход 16 сигнала установки исходного состояния. По этому сигналу в нулевое состояние устанавливаются регистр 1, блок триггеров генератора 2, регистры блока 14,счетчики 36,57 и 58 и-триггер 37 в блоке 15, регистр 11 устанавливается в единичное состояние. Кроме того, по этому же сигналу на все входы блока 5 подаются единичные сигналы, поэтому в регистр 7 запишется суммарное число ребер, соединяющих все вершины исходного графа.

После этого в генераторе 2 начинают формироваться случайные сочетания, т.е. на заданном числе его выходов, но в случайном сочетании появляются единичные сигналы. Происходит это следующим образом. На выходах источников импульсов (фиг.2) в случайные моменты времени вырабатываются пуас- соновские импульсы.Случайный импульс, появившийся на выходе любого из генераторов 61, проходит через соответствующий 4-входовой элемент И 62 и элемент 63 запрета на один из триггеров 64. Причем, поскольку выход каждого элемента И 62 соединен с прямым входом своего элемента 63 запрета и с инверсными входами всех чужих эле

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

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

Счетчики 36 блока 15 осуществляют подсчет числа пришедших импульсов и в нужный момент подают сигнал переключения на триггер 37, чем осуществляется блокировка всех элементов И генератора 2. Если к этому времени предыдущее случайное сочетание уже обработано на модели графа в блок 5 и преобразователем 6, новое сочетани перепишется в регистр 3 и генератор 2 начнет формирование нового сочетания, а сочетание, записанное в регис тре 3, будет обрабатываться в блоке 5 и преобразователе 6.

Преобразователь 6 предназначен дл преобразования совокупности импульсов, появляющихся на выходах блока 5 в двоичный код для последующей обработки в вычитателе 9. При этом число внешних связей данного подграфа определяется как разность между общим числом связей графа, записанным в регистре 7, числом внутренних связей подграфа и числом внутренних связей остальной части графа. Для этого коммутатор 4 по приходу сигнала с выхода 15.7 блока 15 производит инвертирование кода, подаваемого из регистра 3 на входы блока 5. Регистры 8,10 и 12 позволяют обеспечить параллельную обработку информации в блоке 5, преобразователе 6 и вычитателе 9.

При получении отрицательного результата в вычитателе 9 в регистр 13 записывается новое сочетание, а в регистр 11 - число внешних связей подграфа. Счетчик 57 осуществляет подсчет рассмотренных сочетаний.Ког

да их число достигнет заданного, по сигналу с его выхода переключится счетчик 58 и дешифратор 59 подаст сигнал записи сочетания из регистра 13 в соответствующий регистр блока 14, подключит к входу 15.14 вход следующего счетчика блока 36, подаст сигнал записи на управляющий вход регистра 1 и сигнал записи 1 в регистр 11 .

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

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

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

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

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

,, 5 Q Q g е

5

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

t50570312

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

10

п

Фиг. 2

f

5}

В

1Г)Э- гU5( «5 vrj Sj5

о Л -

VS i5 ifi (fj15

c «to 5

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