Л1-Савельев, Овчинников - Конструирование ЭВМ и систем - 1984 год (999411), страница 45
Текст из файла (страница 45)
!0.7), которые удовлетворяли бы следующим требованиям: м 1. () А. ы.! ; ŠŠ— все соединения должны быть выполнены в монтажной области Е - (Е,.'г - 1, 1т'). Здесь )т — число слоев. 2. тг Аь А,ЕЕ, (Аг () Ат -.-- ~";) — в каждом слое пРоводники г=т не должны иметь пересечений. 3. , У Аь А,ЕЕг (Р (Аь А,) =. Р,) — РасстоЯние междУ иРоводниками не должно быть меньше допустимого зазора Р„. 4. 8(А): В (;) Ва — ширина проводника ие должна быть меньше допустимой. . (тг А,. „= Ь, „) ЕА, — все контакты 1'-й цепи должны лежать на 1-м проводнике.
6. (17 А; сЕ ) (1! Атс Е1) (А1ПА1 - '' 1/ А;()Ат~ )т'н); Е„, Е, Š— если необходимо выполнить переход со слоя г на слой й пересечение областей должно иметь размер, достаточный для конструктивной реализации межслойного перехода. 214 Задача одновременной оптимизации всех соединений пока не решена, поэтому трассировка сводится к последовательному построению бесперекрестного леса, каждое дерево которого реализует соответствующую электрическую цепь, и определению конфигурации соединения, Система покрывающих деревьев должна быть размещена в монтажном пространстве типовой конструкции, заданном своей маиематической моделью (см.
з 8.3). Трассировка печатных соединений предполагает выполнение следующих этапов (см. 121!): 1. Определение порядка соединения выводов внутри цепи. 2. Распределение соединений по слоям печатной платы. 3. Нахождение последовательности проведения соединений в каждом слое. 4. Получение конфигурации проводников. При решении задачи трассировки используются следующие основные критерии: 1. Минимум суммарной длины всех проводников. 2. Минимум числа их пересечений, 3.
Минимум изгибов проводников. 4. Минимум числа слоев МПП и переходов со слоя на слой. 5. Минимальная длина параллельных участков соседних проводников. 6. Равномерное распределение проводников по монтажной области. Критерий 1 приводит к уменьшению задержки распространения сигналов по линиям связи, критерии 2, 3 и 4 повышают надежность н технологичность печатной платы, критерии 5 и б увеличивают помехоустойчивость конструктивной реализации схемы и вероятность проведения всех трасс Указанные критерии не удается объединить в обоб.
щенный показатель качества, поэтому на каждом этапе трассировки для конкретной технологии учитывается один наиболее важный критерий или указывается их приоритет. Определение порядка соединения выводов в н у т р и ц е и и. Задача сводится к построению минимального связывающего дерева. При печатном монтаже соединения можно выполнять не только по выводам, но и в любой точке проводника. Поэтому построение минимального связывающего дерева формулируется как задача Штейнера: к множеству Р = (р; 1 — — 1, а) основных добавить множество Я: — (д)') 1, т) дополнительных точек и построить покрывающее дерево минимальной длины.
Здесь множество Р основных точек сопоставлено выводам цепи, а дополнительные точки представляют собой места соединений типа проводник — проводник. При определении положения дополнительных точек можно рассматривать только узлы координатной решетки, построенной на п заданных точках. Тогда число таких точек Щ! и — 2. Метод точного решения задачи Штейнера для реальных цепей требует больших затрат машинного времени. Распределение соединений по слоям.Врезуль.
тате выполнения первого этапа трассировки электрическая цепь представляется минимальным покрывающим деревом, являющимся плоским графом Однако совокупность минимальных деревьев (лес) может иметь пересечения между ребрами, принадлежащими разным деревьям, так как последние строятся на фиксированных вершинах и существуют ограничения на размер монтажного поля, ширину проводников иг р ду .в .р„,,„ ки не должны пересекаться.
д м слое печатные проводни. При ортогональной трассировке возможно аси е ел ний по двум слоям. Кажда е возможно распределение соедине- го покрывающего дерев, аждая цепь представляется в ви де ортогональноа, вертикальные ветви кото ого в одном слое, а горизонтальн рого проводятся минима. ьное(а) и ортогональ Ш ьные — в другом. На ис. 10. рева необходимо делать ное тейпе ово б е е р д .
оличество переходов ть межслойные пе ехо ы. механические параметры печатной платы и и) снижает надежность схемы. При трассировке по произвольным наавлена задача правлениям может быть поставле разбиения графа схемы на минимальное ко- Г ~1 каждый из которых реализуется в своем слое.
е) Эта задача была рассмотрена в 38.2. О ная т рудность прн такой постановке заклюг~ чается в пост оени б ажающей свя построении модели схемы, точно ото- Рис. 108 М р вязность элементов и их гоно (и) и оргтогонвюное логические свойства. Ц)тв перово (й) перевел. аспределение соединений по слоя лоям может перекрывающиеся нря- быть ф~~~~~~~~ыы раскраски ве шин г а ак задача п авильн " р .
ои росеивюшиеси цели ~г), и вершин графа пересечений (см !7!) перосоквюшнесв леревьп редполагаем, что соединение полностью выполняется на одном слое. При ортогональной трассы (е) трассировке на вершинах каждой цепи строится минимал вающий прямоугопь и ( 1О 8 и к рис,в).Считается, что ва с ресекаются если перекр в П ываются соответств ющие и обходимо определять, пер и цепи минимальным пок ываю им р щим деревом не- деревьев. Для пары ветвей пересекается ли каждая па а в р ветвей этих тавляются уравнения пря, ей при известных коо ипатах вершин сос- мн аналитической геомет ии оп и ямых линий. есле я э соотве тствующих соединений, геометрии, определяют возможность пересечения Вершины г а а пе е устанавливают возможно р и р сечений сопоставляются сое ин оединениям, ребра фа будет правил ность их пе есечения. Р цветом.
инимальное количество цветов, кото рое необходимо окраски, определяет число слоев МПП. ерекрытне прямоугольников, построенных на ве ши или пересечение минимальн вершинах цепей, ет, что соответствую мальных покрывающих е ев д р ьев еще не означа- без пересечений. На и . 10.8 в ющие цепи нельзя п от асси р р ровать на одном слое ники (в) и непересекаю а рис.. показаны перек ываю и р щиеся прямоуголь- вершины; пересекаю а щиеся цепи г, соединяю ие ( ), щ охватываемые ими щиеся трассы (е), с щиеся минимальные е д ревья (д) и непересекаюе, соединяющие те же вершины.
При учете возможности п ове и едения «конфликтук»цих» проводииез пересечения за счет огибания, распределение соединений по 213 некоторые ячейки являются занятыми, к ним относятся ячейки, попадающие в области, запрегценные для трассировки: краевые поля монтажной платы, зоны размещения элементов и их выводов, ранее проведенные проводники. Основой алгоритма Ли является процедура нахождения оп нмального в смысле некоторого критерия пути между заданными ячейками а) й) Во второй части алгоритма, начиная с ячейки В, по определенным правилам выполняется переход от ячейки Й-го фронта к ячейке (й — !)-го фронта до ячейки А . Пройденные ячейки составляют искомый путь.
Условия, которые необходимо выполнить при проведении пути, и возможность оценки его оптимальности должны быть заложены в правила, по которым движется фронт волны. Для ячеек дискретного поля устанавливаются отношения соседства. Распространение волны заключается в присваивании ячейкам, соседним с ячейкой предыдущего фронта, значения весовой функции. Вес ячейки и-го фронта Р„ является функцией веса ячейки (й — 1)-го фронта.
В общем случае к весам предъявляется требование Р, , Ф РА М Р„„. В большинстве модификаций алгоритма Ли на веса накладывается ограничение Р, ~ Р„ ,. В этом случае проведение пути заключается в переходе от ячейки В к ячейке А таким образом, чтобы значение Р„ монотонно убывало. При этом возможен вариант, прн котором несколько ячеек, соседних данной, имеют одинаковый вес. Для однозначности выбора при учете критерия минимума изгибов проводника следует сохранять направление движения. Если приходится делать поворот, учитывается заранее заданный порядок предпочтительных направлений, например вверх, вправо, вниз, влево. Рассмотрим случай, когда соседними к данной являются ячейки, имеющие с ней общее ребро, а вес ячейки й-го фронта Рнс.
10.13. Фрагмент ДРП (а), посгроенпс пути, минимального в ортогональной метрике (б), по методу путевых коордпнаг (в), прн коднрованни по моду. лю 3 (г), с пспольаованнем и.- меток Акерса (Л) А и В ДРП (рис . 10.13, а) прн соблюдении ряда условий. Первая часть алгоритма моделирует процесс распространения волны из ячейки А по свободным ячейкам ДРП. При распространении волны от элементарной площадки А алгоритм последовательно строит Ф, (А) — первый, Фа (А) — второй, ..., Фа (А) — л-й ее фронты. Множество ячеек, входящих в ~'-е фронты„для всех ~' ( е называют л-й окрестностью ячейки А — 0„(А). Если проведение пути возможно, то на каком-то й -) 1-м шаге окажется, что ячейка В Е 0„.„(А). Если в следующий франт не удается включить ни одной свободной ячейки, т. е.
0„, (А) -== — — 0„(А), то при данных условиях путь провести невозможно. Таким образом эта часть алгоритма определяет возможность проведения пути между ячейками А и В. хвб (10.14) т. е. равен расстоянию й-й ячейки от исходной А в ортогональной метрике. На рис. 10.13, б проиллюстрирована работа алгоритма на примере соединения ячеек А и В. Волна распространяется из ячейки А, вес которой считаем равным нулю.
Фронт волны доходит до ячейки В на 12-м шаге. В ходе построения пути из ячейки с весом 11 можно перейти в три соседние ячейки с весом 10. Здесь переход осуществляется, сохраняя направление движения. Аналогично происходит переход из ячейки с весом 10. У ячейки с весом 9 есть две соседние ячейки с весом 8. Так как в данном случае приходится изменять направление движения, переход выполняется по предпочтительному направлению вверх. Поскольку вес Уг-й ячейки Р„в данном варианте алгоритма был равен ее расстоянию от ячейки А в ортогональной метрике, найденный путь оптимален в смысле его длины в этой метрике. Так как алгоритм Ли представляет собой алгоритм нахождения кратчайшего пути в графе, он легко распространяется на многослойный печатный монтаж при использовании модели в виде графа монтажного пространства (см.
3 8.3). При наличии ограничений на переходы со слоя на слой можно увеличить вес ребра, соединяющего две смежные вершины на соседних слоях, по сравнению с весом ребра, соединяющего смежные вершины одного слоя. В общем случае весовая функция или критерий качества пути может зависеть от параметров, учитывающих длину пути, число перехо- 3 А. Я. Савельев, В. А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
