Л1-Савельев, Овчинников - Конструирование ЭВМ и систем - 1984 год (999411), страница 42
Текст из файла (страница 42)
Р ассмотрим постановку задачи размещения как задачи квадратичного назначения при использовании критерия минимума суммарной взвешенной длины соединений. Будем считать, что соединения исходят из геометрических центров конструктивных элементов, метрика— ортогональная, расстояния между соседними позициями по горизонтали и вертикали одинаковые. Тогда математической моделью монтажного пространства является граф решетки 6„, а расстояния между позициями установки элементов Т будут определены матрицей расстояний этого графа 0„(см. 5' 8.3).
В к ачестве математической модели схемы используем взвешенный неориентированный мультиграф, в котором 'элементам схемы сопоставлены вершины, а каждая цепь представляется полным подграфом. Связность элементов схемы задается матрицей соединений К, элемент Ен ! гс ! == ~~'., Рд (10.2) д=! Для некоторого размещения суммарная взвешенная длинасоедииений л! л! л~ Е (а) = — ~~~~ У г;; 5(5, Т-т- "' й! 5п5, (10.3) ! —.1 !': —.
! ': — ! где а!из — элемент матрицы 0„определяет расстояние между пози- циями установки конструктивных элементов е! и е;; пТ! — номер вер- тикального ряда, в котором расположен элемент е; (рис. 10.1), Г ! ! ! ! ! Рве. 10.1. Модель поля рвзме- шояия платы субблока Ряс. !Охв Фрагмент схемы (а), кусок графа (б) и представлекие цепей схемы лесом Т (в) Отметим, что первый член выражения (10.3) соответствует полу- сумме элементов матрицы геометрии ).ху (см. 5'8.3). Теперь задача заключается в минимизации Е (а) на множестве размещений А.
Это один из вариантов задачи квадратичного назначения, точное решение которой возможно, например, методом ветвей и границ. Алгоритмы, реализующие этот метод, могут использоваться на практике при 1х' = 15 —;20. На рис. 10.2 показан фрагмент (а) схемы и кусок графа (б) этой схемы. Для подсчета элементов матрицы К цепи схемы представлены лесом на контурной сетке (рис.
10.2, в). Матрица связности 11 подграфа, входящего в кусок, и вектор. столбец Н имеют вид Х, Х! Х5 Хь Х5 Х5 кгр 0 1 0,5 0,5 0 0 1 0 2 0,5 0 5 1 0,5 2 0 0,5 0 0 0,5 0,5 0,5 0 1,5 2 0 0,5 0 1,5 0 2 0 1 0 2 2 0 2 1 2 1 1 2 й 1ВДС ПОСЛЕДОВАТЕЛЬНЫЕ АЛГОРИТМЫ РАЗМЕЩЕНИЯ (10.4) шах (г! 0); х.аь тах) э! г;;1; Хсзь 'я кл !пах 1 ~~ г5; — ~' г5;1, (10.5) — Т 5- !. где !л — - номер столбца матрицы )Т, соответствующий индексу послед- НЕГО РаЗМЕЩЕННОГО ЭЛЕМЕНта; /„И Х'ь - — МНОжЕСтВа 'ИНДЕКСОВ РаЗМЕ- щеииых и неразмещенных элементов, сопоставленных пх номерам из подмножеств Е„и Ел.
Выбор позиции для установки очередного элемента должен вести к минимизации критерия размещения. При использовании критерия мяиимума суммарной взвешенной длины соединений оценкой качества позиции может служить часть вцеиы назначения» 5-го элемента в 1-ю позицию„отражающая суммарную длину его связей с уже размещен- (10.5) 205 Решающее правило большинства последовательных алгоритмов размещения по связности основано на предположении, что наиболее связанные элементы следует распола~ать максимально близко друг к другу.
На каждом шаге алгоритма выбирается в соответствии с некоторой оценкой очередной элемент и позиция для его установки. Связность размещаемых элементов будем задавать матрицей К, а расстояние между позициями их установки — матрицей Р„. Позиции некоторых элементов могут быть заранее указаны разработчиком, исходя из схемотехнических требований. Если таких фиксированных элементов нет, то должно быть задано правило выбора начального элемента и позиции его установки. НаприМер, начальное размещение может быть получено установкой в центральную позицию элемента с максимальным числом связей или в ряду позиций, ближайших к контактной группе, элементов, имеющих максимальную связность с нею. Для выбора размещаемого элемента используют различные оценки степени связности.
Рассмотрим часть из них. Пусть на 55-м шаге алгоритма размещено Ех ~ Е элементов, т. е. имеется некоторое частичное размещение. Множества элементов Е и установочных позиций Т распадаются на непересекающиеся подмножества Е„, Тл — размещенных элементов и занятых ими позиций и Е„, Тх — неразмещенных элементов и свободных позиций. Основными решающими правилами для выбора элемента на (й Р 1)-м шаге алгоритма являются максимумы: связности с предыдущим размещенным элементом; суммарной связности со всеми размещенными элементами; разности связей с размещенными и веразмещенными элементами. Если для оценки связности элементов схемы используется матрипа взвешенных связей к!, то соответствующие решающие правила формулируются следующим образом: ными элементами, в том числе и с контактной группой.
Этот показатель Р1 = ~я~~ гь е с(Ь с Ш+ тейп и эа (10.7) где 1 (1) Е Т вЂ” индекс позиции 1-го размещенного элемента. Для размещения с'-го элемента среди незанятых позиций выбирается та, которая обеспечивает ппп( '~', «с; Ньс ш+ттйз). пата уэза (10.8) Исходными данными для алгоритма, основанного на рассмотренных выше правилах выбора элемента и позиции его установки, являются матрицы К и Р„, вектор взвешенныхсвязейэлементовсвнешнпми выводами Н, множества индексов разме- Я шенных и неразмещенных элементов е „и 7„, множества индексов занятых и сво- 9 $Щ бодных позиций Т„и Т„. Основные пункты алгоритма после- 141 довательного размещения по связности.
Я Е 1. По одному из решающих правил (10.4, 10.5, 10.6) находим индекс очередного размещаемого элемента, например 1«+~ = — гпах1 ~ гп11. ~п ~~а Рис, !0.3. Субблок с элемента ми кратных размсроа 2. Определяем позицию для установки этого элемента Ра« = и и) ","„г,13; и,>+т~й). Пэта ! 1еха 202 Здесь 1 =- 1»»,. 3. Заносим индекс элемента в массив е'„, а позиции †вмасс Т„, исключая их из массивов еа, Та: Уа == У„() 1, „; Уа =,(,;1,,,; Т, = Т, ())...; т„= там, ь, 4. Проверяем, все ли элементы размещены: ~У,,~ = М. Если условие выполняется, то переходим к и.
5, иначе — к и. !. 5. Конец работы алгоритма. Для сокрашения времени вычислений в и. 2 целесообразно исследовать те пз свободных позиций, которые находятся в окрестности занятых. В работе 131 отмечается, что аналогичные алгоритмы могут быть использованы для размещения разногабаритных элементов, размеры которых кратны или близки к кратным. Шаг установки элементов выбнраетси в соответствии с размерами наименьшего конструктивного элемента (рис. 10.3). Прп размещении элемента, у которого хотя бы один размер больше размера позицип, в алгоритме необходимо прове- Рпс. 10,4.
Предполагаемое оптимальное расположсапс псразмсшсппых »лсмсптоа еь ез, е, отпоситсльпо злсмспта е, 102 рять возможность установки элемента в рассматриваемую позицию. После размещения такого элемента в список занятых заносятся все покрываемые им позиции. Алгоритмы последовательного размещения по связности отличаются высоким быстродействием, но, как правило, приводят к результатам, далеким от оптимальных, Качество решения можно повысить, используя более точный показатель «цены назначения» элемента в некоторую позицию и соответствующую стратегию выбора элемента и позиции.
Таким показателем может служить нижняя граница функционала (10.3) при некотор пх частичном размещении. Упростим выражение для Т (а), отбросив в нем линейную часть. Составляющими этого функционала при частичном размещении являются суммы длин связей размещенных элементов между собой, размещаемого элемента с размещенными и неразмещенными, неразмещенных элементов с размещенными и друг с другом. Первая составляющая при каждом частичном размещении одинакова для всех установок элементов 1Е /а в позиции ~Е Т„.
При определении [е,~ ~еД ( ее) ( ез) «цены назначения» »что элемента в 7-ю позицию на я + 1-м шаге процесса размещения будем подсчитывать длину связей размещаемого элемента с размещенными и нижние границы длин связей размещаемого элемента с неразмещенными и неразмещенных элементов между собой. Нижняя граница суммарной длины связей 1-го элемента с иеразмещенными предполагает, что последние будут расположены оптимально относительно бго элемента, но не относительно друг друга.
Рассмотрим один из способов оценки нижних границ. Напомним, что элементы ~'-й строки матрицы К отражают связность 1-го элемента с остальными, а элементы )-й строки матрицы Ре — расстояние от 1-й позиции до друтих. Сумма поэлементного произведения бй строки матрицы К и 7-й строки матрицы Р„ без элементов ~-,, и е(п, равна суммарной длине связей этого элемента со всеми остальными при установке его в )'-ю позицию.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
