Страница: 5/10
3. АЛГОРИТМЫ РАЗМЕЩЕНИЯ
Исходной информацией при решении задач размещения являются: данные о конфигурации и размерах коммутационного пространства, определяемые требованиями установки и крепления данной сборочной единицы в аппаратуре; количество и геометрические размеры конструктивных элементов, подлежащих размещению; схема соединений, а также ряд ограничений на взаимное расположение отдельных элементов, учитывающих особенности разрабатываемой конструкции. Задача сводится к отысканию для каждого размещаемого элемента таких позиций, при которых оптимизируется выбранный показатель качества и обеспечивается наиболее благоприятные условия для последующего электрического монтажа. Особое значение эта задача приобретает при проектировании аппаратуры на печатных платах.
Основная сложность в постановке задач размещения заключается в выборе целевой функции. Связано это с тем, что одной из главных целей размещения является создание наилучших условий для дальнейшей трассировки соединений, что невозможно проверить без проведения самой трассировки. Любые другие способы оценки качества размещения (минимум числа пересечений ребер графа, интерпретирующего электрическую схему соединений, разбиение графа на минимальное число плоских суграфов и т.д.), хотя и позволяют создать благоприятные для трассировки условия, но не гарантируют получение оптимального результата, поскольку печатные проводники представляют собой криволинейные отрезки конечной ширины, конфигурация которых определяется в процессе их построения и зависит от порядка проведения соединений. Следовательно, если для оценки качества размещения элементов выбрать критерий, непосредственно связанный с получением оптимального рисунка металлизации печатной платы, то конечный результат может быть найден только при совместном решении задач размещения, выбора очередности проведения соединений и трассировки, что практически невозможно вследствие огромных затрат машинного времени.
Поэтому все применяемые в настоящее время алгоритмы размещения используют промежуточные критерии, которые лишь качественно способствуют решению основной задачи: получению оптимальной трассировки соединений. К таким критериям относятся: 1) минимум суммарной взвешенной длины соединений; 2) минимум числа соединений, длина которых больше заданной; 3) минимум числа пересечение проводников; 4) максимальное число соединений между элементами, находящимися в соседних позициях либо в позициях, указанных разработчиком; 5) максимум числа цепей простой конфигурации.
Наибольшее распространение в алгоритмах размещения получил первый критерий, что объясняется следующими причинами: уменьшение длин соединений улучшает электрические характеристики устройства, упрощает трассировку печатных плат; кроме того, он сравнительно прост в реализации.
В зависимости от конструкции коммутационной платы и способов выполнения соединений расстояние между позициями установки элементов подсчитывается по одной из следующих формул:
, 
, 
В общем виде задача размещения конструктивных элементов на коммутационной плате формулируется следующим образом. Задано множество конструктивных элементов R={r1,r2,…,rn} и множество связей между этими элементами V={v1,v2,…,vp}, а также множество установочных мест (позиций) на коммутационной плате T={t1,t2,…,tk}. Найти такое отображение множества R на множестве T, которое обеспечивает экстремум целевой функции
, где cij – коэффициент взвешенной связности.
Реферат опубликован: 31/03/2010