С. Лузин, О. Полубасов

Топологическая трассировка: реальность или миф?

В статье сформулированы критерии, отличающие топологические методы разводки печатных плат от других методов, а также даётся ответ на вопрос, существуют ли сейчас практически применимые топологические трассировщики, и могут ли они существовать в принципе.

Компания Altium (бывший Protel) анонсировала выход в первом квартале 2002 года нового продукта — топологического трассировщика Situs. В статье, размещённой на сайте Altium (Topological autoroutingTM) [1], рассказывается о преимуществах "нового", топологического подхода (русский перевод выполнен компанией ЭлектронТрейд и опубликован в журнале Chip News № 2 за 2002 год). Термин "топологическая трассировка" сформировался в СССР более 30 лет назад, и до сих пор считалось, что "топологический" — это классификация, а не название, поэтому приверженцам "старого" топологического подхода представляется спорным такое расширенное толкование термина. Для того, чтобы разобраться в создавшейся ситуации, необходимо сначала вспомнить, что же традиционно понимается под термином "топологическая трассировка", и определить, какие именно свойства отличают топологический трассировщик от нетопологического.

Чисто топологические методы

Строго говоря, для того, чтобы метод можно было назвать чисто топологическим, он должен совсем не оперировать метрическими понятиями, такими как длина, ширина или расстояние, а может иметь дело только с понятиями лежать между, обход по или против часовой стрелки (так как речь идёт о трассировке на ориентированной поверхности — плоскости) и, возможно, слой проводника и пересечение проводников. Такие методы были разработаны [2]. В основном, они базируются на алгоритмах плоских укладок графов. Элемент обычно представляется множеством контактов, между которыми запрещено проведение соединений, а синтез топологии сводится к выбору такой укладки проводников относительно элементов, которая минимизирует количество пересечений проводников или требуемое число слоёв коммутации (рис. 1). В случае однослойной трассировки задача размещения проводников зачастую совмещается с задачей размещения элементов.

Рисунок 1. Три топологических варианта плоской укладки трёх соединений двух элементов с одним пересечением

Чисто топологические методы требуют для представления данных очень небольшого количества машинной памяти, а пространство допустимых решений настолько невелико, что появляется возможность говорить даже о поиске точного решения за приемлемое время. Под точным решением задачи трассировки понимается достижение не просто 100-% трассировки, но трассировки, точно минимизирующей выбранный критерий качества. Как хорошо известно, традиционные методы трассировки не могут претендовать на точную оптимизацию разводки по какому-либо критерию качества (например, суммарной длины трасс или числа межслойных переходов), они даже не всегда находят и просто 100-% разводку всех соединений. "Современные системы автоматизированного проектирования печатных плат различаются между собой настолько незначительно, что, наблюдая процесс трассировки или её результат, трудно отличить одну САПР от другой. Такая схожесть систем является следствием схожести применяемых ими алгоритмов, а особенно схожести моделей коммутационного пространства печатной платы" [3].

Тем не менее, имеющиеся на производстве фотопостроители не умеют работать с топологическим описанием схемы. Для получения платы "в железе" на фотопостроитель необходимо передать чисто геометрическое описание всех проводников и контактных площадок. Переход от чисто топологического к чисто геометрическому представлению топологии называется задачей метризации и представляет очень большую трудность. Обычно печатная плата имеет заранее заданную, непростую форму, на ней могут присутствовать элементы с фиксированным расположением: разъёмы, технологические отверстия, зоны запрета трассировки. Поэтому может оказаться, что найденное топологическое решение не имеет допустимого отображения на заданный конструктив, то есть не может быть реализовано без нарушения технологических норм. С другой стороны, современные технологии обычно позволяют проводить дорожки между контактами элементов РЭА или под планарными контактами в другом слое. Отсутствие учёта такой возможности топологическим трассировщиком будет приводить к неоптимальным решениям из-за того, что чисто топологическая модель коммутационного пространства неадекватно отражает свойства реального конструктива.

Вышеуказанные недостатки привели к тому, что на практике чисто топологические методы применения не получили. Учёные пришли к выводу, что "кроме возможности описания топологической ситуации, модель рабочего поля должна содержать информацию о его метриче-ских параметрах, характеризующих допустимую загруженность трассами промежутков между контактными точками, а также позволяющих определять длины трасс и выделять оптимальные из них" [4]. Такие модели и методы сначала стали называть топогеометрическими или топографическими, но названия не прижились, и эти методы тоже включили в класс топологических, видимо, желая подчеркнуть, что они не являются чисто геометрическими.

