Системы автоматизированного проектирования

Системы автоматизированного проектирования

(магистр ИВТ)

Лекция №7. Алгоритмы и модели трассировки печатных соединений в ЭА

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

Волновые алгоритмы. Волновой алгоритм Ли

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

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

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

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

Первую ячейку, в которой зарождается волна влияний, называют источником, а вторую - приемником волны.

Чтобы иметь возможность следить за прохождением фронта волны влияний, его фрагментам на каждом этапе присваивают некоторые веса:

где P_k и Р_k-1 - веса ячеек k-го и (k-1)-го фронтов; ψ (f₁, f₂, …, f_g) – весоваяфункция, являющаяся показателем качества проведения пути, каждыйпараметр которой f_i(i =1, 2, ..., g) характеризует путь с точки зрения одного из критериев качества (длины пути, числа пересечений и т. п.).

На Р_kнакладывают одно ограничение – веса ячеек предыдущих фронтов не должны быть больше весов ячеек последующих фронтов.

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

Если в результате распространения волна достигла приемника, то осуществляют « проведение пути », которое заключается в движении от приемника к источнику по пройденным на этапе распространения волны ячейкам, следя за тем, чтобы значения Р_k монотонно убывали. В результате получают путь, соединяющий эти две точки.

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

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

Например, если задаться приоритетным порядком проведения пути сверху, справа, снизу и слева, то коды соответствующих путевых координат будут 00, 01, 10 и 11.

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

Примеры

(при использовании различных критериев качества)

Во всех примерах задан приоритетный порядок проведения пути: сверху, справа, снизу и слева:

Рисунок 7.1

Вместо числовых кодов для обозначения соответствующих путевых координат будем использовать стрелки, указывающие их направление

Модификации волнового алгоритма

1. Метод встречной волны.

2. Метод соединения комплексами.

3. Лучевой алгоритм трассировки.

Метод встречной волны

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

Достоинства:

1. время, затрачиваемое на этапе распространения волны, уменьшаются примерно вдвое.

Недостатки:

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

2. возможность построения лишь соединений типа «вывод - вывод».

Метод соединения комплексами:

Пусть необходимо объединить некоторое множество точек М = {т₁, т₂, ..., m_n}.

1. Выбираем в качестве источника произвольную точку

m_i ∈ M

и распространяем из нее волну влияний до встречи с какой-либо точкой

m_j ∈ M

2. Проводим путь, соединяющий точки m_i и т_j.

3. Вновь перейдем к процессу «распространения волны», выбрав в качестве источника только что построенный проводник, и заканчиваем его при встрече с какой-либо точкой

4. Проведя путь, получаем соединение уже трех точек множества М.

5. Теперь источником волны является дерево, состоящее из построенных проводников, и т. д.

Достоинство:

1) возможность присоединения каждой очередной точки (начиная с третьей), к любой точке ранее построенных соединений,

2) сокращение общей длины печатных проводников

3) увеличение числа разводимых цепей

4) возможность построения соединений типа «вывод - проводник» и «проводник - проводник».

Быстродействие алгоритма можно повысить, применив метод встречной волны, если это позволяет объем памяти ЭВМ. В данном случае источниками «распространения волн» являются все ранее построенные проводники и ячейки, подлежащие объединению.

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

Пример.

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

Рисунок 7.6 –Пример для эвристического алгоритма трассировки

Рисунок 7.7 – Путевые координаты для лучей

Зададим следующий приоритетный порядок проведения пути: вверх, вправо, вниз, влево (вариант I).

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

Считаем, что трасса удаляется от цели, если на очередном шаге алгоритма расстояние до данной прямой возрастает.

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

При изменении порядка движения: вправо, вверх, влево, вниз - конфигурация трассы изменится и препятствие будет обойдено справа (вариант 2).

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

Другой вариант эвристического алгоритма, не требующий разбиения монтажного поля на ячейки, основан на проведении соединений по кратчайшему пути в обход препятствий, представляемых в виде прямоугольников, задаваемых координатами своих углов. Размеры прямоугольников выбирают такими, чтобы по его сторонам могли прокладываться новые проводники. При встрече с препятствием трасса проводится по периметру соответствующего прямоугольника. Каждое конкретное направление обхода оценивается с точки зрения удлинения строящегося проводника и числа возможных пересечений его с ранее построенными и еще непроведенными трассами. При этом выбирается то направление, которому соответствует лучшее значение оценки. При невозможности обхода очередного препятствия в программе предусмотрена процедура возврата к предыдущему препятствию и выбору иного варианта его обхода. Использование этой процедуры позволяет сократить число неразведенных цепей. Для экономии оперативной памяти ЭВМ в алгоритме применен принцип фрагментарного проведения трасс, при котором все монтажное поле разбивается на отдельные дискреты, хранящиеся во внешнем ЗУ и вызываемые в оперативную память по мере необходимости при прокладывании проводника внутри соответствующего дискрета. Это создает благоприятные условия для трассировки плат практически любого размера.

Системы автоматизированного проектирования

(магистр ИВТ)

12 3 4 Следующая ⇒