Л1-Савельев, Овчинников - Конструирование ЭВМ и систем - 1984 год, страница 41

9.11. Куска грлфоп Ог" л Ос* пе вершины графа схемы 6 в вер- тРстьем шаге Работы ээРпстического ллшины х», уже включенные в горитмл покрытия формируемый подграф 6>*с 1и (х„, х,)) — число ребер, заходящих в рассматриваемую х;-ю вершину из вершин х, включен ных в под На г-м шаге работы алгоритма для очередного элемента 1-го модуля аданного набора (вершины ус графа Н,) ищется аналогичный элеме ( ершина х; графа 6), имеюсций тот же тип и такие нт лементами, же в л е же связи с , уже включенными в подсхему, как и 1'-и элемент модуля лемента ' абора с его и-ми элементами (гг — 1, 1 -- 1).

Количество связей т схемы с элементами, ие включенными в подсхем, м " э ого ыть меньше ил и равно количеству связей )пго элемента модуля набо- ему, может ода и исхо а п . а с его Р-ми элементами (Р = 1' + 1, 1Уп и ГРавнение полс ступеней ва- ада позволяет исключить из рассмотрения элементы схемы, имеющие больш ьшее количество внешних связей, чем соответствующие элементы модуля набора. На рис. 9.11 показаны куски графов Нг и 6>* на третьем шаге работы алгоритма.

