книги / Автоматизация конструкторского проектирования в радиоэлектронике и вычислительной технике. Автоматизация конструкторского проектирования вычислительной техники

5. БАТИЩЕВ Д.И., МОРОЗОВ В.Ф., АСЛАНОВ А.А. Гео- метрический метод трассировки печатных проводников на дис­ кретном рабочем поле, - В кн.: Вычислительная техника, те­ зисы докладов, Каунас, 1081, с. 119 -121,

УДК 6 2 1 .0 4 9 .7 5

ОПТИМАЛЬНОЕ РАЗМЕЩЕНИЕ ЭЛЕМЕНТОВ НА ПЛАТЕ

В.Г, М а р аг и н, Б.Н. Д е н ь д о б р е н к о

В процессе размещения элементов на платах решаются две задачи: выбора очередного элемента и выбора места на плате для его размещения. Исходными данными для выбора места размещения являются:

1. Списки очередности размещения элементов» Каждый список содержит перечень очередных элементов,

целей и фрагментов цепей, размещаемых на очередном шаге. Количество списков очередидети не более N - числа элемен­ тов в данной схеме.

2. Модель монтажной платы (МП) и модели элементов. Динамическая модель МП описана в [1J. По моделям рас­

считываются оценки для каждого возможного места размеще­ ния и производится выбор места.

3. Описание мест размещения элементов, устанавливаемых на плате по другим критериям или соображениям.

Очевидно, что такие элементы должны размешаться на од­ ном шаге. Их размещение не зависит от связности схемы, они являются конструктивно связными, и образуют комплекс. Нали­ чие таких комплексов существенно ограничивает число возмож­ ных вариантов размещения. Кроме того, для любого элемента может быть задана определенная зона на плате, где этот эле­ мент должен быть размешен (или наоборот, где его размеще­ ние запрещено).

Выбор места размещения является оптимальным по задан­ ному критерию для определенной схемы (описывается списком очередности) и конструктивных ограничений (описываются мо­ делями плат и элементов, а также заданным расположением некоторых элементов и цепей).

11

Разновидности фронта размещения

X. Плоский

—

ф ф ф

ф ф ф X ф ф

ф X X X X ф

Круглый

Рис. X

Формирование фронта размещения

Во фронт размещения должно входить столько мест, что­ бы их число было не меньше числа размещаемых на данном шаге элементов. Оценка этих мест должна быть минимальной» но в случае размещения нескольких элементов, оценки могут иметь и разные значения. При этом во фронт размещения вклю­ чаются все места, имеющие оценки меньше или равные макси­ мальной оценке места данного фронта размещения. После*ис­ следования смежных мест для каждого размещаемого на дан­ ном шаге элемента имеется множество мест, имеющих мини­ мальную оценку.

При выборе мест размещения на данном шаге возможны следующие варианты:

1. Размешается один элемент.

2. Размешается несколько элементов, не связанных меж­ ду собой.

3. Размещается несколько элементов, связанных между собой.

Поскольку на каждом шаге возможно получение несколь­ ких оптимальных вариантов, то необходимо исследовать все возможные. Процесс размещения получается ветвящимся. С вычислительной точки зрения наиболее простой первый случай. Если во фронт размещения входит несхолько мест с одинако­ вой минимальной оценкой, TD получаем соответственно несколь­ ко вариантов размещения. Во втором й третьем случаях нахо­

решается методами целочисленного линейного программирова­ ния, но в отличие от применяемых методов необходимо иссле­ довать все возможные варианты сочетаний мест с минималь­ ной суммарной оценкой. В третьем случае необходимо учесть оценки расположения между выбранными местами размещения. ,пля этого также можно использовать аппарат линейного прог­ раммирования.

Наиболее простой случай размещения тот, когда список

14

на любой ЭВМ, применяемой для САПР, Кроме того, имеется значительный резерв для уменьшения числа вычислений, если применить метод ветвей и границ.

Очевидно, что сумма оптимальных оценок размещения по всем шагам имеет естественный нижний предел. Этот предел можно найти из конструктивных соображений. Оценка спедине-. ния будет минимальной, есливыполнить это соединение без учета'возможных ограничений со стороны других цепей. Она будет физическим пределом оценки данного Соединения при за­ данных конструкциях элементов и' ограничениях. Рассчитав за­ ранее такие оценки и зная оценку оптимального размещения, можно для каждого шага найти нижнюю границу суммы оценок

Граничная оценка зависит только от электрической схемы и одинакова для'любого сйиска очередности. Такая оценка дает некоторую избыточность вариантов на первых шагах размеще­ ния и быстро отрезает нерациональные ветви на последующих, что не совсем рационально. Как раз следовало бы сделать на­ оборот. На первых шагах размещения, когда конструктивных ограничений еще мало (поле размещения свободно) связи бу­ дут реализовываться более близкими к их нижней границе, к концу же размещения величины оценок будут сдвигаться к верхней границе. Кроме того, связи внутри сильносвязаниых симплексов также реализуются более рационально, т.е. ближе

нижней границе оценки. Поэтому границы рационально сни-

16

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

где Pj - число цепей и фрагментов, размещаемых на j шаге по L списку. Можно еще несколько дифференцировать оценку по шагам, введя разный коэффициент увеличения оценки цепи и фрагмента при их реализации в смежных или несмежных по­ зициях. Недостатком такого коэффициента будет необходимость статистических исследований для его нахождения. Только при анализе первого сг гска очередности величина QQ неизвестна. Но так как для данной схемы и конструктива

СО-ГО

то, имея некоторую статистику, можно применить этот коэф­ фициент при вычислении первого оптимального варианта для' ограничения числа рассматриваемых вариантов. Конечно, при этом есть некоторый статистический риск, если величина ес£ слишком мала, то можно вообще не получить решения. Тогда величину надо увеличивать до тех пор, пока решение не бчгдет получено.

Таким образом, если оценка варианта на данном шаге пре­ вышает CSTij J то исследование этой ветви прекращается, и число операций по вычислению оценок уменьшается.

Решение ряда примеров показало, что любой список оче­ редное* и приводит хотя бы к одному оптимальному размеще­ нию. Эффективность по сравнению с САПР "Рапира 5.3": но плата*: размером 80x100 мм сумма длин соединений и число переходных отверстий уменьшаются в 1,8-2 раза. При разме­ щении разногабаритных элементов рационально использовать непрерывную модель МП. При этом изменяются только форму­ лы вычисления оценок мест размещения.

Ли т е р а т у р а

1.МАРАГПН В.Г., ДПНЬДОБРЕНКО Б.Н. Динамическая

17

модель монтажного узла, Сб.: "Автоматизация технического проектирования цифровой аппаратуры". Каунас, 1984, с. 7 2 - 73.

2. МАРАГИН В.Г., ДЕНЬДОБРЕНКО Б.Н. Оптимальное размещение элементов на плате по минимаксной стратегии. "Автоматизация конструкторского проектирования РЭА и ЭВА". Тезисы докладов к областному семинару. Пенза, ГЩНТП, 1983, 5 6 -5 8 .

УДК 6 8 1 .5 .0 0 1 .2 :6 2 1 .3 8

МЕТОДИЧЕСКИЕ ПРОБЛЕМЫ КОНСТРУИРОВАНИЯ ПЕЧАТНЫХ ПЛАТ В ДИАЛОГОВЫХ САПР

Ю.Н. С т р е л ь н и к о в , И.В. П ольщ и кова, Г.Д. Д м и т р е в и ч

Современный этап развития САПР характеризуется приме­ нением двух основных подходов к конструированию печатных плат (ПП). Первый подход связан с выполнением автоматиче­ ских проектных процедур на универсальных ЭВМ класса ЕС и БЭСМ, второй - с организацией проектирования ПП в интер­ активных минимашинных САПР на базе комплекса АРМ-Р.По­ вышение эффективности систем обоих типов связывается,глав­ ным образом, с совершенствованием компонентов техническо­ го обеспечения. Вместе с тем для сложившейся в настоящее время ситуации в области конструирования печатных плат ха­ рактерно смещение акцентов в деятельности разработчиков САПР на решение широкого круга актуальных организационных и методических вопросов, связанных с поиском новых органи­ зационных форм автоматизированного проектирования.

Одной из таких организационных форм явилось совмеще­ ние в едином процессе автоматических процедур формирования проектных решений и интерактивных процедур оценки и редак­ тирования сформированного проекта. Такой подход взят на во­ оружение как ведущими западными фирмами Computeri/csioftj Repас, Appficorr и др., так и в нашей стране [1, 2].

Возможности, которые открываются в этом подходе, сво­ дятся к следующему:

18

- проектировщику предоставляется возможность оператив­ ного выбора одной из широкого набора автоматических или ин­ терактивных процедур в зависимости от сложившейся проект­ ной ситуации;

- текущие проектные решения постоянно отображаются на экране графического дисплея в форме, удобной для оценки их качества, и обновляются с интервалами времени, которые не­ обходимы для завершения выполнения заданной процедуры.

Результаты эксплуатации таких САПР подтвердили их вы­ сокую эффективность, гибкость, снижение доли нетворческой работы конструктора, простоту обучения пользователей, и вме­ сте с тем выдвинули ряд проблем методического обеспечения, включающего правила отбора и эксплуатации средств проекти­ рования.

Сущность первой проблемы заключается в выборе опти­ мальной глубины штерактивногэ взаимодействия человека с системой. Фактически каждый уровень иерархической структу­ ры процесса может быть охвачен контролирующими и регули­ рующими действиями пользователя. Однако охват таких боль­ ших этапов процесса, как проектные процедуры компоновки,- размещения, трассировки и т.д., облагает недостатком, заклю­ чающимся в высокой вероятности появления неудачных реше­ ний (фрагментов топологии печатного монтажа) на ранних ста­ диях выполнения этих этапов. При такой организации диалога Человек не имеет возможности выявить эти решения, а устра­ нение их после выполнения всей процедуры становится чрез­ вычайно трудоемкой задачей.

С другой стороны, спускаясь вниз по иерархической струк­ туре процесса автоматизированного проектирования, можно контролирующими дейстзнями конструктора охватить очень меллие этапы процесса, например, элементарные действия типа перебори возможных позиций для размещения элемента ^ це­ лью определения оптимальной, рсспространения волны или лу­ чей при прокладке соединения и т.д. Однако в этом случае резко возрастает доля времени работы процессора, необходи­ мого для обновления на Эд1ране графического изображен я,что снижает эффективность работы автоматических процедур. Кро­ ме того, частота обновления этого изображения может превы­ сить эргоном1 1ескче и психологические нормы организации ди­ алогового взаимодействия - человек просто не сможет физиче­ ски оценивать качество выполняемого проекта.

19

Таким образом, можно утверждать, что стремление к ох­ вату больших и малых этапов процесса контролем человека не является оптимальным с точки зрения организации интерактив­ ного взаимодействия. Нахождение же "золотой середины" при­ водит к решению донной проблемы, относящейся к классу за­ дач инженерной психологии, распознавания образов и искусст­ венного интеллекта.

Подтверждение выбранного оптимума может быть осуще­ ствлено экспериментально путем хронометрирования процессов проектирования на тестовых задачах в различных САПР,

Вторая методическая проблема заключается в формирова­ нии оптимальных маршрутов проектирования. Эта проблема складывается из следующих составляющих:

-сформировать и классифицировать исчерпывающий на­ бор альтернативных модулей проектирования;

-разработать систему правил выбора дальнейшего направ­ ления проектирования по результатам оценки текущей проект­ ной ситуации;

-снабдить конструктора специальными средствами для принятия решений по информации, отображаемой на экране гра­ фического дисплея.

Для формирования исчерпывающего набора альтернативных модулей проводится декомпозиция процесса проектирования. Ориентация САПР на различные типы объектов проектирования приводит к необходимости введения на ряде этапов процесса наборов альтернативных программных модулей, классифициро­ ванных по классам решаемых задач,- применяемым критериям, времени и точности решения, возможности учета различных конструктивно-технологических ограничений.

Использование набора проектирующих алгоритмов на. ряде этапов проектирования, а также предоставление конструктору возможности чередования автоматических и интерактивных про­ цедур ставит задачу разработки свода правил для выбора даль­ нейшего направления проектирования. Результатом выполнения любого подпроцесса является изменившееся состояние проекта, которое характеризуется наличием различий между текущим и конечным (желаемым) состояниями, являющимися вершинами графа решения задачи конструкторского проектирования. Пере­

20