Устройство для решения задачи размещения

Устройство для решения задачи размещения

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано для автоматизированного построения радиоэлектронной и электронно-вычислительной аппаратуры. Целью изобретения является повышение быстродействия. Устройство содержит генератор тактовых импульсов, регистры сдвига, коммутаторы, блок памяти топологии графа, узел коммутации, группы элементов ИЛИ, группы триггеров, группы элементов И, шифратор, схемы сравнения, буферные регистры, элементы И, триггеры, элементы задержки, элемент НЕ, элементы ИЛИ, блок сложения-вычитания, группы регистров, группы дифференцирующих элементов, блок формирования перестановок, элемент ЗАПРЕТ, вычислитель, сумматор, блок индикации. 5 ил.

Изобретение относится к вычислительной технике и может быть использовано для автоматизированного конструирования радиоэлектронной и электронно-вычислительной аппаратуры. Целью изобретения является повышение быстродействия. На фиг. 1-3 приведена структурная схема устройства; на фиг.4 пример построения коммутатора; на фиг.5 обобщенная структурная схема. Устройство содержит генератор 1 тактовых импульсов (ГТИ), регистр 2 сдвига, коммутатор 3, блок 4 памяти топологии графа, регистр 5 сдвига, узел 6 коммутации, группу 7 элементов ИЛИ, группу 8 триггеров, группу 9 элементов ИЛИ, группу 10 элементов И, группу 11 триггеров, группу 12 элементов И, группу 13 триггеров, группу 14 элементов ИЛИ, группу 15 элементов И, коммутатор 16, шифратор 17, схему 18 сравнения, буферный регистр 19, группу 20 элементов И, буферный регистр 21, регистр 22 сдвига, коммутатор 23, элемент И 24, регистр 25 сдвига, группу 26 элементов И, триггер 27, элемент 28 задержки, элемент НЕ 29, элемент 30 задержки, элемент ИЛИ 31, группу 32 элементов И, элемент ИЛИ 33, блок 34 сложения-вычитания, элемент И 35, схему 36 сравнения, буферный регистр 37, группу 38 регистров, группу 39 регистров, регистр 40 сдвига, регистр 41 сдвига, группу 42 элементов И, группу 43 дифференцирующих элементов, элемент ИЛИ 44, элемент 45 задержки, элемент ИЛИ 46, элемент 47 задержки, группу 48 элементов ИЛИ, элемент ИЛИ 49, регистр 50 сдвига, триггер 51, элемент И 52, группу 53 элементов И, элементы И 54, 55, элемент 56 задержки, элемент ИЛИ 57, блок 58 формирования перестановок, элемент И 59, элемент И 60, элемент ЗАПРЕТ 61, группу 62 регистров, коммутатор 63, вычитатель 64, сумматор 65, группу 66 элементов И, группу 67 элементов ИЛИ, элемент ИЛИ 68, элемент 69 задержки, триггер 70, группу 71 элементов И, элемент И 72, элемент 73 задержки, элемент И 74, элемент ИЛИ 75, элемент ИЛИ 76, буферный регистр 77, схему 78 сравнения, группу 79 регистров, группу 80 элементов И, группу 81 элементов ИЛИ, блок 82 индикации, регистр 83 сдвига, связи 84-88, вход 89 установки исходного состояния устройства, связи 90-109, элемент ИЛИ 110, группу 111 элементов И, элемент ИЛИ 112, группу 113 элементов И, группу 114 дифференцирующих элементов. На фиг.5 показаны блок 115 синхронизации (БС), блок 116 коммутации (БК), блок 117 запоминания матрицы смежности (ВЗМС), блок 118 выбора наилучшего варианта (БВНВ), блок 119 блокировки вершин (ББВ), блок 120 регистрации (БР), блок 121 перестановок (БП), блок 122 вычисления критерия размещения (БВКР). В состав блока 115 синхронизации входят регистр 2 сдвига, ГТИ 1, регистр 22 сдвига, элементы ИЛИ 49 и 75, элементы И 52, 59, 74, 60. В блок 116 коммутации входят коммутаторы 3, 16 и 23, каждый из которых состоит из двух групп элементов И 15, 71, буферный регистр 21, узел 6 коммутации, регистр 5, 25, 50, элементы И 24, 55, 35, группы 26, 12, 53, 10 и 32 элементов И, группы 7, 9, 14, 48 элементов ИЛИ, группы 8, 11 триггеров, элементы 30, 47, 56 задержки, элементы ИЛИ 31, 33, 46, триггер 51. В блок 119 блокировки вершин входят регистры 40, 41 сдвига, группа 42 элементов И, группа 13 триггеров, группа 43 дифференцирующих элементов, элементы 28, 45 задержки, элемент НЕ 29, триггер 27, элементы И 54, ИЛИ 44. В блок 118 выбора наилучшего варианта входят шифратор 17, схемы 18, 36 сравнения, буферные регистры 19, 37, группа 20 элементов И, блок 34 сложения-вычитания. В блок 120 регистрации входят группы 38, 39, 79 регистров, регистр сдвига 83, группа 67 элементов ИЛИ, блок 82 индикации. В блок 122 вычисления критерия размещения входят элементы ИЛИ 57, 68, 76, 110, 112, элементы И 60, 72, элементы 69, 73 задержки, триггер 70, группа 62 регистров, коммутатор 63, вычитатель 64, сумматор 65, буферный регистр 77, схема 78 сравнения, группы 66, 80, 111, 113 элементов И, группа 81 элементов ИЛИ, группа 114 дифференцирующих элементов. Позициями 123-130 обозначены связи. Каждому входу блока памяти топологии графа поставлена в соответствие вершина графа, а каждому выходу ребро между любой парой вершин. Топология исходного графа задается блоком памяти топологии графа таким образом, что при подаче на его входы единичного сигнала он появится на тех выходах, то есть соответствующих им ребрам, соединяющих вершины, на которые были поданы единичные сигналы. Это позволяет в каждом такте работы устройства осуществлять выбор той вершины графа, которая имеет наибольшее (наименьшее) число связей c множеством вершин, выбранных в предыдущем такте. Кроме того, в исходном состоянии с помощью узла коммутации выбирается некоторое число вершин, равное заданному числу подграфов, каждая из которых является базовой в соответствующем подграфе и к которой в процессе работы устройства будут присоединяться дpугие вершины графа. Процесс формирования каждого из подграфов графа заканчивается в тот момент, когда в подграф будет включено заданное число вершин, которые должны быть объединены в один подграф. Формирование всех подграфов графа осуществляется последовательно и после окончания процесса исходный граф будет разбит на заданное число подграфов с локально-минимальным числом связей между ними. Полученный результат разбиения графа на подграфы будет записан в регистры. На следующем шаге оптимизации из рассмотрения исключаются те вершины каждого из подграфов, которые были выбраны на первом шаге оптимизации в качестве вершин, имеющих максимальное число связей с базовой вершиной каждого из подграфов. В качестве новой вершины для каждого из подграфов выбирается следующая по максимальной связности с базовой вершиной. Далее процесс формирования подграфов полностью аналогичен описанному выше. Получив разбиение после второго шага оптимизация происходит сравнение результатов первого и второго шагов, по суммарному числу связей между подграфами графа. В блок запоминания матрицы смежности записываются результаты лучшего из двух полученных разбиений по минимуму указанного критеpия. Далее процесс оптимизации протекают аналогично до тех пор, пока не будет проделано заранее заданное количество различных вариантов разбиения, из которых и будет выбран самый оптимальный по минимуму суммарного числа связей между подграфами. Затем последовательно для каждого из подграфов полученного наилучшего разбиения осуществляется оптимальное размещение вершин в координатной сетке. Оптимизируемым критерием качества L является суммарная длина связей между вершинами в узлы Р координатной сетки. Формализованно суммарная длина связей определяется из выражения L C_ijd_p(i)p(j) где С_ij элемент матрицы смежности С, равный "1", если i-я и j-я вершины смежны, и равен "0" в противном случае; d_p(i)p(j) элемент матрицы расстояний D, равный числу шагов координатной сетке между позициями Р(i) и Р(j) при i j и d_p(i)p(j) 0 при i j; n' число вершин подграфа. Значение величин С_ij матрицы смежности формируются на выходах блока 4 памяти топологии графа аналогично тому, как это делалось при декомпозиции исходного графа. В регистры заносятся двоичные коды позиций: в один регистр записывается двоичный код первой позиции 100.0, во второй регистр двоичный код второй позиции 010.0 и т.д. Величина d_p(i)p(j) определяется с помощью вычитателя как разность двоичных кодов позиций Р(i) и Р(j). Накопление же суммы длин расстояний L осуществляется с помощью коммутатора и сумматора. Перебор всех возможных размещений вершин подграфа в узлах решетки (позициях) осуществляется с помощью блока формирования перестановок (БФП). При этом каждая перестановка соответствует определенному перемещению вершин в узлы координатной сетки. Так, перестановкe 312 соответствует размещение первой вершины подграфа во второй узел (вторую позицию), второй вершины и первую позицию. Единичный сигнал в каждый тактовый момент времени появляется только на одном выходе блока. Последовательность же появления единичных сигналов на всех его выходах определяется каждой новой перестановкой. Так, перестановке 312 соответствует появление единичного сигнала по первому тактовому импульсу на втором выходе БФП (нумерация выходов БФП сверху вниз), по второму тактовому импульсу "1" появляется на третьем выходе БФП и по третьему на первом выходе. Смена перестановок осуществляется подачей сигнала на вход БФП с выхода регистра сдвига, когда закончится анализ смежности каждой вершины подграфа с каждой и произойдет накопление суммарной взвешенной длины связей L при данной перестановке (размещение вершин подграфа в координатной сетке). С помощью регистров сдвига производится распределение импульсов на блок памяти топологии графа и осуществляется последовательный периодический перебор всех вершин подграфа и проверка смежности первой вершины со всеми остальными, второй со всеми остальными вершинами этого же подграфа и т.д. Синхронно с этим БФП для каждой вершины определяет позицию (узел) в соответствии со сформированной перестановкой. После завершения формирования всех возможных перестановок, их обсчета, выбора и запоминания лучшего варианта в регистрах сигналом с выхода БФП осуществляется перевод работы устройства на поиск оптимального размещения вершин следующего подграфа в позиции (узлы) координатной сетки. Процедура осуществляется аналогично описанной выше. Таким образом, производится оптимальное размещение вершин каждого из подграфов исходного графа. Результирующее размещение графа в координатной сетке представляет собой совокупность слабосвязанных локально-оптимально размещенных вершин подграфов. Рассмотрим сначала подготовку устройства и его работу по обобщенной структурной схеме, представленной на фиг.5. Перед началом работы все блоки устройства устанавливаются в исходное состояние. По входу "Уст." в блок 117 вводится информация об исходном графе. При подаче сигнала на вход 89 установки исходного состояния блока 116 на все информационные входы блока 117 поступят единичные сигналы блока 116 и на соответствующих информационных выходах блока 117, в зависимости от конкретной топологии графа, появятся единичные сигналы, поступающие через блок 116 на вход 128 блока 118. Эти сигналы преобразуются в код, используемый в дальнейшем для вычитания кода числа внутренних (между вершинами, входящими в данный подграф) связей каждого из подграфов. В конце решения задачи в этом блоке останется (будет храниться) код минимального числа связей между подграфами графа. На выходе "Т" (транзит) блока 116 устанавливается единичный сигнал, присутствующий до окончания работы устройства в режиме декомпозиции. Каждый тактовый импульс с блока 115 через блок 116 поочередно подключает пару информационных кодов блока 117, т.е. поочередно подает на все пары входов блока 117 единичные потенциалы. В соответствии с этим на информационных выходах блока 117 будет формироваться опpеделенный код, подаваемый через вход 128 на блок 118, который выберет и запомнит пару вершин, соответствующих максимальному коду, т. е. пару сильносвязанных вершин. Эта пара вершин "включается" (заносится) в первый подграф путем перезаписи их номеров через входы 96 из блока 116 в блок 120 по сигналу разрешения из блока 118, поступающему на вход 127 блока 120. Аналогичная процедура повторяется до тех пор, пока в подграф не войдет заданное количество вершин, признаком чего является появление единичного сигнала на входе 94 блока 118, по которому произойдет вычитание кода суммарного числа внутренних ребер сформированного подграфа из кода суммарного числа ребер исходного графа. Аналогичным образом осуществляется формирование следующего подграфа с той лишь разницей, что в его формировании уже не участвует часть вершин, отобранных в первый подграф, что обеспечивается блоком 116. Таким же образом осуществляется формирование последующих подграфов, пока не будут сформированы все подграфы. Признаком этого является появление единичного сигнала на выходе 92 блока 116. По этому сигналу в блоке 118 запомнится код числа, соответствующий наилучшей декомпозиции графа (минимум суммарного числа связей между подграфами), блоке 120 будут храниться номера вершин, вошедших в каждый из подграфов. Этот же сигнал, поступивший на вход 92 блока 119, обеспечивает выбор новой ветви разбиения для того, чтобы процесс разбиения во втором цикле разбиения не пошел по уже проделанному пути. Для этого из блока 119 поступает единичный сигнал на вход 97 блока 118, который блокирует вершину, выбранную в предыдущем варианте разбиения в качестве вершины, имеющей максимальное число связей с базовой для каждого из подграфов. В результате такой блокировки получаем новый вариант разбиения графа, который сравнивается с уже имеющимся вариантом (по единичному сигналу на входе 92 блока 118 с выхода 92 блока 116) и запоминаем лучший из этих вариантов. Таким образом, осуществляется "просмотр" нескольких вариантов разбиения и выбор наилучшего, пока на выходе "П" (переключение) блока 116 не появится единичный сигнал, являющийся сигналом окончания декомпозиции графа и начала размещения элементов каждого из его подграфов. Единичный сигнал на выходе "П" блока 116 обеспечивает установку элементов устройства в исходное состояние, а блок 121 устанавливается в состояние, соответствующее первой перестановке. Очередной тактовый импульс, поступающий с блока 115, возбудит единичный сигнал на его втором выходе. С этого момента начинается подсчет длины связей в блоке 122 между i-й вершиной графа и остальными вершинами первого подграфа. Для этого в блок 122 на вход 106 поступает информация из блока 120 о номерах вершин, включенных в данный подграф, а из блока 117 через блок 116 поступает следующая информация: на вход 101 информация о смежности вершин (наличие хотя бы одной единицы в коде), на входы 99 и 100 "текущие" коды перебора вершин. Если в коде, поступающем на вход 101 блока 122, имеется единичный сигнал, то в блоке 122 из кода номера второй позиции вычитается (по модулю) код номера третьей позиции, а результат вычитания будет суммироваться с предыдущей разностью и накапливаться. Следующий тактовый импульс блока 115 возбудит очередной выход блока 121, и если рассматриваемые вершины смежны, то аналогично будет подсчитано расстояние между ними и просуммировано с уже накопленной суммой (накопление численного значения критерия размещения). При более детальном рассмотрении работы устройства в соответствии с фиг. 1.3 необходимо учесть, что для подготовки устройства к работе выходы переполнения регистров 2 и 22 устанавливаются на тот разряд, который соответствует заданному числу вершин в исходном графе, выход переполнения регистра 25 сдвига устанавливается на тот разряд, который соответствует числу вершин подграфа с максимальной их мощностью, выход переполнения регистра 50 сдвига устанавливается на разряд, соответствующий числу различных вариантов разбиения графа на подграфы, выходы переполнения регистров 5 и 83 устанавливаются на тот разряд, который соответствует числу подграфов, на которое разбивается исходный граф. Блок 4 настраивается на заданную топологию графа, для чего на входы блока 4 подаются соответствующие коды, формируя топологию исходного графа, отображающего заданную схему. Входы блока 4 соответствуют вершинам графа, а выходы ребрам. Число входов и выходов остальных многоразрядных узлов и блоков рассчитывается на максимальное число вершин и ребер в графе и соединяются между собой жестко. Перед началом работы в регистры блока 62 записываются двоичные коды номеров позиций (в первый регистр код 100, во второй 010, в третий 011), регистры 38, 39, 79 устанавливаются в нулевое состояние, триггер 70 устанавливается в единичное состояние, регистры 2, 22, 40, 5, 25, 41, триггеры группы 8, буферные регистры 77 и 19 устанавливаются в нулевое состояние. В буферный регистр 37 записывается код (11.1). Триггеры 11 устанавливаются в единичное состояние, а сбрасываются только триггеры, соответствующие базовым вершинам. Узлом 6 коммутации выходы регистра 5 сдвига в соответствующем порядке подключаются к единичным входам соответствующих триггеров группы 8, обеспечения выбор по одной базовой вершине для каждого подграфа. Порядок подключения К выходов регистра 5 к триггерам группы 8 определяется тем, какие вершины графа должны быть базовыми для соответствующих подграфов и в каком порядке будут формироваться подграфы. Например, если граф с числом вершин, равным 30, необходимо разбить на три подграфа (т.е. К 3), а базовыми вершинами должны быть 5-я, 11-я и 15-я, то последовательно будут формироваться первый подграф с 5-й боковой вершиной, второй подграф с 11-й базовой вершиной и третий подграф с 15-й базовой вершиной. Причем в исходном состоянии единичный потенциал будет только на одном, первом выходе регистра 5 сдвига, т.е. формируется первый подграф и перед началом работы только первый выход регистра 5 сдвига подключен к одному из триггеров группы 8 (в соответствии с примером к пятому триггеру группы 8). При подаче сигнала на вход установки исходного состояния одновременно на все входы блока 4 поступят единичные сигналы и на соответствующих выходах, в зависимости от конкретной топологии графа, появятся единичные сигналы, число которых будет равно общему числу ребер, входящих в данный граф. Это число преобразуется шифратором 17 в соответствующий код и записывается в блок 34 по сигналу, подаваемому на вход "Сложение", т.е. этот код складывается с нулевым кодом блока 34. По окончании формирования очередного подграфа из кода этого числа вычитается код числа внутренних (между вершинами, входящими в данный подграф) связей каждого из подграфов. На выходе триггера 51 устанавливается единичный сигнал, который, поступая на соответствующие входы коммутаторов 3, 16 и 23, осуществляет их включение на передачу информации, поступающей на их входы в прямом, транзитном направлении (для коммутаторов 3 и 16 это передача слева направо, а для коммутатора 23 сверху вниз, согласно фиг. 1). Устройство работает следующим образом. Каждый тактовый импульс, поступая с генератора 1 на регистр 2 сдвига, поочередно подключает каждый его выход через коммутатор 3 к соответствующему входу блока 4, то есть подает поочередно на все вершины графа единичный потенциал. В соответствии с этим в первом такте единичный потенциал будет подан на 5-ю вершину (пятый вход блока 4) как базовую для первого подграфа с 1-го выхода регистра 5 сдвига через узел 6 коммутации, пятый элемент ИЛИ группы 7, взведенный пятый триггер группы 8, пятый элемент ИЛИ группы 9, пятый элемент И группы 10, на входе которого постоянно присутствует единичный потенциал с пятого триггера группы 11, далее, через пятый элемент И группы 12, на вход которого постоянно подается единичный потенциал с пятого триггера группы 13 и, далее, через пятый элемент ИЛИ группы 14 на пятый вход блока 4. Кроме того, в первом такте единичный потенциал будет подан и на первый вход блока 4 с первого выхода регистра 2 сдвига через коммутатор 3, элемент ИЛИ 9 и далее по описанной выше цепочке, только с индексом "1". Поэтому единичный потенциал присутствует на 1-м и 5-м входах блока 4, на соответствующих выходах блока 4 появляются единичные потенциалы, т.е. соответствующих ребрах, которые связывают 1-ю и 5-ю вершины. Число ребер, идентичных 1-й и 5-й вершинам, пройдя через открытые элементы И 15 коммутатора 16, преобразуется шифратором 17 в соответствующий код, который сравнивается с кодом, поступающим на схему 18 сравнения с буферного регистра 19. В первом такте в регистре 19 записан код 000.0. Если код шифратора 17 больше кода регистра 19, то схема 18 сравнения вырабатывает на своем выходе единичный сигнал, по которому код шифратора 17 через элементы И 20 переписывается в буферный регистр 19, а в буферный регистр 21 из регистра 22 через коммутатор 23 переписывается код номера вершины, в данном случае первой вершины (код 000.01). Во втором такте единичный потенциал подается на 5-ю и на 2-ю вершину. Если число ребер, связывающих 2-ю и 5-ю вершины, будет меньше числа ребер, связывающих 1-ю и 5-ю вершины, то на выходе схемы 18 сравнения единичный сигнал не вырабатывается и содержимое регистра 22 и регистра 19 не изменяется. В противном случае сигнал вырабатывается, в буферный регистр 19 переписывается код, соответствующий числу ребер, связывающих 2-ю и 5-ю вершины, а в буферный регистр 21 переписывается код 00.10. Таким образом, последовательно все выходы регистра 2 сдвига оказываются поочередно подключенными к входам блока 4, а в буферный регистр 21 записывается код номера вершины, имеющей с базовой (в примере с 5-й) вершиной наибольшее число ребер. Следующий тактовый импульс сформирует на выходе переполнения регистра 2 сдвига единичный сигнал, который через открытый элемент И 24 продвигает единицу в регистре 25 сдвига и подает сигнал разрешения на элементы И группы 26, так как на другой вход элемента И 24 подается инверсный сигнал с установленного в исходное состояние триггера 27 через элемент 28 задержки и элемент НЕ 29. В результате этого единичный сигнал с того выхода буферного регистра 21, который соответствует вершине, максимальным числом ребер связанной с 5-й вершиной, поступает на соответствующий триггер группы 8 и переводит его в единичное состояние до окончания формирования первого варианта разбиения графа на подграфы. Это означает, что в первый подграф включены уже две вершины: базовая (5-я вершина) и вершина, связанная с ней наибольшим числом ребер. В следующем цикле перебора всех вершин единичный сигнал подается в каждом такте уже на три вершины: постоянно на две выбранную в предыдущем цикле и базовую и поочередно на каждую из всех оставшихся. По окончании этого цикла, аналогично предыдущему циклу, выбирается вершина, имеющая максимальное число ребер с двумя вершинами, выбранными в предыдущем цикле. Процесс формирования первого подграфа окончится, когда в него войдет заданное число вершин. Признаком этого будет появление единичного сигнала на выходе регистра сдвига 25, который поступает на регистр сдвига 5 и продвигает единицу на его второй выход, к которому подключен одиннадцатый триггер группы 8 базовой вершины второго подграфа. Сигнал с выхода регистра 25 поступает через элемент 30 задержки и элемент ИЛИ 31 на входы элементов И группы 32, через элемент ИЛИ 13 (обнуляет) устанавливает в исходное состояние буферный регистр 19, поступает на вход "Вычитание" ("В") блока 34 сложения-вычитания, в котором хранится код суммарного числа связей исходного графа. Из этого кода вычитается код числа связей, соединяющих вершины, выбранные (включенные) в первый подграф. Элемент 30 задержки необходим для того, чтобы успеть произвести описанную выше операцию вычитания прежде, чем произойдет сброс сигналов с входом блока 4, соответствующих вершинам, включенным в первый подграф. При поступлении сигналов на входы элементов И группы 32, на первые входы которых поданы единичные сигналы с триггеров 8, соответствующих вершинам, отобранным в первый подграф, на выходах соответствующих элементов И группы 32 появляется единичный сигнал, который перебрасывает соответствующие триггеры группы 11. Поэтому закрываются соответствующие им элементы И группы 10 и на связанные с этими элементами входы блока 4 через соответствующие открытые элементы И группы 12 и элементы ИЛИ группы 14 единичные сигналы поступать не будут, то есть отобранные в первый подграф вершины блокируются до конца получения первого варианта разбиения и не участвуют в формировании оставшихся подграфов. Так как единичный сигнал присутствует уже на втором выходе регистра 5 сдвига, то он будет подаваться на вторую базовую вершину и аналогично рассмотренному выше формируется второй подграф. После окончания формирования второго подграфа на выходе регистра 25 появится сигнал, который продвигает единицу в регистр 5 на третий выход. По следующему тактовому импульсу начинается формирование третьего подграфа и т.д. до тех пор, пока не будут сформированы все подграфы. Это значит, что каждая вершина графа включена в какой-либо из подграфов, т.е. на выходе каждого из триггеров группы 8 присутствует единица, поэтому появляется сигнал на выходе элемента И 35, который поступает на вход схемы 36 сравнения. Этот сигнал разрешает сравнение кода, записанного в буферном регистре 36 (перед сравнением, после окончания первого разбиения, в нем записан максимально возможный код 11.1), с кодом, находящимся в блоке сложения-вычитания 34 и соответствующим числу связей между подграфами графа. Если код буферного регистра 37 больше кода блока сложения-вычитания 34, то схема 36 сравнения вырабатывает сигнал, по которому код блока сложения-вычитания 34 переписывается в буферный регистр 37, а содержимое регистров группы 38 переписывается в регистры группы 39. Это означает, что запомнилось лучшее из предшествующих разбиений, т.е. какие вершины вошли в какой подграф и число связей между подграфами при таком разбиении. Если же содержимое буферного регистра 37 меньше содержимого блока сложения-вычитания 34, то на выходе схемы сравнения сигнал не появляется и содержимое блоков 37 и 39 не изменится. Группа элементов, в которую входят регистры 40 и 41, группа 42 элементов И, группа 13 триггеров, группа 43 дифференцирующих элементов, элемент ИЛИ 44, триггер 27, элементы 28, 45 задержки и элемент НЕ 29, обеспечивает выбор новой ветви разбиения графа на подграфы с тем, чтобы процесс разбиения на втором цикле разбиения не пошел по уже проделанному пути. Это достигается путем блокировки вершины, которая была выбрана в первом варианте разбиения в качестве вершины, имеющей максимальное число связей с базовой для каждого из подграфов. Это значит, что в начале формирования каждого из подграфов графа в качестве первой вершины, присоединяемой к базовой, будет выбрана другая вершина, имеющая с базовой максимальное число связей, за исключением вершины, которая была выбрана в первом варианте разбиения как максимально связанная, но которая в начале формирования второго варианта заблокирована. По окончании формирования первого варианта разбиения сигнал с элемента И 35 прежде, чем поступать на вход элемента ИЛИ 46 и привести все устройство в исходное состояние перед началом формирования второго варианта разбиения, поступает на вход регистра 4 сдвига и продвигает единицу на его первый выход (верхний по схеме), взводит триггер 27 и через элемент 45 задержки поступает на регистр 40 сдвига, по которому происходит перезапись информации из регистра 41 в регистр 40, но уже в инверсном коде. В регистре 41 по-прежнему остается код 100.0, а в регистре 40 будет код 00.01, который определяет время блокировки перезаписи информации из буферного регистра 21 в триггеры группы 8, так как эта блокировка обеспечивается отсутствием сигнала на входе элемента И 24 через последовательно соединенные триггер 27, элемент 28 задержки и элемент НЕ 29. Сигнал с элемента И 35 через элемент 47 задержки поступает на вход элемента ИЛИ 46, который приводит в исходное состояние регистр 5 сдвига (как описано ранее, записывается код 100.00), сбрасывает триггеры группы 8, через элементы ИЛИ группы 48 сбрасывает триггеры группы 11 и через элемент ИЛИ 49 обнуляет регистры сдвига 2 и 22 и буферный регистр 19. Устройство приведено в исходное состояние и готово к формированию очередного варианта разбиения Второй вариант разбиения начинается по очередному импульсу генератора 1 с выбора вершины, максимально связанной с базовой вершиной первого подграфа. В качестве этой вершины будет выбрана та же вершина, что и в первом разбиении (признак окончания выбора этой вершины сигнал с выхода переполнения регистра сдвига 2), однако, она не будет включена в первый подграф (не будет взведен соответствующий триггер группы 8), так как элемент И 24 по одному из входов будет заблокирован инверсным сигналом с нулевого выхода триггера 27. По этому же сигналу с регистра 2 сдвига продвигается единица на выход переполнения регистра 40 сдвига, в результате чего перебросится триггер 27 и разблокирует элемент И 24, т.е. после выбора следующей вершины (появления импульса на выходе регистра 2 сдвига) она будет включена в подграф. Во время выбора этой вершины выбранная вершина на предыдущем шаге, как максимальным числом связанная с базовой, должна быть заблокирована на входе блока 4, т.е. не должна участвовать в переборе вершин при поиске максимально связанной с базовой во втором варианте разбиения, для того, чтобы она вновь не была выбрана в подграф и процесс разбиения не пошел бы по той же ветви, что и при первом разбиении, т.е. чтобы не повторилось первое разбиение. Блокировка этой вершины осуществляется следующим образом. Перед началом поиска второго варианта разбиения будет включена (взведен триггер 27) только блокировка включения в подграф максимально связанной вершины с базовой, но в переборе она будет принимать участие. Это необходимо для того, чтобы определить, какую именно вершину нужно исключить (заблокировать) из процесса просмотра. Поэтому номер этой вершины будет находиться в буферном регистре 21, а ее код будет подан на входы соответствующих элементов И группы 42, на другие входы которых подается сигнал с триггера 27. Поэтому после окончания первого просмотра по сигналу с выхода переполнения регистра 2 сдвига происходит установка соответствующего триггера в нулевое состояние, таким образом эта вершина не участвует в процессе перебора вершин на втором шаге второго варианта разбиения. После окончания этого шага в буферный регистр 21 записывается код вершины, максимальным числом связей соединенной с базовой, за исключением заблокированной. Однако, код этой вершины не проходит через группу 42 элементов И, так как уже продвинута "единица" на выход переполнения регистра 40 сдвига и, перебросив триггер в нулевое состояние, разблокирует цепь перезаписи в триггеры группы 8 и не дает заблокировать эту вершину на следующий шаг выбора следующей вершины. Поэтому на выходе элемента И 24 появится сигнал, который взводит все триггеры группы 13, разблокировав тем самым заблокированную вершину. Кроме того, по появлении хотя бы одного импульса на выходах элементов И группы 42 сигналом с выхода элемента ИЛИ 44 происходит обнуление буферного регистра 19, для того, чтобы на втором шаге второго варианта разбиения сравнение происходило с кодом 00.0, а не с кодом числа связей заблокированной вершины. В результате получают новый вариант разбиения графа на подграфы, лучший из которых запоминается в регистрах группы 39. По окончании формирования второго варианта разбиения в регистр 41 сдвига будет записана и сдвинута еще одна единица. Инверсный код регистра 41 переписывается в регистр 40 и определяет время блокировки включения вершины в подграф (взведение одного из триггеров группы 8), а также число вершин, которое необходимо блокировать на входе блока 4 (исключить их из просмотра). Таким образом осуществляется выбор новой ветви разбиения и каждое последующее разбиение никогда не повторяет предыдущее, а выбор из них лучшего варианта разбиения по критерию минимума суммарного числа связей между подграфами графа осуществляется по описанному выше принципу схемой сравнения 36. Описанная выше процедура формирования очередного варианта разбиения графа на подграфы и выбор среди них наилучшего будет продолжаться до тех пор, пока на выходе переполнения регистра 50 сдвига не появится сигнал. Число вариантов разбиения определяется содержимым регистра 50. Единичный сигнал с выхода переполнения регистра 50 поступает на триггер 51 установки режима и перебрасывает его из состояния "Транзит" (сигнал "1" на выходе "Т") в состояние "Переключение" (сигнал "1" на выходе "П"). Сигналы "Т" и "П" автоматически переключают устройство в режиме размещения элементов на плоскости последовательно для каждой из частей схемы (каждого подграфа). Нулевой сигнал с выхода "Т" триггера 51 заблокирует пути прохождения сигналов через элемент И 52, элементы И группы 15 управляемого коммутатора 16, элементы И группы 53. Этот же сигнал, поступив на вход элементов И 54 и 55, обеспечит блокировку прохождения сигналов через группу 12 элементов И на входы блока 4. Единичный сигнал с выхода "П" триггера 51 обеспечивает разрешение прохождения сигналов через элементы И группы 71 коммутатора 16 с выходов блока 4 на элемент ИЛИ 57. Аналогично осуществляется коммутация выходов регистров 2 и 22 с входами блока 4 через элементы ИЛИ группы 14 при помощи соответственно коммутаторов 3 и 23, на входы "П" которых поданы единичные сигналы. Кроме того, по единичному сигналу с регистра 50, прошедшему через элементы ИЛИ 46 и 49, осуществляется сброс регистров 2 и 22 и запись единицы соответственно в нулевой и первый разряды, блок 58 формирования перестановок устанавливается в состояние, соответствующее первой формируемой перестановке. Для определенности положим, что осуществляется размещение трех элементов схемы (вершина графа), составляющих первую часть схемы (первый подграф) с момента времени, когда сигнал с выхода переполнения регистра 22 через открытый элемент И 59 установит в блоке 58 перестановку 312 (ей предшествовали перестановки 123, 213, 231 и 321). Очередной тактовый импульс с выхода генератора 1 продвигает единицу на последний выход регистра 2 сдвига и, поступая через элемент И 60 и элемент ЗАПРЕТ 61 на вход блока 58 формирования перестановок, возбудит единичный сигнал на его втором выходе. С этого момента начинается подсчет длины связей между 1-й вершиной графа и остальными двумя вершинами первого подграфа. Поэтому двоичный код 010 с выходов второго регистра группы 62 через коммутатор 63 (верхний выход) в качестве уменьшаемого по сигналу, поступающему на вход вычитателя 64 и сумматора 65 с первого выхода регистра 2 сдвига, перепишется в вычитатель 64, а в сумматор 65 из вычитателя 64 перепишется нулевой код. На первом элементе И группы 66 произойдет совпадение единичных сигналов с регистров 2 и 22 через коммутаторы соответственно 3 и 23, а также с элементов ИЛИ группы 67, через которые поступает информация с регистров группы 39 о номерах вершин, включенных в подграф. В результате совпадения этих трех сигналов на выходе первого (верхнего) элемента И группы 66 появится единичный сигнал, который через элемент ИЛИ 68 и элемент 69 задержки поступит на нулевой вход триггера 70. Вследствие этого коммутатор 63 подключит регистры группы 62 к входам (нижним по схеме) вычитателя 64. Второй тактовый импульс продвинет единицу на второй выход регистра 2 сдвига и возбудит единичный сигнал на 3- м выходе блока 58 формирования перестановок, который через коммутатор 63 подключает третий регистр группы 62 к вычитателю 64. При этом единичный сигнал поступает на первый вход блока 4 с выхода регистра 22 сдвига через коммутатор 23 и элемент ИЛИ 14 и на второй вход блока 4 с выхода регистра 2 сдвига через второй элемент ИЛИ группы 14 (т.е. на 1-ю и 2-ю вершины первого подграфа). Если первая и вторая вершины подграфа смежны, то на первом выходе блока 4 появится единичный сигнал (может возникнуть ситуация, при которой вершины одного подграфа не связаны между собой), который через открытый элемент И 71 группы коммутатора 16, элемент ИЛИ 57 и элемент И 72 поступит на вход вычитателя 64. В результате этого из кода 010 номера второй позиции вычитается (по модулю) код 011 номера третьей позиции и по сигналу с элемента 73 задержки результат вычитания поступит на сумматор 65 и сложится с его содержимым. Третий тактовый импульс передвинет единичное значение на третий выход регистра 2 сдвига и возбудит первый выход блока 58 формирования перестановок. Если первая и третья вершины смежны, то на соответствующем выходе блока 4 появится сигнал, который через элементы И группы 71, ИЛИ 57 и И 72 поступит на вычитатель 64, к которому подключается первый регистр группы 62 и из кода 010 вычитается код 100. Результат вычитания по сигналу с элемента задержки 73 аналогично описанному выше сложится с содержимым сумматора 65. Четвертый тактовый импульс ни один из выходов блока 58 не возбуждает, а лишь подготавливает его к следующему циклу формирования перестановки 312, но появляется на выходе переполнения регистра 2 сдвига