Алгоритмы размещения элементов

Лекция 8

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

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

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

Если элементы конструктивно однотипны, например, микросхемы, то позиции для их размещения фиксированы и находятся в узлах прямоугольной решетки, для которой задается:

- n_x– число позиций в горизонтальном ряду;

- n_y– число позиций в вертикальном ряду;

- h_x– горизонтальный шаг между позициями;

- h_y– вертикальный шаг между позициями;

Могут задаваться, при необходимости, координаты контактных площадок.

Если элементы разногабаритные, то позиции не фиксируются.

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

Длина соединений подсчитывается по формулам:

	(8.1)	эвклидова метрика
	(8.2)	ортогональная метрика
	(8.3)

S=2, 3, - для минимизации наиболее длинных соединений, т.к. они дадут наибольшее приращение.

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

Наиболее часто используются следующие алгоритмы решения задачи размещения:

1. конструктивные алгоритмы начального размещения;

2. итерационные алгоритмы улучшения начального варианта размещения;

3. непрерывно-дискретные методы размещения;

4. алгоритмы, основанные на решении задач математического программирования.