Характеристика основных алгоритмов трассировки соединений

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

1. Трассировка соединений

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

Исходной информацией для решения задач трассировки соединений являются:

- список цепей;

- параметры конструкции элементов и коммутационного поля;

- данные по размещению элементов.

В алгоритмическом плане задача трассировки состоит в построении для всех цепей схемы оптимальных монтажных соединений. Задача трассировки имеет метрический и топологический аспекты. Метрический аспект предполагает учет конструктивных размеров элементов, соединений и коммутационного поля (КП). Топологический аспект связан с выбором допустимого пространственного расположения отдельных монтажных соединений на КП при ограничениях на число пересечений соединений, число слоев коммутационной схемы и т.п.

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

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

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

К первой группе относятся так называемые топографические методы, в которых приоритет отдается метрическому аспекту задачи. Вторая группа основана на графотеоретическом подходе к решению задачи трассировки. В нашем курсе рассматриваются методы первой группы.

Топографический метод трассировки в общем случае содержит следующие основные этапы:

получение списка соединений;

распределение соединений по слоям;

определение порядка прокладки соединений;

собственно трассировка отдельных соединений.

Методы данной группы наиболее эффективны для трассировки двухсторонних и многослойных печатных плат.

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

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

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

2. Алгоритмы трассировки соединений

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

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

Рис. 1. а) принципиальная электрическая схема; б), в) схемы электрических соединений

На рис. 2-4 даны примеры конфигурации разводки электрических цепей автономных объектов.

Рис. 2

Рис. 3

3. Алгоритмы трассировки проводных соединений

Пусть задана электрическая цепь (рис. 4) и соединенные ею элементы.

Рис. 4

Они могут быть представлены полным графом (рис. 5).

Рис. 5

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

Рассмотрим типовые конфигурации. Если не заданы жесткие требования надежности, то это может быть разомкнутая конфигурация, т.е. из графа надо выделить дерево. При этом могут быть заданы ограничения на степень вершин, а могут и не задаваться (рис. 6).

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

Рис. 6

Алгоритм Прима.

Пусть имеется множество точек плоскости P=p1,p2,…,pn, соответствующих выводам произвольной цепи. Пусть эта цепь описывается полным графом G=(E,U), вершины которого соответствуют выводам цепи, а ребра электрическим связям. Ребра с приписанным к ним «весом» характеризуют соединения меду парами выводов. Значение «веса» может быть равно, например, расстоянию между соответствующими точками множества P. Требуется найти минимальное покрывающее дерево (т.е. дерево, включающее в себя все вершины из E и имеющее минимальный вес ребер).

Наиболее эффективным из известных алгоритмов является алгоритм Прима:

1. для произвольного вывода цепи найти ближайший вывод и провести соединение;

2. на последующем шаге i = 2,3,…,n-1 из множества неподсоединненых выводов выбрать тот, который находится ближе остальных к группе yже связанных выводов и подсоединить его к этой группе по кратчайшему пути.

Построенное таким образом дерево будет иметь минимальную суммарную длину соединений.

При разработке монтажных соединений часто вводится ограничение на максимальное число соединений л к клемме элемента, т.е. на степень вершины. Если л<6 (до л=6 алгоритм точный), то можно использовать модифицированный алгоритм Прима:

1. всякая изолированная вершина соединяется с ближайшей, не соединенной с л другими вершинами;

2. всякий изолированный фрагмент соединяется кратчайшим ребром с ближайшей вершиной, не соединенной с л другими вершинами.

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

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

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

1) n-1 шаговый процесс выбора кратчайших ребер в полном графе;

2) проверка каждого ребра на выполнение ограничений задачи;

3) составление пути из выбранных ребер.

Алгоритм:

· составляется упорядоченная по возрастанию длин последовательность ребер полного графа;

· очередное ребро i=1,2,…,n-1 выбирается по порядку из этой последовательности при выполнении следующих условий:

ребро не соединяет конечную и начальную точки;

степень вершин, соединяемых ребром, не превышает допустимой (л=1 - для начальной и конечной точек и л=2 для остальных);

ребро не образует цикла с ребрами, уже включенными в путь;

при включении любого ребра в путь, кроме (n-1)-го , начальная и конечная точки не связываются.

Построение печатных соединений.

Большинство алгоритмов основано на волновом алгоритме, который еще называют алгоритмом Ли.

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

Требуется соединить контакты в каждом подмножестве, чтобы цепи не пересекались.

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

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

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

В алгоритме Ли этот процесс называется распространением волны, а пометки множества узлов, помеченных на каждой итерации - фронтом волны. Если в этом процессе произошел прорыв , т.е. получил пометку сток Т, то это значит, что может быть установлена связь между S и T, которая на этапе проведения пути осуществляется по меткам. В противном случае пути нет.

Сначала пометку (-,(S)=0) получает исток S. Эта пометка означает, что нет узла, из которого помечается исток (-), и итерация этой пометки нулевая ((S)=0), затем помечаются все соседние к истоку узлы. Например, узлы x,y,z,u c пометками (S,е(x)=1), (S,е(y)=1), (S,е(z)=1), (S,е(u)=1) и т.д.

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

Если несколько узлов имеют одинаковое минимальное е, то берется любой из них, для пометки соседних.

Если пометился сток Т, то восстанавливается путь из Т в S, идя по пометкам (их левым частям). Правые части пометок позволяют оптимизировать выбор маршрута из истока в сток.

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

Пример волнового алгоритма.

Пример алгоритма для поиска пути между двумя ячейками - источником и приемником дискретного рабочего поля (ДРП).

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

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

Путь может быть двух видов: ортогональный и ортогонально-диагональный. Путь первого вида состоит из отрезков, параллельных сторонам ДРП. Путь второго вида может вдобавок содержать диагональные отрезки (угол между таким отрезком и стороной ДРП равен 45 или 135 градусов).

В первом случае каждая ячейка имеет 4 соседа, а во втором - 8.

Описание волнового алгоритма.

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

Волна, идущая от источника к приемнику, на каждом шаге первой части алгоритма пополняется свободными ячейками ДРП, которые, во-первых, еще не принадлежат волне, и, во-вторых, являются 4-соседями ячеек, попавших в волну на предыдущем шаге.

В примере волна достигла ячейку-приемник за 23 шага.

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

Рис. 7. Обратный ход: формирование пути

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

Волновой алгоритм либо находит кратчайший путь от источника к приемнику, либо информирует о неудаче, если путь к приемнику блокируется препятствиями.

Размещено на Allbest.ru