Содержание к диссертации
Введение
1. Критерии качества и алгоритмы размещения компонентов электронных схем 10
1.1. Суммарная длина соединений 10
1.2. Равномерность заполнения монтажного пространства 21
1.3. Алгоритмы размещения 27
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» 91
3.4. Выводы 97
4. Реализация результатов работы в САПР «TopoR» 98
4.1. САПР «TopoR» 98
4.2. Сравнение со средствами автоматического размещения компонентов в САПР «Allegro» 101
4.3. Выводы 105
Заключение 107
Список литературы
- Равномерность заполнения монтажного пространства
- Размещение компонентов с использованием задачи о кратчайшем покрытии
- Определение минимальной ширины канала между парой компонентов при топологической трассировке
- Динамическое построение деревьев Штейнера в САПР «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, ж), оценивается по общепринятым критериям как наихудшее.
Также следует отметить, что во всех рассмотренных вариантах полные графы непланарны (это всегда соблюдается при п 4), что указывает на наличие пересечений, которых не должно быть в действительности.
Из представленного материала следует, что оценка качества размещения по минимуму суммарной длины соединений, подсчитанной для всех возможных вариантов соединений в цепях, или по минимуму суммы полупериметров охватывающих цепи прямоугольников не дает представления о реальной длине кратчайших связывающих деревьев. Кроме того, использование этих оценок как критериев оптимальности неизбежно приводит к «скучиванию» многозвенных цепей (как на рисунках 1.2, би 1.2, в) или к их реализации в виде «звезды» (рисунок 1.2, а). Все это способствует образованию областей, перенасыщенных соединениями, изломанных траекторий трасс, и в конечном итоге блокирует прокладку других соединений элементов тех же групп.
Кроме того, отметим, что для многозвенных цепей не только суммарная длина ребер мультиграфа, но и даже суммарная длина кратчайших связывающих деревьев не является достаточно полной характеристикой, поскольку не несет информации о топологии самого дерева (степенях вершин, количестве ветвей).
Зачастую для устранения количественной избыточности мультиграфа в выражении для определения длины соединений для каждой из цепей используются весовые коэффициенты, равные 2/rij. Коэффициент 2/rij получается как отношение числа (п{ —1) ребер любого дерева, построенного на п{ вершинах, к числу yijirij -1)/2 ребер полного графа и отражает вероятность появления любого ребра полного графа в связывающем дереве. Введение подобных весовых коэффициентов позволяет в отдельных случаях получить на этапе размещения меньшую суммарную длину кратчайших связывающих деревьев. Однако вероятностный характер указанных коэффициентов, отражающих только количественную сторону избыточности мультиграфа, никак не учитывающих сторону качественную, т.е. конкретный состав цепей.
Проиллюстрируем вышеизложенное примером. Пусть в двух рядах требуется разместить четыре элемента, по два в ряду, структура связности которых с внешними контактными площадками приведена на рисунке 1.3, а. Вариант оптимального размещения приведен на рисунке 1.3, б. На рисунке 1.3, в приведено размещение, полученное на основе мультиграфа, и введение весовых коэффициентов не повлияет на результат размещения. Размещение на рисунке 1.3, в характеризуется большей длиной кратчайших связывающих деревьев, более сложной конфигурацией трасс и большим числом потенциальных пересечений трасс. a)
Альтернативный подход к устранению избыточности модели электрической схемы - представление цепей не полными подграфами, а деревьями. Однако сложность задачи заключается в обосновании объективного критерия выбора совокупности конкретных деревьев.
Очевидно, что и для сравнительно небольших схем число слишком велико и исключает возможность построения модели путем прямого перебора.
Пусть для каждой цепи определены связывающие деревья. Множество ребер графа модели схемы является объединением ребер этих деревьев. В [53] предлагается выбрать те конфигурации деревьев, которые в объединении дадут граф с минимальным числом ребер. Предложен также алгоритм решения задачи, основанный на составления некоторого логического уравнения, над которым выполняются логические операции конъюнкции и поглощения. Совокупность ребер искомого графа задает терм с минимальным числом переменных в результирующем выражении. Следует, однако, отметить, что уже при п 20(п-число компонентов схемы) указанный алгоритм приводит к слишком громоздким вычислениям и не может быть применен на практике.
Авторы алгоритма, обосновывая предлагаемый подход, говорят о «требовании близкого размещения компонентов, соединенных большим количеством проводников», однако это требование является безусловным лишь для схем с однозвенными цепями.
На рисунке 1.4 приведено размещение элементов некоторой схемы и задана последовательность соединений элементов в цепях. Каждое звено любой из цепей соединяет элементы, расположенные в соседних позициях, следовательно, длина любой цепи минимальна. Кроме того, схема, приведенная на рисунке 1.4, планарна, т.е. отсутствуют пересечения трасс. При этом элементы 4 и 13, соединенные наибольшим количеством общих цепей (четыре), находятся на максимальном расстоянии друг от друга. Ясно, что попытка близкого размещения сильно связанных элементов в подобных случаях приведет либо к увеличению числа пересечений трасс, либо к увеличению суммарной длины соединений.
Размещение компонентов с использованием задачи о кратчайшем покрытии
Несмотря на важность проблемы размещения компонентов и обилие публикаций по теме, до настоящего времени отсутствуют эффективные алгоритмы, позволяющие получать качественные решения даже для упрощенных вариантов постановки задачи.
Низкое качество получаемых автоматически решений приводит к тому, что, несмотря на наличие программных средств автоматического размещения, они не используются в практике проектирования. Разработчики предпочитают размещать компоненты вручную, несмотря на высокую сложность и трудоемкость задачи. Чем же принципиально отличается «ручной подход» от автоматического? Из рекомендаций опытного конструктора: «Если посмотреть схему, то видно, что она состоит из отдельных узлов, и, естественно, детали, входящие в них, должны быть рядом. Подсвечиваете их на схеме и на плате собираете их в кучку. Потом стараетесь для этой кучки найти оптимальное расположение деталей, и после этого трассируете только этот кусок. Также поступаете и с остальными. Затем компонуете куски между собой и трассируете связи между каскадами, не трогая самих узлов. Уточняете расположение деталей внутри узлов для достижения оптимальности связей."
Из вышесказанного следует, что ручной подход предполагает выделение групп сильно связанных компонентов, нахождение вариантов компактного размещения компонентов внутри группы (формирование блока), и затем размещение блоков. Подобный подход позволяет снизить размерность общей задачи, а также существенно уменьшить площадь, занимаемую компонентами, входящими в блок, по сравнению с размещением их по отдельности, тем самым освободить площадь для соединений между блоками. Оригинальный алгоритм выделения кластеров (групп сильно связанных вершин) в графе предложен в работе [95]. Однако при наличии в схеме цепей, соединяющих более двух компонентов, графовая модель схемы в общем случае не является адекватной [29], что не позволяет использовать алгоритм [95] для выделения функциональных узлов на схеме, за исключением специальных случаев (например, когда схема не содержит многоконтактных цепей или когда в схеме все компоненты - двухполюсники).
Наиболее сложный случай для кластеризации представляют схемы с большими содержанием двухполюсников, когда доля непосредственных соединений многополюсников мала, и сигнал от контакта одного многополюсника до контакта другого проходит через ряд двухполюсников. В этом случае традиционные формальные критерии выделения подсхем (максимум количества внутренних электрических цепей подсхемы, минимум количества внешних электрических цепей, максимум разности количества внутренних и внепших электрических цепей и т.д.) не работают, поскольку все претенденты на добавление в подсхему будут иметь одинаковое значение указанных критериев. Более того, двухполюсники в этом случае маскируют возможную сильную связность многополюсников (рисунок 2.1).
Если двухполюсники участвуют в многоконтактных цепях, то силовое размещение может «уводить» их от оптимальной позиции. Так на рисунке 2.2 показано оптимальное положение двухполюсника, а на рисунке 2.3 - положение после действия силового алгоритма. Коррекция при разбиении по квадрантам будет отодвигать двухполюсник еще правее.
Положение двухполюсника после действия силового алгоритма Если определить, какие двухполюсники принадлежат окрестностям многополюсника, и создать виртуальный компонент, соответствующий подсхеме, содержащей многополюсник и его окрестность, либо представить подсхему из двухполюсников как «виртуальный многополюсник», то в модифицированной схеме сократится диаметр, и многополюсники, в том числе, «виртуальные» будут связаны непосредственно, что существенно повысит эффективность использования известных критериев и алгоритмов.
Очевидно, что к окрестности некоторого многополюсника можно отнести малоконтактные компоненты, входящие в цепи, инцидентные многополюснику. Однако эти же цепи, или их часть могут быть инцидентны другому многополюснику, и в этом случае принадлежность конкретного, например, резистора окрестности некоторой микросхемы становится неочевидной.
Воспользуемся используемым в САПР «TopoR» понятием «сигнальный кластер». Сигнальный кластер - это подсхема, содержащая все возможные пути от выбранного источника к приемникам, за исключением путей, включающих фрагменты силовых цепей. В сигнальный кластер попадают все цепи (кроме силовых), связанные с цепью источника через пассивные компоненты.
Распространение волны в некотором направлении заканчивается, если инцидентная двухполюснику цепь является силовой или очередной контакт цепи принадлежит многополюснику (такой контакт не включается во фронт).
В результате будет сформирована подсхема, содержащая двухполюсники, представляющая собой одну компоненту связности, и подключенная к одному или нескольким многополюсникам.
Эту подсхему следует разбить на части таким образом, чтобы число общих для частей цепей было меньше, чем число внешних цепей подсхемы.
Окрестности каждого из многополюсников будем наращивать последовательно.
Некоторые правила: многополюсник, имеющий только одну многоконтактную общую цепь с выделенной подсхемой, можно исключить из рассмотрения; одноконтактный компонент (например, контрольная точка), по-видимому, должен быть расположен в непосредственной близости от эквипотенциального контакта многополюсника, в том числе в многоконтактных цепях, то есть входить в окрестность многополюсника; двухполюсник, оба контакта которого соединены с многополюсником (или окрестностью многополюсника), принадлежит окрестности многополюсника; двухполюсник, один контакт которого соединен с многополюсником (двухконтактная цепь), а другой - принадлежит силовой цепи («земля» или «питание»), очевидно может быть причислен к окрестности многополюсника.
Отдельная проблема - размещение развязывающих конденсаторов. Зачастую это большое количество одинаковых элементов, принадлежащих паре цепей («земля» и «питание»), так что автоматическое размещение их на основе информации о связности с минимизацией суммарной длины проводников приводит к тому, что все они компактно располагаются в минимальном прямоугольнике в какой-либо части платы. В то же время, зная число таких конденсаторов, число микросхем и число контактов питания в каждой из микросхем, нетрудно назначить конкретный конденсатор окрестности конкретной микросхемы и разместить его рядом с конкретным контактом питания.
Определение минимальной ширины канала между парой компонентов при топологической трассировке
Следует отметить, что для цепей земли/питания возможно назначение нескольких соседних контактов на один переход (ограничение должно задаваться пользователем). Однако это не всегда поможет. Для разрешения конфликта возможны два направления: уменьшение числа контактов-претендентов и увеличение числа доступных ячеек. Уменьшение числа контактов-претендентов Соседние контакты цепей земли/питания на каждом из внешних слоев можно объединить в кластеры и построить дерево, доставляющее связность контактов кластера. Тем самым значительно снизится число необходимых переходов (для подключения кластера достаточно разместить один переход в непосредственной близости от любого контакта кластера или пары кластеров, если они находятся на разных слоях).
Соответственно, при решении задачи о назначениях в двудольном графе каждый кластер представлен только одной вершиной, ячейка считается достижимой, если существует путь из любой вершины кластера.
Если после назначения остались свободные ячейки, их можно использовать для уменьшения размеров кластеров (подключить контакт, лучше диаметральный по отношению к уже имеющемуся переходу, и удалить циклические ребра таким образом, чтобы два новых кластера имели минимальный диаметр или примерно равное число контактов). По-видимому, важнее уменьшать размеры кластеров контактов BGA, чем двухполюсников на противоположной стороне. Если число неподключенных контактов превышает число свободных ячеек, следует выдать соответствующее сообщение, в котором указать координаты заблокированных контактов. Увеличение числа доступных ячеек
В ряде случаев межслойных переход не может быть размещен без нарушений в центре ячейки, однако нарушения могут быть устранены при некотором его смещении. (Устранять нарушения можно и при перемещении двухполюсников, однако рассмотрение этого выходит за рамки настоящей работы.)
Кроме того, можно пожертвовать строгостью ограничений на зазоры между объектами одной цепи, то есть разрешить уменьшение (вплоть до 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-градусными дугами окружностей.
Геометрический анализ. Перекрыт ли центр? Дальнейшее решение зависит от того, окажется ли допустимым поместить центр ПО в центре прямоугольника. Ответ на этот вопрос, разумеется, зависит не только от положения помех, но и от радиусов Rl, R2 и длин сторон прямоугольника (BGA-ячейки). Если центр перекрыт «круглыми помехами» (т.е. круги, полученные раздуванием до R1+R2, содержат его внутри), то вся внутренняя область BGA-ячейки перекрыта, и никакого ПО в ней разместить нельзя.
Пусть это не так. Тогда «круглые» помехи не закрывают центр, и нам достаточно проверить, не закрывается ли он какой-то из «угловых» помех, то есть сравнить координаты центра с координатами границ компонентов.
Центр ж перекрыт «угловыми» помехами, если никакая из таких помех не содержит центра. Для выяснения этого факта достаточно сравнить координаты центра с уравнениями трех линий, задающих угловую помеху - горизонтальной, вертикальной и дуговой.
Динамическое построение деревьев Штейнера в САПР «TopoR»
Одна группа контактов расположена горизонтально, другая вертикально. Для этого случая правильная (бесклинчевая) схема расположения переходов очевидна: каждый переход располагается в «своей» горизонтали и в «своей» вертикали. Буквальная реализация этой схемы в САПР «TopoR» имеет вид, представленный на рисунке 3.3. -Перпендикулярные шины, шаг 1 Здесь все проводники слоя Тор (светло-серый цвет на рис. 3.3) горизонтальные, а все проводники слоя Bottom (темно-серый цвет на рис. 3.3) вертикальные. Если бы переходные отверстия имели размеры, не превосходящие ширины проводников, то эта реализация не содержала бы нарушений заданных правил (тонкие черные линии на рисунке 3.3). Однако размер переходного отверстия существенно больше, поэтому для устранения нарушений в САПР «TopoR» применяется автораздвижка. Результат без нарушений представлен на рисунке 3.4.
Решение для этого случая не зависит от расстояний между контактами - в частности, на рисунке 3.5 соседние контакты группы Y находятся в полтора раза дальше друг от друга, чем контакты X. Направим все проводники из группы X под углом (примерно 45) вправо-вверх, а все проводники из контактов группы Y - под таким же углом влево-вверх (рисунок 3.5). Точки пересечения пар проводников, принадлежащих одной цепи, являются точками топологической расстановки переходов.
. Параллельные шины, вариант 2 Здесь рассмотрен вариант, когда расстояние между группами контактов X и Y по горизонтали недостаточно для реализации предыдущего случая, в результате проводники слоя Тор и проводники слоя Bottom должны выходить из своих контактов в одном и том же направлении (для определенности, вправо). под другом, при этом рассматриваем ту же подстановку I 1. Иначе J Z 7 о 1 4 говоря, контакты шины X сверху вниз идут в порядке XI, Х2, ХЗ, Х4, Х5, Х6, Х7, а контакты шины Y - в порядке Y6, Y3, Y2, Y7, Yl, Y5, Y4. При этом чередование X и Y может быть достаточно произвольным, а если пара контактов из разных групп имеет одинаковую координату, считаем, что контакт на вернем слое предшествует контакту на нижнем. Дальше строятся вертикальные «уровневые» линии, между которыми порядок соседних контактов может либо сохраниться, либо поменяться местами (это чем-то сродни алгоритму «пузырьковой» сортировки). Если на очередной линии уровня какая-либо из цепей замыкается и заканчивается, то на следующем вертикальном уровне оставшиеся цепи могут быть сближены.
Отметим, что такая схема разводки не гарантирует оптимальности, но заведомо не содержит «лишних» переходов и петель по сравнению с оптимальной схемой. Реализация схемы в САПР «TopoR» и вариант после подвижки показаны на рисунках 3.9 и 3.10 соответственно.
Рисунок 3.10 - Параллельные шины (2), результат. Отметим, что «физическое» расположение переходов на рисунке 3.10 достаточно сильно отличается от их «схематического» расположения, показанного на рисунках 3.8 и 3.9.
Попарное соединение контактов двух групп, расположенных на одном слое Постановка задачи: соединить (попарно) контакты двух групп (X и Y), находящихся на одном слое Тор. На каждой цепи разрешено не более двух переходов (с Тор на Bottom и обратно). Расстановка переходов не должна создавать «клинчей» и иных трудноисправляемых ошибок.
Предлагаемое решение: разместить непосредственно перед контактами одной из групп все N переходов и тем самым свести задачу к предыдущей. Для оптимальной прокладки рассмотреть и сравнить два варианта - когда такой «комплект переходов» стоит около группы контактов X, и когда он стоит около группы контактов Y.
В САПР «TopoR» на этапе оптимизации положение межслойных переходов на проводнике не фиксируется. Отсутствие фиксации положения перехода и фиксации слоя проводника между парой переходов или между переходом и сквозным контактом позволяет лучше использовать ресурсы монтажного пространства, однако в ряде случаев приводит к появлению «узких» мест из-за недоучета реальных размеров межслойных переходов. В области BGA-компонентов как раз крайне нежелательно удлинять участок проводника от контакта до перехода, поскольку это может заблокировать подход к соседним контактам. При трассировке таких областей в САПР «TopoR» используется специальная процедура, расставляющая в области BGA-компонента межслойные переходы и назначающая на них цепи контактов BGA-компонента и двухполюсников, расположенных в области BGA-компонента.
Маленькими кружками обозначены вершины разбиения, представляющие контакты компонента BGA, большими кружками - вершины, представляющие ячейки для межслойных переходов. Ячейка - область между четырьмя соседними контактами. С каждым задействованным контактом (кроме контактов, расположенных по периметру) связана своя ячейка. Если кружок ячейки не закрашен, это означает, что ячейка несвязанная. Стрелками показано первоначальное назначение ячеек контактам при условии, что все ячейки доступны.
Таким образом, до назначения ячейка является «свободной» и может быть по отношению к контакту «своя», «чужая» и «несвязанная». После назначения ячейка оказывается «назначенной», и по отношению к контакту может быть «своей цепи» и «чужой цепи».
При трассировке области BGA в «ячейках» между контактами расставляются межслойные переходы, и каждому сигналу (каждому задействованному контакту) назначается свой межслойный переход. Обычно ячеек даже больше, чем необходимо. Однако если переходы сквозные и в области BGA на противоположной стороне платы расположены двухполюсники (конденсаторы, резисторы, индуктивности), контакты которых препятствуют размещению переходов в ячейках, то может оказаться, что свободных ячеек меньше, чем необходимо для разводки всех цепей (рисунке 3.12).