Задача трассировки состоит в построении для всех цепей схемы оптимальных монтажных соединений. Метрический аспект задачи предполагает учет конструктивных размеров элементов, соединений и коммутационного поля. Топологический аспект связан с выбором допустимого пространственного расположения отдельных монтажных соединений при ограничениях на число пересечений соединений, число слоев коммутационной схемы и т. п. Классификация методов трассировки представлена на рис. 2.
Алгоритмические методы трассировки печатных соединений существенно зависят от конструкции коммутационного поля и могут быть разделены на две основные группы:
1) топографические методы - в них приоритет отдается метрическому аспекту задачи;
2) графо-теоретические метод решения задач трассировки.
Топографический метод трассировки содержит следующие этапы:
1) получение списка соединений;
2) распределение соединений по слоям;
3) определение порядка прокладки соединений;
4) трассировка отдельных соединений.
Основной задачей первого этапа является предварительное определение порядка соединений выводов внутри отдельных цепей. Такое упорядочение осуществляется с помощью алгоритмов построения минимальных деревьев. При печатном монтаже соединения могут выполняться не только по выводам, но и в любой точке проводника. Поэтому построение КСД формулируется как задача Штейнера. Метод же решения задачи Штейнера требует больших затрат машинного времени.
На втором и третьем этапе решаются вопросы, на каком из слоев будет осуществляться трассировка соединений и в каком порядке. Некоторые методы расслоения основаны на анализе взаимного расположения выводов отдельных цепей, другие - на анализе совмещенной в одной плоскости топологии всех соединений, полученной с помощью применения алгоритма построения минимального дерева независимо для каждой отдельной цепи.
При последовательной трассировке отдельных соединений порядок их прокладки должен быть определен заранее. Существуют различные тактики упорядочения соединений, однако ни одна из них не может считаться вполне удовлетворительной. В связи с этим более предпочтительны динамические процессы трассировки, когда производится перетрассировка неудачно проложенных соединений или порядок прокладки определяется в зависимости от ситуации, сложившейся на ранних этапах процесса. Но использование динамических процессов трассировки должно опираться на быстрое осуществление прокладки отдельных соединений.
Для трассировки отдельных соединений предложены разные алгоритмы, различающиеся скоростью и требуемым объемом памяти при реализации на ЭВМ, а также качеством получаемого результата. Основными из них являются:
1) волновой алгоритм и его модификации;
2) алгоритмы трассировки по магистралям и каналам;
3) комбинированные алгоритмы.
Эффективность применения каждого из алгоритмов определяется рядом факторов: конструкцией коммутационного поля, ресурсами машинного времени и памяти ЭВМ, сложностью схемы соединений и другие.
Реализация волнового алгоритма предполагает введение дискретного рабочего поля (ДРП), являющегося моделью коммутационной платы для отображения в памяти ЭВМ. В связи с этим был предложен ряд способов эффективного сокращения объема информации при отображении процесса трассировки и его результатов в памяти ЭВМ.
Другое направление повышения эффективности алгоритма связано с увеличением средней скорости распространения волны при поиске трассы соединения. Сюда относятся такие приемы, как ограничение области распространения волны, использование метода встречной волны, задание преимущественного направления волны и др. Исследованы вопросы применения волнового алгоритма для оптимизации соединения по совокупности параметров (длине, числу пересечений, числу поворотов и т. д.), для трассировки многоконцевых и многослойных соединений.
Основными недостатками различных модификаций волнового алгоритма являются значительные затраты времени и памяти для представления ДРП, особенно ДРП больших размеров. В связи с этим определенный интерес представляют новые модификации алгоритма.
Повышение скорости трассировки может быть достигнуто при организации процесса прокладки соединений по магистралям. Так как конфигурации подавляющего числа реальных соединений, имеют простой вид, это приводит к сокращению затрат времени на, трассировку соединений, особенно на слабо заполненном коммутационном поле. По мере заполнения поля эффективность алгоритма уменьшается и начинает приближаться к эффективности волнового алгоритма. Основным достоинством алгоритма является отсутствие ДРП, что снижает требования к объему памяти при реализации данного алгоритма.
К этой же группе примыкают эвристические алгоритмы построения малоповоротных путей, в которых осуществляется построение соединений простой конфигурации (до 3-4 изгибов). По имеющимся данным, подобные алгоритмы позволяют осуществить разводку до 90% всех соединений в двухслойных схемах с ортогональными соединениями. Остальные соединения трассируются с помощью волнового алгоритма.
Алгоритмы трассировки по каналам применяются в случае, когда на коммутационном поле естественным образом могут быть выделены горизонтальные и вертикальные каналы для реализации соединений. Каналы образуются между рядами регулярно расположенных на поле элементов или определяются сетью фиксированных металлизированных переходных отверстий. Наиболее эффективная стратегия трассировки в данном случае включает два этапа: распределение соединений по каналам и трассировку внутри каналов. Разновидностью трассировки по каналам является трассировка на сети укрупненных ячеек (граней), образованных на коммутационном поле между разногабаритными элементами. Основные достоинства канальной трассировки - отсутствие ДРП, возможность планирования плотности соединений на отдельных областях коммутационного поля, большая скорость построения соединений.
В ряде конструкций электронных схем параметры размещения элементов и конфигурации трасс соединений сильно взаимосвязаны, и потому расчленение общей задачи проектирования топологии схемы на два традиционных этапа: размещение элементов и трассировку соединений - неоправданно. Характерными особенностями таких конструкций являются нерегулярность расположения элементов и соединений, их разнотипность, наличие одного слоя коммутации. Примерами могут служить односторонние печатные платы с микросхемами и навесными радиодеталями, гибридные микросхемы и биполярные интегральные схемы с одним слоем коммутации.
В последнее время проводятся интенсивные исследования по применению теоретико-графовых методов к конструированию топологии схем подобного рода, поскольку другие методы трассировки в этом случае оказываются малоэффективными. Теоретико-графовый метод предполагает предварительный анализ планарности схемы, представленной в виде графовой модели, и последующую ликвидацию имеющихся пересечений с помощью возможных технологических приемов. Заключительная фаза состоит в построении эскиза топологии схемы при рациональном распределении функций между конструктором и ЭВМ.