Реферат: Методы и алгоритмы компоновки, размещения и трассировки печатных плат
Московский государственный институт электроники иматематики
(Технический университет)
Кафедра ИТАС
РЕФЕРАТ
Привести методы и алгоритмы решения задач компоновки, размещения итрассировки, возникающих в процессе конструирования. Оценить трудоемкостьметодов и качество получаемых с их помощью решений, рассматривая указанные вышезадачи как задачи математического программирования.
Выполнил:
Проверил:
Принял:
МОСКВА 2003
ОГЛАВЛЕНИЕ
1. Введение
2. Алгоритмы компоновка
3. Алгоритмы размещения
4. Алгоритмы трассировки
ВВЕДЕНИЕ
При конструкторском проектировании РЭА(радиоэлектронной аппаратуры) решаются задачи, связанные с поиском наилучшеговарианта конструкции, удовлетворяющего требованиям технического задания имаксимально учитывающего возможности технологической базы производства. Теснаявзаимосвязанность задач и большая размерность каждой из них обычно не позволяетпредложить метод поиска оптимального конструктивного решения в едином цикле всвязи с трудностями создания общей математической модели, комплексноучитывающей особенности конструкторско-технологической базы производства.Поэтому разработка и реализация алгоритмов и методов решения отдельных задачэтапа конструкторского проектирования: компоновки, размещения и трассировки,-до сих пор остаются актуальными проблемами, решение которых неотъемлемо связанос развитием систем автоматизации проектирования.
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 /> X \ X1 включают в G1(X1,U1), если не происходит нарушения ограничения по числувнешних связей куска, т.е.
/>,
гдеαjε<sub/>– элемент матрицы смежности исходно графа G(X,U); δ(xg) – относительный вес вершины xg, ,равный приращению числа внешних ребер куска G1(X1,U1) при включении вершины xg<sub/> вомножество X1; E – множествоиндексов вершин, включенных в формируемый кусок графа на предыдущих шагахалгоритма; m – максимально допустимое число внешних связейотдельно взятого куска со всеми оставшимися.
Указанныйпроцесс продолжается до тех пор, пока множество X1 не будет содержать n элементов либо присоединение очереднойнераспределенной вершины xj<sub/> к куску 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) = />. Переходимк п.6. Если таких вершин несколько, то переходим к п.5
5) Из подмножества вершин Xl содинаковой локальной степенью выбирают вершину xj с максимальнымчислом кратных ребер (минимальным числом смежных вершин), т.е. |Гxj| = />.
6) Запоминаем исходную вершинуформируемого куска графа />.Переходим к п.10
7) По матрице смежности /> строим множество Xs=/> и определяем относительныевеса вершин />:
/>.
8) Из множества XS<sub/> выбираемвершину />. Переходим к п.10. Еслитаких вершин несколько, то переходим к п.9.
9) Из подмножества вершин Xv содинаковым относительным весом выбираем вершину xj с максимальнойлокальной степенью, т.е. />.
10)/>.
11)Если >m, то переходим к п.13.
12)Рассмотренные вершины включаем в формируемый кусок Xf = Xt .
13)Θ = Θ + 1.
14)Если Θ> α, то переходим к п.15, а противном случае – к п.7.
15)Если |Xf|<nmin, где nmin<sub/>–минимально допустимое число вершин в куске, то переходим к п.21.
16)Выбираем окончательный вариант сформированного куска графа:
Xt = Xf; X = X \ Xt; α = nmax .
17) Если |X|>nmax<sub/>,то переходим к п.20.
18)Если |X|< nmin , топереходим к п.21.
19)Определяем число внешних связей последнего куска графа:
/>,
где F – множествоиндексов вершин, входящих в X. Если />, топереходим к п.21, в противном случае – к п.24.
20)Если t<k – 1, где k — число кусков разрезанияграфа, то переходим к п.2, в противном случае – к п.23.
21)Предыдущий цикл «разрезания» считаем недействительным. Если t>1, т.е. имеется как минимум один ранее сформированный кусок, то переходим к п.22.в противном случае – к п.23.
22)Ищем другой допустимый вариант формирования предыдущего куска с меньшим числомвершин: t = t – 1; />.
Переходим к п.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, />. На пересечении k строки (/>и q столбца/> находится элемент
/>,
гдеrk,q– элементматрицы смежности R.
Элементwk,q матрицы W характеризуетизменение числа соединительных ребер между Gi и Gj приперестановке вершин /> и />. Используя матрицу W, можно найтиподстановку, которая увеличит число элементов в подматрицах R1 и R1’. Такой процесс повторяется до тех пор, пока вподматрице R1 несосредоточится максимальное число единиц.
Витерационных алгоритмах предусмотрена возможность поиска оптимального вариантадля различных начальных разбиений. Это связано с тем, что при использованииитерационных алгоритмов оптимальность решения в значительной мере зависит оттого, насколько удачно было произведено начальное разбиение графа 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<sub/>, закрепленных в позициях tfи tg, имеет вид:
/>,
гдеp и h(p) – порядковый номер и позиция закрепления неподвижногоэлемента rp. Если />, тоосуществляют перестановку ri и rj<sub/>, приводящую к уменьшению целевой функции на />, после чего производятпоиск и перестановку следующей пары элементов и т.д. Процесс заканчиваетсяполучением такого варианта размещения, для которого дальнейшее улучшение засчет парных перестановок элементов невозможно.
Использованиеописанного направленного перебора сокращает число анализируемых вариантовразмещения (по сравнению с полным перебором), но приводит к потере гарантиинахождения глобального экстремума целевой функции.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шагов алгоритма.
Алгоритмы,использующие последовательный процесс закрепления элементов в позициях,являются в настоящее время самыми быстродействующими. Однако по качествуполучаемого решения последовательные алгоритмы уступают итерационным. Поэтомуих используют обычно для получения начального размещения элементов на плате.
4. АЛГОРИТМЫ ТРАССИРОВКИ
Трассировкасоединений является, как правило, заключительным этапом конструкторскогопроектирования РЭА и состоит в определении линий, соединяющих эквипотенциальныеконтакты элементов, и компонентов, составляющих проектируемое устройство.
Задачатрассировки – одна из наиболее трудоемких в общей проблеме автоматизациипроектирования РЭА. Это связано с несколькими факторами, в частности смногообразием способов конструктивно-технологической реализации соединений, длякаждого из которых при алгоритмическом решении задачи применяются специфическиекритерии оптимизации и ограничения. С математической точки зрения трассировка –наисложнейшая задача выбора из огромного числа вариантов оптимального решения.
Одновременнаяоптимизации всех соединений при трассировке за счет перебора всех вариантов внастоящее время невозможна. Поэтому разрабатываются в основном локальнооптимальные методы трассировки, когда трасса оптимальна лишь на данном шаге приналичии ранее проведенных соединений.
Основнаязадача трассировки формулируется следующим образом: по заданной схемесоединений проложить необходимые проводники на плоскости (плате, кристалле ит.д.), чтобы реализовать заданные технические соединения с учетом заранеезаданных ограничений. Основными являются ограничения на ширину проводников иминимальные расстояния между ними.
Исходнойинформацией для решения задачи трассировки соединений обычно являются списокцепей, параметры конструкции элементов и коммутационного поля, а также данныепо размещению элементов. Критериями трассировки могут быть процентреализованных соединений, суммарная длина проводников, число пересеченийпроводников, число монтажных слоев, число межслойных переходов, равномерностьраспределения проводников, минимальная область трассировки и т.д. Часто этикритерии являются взаимоисключающими, поэтому оценка качества трассировки ведетсяпо доминирующему критерию при выполнении ограничений по другим критериям либоприменяют аддитивную или мультипликативную форму оценочной функции, напримерследующего вида
/>, где F – аддитивный критерий; λi – весовой коэффициент; fi – частныйкритерий; p – числочастных критериев.
Известныеалгоритмы трассировки печатных плат можно условно разбить на три большиегруппы:
1) Волновые алгоритмы, основанные наидеях Ли и разработанные Ю.Л. Зиманом и Г.Г. Рябовым. Данные алгоритмы получилиширокое распространение в существующих САПР, поскольку они позволяют легкоучитывать технологическую специфику печатного монтажа со своей совокупностьюконструктивных ограничений, Эти алгоритмы всегда гарантируют построение трассы,если путь для нее существует;
2) Ортогональные алгоритмы,обладающие большим быстродействием, чем алгоритмы первой группы. Реализация ихна ЭВМ требует в 75-100 раз меньше вычислений по сравнению с волновымиалгоритмами. Такие алгоритмы применяют при проектировании печатных плат сосквозными металлизированными отверстиями. Недостатки этой группы алгоритмовсвязаны с получением большого числа переходов со слоя на слой, отсутствием100%-ой гарантии проведения трасс, большим числом параллельно идущихпроводников;
3) Алгоритмы эвристического типа. Этиалгоритмы частично основаны на эвристическом приеме поиска пути в лабиринте.При этом каждое соединение проводится по кратчайшему пути, обходя встречающиесяна пути препятствия.
Волновой алгоритм Ли
Данныйалгоритм является классическим примером использования методов динамическогопрограммирования для решения задач трассировки печатных соединений. Основныепринципы построения трасс с помощью динамического алгоритма сводятся кследующему.
Всеячейки монтажного поля подразделяют на занятые и свободные. Занятыми считаютсяячейки, в которых уже расположены проводники, построенные на предыдущих шагах,или находятся монтажные выводы элементов, а также ячейки, соответствующиегранице платы и запрещенным для прокладывания проводников участкам. Каждый разпри проведении новой трассы можно использовать лишь свободные ячейки, числокоторых по мере проведения трасс сокращается.
Намножестве свободных ячеек коммутационного поля моделируют волну влияния изодной ячейки в другую, соединяемых впоследствии общим проводником. Первуюячейку, зарождается волна влияний, называют источником, а вторую – преемникомволны. Чтобы иметь возможность следить за прохождением фронта волны влияний,его фрагментам на каждом этапе присваивают некоторые веса:
/>,
гдеPk и Pk-1 -веса ячеек k-го и (k-1)-го фронтов; />-весовая функция, являющаяся показателем качества проведения пути, каждыйпараметр которой /> характеризуетпуть с точки зрения одного из критериев качества (длины пути, числа пересеченийи т.п.). На Pk накладываютодно ограничение – веса ячеек предыдущих фронтов не должны быть больше весовячеек последующих фронтов. Фронт распространяется только на соседние ячейки,которые имеют с ячейками предыдущего фронта либо общую сторону, либо хотя быодну общую точку. Процесс распространения волны продолжается до тех пор, покаеё расширяющийся фронт не достигнет приемника или на Θ-ом шаге не найдетсяни одной свободной ячейки, которая могла бы быть включена в очередной фронт,что соответствует случаю невозможности проведения трассы при заданныхограничениях.
Еслив результате распространения волна достигла приемника, то осуществляют«проведение пути», которое заключается в движении от приемника к источнику пропройденным на этапе распространения волны ячейкам, следя за тем, чтобы значенияPk монотонноубывали. В результате получают путь, соединяющий эти две точки. Из описанияалгоритма следует, что все условия, необходимые для проведения пути,закладываются в правила приписания веса ячейкам.
Чтобыисключить неопределенность при проведении пути для случая, когда несколькоячеек имеют одинаковый минимальный вес, вводят понятие путевых координат,задающих предпочтительность проведения трассы. Каждое направление кодируютдвоичным числом по mod q, где q – числопросматриваемых соседних ячеек. При этом чем более предпочтительно то или иноенаправление, тем меньший числовой код оно имеет. Например, если задатьсяприоритетным порядком проведения пути сверху, справа, снизу и слева, то кодысоответствующих путевых координат будут 00, 01, 10, и 11. Приписание путевыхкоординат производят на этапе распространения волны. При проведении путидвижение от ячейки к ячейке осуществляют по путевым координатам.
/>/>
Существенныминедостатками волнового алгоритма являются малое быстродействие и большой объемоперативной памяти ЭВМ, необходимый для хранения информации о текущем состояниивсех ячеек коммутационного поля, возможность построения лишь соединений типа«ввод-вывод». Попытки устранить указанные недостатки привели к созданию рядамодификаций волнового алгоритма.
Модификации алгоритма Ли
Метод встречной волны
Вданном методе источниками волн являются обе ячейки, подлежащие электрическомуобъединению. При этом на каждом k-ом шаге поочередно строятсоответствующие фронты первой и второй волн, распространяющихся из этих ячеек.Процесс продолжается до тех пор, пока какая-либо ячейка из фронта первой волныне попадет на фронт второй волны или наоборот. Проведение пути осуществляют изданной ячейки в направлении обоих источников по правилам, описанным в волновомалгоритме Ли.
Оценимчисло ячеек, просматриваемых на этапе распространения волны, при использованиив качестве источников одной или двух объединяемых точек. Пусть расстояниемежду этими точками R. Тогда для первого случая в момент достижения волнойячейки-приемника площадь просмотренной окрестности имеет величину /> (знак равенствасоответствует отсутствию преград пути распространения волны). Для второгослучая в момент встречи фронтов двух волн площадь просмотренной окрестности />.
Такимобразом, при использовании метода встречной волны просматриваемая площадь, аследовательно, и время, затрачиваемое на этапе распространения волны,уменьшаются примерно вдвое.
Недостаткомметода является необходимость выделения дополнительного разряда памяти накаждую рабочую ячейку поля для хранения информации о принадлежности её к первойили второй волне. Однако выигрыш в повышении быстродействия выполняет указанныйнедостаток, поэтому данный метод используют во всех случаях, когда этопозволяет объем оперативной памяти ЭВМ.
Лучевой алгоритм трассировки
Вданном алгоритме, предложенным Л.Б. Абрайтисом, выбор ячеек для определенияпути между соединяемыми точками A и B производят по заранее заданнымнаправлениям, подобным лучам. Это позволяет сократить число просматриваемыхалгоритмом ячеек, а следовательно, и время на анализ и кодировку их состояния,однако приводит к снижению вероятности нахождения пути сложной конфигурации, иусложняет учет конструктивных требований к технологии печатной платы.
Работаалгоритма заключается в следующем. Задается число лучей, распространяемых източек A и B, атакже порядок присвоения путевых координат (обычно число лучей для каждойячейки-источника принимается одинаковым). Лучи A(1), A(2),…, A(n) и B(1), B(2),…, B(n) считают одноименными,если они распространяются из одноименных источников A или B. Лучи A(i) и B(i) являются разноименными по отношению друг к другу.Распространение лучей производят одновременно из обоих источников до встречидвух разноименных лучей в некоторой ячейке C. Путьпроводится из ячейки C ипроходит через ячейки, по которым распространялись лучи.
Прираспространении луча может возникнуть ситуация, когда все соседние ячейки будутзаняты. В этом случае считается заблокированным и его распространениепрекращается.
/>/>
Лучи:
A(1): вверх,влево
A(2): влево,вверх
B(1): вниз,вправо
B(2): вправо,вниз
Навтором шаге луч B(1)оказывается заблокированным, а на четвертом шаге блокируется и луч A(2). Лучи A(1) и B(2) встречаются в ячейке C на восьмом шаге.
Обычнос помощью лучевого алгоритма удается построить до 70-80% трасс, остальныепроводят, используя волновой алгоритм или вручную. Его применение особенновыгодно при проектировании плат с невысокой плотностью монтажа.
ИСПОЛЬЗУЕМАЯЛИТЕРАТУРА
Б.Н. Деньдобренко, А.С. Малика «Автоматизация конструирования РЭА»,Москва «Высшая школа» 1980.
В.М. Курейчик «Математическое обеспечение конструкторского и технологического проектирования с применением САПР»,Москва «Радио и связь» 1990.
К.К. Морзов, В.Г. Одиноков, В.М. Курейчик «Автоматизированное проектирование конструкций радиоэлектронной аппаратуры», Москва «Радио и связь» 1983. В.Н. Ильин, В.Т. Фролкин, А.И. Бутко и др.; «Автоматизация схемотехнического проектирования: Учебное пособие для вузов», Москва «Радио и связь» 1987.