Embed Size (px)
Citation preview
Ein
Übe
rblic
küb
erPl
acem
entu
ndR
outin
gin
inte
grie
rten
Scha
ltung
enun
dSy
stem
en
Jean
-Pie
rre
Schw
icke
rath
Tech
nisc
heU
nive
rsitä
tDar
mst
adt
tud@
schw
icky
.net
Abs
trac
t
Esw
ird
aufd
iesp
ezifi
sche
nP
robl
eme
desP
lace
men
tund
des
Rou
tings
imE
ntw
urfv
onin
tegr
iert
enSc
haltu
ngen
ein-
gega
ngen
.Gen
etis
che
Alg
orith
men
(GA
)un
dst
ocha
stis
che
Verf
ahre
nbi
eten
eine
effiz
ient
eLö
sung
zudi
esen
mei
stN
P-
hart
enP
robl
emen
.Die
Nac
htei
lede
rG
Aun
dde
rst
ocha
sti-
sche
nVe
rfah
ren
könn
enum
gang
enw
erde
n,in
dem
man
bei-
den
Ans
ätze
mite
inan
derk
ombi
nier
t.D
iese
Idee
wir
der
läu-
tert
und
anha
ndei
nes
Bei
spie
lsw
ird
ein
gene
tisch
erP
lace
-m
entu
ndei
nR
outin
gA
lgor
ithm
user
klär
t.
1.E
inle
itung
Die
mei
sten
Prob
lem
e,di
ebe
imE
ntw
urf
von
inte
grie
r-te
nSc
haltu
ngen
auft
rete
nsi
ndse
hrsc
hwie
rige
kom
bina
-to
risc
heO
ptim
ieru
ngsp
robl
eme.
Meh
rere
,von
eina
nder
ab-
häng
ige
Kri
teri
enm
üsse
nun
terR
ücks
icht
nahm
eei
nerg
ros-
sen
Men
geni
cht
triv
iale
rB
edin
gung
enop
timie
rtw
erde
n.D
ieVo
rgän
gebe
steh
enau
sU
nter
prob
lem
en,d
iese
lbst
NP
-ha
rt,g
ross
und
gege
nsei
tigvo
nein
ande
rabh
ängi
gsi
nd[8
].M
eist
ens
beru
hen
die
Ber
echn
unge
nei
nes
solc
hen
Unt
er-
prob
lem
sau
fw
eite
ren,
noch
nich
tbe
rech
nete
nSc
hritt
en.
Som
üsse
nzu
rL
ösun
gde
rPr
oble
me
Abs
chät
zung
enzu
rH
ilfe
geno
mm
enw
erde
n.A
uch
Plac
emen
tund
Rou
ting
gehö
ren
zum
Ent
wur
fvon
Scha
ltung
(sie
heA
bbild
ung
1)un
dzu
dies
erK
ateg
orie
von
Prob
lem
en.M
anka
nnsi
eso
woh
lauf
der
Ebe
neei
ner
Pla-
tine
betr
acht
en(A
bbild
ung
2ze
igtb
eisp
ielh
aftd
enA
blau
fde
sE
ntw
urfs
eine
sPl
atin
e,di
eau
svo
rgef
ertig
ten
Funk
ti-on
sblö
cken
aufg
ebau
tw
ird)
,w
ofe
rtig
eSc
haltu
ngen
mit-
eina
nder
verb
unde
nw
erde
nm
üsse
n,w
ieet
wa
ein
zent
rale
rPr
ozes
sor,
Spei
cher
chip
sund
Ein
-und
Aus
gabe
mod
ule,
als
auch
inne
rhal
bei
nes
solc
hen
Chi
ps(a
uch
„Die
”ge
nann
t),
inde
mdi
vers
eFu
nktio
nsbl
öcke
(Rec
henw
erk,
Steu
erw
erk,
Reg
iste
r)od
erei
neG
ross
zahl
einz
elne
rTr
ansi
stor
enm
it-ei
nand
erve
rbun
den
wer
den
müs
sen.
Die
zulö
send
enPr
o-bl
eme
sind
die
glei
chen
und
die
dazu
verw
ende
ten
Alg
o-ri
thm
enäh
nlic
h.
Die
seA
usar
beitu
ngso
llei
nen
Übe
rblic
küb
erdi
ePr
o-bl
eme
gebe
n,di
ebe
imPl
acem
entu
ndbe
imR
outin
gau
ftre
-te
n.E
sw
ird
ein
gene
tisch
esun
dei
nst
ocha
stis
ches
Ver
fah-
ren
vorg
este
lltun
dbe
spro
chen
wie
die
Ver
fahr
ende
nsp
e-zi
elle
nPr
oble
men
imE
ntw
urfv
onin
tegr
iert
enSc
haltu
ngen
ange
pass
twer
den
könn
en.
Abb
ildun
g1.
Ent
wur
fei
nes
App
licat
ion-
spec
ific
inte
grat
edci
rcui
t(A
SIC
).[1
3]
2.Z
wei
getr
ennt
ePr
oble
me
mit
Gem
eins
am-
keite
n
Bei
mPl
acem
ent
geht
esda
rum
die
Kom
pone
nten
der
Scha
ltung
auf
dem
Subs
trat
zupl
atzi
eren
und
dabe
ive
r-sc
hied
ene
Vorg
aben
einz
uhal
ten.
Die
seVo
rgab
ensi
ndun
ter
ande
rem
:Min
imie
rung
derF
läch
ede
sben
ötig
ten
Subs
trat
s,de
rGes
amtlä
nge
derV
erbi
ndun
gen,
die
glei
chm
ässi
geV
er-
teilu
ngde
rH
itze
und
Ein
haltu
ngge
wis
ser
Lau
fzei
ten.
Sie
häng
enei
ners
eits
vom
Des
ign
ab,
ande
rers
eits
auch
vom
gew
ählte
nSu
bstr
at[7
].E
sm
uss
auss
erde
mge
nüge
ndPl
atz
für
das
Rou
ting
gela
ssen
wer
den.
Der
Plat
z,de
rna
chde
mPl
acem
enta
ufde
mSu
bstr
atüb
rig
blei
btw
ird
inre
chte
ckig
eFl
äche
n,so
gena
nnte
nR
outin
greg
ione
n,au
fget
eilt.
Die
Auf
gabe
des
Rou
tings
ist,
die
Ver
bind
unge
nzw
i-sc
hen
den
Kom
pone
nten
(Pin
s)he
rzus
telle
n.A
uch
hier
gel-
ten
Vorg
aben
wie
die
Min
imie
rung
der
Län
gede
rV
erbi
n-du
ngen
,der
Anz
ahla
nve
rwen
dete
nL
ayer
n(E
bene
n)un
dan
Ver
bind
unge
nzw
isch
ende
nL
ayer
n(V
ias)
,de
rSt
ö-ru
ngsq
uelle
n(C
ross
talk
)un
dde
sR
ausc
hen.
Rou
ting
bei
VL
SI1 -E
ntw
urf
wir
dm
eist
ens
ingl
obal
esR
outin
g(Z
u-te
ilung
von
Ver
bind
ungs
netz
enzu
gew
isse
nR
outin
greg
io-
nen)
und
deta
illie
rtes
Rou
ting
(gen
aue
Posi
tioni
erun
gde
rV
erbi
ndun
gsne
tze
inne
rhal
bei
nerR
outin
greg
ion)
aufg
etei
lt[1
1]. Die
Plac
emen
t-un
dR
outin
gvor
gäng
esi
ndvo
nein
an-
der
abhä
ngig
(wäh
rend
des
Plac
emen
tsm
uss
abge
schä
tzt
wer
den
wie
viel
Plat
zda
sR
outin
gfü
rdi
eno
twen
dige
nV
erbi
ndun
gen
benö
tigen
wir
d)ab
erih
reK
ompl
exitä
tve
r-la
ngt,
dass
sie
getr
ennt
vone
inan
der
beha
ndel
twer
den.
Je-
deE
ntsc
heid
ung,
die
getr
offe
nw
ird
hatA
usw
irku
ngen
auf
den
Res
tde
sPr
ozes
ses
inso
fern
,da
ssdi
ePl
atzi
erun
gei
-ne
rK
ompo
nent
eod
erda
sR
outin
gei
ner
Ver
bind
ung
wen
i-ge
rPla
tzfü
rdie
ande
ren
Kom
pone
nten
bzw
.Ver
bind
unge
nlä
sst.
Folg
lich
sollt
enPl
atzi
erun
gen
oder
Ver
bind
unge
n,di
eei
nen
gros
sen
Ein
fluss
auf
die
Opt
imie
rung
habe
nzu
erst
fest
gele
gtw
erde
n.
Abb
ildun
g2.
Abl
aufd
esD
esig
nsei
nes
Mul
ti-C
hip
Mod
uls.
[7]
1 Ver
yL
arge
Scal
eIn
tegr
ated
2.1.
Das
Plac
emen
t-Pr
oble
m
Das
Plac
emen
t-Pr
oble
mka
nnfo
lgen
derm
asse
nde
finie
rtw
erde
n[9
]:U
nter
Ver
wen
dung
1.ei
nerM
enge
rech
teck
iger
Kom
pone
nten
(Zel
len)
,jed
em
itei
ner
Anz
ahla
nPi
nsan
vorg
egeb
enen
Posi
tione
nen
tlang
dem
Ran
dde
rZel
lepo
sitio
nier
t,
2.ei
nerN
etlis
t,di
edi
eV
erbi
ndun
gen
zwis
chen
alle
nPi
nssp
ezifi
zier
t,un
d
3.ei
neru
ngef
ähre
nho
rizo
ntal
enL
änge
Wde
szu
entw
er-
fend
enC
hips
.
Ber
echn
e
1.di
eab
solu
tePo
sitio
nje
derZ
elle
,
2.di
eO
rien
tieru
ngun
dSp
iege
lung
jede
rZel
le,
3.ei
nR
echt
eck
B,d
ass
die
Form
des
Chi
psde
finie
rt.
Das
Zie
list
es,d
ieFl
äche
von
Bzu
min
imie
ren
unte
rde
nVo
rgab
en,d
ass
kein
ezw
eiZ
elle
nsi
chüb
erla
ppen
,das
sda
sR
echt
eck
Bal
leZ
elle
num
fass
tund
unge
fähr
die
Län
geW
hat,
und,
dass
die
Fläc
hen
inne
rhal
bvo
nB
,die
nich
tvo
nZ
elle
nbe
legt
wer
den,
gros
sge
nug
sind
umda
sR
outin
gde
rV
erbi
ndun
gen
zube
inha
lten.
Ein
idea
lerP
lace
men
talg
orith
-m
usso
llte
folg
lich
das
fläch
enm
ässi
gkl
eins
tmög
liche
Lay
-ou
tgen
erie
ren,
dass
den
elek
tris
chen
und
ther
mis
chen
Re-
geln
ents
pric
ht.
2.2.
Das
Rou
ting-
Prob
lem
Das
Rou
ting-
Prob
lem
kann
als
solc
hes
defin
iert
wer
den
[7]:
Geg
eben
sei
eine
frei
eFl
äche
,ei
neM
enge
von
Pins
und
eine
Net
list.
Ber
echn
edi
ePo
sitio
nun
dde
nV
erla
ufal
-le
rV
erbi
ndun
gen
zwis
chen
den
Pins
,so
dass
die
min
imal
eA
nzah
lan
Lay
ern
benu
tztw
ird,
Lau
fzei
ten
und
Rau
sche
nm
inim
iert
wer
den,
sow
ieH
erst
ellu
ngse
insc
hrän
kung
enei
n-ge
halte
nw
erde
n.D
iese
Ein
schr
änku
ngen
bein
halte
n,da
ssve
rsch
iede
neN
ets2
sich
nich
tauf
eine
mL
ayer
kreu
zen
kön-
nen
und,
dass
sie
eine
nM
inim
alab
stan
dvo
nein
ande
rhab
enm
üsse
n.U
nter
Um
stän
den
darf
nurd
ieM
anha
ttan
Geo
me-
trie
3be
nutz
twer
den.
Abb
ildun
g3
illus
trie
rtdi
eses
Prob
lem
.Dor
tgi
ltes
die
Net
szw
isch
ende
mPi
nsm
itde
rgl
eich
enN
umm
erzu
rou-
ten.
Bei
dem
Prob
lem
hand
elte
ssi
chum
ein
soge
nann
tes
Cha
nnel
-Rou
ting-
Prob
lem
wei
lsi
chdi
ePi
nsau
ssch
liess
-lic
hau
fzw
eige
genü
berl
iege
nden
Seite
nei
nes
für
Rou
ting
zurV
erfü
gung
steh
ende
nR
echt
ecks
,befi
nden
.Dab
eist
elle
ndi
ege
stri
chel
ten
Lin
ien
die
Ver
bind
unge
nau
fein
emer
sten
2 Ein
Net
iste
ine
Men
gevo
nPu
nkte
n(P
ins)
,die
zuve
rsch
iede
nen
Blö
-ck
enge
höre
nun
ddi
em
itein
ande
rve
rbun
den
wer
den
müs
sen.
3 Nur
horiz
onta
leun
dve
rtika
leSe
gmen
tedü
rfen
benu
tztw
erde
n.
Lay
er,u
nddi
edu
rchg
ezog
enen
Lin
ien
auf
eine
m2.
Lay
erda
r.D
iege
füllt
enR
echt
ecke
sind
Via
s,al
soV
erbi
ndun
gen
von
eine
mL
ayer
zum
ande
ren.
Die
Lös
ung
genü
gtde
neb
enge
nann
ten
Bed
ingu
ngen
.
Abb
ildun
g3.
Bei
spie
lfü
rei
nC
hann
el-
Rou
ting-
Pro
blem
(a)
und
eine
mög
liche
Lö-
sung
(b).
[11]
3.G
rund
sätz
liche
algo
rith
mis
che
Übe
rleg
un-
gen
zude
nPr
oble
men
Sow
ohlR
outin
gal
sau
chPl
acem
ents
ind
NP
-har
tePr
o-bl
eme.
Selb
stda
sei
nfac
heB
erec
hnen
der
kürz
este
nV
er-
bind
ung
zwis
chen
eine
rM
enge
von
Tran
sist
oren
istg
leic
hsc
hwer
wie
das
Lös
ende
sSt
eine
rPr
oble
ms
inei
nem
Gra
-ph
en(S
PG),
wel
ches
NP
-har
tist
.Als
die
Anz
ahld
erTr
an-
sist
oren
inei
ner
Scha
ltung
imm
ergr
össe
rw
urde
und
man
die
Plac
emen
t-un
dR
outin
g-Pr
oble
me
nich
tm
ehr
effiz
i-en
tlös
enko
nnte
,ist
man
auf
die
Such
ena
chne
uen
Alg
o-ri
thm
enge
gang
en.M
ittle
rwei
lew
erde
nis
tfas
talle
nC
AD
-Pr
ogra
mm
enzu
mE
ntw
urfv
onSc
haltu
ngen
gene
tisch
eA
l-go
rith
men
und
stoc
hast
isch
eV
erfa
hren
verw
ende
t,di
eim
folg
ende
nku
rzvo
rges
tellt
wer
den.
3.1.
Sim
ulat
edA
nnea
ling
(SA
)
Das
inde
rC
AD
-Com
mun
ityam
belie
btes
ten
stoc
hast
i-sc
heV
erfa
hren
istd
as“S
imul
ated
Ann
ealin
g”.
Der
Alg
orith
mus
ist
dafü
rbe
kann
t,da
sser
auf
Kos
-te
nüb
ertr
iebe
nla
nger
Lau
fzei
tqua
litat
ivho
chw
ertig
eL
ö-su
ngen
bere
chne
t.D
erA
lgor
ithm
usis
tei
neG
ener
alis
ie-
rung
derM
onte
-Car
lo-M
etho
de,i
nde
rdas
Ein
frie
ren
eine
rFl
üssi
gkei
tode
rdie
Kri
stal
lisie
rung
eine
sM
etal
lssi
mul
iert
wir
d.E
ine
ursp
rüng
lich
gesc
hmol
zene
Subs
tanz
wir
dso
lang
sam
abge
kühl
t,da
sssi
esi
chim
mer
bein
ahe
imth
erm
o-dy
nam
isch
enG
leic
hgew
icht
befin
det
(Abb
ildun
g4)
.D
as
Zie
list
eine
mög
lichs
tgle
ichm
ässi
geK
rist
allis
ieru
ngzu
er-
halte
n.
Abb
ildun
g4.
Glo
bale
Str
uktu
rde
sS
imul
ated
Ann
ealin
gA
lgor
ithm
us.[
12]
3.2.
Gen
etis
che
Alg
orith
men
(GA
)
Gen
etis
che
Alg
orith
men
,die
mit
prob
abili
stis
chen
Übe
r-gä
ngen
nach
vort
eilh
afte
nA
npas
sung
enin
eine
rsi
chim
-m
erän
dern
den
Um
gebu
ngsu
chen
(Abb
ildun
g5)
wer
den
imE
ntw
urfv
onin
tegr
iert
enSc
haltu
ngen
oftv
erw
ende
t.D
ortb
ilden
Chr
omos
ome
eine
abtr
akte
Dar
stel
lung
des
Prob
lem
s.In
divi
duen
sind
pote
ntie
lleL
ösun
gen
dies
esPr
o-bl
ems.
Die
seIn
divi
duen
durc
hlau
fen
eine
nE
volu
tions
pro-
zess
,der
aus
drei
Hau
ptte
ilen
best
eht:
•Se
lekt
ion
besc
hrei
btdi
ePh
ase,
inde
rm
ehre
reIn
divi
-du
enfü
rde
nw
eite
ren
Evo
lutio
nspr
ozes
sau
sgew
ählt
wer
den.
Die
sge
schi
etan
hand
derF
itnes
sei
nes
Indi
vi-
duum
s,di
eau
ssag
twie
„gut
”di
eses
Indi
vidu
um(a
lso
die
Lös
ung)
ist.
•D
iese
ausg
ewäh
len
Indi
vidu
enw
erde
nde
rK
reuz
ung
(cro
ssov
erod
erre
com
bina
tion)
unte
rzog
en.E
sen
tste
-he
nne
ueIn
divi
duen
mit
den
best
enE
igen
scha
ften
der
sele
ktie
rten
Vorf
ahre
n.
•W
ähre
ndde
rMut
atio
nw
erde
ndi
ene
uerz
eugt
enIn
di-
vidu
enve
ränd
ertu
mdi
eV
ielfa
ltde
rneu
eB
evöl
keru
ngzu
gara
ntie
ren.
Lau
t[8
]si
ndG
Afü
rC
AD
-Pro
blem
ebe
sten
sge
eign
et,
denn
:
•D
iere
lativ
ePe
rfor
man
zvo
nG
Ave
rbes
sert
sich
mit
derK
ompl
exitä
t,un
ddi
ePr
oble
me
mit
dene
nhi
erge
-ha
ndha
btw
ird,
sind
sehr
kom
plex
.
•G
Asi
ndvo
nN
atur
aus
para
llelis
ierb
arun
dbe
inah
eli-
near
eSk
alie
rung
wur
deau
fMIM
D-A
rchi
tekt
uren
4er
-zi
elt.
Der
Gro
sste
ilde
rR
eche
nzei
tfä
lltbe
ide
rB
e-re
chnu
ngde
rFi
tnes
s(K
oste
nfun
ktio
n)an
.Die
Sele
k-tio
nun
ddi
eM
utat
ion
sind
nich
trec
heni
nten
siv.
Folg
-lic
hka
nnda
sB
erec
hnen
einz
elne
rK
oste
nfun
ktio
nen
auf
Clu
ster
knot
enau
sgel
ager
tw
erde
n,da
zwis
chen
den
Kos
tenf
unkt
ione
nke
inD
aten
aust
ausc
hst
attfi
nden
brau
cht.
InE
ntw
ickl
ungs
einr
icht
unge
nvo
nin
tegr
ier-
ten
Scha
ltung
ensi
ndof
tvie
leve
rnet
zte
Rec
hner
vor-
hand
enau
fde
nen
viel
epa
ralle
leG
Aau
sgef
ührt
wer
-de
nkö
nnen
.Im
Geg
ensa
tzda
zusi
ndSA
basi
erte
Al-
gori
thm
enan
sich
sequ
enzi
ell
und
dadu
rch
sind
viel
schl
echt
erpa
ralle
lisie
rbar
.
•B
eide
rE
ntw
ickl
ung
eine
rSc
haltu
ngw
erde
nge
wis
seSc
hritt
ese
hrof
tite
rativ
wie
derh
olt.
Ein
idea
les
CA
DW
erkz
eug
sollt
edi
eM
öglic
hkei
tbi
eten
zwis
chen
1)ei
ner
über
wie
gend
gute
nab
erse
hrsc
hnel
lbe
rech
ne-
ten
Lös
ung
und
2)ei
ner
qual
itativ
hoch
wer
tigen
Lö-
sung
für
die
man
alle
rdin
gsm
ehr
Rec
henz
eit
opfe
rnm
uss,
zuw
ähle
n.G
Abe
rech
nen
eine
sehr
gute
Lö-
sung
,wen
nm
ansi
ela
nge
lauf
enlä
sst,
aber
dank
der
schn
elle
nK
onve
rgen
zde
sA
lgor
ithm
usin
den
erst
enG
ener
atio
nen
kann
man
inne
rhal
bkü
rzes
ter
Zei
tein
ere
lativ
gute
Lös
ung
bere
chne
n.
3.3.
Die
Fusi
on:S
AG
A
Ein
Prob
lem
der
GA
ist
ihr
Kon
verg
enzv
erha
lten.
Am
Anf
ang
verb
esse
rtsi
chdi
eK
oste
nfun
ktio
nse
hrsc
hnel
labe
rda
nnw
ird
esse
hrsc
hwer
wei
tere
Ver
bess
erun
gen
zuer
zie-
len.
Ein
Gro
sste
ilde
rR
eche
nzei
tgeh
tim
spät
eren
Abl
auf
des
Alg
orith
mus
verl
oren
,wo
nurs
ehrk
lein
eV
erbe
sser
un-
gen
sehr
lang
sam
erzi
eltw
erde
n.A
usse
rdem
iste
inG
Aim
-m
erde
rG
efah
rau
sges
etzt
sich
inei
nem
loka
len
Opt
imum
zuve
rfan
gen.
Esb
ense
nun
dM
azum
der
besc
hrei
ben
in[9
]w
iem
anm
itse
hrei
nfac
hen
Mitt
eln
dem
entg
egen
kom
men
kann
.Die
Idee
istS
Azu
verw
ende
n,de
rau
chim
spät
eren
Teil
der
Ber
echn
ung
imm
erno
chre
spek
tabl
eV
erbe
sser
un-
gen
erzi
elta
bera
mA
nfan
gni
chts
osc
hnel
lkon
verg
iert
wie
ein
GA
.Die
ses
SAG
A-V
erfa
hren
begi
nntm
itde
rA
usfü
h-ru
ngei
nes
rein
enG
A.W
enn
dies
erda
nnbe
inah
ezu
rSt
a-gn
atio
nko
mm
t,w
echs
eltS
AG
Aim
mer
meh
rzu
rA
usfü
h-ru
ngvo
nSA
.4 M
ultip
leIn
stru
ctio
nM
ultip
leD
ata-
Arc
hite
ktur
en,
wie
Shar
ed-
Mem
ory-
Mul
tipro
zess
orsy
stem
eod
erve
rnet
zte
Rec
hner
[10]
.
Abb
ildun
g5.
Glo
bale
Str
uktu
rei
nes
gene
ti-sc
hen
Alg
orith
mus
.[12
]
Abb
ildun
g6
zeig
t,w
iem
andi
ezw
eiA
lgor
ithm
enm
it-ei
nand
erko
mbi
nier
enka
nn.
Πc
ist
die
Bev
ölke
rung
,di
ebe
trac
htet
wir
d.D
ieevaluate()
Rou
tine
ist
die
Kos
ten-
funk
tion,
die
best
imm
twie
gute
ine
Lös
ung
ist.
Wen
nfü
rRG
ener
atio
nen
kein
em
essb
aren
Ver
bess
erun
gen
aufg
etre
ten
sind
,dan
nw
ird
die
Bev
ölke
rung
szah
lMre
duzi
ertu
ndih
reM
utat
ions
rate
p mut
wir
der
höht
.Das
istd
ann
derÜ
berg
ang
zuSA
.E
xper
imen
teun
dB
ench
mar
ks(A
bbild
ung
7)be
lege
n,da
ssde
rst
ocha
stis
che
Opt
imie
rung
salg
orith
mus
SAG
Am
inde
sten
sge
naus
ogu
tist
wie
ande
reSy
stem
eun
din
vie-
len
Fälle
nso
gar
die
Fläc
hede
rSc
haltu
ngw
eite
rre
duzi
e-re
nka
nnun
dda
bei
soga
rei
nekü
rzer
eL
aufz
eit
aufw
eist
.D
ieve
rwen
dete
nB
ench
mar
ksau
sA
bbild
ung
7si
nddi
ede
sM
CN
CIn
tern
atio
nalW
orks
hop
onPl
acem
enta
ndR
outin
gvo
n19
92.
4.Pl
acem
ent
Bei
mPl
acem
entg
ibte
sei
nA
spek
t,de
rim
mer
wic
htig
erw
ird:
die
Län
gede
rVer
bind
unge
n.M
itst
eige
nden
Freq
uen-
zen
mus
sim
mer
meh
rdar
aufg
each
tetw
erde
n,da
ssda
sSi
-gn
alla
nge
genu
gan
liegt
umvo
nde
rQ
uelle
(Driv
er)
zur
Senk
e(T
erm
inal
,Si
nk)
zuko
mm
en.S
ollte
dies
nich
tde
rFa
llse
in,
müs
sen
Buf
fer
eing
ebau
tw
erde
n.D
iese
kost
enw
iede
rum
Zei
tund
Plat
z.B
eila
ngen
Ver
bind
ungs
leitu
ngen
tritt
zude
mda
sPro
blem
desW
ider
stan
desu
ndde
rKap
azitä
tau
f.D
ieL
eitu
ngen
müs
sen
nahe
beim
Driv
erdi
cker
sein
als
Abb
ildun
g6.
Der
Übe
rblic
küb
erS
AG
A.[
9]
beim
Term
inal
.Das
beei
nflus
stbe
imPl
acem
entd
enPl
atz,
derf
ürda
sR
outin
gre
serv
iert
wer
den
mus
s.A
ufG
rund
der
Wid
erst
ände
,di
eau
ftre
ten
könn
ear
-be
iten
Plac
emen
t-W
erkz
euge
mit
soge
nann
ten
dela
yod
erpe
rfor
man
ce-o
rien
ted
Plac
emen
t[7]
.Dor
tbes
chrä
nken
Ti-
min
gbed
ingu
ngen
die
ober
eSc
hran
kede
rV
erbi
ndun
gslä
n-ge
n,di
eda
nnbe
imPl
acem
entb
erüc
ksic
htig
twer
den.
Wen
nm
anm
ehr
als
zwei
Pins
auf
eine
mN
etha
t,da
nnbe
stim
mt
die
Topo
logi
ede
sNet
zesd
esse
nV
erzö
geru
ng.E
sist
schw
erw
ähre
ndde
sPl
acem
ents
die
Ver
zöge
rung
zuap
prox
imie
-re
n.Z
udi
esem
Zw
eck
wur
devo
rges
chla
gen
das
glob
ale
Rou
ting
und
das
Plac
emen
tgle
ichz
eitig
zube
arbe
iten
[2].
Wei
tere
Ans
ätze
betr
acht
enst
attd
esse
nde
nW
ider
stan
dde
rL
eitu
ngun
ddi
eK
apaz
itätd
erSe
nken
.B
eide
ntr
aditi
onel
len
Plac
emen
t-A
nsät
zen
gibt
eszw
eiG
rupp
en:k
onst
rukt
ive
und
itera
tive.
Die
kons
truk
tiven
nehm
enei
nun
volls
tänd
iges
Plac
e-m
enta
lsE
inga
bean
und
prod
uzie
ren
dank
best
imm
ten
Re-
geln
ein
fert
iges
Plac
emen
t.D
afür
wer
den
oftM
in-C
utba
-si
erte
Alg
orith
men
verw
ende
t,di
esu
kzes
sive
Anw
endu
n-ge
nvo
nPa
rtiti
onin
g[1
]be
nutz
en.G
rund
sätz
lich
funk
tio-
nier
tder
Alg
orith
mus
wie
folg
t:
1.Te
iledi
ePl
acem
entfl
äche
inzw
ei.
2.Ta
usch
edi
eL
ogik
zelle
num
die
Schn
ittko
sten
zum
i-ni
mie
ren.
3.W
iede
rhol
eab
Schr
itt1.
Teile
imm
erkl
eine
reSt
ücke
bis
alle
Log
ikze
llen
plat
zier
tsin
d.
Abb
ildun
g7.
Verg
leic
hde
rFl
äche
nde
rE
r-ge
bnis
sevo
nS
AG
Aun
dan
dere
nA
lgor
ith-
men
.[9]
Abb
ildun
g8
zeig
twie
man
das
Teile
ndu
rchf
ührt
:
(a)
Teile
den
Chi
pm
itei
nem
Gitt
erin
Beh
älte
rauf
.
(b)
Führ
eal
leV
erbi
ndun
gen
zum
Mitt
elpu
nktd
esje
wei
li-ge
nB
ehäl
ters
.
(c)
Mac
heei
nen
Schn
ittun
dta
usch
edi
eL
ogik
zelle
num
die
Kos
ten
des
Schn
itts
zum
inim
iere
n.
(d)
Nim
mdi
ege
teilt
enH
älft
enun
den
tfer
neal
leK
ante
n,di
eni
chti
nner
halb
eine
rHäl
fte
sind
.
(e)
Wie
derh
ole
den
Proz
ess
mit
eine
mne
uen
Schn
ittun
dfa
hre
fort
bis
nurn
och
einz
elne
Beh
älte
rübr
igsi
nd.
Abb
ildun
g8.
Min
-Cut
Pla
cem
ent.
[13]
Bei
den
itera
tiven
Met
hode
nw
ird
ein
Ann
ahm
efü
rda
sPl
acem
ent
gem
acht
und
dann
wir
ddi
ese
verf
eine
rtin
dem
man
Bed
ingu
ngen
für
ein
bess
eres
Plac
emen
tbe
rück
sich
-tig
t.D
ieG
A-u
ndSA
-Ans
ätze
falle
nin
dies
eK
ateg
orie
.In
jede
rIte
ratio
nw
ird
eine
Kom
pone
nte
gedr
ehto
derv
ersc
ho-
ben
und
wen
ndi
eK
onfig
urat
ion
bess
eris
tals
die
vorh
erig
e,da
nnw
irdi
ese
als
neue
Gru
ndla
gege
nom
men
.Bei
den
ite-
rativ
enV
erfa
hren
gibt
esgr
unds
ätzl
ich
zwei
Kri
teri
en:
•D
asSe
lekt
ions
krite
rium
,das
ents
chei
detw
elch
eZ
elle
vers
chob
enw
erde
nso
ll.
•D
asM
essk
rite
rium
,das
ents
chei
deto
bdi
eau
sgew
ähl-
teZ
elle
nun
vers
chob
enw
ird.
Wen
nm
anda
sSi
mul
ated
Ann
ealin
gV
erfa
hren
auf
das
Plac
emen
tanw
ende
t,si
ehtd
erA
lgor
ithm
usfo
lgen
derm
as-
sen
aus
[13]
:
1.W
ähle
eine
Log
ikze
llefü
rei
nen
pote
ntie
llen
Taus
ch,
mei
sten
szu
fälli
gau
sgew
ählt.
2.B
erec
hne
die
obje
ktiv
eFu
nktio
nE
fürd
asne
uePl
ace-
men
t.
3.W
enn
∆Ene
gativ
oder
Nul
list
,dan
nw
erde
ndi
eL
o-gi
kzel
len
geta
usch
t.W
enn
∆Epo
sitiv
ist,
dann
wer
den
die
Zel
len
mit
eine
rW
ahrs
chei
nlic
hkei
tvo
ne−
∆E/
T
geta
usch
t(M
essk
rite
rium
).
4.W
iede
rhol
eab
Schr
itt1
für
eine
fest
eA
nzah
lan
Dur
chlä
ufen
und
senk
edi
eTe
mpe
ratu
rT
nach
eine
mA
bküh
lung
ssch
ema.
Zum
Bei
spie
lTn+
1=
0.9T
n.
5.R
outin
g
Wen
nda
sPl
acem
ent
abge
schl
osse
nis
tge
htes
beim
Rou
ting
umdi
ege
naue
Fest
legu
ngde
rV
erbi
ndun
gsne
tze.
Alle
Bed
ingu
ngen
,die
beim
Plac
emen
tein
eR
olle
spie
lten,
gelte
nau
chhi
erun
dm
üsse
nzu
sam
men
mit
wei
tere
nB
edin
-gu
ngen
eing
ehal
ten
wer
den.
Alle
dies
eB
edin
gung
enw
er-
den
eine
nach
der
ande
ren
auf
Erf
üllu
ngge
test
et,w
enn
esda
rum
geht
die
Qua
lität
eine
rgen
erie
rten
Lös
ung
zube
wer
-te
n.E
sgi
btab
erau
chA
lgor
ithm
en,d
ievo
nih
rem
Abl
auf
her
bei
der
Gen
erie
rung
neue
rL
ösun
gen
gew
isse
nB
edin
-gu
ngen
nach
kom
men
.A
nhan
dde
sBei
spie
lsau
sAbb
ildun
g9
soll
erlä
uter
twer
-de
n,w
ieC
hann
el-R
outin
gm
itH
ilfe
von
gene
tisch
enA
lgo-
rith
men
funk
tioni
eren
kann
.Im
Cha
nnel
-Rou
ting-
Prob
lem
kann
ein
Indi
vidu
umal
sda
sE
rgeb
nis
eine
sR
outin
gsbe
-tr
acht
etw
erde
n.D
ieQ
ualit
ätdi
eses
Rou
tings
kann
anha
ndde
rFi
tnes
sde
sIn
divi
duum
sfe
stge
stel
ltw
erde
n.A
mA
n-fa
ngw
ird
eine
initi
ale
Bev
ölke
rung
zufä
llig
erze
ugt.
Die
-se
Bev
ölke
rung
wir
dei
nem
Evo
lutio
nspr
ozes
s(w
iein
3.2
besc
hrie
ben)
ausg
eset
zt.W
enn
die
Sim
ulat
ion
funk
tioni
ert,
dann
wer
den
imm
erbe
sser
eIn
divi
duen
inde
rB
evöl
ke-
rung
vorh
errs
chen
,wei
lsie
eine
höhe
reW
ahrs
chei
nlic
hkei
tha
ben,
Nac
hfah
ren
zupr
oduz
iere
n,di
enu
rdi
ebe
sten
Ei-
gens
chaf
ten
ihre
rVor
fahr
ener
ben.
Die
sebe
sten
Indi
vidu
en
sind
gena
udi
ebe
sten
Rou
tingl
ösun
gen,
die
den
gew
ünsc
h-te
nK
rite
rien
ents
prec
hen.
Die
Anz
ahld
erIn
divi
duen|P
c|bl
eibt
kons
tant
über
alle
Gen
erat
ione
nhi
nweg
.Am
End
ede
sAlg
orith
mus
wir
dp b
est
eine
rOpt
imie
rung
unte
rzog
enun
dbi
ldet
dann
die
endg
ülti-
geL
ösun
gde
sR
outin
gs.
Abb
ildun
g9.
Um
riss
eine
sge
netis
chen
Rou
-tin
galg
orith
mus
.[11
]
Der
Erz
eugu
ngsp
roze
ssde
rin
itial
enB
evöl
keru
nglä
uft
wie
folg
tab.
Am
Anf
ang
wir
dei
neB
evöl
keru
ngau
szu
fäl-
ligen
Indi
vidu
ener
zeug
t.N
unw
ünsc
htm
ansi
chdi
eV
er-
bind
ung
zwis
chen
den
Pins
s iun
dt j
.Daz
uw
ird
von
beid
enPi
nsau
sein
ese
nkre
chte
Lin
ieer
zeug
tbis
dies
eau
fein
Hin
-de
rnis
triff
t,zu
mB
eisp
ield
enR
and
derR
outin
greg
ion
oder
ein
ande
res,
scho
nge
rout
etes
Net
z(A
bbild
ung
10(a
,b))
.Z
wis
chen
den
End
punk
ten
der
gera
deer
zeug
ten
Erw
eite
-ru
ngsl
inie
nw
ird
jew
eils
zufä
llig
ein
Punk
tbes
timm
t.Vo
ndo
rtau
sw
erde
nw
aage
rech
teL
inie
nin
beid
eR
icht
unge
ner
zeug
t(A
bbild
ung
10(c
)).D
ieSu
che
geht
wei
ter
inde
mm
anau
fde
nw
aage
rech
ten
Lin
ien
zwei
zufä
llige
Punk
teau
swäh
ltun
ddo
rtse
nkre
chte
Erw
eite
rung
slin
ien
vera
nker
t(A
bbild
ung
10(d
)).
Das
Lay
erdi
eser
Lin
ien
wir
dw
iefo
lgtb
estim
mt.
Jede
sL
ayer
hate
ine
bevo
rzug
teR
outin
gric
htun
gun
dse
irn
eine
zufä
llige
Zah
lzw
isch
en0
und
1.W
enn
r n≤
2/3
dann
wir
ddi
eL
inie
auf
das
Lay
erge
setz
t,da
ssih
reR
outin
gric
htun
gbe
vorz
ugt.
And
ernf
alls
wir
ddi
eL
inie
aufd
asan
dere
Lay
erge
setz
t.D
erE
rwei
teru
ngsl
inie
npro
zess
wir
dbe
ende
twen
n
•E
rwei
teru
ngsl
inie
nbe
ider
Punk
tetr
effe
nsi
chau
fdem
glei
chen
Lay
er
•D
ieE
rwei
teru
ngsl
inie
von
s itr
iffta
ufei
nePu
nkt,
der
scho
nzu
mN
etz
von
t jge
hört
(wie
inA
bbild
ung
10(e
))od
erum
geke
hrt.
Sollt
edi
eE
rzeu
gung
derE
rwei
teru
ngsl
inie
nni
chti
nner
-ha
lbvo
niI
tera
tione
nzu
mE
nde
kom
men
,dan
nw
erde
nal
leE
rwei
teru
ngsl
inie
nge
lösc
ht,d
ieR
outin
greg
ion
zufä
llig
umei
neG
itter
linie
erw
eite
rtun
ddi
eL
inie
nne
uer
zeug
t.W
enn
nach
zehn
Erw
eite
rung
ende
rR
outin
greg
ion
im-
mer
noch
kein
eV
erbi
ndun
ghe
rges
tellt
wer
den
konn
te,d
ann
wir
ddi
ese
Bev
ölke
rung
kom
plet
taus
gelö
scht
und
zufä
llig
neu
erze
ugt.
Der
Rou
tingp
roze
ssw
ird
abge
schl
osse
nin
dem
der
kür-
zest
eW
egau
fden
Erw
eite
rung
slin
ien
gew
ählt
wir
d.
Abb
ildun
g10
.Bei
spie
lfür
ein
zufä
llige
sR
ou-
ting
zwis
chen
s iun
dt j
.[11
]
Die
ser
Cha
nnel
-Rou
ting
Alg
orith
mus
liefe
rtse
hrgu
teE
rgeb
niss
e,w
iede
rVer
glei
chbe
kann
terC
hann
el-R
oute
rin
Abb
ildun
g11
zeig
t.D
erA
lgor
ithm
usw
urde
nach
150
Ge-
nera
tione
nun
terb
roch
enun
dm
itje
wei
ls| P
c|=
50In
divi
du-
enau
sgef
ührt
.Dab
eiko
nnte
erso
gar
den
Joo6
_16
Ben
ch-
mar
kau
sfüh
ren,
ande
mde
rG
reed
yA
lgor
ithm
usge
sche
i-te
rtis
t. Abb
ildun
g11
.Ben
chm
arke
rgeb
niss
e.[1
1]
6.Z
usam
men
fass
ung
und
Aus
blic
k
Bei
Plac
emen
tun
dR
outin
gha
tm
anes
mit
NP
-har
ten
Prob
lem
enzu
tun.
Vie
le,v
onei
nand
erab
häng
ige
Kri
teri
enm
üsse
nun
terB
erüc
ksic
htig
ung
nich
ttriv
iale
rBed
ingu
ngen
optim
iert
wer
den.
Bei
der
heut
igen
Grö
sse
und
Kom
plex
i-tä
tder
Scha
ltung
enis
tes
nich
tmeh
rmög
lich
dies
em
ittr
a-di
tione
llen
kom
bina
tori
sche
nV
erfa
hren
zube
arbe
iten.
Seit
Mitt
ede
r199
0erJ
ahre
sind
imm
erm
ehrg
enet
isch
eun
dst
o-ch
astis
che
Ver
fahr
enim
Ein
satz
.Sie
habe
nde
nVo
rtei
lseh
rsc
hnel
lzu
konv
ergi
eren
und,
wen
nm
anih
nen
genü
gend
Lau
fzei
tzur
Ver
fügu
ngst
ellt,
liefe
rnsi
eau
chqu
alita
tivex
-ze
llent
eE
rgeb
niss
e.E
inw
icht
iges
Kri
teri
umde
rA
lgor
ith-
men
isti
hre
inhä
rent
ePa
ralle
lisie
rbar
keit.
Nur
soka
nnge
-w
ährl
eist
etw
erde
n,da
sssi
ein
vert
retb
arer
Zei
tbea
rbei
tet
wer
den
könn
en,w
ieet
wa
die
gene
tisch
enA
lgor
ithm
en,d
ieau
fver
netz
ten
Rec
hner
sehr
guts
kalie
ren.
Was
Ben
chm
arks
ange
htso
stel
ltSm
ithin
[13]
fest
,das
sm
anC
AD
-Alg
orith
men
,die
aufZ
ufal
lsda
ten
zurü
ckgr
eife
nse
hrsc
hlec
htve
rgle
iche
nka
nn.D
ieE
rgeb
niss
esi
ndni
cht
wie
derh
olba
rund
Ver
glei
che
aufz
uste
llen
istg
ewag
t,es
sei
denn
man
hats
tatis
tisch
ausr
eich
end
viel
eTe
stlä
ufe
fürs
ta-
tistis
chau
srei
chen
dvi
ele
Chi
psdu
rchg
efüh
rt.
Cha
nget
al.h
aben
in[3
]Pl
acem
entu
ndR
outin
gW
erk-
zeug
e(D
rago
n,C
api,
mPL
,mPG
und
QPl
ace)
mite
inan
der
verg
liche
n.Si
eha
ben
die
Wer
kzeu
geau
fPr
oble
me
ange
-se
tzt,
dere
nop
timal
eV
erbi
ndun
gsne
tzlä
ngen
beka
nnts
ind.
Sie
sind
zude
mSc
hlus
sge
kom
men
,da
ssdi
eL
änge
der
Ver
bind
unge
nin
den
Erg
ebni
ssen
imD
urch
schn
itt1.
62bi
s2.
07M
allä
nger
war
enal
sdi
eop
timal
enL
ösun
gen.
Sie
stel
lten
eben
falls
fest
,das
sdi
eQ
ualit
ätde
rL
ösun
gen
um9%
bis
17%
schl
echt
erw
urde
n,w
enn
das
Prob
lem
umFa
k-to
r10
verg
röss
ert
wur
de.
Dar
aus
kann
mal
folg
ern,
dass
Wer
kzeu
gezu
mE
ntw
urfv
onSc
haltu
ngen
imm
erno
chve
r-be
sser
ungs
fähi
gsi
nd.
Sollt
edi
esge
linge
n,so
kom
mt
esde
mFo
rtsc
hritt
meh
rere
rGen
erat
ione
nan
Her
stel
lung
sver
-fa
hren
glei
ch.
Lite
ratu
r
[1]
M.B
reue
r.M
in-c
utpl
acem
ent.
Jour
nalo
fDes
ign
Aut
oma-
tion
and
Faul
tTol
eran
tCom
putin
g,1(
4):3
43–3
82,O
ctob
er19
77.
[2]
M.B
urst
ein.
Ano
npl
acem
ent-
rout
ing
appr
oach
toau
tom
a-tio
nof
VL
SIla
yout
desi
gn.P
roce
edin
gsof
the
Inte
rnat
iona
lSy
mpo
sium
ofC
ircu
its,p
ages
234–
244,
1989
.[3
]M
.R.C
hin-
Chi
hC
hang
,Jas
onC
ong
and
M.X
ie.
Opt
ima-
lity
and
scal
abili
tyst
udy
ofex
istin
gpl
acem
ent
algo
rith
ms.
IEE
ETr
ansa
ctio
nson
Com
pute
r-A
ided
Des
ign
ofIn
tegr
ated
Cir
cuits
and
Syst
ems,
23(4
):53
7–54
9,20
04.
[4]
J.Y.
Cho
and
J.D
.Cho
.Im
prov
ing
perf
orm
ance
and
rout
a-bi
lity
estim
atio
nin
mcm
plac
emen
t.[5
]J.
Con
g,L
.He,
C.K
oh,a
ndP.
Mad
den.
Perf
orm
ance
opti-
miz
atio
nof
vlsi
inte
rcon
nect
layo
ut,1
996.
[6]
E.C
.S.D
.J.H
atha
way
,R.R
.Hab
raan
dS.
J.R
othm
an.C
ir-cu
itpl
acem
ent,
chip
optim
izat
ion
and
wir
ero
utin
gfo
rIB
MIC
tech
nolo
gy.I
BM
J.R
ES.
Dev
elop
.,40
(4):
453–
460,
1996
.[7
]S.
C.D
onal
d.A
nov
ervi
ewof
plac
emen
tand
rout
ing
algo
-ri
thm
sfo
rmul
ti-ch
ipm
odul
es.
[8]
R.
Dre
chsl
er,
H.
Esb
ense
n,an
dB
.B
ecke
r.G
enet
ical
go-
rith
ms
inco
mpu
tera
ided
desi
gnof
inte
grat
edci
rcui
ts,1
994.
[9]
H.E
sben
sen
and
P.M
azum
der.
SAG
A:a
unifi
catio
nof
the
gene
tical
gori
thm
with
sim
ulat
edan
neal
ing
and
itsap
plic
a-tio
nto
mac
ro-c
ell
plac
emen
t.P
roce
edin
gsof
the
Seve
nth
Inte
rnat
iona
lC
onfe
renc
eon
VLS
ID
esig
n,pa
ges
211–
214,
1994
.[1
0]R
.Hof
fman
n.E
infü
hrun
gska
pite
lzur
Vorl
esun
gR
echn
erar
-ch
itekt
ur,2
003.
[11]
J.L
ieni
gan
dK
.T
hula
sira
man
.A
gene
tical
gori
thm
for
chan
nel
rout
ing
inV
LSI
circ
uits
.E
volu
tiona
ryC
ompu
ta-
tion,
1(4)
:293
–311
,199
3.[1
2]C
.S.E
.Pro
ject
.Mat
hem
atic
alO
ptim
izat
ion.
1995
.[1
3]M
.J.
S.Sm
ith.
App
licat
ion-
Spec
ific
Inte
grat
edC
ircu
its.
Add
ison
-Wes
ley
Publ
ishi
ngC
ompa
ny,1
997.
