Полупроводниковые микросхемы. Многокристальная и однокристальная микросхема. Гибридно-плёночные микросхемы, страница 12

. Если все bij ≤ 0, то смысла переставлять эти вершины нет. Если есть положительные, то выбираются max bij и эти вершины меняются местами. И все начинается сначала (вычисляется α и т. д.)

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

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

Алгоритм размещения делятся на:

1. алгоритмы размещения математических задач, являющимися моделями задачи размещения

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

3. итерационные алгоритмы улучшения размещения

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

Метод ветвей и границ.

Все множество допустимых решений разбивают на подмножества, для каждого подмножества вычисляется нижняя граница функционала (самое меньшее значение), отбрасываются F(p2) … F(pi) и ищется только в F(p1). Потом F(p1) разбивается на подмножества и так же ищется минимальное значение, остальные отбрасываются и т. д. Цель – сократить перебор. Все модификации этого метода отличаются способом разбиения множества допустимых решений на подмножества и способом вычисления нижней границы.

Способ разбиения на подмножества.

Первый  элемент попадает во все позиции, это и есть подмножества и т. д.

Вычисление нижней границы. Если есть 2 вектора r{r1, r2, …, rm) и d {d1, d2, … , dm). -  принимает минимальное значение, если эти вектора упорядочены по – разному (r  - по возрастанию, d – по убыванию или наоборот).

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

Пошаговый алгоритм – на каждом шаге точно один элемент помещается точно в одну позицию. На каждом шаге решаются 2 задачи: а) выбор элемента; б) выбор позиции для размещения этого элемента. Пусть к к-ому шагу размещено Ек элементов.

+ простота

- последовательный (ищет место для конкретного элемента на заботясь об остальных).

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

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

Простейший алгоритм – алгоритм парных перестановок. Критерий minmax eij – длина между  ij. Если eij уменьшалось, то выбирается новое размещение. Если eij не уменьшалось, но количество максимумов уменьшалось - то перестановка удачная. Если нет, то размещение остается прежним. Далее выбираются другие точки. Если 4 попытки не дают результата, то итерации завершаются.

Улучшение eij от 1% до 50%.

Максимальный эффект дают первые 5 итераций

Алгоритм групповых перестановок (а. Штейнера).

Пусть w = (e1; e2; …;ek) – внутренне устойчивое множество элементов (элементы между собой не связаны). То есть их положение не влияет на другие элементы. Можно составить матрицу А = || aij || k*k

Pk- позиции, не которых стоят элементы. Можно посчитать суммарную длину для каждого элемента.

W’ – следующее внутренне устойчивое множество и тоже самое.

Трудоемкость ~O (m³), где m = max (W) – мощность max W.

Непрерывно-дискретные алгоритмы размещения. Есть непрерывное поле (нач. размещения нет).

ei и ej материальные точки, между которыми есть силы притяжения и отталкивания. - сила притяжения,  - сила отталкивания

Для каждого элемента – дифур, описывается движение материальной точки в положении равновесия. Для каждой точки решение – ее координаты. И далее эти точки располагают на узлы сетки с минимальным искажением.