Методы и алгоритмы решения задач компоновки

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

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

 

Существенными недостатками волнового алгоритма являются малое быстродействие и большой объем оперативной памяти ЭВМ, необходимый для хранения информации о текущем состоянии всех ячеек коммутационного поля, возможность построения лишь соединений типа «ввод-вывод». Попытки устранить указанные недостатки привели к созданию ряда модификаций волнового алгоритма.

 

 

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

 

 

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

 

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

Оценим число ячеек, просматриваемых на этапе распространения волны, при использовании в качестве источников одной или двух объединяемых точек. Пусть расстояние между  этими точками R. Тогда для первого случая в момент достижения волной ячейки-приемника площадь просмотренной окрестности имеет величину (знак равенства соответствует отсутствию преград пути распространения волны). Для второго случая в момент встречи фронтов двух волн площадь просмотренной окрестности .

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

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

 

 

 

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

 

 

В данном алгоритме, предложенным Л.Б. Абрайтисом, выбор ячеек для определения пути между соединяемыми точками A и B производят по заранее заданным направлениям, подобным лучам. Это позволяет сократить число просматриваемых алгоритмом ячеек, а следовательно, и время на анализ и кодировку их состояния, однако приводит к снижению вероятности нахождения пути сложной конфигурации, и усложняет учет конструктивных требований к технологии печатной платы.

Работа алгоритма заключается в следующем. Задается число лучей, распространяемых из точек A и B, а также порядок присвоения путевых координат (обычно число лучей для каждой ячейки-источника принимается одинаковым). Лучи A(1), A(2),…, A(n) и B(1), B(2),…, B(n) считают одноименными, если они распространяются из одноименных источников A или B. Лучи A(i) и B(i) являются разноименными по отношению друг к другу. Распространение лучей производят одновременно из обоих источников до встречи двух разноименных лучей в некоторой ячейке C. Путь проводится из ячейки C и проходит через ячейки, по которым распространялись лучи.

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

 

 

 

 

Лучи:

A(1): вверх, влево

A(2): влево, вверх

B(1): вниз, вправо

B(2): вправо, вниз

На втором шаге луч B(1) оказывается заблокированным, а на четвертом шаге блокируется и луч A(2). Лучи A(1) и B(2) встречаются в ячейке C на восьмом шаге.

 

 

Обычно с помощью лучевого алгоритма удается построить до 70-80% трасс, остальные проводят, используя волновой алгоритм или вручную. Его применение особенно выгодно при проектировании плат с невысокой плотностью монтажа.

 

 

 

 

 

 

 

 

 

 

 

 

 

ИСПОЛЬЗУЕМАЯ ЛИТЕРАТУРА

 

 

1. Б.Н. Деньдобренко, А.С. Малика  «Автоматизация конструирования РЭА»,

Москва «Высшая школа» 1980.

2. В.М. Курейчик «Математическое обеспечение конструкторского и технологического проектирования с применением САПР»,

Москва «Радио и связь» 1990.

3. К.К. Морзов, В.Г. Одиноков, В.М. Курейчик «Автоматизированное проектирование конструкций радиоэлектронной аппаратуры», Москва «Радио и связь» 1983.
4. В.Н. Ильин, В.Т. Фролкин, А.И. Бутко и др.; «Автоматизация схемотехнического проектирования: Учебное пособие для вузов», Москва «Радио и связь» 1987.