Алгоритмы расслоения (многослойные печатные платы)

Многослойный монтаж печатных (плёночных) соединений между компонентами электронной схемы позволяют сократить суммарную длину соединений (τ_{зад. min}), уменьшить вес и габариты проектируемой аппаратуры.

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

Целью решения этой задачи является обеспечение 100% трассировки соединений, уменьшение числа слоёв и межслойных переходов, наиболее рациональное использование объёма монтажного пространства.

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

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

Большинство приближенных алгоритмов расслоения до трассировки связана с введением определенных количественных оценок, конфликтуемости цепей при их распределении в 1 слой. Эти оценки вычисляются на основе инф-ии о расположении элементов и контактов цепей, полученных после решения задач размещения. Такого рода оценки могут зависеть от степени перекрытия минимальных прямоугольников, охватывающих контакты отдельных цепей, числа контактов цепей и т.д. После определения степени конфликтуемости каждой пары цепей строится взвешенный неор. граф конфликтов, в котором кажд.вершине h?H соответствует некоторая цепь, а каждому ребру v_i,j?V соот-т наличие конфликта между цепями Hi и Hj. Вес принимается равным оценке конфликтуемости между соот-ми цепями. Далее осуществляется раскраска вершин графа G в заданное число цветов, при котором сумма весов ребер, соединяющих вершин одного цвета минимальна. Раскраска вершин графа конфликтов осуществляется различными эвристическими алгоритмами.

Расслоение после предварительной трассировки состоит в следующим. На 1-м этапе с помощью одного из алгоритмов построения кратчайших, связ-х деревьев(КСД) осуществляется предварительная трассировка соединений в одном слое. В процессе получения совмещенной топологии минимизируется такие геометрические размеры как длина, число перегибов, число пересечений. Далее также, как и в алгоритме расслоения до трассировки строится граф конфликтов, но не между цепями, а между отдельными двухконтактными соединениями(отрезками проводников) При этом граф конфликтов G=(X,V) явл-ся неорг-м графом, наличие ребра в котором между x_i и y_j соответствует пересечению отрезков в совмещенной топологии.

Пример:

К=2(требуемое число слоев)

Вершина ГК раскрашивается в заданное минимальное число цветов так, что вершина первого цвета не имеет ни 1 единого ребра. Каждое подмножество, соответ-е вершинам 1-го цвета распределяется в 1 из слоев. Не вошедшие ни в 1 из подмножеств отрезки,(что м. иметь место при заданном К последовательно распределяется в те слои, в которых они имеют минимальное число пресечений).

Расслоение в процессе трассировки осуществляется одновременно с прокладкой соединений многослойным ДРП с помощью различных модификаций волнового алгоритма трассировки. Рассмотрим математическую постановку задачи по слоям после предварительной трассировки. Будем считать число слоев К. Пусть G=(X,Y)– граф пересечений, в котором каждой вершинеx_i соответствует отрезок i, i=1,n, а ребру(x_ix_j)соответствует n отрезков i и j в совмещенной топологии.

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

Введем в рассмотрение матрицу Y=[y_ij]_n*k 1, отр-к x_i помещен в слой j

y_ij= 0, в противном случае

При таком подходе задача расслоения может быть сформулирована:

Требуется минимизировать (*), где c_ij – соответствующий элемент матрицы смежности c_ij=1, если i и p конфл-т между собой, 0, в прот. случае

На элементы i и j наложены ограничения:

(любой отрезок может быть помещен в 1 из слоев)

Данная задача является квадратичной задачей целочисленного программирования с булевыми переменными (y_ij,y_pj) Рассмотрим приближенный алгоритм ее решения.

Алгоритм расслоении МПП

1. В соответствие с результатами предварительной трассировки строится граф конфликтов отрезков в размещенной топологии схемы.

2. Из графа конфликтов последовательно удаляется вершины, имеющие локальную степень(число ребер, инцидентных вершине)<K. Удаление вершин здесь и далее осуществляется вместе с инцидентными им ребрами. Формируется список таких вершин. Очевидно, что отрезки, соот-ие таким вершинам может быть реализованы в слоях К без пересечений.

3. Формируется список S1 отрезков, распределенных в 1-й слой. С этой целью в графе G1=(X1,V1), гдеX1=X\S; V1=V\Vs, гдеVs – множество ребер, инцидентных вершинам множества S. В этом графе находится максимальное число несмежных между собой вершин. При этом используется приближенная процедура. Из графа G1 последовательно удаляется вершины с максимальными локальными степенями до получения графа без ребер. Множество оставшихся при этом вершин графа включается в список S1. Очевидно, что соответствующие этому списку отрезки между собой не конфликтуют и могут быть расположены в 1-м слое без пересечений

4. Далее из графа G1, из которого исключены вершины списка S1 последовательно удаляются и заносятся в список S вершины, имеющие локальную степень <(K-1). Отрезки, соответ-ие этим вершинам всегда м.б. расположены в (К-1) слой (кроме 1-го) без пересечений. Получаем граф G2=(X2,V2) X2=X\(SUS1); V2=\(VsUVs1)

5. Аналогично формируются S1S2,S3,..,Sk. При этом м. остаться некоторое множество отрезков S*, которое нельзя реализовать без пересечений в 1-м слое.

6. Из списка S последовательно в порядке, обратно порядку включения в список выбирается очередной отрезок и включается в тот слой, в который он не имеет пересечений. Так слой найдется, что следует из процедуры формирования списка S.

7. Из списка S* последовательно выбирается очередной отрезок и распределяется в тот слой, где имеет минимальной число n. Если слоев несколько, то отрезок распределяется в слой с меньшим общим числом отрезков.