Android-приложение для поиска дешевых авиабилетов: play.google.com
Главная -> Печатный монтаж

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 [17] 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

странство между ними может быть занято соединениями между другими модулями. Тем не менее данный критерий находит широкое применение в существующих алгоритмах размещения, так как все-таки дает некоторые гарантии удачного решения задачи размещения.

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

Данный критерий в настоящее вре-мя широко применяется. Его существенное преимущество заключается в том, что алгоритмы, основанные на реализации этого критерия, просты и требуют малого времени для решения задачи размещения. З. Длина самой протяженной связи должна быть минимальна. Алгоритмы, построенные на базе этого критерия, стремятся так разместить узлы на плате, чтобы длина всех проводников стремилась к среднему значению. Основанием для рассматриваемого критерия служит то обстоятельство, что длинные трассы пересекают болыиее число путей прокладки проводников, мешая таким образом успешному решению задачи трассировки.

Данный критерий обычно используется в комбинации с другими основными критериями размещения.

4. Число пересечений связей минимально. Очевидно, что этот критерий качества определяет самую суть задачи размещения.

Однако для своей реализации он требует совместного решения задач размещения узлов и трассировки.

Эта проблема ставит непреодолимые трудности в необходимом машинном времени и объеме памяти запоминающих устройств (ЗУ) и современными алгоритмами не решается.

Однако в некоторых алгоритмах требования данного критерия качества учитываются.

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

1. Метод последовательной оптимизации, при котором начальная произвольная расстановка модулей на плате целенаправленно и последовательно улучшается в соответствии с принятым критерием качества.

2. Метод перестановки модулей, реализуемый перебором различных размещений до получения первого приемлемого решения. Если, например, в качестве критерия принята минимальная суммарная длина всех трасс L, то задача может решаться в следующей последовательности: вычисляется величина Lo для Начального размещения; затем переставляются два модуля и *нова вычисляется Ьй если L\<Lq, то эта ситуация фиксирует-

памяти ЦВМ. Подобный процесс выполняется заранее за-



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

3. Метод последовательного размещения узлов на плате, который применяется, как правило, при реализации второго критерия качества. В этом случаенервымразмещается 1мадуль,наи-более связанный с разъемом платы, затем модуль, наиболее связанный с первым модулем и разъемом. Этот процесс повторяется, пока не будут размещены все модули на плате.

Рассмотрим некоторые алгоритмы размещения функциональных узлов, применяемых в современных системах автоматизированного конструирования печатных плат. Действующие алгоритмы требуют для своей реализации в среднем 10-30 мин машинного времени для ЦВМ средней мощности (типа М-220, Урал-14 и т. д.).

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

rij=\Xi-Xj\ + \yi->ryj\.

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

Ln - суммарная длина всех связей между модулями после i-ro решения задачи размещения; Lq - суммарная длина всех связей между модулями при начальном размещении"; AL„ - . приращение суммарной длины всех связей на плате в результате выполнения п-го цикла решения задачи размещения; r,j - расстояние между модулями с номерами I и /; Кц - число связей между модулями с номерами i и /; - множество модулей на плате; № - множество неразмещенных модулей после п-го цикла решения задачи; - модуль, размещенный на п-ом шаге решения задачи; N - общее количество модулей на плате; D=i{Dj} - множество точек на плате, в которых размещаются модули; - множество свободных точек на плате после п шагов решения задачи размещения; - точка на плате, занятая модулем на п-ом цикле размещения; № - суммарная длина связей модуля Ei (точки D,) с остальными модулями- (точками на плате, в которых размещаются модули);

- связность модуля Ei.

Значение этой величины будет раскрыто при описании конкретных алгоритмов.



Алгоритм последовательной оптимизации размещения узлов на плате с помощью групповой перестановки

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

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

N (N~\) о

дулей, число которых равно----.Затем, из всего множества

перестановок, дающих отрицательные приращения, выделяется некоторое подмножество, которое должно удовлетворять условиям:

а) выбранное подмножество перестановок, позволяет максимально уменьшить суммарную длину всех связей;

б) любой модуль -может менять свое место только один раз;

в) в подмножество входят такие попарные перестановки, при которых модули, меняющиеся местами, не связаны ни с одним модулем из других пар.

Очевидно, что несоблюдение хотя бы одного из двух последних условий может ухудшить результат размещения по сравнению с первоначальным, так как при этом может произойти увеличение длины связей между модулями из разных пар.

Рассмотрим математическое обоснование описываемого алгоритма.

Если Vit есть расстояние между двумя модулями, а Ки - число связей между ними, то суммарная длина всех связей между . узлами Е{ и Et

,-.= г,Д,, (1.1)

Распространяя это выражение на все множество модулей, получаем следующее выражение для определения суммарной длины связей модуля со всеми остальными:

= (1.2)

Отсюда легко вычислить суммарную длину всех связей:

N N N

i=i 11 та"

Если выделить из всего множества модулей на плате модули * и Ej, то суммарная длина- связей этих модулей со всеми остальными определится, как



0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 [17] 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69



0.0167
Яндекс.Метрика