Метод гибкой трассировки

В 70-х годах прошлого века Р.П. Ба- зилевич [4,5] предложил разделить решение задачи трассировки электрических соединений при проектировании узлов радиоэлектронной аппаратуры на два этапа, получив тем самым последовательное снижение неопределённости положения трасс. На этапе топологической трассировки положение трасс не фиксируется жёстко, трассы назначаются в широкие области, в пределах которых их местоположение не конкретизировано (тем не менее, относительное расположение трасс внутри областей определено). При этом остаётся значительная свобода в выборе геометрических характеристик трасс. Полностью неопределённость положения трасс устраняется на этапе геометрической трассировки.

Для обеспечения возможности, с одной стороны, получения информации о топологии трасс без конкретизации значений реальных координат всех их точек, а с другой — нетрудоёмкого алгоритмического поиска оптимального по заданным критериям топологического расположения трасс, Базилевич предложил разбить рабочее поле на выпуклые многоугольные области (например, треугольники), в углах которых находятся контакты (рис. 2), и назвал свою модель дискретным топологическим рабочим полем, а метод — методом гибкой трассировки.

Рисунок 2. Разбиение рабочего поля и возможные пути проводников

Метод гибкой трассировки позволил преодолеть многие серьёзные недостатки традиционных методов трассировки на дискретном рабочем поле (ДРП). Ниже перечислены три главных, по мнению авторов статьи, недостатка ДРП, отсутствующих в методе гибкой трассировки.

Сеточность

Каждый элемент топологии (контакт или проводник) представляется набором прямоугольных дискретов, поэтому для одного и того же проекта уменьшение шага сетки ведёт к квадратичному увеличению числа её узлов, что означает соответственное увеличение требующейся машинной памяти и времени решения. Из-за сеточности неэкономно используются ресурсы коммутационного пространства: если какая-либо деталь топологического элемента занимает лишь часть площади дискрета, то всё равно оккупируется весь дискрет. Каждая трасса занимает весь дискрет целиком. Дополнительные сложности возникают при наличии трасс различной ширины или элементов с различным шагом выводов.

В отличие от сеточных алгоритмов, в методе гибкой трассировки количество дискретов не зависит от размеров рабочего поля, а лишь от числа контактов, что обеспечивает высокую скорость трассировки и малые требования к памяти. На рис. 3 слева показана разводка на дискретном рабочем поле, а справа — на дискретном топологическом рабочем поле. Хорошо видно, что левое разбиение содержит гораздо больше узлов, чем правое.

Рисунок 3. Слева разводка на ДРП, справа — на ДТРП

Ортогональность разводки

Каждый знает, что гипотенуза короче суммы двух катетов, и, тем не менее, каждый видел, что на современных печатных платах проводники не идут по кратчайшему пути, огибая препятствие, а совершают резкие повороты под 90 или 45 градусов, идут по ломаной линии там, где можно пройти по прямой.

Гибкая трассировка изотропна, то есть не имеет никаких выделенных направлений и не подвержена "болезни ортогональности", проводники идут так, как им ближе.

Негибкость

Прокладка проводников осуществляется последовательно, при этом никак не учитываются потребности ещё не проложенных проводников. После прокладки форма проводника фиксируется (при поиске путей для следующих трасс нет возможности автоматически изменить форму уже проложенных трасс, отодвинуть фрагмент, перенести в другой слой и так далее). Каждая новая связь становится препятствием для последующих, усложняя собою лабиринт, из-за чего возникают области блокировки контактов (особенно планарных) даже при наличии свободных ресурсов площади. Для того, чтобы снизить отрицательный эффект, прибегают к специальным мерам, таким как расстановка стрингеров, которые, в свою очередь, отнимают площадь и усложняют лабиринт.

Модель гибкой трассировки, напротив, не приводит к образованию большого количества препятствий метрического характера, имеющих искусственное, а не естественное происхождение и возникающих вследствие жёсткой фиксации трасс. Когда некоторая трасса пересекает ребро макродискрета, фиксируется лишь сам факт пересечения, но не точные координаты трассы. Поэтому, если на ребре ещё осталось место, по-следующие трассы имеют возможность пересечь это же ребро справа или слева от данной трассы, как им окажется удобнее.

