Алгоритм трассировки межсоединений
Задача геометрического построения на поле всех цепей данного конструктив…, координаты начала и конца которых определены при размещении с ограничениями:
- различно ???проводников или нет
- возможен переход со слоя на слой
- сколько слоев для трассировки
- под каким углом можно проводить проводники
- допустимая ширина проводников и расстояний между ними
- максимальная длина двух соседних парал. Проводников алгоритмы зависят от конструктивно-технологической базы и технологии изготовления.
Задача трассировки межсоединений обычно делят на подзадачи.
1. построение списка соединений. Сводится к построению мин связывающего дерева
Алгоритм прима.
1. Для любой вершины х ищется ближайшая к ней и они соединяются.
2. Из всех неприсоединенных ищется ближайшая к этой паре и примоединяется до тех пор пока ребер не станет n-1.
Алгоритм Каскала.
Все пары элементов упорядочиваются по неубыванию расстояний между ними. В дерево включается каждое ребро, не образующее цикла с ребрами, уже вошедших в дерево.
Оба алгоритма дают точный результат за ………… время.
3. Определение порядка трассировки (порядка проведения соединений)
Порядок влияет на качество трассировки.
Метод прямоугольников
Для каждой цепи строится мин охватывающий прямоугольник. Подсчитывается количество контактов других цепей, попавших в прямоугольник данной цепи, упорядочиваются по неубыванию этого числа. Получившийся порядок – порядок провед. соединений. Можно проводить: короткие-длинные, или длинные-короткие.
4. Алгоритм трассировки – основной и наиболее трудоемкий этап, обеспечивающий эффективность и качество трассировки в целом
Волновой алгоритм и его модификации
+++Всегда строит путь, если он есть и этот путь мин
---В процессе распространения волны каждая ячейка может быть свободна/запрещена/помечена. При макс L необходимо хранить (L+L) значений, т.е. кучу бит информации.
Входит во все САПР, предложен … Коммутационное поле разбивается на дискреты, в которых может проходить только один проводник (определяется минимальной шириной проводника и мин расстоянием между ними)
- дискретно рабочее поле (ДРП)
Алгоритм состоит из 2 этапов:
1. распространение волны . Формируются фронты – множество дискрет ДРП входящих в окрестность источника А. Распространение волны продолжается до тех пор, пока очередной фронт не достигнет приемника или в него не удастся включить ни одной новой ячейки. По мере распространения волны, ячейки i-го фронта помечаются. Если путь существует.
2. Проведение трассы. От ячеек к-го фронта переходим по определенным правилам к к-1 и т.д. до 0. Пройденные ячейки – искомый путь.
Модификация. Кодирование по mod3
Хранится не само число (вес ячейки), а число mod3. Ячейка : свободна/запрещена/0/1/2. ищем из 2-1, из 1-0, из 2-0, для каждой ячейки храним 3 бита, что не зависит от размера платы.
Метод путевых координат.
Путевой координатой ячейки С будем называть ячейку предыдущего фронта, от которого ячейка С получает свой вес.
До трассировки задается правило приоритета.
Для того чтобы идти в прав. Сторону, у любой ячейки должны быть разные соседи. Для этого последовательность001100110011 .
На самом деле ячейки сложнее – есть еще признак цепи: если принадлеж цепи, то ячейки помечаются тем же фронтом.
------Трудоемкость алгоритмов.
!Выбор источника волны – за источник волны вибирается ячейка, находящаяся ближе к краю коммутационного поля.
Метод встречной волны ………..
..Обрамление
Волна распространяется не по всему полю, а в рамке, ограниченной дельтой. Если не удается достигнуть из А в В то дельту увеличивают.
!----последовательный характер алгоритма. Учет длины пути, числа переходов со слоя на слой необходим.
Лучевые алгоритмы Скорость на 2 порядка выше чем у волновых
Алгоритм Абрайтиса
Вспомогательный луч старается обойти препятствие. Если лучи не встретятся (40% трасс) то пользуются волновым.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.