Содержание к диссертации
Введение
1. Критерии качества и алгоритмы размещения компонентов электронных схем 10
1.1. Суммарная длина соединений 10
1.2. Равномерность заполнения монтажного пространства 21
1.3. Алгоритмы размещения
1.3.1. Типовой конструктивный алгоритм размещения 28
1.3.2. Силовое размещение 30
1.3.3. Метод дихотомического деления 36
1.3.4. Алгоритм Гото 38
1.3.5 Размещение компонентов с использованием задачи о кратчайшем покрытии 40
1.3.6 Плотная упаковка компонентов 44
1.4. Выводы 48
2. Локальная оптимизация размещения компонентов 49
2.1. Определение окрестностей многополюсника 49
2.2. Определение минимальной ширины канала между парой компонентов при топологической трассировке 56
2.3. Компактное размещение двухполюсников 61
2.4. Выводы 70
3. Локальная оптимизация положения элементов топологии 71
3.1. Определение относительного расположения переходных отверстий на группе проводников, пересекающихся в паре слоев 71
3.2. Назначение межслойных переходов в области BGA-компонента
3.3. Динамическое построение деревьев Штейнера в САПР «TopoR»
3.4. Выводы
101 105 107 108
1 4. Реализация результатов работы в САПР «TopoR»
4.1. САПР «TopoR»
4.2. Сравнение со средствами автоматического размещения компонентов в САПР «Allegro»
4.3. Выводы
Заключение
Список литературы
- Равномерность заполнения монтажного пространства
- Размещение компонентов с использованием задачи о кратчайшем покрытии
- Определение минимальной ширины канала между парой компонентов при топологической трассировке
- Динамическое построение деревьев Штейнера в САПР «TopoR»
Равномерность заполнения монтажного пространства
Деревья а), б) и в) неизоморфны, однако поскольку вершины имеют идентичное расположение, то полные подграфы, построенные на этих вершинах, имеют одинаковую суммарную длину ребер, равную 78 дискретам (10 ребер единичной длины, 14 ребер длины 2, 8 ребер длины 3 и 4 ребра длины 4). Равны также и полупериметры охватывающих прямоугольников: 4 дискрета.
Деревья г), д) и е) изоморфны, однако полные подграфы имеют различную длину: г) – 100 дискрет, д) – 88 дискрет, е) – 98 дискрет. Полупериметры охватывающих прямоугольников равны соответственно 6, 5 и 7 дискрет.
Дерево ж) изоморфно дереву б), однако полный граф, построенный на вершинах дерева ж), имеет длину 120 дискрет (в 1,67 раз больше) и полупериметр охватывающего прямоугольника равен 8 дискретам, т.е. в два раза больше.
Дерево з) имеет длину 14 дискрет – в 1,75 раз больше, чем дерево ж), но полупериметры охватывающих прямоугольников здесь равны (по 8 дискрет), а полный граф, построенный на вершинах дерева з) имеет даже меньшую длину – 116 дискрет.
Рассмотренные примеры показывают, что размещение, позволяющее получить при той же длине наиболее рациональную конфигурацию многозвенных трасс (рисунок 1.2, ж), оценивается по общепринятым критериям как наихудшее.
Также следует отметить, что во всех рассмотренных вариантах полные графы непланарны (это всегда соблюдается при n 4), что указывает на наличие пересечений, которых не должно быть в действительности.
Из представленного материала следует, что оценка качества размещения по минимуму суммарной длины соединений, подсчитанной для всех возможных вариантов соединений в цепях, или по минимуму суммы полупериметров охватывающих цепи прямоугольников не дает представления о реальной длине кратчайших связывающих деревьев. Кроме того, использование этих оценок как критериев оптимальности неизбежно приводит к «скучиванию» многозвенных цепей (как на рисунках 1.2, б и 1.2, в) или к их реализации в виде «звезды» (рисунок 1.2, а). Все это способствует образованию областей, перенасыщенных соединениями, изломанных траекторий трасс, и в конечном итоге блокирует прокладку других соединений элементов тех же групп.
Кроме того, отметим, что для многозвенных цепей не только суммарная длина ребер мультиграфа, но и даже суммарная длина кратчайших связывающих деревьев не является достаточно полной характеристикой, поскольку не несет информации о топологии самого дерева (степенях вершин, количестве ветвей).
Зачастую для устранения количественной избыточности мультиграфа в выражении для определения длины соединений для каждой из цепей используются весовые коэффициенты, равные 2/ni. Коэффициент 2/ni получается как отношение числа (ni –1) ребер любого дерева, построенного на ni вершинах, к числу ni(ni –1)/2 ребер полного графа и отражает вероятность появления любого ребра полного графа в связывающем дереве. Введение подобных весовых коэффициентов позволяет в отдельных случаях получить на этапе размещения меньшую суммарную длину кратчайших связывающих деревьев. Однако вероятностный характер указанных коэффициентов, отражающих только количественную сторону избыточности мультиграфа, никак не учитывающих сторону качественную, т.е. конкретный состав цепей.
Проиллюстрируем вышеизложенное примером. Пусть в двух рядах требуется разместить четыре элемента, по два в ряду, структура связности которых с внешними контактными площадками приведена на рисунке 1.3, а. Вариант оптимального размещения приведен на рисунке 1.3, б. На рисунке 1.3, в приведено размещение, полученное на основе мультиграфа, и введение весовых коэффициентов не повлияет на результат размещения. Размещение на рисунке 1.3, в характеризуется большей длиной кратчайших связывающих деревьев, более сложной конфигурацией трасс и большим числом потенциальных пересечений трасс.
Альтернативный подход к устранению избыточности модели электрической схемы – представление цепей не полными подграфами, а деревьями. Однако сложность задачи заключается в обосновании объективного критерия выбора совокупности конкретных деревьев.
Известно, что число различных деревьев, которые можно построить на n вершинах [28], равно nn-2. Поэтому число возможных вариантов моделей схемы составит: Q=Y\n i=\ щ-2 (1.11) где m – число цепей. Очевидно, что и для сравнительно небольших схем число Q слишком велико и исключает возможность построения модели путем прямого перебора.
Пусть для каждой цепи определены связывающие деревья. Множество ребер графа модели схемы является объединением ребер этих деревьев. В [53] предлагается выбрать те конфигурации деревьев, которые в объединении дадут граф с минимальным числом ребер. Предложен также алгоритм решения задачи, основанный на составления некоторого логического уравнения, над которым выполняются логические операции конъюнкции и поглощения. Совокупность ребер искомого графа задает терм с минимальным числом переменных в результирующем выражении. Следует, однако, отметить, что уже при n 20 (n – число компонентов схемы) указанный алгоритм приводит к слишком громоздким вычислениям и не может быть применен на практике.
Авторы алгоритма, обосновывая предлагаемый подход, говорят о «требовании близкого размещения компонентов, соединенных большим количеством проводников», однако это требование является безусловным лишь для схем с однозвенными цепями.
На рисунке 1.4 приведено размещение элементов некоторой схемы и задана последовательность соединений элементов в цепях. Каждое звено любой из цепей соединяет элементы, расположенные в соседних позициях, следовательно, длина любой цепи минимальна. Кроме того, схема, приведенная на рисунке 1.4, планарна, т.е. отсутствуют пересечения трасс. При этом элементы 4 и 13, соединенные наибольшим количеством общих цепей (четыре), находятся на максимальном расстоянии друг от друга. Ясно, что попытка близкого размещения сильно связанных элементов в подобных случаях приведет либо к увеличению числа пересечений трасс, либо к увеличению суммарной длины соединений.
Размещение компонентов с использованием задачи о кратчайшем покрытии
Минимальное расстояние между смежными контактами микросхемы и двухполюсника зависит от расстояния между соседними контактами микросхемы (шаг), толщины проводников и зазоров между ними, а также размеров контактов микросхемы и двухполюсников и количества двухполюсников [12].
В некоторых случаях целесообразно расположение двухполюсников в несколько ярусов. В зависимости от соотношений размеров контактных площадок микросхемы и двухполюсников, а также от числа двухполюсников подобное расположение может оказаться экономичнее в части занимаемой площади и суммарной длины проводников (рисунок 2.9).
Отметим, что если на второй контакт двухполюсника назначена цепь, выходящая на опорные слои, то такие двухполюсники целесообразно ставить в первые ряды, поскольку в этом случае обеспечивается сокращение суммарной длины проводников (рисунок 2.10).
Дан многоконтактный прямоугольный компонент, контакты одной из сторон которого (конкретно верхней) расположены горизонтально на равных расстояниях друг от друга. Этот ряд контактов мы будем называть «первым рядом контактов». Над ним необходимо также горизонтально расположить нижние контакты двухполюсников, причем между каждыми двумя соседними контактами должен быть оставлен необходимый зазор для прокладки проводников, ведущих к другим (более верхним) рядам контактов. Эти двухполюсники и проводники мы будем называть «вторым рядом контактов».
Требуется расположить первый и второй ряды на минимальном расстоянии, позволяющем произвести «поконтактную» разводку проводников между ними с учетом заданной ширины проводника d\, заданной ширины двухполюсника d и минимального зазора d2. После вычисления этого расстояния необходимо рассчитать общую площадь, занятую всем этим участком схемы - от первого ряда до верхней границы последнего ряда. Высота каждого двухполюсника равна Я, а расстояние по вертикали между соседними двухполюсниками считать равным d2.
Вычисления для стандартной конфигурации: Стандартной будем называть такую конфигурацию, в которой 1. Середина второго ряда имеет общую вертикальную ось симметрии с серединой первого ряда (середины рядов находятся точно друг под другом). 2. Зазоры между соседними контактами первого ряда минимальны, то есть равны d2; ширина проводников тоже минимальна и равна d\. 3. Зазоры между проводниками второго ряда, а также между проводниками и контактами двухполюсников, – такие же. 4. Второй ряд содержит N двухполюсников и (m–1)(N–1) проводников, а первый ряд содержит столько же (т.е. N+(m–1)(N–1)) контактов и выходящих из них одинаковых проводников. Тогда общая длина первого ряда равна W1=(d1+d2)(N+(m–1)(N–1)) – d2, (2.19) а длина второго равна W2=d3N + d1(m–1)(N–1) + d2(N+(m–1)(N–1) –1). (2.20) При этом расстояние между левыми контактами соседних двухполюсников должно быть таким, чтобы там поместились один двухполюсник, (m–1) проводников и m зазоров. Иначе говоря, B= d3 + md2 + (m–1)d1. (2.21) Координату A первой (самой левой) точки второго ряда мы можем найти из такого соотношения: она левее первой точки первого ряда (0,0) на половину разности длин рядов, то есть на величину (d3–d1)N/2. Таким образом, A= – (d3 – d1)N/2. (2.22)
Отрезок OLk назовем критичным, если для данного значения k длина этого отрезка в точности равна той минимальной длине, на которой можно поместить нужное число сечений проводников и зазоров между ними. Если критичных отрезков нет, мы можем уменьшить h до того значения, при котором они появятся. Поэтому будем считать, что критичный отрезок существует и идет от точки O к точке Lj.
На рисунке 2.11 показан критичный отрезок OL2, ортогонально пересекающий три проводника и три зазора. Рисунок 2.11. – Три ряда двухполюсников и критичный отрезок Лемма. Критичный отрезок может идти только к такой точке, которая является левым контактом двухполюсника.
Доказательство. Предположим, что критичным является другой отрезок OT, пересекающий сколько-то отрезков и зазоров между ними. По предположению, OT имеет минимально возможную длину. Найдем ближайший справа от T левый конец двухполюсника (на рисунке – L2). Отрезок TL2 также пересекает сколько-то отрезков и зазоров и также имеет минимально возможную длину. Но тогда отрезок OL2, пересекающий все те же отрезки и зазоры, что OT и TL2 вместе взятые, имеет длину, меньшую, чем ломаная OTL2, то есть меньше критичной длины! Противоречие.
Согласно лемме, искать концы критичных отрезков можно только среди левых концов контактов двухполюсников. Их координаты образуют арифметическую прогрессию, что позволяет упростить и постановку, и решение задачи, сведя ее к решенной в предыдущем разделе [12] задаче о минимуме расстояния между парой многоконтактных компонентов. Условие допустимости разводки (OnlineDRC) с учетом леммы 1: \OLk (dl+ d2) m (k–\) для любого (2.23) (до k-й левой точки должны проходить по m проводников к каждой из (к–1) предыдущих нижних границ двухполюсников и к следующим рядам).
Определение минимальной ширины канала между парой компонентов при топологической трассировке
Если число неподключенных контактов превышает число свободных ячеек, следует выдать соответствующее сообщение, в котором указать координаты заблокированных контактов. Увеличение числа доступных ячеек
В ряде случаев межслойных переход не может быть размещен без нарушений в центре ячейки, однако нарушения могут быть устранены при некотором его смещении. (Устранять нарушения можно и при перемещении двухполюсников, однако рассмотрение этого выходит за рамки настоящей работы.)
Кроме того, можно пожертвовать строгостью ограничений на зазоры между объектами одной цепи, то есть разрешить уменьшение (вплоть до 0) зазора между переходом и контактом, принадлежащим той же цепи. Если после решения задачи о назначениях остались свободные ячейки, их можно использовать для уменьшения числа мест с уменьшенным зазором.
Поиск места для размещения переходного отверстия Имеется прямоугольная ячейка BGA-компонента, внутри которой должно быть размещено переходное отверстие (ПО). Если на другом слое платы не размещены никакие компоненты, то ячейку гарантированно можно ставить в центре ячейки. (Это связано с тем, что центр прямоугольника – точка, одинаково удаленная от всех его вершин.) Однако наличие компонентов на других слоях может этому помешать. В связи с этим мы хотели бы определить местоположение центра переходного отверстия, не создающее помех для других компонентов. Анализ задачи. Классификация случаев и сведение к одному. В зависимости от расположения компонентов на другом слое мы будем различать три случая. Первый случай (рисунок 3.13, а – четыре «обобщенные помехи») соответствует ситуации, когда на другом слое находятся до четырех различных компонентов, каждый из которых закрывает не более одного узла данной BGA-ячейки. Одна или несколько из таких помех могут отсутствовать, – решение задачи для этого частного случая не будет отличаться от общего решения.
Второй случай (рисунок 3.13, б - три «обобщенные помехи») - ситуация, когда на другом слое находится до трех различных компонентов, причем ровно один из них перекрывает два соседних узла BGA-ячейки. На рисунке такими двумя узлами являются нижние, но, разумеется, возможны и повороты этого рисунка на 90 или 180.
Третий случай (рисунок 3.13, в - две «обобщенные помехи») - ситуация, когда два компонента другого слоя перекрывают по два соседних узла BGA. На рисунке такими парами узлов являются пара нижних и пара верхних, но возможен и поворот этого рисунка на 90. Отметим, что нижняя пунктирная линия на рисунке создает «помеху снизу», в то время как верхняя - «помеху сверху».
В дальнейшем мы будем рассматривать только первый случай, сводя к нему остальные следующим несложным приемом: на рисунке 3.13, б отметим середину нижней помехи, и от этой точки проведем границу вниз. Тем самым «прямая» помеха окажется разбитой на две «угловых». Аналогично на рисунке 3.13, в так же поступим с обеими горизонтальными помехами.
Геометрический анализ. «Надувание» помех и стягивание окружности в точку На рисунке 3.14 показаны два изображения одной и той же ситуации. На левом изображении – две окружности, одна из которых (вокруг жирной точки) имеет радиус R1, равный минимальному зазору, а вторая (вокруг маленькой точки) изображает искомое переходное отверстие радиуса R2. Центр ПО можно поместить в данной маленькой точке, если две этих окружности не пересекаются.
На правом изображении одновременно вторая окружность «стянута» в точку (ее радиус уменьшился до нуля), а первая – «надута» до радиуса R1+R2. Центр ПО можно поместить в данной маленькой точке, если эта точка лежит вне проведенной окружности. Процедуру «надувания» можно одновременно провести для всех четырех вершин прямоугольной ячейки.
Процедура «надувания» для угловых границ помех очень похожа и в чем-то даже более проста: прямые, соответствующие «помехе слева», в результате надувания должны быть сдвинуты правее на расстояние R2, прямые для «помехи справа» сдвигаются на R2 левее, аналогичные сдвиги делаются для помех сверху и снизу. Углы (точки) при этом становятся 90-градусными дугами окружностей.
Геометрический анализ. Перекрыт ли центр? Дальнейшее решение зависит от того, окажется ли допустимым поместить центр ПО в центре прямоугольника. Ответ на этот вопрос, разумеется, зависит не только от положения помех, но и от радиусов R1, R2 и длин сторон прямоугольника (BGA-ячейки). Если центр перекрыт «круглыми помехами» (т.е. круги, полученные раздуванием до R1+R2, содержат его внутри), то вся внутренняя область BGA-ячейки перекрыта, и никакого ПО в ней разместить нельзя.
Пусть это не так. Тогда «круглые» помехи не закрывают центр, и нам достаточно проверить, не закрывается ли он какой-то из «угловых» помех, то есть сравнить координаты центра с координатами границ компонентов.
Центр не перекрыт «угловыми» помехами, если никакая из таких помех не содержит центра. Для выяснения этого факта достаточно сравнить координаты центра с уравнениями трех линий, задающих угловую помеху – горизонтальной, вертикальной и дуговой. Решение. Общий подход. Как уже было объяснено выше, мы умеем сводить случаи 2 и 3 к случаю 1, когда около каждого угла рассматривается угловая помеха. После «надувания» такие помехи становятся скругленными прямоугольниками.
Решать задачу мы будем следующим способом: если центр не перекрыт, то именно его и выберем в качестве центральной точки ПО (ЦПО); если же центр перекрыт, то будем решать задачу раздельно для каждого из четырех «квадрантов» BGA-ячейки (один квадрант – это прямоугольная область с углом в центре ячейки, внутри которой находится ровно одна вершина BGA-ячейки). В каждом квадранте найдем ближайшую к центру свободную точку. Затем из всех (четырех) найденных таким образом точек (кандидатов в ЦПО, или КЦПО) выберем ближайшую к центру; именно она и будет ЦПО. Решение для левого нижнего квадранта.
Теперь рассмотрим помеху правой верхней вершины (рисунок 3.16). У нее есть три куска – горизонтальный, дуговой, вертикальный. Если эта помеха не пересекается с квадрантом, то алгоритм поиска КЦПО может не учитывать наличия этой помехи. Рисунок 3.16 – Центр ячейки перекрыт помехой левой верхней вершины
Случай 1. Поиск КЦПО без правой верхней помехи.
Если две пунктирных помехи от правой нижней и левой верхней вершин (одна горизонтальная со скруглением, другая – вертикальная со скруглением) пересекаются, у них есть единственная точка пересечения, которая и будет на этом шаге рассматриваться как КЦПО. Если они не пересекаются, то множество точек КЦПО – либо отрезок (одной из пунктирных линий), либо сумма «отрезок+дуга».
Далее надо проверить, как множество точек КЦПО пересекается с двумя помехами левого нижнего угла (угловой и круглой). Если это множество – точка, и она закрыта хотя бы одной левой нижней помехой, то точек внутри квадранта НЕТ. Иначе данная точка остается КЦПО.
Если это множество – вертикальный отрезок, и он закрыт левой нижней помехой, то точек внутри квадранта снова НЕТ. Если такой отрезок закрыт левой нижней помехой не до самого верха, то в качестве КЦПО берется верхняя точка этого отрезка.
Динамическое построение деревьев Штейнера в САПР «TopoR»
При проектировании коммуникаций (дорог, линий электропередач, трубопроводов, соединений на печатной плате) возникает необходимость построения сети минимальной длины. В теории графов известны эффективные (полиномиальные) алгоритмы Краскала и Прима решения задачи построения минимального остовного дерева [25]. Однако в большинстве случаев введение дополнительных вершин позволяет получить сеть меньшей длины. Деревья с дополнительными вершинами называют деревьями Штейнера [42]. В отличие от задачи построения минимального остовного дерева, для задачи Штейнера (поиск деревьев Штейнера минимальной длины) не известны полиномиальные по сложности методы решения [19], [57], [61].
В дереве Штейнера все соединения должны быть отрезками, соединяющими вершины (терминальные и дополнительные). В каждой дополнительной вершине должны сходиться три отрезка, а в терминальных – не более трех. Угол между отрезками, сходящимися в одной точке, не должен быть меньше 120. Построить дерево Штейнера с выполнением перечисленных достаточных условий нетрудно, но оно не обязательно будет минимальным. Минимальное (черный цвет) и неминимальное (серый цвет) деревья Штейнера приведены на рисунке 3.17.
Если четыре терминальных вершины образуют выпуклый четырехугольник, критерий минимальности прост: пары терминальных вершин, соединенные с дополнительной вершиной, должны быть расположены напротив острых углов, образованных диагоналями четырехугольника [42]. Если диагонали ортогональны, оба дерева имеют одинаковую длину. При проектировании реальных коммуникаций необходимо учитывать наличие различного рода препятствий, что, к сожалению, ограничивает возможность использования как алгоритмов построения минимального остовного дерева (рисунок 3.18, а), так и геометрических методов построения деревьев Штейнера (рисунок 3.18, б).
Предлагается подход к построению деревьев Штейнера при наличии препятствий, основанный на динамическом перестроении сети соединений, не содержащей дополнительных вершин. Основные механизмы: создание дополнительных вершин и итерационное перемещение их в точку равновесия с использованием силового алгоритма.
Пусть получена сеть соединений, не содержащая дополнительных вершин. На реальных сетях пары терминальных вершин не всегда соединяются отрезком прямой. На пути соединения могут быть препятствия различной природы. Если соединение пары вершин содержит более одного отрезка (рисунок 3.18, б), в качестве виртуальной терминальной вершины следует использовать конец отрезка, инцидентного вершине.
Силовое размещение
Огибая элементы топологии, проводник оказывает на них «давление», как бы «выталкивая» со своего пути (рисунок 3.19, а). Это давление направлено к центру окружности и численно равно отношению уменьшения длины проводника к величине сдвига элемента в сторону давления (с необходимым коэффициентом, если стоимость длины для разных проводников различна). Точно так же проводник «тянет» элементы, к которым прикреплен концами. Одновременно с этим проводник «расталкивает» элементы топологии, между которыми он проходит (рисунок 3.19, б). Суммарная сила, приложенная к элементу (компоненту, межслойному переходу, точке ветвления проводников) всеми проводниками, определяет, в какую сторону «желает» сдвинуться элемент и как сильно.
Наличие угла, меньшего 120 (рисунки 3.20, а и 3.20, в), между парой сегментов, инцидентных одной вершине (терминальной или дополнительной), – признак локальной неоптимальности подсети. В этом случае следует добавить дополнительную вершину: пара сегментов заменяется на три сегмента, инцидентных дополнительной вершине (рисунки 3.20, б и 3.20, г). Положение дополнительных вершин оптимизируется с использованием силового алгоритма
Рассмотрим оптимизации дерева Штейнера при наличии мешающего объекта. На рисунке 3.22, а приведен пример минимального связывающего дерева для сети. Как было описано в предыдущем разделе, у верхней терминальной вершины добавляется новая нетерминальная вершина (рисунок 3.22, б). Новой вершине занять оптимальное положение силовым алгоритмом мешает терминальная вершина.
В данном случае положение терминальной вершины может продолжить оптимизироваться, если переложить один из двух огибающей путей, с другой стороны от мешающей вершины (рисунок 3.22, в). Итоговое положение показано на рисунке 3.22, г.
Рассмотрим оптимизацию сети соединений в случае, когда построению дерева Штейнера мешают другие сети. Клинчем называется ситуация, в которой путь в одной сети net1 огибает терминальную вершину другой сети net2. При этом к огибаемой вершине также построен путь [6]. Таким образом проложенный путь в сети net2 мешает проложить более короткий путь сети net1.
На рисунке 3.23, а приведен пример простого клинча в топологии печатного монтажа. Имеется цепь net1, состоящая из трех проводников, соединенных точкой ветвления (нетерминальной вершиной). Имеется один проводник цепи net2. Путь из проводников первой цепи огибает терминальную вершину второй цепи. При этом каждой из двух терминальных вершин цепи net2 инцидентен только один проводник.