Важное отличие метода гибкой трассировки от других макротрассировок состоит в том, что на ребре фиксируется относительное расположение пересекающих проводников.

Shape-based трассировщики

Шло время, метод гибкой трассировки так и не покинул пределы лаборатории, а на смену трассировщикам на ДРП пришли Shape-based методы. Вдруг скромная фирма Cooper&Chyan Technology разработала трассировщик SPECCTRA, который сразу покорил сердца проектировщиков. Топологическими эти методы назвать никто не решился, но, по сравнению с трассировкой на ДРП, эти методы имеют явные преимущества.

Бессеточность

SPECCTRA работает с геометрическими объектами (контактными площадками, переходными отверстиями и линейными фрагментами проводников), не раскладывая их в набор дискретов, что позволяет существенно сократить размерность описаний и за счёт этого повысить скорость решения задачи.

Оптимизационный характер

При прокладке трасс SPECCTRA сначала разрешает проводникам пересекаться и прокладывает их с малыми зазорами, а затем производит несколько циклов оптимизации, перекладывая проводники и увеличивая зазоры, где возможно. Так как при оптимизации учитываются нужды всех проводников, а не только уже проложенных, качество разводки существенно возрастает.

Смещение акцента с последовательной бесконфликтной прокладки проводников на сначала 100-% разводку с конфликтами, затем оптимизирующуюся для уменьшения количества конфликтов, перевело алгоритмы из класса последовательных в класс оптимизационных, что, как выяснилось, оказывает колоссальное влияние на качество разводки (справедливости ради, необходимо отметить, что в последние годы сеточные трассировщики (например, MAXROUTE) тоже стали разрешать разводку с конфликтами, затем итерационно оптимизирующуюся).

Тем не менее, такие недостатки, как ортогональность и негибкость, остались. Проводники прокладываются ортогонально (по сетке, как бы странно это ни звучало для “бессеточного” трассировщика) и сразу же фиксируются, пополняя список объектов. Поскольку поиск маршрута проводника производится в лабиринте, образованном расположенными на плате объектами, а в число объектов входят и фрагменты проводников, то неподвижность этих объектов существенно затрудняет поиск оптимального маршрута, не позволяя гибко использовать коммутационные ресурсы платы. Таким образом, можно сделать вывод, что Shape-based методы не относятся к методам гибкой трассировки.

Признак топологического трассировщика

Так какие же свойства метода гибкой трассировки позволяют назвать его топологическим? После недолгих размышлений становится понятно, что бессеточность (правильнее было бы сказать, макродискретность) таким решающим свойством являться не может, так как Shape-based трассировщики также обладают свойством бессеточности, но топологическими не называются. Изотропность, вроде бы, является важным признаком топологичности, так как ослабляет требования к геометрической форме проводников, но вспомним, что в методе гибкой трассировки геометриче-ская форма проводников вообще не фиксируется, фиксируются лишь их топологические пути. Два пути называются топологически эквивалентными, если один из них можно перевести в другой с помощью непрерывной деформации, не пересекая при этом вершин разбиения (рис. 4).

Рисунок 4. a, b, c — топологически эквивалентные пути проводника; d — топологически не эквивалентный им путь

Итак, удалось сформулировать признак топологической трассировки: метод называется топологическим, если в процессе трассировки пути проводников фиксируются лишь с точностью до топологической эквивалентности.

Является ли Situs топологическим трассировщиком

Вернёмся к трассировщику Situs компании Altium, упомянутому в начале статьи. Как видно из рис. 2, 5 и 6, в этом методе, как и в методе гибкой трассировки, разбиением рабочего поля служит триангуляция, и точно так же находится путь трассы через макродискреты. Но затем вдруг трассировщик Situs идёт на попятную и "использует специальный алгоритм, привязывающий путь трассы к реальному пространству трассировки с заданной координатной сеткой", то есть трасса ортогонализируется, фиксируется и пополняет собой множество препятствий.

