"", 6, 2008 .

Эвристический  алгоритм  проектирования многослойных коммутационных плат

Хватынец С.А.

(Московский Энергетический Институт (ТУ), каф. РПУ. e-mail: vintmf@mail.ru)

 

Введение

Известно, что надежность устройства закладывается на протяжении всех этапов проектирования. Этап проектирования печатной платы устройства крайне ответственный, т.к. надежность устройства во многом будет определена грамотностью размещения компонентов на поверхности печатной платы и правильностью трассировки печатных проводников. Современные методы конструирования радиоэлектронных устройств, предполагают использование различных пакетов САПР для топологического проектирования многослой­ных коммутационных плат (МКП) РЭА. В частности, в настоящее время широкое распро­странение получила система автоматизированного проектирования Altium Р-САD, которая способна работать как в автоматическом, так и в автоматизированном режимах. Кроме САПР Р-САD существует большое количество других не менее достойных САПР. Например, Expedition PCB, САПР, разрабатываемая фирмой Mentor Graphics совместно со своими российскими коллегами. Expedition PCB обладает по истине уникальным автоматическим трассировщиком, способным по качеству трассировки приблизиться к трассировке, выполненной «руками» в автоматизированном режиме. Но, не смотря на то, что алгоритмы автоматического проектирования постоянно совершенствуются, «ручное» проектирование остается самым качественным и по сей день. В отличие от автоматизированного, автоматические методы проектирования требуют больших временных затрат для достижения приемлемых результатов размещения и трассировки. Разработчику необходимо точно описать назначения выводов компонентов (вход, выход, питание, тактирование и т.д.), назначать классы цепей, объединять электрические цепи и шины в группы, определить тактику размещения компонентов, задать технологические нормы. В результате работы автоматических программ проектирования разработчик получает «полуфабрикат», который он должен в последующем «доводить» вручную. Получается, что чем сложнее проект, тем более трудоемким становится процесс подготовки проекта к автоматическому размещению и трассировке, а также последующей «доводки» результата, полученного с помощью автоматических методов, тем невыгоднее применять автоматические методы проектирования.
Это подтверждает практика использования Р-САD на предприятиях радиоэлектронного профиля. Современные устройства повышенной сложности, такие как системные платы (до 20-ти слоев), видеокарты (до 12 слоев) платы других устройств и подсистем сегодня на практике не проектируют в автоматическом режиме. Как уже отмечалось, проектирование сложных устройств с применением автоматических алгоритмов трассировки печатных проводников и размещения компонентов потребует гораздо большего времени, нежели изначальное применение автоматизированного эвристического проектирования с применением P-CAD в качестве редактора высокого уровня.
В предлагаемой работе изложена доработка, разработанного ранее  эвристического метода проектирования МПП [4] [5], с привлечением методов многокритериального выбора [3], состоящего из четырех этапов:

  1. поиск оптимального варианта стратегии размещения компонентов;
  2. выбор «главных» компонентов, вокруг которых будут размещаться компоненты обвязки – формирование острова;
  3. сближение образованных островов;
  4. переразмещение мелких компонентов для большего сближения островов и трассировки печатных проводников.

Поясним на примере работу островного алгоритма размещения компонентов. Пусть для примера, поясняющего работу алгоритма, необходимо разработать МКП для графической МКП.  
Требуется:

  1. Разместить на МКП компоненты устройства, состоящего из процессора обработки двухмерной и трехмерной графической информации, оперативной памяти, микросхемы BIOS начальной инициализации устройства, разъема монитора и источника питания.
  2. Осуществить трассировку проводников на четырех слоях печатной платы – двух питающих (питание и заземление) и двух сигнальных.

Данное устройство применяется в качестве графической подсистемы в серверных системных платах. Передача информации от процессора в оперативную память происходит по шине данных 128 бит.
Подсистема оперативной памяти процессора состоит из двух банков. Тактирование каждого банка памяти асинхронное, тактирование внутри банка – синхронное. В зависимости о внутренней организации микросхем памяти, в каждом банке может быть от одной до четырех микросхем.

Предпосылки и средства для решения проблемы
Существует много известных автоматических методов размещения компонентов и трассировки печатных проводников [1], реализованных в различных программах. Однако, и компания Mentor Graphics – производитель САПР Expedition PCB, которая обеспечивает, без преувеличения, самое высокое качество автоматической трассировки, признает, что проектирование устройств, осуществленное в автоматизированном (фактически ручном способе), по качеству на порядок выше самых продвинутых программ и автоматических алгоритмов размещения компонентов и трассировки соединений. Поэтому разработчикам реальных изделий МКП стоит обратить особое внимание на эвристические алгоритмы размещения и трассировки.


