--II семестр-- / Лекции1 / Лекция 6

Лекция 6.

Постановка задачи размещения модулей.

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

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

Исходной информацией при решении задач размещения являются:

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

• количество и геометрические размеры конструктивных элементов подлежащих размещению;

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

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

К таким критериям относятся:

1. минимум суммарной взвешенной длины соединений;

2. минимум числа соединений, длина которых больше заданных;

3. минимум числа пересечений проводников;

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

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

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

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

(1)

(2)

(3),

где и – координаты i-ой и j-ой позиции коммутационной платы.

Формула (1) соответствует проведению проводников по кратчайшему пути между соединяемыми точками.

Формула (2) предлагает раскладку проводников параллельным сторонам платы.

Формула (3) – применяется при наличии особых требований к максимальной длине отдельных соединений (как правило, t=2).

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

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

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

(4)

где - вес s-ой цепи, связывающей элементы i и j;

- коэффициент учета размера цепи, равный ;

- число выводов s-ой цепи;

g - число цепей, связывающих элементы i и j.

Величина определяет важность s-ой цепи с точки зрения минимизации ее длины.

Если при решении задач размещения требуется произвести рассредоточение теплонагруженных элементов, то

(5)

где - значение коэффициента взвешенной связности, определяемое из соотношения (4);

- мощность рассеяния i-го и j-го элементов;

- допустимая мощность рассеяния двух рядом стоящих элементов;

- коэффициент, учитывающий теплоотдачу в реальной конструкции.

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

и множество связей между элементами:

,

а также множество установочных мест (позиций) на коммутационной плате . Найти такое отображение множества R на множестве T, которое обеспечивает экстремум целевой функции F.

Если критерием качества размещения является минимум суммарной взвешенной длины соединений, то задача состоит в минимизации:

(6).

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

(рис. 1). В результате получим фиксированные позиции для установки элементов.

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

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

1. нефиксированные элементы, местоположение которых на плате заранее не известно. Пусть таких элементов будет ;

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

3. фиксированные элементы, местоположение которых заранее известно (указано разработчиком). Таких элементов будет

Ограничение на размещение элементов указанных трех групп имеют следующий вид:

где и - это координаты центра левой нижней позиции (рис.1);

и - координаты центра i-го фиксированного элемента.

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

(7)

при для ;

для

для

; для (8)

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

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

Рис.1

Рис.2

33