КТОП теория
.pdfПостроение числовой волны начинается с выбора в качестве начальной точки произвольного вывода, например источника s. В процессе формирования числового фронта волны всем свободным квадратам, соседним с квадратами предыдущего фронта, ставится в соответствие число q, называемое весом квадрата. Это число пропорционально заданной весовой функции F, которая является критерием качества трассы и характеризует путь определенным комплексом параметров (длина, число пересечений с другими проводниками, число переходов из слоя в слой и т. п.). Основной критерий – минимальная длина трассы.
При трассировке расстояние между соседними квадратами принимается равным единице. Всем свободным квадратам присваивается вес, равный расстоянию от начального квадрата, соответствующего выводу А, до данного квадрата в ортогональной метрике. Совокупность квадратов одинакового веса называют фронтом волны. На каждом шаге распространения волны всем свободным квадратам, соседним с квадратами предыдущего фронта, присваивается вес на 1 больше. При этом номер фронта совпадает со значением веса квадратов и числом шагов алгоритма. Волна распространяется до тех пор, пока не достигнет вывода-приемника t или в очередном фронте не будет свободных квадратов. В первом случае трасса существует и её минимальная длина равна числу шагов, во втором – трасса отсутствует. Это простейший случай.
В более сложном алгоритме после достижения вывода – приемника t её генерация прекращается, и программа начинает анализировать полученную карту для прокладки трассы. Теперь основным критерием для неё являются цены, установленные в стратегии трассировки. При оценке проложенной трассы программа умножает число, стоящее в клетке, на цену трассы в данном направлении. При этом программа также пробует ставить и переходные отверстия при обходе какого-либо препятствия (другой трассы, барьера). Из всех вариантов выбирается наиболее “дешевый”, вновь пускается волна − процесс продолжается до тех пор, пока не будет достигнут требуемый вывод или не заполнятся все свободные квадраты, что определяет невозможность проведения данного проводника.
Второй этап − проведение трассы. Для этого просматриваются все отмеченные квадраты в обратном порядке от В. Сначала просматриваются квадраты, соседние с квадратом В и выбирается тот, у которого вес минимален. Затем выбираются квадраты соседние с выбранным и имеющие минимальный вес и т. д., пока не будет достигнут квадрат А. Координаты выбранных квадратов в совокупности описывают некоторую трассу между выводами А и В.
Особенности реального волнового алгоритма. Эти особенности следующие:
-вход и выход трасс могут представляться более чем одной клеткой;
-программ подсчитывает число ячеек, используемых в каждом направлении каждого слоя, и число переходных отверстий. Затем все используемые ячейки и переходные отверстия умножаются на соответствующие веса, определенные в стратегии разводки. Ищется путь с минимальным весом, который исполняется, если есть альтернативные варианты трассировки;
-ищутся в первую очередь возможные варианты трассировки в направлении, по которому расположен вывод-приемник (В);
-волновой алгоритм работает и по диагонали;
-для трассировки планарных элементов на МПП генерируются “стрингеры” от каждого планарного вывода (“стрингер”- это короткий проводник от вывода элемента до сквозного переходного отверстия); стрингеры улучшают трассировку, т. к. каждый планарный вывод становится доступным с любого слоя, а неиспользованные стрингеры автоматически удаляются;
-возможно размещение выводов и не в узлах координатной сетки;
-для цифровых схем типа “память” выполняется трассировка коллинеарных трасс по Х или по У (рис.11.3).
Всовременных пакетах трассировки применяют алгоритм RIP-N-ROUTE (Стираю и развожу), особенности которого следующие:
-используют алгоритм Rip – up (“стираю”), который позволяет максимально увеличить процент разведенных цепей;
-программа имеет оптимизатор (уменьшение числа переходных отверстий и числа изгибов, спрямляющих трассу);
-используют метод “уплотнения трасс”;
-программа автоматически определяет, какие проводники уже проведены
ине проводит их повторной трассировки;
-предварительно размещенные проводники могут участвовать в формировании Т-образных соединений;
-выполняется разводка шин – они воспринимаются как большие прямоугольные области.
11.2. Модификации волнового алгоритма
В общем случае весовая функция или критерий качества пути может зависеть от параметров, учитывающих длину пути, число переходов со слоя на слой, степень близости к другим и т. д., например, в виде аддитивной функции
где ai – весовой коэффициент, учитывающий важность i-го параметра; рi (k) – значение учитываемого параметра.
Усложнение функции веса увеличивает объем информации на одну ячейку дискретного рабочего поля (ДРП) и время работы первой части алгоритма. Кроме того, не представляется возможным строго обосновать выбор значений весовых коэффициентов аi .
При практической реализации волнового алгоритма остается важная проблема – сокращение объема памяти, необходимой для запоминания весов ячеек. При вычислении весов ячеек ячейка может быть в следующих состояниях: свободна, занята или имеет вес от 1 до L, где L максимально возможная длина пути, определяемая как количество составляющих его ячеек ДРП. Необходимое для запоминания состояния одной ячейки ДРП число разрядов памяти
Наиболее эффективные способы кодирования состояния ячеек ДРП – метод путевых координат, кодирование по модулю 3 и метод Акерса.
Метод путевых координат. При выборе последовательности ячеек по этому методу для каждой ячейки, начиная с В, в случае соседства по ребрам достаточно знать, от какой соседней ячейки в нее пришла волна: сверху, слева, снизу, справа, что задается стрелками
.
Следовательно, ячейка может иметь следующие признаки: свободна, занята или одну из путевых координат. Число разрядов на кодирование состояния ячеек Если в данную
ячейку волна приходит из нескольких соседних, то присвоение путевых координат производят по заранее заданному правилу приоритетов. При проведении пути достаточно переходить по путевым координатам из ячейки В ячейку А. Пример проведения пути при использовании данного метода показан на рис.11.4.