Весь  процесс  проектирования  устройства,  можно разбить на  этапы.

Первый этап размещения – это поиск стратегии размещения компонентов. Размещение компонентов подчиняется определенной стратегии, которую разработчик разрабатывает на основе конкретного технического задания, документации и руководящих технических материалов (РТМ) как на систему, так и на элементы при ограничениях по тепловым процессам и электромагнитной совместимости.
Под стратегией размещения будем понимать некий абстрактный эскиз (идею) печатной платы, с размещенными на ней «главными» компонентами. На последующих этапах эскиз будет оптимизироваться с учетом выбранных критериев оптимальности. Под главными компонентами понимаются крупные компоненты, такие как – процессоры, микросхемы, разъемы, MOSFET транзисторы и т.д.
Важно, что расстояния между главными компонентами на данном этапе роли не играют. Стратегия показывает, как будут располагаться и как будут развернуты главные компоненты друг относительно друга и краев печатной платы. Процесс поиска оптимальных вариантов стратегии можно представить виде алгоритма.
Для упрощения процесса выбора оптимального варианта стратегии размещения, необходимо рассмотреть прототипы проектируемого устройства {блок 4}. Прототипы проектируемого устройства способны дать нам необходимые варианты стратегии размещения. Усечение множества таких вариантов будет производиться путем наложения надсистемой условий и ограничений. Например, ЭМС с другими устройствами надсистемы, габаритные размеры, цена изготовления. Если же устройство проектируется впервые или прототипы не доступны по тем или иным причинам, получить множество вариантов стратегии размещения компонентов можно, используя левую часть алгоритма, изображенного на рис.1.

Рис. 1. Алгоритм поиска оптимальной стратегии размещения компонентов.

{блок 3}   Всем «главным» компонентам эвристически назначаются коэффициенты важности в порядке убывания жесткости требований по ЭМС и тепловому режиму. В нашем примере «главными» компонентами являются процессор, четыре микросхемы оперативной памяти и источник питания.
{блок 5}   Для начала формирования стратегии, необходимо получить «опорный вариант размещения», вокруг которого будут формироваться остальные компоненты. Для этого осуществляется поиск «главных» компонентов с наибольшим значением коэффициента важности, а также  имеющих наибольшее число взаимных связей. В нашем примере такими компонентами являются процессор и четыре микросхемы оперативной памяти.
{блок 6}  Осуществляется поиск всех возможных вариантов взаимного расположения ранее отобранных «главных» компонентов (множество А0). В нашем примере наиболее вероятными вариантами размещения микросхем оперативной памяти относительно процессора будут следующие (см. Рис. 2, 3, 4 и 5).


Рис. 2. Вариант 1 размещения памяти.

Рис. 3. Вариант 2 размещения памяти.

Рис. 4. Вариант 3 размещения памяти.

Рис. 5. Вариант 4 размещения памяти.


Рис. 6. Расположение групп контактов процессора

{блок 7}   Теперь необходимо усечь множество вариантов А0, наложив ограничения по ЭМС и тепловому режиму. Для удобства трассировки печатных проводников выводы процессора располагаются группами. Примерное расположение функциональных групп контактов показано на рис. 6. 
                   Из рис. 6 следует, что все остальные варианты расположения микросхем оперативной памяти, не приведенные выше – худшие и рассмотрению не подлежат, т.к. не выполняются требования ЭМС. Обратимся к вариантам, представленным на Рис.2 – Рис.6. Опишем процесс отбора оптимальных по ЭМС вариантов.

Рис. 7. Расположение источника питания в Варианте 2.

Рис. 8. Расположение источника питания в Варианте 4.

