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

Предлагается общая 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