5.4. Смешанный алгоритм компоновки

Смешанный алгоритм компоновки основан на идеях итерационного алгоритма, но для него не нужно начального разрезания. Он работает со всей матрицей соединений.

Алгоритм включает следующие шаги.

1. В матрице R выделяется подматрица порядка, равного числу вершин n₁ в G₁. Матрица R при этом разбивается на две подматрицы: R₁ и R₂.

2. По матрице R находится характеристики  (x_i).

3. Строится матрица B.

4. Определяется максимальный элемент b_ij≥0. Если в матрице В нет положительных элементов, по переход к п. 6. Переставляются вершины x_i и x_j. Получена матрица R’.

5. Последовательно выполняются п.п. 2-4 до тех пор, пока окажется для всех пар вершин b_ij0.

6. Из графа G удаляется часть G₁, соответствующая подматрице R₁.

7. Повторяется работа п.п. 1-6 с матрицами R₂, R₃, …, R_k-1.

8. Разбиение получено.

Продемонстрируем работу алгоритма на примере компоновки рис. 5.2.

1. В матрице R выделим подматрицу порядка n₁ = 3 и вычислим  (x_i).

2. Для всех пар вершин разных кусков вычислим b_ij

3. Max b₁₅ = 6. В матрице R переставляем строки и столбцы, соответствующие элементам x₁ и x₅ и пересчитываем  (x_i).

4. Все  (x_i) ≤ 0. Первый кусок сформирован X₁={x₂, x₃, x₅}.

5. Удаляем из графа G подграф G₁.

6. В матрице R’ выделим подматрицу порядка n₂ = 2 и вычислим  (x_i).

7. Для всех пар вершин разных кусков вычислим b_ij

8. Мах b₁₆ = b₄₇ =2. Поменяем местами x₁ и x₆.

9. Все  (x_i) ≤ 0. Сформирован второй кусок X₂={x₄, x₆}. Оставшиеся вершины образуют третий кусок X₃={x₁, x₇}.

Получено разрезание графа G, совпадающее с оптимальным (рис. 5.3 (б)).

6. Алгоритмы размещения элементов

6.1. Постановка задачи

Задачи размещения элементов и трассировки их соединений тесно связаны и при обычных ("ручных") методах конструирования решаются одновременно. В процессе размещения элементов уточняются трассы соединений, после чего положение некоторых элементов может корректироваться. В зависимости от принятой конструктивно - технологической и схемотехнической базы при решении этих задач используются различные критерии и ограничения. В результате получается точное пространственное расположение отдельных элементов конструктивного узла и геометрически определенный способ соединений выводов этих элементов.

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

К метрическим параметрам относятся размеры элементов и расстояния между ними, размеры коммутационного поля, расстояния между выводами элементов, допустимые длины соединений и т.д.

Топологические параметры в основном определяются принятым в конкретной конструкции способом устранения пересечений соединений и относительным расположением соединений на коммутационном поле. К ним относятся: число пространственных пересечений соединений, число межслойных переходов, близость расположения друг к другу тепловыделяющих элементов или несовместимых в электромагнитном отношении элементов и соединений.

В конкретных задачах указанные параметры в различных сочетаниях могут быть либо главными критериями оптимизации, либо выступать в качестве ограничений.

Совместное решение задач размещения и трассировки представляет значительные трудности ввиду сложного характера взаимосвязи между отдельными параметрами конструкции и схем соединений. В связи с этим при алгоритмическом подходе к их решению они рассматриваются, как правило, раздельно. Сначала осуществляется размещение элементов, а затем трассировка межсоединений. Если необходимо, этот процесс может быть повторен при другом расположении отдельных элементов.

Основной целью размещения считают создание наилучших условий для последующей трассировки соединений при удовлетворении основных требований, обеспечивающих работоспособность схем.

В общем виде задачу размещения элементов узла описывают следующим образом.

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

Исходными данными для размещения являются: данные о конфигурации и размерах КП (установка и крепление); количество и размеры элементов; схема соединений; ограничения на установку элементов.

Вариантами КП могут быть панель с проводными соединениями, печатная плата, подложка микросборки, кристалл БИС.

Основная сложность в постановке задачи размещения заключается в выборе целевой функции. Это связано с основной целью размещения, которую нельзя оценить без проведения трассировки. Особенностью критериев, используемых в задаче размещения, является их эвристический характер, т. к. все они косвенно учитывают условия трассировки. Классическим критерием является критерий суммарной длины соединений (СДС), который интегральным образом учитывает многочисленные требования, предъявляемые к расположению элементов и трасс их соединений. Это обуславливается рядом факторов:

• уменьшение длин соединений улучшает электрические параметры схемы;

• чем меньше суммарная длина соединений, тем, в среднем, проще их реализация в процессе трассировки;

• уменьшение суммарной длины соединений снижает трудоемкость изготовления монтажных схем, особенно схем проводного монтажа;

• данный критерий относительно прост с математической точки зрения и позволяет косвенным образом учитывать другие параметры схем путем присвоения весовых оценок отдельным соединениям.

Кроме СДС в САПР нашли применение следующие критерии:

• расстояние между элементами, соединенными наибольшим числом связей;

• число пересечений проводников на КП;

• длина наиболее длинных связей;

• число перегибов проводников;

• число межслойных переходов;

• параметры паразитных связей между элементами и проводниками;

• равномерность распределения температуры по поверхности КП и др.

Всю совокупность алгоритмов размещения можно разделить на следующие основные группы:

1. алгоритмы решения математических задач, являющихся моделями задач размещения;

2. конструктивные алгоритмы начального размещения;

3. итерационные алгоритмы улучшения начального размещения;

4. непрерывно - дискретные методы размещения.

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

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

Характерной особенностью конструктивных алгоритмов является то, что они создают размещение. Итерационные алгоритмы предполагают задание начального размещения.

Конструктивные алгоритмы используют последовательный или параллельно - последовательный процесс установки элементов в позиции при локальной оптимизации функции - критерия размещения.

В итерационных алгоритмах производится переразмещение элементов или их групп с целью минимизации выбранного критерия. Эти алгоритмы требуют существенных затрат машинного времени и используются для получения окончательного размещения.

Основной областью применения непрерывно - дискретных методов размещения являются конструкции, в которых позиции для установки элементов заранее не фиксированы. Исходной базой для построения алгоритмов данной группы являются непрерывные модели и механические аналогии задачи размещения.