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

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

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

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

Достаточно большая группа методов трассировки печатных соединений основана на использовании представлений о магистралях.

В работе [1] Миками и Табуки предложили один из алгоритмов ма­гистральной трассировки. Основная идея заключается в следующем. Пусть требуется найти соединение между точками А и В (рис. 1.). Из точек А и В строятся лучи в горизонтальных и вертикальных направлениях с использованием только свободных ячеек. Эти лучи являются магистралями первого уровня. Если эти магистрали пересекутся, то сразу получается искомое соединение. Если магистрали и не пересекутся, то строятся магистрали второго уровня. Они перпендикулярны к магистралям первого уровня и проводятся через точки, расположенные в узлах основной сетки.

В общем случае процесс построения магистралей -го уровня состоит в выборе базовых точек на магистралях i-го уровня и проведения через них отрезков нормалей, не пересекающих области, запрещенные для проведения соединений. Построение магистралей следующего уровня выполняется попеременно для точек А и В до тех пор, пока либо очередной уровень не может быть образован (проведение пути невозможно), либо на очередном шаге некоторая магистраль из  пересечется с магистралью из  В последнем случае может быть построен путь, содержащий (1+j-1) поворот (переход). Далее применяется процедура минимизации длины соединения. При программной реализации данного алгоритма на ЭВМ возможно кодирование коммутационного поля без использования матричных представлений. Тогда время работы алгоритма и требуемый объем памяти не зависят прямым образом от размеров коммутационного поля, а определяются в основном сложностью конфигураций проложенных соединений. С этой точки зрения трассировка по магистралям более эффективна, чем волновой алгоритм. Но по мере заполнения поля трассами соединений эффективность процесса поиска снижается и временные затраты приближаются к затратам времени волнового алгоритма.

а)

б)

Рисунок 1. Трассировка по магистралям

а) Магистрали первого уровня; б) Магистрали второго уровня

Статистический анализ реальных топологий, выполненных конструктором, показывает, что подавляющая часть соединений имеет 2-3 поворота. В этой связи был разработан ряд эвристических алгоритмов поиска малоповоротных путей [2, 3, 4, 5], имеющих в основе своей работы представления о магистралях. Отличительной особенностью этих алгоритмов является то, что они исследуют лишь незначительную часть путей простой конфигурации. Благодаря этому затраты времени на построение основной части соединений значительно меньше. С небольшими изменениями эти же алгоритмы позволяют производить трассировку двухслойных ортогональных соединений. В этом случае применяется совмещенное рабочее поле для горизонтальных и вертикальных соединений, и соответственным образом изменяется определение занятости ячеек ДРП.

При построении горизонтальных отрезков ранее расположенные вертикальные отрезки не считаются преградами и наоборот. В точках поворота соединений вводятся межслойные переходы. Время расчета одного соединения с помощью алгоритма [3] сокращается примерно на 2 порядка по сравнению с волновым алгоритмом. Этот алгоритм завершает построение порядка 90 % всех двухслойных соединений. К числу непроведенных соединений, как правило, относятся соединения более сложной формы, с большим числом поворотов. Другой компенсирующий алгоритм поиска малоповоротных путей [2] осуществляет построение соединений с двумя поворотами примерно в 4 раза быстрее волнового алгоритма. Но при усложнении конфигураций соединений (число поворотов больше 3-4) эффективность подобного рода алгоритмов по сравнению с волновыми снижается. Аналогичные результаты дают алгоритмы [4, 5].

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

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

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

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

1. Mikami K., Tabuchi K. A computer program for optimal routing of printed circuit conductor // IFIP Congress 68,- Edinburg, 1968,- P. 76 - 79.
2. Андреев Г.Ю., Петухов Г.А., Скородубский В.Н. Компенсирующий алгоритм поиска малоповоротных путей // Вычислительная техника. - Каунас: Каунас, политехи, ин-т, 1972,- T.III.- С. 380 - 386.
3. Ногис Р.В., Юркунас Д.Ю. Алгоритм трассировки печатных соединений с малым числом поворотов // Вычислительная техника,- Каунас: Каунас, политехи. ин-т, 1970,- T.I.- С. 326 - 331.
4. Aramaki J., Kawabata Т., Arimoto K. Automation of etching pattern layout //Comm. ACM.- 1971,-V.14, № Ц.. p. 720-730.
5. Glem R.R., Lathrop J.W. Two approaches to the computer routing of interconnections // Proc. 20th Electr. Comp. Conf. 1970,- № 4,- P. 390 - 411.