Таким образом, Situs характеризуется теми же свойствами, что и Shape-based методы — бессеточностью, ортогональностью разводки и негибкостью. С позиций данного выше определения, "топологический" трассировщик Situs пока ещё не является топологическим, так как в процессе трассировки фиксирует геометрические пути проводников. Форма макродискретов, конечно же, решающего значения не имеет, например, на рис. 4 представлен пятиугольный макродискрет, но трассировка от этого не перестаёт быть топологической. Треугольные макродискреты удобнее многоугольных лишь потому, что в рамках топологиче-ской модели позволяют контролировать большее число метрических ограничений. Например, проведение в пятиугольнике двух диагоналей разобьёт его на три треугольника и позволит контролировать геометрические требования на этих двух новых рёбрах разбиения. Ещё Л. Эйлер показал, что триангуляция — разбиение плоскости на треугольники — является наибольшим разбиением по числу рёбер. Среди всех триангуляций особыми свойствами обладает триангуляция Делоне: она не только разбивает плоскость на наиболее правильные треугольники, но и её рёбра всегда соединяют любую из вершин разбиения с ближайшей к ней, что очень полезно для практической задачи контроля зазоров.

Можно резюмировать, что Situs попытался сделать шаг на пути превращения в топологический трассировщик, но для успеха на этом пути очень важно не цепляться за старое, не тащить неподъёмный багаж геометрических представлений и наработок: "В одну телегу впрячь не можно коня и трепетную лань". Нам же остаётся только пожелать удачи разработчикам Situs и надеяться, что новые воззрения победят, не погибнут под грузом старых, "проверенных годами" приёмов, которые были хороши для наивной, слепой трассировки, но абсолютно не подходят для топологической.

Недостатки метода гибкой трассировки

Почему же современные САПР не используют гибкую трассировку, почему идеи топологической трассировки так и не получили практического воплощения, хотя кроме Базилевича в этом направлении работало и много других сильных учёных, достаточно вспомнить хотя бы коллектив А.Я. Тетельбаума [6]? Как ни парадоксально, гибкая трассировка не получила распространения именно из-за своей гибкости. Чем гибче модель, чем меньше она фиксирует метрических ограничений, тем значительнее сокращается пространство решений, а значит, облегчается поиск хороших решений, но тем труднее обеспечить соблюдение этих ограничений.

Например, триангуляция успешно справляется с контролем зазоров, если все элементы топологии (вершины триангуляции) круглые, но пасует, когда появляются протяжённые элементы. На рис. 5 имеются протяжённые элементы топологии — это планарные контактные площадки и граница платы (которую авторы рисунка "забыли" включить в триангуляцию). Большинство разработчиков, в том числе и Базилевич, выходят из положения, подразбивая длинные элементы дополнительными точками на более мелкие. Увеличение количества вершин приводит к снижению эффективности, а гарантии соблюдения всех метрических ограничений всё равно не даёт.

Рисунок 5. Поиск пути трассировки методом топологического анализа

Рисунок 6. Конечный вид разведённого проводника

Более неприятен другой факт — наличие “слойных” элементов топологии, которые присутствуют только на подмножестве имеющихся коммутационных слоёв. Если такие элементы считать сквозными, то неэкономно используются ресурсы коммутационного пространства, а если не считать их сквозными, то на разных слоях получаются разные триангуляции, и тогда возникают большие трудности с переходами трассы со слоя на слой.

Имеются и другие сложности, в частности, очень непросто на топологиче-ской модели реализовать второй этап гибкой трассировки — устранение неопределённости геометрического положения трасс.

От двух этапов — к двум моделям

Итак, топологическая модель позво- ляет достичь высокой производительности и качества разводки, но она же и затрудняет переход к метрическому этапу. Неужели это означает практическую невозможность топологической трассировки, неужели из-за этого противоречия топологические трассировщики так и останутся не более чем лабораторными экспериментами? Нет, конечно. Напрашивается простое разрешение дилеммы: для того, чтобы иметь модель, достаточно гибкую, чтобы получить разводку высокого качества, и одновременно модель, учитывающую все конструкторско-технологические требования, нужно иметь, как минимум, две модели.

Отечественный топологический трассировщик FreeStyleRoute (FSR) [3,7], успешно эксплуатирующийся с 1996 года, развивает идеи Базилевича. Он бессеточный, изотропный, оптимизирующий и даже более гибкий, чем его прототип. Так, он не только не фиксирует положение проводника внутри макродискрета, но даже и положение межслойного перехода на проводнике фиксирует только с точностью до участка между двумя соседними пересечениями, а для некоторых проводников, которые не пересекаются с другими, совсем не фиксирует слой. Можно сказать, что FSR гибкий не в двух измерениях, а в трёх.

