Содержание к диссертации
Введение
I. Критерии качества монтажно-коммутационного проектирования РЭС 11
1.1. Размещение для получения минимальной длины соединений 12
1.2. Размещение для получения равномерного заполнения монтажного пространства 24
1.3. Частные оценки размещения 32
1.4. Формирование эффективного критерия качества размещения 37
Выводы 47
II. Оптимизация модели электрической схемы 48
2.1. Минимизация числа ребер графа модели схемы 49
2.2. Построение модели схемы на основе линейного размещения независимых цепей 59
2.3. Построение модели схемы на основе решения задачи о кратчайшем покрытии 69
Выводы 75
III. Расчет электромагнитных помех в печатных платах 76
3.1. Допущения, принятые при расчете электромагнитных помех 77
3.2. Одиночные линии 79
3.3. Связанные линии , 80
3.4. Эквивалентные однопроводные и двухпроводные линии 81
3.5. Удельные электрические параметры линий передачи на печатных платах 82
3.6. Формулы расчета 86
3.7. Метод расчета сигналов и помех 92
3.8. Использование подсхем и компактного хранения параметров 93
3.9. Редукция многополюсников, представленных Y - параметрами 94
3.10. Редукция эквивалентных схем путем преобразований «звезда-многоугольник» 96
Выводы 97
IV. Совместное решение задач размещения и трассировки 98
4.1. Создание условий для качественной детальной трассировки 99
4.2. Начальное размещение 100
4.3. Выбор конфигурации цепей 108
4.4. Разбиение областей 108
4.5. Назначение ячеек на области и установка размеров новых областей 109
4.6. Предварительная трассировка 111
Выводы 112
V. Разработка и эксплуатация программной подсистемы размещения 113
5.1. Входные - выходные данные 113
5.2. Структура данных 113
5.2.1. Сущности 114
5.2.2. Конструктив и схема соединений 116
5.2.3. Принадлежность ячеек областям 116
5.2.4. Графы горизонтального и вертикального разбиений 117
5.2.5. Лес цепей 117
5.2.6. Граф смежности областей для макротрассировки 118
5.3. Пользовательский интерфейс 118
5.4. Экспериментальная оценка качества машинного размещения 121
5.4.1. Сравнительные результаты расчета электромагнитных помех 121
5.4.2. Сравнение результатов автоматического размещения компонентов в программах
Specctra и AuTOP 123
Выводы 125
Заключение 126
Литература 128
Приложения
- Размещение для получения равномерного заполнения монтажного пространства
- Построение модели схемы на основе линейного размещения независимых цепей
- Удельные электрические параметры линий передачи на печатных платах
- Назначение ячеек на области и установка размеров новых областей
Введение к работе
Техническое проектирования является важнейшим этапом разработки радиоэлектронных средств (РЭС) различного назначения.
На этом этапе определяется конструктивная реализация проектных идей и решений, формируются основные производственно-экономические и эксплуатационные характеристики будущих изделий. В результате технического проектирования описание (модель) разрабатываемого объекта достигает наиболее полного и детального уровня, необходимого для непосредственного материального воплощения проекта. Многообразие требований, ограничений и компонентов получают здесь конкретное единство.
Современным радиоэлектронным устройствам присущи многоуровневая структура и многоэлементность. Преобладающее распространение п конструировании РЭС получили микроэлектроиная реализация и печатный монтаж. В этих условиях одним из наиболее сложных этапов технического проектирования стало монтажно-коммутациошюе проектирование (МКП), на котором определятся расположение электрорадиоэлементов (ЭРЭ) в монтажном пространстве и траектории связывающих их электрических соединений. В практике МКП широкое применение находят автоматизированные методы. Большинство известных систем автоматизированного проектирования (САПР) РЭС в качестве обязательной включают процедуру МКП, а во многих случаях сводятся к ней.
Несмотря на богатый алгоритмический МКП и его интенсивное практическое использование, ручные методы проектирования остаются в настоящее время конкурентоспособными и зачастую превосходят по качеству получаемых решений результаты, достигнутые с помощью ЭВМ. Однако, даже уступая в качестве, автоматизированные методы становятся
незаменимыми при поточной разработке устройств с миллионами и десятками миллионов электрически и пространственно связанных элементов. Существует и обостряется проблема значительного повышения эффективности автоматизированных методов МКП. Объектив!пле факторы, стимулирующие критическое переосмысливание сложившихся подходов в машинном поиске решений, сводятся в основном к следующим:
переход к конструированию функционально законченных узлов в гибридно-интегральном исполнении с использованием крупноформантых подложек-оснований и установкой на них разнотипных электрорадиоэлементов;
широкая номенклатура проектируемых электронных узлов, различающихся по сложности и требующих учета различных схемно-конструкторских ограничений;
повышение требований к надежности и технологичности изделий, в частности, монтажа межсоединений;
необходимость ориентации создаваемых САПР на автоматизированное производство; недостаточно высокое качество результатов автоматического синтеза топологии в известных САПР, вынуждающее "дорабатывать" машинные решения вручную или в диалоговом режиме, но без гарантий оптимальности конечного результата.
Заметный вклад в исследование проблемы эффективности автоматизированных методов МКП внесли Л.Б.Абрайтис, Р.П., Базилевич, A.M. Бершадский, В.М. Глушков, Б.Н. Деньдобренко, В.М. Курейчик, С.А. Майоров, Н.Я. Матюхин, А.Н. Мелихов, К.К. Морозов, А.И. Петренко, Г.Г. Рябов, В.А. Селютин, А.Я. Тетельбаум, Г.Р. Фридман, М.Е. Штейн, Г.Э. Широ и многие другие.
Продолжают разрабатываться все новые и новые алгоритмы топологического синтеза (размещения элементов и трассировки
межсоединений), различающихся в основном конкретными машинными версиями и учетом технологических ограничений. Ведется активный поиск критериев качества МКП и совершенствование программной и аппаратной реализации САПР. В меньшей степени уделяется внимание совершенствованию математических моделей проектируемых устройств, доказательству обоснованности выбора используемых для решения задач МКП эвристических процедур.
Возможности дальнейшей плодотворной разработки проблемы повышения эффективности автоматизированных методов МКП заключаются в быстром расширении практики и опыта автоматизированного конструирования и смежных специальных дисциплин, наконец, в пополнении и развитии аппарата вычислительной математики и интенсивном развитии средств вычислительной техники.
Целью диссертационной работы является исследование возможности повы[пения степени адекватности моделей объектов и эффективности алгоритмов автоматического МКП узлов РЭС, выполненных па основе изделий микроэлектроники с применением печатного монтажа или гибридно-интегральной технологии. В соответствии с этим в работе ставились и решались следующие задачи:
анализ применяемых моделей объектов и критериев МКП узлов РЭС на печатных платах, микросборках и СБИС; формирование эффективной оценки качества размещения ЭРЭ в монтажном пространстве;
построение адекватных требованиям топологического синтеза моделей электрических схем проектируемых узлов, используемых на этапе размещения компонентов;
разработка методики расчета электромагнитных помех в устройствах с печатным монтажом;
разработка эффективного метода размещения компонентов с учетом оценочного уровня электромагнитных помех и загруженности монтажного пространства;
создание и адаптация к промышленным условиям эксплуатации быстродействующих программных средств автоматического размещения ЭРЭ на печатных платах и микросборках для проведения автоматизированного проектирования узлов РЭС.
Научная новизна работы заключается:
в выявлении закономерностей, определяющих влияние параметров модели электрической схемы, используемой для решения задачи размещения компонентов, на плотность и равномерность заполнения монтажного пространства;
в разработке моделей электрических схем, адекватных требованиям топологического синтеза РЭС;
в разработке эффективного алгоритма размещения компонентов электронных схем в плоском коммутационном пространстве.
Практическая ценность работы состоит в создании прикладных программ, предназначенных для решения задачи размещения ЭРЭ в автоматическом режиме. Применение разработанных программ обеспечивает улучшение качества и сокращение сроков проектирования СБИС и печатных узлов РЭС, позволяет сосредоточить внимание конструкторов на поиске действительно оптимальных вариантов конструктивной реализации аппаратуры.
Результаты диссертационной работы в виде конкретных положений, выводов, методов, алгоритмов, машинных программ и расчетных данных внедрены и инженерную практику и используются на промышленных предприятиях в Санкт-Петербурге и Одессе, а также в учебном процессе СПбГУТ им. проф. М.Л.Бонч-Бруевича и СЗПИ. Акты, подтверждающие внедрение, приведены в приложении.
Основные положения и результаты диссертационной работы докладывались и были одобрены на следующих конференциях:
III Международной научно-практической конференции "Системы и средства передачи и обработки информации", г. Одесса, 1999г;
П-ой международной научно-технической конференции студентов, аспирантов и молодых специалистов стран СНГ, г. Санкт-Петербург, 2000г. (2 доклада);
IV Международной научно-практической конференции "Системы и средства передачи и обработки информации", г. Одесса, 2000г.;
Научно-практической конференции "Современные информационные и электронные технологии", г. Одесса, 2000г.;
V международной научно-практической конференции "Системы и средства передачи и обработки информации", г. Одесса, 2001г.;
8-й международной научно-технической конференции студентов и аспирантов "Радиоэлектроника, электротехника и энергетика", Москва, 2002г.;
9-й международной конференции "Современные технологии обучения", С.-Петербург, 2003 г.;
4-й международной НПК "Современные информационные и электронные технологии", Одесса, 2003 г.;
1-й международной научно-технической конференции HnH(CALS)-2003 "Информационные технологии в управлении жизненным циклом изделий", С.-Петербург, 2003 г.;
Научно-технических конференциях профессорско-преподавательского состава СПбГУТ им. проф. М.А.Бонч-Бруевича, г. Санкт-Петербург, 1998г., 1999г.
По теме диссертации опубликовано 20 работ. Получено авторское свидетельство на программное средство, зарегистрированное в Государственном фонде.
Диссертация состоит из введения, пяти глав, заключения, одного приложения и списка литературы, включающего 87 наименований. Основная часть работы изложена на 125 страницах машинописного текста. Работа содержит 43 рисунка и 10 таблиц.
Во введении кратко освещен предмет исследования, обоснована актуальность темы диссертационной работы. Сформулированы основные положения, выносимые па защиту, научная новизна и практическая ценность результатов. Кратко описано содержание диссертации по главам.
В первом разделе дан аналитический обзор современных моделей, методов и критериев оценки качества автоматизированного синтеза конструкторских решений, сформулированы перспективные направления повышения эффективности алгоритмов и программных систем на их основе и обоснована постановка задач диссертационной работы.
Во второй главе предложены методы построения теоретикографовой модели электрической схемы устройства для решения задач компоновки и размещения.
В третьей главе предложены методы расчета электромагнитных помех в печатных платах.
В четвертой главе предложена методика оптимизации размещения с целью равномерной загрузки монтажного пространства, минимизации суммарной длины соединений и числа пересечений трасс при обеспечении минимального уровня электромагнитных помех.
В пятой главе приведены результаты экспериментальных исследований разработанных алгоритмов и программ.
В заключении сформулированы основные научные и практические результаты работы.
В приложении даются сведения, подтверждающие использование полученных результатов в народном хозяйстве страны.
Размещение для получения равномерного заполнения монтажного пространства
Другой подход к устранению избыточности модели электрической схемы заключается в представлении ее графом, в котором в целях устранения полных подграфов цепей переходят к представлению цепей их деревьями. Сложность задачи в данном случае заключается в обосновании объективного критерия выбора совокупности деревьев, а также в алгоритмических трудностях, связанных с определением набора этих деревьев.
Действительно известно, что число различных деревьев, которые можно построить на П вершинах [93], равно п , поэтому число возможных вариантов моделей схемы составит Даже для сравнительно небольших схем число Q огромно и исключает возможность построения модели путем прямого перебора.
Допустим, что деревья определены для каждой цепи. Объединение ребер этих деревьев образует множество ребер графа искомой модели. В [118] предлагается из множества Q конфигураций деревьев выбрать те, которые в объединении дают граф с минимальным числом ребер. В этой же работе рассматривается точный алгоритм решения поставленной задачи, в основу которого положена идея составления некоторого логического уравнения. Над этим уравнением последовательно выполняются операции конъюнкции и поглощения. Терм с минимальным числом переменных в результирующем выражении определяет совокупность ребер искомого графа. Однако указанный алгоритм приводит к слишком громоздким вычислениям уже при # 20 (ft- число компонентов схемы) и не находит применения на практике.
Авторы отмечают, что сокращение числа ветвей графа модели схемы "приводит к уменьшению числа ненулевых элементов и одновременному увеличению их значений в матрице коэффициентов связей, что создает предпосылки для получения лучших решений задачи размещения, так как появляется возможность полнее учесть требование близкого размещения компонентов, соединенных большим количеством проводников... Использование подобной модели косвенно способствует упрощению и этапа трассировки. Действительно, так как уменьшение числа ребер графа модели схемы связано с уменьшением толщины графа, то это, в свою очередь, создает предпосылки для уменьшения числа слоев при реализации многослойных печатных плат".
Однако аргументы, приводимые авторами в защиту модели, нельзя признать состоятельными. Во-первых, "требование близкого размещения компонентов, соединенных большим количеством проводников", является безусловным лишь для схем с од-нозвенными цепями.
Каждое звено любой из цепей соединяет элементы, размещенные в смежных позициях, следовательно, длина любой цепи минимальна. Кроме того, схема, приведенная на рис, 1.4, планарна, т.е. отсутствуют пересечения трасс. При этом элементы 4 и 13, соединенные наибольшим количеством проводников (четыре общих цепи), максимально удалены друг от друга. Ясно, что близкое размещение сильно связанных элементов в подобных случаях приводит либо к увеличению числа пересечений трасс, либо к увеличению суммарной длины соединений. Во-вторых, поскольку при трассировке каждая цепь реализуется в виде некоторого дерева (а не полного графа), сравнение толщин графа исходной (избыточной) модели и преобразованной (неизбыточной) вообще пе имеет смысла. Как признают сами авторы рассматриваемой работы, основными недостатками данной модели являются сложность определения графа модели схемы и повышение числа проводников на отдельных участках платы, что может затруднить трассировку.
Математическая модель монтажного пространства обычно представляет собой (для случая размещения одногабаритных элементов) регулярный степени четыре бихроматический граф. Если графы модели схемы и модели монтажного пространства изоморфны [3], то укладка схемы в монтажное пространство может быть произведена без пересечения трасс и с минимальной суммарной длиной соединений, так как в этом случае длина каждого звена в любой цепи равняется расстоянию между смежными позициями. Чем выше степень интеграции элементов, тем больше количество внешних выводов и соответственно больше цепей, в которых задействован элемент.
Таким образом, рост степени интеграции элементов автоматически приводит к росту степеней вершин графа модели электрической схемы, в то время как модель монтажного пространства не претерпевает изменений. Это приводит к обострению конфликта между ограниченным числом ближайших позиций и возрастающим числом претендентов на размещение. В подобной ситуации размещение элементов только на основе информации о количестве общих цепей пи-как не учитывает возможность многократного дублирования одних и тех же цепей. Теоретически возможен случай, когда минимум суммарной длины, полученный при использовании избыточного мультиграфа, будет сочетаться с максимумом суммарной длины кратчайших связывающих деревьев, построенных для каждой из цепей, т.е. подобное размещение будет наименее благоприятным для последующей трассировки межсоединений.
Построение модели схемы на основе линейного размещения независимых цепей
Произведем линейное размещение выделенного подграфа по критерию минимальной суммарной длины межсоединений, воспользовавшись для этого алгоритмом [116]. В результате получим следующее линейное размещение подграфа: 5-1-3-6-4.
Построим матрицу смежности, в которой отметим количество связей между соседними элементами (рис.2.4а). Длина цепей с номерами 2, 4, 6 в исходном мультиграфе и в порожденном подграфе одинакова, следовательно, эти цепи являются зависимыми и исключаются из рассмотрения. После исключения цепей с номерами 2, 4, 5, 6 в табл. 2.2 имеем две цепи с максимальной длиной - 1 и 3, т.е. две независимые цепи. Применив для цепей 1 и 3 процедуру, аналогичную рассмотренной выше, получим линейное размещение связываемых этими цепями элементов соответственно 1-4-2 и 2-4-6; при этом матрица смежности нового мультиграфа будет иметь вид, показанный на рис.2.4б (зависимая цепь 7 исключается).
Таким образом, осуществляется линейное размещение всех порожденных подграфов, сопоставленных множеству всех независимых цепей. Полученная матрица смежности (рис.2.4б) соответствует мультиграфу, изображенному на рис. 2.5, который и является окончательной моделью электрической схемы, используемой затем при размещении.
Сравнение исходного и преобразованного мультиграфов показывает, что преобразованный мультиграф планарен в отличие от исходного и имеет меньшее количество ребер, что упрощает решение задачи размещения элементов.
Для того, чтобы минимизировать суммарную длину звеньев цепей, соединяющих некоторый элемент Х( с другими элементами, необходимо и достаточно расположить рядом с этим элементом минимальное множество элементов, содержащих все внешние связи данного элемента. Очевидно, что если минимальна суммарная длина внешних связей для любого из элементов, размещенных на плате, то минимальна и общая суммарная длина межсоединений. Исходя из этого, можно исключить избыточные ребра мультиграфа, решив для каждого из элементов задачу наименьшего покрытия их внешних связей и построив матрицу смежности теоретико-графовой модели схемы, в которой отмечено наличие связей "покрытого" элемента только с множеством элементов, образующих его наименьшее покрытие. Математически задача формулируется следующим образом. Поскольку при реализации "покрытия" некоторого элемента множеством других элементов последние оказываются "частично покрытыми" и притом, возможно, не оптимально, то необходимо установить критерий для определения последовательности решения этой задачи. Очевидно, что сначала необходимо реализовать покрытие наиболее "труднопокрынаемых" элементов, т.е. таких, для которых вероятность их покрытия некоторой группой случайным образом выбранных элементов минимальна. Поскольку вероятность покрытия внешних связей некоторого элемента тем меньше, чем короче его внешние связи ( чем меньше звеньев в цепях) и тем больше, чем меньше количество внешних связей, то для определения последовательности решения задачи наименьшего покрытия воспользуемся следующей оценкой покрываемости элемента: где L -длина j-й цепи (количествоэлементов, связанных j-й цепью); к - количество внешних связей элемента xs; Расположив номера элементов в порядке убывания значения оценки Fjy получим последовательность элементов, определяющую порядок их покрытия. Для решения задачи наименьшего покрытия внешних связей некоторого элемента составим таблицу, каждый столбец которой содержит номера элементов, связанных с данным некоторой цепью. Количество столбцов таблицы определяется количеством внешних связей данного элемента. Запишем информацию, содержащуюся в указанной таблице в виде псевдобулевой функции, в которой номера элементов (а они выступают в качестве идентификаторов некоторых псевдобулевых переменных), заиисанных в столбце, связаны операцией дизъюнкции, а все элементарные диз7 юнкции, соответствующие столбцам таблицы, связаны операцией конъюнкции: Воспользовавшись известным соотношением алгебры логики а л(а v b) = a{a,b — 0 v 1), .можно упростить указанную псевдобулеву функцию и получить наименьшее покрывающее множество, которому будет соответствовать терм минимальной длины. При этом в матрице смежности синтезируемой модели схемы необходимо отметить наличие связей вершины, соответствующей элементу х,., с вершинами, соответствующими элементам, номера которых вошли в терм минимальной длины. Таким образом данный метод направлен на снижение максимальной степени вершин графа модели схемы и, следовательно, способствует уменьшению среднеквадратичного разброса степеней вершин.
Удельные электрические параметры линий передачи на печатных платах
Уменьшение размеров интегральных микросхем и одновременное увеличение количества входных и выходных контактов при реализации цифровых цепей на печатных платах (ПП) приводит к значительному повышению плотности монтажа. Повышение тактовой частоты работы цифровых цепей в этих условиях увеличивает влияние между цепями (электромагнитные помехи). Соединения между микросхемами, по которым передаются сигналы, фактически становятся длинными линиями с распределенными параметрами, поэтому задача нахождения электромагнитных помех приводит к задаче расчета электрических и магнитных полей в системе печатных проводников и контактных площадок цифровой цепи.
Точное решение этой задачи может быть получено путем составления и решения уравнений Максвелла [4], однако решение этих уравнений даже для простейшей задачи из нескольких цепей является очень сложным. В современных печатных платах количество цепей может доходить до нескольких тысяч, поэтому необходимо использование приближенных методов.
Кроме помех, определяемых электромагнитными полями, в печатных платах существует и другой вид помех: связь через общее сопротивление [1] (ток в шине заземления от одной микросхемы вызывает падение напряжения, которое может попасть на выход другой микросхемы и вызвать ее ложное срабатывание).
В настоящей главе рассмотрены вопросы расчета только помех первого вида, так как способы расчета их сильно отличаются от способов расчета помех второго вида. Однако, многие используемые методики применимы и для последних. Линии с распределенными параметрами будем представлять так называемыми цепными схемами, состоящими из достаточно большого количества ячеек, составленных из элементов с сосредоточенными параметрами (R, L, С). Взаимная связь линий учитывается в ячейках с помощью коэффициента взаимной индукции (М). В печатных платах цифровых узлов электромагнитные помехи существенно могут повлиять только на входы микросхем, влиянием помех на цепи питания и выходы микросхем можно пренебречь. Так как цепные схемы, моделирующие влияние помех, являются линейными, используются принципы наложения: на каждую цепь подается сигнал, и вычисляются помехи в связанных цепях, которые суммируются с уже ранее вычисленными помехами от других цепей. Влияние цепей друг на друга уменьшается при увеличении расстояния между ними, поэтому при расчете помех учитываются только цепи, находящиеся ближе заданного расстояния, которое может изменяться, lie учитываются также линии, длины которых меньше заданной. Эта длина также может изменяться. Для расчета удельных параметров использованы формулы из [4]. Как показали расчеты, указанные выше допущения не приводят к существенным погрешностям. Результаты расчета цепных схем, приведенные в [7,10], также подтверждают это. Будем определять напряжение на входах микросхем при синусоидальном напряжении источника сигнала. Это дает возможность оценить величину помех и сравнивать по уровню помех ПП, на которых реализована одна и та же цифровая цепь разными трассировщиками (например, PCAD и TopoR), а также направленно снижать уровень помех, изменяя метрические соотношения или топологию печатной платы. Источник сигнала в цифровых цепях импульсный и это, конечно, влияет на величину помех. Решить задачу вычисления помех при импульсном источнике сигнала можно, используя преобразование Фурье частотной характеристики. Такие решения описаны в [8,10]. Хотя задачей работы был расчет только электромагнитных помех, но как побочный результат, разработанная методика позволяет производить также расчет сигналов на входах элементов и оценить отношение помеха/сигнал. Используя, как и указанно выше, преобразование Фурье можно оценить искажения и задержки сигналов в цифровых цепях печатной платы. При расчете электромагнитных помех учитывается трехмерный характер задачи. На рис.3.1 показан фрагмент МПП в поперечном разрезе. Сигнальная линия (SL) - это линия, по которой передается сигнал. Вокруг нее показаны 8 возможных параллельных линий (0-7).
Как уже указывалось выше, учитываются только линии, находящиеся ближе заданного расстояния. Таким образом, в ячейку цепной схемы может входить трансформатор с 9 обмотками. Эквивалентная схема такого трансформатора очень сложна [5]. Учитывая, что нагрузка, создаваемая связанной линией, достаточно мала, можно пренебречь влиянием одной связанной линии на другую линию, связанную с этой же сигнальной линией. Поэтому в рассматриваемом случае можно заменить трансформатор с 9 обмотками 8-ю трансформаторами, каждый из которых имеет только 2 обмотки, что позволяет вместо одной сложной схемы рассматривать 8 значительно более простых схем.
Назначение ячеек на области и установка размеров новых областей
Для уменьшения высоты дерева разбиений, а значит, количества итераций силового размещения и пробной трассировки, выгодно помешать в каждую из двух новых областей примерно одинаковое количество ячеек (то есть делить по медиане), однако лучшее по качеству назначение можно получить, если делить множество ячеек по координате центра области.
Альтернативные методы дихотомического деления используют для распределения ячеек не силовой алгоритм, а находят минимальный разрез подсхемы и делят вдоль него. Это обеспечивает меньшую перегруженность сечений. Однако, как было показано в первой главе, поподобный подход не способствует получению рациональных конфигураций цепей.
Перед тем, как начать пробную трассировку, необходимо приписать новым областям какие-нибудь размеры, то есть разделить старую область в каком-нибудь отношении. Разделение осуществляется пропорционально суммарной площади ячеек с учетом количества задействованных портов.
Обычно для решения подобных задач используются методы сетевого планирования. Найдя критические пути в сетевом графике, определим необходимые размеры области. После изменения размеров областей, надо пересчитать координаты ячеек. Пусть (XL, YB) и (XR, YT) - координаты соответственно левого нижнего и правого верхнего углов прямоугольной области до изменения сё размеров, (XL , YB ) и (XR , YT ) - после изменения размеров, (х, у) -координаты какой-либо ячейки из этой области до изменения размеров области. Тогда координаты этой ячейки после изменения размеров (х , у ) выражаются:
Аналогичные преобразования выполняются и для всех внешних контактов, относящихся к этой области. Это обеспечивает пропорциональное растяжение/сжатие всего содержимого области без изменения относительного расположения.
Пусть для некоторого печатного проводника на одном слое известны начальная и конечная точки пути, известно, между какими элементами топологии проходит его маршрут и как велико минимально возможное расстояние от оси проводника до этих элементов. Минимально возможное расстояние складывается из радиуса элемента топологии, половины ширины проводника, суммы ширин всех проводников, лежащих между ними, и суммы допустимых зазоров между упомянутыми объектами. Тогда для этого проводника существует единственный путь минимальной длины. Проводник огибает элементы топологии по дугам окружностей с необходимыми радиусами, а с одной окружности на другую переходит вдоль отрезков прямых, касательных к обеим окружностям.
Важно, что, если путь каждого проводника выбирается таким способом, то разные проводники огибают одно и то же препятствие по дугам концентрических окружностей, а значит форма пути каждого проводника не зависит от порядка обработки других проводников. Поэтому порядок обработки проводников может быть произвольным, вычисления их путей могут даже производиться параллельно.
Таким образом, для того, чтобы вычислить оптимальную геометрическую форму проводника, достаточно знать, какие рёбра триангуляции он пересекает, то есть топологический маршрут проводника. Топологические маршруты проводников находит гибкий бессеточный топологический трассировщик TopoR [ ]. Более того, TopoR осуществляет автоматическое силовое перемещение элементов на уже разведённой плате, сохраняя при этом целостность разводки и соблюдая заданные зазоры.
Результатом трассировки является точная топология трасс, а также информация о загруженности ребер и о загруженности областей участками трасс, включая и трассы, которые заканчиваются в области.
Точная топология трасс используется в качестве входной информации программы расчета электромагнитных помех. На основе информации об уровне помех на каждой цепи осуществляется корректировка правил трассировки цепи (увеличение зазоров). После чего включается силовое перемещение компонентов. Все это (трассировка, расчет перекрестных помех, раздвижка компонентов) повторяется до обепечения требуемого уровня электромагниных помех, либо до установления факта, что ресурсов площади недостаточно для обеспечения требуемых зазоров.
