книги / Автоматизация конструкторского проектирования в радиоэлектронике и вычислительной технике. Автоматизация конструкторского проектирования вычислительной техники
.pdfПредлагается общая c veMa формирования тестовых, задач разрезания графа на фиксированное число подграфов с априор ным указанием оптимального решения задачи. Дается конкрет ный алгоритм, реализующий эту схему. Генерируемые тест-за- дачи можно использовать в целях экспериментального исследо вания приближенных алгоритмов.
Ил. 1, библ. 8.
УДК 6 2 1 .3 .0 4 9
В*А. Штуйкис, Г.К, Сабаляускас. Приближенный алго ритм определения маршрута коммивояжёра на подмно жестве узлов координатной сетки. - В межвузовском сб.: Автоматизация конструкторского проектирования в радиоэлектронике.,и вычислительной технике. Виль нюс, 1985, т. 5, с. 8 5 -9 3 .
Формулируется задача оптимизации гамильтонова цикла на подмножестве узлов координатной сетки по двум критериям - длине цикла и числу "лишних углов" в цикле. Предлагается приближенный алгоритм решения задачи и приводятся резуль таты экспериментов.
Ил. 3, библ. 11.
УДК 6 2 1 .3 9 6 .6
Э.Ш. Гайфуллин, Г.Н. Ярочкина. Модели элементов на этапе планаризацин при топологическом проектирова нии гибридной интегральной схемы. - В межвузовском сб.: Автоматизация конструкторского проектирования в радиоэлектронике и вычислительной технике. Виль нюс, 1985, т. 5, с. 9 4 -1 0 3 .
В работе рассматривается задача восстановления удален ных ребер графа, возникающая при реализации графа на плос кости. Описываются операторы планаризашш графа и предлага ются модели элементов, учитывающие ограничения метрическо го и топологического характера.
Мл. 4, библ. 11.
1 6 1
УПК 6 8 1 .3 :5 1 9 .8 |
|
|
|
Л.В. Ноаов, Поиск ближайшей точки при графическом |
|
|
редактировании топологии ИС. - В межвузовском сб.: |
|
|
Автоматизация конструкторского проектирования в ра |
|
|
диоэлектронике и вычислительной технике, Вильнюс, |
|
|
1985, т. 5, с, |
1 0 3 -1 0 8 , |
Рассматривается следующая задача, возникающая при‘соз |
||
дании |
системы графического редактирования топологии ИС: сре |
|
ди /Уточек на хшоскости |
найти ближайшую к заданной. Приво |
|
дится |
структура данных, |
которая обеспечивает эффективное вы |
полнение поиска ближайшей точки, операций удаления и встав ки точки. С учетом некоторых ограничений, естественных при графическом редактировании топологии ИС, время выполнения всех этих операций составляет O(t0$N)*
Ил. 2, библ, 5.
УДК 6 8 1 .3 .0 8 2 .5
В.А. Жилявичюс, А.Ю. Сакалаускас. Интерактивные ме тоды САПР печатного монтажа: обоснование, взаимо действие. - В межвузовском сб,: Автоматизация кон структорского проектирования в радиоэлектронике и вычислительной технике. Вильнюс, 1985, т. 5, с. 1 0 9 -
114.
Встатье дается обоснование интерактивного метода про ектирования на ЭВМ средней и высокой роизводительности с развитым набором графических устройств вводд/вывода, Интер активные методы проектирования печатного монтажа разраба тываются на осюве алгоритмической и-информационной базы комплексной САПР. Рассмотрены общие требования к языку взаимодействия "человек-машина" такой САПР.
Библ. 7.
УДК 6 8 1 ,3 2 6 .5 1
А.Э. Таргамадзе, Э.В. Барейша. Моделирование логи-
162
ческих схем с БИ~. - В межвузовском сб.: Автомати зация конструкторского проектирования в радиоэлект ронике и вычислительной технике. Вильнюс, 198 5 , т. 5, с. 1 1 4 -1 2 4 .
Рассмотрены вопросы построен ия модели БИС'а и органи зация процесса моделирования в схеме на основе разработан ной модели. Вопросы моделирования схемы затронуты по мере необходимости обеспечения правильного моделирования элемен тов, а также при рассмотрении структур схемы, обусловленных появлением БИС.
Ил. 5, библ. 4.
УДК 6 8 1 .3 2 5
В.Ф. Звягин, А.А. Бутылин. Расчет оценок управляемо сти элементов логической схемы. - В межвузовском сб.: Автоматизация конструкторского проектирования в радиоэлектронике и вычислительной технике. Виль нюс, 1985, т. 5, с. 1 2 5 -1 3 3 .
Предложены числовые оценки управляемости элементов ло гической схемы. Приведены формулы оценок управляемости для различных типов регистров. Указаны пути применения оценок цдя повышения контролепригодности и упорядочения перебора при генерации тестов.
Ил. 4, библ. 2.
УДК 6 8 1 .3 .0 6
Р.К. Мэтеюнене, К.Л. Мэтеюнас. Анализ контролепри годности цифровых устройств. - В межвузовском сб.: Автоматизация конструкторского проектирования в ра диоэлектронике и вычислительной технике. Вильнюс,
т.5, с. 1 3 4 -1 4 3 .
Встатьё предложена методика вычисления для заданного узла схемы показателей управляемости и наблюдаемости. При этом учитываются выполняемые логическими элементами функ-
1 6 3
ции, разветвления схемы, элементы памяти и обратные связи. В качестве единицы показателей используется операция обра щения к таблицам истинности элементов. Вычисляемые показа тели позволяют инженеру-разработчику оценить проектируемую схему с точки зрения ее тестируемости и еще до того, как будут затрачены средства на изготовление опытных образцов, внести в нее соответствующие изменения. Кроме того, данные анализа в дальнейшем могут быть использованы для управле ния процессом генерации тестов.
Ил. 2, библ. 3.
УДК 6 8 1 .3 2 5 .6
А.Э. Таргамацзе, В.П. Юсас. Подсистема анализа пол ноты проверяющих тестов в САПР "Каунас-3". - В межвузовском сб.: Автоматизация конструкторского проектирования в радиоэлектронике и вычислительной технике. Вильнюс, 1985, т. 5, с. Х 43-Х 49.
В статье рассмотрены алгоритмы и методы, применяемые для онализа полноты проверяющих тестов в САПР "Каунас-3".
Библ. 3.
УДК 6 8 1 .325
А.А. Ярамайтис. О выборе пррверяющегэ вектора в вероятностных системах диагностирования дискретных устройств. - В межвузовском сб.: Автоматизация кон структорского-проектирования в радиоэлектронике и ....
.вычислительной технике. Вильнюс, 1985, т. 5, с. Х49- *5 6 .
Работа посвящена проблеме выбора входных последователь ностей в вероятностных системах диагностирования дискретных устройств. Предложен способ определения проверяющего век тора, обеспечивающего высокие вероятности обнаружения неис правностей.
Ил. 3, библ. 5.
1 6 4
|
|
|
D. |
|
B a tis tc h e v , |
V. |
M o ro so v , |
V e rs a tile |
r o u |
|
||||||||||||||||
|
|
|
ting |
|
of |
p rin te d |
c irc u its |
ta k in g |
into |
|
a c c o u n t |
|||||||||||||||
|
|
|
m etric a l |
re s tric tio n s ,. |
— T h e |
sc ie n tific |
w o rk s |
|||||||||||||||||||
|
|
|
c o lle c tio n |
of |
h ig h e r |
|
s c h o o ls |
" C o n s tru c tiv e |
|
|||||||||||||||||
|
|
|
d e s ig n |
au to m atio n |
in |
ra d io e le c tr o n ic s |
|
a n d |
||||||||||||||||||
|
|
|
co m p u tin g |
m ac h in e ry ", |
v . |
|
5, |
V ilnius, |
|
1 9 8 5 , |
||||||||||||||||
|
|
|
p. |
3 - 1 1 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
A |
problem |
of |
p rin te d |
c irc u it |
ro u tin g |
is |
c o n s id e |
|||||||||||||||||||
red |
a s |
a |
m ultiple |
c rite ria |
o p tim izatio n |
|
p ro b lem . A n |
|||||||||||||||||||
algorithm |
is |
|
p r e s e n te d |
w h ich |
c o m b in e s |
th e |
e ffic a c y |
|||||||||||||||||||
of v e rs a tile |
|
ro u tin g |
a lg o rith m s |
an d |
w av e |
o n e s |
w ith |
|||||||||||||||||||
a c c o u n tin g |
of |
m e tric a l |
r e s tr ic tio n s . |
T h e |
alg o rith m |
is |
||||||||||||||||||||
Illu stra te d |
by |
a n |
e x a m p le . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
F ig . 4 , r e f r . 5. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
V.G-. |
M a ra g in , |
B .N . |
D e n d o b re n k o . |
T h e |
o p ti |
||||||||||||||||||
|
|
|
mal |
|
p la c e m e n t |
of |
|
c o m p o n e n ts |
on |
a |
p rin te d |
|||||||||||||||
|
|
|
c irc u it |
b o a rd . |
- |
T h e |
s c ie n tific |
|
w o rk s |
c o lle c |
||||||||||||||||
|
|
|
tion |
|
of |
|
h ig h e r |
s c h o o ls |
" C o n s tru c tiv e |
d e s ig n |
||||||||||||||||
|
|
|
au to m atio n in |
r a d io e le c tr o n ic s |
|
a n d |
|
c o m p u |
||||||||||||||||||
|
|
|
ting |
|
m ac h in ery ", |
v . |
5, |
V ilnius, |
198 5 , |
p. Ц - . |
||||||||||||||||
|
|
|
18 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A |
new |
p ro c e d u re |
of |
th e |
|
p la c e m e n t |
of |
c o m p o n e n ts |
||||||||||||||||||
on |
a |
p rin te d |
c irc u it |
b o a rd |
g iv in g so lu tio n |
|
g lo b ally |
|||||||||||||||||||
optim a l |
in |
th e |
s e n s e |
of |
th e |
|
sum |
|
of |
w ire |
le n g th s |
is |
||||||||||||||
d e s c r ib e d . |
T h is |
p ro c e d u re |
u s e s |
|
a t |
m ost |
N |
q u e u e |
||||||||||||||||||
lists, |
w h e re |
N |
is |
th e |
n u m b e r |
of |
c irc u it |
c o m p o n e n ts . |
||||||||||||||||||
F o r s e le c tio n |
the |
p o sitio n |
a |
p la c e m e n t |
fro n t |
is |
fo r |
|||||||||||||||||||
med |
from |
p o sitio n s |
c o n tig u o u s |
to |
a lr e a d y |
o c c u p ie d |
||||||||||||||||||||
o n e s . |
T o |
dim in ish |
th e |
n u m b er |
of |
s o lu tio n s |
e x a m i |
|||||||||||||||||||
n e d |
th e |
b r a n c h - a n d - b o u n d |
|
m ethod |
is |
a d a p te d . A t |
|
|||||||||||||||||||
e v e ry s te p of th e p la c e m e n t p r o c e d u r e th e lo w e r |
|
|||||||||||||||||||||||||
b o u n d |
is |
c a lc u la te d |
w h ich |
e q u a ls |
to |
m inim ally |
p o |
|||||||||||||||||||
s s ib le |
sum |
of |
w ire |
le n g th s |
|
w h en |
|
th e |
b e s t |
a r r a n g e |
||||||||||||||||
m ent |
of |
c o m p o n e n ts |
ia c o n s id e r e d . |
|
|
|
|
|
|
|
|
|||||||||||||||
|
F ig . |
1, |
re fr. |
2. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 6 5
|
|
Y . |
|
S treln ik o v , |
|
I. |
|
P o lc h ik o v a , |
G-. |
D m itrevich . |
|||||||||||||||||
|
|
M eth o d ical |
p ro b lem s |
of |
p rin te d |
c irc u it |
b o ard |
||||||||||||||||||||
|
|
d e sig n |
u sin g |
d ialo g ic |
|
CAD |
s y s te m s . |
—T h e |
|||||||||||||||||||
|
|
scien tific |
w o rk s |
|
c o lle c tio n |
of h ig h e r |
|
s c h o o ls |
|||||||||||||||||||
|
|
^ C o n stru ctiv e |
d e s ig n |
|
autom ation |
in |
r a d io e |
||||||||||||||||||||
|
|
le c tro n ic s |
and |
com puting |
m ac h in ery ", |
|
v . |
5, |
|||||||||||||||||||
|
|
Vilnius, |
1985, |
|
p. |
|
1 8 -2 6 . |
|
|
|
|
|
|
|
|
|
|
||||||||||
|
S om e |
m eth o d ica . |
p ro b lem s |
|
of |
PC B |
d e s ig n |
|
|
a re |
|||||||||||||||||
d is c u s s e d . |
T h e |
p ro b lem s |
a r is e |
w h en |
w e |
a r e |
|
c o n |
|||||||||||||||||||
c e rn in g |
th e u n s e p a ra te d |
|
im plem entation |
of a u to m a |
|||||||||||||||||||||||
t e |
a n d |
in te rac tiv e |
|
g rap h ic |
te c h n iq u e s |
for |
form ing |
||||||||||||||||||||
d e s ig n so lu tio n s. |
T h e s e |
|
p ro b lem s |
d e a l |
with |
a |
c h o i |
||||||||||||||||||||
c e |
of |
an |
optim al |
in te ra c tio n a l |
|
lev el, |
a |
form ation |
of |
||||||||||||||||||
ra tio n a l |
d e sig n |
path |
an d |
|
le a rn in g |
|
u s e r s |
a n d |
CAD |
||||||||||||||||||
s y s te m s . |
M eth o d s |
|
an d |
w a y s |
|
for |
so lv in g |
th e s e |
p ro b |
||||||||||||||||||
lem s |
a re |
|
p ro p o se d . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
R efr.. b. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
V. Z h ilev ich iu s, |
R . |
B a ltru s h a itis . |
|
C rite ria for |
||||||||||||||||||||
|
|
uniform |
p lacem en t. |
- |
|
T h e |
|
s c ie n tific |
w o rk s |
||||||||||||||||||
|
|
co lle ctio n |
of h ig h e r |
s c h o o ls |
''C o n s tru c tiv e |
d e |
|||||||||||||||||||||
|
|
|
sig n |
autom ation |
in r a d io e le c tro n ic s |
a n d |
|
com p u |
|||||||||||||||||||
|
|
ting m ach in ery ", |
v . |
5, |
|
V ilnius, |
1 9 8 5 , |
p, 2 6 -43 . |
|||||||||||||||||||
|
P ro b le m s |
of |
d eterm in in g |
|
th e e v a lu a tio n s |
|
of |
lo a |
|||||||||||||||||||
ding |
by |
c o n n e c tio n s |
an d |
c a p a b ility |
of |
s e p a r a te |
la y |
||||||||||||||||||||
o u t |
a re a |
|
p a rts |
a re |
d is c u s s e d . |
D ifferent |
c r ite r ia |
for |
|||||||||||||||||||
p lacem en t |
|
aim ing |
a t |
uniform |
d istrib u tio n |
o f c o n n e c |
|||||||||||||||||||||
tio n s |
b a s e d |
on th e s e |
e v a lu a tio n s |
|
a r e |
d e v e lo p e d . |
|||||||||||||||||||||
E x p erim en tal |
r e s u lts |
a re |
|
p re s e n te d . |
|
|
|
|
|
|
|
|
|||||||||||||||
|
Fig.* |
4, |
re fr, |
9. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
E. |
|
O ichm an . |
M ath em atical |
|
e s tim a tio n s |
|
of d a |
||||||||||||||||||
|
|
|
ta |
|
s tru c tu re s |
in |
|
c o re |
|
|
s to ra g e |
for |
in te ra c tiv e |
||||||||||||||
|
|
|
CAD |
s y s te m s . |
- |
|
T h e |
|
|
sc ie n tific |
w o rk s |
c o |
|||||||||||||||
|
|
llectio n |
)of |
h ig h e r |
s c h o o ls |
|
" C o n s tru c tiv e d e |
||||||||||||||||||||
|
|
|
sig n |
autom ation |
|
in |
ra d io e le c tro n ic s |
|
|
|
and |
||||||||||||||||
|
|
com puting |
|
m ach in ery ", |
v . |
|
5, |
V ilnius, |
|
p. |
4 3 - |
||||||||||||||||
|
|
4 8 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 6 6
|
P ro b le m s |
c o n c e rn in g |
e v a lu a tio n |
of |
d a ta |
s tr u c tu |
||||||||||||||||||
re in fo lo g ical |
m o d els |
a re |
c o n s id e r e d . |
|
T h e |
c rite r ia |
||||||||||||||||||
for |
m odel |
e v a lu a tio n |
s u c h |
a s |
c o re |
s to r a g e |
r e q u i |
|||||||||||||||||
rem ent, |
s e a r c h |
time |
an d |
d a ta |
u p d atin g |
|
time |
a re |
in |
|||||||||||||||
tro d u c e d , |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
R efr. 6. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
V_A# |
S tu ik y s . |
A |
m ethod |
|
for |
g ro u p in g |
of |
o b |
|||||||||||||
|
|
|
je c ts |
b a s e d |
o n |
|
m ultiple |
s o lv in g |
an a s s i g n |
|||||||||||||||
|
|
|
m ent |
p ro b lem . |
- |
T h e |
sc ie n tific |
|
w o rk s |
c o lle c |
||||||||||||||
|
|
|
tion |
of |
h ig h e r |
s c h o o ls |
" C o n stru c tiv e |
d e s ig n |
||||||||||||||||
|
|
|
au to m atio n |
in |
ra d io e le c tro n ic s |
|
a n d |
c o m p u |
||||||||||||||||
|
|
|
ting |
m ac h in ery ", |
v . |
5, |
V ilnius, |
1985, |
|
p. |
4 8 - |
|||||||||||||
|
|
|
57, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
T h e |
problem |
a n d |
the m ethod |
for |
g ro u p in g |
|
|
of |
|||||||||||||||
o b je c ts |
w hen |
c rite rio n |
is |
minimum |
( maximum) |
of the |
||||||||||||||||||
sum |
|
of |
ty p e s |
o f |
e le m e n ts |
in |
all |
g ro u p s |
a re |
s u g g e s |
||||||||||||||
ted . |
|
M otivation |
an d |
s ta g e s |
of |
the m ethod |
a s |
|
w ell |
|||||||||||||||
a s |
a |
n u m e ric a l |
ex am p le |
o f |
its |
re a liz a tio n |
a re |
d e s c r i |
||||||||||||||||
b ed . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F ig . |
1, |
re fr. |
|
3. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
R. |
B a z y le v itc h , |
|
Y . |
G re s k o . |
T o p o lo g ic a l |
|
d e |
||||||||||||||
|
|
|
sig n |
of |
la y e r s |
with |
m inim ization |
the |
n u m b er |
|||||||||||||||
|
|
|
of |
v ia s . |
|
- |
T h e |
|
sc ie n tific |
w o rk s |
c o lle c tio n of |
|||||||||||||
|
|
|
h ig h er |
s c h o o ls |
|
"C o n stru c tiv e |
d e s ig n |
a u to m a |
||||||||||||||||
|
|
|
tion |
in |
ra d io e le c tro n ic s |
an d |
co m p u tin g |
|
m a |
|||||||||||||||
|
|
|
c h in e ry ", |
v . |
5, |
V ilnius, |
1985, |
p. |
5 7 -6 7 .. |
|
|
|||||||||||||
|
F o r a s e p a r a te d c lo s e d a r e a c r o s s e d by a s e t |
|||||||||||||||||||||||
o f c o n n e c tio n s |
th e |
s y n th e s is p roblem |
|
for |
two |
a v a i |
||||||||||||||||||
lab le |
la y e r s is |
c o n s id e re d . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
An |
efficien t |
algorithm , |
im p lem en tin g |
|
to p o lo g ic a l |
||||||||||||||||||
a p p ro a c h |
an d aim ing |
a t |
m inim ization |
th e n u m b e r |
of |
|||||||||||||||||||
c o n n e c tio n s |
re a liz e d |
with |
v ia s |
a s |
w ell |
a s |
th e |
to ta l |
n u m b er of v ia s , is p rp p o s e d . S om e c o m p u te r e x p e
rim e n ts |
a re |
d is c u s s e d . |
F ig . |
6, |
re fr. 3. |
1 6 7
|
A . |
B e rs h a d s k y , |
Е . |
K a rp o v , |
I. |
T u z h ilo v . |
|
|
|||||||||||||||||||
|
A n a p p lic atio n |
of |
the |
p rin te d |
|
w irin g |
s p a c e |
|
|||||||||||||||||||
|
utilization |
|
function |
|
for |
m atrix |
|
LSI |
a n d |
|
P C B . |
|
|||||||||||||||
|
- |
T h e |
scien tific |
w o rk s |
c o lle c tio n |
of |
h ig h e r |
||||||||||||||||||||
|
|
s c h o o ls |
'‘C o n s tru c tiv e |
|
d e s ig n |
au to m atio n |
in |
||||||||||||||||||||
|
ra d io e le c tro n ic s |
a n d |
|
com p u tin g |
m ac h in ery ", |
||||||||||||||||||||||
|
v. |
5, |
V ilnius, |
|
1 9 8 5 , p. 6 7 - 7 2 . |
|
|
|
|
|
|
|
|||||||||||||||
T h is |
|
p a p e r |
d e a ls |
|
|
with |
|
CAD |
|
te c h n iq u e |
for |
p la |
|
||||||||||||||
c e m e n t |
of |
m atrix |
LSI |
|
an d |
|
PC B |
|
co m p o n en ts* T h e |
p la |
|||||||||||||||||
c e m e n t |
te c h n iq u e |
|
p ro v id e s |
go o d |
c o n d itio n s |
for o b |
|
||||||||||||||||||||
tain in g |
th e |
final |
lay o u t |
by |
w ay |
|
of |
fully |
au to m atic ro u |
||||||||||||||||||
tin g technique* |
T h e |
p rin te d |
w iring |
s p a c e |
u tilizatio n |
||||||||||||||||||||||
function |
|
is |
u s e d |
in |
o r d e r |
|
to |
|
link |
p la c e m e n t |
w ith la y - |
||||||||||||||||
in g -o ut. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F ig . |
|
1, |
refr. |
5* |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
E. |
O ichm an . |
|
M o d e ls |
of |
|
sy s te m |
lib r a rie s |
of |
|
|||||||||||||||||
|
elem en ts |
for |
|
in te ra c tiv e |
|
P C B |
|
CAD |
|
s y s te m s . |
|||||||||||||||||
|
|
- |
T h e sc ie n tific |
w o rk s |
|
c o lle c tio n |
of |
h ig h e r |
|||||||||||||||||||
|
s c h o o ls |
"C o n stru c tiv e |
|
d e s ig n |
au to m atio n |
in |
|||||||||||||||||||||
|
ra d io e le c tro n ic s |
a n d |
|
co m p u tin g |
m ac h in ery ", |
||||||||||||||||||||||
|
v. |
5, |
Vilnius^ |
|
1985, |
p. |
7 2 - 7 8 . |
|
|
|
|
|
|
|
|||||||||||||
D ifferent |
m eth o d s |
|
|
for |
elem en t |
lib ra rie s |
d e v e lo p |
||||||||||||||||||||
m ent a re |
c o n s id e re d . |
|
A sy s te m |
|
lib ra ry |
m odel |
having |
||||||||||||||||||||
sim ple |
u p d atin g |
m e a n s |
is |
|
p ro p o s e d . |
|
|
|
|
|
|
|
|
|
|||||||||||||
R efr. |
4. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
J. |
M atick as, |
|
G . |
P a lu b e c k is . |
|
G e n e ra tin g |
of |
|||||||||||||||||||
|
|
g ra p h p artitio n in g |
|
problem |
in s ta n c e s |
|
with |
a |
|||||||||||||||||||
|
|
g iv en |
optim al |
so lu tio n . |
|
- |
T h e |
s c ie n tific |
w orks |
||||||||||||||||||
|
|
c o lle ctio n |
of |
|
|
h ig h e r |
s c h o o ls |
|
" C o n s tru c tiv e |
|
|||||||||||||||||
|
d e sig n |
autom ation |
|
in |
|
ra d io e le c tro n ic s |
|
a n d |
|
||||||||||||||||||
|
E!imp_uUng |
m ach in ery ", |
v . |
5, |
|
V ilnius, |
1985, |
p. |
|||||||||||||||||||
|
|
7 8 -8 4 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
T h e |
|
problem |
c o n s id e re d |
is |
|
th at |
of |
p a rtitio n in g |
an |
||||||||||||||||||
e d g e -w e ig h te d |
g ra p h |
|
into |
|
a |
g iv en |
n u m b er |
of |
|
p a rts |
|||||||||||||||||
e a c h c o n s tra in e d |
|
in |
|
s iz e |
|
w ith |
the |
o b je c tiv e |
of |
mini |
|||||||||||||||||
m izing th e |
to tal |
w eight o f e d g e s |
c o n n e c tin g |
v e rtic e s |
1 6 8
from |
d ifferen t |
p a rts . |
|
Л g e n e ra l |
te c h n iq u e |
|
for. |
g e n e |
|||||||||||||||||||
ratin g in s ta n c e s |
of |
th is |
problem |
h av in g |
|
a |
p rio ri |
g i |
|||||||||||||||||||
v en |
optim al |
so lu tio n |
is |
p re s e n te d . S p ecific |
algorithm |
||||||||||||||||||||||
b a s e d |
upon |
th is |
te c h n iq u e |
|
is |
|
d e v e lo p e d . |
|
P ro b lem |
||||||||||||||||||
in s ta n c e s |
g e n e ra te d |
|
by |
th is |
algorithm |
c a n |
|
be |
a p p |
||||||||||||||||||
lied |
in |
|
e x p e rim e n tal |
|
in v e stig a tio n |
of |
ap p ro x im ativ e |
||||||||||||||||||||
alg o rith m s. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Fig. |
|
1, refr. 8. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
V. S tu ik y s, |
|
G . |
S a b a lia u s k a s . |
|
An |
a p p ro x im a |
||||||||||||||||||
|
|
|
tive |
algorithm |
for |
finding |
the |
|
tra v e llin g |
|
s a |
||||||||||||||||
|
|
|
lesm an |
|
to u r |
|
on |
|
the |
s u b s e t |
0 1 |
a |
|
re fe re n c e |
|||||||||||||
|
|
|
grid . |
- |
|
T h e |
|
sc ie n tific |
|
w o rk s |
c o llectio n |
of h ig |
|||||||||||||||
|
|
|
h e r |
sci |
o o ls |
|
‘'C o n stru c tiv e |
d e sig n |
autom ation |
||||||||||||||||||
|
|
|
in |
ra d io e le c tro n ic s |
|
an d |
com put;og |
m ac h in e |
|||||||||||||||||||
|
|
|
ry", |
v . |
5, |
V ilnius, |
1985, |
p .8 5 - 9 3 . |
|
|
|
|
|||||||||||||||
T h e |
|
tw o - c rite ria |
|
problem |
of |
optim izing |
the |
H am il |
|||||||||||||||||||
to n ian |
c irc u it |
on |
a |
s u b s e t |
|
of |
|
n o d e s |
of |
a |
re fe re n c e |
||||||||||||||||
grid |
an d its |
h e u ristic |
so lu tio n |
alo n g |
|
with |
som e |
e x |
|||||||||||||||||||
p erim en tal |
r e s u lts |
|
a re |
given . |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
Fig . |
|
3, refr. 11. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
E. |
S h . |
|
G aifullin, |
G .N . |
|
Ja ro c h k in a , |
E lem ent |
|||||||||||||||||
|
|
|
m odels |
in |
the |
p la n a riz a tio n |
p h a s e |
|
of |
the |
|||||||||||||||||
|
|
|
h y brid |
|
IC |
|
lay o u t |
d e sig n . |
- |
T h e |
|
scien tific |
|||||||||||||||
|
|
|
w o rk s |
|
c o lle ctio n |
of |
h ig h er |
s c h o o ls |
" C o n s tru c |
||||||||||||||||||
|
|
|
tive |
d e sig n |
|
autom ation |
ir ra d io e le c tro n ic s |
||||||||||||||||||||
|
|
|
an d |
com puting |
m ach in ery ", |
v. |
5, |
|
V ilnius, 1985, |
||||||||||||||||||
|
|
|
p. 9 4 -1 0 3 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
T h e |
|
p a p e r |
|
d e a ls |
|
with |
the |
problem |
of |
in se rtin g |
|||||||||||||||||
the |
re v io u sly |
|
rem o v ed |
e d g e s |
of |
a |
g rap h |
|
w hf :h |
a r i |
|||||||||||||||||
s e s |
w hen |
the |
g ra p h |
|
is |
to |
|
be |
|
em b ed ed |
on |
|
a p lan e . |
||||||||||||||
T h e o p e ra tio n s |
of |
g rap h |
p la n a riz a tio n |
a re |
|
d e s c rib e d . |
|||||||||||||||||||||
E lem ent |
m odels |
tak in g |
into |
a c c o u n t |
m etric |
|
an d to p o |
||||||||||||||||||||
lo g ical |
|
re s tric tio n s |
a re |
|
s u g g e s te d . |
|
|
|
|
|
|
|
|
|
|||||||||||||
F ig . |
4; |
refr. |
11. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
L. |
K o so v . |
|
C lo s e s t |
|
point |
problem |
|
in |
g rap h ic |
|||||||||||||||
|
|
|
ed itin g |
|
of |
|
IS |
m a s k s . |
— T h e |
sc ie n tific |
w o rk s |
160
|
|
c o lle c tio n |
|
of |
h ig h er |
|
s c h o o ls |
" C o n s tru c tiv e |
d e - |
|||||||||||||||||
|
|
sin g |
*autom ation |
in |
ra d io e le c tro n ic s |
|
a n d |
co m |
||||||||||||||||||
|
|
puting |
m ach in ery ", |
v . |
5, |
V ilnius, |
1 9 8 5 , |
p. Ю З - |
||||||||||||||||||
|
|
1 0 8 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
T h is |
|
|
p a p e r |
|
d e a ls |
with |
the |
follow ing |
|
p ro b lem |
|
||||||||||||||
a ris in g |
in |
g rap h ic |
ed itin g of |
IS |
m a sk s: |
g iv en |
N |
p o |
||||||||||||||||||
in ts |
|
in |
|
the |
p lan e, |
find |
the |
c lo s e s t |
p o in t |
for |
q n y |
|||||||||||||||
new |
|
o n e . |
T h e |
d a ta |
s tru c tu re |
p ro v id in g |
q u ic k |
s e a r |
||||||||||||||||||
c h in g |
of |
th e |
c lo s e s t |
point |
a s |
|
w ell |
a s |
q u ic k |
d e le |
||||||||||||||||
tion |
o r |
addition |
|
of |
a |
point |
is |
s u g g e s te d . |
A ll |
a b o v e |
||||||||||||||||
o p e ra tio n s |
run |
in |
О |
|
( log |
N) |
tim e |
w hen |
|
so m e |
r e s |
|||||||||||||||
tric tio n s |
|
a re |
im p o sed . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
F ig . |
|
2, |
refr. |
|
5. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
V. |
|
Z h ile v ich iu s, |
A . |
S a k a la u s k a s . |
In te ra c tiv e |
|||||||||||||||||||
|
|
m ethods |
for |
p rin ted |
c irc u it |
la y o u t |
with |
|
CAD |
|||||||||||||||||
|
|
sy stem : |
m otivation, |
in te ra c tio n . |
— T h e |
s c ie n ti |
||||||||||||||||||||
|
|
fic |
|
w o rk s |
co lle ctio n |
o f h ig h e r |
s c h o o ls |
" C o n s |
||||||||||||||||||
|
|
tru c tiv e |
d e s ig n |
|
au to m atio n |
in |
r a d io e le c tr o n ic s |
|||||||||||||||||||
|
|
an d |
|
com puting |
|
m ac h in ery ", |
v . |
5, |
V ilnius, |
1 9 8 5 , |
||||||||||||||||
|
|
p. 1 0 9 - 1 1 4 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
T h is |
|
p a p e r |
s e r v e s |
to |
g ro u n d |
th e |
in te ra c tiv e |
m et |
|||||||||||||||||
hod |
o f d e sig n |
on |
a |
|
m edium |
|
o r |
high |
p ro d u c tiv ity |
com |
||||||||||||||||
p u ter |
with |
a |
d e v e lo p e d |
s y ste m |
|
of |
in p u t/o u tp u t |
g r a p |
||||||||||||||||||
hic |
d e v ic e s . |
In te ra c tiv e |
m eth o d s |
|
for |
d e s ig n |
|
of th e |
||||||||||||||||||
p rin ted |
c irc u its |
|
a re |
d e v e lo p e d |
on |
th e |
b a s is |
of |
th e |
|||||||||||||||||
algorithm |
— inform ation |
com plex^ CAD |
s y s te m . |
T h e |
||||||||||||||||||||||
a n a ly s is |
|
of |
the |
|
m ain |
re q u ire m e n ts |
to |
the |
m an |
— m a |
||||||||||||||||
c h in e in te ra c tio n |
la n g u a g e |
for |
s u c h |
a |
s y s te m |
is |
g i |
|||||||||||||||||||
v e n . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
R efr. |
|
7. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
A . |
|
T a rg a m a d z e , |
E . |
B a r e is c h a . |
S im ulation of lo |
|||||||||||||||||||
|
|
gic |
c irc u its |
c o n ta in in g |
LSI. |
- |
T h e |
|
s c ie n tific |
|||||||||||||||||
|
|
w o rk s |
c o lle c tio n of |
h ig h e r |
s c h o o ls |
|
" C o n s tru c |
|||||||||||||||||||
|
|
tiv e |
|
d e s ig n |
au to m atio n |
|
in |
r a d io e le c tr o n ic s |
a n d |
|||||||||||||||||
|
|
co m p u tin g |
|
m ac h in ery ", |
|
v. |
5, |
V ilnius, |
1 9 8 5 , |
p. |
||||||||||||||||
|
|
1 1 4 - 1 2 4 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 7 0