Тем не менее, результирующие проводники FSR не только соблюдают все заданные метрические ограничения, но и обладают наименьшей длиной среди всех возможных вариаций формы проводника при найденном топологическом расположении. Проводники огибают препятствия по дугам окружностей с необходимым зазором, а с одной дуги на другую переходят вдоль отрезков прямых, касательных к обеим окружностям (рис. 7).

Рисунок 7. Фрагмент печатной платы, разведённой с помощью программного комплекса FreeStyleRoute

Секрет прост: FSR не только реализует два (а если быть точным, четыре) этапа трассировки, но и на разных этапах использует разные модели. На этапе топологической оптимизации моделью является триангуляция Делоне, общая для всех трассировочных слоёв, которая позволяет быстро создать качественную трассировку с очень небольшим числом переходов. А на этапе геометрической коррекции используется совсем другое разбиение рабочего поля, позволяющее эффективно контролировать зазоры не только между круглыми элементами топологии, но и между вытянутыми, и названное автором квазитриангуляцией, поскольку является обобщением триангуляции Делоне и вырождается в последнюю, когда все элементы топологии — круглые. Квазитриангуляция на каждом слое своя, поэтому этап геометрической коррекции не в состоянии оптимизировать количество переходов, зато он обладает способностью перемещать элементы на уже оттрассированной плате, автоматически сохраняя имеющуюся разводку и соблюдая заданные зазоры. Элементы раздвигаются, обеспечивая возможность прокладки между ними нужного числа проводников, и сдвигаются, уменьшая длину проводников и освобождая площадь платы.

Реализован быстрый переход от одной модели к другой и обратно. Как оказалось, гораздо проще переключиться на другую модель, чем пытаться выполнять на модели несвойственные ей функции.

Тем не менее, так как высокая гибкость топологической модели достигается за счёт приближенного учёта некоторых метрических характеристик, то и FSR не лишён проблем. В частности, размеры переходных отверстий при трассировке учитываются лишь приближённо. Этот недостаток обычно компенсируется существенным уменьшением количества переходных отверстий, но иногда может создавать неудобства. Так же, при двухсторонней установке компонентов ресурсы платы иногда могут использоваться не полностью.

Заключение

Метод является топологическим, если в процессе трассировки пути проводников фиксируются лишь с точностью до топологической эквивалентности.

Топологическая модель позволяет достичь высокой производительности и качества разводки, но она же и затрудняет переход к метрическому этапу. Чем гибче модель, чем меньше она фиксирует метрические ограничения, тем значительнее сокращается пространство решений, а значит, облегчается поиск хороших решений, но тем труднее обеспечить соблюдение этих ограничений. Для реализации практически пригодного топологического трассировщика необходимо, чтобы этапы собственно трассировки и метризации работали на разных моделях коммутационного пространства, иначе либо метод не будет топологическим, либо учёт метрических требований будет неполным.

Несмотря на трудности развития топологических средств трассировки, опыт эксплуатации трассировщика FreeStyleRoute демонстрирует перспективность этого направления. И хотя реализована лишь малая часть возможностей, предоставляемых новыми моделями, уже почти очевидно, что будущее — за топологическими методами.

Литература

1. Хигстон Д., Логхид Ф., Ирвин Р. Новый топологический автотрассировщик. // Chip News. 2002. № 2. C. 60–64.
2. Базилевич Р.П. Некоторые задачи синтеза планарных топологий. Вычислительная техника. Вильнюс, 1979. Т. 12. С. 16–23.
3. Лузин С.Ю., Полубасов О.Б. Проектирование печатных плат. Новые методы решения старых проблем. "САПР и графика", 1997. № 11. С. 58–59.
4. Базилевич Р.П. Декомпозиционные итопологические методы автоматизированного метода конструирования электронных устройств. Львов.: Вища школа, 1981. 168 с.
5. Базилевич Р.П. Обобщённый подход к формализации задачи машинной трассировки межсоединений на плоскости. Изв. вузов СССР. Радиоэлектроника, 1974. № 6. С. 98–103.
6. Петренко А.П., Тетельбаум А.Я., Забалуев Н.Н. Топологические алгоритмы трассировки многослойных печатных плат. М.: Радио исвязь, 1983. 152 с.
7. Сухарев А.В., Золотов А.И. Модели и процедуры оптимизации в автоматизации проектирования. (Программный комплекс FreeStyle Router): Учеб. пособие. СПб.: СЗТУ, 2001. 165 с.