книги / Автоматизация конструкторского проектирования в радиоэлектронике и вычислительной технике. Автоматизация конструкторского проектирования вычислительной техники
.pdfв модели соответствуют модельные ребра с ненулевой пропуск ной способностью.
Рассмотренные, модели элементов отражают ограничения метрического и топологического характера, которые необходи мо учитывать при туннелировании элементов. Зги ограничения отображаются в моделях элементов введением понятия пропуск
ной способности модельного |
ребра и хорды, причем различают |
ся прэрускная способность |
промежутков между соседними кон |
тактами, между противоположными контактами, пропускная спо собность гибких проволочных выводов.
Кроме модельных рёбер, в графе схемы присутствуют реб ра, отражающие факт вхождения контакта в электрическую цепь, так называемые сигнальные ребра м - Пересечение модель ных ребер между собой допускается только в том случае, ес-* ли восстанавливаемое ребро соответствует пленочному резисто ру. Лопускается пересечение сигнальными ребрами модельных с ненулевой пропускной способностью.
Поставим в соответствие конструкторско-технологическим способам устранения пересечений через туннелирование элемен тов оператор планаризации, который назовем оператором нелирования.
Введем формальное определение оператора туннелирования (QT). Пусть 6 СХ,а) - максимальный плоский подграф схемы, являющийся исходным графом для этапа планаризации. Разо
бьем вершины исходного графа G |
на классы |
J)j Ха |
и |
Л}, где |
Л/ - вершины, отображающие электрические цепи; |
Хг - |
вер- |
||
’шины, отображающие контакты элементов; |
- центральные |
|||
вершины в звездных моделях элементов. |
|
|
|
|
Аналогично множество ребер |
U представим в виде |
сово |
купности двух непересекающихся подмножеств: множества мо
дельных |
ребер |
U/t удовлетворяющих условию CV'UiG&riCMi =* |
|
и множества |
6Хг » |
€*£»] |
|
Uz сигнальных ребер, |
удовлетворяющих условию |
||
( Щ |
с и ^ Щ |
е л , Д7* |
Применение оператора туннелирования приводит к появле нию дополнительных вершин двух видов:
- отображающих фиктивные контакты у элементов - они появляются в модели элемента после проведения проводника между соответствующими контактами туннелируемого элемен та (обозначим множество таких вершин через //* );
101
- отображающих шлгшшителькую цепь, реализующую вос становленное ребро (обозначим множество таких вершин че рез X j\
Восстанавливаемое ребро реализуется в Сг рядом планар ных ребер, соединяющих дополнительно введенные вершины (обозначим множество таких ребер через
Ojy^jpjenejnxe^^. Оператором туннелирования называется
такое |
преобразование графа G(X,tO,что |
|||
|
|
ГСв(Х,и})=0*СХ* и*), |
||
где |
x*=XMf9M2r и |
аг*и и*; u f |
а , (и^)} и* •= ие а и*- j |
|
и*=щи?)оа*; |
и /'^ ееф {щ =ог/^т)^га^бл*)&■ |
|||
(*т е4 )] } ; ( Щ |
е ф р * £ |
|
е x / j j г |
|
i/f(re е ф & мт е* IJJгш е 6X*)& ат е x fjjJ |
||||
Здесь Xjc,/g и x f ^ X g - |
множества |
вершин, входящих в моде |
||
ли туннелируемых элементов, |
|
Таким образом, введенные модели элементов и оператор туннелирования позволяют отразить в графовой модели схемы процесс восстановления удаленного ребра.
Лит е р а ту р а
1.ПЕТРЕНКО А.И., ТЕТЕЛЬБАУМ А.Я., ШРАМЧЕНКО Б Л Автоматизация конструирования электронной аппаратуры. - Ки
ев: Вища школа, |
1980 . - 173 с. |
2. СЕЛЮТИН |
В.А. Автоматизированное конструирование |
топологии БИС. - |
М.: Рацио и связь, 1983 . - 112 с. |
3. БАЗИЛЕВИЧ Р.П. Декомпозиционные и топологические |
методы автоматизированного конструирования электронных уст ройств. - Львов: Вища школа, 1981 . - 167 с.
4 . АБРАЙТИС Л.Б. Метод планаризации моделей электри ческих схем. - В сб. "Автоматизация технического проектиро
вания", |
т. |
1, |
Вильнюс, |
1981, с, |
6 |
1 -7 2 . |
|
|
|
|
5. |
ZIB ER T |
К ., |
SAAL |
R. |
"On |
c o m p u te r- a id e d |
||||
d e s ig n |
o f |
h y b rid c irc u it lay au t". - |
P ro c . IE E E |
Int. |
||||||
S ym p . C A S, N o. 4, 1 9 7 4 , p. 3 1 4 - 3 1 8 . |
|
|
||||||||
6. VAN |
C L E E M P U T W .M . "An |
im p ro v ed |
g r a p h - |
|||||||
th e o re tic |
m odel |
for |
c irc u it |
la y o n t |
p ro b lem ". |
- |
in |
|||
P ro c , |
1 1 - th |
D e sig n |
A utom ation W o rk sh o p , |
1974, |
p. 8 2 - 9 0 .
1 02
7. |
VAN |
LIER |
M ,C „ O T T E N R.H. “A utom atic IC - |
||||
layout: so m e |
p la n a riz a tio n |
a lg o rith m s1' - |
P ro c . IE E E |
||||
Ink |
Sym p. |
on |
C A S, 1976, |
p. 6 6 |
2 -6 6 5 . |
|
|
8. |
EN G L W.L. |
M LY N SK I |
D-.A. |
“C o m p u ter-aid e d to |
|||
pological |
d e s ig n |
for IC“ - |
IE E E |
T r a n s , |
C T . V ol- |
20, Nr, 2, |
1 9 7 3 |
, |
p. |
7 1 7 -7 2 5 . |
9. P E R N A R D S |
P. |
" E le k tro n isc h sin n v o lle P la — |
||
n a risie ru n g |
v o n |
|
S c h a ltu u g s g ra p h e n " - D isse r., RWTH, |
|
A ach en , |
|
|
|
|
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]. Она опре
деляется как |
совокупность многоугольников |
Вороного |
/£ |
соот |
|||||
ветствующих |
точкам |
р. |
j 4 = 1, 2, |
/у. Многоугольник |
|
||||
является пересечением содержащих /£■ |
полуплоскостей, каждая |
||||||||
из которых определяется прямой, перпендикулярной отрезку, |
|||||||||
соединяющему точки |
/J |
и f>j |
и проходящей через |
его |
|||||
середину. Понятно, что |
многоугольник |
состоит |
из |
точек,для |
|||||
которых f t |
является |
ближайшей среди |
данных /У |
точек. Поэто |
|||||
му задача |
о ближайшей точке может быть переформулирована |
||||||||
следующим |
образом: найти многоугольник |
которому при |
|||||||
надлежит заданная точка. |
|
|
|
O(tojN) |
|||||
В [5 ] |
приведен алгоритм, позволяющий за время |
||||||||
найти грань плоского прямолинейного |
графа |
с /У |
вершинами, |
которая содержит некоторую заданную точку. Отсюда вытека ет, что задача о ближайшей точке на плоскости решается за
время |
поскольку диаграмму Вороного для /У точек |
можно интерпретировать как плоский прямолинейный граф с |
|
числом вершил, |
не п р е в о с х о д я щ и м [3]. |
Однако использовать диаграмму Вороного в качестве струк туры данных для графического ледактирзвания нецелееоэбраэ-
1 0 4
но,прежде всего из-за сложностей в практической реализации. К тому же операции удаления и вставки выполняются на этой структуре за время OjCogHk худшем случае, т.е. могут вы рождаться, по существу^ в полный просмотр точек. Действи тельно, вставка в диаграмму Вороного, соответствующую /У точкам на прямой, любой точки, но лежащей на этой прямой, требует добавления в диаграмму /У-/ вершины и А/ ребер (рис. 1).
Рис. X. Худший случай при вставке точки в диаграмму Вороного
При графическом редактировании естественно ограничить поиск ближайшей точки некоторой достаточно малой окрестно стью, например, осуществлять его в круге фиксированного ра диуса с центром в заданной точке. Если исходить из такой эслабленной#постановки задачи о ближайшей точке и принять во внимание, что топология ИС задается в некоторой коорди натной сетке (т.е. координаты точек являются целыми числа ми), то возможно построить сравнительно простую структуру данных, которая требует О(М) памяти, обеспечивает поиск блй-
1 0 5
жайшей точки и выполнение операций удаления и вставки т ки за время •0(£р^Р) в худшем случае.
Рассмотрим на плоскости в ортогональной декартовой си
стеме координат произвольное множество Р из N |
точек |
с це |
|||||||
лочисленными координатами. Обозначим через |
X множество |
||||||||
абсцисс точек из Р, |
а |
через Рх |
подмножество |
Р, |
состоящее |
||||
из |
точек с абсциссой |
х |
Алгоритм, |
который приводится |
ни |
||||
же, находит все точки из множества |
Р, которые лежат в |
кру |
|||||||
ге |
радиуса Jr* с центром в заданной |
точке p m ( a j b ) . |
|
||||||
|
Алгоритм 1 (Поиск ближайших точек). |
|
|
|
|||||
|
1. Находим в множестве |
х |
подмножество |
|
lx* 1***X* |
||||
|
II* В каждом множестве |
х |
|
находим подмножество |
|||||
|
/*/ *{ЩрО/ |
^ |
|
|
д' 4:b |
|
} |
|
|
|
Искомое множество |
образуют точки |
|
|
|
Алгоритм 1 сводит решение задачи поиска ближайших то чек на плоскости к решению аналогичной задачи на прямой.
Для /У точек на прямой задача нахождения точек из |
некоторо |
||||||||
го интервала решается за время |
0 Стах( e*gAf,/o)fr де |
К - чис |
|||||||
ло искомых точек |
[2 ]г |
|
|
|
|
|
|
||
Число точек множества X, лежащих в интервале |
|
||||||||
не превосходит [Z rJ+t j где[2-rJ |
- |
целая часть числа 2-г*. По |
|||||||
этому |
время выполнения шага |
1 |
оценивается как OtoaxCityN(X)j |
||||||
j b))j |
где MX) |
- |
число |
точек множества X . |
Шаг |
II выпол |
|||
няется |
за время |
0 |
С т |
а |
х |
С |
*))< где щ |
,)- число точек |
|
множества Ptf j |
М |
- числа точек множества р |
, которые ле |
||||||
жат в заданном круге.. Поскольку |
М х ) 4 W, Z |
/*/№ %*)£ |
|||||||
fxyAfj #<(Г£фО*ъ /"-кон стан та, |
то время выполнения алго |
ритма 1 в худи ;м случае равно PCPfyXjMb рис. 2 представле на схема работы алгоритма 1.
Если в качестве структуры данных для множеств / ъ /£ использовать бинарное сбалансированное дерево, то время вы
полнения |
операций удаления |
и вставки |
точки в полученную |
||
структуру |
составит |
|
худшем |
случае. Рассмотрим, к |
|
примеру, |
алгоритм вставки |
точки |
с координатами Са,А) |
||
Алгоритм 2. |
(Вставка |
точки). |
|
||
1. Нахрцим в |
множестве |
/ элемент X ближайший к <£. |
1 0 6
II. |
Если Х*и, то выполняем |
операцию вставки (U,6) в |
|||
ДО |
В противном случае |
образуем множество |
и |
||
выполняем операцию вставки |
а |
в Л. |
|
||
Поскольку |
операции вставки |
и поиска ближайшего элемен |
|||
та выполняются |
на сбалансированном цереве за |
время |
то время выполнения алгоритма 2 составляет также Предлагаемая структура данных позволяет достаточно эф
фективно выполнять операцию кадрирования или отсечения то чек, лежащих вне некоторого прямоугольного окна, и обратную операцию вставки прямоугольного окна. Обе эти операции да ют возможность свести редактирование целого чертежа к ре
дактированию его |
части. |
|
Пусть (d /i) |
- координаты левой нижней, a |
коорди |
наты правой*верхней точки окна. На предлагаемой структуре выполнение операции кадрирования заключается в выделении в
X подмножества Л {x"/x''GXj |
в каждом %н,х'кХ^5; |
подмножества |
(/}, и в представлении X м н РЖ1 |
107
в виде бинарных сбалансированных деревьев. Для выполнения этих преобразований можно, очевидно, использовать операции удаления и вставки на бинарном сбалансированном дереве. Но тогда время выполнения кадрирования составит 0(/У0*рА)ъ худ шем случае. Известно, что расщепление дерева в заданном уз ле без нарушения сбалансированности выполняется за время
[2 ]. Воспользовавшись этим алгоритмом расщепления|
можно выполнить операцию кадрирования за |
время 0(m axttym # |
|||
' |
где |
“ числ0 точек множества |
||
Положим, что /yCfV - |
число |
точек X”, тогда |
имеет место сле |
|
дующая цепочка неравенств: |
|
|
||
00$ < £ . NС )//V(X")) |
С*3# ,) $ w . |
Отсюда следует, что |
операция кадрирования выполняется в худшем случае за время О(А/), Операция вставки окна выполняется также за время 0(М) в худшем случае, если использовать алгоритм конкате нации бинарных сбалансированных деревьев- с временем выпол нения 0f00£/V)[2],
В заключение отметим, что предлагаемая структура дан ных допускает фрагментацию точек на плоскости (фрагмент об разуют точки, лежащие в некотором прямоугольнике или квад рате), и это является основой для ее практической реализации,
Ли т е р а т у р а
1.УОКЕР Б.С., ГУРД Дж.Р., ДРОНИК Е.А. Интерактив
ная машинная графика, - |
М,: Машиностроение, 1980 . - 168 с* |
|||
2 Г КНУТ Д. Искусство программирования для ЭВМ. - |
М.; |
|||
Мир, 1 9 7 8 , |
т. 3 - 8 4 4 |
с. |
|
|
-3. M.I. |
SH A M O S, |
G e o m e tric |
fco n p lex lty . — P ro c . |
|
7 th A n n u a l A C M Sym p. on T h e o ry |
of C om put,, 1 9 7 5 , p. |
|||
2 2 4 -2 3 3 . |
|
|
|
|
4. А Д ЕЛ ЬС О Н -В Е Л ьС К И Й гХ , ЛАНДИС E.M. Один ал |
||||
горитм организации информации. - ДАН СССР, 1962, № |
146, |
|||
2 6 3 -2 6 6 с. |
|
|
|
|
5. R ,j. |
L IPT O N , R .E . T A R JA N . A p p lic a tio n s |
of |
||
p la n a r s e p a r a to r th e o re m . - P r o c . 18 th A n n u a l |
|
|||
S ym p . on F o u n d , o f |
C om put. S c l.r 1 9 7 7 , p, 1 6 2 —170. |
УДК 6 8 1 .3 .0 8 2 .5
ИНТЕРАКТИВНЫЕ МЕТОДЫ САПР ПЕЧАТНОГО МОНТАЖА: ОБОСНОВАНИЕ, ВЗАИМОДЕЙСТВИЕ
В.А. Жиля вичюс , А.Ю. С а к а л а у с к а с Повышение требований к качеству и плотности радиоэлект
ронной ,и вычислительной аппаратуры приводит к необходимо сти совершенствования методов ее автоматизированного проек тирования. Современный уровень развития программно-техни ческих комплексов САПР позволяет сделать вывод, что даль нейшие качественные изменения характеристик процесса проек тирования печатного монтажа будут происходить в зависимо сти от степени развития интерактивных средств в САПР.
В большинстве созданных САПР печатного монтажа реали зован один из методов проектирования: автоматический или ав томатизированный, определяющий место конструктора-пользо- вателя в процессе конструирования и проектирования печатных плат.
Автоматический метод проектирования является наиболее совершенным, так как исключает пользователя при формирова нии топологии печатного монтажа. Недостатками этого мето да является то, что для получения 100% трассировки межсо единений требуется: сложное программное обеспечение, универ сальная ЭВМ высокой производительности, а также высокая трудоемкость ввода исходной информации и сложность последу ющего редактирования результатов трассировки.
При проектировании крупногабаритных печатных плат с эле ментами высокой степени интеграции автоматическим методом трудоемкость и время на их разработку соизмеримы с соот ветствующими параметрами при. разработке таких плат ручным методом.
Автоматизированный метод проектирования печатного мон тажа обеспечивает высокую, плотность компоновки, однако на человека возлагается большая часть рутинной работы по фор мированию топологи» монтажа.
Применение интерактивных методов в процессе проектиро вания печатного монтажа позволяет устранить недостатки ав томатического и автоматизированного методов проектиро-
1 0 9
ваиия. Анализ существующей алгоритмической базы решения задач размещения элементов и трассировки соединений пока зывает, что необходимо применять методы интерактивного вза имодействия, позволяющие сочетать опыт и творчество челове ка со скоростью ЭВМ при обработке графической информации.
Исследование технических средств современных САПР пе чатного монтажа показало, что в качестве базовых средств ис пользуются:
- |
комплексы автоматизированных рабочих мест |
£1] ; |
- |
ЭВМ высокой производительности, оборудованная допол |
|
нительными графическими средствами ввэца/вывэца |
[2 ]; |
- комплексы АРМ совместно с ЭВМ большой мощности [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