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

вать подпроцессы различных уровней иерархии, реализуемые

на каждом /V -ом шаге процесса имеется некоторое множест­ во преобразований ^ = которые различаются своим результатом для множества состояний проекта на данном ша­ ге, являющихся различными вариантами решения частной зада­ чи проектирования. Для состояния системы на Ся+1) шаге бу­ дем иметь:

Цель решаемой задачи - найти наиболее предпочтительную последовательность подпроцессов, позволяющую учесть все предъявляемые к проекту требования. В интерактИЕНо-алгарит­ мическом методе проектирования вмешательство человека поз­ воляет выработать нетривиальные решения. Из ?того следует, что при определении оптимального маршрута целесообразно ис­ пользовать пошаговые методы нахождения наиболее предпочти­ тельного пути. Основная функция системы - помочь человеку в сложных и неопределенных ситуациях выбрать решения, со­ гласованные с системой его предпочтений, за счет применения методов, позволяющих избежать логи* эских ошибок в длинных цепях рассуждений.

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

-общность для всех допустимых решений;

-значимость в отношении конечного результата, призна­ ваемая пользователем.

21

мальным является маршрут, для которого функция /сл макси­ мальна, а для любого другого маршрута

Ал (Joj О*') sXnVojO V .

Функция оценки имеет аддитивный характер [3] и являет­ ся взвешенной комбинацией различных показателей, которые условно можно разбить на две группы: конструктивно-техноло­ гические характеристики объекта проектирования и технические характеристики, указанные в техническом задании*

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

Для нахождения оптимального маршрута можно воспользо­ ваться принципом Веллмана [4J, согласно которому последу­ ющее. преобразэвание должно быть оптимальным относительно состояния, являющегося результатом применения начального преобразования P0j каковы бы ни были начальное состояние J0 и начальное преобразование Таким образом, для вы­ бора оптимального на данном шаге оператора должно выпол­ няться условие

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

1. Планирование, При эксплуатации системы в архиве на-

22

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

2. Анализ "средства-цели*. Выбор очередного оператора осуществляется на основе сопоставления текущей ситуации и цели так* чтобы максимально уменьшить различие между нюми* Снижение сложности подзадачи выбора очередного опера­ тора при применении анализа "средства-цели" достигается за счет использования для выбора оператора той информации, ко­ торая содержится в описании целей.

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

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

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

системы автоматизированного проектирования происходит в про­ цессе разработки реального проекта.

Первый аспект этой проблемы связан с тем, что увеличе­ ние количества альтернативных автоматических и интерактцв-

23

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

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

основываться на принципах и нормах теории инженерной психо­ логии, эргономики и дидактики.

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

Знание закономерностей поведения объекта проектирования на различных этапах процесса разработки проекта позволяет прогнозировать возможное развитие событий, оценивать эпти-

24

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

Примером обучающей функции может служить выполнение программы начального размещения элементов проектируемой схемы на ПП [ 6 ], сопровождающегося анализом возможности установки в зоне очередного элемента связанных с ним, но еще не размещенных элементов. Если результаты анализа от­ рицательны, конструктору рекомендуется обратить внимание на* этот элемент; при этом указывается область, наиболее при­ годная в данной ситуации для размещения элемента в интерак­ тивном режиме.

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

Ли т е р а т у р а

г.ДМИТРЕВИЧ Г.Д., АНТРОПОВ А.Н., СТРЕЛЬНИКОВ Ю.Н. Вопросы интерактивного взаимодействия в комплексной САПР конструктивных узлов электронной аппаратуры. - В кн.: Авто­ матизация конструкторского проектирования в радиоэлектрони­ ке и вычислительной технике. Межвуз. сб, научн. тр. - Виль­

нюс, 1983,. т. 3, с. 4 1 -4 6 .

2. ОЙХМАН Е.Г., ГОРДОН Л.Г., ЖУКОВ В.А. и др. Мо­ дульная автоматизированная интерактивная система для проек­ тирования печатных плат на базе СМ ЭВМ. - В кн.: Автома­ тизация проектирования СМ ЭВМ. Сб. научн. тр. / ИНЭУМ. - М., 1982, вып. 93, с. 58-66*

3. КИНИ Р.Л., РАЙФА' X. Принятие решений при многих критериях: предпочтения и замещения. - М., Рацио и связь, 1981.

4. МАКАРОВА И.М., ВИНОГРАДСКАЯ Т.М., РУБЧИН-г

25

СКИЙ А,А., СОКОЛОВ В.Б. Теория выбора и принятия реше­ ний. - M.f Наука, 1982 .

5. ГЛАЛУН В.П. Эвристический поиск в сложных средах, - Киев, Наук, думка, 1977 .

6. ПОЛЫЦИКОВА И.В., СТРЕЛЬНИКОВ Ю.И. Повышение эффективности процесса размещения в диалоговых САПР печат­ ных плат. - В кн.: Автоматизация конструкторского проекти­ рования РЭА и ЭВА.:Тез. цокл, научн.-техн. конф. - Пенза, 1984, с. 7 2 -7 8 .

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

КРИТЕРИИ РАВНОМЕРНОГО РАЗМЕЩЕНИЯ

В.А. Жи ля ви чюс , Р.Й. Б а л т р у ш а й т и с

Введеиие, Одной из наиболее важных проблем на этапе конструкторского проектирования узлов радиоэлектронной и вычислительной аппаратуры (РЭА и ЭВА) является достиже­ ние полной трассировки соединений между размещаемыми эле­ ментами этих узлов. Разделение решаемых задач: компонов­ ки, размещения, трассиров1Ш, редактирования - связано с прак­ тической невозможностью совместного их решения. Разделени­ ем удается уменьшить сложность решаемых задач. Однако, при этом возникает новая проблема - согласование критериев, применяемых при решении отдельных задач.

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

2 6

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

Постан£вка_задачи. Задачу размещения элементов на пло­ скости монтажного пространства можно формулировать следу­

множество цепей G=[fa C=l7uj определенных на подмножест­

Необходимо найти такое отображение 4 * 6 * ,при котором

F a *>~F3 min

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

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

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

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

2 7

В методах, использующих для оценки длины соединений, списки цепей, подсчитываются полупериметры прямоугольников, покрывающих все контакты отдельных целей:

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

Как показывают результаты экспериментальных исследова­ ний, приведенные в [2 , 3 ], использование различных оценок длины (1), (2) и др. приводит к одинаковым конечным резуль­ татам. То есть минимизация но одному из этих критериев при­ водит к уменьшению и других.

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

Другие_эцсшщ.. Ряд работ основан на разделении МП и проектируемой схемы на части и размещении элементов каж­ дой части схемы в соответствующей области МП. В алгоритме, предложенном Гинзбургом [5 ], вначале МП и множество раз­ мещенных элементов делятся на две одинаковые части. При этом разделение элементов проводится с тем, чтобы минимизи­ ровать число соединений между отдельными частями. Деление продолжается до тех пэр, пока в одной части не остается один элемент, а соответствующая область МП содержит одну пози­ цию для его размещения.

Основательными работами, в которых исследованы различ­ ные стратегии этого подхода, называемого методом сечений, являются работы Брейера [б]. Суть метода сечений состоит в следующем.

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

2 8

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

Однако, методы минимальных сечений не гарантируют рав­ номерного распределения соединений на отдельных участках сечения, хотя в целом загруженность сечения может оказать­ ся минимальной [7J.

В работе [ 8] при размещении элементов преследуется цель равномерной загрузки областей и минимизации суммарной дли­ ны соединений. Используется так называемое значение обла­ сти - сумма длин частей соединений, проходящих заданную об­ ласть (J - площадь области, £^ - сумма длин соединений в

С -ой области). Введено понятие порога - желаемое заполне­

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

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

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

Используя при размещении методы сечений, применяется простое правило: считается, что трасса цепи пересекает сече­ ние один раз, если контакты исследуемой цепи находятся в

29

разных сторонах сечения, хотя после трассировки число пере­ сечений может оказаться и больше.

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

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

Пусть контакты одной исследуемой цепи находятся в пре­

соединений цепи будет минимальной длины, то трасса займет R дискретов из общего числа дискретов прямоуголь­ ника <5* Если предположить, что любые дискреты могут быть заняты трассой с одинаковой вероятностью, то эта вероят­ ность P=R/Q. Однако, это предположение имеет две неточности:

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

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

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

Алгоритмы трассировки обычно стараются провести трас­ сы более простой конфигурации, т.е. не все конфигурации ис-

3 0