Навигация
3. АЛГОРИТМЫ РАЗМЕЩЕНИЯ
Исходной информацией при решении задач размещения являются: данные о конфигурации и размерах коммутационного пространства, определяемые требованиями установки и крепления данной сборочной единицы в аппаратуре; количество и геометрические размеры конструктивных элементов, подлежащих размещению; схема соединений, а также ряд ограничений на взаимное расположение отдельных элементов, учитывающих особенности разрабатываемой конструкции. Задача сводится к отысканию для каждого размещаемого элемента таких позиций, при которых оптимизируется выбранный показатель качества и обеспечивается наиболее благоприятные условия для последующего электрического монтажа. Особое значение эта задача приобретает при проектировании аппаратуры на печатных платах.
Основная сложность в постановке задач размещения заключается в выборе целевой функции. Связано это с тем, что одной из главных целей размещения является создание наилучших условий для дальнейшей трассировки соединений, что невозможно проверить без проведения самой трассировки. Любые другие способы оценки качества размещения (минимум числа пересечений ребер графа, интерпретирующего электрическую схему соединений, разбиение графа на минимальное число плоских суграфов и т.д.), хотя и позволяют создать благоприятные для трассировки условия, но не гарантируют получение оптимального результата, поскольку печатные проводники представляют собой криволинейные отрезки конечной ширины, конфигурация которых определяется в процессе их построения и зависит от порядка проведения соединений. Следовательно, если для оценки качества размещения элементов выбрать критерий, непосредственно связанный с получением оптимального рисунка металлизации печатной платы, то конечный результат может быть найден только при совместном решении задач размещения, выбора очередности проведения соединений и трассировки, что практически невозможно вследствие огромных затрат машинного времени.
Поэтому все применяемые в настоящее время алгоритмы размещения используют промежуточные критерии, которые лишь качественно способствуют решению основной задачи: получению оптимальной трассировки соединений. К таким критериям относятся: 1) минимум суммарной взвешенной длины соединений; 2) минимум числа соединений, длина которых больше заданной; 3) минимум числа пересечение проводников; 4) максимальное число соединений между элементами, находящимися в соседних позициях либо в позициях, указанных разработчиком; 5) максимум числа цепей простой конфигурации.
Наибольшее распространение в алгоритмах размещения получил первый критерий, что объясняется следующими причинами: уменьшение длин соединений улучшает электрические характеристики устройства, упрощает трассировку печатных плат; кроме того, он сравнительно прост в реализации.
В зависимости от конструкции коммутационной платы и способов выполнения соединений расстояние между позициями установки элементов подсчитывается по одной из следующих формул:
, ,
В общем виде задача размещения конструктивных элементов на коммутационной плате формулируется следующим образом. Задано множество конструктивных элементов R={r1,r2,…,rn} и множество связей между этими элементами V={v1,v2,…,vp}, а также множество установочных мест (позиций) на коммутационной плате T={t1,t2,…,tk}. Найти такое отображение множества R на множестве T, которое обеспечивает экстремум целевой функции
, где cij – коэффициент взвешенной связности.
Силовые алгоритмы размещения
В основу этой группы алгоритмов положен динамический метод В.С. Линского. Процесс размещения элементов на плате представляется как движение к состоянию равновесия системы материальных точек (элементов), на каждую из которых действуют силы притяжения и отталкивания, интерпретирующие связи между размещаемыми элементами. Если силы притяжения, действующие между любыми двумя материальными точками ri и rj пропорциональны числу электрических связей между данными конструктивными элементами, то состояние равновесия такой системы соответствует минимуму суммарной длины всех соединений. Введение сил отталкивания материальных точек друг от друга и от границ платы исключает возможность слияния двух любых точек и способствует их равномерному распределению по поверхности монтажного поля. Чтобы устранить возникновение в системе незатухающих колебаний, вводят силы сопротивления среды, пропорциональные скорости движения материальных точек.
Таким образом, задача оптимального размещения элементов сводится к нахождению такого местоположения точек, при котором равнодействующие всех сил обращаются в нуль.
К достоинствам данного метода относятся возможность получения глобального экстремума целевой функции, а также сведение поиска к вычислительным процедурам, для которых имеются разработанные численные методы.
Недостатками являются трудоемкость метода и сложность его реализации (подбора коэффициентов для силовых связей); необходимость фиксирования местоположения некоторого числа конструктивных элементов на плате для предотвращения большой неравномерности их размещения на отдельных участках платы.
Итерационные алгоритмы размещения
Итерационные алгоритмы имеют структуру, аналогичную итерационным алгоритмам компоновки, рассмотренным ранее. В них для улучшения исходного размещения элементов на плате вводят итерационный процесс перестановки местами пар элементов.
В случае минимизации суммарной взвешенной длины соединений формула для расчета изменения значения целевой функции при перестановке местами элементов ri и rj, закрепленных в позициях tf и tg, имеет вид:
,
где p и h(p) – порядковый номер и позиция закрепления неподвижного элемента rp. Если , то осуществляют перестановку ri и rj, приводящую к уменьшению целевой функции на , после чего производят поиск и перестановку следующей пары элементов и т.д. Процесс заканчивается получением такого варианта размещения, для которого дальнейшее улучшение за счет парных перестановок элементов невозможно.
Использование описанного направленного перебора сокращает число анализируемых вариантов размещения (по сравнению с полным перебором), но приводит к потере гарантии нахождения глобального экстремума целевой функции.20
Алгоритмы дано группы характеризуются достаточно высоким быстродействием. Алгоритмы с групповыми перестановками элементов на практике используются редко ввиду их сложности, которая часто не оправдывает достигаемую степень улучшения результата.
Последовательные алгоритмы размещения
Последовательные алгоритмы основаны на допущении, что для получения оптимального размещения необходимо в соседних позициях располагать элементы, максимально связанные друг с другом. Сущность этих алгоритмов состоит в последовательном закреплении заданного набора конструктивных элементов на коммутационной плате относительно ранее установленных. В качестве первоначально закрепленных на плате элементов обычно выбирают разъемы, которые искусственно «раздвигают» до краев платы. При этом все контакты разъемов равномерно распределяются по секциям (столбцам и строкам координатной сетки). На каждом l-ом шаге (l=1,2,…,n) для установки на коммутационную плату выбирают элемент из числа еще не размещенных, имеющий максимальную степень связности с ранее закрепленными элементами Rl-1. В большинстве используемых в настоящее время алгоритмов оценку степени связности производят по одной из следующих формул:
;
,
где cij – коэффициент взвешенной связности элементов i и j; Jl-1 – множество индексов элементов, закрепленных на предыдущих l-1 шагах; n – общее число размещенных элементов.
Если установочные размеры всех размещаемых на плате элементов одинаковы, то выбранный на очередном шаге элемент закрепляют в той позиции из числа незанятых, для которой значение целевой функции с учетом ранее размещенных элементов Rl-1 минимально. В частности, если критерием оптимальности является минимум суммарной взвешенной длины соединений, то
,
где dfj – расстояние между f-ой позицией установки элемента и позицией размещенного ранее элемента rj; Tl-1 – множество позиций, занятых элементами после (l-1)-го шага алгоритма.
Процесс размещения алгоритма заканчивается после выполнения n шагов алгоритма.
Алгоритмы, использующие последовательный процесс закрепления элементов в позициях, являются в настоящее время самыми быстродействующими. Однако по качеству получаемого решения последовательные алгоритмы уступают итерационным. Поэтому их используют обычно для получения начального размещения элементов на плате.
Похожие работы
... приводится в графической части. 3. ТРАССИРОВКА МОНТАЖНЫХ СОЕДИНЕНИЙ. 3.1 Трассировка с помощью алгоритма Прима На основании полученных ранее данных и требований задания проведем трассировку общего провода цепи питания печатной платы блока оперативной памяти методом Прима. Для этого приведём необходимый участок печатной платы в сетке с шагом 5. Вывод 1 разъёма должен быть соединён с выводами 7 ...
... на ней корпусами микросхемы (см Приложение 2). Выбирается произвольная точка, которая служит началом координат Рис. 11. Корпус микросхемы Рис. 12. Соответствие логических выводов микросхемы выводам корпуса 5. Согласно полученному эскизу печатной платы каждому выводу корпуса назначается своя координата относительно начала координат. Рис. 13 Матрица D до начала выполнения ...
... Рис.6 3. Трассировка цепей питания и земли Трассировка – прокладка электрических трасс (проводов при проводном монтаже и печатных соединений при печатном монтаже), соответствующих принципиальной электрической схеме. 3.1 Краткое описание алгоритма Краскала В алгоритме Краскала кратчайшую связывающую сеть (КСС) строят путем последовательного присоединения к ним ребер, удовлетворяющих ...
... УЛПМ-901. 11 Визуальный контроль качества сборки при увеличении 2,5. ГГ6366У/012. Маршрутная карта на техпроцесс изготовления печатной платы приведена в приложении. 8 ТЕХНИКО-ЭКОНОМИЧЕСКОЕ ОБОСНОВАНИЕ ДИПЛОМНОГО ПРОЕКТА 8.1 Характеристика изделия «Модуль управления временными параметрами». Обоснование объема производства и расчетного периода Модуль управления временными параметрами – ...
0 комментариев