eng
По мнению специалистов, отечественная САПР печатных плат TopoR (Topological Router) [1,2]
входит в десятку лучших САПР мира [3]. Про особенности САПР TopoR и приемы работы с ней написано уже немало, в том числе и в журнале «Электроника: НТБ» [4, 5]. Но пользователи интересуются «внутренностями» системы, например, часто спрашивают, почему нет возможности управлять штрафами, зачем сохраняется несколько вариантов разводки, как определить, что трассировка уже закончена, и как вообще все это работает. В статье рассмотрены основные принципы и механизмы трассировки в САПР TopoR.
входит в десятку лучших САПР мира [3]. Про особенности САПР TopoR и приемы работы с ней написано уже немало, в том числе и в журнале «Электроника: НТБ» [4, 5]. Но пользователи интересуются «внутренностями» системы, например, часто спрашивают, почему нет возможности управлять штрафами, зачем сохраняется несколько вариантов разводки, как определить, что трассировка уже закончена, и как вообще все это работает. В статье рассмотрены основные принципы и механизмы трассировки в САПР TopoR.
TopoR — развитие более ранней САПР FreeStyleRoute (FSR), работавшей под управлением DOS. В отличие от зарубежных аналогов, TopoR является топологическим автотрассировщиком [6], т.е. стадии трассировки и метризации разделены. Трассировка производится на разбиении рабочего поля на треугольные области с помощью триангуляции Делоне. Вершинами триангуляции выступают точки, расположенные на контактах, барьерах, полигонах и других элементах топологии, не изменяющихся во время трассировки. Определяются лишь топологические пути проводников на триангуляции, а точная геометрическая форма проводников и точное местоположение переходов вычисляются позднее, на метрическом этапе. Описание метрического этапа выходит за рамки статьи, следует лишь отметить, что результирующие проводники имеют не привычную ортогональную форму, а состоят из отрезков, расположенных под произвольными углами, и даже (если выбрана соответствующая опция) могут содержать дугообразные участки.
Трассировка в САПР TopoR подразделяется на начальную трассировку и оптимизацию разводки. При оптимизации итерационно выполняются такие процедуры, как перекладка проводников, «всплытие» участков проводников и оптимизация расслоения. Когда заканчивать оптимизацию, пользователь решает сам.
Начальная трассировка
Начальная трассировка выполняется последовательно. Сначала разводятся более широкие проводники, а среди них — более короткие. Для каждого проводника выбирается кратчайший путь по триангуляции с учетом необходимых зазоров, а в рамках этого пути — топологический путь с минимумом пересечений с другими проводниками. Используемая топологическая модель характеризуется тем, что в каждой точке могут пересекаться не более двух проводников. Слои участкам проводников на этом этапе не назначаются. Благодаря такой упрощенной модели начальная трассировка обычно производится очень быстро. Это позволяет выполнять ее «на лету» после каждой операции редактирования расположения компонентов. Таким образом, еще на этапе размещения компонентов конструктор получает наглядную информацию о перегруженных и недогруженных областях платы и может принять решение, какие компоненты следует раздвинуть, развернуть или переместить на другое место платы.
Последовательная прокладка проводников имеет недостаток: ее результат может существенно зависеть от порядка прокладки. Этот недостаток в некоторой степени компенсируется с помощью специальных приемов. Один из таких приемов — автоматическое устранение двойных пересечений проводников одинаковой ширины (рис.1). При устранении одного двойного пересечения могут появиться новые, которые также подлежат устранению (рис.2).
Другой прием — использование функциональной эквивалентности контактов. Например, на рис.3 контакты 1 и 2 функционально эквивалентны, а подходящие к ним проводники пересекаются. Обменяв у контактов 1 и 2 назначенные им цепи, можно устранить пересечение проводников.
После устранения пересечения или цепочки пересечений все проводники, участвовавшие в преобразованиях, перекладываются заново, поскольку существует большая вероятность найти для них более короткие пути. Так как устранение лишних пересечений облегчает условия для прокладки последующих проводников, то поиск устраняемых пересечений целесообразно проводить не однократно по завершении начальной трассировки, а после прокладки каждого очередного проводника.
По завершении начальной разводки производится ее оптимизация. Перед началом оптимизации каждому участку проводников автоматически назначается слой, чтобы пересекающиеся участки попали в разные слои.
Перекладка проводников
Основным механизмом оптимизации разводки является поочередное удаление проводников и проведение их более дешевыми путями. Под стоимостью пути здесь понимается интегральный критерий, учитывающий большое количество факторов: S=Σki,xi, где S — стоимость пути, xi — величина i-го фактора, ki — коэффициент при факторе, kixi — штраф за величину фактора. Некоторые факторы, такие как длина проводника (приблизительная, так как точная геометрическая форма проводников еще не известна), число переходов проводника со слоя на слой, число нарушений проектных норм, непосредственно понятны конструктору. Однако TopoR рассматривает еще около сотни факторов, которые не ухудшают путь проводника, но мешают другим проводникам. Такими факторами являются пересечения с другими проводниками, вклинивания между участками других проводников, подключения к планарным контактам, подключения к точкам ветвления и другие неочевидные для конструктора события, полное перечисление и объяснение которых выходит за рамки статьи. Рассмотрим примеры учета некоторых из таких факторов.
На рис.4а проводник 1 проложен кратчайшим путем, и если он не будет учитывать нужды других проводников, то свой путь не изменит. Однако если ввести достаточный штраф за пересечение участка проводника, на котором имеется переход, то проводник 1 может пойти другим, более длинным путем (рис.4б), тем самым позволив проводнику 2 пройти без переходов.
На рис.5а проводник 1 также проложен кратчайшим путем. При этом он мешает проводнику 2. Если ввести штраф за проход проводника между участками другого проводника, то проводник 1 может пойти другим, более длинным путем (рис.5б), тем самым позволив проводнику 2 пройти более коротким путем и без пересечений (рис.5в).
Важнейшую роль играет соотношение между коэффициентами при различных факторах в функции стоимости пути. Если штраф за два перехода будет больше, чем стоимость удлинения проводника 2, но меньше, чем стоимость удлинения проводника 1 (рис.6а), то сначала проводник 2 может переложиться с добавлением двух переходов (рис.6б), а затем проводник 1 — переложиться так, что переходы на проводнике 2 исчезнут (рис.6в).
К сожалению, надежда на то, что удастся подобрать какую‑то «идеальную» функцию стоимости, годную на все случаи жизни, несбыточна, так как хорошо ведущая себя функция может быть различна не только для разных плат, но даже для разных областей одной платы. Поэтому в САПР TopoR коэффициенты при факторах не фиксированы, а, во‑первых, автоматически подбираются для каждого перекладываемого проводника (в зависимости от качества его пути и от его окружения) и, во‑вторых, колеблются в некоторых пределах. Такие колебания «раскачивают» функцию стоимости, расширяя возможности перекладки проводников.
Более или менее похожая перекладка проводников используется практически во всех электронных САПР, однако функция стоимости обычно бывает проработана слабо. Чаще всего выбор величины штрафов попросту возлагается на пользователя, поэтому все штрафы должны быть ему понятны. Такая практика даже приводит к почти религиозной вере некоторых конструкторов в волшебные свойства «правильно» подобранной стратегии трассировки. САПР TopoR не позволяет пользователю задавать величины штрафов, так как учитываемые факторы многочисленны и не всегда очевидны для пользователя, а коэффициенты при факторах изменчивы.
Пространство решений
Каждая конкретная топология проводников, полученная после начальной трассировки или после любого шага оптимизации, является решением задачи разводки электрических цепей на заданном конструктиве. Под пространством решений понимается граф, каждой вершине которого соответствует какая‑то топология проводников, а каждому ребру — возможный переход от одной топологии к другой за один шаг оптимизации. Если рассматривать только одну операцию оптимизации, а именно перекладку отдельного проводника, то степень вершины равна числу проводников на плате.
Расстоянием между двумя вершинами называется длина кратчайшего пути между ними, в данном случае — минимальное число операций оптимизации, необходимое для перехода от одной вершины к другой. Максимальное расстояние на графе называется диаметром графа. Ясно, что искать лучшее решение проще на том графе, диаметр которого меньше. Методы оптимизации, которые используются в САПР TopoR, уменьшают диаметр графа пространства решений. Они описаны в следующих разделах.
Так как точная геометрическая форма проводников и точное местоположение переходов при трассировке и оптимизации в САПР TopoR не определяются, то каждая вершина в пространстве решений является представителем большого множества конкретных геометрических реализаций проводников. Таким образом, размер пространства решений оказывается существенно меньшим, чем у нетопологических трассировщиков, фиксирующих геометрическую форму проводников во время трассировки. За счет сокращения пространства решений значительно увеличивается скорость разводки.
Алгоритмы оптимизации разводки в TopoR стартуют с вершины, соответствующей результату начальной трассировки, и каждый раз переходят по одному из инцидентных вершине ребер в вершину с лучшей топологией.
Качество каждой конкретной топологии проводников оценивают с помощью специальной функции, по своей структуре похожей на функцию стоимости пути проводника при его перекладке. В отличие от функции стоимости оценочная функция для топологии всей платы должна учитывать только очевидные для конструктора факторы. Более того, для того чтобы с помощью оценочной функции можно было сравнивать два решения, при оценке обоих решений коэффициенты при каждом факторе должны быть одинаковыми, а значит, постоянными для всего пространства решений. Конечно же, коэффициенты оценочной функции должны коррелировать с соответствующими коэффициентами функции стоимости, но точного совпадения не требуется.
Оптимизация расслоения
Как следует из предыдущего раздела, успешная перекладка проводника — это переход в вершину с лучшей оценкой, т.е. спуск по склону оценочной функции. Понятно, что рано или поздно будет достигнут локальный минимум оценочной функции, когда никакая перекладка одиночного проводника не может улучшить качество разводки (точка 1 на рис.7). Проблема «застревания» в локальном минимуме стоит очень остро во всех САПР, использующих последовательную оптимизацию. В САПР TopoR применяется уникальная процедура оптимизации расслоения [7], которая действует глобально на всей плате и кардинально меняет слойность участков проводников. В результате топологическая ситуация на плате может радикально измениться, т.е. система проводников перейдет в другую (зачастую очень далекую от исходной) точку в пространстве решений (точка 2 на рис.7), из которой уже возможен спуск в другой локальный минимум (точка 3 на рис.7).
Проиллюстрируем это конкретным примером. Конфигурация проводников на рис.8 соответствует локальному минимуму оценочной функции. Перекладка ни одного из проводников не может улучшить качество разводки.
В результате оптимизации расслоения изменилась слойность участков проводников (рис.9а). Видно, что теперь может быть более качественно переложен проводник 5 (рис.9б), а затем и проводник 2 (рис.9в).
Заметим, что в данном примере число переходов в результате оптимизации расслоения (см. рис.9а) не изменилось, т.е. полезный эффект оптимизации расслоения получился не от уменьшения количества переходов, а от радикального изменения топологической ситуации на плате.
Процедура оптимизации расслоения обладает рядом достоинств. Она никогда не ухудшает качество разводки, так как топологические пути проводников не изменяются, а количество переходов может только уменьшиться. Более того, в двухслойном случае оптимизация расслоения находит точный минимум числа переходов. В многослойном случае задача минимизации количества переходов становится NP-трудной (для NP-трудных задач не известны непереборные методы точного решения), поэтому на получение точного минимума за приемлемое время рассчитывать не приходится. Применяемый алгоритм дает только приближенное решение. Но, как мы убедились, польза оптимизации расслоения заключается не только и не столько в уменьшении количества переходов, сколько в радикальном изменении ситуации на плате. Важно, что и приближенное решение не может увеличить число переходов.
Оптимизация расслоения выполняется очень быстро, так как требуемое для нее время линейно зависит от числа пересечений проводников. Это позволяет оптимизировать топологию по мере необходимости, не дожидаясь «застревания» в локальном минимуме. На практике это означает, что можно выбрать, какую долю времени программа будет заниматься перекладкой проводников, а какую — оптимизацией расслоения. TopoR запоминает, сколько времени заняла последняя оптимизация расслоения, и запускает ее в следующий раз не раньше, чем истечет такой же интервал времени. В результате временные затраты на оптимизацию расслоения не превышают 50 % от общего времени.
Расслоений с одинаковым количеством переходов обычно бывает неожиданно много. Например, даже для такой простой топологии, которая приведена на рис.8, возможны 12 оптимальных расслоений (с тремя переходами), но только два из них позволяют выбраться из локального минимума. Отсюда можно сделать несколько выводов.
Расслоение следует выбирать случайным образом, чтобы получать разнообразные топологические ситуации.
Оптимизацию расслоения имеет смысл выполнять, даже если на плате совсем нет переходов. Так, на рис.10а проводник 1 мешает проводнику 3. Оптимизация расслоения (рис.10б) позволяет выбраться из локального минимума и переложить проводник 3 лучшим путем (рис.10в).
В результате оптимизации расслоения некоторые проводники получают возможность переложиться более качественно. Надо уметь обнаруживать такие проводники и запускать для них процедуру перекладки, пока ситуация на плате опять не поменялась в результате следующей оптимизации расслоения. Хорошими кандидатами на перекладку выступают те проводники, на которых увеличилось число переходов. Так, в примере на рис.9а это проводники 5 и 2. Однако здесь существует опасность натолкнуться на осциллирующие конфигурации (рис.11). Чтобы в подобных случаях не перекладывать проводники постоянно, TopoR для каждого проводника использует счетчик перекладок, не позволяющий перекладывать один и тот же проводник слишком часто.
Методика оптимизации расслоения — одна из уникальных особенностей САПР TopoR. Наличие «туннельных переходов», резко увеличивая степени вершин, соответственно уменьшает диаметр графа пространства решений и число локальных минимумов, что помогает найти более качественный вариант разводки.
Процедура «всплытия» участков проводников
В многослойном случае процедура оптимизации расслоения работает каждый раз только с одной парой слоев, не обязательно соседних. При этом слой каждого участка проводников может меняться только с одного слоя обрабатываемой пары на другой и обратно — вне зависимости от того, сколько доступных слоев имеется в наличии.
Для устранения этого недостатка используется процедура «всплытия» участков проводников. Она применяется к отдельному проводнику и умеет переносить в любой другой слой как участки обрабатываемого проводника, так и пересекаемые им участки других проводников. Например, процедура «всплытия», примененная к топологии, приведенной на рис.8, приводит к переносу обоих участков проводника 4 в синий слой и в результате — к избавлению от перехода (рис.12а). Возникшая конфигурация тоже допускает 12 различных оптимальных расслоений, два из которых позволяют выбраться из локального минимума (рис.12б, в).
В том или ином виде процедура «всплытия» применяется практически в любом автоматическом трассировщике, но не в процессе трассировки с целью изменить топологическую ситуацию на плате, а уже после трассировки для уменьшения числа переходов.
Многовариантная оптимизация
Как уже говорилось, оценочная функция для топологии всей платы учитывает только очевидные для конструктора факторы, такие как суммарная длина проводников, количество нарушений проектных норм, число межслойных переходов, причем коэффициенты при факторах постоянны. Если понятно, что нарушение проектных норм нельзя компенсировать никаким уменьшением длины проводников, то мнения о таком параметре, как цена перехода (компромисс между количеством переходов и суммарной длиной проводников) у разных конструкторов зачастую диаметрально противоположны. Ниже описано, как можно примирить различные точки зрения по этому вопросу.
TopoR вводит в рассмотрение две вспомогательные оценочные функции [8]. Все факторы, кроме переходов, в этих функциях учитываются одинаково, но переходы первая функция F1 ценит очень дешево, а вторая F2 — очень дорого. Тогда любая оценочная функция F с промежуточной ценой перехода может быть выражена в виде выпуклой комбинации F1 и F2: F = F1 sinϕ + F2 cosϕ, 0 ≤ ϕ ≤ π / 2. В декартовой системе координат (F1, F2) линии уровня функции F представляют собой параллельные прямые c углом наклона ϕ к оси абсцисс. Если имеется множество из N вариантов разводки, то наименьшее значение F достигается на линии уровня, касательной к этому множеству со стороны нуля координат (рис.13а).
Касательные линии уровня для всевозможных значений ϕ отсекают незамкнутую выпуклую многоугольную область плоскости, причем только некоторые линии уровня проходят через стороны многоугольника. Именно эти линии и определяют критические значения угла ϕ, и только крайние точки множества (углы многоугольника) определяют варианты разводки, оптимальные для каких‑нибудь интервалов значений ϕ. Остальные варианты не являются оптимальными ни при каких значениях ϕ (рис.13б).
Это означает, что после каждого шага локальной оптимизации можно оценивать полученный вариант не с точки зрения определенной функции F, а по критерию попадания внутрь выпуклой оболочки уже имеющихся вариантов (рис.13в). Новый вариант либо отбрасывается (в случае попадания), либо сохраняется как новый оптимальный. При сохранении варианта могут удалиться варианты, переставшие быть оптимальными (рис.13г).
Таким образом, в процессе оптимизации сохраняется не один вариант разводки, а сразу несколько, оптимальных для всех возможных функций. Во время оптимизации TopoR отображает таблицу сохраненных вариантов (см. табл.). Первый столбец показывает автоматически назначенное имя файла, в котором сохранен вариант, второй — суммарную длину проводников (варианты отсортированы по возрастанию этого параметра), третий — число переходов, четвертый — количество нарушений проектных норм, пятый — количество участков проводников, на которых надо будет уменьшить ширину проводника, шестой — через какое время после начала оптимизации был получен вариант, седьмой — номер поколения варианта (каждый вариант получается из другого варианта, которого, возможно, уже нет в таблице).
Последний столбец показывает интервал цен перехода, в котором вариант оптимален. Так, первый вариант оптимален при цене перехода от 0 до 6 мм на переход, второй — от 6 до 30, третий — от 30 до 59,0, четвертый — от 59,0 до 59,2, пятый — от 59,2 до 110 и шестой — от 110 до бесконечности. Разработчик, остановив оптимизацию, может выбрать лучший из вариантов, руководствуясь своими собственными соображениями, а может попробовать и несколько вариантов. Необходимость заранее задавать цену перехода отпадает.
Поскольку оптимальные варианты решений для разводки сохраняются, то спуск из каждого из них можно производить неоднократно, разными способами. Это делает проблему «застревания» в локальных минимумах менее острой. TopoR периодически прекращает обработку текущего варианта и для дальнейшей оптимизации случайным образом выбирает вариант из таблицы.
Так как спуски из разных вариантов или разные спуски из одного и того же варианта независимы, то их можно выполнять параллельно на разных ядрах компьютера или на разных компьютерах, объединенных в локальную сеть. Такую распределенную трассировку планируется включить в одну из следующих версий САПР TopoR.
Литература
1. Лузин С. Ю., Лячек Ю. Т., Полубасов О.Б. Автоматизация проектирования печатных плат. Система топологической трассировки TopoR. — СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2005.
2. Полубасов О.Б. и др. Система топологической трассировки печатного монтажа «TopoR». Свидетельство об официальной регистрации программы для ЭВМ № 2005611370. — М.: Российское агентство по патентам и товарным знакам (РОСПАТЕНТ), 2005.
3. Уваров А. С. Проектирование печатных плат. 8 лучших программ. — М.: ДМК Пресс, 2009.
4. Лузин С. Ю., Полубасов О.Б. Система TopoR. Преимущества топологической трассировки. — Электроника: НТБ, 2005, № 5, с.46–47.
5. Лысенко А. А., Полубасов О.Б. Проектирование высокоскоростных плат в САПР TopoR. — Электроника: НТБ, 2010, № 2, с.102–103.
6. Лузин С. Ю., Полубасов О.Б. Топологическая трассировка: реальность или миф? — Chip News, 2002, № 5, с.42–46.
7. Полубасов О.Б. Глобальная минимизация количества межслойных переходов. — Технология и конструирование в электронной аппаратуре, 2001, № 2, с. 3–9.
8. Полубасов О.Б., Петросян Г. С. Методика отбора вариантов при оптимизации разводки соединений. — Технологии приборостроения, 2005, № 3, с.16–19.
Трассировка в САПР TopoR подразделяется на начальную трассировку и оптимизацию разводки. При оптимизации итерационно выполняются такие процедуры, как перекладка проводников, «всплытие» участков проводников и оптимизация расслоения. Когда заканчивать оптимизацию, пользователь решает сам.
Начальная трассировка
Начальная трассировка выполняется последовательно. Сначала разводятся более широкие проводники, а среди них — более короткие. Для каждого проводника выбирается кратчайший путь по триангуляции с учетом необходимых зазоров, а в рамках этого пути — топологический путь с минимумом пересечений с другими проводниками. Используемая топологическая модель характеризуется тем, что в каждой точке могут пересекаться не более двух проводников. Слои участкам проводников на этом этапе не назначаются. Благодаря такой упрощенной модели начальная трассировка обычно производится очень быстро. Это позволяет выполнять ее «на лету» после каждой операции редактирования расположения компонентов. Таким образом, еще на этапе размещения компонентов конструктор получает наглядную информацию о перегруженных и недогруженных областях платы и может принять решение, какие компоненты следует раздвинуть, развернуть или переместить на другое место платы.
Последовательная прокладка проводников имеет недостаток: ее результат может существенно зависеть от порядка прокладки. Этот недостаток в некоторой степени компенсируется с помощью специальных приемов. Один из таких приемов — автоматическое устранение двойных пересечений проводников одинаковой ширины (рис.1). При устранении одного двойного пересечения могут появиться новые, которые также подлежат устранению (рис.2).
Другой прием — использование функциональной эквивалентности контактов. Например, на рис.3 контакты 1 и 2 функционально эквивалентны, а подходящие к ним проводники пересекаются. Обменяв у контактов 1 и 2 назначенные им цепи, можно устранить пересечение проводников.
После устранения пересечения или цепочки пересечений все проводники, участвовавшие в преобразованиях, перекладываются заново, поскольку существует большая вероятность найти для них более короткие пути. Так как устранение лишних пересечений облегчает условия для прокладки последующих проводников, то поиск устраняемых пересечений целесообразно проводить не однократно по завершении начальной трассировки, а после прокладки каждого очередного проводника.
По завершении начальной разводки производится ее оптимизация. Перед началом оптимизации каждому участку проводников автоматически назначается слой, чтобы пересекающиеся участки попали в разные слои.
Перекладка проводников
Основным механизмом оптимизации разводки является поочередное удаление проводников и проведение их более дешевыми путями. Под стоимостью пути здесь понимается интегральный критерий, учитывающий большое количество факторов: S=Σki,xi, где S — стоимость пути, xi — величина i-го фактора, ki — коэффициент при факторе, kixi — штраф за величину фактора. Некоторые факторы, такие как длина проводника (приблизительная, так как точная геометрическая форма проводников еще не известна), число переходов проводника со слоя на слой, число нарушений проектных норм, непосредственно понятны конструктору. Однако TopoR рассматривает еще около сотни факторов, которые не ухудшают путь проводника, но мешают другим проводникам. Такими факторами являются пересечения с другими проводниками, вклинивания между участками других проводников, подключения к планарным контактам, подключения к точкам ветвления и другие неочевидные для конструктора события, полное перечисление и объяснение которых выходит за рамки статьи. Рассмотрим примеры учета некоторых из таких факторов.
На рис.4а проводник 1 проложен кратчайшим путем, и если он не будет учитывать нужды других проводников, то свой путь не изменит. Однако если ввести достаточный штраф за пересечение участка проводника, на котором имеется переход, то проводник 1 может пойти другим, более длинным путем (рис.4б), тем самым позволив проводнику 2 пройти без переходов.
На рис.5а проводник 1 также проложен кратчайшим путем. При этом он мешает проводнику 2. Если ввести штраф за проход проводника между участками другого проводника, то проводник 1 может пойти другим, более длинным путем (рис.5б), тем самым позволив проводнику 2 пройти более коротким путем и без пересечений (рис.5в).
Важнейшую роль играет соотношение между коэффициентами при различных факторах в функции стоимости пути. Если штраф за два перехода будет больше, чем стоимость удлинения проводника 2, но меньше, чем стоимость удлинения проводника 1 (рис.6а), то сначала проводник 2 может переложиться с добавлением двух переходов (рис.6б), а затем проводник 1 — переложиться так, что переходы на проводнике 2 исчезнут (рис.6в).
К сожалению, надежда на то, что удастся подобрать какую‑то «идеальную» функцию стоимости, годную на все случаи жизни, несбыточна, так как хорошо ведущая себя функция может быть различна не только для разных плат, но даже для разных областей одной платы. Поэтому в САПР TopoR коэффициенты при факторах не фиксированы, а, во‑первых, автоматически подбираются для каждого перекладываемого проводника (в зависимости от качества его пути и от его окружения) и, во‑вторых, колеблются в некоторых пределах. Такие колебания «раскачивают» функцию стоимости, расширяя возможности перекладки проводников.
Более или менее похожая перекладка проводников используется практически во всех электронных САПР, однако функция стоимости обычно бывает проработана слабо. Чаще всего выбор величины штрафов попросту возлагается на пользователя, поэтому все штрафы должны быть ему понятны. Такая практика даже приводит к почти религиозной вере некоторых конструкторов в волшебные свойства «правильно» подобранной стратегии трассировки. САПР TopoR не позволяет пользователю задавать величины штрафов, так как учитываемые факторы многочисленны и не всегда очевидны для пользователя, а коэффициенты при факторах изменчивы.
Пространство решений
Каждая конкретная топология проводников, полученная после начальной трассировки или после любого шага оптимизации, является решением задачи разводки электрических цепей на заданном конструктиве. Под пространством решений понимается граф, каждой вершине которого соответствует какая‑то топология проводников, а каждому ребру — возможный переход от одной топологии к другой за один шаг оптимизации. Если рассматривать только одну операцию оптимизации, а именно перекладку отдельного проводника, то степень вершины равна числу проводников на плате.
Расстоянием между двумя вершинами называется длина кратчайшего пути между ними, в данном случае — минимальное число операций оптимизации, необходимое для перехода от одной вершины к другой. Максимальное расстояние на графе называется диаметром графа. Ясно, что искать лучшее решение проще на том графе, диаметр которого меньше. Методы оптимизации, которые используются в САПР TopoR, уменьшают диаметр графа пространства решений. Они описаны в следующих разделах.
Так как точная геометрическая форма проводников и точное местоположение переходов при трассировке и оптимизации в САПР TopoR не определяются, то каждая вершина в пространстве решений является представителем большого множества конкретных геометрических реализаций проводников. Таким образом, размер пространства решений оказывается существенно меньшим, чем у нетопологических трассировщиков, фиксирующих геометрическую форму проводников во время трассировки. За счет сокращения пространства решений значительно увеличивается скорость разводки.
Алгоритмы оптимизации разводки в TopoR стартуют с вершины, соответствующей результату начальной трассировки, и каждый раз переходят по одному из инцидентных вершине ребер в вершину с лучшей топологией.
Качество каждой конкретной топологии проводников оценивают с помощью специальной функции, по своей структуре похожей на функцию стоимости пути проводника при его перекладке. В отличие от функции стоимости оценочная функция для топологии всей платы должна учитывать только очевидные для конструктора факторы. Более того, для того чтобы с помощью оценочной функции можно было сравнивать два решения, при оценке обоих решений коэффициенты при каждом факторе должны быть одинаковыми, а значит, постоянными для всего пространства решений. Конечно же, коэффициенты оценочной функции должны коррелировать с соответствующими коэффициентами функции стоимости, но точного совпадения не требуется.
Оптимизация расслоения
Как следует из предыдущего раздела, успешная перекладка проводника — это переход в вершину с лучшей оценкой, т.е. спуск по склону оценочной функции. Понятно, что рано или поздно будет достигнут локальный минимум оценочной функции, когда никакая перекладка одиночного проводника не может улучшить качество разводки (точка 1 на рис.7). Проблема «застревания» в локальном минимуме стоит очень остро во всех САПР, использующих последовательную оптимизацию. В САПР TopoR применяется уникальная процедура оптимизации расслоения [7], которая действует глобально на всей плате и кардинально меняет слойность участков проводников. В результате топологическая ситуация на плате может радикально измениться, т.е. система проводников перейдет в другую (зачастую очень далекую от исходной) точку в пространстве решений (точка 2 на рис.7), из которой уже возможен спуск в другой локальный минимум (точка 3 на рис.7).
Проиллюстрируем это конкретным примером. Конфигурация проводников на рис.8 соответствует локальному минимуму оценочной функции. Перекладка ни одного из проводников не может улучшить качество разводки.
В результате оптимизации расслоения изменилась слойность участков проводников (рис.9а). Видно, что теперь может быть более качественно переложен проводник 5 (рис.9б), а затем и проводник 2 (рис.9в).
Заметим, что в данном примере число переходов в результате оптимизации расслоения (см. рис.9а) не изменилось, т.е. полезный эффект оптимизации расслоения получился не от уменьшения количества переходов, а от радикального изменения топологической ситуации на плате.
Процедура оптимизации расслоения обладает рядом достоинств. Она никогда не ухудшает качество разводки, так как топологические пути проводников не изменяются, а количество переходов может только уменьшиться. Более того, в двухслойном случае оптимизация расслоения находит точный минимум числа переходов. В многослойном случае задача минимизации количества переходов становится NP-трудной (для NP-трудных задач не известны непереборные методы точного решения), поэтому на получение точного минимума за приемлемое время рассчитывать не приходится. Применяемый алгоритм дает только приближенное решение. Но, как мы убедились, польза оптимизации расслоения заключается не только и не столько в уменьшении количества переходов, сколько в радикальном изменении ситуации на плате. Важно, что и приближенное решение не может увеличить число переходов.
Оптимизация расслоения выполняется очень быстро, так как требуемое для нее время линейно зависит от числа пересечений проводников. Это позволяет оптимизировать топологию по мере необходимости, не дожидаясь «застревания» в локальном минимуме. На практике это означает, что можно выбрать, какую долю времени программа будет заниматься перекладкой проводников, а какую — оптимизацией расслоения. TopoR запоминает, сколько времени заняла последняя оптимизация расслоения, и запускает ее в следующий раз не раньше, чем истечет такой же интервал времени. В результате временные затраты на оптимизацию расслоения не превышают 50 % от общего времени.
Расслоений с одинаковым количеством переходов обычно бывает неожиданно много. Например, даже для такой простой топологии, которая приведена на рис.8, возможны 12 оптимальных расслоений (с тремя переходами), но только два из них позволяют выбраться из локального минимума. Отсюда можно сделать несколько выводов.
Расслоение следует выбирать случайным образом, чтобы получать разнообразные топологические ситуации.
Оптимизацию расслоения имеет смысл выполнять, даже если на плате совсем нет переходов. Так, на рис.10а проводник 1 мешает проводнику 3. Оптимизация расслоения (рис.10б) позволяет выбраться из локального минимума и переложить проводник 3 лучшим путем (рис.10в).
В результате оптимизации расслоения некоторые проводники получают возможность переложиться более качественно. Надо уметь обнаруживать такие проводники и запускать для них процедуру перекладки, пока ситуация на плате опять не поменялась в результате следующей оптимизации расслоения. Хорошими кандидатами на перекладку выступают те проводники, на которых увеличилось число переходов. Так, в примере на рис.9а это проводники 5 и 2. Однако здесь существует опасность натолкнуться на осциллирующие конфигурации (рис.11). Чтобы в подобных случаях не перекладывать проводники постоянно, TopoR для каждого проводника использует счетчик перекладок, не позволяющий перекладывать один и тот же проводник слишком часто.
Методика оптимизации расслоения — одна из уникальных особенностей САПР TopoR. Наличие «туннельных переходов», резко увеличивая степени вершин, соответственно уменьшает диаметр графа пространства решений и число локальных минимумов, что помогает найти более качественный вариант разводки.
Процедура «всплытия» участков проводников
В многослойном случае процедура оптимизации расслоения работает каждый раз только с одной парой слоев, не обязательно соседних. При этом слой каждого участка проводников может меняться только с одного слоя обрабатываемой пары на другой и обратно — вне зависимости от того, сколько доступных слоев имеется в наличии.
Для устранения этого недостатка используется процедура «всплытия» участков проводников. Она применяется к отдельному проводнику и умеет переносить в любой другой слой как участки обрабатываемого проводника, так и пересекаемые им участки других проводников. Например, процедура «всплытия», примененная к топологии, приведенной на рис.8, приводит к переносу обоих участков проводника 4 в синий слой и в результате — к избавлению от перехода (рис.12а). Возникшая конфигурация тоже допускает 12 различных оптимальных расслоений, два из которых позволяют выбраться из локального минимума (рис.12б, в).
В том или ином виде процедура «всплытия» применяется практически в любом автоматическом трассировщике, но не в процессе трассировки с целью изменить топологическую ситуацию на плате, а уже после трассировки для уменьшения числа переходов.
Многовариантная оптимизация
Как уже говорилось, оценочная функция для топологии всей платы учитывает только очевидные для конструктора факторы, такие как суммарная длина проводников, количество нарушений проектных норм, число межслойных переходов, причем коэффициенты при факторах постоянны. Если понятно, что нарушение проектных норм нельзя компенсировать никаким уменьшением длины проводников, то мнения о таком параметре, как цена перехода (компромисс между количеством переходов и суммарной длиной проводников) у разных конструкторов зачастую диаметрально противоположны. Ниже описано, как можно примирить различные точки зрения по этому вопросу.
TopoR вводит в рассмотрение две вспомогательные оценочные функции [8]. Все факторы, кроме переходов, в этих функциях учитываются одинаково, но переходы первая функция F1 ценит очень дешево, а вторая F2 — очень дорого. Тогда любая оценочная функция F с промежуточной ценой перехода может быть выражена в виде выпуклой комбинации F1 и F2: F = F1 sinϕ + F2 cosϕ, 0 ≤ ϕ ≤ π / 2. В декартовой системе координат (F1, F2) линии уровня функции F представляют собой параллельные прямые c углом наклона ϕ к оси абсцисс. Если имеется множество из N вариантов разводки, то наименьшее значение F достигается на линии уровня, касательной к этому множеству со стороны нуля координат (рис.13а).
Касательные линии уровня для всевозможных значений ϕ отсекают незамкнутую выпуклую многоугольную область плоскости, причем только некоторые линии уровня проходят через стороны многоугольника. Именно эти линии и определяют критические значения угла ϕ, и только крайние точки множества (углы многоугольника) определяют варианты разводки, оптимальные для каких‑нибудь интервалов значений ϕ. Остальные варианты не являются оптимальными ни при каких значениях ϕ (рис.13б).
Это означает, что после каждого шага локальной оптимизации можно оценивать полученный вариант не с точки зрения определенной функции F, а по критерию попадания внутрь выпуклой оболочки уже имеющихся вариантов (рис.13в). Новый вариант либо отбрасывается (в случае попадания), либо сохраняется как новый оптимальный. При сохранении варианта могут удалиться варианты, переставшие быть оптимальными (рис.13г).
Таким образом, в процессе оптимизации сохраняется не один вариант разводки, а сразу несколько, оптимальных для всех возможных функций. Во время оптимизации TopoR отображает таблицу сохраненных вариантов (см. табл.). Первый столбец показывает автоматически назначенное имя файла, в котором сохранен вариант, второй — суммарную длину проводников (варианты отсортированы по возрастанию этого параметра), третий — число переходов, четвертый — количество нарушений проектных норм, пятый — количество участков проводников, на которых надо будет уменьшить ширину проводника, шестой — через какое время после начала оптимизации был получен вариант, седьмой — номер поколения варианта (каждый вариант получается из другого варианта, которого, возможно, уже нет в таблице).
Последний столбец показывает интервал цен перехода, в котором вариант оптимален. Так, первый вариант оптимален при цене перехода от 0 до 6 мм на переход, второй — от 6 до 30, третий — от 30 до 59,0, четвертый — от 59,0 до 59,2, пятый — от 59,2 до 110 и шестой — от 110 до бесконечности. Разработчик, остановив оптимизацию, может выбрать лучший из вариантов, руководствуясь своими собственными соображениями, а может попробовать и несколько вариантов. Необходимость заранее задавать цену перехода отпадает.
Поскольку оптимальные варианты решений для разводки сохраняются, то спуск из каждого из них можно производить неоднократно, разными способами. Это делает проблему «застревания» в локальных минимумах менее острой. TopoR периодически прекращает обработку текущего варианта и для дальнейшей оптимизации случайным образом выбирает вариант из таблицы.
Так как спуски из разных вариантов или разные спуски из одного и того же варианта независимы, то их можно выполнять параллельно на разных ядрах компьютера или на разных компьютерах, объединенных в локальную сеть. Такую распределенную трассировку планируется включить в одну из следующих версий САПР TopoR.
Литература
1. Лузин С. Ю., Лячек Ю. Т., Полубасов О.Б. Автоматизация проектирования печатных плат. Система топологической трассировки TopoR. — СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2005.
2. Полубасов О.Б. и др. Система топологической трассировки печатного монтажа «TopoR». Свидетельство об официальной регистрации программы для ЭВМ № 2005611370. — М.: Российское агентство по патентам и товарным знакам (РОСПАТЕНТ), 2005.
3. Уваров А. С. Проектирование печатных плат. 8 лучших программ. — М.: ДМК Пресс, 2009.
4. Лузин С. Ю., Полубасов О.Б. Система TopoR. Преимущества топологической трассировки. — Электроника: НТБ, 2005, № 5, с.46–47.
5. Лысенко А. А., Полубасов О.Б. Проектирование высокоскоростных плат в САПР TopoR. — Электроника: НТБ, 2010, № 2, с.102–103.
6. Лузин С. Ю., Полубасов О.Б. Топологическая трассировка: реальность или миф? — Chip News, 2002, № 5, с.42–46.
7. Полубасов О.Б. Глобальная минимизация количества межслойных переходов. — Технология и конструирование в электронной аппаратуре, 2001, № 2, с. 3–9.
8. Полубасов О.Б., Петросян Г. С. Методика отбора вариантов при оптимизации разводки соединений. — Технологии приборостроения, 2005, № 3, с.16–19.
Отзывы читателей
