Содержание к диссертации
Введение
ГЛАВА 1. Задачи анализа электромагнитной совместимости печатных плат цифровых электронных средств 13
1.1. Электромагнитная совместимость. Межсоединения электронных средств 13
1.2.Системы анализа электромагнитной совместимости электронных средств 33
1.3.Постановка проблемы 50
Выводы по главе 1 54
ГЛАВА 2. Моделирование внутриаппаратурной электромагнитной совместимости печатных плат цифровых электронных средств 55
2.1.Методы анализа электрических параметров межсоединений 55
2.2. Методы анализа электромагнитных процессов в межсоединениях 86
2.3.Модели для анализа электромагнитных процессов в межсоединениях 133
2.4.Методы снижения размерностей задач анализа 146
2.5.Модель для анализа импульсных помех на шине земли 168
Выводы по главе 2 181
ГЛАВА 3 . Электромагнитное взаимодействие печатных плат цифровых электронных средств с окружающей средой 183
3.1.Моделирование влияния статического электричества на печатные платы 183
3.2.Моделирование влияния внешнего электромагнитного поля на печатные платы 217
3.3. Моделирование электромагнитных излучений от печатных плат 255
Выводы по главе 3 291
ГЛАВА 4. Оптимизация электромагнитной совместимости межсоединений печатных плат цифровых электронных средств 293
4.1.Цель и методы оптимизации 293
4.2.Оптимизация внутриаппаратурной электромагнитной совместимости межсоединений цифровых печатных плат 303
4.3. Многокритериальная оптимизация электромагнитной совместимости межсоединений цифровых печатных плат 327
Выводы по главе 4 346
ГЛАВА 5. Проектирование печатных плат цифровых электронных средств с учетом критерия электромагнитной совместимости 347
5.1.Рекомендации по проектированию печатных плат 347
5.2. Методы и алгоритмы проектирования межсоединений печатных плат 353
5.3.Модели и стратегии для проектирования межсоединений печатных плат 374
5.4.Размещение элементов на печатной плате генетическим алгоритмом 407
5.5.Компоновка схем по модулям генетическим алгоритмом 418
Выводы по главе 5 428
Выводы 429
Библиографический список
Использованной литературы
- Электромагнитная совместимость. Межсоединения электронных средств
- Методы анализа электромагнитных процессов в межсоединениях
- Многокритериальная оптимизация электромагнитной совместимости межсоединений цифровых печатных плат
- Методы и алгоритмы проектирования межсоединений печатных плат
Электромагнитная совместимость. Межсоединения электронных средств
Электромагнитная совместимость - современное понятие [93, 334], обобщающее возникшую еще в начале развития электротехники и приобретающую в настоящее время все большое значение проблематику. С появлением электроники и микроэлектроники резко возросло число как излучающих помехи технических средств, так и реагирующих на помехи устройств. Это привело к необходимости нормирования уровней излучаемых помех и помехоустойчивости.
Под электромагнитной совместимостью понимают нормальное функционирование передатчиков и приемников электромагнитной энергии. Иными словами, энергия передатчиков достигнет только желаемых приемников, приемники отреагируют только на сигналы передатчиков по своему назначению, нежелательные взаимные влияния отсутствуют.
Понятия «передатчик» и «приемник» имеют более широкий смысл, чем, например, в средствах связи. Так, к передатчикам электромагнитной энергии наряду с телевизионными и радиовещательными устройствами относят также электрические цепи и системы, которые непреднамеренно излучают в окружающую среду влияющую электромагнитную энергию (так называемые источники помех), например, силовая электроника, контакты выключателей, электродвигатели, люминесцентные лампы, атмосферные разряды и т.д. Приемниками электромагнитной энергии наряду с радио- и телевизионными устройствами являются системы автоматизации, автомобильная микроэлектроника, измерительные и управляющие приборы и регуляторы, электронные средства, сердечные стимуляторы, биоорганизмы и т.д. Тем самым современное понятие ЭМС выходит далеко за рамки классической
зашиты радиопомех, являясь более общим понятием.
Технические средства могут одновременно действовать и как приемники, и как передатчики. В связи с этим можно упомянуть промежуточную частоту супергетеродинных приемников, частоту строчной развертки компьютерных мониторов, частоту таймеров ЭВМ и т.д. Поэтому говорят об электромагнитной совместимости отдельных технических средств. Закон Российской Федерации "О техническом регулировании" и Технический регламент "Об электромагнитной совместимости" определяют электромагнитную совместимость технических средств как "способность технических средств функционировать удовлетворительно в их электромагнитной обстановке, не создавая недопустимых электромагнитных помех другим техническим средствам". Поэтому техническое средство считается совместимым, если оно в качестве передатчика является источником помех не выше допустимых, а в качестве приемника обладает допустимой чувствительностью к посторонним влияниям, т.е. достаточной помехоустойчивостью или иммунитетом. Проблема ЭМС возникает, как правило, прежде всего, у приемников, если нарушается безупречный прием полезного сигнала, например, случайно поступившей электромагнитной энергией нарушено или сделано совсем невозможным нормальное функционирование системы автоматизации. Тогда говорят о наличии электромагнитных влияний. Работа [334] определяет электромагнитные влияния как «воздействие электромагнитных величин на технические средства, электрические цепи, приборы, системы или живые существа».
В противоположность влияниям между различными системами, которые называют внешними электромагнитными влияниями, передатчик и приемник могут быть также частями одной и той же системы. Тогда говорят о внутренних влияниях (рис. 1.2). Типичными примерами внутренних влияний являются изменения сигналов в соседних проводниках электронных узлов, изменения тока в проводах электроснабжения и вызванные ими падения напряжения.
В каких случаях передатчики и приемники характеризуются как электромагнитно совместимые, что существенно зависит от вида передатчика или приемника. Передатчики, которые отдают паразитную электромагнитную энергию в окружающую среду, считаются совместимыми, если значения напряженности производимого ими поля на определенном расстоянии не превосходят установленных предельных значений, т.е. если возможно безупречное функционирование находящегося на этом расстоянии приемника в соответствии с его паспортными данными. Приемники считаются совместимыми, если они в состоянии принимать при электромагнитном загрязнении свой полезный сигнал с удовлетворительным уровнем помех, а сами не излучают недопустимых помех (например, мониторы персональных ЭВМ).
Благодаря надлежащим техническим мероприятиям при конструировании передатчиков (экранирование, ограничение спектра, направленные антенны), путей коммуникаций (экранирование, фильтрация, топология проводников), приемников (экранирование, фильтрация, схема) возможно практически во всех случаях достичь удовлетворительной ЭМС. Однако по экономическим соображениям, если это технически выполнимо, стремятся вначале к возможно более высокой совместимости передатчиков (первичные мероприятия), а совершенствованием многочисленных приемников занимаются лишь во вторую очередь (вторичные мероприятия). Типичными примерами первичных мероприятий служат уменьшение влияния сети в выпрямителях путем компенсации или фильтрации, соответствующая проводка кабелей, экранирование микроволновых печей. Часто ЭМС достигается лишь совместными мероприятиями, реализованными у всех компонентов,
Соблюдение ЭМС при внутренних влияниях в большинстве случаев можно доверить изготовителю или пользователю, которые, безусловно, заинтересованы в работоспособной системе. При внешних электромагнитных влияниях законодатель в рамках требований защиты от помех предписывает предельные значения допустимых излучений. Допустимые излучения устанавливаются в результате компромисса, который должен учитывать как природу передатчиков, так и технические потребности работающих в данном частотном диапазоне приемников.
В настоящее время применение субнаносекундных интегральных схем в ЭС показало [270, 289], что задача обеспечения ЭМС и помехоустойчивости ЭС является одной из важнейших. Внедрение интегральных схем (ИС), особенно большой и сверхбольшой степени интеграции, в ЭС приводит к резкому увеличению плотности компоновки элементов и значительному изменению методов конструирования ЭС. При этом возрастают требования к помехоустойчивости ИС, особенно по отношению к импульсным помехам, а также к конструкции межсоединений. Задача обеспечения ЭМС ЭС является наиболее сложной, если применяются ИС с высоким быстродействием: эмиттерно-связанной логикой (ЭСЛ) и транзисторно-транзисторные логические (ТТЛ) схемы. В этом случае время переключения элементов схем (от единиц до долей наносекунд) соизмеримо со временем распространения сигнала в межсоединениях и длительностью помех, возникающих от них.
Одновременно с ростом быстродействия элементов расширяется частотная полоса пропускания в активной зоне переключения и уменьшается помехоустойчивость элементов при воздействии импульсов помех, формируемых в межсоединениях как сигналами в соседних линиях связи, так и внешними электромагнитными полями. В этих условиях при конструировании ЭС к межсоединениям предъявляется ряд требований, выполнение которых существенно влияет на конструкцию ЭС в целом. Структура, конструкция и организация межсоединений ЭС, построенных с использованием субнаносекундных элементов, в первую очередь должны обеспечивать ЭМС устройств и высокие скоростные характеристики основной системы логических элементов в сочетании с технологичностью, надежностью и высокими экономическими характеристиками устройств.
Проектирование межсоединений субнаносекундных ЭС характеризуется рядом особенностей [289]: 1) значительное повышение быстродействия, увеличение плотности размещения межсоединений на конструктивах, снижение уровней логических перепадов при уменьшении времен переключения схем и повышение чувствительности элементов к электромагнитным помехам; 2) значительную часть площади на конструктивных модулях 1-го и 2-го уровня занимают межсоединения, например, в сверхбольших интегральных схемах (СБИС) до 80 - 95%; 3) возможности физической реализации межсоединений опережают возможности выполнения испытаний устройств, в том числе на помехоустойчивость. При проектировании отдельных конструктивов для разработки тестов по их проверке требуется несколько человеко-лет; 4) использование СБИС и многослойных печатных плат (МПП) со СБИС не позволяет конструктору наблюдать пути прохождения сигнала на физической реализации машины и, как показал опыт, все пути сигналов (короткие и длинные) являются потенциально критическими; 5) задаче качественного проектирования помехоустойчивых конструктивов подчинены этапы компоновки и размещения элементов на модулях; 6) невозможно изменять топологию ИС изготовленных конструктивов и, следовательно, устранять опасные ситуации в опытном образце устройства; 7) существенно увеличиваются стоимость и сроки разработки аппаратуры, если анализ помехоустойчивости не проводился, начиная со стадии проектирования; 8) экспериментальные исследования ЭМС модулей на СБИС представляют значительные трудности и требуют разработки новых методов и принципов измерений.
Методы анализа электромагнитных процессов в межсоединениях
Решение уравнений Максвелла во временной области позволяет исследовать электромагнитные процессы в ЭС, Однако это решение оказывается довольно сложным даже для простейших структур и трудноосуществимым на высокопроизводительных ЭВМ. Поэтому обычно прибегают к определенным приближениям, следующим из особенностей структур и существенно упрощающим анализ.
Во-первых, межсоединения конструктива кусочно-однородны по длине. На концах нагружены элементами, представляющими произвольные цепи. Если вдоль линии имеются неоднородности, то межсоединения можно разбить на ряд однородных участков, а влияние неоднородностей учесть, вводя соответствующие эквивалентные цепи.
Во-вторых, в линиях связи МПП распространяются квази-ТЕМ-волны [70], а для анализа межсоединений в СБИС применимы методы теории цепей [200].
С учетом этих особенностей межсоединения конструктива можно описать системой дифференциальных уравнений в частных производных во временной области и системой обыкновенных дифференциальных уравнений в частотной области. Существует несколько методов решения подобных уравнений; методы нормальных волн в частотной и временной области, метод функции Грина, метод пошагового продвижения по времени.
Рассмотрим межсоединения конструктива, состоящие в общей сложности из (N+1) проводников (рис. 2.11). Предполагается, что N проводников являются сигнальными, а проводник с номером (Лґ+l) представляет собой земляной проводник. Будем также полагать, что земля имеет нулевой потенциал, а линия имеет произвольное поперечное сечение, но по длине однородна. Пусть ось X направлена вдоль линии, причем точка Х=0 соответствует положению генератора, a X=D - положению нагрузки.
Если диэлектрик линии однороден, а проводники не имеют потерь, то в такой линии существуют ТЕМ-волны любой частоты. Эти волны обладают тем фундаментальным свойством, что вектор электрического поля Е и вектор
магнитного поля Н имеют лишь составляющие, перпендикулярные направлению распространения волн вдоль линии. Иными словами, для этих волн Ех=0 и#х=0. Строго говоря, при наличии неоднородных диэлектриков
и (или) потерь в межсоединениях волны, распространяющиеся по линии, не могут быть волнами типа ТЕМ. В общем случае это гибридные или смешанные волны, то есть волны, которые представляют собой некоторую комбинацию ТЕ- и ТМ-волн; для них Ех 0 и Нх 0. Однако при максимальных
поперечных размерах межсоединений, достаточно малых по сравнению с длиной волны для представляющей интерес составляющей наивысшей частоты, продольные составляющие напряженности поля будут много меньше поперечных составляющих. Поэтому такие гибридные волны можно аппроксимировать квази-ТЕМ-волнами. При анализе межсоединений конструктивов будем полагать, что в линии происходит распространение только квази-ТЕМ-волн. Распространение квази-ТЕМ-волн можно исследовать либо с помощью теории поля, то есть на основе уравнений Максвелла, либо с помощью теории цепей с распределенными параметрами. Для межсоединений с низкими потерями на не слишком высоких частотах (соответствует нашему случаю) оба подхода дают практически одинаковые результаты.
Считаем электрические параметры межсоединений, рассматриваемые в разделе 2.1, известными, то есть будем полагать, что известны следующие (Л хЛГ)-матрицы: матрица [L] погонных индуктивностей, матрица [R] погонных сопротивлений, матрица [В] погонных коэффициентов электростатической индукции и матрица [G] погонных проводимостей. Заметим, что элементы матрицы [В] часто называют емкостными коэффициентами, однако эти коэффициенты не равны собственным и взаимным емкостям между проводниками, поэтому термин "емкостный коэффициент" может ввести в заблуждение. Напомним, что собственная емкость А:-го проводника равна сумме коэффициентов электростатической индукции к-й строки матрицы [В], тогда как взаимная емкость между k-м и /-м проводниками равна коэффициенту Bhi матрицы [В], взятому с обратным знаком. Заметим, что взаимные емкости всегда положительны, тогда как недиагональные коэффициенты матрицы [В] всегда отрицательны. Обозначим через Vu(x,t) напряжение между к-м сигнальным проводником и землей на расстоянии х от генераторного конца в некоторый момент времени Л Обозначим через ik(x,t) ток, протекающий по к-му проводнику на расстоянии х от генераторного конца в некоторый момент времени /. Предполагается, что направление тока отсчитывается от генераторного конца к нагрузке. Согласно теории цепей, напряжения и токи в межсоединениях конструктива при распространении ТЕМ-волн связаны телеграфными уравнениями.
В этих уравнениях собственные (Rkk) и взаимные (Rkl, к Г) сопротивления
обусловлены потерями в проводниках, собственные (Lkk) и взаимные (Lkl, к?$)
индуктивности определяют наводимую ЭДС, обусловленную
электромагнитной индукцией, собственные (Gkk) и взаимные (G№ к?4) проводимости обусловлены потерями в диэлектриках, а собственные (Вкк) и взаимные (Вк1, к 4) коэффициенты электростатической индукции обусловлены
электростатическими зффеїсгами. Следует отметить, что уравнения (2.19) и (2.20) справедливы только для линии, параметры которой не зависят от частоты. Если это условие не соблюдается, то межсоединение должно описываться более сложными уравнениями.
Телеграфные уравнения (2.21) и (2.22) во временной области или (2.23) и (2.24) в частотной области полностью описывают межсоединения. Однако для нахождения характеристики линии, нагруженной определенными цепями, необходимо рассмотреть систему уравнений, объединяющую телеграфные уравнения с уравнениями, описывающими нагруженные цепи. Последние уравнения выражают граничные условия, налагаемые на телеграфные уравнения при х=0 и x=D. Эти уравнения дают соотношения между [KfUOl] и 7(Т),()] прид:=0 и [V(D,tJ] и [i(D,l)\ при x=D, Общей формы для этих уравнений нет, так как они зависят от вида нагружающих цепей. Заметим также, что обычно предполагается, что нагружающие цепи взаимосвязаны только через межсоединения, то есть предполагается, что другого схемного элемента, связывающего обе нагружающие цепи, нет.
Помимо граничных условий при проведении анализа во временной области необходимо знать совокупность начальных условий, которым удовлетворяют напряжения и токи линии в определенный момент времени I. Будем полагать, что в момент /=0 напряжения и токи в линии отсутствуют, Иными словами, начальные условия имеют следующий вид:
Уравнения (2.29) и (2.30) или (2.31) и (2.32) представляют пару матричных уравнений соответственно для напряжений и токов межсоединений, но они не независимы, так как напряжения и токи взаимосвязаны телеграфными уравнениями (2.21) и (2.22).
Рассмотрим описание электромагнитных влияний в частотной и временной областях [334]. Если электромагнитные влияния проявляются преимущественно в форме дискретных частот или шума, их следует рассматривать в частотной области, если как импульсы, переходные и электромагнитные процессы - во временной. Однако поскольку передаточные свойства путей связи и средств помехоподавления удобнее представлять в частотной области, такое представление чаще всего предпочитают и для помех, выраженных во временной области. Пересчет периодических процессов из временной области в частотную выполняют при помощи ряда Фурье, пересчет однократных импульсных процессов - при помощи интеграла Фурье.
Многокритериальная оптимизация электромагнитной совместимости межсоединений цифровых печатных плат
Многие реальные задачи ЭМС межсоединений цифровых печатных плат ЭС требуют оптимизации функции, в которую часто входят конкурирующие критерии и, следовательно, решение подобных задач обычно возможно с помощью комбинации этих критериев в единственный оптимизируемый критерий в соответствии с некоторой функцией полезности или пригодности. Обычно данная функция не известна достаточно хорошо до начала оптимизации. В этом случае вся задача оптимизации должна быть сформулирована как многокритериальная задача с несоизмеримыми (несопоставимыми) критериями. В многокритериальной задаче оптимизируются компоненты векторной ценовой функции. В отличие от оптимизации с единственным критерием, решение данной задачи не единственная точка, а семейство точек, область или поверхность. Каждая точка на этой поверхности оптимальна в том смысле, что не может быть достигнуто улучшение одной векторной компоненты, которое не ведет к ухудшению хотя бы одной из оставшихся компонент.
Отметим, что формулировка задачи многокритериальной оптимизации ЭМС межсоединений цифровых печатных плат отличается от формулировки задачи оптимизации внутриаппаратурной ЭМС (см. раздел 4.2), т.к. требуется оптимизация по нескольким целям (критериям) и (или) учет влияния статического электричества, внешних электромагнитных помех и электромагнитного излучения (см. главу 3). Данные факторы предлагается объединить в единый обобщенный критерий - площадь контура 5, образованного сигнальным проводником на плате и шиной земли.
В данной работе предлагается многокритериальная оптимизация ЭМС межсоединений печатных плат цифровых ЭС генетическими алгоритмами.
Сознавая потенциал генетических алгоритмов в многокритериальной оптимизации [377 ], Шаффер предложил расширение простого генетического алгоритма, чтобы приспособить его к векторным вычислениям функции пригодности, которое он назвал векторным генетическим алгоритмом. В этом случае шаг отбора хромосом преобразовывался таким образом, что в каждом поколении создавалось некоторое количество субпопуляций путем пропорционального отбора особей по очереди в зависимости от каждой целевой функции. Таким образом, для задачи с q критериями, будет получено q субпопуляций размером Niq каждая, полагая, что размер популяции N. Затем эти субпопуляции перемешиваются между собой, чтобы получить новую популяцию размера N. Далее применяются обычные операторы скрещивания и мутации. Однако перемешивание всех хромосом в субпопуляциях вместе, чтобы получить новую популяцию, эквивалентно линейной комбинации вектора функций пригодности [377]. Но весовые коэффициенты зависят от текущей популяции. Это означает, что в общем случае не только две недоминирующие хромосомы могут быть взяты за образцы с разными вероятностями, но также, в случае вогнутой компромиссной поверхности, популяция направляется в трещину между разными частями поверхности, каждая из которых особенно сильна в одном из критериев. Это свойство векторного генетического алгоритма называется видообразованием. Видообразование нежелательно, так как оно препятствует нахождению оптимального решения.
Традиционные приемы определения распределений функций пригодности достаточно малоэффективны в случае многомодальной оптимизации. В работе был предложен новый параметр генетического алгоритма - параметр распределения (размер "ниши") с е, который необходимо тщательно устанавливать. Параметр распределения хромосом устанавливает, насколько далеко могут находиться две особи, чтобы при дальнейшем их скрещивании значение функции пригодности потомка имело более лучшее значение. Существующие теории для установки значения crshare предполагают необходимость предварительного задания некоторых параметров генетического алгоритма. С другой стороны, глобальное решение многокритериальной задачи оптимизации лежит на плоскости среди особей с некоторым значением пригодности, и невозможно узнать размер популяции заблаговременно. Также локальный оптимум не очень интересен для проектировщика, который хочет достичь множества глобальных недоминирующих решений, возможно однородно расположенных и показанных как глобальное пространство компромиссных решений. Метод расчета "ниш" может быть последовательно объединен с процедурой ранжирования особей в популяции путем использования шкалирования функций пригодности в каждом ранге.
Размер области решений многокритериальной задачи оптимизации неизвестен, пока он зависит от отображений целевой функции. Однако когда данный размер выражается через область значений целевых функций и в зависимости от значений недоминирующих, нижний и верхний предел множества решений можно определить исходя из минимальных и максимальных значений каждого критерия внутри этого множества.
В соответствии с тем, что обычно критерии оптимизации в задаче являются несоизмеримыми по физическим размерностям, использование безразмерных величин для измерения "расстояния" между хромосомами кажется более естественным и простым при вычислениях. Однако в этом случае необходимо определять параметр распределения o dtan для каждой особи.
Использование ограничений скрещивания хромосом было предложено в работе [382], чтобы избегать сильной конкуренции между удаленными членами популяции. Способность вычисления & share в области критериев дает возможность представления ограничения скрещивания в той же области. Ограничение скрещивания предполагает, что соседние особи похожи по генотипу, т.е. они могут формировать стабильную "нишу". Далее особое внимание должно быть обращено на кодирование хромосом. Серое кодирование, в противоположность стандартному бинарному, известно своим полезным свойством смежности. Однако кодирование переменных решения как объединение независимых бинарных строк не может последовательно выражать связь между ними. С другой стороны, например, множество Парето, когда оно представлено в области переменных решения, может демонстрировать такие зависимости. В этом случае даже слабо связанные регионы в множестве Парето [381] не могут быть охарактеризованы как одиночные схемы высокого порядка, и возможность ограничений скрещивания, чтобы уменьшить образование непригодных особей, может быть очень мала. Пока значение множества решений увеличивается, увеличение количества хромосом может быть необходимым для того, чтобы обеспечить размер "ниши" достаточно малым. Проектировщик часто ищет единственное компромиссное решение многокритериальной задачи оптимизации, уменьшая область множества решений путем решения на верхнем уровне, какие хромосомы хороши для компромисса, и это помогает преодолеть проблему, описанную выше.
При представлении компромиссной поверхности с заданной функцией, лицо, принимающее решение (ЛПР), должно решить, какие из всех недоминирующих точек выбрать в качестве решения задачи. Сначала должны быть идентифицированы регионы множества Парето (если они рассматриваются), которые отображают хороший компромисс, связанный с некоторым знанием. Затем, имея ясную картину, необходимо искать идею компромисса, пока не будет найдено оптимальное решение. Вызов ЛПР применяется для уменьшения области множества решений и включается в алгоритм отбора. Идея заключается в том, чтобы не просто уменьшить область поиска, а масштабировать регионы области поиска для ЛПР путем обеспечения внешней информации в алгоритме отбора. Метод, описанный ранее, модифицируется для того, чтобы воспринимать информацию в виде цели, которую надо достигнуть.
Методы и алгоритмы проектирования межсоединений печатных плат
Проектирование межсоединений цифровых печатных плат, иначе трассировка межсоединений, является одной из наиболее трудных задач в общей проблеме автоматизации проектирования ЭС. Прежде всего, это связано с многообразием способов конструктивно-технологической реализации соединений, каждый из которых обусловливает использование специфических критериев оптимизации и ограничений при алгоритмическом решении задачи трассировки. С математической точки зрения трассировка - наисложнейшая задача выбора оптимального решения из огромного числа вариантов. Одновременно оптимизация всех соединений при трассировке за счет полного перебора всех вариантов в настоящее время невозможна. Поэтому разрабатываются в основном локально оптимальные методы трассировки, когда трасса оптимальна лишь на данном шаге при наличии ранее проведенных соединений.
Исходной информацией для решения задач трассировки межсоединений являются список цепей, параметры конструкции элементов и коммутационного поля, а также данные по размещению элементов. Таким образом, перед трассировкой межсоединений для каждой цепи схемы могут быть рассчитаны координаты расположения выводов на коммутационном поле.
В алгоритмическом плане задача трассировки состоит в построении для всех цепей схемы оптимальных монтажных соединений. Алгоритмические методы трассировки проводных и печатных соединений существенно различаются.
Алгоритмические методы трассировки печатных межсоединений существенно зависят от конструкции коммутационного поля и могут быть разделены на две основные группы (рис. 5.3). К первой группе относятся так называемые топографические методы [187, 188], в которых приоритет отдается метрическому аспекту задачи. Вторая группа основана на графотеоретическом подходе к решению задачи трассировки. Топографический метод трассировки в общем случае содержит следующие основные этапы: 1) получение списка соединений; 2) распределение соединений по слоям; 3) определение порядка прокладки соединений; 4) собственно трассировка отдельных соединений. Методы данной группы наиболее эффективны для трассировки двухсторонних и многослойных печатных плат, подложек многокристальных БИС, а также для твердотельных БИС с несколькими слоями коммутации.
Поскольку список цепей определяет лишь группы эквипотенциальных выводов, основной задачей первого этапа является предварительное определение порядка соединений выводов внутри отдельных цепей. Такое упорядочение, как и при проектировании монтажных схем проводных соединений, осуществляется с помощью алгоритмов построения минимальных деревьев [216].
Графотеоретические методы трассировки [67, 190] предполагают предварительный анализ планарности схемы, представленной в виде графовой модели, и последующую ликвидацию пересечений с помощью технологических приемов. Окончательная фаза состоит в построении эскиза топологии схемы при рациональном распределении функций между конструктором и ЭВМ. Как уже отмечалось ранее, трассировка соединений является, как правило, заключительным этапом конструкторского проектирования ЭС и состоит в определении линий, соединяющих проектируемое устройство.
Основная задача трассировки формулируется следующим образом: по заданной схеме соединений проложить необходимые проводники на плоскости платы (панели, кристалла и т.п.), чтобы реализовать заданные электрические соединения с учетом заранее заданных ограничений [67, 190]. Основными являются ограничения на ширину проводников и минимальные расстояния между ними.
Задача трассировки всегда имеет топологический и метрический аспекты. Топологический аспект связан с выбором допустимого пространственного расположения отдельных фрагментов соединений без фиксации их конкретного месторасположения при ограничениях на число пересечений и слоев и т.п. Метрический аспект предполагает учет конструктивных размеров элементов, соединений и коммутационного поля, а также метрических ограничений на трассировку.
В известных алгоритмических методах решения задачи трассировки метрический аспект присутствует всегда, а топологический - в большей или меньшей степени. Все существующие методы трассировки можно подразделить на две большие группы: последовательные и параллельные.
В последовательных методах трассы проводят одну за другой последовательно, при этом проведение какой-либо трассы а на (М)-м шаге может затруднить проведение трассы b на /-м шаге, если трасса а является препятствием для проведения трассы Ь. Следовательно, особенно актуальным для последовательных алгоритмов трассировки является предварительное ранжирование (упорядочение) соединений до трассировки. Существуют различные стратегии упорядочения, основанные, в частности, на длине соединений, степени охвата соединением других проводников и т.д. Однако объективных оценок эффективности таких методик в настоящее время пет, поэтому наиболее разумным представляется использование нескольких вариантов очередности и выбор из них наилучшего.
Четвертый этап (трассировка) является основным, наиболее трудоемким, определяющим эффективность и качество всей задачи трассировки. На рис. 5.4 приведена классификация алгоритмов трассировки этого этапа. Рассмотрим и сравним различные методы (алгоритмы) трассировки печатных соединений.
К волновым относятся алгоритмы, основанные на идеях динамического программирования на дискретном рабочем поле (ДРП). В настоящее время разработано огромное число модификаций волнового алгоритма, предложенного Ли еще в 1961 г. Однако все они сохраняют его основной недостаток: большие объемы вычислений и памяти ЭВМ. Временная сложность волнового алгоритма составляет 0(M N), где N-чиспо клеток ДРП; М-число точек, подлежащих соединению. Эффективное использование волновых алгоритмов возможно лишь для ДРП с числом клеток не более 105, при этом время трассировки составляет несколько часов работы ЭВМ Pentium III - 1000 МГц. Число неразведенных трасс обычно не превышает 10%.
Основная идея лабиринтных алгоритмов состоит в отыскании пути между двумя ячейками ДРП посредством последовательного обхода преград в лабиринте, образованном занятыми и свободными ячейками. В отличие от волнового алгоритма поиск носит направленный характер, поэтому время поиска сокращается. Алгоритмы обычно обеспечивают разводку около 80% межсоединений.
