Конструктивные алгоритмы размешения

Среди конструктивных алгоритмов размещения выделяют последовательные и параллельно-последовательные алгоритмы.

В последовательном алгоритме используется n –шаговый процесс принятия решения. На каждом шаге здесь размещается один элемент. В параллельно-последовательном алгоритме на каждом шаге размещается группа элементов (или даже все элементы).

Среди последовательных алгоритмов различают последовательные алгоритмы размещения по связности и матричные алгоритмы.

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

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

где c_ij – элемент матрицы смежности ВНГ; – соответственно множества размещенных и неразмещенных на k –м шаге алгоритма модулей.

Задача размещения при этом сводится к максимизации оценки (6.1) по всем модулям, принадлежащим множеству .

Далее для выбранного модуля находится наиболее приемлемая позиция на плате. Для выбора такой позиции используется критерий минимальности длины связей размещаемого модуля с уже размещенными модулями. При этом, очевидно, нет необходимости рассматривать все незанятые на этом шаге позиции, а достаточно оценить лишь множество позиций, соседних с занятыми. При этом позиция p_i, в которую необходимо поместить i –й модуль, определяется из условия минимизации следующего выражения:

где c_ij – элемент матрицы смежности ВНГ; R^k –множество позиций, соседних с занятыми, на k –м шаге.

Рассмотрим работу последовательного алгоритма размещения по связности на примере (рис. 6.1).

Рис. 6.1.

Пусть элемент e₂ директивно помещается в 6-ю позицию, элемент e₃ директивно помещается в 9-ю позицию.

Чтобы выбрать очередной размещаемый модуль, необходимо в соответствии с (6.1) найти модуль с максимальной оценкой J.

П. 1.

Вычисляем оценки по связности для каждого неразмещенного модуля:

Элементы e₁ и e₅ имеют максимальную оценку, равную +1. Для дальнейшего анализа выбираем элемент e₁ (с меньшим порядковым номером).

П. 1.1.

Модуль e₁ в соответствии с (6.2) размещаем во 2-ю позицию (с меньшим порядковым номером) (см. ниже).

Определим F, предполагая, что модуль e₁ размещен

Окончательно размещаем e₁ во 2-ю позицию (с меньшим порядковым номером) и корректируем массив соседних позиций.

П. 2.

Определим следующий модуль для размещения.

Модуль e₅ имеет максимальную оценку, равную +1. в соответствии с (6.2) он помещается в 5-ю позицию.

И т. д. и т. п.

Окончательный вариант размещения представлен на рис. 6.2.

Рис. 6.2.

Укрупненная схема последовательного алгоритма размещения приведена на рисунке 6.3.

Рис. 6.3. Схема последовательного алгоритма размещения.

Замечание: соседние позиции.  

Приведем краткий перечень идентификаторов для реализации последовательного алгоритма размещения.

L – число элементов;

D – число директивных элементов;

M – число позиций по горизонтали;

N – число позиций по вертикали;

E(I) – массив директивных элементов;

P(I) – массив директивных позиций;

POS(LI) – номер позиции, в которую размещается элемент с номером LI;

Z(I) – массив соседних позиций;

SP1 – список элементов, связанных с данным элементом;

SP2 – список количества связей между элементами;

RSP – список, устанавливающий связность SP1 и SP2.

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

Учтем, что списки имеют вид SP1=(2,4,9), SP2=(1,1), RSP(1)=0, RSP(1+1)=1, RSP(2)=3 от E(1) переходим к E(4).

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

Дата добавления: 2014-01-14