Московский государственный институт электроники иматематики
(Технический университет)
Кафедра ИТАС
РЕФЕРАТ
Привести методы и алгоритмы решения задач компоновки, размещения итрассировки, возникающих в процессе конструирования. Оценить трудоемкостьметодов и качество получаемых с их помощью решений, рассматривая указанные вышезадачи как задачи математического программирования.
Выполнил:
Проверил:
Принял:
МОСКВА 2003
ОГЛАВЛЕНИЕ
1. Введение…………………………………………….1
2. Алгоритмы компоновки……………………………1
3. Алгоритмы размещения……………………………7
4. Алгоритмы трассировки…………………………..10
ВВЕДЕНИЕ
При конструкторском проектировании РЭА (радиоэлектроннойаппаратуры) решаются задачи, связанные с поиском наилучшего вариантаконструкции, удовлетворяющего требованиям технического задания и максимальноучитывающего возможности технологической базы производства. Теснаявзаимосвязанность задач и большая размерность каждой из них обычно не позволяетпредложить метод поиска оптимального конструктивного решения в едином цикле всвязи с трудностями создания общей математической модели, комплексноучитывающей особенности конструкторско-технологической базы производства.Поэтому разработка и реализацияалгоритмов и методов решения отдельных задач этапа конструкторскогопроектирования: компоновки, размещения и трассировки,- до сих пор остаютсяактуальными проблемами, решение которых неотъемлемо связано с развитием системавтоматизации проектирования.
2. АЛГОРИТМЫ КОМПОНОВКИ
На этапе конструкторского проектирования решаютсявопросы, связанные с компоновкой элементов логической схемы в модули,модулей в ячейки, ячеек в панели и т. д.Эти задачи в общем случае тесно связаны между собой, и их решение позволяетзначительно сократить затраты и трудоемкость указанного этапа в САПР. Обычнозадачи компоновки рассматриваются как процесс принятия решений в определенныхили неопределенных условиях, в результате выполнения которого части логической схемы располагаются вконструктивных элементах i-го уровня, аэти элементы размещаются в конструктивных элементах (i+1) –гоуровня и т. д., причем расположение выполняется с оптимизацией по выбранномукритерию.
Компоновкой электрической схемы РЭА на конструктивнозаконченные части называется процесс распределения элементов низшегоконструктивного уровня в высший всоответствии с выбранным критерием. Основным для компоновки является критерийэлектромагнитотепловой совместимости элементов низшего уровня. Данный критерийопределяет область допустимых разбиений схемы, на которой формулируются другиекритерии. Такими критериями могут быть: минимум типов конструктивно законченныхчастей, плотность компоновки, минимум соединений между устройствами и др.Очевидно, что внешние соединения между частями схем являются одним из важнейшихфакторов, определяющих надежность РЭА. Поэтому наиболее распространеннымкритерием является критерий минимума числа внешних связей. Выполнение этогокритерия обеспечивает минимизацию взаимных наводок, упрощение конструкции,повышение надежности и т. д.
Для построенияформальной математической модели компоновочных задач удобно использовать теориюграфов. При этом электрическую схему интерпретируют ненаправленныммультиграфом, в котором каждому конструктивному элементу (модулю) ставят всоответствие вершину мультиграфа, а электрическим связям схемы – его ребра.Тогда задача компоновки формулируется следующим образом, Задан мультиграф G(X,U). Требуется “разрезать” его на отдельные куски G1(X1,U1), G2(X2,U2),…, Gk(Xk,Uk) так, чтобы число ребер, соединяющих эти куски, быломинимальным, т.е.
минимизировать i≠j
при 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 Xсминимальной локальной степенью
Если таких вершин несколько, то предпочтение отдаютвершине с максимальным числом кратных ребер. Из множества вершин, смежных свершинами формируемого куска графа G1(X1,U1), выбирают ту, которая обеспечивает минимальноеприращение связей куска с еще нераспределенными вершинами. Данную вершину xi XX1включают в G1(X1,U1), если не происходит нарушения ограничения по числувнешних связей куска, т.е.
гдеαjε– элемент матрицы смежностиисходно графа G(X,U); δ(xg) – относительный вес вершины xg, ,равный приращению числа внешних ребер куска G1(X1,U1) привключении вершины xg во множество X1; E– множество индексов вершин, включенных в формируемыйкусок графа на предыдущих шагах алгоритма; m– максимально допустимое число внешних связей отдельновзятого куска со всеми оставшимися.
Указанный процесс продолжается дотех пор, пока множество X1не будет содержать nэлементов либоприсоединение очередной нераспределенной вершины xj к куску G1(X1,U1) неприведет к нарушению ограничения по числу внешних соединений куска, равному
Следует отметить, что величина не является монотоннойфункцией |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для сокращения объема оперативной памяти ЭВМиспользуем не саму матрицу смежности, а её кодовую реализацию), определяемлокальные степени вершин
4) Из множества нераспределенных вершин Xвыбираемвершину xjс ρ(xj) =
5) Из подмножества вершин Xlс одинаковой локальной степенью выбирают вершину xjс максимальнымчислом кратных ребер (минимальным числом смежных вершин), т.е. |Гxj| =
6) Запоминаем исходную вершину формируемого куска графа
7) По матрице смежности строим множество Xs= и определяемотносительные веса вершин
.
8) Из множества XS выбираемвершину п.10.Если таких вершин несколько, то переходим к п.9.
9) Из подмножества вершин Xvс одинаковым относительным весом выбираем вершину xjс максимальнойлокальной степенью, т.е.
10)
11)Если m, то переходимк п.13.
12)Рассмотренные вершины включаем в формируемый кусок Xf= Xt.
13)Θ= Θ+ 1.
14)Если Θ> α, то переходим к п.15, а противном случае – к п.7.
15)Если |Xf|
16)Выбираем окончательный вариант сформированного кускаграфа:
Xt= Xf; X= XXt; α= nmax.
17)Если|X|> nmax, топереходим к п.20.
18)Если |X|
19)Определяем число внешних связей последнего кускаграфа:
где F– множествоиндексов вершин, входящих в X. Если
20)Если t
21)Предыдущий цикл «разрезания» считаемнедействительным. Если t>1, т.е. имеется как минимум один ранеесформированный кусок, то переходим к п.22. в противном случае – к п.23.
22)Ищем другой допустимый вариант формированияпредыдущего куска с меньшим числом вершин: t= t– 1;
Переходим кп.7.
23)Задача при заданных ограничениях не имеет решения.
24)Конец работы алгоритма.
Рассмотренный алгоритм прост, легко реализуется на ЭВМи позволяет получить решение задачи компоновки. Также среди достоинств даннойгруппы алгоритмов выступает высокое быстродействие их при решении задачкомпоновки.
Основным недостаткомпоследовательного алгоритма является неспособность находить глобальный минимумколичества внешних связей (не анализируются возможные ситуации). Наибольшаяэффективность метода последовательного разбиения графа имеет место, когда числовершин графа Gзначительно больше вершин в любой части разбиения.
Итерационные алгоритмы компоновки
Сущность даннойгруппы алгоритмов заключается в выборе некоторого начального «разрезания» исходного графа на куски (вручную или спомощью последовательного метода компоновки) и последующего его улучшения спомощью итерационного парного или группового обмена вершин из различных кусков.При этом для каждой итерации осуществляется перестановка тех вершин, котораяобеспечивает максимальное уменьшение числа связей между кусками графа илимаксимальное улучшение другого выбранного показателя качества с учетомиспользуемых ограничений (например, на максимальное число внешних ребер любогоотдельно взятого куска).
Найдем выражениедля подсчета приращения числа ребер, соединяющих куски GA(XA,UA)и GB(XB,UB), при парном обмене вершин и
Очевидно, что парная перестановкавершин xgи xhприведет к изменению числа только тех связывающих куски GA(XA,UA)и GB(XB,UB)ребер, которые инцидентны этим вершинам. Общее числосоединительных ребер между GA(XA,UA)и GB(XB,UB), инцидентных xgи xh,до перестановки вершин определяют по матрице смежности следующим образом:
гдеIи J– множестваиндексов вершин, принадлежащих XBи XA. В этомвыражении первые два слагаемых определяют число ребер, соединяющих вершины xgс GB(XB,UB)и xhс GA(XA,UA), а наличие третьего члена обусловлено тем, что связьдвух слагаемых учитывалась дважды.
После перестановки вершин xgи xhполучим:
Третий член выражения указывает насохранение связи (xg, xh) после перестановки вершин. Следовательно, в результатеперестановки xgи xhприращениечисла ребер, соединяющих GA(XA,UA)и GB(XB,UB),
Перестановка вершин целесообразна,если
Если исходный граф G(X,U)заданматрицей смежности G(X,U)на kкусковэквивалентно разбиению матрицы Aна kxkподматриц:
SHAPE * MERGEFORMAT
A11
A1j
A1k
Ar1
Arj
Ark
Ak1
Akj
Akk
A =
Операция парного обмена вершин xgи xhсводится кперестановке соответствующих строк и столбцов матрицы A. Так каксумма элементов любой подматрицы Arjопределяетчисло ребер, связывающих Gr(Xr,Ur) и Gj(Xj,Uj), то процесс оптимального разрезания» графа G(X,U)на кускизаключается в отыскании на каждой итерации таких парных перестановок строк истолбцов матрицы A, при которых максимизируется сумма элементов вдиагональных подматрицах Ajj(j=1,2,…,k), что равносильно минимизации числа соединительныхребер.
В итерационных алгоритмах предусмотрена возможностьпоиска оптимального варианта для различных начальных разбиений. Это связано стем, что при использовании итерационных алгоритмов оптимальность решения взначительной мере зависит от того, насколько удачно было произведено начальноеразбиение графа G(X,U).
Итерационные алгоритмыкомпоновки обеспечивают высокое качество решения задачи, однако требуют большихзатрат машинного времени, чем последовательные алгоритмы. Для сокращения числаитераций обмена вершин между кусками в смешанных алгоритмах для полученияначального «разрезания» графа применяют последовательные методы формированияего кусков. С этой целью в некоторых итерационных алгоритмах используют процессгрупповой перестановки взаимно непересекающихся пар вершин.
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, приводящую к уменьшению целевой функции на
Использование описанногонаправленного перебора сокращает число анализируемых вариантов размещения (посравнению с полным перебором), но приводит к потере гарантии нахожденияглобального экстремума целевой функции.
Алгоритмы данной группы характеризуютсядостаточно высоким быстродействием. Алгоритмы с групповыми перестановкамиэлементов на практике используются редко ввиду их сложности, которая часто неоправдывает достигаемую степень улучшения результата.
Последовательные алгоритмы размещения
Последовательные алгоритмы основаны на допущении, чтодля получения оптимального размещения необходимо в соседних позицияхрасполагать элементы, максимально связанные друг с другом. Сущность этихалгоритмов состоит в последовательном закреплении заданного набораконструктивных элементов на коммутационной плате относительно ранееустановленных. В качестве первоначально закрепленных на плате элементов обычновыбирают разъемы, которые искусственно «раздвигают» до краев платы. При этомвсе контакты разъемов равномерно распределяются по секциям (столбцам и строкамкоординатной сетки). На каждом 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шаговалгоритма.