 |
Алгоритмы. Задачи трассировки.
|
|
|
|
Исходными данными для решения задач трассировки межэлементного соединения некоторого узла, являются параметры коммутационного поля – размеры коммутационного поля узла, координаты всех контактных площадок и внешних выводов печатной платы, координаты контактов разъема и т.д. Координаты контактов каждого конструктивного элемента на коммутационном поле, определяют по результатам размещения элементов в узле. Список всех элементных цепей и перечень конструктивов элементов, относящихся к каждой отдельной цепи, составляют по схеме соединений элементов.
В результате решение задачи трассировки необходимо соединить печатными, пленочными или навесными проводниками все контакты элементов согласно электрической схеме соединений с учетом определенных требований и ограничений.
В зависимости от способа реализации соединений критериями оптимальной трассировки могут быть минимизация и суммарная длина соединений, минимальное число слоев монтажа, минимальное число переходников их слоя в слой, минимальные наводки в цепях связей элементов.
К числу ограничений, обусловленных в основном технологическими процессами относятся: для проводного монтажа максимальное число нагрузок на один контакт, тип монтажа: в навал или жгутовой, длина проводников и т.п.
Для печатного монтажа – ширина проводников и расстояние между ними, число проводников, проводимых к первому контакту, максимальное число слоев платы и т.д.
Разнообразие требований и ограничений привело к тому, что для каждого способа реализации межэлементных соединений существуют свои специфические методы и алгоритмы задачи трассировки, причем в каждом конкретном случае задачи трассировки решаются последовательно в несколько самостоятельных этапов. Это связано с большой трудоемкостью формализации и оптимизации задачи на ЭВМ, т.к. в данном случае необходимо оперировать геометрическими образами, а это требует больших затрат памяти и машинного времени ЭВМ.
|
|
|
Во почему не один из существующих методов алгоритмов трассировки не в состоянии конкурировать по качеству проведения соединений с высококвалифицированным конструктором.
Рассмотрим основные методы и алгоритмы на примере решения отдельных этапов задачи трассировки, многоблочной печатной платы, т.к. эти методы в той или иной модификации используются для решения многих других задач трассировки.
Конструктивы многослойной печатной платы представляют собой совокупность монтажных слоев, расположенных один под другим. Монтажный слой – плоскость ограниченных размеров, на которую условно нанесена координатная сетка линий, определяющая места прокладки печатных проводников. Шаг координатной сетки определяет ограничения на ширину проводников и минимальные расстояния между ними.
Вопрос №17
Решение задачи трассировки в многослойной печатной плате предполагает решения следующих этапов:
1. Определение перечня, списка всех проводников, которые должны быть проложены между парами различных контактов.
2. Распределение проводников по слоям.
3. Определение последовательной трассировки проводников в каждом слое.
4. трассировка проводников.
На 1-ом этапе необходимо решить в какой последовательности следует соединить контакты одной цепи, чтобы суммарная длина всех соединений была минимальной. Эта задача сводится к задаче построения минимального связывающего дерева. Наибольшее распространение для решения этой задачи на ЭВМ получил алгоритм Прима.
2-ой этап выполняется двумя способами:
1) Последовательно проводят соединения до заполнения очередного слоя, после чего переходят к заполнению следующего слоя.
|
|
|
При таком подходе получается большое число слоев и неравномерное их заполнение.
2) Подсчитав число пересечений проводников, совмещают в первом слое, а затем проводят распределение по слоям.
3-й этап: Определение порядка трассировки успех трассировки очередного проводника существенно зависит от конфигурации уже проведенных трасс. Для решения этой задачи разработаны эвристические алгоритмы, т.к. задача не формализуется теоретическими методами. Наибольшее распространение получили методы упорядочивания, основанные на оценке длины проводников. Здесь возможны два различных подхода: 1) соединение проводников в порядке возвратности длины отдельных проводников (кратчайшее расстояние между соединенными контактами); 2)соединение проводников в порядке убывания их длины, т.к. более длинные проводники труднее трассировать. С точки зрения минимализации суммарной длины соединений оба подхода дают приблизительно одинаковые результаты. Другие методы упорядочивания связаны с учетом степени величины проводников друг на друга по площади перекрытия минимальных прямоугольников, с подсчетом числа контактов, попадающих в минимальный прямоугольник или другими эвристическими критериями.
4-й этап Трассировка соединений заключается в последовательном построении трасс в каждом слое для всех контактов с учётом заданных требований и ограничений. В большинстве известных методов трассировки вся плоскость разбивается на квадраты, размер которых равен допустимому расстоянию между проводниками.
Вопрос №18
Существующий алгоритм проведения трасс между двумя контактами можно условно разбить на две группы, основанные на цепях волнового алгоритма и эвристического.
Волновой алгоритм (алгоритм Ли) позволяет находить кратчайшие трассы оптимальные по целому ряду параметров и являющиеся универсальными. В волновом алгоритме можно выделить 2 этапа: распределение числовой волны и проведение трассы. На первом этапе всё множество квадратов … поля разделяют на две группы:
- под множество свободных квадратов 
- под множество занятых квадратов 
Трассы могут проходить только по свободным квадратам причём после проведения трассы все её свободные квадраты считаются занятыми.
|
|
|
На втором этапе волнового алгоритма осуществляется проведение трассы, для этого рассматриваются все квадраты отмеченные в обратном порядке.
Характеризуется универсальностью и всегда находит кратчайшую трассу. Главный недостаток этого алгоритма большой объем памяти и большие затраты машинного времени. сокращение затрат памяти и времени ЭВМ можно достичь применяя лучевой алгоритм трассировки.
Основная идея лучевого алгоритма заключается в исследовании не всех квадратов, а только части из них по некоторым заданным направлениям, подобно лучам.
В двух лучевом алгоритме от каждого контакта Xi и Xj распространяются по двум лучам и каждый фронт содержит не более четырех элементов.
Троса …, если лучи от разных контактов пересекаются в некотором квадрате. Основная часть времени при выполнении волнового алгоритма затрачивается на распределение волны. С целью сокращения этого времени используют метода встречной волны. Сокращение затрат времени и памяти ЭВМ достигается применением лучевых алгоритмов трассировки.
Эвристический алгоритм трассировки – это наиболее быстродействующий алгоритм и, в отличии от волнового алгоритма в них не рассматриваются все возможные трассы для выбранных вариантов, а сразу стремятся распределить трассу по кратчайшему пути.
В алгоритмах итерационного типа на первом этапе все трассы прокладываются без учета взаимного влияния. После этого проводится анализ взаимного расположения трасс. Трассы которые имеют max длину, max число пересечений удаляются, после чего проводится их повторная трассировка.
Канальный алгоритм – это алгоритм основан на прокладке трасс по укрупненным дискретам, представляющим собой каналы. Каналы характеризуются пропускной способностью т.е. допускают количество, проходов через него магистралей. Каналы обращаются как правило между рядами устройств элементов или компонентов. При проектировании БИС производится предварительная трассировка, в результате которой определяют области по которым пройдет трасса. Такими областями обычно служат каналы, незанятые элементами, либо отдельные свободные участки. Главная цель предварительной трассировки – равномерное распределение цепей без превышения пропускной способности каналов.
|
|
|
