15. Классификация алгоритмов трассировки, бессеточные трассировщики.

Существующие алгоритмы прокладки трасс условно можно разделить на следующие группы:

1. Волновые алгоритмы, основанные на идеях Ли. Они получили широкое распространение, так как позволяют легко учитывать конструкторские и технологические ограничения. Они всегда гарантируют построение трассы, если путь для нее существует.

2. Канальные алгоритмы, они обладают большим быстродействием, чем волновые. Недостатком является большое количество переходов со слоя на слой, отсутствие 100% гарантии проведения ряда трасс, большим количеством параллельно идущих проводников. Большее применение они получили при трассировке топологии кристаллов микросхем.

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

4. Генетические алгоритмы. Это поисковые алгоритмы, основанные на механизмах натуральной селекции и натуральной генетики.

3. Бессеточные трассировщики.

В современных САПР чаще всего используются так называемые бессеточные (Shape-Based) трассировщики. Например, в программе SPECCTRA согласно этой технологии все объекты моделируются в виде совокупности геометрических фигур (прямоугольник, круг, дуга, трасса, полигон), которым приписаны определенные электрические и физические характеристики и правила проектирования. В отличие от привязанных к сеткам технологиям (Grid-Based) каждый объект моделируется геометрически точно, за счет чего достигается более плотный монтаж с меньшим числом слоев. За счет точного моделирования геометрических форм объектов бессеточными технологиями образуется дополнительное свободное пространство, которое можно использовать для более тесного расположения компонентов и проводников. Характерная особенность бессеточной технологии – меньшие затраты памяти. Если для бессеточных технологий объем памяти не зависит от шага сетки, то при использовании сеточных технологий при уменьшении шага сетки необходимый объем памяти возрастает в квадратичной зависимости. В бессеточных технологиях память тратится только на описание геометрических форм объектов, а не на запоминание координат помеченных узлов сетки.

16. Волновой алгоритм трассировки соединений.

Основные принципы построения трасс с помощью волнового алгоритма сводятся к следующему. Все ячейки монтажного поля (МП) подразделяют на занятые и свободные. Занятыми считаются ячейки:

1. в которых уже расположены проводники, построенные на предыдущих шагах или находятся монтажные выводы элементов;

2. ячейки, соответствующие границе платы и запрещенным для прокладывания проводников участкам.

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

Первую ячейку, в которой зарождается волна, называют источником, а вторую – приемником волны.

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

, где - вес ячейки k – фронта; - вес ячейки k-1 фронта; - весовая функция, являющаяся показателем качества проведения пути; - параметр функции, характеризующий путь с точки зрения одного из критериев качества (длина пути, число пересечений, изгибов и т.п.).

Совокупность ячеек с одинаковым весом называется фронтом волны.

На накладывается ограничение: . Фронт распространяется на соседние ячейки, которые имеют с ячейками предыдущего фронта либо одну общую сторону, либо хотя бы одну общую точку.

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

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

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

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

Пример.

Запишем вышеприведенную формулу в следующем виде:

, где - весовой коэффициент, определяющий степень важности i-го параметра; - признак изменения i-го параметра {0,1}.

Пусть - для параметра длины пути;

 - для параметра числа пересечений (переход со слоя на слой).

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

Д ля повышения быстродействия волновых алгоритмов предлагают:

1. метод встречной волны, то есть одновременное распространение волны от двух источников;

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

3. начало трассировки с точки, максимально удаленной от центра.

Недостатком волнового алгоритма является большой объем времени и памяти ЭВМ, затрачиваемого на трассировку.