КТОП теория

Конструктивные алгоритмы (например, последовательный метод связывания пар, или последовательно-параллельный метод расширения ядер) формирует размещение, начиная от некоторого заданного элемента (контактов МС), последовательным добавлением элементов с учетом критерия оптимальности и заданных ограничений до тех пор, пока все элементы не будут установлены. Конфигурация размещения при использовании конструктивных алгоритмов определяется только после полного завершения работы алгоритма.

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

Задача оптимизации в полном объеме ставится как линейное или квадратичное назначение с введением весовых коэффициентов в функцию критерия качества

где к1, к2 – весовые коэффициенты, учитывающие важность используемого критерия качества (выбирается эвристически); сij – элемент матрицы

стоимости С = [cij] назначения i-го компонента на j-ю позицию; d p(i)p(j) – элементы матрицы расстояний D = d [l, h] , вычисленные с учетом принятой

метрики; aip(i) –элементы стоимости назначения по другому критерию; p –

заданная перестановка элементов. Если матрицы C и D симметричны, то квадратичная задача назначения (при к2 = 0) часто формулируется

следующим образом: найти перестановку р, которая минимизирует функционал

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

9.2. Пример линейного размещения элементов

Как пример простого алгоритма решения задачи размещения, рассмотрим конструктивный алгоритм «обратного размещения». В этом методе задается матрица соединений элементов и матрица расстояний между позициями. Для каждого элемента рассчитывается по матрице С суммарное число соединений с остальными элементами

n

{ci =Σ cij , I = 1,2,…,n} (cij = 0 при i = j),

j=1

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

n

{di = Σdij , i = 1,2,…, n} (d ij = 0 при i = j).

j=1

Очевидно, что центральные позиции монтажного пространства, имеющие меньшее значения di, наиболее благоприятны для расположения сильно

связанных элементов, имеющих большие значения сi. Минимизируя функцию

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

1.Элементы сортируют по возрастанию характеристики ci (ci1 ≤ci2 ≤ …≤cin).

2.Позиции сортируют по убыванию характеристики dj (dj1 ≥dj2 ≥…≥djn).

3.Правило размещения определяется перестановкой p(ik) = jk, k = 1, 2,…, n.

Таким образом, на «лучшие» позиции устанавливаются «худшие» элементы. Пример выполнения рассмотренного алгоритма размещения (рис. 9.1.).

{di} (рис. 9.1) имеется ряд вариантов размещения, первый из которых (в

соответствии с порядком следования элементов после сортировки) приведен на рис. 9.1,б. Этот вариант понижает критерий оптимальности от F = 197 (рис.9.1,г) до F = 179 (рис. 9.1, д). Однако наилучшим является вариант размещения на рис. 9.1,е (F = 170) [1].

Рис. 9.1. Пример применения алгоритма обратного размещения: а - матрица соединений С и множество {ci}, полученное суммированием по

строкам С, матрица расстояний ─ D и множество {dj}, полученное суммированием по строкам;

Рис. 9.1. Пример применения алгоритма обратного размещения:

б – определение расстановки элементов установлением соответствия элементов {ci} и {dj} согласно алгоритму; в – пронумерованные пустые

позиции для расстановки элементов; г – начальное размещение; д – размещение в соответствии с полученным на рис. 9.1, б результатом; е – оптимальное размещение.

Пояснение: расчет функционала F ведется по формуле

F = ∑cij d p(i)p(j) , i<j

где сij – элементы матрицы стоимости равное числу соединений,

dp(i)p(j) − элементы матрицы расстояний, p – перестановка элементов.

9.3. Последовательные алгоритмы размещения

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

Позиции некоторых элементов могут быть заранее указаны разработчиком, исходя из схемотехнических требований. Например, элементы с большим коэффициентом разветвления следует располагать в первом ряду от выходных контактов платы субблока. Если фиксированных элементов нет, то должно быть задано правило выбора начального элемента и позиции его установки.

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

Оценка степени связности производится таким образом. Пусть на k-м шаге

алгоритма размещено элементов. Множества элементов Е и установочных позиций М распадаются на непересекающиеся подмножества размещенных элементов и занятых ими позиций E к, M к и не размещенных элементов и свободных позиций Еn и Мn соответственно. Основными решающими правилами для выбора элемента на (к+1)-м шаге алгоритма являются максимумы: связности с предыдущими размещенными элементами, суммарной связности со всеми размещенными элементами, разности связей с размещенными и не размещенными элементами.

Выбор позиции для установки очередного элемента должен вести к минимизации критерия размещения. При использовании критерия минимума суммарной длины соединений наиболее простой оценкой качества позиции является часть “цены назначения” i-го элемента в j-ю позицию, отражающая суммарную длину его связей с уже размещенными элементами, в том числе и с контактной группой.

Последовательный алгоритм размещения по мультиграфу схемы. Исходные данные для алгоритма, основанного на рассмотренных выше правилах выбора элемента и позиции его установки, − матрицы С и Dr , вектор взвешенных связей элементов с внешними выводами H, множества индексов размещенных и не размещенных элементов Jk и Jn , множества индексов занятых и свободных позиций Мк и Мn .