Методы и алгоритмы компоновки, размещения и трассировки печатных плат - Радиоэлектроника - Скачать бесплатно
Московский государственный институт электроники и математики
(Технический университет)
Кафедра ИТАС
РЕФЕРАТ
Привести методы и алгоритмы решения задач компоновки,
размещения и трассировки, возникающих в процессе
конструирования. Оценить трудоемкость методов и качество
получаемых с их помощью решений, рассматривая указанные выше
задачи как задачи математического программирования.
Выполнил:
Проверил:
Принял:
МОСКВА 2003
ОГЛАВЛЕНИЕ
1. Введение
2. Алгоритмы компоновка
3. Алгоритмы размещения
4. Алгоритмы трассировки
1. ВВЕДЕНИЕ
При конструкторском проектировании РЭА (радиоэлектронной аппаратуры)
решаются задачи, связанные с поиском наилучшего варианта конструкции,
удовлетворяющего требованиям технического задания и максимально
учитывающего возможности технологической базы производства. Тесная
взаимосвязанность задач и большая размерность каждой из них обычно не
позволяет предложить метод поиска оптимального конструктивного решения в
едином цикле в связи с трудностями создания общей математической модели,
комплексно учитывающей особенности конструкторско-технологической базы
производства. Поэтому разработка и реализация алгоритмов и методов решения
отдельных задач этапа конструкторского проектирования: компоновки,
размещения и трассировки,- до сих пор остаются актуальными проблемами,
решение которых неотъемлемо связано с развитием систем автоматизации
проектирования.
2. АЛГОРИТМЫ КОМПОНОВКИ
На этапе конструкторского проектирования решаются вопросы, связанные с
компоновкой элементов логической схемы в модули, модулей в ячейки, ячеек в
панели и т. д. Эти задачи в общем случае тесно связаны между собой, и их
решение позволяет значительно сократить затраты и трудоемкость указанного
этапа в САПР. Обычно задачи компоновки рассматриваются как процесс принятия
решений в определенных или неопределенных условиях, в результате выполнения
которого части логической схемы располагаются в конструктивных элементах i-
го уровня, а эти элементы размещаются в конструктивных элементах (i+1) –го
уровня и т. д., причем расположение выполняется с оптимизацией по
выбранному критерию.
Компоновкой электрической схемы РЭА на конструктивно законченные части
называется процесс распределения элементов низшего конструктивного уровня в
высший в соответствии с выбранным критерием. Основным для компоновки
является критерий электромагнитотепловой совместимости элементов низшего
уровня. Данный критерий определяет область допустимых разбиений схемы, на
которой формулируются другие критерии. Такими критериями могут быть:
минимум типов конструктивно законченных частей, плотность компоновки,
минимум соединений между устройствами, простота диагностирования и др.
Очевидно, что внешние соединения между частями схем являются одним из
важнейших факторов, определяющих надежность РЭА. Поэтому наиболее
распространенным критерием является критерий минимума числа внешних связей.
Выполнение этого критерия обеспечивает минимизацию взаимных наводок,
упрощение конструкции, повышение надежности и т. д.
Для построения формальной математической модели компоновочных задач
удобно использовать теорию графов. При этом электрическую схему
интерпретируют ненаправленным мультиграфом, в котором каждому
конструктивному элементу (модулю) ставят в соответствие вершину
мультиграфа, а электрическим связям схемы – его ребра. Тогда задача
компоновки формулируется следующим образом, Задан мультиграф G(X,U).
Требуется “разрезать” его на отдельные куски G1(X1,U1), G2(X2,U2),…,
Gk(Xk,Uk) так, чтобы число ребер, соединяющих эти куски, было минимальным,
т.е.
минимизировать [pic] i?j
при [pic][pic] i,j = 1,2,…,k,
где Uij – множество ребер, соединяющих куски Gi(Xi,Ui) и Gj(Xj,Uj).
Другими словами разбиениями частей совокупности G на графы считаются,
если любая часть из этой совокупности не пустая; для любых двух частей
пересечение множества ребер может быть не пустым; объединение всех частей в
точности равно графу G.
Известные алгоритмы компоновки можно условно разбить на пять групп:
1. алгоритмы, использующие методы целочисленного
программирования.
2. последовательные алгоритмы
3. итерационные алгоритмы
4. смешанные алгоритмы
Алгоритмы первой группы хотя и позволяют получить точное решение
задачи, однако для устройства реальной сложности фактически не реализуемы
на ЭВМ. В последнее время наибольшее распространение получили приближенные
алгоритмы компоновки (последовательные, итерационные, смешанные). При
использовании последовательных алгоритмов сначала по определенному правилу
выбирают вершину графа, затем осуществляют последовательный выбор вершин
(из числа нераспределенных) и присоединение их к формируемому куску графа.
После образования первого куска переходят ко второму и т. д. до получения
желаемого разрезания исходного графа. В итерационных алгоритмах начальное
разрезание графа на куски выполняют произвольным образом; оптимизация
компоновки достигается парными или групповыми перестановками вершин графа
из различных кусков. Процесс перераспределения вершин заканчивают при
получении локального экстремума целевой функции, удовлетворяющим
требованиям разработчика. В смешанных алгоритмах компоновки для получения
начального варианта “разрезания” используется алгоритм последовательного
формирования кусков; дальнейшая оптимизация решения осуществляется
перераспределением вершин между отдельными кусками графа.
Последовательные алгоритмыкомпоновки
В последовательных алгоритмах компоновки «разрезание» исходного графа
G(X,U) на куски G1(X1,U1), G2(X2,U2),…, Gk(Xk,Uk) сводится к следующему. В
графе G(X,U) находят вершину xi [pic] X с минимальной локальной степенью
[pic].
Если таких вершин несколько, то предпочтение отдают вершине с
максимальным числом кратных ребер. Из множества вершин, смежных с вершинами
формируемого куска графа G1(X1,U1), выбирают ту, которая обеспечивает
минимальное приращение связей куска с еще нераспределенными вершинами.
Данную вершину xi [pic] X X1 включают в G1(X1,U1), если не происходит
нарушения ограничения по числу внешних связей куска, т.е.
[pic],
где ?j? – элемент матрицы смежности исходно графа G(X,U); ?(xg) –
относительный вес вершины xg, , равный приращению числа внешних ребер куска
G1(X1,U1) при включении вершины xg во множество X1; E – множество индексов
вершин, включенных в формируемый кусок графа на предыдущих шагах алгоритма;
m – максимально допустимое число внешних связей отдельно взятого куска со
всеми оставшимися.
Указанный процесс продолжается до тех пор, пока множество X1 не будет
содержать n элементов либо присоединение очередной нераспределенной вершины
xj к куску G1(X1,U1) не приведет к нарушению ограничения по числу внешних
соединений куска, равному
[pic]
Следует отметить, что величина [pic] не является монотонной функцией
|X1|, поэтому, для того чтобы убедится в невозможности дальнейшего
формирования куска вследствие нарушения последнего ограничения, необходимо
проверить его невыполнимость на последующих шагах увеличения множества X1
вплоть до n. В качестве окончательного варианта выбирают кусок
G10(X10,U10), содержащий максимально возможное число вершин графа G(X,U),
для которого выполняются ограничения на число внешних связей и входящих в
него вершин (nmin-nmax).
После преобразования куска G10(X10,U10) процесс повторяют для
формирования второго, третьего и т.д. кусков исходного графа с той лишь
разницей, что рассмотрению подлежат вершины, не вошедшие в предыдущие
куски.
Сформулируем алгоритм последовательной компоновки конструктивных
элементов.
1) t:0
2) Xf = Xt = Ш; t=t+1; ?=1; ?=nmax,
Где t, ? – порядковые номера формируемого куска и присоединяемой
вершины; ? – ограничение на число вершин в куске.
3) По матрице смежности исходного графа | ?hp|NxN, где N – число
вершин исходного графа (при большом значении N для сокращения
объема оперативной памяти ЭВМ используем не саму матрицу смежности,
а её кодовую реализацию), определяем локальные степени вершин
[pic].
4) Из множества нераспределенных вершин X выбираем вершину xj с ?(xj)
= [pic]. Переходим к п.6. Если таких вершин несколько, то переходим
к п.5
5) Из подмножества вершин Xl с одинаковой локальной степенью выбирают
вершину xj с максимальным числом кратных ребер (минимальным числом
смежных вершин), т.е. |Гxj| = [pic].
6) Запоминаем исходную вершину формируемого куска графа [pic].
Переходим к п.10
7) По матрице смежности [pic] строим множество Xs = [pic] и определяем
относительные веса вершин [pic]:
[pic].
8) Из множества XS выбираем вершину [pic]. Переходим к п.10. Если
таких вершин несколько, то переходим к п.9.
9) Из подмножества вершин Xv с одинаковым относительным весом выбираем
вершину xj с максимальной локальной степенью, т.е. [pic].
10) [pic].
11) Если >m , то переходим к п.13.
12) Рассмотренные вершины включаем в формируемый кусок Xf = Xt .
13) ? = ? + 1.
14) Если ?> ?, то переходим к п.15, а противном случае – к п.7.
15) Если |Xf| nmax , то переходим к п.20.
18) Если |X|< nmin , то переходим к п.21.
19) Определяем число внешних связей последнего куска графа:
[pic],
где F – множество индексов вершин, входящих в X. Если [pic],
то переходим к п.21, в противном случае – к п.24.
20) Если t1,
т.е. имеется как минимум один ранее сформированный кусок, то
переходим к п.22. в противном случае – к п.23.
22) Ищем другой допустимый вариант формирования предыдущего куска с
меньшим числом вершин: t = t – 1; [pic].
Переходим к п.7.
23) Задача при заданных ограничениях не имеет решения.
24) Конец работы алгоритма.
Рассмотренный алгоритм прост, легко реализуется на ЭВМ и позволяет
получить решение задачи компоновки. Также среди достоинств данной группу
алгоритмов выступает высокое быстродействие их при решении задач
компоновки.
Основным недостатком последовательного алгоритма является
неспособность находить глобальный минимум количества внешних связей (не
анализируются возможные ситуации). Наибольшая эффективность метода
последовательного разбиения графа имеет место, когда число вершин графа G
значительно больше вершин в любой части разбиения.
Итерационные алгоритмы компоновки
Сущность данной группы алгоритмов заключается в выборе некоторого
начального «разрезания» исходного графа на куски (вручную или с помощью
последовательного метода компоновки) и последующего его улучшения с помощью
итерационного парного или группового обмена вершин из различных кусков. При
этом для каждой итерации осуществляется перестановка тех вершин, которая
обеспечивает максимальное уменьшение числа связей между кусками графа или
максимальное улучшение другого выбранного показателя качества с учетом
используемых ограничений (например, на максимальное число внешних ребер
любого отдельно взятого куска).
Рассмотрим основную идею итерационного алгоритма разбиения графа G,
заданного матрицей смежности, с минимизацией числа соединительных ребер.
Разбиение графа G = (X,U) на l подграфов G1 = (X1,U1), G2 = (X2,U2),…,Gl =
(Xl,Ul) сведем к разбиению на два подграфа. С этой целью в матрице
смежности R выделим по главной диагонали две подматрицы R1 и R2. При этом
порядок подматрицы R1 равен числу вершин, которые должны находится в G1, а
порядок подматрицы R2 – числу всех оставшихся вершин графа. Необходимо так
переставить строки и столбцы матрицы R, чтобы число ребер между G1 и
оставшейся частью графа G было минимальным. После этого подматрицу R1 из
матрицы R исключаем, вычеркнув из R строки и столбцы, соответствующие
элементам R1. Далее подматрицу R1’ разбиваем снова на две подматрицы R2 и
R2’, причем порядок R2 соответствует числу вершин второго выделяемого
подграфа, а порядок R2 – числу оставшихся вершин графа. Переставляем строки
и столбцы R1’ с целью минимизации числа соединительных ребер. После этого
подматрица R2’ исключается и процесс повторяется до тех пор, пока не будет
выполнено разбиение графа G на l подграфов.
Основная идея алгоритма заключается в выборе таких строк и столбцов,
перестановка которых приводит к сосредоточению в диагональных клетках
матрицы R максимального числа элементов. Построим прямоугольную матрицу W
= ||wi,j||nix(n-ni), в которой строки определяются вершинами из множества
I, а столбцы – из множества V, [pic]. На пересечении k строки ([pic]и q
столбца [pic] находится элемент
[pic],
где rk,q – элемент матрицы смежности R.
Элемент wk,q матрицы W характеризует изменение числа соединительных
ребер между Gi и Gj при перестановке вершин [pic] и [pic]. Используя
матрицу W , можно найти подстановку, которая увеличит число элементов в
подматрицах R1 и R1’ . Такой процесс повторяется до тех пор, пока в
подматрице R1 не сосредоточится максимальное число единиц.
В итерационных алгоритмах предусмотрена возможность поиска
оптимального варианта для различных начальных разбиений. Это связано с тем,
что при использовании итерационных алгоритмов оптимальность решения в
значительной мере зависит от того, насколько удачно было произведено
начальное разбиение графа G(X,U).
Итерационные алгоритмы компоновки обеспечивают высокое качество
решения задачи, однако требуют больших затрат машинного времени, чем
последовательные алгоритмы. Для сокращения числа итераций обмена вершин
между кусками в смешанных алгоритмах для получения начального «разрезания»
графа применяют последовательные методы формирования его кусков. С этой
целью в некоторых итерационных алгоритмах используют процесс групповой
перестановки взаимно непересекающихся пар вершин.
3. АЛГОРИТМЫ РАЗМЕЩЕНИЯ
Исходной информацией при решении задач размещения являются: данные о
конфигурации и размерах коммутационного пространства, определяемые
требованиями установки и крепления данной сборочной единицы в аппаратуре;
количество и геометрические размеры конструктивных элементов, подлежащих
размещению; схема соединений, а также ряд ограничений на взаимное
расположение отдельных элементов, учитывающих особенности разрабатываемой
конструкции. Задача сводится к отысканию для каждого размещаемого элемента
таких позиций, при которых оптимизируется выбранный показатель качества и
обеспечивается наиболее благоприятные условия для последующего
электрического монтажа. Особое значение эта задача приобретает при
проектировании аппаратуры на печатных платах.
Основная сложность в постановке задач размещения заключается в выборе
целевой функции. Связано это с тем, что одной из главных целей размещения
является создание наилучших условий для дальнейшей трассировки соединений,
что невозможно проверить без проведения самой трассировки. Любые другие
способы оценки качества размещения (минимум числа пересечений ребер графа,
интерпретирующего электрическую схему соединений, разбиение графа на
минимальное число плоских суграфов и т.д.), хотя и позволяют создать
благоприятные для трассировки условия, но не гарантируют получение
оптимального результата, поскольку печатные проводники представляют собой
криволинейные отрезки конечной ширины, конфигурация которых определяется в
процессе их построения и зависит от порядка проведения соединений.
Следовательно, если для оценки качества размещения элементов выбрать
критерий, непосредственно связанный с получением оптимального рисунка
металлизации печатной платы, то конечный результат может быть найден только
при совместном решении задач размещения, выбора очередности проведения
соединений и трассировки, что практически невозможно вследствие огромных
затрат машинного времени.
Поэтому все применяемые в настоящее время алгоритмы размещения используют
промежуточные критерии, которые лишь качественно способствуют решению
основной задачи: получению оптимальной трассировки соединений. К таким
критериям относятся: 1) минимум суммарной взвешенной длины соединений; 2)
минимум числа соединений, длина которых больше заданной; 3) минимум числа
пересечение проводников; 4) максимальное число соединений между элементами,
находящимися в соседних позициях либо в позициях, указанных разработчиком;
5) максимум числа цепей простой конфигурации.
Наибольшее распространение в алгоритмах размещения получил первый
критерий, что объясняется следующими причинами: уменьшение длин соединений
улучшает электрические характеристики устройства, упрощает трассировку
печатных плат; кроме того, он сравнительно прост в реализации.
В зависимости от конструкции коммутационной платы и способов выполнения
соединений расстояние между позициями установки элементов подсчитывается по
одной из следующих формул:
[pic], [pic], [pic]
В общем виде задача размещения конструктивных элементов на коммутационной
плате формулируется следующим образом. Задано множество конструктивных
элементов R={r1,r2,…,rn} и множество связей между этими элементами
V={v1,v2,…,vp}, а также множество установочных мест (позиций) на
коммутационной плате T={t1,t2,…,tk}. Найти такое отображение множества R на
множестве T, которое обеспечивает экстремум целевой функции
[pic], где cij – коэффициент взвешенной связности.
Силовые алгоритмы размещения
В основу этой группы алгоритмов положен динамический метод В.С. Линского.
Процесс размещения элементов на плате представляется как движение к
состоянию равновесия системы материальных точек (элементов), на каждую из
которых действуют силы притяжения и отталкивания, интерпретирующие связи
между размещаемыми элементами. Если силы притяжения, действующие между
любыми двумя материальными точками ri и rj пропорциональны числу
электрических связей между данными конструктивными элементами, то состояние
равновесия такой системы соответствует минимуму суммарной длины всех
соединений. Введение сил отталкивания материальных точек друг от друга и от
границ платы исключает возможность слияния двух любых точек и способствует
их равномерному распределению по поверхности монтажного поля. Чтобы
устранить возникновение в системе незатухающих колебаний, вводят силы
сопротивления среды, пропорциональные скорости движения материальных точек.
Таким образом, задача оптимального размещения элементов сводится к
нахождению такого местоположения точек, при котором равнодействующие всех
сил обращаются в нуль.
К достоинствам данного метода относятся возможность получения
глобального экстремума целевой функции, а также сведение поиска к
вычислительным процедурам, для которых имеются разработанные численные
методы.
Недостатками являются трудоемкость метода и сложность его реализации
(подбора коэффициентов для силовых связей); необходимость фиксирования
местоположения некоторого числа конструктивных элементов на плате для
предотвращения большой неравномерности их размещения на отдельных участках
платы.
Итерационные алгоритмы размещения
Итерационные алгоритмы имеют структуру, аналогичную итерационным
алгоритмам компоновки, рассмотренным ранее. В них для улучшения исходного
размещения элементов на плате вводят итерационный процесс перестановки
местами пар элементов.
В случае минимизации суммарной взвешенной длины соединений формула
для расчета изменения значения целевой функции при перестановке местами
элементов ri и rj , закрепленных в позициях tf и tg, имеет вид:
[pic],
где p и h(p) – порядковый номер и позиция закрепления неподвижного элемента
rp. Если [pic], то осуществляют перестановку ri и rj , приводящую к
уменьшению целевой функции на [pic], после чего производят поиск и
перестановку следующей пары элементов и т.д. Процесс заканчивается
получением такого варианта размещения, для которого дальнейшее улучшение за
счет парных перестановок элементов невозможно.
Использование описанного направленного перебора сокращает число
анализируемых вариантов размещения (по сравнению с полным перебором), но
приводит к потере гарантии нахождения глобального экстремума целевой
функции.20
Алгоритмы дано группы характеризуются достаточно высоким
быстродействием. Алгоритмы с групповыми перестановками элементов на
практике используются редко ввиду их сложности, которая часто не
оправдывает достигаемую степень улучшения результата.
Последовательные алгоритмы размещения
Последовательные алгоритмы основаны на допущении, что для получения
оптимального размещения необходимо в соседних позициях располагать
элементы, максимально связанные друг с другом. Сущность этих алгоритмов
состоит в последовательном закреплении заданного набора конструктивных
элементов на коммутационной плате относительно ранее установленных. В
качестве первоначально закрепленных на плате элементов обычно выбирают
разъемы, которые искусственно «раздвигают» до краев платы. При этом все
контакты разъемов равномерно распределяются по секциям (столбцам и строкам
координатной сетки). На каждом l-ом шаге (l=1,2,…,n) для установки на
коммутационную плату выбирают элемент [pic] из числа еще не размещенных,
имеющий максимальную степень связности с ранее закрепленными элементами Rl-
1. В большинстве используемых в настоящее время алгоритмов оценку степени
связности производят по одной из следующих формул:
|