Как было сказано ранее, процессор имеет два банка памяти. Он осуществляет синхронное тактирование микросхем памяти внутри каждого банка и асинхронное для двух банков.
При размещении графической памяти по Варианту 1 (Рис. 2) длина тактирующих проводников для обоих банков памяти примерно равна, что положительно скажется на стабильности работы оперативной памяти.
Во втором варианте размещения (см. рис. 7), микросхемы памяти во втором банке находятся на разных расстояниях от соответствующих контактных групп процессора, что приводит к необходимости выравнивания по длине проводника для микросхемы «1». Выравнивание осуществляется путем многократных изгибов проводника, что повышает паразитную индуктивность и емкость такой линии передач, а также требует дополнительного места на печатной плате и может помешать нормальной трассировке шин данных. Всё это говорит о том, что этот вариант не подходит.
Вариант 3 (см. Рис. 4) обладает теми же положительными качествами, что и Вариант 1 (см. Рис. 7).
    Вариант 4 (см. рис. 8) обладает тем же недостатком, что и Вариант 2 (см. рис. 7). Этот вариант также не подходит.
            Итак, исходное множество вариантов размещения «главных» компонентов с высокими значениями коэффициентов важности А0 усечено до двух – Вариант 1 и Вариант 3, после того, как были наложены ограничения по ЭМС. Эти два варианта образуют множество А1. Область занимаемая компонентами из А1 фиксируется и на последующих шагах алгоритма поиска стратегии размещения (см. рис. 1) положение компонентов из А1 не изменяется.
{блок 8}    Снизив значение коэффициента важности, мы «открываем» другие компоненты. В нашем примере это источник питания ядра процессора.
{блок 9}    В нашем примере множество А1 включает в себя два варианта стратегии размещения и для них необходимо выбрать оптимальное расположение источника питания ядра процессора. Два варианта расположения источника питания ядра процессора показаны на рис. 9 и рис. 10. Остальные варианты не отвечают требованиям по ЭМС либо в них неэкономно расходуется пространство печатной платы.
После того, как были определены оптимальные варианты расположения источника питания, множество А1 обновляется. Теперь Вариант №1 из множества А1 содержит в себе процессор, четыре микросхемы памяти и источник питания. Тоже и с Вариантом №3.
{блок 10}  Теперь нам необходимо отсеять варианты, входящие во множество А1, не отвечающие требованиям по ЭМС, как для самой проектируемой системы, так и для надсистемы (в нашем примере это системная плата).

Рис. 9. Расположение источника питания ядра процессора при Варианте №1 размещения оперативной памяти


Рис. 10. Расположение источника питания ядра процессора при Варианте №3 размещения оперативной памяти

Питание ядра процессора осуществляется специальным источником питания, обеспечивающим до 15А при напряжении питания 2.7 В. Такой ток невозможно передать по печатному проводнику, поэтому для подведения питания используется область питающего слоя.
На рис. 9 представлено размещение источника питания при Варианте №1 расположения оперативной памяти. В этом случае размер области, занимаемой компонентами на печатной плате – минимальный, а расположение источника питания обеспечивает легкое подведение к ядру процессора питающего напряжения с помощью отдельного слоя.
            В варианте №3 (см. Рис. 10) источник питания расположен вдали от аналоговых RGB трасс, что положительно сказывается на качестве видео сигнала. Однако, размер области, занимаемой компонентами в этом варианте размещения больше, нежели в Варианте 1.
            Для того чтобы выбрать один из двух вариантов, необходимо привлечь дополнительную информацию. В нашем примере графическая система располагается непосредственно на системной плате, необходимо экономить пространство, занимаемое компонентами.  Отсюда следует, что Вариант №1 (см. рис. 9) – отвечает всем предъявляемым требованиям.
Итак, мы усекли множество А1 до единственного варианта, тем самым определив стратегию размещения «главных» компонентов – Вариант №1 (см. рис. 9).
Второй этап размещения – формирование «островов». Под «островом» будем понимать «главный» компонент, с размещенными вокруг него подчиненными компонентами более низкого уровня иерархии («обвязкой»). Как и на первом этапе, фактические расстояния между «главными» компонентами для нас не важны.
«Главные» компоненты свободно размещаются на рабочем поле САПР в соответствии с выбранной на первом этапе стратегией. Производится размещение компонентов обвязки вокруг соответствующего «главного» компонента с учетом требований по электромагнитной совместимости [2]. Если отдельные компоненты обвязки принадлежат нескольким главным компонентам, их необходимо равномерно распределить между ними, если это специально не оговаривается в документации.
После завершения второго этапа размещения на рабочем поле САПР образуются участки с повышенной концентрацией компонентов и пустые участки.
Третий этап размещения -этосближение образовавшихся островов.  Третий этап начинается с определения приоритетов направления сближения между островами, которые обусловлены заданными на первом этапе значениями коэффициентов важности ({Блок 3} алгоритма на рис. 1). Конечная цель данного этапа – как можно плотнее сблизить получившиеся острова, основываясь на выбранной стратегии размещения. Степень сближения зависит от ширины используемых в проекте печатных проводников, т.к. необходимо оставить достаточное пространство между островами для трассировки. Степень сближения оценивается разработчиком эвристически.
Кроме определения приоритетов сближения необходимо выделить центр сближения. Центр сближения – это остров, который в процессе сближения островов остается неподвижным, т.е. к которому осуществляется сдвиг остальных островов. Чаще всего это остров, образованный «главным» компонентом, расположение которого жестко оговорено либо по заданию, либо параметрами надсистемы. Например, торцевые разъемы, внешние разъемы, расположение которых строго определено форм-фактором корпуса устройства. Если же компоненты со строго заданным положением отсутствуют, центром сближения назначается компонент либо с наибольшим значением коэффициента важности, либо компонент, имеющий наибольшую степень связности.
Вышесказанное можно представить в виде алгоритма (см. рис. 11)

