КТОП теория

Построение числовой волны начинается с выбора в качестве начальной точки произвольного вывода, например источника s. В процессе формирования числового фронта волны всем свободным квадратам, соседним с квадратами предыдущего фронта, ставится в соответствие число q, называемое весом квадрата. Это число пропорционально заданной весовой функции F, которая является критерием качества трассы и характеризует путь определенным комплексом параметров (длина, число пересечений с другими проводниками, число переходов из слоя в слой и т. п.). Основной критерий – минимальная длина трассы.

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

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

Второй этап − проведение трассы. Для этого просматриваются все отмеченные квадраты в обратном порядке от В. Сначала просматриваются квадраты, соседние с квадратом В и выбирается тот, у которого вес минимален. Затем выбираются квадраты соседние с выбранным и имеющие минимальный вес и т. д., пока не будет достигнут квадрат А. Координаты выбранных квадратов в совокупности описывают некоторую трассу между выводами А и В.

Особенности реального волнового алгоритма. Эти особенности следующие:

-вход и выход трасс могут представляться более чем одной клеткой;

-программ подсчитывает число ячеек, используемых в каждом направлении каждого слоя, и число переходных отверстий. Затем все используемые ячейки и переходные отверстия умножаются на соответствующие веса, определенные в стратегии разводки. Ищется путь с минимальным весом, который исполняется, если есть альтернативные варианты трассировки;

-ищутся в первую очередь возможные варианты трассировки в направлении, по которому расположен вывод-приемник (В);

-волновой алгоритм работает и по диагонали;

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

-возможно размещение выводов и не в узлах координатной сетки;

-для цифровых схем типа “память” выполняется трассировка коллинеарных трасс по Х или по У (рис.11.3).

Всовременных пакетах трассировки применяют алгоритм RIP-N-ROUTE (Стираю и развожу), особенности которого следующие:

-используют алгоритм Rip – up (“стираю”), который позволяет максимально увеличить процент разведенных цепей;

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

-используют метод “уплотнения трасс”;

-программа автоматически определяет, какие проводники уже проведены

ине проводит их повторной трассировки;

-предварительно размещенные проводники могут участвовать в формировании Т-образных соединений;

-выполняется разводка шин – они воспринимаются как большие прямоугольные области.

11.2. Модификации волнового алгоритма

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

где ai – весовой коэффициент, учитывающий важность i-го параметра; рi (k) – значение учитываемого параметра.

Усложнение функции веса увеличивает объем информации на одну ячейку дискретного рабочего поля (ДРП) и время работы первой части алгоритма. Кроме того, не представляется возможным строго обосновать выбор значений весовых коэффициентов аi .

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

.

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

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