КТОП теория

11. ЗАДАЧА ТРАССИРОВКИ И АЛГОРИТМЫ ЕЁ РЕАЛИЗАЦИИ

11.1. Решение задач трассировки

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

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

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

Алгоритмические методы трассировки, классификация которых приведена на рис. 11.1, несмотря на их многообразие, не гарантируют проведения 100% соединений. По способу построения трасс методы трассировки разделяются на конструктивные и итерационные.

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

Рис 11.1.1 Пример трассировки соединений

б- минимизация числа пересечений;

Рис 11.1.1 Пример трассировки соединений

в- устранение пересечений (не проведенное соединение 13)

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

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

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

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

Выполнение алгоритма производится в два этапа: 1) распространение числовой волны; 2) собственно проведение трассы. Работает алгоритм по сетке квадратов монтажного пространства, множество которых разделяется на две группы: подмножества свободных квадратов и подмножество занятых.

Перед началом каждого прохода программа создает карту из всех точек сетки, заданной в стратегии трассировки. Принцип трассировки приведен на рис. 11.2.