КАНАЛЬНЫЕ АЛГОРИТМЫ ТРАССИРОВКИ ПЕЧАТНЫХ ПЛАТ

Всякий процесс создания сложных систем, в том числе и РЭА, представляет собой последовательность определенных этапов. При разработке изделий РЭА традиционным является метод нисходящего проектирования. Если при этом исключить стадию производства элементной базы (как правило, интегральные схемы, транзисторы, диоды и др. создаются независимо от того или иного радиоэлектронного комплекса), то одним из этапов будет трассировка печатных плат.

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

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

К одному из способов относят алгоритм канальной трассировки [1, 2, 3, 4, 5, 6]. Каналы представляют собой совокупности магистралей, расположенных между рядами и столбцами элементов навесного монтажа на коммутационном поле (рис. 1).

Рисунок 1. Сеть горизонтальных и вертикальных каналов

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

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

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

В работах [1, 2] предложен учет текущей загрузки каналов при трас­сировке очередной цепи. Перед началом процесса трассировки для каждой цепи строится сеть возможных каналов. При построении сети считается, что каждому выводу сопоставляется вертикальный или горизонтальный каналы. Наложение сетей отдельных цепей на основную сеть каналов позволяет дать верхнюю оценку загрузки каналов на различных участках.

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

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

Основной задачей является выделение из множества соединений, отне­сенных к каналу, минимального числа h подмножеств отрезков, каждое из которых может быть назначено на одну магистраль канала. При этом число h должно быть меньше пропускной способности γ.

Пусть  - множество отрезков, отнесенных к одному каналу: , i = 1, 2,... n. Два отрезка считаются пересекающимися и не могут быть помещены на одну магистраль, если .

Графом отрезков G(S) множества S является граф, вершинами которого служат отрезки  (i=1,2, … n), а ребра соответствуют пересечению отрезков  и  (рис. 2). Для оптимального использования магистралей канала необходимо получить минимальную раскраску вершин графа отрезков G(S). При этом вершинам одного цвета соответствуют отрезки одной магистрали, а хроматическое число  равно минимальному числу используемых магистралей.

Рисунок 2. Построение графа отрезков

В работах [8, 9] рассмотрен случай, когда цепь располагается в не­скольких горизонтальных каналах. При этом минимизация числа используемых горизонтальных магистралей осуществляется с учетом вертикальных связей между каналами. В случае, если пропускная способность канала фиксирована, то возникает задача выделения максимального числа отрезков из множества , которые могут быть помещены на γ магистралях канала. Методы решения этой задачи приводятся в работе.

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

Список литературы:

1. Гурвич Е.И., Крапчин А.И. Быстродействующий алгоритм трассировки двуслойных печатных плат // Вычислительная техника,- Каунас: Каунас, политехн. ин-т, 1973,- T.IV.- С. 132 - 136.
2. Лазарева Т.С. Алгоритм трассировки печатных соединений на основе пред­ставления о каналах // Автоматика и вычислительная техника,- 1969,- №5,- С. 12-15.
3. Freitag H. Design automation for large scale integration / Wescon Technical Papers.- Los Angeles, Calif., 1966.
4. Gresse M. A. Une me'thode de trace' en technologie "blocs denses" // Colloque international sur la microe'lectronique avance'e.- Paris, 1970.- P. 393 - 401.
5. Litaize D. Trace' automatique de plaquettes de circuits imprime's // Automatisme.- 1973,-V.XVIII,№1.-P. 7- 15.
6. Loberman H., Weinberger A. Formal procedures for connecting terminals With a minimum total wire length // J. ACM.- 1959,- V.4, № 4,- P. 428 - 437.
7. Mah L., Steinberg L. Topological class routing for printed circuit boards // Proc. ACM - IEEE Design-automation workshop.- Los Angeles, 1972,- P. 80 - 93.
8. Курейчик В.М., Лебедев В.К. Алгоритм уменьшения числа каналов при трассировке соединений // Методы расчета и автоматизации проектирования устройств микроэлектронных ЦВМ,- Киев: ИК АН УССР, 1974,- С. 52 - 63.
9. Alia G., Frosini G., Maestrini P. Automated module placement and wire routing according to a structured biplanar scheme in printed boards // Computer aided design.- 1973,- V.5, № 3,- P. 152 - 159.