14. Трассировка соединений. Критерии и ограничения, этапы решения задачи трассировки.

1. Постановка задачи, критерии оптимизации и ограничения.

С математической точки зрения – трассировка наисложнейшая задача выбора из огромного числа вариантов оптимального решения.

Полная оптимизация всех соединений за счет перебора всех вариантов в настоящее время невозможна. Поэтому разрабатываются в основном локально-оптимальные методы трассировки, когда трасса оптимальна лишь на данном шаге, при наличии ранее проведенных соединений.

Основная задача трассировки формулируется следующим образом: по заданной схеме соединений проложить необходимые проводники на плоскости, чтобы реализовать заданные электрические соединения с учетом определенных требований и ограничений.

Исходными данными для задачи трассировки являются: список цепей, параметры конструкции элементов и коммутационного поля, данные по размещению элементов.

В зависимости от способа реализации соединений (печатный или проводной монтаж) критериями оптимальности трассировки могут быть: минимальная суммарная длина соединений, минимальное число слоев монтажа, минимальное число переходов из слоя в слой, минимальные наводки в проводниках, процент трассировки и т.д.

Оценка качества ведется по доминирующему критерию при ограничениях на другие критерии, либо применяют аддитивную форму целевой функции:

, где - весовой коэффициент; - частный критерий.

Ограничения для задачи трассировки можно разделить на конструкторские и технологические. К технологическим ограничениям относятся (для печатного монтажа): ширина проводников и расстояния между ними, максимальное число слоев, минимальное расстояние между контактными площадками и т.п.

К конструктивным ограничениям относятся: размеры коммутационного поля, наличие проводников, трассы которых уже заданы, максимальная длина проводников, участки, запрещенные для трассировки и т.п.

2. Этапы решения задачи трассировки.

Для каждого способа реализации монтажа (проводной и печатный) существуют свои методы и алгоритмы решения задачи трассировки.

Рассмотрим основные методы и алгоритмы на примере решения задачи трассировки соединений многослойной печатной платы. Задача решается в несколько самостоятельных этапов:

1. Определение перечня (списка) всех проводников, которые должны быть проложены между парами различных контактов.

2. Распределение проводников по слоям.

3. Определение последовательности трассировки проводников в каждом слое.

4. Собственно трассировка проводников.

На первом этапе необходимо решить, в какой последовательности соединять контакты, принадлежащие одной цепи, чтобы суммарная длина всех соединений была минимальной. Эта задача сводится к построению минимального связующего дерева (МСД), то есть такого, чтобы суммарная длина его ребер была минимальной.

На втором этапе определяется планарность графовой модели схемы (возможность расположения ребер на плоскости без пересечений) на основе теории графов и если она планарная, производится её плоская укладка. Если же модель не планарная, решают задачу распределения ребер графа по слоям. В зависимости от организации процесса трассировки, расслоение осуществляется либо до, либо после, либо в процессе трассировки.

При определении порядка трассировки проводников используют в основном два подхода:

1. соединение проводников в порядке возрастания длины проводников;

2. соединение в порядке убывания длины.

Первый способ основан на том соображении, что короткие проводники вносят меньше конфликтных ситуаций, а второй на том, что длинные проводники труднее трассировать.

Собственно трассировка соединений заключается в последовательном построении трасс в каждом слое для всех пар контактов, с учетом определенных требований и ограничений. В большинстве известных алгоритмов вся плоскость платы разбивается на квадраты (хотя возможны треугольники или другие фигуры). Максимальные размеры ячеек определяются допустимой точностью воспроизведения проводников. Минимальные размеры обуславливаются объемом памяти ЭВМ и соотношением: , где - расстояние между центрами ячеек; - ширина проводника; - минимальное расстояние между проводниками.

В каждой ячейке обычно располагается только один вывод или печатный проводник. Трассой между контактами и называется совокупность соседних ячеек, соединяющих эти контакты.