Основное назначение лекции - показать работу алгоритмов размещения элементов электрических схем на конкретных примерах для лучшего усвоения материала.
20.1. Общая постановка задачи
Задачи размещения элементов и трассировки их соединений тесно связаны и при обычных, "ручных", методах конструирования решаются одновременно. В процессе размещения элементов уточняются трассы соединений, после чего положение некоторых элементов может корректироваться. В зависимости от принятой конструктивно - технологической и схемотехнической базы при решении этих задач используются различные критерии и ограничения. Однако все конкретные разновидности упомянутых задач связаны с проблемой оптимизации схем соединений. В результате получается точное пространственное расположение отдельных элементов конструктивного узла и геометрически определённый способ соединений выводов этих элементов.
Конструкции узлов современных электронных устройств - в значительной степени унифицированные единицы. Основным элементом является коммутационная часть, определяющая конструктивно - технологический способ реализации соединений.
Критерии качества и ограничения, связанные с конкретными задачами размещения и трассировки, опираются на конкретные конструктивные и технологические особенности реализации коммутационной части узла. Всю совокупность критериев и ограничений можно разделить на две группы в соответствии с метрическими и топологическими параметрами конструкции узлов и схем.
К метрическим параметрам относятся размеры элементов и расстояния между ними, размеры коммутационного поля, расстояния между выводами элементов, допустимые длины соединений и т.д.
Топологические параметры в основном определяются принятым в конкретной конструкции способом устранения пересечений соединений и относительным расположением соединений на коммутационном поле. К ним относятся: число пространственных пересечений соединений, число межслойных переходов, близость расположения друг к другу тепловыделяющих элементов или несовместимых в электромагнитном отношении элементов и соединений.
В конкретных задачах указанные параметры в различных сочетаниях могут быть либо главными критериями оптимизации, либо выступать в качестве ограничений.
Совместное решение задач размещения и трассировки представляет значительные трудности ввиду сложного характера взаимосвязи между отдельными параметрами конструкции и схем соединений. В связи с этим при алгоритмическом подходе к их решению они рассматриваются, как правило, раздельно. Сначала осуществляется размещение элементов, а затем трассировка межсоединений. Если необходимо, этот процесс может быть повторен при другом расположении отдельных элементов.
Основной целью размещения считают создание наилучших условий для последующей трассировки соединений при удовлетворении основных требований, обеспечивающих работоспособность схем.
В общем виде задачи размещения элементов узла описывают следующим образом.
Дано множество конструктивных элементов, связанных между собой в соответствии с принципиальной электрической схемой узла. Требуется разместить элементы на некотором плоском коммутационном поле (КП) таким образом, чтобы некоторый функционал достигал экстремального значения.
Вариантами КП могут быть: панель с проводными соединениями, печатная плата, подложка микросборки, кристалл БИС.
При конструктивно однотипных элементах позиции для их установки на КП фиксированы, расположены в узлах прямоугольной решётки и могут быть описаны следующей системой параметров: $$n _{x }, n _{y }, h _{x }, h _{y }$$, где
$$n _{x }$$ - число позиций в горизонтальном ряду;
$$n _{x }$$ - число позиций в вертикальном ряду;
$$h _{x }$$ - горизонтальный шаг между позициями ;
$$h _{y }$$ - вертикальный шаг между позициями.
Возможные конструктивные особенности КП, связанные с расположением контактов элементов и внешних выводов узла, могут быть определены дополнительным набором параметров: координатами контактных площадок относительно центров позиции $$(x _{b }, y _{b})$$ и т.д.
При конструировании печатных плат с разногабаритными навесными элементами, подложек гибридных ИС, а также топологии твердотельных ИС и БИС с одним слоем коммутации позиции для размещения элементов заранее не фиксированы и окончательно определяются после трассировки соединений. Характерной особенностью задач размещения в этих конструкциях является необходимость учёта разногабаритности отдельных элементов, требований минимизации суммарной площади, занимаемой схемой, и ограничений по числу внутренних пересечений.
Раздельное решение задач размещения и трассировки приводит, как правило, к неудовлетворительным результатам. Конструирование топологии таких схем обычными методами сводится к методу "проб и ошибок", а автоматизация этого процесса основана на использовании методов топологического анализа схем и интерактивных систем графического взаимодействия конструктора с ЭВМ.
Последовательное решение задач размещения и трассировки, учитывая сложность их совместного решения, оправдано в конструкциях с высокой степенью унификации размеров элементов и соединений. Примерами являются следующие конструкции: узлы, состоящие из микросхем, соединённых с помощью двусторонних или многослойных печатных плат; панели с проводным и печатным монтажом, объединяющие конструктивно унифицированные узлы низшего уровня. Для таких конструкций обычно удаётся выделить главный критерий при оптимизации размещения, учитывая остальные параметры в виде набора дополнительных ограничений.
Критерием в большинстве случаев является критерий минимума взвешенной длины (МСВД) соединений, который интегральным образом учитывает многочисленные требования, предъявляемые к расположению элементов и трасс их соединений. Это обуславливается рядом факторов:
уменьшение длин соединений улучшает электрические параметры схемы;
чем меньше суммарная длина соединений, тем, в среднем, проще их реализация в процессе трассировки;
уменьшение суммарной длины соединений снижает трудоёмкость изготовления монтажных схем, особенно схем проводного монтажа;
данный критерий относительно прост с математической точки зрения и позволяет косвенным образом учитывать другие параметры схем путем присвоения весовых оценок отдельным соединениям.
20.2. Общая характеристика алгоритмов размещения
Задача размещения элементов является одной из основных задач конструкторского этапа проектирования электронных устройств и состоит в определении оптимального пространственного расположения элементов на коммутационном поле. В качестве критериев оптимальности размещения могут быть приняты различные характеристики схемы соединений элементов или конструкции узла в целом. В большинстве случаев выбирается один главный критерий, в наилучшей степени учитывающий многочисленные конструктивные и технологические требования. Классическим критерием является критерий минимума суммарной длины соединений (МСД). Однако для определённого класса конструкций печатных плат и интегральных схем первостепенными могут стать такие критерии, как число пересечений соединений, число слоёв коммутации и т.д.
Всю совокупность алгоритмов размещения можно разделить на следующие основные группы:
алгоритмы решения математических задач, являющихся моделями задачи размещения;
конструктивные алгоритмы начального размещения;
итерационные алгоритмы улучшения начального варианта размещения;
непрерывно - дискретные методы размещения.
К первой группе относится, прежде всего, метод ветвей и границ для задачи квадратичного назначения, к которой при определённых упрощениях сводится задача размещения: набор позиций считается фиксированным, элементы рассматриваются как геометрические точки, схема соединений представляется взвешенным графом соединений.
Другой класс моделей связан с оптимизацией размещения на непрерывной плоскости, когда набор позиций для установки заранее не фиксирован.
Третья и четвёртая группы включают приближённые алгоритмы, в основном предназначенные для оптимизации размещения элементов в фиксированном наборе позиций.
Характерной особенностью конструктивных алгоритмов является то, что они создают размещение. Итерационные алгоритмы предполагают задание начального размещения.
Конструктивные алгоритмы используют последовательный или параллельно - последовательный процесс установки элементов в позиции при локальной оптимизации функции - критерия размещения.
В итерационных алгоритмах производится переразмещение элементов или их групп с целью минимизации выбранного критерия. Эти алгоритмы требуют существенных затрат машинного времени и используются для получения окончательного размещения.
Основной областью применения непрерывно - дискретных методов размещения являются конструкции, в которых позиции для установки элементов заранее не фиксированы. Исходной базой для построения алгоритмов данной группы являются непрерывные модели и механические аналогии задачи размещения.
20.3. М М задачи размещения. Модель квадратичного назначения
Пусть, даны элементы $$е_{1 }, е_{2 }, … е _{n }$$ и для каждой пары элементов заданы весовые коэффициенты $$r _{i j }( i, j = 1, 2 , ..., n ),$$ определяющие " степень связи " элементов друг с другом.
Таким образом, считаем, что схема задана матрицей соединений
$$R = || r _{i j} || _{n x n }.$$
Пусть, имеется некоторый фиксированный набор позиций для размещения элементов $$р_{1 }, р_{2 }, … , р _{m } ( m \ge n )$$. В дальнейшем будем полагать, что $$m = n$$.
Если $$m > n,$$ можно ввести $$(m - n)$$ фиктивных элементов, не имеющих соединений с остальными элементами $$r _{i j} = 0; i = n + 1 ... m; j = 1, 2, ... , m $$.
Определим расстояние $$d _{i j}$$ между парами позиций.
Для этого воспользуемся дополнительной информацией. Пусть, на коммутационном поле фиксированы позиции для размещения элементов.
Для них можно задать матрицу расстояний
$$D = || d _{i j} || _{n x m} ,$$
в которой элемент $$d _{i j }$$ равен расстоянию между центрами позиций $$p (i)$$ и $$p (j)$$. Матрица $$D$$ - симметричная, с нулевой главной диагональю $$(d _{i j} = 0, i = 1, 2, ... , n)$$.
Рассмотрим такой фиксированный набор позиций (рис. 20.1):
(рис 20.1) Фиксированный набор позицийДля такого набора позиций имеем :
$$D =
\begin{array}{cccccccccccccc}
123456789101112\\
\begin{array}{c}1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 12\end{array}
\left \|
\begin{array}{c}0 \\ 1 \\ 2 \\ 3 \\ 1 \\ 2 \\ 3 \\ 4 \\ 2 \\ 3 \\ 4 \\ 5\end{array}
\begin{array}{c}1 \\ 0 \\ 1 \\ 2 \\ 2 \\ 1 \\ 2 \\ 3 \\ 3 \\ 2 \\ 3 \\ 4\end{array}
\begin{array}{c}2 \\ 1 \\ 0 \\ 1 \\ 3 \\ 2 \\ 1 \\ 2 \\ 4 \\ 3 \\ 2 \\ 3\end{array}
\begin{array}{c}3 \\ 2 \\ 1 \\ 0 \\ 4 \\ 3 \\ 2 \\ 1 \\ 5 \\ 4 \\ 3 \\ 2\end{array}
\begin{array}{c}1 \\ 2 \\ 3 \\ 4 \\ 0 \\ 1 \\ 2 \\ 3 \\ 1 \\ 2 \\ 3 \\ 4\end{array}
\begin{array}{c}2 \\ 1 \\ 2 \\ 3 \\ 1 \\ 0 \\ 1 \\ 2 \\ 2 \\ 1 \\ 2 \\ 3\end{array}
\begin{array}{c}3 \\ 2 \\ 1 \\ 2 \\ 2 \\ 1 \\ 0 \\ 1 \\ 3 \\ 2 \\ 1 \\ 2\end{array}
\begin{array}{c}4 \\ 3 \\ 2 \\ 1 \\ 3 \\ 2 \\ 1 \\ 0 \\ 4 \\ 3 \\ 2 \\ 1\end{array}
\begin{array}{c}2 \\ 3 \\ 4 \\ 5 \\ 1 \\ 2 \\ 3 \\ 4 \\ 0 \\ 1 \\ 2 \\ 3\end{array}
\begin{array}{c}3 \\ 2 \\ 3 \\ 4 \\ 2 \\ 1 \\ 2 \\ 3 \\ 1 \\ 0 \\ 1 \\ 2\end{array}
\begin{array}{c}4 \\ 3 \\ 2 \\ 3 \\ 3 \\ 2 \\ 1 \\ 2 \\ 2 \\ 1 \\ 0 \\ 1\end{array}
\begin{array}{c}5 \\ 4 \\ 3 \\ 2 \\ 4 \\ 3 \\ 2 \\ 1 \\ 3 \\ 2 \\ 1 \\ 0\end{array}
\left \|
\begin{array}{c} \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \end{array}
\end{array}$$
Для вычисления элементов матрицы $$D$$ использована ортогональная метрика,
причём расстояние между соседними позициями по вертикали и горизонтали равно 1.
Произвольное размещение элементов в позициях представляет собой некоторую перестановку $$р = р ( 1 ), … р ( n )$$, где $$n ( i )$$ задает номер позиции, присвоенной $$i$$ - тому элементу.
Таким образом, имеется всего $$n$$! различных вариантов размещения элементов.
Попытки найти оптимальный вариант полным перебором безуспешны даже при малых значениях $$n$$.
Рассмотрим задачу минимизации суммарной взвешенной длины (МСВД) соединений при следующих предположениях.
Соединения считаем условно исходящими из геометрических центров элементов.
Кроме того, предполагаем совпадение центров элементов и позиций.
Как правило, при решении задачи размещения необходимо учитывать предварительное закрепление некоторых элементов в позициях и
соединения элементов с внешними выводами. Сопоставляя внешним выводам элемент $$е_{0}$$ и фиксируя расположение части элементов, получим упрощенное представление коммутационного поля (рис. 20.2).
Очевидно, что длина соединений между элементами $$е_{i}$$ и $$e_{j}$$ оценивается величиной
$$L _{i j } = r _{i j }d _{p ( i ) p ( j ) }.$$
(рис 20.2) Представление коммутационного поляОбозначим через $$E_{S}$$ множество всех фиксированных элементов, включая элемент $$е_{0}$$ ; тогда суммарная взвешенная длина соединений элемента $$е_{i}$$ с элементами из $$E_{S}$$ оценивается по формуле:
$$a _{i p ( i )} = \sum\limits_{S\in E_S}{r_{is}d_{p(i)S}}$$
где $$d _{p ( i ) S}$$ - расстояние между элементом $$е_{i},$$
находящимся в позиции $$p ( i )$$, и элементом $$е_{S}$$.
Учитывая вышесказанное, а также симметричность матриц $$R$$ и $$D$$, запишем выражение для суммарной вешенной длины соединений при произвольном размещении:
$$F ( p ) = \cfrac{1}{2}\sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{n}{ r _{ij }d_{p(i)p(j) }}} +
\sum\limits_{i=1}^{n}{ a_{i p ( i ) }}$$
Таким образом, задача размещения по критерию МСВД соединений состоит в минимизации функционала (19.5) на множестве перестановок Р.
Данная задача является вариантом общей математической модели, получившей название задачи квадратичного назначения.
20.4. Алгоритмы последовательного размещения элементов по связности
Исходной информацией для размещения элементов является:
схема соединений;
параметры конструкции элементов и коммутационного поля.
Прежде всего, рассмотрим наиболее представительные алгоритмы, использующие последовательный процесс установки элементов в позиции.
Пусть, $$Е = \{ e_{1} , e_{2} , ... , e_{n} \}$$ - множество элементов, подлежащих размещению, а $$Р = \{ р_{1} , р_{2} , … , р_{n} \}$$ - множество позиций для их установки.
Вводится $$n$$ - шаговый процесс принятия решений, на каждом шаге которого выбирается один из
неразмещённых элементов и помещается в одну из незанятых позиций.
Структура любого последовательного алгоритма размещения определяется правилами выбора очередного элемента и позиции для его установки.
Пусть, $$Е_{к }$$ - элементы, размещённые до $$k$$ - го шага, а $$Р_{k}$$ - позиции, занятые этими элементами; $$\overline{E}_{k }$$ и $$\overline{P}_{k}$$ - соответственно, неразмещённые элементы и незанятые позиции.
Перед началом размещения могут быть две ситуации:
нет размещённых ранее элементов, внешние выводы узла (контакты, разъёмы и т.п.) не закреплены (в этом случае в алгоритме должен быть особо определён способ установки первого элемента);
имеется группа заранее размещённых элементов или закреплённых внешних выводов.
В основу большинства последовательных алгоритмов размещения положен принцип оптимизации целевой функции, сводящийся к выбору на данном шаге локально оптимальной позиции для одного из элементов при неизменности положения ранее размещенных элементов.
Поскольку критерий минимума суммарной длины соединений наиболее распространён, он и будет рассмотрен при описании алгоритмов данной группы.
Рассмотрим последовательный алгоритм по связности. В алгоритмах размещения по связности элемент и позиция выбираются независимо.
Выбор элемента
Любое правило выбора элемента для размещения основано на вычислении "меры связности" ещё не размещённых элементов с уже размещёнными.
Мерой связности двух элементов $$e_{i }$$ и $$e_{j}$$ является количество соединений между ними, заданное в матрице соединений $$R= || r _{i j} || _{n x n}.$$ Существуют различные способы расчёта значений $$r _{i j}.$$
Так, в алгоритмах " попарных связей " для каждого неразмещённого элемента $$e_{i}$$ подсчитывается характеристика
$$С_{i} = \max\limits_{ e_{j}\in E_{k }} r _{i j } = \sum{r _{i j }},$$
причем, $$r _{i j}$$ рассчитывается по формуле
$$r _{i j} = \sum{\cfrac{\rho_S +\lambda}{\rho_S}}\times W_S,$$
в которой $$r _{i j }$$ - множество цепей, связывающих элементы $$e_{i}$$ и $$e_{j}$$ ;
$$\rho_{s}$$ - размер цепи;
$$w_{s}$$ - весовой коэффициент;
$$\lambda$$ - целочисленный параметр.
Параметр $$\lambda$$ позволяет дифференцировать вклад цепей различного размера.
Чем больше значение $$\lambda$$, тем больше влияние цепей с малым значением $$\rho_{s}.$$
Очередным размещённым элементом является элемент, имеющий максимальную характеристику (20.6), т.е. выбор элемента осуществляется по наибольшему числу связей с уже размещёнными элементами.
Существует и другое правило выбора очередного размещаемого элемента, основанное на оценке числа связей размещаемого элемента $$e_{i} \in E_{k}$$ как с размещёнными, так и с неразмещёнными элементами (характеристика абсолютной связности ):
$$С_{i} = \sum\limits_{ e_{j}\in E_{k}}{ r _{i j }}- \sum\limits_{ e_{j}\in \overline{E}_{k}}{ r _{i j }}.$$
}В этом случае выбирается элемент с максимальным значением $$С_{i}$$ (20.8) (данный выбор аналогичен принципу максимальной конъюнкции - минимальной дизъюнкции, применяемому в алгоритмах компоновки).
К этому же типу относится характеристика относительной связности:
$$С_{i} = \cfrac{\sum\limits_{ e_{j}\in E_{k}}{ r _{i j }}}{\sum\limits_{ e_{j}\in \overline{E}_{k}}{ r _{i j }}}.$$
На очередном шаге алгоритма размещается элемент, имеющий максимальный коэффициент относительной связности.
Рассмотренные характеристики не зависят от положений элементов, поэтому в принципе может быть выполнено предварительное упорядочение всех элементов, а потом уже и их размещение.
Рассмотрим исходную матрицу смежности с элементом x_{0}, который в нашем случае содержит клеммы К1, К2, К3, К4 (рис. 20.2). Он является уже фиксированным элементом, поэтому размещать остальные элементы будем по отношении к нему.
Первый шаг.
$$C1 = 3r_{10 }/ r_{13} = 3/1=3; \;\;\; C2 = r_{20 }/ (r_{23}+2r_{24}) = 1/3; \;\; C3 = r_{30 }/ (r_{31}+r_{32}+2r_{34}+r_{35}) = 0;\\
C4 = r_{40}/ (2r_{42 }+ 2r_{43 }+ r _{46}) = 0;\;\;\; C5 = r_{50}/ (r_{53 }+r_{56})= 0; \\
C6 = r_{60}/ (r_{64}+r_{65}+r_{67}) = 0; \;\;\; C7 = r_{70 }/ r_{76 }= 1.$$
Максимальную характеристику имеет элемент $$x_{1}$$, следовательно, его размещаем вторым.
Имеем: $$x_{0}; x_{1}$$.
Второй шаг. Расчет проводим с учетом этих двух размещенных элементов:
$$C2 = (r_{20}+r_{21}) / (r_{23}+2r_{24}) = 1/3; \\
C3 = (r_{30 }+r_{31}) / (r_{32}+2r_{34}+r_{35}) = 1/4; \\
C4 = 0; \;\;C5 = 0; \;\; C6 = 0; \;\; C7 = 1.$$
Макимальную характеристику имеет элемент $$х_{7}$$, поэтому его размещаем третьим.
Имеем: $$x_{0}; x_{1}; x_{7}$$.
Третий шаг. Произведём расчёт с учётом уже трёх размещённых элементов:
$$C2 = (r_{20}+r_{21}+r_{27}) / (r_{23}+2r_{24}) = 1/3; \\
C3 = (r_{30 }+r_{31}+r_{37}) / (r_{32}+2r_{34}+r_{35}) =1/4; \\
C4 = (r_{40 }+r_{41}+r_{47}) / (2r_{42}+2r_{43}+r_{46}) = 0; \\
C5 = 0; \\
С6=1/2.$$
Максимальную характеристику имеет элемент $$x_{6}$$, поэтому шестой элемент размещаем четвёртым. Имеем: $$x_{0}; x_{1}; x_{7}; x_{6}$$.
Четвертый шаг. Производим расчет с учетом четырех размещенных элементов:
$$C2 = \cfrac{r_{20}}{r_{23}+2r_{24} }= \cfrac{1}{3};\\
C3 = \cfrac{r_{31} }{r_{32}+2r_{34}+r_{35}} = \cfrac{1}{4};\\
C4=\cfrac{1}{4};\\
С5 = 1.$$
Максимальную характеристику имеет элемент $$x_{5}$$, его размещаем пятым. Имеем: $$x_{0}; x_{1}; x_{7}; x_{6}; х_{5}$$.
Пятый шаг. Производим расчет с учетом уже пяти размещенных элементов.
$$C2 = r_{20} / (r_{23}+2r_{24}) = \cfrac{1}{3};\\
C3 = (r_{31}+r_{35}) / (r_{32}+2r_{34}) = \cfrac{2}{3}; \\
С4 = \cfrac{1}{4}.$$
Максимальную характеристику имеет элемент $$x_{3}$$, следовательно, третий элемент размещаем шестым.
Имеем: $$x_{0}; x_{1}; x_{7}; x_{6}; х_{5}; x_{3}$$.
Шестой шаг. Производим расчет с учетом уже шести размещенных элементов.
$$C2 = (r_{20}+r_{23}) / 2r_{24}= 1; \;\;\; С4=3/2 =1,5.$$
Максимальную характеристику имеет элемент $$x_{4}$$, следовательно, его размещаем седьмым.
Окончательная последовательность размещения будет такой:
$$x_{0}; x_{1}; x_{7}; x_{6}; х_{5}; x_{3}; х_{4}; х_{2}.$$
Выбор позиции
Выбранный для размещения элемент $$e _{i 0}$$ должен быть установлен в одну из незанятых позиций из множества $$\overline{P}_{k}.$$ Эта позиция выбирается с учётом минимизации критерия размещения,
в частности МСВД соединений.
При последовательном процессе размещения может быть оценена лишь суммарная длина частичных монтажных соединений данного элемента e _{i 0} с уже размещёнными элементами $$Е_{k}$$.
При установке элемента в позицию рассчитываются трассы соответствующих соединений. Длина этих соединений является критерием для выбора позиций. Однако большие затраты машинного времени делают этот подход нереальным, при конструировании узлов с печатными соединениями, и ограниченно применимым при конструировании монтажных схем проводных соединений.
Для выбора позиции $$Р_{j }\in \overline{P}_{k }$$ применяют приближённые методы оценки кратчайших монтажных соединений, т.е. рассчитывают псевдодлину реальных соединений. Одна из них, имеет вид:
$$F_{j} = \sum\limits_{ e_{j}\in E_{k}}{r _{i 0 i } d _{p ( i 0 ) p ( i )}}.$$
Выбирается та из позиций, для которой $$F_{j}$$ минимальна.
Для экономии вычислений всегда целесообразно рассматривать не всё множество позиций $$\overline{P}_{k},$$
а лишь часть.
Эти позиции находятся на периферии множества незанятых позиций $$\overline{P}_{k}.$$
Другой способ выбора позиции состоит в следующем.
Пусть $$d_{ j}^s$$ - минимальное расстояние позиции $$l_{j}$$ до одного из уже размещенных элементов в цепи $$v_{s}$$, связанной с элементом $$e _{i 0}$$.
Для размещения элемента $$e _{i0}$$ выбирают ту позицию, для которой
$$F_{j} = \sum\limits_{ S \in J _{i 0 k} }d_{ j s}$$
минимальна, $$J _{i 0 k }$$ - множество цепей,
связывающих $$e _{i 0 }$$ и $$Е_{k }$$.
Поскольку назначение первого элемента предопределяет весь дальнейший процесс размещения, при небольших затратах ЭВМ - времени на реализацию алгоритма, желательно рассмотреть несколько вариантов таких назначений и из полученных размещений выбрать лучшее.
Продолжим расчёты для нашего примера.
Шаг между двумя позициями принимаем равным единице. Пусть, например, $$x_{0 }$$ находится в четвёртой позиции. Имеем первоначальное размещение: $$x_{1}; x_{7}; x_{6}; x_{0}; х_{5}; x_{3}; х_{4}; х_{2}$$.
(рис 20.3) Первоначальное размещение элементов (вверху указаны номера позиций).Первый шаг. Размещаем элемент $$x_{1}$$.
Поместим его в каждую из позиций и определим длину:
$$F_{1} = r_{10 }\cdot d_{14} = 3 \cdot 3 = 9;\;\;\; F_{3} = r_{10 }\cdot d_{34} = 3; \;\;\; F_{6} = 6;\;\;\; F_{8 }=12.\\
F_{2} = r_{10 }\cdot d_{24} = 3 \cdot 2 = 6;\;\;\; F_{5} = r_{10 }\cdot d_{54} = 3; \;\;\;F_{7} = 9.$$
Минимальными являются критерии $$F_{3}$$ и $$F_{5}$$, следовательно, элемент $$x_{1}$$ можно разместить в пятой позиции, например: $$…; …; …; х_{0}; х_{1}; …; …; … $$.
Второй шаг. Размещаем $$х_{7}$$, но с учетом уже двух занятых позиций:
$$F_{1} = r_{70} \cdot d_{14} + r_{71} \cdot d_{15} = 3;\;\;\; F_{6} = r_{70} \cdot d_{64} + r_{71} \cdot d_{65} = 2;\\
F_{2} = r_{70} \cdot d_{24} + r_{71} \cdot d_{25} = 2;\;\;\; F_{7} = r_{70} \cdot d_{74} + r_{71} \cdot d_{75} = 3;\\
F_{3} = r_{70} \cdot d_{34} + r_{71} \cdot d_{35} = 1;\;\;\; F_{8} = r_{70} \cdot d_{84} + r_{71} \cdot d_{85} = 4.$$
Поскольку минимальным является критерий $$F_{3}$$, следовательно,
элемент $$x_{7}$$ размещаем в третьей позиции.
Третий шаг. Размещаем $$х_{6 }$$ в незанятые позиции:
$$F_{1} = r_{60} \cdot d_{14} + r_{61} \cdot d_{15} + r_{67} \cdot d_{13} = 2; \;\;\;
F_{7} = r_{60} \cdot d_{74} + r_{61} \cdot d_{75} + r_{67} \cdot d_{73} = 4;\\
F_{2} = r_{60} \cdot d_{24} + r_{61} \cdot d_{25} + r_{67} \cdot d_{23} = 1;\;\;\;
F_{8} = r_{60} \cdot d_{84} + r_{61} \cdot d_{85} + r_{67} \cdot d_{83} = 5.\\
F_{6} = r_{60} \cdot d_{64} + r_{61} \cdot d_{65} + r_{67} \cdot d_{63} = 3;$$
Помещаем $$х_{6}$$ во 2-ю позицию.
Четвертый шаг. Размещаем $$х_{5}$$ в незанятые позиции:
$$F_{1} = r_{50} \cdot d_{14} + r_{51} \cdot d_{15} + r_{57} \cdot d_{13} + r_{56} \cdot d_{12} = 1; \\
F_{7} =_{ }r_{50} \cdot d_{74} + r_{51} \cdot d_{75} + r_{57} \cdot d_{73} + r_{56} \cdot d_{72} = 5;\\
F_{6} =_{ }r_{50} \cdot d_{64} + r_{51} \cdot d_{65} + r_{57} \cdot d_{63} + r_{56} \cdot d_{62} = 4; \\
F_{8} =_{ }r_{50} \cdot d_{84} + r_{51} \cdot d_{85} + r_{57} \cdot d_{83} + r_{56} \cdot d_{82} = 6.$$
Размещаем $$х_{5}$$ в 1-ю позицию.
Пятый шаг. Размещаем $$х_{3}$$ в оставшиеся позиции:
$$F_{6} =r_{30} \cdot d_{64} + r_{31} \cdot d_{65} + r_{37} \cdot d_{63} + r_{36} \cdot d_{62} + r_{35} \cdot d_{61} = 6;\\
F_{7} = r_{30} \cdot d_{74} + r_{31} \cdot d_{75} + r_{37} \cdot d_{73} + r_{36} \cdot d_{72} + r_{35} \cdot d_{71 }= 8;\\
F_{8} = r_{30} \cdot d_{84} + r_{31} \cdot d_{85} + r_{37} \cdot d_{83} + r_{36} \cdot d_{82} + r_{36} \cdot d_{81} = 10.$$
Размещаем $$х_{3}$$ в 6-ю позицию.
Шестой шаг. Размещаем $$х_{4}$$:
$$F_{7} = r_{40} \cdot d_{74 }+ r_{41} \cdot d_{75} + r_{47} \cdot d_{73 }+ r_{46} \cdot d_{72 }+ r_{45} \cdot d_{71 }+ r_{43} \cdot d_{76} = 7\\
F_{8} = r_{40} \cdot d_{84 }+ r_{41} \cdot d_{85} + r_{47} \cdot d_{83 }+ r_{46} \cdot d_{82 }+ r_{45} \cdot d_{81 }+ r_{43} \cdot d_{86} = 10$$
Устанавливаем $$x_{4}$$ в 7-ю позицию.
Оставшийся элемент $$x_{2}$$ разместим на восьмой позиции.
В результате получим следующее размещение элементов:
(рис 20.4) Оконательное размещение элементовРассчитаем минимальную суммарную взвешенную длину связей между позициями по формуле
$$L = 1/2 \sum{\sum{ r_{ij}d_{p(i)p(j)}}}.$$
$$L = r_{56 } \cdot d_{12 }+ r_{57} \cdot d_{13 }+ r_{50} \cdot d_{14} + r_{51} \cdot d_{15 }+ r_{53 }\cdot d_{16} +
r_{54 }\cdot d_{17} + r_{52 }\cdot d_{18} + r_{67 }\cdot d_{23 }+ \\
+r_{60} \cdot d_{24} + r_{61} \cdot d_{25} +
r_{63} \cdot d_{26} + r_{64} \cdot d_{27} + r_{62} \cdot d_{28} + r_{70} \cdot d_{34} + r_{71} \cdot d_{35} +
r_{73} \cdot d_{36} + \\
+r_{74} \cdot d_{37} + r_{72} \cdot d_{38} + r_{01} \cdot d_{45} + r_{03} \cdot d_{46} +
r_{04} \cdot d_{47} + r_{02} \cdot d_{48} + r_{13} \cdot d_{56} + r_{14} \cdot d_{57} + \\
+r_{12} \cdot d_{58} + r_{34} \cdot d_{67} + r_{32} \cdot d_{68} + r_{42} \cdot d_{78} = 27 \text{ условных единиц}.$$
Для оптимизации критерия размещения используются итерационные алгоритмы.
20.5. Итерационные алгоритмы улучшения начального размещения
Алгоритмы данной группы используют общие идеи методов последовательных приближений и являются комбинаторными аналогами градиентных методов оптимизации. Для этих алгоритмов необходимо задать начальный вариант размещения.
Итерационные алгоритмы применяются для решения задачи размещения с различными критериями оптимизации $$F (p)$$: суммарная длина соединений, суммарное число пересечений соединений и т.д.
В любом итерационном алгоритме исследуется подмножество размещений, в некотором смысле близких к начальному, для выделения в нём размещения с меньшим значением функции - критерия. Найденное размещение вновь принимается за начальное, и процесс повторяется.
Алгоритм завершается при отыскании некоторого размещения, в окружности которого отсутствуют варианты с меньшим значением функций - критерия. В большинстве случаев такой процесс приводит к получению локального минимума функции $$F (p)$$.
Пусть, $$F (p)$$ - некоторая функция - критерий размещения, а $$P_{нач}$$ - начальное размещение.
Тогда в результате применения итерационного алгоритма размещения получается последовательность размещений $$р_{нач }, р_{1 }, р_{2 },…, р^*$$, которой соответствует монотонно убывающая последовательность значений $$F ( р_{нач }) > F ( р_{нач }) > F ( р_{2 }) … > F ( р^{* })$$ (рис. 20.5).
Значение $$F ( р_{* })$$ соответствует локальному минимуму функции.
Практика применения подобных алгоритмов показывает, что получаемые размещения близки к оптимальным.
Это связано с тем, что используемые критерии оптимизации $$F(P)$$
являются относительно пологими функциями, не имеющими " острых " экстремумов.
(рис 20.5) Улучшение начального размещенияХарактерной чертой итерационного алгоритма является возможность получения варианта размещения в любой момент итерационного процесса. При реализации алгоритма на ЭВМ, как правило, итерационный процесс заканчивается, как только разность значений функций - критерия для двух соседних итераций становится относительно малой:
$$[ F(р_{k}) - F ( р_{k-1 }) ] / F ( р_{k }) < \delta,$$
где $$\delta$$ - заранее заданное число.
Различные итерационные алгоритмы размещения имеют сходную структуру, содержащую следующие элементы:
преобразование очередного размещения;
вычисление функции размещения;
выбор лучшего размещения;
переход к следующей итерации и правило остановки.
В качестве начального может быть взято размещение, полученное одним из конструктивных алгоритмов размещения, с помощью генератора случайных размещений или заданное конструктором.
Из-за отсутствия теоретических оценок эффективности различных итерационных алгоритмов невозможно отдать явное предпочтение одному из них. Поэтому рассмотрим один из наиболее распространенных методов, эффективность которого подтверждается при решении практических задач.
Алгоритм парных перестановок
Алгоритмы парных перестановок являются простейшими в рассматриваемом классе алгоритмов размещения.
Пусть, имеется некоторое размещение (начальное или результат предыдущей итерации). Выбираются два элемента $$е_{i}$$ и $$e_{j},$$ которые затем меняются местами.
Рассчитывается новое значение $$F (P)$$ ; если оно меньше прежнего, то производится обмен.
Выбирается другая пара элементов и осуществляется аналогичная процедура.
Процесс итеративно продолжается до тех пор, пока не будет применено используемое в алгоритме правило остановки.
Пример. Рассмотрим минимизацию суммарной длины соединений:
$$F = \sum_{i=1}^{n}{\sum_{j=i+1}^{n}{r_{ij}d_{p(i)p(j)}}},$$
где $$R = || r _{i j }|| _{n x n}$$ и $$D = || d _{i j} || _{n x n}$$ - соответственно, матрицы соединений и расстояний.
Найдем приращение значения функции (21.13) при перестановке местами элементов $$е_{i}$$ и $$e_{j}$$, находящихся первоначально в позициях " $$h$$ " и
" $$k$$ ", соответственно.
На рис. 20.6. показано положение этих элементов до и после перестановки, а также их связи с некоторым элементом $$e_{s} (S \ne i \ne j)$$, не участвующим в перестановке и находящимся в позиции $$Р(S)$$.
Если длину соединений между всеми парами элементов, не затрагиваемых данной перестановкой, обозначить через
" $$С$$ ", то получим следующее выражение для суммарной длины соединений
$$F = \sum\limits_S{r _{i s }d _{h p ( S )} + r _{i j }d _{h k}} + \sum\limits_S{r _{j s }d _{k p ( S )}} + C.$$
(рис 20.6) Положение элементов: а) до перестановки; б) после перестановкиПосле перестановки местами элементов $$е_{i}$$ и $$е_{j}$$ значение суммарной длины изменится и станет равным:
$$F' = \sum\limits_S{r _{j s }d _{h p ( S )}} + r _{i j }d _{h k} + \sum\limits_S{r _{j s }d _{k p ( S )}} + C .$$
Сравнивая (20.14) и (20.15), можно подсчитать приращение функции
$$\Delta F _{i j} = F - F'.$$
После некоторых преобразований получим
$$\Delta F _{i j} = \sum\limits_S{ ( r _{i s} - r _{j s }) ( d _{h p ( s ) }- d _{k p ( s ) })} , s \ne i , j .$$
Алгоритмы парных перестановок для минимизации суммарной длины соединений отличаются как способом определения исследуемой окрестности очередного варианта размещения, так и стратегией выбора следующего варианта с меньшим значением длины соединений.
Очередная пара элементов для перестановки выбирается либо случайно, либо, что более эффективно, некоторым систематическим образом.
На очередной итерации для каждого элемента $$i_{k}$$ в последовательности $$I$$ рассчитывается приращение $$\Delta F _{i j}$$ (20.17) , при условии перестановки этого элемента с элементами, стоящими правее в последовательности $$I$$.
После расчёта всех характеристик $$\Delta F _{i j}$$ выбирается максимальное положительное значение $$\Delta Fi_{k}j,$$ и элемент $$е_{i}$$ меняется местами с соответствующим элементом
последовательности $$е_{j}$$.
Если для данного элемента $$e_{i}$$ в наборе $$\{\DeltaFi_{k}j\}$$ отсутствуют положительные приращения, он оставляется на своём месте и осуществляется переход к отысканию "наилучшего" места для следующего элемента $$е_{i+1}$$.
По окончании очередной итерации получается размещение с меньшей длиной соединений и осуществляется переход к следующей итерации.
Итерационный процесс заканчивается, когда изменение общей длины соединений в соответствии с (20.12) становится относительно малым.
Рассмотрение на каждой итерации возможных перестановок связано со значительными временными затратами. Поэтому в ряде алгоритмов на каждой итерации исследуются лишь перестановки соседних элементов. Кроме сокращения количества рассчитываемых приращений (оно становится пропорциональным $$n$$ ) упрощается и вычисление самих приращений.
Продолжим расчет для нашего примера.
Попытаемся улучшить критерий размещения, полученный после применения последовательного алгоритма (рис. 20.4).
Первый шаг. Берем элемент $$х_{5}$$,
условно меняем местами со всеми остальными элементами, кроме фиксированного $$х_{0}$$,
и рассчитываем приращение (20.4) относительно $$х_{0}$$:
$$\Delta F_{12} = (r_{50} - r_{60})(d_{14} - d_{24}) = 0;\;\;\; \Delta F_{16} = (r_{50 }- r_{30})(d_{14 }- d_{64}) = 0;\\
\Delta F_{13} = (r_{50} - r_{70})(d_{14 }- d_{34}) = -2; \;\;\; \Delta F_{17} = (r_{50 }- r_{40})(d_{14 }- d_{74}) = 0;\\
\Delta F_{15} = (r_{50 }- r_{10})(d_{14 }- d_{54}) = -6; \;\;\; \Delta F_{18} = (r_{50 }- r_{20})(d_{14 }- d_{84}) = 1.\\$$
Так как $$\Delta F_{18}$$ получилось положительным, то меняем местами $$х_{5}$$ и $$х_{2}$$.
Элемент $$х_{2}$$ помещаем в первую позицию:
(рис 20.5) Перемещение элементов х5 и х2Тогда $$\Delta F_{18 }= (r_{20 }- r_{50})(d_{14 }- d_{84}) = -1$$.
Значение получилось отрицательным, элементы так и оставляем.
Второй шаг. На втором шаге меняем местами элемент $$х_{6}$$
со всеми остальными элементами, кроме $$х_{0}$$ и $$х_{2}$$, и рассчитываем приращения относительно уже двух этих фиксированных элементов:
$$\Delta F_{23} = (r_{60} - r_{70})(d_{24} - d_{34}) + (r_{62} - r_{72})(d_{21} - d_{31}) = -1 \cdot 1 + 0 = -1;\\
\Delta F_{25} = (r_{60} - r_{10})(d_{24 }- d_{54}) + (r_{62 }- r_{12})(d_{21} - d_{51}) = -3 \cdot 1 + 0 = -3;\\
\Delta F_{26} = (r_{60} - r_{30})(d_{24 }- d_{64}) + (r_{62 }- r_{32})(d_{21} - d_{61}) = 0 + (-1) \cdot (-4) = 4;\\
\Delta F_{27} = (r_{60 }- r_{40})(d_{24 }- d_{74}) + (r_{62 }- r_{42})(d_{21} - d_{71}) = 0 + (-2) \cdot (-5) = 10;\\
\Delta F_{28} = (r_{60 }- r_{50})(d_{24 }- d_{84}) + (r_{62 }- r_{52})(d_{21} - d_{81}) = 0 + 0 = 0.$$
(рис 20.6) Перемещение элементов х6 и х4Так как $$\Delta F_{27}$$ получилось наибольшим положительным, то меняем местами $$х_{6}$$ с элементом $$х_{4}$$, который находится в седьмой позиции, получаем:
$$F_{27 }= (r_{40 }- r_{60})(d_{24 }- d_{74}) + (r_{42 }- r_{62})(d_{21} - d_{71}) = 0 - 10 = -10,$$
переходим к следующему шагу.
Третий шаг. Аналогично проводим расчеты для оставшихся элементов.
$$\Delta F_{35} =(r_{70 }- r_{10})(d_{34 }- d_{54}) + (r_{72 }- r_{12})(d_{31 }- d_{51}) + (r_{74 }- r_{14})(d_{32 }- d_{52})=0 + 0 + 0 = 0; \\
\Delta F_{36 }=(r_{70 }- r_{30})(d_{34 }- d_{64}) + (r_{72 }- r_{32})(d_{31 }- d_{61}) + (r_{74 }- r_{34})(d_{32 }- d_{62})= -1 + 3+6 = 8;\\
\Delta F_{37} =(r_{70 }- r_{60})(d_{34 }- d_{74}) + (r_{72 }- r_{62})(d_{31 }- d_{71}) + (r_{74 }- r_{64})(d_{32 }- d_{72})= -2 + 0 +4 = 2;\\
\Delta F_{38} =(r_{70 }- r_{50})(d_{34 }- d_{34}) + (r_{72 }- r_{52})(d_{31 }- d_{31}) + (r_{74 }- r_{52})(d_{32 }- d_{82})= -3 + 0 +0 = -3.$$
Так как $$\Delta F_{36 }$$ получилось наибольшим положительным, то меняем местами $$х_{7 }$$ и $$х_{3}$$.
(рис 20.7) Перемещение элементов х7 и х3$$\Delta F_{36} = (r_{30 }- r_{70})(d_{34 }- d_{64}) + (r_{32}-r_{72})(d_{31 }- d_{61}) + (r_{34 }- r_{74})(d_{32 }- d_{62}) = 1 - 3 - 6 = -8,$$
переходим к следующему шагу.
Четвертый шаг.
$$\Delta F_{56} = (r_{10 }- r_{70})(d_{54} - d_{64}) + (r_{13} - r_{73})(d_{53} - d_{63}) + (r_{14} -r_{74})(d_{52} - d_{62}) + (r_{12} -r_{72})(d_{51} - d_{61}) = -2 - 1 + 0 + 0 = -3\\
\Delta F_{57 }= (r_{10} - r_{60})(d_{54} - d_{74}) + (r_{13} - r_{63})(d_{53} - d_{73}) + (r_{14} - r_{64})(d_{52} - d_{72}) + (r_{12} - r_{62})(d_{51} - d_{71}) = -6 - 2 + 2 = - 6\\
\Delta F_{58} = (r_{10} - r_{50})(d_{54 }- d_{34}) + (r_{13} - r_{53})(d_{53} - d_{83}) + (r_{14} - r_{54})(d_{52} - d_{82}) + (r_{12} - r_{52})(d_{51} - d_{81}) = -9 + 0 + 0 + 0 = -9$$
Элемент $$х_{1}$$ остаётся неизменным.
(рис 20.8) Размещение элементов на четвертом шагеПятый шаг.
$$\Delta F_{67} = (r_{70} - r_{60})(d_{64} - d_{74}) + (r_{71} - r_{61})(d_{65}- d_{75}) + (r_{73} - r_{63})(d_{63} - d_{73}) + (r_{74} -r_{64})(d_{62} - d_{72}) + (r_{72} - r_{62})(d_{61} - d_{71}) = -1 + 0 + 0 + 1 + 0 = 0;\\
\Delta F_{68 }= (r_{71} - r_{51})(d_{65} - d_{85}) + (r_{70} - r_{50})(d_{64} - d_{34}) + (r_{73} - r_{53})(d_{63} - d_{83}) + (r_{74} - r_{54})(d_{62}- d_{82}) + (r_{72} -r_{52})(d_{61} - d_{81}) = 0 - 2 + 2 +0 + 0 = 0.$$
Оставляем $$х_{7}$$ в позиции 6.
(рис 20.9) Размещение элементов на пятом шагеШестой шаг.
$$\Delta F_{78} = (r_{67} - r_{57})(d_{76} - d_{86}) + (r_{61} - r_{51})(d_{75}- d_{85}) + (r_{60} -r_{50})(d_{74} - d_{84}) + (r_{63} - r_{53})(d_{73} - d_{83}) +\\ (r_{64} -r_{54})(d_{72} - d_{82}) + (r_{62} -r_{52})(d_{71} - d_{81}) = -1 + 1 - 1 = -1.$$
Получили отрицательное число, следовательно, перестановку элементов не производим.
В результате получили окончательное размещение
(рис 20.10) Окончательное размещение элементовРассчитаем критерий размещения после использования итерационного алгоритма
$$L' = 1/2 \sum{\sum{ r_{ij}d_{p(i)p(j)}}}.$$
Для этого вычислим минимальную суммарную взвешенную длину связей между позициями:
$$L
= r_{24}d_{12}+ r_{23}d_{13}+ r_{20}d_{14}+ r_{21}d_{15}+ r_{27}d_{16}+ r_{26}d_{17}+ r_{25}d_{18}+ r_{43}d_{23}+ r_{40}d_{24}+ \\
+ r_{41}d_{25}+ r_{47}d_{26}+ r_{46}d_{27}+ r_{45}d_{28}+ r_{30}d_{34}+ r_{31}d_{35}+ r_{37}d_{36}+ r_{36}d_{37}+ r_{35}d_{38}+ \\
+ r_{01}d_{45}+ r_{07}d_{46}+ r_{06}d_{47}+ r_{05}d_{48}+ r_{17}d_{56}+ r_{16}d_{5 }+ r_{15}d_{58}+ r_{76}d_{67}+ r_{75}d_{68}+ \\
+ r_{65}d_{78} = 25\text{ (условных единиц)}.$$
Значение МСВД уменьшилось. Это свидетельствует о том, что данный метод помог улучшить размещение элементов.
Контрольные вопросы
Что относится к метрическим параметрам конструкции узлов и схем?
Что относится к топологическим параметрам конструкции узлов и схем?
Что является главной целью размещения?
Как рассчитывается главный критерий размещения?
Что является вариантами коммутационного поля?
Дайте общую характеристику алгоритмов размещения.
Как рассчитывается матрица длин D?
Как решается задача квадратичного назначения?
Какие предположения делают при решении задачи минимизации СВД?
Расскажите о работе последовательного алгоритма размещения по связности.
Что является мерой связности двух элементов?
Как осуществляется выбор элементов в последовательном алгоритме?
Как рассчитывается характеристика абсолютной связности?
Как рассчитывается характеристика относительной связности?
Как осуществляется выбор позиции в последовательном алгоритме размещения?
Поясните структуру итерационного алгоритма.
Как работает итерационный алгоритм парных перестановок?
Основное назначение лекции - показать работу алгоритмов размещения элементов электрических схем на конкретных примерах для лучшего усвоения материала.
20.1. Общая постановка задачи
Задачи размещения элементов и трассировки их соединений тесно связаны и при обычных, "ручных", методах конструирования решаются одновременно. В процессе размещения элементов уточняются трассы соединений, после чего положение некоторых элементов может корректироваться. В зависимости от принятой конструктивно - технологической и схемотехнической базы при решении этих задач используются различные критерии и ограничения. Однако все конкретные разновидности упомянутых задач связаны с проблемой оптимизации схем соединений. В результате получается точное пространственное расположение отдельных элементов конструктивного узла и геометрически определённый способ соединений выводов этих элементов.
Конструкции узлов современных электронных устройств - в значительной степени унифицированные единицы. Основным элементом является коммутационная часть, определяющая конструктивно - технологический способ реализации соединений.
Критерии качества и ограничения, связанные с конкретными задачами размещения и трассировки, опираются на конкретные конструктивные и технологические особенности реализации коммутационной части узла. Всю совокупность критериев и ограничений можно разделить на две группы в соответствии с метрическими и топологическими параметрами конструкции узлов и схем.
К метрическим параметрам относятся размеры элементов и расстояния между ними, размеры коммутационного поля, расстояния между выводами элементов, допустимые длины соединений и т.д.
Топологические параметры в основном определяются принятым в конкретной конструкции способом устранения пересечений соединений и относительным расположением соединений на коммутационном поле. К ним относятся: число пространственных пересечений соединений, число межслойных переходов, близость расположения друг к другу тепловыделяющих элементов или несовместимых в электромагнитном отношении элементов и соединений.
В конкретных задачах указанные параметры в различных сочетаниях могут быть либо главными критериями оптимизации, либо выступать в качестве ограничений.
Совместное решение задач размещения и трассировки представляет значительные трудности ввиду сложного характера взаимосвязи между отдельными параметрами конструкции и схем соединений. В связи с этим при алгоритмическом подходе к их решению они рассматриваются, как правило, раздельно. Сначала осуществляется размещение элементов, а затем трассировка межсоединений. Если необходимо, этот процесс может быть повторен при другом расположении отдельных элементов.
Основной целью размещения считают создание наилучших условий для последующей трассировки соединений при удовлетворении основных требований, обеспечивающих работоспособность схем.
В общем виде задачи размещения элементов узла описывают следующим образом.
Дано множество конструктивных элементов, связанных между собой в соответствии с принципиальной электрической схемой узла. Требуется разместить элементы на некотором плоском коммутационном поле (КП) таким образом, чтобы некоторый функционал достигал экстремального значения.
Вариантами КП могут быть: панель с проводными соединениями, печатная плата, подложка микросборки, кристалл БИС.
При конструктивно однотипных элементах позиции для их установки на КП фиксированы, расположены в узлах прямоугольной решётки и могут быть описаны следующей системой параметров: $$n _{x }, n _{y }, h _{x }, h _{y }$$, где
$$n _{x }$$ - число позиций в горизонтальном ряду;
$$n _{x }$$ - число позиций в вертикальном ряду;
$$h _{x }$$ - горизонтальный шаг между позициями ;
$$h _{y }$$ - вертикальный шаг между позициями.
Возможные конструктивные особенности КП, связанные с расположением контактов элементов и внешних выводов узла, могут быть определены дополнительным набором параметров: координатами контактных площадок относительно центров позиции $$(x _{b }, y _{b})$$ и т.д.
При конструировании печатных плат с разногабаритными навесными элементами, подложек гибридных ИС, а также топологии твердотельных ИС и БИС с одним слоем коммутации позиции для размещения элементов заранее не фиксированы и окончательно определяются после трассировки соединений. Характерной особенностью задач размещения в этих конструкциях является необходимость учёта разногабаритности отдельных элементов, требований минимизации суммарной площади, занимаемой схемой, и ограничений по числу внутренних пересечений.
Раздельное решение задач размещения и трассировки приводит, как правило, к неудовлетворительным результатам. Конструирование топологии таких схем обычными методами сводится к методу "проб и ошибок", а автоматизация этого процесса основана на использовании методов топологического анализа схем и интерактивных систем графического взаимодействия конструктора с ЭВМ.
Последовательное решение задач размещения и трассировки, учитывая сложность их совместного решения, оправдано в конструкциях с высокой степенью унификации размеров элементов и соединений. Примерами являются следующие конструкции: узлы, состоящие из микросхем, соединённых с помощью двусторонних или многослойных печатных плат; панели с проводным и печатным монтажом, объединяющие конструктивно унифицированные узлы низшего уровня. Для таких конструкций обычно удаётся выделить главный критерий при оптимизации размещения, учитывая остальные параметры в виде набора дополнительных ограничений.
Критерием в большинстве случаев является критерий минимума взвешенной длины (МСВД) соединений, который интегральным образом учитывает многочисленные требования, предъявляемые к расположению элементов и трасс их соединений. Это обуславливается рядом факторов:
уменьшение длин соединений улучшает электрические параметры схемы;
чем меньше суммарная длина соединений, тем, в среднем, проще их реализация в процессе трассировки;
уменьшение суммарной длины соединений снижает трудоёмкость изготовления монтажных схем, особенно схем проводного монтажа;
данный критерий относительно прост с математической точки зрения и позволяет косвенным образом учитывать другие параметры схем путем присвоения весовых оценок отдельным соединениям.
20.2. Общая характеристика алгоритмов размещения
Задача размещения элементов является одной из основных задач конструкторского этапа проектирования электронных устройств и состоит в определении оптимального пространственного расположения элементов на коммутационном поле. В качестве критериев оптимальности размещения могут быть приняты различные характеристики схемы соединений элементов или конструкции узла в целом. В большинстве случаев выбирается один главный критерий, в наилучшей степени учитывающий многочисленные конструктивные и технологические требования. Классическим критерием является критерий минимума суммарной длины соединений (МСД). Однако для определённого класса конструкций печатных плат и интегральных схем первостепенными могут стать такие критерии, как число пересечений соединений, число слоёв коммутации и т.д.
Всю совокупность алгоритмов размещения можно разделить на следующие основные группы:
алгоритмы решения математических задач, являющихся моделями задачи размещения;
конструктивные алгоритмы начального размещения;
итерационные алгоритмы улучшения начального варианта размещения;
непрерывно - дискретные методы размещения.
К первой группе относится, прежде всего, метод ветвей и границ для задачи квадратичного назначения, к которой при определённых упрощениях сводится задача размещения: набор позиций считается фиксированным, элементы рассматриваются как геометрические точки, схема соединений представляется взвешенным графом соединений.
Другой класс моделей связан с оптимизацией размещения на непрерывной плоскости, когда набор позиций для установки заранее не фиксирован.
Третья и четвёртая группы включают приближённые алгоритмы, в основном предназначенные для оптимизации размещения элементов в фиксированном наборе позиций.
Характерной особенностью конструктивных алгоритмов является то, что они создают размещение. Итерационные алгоритмы предполагают задание начального размещения.
Конструктивные алгоритмы используют последовательный или параллельно - последовательный процесс установки элементов в позиции при локальной оптимизации функции - критерия размещения.
В итерационных алгоритмах производится переразмещение элементов или их групп с целью минимизации выбранного критерия. Эти алгоритмы требуют существенных затрат машинного времени и используются для получения окончательного размещения.
Основной областью применения непрерывно - дискретных методов размещения являются конструкции, в которых позиции для установки элементов заранее не фиксированы. Исходной базой для построения алгоритмов данной группы являются непрерывные модели и механические аналогии задачи размещения.
20.3. М М задачи размещения. Модель квадратичного назначения
Пусть, даны элементы $$е_{1 }, е_{2 }, … е _{n }$$ и для каждой пары элементов заданы весовые коэффициенты $$r _{i j }( i, j = 1, 2 , ..., n ),$$ определяющие " степень связи " элементов друг с другом.
Таким образом, считаем, что схема задана матрицей соединений
$$R = || r _{i j} || _{n x n }.$$
Пусть, имеется некоторый фиксированный набор позиций для размещения элементов $$р_{1 }, р_{2 }, … , р _{m } ( m \ge n )$$. В дальнейшем будем полагать, что $$m = n$$.
Если $$m > n,$$ можно ввести $$(m - n)$$ фиктивных элементов, не имеющих соединений с остальными элементами $$r _{i j} = 0; i = n + 1 ... m; j = 1, 2, ... , m $$.
Определим расстояние $$d _{i j}$$ между парами позиций.
Для этого воспользуемся дополнительной информацией. Пусть, на коммутационном поле фиксированы позиции для размещения элементов.
Для них можно задать матрицу расстояний
$$D = || d _{i j} || _{n x m} ,$$
в которой элемент $$d _{i j }$$ равен расстоянию между центрами позиций $$p (i)$$ и $$p (j)$$. Матрица $$D$$ - симметричная, с нулевой главной диагональю $$(d _{i j} = 0, i = 1, 2, ... , n)$$.
Рассмотрим такой фиксированный набор позиций (рис. 20.1):
(рис 20.1) Фиксированный набор позицийДля такого набора позиций имеем :
$$D =
\begin{array}{cccccccccccccc}
123456789101112\\
\begin{array}{c}1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 12\end{array}
\left \|
\begin{array}{c}0 \\ 1 \\ 2 \\ 3 \\ 1 \\ 2 \\ 3 \\ 4 \\ 2 \\ 3 \\ 4 \\ 5\end{array}
\begin{array}{c}1 \\ 0 \\ 1 \\ 2 \\ 2 \\ 1 \\ 2 \\ 3 \\ 3 \\ 2 \\ 3 \\ 4\end{array}
\begin{array}{c}2 \\ 1 \\ 0 \\ 1 \\ 3 \\ 2 \\ 1 \\ 2 \\ 4 \\ 3 \\ 2 \\ 3\end{array}
\begin{array}{c}3 \\ 2 \\ 1 \\ 0 \\ 4 \\ 3 \\ 2 \\ 1 \\ 5 \\ 4 \\ 3 \\ 2\end{array}
\begin{array}{c}1 \\ 2 \\ 3 \\ 4 \\ 0 \\ 1 \\ 2 \\ 3 \\ 1 \\ 2 \\ 3 \\ 4\end{array}
\begin{array}{c}2 \\ 1 \\ 2 \\ 3 \\ 1 \\ 0 \\ 1 \\ 2 \\ 2 \\ 1 \\ 2 \\ 3\end{array}
\begin{array}{c}3 \\ 2 \\ 1 \\ 2 \\ 2 \\ 1 \\ 0 \\ 1 \\ 3 \\ 2 \\ 1 \\ 2\end{array}
\begin{array}{c}4 \\ 3 \\ 2 \\ 1 \\ 3 \\ 2 \\ 1 \\ 0 \\ 4 \\ 3 \\ 2 \\ 1\end{array}
\begin{array}{c}2 \\ 3 \\ 4 \\ 5 \\ 1 \\ 2 \\ 3 \\ 4 \\ 0 \\ 1 \\ 2 \\ 3\end{array}
\begin{array}{c}3 \\ 2 \\ 3 \\ 4 \\ 2 \\ 1 \\ 2 \\ 3 \\ 1 \\ 0 \\ 1 \\ 2\end{array}
\begin{array}{c}4 \\ 3 \\ 2 \\ 3 \\ 3 \\ 2 \\ 1 \\ 2 \\ 2 \\ 1 \\ 0 \\ 1\end{array}
\begin{array}{c}5 \\ 4 \\ 3 \\ 2 \\ 4 \\ 3 \\ 2 \\ 1 \\ 3 \\ 2 \\ 1 \\ 0\end{array}
\left \|
\begin{array}{c} \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \end{array}
\end{array}$$
Для вычисления элементов матрицы $$D$$ использована ортогональная метрика,
причём расстояние между соседними позициями по вертикали и горизонтали равно 1.
Произвольное размещение элементов в позициях представляет собой некоторую перестановку $$р = р ( 1 ), … р ( n )$$, где $$n ( i )$$ задает номер позиции, присвоенной $$i$$ - тому элементу.
Таким образом, имеется всего $$n$$! различных вариантов размещения элементов.
Попытки найти оптимальный вариант полным перебором безуспешны даже при малых значениях $$n$$.
Рассмотрим задачу минимизации суммарной взвешенной длины (МСВД) соединений при следующих предположениях.
Соединения считаем условно исходящими из геометрических центров элементов.
Кроме того, предполагаем совпадение центров элементов и позиций.
Как правило, при решении задачи размещения необходимо учитывать предварительное закрепление некоторых элементов в позициях и
соединения элементов с внешними выводами. Сопоставляя внешним выводам элемент $$е_{0}$$ и фиксируя расположение части элементов, получим упрощенное представление коммутационного поля (рис. 20.2).
Очевидно, что длина соединений между элементами $$е_{i}$$ и $$e_{j}$$ оценивается величиной
$$L _{i j } = r _{i j }d _{p ( i ) p ( j ) }.$$
(рис 20.2) Представление коммутационного поляОбозначим через $$E_{S}$$ множество всех фиксированных элементов, включая элемент $$е_{0}$$ ; тогда суммарная взвешенная длина соединений элемента $$е_{i}$$ с элементами из $$E_{S}$$ оценивается по формуле:
$$a _{i p ( i )} = \sum\limits_{S\in E_S}{r_{is}d_{p(i)S}}$$
где $$d _{p ( i ) S}$$ - расстояние между элементом $$е_{i},$$
находящимся в позиции $$p ( i )$$, и элементом $$е_{S}$$.
Учитывая вышесказанное, а также симметричность матриц $$R$$ и $$D$$, запишем выражение для суммарной вешенной длины соединений при произвольном размещении:
$$F ( p ) = \cfrac{1}{2}\sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{n}{ r _{ij }d_{p(i)p(j) }}} +
\sum\limits_{i=1}^{n}{ a_{i p ( i ) }}$$
Таким образом, задача размещения по критерию МСВД соединений состоит в минимизации функционала (19.5) на множестве перестановок Р.
Данная задача является вариантом общей математической модели, получившей название задачи квадратичного назначения.
20.4. Алгоритмы последовательного размещения элементов по связности
Исходной информацией для размещения элементов является:
схема соединений;
параметры конструкции элементов и коммутационного поля.
Прежде всего, рассмотрим наиболее представительные алгоритмы, использующие последовательный процесс установки элементов в позиции.
Пусть, $$Е = \{ e_{1} , e_{2} , ... , e_{n} \}$$ - множество элементов, подлежащих размещению, а $$Р = \{ р_{1} , р_{2} , … , р_{n} \}$$ - множество позиций для их установки.
Вводится $$n$$ - шаговый процесс принятия решений, на каждом шаге которого выбирается один из
неразмещённых элементов и помещается в одну из незанятых позиций.
Структура любого последовательного алгоритма размещения определяется правилами выбора очередного элемента и позиции для его установки.
Пусть, $$Е_{к }$$ - элементы, размещённые до $$k$$ - го шага, а $$Р_{k}$$ - позиции, занятые этими элементами; $$\overline{E}_{k }$$ и $$\overline{P}_{k}$$ - соответственно, неразмещённые элементы и незанятые позиции.
Перед началом размещения могут быть две ситуации:
нет размещённых ранее элементов, внешние выводы узла (контакты, разъёмы и т.п.) не закреплены (в этом случае в алгоритме должен быть особо определён способ установки первого элемента);
имеется группа заранее размещённых элементов или закреплённых внешних выводов.
В основу большинства последовательных алгоритмов размещения положен принцип оптимизации целевой функции, сводящийся к выбору на данном шаге локально оптимальной позиции для одного из элементов при неизменности положения ранее размещенных элементов.
Поскольку критерий минимума суммарной длины соединений наиболее распространён, он и будет рассмотрен при описании алгоритмов данной группы.
Рассмотрим последовательный алгоритм по связности. В алгоритмах размещения по связности элемент и позиция выбираются независимо.
Выбор элемента
Любое правило выбора элемента для размещения основано на вычислении "меры связности" ещё не размещённых элементов с уже размещёнными.
Мерой связности двух элементов $$e_{i }$$ и $$e_{j}$$ является количество соединений между ними, заданное в матрице соединений $$R= || r _{i j} || _{n x n}.$$ Существуют различные способы расчёта значений $$r _{i j}.$$
Так, в алгоритмах " попарных связей " для каждого неразмещённого элемента $$e_{i}$$ подсчитывается характеристика
$$С_{i} = \max\limits_{ e_{j}\in E_{k }} r _{i j } = \sum{r _{i j }},$$
причем, $$r _{i j}$$ рассчитывается по формуле
$$r _{i j} = \sum{\cfrac{\rho_S +\lambda}{\rho_S}}\times W_S,$$
в которой $$r _{i j }$$ - множество цепей, связывающих элементы $$e_{i}$$ и $$e_{j}$$ ;
$$\rho_{s}$$ - размер цепи;
$$w_{s}$$ - весовой коэффициент;
$$\lambda$$ - целочисленный параметр.
Параметр $$\lambda$$ позволяет дифференцировать вклад цепей различного размера.
Чем больше значение $$\lambda$$, тем больше влияние цепей с малым значением $$\rho_{s}.$$
Очередным размещённым элементом является элемент, имеющий максимальную характеристику (20.6), т.е. выбор элемента осуществляется по наибольшему числу связей с уже размещёнными элементами.
Существует и другое правило выбора очередного размещаемого элемента, основанное на оценке числа связей размещаемого элемента $$e_{i} \in E_{k}$$ как с размещёнными, так и с неразмещёнными элементами (характеристика абсолютной связности ):
$$С_{i} = \sum\limits_{ e_{j}\in E_{k}}{ r _{i j }}- \sum\limits_{ e_{j}\in \overline{E}_{k}}{ r _{i j }}.$$
}В этом случае выбирается элемент с максимальным значением $$С_{i}$$ (20.8) (данный выбор аналогичен принципу максимальной конъюнкции - минимальной дизъюнкции, применяемому в алгоритмах компоновки).
К этому же типу относится характеристика относительной связности:
$$С_{i} = \cfrac{\sum\limits_{ e_{j}\in E_{k}}{ r _{i j }}}{\sum\limits_{ e_{j}\in \overline{E}_{k}}{ r _{i j }}}.$$
На очередном шаге алгоритма размещается элемент, имеющий максимальный коэффициент относительной связности.
Рассмотренные характеристики не зависят от положений элементов, поэтому в принципе может быть выполнено предварительное упорядочение всех элементов, а потом уже и их размещение.
Рассмотрим исходную матрицу смежности с элементом x_{0}, который в нашем случае содержит клеммы К1, К2, К3, К4 (рис. 20.2). Он является уже фиксированным элементом, поэтому размещать остальные элементы будем по отношении к нему.
Первый шаг.
$$C1 = 3r_{10 }/ r_{13} = 3/1=3; \;\;\; C2 = r_{20 }/ (r_{23}+2r_{24}) = 1/3; \;\; C3 = r_{30 }/ (r_{31}+r_{32}+2r_{34}+r_{35}) = 0;\\
C4 = r_{40}/ (2r_{42 }+ 2r_{43 }+ r _{46}) = 0;\;\;\; C5 = r_{50}/ (r_{53 }+r_{56})= 0; \\
C6 = r_{60}/ (r_{64}+r_{65}+r_{67}) = 0; \;\;\; C7 = r_{70 }/ r_{76 }= 1.$$
Максимальную характеристику имеет элемент $$x_{1}$$, следовательно, его размещаем вторым.
Имеем: $$x_{0}; x_{1}$$.
Второй шаг. Расчет проводим с учетом этих двух размещенных элементов:
$$C2 = (r_{20}+r_{21}) / (r_{23}+2r_{24}) = 1/3; \\
C3 = (r_{30 }+r_{31}) / (r_{32}+2r_{34}+r_{35}) = 1/4; \\
C4 = 0; \;\;C5 = 0; \;\; C6 = 0; \;\; C7 = 1.$$
Макимальную характеристику имеет элемент $$х_{7}$$, поэтому его размещаем третьим.
Имеем: $$x_{0}; x_{1}; x_{7}$$.
Третий шаг. Произведём расчёт с учётом уже трёх размещённых элементов:
$$C2 = (r_{20}+r_{21}+r_{27}) / (r_{23}+2r_{24}) = 1/3; \\
C3 = (r_{30 }+r_{31}+r_{37}) / (r_{32}+2r_{34}+r_{35}) =1/4; \\
C4 = (r_{40 }+r_{41}+r_{47}) / (2r_{42}+2r_{43}+r_{46}) = 0; \\
C5 = 0; \\
С6=1/2.$$
Максимальную характеристику имеет элемент $$x_{6}$$, поэтому шестой элемент размещаем четвёртым. Имеем: $$x_{0}; x_{1}; x_{7}; x_{6}$$.
Четвертый шаг. Производим расчет с учетом четырех размещенных элементов:
$$C2 = \cfrac{r_{20}}{r_{23}+2r_{24} }= \cfrac{1}{3};\\
C3 = \cfrac{r_{31} }{r_{32}+2r_{34}+r_{35}} = \cfrac{1}{4};\\
C4=\cfrac{1}{4};\\
С5 = 1.$$
Максимальную характеристику имеет элемент $$x_{5}$$, его размещаем пятым. Имеем: $$x_{0}; x_{1}; x_{7}; x_{6}; х_{5}$$.
Пятый шаг. Производим расчет с учетом уже пяти размещенных элементов.
$$C2 = r_{20} / (r_{23}+2r_{24}) = \cfrac{1}{3};\\
C3 = (r_{31}+r_{35}) / (r_{32}+2r_{34}) = \cfrac{2}{3}; \\
С4 = \cfrac{1}{4}.$$
Максимальную характеристику имеет элемент $$x_{3}$$, следовательно, третий элемент размещаем шестым.
Имеем: $$x_{0}; x_{1}; x_{7}; x_{6}; х_{5}; x_{3}$$.
Шестой шаг. Производим расчет с учетом уже шести размещенных элементов.
$$C2 = (r_{20}+r_{23}) / 2r_{24}= 1; \;\;\; С4=3/2 =1,5.$$
Максимальную характеристику имеет элемент $$x_{4}$$, следовательно, его размещаем седьмым.
Окончательная последовательность размещения будет такой:
$$x_{0}; x_{1}; x_{7}; x_{6}; х_{5}; x_{3}; х_{4}; х_{2}.$$
Выбор позиции
Выбранный для размещения элемент $$e _{i 0}$$ должен быть установлен в одну из незанятых позиций из множества $$\overline{P}_{k}.$$ Эта позиция выбирается с учётом минимизации критерия размещения,
в частности МСВД соединений.
При последовательном процессе размещения может быть оценена лишь суммарная длина частичных монтажных соединений данного элемента e _{i 0} с уже размещёнными элементами $$Е_{k}$$.
При установке элемента в позицию рассчитываются трассы соответствующих соединений. Длина этих соединений является критерием для выбора позиций. Однако большие затраты машинного времени делают этот подход нереальным, при конструировании узлов с печатными соединениями, и ограниченно применимым при конструировании монтажных схем проводных соединений.
Для выбора позиции $$Р_{j }\in \overline{P}_{k }$$ применяют приближённые методы оценки кратчайших монтажных соединений, т.е. рассчитывают псевдодлину реальных соединений. Одна из них, имеет вид:
$$F_{j} = \sum\limits_{ e_{j}\in E_{k}}{r _{i 0 i } d _{p ( i 0 ) p ( i )}}.$$
Выбирается та из позиций, для которой $$F_{j}$$ минимальна.
Для экономии вычислений всегда целесообразно рассматривать не всё множество позиций $$\overline{P}_{k},$$
а лишь часть.
Эти позиции находятся на периферии множества незанятых позиций $$\overline{P}_{k}.$$
Другой способ выбора позиции состоит в следующем.
Пусть $$d_{ j}^s$$ - минимальное расстояние позиции $$l_{j}$$ до одного из уже размещенных элементов в цепи $$v_{s}$$, связанной с элементом $$e _{i 0}$$.
Для размещения элемента $$e _{i0}$$ выбирают ту позицию, для которой
$$F_{j} = \sum\limits_{ S \in J _{i 0 k} }d_{ j s}$$
минимальна, $$J _{i 0 k }$$ - множество цепей,
связывающих $$e _{i 0 }$$ и $$Е_{k }$$.
Поскольку назначение первого элемента предопределяет весь дальнейший процесс размещения, при небольших затратах ЭВМ - времени на реализацию алгоритма, желательно рассмотреть несколько вариантов таких назначений и из полученных размещений выбрать лучшее.
Продолжим расчёты для нашего примера.
Шаг между двумя позициями принимаем равным единице. Пусть, например, $$x_{0 }$$ находится в четвёртой позиции. Имеем первоначальное размещение: $$x_{1}; x_{7}; x_{6}; x_{0}; х_{5}; x_{3}; х_{4}; х_{2}$$.
(рис 20.3) Первоначальное размещение элементов (вверху указаны номера позиций).Первый шаг. Размещаем элемент $$x_{1}$$.
Поместим его в каждую из позиций и определим длину:
$$F_{1} = r_{10 }\cdot d_{14} = 3 \cdot 3 = 9;\;\;\; F_{3} = r_{10 }\cdot d_{34} = 3; \;\;\; F_{6} = 6;\;\;\; F_{8 }=12.\\
F_{2} = r_{10 }\cdot d_{24} = 3 \cdot 2 = 6;\;\;\; F_{5} = r_{10 }\cdot d_{54} = 3; \;\;\;F_{7} = 9.$$
Минимальными являются критерии $$F_{3}$$ и $$F_{5}$$, следовательно, элемент $$x_{1}$$ можно разместить в пятой позиции, например: $$…; …; …; х_{0}; х_{1}; …; …; … $$.
Второй шаг. Размещаем $$х_{7}$$, но с учетом уже двух занятых позиций:
$$F_{1} = r_{70} \cdot d_{14} + r_{71} \cdot d_{15} = 3;\;\;\; F_{6} = r_{70} \cdot d_{64} + r_{71} \cdot d_{65} = 2;\\
F_{2} = r_{70} \cdot d_{24} + r_{71} \cdot d_{25} = 2;\;\;\; F_{7} = r_{70} \cdot d_{74} + r_{71} \cdot d_{75} = 3;\\
F_{3} = r_{70} \cdot d_{34} + r_{71} \cdot d_{35} = 1;\;\;\; F_{8} = r_{70} \cdot d_{84} + r_{71} \cdot d_{85} = 4.$$
Поскольку минимальным является критерий $$F_{3}$$, следовательно,
элемент $$x_{7}$$ размещаем в третьей позиции.
Третий шаг. Размещаем $$х_{6 }$$ в незанятые позиции:
$$F_{1} = r_{60} \cdot d_{14} + r_{61} \cdot d_{15} + r_{67} \cdot d_{13} = 2; \;\;\;
F_{7} = r_{60} \cdot d_{74} + r_{61} \cdot d_{75} + r_{67} \cdot d_{73} = 4;\\
F_{2} = r_{60} \cdot d_{24} + r_{61} \cdot d_{25} + r_{67} \cdot d_{23} = 1;\;\;\;
F_{8} = r_{60} \cdot d_{84} + r_{61} \cdot d_{85} + r_{67} \cdot d_{83} = 5.\\
F_{6} = r_{60} \cdot d_{64} + r_{61} \cdot d_{65} + r_{67} \cdot d_{63} = 3;$$
Помещаем $$х_{6}$$ во 2-ю позицию.
Четвертый шаг. Размещаем $$х_{5}$$ в незанятые позиции:
$$F_{1} = r_{50} \cdot d_{14} + r_{51} \cdot d_{15} + r_{57} \cdot d_{13} + r_{56} \cdot d_{12} = 1; \\
F_{7} =_{ }r_{50} \cdot d_{74} + r_{51} \cdot d_{75} + r_{57} \cdot d_{73} + r_{56} \cdot d_{72} = 5;\\
F_{6} =_{ }r_{50} \cdot d_{64} + r_{51} \cdot d_{65} + r_{57} \cdot d_{63} + r_{56} \cdot d_{62} = 4; \\
F_{8} =_{ }r_{50} \cdot d_{84} + r_{51} \cdot d_{85} + r_{57} \cdot d_{83} + r_{56} \cdot d_{82} = 6.$$
Размещаем $$х_{5}$$ в 1-ю позицию.
Пятый шаг. Размещаем $$х_{3}$$ в оставшиеся позиции:
$$F_{6} =r_{30} \cdot d_{64} + r_{31} \cdot d_{65} + r_{37} \cdot d_{63} + r_{36} \cdot d_{62} + r_{35} \cdot d_{61} = 6;\\
F_{7} = r_{30} \cdot d_{74} + r_{31} \cdot d_{75} + r_{37} \cdot d_{73} + r_{36} \cdot d_{72} + r_{35} \cdot d_{71 }= 8;\\
F_{8} = r_{30} \cdot d_{84} + r_{31} \cdot d_{85} + r_{37} \cdot d_{83} + r_{36} \cdot d_{82} + r_{36} \cdot d_{81} = 10.$$
Размещаем $$х_{3}$$ в 6-ю позицию.
Шестой шаг. Размещаем $$х_{4}$$:
$$F_{7} = r_{40} \cdot d_{74 }+ r_{41} \cdot d_{75} + r_{47} \cdot d_{73 }+ r_{46} \cdot d_{72 }+ r_{45} \cdot d_{71 }+ r_{43} \cdot d_{76} = 7\\
F_{8} = r_{40} \cdot d_{84 }+ r_{41} \cdot d_{85} + r_{47} \cdot d_{83 }+ r_{46} \cdot d_{82 }+ r_{45} \cdot d_{81 }+ r_{43} \cdot d_{86} = 10$$
Устанавливаем $$x_{4}$$ в 7-ю позицию.
Оставшийся элемент $$x_{2}$$ разместим на восьмой позиции.
В результате получим следующее размещение элементов:
(рис 20.4) Оконательное размещение элементовРассчитаем минимальную суммарную взвешенную длину связей между позициями по формуле
$$L = 1/2 \sum{\sum{ r_{ij}d_{p(i)p(j)}}}.$$
$$L = r_{56 } \cdot d_{12 }+ r_{57} \cdot d_{13 }+ r_{50} \cdot d_{14} + r_{51} \cdot d_{15 }+ r_{53 }\cdot d_{16} +
r_{54 }\cdot d_{17} + r_{52 }\cdot d_{18} + r_{67 }\cdot d_{23 }+ \\
+r_{60} \cdot d_{24} + r_{61} \cdot d_{25} +
r_{63} \cdot d_{26} + r_{64} \cdot d_{27} + r_{62} \cdot d_{28} + r_{70} \cdot d_{34} + r_{71} \cdot d_{35} +
r_{73} \cdot d_{36} + \\
+r_{74} \cdot d_{37} + r_{72} \cdot d_{38} + r_{01} \cdot d_{45} + r_{03} \cdot d_{46} +
r_{04} \cdot d_{47} + r_{02} \cdot d_{48} + r_{13} \cdot d_{56} + r_{14} \cdot d_{57} + \\
+r_{12} \cdot d_{58} + r_{34} \cdot d_{67} + r_{32} \cdot d_{68} + r_{42} \cdot d_{78} = 27 \text{ условных единиц}.$$
Для оптимизации критерия размещения используются итерационные алгоритмы.
20.5. Итерационные алгоритмы улучшения начального размещения
Алгоритмы данной группы используют общие идеи методов последовательных приближений и являются комбинаторными аналогами градиентных методов оптимизации. Для этих алгоритмов необходимо задать начальный вариант размещения.
Итерационные алгоритмы применяются для решения задачи размещения с различными критериями оптимизации $$F (p)$$: суммарная длина соединений, суммарное число пересечений соединений и т.д.
В любом итерационном алгоритме исследуется подмножество размещений, в некотором смысле близких к начальному, для выделения в нём размещения с меньшим значением функции - критерия. Найденное размещение вновь принимается за начальное, и процесс повторяется.
Алгоритм завершается при отыскании некоторого размещения, в окружности которого отсутствуют варианты с меньшим значением функций - критерия. В большинстве случаев такой процесс приводит к получению локального минимума функции $$F (p)$$.
Пусть, $$F (p)$$ - некоторая функция - критерий размещения, а $$P_{нач}$$ - начальное размещение.
Тогда в результате применения итерационного алгоритма размещения получается последовательность размещений $$р_{нач }, р_{1 }, р_{2 },…, р^*$$, которой соответствует монотонно убывающая последовательность значений $$F ( р_{нач }) > F ( р_{нач }) > F ( р_{2 }) … > F ( р^{* })$$ (рис. 20.5).
Значение $$F ( р_{* })$$ соответствует локальному минимуму функции.
Практика применения подобных алгоритмов показывает, что получаемые размещения близки к оптимальным.
Это связано с тем, что используемые критерии оптимизации $$F(P)$$
являются относительно пологими функциями, не имеющими " острых " экстремумов.
(рис 20.5) Улучшение начального размещенияХарактерной чертой итерационного алгоритма является возможность получения варианта размещения в любой момент итерационного процесса. При реализации алгоритма на ЭВМ, как правило, итерационный процесс заканчивается, как только разность значений функций - критерия для двух соседних итераций становится относительно малой:
$$[ F(р_{k}) - F ( р_{k-1 }) ] / F ( р_{k }) < \delta,$$
где $$\delta$$ - заранее заданное число.
Различные итерационные алгоритмы размещения имеют сходную структуру, содержащую следующие элементы:
преобразование очередного размещения;
вычисление функции размещения;
выбор лучшего размещения;
переход к следующей итерации и правило остановки.
В качестве начального может быть взято размещение, полученное одним из конструктивных алгоритмов размещения, с помощью генератора случайных размещений или заданное конструктором.
Из-за отсутствия теоретических оценок эффективности различных итерационных алгоритмов невозможно отдать явное предпочтение одному из них. Поэтому рассмотрим один из наиболее распространенных методов, эффективность которого подтверждается при решении практических задач.
Алгоритм парных перестановок
Алгоритмы парных перестановок являются простейшими в рассматриваемом классе алгоритмов размещения.
Пусть, имеется некоторое размещение (начальное или результат предыдущей итерации). Выбираются два элемента $$е_{i}$$ и $$e_{j},$$ которые затем меняются местами.
Рассчитывается новое значение $$F (P)$$ ; если оно меньше прежнего, то производится обмен.
Выбирается другая пара элементов и осуществляется аналогичная процедура.
Процесс итеративно продолжается до тех пор, пока не будет применено используемое в алгоритме правило остановки.
Пример. Рассмотрим минимизацию суммарной длины соединений:
$$F = \sum_{i=1}^{n}{\sum_{j=i+1}^{n}{r_{ij}d_{p(i)p(j)}}},$$
где $$R = || r _{i j }|| _{n x n}$$ и $$D = || d _{i j} || _{n x n}$$ - соответственно, матрицы соединений и расстояний.
Найдем приращение значения функции (21.13) при перестановке местами элементов $$е_{i}$$ и $$e_{j}$$, находящихся первоначально в позициях " $$h$$ " и
" $$k$$ ", соответственно.
На рис. 20.6. показано положение этих элементов до и после перестановки, а также их связи с некоторым элементом $$e_{s} (S \ne i \ne j)$$, не участвующим в перестановке и находящимся в позиции $$Р(S)$$.
Если длину соединений между всеми парами элементов, не затрагиваемых данной перестановкой, обозначить через
" $$С$$ ", то получим следующее выражение для суммарной длины соединений
$$F = \sum\limits_S{r _{i s }d _{h p ( S )} + r _{i j }d _{h k}} + \sum\limits_S{r _{j s }d _{k p ( S )}} + C.$$
(рис 20.6) Положение элементов: а) до перестановки; б) после перестановкиПосле перестановки местами элементов $$е_{i}$$ и $$е_{j}$$ значение суммарной длины изменится и станет равным:
$$F' = \sum\limits_S{r _{j s }d _{h p ( S )}} + r _{i j }d _{h k} + \sum\limits_S{r _{j s }d _{k p ( S )}} + C .$$
Сравнивая (20.14) и (20.15), можно подсчитать приращение функции
$$\Delta F _{i j} = F - F'.$$
После некоторых преобразований получим
$$\Delta F _{i j} = \sum\limits_S{ ( r _{i s} - r _{j s }) ( d _{h p ( s ) }- d _{k p ( s ) })} , s \ne i , j .$$
Алгоритмы парных перестановок для минимизации суммарной длины соединений отличаются как способом определения исследуемой окрестности очередного варианта размещения, так и стратегией выбора следующего варианта с меньшим значением длины соединений.
Очередная пара элементов для перестановки выбирается либо случайно, либо, что более эффективно, некоторым систематическим образом.
На очередной итерации для каждого элемента $$i_{k}$$ в последовательности $$I$$ рассчитывается приращение $$\Delta F _{i j}$$ (20.17) , при условии перестановки этого элемента с элементами, стоящими правее в последовательности $$I$$.
После расчёта всех характеристик $$\Delta F _{i j}$$ выбирается максимальное положительное значение $$\Delta Fi_{k}j,$$ и элемент $$е_{i}$$ меняется местами с соответствующим элементом
последовательности $$е_{j}$$.
Если для данного элемента $$e_{i}$$ в наборе $$\{\DeltaFi_{k}j\}$$ отсутствуют положительные приращения, он оставляется на своём месте и осуществляется переход к отысканию "наилучшего" места для следующего элемента $$е_{i+1}$$.
По окончании очередной итерации получается размещение с меньшей длиной соединений и осуществляется переход к следующей итерации.
Итерационный процесс заканчивается, когда изменение общей длины соединений в соответствии с (20.12) становится относительно малым.
Рассмотрение на каждой итерации возможных перестановок связано со значительными временными затратами. Поэтому в ряде алгоритмов на каждой итерации исследуются лишь перестановки соседних элементов. Кроме сокращения количества рассчитываемых приращений (оно становится пропорциональным $$n$$ ) упрощается и вычисление самих приращений.
Продолжим расчет для нашего примера.
Попытаемся улучшить критерий размещения, полученный после применения последовательного алгоритма (рис. 20.4).
Первый шаг. Берем элемент $$х_{5}$$,
условно меняем местами со всеми остальными элементами, кроме фиксированного $$х_{0}$$,
и рассчитываем приращение (20.4) относительно $$х_{0}$$:
$$\Delta F_{12} = (r_{50} - r_{60})(d_{14} - d_{24}) = 0;\;\;\; \Delta F_{16} = (r_{50 }- r_{30})(d_{14 }- d_{64}) = 0;\\
\Delta F_{13} = (r_{50} - r_{70})(d_{14 }- d_{34}) = -2; \;\;\; \Delta F_{17} = (r_{50 }- r_{40})(d_{14 }- d_{74}) = 0;\\
\Delta F_{15} = (r_{50 }- r_{10})(d_{14 }- d_{54}) = -6; \;\;\; \Delta F_{18} = (r_{50 }- r_{20})(d_{14 }- d_{84}) = 1.\\$$
Так как $$\Delta F_{18}$$ получилось положительным, то меняем местами $$х_{5}$$ и $$х_{2}$$.
Элемент $$х_{2}$$ помещаем в первую позицию:
(рис 20.5) Перемещение элементов х5 и х2Тогда $$\Delta F_{18 }= (r_{20 }- r_{50})(d_{14 }- d_{84}) = -1$$.
Значение получилось отрицательным, элементы так и оставляем.
Второй шаг. На втором шаге меняем местами элемент $$х_{6}$$
со всеми остальными элементами, кроме $$х_{0}$$ и $$х_{2}$$, и рассчитываем приращения относительно уже двух этих фиксированных элементов:
$$\Delta F_{23} = (r_{60} - r_{70})(d_{24} - d_{34}) + (r_{62} - r_{72})(d_{21} - d_{31}) = -1 \cdot 1 + 0 = -1;\\
\Delta F_{25} = (r_{60} - r_{10})(d_{24 }- d_{54}) + (r_{62 }- r_{12})(d_{21} - d_{51}) = -3 \cdot 1 + 0 = -3;\\
\Delta F_{26} = (r_{60} - r_{30})(d_{24 }- d_{64}) + (r_{62 }- r_{32})(d_{21} - d_{61}) = 0 + (-1) \cdot (-4) = 4;\\
\Delta F_{27} = (r_{60 }- r_{40})(d_{24 }- d_{74}) + (r_{62 }- r_{42})(d_{21} - d_{71}) = 0 + (-2) \cdot (-5) = 10;\\
\Delta F_{28} = (r_{60 }- r_{50})(d_{24 }- d_{84}) + (r_{62 }- r_{52})(d_{21} - d_{81}) = 0 + 0 = 0.$$
(рис 20.6) Перемещение элементов х6 и х4Так как $$\Delta F_{27}$$ получилось наибольшим положительным, то меняем местами $$х_{6}$$ с элементом $$х_{4}$$, который находится в седьмой позиции, получаем:
$$F_{27 }= (r_{40 }- r_{60})(d_{24 }- d_{74}) + (r_{42 }- r_{62})(d_{21} - d_{71}) = 0 - 10 = -10,$$
переходим к следующему шагу.
Третий шаг. Аналогично проводим расчеты для оставшихся элементов.
$$\Delta F_{35} =(r_{70 }- r_{10})(d_{34 }- d_{54}) + (r_{72 }- r_{12})(d_{31 }- d_{51}) + (r_{74 }- r_{14})(d_{32 }- d_{52})=0 + 0 + 0 = 0; \\
\Delta F_{36 }=(r_{70 }- r_{30})(d_{34 }- d_{64}) + (r_{72 }- r_{32})(d_{31 }- d_{61}) + (r_{74 }- r_{34})(d_{32 }- d_{62})= -1 + 3+6 = 8;\\
\Delta F_{37} =(r_{70 }- r_{60})(d_{34 }- d_{74}) + (r_{72 }- r_{62})(d_{31 }- d_{71}) + (r_{74 }- r_{64})(d_{32 }- d_{72})= -2 + 0 +4 = 2;\\
\Delta F_{38} =(r_{70 }- r_{50})(d_{34 }- d_{34}) + (r_{72 }- r_{52})(d_{31 }- d_{31}) + (r_{74 }- r_{52})(d_{32 }- d_{82})= -3 + 0 +0 = -3.$$
Так как $$\Delta F_{36 }$$ получилось наибольшим положительным, то меняем местами $$х_{7 }$$ и $$х_{3}$$.
(рис 20.7) Перемещение элементов х7 и х3$$\Delta F_{36} = (r_{30 }- r_{70})(d_{34 }- d_{64}) + (r_{32}-r_{72})(d_{31 }- d_{61}) + (r_{34 }- r_{74})(d_{32 }- d_{62}) = 1 - 3 - 6 = -8,$$
переходим к следующему шагу.
Четвертый шаг.
$$\Delta F_{56} = (r_{10 }- r_{70})(d_{54} - d_{64}) + (r_{13} - r_{73})(d_{53} - d_{63}) + (r_{14} -r_{74})(d_{52} - d_{62}) + (r_{12} -r_{72})(d_{51} - d_{61}) = -2 - 1 + 0 + 0 = -3\\
\Delta F_{57 }= (r_{10} - r_{60})(d_{54} - d_{74}) + (r_{13} - r_{63})(d_{53} - d_{73}) + (r_{14} - r_{64})(d_{52} - d_{72}) + (r_{12} - r_{62})(d_{51} - d_{71}) = -6 - 2 + 2 = - 6\\
\Delta F_{58} = (r_{10} - r_{50})(d_{54 }- d_{34}) + (r_{13} - r_{53})(d_{53} - d_{83}) + (r_{14} - r_{54})(d_{52} - d_{82}) + (r_{12} - r_{52})(d_{51} - d_{81}) = -9 + 0 + 0 + 0 = -9$$
Элемент $$х_{1}$$ остаётся неизменным.
(рис 20.8) Размещение элементов на четвертом шагеПятый шаг.
$$\Delta F_{67} = (r_{70} - r_{60})(d_{64} - d_{74}) + (r_{71} - r_{61})(d_{65}- d_{75}) + (r_{73} - r_{63})(d_{63} - d_{73}) + (r_{74} -r_{64})(d_{62} - d_{72}) + (r_{72} - r_{62})(d_{61} - d_{71}) = -1 + 0 + 0 + 1 + 0 = 0;\\
\Delta F_{68 }= (r_{71} - r_{51})(d_{65} - d_{85}) + (r_{70} - r_{50})(d_{64} - d_{34}) + (r_{73} - r_{53})(d_{63} - d_{83}) + (r_{74} - r_{54})(d_{62}- d_{82}) + (r_{72} -r_{52})(d_{61} - d_{81}) = 0 - 2 + 2 +0 + 0 = 0.$$
Оставляем $$х_{7}$$ в позиции 6.
(рис 20.9) Размещение элементов на пятом шагеШестой шаг.
$$\Delta F_{78} = (r_{67} - r_{57})(d_{76} - d_{86}) + (r_{61} - r_{51})(d_{75}- d_{85}) + (r_{60} -r_{50})(d_{74} - d_{84}) + (r_{63} - r_{53})(d_{73} - d_{83}) +\\ (r_{64} -r_{54})(d_{72} - d_{82}) + (r_{62} -r_{52})(d_{71} - d_{81}) = -1 + 1 - 1 = -1.$$
Получили отрицательное число, следовательно, перестановку элементов не производим.
В результате получили окончательное размещение
(рис 20.10) Окончательное размещение элементовРассчитаем критерий размещения после использования итерационного алгоритма
$$L' = 1/2 \sum{\sum{ r_{ij}d_{p(i)p(j)}}}.$$
Для этого вычислим минимальную суммарную взвешенную длину связей между позициями:
$$L
= r_{24}d_{12}+ r_{23}d_{13}+ r_{20}d_{14}+ r_{21}d_{15}+ r_{27}d_{16}+ r_{26}d_{17}+ r_{25}d_{18}+ r_{43}d_{23}+ r_{40}d_{24}+ \\
+ r_{41}d_{25}+ r_{47}d_{26}+ r_{46}d_{27}+ r_{45}d_{28}+ r_{30}d_{34}+ r_{31}d_{35}+ r_{37}d_{36}+ r_{36}d_{37}+ r_{35}d_{38}+ \\
+ r_{01}d_{45}+ r_{07}d_{46}+ r_{06}d_{47}+ r_{05}d_{48}+ r_{17}d_{56}+ r_{16}d_{5 }+ r_{15}d_{58}+ r_{76}d_{67}+ r_{75}d_{68}+ \\
+ r_{65}d_{78} = 25\text{ (условных единиц)}.$$
Значение МСВД уменьшилось. Это свидетельствует о том, что данный метод помог улучшить размещение элементов.
Контрольные вопросы
Что относится к метрическим параметрам конструкции узлов и схем?
Что относится к топологическим параметрам конструкции узлов и схем?
Что является главной целью размещения?
Как рассчитывается главный критерий размещения?
Что является вариантами коммутационного поля?
Дайте общую характеристику алгоритмов размещения.
Как рассчитывается матрица длин D?
Как решается задача квадратичного назначения?
Какие предположения делают при решении задачи минимизации СВД?
Расскажите о работе последовательного алгоритма размещения по связности.
Что является мерой связности двух элементов?
Как осуществляется выбор элементов в последовательном алгоритме?
Как рассчитывается характеристика абсолютной связности?
Как рассчитывается характеристика относительной связности?
Как осуществляется выбор позиции в последовательном алгоритме размещения?
Поясните структуру итерационного алгоритма.
Как работает итерационный алгоритм парных перестановок?
