Вопрос №18
Существующий алгоритм проведения трасс между двумя контактами можно условно разбить на две группы, основанные на цепях волнового алгоритма и эвристического.
Волновой алгоритм(алгоритм Ли) позволяет находить кратчайшие трассы оптимальные по целому ряду параметров и являющиеся универсальными. В волновом алгоритме можно выделить 2 этапа: распределение числовой волны и проведение трассы. На первом этапе всё множество квадратов … поля разделяют на две группы:
- под множество свободных квадратов
- под множество занятых квадратов
Трассы могут проходить только по свободным квадратам причём после проведения трассы все её свободные квадраты считаются занятыми.
На втором этапе волнового алгоритма осуществляется проведение трассы, для этого рассматриваются все квадраты отмеченные в обратном порядке.
Характеризуется универсальностью и всегда находит кратчайшую трассу. Главный недостаток этого алгоритма большой объем памяти и большие затраты машинного времени. сокращение затрат памяти и времени ЭВМ можно достичь применяя лучевой алгоритм трассировки.
Основная идея лучевого алгоритма заключается в исследовании не всех квадратов, а только части из них по некоторым заданным направлениям, подобно лучам.
В двух лучевом алгоритме от каждого контакта XiиXjраспространяются по двум лучам и каждый фронт содержит не более четырех элементов.
Троса …, если лучи от разных контактов пересекаются в некотором квадрате. Основная часть времени при выполнении волнового алгоритма затрачивается на распределение волны. С целью сокращения этого времени используют метода встречной волны. Сокращение затрат времени и памяти ЭВМ достигается применением лучевых алгоритмов трассировки.
Эвристический алгоритм трассировки– это наиболее быстродействующий алгоритм и, в отличии от волнового алгоритма в них не рассматриваются все возможные трассы для выбранных вариантов, а сразу стремятся распределить трассу по кратчайшему пути.
В алгоритмах итерационного типа на первом этапе все трассы прокладываются без учета взаимного влияния. После этого проводится анализ взаимного расположения трасс. Трассы которые имеют maxдлину,maxчисло пересечений удаляются, после чего проводится их повторная трассировка.
Канальный алгоритм– это алгоритм основан на прокладке трасс по укрупненным дискретам, представляющим собой каналы. Каналы характеризуются пропускной способностью т.е. допускают количество, проходов через него магистралей. Каналы обращаются как правило между рядами устройств элементов или компонентов.При проектировании БИС производится предварительная трассировка, в результате которой определяют области по которым пройдет трасса. Такими областями обычно служат каналы, незанятые элементами, либо отдельные свободные участки. Главная цель предварительной трассировки – равномерное распределение цепей без превышения пропускной способности каналов.
Особенности трассировки соединений в бис.
При проектировании БИС производится предварительная трассировка, в результате которой определяются области по которым пройдет трасса. такими областями обычно служат каналы не занятые элементами, либо отдельные свободные участки.
Главная цель предварительной трассировки– равномерное распределение цепей бес превышения пропускной способности каналов.
Основным алгоритмом нашедшем широкое применение является волновой алгоритм и его модификации.