ВУЗ:
Составители:
Рубрика:
24
разрядов памяти на ячейку ДРП N = log2(4) = 2.Если построение последо-
вательности возможно по нескольким направлениям, то выбор осуществ-
ляют по приоритетам.
Волновой алгоритм характеризуется высокой эффективностью нахо-
ждения пути за счет исследования всех свободных ячеек ДРП, но требует
значительного времени на распространение волны. В связи с этим ис-
пользуются различные методы ускорения выполнения первого этапа алго-
ритма. Одним из них является выбор начальной точки. При выборе в каче-
стве источника распространения волны
площадки, максимально удаленной
от центра платы, просматривается меньшee число свободных ячеек ДРП.
Это становится очевидным по мере роста числа протрассированных цепей.
Более эффективен метод встречной волны. Выигрыш во времени про-
порционален отношению числа исследуемых ячеек при одновременном
распространении волны и распространении волны из одного источника.
При непрерывной модели окрестности волны
на свободном поле ДРП от-
ношение исследуемых площадей M = π·r·r/(2·π(r/2)^2) = 2. Для реальных
состояний ДРП выигрыш во времени может отличаться, однако в среднем
оценка является объективной. Использование данной идеи приводит к ус-
ложнению алгоритма.
Поле распространения волны можно уменьшить, ограничивая его
прямоугольником, внутри которого находятся соединяемые площадки.
Начальная площадь прямоугольника обычно на
10-20% больше площади
прямоугольника, проходящего через эти площадки. Если соединение най-
ти не удалось, то границы прямоугольника расширяются. Данный метод
обладает большей эффективностью ускорения работы алгоритма по срав-
нению с вышеописанными.
Волновой алгоритм можно использовать при различных стратегиях
построения цепей. Выполнение первых трех этапов задачи трассировки
подразумевает переход к построению следующей
цепи после получения
конфигурации текущей или установления невозможности этого. Вслед-
ствие того что в цепь могут входить как длинные соединения, так и корот-
кие, при такой стратегии будет нарушен желательный порядок проведения
соединений от коротких к длинным. После длинных отрезков одной цепи
могут строиться более короткие первые отрезки следующей цепи. Чтобы
избежать этого, проводят сначала соединения, стоящие первыми в списках
всех цепей, затем вторые и т.д. Данный подход будет более корректным,
если после распределения соединений по слоям определить порядок про-
ведения отрезков по всем цепям каждого слоя.
Одна из модификаций алгоритма Ли позволяет исключить этап опре-
деления порядка соединения выводов
внутри каждой цепи. В этом алго-
ритме используется метод встречной волны. Из n элементарных площадок,
сопоставленных с контактами цепи, одновременно распространяются вол-
ны до тех пор, пока не встретятся два фронта. Выполняется вторая часть
Страницы
- « первая
- ‹ предыдущая
- …
- 22
- 23
- 24
- 25
- 26
- …
- следующая ›
- последняя »
