Задача трассировки – одна из наиболее трудоемких задач в общей проблеме автоматизации проектирования РЭА. Это связано с несколькими факторами, в частности с многообразием способов конструктивно-технологической реализации соединений, для каждого из которых при алгоритмическом решении задачи применяются специфические критерии оптимизации и ограничения. С математической точки зрения трассировка – наисложнейшая задача выбора из огромного числа вариантов оптимального решения.
Одновременная оптимизация всех соединений при трассировке за счет перебора всех вариантов в настоящее время невозможна. Поэтому разрабатываются в основном локально оптимальные методы трассировки, когда трасса оптимальна лишь на данном шаге при наличии ранее проведенных соединений.
Основная задача трассировки формулируется следующим образом: по заданной схеме соединений проложить необходимые проводники на плоскости (плате, кристалле и т.д.), чтобы реализовать заданные технические соединения с учетом заранее заданных ограничений. Основными являются ограничения на ширину проводников и минимальные расстояния между ними.
При решении задачи трассировки контактная площадь печатной платы разбивается на элементарные ячейки. Размеры ячеек и их количество определяются площадью поля, допустимой плотностью расположения выводов элементов и проводников. Выбранная система ячеек определяет среду, в которой осуществляется построение соединений. В простейшем случае ячейка представляет собой квадрат со стороной h, равной расстоянию между соседними линиями двух соседних проводников.
В ДРП, приведенном на рисунке 2, определяется множество занятых ячеек, соответствующее зонам, запрещенным для проведения соединений.
Задача трассировки печатных соединений заключается в построении трассы от начальной ячейки до конечной таким образом, чтобы она не включала запрещенные ячейки и имела минимальную длину в ортогональной метрике. Рисунок 1. Образец ДРП
Анализ существующих алгоритмов решения задачи
Существуют две группы алгоритмов решения задачи трассировки: последовательные и параллельные. Более подробная классификация приведена на рисунке 2. Рисунок 2. Классификация алгоритмов трассировки
В последовательных методах трассы проводят одну за другой последовательно, при этом проведение какой-либо трассы a на (i-1)-ом шаге может затруднить проведение трассы b на i-ом шаге, так как является препятствием для проведения трассы b. Следовательно, особенно актуальным для последовательных алгоритмов является предварительное ранжирование (упорядочивание) соединений до трассировки. Существуют различные стратегии упорядочивания, основанные, в частности, на длине соединений, степени охвата соединением других соединений и др. Однако объективных оценок эффективности таких методик в настоящее время нет, поэтому наиболее разумными представляются использование нескольких вариантов очередности и выбор из них наилучшего.
К волновым относятся алгоритмы, основанные на идеях динамического программирования на дискретном рабочем поле (ДРП). В настоящее время разработано огромное число модификаций волнового алгоритма, предложенного Ли еще в 1961г.; однако все они сохраняют его основной недостаток: большие вычислительные затраты и большие затраты памяти ЭВМ. Временная сложность волнового алгоритма составляет O(M*N), где N – число клеток ДРП, M – число точек, подлежащих соединению. Эффективное использование волновых алгоритмов возможно лишь для ДРП с числом ячеек не более 105, при этом время трассировки составляет несколько часов работы ЭВМ. Число неразведенных трасс обычно не превышает 10%.
Основная идея лабиринтных алгоритмов состоит в отыскании пути между двумя ячейками ДРП посредством последовательного обхода преград в лабиринте, образованном занятыми и свободными ячейками. В отличие от волнового алгоритма поиск носит направленный характер, поэтому время поиска сокращается. Алгоритм обычно обеспечивает разводку около 80% соединений. Эвристические алгоритмы трассировки эффективны, как правило, только на начальных стадиях трассировки, когда на плоскости мало преград. Основная идея состоит в генерации самых длинных незанятых отрезков в направлении цели с эвристическими приемами обхода препятствий.
В параллельных алгоритмах трассировки вначале определяется допустимое взаимное расположение трасс, которое оптимизируется по выбранному критерию, и лишь потом трассы фиксируются на коммутационном поле.
Перспективными в настоящее время являются канальные алгоритмы, основанные на возможности в некоторых случаях регулярного разбиения коммутационного поля (КП) на каналы и трассировки внутри каналов вертикальными и горизонтальными отрезками. Алгоритмы работают быстро, однако для них актуальна проблема качества получаемых решений. Канальным алгоритмам свойственен иерархический подход к трассировке, когда исходная задача декомпозируется на несколько подзадач. При этом на каждом иерархическом уровне, в зависимости от его специфики, целесообразно применение различных методов трассировки.
В алгоритмах гибкой трассировки на первом этапе строятся модели топологии для трасс цепей на дискретном топологическом рабочем поле (ДТРП) (без жесткой фиксации), а на втором этапе – модели геометрии, которые метрически точно определяют конфигурацию и месторасположение каждой трассы на КП.
В графотеоретических методах используют графовые модели элементов и компонентов схем, на основе которых синтезируется топологический эскиз проектируемого устройства. На следующем этапе решается задача метризации топологического эскиза.
Описание волнового алгоритма Волновой алгоритм состоит из двух этапов.
На первом этапе моделируется процесс распространения волны от ячейки А по свободным ячейкам ДРП.
При распространении волны от ячейки А, алгоритм последовательно строит Ф1(А)-первый, Ф2(А)-второй, ... , ФК(А)-k-ый ее фронты. Если проведение пути возможно, то на k+1-ом шаге окажется, что ячейка ВєОk+1(А). Если в следующий фронт не удается включить ни одной свободной ячейки, т.е. Оk(А)= Оk+1(А), то при данных условиях путь провести невозможно.
Т.о. первый этап волнового алгоритма определяет возможность проведения пути между А и В.
На втором этапе, начиная с ячейки В, по определенным правилам, выполняется переход от ячейки k-ого фронта к ячейке k-1 фронта до ячейки А. Пройденные ячейки – искомый путь.
Условия, которые нужно выполнить для проведения пути и оценки его оптимальности должны быть заложены в правила, по которым движется фронт волны.
Распространение волны заключается в присваивании ячейкам, соседним с ячейкой предыдущего фронта, значения весовой функции. Вес ячейки k-ого фронта Pk является функцией веса ячейки k-1-ого фронта.
Метод кодирования ячеек по mod3 базируется на основном требовании к весам: Pk-1≠Pk≠Pk+1. Ячейкам, включенным в последующие фронты, можно присваивать не сами веса, а их значения по mod3 (1,2,3,1,2,3,...). Проведение пути заключается в отслеживании отметок (1,2,3). Если ячейка имеет несколько соседних ячеек с одинаковыми метками, то используется правило приоритетных направлений.
При движении от ячейки В к ячейке А используется следующее правило приоритетов: ←, ↑, →, ↓.
Опубликовал Kest
December 01 2009 12:28:06 ·
1 Комментариев ·
15881 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
ТГУ December 19 2013 05:51:53
спасибо за статью
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
