ВЫЧИСЛЕНИЕ МИНИМАЛЬНОГО ПО ДЛИНЕ ПУТИ ПРОВОДНИКА В ТОПОЛОГИЧЕСКОЙ ТРАССИРОВКЕ ПЕЧАТНОГО МОНТАЖА
Ю.И. Попов, С.И. Попов
УДК 004.421.2
ВЫЧИСЛЕНИЕ МИНИМАЛЬНОГО ПО ДЛИНЕ ПУТИ ПРОВОДНИКА В ТОПОЛОГИЧЕСКОЙ ТРАССИРОВКЕ ПЕЧАТНОГО МОНТАЖА
Ю.И. Попов, С.И. Попов
В топологическом подходе к трассировке печатных плат возникает задача вычисления пути (формы) проводника по его топологическому пути. Предложен алгоритм, вычисляющий путь минимальной длины с соблюдением конструктивно-технологических ограничений. Алгоритм используется при расчете формы проводников в системе автоматизированного проектирования TopoR. Ключевые слова: САПР, автоматическая трассировка, топологическая трассировка.
Введение
Существует два основных подхода к автоматической трассировке печатных плат: геометрический и топологический. Первый предлагает на протяжении процесса трассировки оперировать метрикой коммутационного пространства, т.е. такими понятиями, как координаты, длина, ширина, расстояние. Второй предлагает использовать только такие понятия, как лежать слева, справа, между; обход по или против часовой стрелки [1].
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 6 (82)
117
ВЫЧИСЛЕНИЕ МИНИМАЛЬНОГО ПО ДЛИНЕ ПУТИ ПРОВОДНИКА…
В 1970-х г.г. Р.П. Базилевич [2] предложил во втором подходе разделить процесс трассировки на два этапа: топологический и геометрический. На первом этапе проводники назначаются в широкие области, в которых они не фиксированы жестко, а лишь задано их относительное положение. На втором этапе – метризации – определяется конкретное положение сегментов проводника с соблюдением конструктивно-технологических ограничений.
В отличие от геометрического подхода, когда на конфигурацию проводника оказывают влияние только соседние элементы топологии, положение которых, как правило, фиксировано, при топологическом подходе на путь (форму) проводника может влиять элемент, находящийся от него на произвольном расстоянии. Проблема состоит в точном учете влияния элементов топологии при вычислении минимального по длине пути проводника.
На форму отдельно взятого сегмента проводника, как правило, влияет лишь небольшая часть элементов топологии. По этой причине для повышения эффективности представляет интерес заранее определить элементы, которые могут оказать влияния на форму сегмента, и не рассматривать остальные при ее вычислении. Предложенный алгоритм реализует эту идею и вычисляет минимальные по длине пути проводников с соблюдением конструктивно-технологических ограничений.
Минимальный по длине путь проводника
Для представления минимального по длине пути проводника рассмотрим следующий пример из [1]. Пусть в некотором зале расставлено множество круглых колонн разного диаметра. Путник, петляя между колоннами, прошел из точки A зала в точку B длинным маршрутом, ни разу не пересекая собственный путь. По дороге он разматывал клубок ниток. Существует бесконечное множество путей, топологически эквивалентных маршруту путника, т.е. проходящих между теми же парами колонн. Но среди этих путей существует кратчайший. Этот путь можно узнать, натянув нить. Нить примет форму единственной кривой, и длина этой кривой будет минимально возможной. Натянутая нить будет огибать колонны по дугам окружностей с соответствующими радиусами, а с одной окружности на другую будет переходить по прямой, касательной к обеим окружностям (рис. 1).
ВВ
АА
аб
Рис. 1. Натянутая нить огибает колонны по дугам окружностей: нить путника (а); натянутая нить путника (б)
Печатная плата, в общем случае, имеет несколько слоев. Каждый из них может быть рассмотрен независимо. Под проводником в работе понимается фрагмент трассы, ограниченный точками ветвления, переходными отверстиями, контактными площадками компонентов, областями металлизации. Проводник прокладывается с соблюдением конструктивно-технологических ограничений (ширины проводников, размеры объектов печатного монтажа, зазоры между ними). Например, если путь проводника w проходит мимо контактной площадки C, то следует учесть ее размеры, другие проводники (с их ширинами), проходящие между w и C, а также требуемые зазоры между ними.
История вопроса
Первый подход к решению задачи вычисления минимального по длине пути предложил в 1980 г. М. Томпа (M. Tompa) [3]. Однако алгоритм имеет ряд существенных ограничений: узлы компонентов упорядочены и находятся на параллельных сторонах канала, ширины проводников нулевые, минимальные зазоры между проводниками одинаковы.
В 1988 г. Ш. Гао (S. Gao) с соавторами опубликовал работу [4]. В ней предложен более сложный алгоритм, однако также с существенными ограничениями на входные данные: одинаковые зазоры между проводниками, нулевые ширины, наличие лишь точечных контактных площадок компонентов.
В 1999 г. Т. Хама (T. Hama) и Х. Этох (H. Etoh) предложили новый подход к решению задачи [5]. Они используют триангуляцию Делоне для разбиения монтажного пространства. Условие Делоне (окружность, описанная вокруг треугольной грани не содержит других вершин триангуляции) они используют как ограничение для расстояния, на котором учитывается влияние контактных площадок на форму проводника. На реальных платах зазор между контактной площадкой и проводником может быть произвольно большим, и соответственно расчет будет некорректным. Кроме того, в предложенном подходе рассматриваются только круглые контактные площадки.
118
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 6 (82)
Ю.И. Попов, С.И. Попов
В системе автоматизированного проектирования (САПР) FreeStyle Router в 1990-х г.г., а затем и в САПР TopoR (вплоть до версии 5.2) был реализован алгоритм, позволяющий вычислять пути проводников [1]. Однако алгоритм не учитывал влияние на путь проводника контактных площадок, расположенных на достаточном удалении от него. Недоучет любого фактора приводит к получению конфигураций с нарушениями конструктивно-технологических ограничений.
Представление объектов печатного монтажа набором круглых примитивов
При работе с объектами печатного монтажа удобно использовать разбиение монтажного пространства, например, в виде триангуляции Делоне или квазитриангуляции [1]. Объекты произвольной формы в разбиении представлены не одной вершиной, а набором вершин, соответствующих вершинам многоугольника, а в ряде случаев и дополнительными вершинами, например, расположенными вдоль линейно протяженных объектов. На рис. 2 приведено возможное расположение вершин на границе прямоугольного объекта печатного монтажа.
Рис. 2. Расположение вершин разбиения на границе прямоугольного объекта
С этими вершинами можно связать круглые примитивы, радиус которых зависит от выбранной модели. Между проводником, проходящим мимо объекта, и примитивом должен быть соблюден зазор, заданный конструктивно-технологическими ограничениями. Чтобы проводник не «провис» между двумя соседними огибаемыми примитивами одного объекта под действием других примитивов (возможно, другого объекта), следует учитывать расстояние до ребра, соединяющего вершины этих примитивов.
Таким образом, «некруглость» объектов просто увеличивает число вершин разбиения, поэтому в дальнейшем изложении без потери общности принимаем, что имеются только круглые контактные площадки, к ним приравняем переходные отверстия, точки ветвления и другие круглые примитивы, разбивающие более сложные объекты. Разбиение монтажного пространства – триангуляция.
Алгоритм вычисления минимального по длине пути
После топологического этапа пути проводников могут быть представлены последовательностью ребер, которые они пересекают. Рассмотрим топологический путь проводника как последовательность отрезков, проходящих, например, через центры пересекаемых ребер.
В общем случае каждая контактная площадка на печатной плате может повлиять на длину пути. Рассмотрим расстояние d между центром круглой контактной площадки C и средней линией сегмента проводника w. Оно должно быть не меньше расстояния, складывающегося из конструктивнотехнологических ограничений: радиус контактной площадки C; ширины проводников, расположенных между w и C; половина ширины проводника w; зазоры между ними.
Для каждого отрезка топологического пути проводника определяются дуги окружностей, центры которых расположены в центрах контактных площадок, а радиусы равны расстояниям d. Путь проводника не может пересекать дуги, так как они построены по конструктивно-технологическим ограничениям.
Алгоритм вычисления минимального по длине пути состоит из двух этапов. 1. Построение вышеописанных окружностей. 2. Вычисление минимального по длине пути, огибающего эти окружности.
Рассмотрим сначала вычисление пути.
Алгоритм вычисления пути, огибающего окружности
Основная идея алгоритма состоит в следующем [1, 3–5]. Пусть дано множество окружностей, упорядоченных вдоль топологического пути. Если задано направление пути, то окружности можно разделить на левые (D, C) и правые (A, B) относительно пути (рис. 3). К окружностям в порядке очередности строятся касательные.
Сначала следует построить касательные к первым левой (D) и правой (A) окружностям, проходящие через начальную точку S. В результате образуется воронка, в пределах которой должен располагаться путь. Если построить касательную из точки S к следующей правой окружности B, то окружность A можно исключить из рассмотрения, так как она находится правее. Касательная из точки S к окружности
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 6 (82)
119
ВЫЧИСЛЕНИЕ МИНИМАЛЬНОГО ПО ДЛИНЕ ПУТИ ПРОВОДНИКА…
C пересекает окружность D, поэтому последняя становится частью воронки (рис. 3, а). Далее аналогично строятся касательные к следующим левым и правым окружностям.
Если правая касательная пересекает левую окружность (рис. 3, б), то левая касательная (ее отрезок) из точки S к этой окружности становится геометрически частью вычисляемого пути (рис. 3, в). В этом случае необходимо далее строить общие касательные с окружностью D (вместо проходящих через точку S). Для левой касательной построение аналогично.
Если два отрезка касательных добавлены в путь, то дуга окружности между ними также становится частью пути.
Полученная последовательность отрезков касательных и дуг окружностей составляет путь минимальной длины.
СВ
СВ
СВ
DD
D
А s
sА
sА
аб
в
Рис. 3. Вычисление пути: построение касательных (а); пересечение касательной и окружности (б); отрезок касательной добавлен в путь (в)
Построение окружностей
Предлагается строить окружности в два этапа. На первом этапе для каждой контактной площадки следует построить множество окружностей. Процесс их построения можно представить как волну, распространяющуюся от центра контактной площадки, поглощая встречающиеся проводники и разделяясь при встрече других контактных площадок. Эти окружности не предназначены для непосредственного вычисления путей проводников, они помогут определить контактные площадки, которые влияют на форму сегментов. На втором этапе, используя эту информацию, следует построить окружности для каждого проводника в отдельности. Опишем этапы по порядку.
На первом этапе для каждой вершины v (соответствующей контактной площадке) рассматривается каждая грань, которой принадлежит вершина v, и выполняются следующие шаги. 1. Из центра контактной площадки A построить две касательные к окружностям контактных площадок B
и C (рис. 4). (Если контактные площадки пересекаются, то перейти к следующей грани.) Рассматриваются касательные, пересекающие ребро b. Они вырезают в плоскости сектор, внутри которого дуга окружности может влиять на минимальный по длине путь проводника. Этот сектор позволяет пространственно ограничить направления, в которых контактная площадка влияет на проводники (сектор в процессе выполнения алгоритма может только уменьшиться).
C bB
cа
А
Рис. 4. Из центра A к окружностям контактных площадок строятся две касательные
2. Вычислить радиусы окружностей с учетом путей проводников, пересекающих грань. На рис. 5 изображена контактная площадка A и три проводника: w1, w2 и w3. Здесь известно только, в каком порядке расположены пути проводников относительно друг друга и контактных площадок. Вычислим последовательно радиусы окружностей для каждого из проводников, необходимые для соблюдения конструктивно-технологических ограничений. Первый радиус (для проводника w1) – это сумма радиуса контактной площадки A, зазора до проводника w1 и половины ширины проводника w1. Второй радиус (для w2) – это сумма первого радиуса, зазора между проводниками w1 и w2, а также половины ширины проводника w2. Последний радиус может влиять на проводник w3 за ребром b.
120
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 6 (82)
Ю.И. Попов, С.И. Попов
b w3
w2
w1 А
Рис. 5. Вычисление радиусов с учетом контактной площадки A и проводников w1, w2 и w3
3. Если последняя окружность с вычисленным радиусом пересекает ребро b, то запомнить информацию о ней в ассоциации с ребром (она будет использована на шаге 2 второго этапа). За ребром b начальной грани находятся грань и два ребра (рис. 6). Через них следует продолжить распространение вычисления радиусов. При этом необходимо построить касательные к окружности контактной площадки за ребром b, так как они могут уменьшить сектор. На рис. 6 за ребром b находятся ребра d и e. Проводник w2 не влияет на радиус окружности для ребра e (не будет учтен при проверке на пересечение). Для ребра d ситуация сложнее. Если бы проводник w2 пересекал ребро e, то можно было бы однозначно указать на необходимость его учета. В приведенном случае проводник учитывается условно. Если за ребром d на расстоянии, учитывающем ширину проводника w2 и соответствующие зазоры, нет других проводников, то процесс распространения в данном направлении будет остановлен. Продолжать вычисление радиусов (за ребра e и d) следует, пока зазоры и ширины проводников могут его увеличить, до пересечения очередного ребра.
ed b
w2
А w1
Рис. 6. Учет проводника w2 при вычислении радиусов окружностей
На втором этапе по очереди рассматриваются топологические пути проводников (последовательности отрезков). Пересекая грань, топологический путь через одно ребро входит, а через другое выходит из нее. Существуют не более двух граней, в которых путь пересекает только одно ребро, – грани, в вершинах которых путь начинается и заканчивается. Для каждого топологического пути выполняются следующие шаги. 1. Каждое пересекаемое топологическим путем ребро инцидентно двум вершинам. Между контактной
площадкой вершины и проводником w находятся другие проводники. Для каждой из вершин необходимо построить окружности с радиусом, равным сумме радиуса контактной площадки, ширин проводников и зазоров между ними. Последним учтенным в радиусе будет рассматриваемый отрезок топологического пути. 2. Для каждого отрезка топологического пути по триангуляции определить окружности, построенные на первом этапе. Эти окружности могут повлиять на минимальный по длине путь, но их радиусы следует изменить таким образом, чтобы последним учтенным в радиусе стал рассматриваемый отрезок топологического пути.
Дуги построенных окружностей, ограниченные секторами, учитывают все необходимые конструктивно-технологические ограничения, поэтому можно применить алгоритм вычисления пути, огибающего окружности.
Заключение
В описанном подходе, в отличие от предложенных ранее, отсутствует ограничение на форму канала, учитываются ширины всех проводников и необходимые зазоры, нет ограничений на их величины. Объекты произвольной формы моделируются набором круглых примитивов с обработкой возможного «провисания» проводников. При этом учет перечисленных факторов не сопровождается снижением производительности.
Асимптотические оценки алгоритма: O(B · F2 · log(B · F)) – время; O(B · F2) – память, где B – общее число изломов путей проводников, состоящих из отрезков между ребрами; F – число контактных площадок на плате – совпадают с оценками алгоритма из [4]. Но в [4] рассматривается влияние каждой контактной площадки на каждый проводник посредством простого перебора и упорядочивания. При
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 6 (82)
121
ВЫЧИСЛЕНИЕ МИНИМАЛЬНОГО ПО ДЛИНЕ ПУТИ ПРОВОДНИКА…
этом строятся заранее все возможные окружности для всех проводников. Предложенный алгоритм строит окружности итеративно, заранее определяется, что в продолжении итераций нет необходимости. Таким образом, предложенный метод не только свободен от существенных недостатков предыдущих версий, но и превосходит их в эффективности. Алгоритм реализован и используется в последней версии системы автоматизированного проектирования TopoR.
Литература
1. Лузин С.Ю., Лячек Ю.Т., Петросян Г.С., Полубасов О.Б. Модели и алгоритмы автоматизированного проектирования радиоэлектронной и электронно-вычислительной аппаратуры. – СПб: БХВПетербург, 2010. – 224 с.
2. Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного конструирования электронных устройств. – Львов: Вища школа, 1981. – 168 с.
3. Tompa M. An Optimal Solution to a Wire-Routing Problem // Journal of Computer and System Sciences 23. – 1980. – P. 127–150.
4. Gao S., Jerrum M., Kaufmann M., Mehlhorn K., Rulling W., Storb C. On continuous homotopic one layer routing // in Proc. 4th Annu. ACM Symp. Computational Geometry. – 1988. – P. 392–402.
5. Hama T., Etoh H. Curvilinear Detailed Routing with Simultaneous Wire-Spreading and Wire-Fattening // IEEE Transactions on computer-aided design of integrated circuits and systems. – 1999. – V. 18. – № 11. – P. 1646–1653.
Попов Юрий Игоревич Попов Сергей Игоревич
– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, аспирант, yurpopov@rambler.ru
– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, аспирант, sergey.popove@yandex.ru
122
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 6 (82)
УДК 004.421.2
ВЫЧИСЛЕНИЕ МИНИМАЛЬНОГО ПО ДЛИНЕ ПУТИ ПРОВОДНИКА В ТОПОЛОГИЧЕСКОЙ ТРАССИРОВКЕ ПЕЧАТНОГО МОНТАЖА
Ю.И. Попов, С.И. Попов
В топологическом подходе к трассировке печатных плат возникает задача вычисления пути (формы) проводника по его топологическому пути. Предложен алгоритм, вычисляющий путь минимальной длины с соблюдением конструктивно-технологических ограничений. Алгоритм используется при расчете формы проводников в системе автоматизированного проектирования TopoR. Ключевые слова: САПР, автоматическая трассировка, топологическая трассировка.
Введение
Существует два основных подхода к автоматической трассировке печатных плат: геометрический и топологический. Первый предлагает на протяжении процесса трассировки оперировать метрикой коммутационного пространства, т.е. такими понятиями, как координаты, длина, ширина, расстояние. Второй предлагает использовать только такие понятия, как лежать слева, справа, между; обход по или против часовой стрелки [1].
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 6 (82)
117
ВЫЧИСЛЕНИЕ МИНИМАЛЬНОГО ПО ДЛИНЕ ПУТИ ПРОВОДНИКА…
В 1970-х г.г. Р.П. Базилевич [2] предложил во втором подходе разделить процесс трассировки на два этапа: топологический и геометрический. На первом этапе проводники назначаются в широкие области, в которых они не фиксированы жестко, а лишь задано их относительное положение. На втором этапе – метризации – определяется конкретное положение сегментов проводника с соблюдением конструктивно-технологических ограничений.
В отличие от геометрического подхода, когда на конфигурацию проводника оказывают влияние только соседние элементы топологии, положение которых, как правило, фиксировано, при топологическом подходе на путь (форму) проводника может влиять элемент, находящийся от него на произвольном расстоянии. Проблема состоит в точном учете влияния элементов топологии при вычислении минимального по длине пути проводника.
На форму отдельно взятого сегмента проводника, как правило, влияет лишь небольшая часть элементов топологии. По этой причине для повышения эффективности представляет интерес заранее определить элементы, которые могут оказать влияния на форму сегмента, и не рассматривать остальные при ее вычислении. Предложенный алгоритм реализует эту идею и вычисляет минимальные по длине пути проводников с соблюдением конструктивно-технологических ограничений.
Минимальный по длине путь проводника
Для представления минимального по длине пути проводника рассмотрим следующий пример из [1]. Пусть в некотором зале расставлено множество круглых колонн разного диаметра. Путник, петляя между колоннами, прошел из точки A зала в точку B длинным маршрутом, ни разу не пересекая собственный путь. По дороге он разматывал клубок ниток. Существует бесконечное множество путей, топологически эквивалентных маршруту путника, т.е. проходящих между теми же парами колонн. Но среди этих путей существует кратчайший. Этот путь можно узнать, натянув нить. Нить примет форму единственной кривой, и длина этой кривой будет минимально возможной. Натянутая нить будет огибать колонны по дугам окружностей с соответствующими радиусами, а с одной окружности на другую будет переходить по прямой, касательной к обеим окружностям (рис. 1).
ВВ
АА
аб
Рис. 1. Натянутая нить огибает колонны по дугам окружностей: нить путника (а); натянутая нить путника (б)
Печатная плата, в общем случае, имеет несколько слоев. Каждый из них может быть рассмотрен независимо. Под проводником в работе понимается фрагмент трассы, ограниченный точками ветвления, переходными отверстиями, контактными площадками компонентов, областями металлизации. Проводник прокладывается с соблюдением конструктивно-технологических ограничений (ширины проводников, размеры объектов печатного монтажа, зазоры между ними). Например, если путь проводника w проходит мимо контактной площадки C, то следует учесть ее размеры, другие проводники (с их ширинами), проходящие между w и C, а также требуемые зазоры между ними.
История вопроса
Первый подход к решению задачи вычисления минимального по длине пути предложил в 1980 г. М. Томпа (M. Tompa) [3]. Однако алгоритм имеет ряд существенных ограничений: узлы компонентов упорядочены и находятся на параллельных сторонах канала, ширины проводников нулевые, минимальные зазоры между проводниками одинаковы.
В 1988 г. Ш. Гао (S. Gao) с соавторами опубликовал работу [4]. В ней предложен более сложный алгоритм, однако также с существенными ограничениями на входные данные: одинаковые зазоры между проводниками, нулевые ширины, наличие лишь точечных контактных площадок компонентов.
В 1999 г. Т. Хама (T. Hama) и Х. Этох (H. Etoh) предложили новый подход к решению задачи [5]. Они используют триангуляцию Делоне для разбиения монтажного пространства. Условие Делоне (окружность, описанная вокруг треугольной грани не содержит других вершин триангуляции) они используют как ограничение для расстояния, на котором учитывается влияние контактных площадок на форму проводника. На реальных платах зазор между контактной площадкой и проводником может быть произвольно большим, и соответственно расчет будет некорректным. Кроме того, в предложенном подходе рассматриваются только круглые контактные площадки.
118
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 6 (82)
Ю.И. Попов, С.И. Попов
В системе автоматизированного проектирования (САПР) FreeStyle Router в 1990-х г.г., а затем и в САПР TopoR (вплоть до версии 5.2) был реализован алгоритм, позволяющий вычислять пути проводников [1]. Однако алгоритм не учитывал влияние на путь проводника контактных площадок, расположенных на достаточном удалении от него. Недоучет любого фактора приводит к получению конфигураций с нарушениями конструктивно-технологических ограничений.
Представление объектов печатного монтажа набором круглых примитивов
При работе с объектами печатного монтажа удобно использовать разбиение монтажного пространства, например, в виде триангуляции Делоне или квазитриангуляции [1]. Объекты произвольной формы в разбиении представлены не одной вершиной, а набором вершин, соответствующих вершинам многоугольника, а в ряде случаев и дополнительными вершинами, например, расположенными вдоль линейно протяженных объектов. На рис. 2 приведено возможное расположение вершин на границе прямоугольного объекта печатного монтажа.
Рис. 2. Расположение вершин разбиения на границе прямоугольного объекта
С этими вершинами можно связать круглые примитивы, радиус которых зависит от выбранной модели. Между проводником, проходящим мимо объекта, и примитивом должен быть соблюден зазор, заданный конструктивно-технологическими ограничениями. Чтобы проводник не «провис» между двумя соседними огибаемыми примитивами одного объекта под действием других примитивов (возможно, другого объекта), следует учитывать расстояние до ребра, соединяющего вершины этих примитивов.
Таким образом, «некруглость» объектов просто увеличивает число вершин разбиения, поэтому в дальнейшем изложении без потери общности принимаем, что имеются только круглые контактные площадки, к ним приравняем переходные отверстия, точки ветвления и другие круглые примитивы, разбивающие более сложные объекты. Разбиение монтажного пространства – триангуляция.
Алгоритм вычисления минимального по длине пути
После топологического этапа пути проводников могут быть представлены последовательностью ребер, которые они пересекают. Рассмотрим топологический путь проводника как последовательность отрезков, проходящих, например, через центры пересекаемых ребер.
В общем случае каждая контактная площадка на печатной плате может повлиять на длину пути. Рассмотрим расстояние d между центром круглой контактной площадки C и средней линией сегмента проводника w. Оно должно быть не меньше расстояния, складывающегося из конструктивнотехнологических ограничений: радиус контактной площадки C; ширины проводников, расположенных между w и C; половина ширины проводника w; зазоры между ними.
Для каждого отрезка топологического пути проводника определяются дуги окружностей, центры которых расположены в центрах контактных площадок, а радиусы равны расстояниям d. Путь проводника не может пересекать дуги, так как они построены по конструктивно-технологическим ограничениям.
Алгоритм вычисления минимального по длине пути состоит из двух этапов. 1. Построение вышеописанных окружностей. 2. Вычисление минимального по длине пути, огибающего эти окружности.
Рассмотрим сначала вычисление пути.
Алгоритм вычисления пути, огибающего окружности
Основная идея алгоритма состоит в следующем [1, 3–5]. Пусть дано множество окружностей, упорядоченных вдоль топологического пути. Если задано направление пути, то окружности можно разделить на левые (D, C) и правые (A, B) относительно пути (рис. 3). К окружностям в порядке очередности строятся касательные.
Сначала следует построить касательные к первым левой (D) и правой (A) окружностям, проходящие через начальную точку S. В результате образуется воронка, в пределах которой должен располагаться путь. Если построить касательную из точки S к следующей правой окружности B, то окружность A можно исключить из рассмотрения, так как она находится правее. Касательная из точки S к окружности
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 6 (82)
119
ВЫЧИСЛЕНИЕ МИНИМАЛЬНОГО ПО ДЛИНЕ ПУТИ ПРОВОДНИКА…
C пересекает окружность D, поэтому последняя становится частью воронки (рис. 3, а). Далее аналогично строятся касательные к следующим левым и правым окружностям.
Если правая касательная пересекает левую окружность (рис. 3, б), то левая касательная (ее отрезок) из точки S к этой окружности становится геометрически частью вычисляемого пути (рис. 3, в). В этом случае необходимо далее строить общие касательные с окружностью D (вместо проходящих через точку S). Для левой касательной построение аналогично.
Если два отрезка касательных добавлены в путь, то дуга окружности между ними также становится частью пути.
Полученная последовательность отрезков касательных и дуг окружностей составляет путь минимальной длины.
СВ
СВ
СВ
DD
D
А s
sА
sА
аб
в
Рис. 3. Вычисление пути: построение касательных (а); пересечение касательной и окружности (б); отрезок касательной добавлен в путь (в)
Построение окружностей
Предлагается строить окружности в два этапа. На первом этапе для каждой контактной площадки следует построить множество окружностей. Процесс их построения можно представить как волну, распространяющуюся от центра контактной площадки, поглощая встречающиеся проводники и разделяясь при встрече других контактных площадок. Эти окружности не предназначены для непосредственного вычисления путей проводников, они помогут определить контактные площадки, которые влияют на форму сегментов. На втором этапе, используя эту информацию, следует построить окружности для каждого проводника в отдельности. Опишем этапы по порядку.
На первом этапе для каждой вершины v (соответствующей контактной площадке) рассматривается каждая грань, которой принадлежит вершина v, и выполняются следующие шаги. 1. Из центра контактной площадки A построить две касательные к окружностям контактных площадок B
и C (рис. 4). (Если контактные площадки пересекаются, то перейти к следующей грани.) Рассматриваются касательные, пересекающие ребро b. Они вырезают в плоскости сектор, внутри которого дуга окружности может влиять на минимальный по длине путь проводника. Этот сектор позволяет пространственно ограничить направления, в которых контактная площадка влияет на проводники (сектор в процессе выполнения алгоритма может только уменьшиться).
C bB
cа
А
Рис. 4. Из центра A к окружностям контактных площадок строятся две касательные
2. Вычислить радиусы окружностей с учетом путей проводников, пересекающих грань. На рис. 5 изображена контактная площадка A и три проводника: w1, w2 и w3. Здесь известно только, в каком порядке расположены пути проводников относительно друг друга и контактных площадок. Вычислим последовательно радиусы окружностей для каждого из проводников, необходимые для соблюдения конструктивно-технологических ограничений. Первый радиус (для проводника w1) – это сумма радиуса контактной площадки A, зазора до проводника w1 и половины ширины проводника w1. Второй радиус (для w2) – это сумма первого радиуса, зазора между проводниками w1 и w2, а также половины ширины проводника w2. Последний радиус может влиять на проводник w3 за ребром b.
120
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 6 (82)
Ю.И. Попов, С.И. Попов
b w3
w2
w1 А
Рис. 5. Вычисление радиусов с учетом контактной площадки A и проводников w1, w2 и w3
3. Если последняя окружность с вычисленным радиусом пересекает ребро b, то запомнить информацию о ней в ассоциации с ребром (она будет использована на шаге 2 второго этапа). За ребром b начальной грани находятся грань и два ребра (рис. 6). Через них следует продолжить распространение вычисления радиусов. При этом необходимо построить касательные к окружности контактной площадки за ребром b, так как они могут уменьшить сектор. На рис. 6 за ребром b находятся ребра d и e. Проводник w2 не влияет на радиус окружности для ребра e (не будет учтен при проверке на пересечение). Для ребра d ситуация сложнее. Если бы проводник w2 пересекал ребро e, то можно было бы однозначно указать на необходимость его учета. В приведенном случае проводник учитывается условно. Если за ребром d на расстоянии, учитывающем ширину проводника w2 и соответствующие зазоры, нет других проводников, то процесс распространения в данном направлении будет остановлен. Продолжать вычисление радиусов (за ребра e и d) следует, пока зазоры и ширины проводников могут его увеличить, до пересечения очередного ребра.
ed b
w2
А w1
Рис. 6. Учет проводника w2 при вычислении радиусов окружностей
На втором этапе по очереди рассматриваются топологические пути проводников (последовательности отрезков). Пересекая грань, топологический путь через одно ребро входит, а через другое выходит из нее. Существуют не более двух граней, в которых путь пересекает только одно ребро, – грани, в вершинах которых путь начинается и заканчивается. Для каждого топологического пути выполняются следующие шаги. 1. Каждое пересекаемое топологическим путем ребро инцидентно двум вершинам. Между контактной
площадкой вершины и проводником w находятся другие проводники. Для каждой из вершин необходимо построить окружности с радиусом, равным сумме радиуса контактной площадки, ширин проводников и зазоров между ними. Последним учтенным в радиусе будет рассматриваемый отрезок топологического пути. 2. Для каждого отрезка топологического пути по триангуляции определить окружности, построенные на первом этапе. Эти окружности могут повлиять на минимальный по длине путь, но их радиусы следует изменить таким образом, чтобы последним учтенным в радиусе стал рассматриваемый отрезок топологического пути.
Дуги построенных окружностей, ограниченные секторами, учитывают все необходимые конструктивно-технологические ограничения, поэтому можно применить алгоритм вычисления пути, огибающего окружности.
Заключение
В описанном подходе, в отличие от предложенных ранее, отсутствует ограничение на форму канала, учитываются ширины всех проводников и необходимые зазоры, нет ограничений на их величины. Объекты произвольной формы моделируются набором круглых примитивов с обработкой возможного «провисания» проводников. При этом учет перечисленных факторов не сопровождается снижением производительности.
Асимптотические оценки алгоритма: O(B · F2 · log(B · F)) – время; O(B · F2) – память, где B – общее число изломов путей проводников, состоящих из отрезков между ребрами; F – число контактных площадок на плате – совпадают с оценками алгоритма из [4]. Но в [4] рассматривается влияние каждой контактной площадки на каждый проводник посредством простого перебора и упорядочивания. При
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 6 (82)
121
ВЫЧИСЛЕНИЕ МИНИМАЛЬНОГО ПО ДЛИНЕ ПУТИ ПРОВОДНИКА…
этом строятся заранее все возможные окружности для всех проводников. Предложенный алгоритм строит окружности итеративно, заранее определяется, что в продолжении итераций нет необходимости. Таким образом, предложенный метод не только свободен от существенных недостатков предыдущих версий, но и превосходит их в эффективности. Алгоритм реализован и используется в последней версии системы автоматизированного проектирования TopoR.
Литература
1. Лузин С.Ю., Лячек Ю.Т., Петросян Г.С., Полубасов О.Б. Модели и алгоритмы автоматизированного проектирования радиоэлектронной и электронно-вычислительной аппаратуры. – СПб: БХВПетербург, 2010. – 224 с.
2. Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного конструирования электронных устройств. – Львов: Вища школа, 1981. – 168 с.
3. Tompa M. An Optimal Solution to a Wire-Routing Problem // Journal of Computer and System Sciences 23. – 1980. – P. 127–150.
4. Gao S., Jerrum M., Kaufmann M., Mehlhorn K., Rulling W., Storb C. On continuous homotopic one layer routing // in Proc. 4th Annu. ACM Symp. Computational Geometry. – 1988. – P. 392–402.
5. Hama T., Etoh H. Curvilinear Detailed Routing with Simultaneous Wire-Spreading and Wire-Fattening // IEEE Transactions on computer-aided design of integrated circuits and systems. – 1999. – V. 18. – № 11. – P. 1646–1653.
Попов Юрий Игоревич Попов Сергей Игоревич
– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, аспирант, yurpopov@rambler.ru
– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, аспирант, sergey.popove@yandex.ru
122
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 6 (82)