АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. Алгоритмы
  2. Алгоритмы диагностирования и методы их построения
  3. Алгоритмы обхода дерева
  4. Алгоритмы поиска дефектов
  5. Алгоритмы упорядочивания элементов в массивах
  6. Алгоритмы электронной цифровой подписи
  7. Анализ размещения капитала предприятия
  8. Анализ состава оборотных средств и их размещения
  9. Асимметричные криптоалгоритмы
  10. Аудит привлечения и размещения межбанковских кредитов
  11. Введение в стандартную библиотека шаблонов (STL): контейнеры, алгоритмы, итераторы.
  12. Выбор размещения видов деятельности

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

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

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

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

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

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

Рис. 6.1.

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

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

П. 1.

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

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

П. 1.1.

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

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

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

 

П. 2.

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

Модуль e5 имеет максимальную оценку, равную +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 часто используется не модель ВНГ а модель ГГ в этом случае при определении позиции можно учесть взаимное расположение элемента в цепи, а также использовать в качестве оценки для позиции критерий минимизации многоугольника охватывающего элементы цепи.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |

Поиск по сайту:



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