Трассировка по магистралям

Волновой алгоритм в той или иной модификации является основой большинства развитых программ машинной трассировки ввиду его универсальности.

Однако в определённых ситуациях эффективнее применять другие алгоритмы, которые дают более быстрое и качественное решение.

Алгоритмы построения соединений с малым числом поворотов (лучевой алгоритм).Это такой алгоритм трассировки, в котором основные процедуры поиска и проведения пути осуществляются путём исследования пространства магистралей (линий), а не ячеек ДРП, как в классическом алгоритме Ли.

Для построения процесса рассмотрим ДРП (рис. 5).

Рисунок 5 -  Магистрали первого уровня

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

Будем считать их магистралями первого уровня (фронта) и обозначим их, соответственно, и .

В простейшем случае, когда эти магистрали пересекутся, сразу получаем искомое соединение.

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

Если магистрали и не пересекаются, строим магистрали второго уровня (фронта). Соответственно, для точек и (рис. 6).

Рисунок 6 -  Магистрали второго уровня

На рис. 6 и - магистрали второго уровня.

Эти магистрали перпендикулярны к магистралям первого уровня и проводятся через точки, расположенные в узлах основной сетки. Назовём эти точки базовыми.

При переходе с магистралей первого уровня на магистрали второго уровня в возможную конфигурацию соединения добавляется один поворот.

Использование алгоритма трассировки по магистралям приводит к минимизации числа переходов при трассировке двухслойных схем с ортогональными соединениями. Такие пути называются простейшими или малоповоротными.

В общем случае процесс построения магистралей -го уровня состоит в выборе базовых точек на магистралях i - го уровня и проведении через них отрезков нормалей, не пересекающих области, запрещённые для проведения соединений.

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

В последнем случае может быть построен путь, содержащий поворот (переход).

Для минимизации длины пути применяется следующая процедура.

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

Аналогичная процедура применяется для магистралей всех уровней точки В.

Результирующий путь состоит из выбранных отрезков и содержит минимальное число поворотов.

Рассмотренный принцип трассировки по магистралям с незначительной модификацией может быть использован для построения многоконцевых соединений.

Следует отметить, что при программной реализации алгоритма на ЭВМ можно отказаться от матричного способа кодировании КП. Поэтому время работы алгоритма и требуемый объём памяти не зависят прямым образом от размеров КП, а определяются, главным образом, сложностью конфигураций уже приложенных соединений. В связи с этим трассировка по магистралям с точки зрения затрат времени и памяти ЭВМ более эффективна, чем волновой алгоритм, для полей большой площади, причём требуемые затраты времени существенно меньше для слабо заполненных полей. По мере заполнения поля трассами соединений эффективность процесса поиска снижается и временные затраты ЭВМ приближаются к затратам времени волнового алгоритма.

Осуществим трассировку схемы с использованием волнового и лучевого алгоритмов (рис. 7).

Рисунок7 -  Трассировка схемы по магистралям

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

Рассмотренные алгоритмы показывают эффективность их комплексного использования в зависимости от конкретных условий.