12. Задача компоновки. Критерии и ограничения, алгоритмы решения.

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

1. число межмодульных связей;

2. число модулей разбиения.

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

2.1 Математическая постановка.

Электрическую схему удобно интерпретировать мультиграфом, тогда задача компоновки формулируется следующим образом: задан граф . Требуется разрезать его на отдельные куски , так, чтобы число ребер соединяющих эти куски было минимальным, то есть минимизировать где - множество ребер соединяющих куски и . При следующих ограничениях:

1. на число кусков разрезания K;

2. на число вершин в каждом из кусков;

3. на число внешних связей каждого куска графа.

2.2 Алгоритмы решения.

Для задач невысокой размерности применение нашли методы целочисленного программирования (метод ветвей и границ). Эти методы дают наиболее точный результат.

Для задач большей размерности эти методы неприемлемы из-за больших затрат времени и памяти ЭВМ, поэтому наибольшее распространение получили эвристические алгоритмы, которые можно разбить на две группы:

1. последовательные алгоритмы;

2. итерационные алгоритмы.

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

Итерационные алгоритмы в зависимости от исходных данных могут быть двух типов.

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

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

13. Задача размещения. Критерии и ограничения, классификация алгоритмов.

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

В общем виде задача размещения формулируется следующим образом. Заданы множество модулей и множество связей между ними , а так же множество установочных мест (позиций) на коммутационной плате . Найти такое отображение множества S на множестве Z, которое обеспечивает экстремум некоторой целевой функции F.

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

• минимум суммарной длины всех соединений платы;

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

• минимизация числа пересечений сигнальных цепей;

• максимум числа цепей простой конфигурации.

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

2. Классификация алгоритмов размещения

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

• непрерывно - дискретные алгоритмы;

• дискретные алгоритмы размещения.

При использовании непрерывно-дискретных алгоритмов задача размещения решается в два этапа: на первом, полагая МКП (монтажно-коммутационное поле) непрерывным, определяют координаты центров элементов, при которых целевая функция имеет экстремальное значение. На втором этапе, полученные значения округляют до целочисленных значений. Для решения задачи размещения в этом случае могут использоваться методы, основанные на решении нелинейной задачи математического программирования, и методы, основанные на решении задачи динамического программирования.

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

Алгоритмы случайного поиска основаны на использовании методов Монте-Карло и относятся к итерационным. На основе датчика случайных чисел получают некоторый вариант размещения, для которого вычисляют целевую функцию, результат запоминают, если значение функции является наилучшим, и так до тех пор, пока не будет найдено устраивающее разработчика решение. Существует несколько модификаций такого типа алгоритмов, в зависимости от датчика случайных номеров позиций.