20. Постановка задачи размещ при конструир типовых элементов эвм. Критерии оптимизации

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

Т.к очень много факторов влияет на решение задачи, то она разбивается на два этапа: размещение и трассировка.

Сначала размещение, потом трассировка. Исходные данные:1.Схема соед эл-ов. 2.Метрические параметры и топологические свойства монтажного пространства.

Имеем множ-во эл-ов и множ-во цепей. Монтажное пространство определяется множеством фиксированных позиций. Необходимо найти такое отображение множества элементов во множество позиций, при кот достигается максимум ЦФ.

Критерий оптимизации: 1.Мин суммарная длина всех соед или длина самой длинной связи. 2.Мин число пересеченных связей. 3.Максимиз числа цепей с простой конфигурацией. 4.Макс близкое расположение модулей, имеющих наиб колво связей между собой.

Для N элементов и M позиций сущ множво А={al/l=1,L} возможных размещений.

L=M!/(M-N)! при M>N.

L=M! при M=N.

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

rij=∑Pq , где |Qij| - число цепей, в кот входные элементы ei и ej.

Pq=1/(pq-1) – вес q-й связи

pq – количество элементов, соединенных q-й связью.

Мат мод монтаж пространства–это граф решетки Gr.

Расст между позициями установки опред матрицей расстояний этого графа Dr как правило, внешним выводам сопоставляется элемент e_0. Соединения с внешним выводом учтем вектором – столбцом взаимных связей H={hi/i=1,N}. Внешние выводы обычно фиксированы на периферии входных конструкций.

Внешние выводы фиксир на перифирии типовой конструкции. mi - № верш ряда, где располож ei эл-нт.

Обозначим mi номер вероятностного ряда, где располаг элементы ei. Тогда для некот размещения сумм взвешенная длина соединения L(a) будет вычисляться

L(a)=1/2 *∑∑Ni,j di,j + ∑hi mi

Di,j – эл-нт матрицы расстояний Dr (расст между ei и ej)

1/2 *∑∑Ni,j di,j – полусумма эл-ов матрицы эл-ов Dγ

∑hi mi – расс до разъема Требуется найти L(a) на множестве размещений А.

Мат мет реш данной задачи явл метод ветвей и границ.

21. Последовательные алгоритмы размещения конструктивных элементов. Улучшение размещения перестановкой модулей.

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

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

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

1.связности с предыд размещенным элтом. 2.суммарной связности со всеми размещенными элтами. 3.разности связей с размещенными и неразмещенными элементами.

Улучшение размещения перестановкой модулей

Идея та же что и у итерационных алгоритмов улучшения компоновки. Для улучш некот нач размещ меняются местами те элты, перестановка кот приводит к оптимиз критерия качва. Процесс заканчивается, если не сущ перестановок, кот улучшили бы критерий кач-ва на очередном шаге. Итерационный алг парных перестановок соотв замене в матрице R соответствующих строк и столбцов при перестановке элементов ei и ej.

Далее подсчитывается приращения функционала, ∆L=Lk-1-Lk, где L-взвешенная суммарная длина соед.