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

в модели соответствуют модельные ребра с ненулевой пропуск­ ной способностью.

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

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

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

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

Введем формальное определение оператора туннелирования (QT). Пусть 6 СХ,а) - максимальный плоский подграф схемы, являющийся исходным графом для этапа планаризации. Разо­

купности двух непересекающихся подмножеств: множества мо­

Применение оператора туннелирования приводит к появле­ нию дополнительных вершин двух видов:

- отображающих фиктивные контакты у элементов - они появляются в модели элемента после проведения проводника между соответствующими контактами туннелируемого элемен­ та (обозначим множество таких вершин через //* );

101

- отображающих шлгшшителькую цепь, реализующую вос­ становленное ребро (обозначим множество таких вершин че­ рез X j\

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

Ojy^jpjenejnxe^^. Оператором туннелирования называется

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

Лит е р а ту р а

1.ПЕТРЕНКО А.И., ТЕТЕЛЬБАУМ А.Я., ШРАМЧЕНКО Б Л Автоматизация конструирования электронной аппаратуры. - Ки­

методы автоматизированного конструирования электронных уст­ ройств. - Львов: Вища школа, 1981 . - 167 с.

4 . АБРАЙТИС Л.Б. Метод планаризации моделей электри­ ческих схем. - В сб. "Автоматизация технического проектиро­

p. 8 2 - 9 0 .

1 02

10. КОНСТРУИР(ЖАН1Ш и технологик микросхем / Под редакцией Коледова Л.А. - М.: Высшая школа, 1984 . - 2 3 Ос. 11 СЕЛЮТИИ В. А. Модели и алгоритмы синтеза топологии схем с одним слоем коммутации. - Электронная техника, се­

рия 10, 1 9 7 8 , N° 17.

УДК 6 8 1 .3 :5 1 9 .8

ПОИСК БЛИЖАЙШЕЙ ТОЧКИ ПРИ ГРАФИЧЕСКОМ РЕДАКТИРОВАНИИ ТОПОЛОГИИ ИС

Л«В. Но с о в Подсистема графического редактирования является состав­

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

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

1 0 3

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

Таким образом, при графическом редактировании возникает следующая задача: среди А/ точек на плоскости найти ближай­ шую к данной. В Г2] она упоминается как задача поиска бли­ жайшего города, в [3] как задача о ближайшей точке. Триви­ альное решение этой задачи путем просмотра всех точек зани­ мает значительное время при больших /1/, и потому неприем­ лемо для редактирования в интерактивном режиме топологий БИС. Для графического редактирования топологии БИС необ­ ходима структура данных, которая обеспечивает эффективный п^иск ближайшей точки. Эта структура должна также обеспе­ чивать эффективное выполнение операций удаления и вставки точки, поскольку операции удаления и вставки элемента черте­ жа сводятся к соответствующим операциям над его угловыми (или концевыми) точками.

Извести , что для точек на прямой структура данных ти­ па бинарного сбалансированного дерева [4] позволяет осуще­ ствить поиск ближайшей точки, операции удаления и вставки за время 0 ( в худшем случае, и требует 0(#) памяти. На плоскости структурой данных, отражающей отношение близости, является так называемая диаграмма Вороного £.3]. Она опре­

которая содержит некоторую заданную точку. Отсюда вытека­ ет, что задача о ближайшей точке на плоскости решается за

Однако использовать диаграмму Вороного в качестве струк­ туры данных для графического ледактирзвания нецелееоэбраэ-

1 0 4

но,прежде всего из-за сложностей в практической реализации. К тому же операции удаления и вставки выполняются на этой структуре за время OjCogHk худшем случае, т.е. могут вы­ рождаться, по существу^ в полный просмотр точек. Действи­ тельно, вставка в диаграмму Вороного, соответствующую /У точкам на прямой, любой точки, но лежащей на этой прямой, требует добавления в диаграмму /У-/ вершины и А/ ребер (рис. 1).

Рис. X. Худший случай при вставке точки в диаграмму Вороного

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

1 0 5

жайшей точки и выполнение операций удаления и вставки т ки за время •0(£р^Р) в худшем случае.

Рассмотрим на плоскости в ортогональной декартовой си­

Алгоритм 1 сводит решение задачи поиска ближайших то­ чек на плоскости к решению аналогичной задачи на прямой.

ритма 1 в худи ;м случае равно PCPfyXjMb рис. 2 представле­ на схема работы алгоритма 1.

Если в качестве структуры данных для множеств / ъ /£ использовать бинарное сбалансированное дерево, то время вы­

1 0 6

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

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

наты правой*верхней точки окна. На предлагаемой структуре выполнение операции кадрирования заключается в выделении в

107

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

ИНТЕРАКТИВНЫЕ МЕТОДЫ САПР ПЕЧАТНОГО МОНТАЖА: ОБОСНОВАНИЕ, ВЗАИМОДЕЙСТВИЕ

В.А. Жиля вичюс , А.Ю. С а к а л а у с к а с Повышение требований к качеству и плотности радиоэлект­

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

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

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

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

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

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

1 0 9

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

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

- комплексы АРМ совместно с ЭВМ большой мощности [3]; Необходимо отметить, что использование АРМ второго по­

коления экономически выгодней, чем применение ЭВМ средней и высокой производительности с графическими устройствами ввода/ вывода. Однако использование ЭВМ СМ заставляет разрабаты­ вать алгоритмы и программы проектирования печатного монта­ жа, ориентированные на небольшой объем оперативной памяти, но обладающие большим быстродействием и эффективностью. Коррекция и редактирование графической информации с помо­ щью разработанных ППП ГРИФ и системы ДИАГРАФ [1] воз­ можна только после завершения прикладной программы. Таким образом, на данном этапе развития САПР, комплексы АРМ рассматриваются как вспомогательные средства для доработки проектных решений, полученных автоматическим или автомати­ зированным методом проектирования печатного монтажа.

Включение интерактивных методов проектирования в САПР на ЭВМ высокой производительности с развитым набором гра­ фических устройств ввода/вывода позволяет проектировать пе­ чатные платы, технологически пригодные для серийного произ­ водства, и обеспечивает высокую плотность монтажа. Сущест­ вующая алгоритмическая и информационная база проектирова­ ния монтажа ориентирована на пакетный режим работы ЭВМ. Однако практика зарубежных фирм IBM .LO C K H EED , " S c ie n ­ tific C a lc u la tio n s nnоказывает, что использование интерактив­ ных методов в САПР на ЭВМ средней или большой мощности с развитым набором графических средств оправдано для комп­ лексного решения задач проектирования печатных плат (от вво­ да данных о схеме электрической до выпуска технической,эксплуата циоиной д окументации).

1 1 0