При реализации блока 4 проводится проверка выполнения условия {Фк}¥=0, т. е. выясняется наличие в составе /(-фронта элементов, имеющих такие же по направлению путевые координаты, что и элементы предыдущего фронта, по номерам которых выполнено присвоение, путевых координат. На рис. 1.24 показано, что распространение волны идет и через занятые элементы, останавливаясь только при достижении запретных.

Такими на рис. 1.24 будут, например, элементы с координатами (5, 8), (3, 10) и (5, 14).

Г5 14

13 12 11

. / 2 3 4 5 6 7 8 S 10 11 12 13 П 13 16 17 18

Рис. 1.24. Пример определения трассы с помощью волнового алгоритма прокладки пути с минимальным числом изменений направления

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

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

Если при записи координат трассы АВ встретился элемент с двумя путевыми координатами, то предпочтение отдается той из них, которая не меняет направления проводника. Например, нз рис. 1.24 дан случай, когда при прохождении трассы через эле-

менты с координатами (13, 8) и (13, 9)приоритет имеет вертикальное направление.

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

Нами рассмотрено 4 модификации волнового алгоритма, причем в основу каждой положены различные критерии качества. На практике задача трассировки, как правило, формулируется более сложно, так как требуется одновременно удЬвлетворять нескольким критериям. Если между критериями качества имеются количественные соотношения, то создание такого алгоритма не представляет труда.

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

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

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

Волновой алгоритм обладает наибольшей универсальностью из всех известных алгоритмов, однако ему присущи весьма серьезные недостатки. Как было показано, моделирование распространения волны вызывает необходимость в анализе большого числа элементов. В пределе это могут быть все элементы пространства платы, число которых на одном слое современных многослойных плат может достигать 1 млн. В связи с этим применение волнового алгоритма ставит в ряде случаев невыполнимые требования в смысле машинного времени и объема памяти ЗУ. Это заставляет конструкторов во многих случаях применять менее универсальные, но более экономичные алгоритмы трассировки.

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

1. Распространение фронтов лучей от обоих конечных элемен-, тов трассы по заранее определенным направлениям. Моделирование лучей оканчивается, когда на некотором элементе встре-

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

Будем обозначать лучи, распространяемые от элемента А-Л-лучами, а от элемента В - Б-лучами. При двухлучевом алгоритме от каждого конечного элемента распространяется по 2 луча: Лрлуч, Лг-луч, Брлуч, Бг-луч. Следовательно, в этом случае каждый /(-фронт содержит не более 4 элементов. Распространение каждого луча прекращается, когда он попадает в элемент, все соседние элементы которого являются занятыми или запрещенными.

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

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

ВВод Зонных

2 Вычисление приоритетных направлений распространения лучей

3 Вычиспение ноординат множества элементов (Фк)

* Проверка Выполнения условия (F,,} + 0

5 Присвоение путевых координат -мно/кестви элемен-

Проверка Выполнения успоВия-

8 Запись трассы АВ в список, непроведен-ных соединений

7 Запись координат трассы АВ

Рис. 1.25. Структурная схема двухлучевого алгоритма трассировки без пересечения ранее проложенных проводников