Материал: лабораторная работа№7 Исследование алгоритмов трассировки печатных соединений

38

показан на рис.7.8. В каждой ячейке указаны приписанные ей на этапе распространения волны путевые координаты и веса. Ячейка B достигается при построении 16-го фронта волны.

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

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

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

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

1.4. Алгоритм Акерса

Наиболее экономичный способ кодирования состояний ячеек коммутационного поля предложен Акерсом [1 – 4]. При распространении волны ячейки поля получают отметки в соответствии с базовой последовательностью 1, 1, 2, 2, 1, 1, 2, 2, … . Данная последовательность характерна тем, что в ней любой член имеет разных соседей слева и справа. Вначале все незанятые ячейки, соседние с ячейкой-источником, помечаются 1, затем все ячейки фронта Ф 2

помечаются так же 1. Далее отметка 2 присваивается ячейкам фронта Ф 3 и т. д.

(рис.7.10).

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

Вариант соединения контактов A и B при этом заданном приоритете дан на рис.7.10.

39

В методе Акерса ячейка поля может находиться в следующих состояниях: пустая, занятая, иметь отметку 1 или 2. Таким образом, на каждую ячейку поля достаточно всего два двоичных разряда памяти.

1.5. Лучевой алгоритм

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

Рис.7.10.

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

Обычно число лучей для каждой из ячеек (источников) принимают одинаковым (часто равным двум). Лучи A (1) , A ( 2) , …, A ( n ) и B (1) , B ( 2) , …, B ( n ) считаются одноименными, если они распространяются из одноименных

источников A или B. Лучи A (i ) и B (i ) являются разноименными по отношению друг к другу. Распространение лучей происходит одновременно из обоих источников до встречи двух разноименных лучей в некоторой точке C.

Путь проводится из ячейки C, в которой встретились лучи по путевым координатам, и проходит через ячейки, по которым распространялись лучи.

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

Рассмотрим работу лучевого алгоритма на примере (рис.7.11).

40

Для источников A и B взято по два луча с взаимно противоположными направлениями. Поскольку разности координат (x A x B ) 0 и (yA yB ) 0 ,

то для луча A (1) допустимое направление движения вначале вниз, а в случае преграды – вправо; для луча B (1) – вверх, влево; для A ( 2) – вправо, вниз; для

B ( 2) – влево, вверх. Если ячейка B будет расположена не справа от A, а слева, то путевые координаты вправо и влево надо поменять местами.

На первом шаге алгоритма просматриваются ячейки с координатами (3,8), (9,3), (4,9) и (8,2). Поскольку эти ячейки оказались свободными, в них ставятся путевые координаты, которые указывают назад, т.е. на те ячейки, из которых на

Рис.7.11.

этом шаге поступил луч. На третьем шаге луч B (1) сверху оказывается заблокированным, поэтому он меняет направление «вверх» на направление «влево» – просматривается ячейка с координатами (8,4). На четвертом шаге луч B (1) оказывается заблокированным, а лучи A (1) и B ( 2) встретились в ячейке C с

координатами (5,4). Луч A ( 2) , пройдя через все поле, оказывается заблокированным в ячейке с координатами (10,1).

Путь строится из ячейки C по путевым координатам в направлении ячеек A

и B. Если бы ячейка (7,2) была занята, то лучи B (1) и B ( 2) оказались бы заблокированными, и решение найдено не было, хотя путь из A в B провести можно.

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

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

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

42

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

Вцентральной части разбитое на квадратные ячейки рабочее поле. Справа зона установки направлений распространения лучей.

Внижней части экрана приведены зоны выбора алгоритма, вида трассировки и режимов ввода контактов и препятствий (проводников).

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

Кроме этого управление возможно с клавиатуры. Клавишей [-] переключается программа в режим ввода препятствий, которые задаются также нажатием клавиши [Insert]. На экране такие ячейки поля выделяются красным цветом.

Для удаления контакта или препятствия необходимо установить на них курсор и нажать клавишу [Delete].

Перед трассировкой соединений с помощью клавиши [/] необходимо выбрать один из алгоритмов (волновой Ли, Акерса или лучевой). Клавишей [*] задать количество направлений распространения числовой волны (4 или 8).

Информация о выбранном алгоритме, направлениях, режиме ввода (контактов либо препятствий) выводится в нижней части экрана.

Режим работы программы (автоматический или пошаговый) задается клавишей [+] и высвечивается в правом верхнем углу экрана. Приоритеты для каждого из восьми направлений трассировки задаются одновременным нажатием клавиши [Alt] и одной из клавиш цифр от 0 до 7. При этом наиболее предпочтительным является нулевое направление, а затем в порядке возрастания чисел. Информация о заданных приоритетах также выводится в правой части экрана.

Трассировка по алгоритму Акерса выполняется в пошаговом режиме. В случае зацикливания программ необходимо одновременно нажать клавиши [Alt] и [Pause]. Каждый последующий шаг в этом режиме выполняется клавишей [Enter].

Удаление выполняется клавишей [Esc].

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

При работе лучевого алгоритма направления распространения лучей устанавливаются клавишами [0] – [7]. При этом информация о направлении