КТОП теория

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

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

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

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

Причем, проводники, отнесенные к одной магистрали, т. е. включенные в подмножество М I , не должны перекрываться, чтобы не было

наложения отрезков разных цепей.

Эффективный алгоритм распределения отрезков по магистралям канала заключается в следующем: 1) упорядочиваем отрезки множества М по начальной координате; 2) формируем подмножества Мi, последовательно включая в них те отрезки, у которых начальная координата больше конечной координаты предыдущего отрезка. Результаты работы первого и второго пунктов алгоритма даны на рис. 11.12. Здесь исходное множество M = {m1, m2 , m3 , m4 , m5 , m6 , m7} и

упорядоченное множество M1 = {m2, m5 , m3 , m1 , m4 , m6 , m7}. Сформированные подмножества M1 = { m2 , m1, m7}; M2 = { m5 , m4}; M3 = { m3 , m6 }.

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

В САПР схемно-топологического конструирования разработка заканчивается выпуском соответствующей конструкторской и технологической документации. Существующие САПР позволяют получать следующую конструкторскую документацию: принципиальные электрические схемы, перечни элементов, сборочные чертежи, спецификации, чертежи слоев ПП и ведомости по ЕСКД. Технологическая документация оформляется в виде компьютерных носителей информации.

11