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

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

Рассмотрим основные применяемые алгоритмы трассировки соединений.

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

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

В реальных печатных платах с помощью волнового алгоритма удается проложить до 90-957о нсех трасс за несколько часов работы на ЦВМ средней мощности.

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

Лучевой алгоритм менее универсален, чем волновой, и позволяет прокладывать около 80% трасс, но более экономичен (время трассировки одной платы на ЦВМ средней мощности 10-15 мин).

3. Маршрутные алгоритмы, названные так потому, что они строят трассу по кратчайшим маршрутам, а в случае встречи с

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

Так же как и лучевые, маршрутные алгоритмы позволяют находить около 80% трасс на печатной плате за 5-15 мин на ЦВМ средней мощности.

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

В основу алгоритма положены следующие критерии качества трассировки:

а) соединения между элементами внутри каждого связного множества должны быть наименьшей длины;

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

Решение задачи трассировки при применении волнового алгоритма выполняется в 2 этапа:

1. Моделирование распространения волны на пространстве платы и определение возможности прокладки трассы.

На этом этапе на каждом шаге моделирования создается фронт волны. Во множество элементов 1-фронта будут входить все соседние с исходным элементом А элементы. В общем случае часть элементов 1-фронта будет свободна, а остальные - заняты или запрещены. В состав элементов 2-фронта входят все элементы пространства, которые являются соседними для свободных элементов 1-фронта и не являются исходным элементом, в состав элементов 3-фронта входят все элементы пространства, которые являются соседними для свободных элементов 2-фронта и не входят в состав 1-фронта. В состав эле-IMeHTOB /С-фронта входят все элементы пространства, которые являются соседними для свободных элементов (/С-1)-фронта и не входят в множество элементов фронтов с номерами /С-2. Введем следующие обозначения:

{Фк} - множество элементов /С-фронта волны.

{Р. {С.

- множество элементов /С-окрестности элемента Л,

- подмножество свободных элементов /С-фронта волны, подмножество занятых элементов /С-фронта,

- подмножество запрещенных элементов /С-фронта.

Очевидны следующие соотношения:

W={Pi}; {0j = +{Сj-f{Zj. (I.И)

Для пространства, не имеющего занятых и запрещенных элементов, справедливо следующее:

*~-2308 65

На каждом шаге формирования фронта волны проводится проверка двух условий: 1. Бе 2. {Р} =0.

Вьшолнение первого условия означает, что элемент В входит в состав /(-фронта волны, распространяемой от А, т. е. проведение трассы АВ возможно.

При анализе второго условия проверяется существование возможности распространения волны. Если все элементы фрон-

Вбод Ванны/

2 вычисление координат множества элементов

(•Рк)

Проверка условия (Фк]+0

* Присвоение путевых координат элементам множества ()

Проберна услаВия

7 Запись трассы АВ В список непроВеВенных трасс

Запись координат-трассы АВ

Рис. I.I7. Структурная схема волнового алгоритма нахождения кратчайшего пути без пересечений множества занятых и запрещенных элементов

та волны являются занятыми или запрещенными, а элемент В в состав /С-фронта не вошел, то проведение трассы АВ без пересечения.невозможно.

2. Определение искомого соединения по путевым координатам, вычисленным в процессе распространения волны.

Рассмотрим структурную схему алгоритма (рис. 1.17).

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

1а. г/al. 1в. у л