книги / Автоматизация конструкторского проектирования в радиоэлектронике и вычислительной технике. Автоматизация конструкторского проектирования вычислительной техники
.pdfвать подпроцессы различных уровней иерархии, реализуемые
автоматическими и/или интерактивными программами. |
|
|
Тогда, если |
состояния проекта, О- |
} |
- множество операторов, |
Р6‘ - некоторое преобразование, |
то |
на каждом /V -ом шаге процесса имеется некоторое множест во преобразований ^ = которые различаются своим результатом для множества состояний проекта на данном ша ге, являющихся различными вариантами решения частной зада чи проектирования. Для состояния системы на Ся+1) шаге бу дем иметь:
Цель решаемой задачи - найти наиболее предпочтительную последовательность подпроцессов, позволяющую учесть все предъявляемые к проекту требования. В интерактИЕНо-алгарит мическом методе проектирования вмешательство человека поз воляет выработать нетривиальные решения. Из ?того следует, что при определении оптимального маршрута целесообразно ис пользовать пошаговые методы нахождения наиболее предпочти тельного пути. Основная функция системы - помочь человеку в сложных и неопределенных ситуациях выбрать решения, со гласованные с системой его предпочтений, за счет применения методов, позволяющих избежать логи* эских ошибок в длинных цепях рассуждений.
Для упорядочения перебора вершин используется функция оценки, которая должна обеспечить выделение вершины, с наи большей вероятностью лежащей на пути к цели. В качестве критериев используются показатели, к которым предъявляются следующие требования:
-общность для всех допустимых решений;
-значимость в отношении конечного результата, призна ваемая пользователем.
Пусть |
/>, - значение функции |
оценки на шаге причем |
= f(S nJQ„). Тогда качество маршрута можно оценить как |
||
|
к м , **J= % r e s e a t ) , |
|
где 0* - |
последовательность операторов, с помощью кото |
|
рых система пришла в состояние |
о** { а09...j O^^tfciO.Oxww- |
21
мальным является маршрут, для которого функция /сл макси мальна, а для любого другого маршрута
Ал (Joj О*') sXnVojO V .
Функция оценки имеет аддитивный характер [3] и являет ся взвешенной комбинацией различных показателей, которые условно можно разбить на две группы: конструктивно-техноло гические характеристики объекта проектирования и технические характеристики, указанные в техническом задании*
Кроме того, одно из слагаемых функции оценки должно учитывать последовательность подпроцессов, в результате вы полнения которых система пришла в рассматриваемое состояние. Необходимость введения этого слагаемого объясняется целесообразностью учета особенностей проектирующих алгорит мов с точки зрения достижения конечного результата* Так,на пример, после использования алгоритмов размещения на непре рывной монтажной плоскости более эффективным будет приме нение различных модификаций волнового алгоритма по сравне нию с лучевым.
Для нахождения оптимального маршрута можно воспользо ваться принципом Веллмана [4J, согласно которому последу ющее. преобразэвание должно быть оптимальным относительно состояния, являющегося результатом применения начального преобразования P0j каковы бы ни были начальное состояние J0 и начальное преобразование Таким образом, для вы бора оптимального на данном шаге оператора должно выпол няться условие
|
F(Sn)0„)~Argmax |
[f(S^O ')]J |
|
|
где £ |
- количество различных состояний проекта |
на л |
-ом |
|
шаге процесса проектирования,^,^ |
- j -эе состояние |
и |
||
J -ый |
оператор на л -ом шаге соответственно. |
|
|
|
Поиск оптимального маршрута осуществляется |
последова |
тельно, при этом на каждом шаге производится выбор очеред ного локально оптимального оператора решения. Сложность подзадачи выбора возрастает с ростом объема поиска решений и уменьшением количества информации о цепочках операторов, ведущих к цели. Возможны различные стратегии поиска [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
выступать и в качестве функции цели при оптимизации разме щения в итерационных алгоритмах, использующих замены равногабаритных элементов.
Постан£вка_задачи. Задачу размещения элементов на пло скости монтажного пространства можно формулировать следу
ющим образом. |
|
Задано множество размещаемых элементов £* |
},i= rJ7t; |
множество цепей G=[fa C=l7uj определенных на подмножест
вах этих элементов; множество позиций на МП Р- |
Л i- |
л? } пj мнЬжеств о всех в озможных отображений R = |
jj i * |
заданного множества элементов в множество позиций |
р мон |
тажного пространства. |
|
Необходимо найти такое отображение 4 * 6 * ,при котором
F a *>~F3 min
при соблюдении заданных ограничений. Здесь F - критерий оптимизации при размещении. В качестве ограничений могут выступать требования на длину соединений, на расстояние меж- t ay заданными элементами и др. Некоторые из этих ограниче ний могут быть составной частью интегрированного критерия.
Задача состоит в выборе такого критерия оптимизации Fj который наилучшим образом, учитывал бы требования последу ющей задачи трассировки соединений. Степень пригодности критерия можно определить процентом построенных соединений •после проведения трассировки.
В большинстве методов размещения элемен тов для печатного монтажа используются различные оценки длины. Для определения длины соединений перед трассировкой предполагается задание числа соединений между различными
парами элементов матрицей |
соединений f t ] . Тогда длина со |
|||
единений |
оценивается следующим образом: |
|
||
|
|
~ |
SiJ аim icj>1 |
( l ) |
где |
Sij |
- число соединений мёжду элементами |
и еу; |
|
|
'* |
“ Расст£>яние между позициями 4(c) , |
кото- |
|
|
рых размещены элементы в; и Су |
|
||
Для |
использования суммарной длины соединений |
(1) в ка |
честве критерия задачи размещения необходимо уже перед раз мещением определить связывающие деревья для цепей, содер жащих более двух контактов.
2 7
В методах, использующих для оценки длины соединений, списки цепей, подсчитываются полупериметры прямоугольников, покрывающих все контакты отдельных целей:
|
SeO |
*Ul f тахЫ Г m inh t i ) ; ’ |
(2) |
|
4**3 |
|
|
|
|
|
|
где |
|
к00РДииатьг позиции £ и ) . |
|
Более |
сложные оценки ожидаемой длины соединений учи |
тывают число контактов, цепи, конфликтность соединений от дельных цепей, а также используют более точные способы оп ределения конф.ггурации, чем покрывающие прямоугольники.
Как показывают результаты экспериментальных исследова ний, приведенные в [2 , 3 ], использование различных оценок длины (1), (2) и др. приводит к одинаковым конечным резуль татам. То есть минимизация но одному из этих критериев при водит к уменьшению и других.
Неудачи при трассировке в большинстве случаев обуслов лены перегрузкой некоторых областей МП [4 ]. В то же вре мя все алгоритмы размещения, проводящие оптимизацию по критериям на основе длины соединений, производят стягивание сильно связанных' между собой элементов, что приводит к пе регрузке отдельных областей.
Другие_эцсшщ.. Ряд работ основан на разделении МП и проектируемой схемы на части и размещении элементов каж дой части схемы в соответствующей области МП. В алгоритме, предложенном Гинзбургом [5 ], вначале МП и множество раз мещенных элементов делятся на две одинаковые части. При этом разделение элементов проводится с тем, чтобы минимизи ровать число соединений между отдельными частями. Деление продолжается до тех пэр, пока в одной части не остается один элемент, а соответствующая область МП содержит одну пози цию для его размещения.
Основательными работами, в которых исследованы различ ные стратегии этого подхода, называемого методом сечений, являются работы Брейера [б]. Суть метода сечений состоит в следующем.
Если монтажное пространство разделить сечением на две области, то число соединений, проходящих это сечение, можно оценить числом цепей, соединяющие контакты которых находят ся в различных областях. Тогда загруженность такого сечения
2 8
соединениями можно минимизировать путем перестановки эле ментов из разных сторон этого сечения.
Однако, методы минимальных сечений не гарантируют рав номерного распределения соединений на отдельных участках сечения, хотя в целом загруженность сечения может оказать ся минимальной [7J.
В работе [ 8] при размещении элементов преследуется цель равномерной загрузки областей и минимизации суммарной дли ны соединений. Используется так называемое значение обла сти - сумма длин частей соединений, проходящих заданную об ласть (J - площадь области, £^ - сумма длин соединений в
С -ой области). Введено понятие порога - желаемое заполне
ние площади |
области соединениями в процентах *(Т - порог). |
||||
Область i |
переполнена, |
если |
J |
Функция цели F = gf. t |
|
где |
|
|
|
|
с |
|
, |
/ ° . е с л И 4 |
^ |
|
|
|
|
|
j 6 противном |
случае. |
|
Если |
А о , минимизируется только |
суммарная длина соединений. |
|||
Если |
Т> О, минимизируется суммарная перегруженность пере |
полненных областей. В работах приведены экспериментальные исследования предложенного метода. Они показывают, что ре зультаты последующей трассировки (в смысле разведенных со единений) значительно лучше, чем для размещения, получен ного jio критерию суммарной длины соединений.
Однако предложенный метод не учитывает пропускной спо собности отдельных областей ЛАП Поэтому он применим толь ко для регулярного размещения позицпониых равнэгабарцтных элементов с однородной структурой ЛАП
ниости _этдельных^участков_ЛАП. При любом способе оценки качества размещения необходимо прог нозировать возможную конфигурацию трасс соединений различ ных цепей. Однако, даже четкое представление правил после дующей трассировки не позволяет без ее проведения устано вить точную конфигурацию трасс. Поэтому приходится пользо ваться вероятностными методами, когда определяется вероят ность прохода трассы цепи через определенные области.
Используя при размещении методы сечений, применяется простое правило: считается, что трасса цепи пересекает сече ние один раз, если контакты исследуемой цепи находятся в
29
разных сторонах сечения, хотя после трассировки число пере сечений может оказаться и больше.
Сложнее обстоит дело, если требуется определить загру женность отдельных областей МП или частей сечений. Рассмот рим возможные способы решения возникающих при этом задач. Будем базироваться на предположении, что трассы соединений одной цепи будут проведены в пределах некоторого прямоуголь ника, включающего все контакты исследуемой цепи.
Пусть МП разбито на множество квадратных дискретов. Их размеры определяются размерами контактов, межслойных переходов и шириной трасс, а также требуемыми зазорами.Да лее все размеры на МП будут выражаться в дискретах прямо угольной метрики.
Пусть контакты одной исследуемой цепи находятся в пре
делах минимального прямоугольника |
s (покрывающего прямо |
|
угольника) со сторонами а и ^.Обозначим через |
/? полупери- |
|
метр покрывающего прямоугольника, |
т.е. |
Если трасса |
соединений цепи будет минимальной длины, то трасса займет R дискретов из общего числа дискретов прямоуголь ника <5* Если предположить, что любые дискреты могут быть заняты трассой с одинаковой вероятностью, то эта вероят ность P=R/Q. Однако, это предположение имеет две неточности:
1. Вероятность загрузки больше у дискретов, находящих ся ближе к соединяемым контактам.
.2. Если в разных слоях заданы преимущественные направ ления трасс (горизонтальные или вертикальные), то вероят ность'загрузки дискретов в разных слоях неодинакова. В этом случае, по аналогии с методами сечений, ожидается, что трас
са проходит вертикальное |
(горизонтальное) |
сечение прямоуголь |
||
ника J |
в горизонтальном |
(вертикальном) |
слое одир раз. Тог |
|
да вероятность загрузки дискрета горизонтального слоя рав |
||||
няется |
Г/д \ вертикального - |
f/a |
|
Для учета неравномерной загрузки дискретов возможны два способа: а) считать, что одинаково вероятно использова ние из множества всевозможных конфигураций в прямоуголь нике J трассы некоторой конфигурации минимальной длины, или б) считать, что при проведении трассы от некоторого кон такта вероятность перехода к соседним дискретам одинакова.
Алгоритмы трассировки обычно стараются провести трас сы более простой конфигурации, т.е. не все конфигурации ис-
3 0