Трассировка межсоединений является одним из наиболее трудоёмких этапов проектирования печатного монтажа и заключается в проведении на плате всех электрических связей схемы с учетом заданных ограничений: отсутствие пересечений (нарушение по зазорам между печатными проводниками), минимальное количество переходных отверстий и изгибов печатных проводников, минимизация длины печатных проводников, правильное подключение к контактным площадкам (с технологической точки зрения), расстановка фанаутов (межслойных переходов, соединённых с планарными выводами электронного компонента и расположенных в непосредственной близости от него. Создание фанаутов является одним из способов трассировки при высокой плотности монтажа) и т.д. Такое разнообразие технологических требований и конкретных параметров печатного монтажа повлекло создание большого количества узкоспециализированных алгоритмов и привело к невозможности сравнительной оценки различных методов трассировки, определения степени влияния на результирующую плотность монтажа того или иного ограничения. Так, например, количество непроведенных соединений не может служить характеристикой алгоритма без тщательного анализа конструкции, технологии и параметров схемы. Известные алгоритмы ориентированы на применение ручной дотрассировки непроведенных соединений. Поэтому в настоящее время актуальна задача совершенствования алгоритмов, а также разработки и применения новых принципов трассировки.
При разработке автотрассировщиков используется теория графов. Использование алгоритмов теории графов объясняется тем, что граф, сохраняя наглядность и содержательность отображаемого им объекта, позволяет также строить формальные алгоритмы преобразования и легко описывается на языках программирования либо с помощью структур типа ссылка, либо при помощи различных матричных структур, соответствующих графу.
В основе многих алгоритмов автотрассировки лежит алгоритм С. Ли, называемый также волновым алгоритмом, лучевой алгоритм, канальные методы.
Волновой алгоритм
В основе алгоритма Ли и его модификаций лежат два этапа - распространение волны и проведение трассы. На первом этапе плата разбивается на прямоугольные площадки. Трассировка сводится к выявлению площадок, соединяющих элементы a и b, соответствующие выводам электронных компонентов. На втором этапе задается весовая функция F=F(f1,f2,…,fi), являющаяся критерием качества пути. Аргументами весовой функции fi являются численные характеристики данной трассы - длина пути, число пересечений, переходов со слоя на слой и т.д. Следует отметить, что выбор весовой функции – одна из главных задач при проектировании соответствующего алгоритма автотрассировки. Начиная с элемента a прямоугольным площадкам, расположенным рядом с рассмотренными, присваивается определенное значение весовой функции F=m(i,j), называемое весом. Эта процедура продолжается до тех пор, пока элементу b не будет присвоено некоторое значение массы (ib, jb). Перемещаются от элемента b к a по пройденным площадкам, следя за тем, чтобы значение масс площадок убывало монотонно (или возрастали, в зависимости от выбранной целевой функции). Получают трассу, соединяющие элементы a и b. Алгоритм позволяет установить, существует ли путь между элементами, удовлетворяющий определенным критериям, и если такой путь есть, то найти его.
Недостатком волнового алгоритм является необходимость просматривать все клетки монтажного пространства даже в том случае когда соединение несложной формы. Кроме того, данный алгоритм требует значительных затрат машинного времени: 90% на математические вычисления распространения волны, 10% для проведения пути. Более того, существует проблема очередности проведения трасс.
В этих случаях целесообразно использовать лучевые алгоритмы трассировки (в частности, известен алгоритм Л.Б. Абрайтиса).
Лучевой алгоритм
Основная идея лучевого алгоритма состоит в исследовании решетки для определения пути между вершинами по некоторым заранее заданным направлениям - лучам. Задаётся количество лучей, распространяемых из точек А и В, соответствующих выводам, а также порядок присвоения путевых координат. Обычно число лучей для каждой из точек равно двум. Лучи распространяются одновременно из точек А и В до встречи в некоторой точке С. При помощи лучевого алгоритма не всегда удается решить задачу, поэтому его целесообразно применять совместно с волновым алгоритмом.
Канальный алгоритм
Помимо волнового алгоритма и его модификаций в САПР печатных плат используют алгоритмы, основанные на методе прокладки каналов. Сущность канальных алгоритмов заключается в следующем. Определяют области и пути прохождения трасс. Для этого поле печатной платы разбивают на полосы-каналы. Пропускная способность каналов определяется числом магистралей, которые можно проложить в слое, а также загрузкой канала, под которой понимается число, трасс, проложенных в канале.
Каждая цепь разделяется на прямолинейные фрагменты, которыми оперируют в пределах каналов. Задача проектирования соединений сводится к задаче оптимального по ряду критериев назначения фрагментов цепей в каналы и магистрали. Предварительно все цепи размещают по каналам в одном слое по критерию минимума суммарной длины. Затем фрагменты цепей в пределах канала упорядочивают относительно друг друга по критерию минимума пересечений. Строят граф пересечений, вершины которого соответствуют цепям схемы. Две вершины связывают ребром, если соответствующие им цепи пересекаются хотя бы в одной точке. Далее раскрашивают вершины графа пересечений в минимальное число цветов, причем одним цветом не связанные между собой вершины, что соответствует разнесению цепей схемы в наименьшее число слоев. На следующих этапах производится упаковка фрагментов цепей и распределение по магистралям, расчет координат фрагментов и вывод информации.
Работа канального алгоритма состоит из двух этапов. На первом этапе вычисляются таблицы загрузки каналов, затем каждая вершина и каждый участок канала между двумя вершинами представляется в укрупненном рабочем поле одной элементарной площадки. При распространении волны площадкам присваивают путевые координаты и веса. Распространяющаяся волна скачком переходит от одной вершины координатной сетки к другой независимо от фактической длины канала между этими вершинами. Трасса прокладывается по участкам канала с наименьшим весом. На втором этапе алгоритма производится распределение трасс внутри каналов по магистралям.
Некоторую особенность имеют алгоритмы автоматической трассировки, работающие более чем в двух слоях. В этом случае одним из наиболее существенных ограничений является сведение к минимуму длины проводников, идущих параллельно в разных слоях. Наличие таких участков приводит к паразитным наводкам и препятствует повышению быстродействия схемы. Кроме того, технологически трудно осуществить переход из слоя в слой в любой точке платы. В этом случае целесообразно начинать проведение трасс с кратчайших соединений, переходя затем к более длинным связям, что позволяет значительно повысить плотность монтажа.
Рассмотренные алгоритмы имеют общей чертой наличие координатной сетки. Принципиально отличными от них являются бессеточные алгоритмы программы SPECCTRA, осуществляющие трассировку в ортогональном режиме, а также под углом 45 градусов. Кроме того, следует отметить и отечественный программный продукт по автоматической трассировке печатных плат TopoR, который в настоящее время уже интегрирован в отечественную САПР Delta Design, начиная с версии 3. Алгоритм трассировщика TopoR позволяет реализовать топологическую трассировку печатной платы – трассировка под любым углом, что имеет важное значение с точки зрения уменьшения длины соединений, числа слоев печатной платы, числа переходных отверстий, а также в реализации топологии с учетом целостности сигнала в аппаратуре радиоэлектронных средств, работающей на высоких частотах.
Указанные трассировщики имеют свои достоинства и недостатки, связанные с тем, что сложность проблемы трассировки связана с трудностями формализации факторов и критериев, влияющих на конечный результат и как следствие отсутствие математических моделей и методов глобальной оптимизации и решений конфликтных ситуаций.