7.4.6. Методы повышения быстродействия волнового алгоритма

Методы сокращают время распространения волны. Это методы:

1. Выбор источника волны.

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

Рисунок 7.30. Источники волны ячейка А (а), ячейка В (б)

2. Метод встречной волны.

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

Рисунок 7.31. Метод встречной волны

Площадь заштрихованной фигуры рис. 7.31 (а) S₁ =  L²_AB , а фигуры рис. 7.31 (б) – S₂ = 2 (L_AB /2)² =  L²_AB/2, т.е. в два раза меньше. Время распространения волны во втором случае, с учетом потери времени на организацию попеременной волны, почти в два раза меньше.

3. Обрамление соединяемых точек.

Путь ищется не во всем коммутационном поле а в окрестности ячеек А и В (рис.7.32)

Рисунок 7.32. Обрамление области поиска пути

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

7.4.7. Многослойная трассировка

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

Одним из таких алгоритмов является алгоритм многослойной трассировки Хейса (S. Heiss). При распространении волны свободным ячейкам ДРП_i присваивается индекс длины пути p_i и индекс количества межслойных переходов v_i.

Рисунок 7.33. Дискретное рабочее поле для многослойной трассировки

При расчете длины p_i межслойные переходы учитываются путем добавления k единиц длины на каждый переход.

Рассмотрим трассировку соединений двухслойной печатной платы. Примем цену перехода k = 1 (рис. 7.34).

В

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

Джейер (J.M. Geyer) распространил однослойный вариант трассировки на n слоев. В алгоритме Джейера используется единственное плоское ДРП, которое отображает состояние ячеек для всех слоев. В этом ДРП реализуется процедура распространения волны. Оно происходит одновременно во всех слоях схемы.

Для каждой ячейки ДРП вводятся следующие поля описания (рис. 7.35):

р – индекс длины (вес);

А = a_i_n – n признаков занятости ячейки по каждому слою;

B = b_i_n – n признаков допустимости для включения ячейки в путь по каждому слою;

v – возможные переходы.

v	bn	...	b2	b1	an	...	a2	a1	р
2n + 3	2n + 2		n +4	n +3	n +2		4	3	2 1

Рисунок 7.35. Формат ячейки ДРП

Для кодирования каждой ячейки ДРП требуется 2n + 3 разрядов.

Достоинство волнового алгоритма то, что он всегда строит путь, если он существует и этот путь минимальной длины.

Недостатками алгоритма являются трудоемкость, большой объем требуемой оперативной памяти и последовательный характер построения трасс. Сложность волнового алгоритма составляет О(NM), где N – число клеток ДРП; M – число контактов.