Рис. 11. Алгоритм сближения островов.


Рис. 12. Возможные положения источника питания ядра процессора (Остров 2).

В нашем примере, компонентов со строго заданным расположением нет, но есть компонент с наибольшей степенью связности и наибольшим значением коэффициента важности – процессор. Поэтому он и назначается центром сближения.
Следующие по значению коэффициента важности – четыре микросхемы оперативной памяти. Направление сдвига их островов по направлению к процессору определены выбранной на первом этапе стратегией размещения.
Далее следует источник питания ядра процессора (Остров 2). Расположение его острова относительно центра сближения также определяется стратегией размещения, выбранной на первом этапе. Для снижения уровня электромагнитных помех, идущих от источника питания, рекомендуется минимизировать длину трассы от источника до нагрузки. Данная минимизация так же сэкономит пространство, занимаемое графической системой на печатной плате.
Исходя из выбранной на первом этапе стратегии размещения, остров источника питания (Остров 2) (см. рис. 12) располагается между Островом 3 (центр сближения) и Островом 1Г. Серым прямоугольником показаны примерные габариты острова источника питания. Габариты Острова 2 таковы, что позволяют смещать его на величину Δ. Большее, чем указанное на рисунке смещение Δ, нецелесообразно, т.к. теряется полезное пространство на печатной плате.
Итак, к концу третьего этапа определены (но не окончательно) положения островов и трассированы печатные проводники внутри каждого острова.
            Четвертый этап размещения предполагает осуществление процесса переразмещения мелких компонентов, трассировки и перетрассировки соединений. На этом этапе, ранее размещенные мелкие элементы, с учетом про­кладываемых трасс, могут быть или смещены, или перемещены на другие места, обеспечи­вающие более рациональное формирование межсоединений. Трассировка осуществляется эвристически по визуально выделенному полю с соблюдением общих правил [2] и требований по ЭМС.
Порядок трассировки также подчиняется порядку значений коэффициентов важности, т.е. острова с высоким значением коэффициента важности трассируются в первую очередь. Процесс трассировки печатных проводников между островами представлен на рис. 13 в виде эвристического алгоритма.

Рис. 13. Алгоритм трассировки соединений на Этапе 4.

Окончательно «островной» способ размещения и трассировки можно представить в виде обобщенного алгоритма см. Рис. 14.

Рис. 17. «Островной» алгоритм размещения и трассировки компонентов

 

Заключение
Решаемая задача топологического проектирования в среде САПР P-CAD актуальна для многих приложений проектирования конструкций многослойных коммутационных плат РЭА и ЭВА, а идеи, положенные в основу разработанной методики, такие как: разбивка всех компонентов на «главные» и «обвязку», назначение коэффициентов приоритета, привлечение многокритериального выбора в процесс проектирования, являются оригиналь­ными и содержат новые элементы. Разработанная методика неоднократно докладывалась на научных семинарах и международных конференциях, использовалась при разработке МКП в ряде предприятий. Она использована в учебном процессе и практическом проектировании в Московском энергетическом институте МЭИ (ТУ). Некоторые фрагменты её можно найти на сайте www.pilab.ru в разделе УМК–Радиотехника–Конструирование и технология производства РЭС.  По работе имеется четыре акта о внедрении научных результатов.
Предлагаемая в работе методика основана на эвристическом формировании несколь­ких альтернативных вариантов создания топологии «островов» и размещении подчиненных элементов внутри них. Подобный подход позволяет осуществить многовариантное проек­тирование МКП и последующее сравнение выдвинутых гипотез о рациональности конст­руктивных решений по критериям минимальной суммарной длинны и максимальной связ­ности элементов, как внутри образований, так и «островов» между собой. Разработанный алгоритм универсален он позволяет проектировать печатные платы с любым количеством слоев для РЭС и ЭВА.

Литература

    "", 6, 2008 .