Около вершин в скобках цифрами обозначен тве верхнего индекса при вершинах, уже включенных в кусок 6>*, показаны их номера в графе 6. Множество вершин-кандидатов 495 Х; -- (х.з, х„, х,). Вершиной, Действнтельно: сз — --2, с(з=-5' Уч ' уз П У; =- (Уз)' г узП1 ! (Ум уз) ~, (у„у,) ! --. о; !. (Уз, уз)!=- 1; ! о (ум уз) ) = 1; ! о(ум Уз)! =2 аналогичной узи является только хзм аз„= 2, Ьзз =- 5; Р+ хзз П Х! =- (хз); У- х„ПХ,"=(хмхз); !и(х х!4)! О.

1и (хзз, хз) / =-1; ! и (х~!', х„) ! = — 1; ! и (хз хзз) ! = 2. Основные пункты эвристического алгоритма покрытия: 1. Проверяем по типам вершин возможность вложения гр ф и г афаИ в граф 6, т. е. (уу!Е У,) (Вх!Е Х) (1; -= 6). Если условие не выполняется, то переходим к и.

26, иначе — к и. 2. 2. Выделяем нз графа схемы подмножество вершин Х!ь которые удовлетворяют условию (вгх! 6= х:а х) ((1!=(,) !ь (а! (с;! !ь (ь, (с(з)1. 3. Текущую вершину х; ставим в соответствие вершине у, (х; = у!). 4. Если вершина эталона у; является по порядку первой (! — ), вой (' —. 1), то переходим к п. 21, иначе — к п. 5. 5. Определяем обратные отображения Г 'х; и Г 'у,.

6. ДлЯ очеРеДных веРшин Уха Г 'У; н хе 8 Р 'х! пРовеРЯем выполнение условия уд Е У!* ь; х„Е Х,", Если условие выполняется, то переходим к п. 8, иначе — к п. 7. 7. Проверяем выполнение условия уз 66 У! ь х„~ Х!. Е ловне выполняется, то переходим к п. 1О, иначе — к и. 20. 8. Проверяем выполнение условия !о (уы у,)1 -= ! и (х„, х;) 1. х, х) Если условие выполняется, то переходим к п.

9, иначе — к и. 20. 9. Подсчитываем общее количество связей рассматриваемых вер шин х! и У; с веРшинами ххах Х!* и Ув Е У!'! ! — ! 8!=- Ъ" ! и(~з, х!)(; в= ! ! — ! 8 = ~ !о(уз у!)!. 19. При невыполнении условия (9.31) по выходящим ребрам, переходим к п. 20. 20. Анализируем, все лн вершины из подмножества кандидатов Х просмотрены. Если все, то переходим к п.

24, иначе — к п. 3. 2!. Включаем вершину х; в формируемый подграф 6!", т, е. Х! =- = Х!'Ох; 22. Если подграф 6, не построен полностью, т, е, 1Х! ! ( 1У!!, то увеличиваем значение у на единицу и переходим к п. 2, иначе — к п. 23. 23. Подграф 6ь идентичный эталонному подграфу Нз, сформирован. Переходим к п. 27. 24. Возвращаемся на предыдущий (! — 1)-й шаг алгоритма. Проверяем условие ! — 1 -=- О.

Если условие выполняется, то переходим к п. 26, иначе — к п. 25. 25. Анализируем, все ли вершины нз подмножества Х; ! просмотрены. Если да, то переходим к и. 24, иначе выполняем пп. 4 — 20 для (! -- 1)-го шага алгоритма, т. е. ищем в графе схемы новую вершину хз, аналогичную вершине у; ! эталонного графа.

26. Подграфа, идентичного эталонному, в графе схемы нет. 27. Конец работы алгоритма. Для построения дерева решений предназначены пп. 24 н 25. Для сокращения числа ветвей (числа переборов) в п. 2 может быть наложено ограничение на число вершин в множестве Х,'. Алгоритм может быть использован для покрытия схем, построенных на многополюсниках но входу и выходу с неравнозначными выводами. Для этого в пп. 8 и 15 необходимо добавить проверку совпадения весов соответствующих ребер. 1О. Анализируем, все ли вершины из обратных отображений у; з — в н Р 'х; просмотрены.

Если нет, то переходим к п. 6, иначе — к че — к и. 11. 11. Для вершин у, и х; проверяем условие (9.31) по заходящим ребрам: (е(з — Яз) ~ (Ь; — 8;). Если условие не выполняется, то переходим к п. 20, иначе — к п. 12. 12 — 18. Повторяют пп. 5 — 11 для прямого отображения.

При выполнении условия (9,31) по выходящим ребрам переходим к п. !96 М я. Сввелвев, В. А. Овеввввв, в РАЗМЕЩЕНИЕ И ТРАССИРОВКА $«ВЛ. ПОСТАНОВКА ЗАДАЧИ РАЗМЕЩЕНИЯ. КРИТЕРИИ ОПТИМИЗАЦИИ В общем виде размещение заключается в определении оптимального в смысле некоторого критерия положения элементов и связей между ними в монтажном пространстве типовой конструкции. При этом должны быть удовлетворены заданные конструктивно-технологические ограничения. В такой постановке задача размещения может быть сформулирована как задача пелочисленного программирования, однако из-за большой размерности ее практическая реализация нецелесообразна.

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

Тогда задача размещения может быть сформулирована следующим образом. Имеется множество конструктивных элементов Е =- (е«Й =- 1, Л!) и множество соединяющих их цепей «,'! = («)!,Ог 1, К). Монтажное пространство определено множеством фиксированных позиций для установки элементов Т = («!!!' - 1, М), причем М ~ Л'. Найти такое отображение множества Е в множество Т, при котором достигается экстремум целевой функции Е. Главная пель размещения — создание наилучших условий для трассировки. Вследствие условности разделения задач размещения и трассировки трудно установить для задачи размещения такой критерий оптимизации, который в достаточной мере удовлетворял бы требованиям трассировки. В настоящее время используются следующие критерии: минимум суммарной длины всех соединений или длины са! мой длинной связи; минимум числа пересечений связей при произвольной их конфигурации; максимум числа цепей с возможно более простой конфигурацией; максимально близкое расположение модулей, имеющих наибольшее количество связей между собой.

Указанные критерии лишь качественно способствуют решению основной задачи: обеспечить оптимальную трассировку соединений. Од- 19В ним из наиболее распространенных является критерий минимума суммарной длины соединений в связи с тем, что при его оптимизации косвенно минимизируется длина связей и число их пересечений, снижаются искажения сигналов.

Для Л! элементов, которые могут быть установлены в М позиций, существует множество А =- (а!Д =- 1, Е) размещений. Количество их ( М1/(М вЂ” Л!)! при М ) Лг; (М! при М=.Л!, (10.1) которой отражает взвешенную связанность вершин х; е; и х, «-+ е,. десь ф ! — число цепей, в которые входят одновременно элементы е ие; ,; р „= 11 (р „--- ! ) — вес «)-й связи; р ч — количество элементов, соединяемых а-й цепью. Внешним выводам сопоставим элемент ео. Соединения с ними элементов из множества Е учтем вектором — столбцом взвешенных связей г) -. 1Л.!; ..

! Л!) М ==- (Ь! ! = 1, Л!). Монтажная область внешних выводов. обычно фиксирована на периферии типовой конструкции, т. е. расположение контактных площадок является заданным. Контактные площадки, кроме выводов питания и земли, — инвариантны, поэтому расстояние от элемента е! до внешних выводов можно приближенно определять как расстояние от вертикального (горизонтального) ряда, где установлен этот элемент, до контактной группы. ИР В связи с этим поиск оптимального варианта размещения полным перебором нецелесообразен уже при Л! =- 15 —;20.

В дальнейшем будем полагать, что М -- Л'. Если число элементов меньше числа позиций, можно ввести М вЂ” Л' фиктивных элементов. Различные алгоритмы размещения: згут быть сведены в следующие основные группы (см. (19)): алгоритмы решения задач математип ческого программирования, являющихся моделями задачи размещени; я; «оследовательные алгоритмы; итерационные алгоритмы; алгоритмы, использующие непрерывно-дискретные методы оптимизации.