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

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

Для оценки качества трассировки используются различные кри­терии. Трасса выбирается таким образом, чтобы минимизировать со­вокупный показатель F, характеризующий качество трассы по ис­пользуемым критериям.

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

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

1. Распространение числовой волны.

2. Проведение трассы.

На первом этапе все множество квадратов коммутационного поля разделяют на две группы: подмножество свободных квадратов К^с и подмножество занятых квадратов К^з. Трассы могут проходить толь­ко по свободным квадратам, причем после проведения трассы все ее квадраты считаются занятыми. В исходном состоянии к подмноже­ству К^з относятся, например, квадраты, соответствующие контактам элементов и выводам разъемов. Необходимо оптимальным образом соединить контакты x_i и x_j.

Построение числовой волны начинается с выбора в качестве начальной точки произвольного контакта, например контакта x_i. В про­цессе формирования числового фронта волны всем свободным квад­ратам, соседним с квадратами предыдущего фронта, ставится в соот­ветствие число m_r, называемое массой квадрата. Это число пропор­ционально заданной весовой функции F, которая является критерием качества трассы, и характеризует путь с конкретной точки зрения (дли­на пути, число пересечений с другими проводниками, число переходов из слоя в слой и т. п.).

Дата добавления: 2013-12-12