Информационные технологии проектирования электронных средств

- 67 - Тема: Многослойная трассировка ЛЕКЦИЯ 15. Распределение соединений по слоям После построения КПД (Прима или Штейнера) проводится анализ схе- мы соединений для выявления таких групп соединений, которые не могут быть расположены на одной плоскости из-за возможных пересечений. Математиче- ски эта задача сводится к отысканию разбиения графа схемы на минимальное число планарных подграфов с последующей реализацией их в отдельных слоях. При разработке топологии многослойных схем возникает также задача распределения “конфликтующих” соединений или их групп по отдельным сло- ям. Это так называемое расслоение, которое может выполняться до, после или во время трассировки. Среди алгоритмов многослойной трассировки наиболее известен алго- ритм Хейса. Он является обобщением алгоритма Ли и позволяет осуществлять построение соединений в пространстве. В качестве рабочего пространства, как правило, используется набор плоскостей (слоев), связанных между собой с по- мощью межслойных переходов (рис.38). Алгоритм осуществляет поиск крат- чайшего пути в многослойном дискретном рабочем поле (ДРП) между двумя рабочими точками. Для каждого слоя коммутации вводится дискретное рабочее поле ДРП i , где i – номер слоя. Считается, что ячейки, принадлежащие различным слоям и лежащие друг над другом, в процессе трассировки могут быть связаны перехо- дами. Алгоритм Хейса включает процедуру распространения числовой волны для каждого ДРП i и процедуру проведения пути. В процессе поиска пути запрещаются пересечения уже проведенных со- единений, поэтому ячейки ДРП i могут быть занятыми и свободными. Занятой