К минимизации числа межслойных переходов на печатных платах

С.Ю. Лузин,

технич. дир., д.т.н., luzin@eremex.com,

С.И. Попов,

инж.,

Ю.И. Попов,

инж.,

ЭРЕМЕКС, г. Санкт-Петербург

Предложен алгоритм локальной минимизации числа межслойных переходов, основанный на анализе топологии окрестностей пары смежных переходов.

The algorithm for the local minimization of vias number, based on the analysis of the topology of the neighborhood of adjacent pairs of vias, is proposed.

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

Последовательная прокладка проводников обладает тем недостатком, что её результат может существенно зависеть от порядка прокладки проводников.

Основным механизмом оптимизации разводки является последовательная перекладка проводников - поочерёдное удаление и проведение их более дешёвыми путями (или старым путём, если более дешёвого пути не нашлось). Под стоимостью пути здесь понимается интегральный критерий, учитывающий различные факторы (длину проводника, количество переходов проводника со слоя на слой, количество нарушений проектных норм и т.д.): , где S – стоимость пути, x_i – величина i-го фактора, k_i - коэффициент при факторе, k_ix_i – штраф за величину фактора, .

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

Проблема «застревания» в локальном минимуме, когда никакая перекладка одиночного проводника не может улучшить качество разводки, стоит очень остро во всех САПР, использующих последовательную оптимизацию.

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

В данной работе предложен алгоритм локальной минимизации числа межслойных переходов, основанный на анализе топологии окрестностей пары смежных переходов.

Если в цепи имеются смежные переходы v и u и длина соединяющего их проводника менее заданной (например, 10 мм):

1. Получить списки и слоев, на которых расположены проводники, инцидентные v и u соответственно, исключая проводники в пути, соединяющем v и u.

2. Получить список слоев, на которых расположены проводники, пересекающие (на совмещенной топологии) проводники в пути, соединяющем v и u.

3. Если ∩ ( ∩ ) ≠

Перейти к следующей паре смежных переходов (локальная оптимизация невозможна).

4. Если путь P из проводников между v и u состоит не из одного проводника:

Продублировать P по часовой от каждого из переходов до последнего проводника, отходящего от P в соответствующем направлении (рис. 1).

рис. 1. Дублирование пути между переходами (проводники серого, черного цветов и проводник, представленный штриховой линией, находятся на трех разных слоях соответственно)

5. Определить, можно ли скопировать проводник, соединяющий v и u, на слои и (проводник не пересекает проводники на слоях L).

6. Если невозможно скопировать проводник ни на , ни на : Перейти к следующей паре смежных переходов (локальная оптимизация невозможна).

7. Иначе, если возможно скопировать и на и на , то выбрать тот переход (v), для которого │  ∩  │ ≤ │  ∩ │.

8. Иначе выбрать переход (v), для которого возможно скопировать проводник (на ).

9. Если ∩ ≠ (рис. 2)

9.1. В слоях ∩ завести за u проводники, пересекающие проводник, соединяющий v и u .

9.2. Если диапазон слоев перехода u не содержит какие-либо слои из , сменить тип перехода u на тип, содержащий .

9.3. Скопировать проводник, соединяющий v и u, на слои .

10. Удалить исходный проводник, соединяющий v и u.

11. Удалить переход v.

12. Перейти к следующей паре смежных переходов.

рис. 2. Устранение лишнего смежного перехода

На тестовых примерах многослойных плат использование данного алгоритма позволило на 5-10% уменьшить число межслойных переходов.

Литература

1. Полубасов О.Б. Глобальная минимизация количества межслойных переходов / Полубасов О.Б. // Технология и конструирование в электронной аппаратуре. - 2001. № 2. - C. 3-9.