Материал: Алгоритм парных перестановок для решения задач оптимизации компоновки и размещения элементов РЭС. Муратов А.В., Скоробогатов В.С
11
платы, то конечный результат может быть найден только при совместном решении задач размещения, выбора очередности проведения соединений и трассировки, что практически невозможно уже для схем средней сложности вследствие огромных затрат машинного времени.
Поэтому все применяемые в настоящее время алгоритмы размещения используют промежуточные критерии, которые лишь качественно способствуют решению основной задачи: получению оптимальной трассировки соединений. К таким критериям относятся:
1)минимум суммарной взвешенной длины соединений;
2)минимум числа соединений, длина которых больше заданной;
3)минимум числа пересечений проводников;
4)максимальное число соединений между элементами, находящимися в
соседних позициях либо в позициях, указанных разработчиком; 5) максимум числа цепей простой конфигурации.
Наибольшее распространение в алгоритмах размещения получил первый критерий, что объясняется следующими причинами: уменьшение длин соединений улучшает электрические характеристики устройства, упрощает трассировку печатных проводников и снижает трудоемкость изготовления печатных плат; кроме того, он сравнительно прост в реализации.
В зависимости от конструкции коммутационной платы и способа выполнения соединений расстояние между позициями установки элементов подсчитывается по одной из следующих формул:
d(1) |
|
|
|
|
|
|
|
|
||
|
(x |
i |
x )2 |
(y |
y )2 |
; |
(2.1) |
|||
ij |
|
|
|
|
j |
i |
j |
|
|
|
d(2) |
| x |
i |
|
x | |
| y |
y | ; |
|
(2.2) |
||
ij |
|
|
|
j |
i |
j |
|
|
||
d(3) |
(x |
i |
|
x )t |
(y |
y )t . |
|
(2.3) |
||
ij |
|
|
|
|
j |
i |
j |
|
|
|
где (хi, yi) и (хj, yj) — координаты i-й и j-й позиций коммутационной платы.
Формула (2.1) соответствует проведению проводников по кратчайшему пути между соединяемыми точками. Выражение (2.2) предполагает раскладку проводников по каналам или магистралям, параллельным сторонам платы, что характерно для печатного монтажа с ортогональным рисунком соединений и жгутового монтажа.
Формулу (2.3) применяют при наличии особых требований к максимальной длине отдельных соединений (как правило, t = 2).
При практической реализации алгоритмов размещения часто используют представление конструктивных элементов и позиций на коммутационной плате точками,
12
совпадающими с их геометрическими центрами, а все соединения между элементами приводят к попарно взвешенным связям. Весовые оценки связей учитывают такие харак-
теристики схемы, как число электрических цепей между элементами, теплонагруженность элементов, условия распространения сигналов в цепях и т. д. Широкий класс таких оценок описывается формулой
|
g |
(s)ij x(ρs) , |
|
cij |
f |
(2.4) |
|
s |
1 |
|
|
где fij(s) — вес s-й цепи, связывающей элементы i и j; x( s) — коэффициент учета размера цепи, равный 2/ s; s — число эквипотенциальных выводов s-й цепи; g —
число цепей, связывающих элементы i и j. Величина fij(s) определяет важность s-й цепи с точки зрения минимизации ее длины (при работе алгоритма в первую очередь минимизи-
руются связи с большим весом).
Вобщем виде задача размещения конструктивных элементов на
коммутационной плате формулируется следующим образом. Задано множество конструктивных элементов R == {r1, r2,.…,rn} и множество связей между этими элементами V = {v1,v2, ..., vp}, а также множество установочных мест (позиций) на коммутационной плате T = {t1, t2, ..., tk}. Найти такое отображение множества R на мно-
жестве Т, которое обеспечивает экстремум целевой функции F.
Если критерием качества размещения является минимум суммарной взвешенной длины соединений, то задача состоит в минимизации
n |
n |
|
F |
cijdij, |
(2.5) |
i 1 j 1 |
|
|
Как указывалось ранее, наиболее часто решение задачи ищется именно в такой постановке.
Обычно поле позиций (коммутационная плата) имеет форму прямоугольника Рab = а b с координатами 0 x а и 0 t b. Вся площадь платы разбивается на ряд областей
(позиций), число которых должно быть не меньше числа размещаемых элементов (рис.
2.1).
13
Рис. 2.1
В результате получим фиксированные позиции для установки элементов.
Следует отметить, что перед разбиением поверхности коммутационной платы на позиции из нее, исходя из конструктивных соображений, выделяют области для раз-
мещения выводных контактных зон схемы (разъемов), а также запрещенные области, в
которых не должны помещаться элементы схемы (зоны крепления платы, конструктивные вырезы и т. п.).
Все конструктивные элементы, подлежащие размещению, можно условно разде-
лить на три группы:
1) нефиксированные элементы, местоположение которых на плате заранее не из-
вестно. Пусть таких элементов будет q;
2) граничные элементы, к которым относятся элементы, связанные с разъемами,
осуществляющими электрическую связь с элементами, расположенными на других коммутационных платах. Так как разъемы обычно помещают на внешней стороне коммутационной платы (рис. 2.1), то эти элементы желательно располагать у границы коммутационного поля. Пусть число таких элементов будет h — q;
3) фиксированные элементы, местоположение которых на плате заранее определено (указано разработчиком). Таких элементов будет n — h.
Для рассмотренного случая задачу размещения можно сформулировать следующим образом. Найти такое местоположение элементов на коммутационной плате,
при котором достигается минимум
|
n n |
|
F |
cij[(xi - xj)t + (yi - yj)t] |
(2.6) |
i |
1 j 1 |
|
Оптимизацию размещения осуществляют, как правило, локально из некоторого случайного или интуитивно выбранного первоначального размещения.
14
По принципам реализации известные алгоритмы размещения можно разделить на алгоритмы, использующие непрерывно-дискретные и дискретные методы оптимизации
(рис. 2.2). Эффективность того или иного алгоритма обычно оценивают по результатам решения типовых конструкторских задач.
Рис. 2.2.
Эвристические алгоритмы. Практическая реализация большинства указанных на рис. 2.1 алгоритмов размещения связана со значительными затратами машинного времени и памяти ЭВМ. Поэтому для размещения большого числа конструктивных элементов (n > 100) часто используют эвристические алгоритмы, позволяющие сократить время решения задачи при вполне приемлемом для практики качестве получаемого результата. Кроме того, такие алгоритмы лучше приспособлены для учета конкретных конструкторско-
технологических ограничений. К данной группе алгоритмов относятся итерационные,
последовательные и смешанные, в которых начальное размещение получают с помощью последовательного закрепления элементов в позициях, а улучшение размещения достигается в результате их парных перестановок.
Итерационные алгоритмы имеют структуру, аналогичную итерационным алгоритмам компоновки, рассмотренным в пункте 2.2. В них для улучшения исходного размещения элементов на плате вводят итерационный процесс перестановки местами пар элементов.
В случае минимизации суммарной взвешенной длины соединений формула для расчета изменения значения целевой функции при перестановке местами элементов ri и rj
закрепленных в позициях tj и tg имеет вид /1/
15
k
Fij(f,g) = |
(cip - cjp)(dfh(p) - dgh(p)), |
(2.7) |
p 1
где р и h(p) — порядковый номер и позиция закрепления неподвижного элемента rр. Если Fij(f, g) > 0, то осуществляют перестановку ri, и rj приводящую к уменьшению целевой функции на Fij(f,g), после чего производят поиск и перестановку следующей пары элементов и т. д. Процесс заканчивается получением такого варианта размещения, для которого дальнейшее улучшение за счет парных перестановок элементов невозможно.
Использование описанного направленного перебора сокращает общее число анализируемых вариантов размещения (по сравнению с полным перебором), но приводит к потере гарантии нахождения глобального экстремума целевой функции.
Итерационные алгоритмы позволяют получить локальный экстремум целевой функции, более близкий к глобальному, вследствие учета связей всед размещенных на плате элементов.
Итерационные алгоритмы с групповыми перестановками элементов на практике используются редко ввиду сложности, которая часто не оправдывает достигаемую степень улучшения результата.
Рассмотренный алгоритм можно использовать и для размещения разногабаритных элементов, если их геометрические размеры кратны или близки к кратным. При этом поверхность платы условно покрывается прямоугольной координатной сеткой, линейные размеры ячеек которой равны соответствующим линейным размерам позиций минимальных конструктивных элементов.
Особенности алгоритмов размещения при многоцелевой оптимизации модулей.
Характерной особенностью оптимального конструирования РЭА является трудность установления единого критерия качества, приводящего к действительно оптимальной конструкции. Например, при решении задач размещения элементов на печатных платах нужно не только учесть возможность последующей реализации печатного монтажа в соответствии с применяемой технологией, но и обеспечить нормальный тепловой режим и надежность создаваемой конструкции при минимальных затратах на ее производство и эксплуатацию. Кроме того, часто следует учитывать еще такие показатели качества, как коэффициент заполнения монтажной плоскости, ремонтопригодность и целый ряд специальных требований, связанных с особенностями разрабатываемой аппаратуры. Все