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

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

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

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

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

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

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

Весьма важным вопросом проектирования печатных проводников является повышение скорости разводки соединений. В этой связи был разработан ряд алгоритмов, основанных на геометрических методах. Основная идея данной группы алгоритмов состоит в осуществлении направленного поиска пути между источником и целью. В работах [4, 5, 6, 7, 8] изложены основные принципы функционирования различных лучевых алгоритмов и алгоритмов "прицеливания". Эти методы обладают достаточно высоким быстродействием и применяются при разработке топологии схем с невысокой плотностью соединений в режиме оперативного графического взаимодействия. При ортогональной разводке они обеспечивают порядка 80% соединений. Оставшиеся соединения дотрассируются как правило одним из волновых алгоритмов.

Практически все основные алгоритмические методы, используемые при создании САПР печатных соединений, обладают ограниченной областью применения и не свободны от недостатков. Попытки устранить эти недостатки привели к разработке ряда алгоритмических методов трассировки, в которых используются различные комбинации основных методов и наряду с этим содержатся некоторые новые элементы. Число таких алгоритмов постоянно растет и классифицировать их по какому-либо основному принципу функционирования весьма затруднительно.

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

Для эвристического алгоритма затраты времени относительно малы и остаются практически неизменными в ходе трассировки. Вместе с тем, по мере заполнения поля эффективность алгоритма падает. Оптимальное сочетание преимуществ обоих алгоритмов иллюстрируется на рис. 2.

а)

б)

Рисунок 1. Затраты времени на построение одного соединения

а) Волновой алгоритм; б) Эвристический алгоритм

Рисунок 2. Суммарные затраты времени на трассировку

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

1. Широ Г.Э., Лапидус Л.И. Метод трассировки печатных соединений // Применение вычислительных машин для проектирования цифровых устройств.- М.: Сов.радио, 1968,- С. 199 - 215.
2. Широ Г.Э. Метод проектирования печатного монтажа, основанный на эвристических принципах // Методы разработки схем и конструкций цифровых систем,- Л.: ЛДНТП, 1967,- С. 132 - 148.
3. Особенности использования аналогового рабочего поля для машинной трассировки межсоединений / Р.П. Базилевич, И.В. Парканий, Н.Ф. Стороженко, О.З. Ясеницкий // Вычислительная техника.- Каунас: Каунас, политехи, ин-т, 1974,- Т.VII,- С. 103 - 106.
4. Абрайтис Л.Б. Лучевой алгоритм для проведения печатных соединений // Во­просы радиоэлектроники. Сер. VII.- Электронная вычислительная техника. - 1968,-Вып. З.-С. 35 -46.
5. Орловский Г.В., Покровский А.М. Алгоритм трассировки печатных плат // Обмен опытом в радиопромышленности,- 1971.- № 7,- С. 11 - 15.
6. Рябов Г.Г., Бликова Л.А. Динамический подход к задаче трассировки // Вычислительная техника,- Каунас: Каунас, политехи, ин-т, 1972,- Т.III,-С. 403 - 407.
7. AirdТ.,Milnes H.W. A program for automating circuit layout // The Journal of the Industrial Mathematics Society.- 1964,- V.14, pt.2.- P. 1 - 8.
8. Galy P., Ghendrich P., GuillameG., Ombredan E., Wolf A. Trace' automatique des circuits imprime's // L'onde electrique.- 1969,- V.49, № 1.- P. 113 - 119.
9. Glem R.R., Lathrop J.W. Two approaches to the computer routing of interconnec­tions // Proc. 20th Electr. Comp. Conf. 1970,- № 4,- P. 390 - 411.