Размещение элементов — это задача конструкторского проектирования, заключающаяся в определении местоположения элементов на коммутационном поле (КП) в конструктивном модуле. Местоположение должно быть таким, при котором создаются наилучшие условия для решения последующей задачи трассировки соединений с учетом конструктивно-технологических требований и ограничений.
Следует отметить, что задачи размещения элементов и трассировки соединений тесно связаны и в неавтоматизированных методах конструирования решаются одновременно. Раздельное решение этих задач в ECAD объясняется только сложностью их совместного автоматического решения.
В САПР находят применение следующие критерии размещения:
Можно выделить три типа задач размещения:
1. Размещение однотипных элементов с заранее заданными однотипными установочными местами на КП (под однотипностью понимается, что любой элемент может быть помещен на любое посадочное место).
2. Размещение элементов нескольких разных типов кратных размеров с заранее определенными установочными местами на КП.
3. Размещение разногабаритных элементов, таких как электрорадиоэлементы, компоненты ИС, ГИС и т. п., на КП произвольной конфигурации.
Естественно, что наиболее труден третий тип задач. В этом случае, как правило, синтезируют промежуточные псевдомодули (объединяющие ЭРЭ по группам) с определенными геометрическими посадочными размерами.
Исходной информацией для задач размещения являются: габариты и конфигурация КП, геометрические размеры всех типов размещаемых элементов, ограничения на взаимное расположение отдельных элементов.
При размещении элементы представляются точками, что значительно упрощает решение задачи, к тому же принципиальных трудностей при переходе от точек к элементам нет.
В большинстве случаев основным критерием является суммарная длина соединений (СДС), который косвенно учитывает другие из перечисленных критериев и прост с математической точки зрения.
Расстояние между позициями установки элементов (точками) рассчитывается по одной из следующих формул:
= (1)
(2)
(3)
где (, ), (, ) — координаты -й и -й позиций КП.
Формула (1) соответствует прокладке проводных соединений по кратчайшему пути, формула (2) — проведению проводников по каналам или магистралям, параллельным координатным осям КП, формула (3) используется для уменьшения максимальной длины проводников (показатель степени = 3, 4, 5 выбирается экспериментальным путем).
Задача сводится к тому, чтобы на множестве установочных вакантных мест = {, , ..., } разместить множество элементов схемы = {э1, э2, ... эn}, добиваясь минимизации целевой функции, которая выражает один или несколько критериев размещения. В большинстве случаев минимизируется общая суммарная длина соединений между размещенными элементами
L = (4)
где — число связей между элементами эi и эj (число кратных ребер графа, отображающего схему).
Часто элементы, наиболее связанные между собой, предварительно объединяются в группы. Группа при размещении рассматривается как один элемент, внутренние связи которого не учитываются.
Все известные и доведенные до практической реализации алгоритмы размещения являются приближенными, что оказывается достаточным, так как величины в (4) суть расстояния между центрами элементов (точек), а не истинные длины соединений, которые определяются при дальнейшем решении задачи трассировки.