Int
ern
at
i
onal
Journ
al of Ele
ctrical
an
d
Co
mput
er
En
gin
eeri
ng
(IJ
E
C
E)
Vo
l.
10
,
No.
3
,
June
2020,
pp. 2
95
9
~
2968
IS
S
N: 20
88
-
8708
,
DOI: 10
.11
591/
ijece
.
v10
i
3
.
pp2959
-
29
68
2959
Journ
al h
om
e
page
:
http:
//
ij
ece.i
aesc
or
e.c
om/i
nd
ex
.ph
p/IJ
ECE
Mem
ory and I/O
optimiz
ed
rectili
near
St
einer
min
i
mu
m tree
ro
utin
g for
VLSI
Latha
N.
R
.
,
G.
R.
Pras
ad
Depa
rtment
o
f
C
SE,
B.
M
.
S.
Col
l
ege
of
Eng
ine
e
ri
ng,
Indi
a
Art
ic
le
In
f
o
ABSTR
A
CT
Art
ic
le
history:
Re
cei
ved
J
un
11
, 2
019
Re
vised
Dec
16
,
20
19
Accepte
d
Ja
n 7
, 2020
As
the
size
of
d
evi
c
es
are
sca
li
n
g
down
at
rap
id
pac
e
,
the
int
e
rco
nnec
t
d
ela
y
play
a
m
aj
or
pa
rt
in
per
form
ance
of
IC
ch
ips.
T
her
efo
re
m
ini
m
i
zi
ng
d
ela
y
and
wire
le
ng
th
is
the
m
ost
desire
d
obje
c
ti
v
e.
FL
UTE
(Fast
Look
-
Up
ta
ble)
pre
sente
d
a
f
ast
and
ac
cur
at
e
RS
MT
(Rec
ti
li
n
ea
r
Stei
n
er
Minim
um
Tre
e)
construc
t
ion
for
both
sm
al
le
r
and
highe
r
deg
ree
net.
FLUTE
pre
sented
an
opt
imiza
t
ion
technique
th
a
t
red
u
ce
s
t
ime
complexit
y
f
or
RS
MT
c
onstruction
for
both
sm
al
le
r
a
nd
la
rge
r
d
egr
e
e
net
s.
How
ev
e
r
for
la
rg
er
degr
ee
n
et
thi
s
t
ec
hniqu
e
induce
s
m
emory
over
h
ea
d,
as
it
does
not
conside
r
the
m
emor
y
re
quire
m
ent
in
c
onstruct
ing
RS
MT.
Since
av
a
il
ability
of
m
emory
is
v
er
y
le
ss
and
is
exp
ensive
,
it
i
s
desi
red
to
ut
il
i
ze
m
emor
y
m
ore
eff
icientl
y
whic
h
in
turn
result
s
in
red
u
ci
ng
I
/O
t
ime
(i.e.
red
uc
e
the
num
be
r
of
I/O
disk
acc
ess).
The
propo
sed
work
pre
se
nts
a
Mem
or
y
Optimize
d
RS
MT
(MO
R
S
MT)
construc
t
io
n
in
orde
r
to
ad
dre
ss
the
m
emor
y
ov
erh
ea
d
for
la
rg
er
deg
ree
net.
Th
e
d
ept
h
-
f
irst
sea
r
ch
and
d
ivi
de
and
conqu
er
appr
o
ac
h
is
adopt
ed
to
buil
d
a
Mem
or
y
opti
m
iz
ed
tr
ee
.
E
xper
iments
are
c
onduct
ed
t
o
eva
lu
at
e
th
e
pe
rform
anc
e
of
pr
oposed
appr
oa
c
h
over
exi
sting
m
odel
fo
r
var
ie
d
ben
chmar
ks
in
te
rm
s
of
co
m
puta
ti
on
ti
m
e,
m
emory
over
h
ead
and
wire
le
ngth
.
The
exp
eri
m
ent
a
l
result
s
show
tha
t
the
proposed
m
odel
is
sca
la
bl
e
and
eff
icient.
Ke
yw
or
d
s
:
Mi
ni
m
u
m
sp
an
ning tree
Re
ct
il
inear S
te
iner
tree
VLSI
W
i
relen
gth est
im
at
ion
Copyright
©
202
0
Instit
ut
e
o
f Ad
vanc
ed
Engi
n
ee
r
ing
and
S
cienc
e
.
Al
l
rights re
serv
ed
.
Corres
pond
in
g
Aut
h
or
:
Lat
ha N.
R.
,
Dep
a
rtm
ent o
f C
SE,
B.M
.
S.,
Coll
ege
of
En
gi
neer
in
g, I
nd
ia
.
Em
a
il
:
lathan
r
11@r
e
dif
fm
ai
l
.co
m
1.
INTROD
U
CTION
Re
ct
il
inear
Stei
ner
Mi
nim
a
l
Tree
(RSMT
)
is
com
po
sed
of
sm
a
ll
se
t
of
connecte
d
pi
ns
thr
ough
Stei
ner
no
des
with
m
ini
m
a
l
cu
m
ulati
ve
edg
e
siz
e
in
Ma
nh
at
ta
n
di
sta
nce
for
a
giv
en
set
of
pin
s.
The
co
ns
tr
uction
of
RSM
T
is
a
m
ajo
r
iss
ue
in
desig
ning
Ver
y
Lar
ge
Sca
le
In
te
gr
a
ti
on
(VLSI
)
s
uch
a
s
interco
nnect
s
desig
n,
placem
ent
an
d
flo
or
plan
ning.
It
ha
s
bee
n
a
dopte
d
in
c
om
pu
ti
ng
tra
ns
m
issi
on
delay
,
interco
nnect
de
la
y
and
in
work
l
oad
c
om
pu
ta
ti
on
.
It
is
al
so
adopted
in
som
e
glo
bal
rout
ing
strat
egies
t
o
buil
d
a r
ou
ti
ng t
opog
raphy
of
all
net
s.
The
c
onstr
uction
of
RSM
T
f
or
VL
SI
is
co
ns
ide
red
a
Non
-
determ
inist
ic
poly
no
m
ia
l
pr
oble
m
[1
]
,
as
a
resu
lt
recti
li
near
m
ini
m
um
sp
ann
i
ng
tre
e
(RMST)
has
been
a
dopte
d
in
so
m
e
earli
er
desig
n
by
ex
pl
or
i
ng
sp
ace
dim
ension
al
de
sig
n.
RM
ST
con
st
ru
ct
ion
re
quires
fa
st
tree
co
m
pu
ti
ng
strat
egy
a
nd
sin
ce
the
RM
ST
do
e
s
no
t
al
lo
w
Stei
ner
no
des
in
tree
co
ns
tr
uction
the
res
ul
ti
ng
RM
ST,
le
ng
t
h
is
l
onger
than
that
of
R
SMT.
In
[2
]
s
howe
d
that
RM
ST
is
on
e
a
nd
half
ti
m
es
gr
eat
er
t
ha
n
that
of
RS
MT
with
le
ss
t
han
50%
in
te
r
m
s
of
accuracy,
w
hich
is
tolera
ble
in
earli
er
desi
gn.
Howe
ver,
th
e
la
te
r
desig
n
r
equ
i
res
go
od
wire
le
ngth
a
c
cur
acy
for
w
hich
the
con
str
uctio
n
of
RSM
T
is
r
equ
i
red.
In
[3
]
pr
ese
nted
a
wide
ra
nge
ch
aracte
risti
c
of
RSM
T
const
ru
ct
io
n.
I
n
[
4,
5]
p
rese
nted
a
n
optim
al
strat
egy
f
or
RSM
T
co
ns
tr
uction,
wh
ic
h
is
sai
d
to
ha
ve
le
ast
com
pu
ta
ti
on
ti
m
e.
In
[
6]
presented
a
nea
r
optim
al
so
luti
on
for
RSM
T
co
ns
tr
uction.
H
ow
e
ver,
the
y
ar
e
com
pu
ta
ti
on
al
ly
v
ery
hea
vy a
nd are
not s
uitable
for ap
plica
ti
on
s
, speci
fical
ly
f
or VLSI
d
e
sign.
Evaluation Warning : The document was created with Spire.PDF for Python.
IS
S
N
:
2088
-
8708
In
t J
Elec
&
C
om
p
En
g,
V
ol.
10
, No
.
3
,
J
une
2020 :
26
5
9
-
296
8
2960
Ma
ny
appro
a
ches
ha
ve
be
en
pr
e
sente
d
to
reduce
tim
e
com
plexity
in
con
str
ucting
RSM
T
.
In
[
7]
adopted
sp
a
nn
i
ng
gra
ph
[8
]
to
ai
d
in
bu
il
di
ng
the
prim
ary
set
of
spa
nn
i
ng
tree
an
d
obta
in
finest
set
s
fo
r
the
ed
ge
-
w
hic
h
are
com
pu
t
ed
it
erati
vel
y
to
el
i
m
inate
l
ongest
e
dg
e
.
I
n
[
9]
prese
nte
d
a
gr
ee
dy
ba
tc
hed
te
chn
iq
ue,
w
hi
ch
im
pr
ov
e
d
e
ff
ic
ie
ncy
a
nd
reduce
d
the
c
om
pu
ta
ti
on
ti
m
e.
The
Sin
gl
e
Trun
k
Stei
ne
r
Tre
e
(S
TS
T)
is
buil
t
to
c
onnect
a
s
et
of
pi
ns
t
o
in
div
id
ual
tr
unks
,
w
hich
tra
ver
s
e
ve
rtic
al
ly
or
horizo
ntall
y
throu
gh
set
of
al
l
pin
s,
bu
t
is
no
t
ef
fic
ie
nt
fo
r
m
edium
siz
e
pin
s.
In
[1
0]
prese
nted
ref
ine
d
sin
gle
-
tru
nk
tree
f
or
de
gr
ee
up
t
o
5
nets
a
nd
it
is
optim
a
ll
y
accurate
for
m
ediu
m
deg
r
ee
nets
with
fa
ir
run
ti
m
e
co
m
plexit
y.
In
[
3
1
,
3
4
]
sp
a
nn
i
ng tre
e
ba
sed
a
ppr
ox
im
at
ion
alg
ori
thm
that pr
oduce
d op
ti
m
al
so
luti
on
s
wer
e
prese
nt
ed.
In
[
11,
12]
pr
e
sented
l
ooku
p
ta
ble
base
d
fas
t
and
accu
rate
op
ti
m
al
so
luti
on
f
or
RSM
T
c
on
st
ru
ct
io
n
nam
ely
FLU
T
E.
I
n
this
te
c
hniq
ue,
t
he
nets
are
re
cu
rsivel
y
brok
e
n
i
nto
su
b
set
of
nets
.
FL
UTE
is
e
va
luate
d
for
lo
w
de
gr
ee
nets
a
nd
it
is
su
it
able
f
or
VLSI
desig
n.
FLU
T
E
is
al
s
o
e
ff
ic
ie
nt
for
high
de
gr
ee
ne
ts
with
runtim
e
co
m
pl
exity
of
(
log
)
.
H
owever,
f
or
highe
r
de
gr
ee
nets
t
he
accu
racy
of
RSM
T
co
ns
tr
uction
is
sever
el
y
af
fected.
T
his
is
due
to
the
erro
r
induced
duri
ng
net
breaki
ng
te
ch
nique.
T
o
ad
dr
e
ss
this
issue
in
[
13]
prese
nted
a
scal
able
ne
t
par
ti
ti
on
i
ng
te
chn
iq
ue,
wh
e
re
the
nets
are
bro
ken
into
sm
al
le
r
subset
of
nets
and
agai
n
m
erg
ed
by
a
ddin
g
Stei
ner
nodes
.
This
te
ch
nique
co
uld
ha
nd
le
bo
t
h
sm
al
le
r
and
la
r
ger
de
gree
nets
with
sli
gh
t
re
duct
ion
i
n
accu
r
acy
bu
t
it
ind
uc
ed
a
r
un
ti
m
e
com
plexity
of
(
log
2
)
.
In
[14]
pr
e
sent
ed
a
fast
lookup
ta
ble
ba
sed
RSM
T
c
on
st
ru
ct
io
n,
w
hich
br
in
gs
a
good
trade
off
betwee
n
accu
r
acy
and
the
r
untim
e
com
plexity
.
As
sp
eci
fie
d
in
[
2
8
-
30
,
3
2
]
m
e
m
or
y
is
gaining
prom
inence
and
e
ff
ic
ie
nt
use
of
t
his
res
ource
is
ver
y
im
po
rtan
t.
Both
[13,
14
]
did
not
c
on
si
der
the
m
e
m
or
y
co
ns
tra
int
in
bu
il
di
ng
a
lo
ok
up
ta
ble.
The
fu
t
ur
e
VL
SI
desig
n
c
ons
ist
s
of
fixe
d
blo
ck
s
suc
h
a
s
I
P
bl
ock
s
,
m
acro
s,
a
nd
s
o
on
a
nd
FL
UTE
is
a
dopte
d
by
these resear
cher
s [15,
16]
.
In
s
uc
h
desig
ns
m
ini
m
izing
w
ire
le
ngth
an
d
re
duci
ng
m
e
m
or
y
ov
er
hea
d
is
m
os
t
desire
d.
To
a
ddress
these
iss
ues
t
he
pro
po
s
ed
wor
k
pr
ese
nts
a
m
e
m
or
y
op
ti
m
iz
ed
RSM
T
co
ns
tr
u
ct
ion
tha
t
reduces
wire
leng
t
h
a
nd co
m
pu
ta
ti
on
al
over
he
ad
c
om
plexities.
T
he
c
on
t
rib
ution o
f resear
ch wor
k:
No
pri
or
w
ork
has
c
onside
red
m
e
m
or
y
con
st
raint
in
de
sig
nin
g
RSM
T
c
ons
tructi
on.
The
pro
posed
w
or
k
pr
ese
nts a
m
e
m
or
y op
ti
m
iz
e
d
RSM
T
const
ru
ct
io
n.
The
pro
posed
m
od
el
r
ed
uces
the w
i
re len
gth an
d
c
om
pu
ta
ti
on tim
e in cons
tructi
ng RSMT
.
The
pro
posed
m
od
el
is
evalu
at
ed
co
ns
i
der
i
ng
di
ff
e
ren
t
be
nch
m
ark
[
25
]
an
d
s
hows
th
at
the
pr
opos
e
d
m
od
el
is
eff
ic
i
ent
co
ns
ide
rin
g
al
l
ben
c
hm
ark
in
te
rm
s
of
m
e
m
or
y
ov
er
he
ad,
c
om
pu
ta
tio
n
ti
m
e
and
wir
e
le
ng
th
.
The
pa
per
or
gan
iz
at
io
n
is
as
fo
ll
ows:
In
sect
ion
2
ex
te
ns
ive
li
te
ratur
e
s
urvey
is
carried
out.
The
propose
d
m
e
m
or
y
op
ti
m
iz
ed
RSM
T
m
od
el
s
are
pr
ese
nted
i
n
Sect
ion
3
.
T
he
exp
e
rim
enta
l
stud
y
consi
der
i
ng
va
rio
us
be
nch
m
ark
are
pr
ese
nte
d
in
pe
nu
lt
im
ate
sect
ion
.
The
con
cl
ud
i
ng
re
m
ark
an
d
fu
t
ure
wo
r
k
is discu
ssed
in t
he
la
st sect
io
n.
2.
LIT
TE
RA
TU
RE S
URVE
Y
VLSI
is
a
te
chn
i
qu
e
of
c
ombinin
g
la
khs
of
tra
ns
ist
ors
i
nt
o
s
olit
ary
In
t
egr
at
e
d
Ci
rc
uit
(I
C)
c
hip.
W
it
h
the
inc
re
ase
in
tra
ns
ist
ors,
t
he
inte
rcon
necti
ng
wi
re
le
ng
t
h
al
s
o
inc
re
ases.
It
is
chall
eng
i
ng
to
m
inim
ize
the
re
sist
ive
a
nd
ca
pacit
ive
fe
at
ur
es,
wh
ic
h
ha
ve
a
n
im
pact
on
de
la
y.
T
he
i
nterc
onnect
wires
ha
ve
fi
xe
d
width
and
a
rea
m
aking
le
ng
t
h
as
t
he
only
pa
ram
et
er
that
can
b
e
op
ti
m
iz
ed.
A
s
a
res
ult,
m
any
routing
te
c
hniq
ues
hav
e
b
ee
n p
rop
os
e
d
in
V
L
SI d
esi
gn
s
that a
re
as surve
ye
d be
low.
In
[17]
s
howe
d
that
the
global
router
ge
ner
al
ly
deco
m
po
se
net
thr
ough
RS
MT.
The
refo
re
,
to
reduce
congesti
on
a
nd
prov
i
de
fle
xi
bili
ty
i
t
m
ai
nl
y
d
epe
nds
on
RSM
T
co
ns
tr
uc
ti
on
.
FLUTE
is
a
widely
a
dopted
te
chn
iq
ue
for
f
ast
RSM
T
const
ru
ct
io
n
with
m
ini
m
al
wire
l
eng
t
h.
Howe
ve
r,
it
fail
s
to
inc
orp
or
at
e
co
nge
sti
on.
To
prov
i
de
fle
xib
il
it
y
and
co
ng
e
sti
on
optim
iz
at
ion
f
or
net
[17]
pr
e
sente
d
a
m
od
el
na
m
el
y
Fthu
,
w
hi
ch
is
a
two
-
phase
ap
proac
h
by
a
do
pting
FL
UTE
.
In
first
phase,
i
t
decr
ease
s
co
ngest
io
n
a
nd
i
nc
reases
flexibili
ty
by
app
ly
in
g
re
for
m
ed
edg
e
sh
if
ti
ng
an
d
e
dg
e
sh
ri
nk
i
ng
te
c
hn
i
qu
e
with
out
changin
g
St
ei
ner
tree
to
polo
gy
.
In
s
eco
nd
ph
ase,
the
c
onge
ste
d
St
ei
ne
r
tree
is
bro
ke
n
an
d
rec
onne
ct
ed
us
i
ng
MST
-
base
d
ap
proac
h.
The
outc
om
es
sh
ow
bette
r
perform
ance
i
n
te
rm
s
of
red
uce
d
co
ngest
ion
tim
e.
Howev
e
r,
the
re
is
no
i
m
pr
ovem
ent i
n wire le
ng
t
h p
erfor
m
ance.
In
[
18,
19,
2
6
,
2
7
]
pr
ese
nted
a
m
od
el
to
s
olv
e
gl
ob
al
r
ou
ti
ng
prob
le
m
.
In
[
18
]
pr
e
se
nted
m
od
el
,
nam
ely
GRIP
(G
l
ob
al
R
outi
ng
Tec
hnology
via
Li
near
Program
m
ing
)
.Th
is
m
od
el
pr
ese
nte
d
in
te
ger
-
pro
gr
am
m
ing
m
od
el
fo
r
c
urr
ent
la
rg
e
-
scal
e
netw
ork.
T
he
m
od
el
ob
ta
ine
d
hi
gh
qual
it
y
so
luti
on
by
ad
op
ti
ng
FLU
T
E
f
or
i
niti
al
RSM
T
const
ru
ct
io
n.
The
outc
om
e
show
s
im
pr
ov
em
ent
in
c
os
t
a
nd
wire
le
ngt
h
perform
ance.
Howe
ver,
they
did
not
e
xploi
t
CPU
a
nd
m
e
m
or
y
per
f
or
m
ance.
Linea
r
program
m
ing
m
od
el
a
re
pro
ne
to
get
stuck
in
lo
cal
optim
a.
To
ov
erc
om
e
[1
9]
pr
ese
nted
a
fast
co
ngest
io
n
dr
i
ve
n
Stei
ner
tree
cre
at
io
n
Evaluation Warning : The document was created with Spire.PDF for Python.
In
t J
Elec
&
C
om
p
En
g
IS
S
N: 20
88
-
8708
Mem
or
y
of
I/
O
opti
mized
recti
li
nea
r
Steiner
minimu
m
tre
e
ro
uti
ng for VL
SI (Lath
a
N
. R.)
2961
by
adoptin
g
F
LUTE
.
The
outc
om
e
sh
ow
s
sign
i
ficant
in
te
r
m
s
of
runtim
e
com
plexity
.
To
so
lve
the
c
onge
sti
on
in
gl
ob
al
r
ou
ti
ng
[
20,
21,
33
]
ad
opte
d
ga
m
e
theor
y
a
pp
ro
ac
h.
T
he
ga
m
e
theor
y
a
pp
ro
ac
h
is
ad
opte
d
to
i
m
pr
ove r
unti
m
e com
plexity
of cluste
rin
g
a
ppr
oach f
or VLSI
r
ou
ti
ng
pla
ce
m
ent d
esi
gn.
In
[
22]
stud
ie
d
var
io
us
cl
us
te
rin
g
base
d
place
m
ent
too
l.
A
n
eff
ic
ie
nt
cl
ust
ering
ap
proac
h
can
ai
d
in
reducin
g
wire
le
ng
th
,
cy
cl
e
tim
e
or
op
ti
m
iz
e
a
design
based
on
the
se
obj
ect
ives
.
Howe
ver
cl
ust
eri
ng
appr
oach
ca
n
ind
uce
ti
m
e
con
strai
nt.
T
o
ad
dr
es
s
the
tim
e
con
strai
nt
[22]
exp
l
oited
a
heterog
eneous
com
pu
ti
ng
a
nd
pr
ese
nted
a p
a
rall
el
cl
us
te
rin
g
ap
proac
h
f
or p
la
cem
ent.
Their
m
od
el
is
exp
loit
ed
for
bot
h
CPU
as
well
as
G
P
U.
The
m
od
el
util
iz
es
the
CP
U
a
nd
GPU
c
or
e
to
f
ull
ext
ent.
T
he
outc
om
e
sh
ows
it
a
chieves
a
good
s
pee
d
up
wh
e
n
c
om
par
ed
to
se
rial
ex
ecuti
on
strat
e
gy
.
H
ow
e
ver
a
doptin
g
GPU
for
pr
ocessin
g
i
nduce
s
high
c
os
t
of
de
plo
ym
ent
and
t
heir
m
od
el
di
d
not
co
ns
ide
r
t
he
m
e
m
or
y
con
strai
nt.
As
a
r
esult,
it
increas
es
I/O
acce
ss tim
e.
Extensi
ve
li
te
ratur
e
s
urvey
carried
out
sho
ws
that
m
ini
mizi
ng
tim
e
com
plexit
y
(r
unti
m
e)
and
wir
e
le
ng
th
is
a
cr
it
ic
al
factor
f
or
desi
gn
i
ng
an
ef
fici
ent
r
ou
ti
ng
te
c
hn
i
que
in
VL
SI
de
sign.
S
om
e
e
xisti
ng
appr
oach
es
ha
ve
c
onside
red
m
ini
m
iz
ing
wire
le
ngth
or
r
untim
e
and
so
m
e
co
ns
ide
re
d
both
f
or
opti
m
i
zat
ion
.
To
im
pr
ov
e
r
untim
e
few
appro
ac
hes
ha
ve
c
on
si
der
e
d
a
pa
rall
el
i
m
ple
m
e
ntati
on
by
util
i
zi
ng
CP
U
an
d
G
P
U
cor
e
.
H
ow
e
ve
r,
no
ne
of
t
he
appro
ac
hes
has
co
ns
ide
re
d
m
e
m
or
y
pe
rfor
m
ance.
Ut
il
i
zi
ng
the
m
e
m
or
y
eff
ic
ie
ntly
can
ai
d
in
re
du
ci
ng
the
ti
m
e
c
om
plexity
(i.e.
I/O
acce
s
s
ti
m
e).
The
pro
pose
d
w
ork
pre
sents
a
m
e
m
or
y
op
ti
m
iz
at
ion
based
RSM
T
to
i
m
pr
ove
wi
re
le
ng
th,
r
un
ti
m
e
and
m
e
m
or
y
per
f
or
m
ance.
I
n
th
e
nex
t
sect
ion
belo
w
t
he pr
opos
e
d
m
e
m
or
y o
ptim
ized
RSMT
(
MO
RSM
T)
m
od
el
is pr
e
sente
d.
3.
PROP
OSE
D MEM
ORY
O
PTIMIZ
ED
R
SMT
MO
DE
L
Her
e
we
pr
ese
nt
a
m
e
m
or
y
op
tim
iz
ed
RSM
T
co
ns
tr
uction
that
reduces
wire
le
ngth
,
m
e
m
or
y
us
a
ge
and
com
pu
ta
ti
on
tim
e.
As
si
m
il
ar
to
[14],
l
et
us
c
onside
r
that
the
siz
e
of
each
su
b
tree
be
div
ide
d
bas
ed
on
m
e
m
or
y
op
ti
m
iz
ed
tree
a
nd
t
akes
m
e
m
or
y
and
sp
a
nnin
g
t
ree
as
i
nput.
Firstl
y
it
com
pu
te
s
the
le
ast
overh
ea
d
edg
e
s
(u
si
ng
m
e
m
or
y
op
tim
iz
ed
s
pannin
g
gr
a
ph)
an
d
sel
ect
s
on
e
of
the
node
as
it
s
ro
ot.
The
no
de,
wh
ic
h
is
cl
os
er
to
t
he
r
oo
t
node,
is
c
on
si
der
e
d
as
pa
ren
t
no
de
by
reali
zi
ng
c
hild
-
par
e
nt
relat
ion
s
hi
p
al
ong
each
of
the
ed
ges.
T
he
n
dep
t
h
-
first
se
arch
a
nd
div
id
e
an
d
co
nque
r
appr
oach
is
ad
o
pte
d
to
opti
m
i
ze
m
e
m
or
y
fo
r
la
rg
e
r
siz
e
nets.
Let
us
co
ns
ide
r
a
graph
(
,
)
,
w
he
re
an
d
dep
ic
ts
a
set
of
orde
red
pai
rs
of
e
dg
e
s
an
d
nodes
resp
ect
ively
.
L
et
=
|
|
an
d
=
|
|
re
pr
ese
nt
set
of
e
dg
es
and
nodes
res
pe
ct
ively
.
He
re,
we
first
co
ns
tr
uc
t
an
in
it
ia
l
sp
an
ning
grap
h
by
add
i
ng
Stei
ne
r
node
s
an
d
is
con
si
der
e
d
to
be
co
nnect
ed
t
o
al
l
nodes
in
.
The
n
div
i
de
-
c
onquer
a
ppr
oa
ch
is
a
ppli
ed
t
o
buil
d
a
m
e
mo
ry
opti
m
iz
ed
tree
of
gr
a
ph
.
Be
low
ta
ble
show
s
the notat
io
ns
a
nd sym
bo
ls us
ed
in
the
pa
per.
Table
1.
N
otati
on
s
a
nd sym
bo
l
s
us
e
d
Sy
m
b
o
l
u
sed
Ab
b
reviatio
n
Graph
Set of
no
d
es
Set of
edg
es
(
|
)
It
is a
directed g
ra
p
h
Sp
an
n
in
g
grap
h
Set of
Steiner no
d
es
Me
m
o
r
y
Av
ailab
le
Me
m
o
r
y
op
ti
m
ize
d
su
b
tree
g
raph
Nu
m
b
e
r
o
f
su
b
tree
3.1.
Me
mor
y opt
im
i
z
ed
divi
de and c
onqu
er appro
ach
The
m
e
m
or
y o
pti
m
iz
ed
div
id
e conqu
e
r
ap
proach
takes
m
e
m
or
y S, S
pan
ni
ng
grap
h
G
of H
and g
r
a
ph
H
as
an
in
pu
t
and
ob
ta
i
n
a
tree
Gas
outp
ut
wh
ic
h
is
a
dept
h
first
searc
h
tree
of
H,
w
he
re
G
is
retai
n
e
d
in
m
e
m
or
y
and
H
is
ke
pt
in
di
sk
.
T
he
al
go
rithm
first
te
sts
wh
et
her
gr
a
ph
H
can
sat
isfy
m
e
m
or
y
op
ti
m
iz
at
ion
requirem
ent,
so
that
the
H
ca
n
be
l
oad
e
d
int
o
S
a
nd
if
s
o
i
t
com
pu
te
s
m
e
m
or
y
op
tim
iz
e
d
tree
G
of
H
us
in
g
avail
able
-
m
e
m
or
y o
ptim
iz
at
i
on
strate
gy an
d ob
ta
ins
G.
Or else i
f
do
es not
o
btain an
y G
, th
e algori
thm
f
ur
t
he
r
com
pu
te
s
m
e
mo
ry
op
ti
m
iz
ed
tree
G
of
H
by
div
i
ding
m
e
mo
ry
op
ti
m
iz
ed
tree
G
by
us
i
ng
di
vid
e
a
nd
c
onquer
appr
oach.
To
obta
in
a
n
e
f
fici
ent
m
e
m
or
y
op
ti
m
iz
ed
tree
the
le
gal
di
vid
en
d
of H
m
us
t
be
c
om
pu
te
d
wh
ic
h
is
set
to
false
init
ia
l
ly
as
s
how
n
in
flo
wc
har
t
i
n
Figure
1.
T
he
n
t
he
pr
ese
nt
s
pannin
g
grap
h
G
is
op
ti
m
iz
e
d
with
resp
ect
to
H
unti
l
G
is
a
m
e
m
or
y
op
tim
iz
e
d
tree
G
o
f
H
or
we
obta
in
a
le
gal
div
ide
nd
of
H
on
spa
nni
ng
tree
Evaluation Warning : The document was created with Spire.PDF for Python.
IS
S
N
:
2088
-
8708
In
t J
Elec
&
C
om
p
En
g,
V
ol.
10
, No
.
3
,
J
une
2020 :
26
5
9
-
296
8
2962
G.
He
re
the
div
ide
nd
is
obta
i
ned
by
invo
kin
g
div
i
dend
optim
iz
at
ion
te
c
hn
i
qu
e
t
o
achi
eve
a
gr
a
ph
di
visio
n
H_0,H
_1,H_
2,…,H
_d
of
H
with
res
ultant
sp
a
nn
i
ng
gr
a
ph
〖
G
〗
_0,
G
_1,G_2,…,
G
_d.
Th
e
div
ide
nd
optim
iz
er
al
so
e
valuates
a
m
e
m
or
y op
ti
m
iz
ed
gr
a
ph
μ durin
g
t
he
m
erg
e
op
e
rati
on.
The
div
ide
nd
is
sai
d
to
be
le
gal
only
if
d>
1
as
show
n
in
fl
ow
c
ha
rt
in
Fi
gure
1.
On
ce
t
he
le
gal
tree
div
isi
on
is
obta
ined,
the
m
em
or
y
-
op
ti
m
iz
e
d
tree
G
_q
is
com
pu
te
d
for
al
l
su
b
-
gra
ph
H_
q
us
in
g
divi
de
an
d
conq
uer
a
ppr
oa
ch
in
a
rec
ur
s
ive
m
ann
er.
T
hen
by
com
bin
ing
al
l
m
e
m
or
y
op
ti
m
iz
ed
tree
G_q
of
H
_q
based
on
μ
the
m
e
m
or
y
optim
iz
ed
tree
G
is
co
m
pu
te
d
an
d
ob
ta
in
G
as
m
e
m
o
ry
op
ti
m
iz
ed
tree
of
H.
T
he
overall
flo
w of
pro
pos
ed
m
e
m
or
y op
t
i
m
iz
ed
R
S
MT const
ru
ct
io
n
is
sh
ow
n
in
Fi
gur
e
1.
Figure
1
.
Mem
ory
opti
m
ized
b
ase
d
recti
l
inear
ste
i
ner
m
ini
m
um
tree
constru
ct
ion
3.2.
Me
mor
y
op
timi
z
ed divi
sion
algorith
m
The
obj
ect
ive
of
m
e
m
or
y
optim
iz
ed
div
i
de
and
c
onque
r
appr
oach
is
to
m
axi
m
iz
e
the
nu
m
ber
of
div
ide
d
s
ubgra
ph.
I
n
e
xisti
ng
m
od
el
,
for
a
gi
ven
sp
a
nnin
g
tree
and
gr
a
ph
,
the
di
vision
is
ob
ta
i
ned
us
i
ng
structu
re
0
with
sam
e
par
ent
as
.
T
his
le
ads
to
f
o
ll
owin
g
pro
blem
.
Firstly,
is
obta
ined
on
to
p
of
0
,
wh
e
re
0
is
ge
ne
rated
base
d
on
on
ly
one
le
vel
of
nodes
i
n
.
The
relat
io
ns
hi
p
of
sub
graph
in
du
ce
d
by
su
bt
rees
r
oo
te
d
at
le
af
no
des
of
0
is
com
plex
or
w
he
n
t
he
pa
ren
t
0
at
ha
s
li
m
it
ed
nu
m
ber
o
f
child
nodes
,
after
eval
uatin
g
the
di
vision
by
con
t
racti
ng
al
l
SCC
s
(S
trongly
Connect
ed
Com
po
ne
nt
),
this
m
igh
t
resu
lt
in
avail
abili
ty
of
on
ly
few
di
vide
d
s
ubgrap
hs.
Seco
nd
ly
,
is
ob
ta
ine
d
by
sc
ann
i
ng
gra
ph
on
dis
k
once
a
nd
evaluate
set
of
edg
e
s
̅
,
na
m
el
y
̅
(
̅
,
̅
)
with
̅
an
d
̅
be
t
he
le
af
node
of
0
in
,
w
her
eas
,
t
he
nu
m
ber
of
le
af
no
de
0
is
le
ss,
the
n
̅
m
ay
be
sm
aller
than
the
̅
,
wh
ic
h
is
a
vaila
ble
in
gra
ph.
As
a
res
ult
la
rg
e
am
ount
of
̿
is
com
pu
te
d
but
not
util
iz
ed
durin
g
sca
nn
i
ng
ed
ges.
This
reduces
the
I/
O
ef
fici
ency,
wh
ic
h
res
ults
in
the
increase i
n
c
om
pu
ta
ti
on
tim
e
.
Our
pro
posed
m
od
el
will
ov
e
rc
om
e
these
pr
ob
le
m
s
by
e
nlar
ging
the
siz
e
of
0
an
d
it
s
corres
pondent
with
re
sp
ect
t
o
m
e
m
or
y
siz
e
(i.e.
w
hethe
r
th
ey
can
fit
in
m
ai
n
m
e
m
or
y).
To
sat
isfy
m
em
or
y
const
raint,
the
m
od
el
co
ns
i
de
rs
m
ulti
ple
le
vels
of
node
s
in
to
ge
nerat
e
0
a
nd
it
’s
corres
pondent
.
The
m
ulti
-
le
vel
su
btree
is
de
fine
d
as
a
pa
rt
it
ion
ed
tree
.
L
et
us
co
ns
ide
r
a
tree
with
pa
ren
t
node
0
,
par
ti
ti
on
e
d
tree
that
is
a
su
bt
r
ee
of
m
us
t
sat
i
sfy
the
f
ollo
wing
c
onditi
on.
Firstl
y,
the
pa
r
ent
of
sh
ould
be
0
.
Seco
ndly
,
f
or
a
ny
node
,
f
or
insta
nce
the
le
af
nodes
of
in
are
1
,
2
,
3
,
…
,
,
if
∈
(
)
,
then
is ei
ther
a
no
de
in
with lea
f nodes
1
,
2
,
3
,
…
,
or
a
leaf
nod
e
of
in
.
Evaluation Warning : The document was created with Spire.PDF for Python.
In
t J
Elec
&
C
om
p
En
g
IS
S
N: 20
88
-
8708
Mem
or
y
of
I/
O
opti
mized
recti
li
nea
r
Steiner
minimu
m
tre
e
ro
uti
ng for VL
SI (Lath
a
N
. R.)
2963
To
sat
isfy
th
ese
co
ns
trai
nt
s,
co
ns
i
der
a
tree
with
par
e
nt
0
and
m
e
m
or
y
con
st
raint
̅
,
the
par
ti
ti
on
e
d
tree
is
ge
nerat
ed
as
f
ollo
w
s.
T
he
init
ia
ll
y
is
com
po
se
d
of
one
node
0
.
The
n
the
c
hild
node
are
it
erati
vely
sel
ect
ed
f
ro
m
,
wh
e
re
al
l
le
af
nodes
of
in
as
the
le
af
node
s
of
in
.Not
e
with
resp
ect
t
o
co
m
pr
ise
s
of
at
le
ast
|
(
)
|
2
edg
es
.
As
a
res
ult,
t
he
e
xecu
ti
on
is
stoppe
d
when
a
dd
i
ng
node
|
(
)
|
2
>
.
The
m
e
m
or
y
op
ti
m
iz
ed
div
isi
on
m
od
el
is
as
presente
d
in
Fig
ur
e
2.
Her
e
0
is
co
nst
ru
ct
ed
i
n
top
-
do
wn
fas
hi
on
base
d
on
.
T
he
al
go
rithm
first
eval
uates
par
ti
ti
on
tree
̅
0
of
us
in
g
a
bo
ve
discusse
d
m
et
ho
d
an
d
init
ia
li
ze
to
be
̅
0
.
The
n
it
searc
hes
al
l
ed
ges
(
,
)
in
on
dis
k
and
a
dd
(
,
)
=
(
,
)
into
,
if
and
belo
ngs
t
o
(
̅
0
)
.
Th
en
t
he
m
od
el
fin
ds
al
l
in
and
to
p
-
do
wn
m
et
ho
dolo
gy
i
s
us
e
d
to
ge
ne
rate
0
.
Af
te
r
that
0
an
d
FI
F
O
(F
i
rst
in
First
o
ut
)
qu
e
ue
is
init
ia
li
zed.
It
fir
st
pu
s
hes
parent
0
of
into
.
The
n
the
e
dg
e
s
ar
e
it
erati
vely
a
dd
e
d
int
o
0
un
ti
l
beco
m
es
nu
l
l.
In
e
ver
y
rou
nd, it first re
trie
ves
the t
op n
ode
in
and
pu
s
hes
al
l l
eaf
nodes
of
into
0
(i.e.
if
is i
n
the
tree and
is
not
a
Stei
ne
r
no
de).
F
or
ea
ch
s
uc
h
insta
nc
es
(i.e.
push
e
d
int
o
0
),
it
is
f
urt
her
pus
he
d
in
to
for
furthe
r
exp
a
ns
i
on.
O
nc
e
0
is
c
om
pu
te
d,
is
updated
.
The
updated
by
poppin
g
(
del
et
ing
)
al
l
node
s
that
are
not
in
(
0
)
from
. Lastl
y, div
i
ded s
ubgrap
h
1
,
2
,
3
,
…
,
an
d
s
ubtr
ees
1
,
2
,
3
,
…
,
are ev
al
uat
ed.
Figure
2.
Mem
ory
opti
m
ized
d
ivis
ion
al
gor
it
hm
3.2.
Me
mor
y opt
im
iz
ed me
rging al
go
ri
thm
The
m
erg
e
al
gorithm
pr
ese
nted
i
n
Fi
gure
3
ta
kes
as
in
pu
t,
a
div
id
ed
tree
0
,
1
,
2
,
…
,
an
d
the
co
rr
e
spo
nding
an
d
outp
ut
s
a
grap
h
.
To
perf
or
m
the
m
erg
e
op
e
rati
on
acc
ordin
g
t
o
the
al
go
rithm
in
Fig
ure
3,
t
he
f
ollow
i
ng
issue
s
m
us
t
be
so
l
ve
d.
First
iss
ue
is
how
t
o
a
rr
a
ng
e
0
,
1
,
2
,
…
,
in
the
m
erg
ed
tree
,
su
c
h
tha
t
is
a
tree
of
gr
a
ph
.
And
Sec
ond
iss
ue
is
how
t
o
handle
the
Stei
ner
node
in
tree
0
,
1
,
2
,
…
,
.
T
he flo
w of m
erg
ing
al
gorithm
is as shown i
n
Fi
g
ure
3.
Evaluation Warning : The document was created with Spire.PDF for Python.
IS
S
N
:
2088
-
8708
In
t J
Elec
&
C
om
p
En
g,
V
ol.
10
, No
.
3
,
J
une
2020 :
26
5
9
-
296
8
2964
Figure
3
.
Mem
ory
opti
m
ized
m
er
ging
a
lgori
thm
To
s
olv
e
t
he
f
irst
issue,
we
us
e
in
f
or
m
at
ion
of
(i.e.
is
a
gr
a
ph
that
preserv
e
s
the
t
opol
og
y
of
edg
e
s
of
al
l
pa
rtit
ion
ed
s
ub
grap
hs).
T
hen
s
or
t
al
l
the
no
de
s
in
and
rea
rr
a
ng
e
t
he
no
de
s
in
0
based
on
rev
e
rse
to
polo
gical
order
of
corres
pondent
nodes
in
a
nd
then
m
erg
e
al
l
(
1
≤
≤
)
with
0
to
ob
ta
i
n
tree of
, w
e
ne
ed
to
be
ass
ur
e
d
that
is a DAG and
(
)
=
(
0
)
.
To
s
ol
ve
the sec
ond
i
ssu
e,
we
m
erg
e
al
l
trees
0
,
1
,
2
,
…
,
,
t
o
ob
ta
in
a
tree
.
F
or
eac
h
Stei
ner
node
∈
(
0
)
,
f
or
instance
r
oot
no
de
of
in
is
,
the
n
delet
e
e
dg
e
(
,
)
from
,
an
d
for
eac
h
le
a
f
node
of
in
,
we
el
im
inate
edg
e
(
,
)
from
and
add
e
dg
e
(
,
)
into
.
T
his
m
et
hod
ai
ds
i
n
im
pr
ov
i
ng
to
valid
at
e
that
the
re
su
lt
ant
tree
is
tree
of
.
The
perf
or
m
ance stu
d
y
of the
pro
po
se
d
a
ppr
oach is
pr
ese
nt
ed
in
the
ne
xt s
ect
ion
.
4.
RESU
LT
A
N
D ANALY
SIS
The
M
ORSMT
al
gorithm
i
s
i
m
ple
m
ented
usi
ng
C+
+
obj
ect
or
ie
nted
program
m
i
ng
la
ngua
ge
.
The
GCC
com
piler
is
us
e
d
t
o
com
pile
the
cod
e
.
T
he
ecl
ipse
Kep
le
r
I
D
E
us
e
d
f
or
r
unning
the
al
gorithm
.
The
syst
em
env
ir
on
m
ent
us
e
d
to
r
un
t
he
al
gorithm
is
Ce
nto
s
7.0
Lin
ux
op
e
rati
ng
syst
em
,
3.
2
GH
z
,
I
ntel
I
-
5
Qu
a
d
co
re
pr
oc
esso
r
an
d
16
GB
RAM.
Th
e
IBM
ben
c
hm
ark
[
25
]
is
con
si
der
e
d
f
or
evaluati
on,
whic
h
is
as
sh
ow
n
in
Ta
ble
2.
T
he
ex
pe
rim
ent
is
carried
out
to
eval
uate
the
pe
rform
ance
of
MO
RSM
T
ov
e
r
e
xisti
ng
appr
oach [
14
]
i
n
te
rm
s
of
wire
le
ng
th
, m
e
m
or
y uti
li
zat
ion
and c
om
pu
ta
ti
on
tim
e.
4.1.
Wir
el
ength pe
rf
orm
a
n
ce
Ex
per
im
ents
are
car
ried
out
to
e
valuate
wirelen
gth
pe
r
form
ance
an
d
18
IBM
ci
r
cui
t
in
I
SP
D98
ben
c
hm
ark
is
us
e
d.
The
in
form
ation
of
benchm
ark
is
sh
own
in
Ta
ble
2.
and
there
are
1.57
m
illi
on
ne
ts
in
total
.
Th
e
propose
d
MORSM
T
appr
oach
is
com
par
ed
with
F
LUTE
[
14
]
with
de
fa
ult
accuracy
=
3
in
te
rm
s
of
wire
le
ngth
perform
ance
,
wh
ic
h
is
show
n
in
Ta
ble
3
.
The
outc
om
e
sh
ows
that
MO
RSM
T
perfor
m
s
bette
r
than
e
xisti
ng
a
ppr
oach
in
te
r
m
s
of
wire
le
ngth
re
du
ct
io
n
f
or
al
l
t
he
case
s.
A
n
a
ve
rag
e
reducti
on
of
0.026%
is
achieve
d by
MORSM
T
ov
e
r
e
xisti
ng
a
ppr
oach.
4.2.
C
omput
ati
on time
perf
orm
an
ce
The
pro
posed
MORSM
T
a
pp
ro
ac
h
is
c
om
par
ed
with
F
LU
TE
[
14]
wit
h
def
a
ult
acc
ur
a
cy
=
3
in
te
rm
s
of
com
p
utati
on
ti
m
e
p
erfor
m
ance,
w
hich
is
s
how
n
in
T
able
4
.
T
he
outc
om
e
sh
ow
s
t
hat
MO
RSM
T
perform
s
better
than
existi
ng
app
r
oac
h
in
te
rm
s
of
co
m
pu
ta
ti
on
tim
e
red
uction
f
or
al
l
t
h
e
cases.
A
n
aver
a
ge
i
m
pr
ovem
ent
of
32.62% is
ac
hieve
d by MO
RSM
T over
exi
sti
ng
a
ppro
a
ch
.
Evaluation Warning : The document was created with Spire.PDF for Python.
In
t J
Elec
&
C
om
p
En
g
IS
S
N: 20
88
-
8708
Mem
or
y
of
I/
O
opti
mized
recti
li
nea
r
Steiner
minimu
m
tre
e
ro
uti
ng for VL
SI (Lath
a
N
. R.)
2965
Table
2.
Be
nc
hm
ark
detai
ls
Ben
ch
m
a
rk
ci
rcuit
case
Nu
m
b
e
r
o
f
n
ets
Maxi
m
u
m
d
eg
ree
Av
erage
d
eg
ree
IBM1
1
4
1
1
1
42
3
.58
IBM2
1
9
5
8
4
134
4
.15
IBM3
2
7
4
0
1
55
3
.41
IBM4
3
1
9
7
0
46
3
.31
IBM5
2
8
4
4
6
17
4
.44
IBM6
3
4
8
2
6
35
3
.68
IBM7
4
8
1
1
7
25
3
.65
IBM8
5
0
5
1
3
75
4
.06
IBM9
6
0
9
0
2
39
3
.65
IBM10
7
5
1
9
6
41
3
.96
IBM11
8
1
4
5
4
24
3
.45
IBM12
7
7
2
4
0
28
4
.11
IBM13
9
9
6
6
6
24
3
.58
IBM14
1
5
2
7
7
2
33
3
.58
IBM15
1
8
6
6
0
8
36
3
.84
IBM16
1
9
0
0
4
8
40
4
.10
IBM17
1
8
9
5
8
1
36
4
.54
IBM18
2
0
1
9
2
0
66
4
.06
Av
erage
1
0
6
2
9
9
134
3
.92
Table
3.
Wirel
eng
t
h per
form
a
nce
Ben
ch
m
a
rk
ci
rcuit
case
MORSM
T
FLUT
E
[
1
4
]
IBM1
4
4
4
3
0
7
4
4
4
5
5
3
IBM2
5
2
7
3
8
2
5
2
7
6
4
1
IBM3
7
6
1
9
9
3
7
6
2
2
7
6
IBM4
8
5
5
9
8
6
8
5
6
2
7
3
IBM5
2
8
0
9
6
1
5
2
8
1
0
8
1
6
IBM6
4
9
4
1
4
4
4
9
5
9
6
9
IBM7
9
9
4
9
7
8
9
9
5
2
6
5
IBM8
9
4
4
0
9
6
9
4
4
3
8
2
IBM9
1
2
6
0
9
1
4
1
2
6
1
1
9
9
IBM10
3
1
9
0
8
7
1
3
1
9
1
6
1
5
IBM11
1
8
9
8
9
6
1
1
8
9
9
3
6
7
IBM12
2
9
1
4
8
8
4
2
9
1
5
5
2
1
IBM13
2
4
5
0
0
8
7
2
4
5
0
5
7
7
IBM14
3
1
8
0
2
6
0
3
1
8
0
7
7
7
IBM15
2
9
2
2
3
9
5
2
9
2
2
7
7
8
IBM16
3
5
0
0
2
7
2
3
5
0
0
7
7
6
IBM17
5
3
6
8
9
1
6
5
3
6
9
6
5
9
IBM18
2
1
4
5
8
5
6
2
1
4
6
1
2
8
Av
erage
2
0
3
6
9
9
5
.3
8
9
2
0
3
7
5
3
1
.7
7
8
Table
4.
C
om
pu
ta
ti
on
ti
m
e p
erfor
m
ance
Ben
ch
m
a
rk
ci
rcuit
case
MORSM
T
FLUT
E
[
1
4
]
IBM1
9
0
0
0
0
1
8
0
0
0
0
IBM2
1
3
0
0
0
0
2
2
0
0
0
0
IBM3
1
6
3
7
0
0
2
6
7
0
0
0
IBM4
1
6
1
1
0
0
2
6
9
0
0
0
IBM5
4
1
0
0
0
0
8
7
0
0
0
0
IBM6
1
8
3
0
0
0
2
7
7
0
0
0
IBM7
1
9
3
0
0
0
2
9
8
8
0
0
IBM8
2
5
0
0
0
0
3
2
0
0
0
0
IBM9
2
1
9
0
0
0
3
2
2
0
0
0
IBM10
2
6
0
0
0
0
3
4
7
0
0
0
IBM11
2
9
8
0
0
0
3
9
0
0
0
0
IBM12
3
9
0
0
0
0
5
1
0
0
0
0
IBM13
4
1
0
0
0
0
5
7
0
0
0
0
IBM14
5
2
0
0
0
0
6
4
0
0
0
0
IBM15
5
1
7
0
0
0
6
5
1
0
0
0
IBM16
5
8
7
0
0
0
6
9
0
0
0
0
IBM17
1
1
9
0
0
0
0
1
7
8
0
0
0
0
IBM18
1
0
9
0
0
0
0
1
8
8
0
0
0
0
Av
erage
3
9
2
3
2
2
.2
5
8
2
3
2
2
.2222
Evaluation Warning : The document was created with Spire.PDF for Python.
IS
S
N
:
2088
-
8708
In
t J
Elec
&
C
om
p
En
g,
V
ol.
10
, No
.
3
,
J
une
2020 :
26
5
9
-
296
8
2966
4.3.
Me
mor
y util
iz
at
ion p
er
fo
rm
an
ce
To
eval
uate
the
per
f
orm
ance
of
m
e
m
or
y
u
sage,
v
al
gr
i
nd
[23,
24]
has
been
us
e
d.
Th
e
propos
e
d
MORSM
T
a
ppr
oac
h
is
c
om
par
ed
with
FLU
T
E
[14]
with
de
fau
lt
a
ccur
acy
=
3
inter
m
s
of
m
e
m
or
y
util
iz
at
ion
perf
or
m
ance
wh
ic
h
is
as
sh
own
in
Table
5
.
T
he
ou
tc
om
e
sh
ows
that
MORSM
T
perform
s
bette
r
than
existi
ng
a
ppr
oach
in
te
r
m
s
of
m
e
m
or
y
con
s
um
ption
f
or
al
l
the
cases
.
An
a
ver
a
ge
r
edu
ct
io
n
of
77.
71%
is
achieve
d
by
M
ORSMT
ov
e
r
existi
ng
ap
pro
ach.
The
outc
om
e
sh
ows
t
hat
m
e
m
or
y
us
age
is
directl
y
de
pe
nd
e
nt
on w
i
re len
gth
and d
e
gree si
z
e.
Table
5.
Me
m
or
y uti
li
zat
ion
pe
rfor
m
ance
Ben
ch
m
a
rk
ci
rcuit
case
MORSM
T
FLUT
E
[
1
4
]
IBM1
1
0
9
,264
3
9
8
,908
IBM2
1
6
8
,457
7
1
3
,451
IBM3
1
8
0
,996
7
1
1
,893
IBM4
2
1
1
,003
7
2
3
,607
IBM5
2
2
4
,661
1
,18
8
,898
IBM6
2
4
4
,577
9
7
0
,098
IBM7
3
3
7
,674
1
,24
8
,799
IBM8
4
1
4
,185
2
,07
8
,590
IBM9
4
1
1
,154
1
,59
5
,039
IBM10
5
2
4
,740
2
,23
9
,228
IBM11
5
3
1
,886
1
,78
9
,611
IBM12
5
4
3
,178
2
,40
7
,032
IBM13
6
5
9
,237
2
,55
1
,928
IBM14
1
,03
0
,486
3
,80
1
,149
IBM15
1
,28
4
,495
5
,60
3
,960
IBM16
1
,34
8
,313
5
,73
2
,675
IBM17
1
,41
4
,806
6
8
0
4
7
7
8
IBM18
1
,62
7
,262
6
9
8
2
4
6
2
Av
erage
6
2
5
,910
2
,64
1
,228
5.
CONCL
US
I
O
N
This
wor
k
presented
a
m
em
or
y
eff
ic
ie
nt
RSM
T
c
ons
tructi
on.
The
pro
posed
m
od
el
is
a
n
i
m
pr
ovem
ent
of
ori
gi
nal
FL
U
TE.
FL
UTE
do
es
not
co
ns
ide
r
m
e
m
or
y
op
ti
m
iz
at
ion
in
RS
MT
co
ns
tr
uction
an
d
adopted
brea
dth
first
sea
rch
to
fin
d
m
ini
m
u
m
sp
ann
in
g
t
r
ee,
w
hich
in
du
ced
m
e
m
or
y
over
hea
d.
To
a
ddress
this
pro
blem
t
he
pro
pose
d
work
a
dopts
di
vid
e
an
d
c
onqu
e
r
an
d
dep
t
h
first
sea
rch
to
fin
d
the
m
i
nim
u
m
sp
a
nn
i
ng
tree
.
The
ex
pe
rim
ents
are
c
onduct
ed
to
e
valu
at
e
the
perfor
m
ance
of
pro
po
s
ed
a
ppr
oac
h
over
existi
ng
a
ppr
oa
ch
f
or
var
ie
d
ben
c
hm
ark
s.
The
outc
om
e
sh
ows
si
gn
ific
ant
perf
or
m
ance
i
m
pr
ov
em
ent
of
0.026%
,
76.
3%
,
an
d
32.
62%
ov
e
r
existi
ng
a
ppr
oach
i
n
te
rm
s
of
wire
le
ng
t
h,
m
e
m
or
y
ov
erh
e
a
d
,
an
d
c
om
pu
ta
ti
on
ti
m
e
red
uc
ti
on
resp
ect
ively
.
The
fu
t
ur
e
w
ork
would
co
ns
ide
r
pr
ese
nt
ing
par
al
le
l
m
e
m
ory
op
ti
m
iz
ed
RSM
T
co
ns
tr
uction
an
d
e
xperi
m
ent
will
be
c
arr
ie
d
out
on
m
ul
ti
-
cor
e
e
nviro
nm
ent
su
ch
as
CPU
or
GPU to
im
pr
ove s
pee
dup per
form
ance.
ACKN
OWLE
DGE
MENTS
The
a
uthor
w
ou
l
d
li
ke
to
ackno
wled
ge
and
tha
nk
Te
chn
ic
al
E
duca
ti
on
Qu
al
it
y
I
m
pr
ov
em
en
t
Pr
og
ram
[
TEQ
IP
]
P
hase
3, BM
S Co
ll
ege
of
En
gin
eeri
ng.
REFERE
NCE
S
[
1
]
M.
R.
Gare
y
a
nd
D.
S.
Johns
on,
“
Com
pute
rs
and
i
ntr
ac
t
abili
t
y
:
A
guide
t
o
the
th
eor
y
of
N
P
-
complet
ene
ss
,
”
New York:
Free
m
an,
1979.
[
2
]
F.
K.
Hw
ang,
“
On
S
te
ine
r
m
inim
al
trees
with
re
ct
iline
ar
dis
t
ance
,
”
SI
AM
J.
Appl.
Math
.
,
v
o
l.
30
,
no.
1,
pp.
104
–
1
14,
Jan
1976.
[
3
]
F.
K.
Hw
ang,
D.
S.
Ri
cha
rds,
and
P.
W
int
er
,
“
The
S
teiner
tr
ee
prob
le
m
,
”
in
Annal
s
of
Disc
rete
Ma
the
mati
c
s
,
Am
sterda
m
,
The Net
her
la
nds:
Els
evi
er,
1992.
[
4
]
D.
M.
W
arme,
P.
W
int
er,
and
M.
Za
ch
ar
ia
sen
,
“
E
xac
t
a
lgorithm
s
for
pla
ne
Ste
ine
r
tre
e
probl
ems
:
A
computat
iona
l
stud
y
,
”
in
Ad
va
nce
s
in
Steiner
Tr
ee
s
,
D.
Z.
Du,
J.
M.
Sm
it
h,
a
nd
J.
H.
Rubinste
in
,
Eds.
Norw
el
l
,
MA
:
Kluwer,
pp.
81
–
116
,
200
0.
[
5
]
“
GeoStei
ner
—
Software
for
Com
puti
ng
Ste
ine
r
T
ree
s,”
[Onlin
e]
.
Avail
ab
le
:
htt
p
:/
/
ww
w.di
ku.
dk/geos
te
ine
r
[
6
]
V.
Vani
and
G.
R.
Prasad,
“
A
n
i
m
prove
d
augmente
d
l
ine
segm
ent
base
d
al
gor
it
h
m
for
the
g
ene
r
a
ti
on
of
recti
l
inea
r
S
te
ine
r
m
ini
m
um
tre
e
,
”
In
te
rn
ati
onal
Journal
of
El
e
ct
rica
l
a
nd
Computer
E
ngine
ering
(
IJE
CE)
,
v
ol.
7,
n
o
.
3,
pp.
1262
-
1267
,
J
une
2017
.
Evaluation Warning : The document was created with Spire.PDF for Python.
In
t J
Elec
&
C
om
p
En
g
IS
S
N: 20
88
-
8708
Mem
or
y
of
I/
O
opti
mized
recti
li
nea
r
Steiner
minimu
m
tre
e
ro
uti
ng for VL
SI (Lath
a
N
. R.)
2967
[
7
]
H.
Zhou,
“
Eff
ici
ent
Ste
ine
r
tree
construc
t
ion
bas
ed
on
spanning
gra
phs,”
in
Proc
.
Int
.
Symp
.
Ph
y
s
.
,
pp.
152
–
157,
2003.
[
8
]
H.
Zhou,
N.
Sh
eno
y
,
and
W
.
N
ic
holl
s
,
“
Eff
icie
nt
spanning
tr
ee
construc
t
ion
wi
thout
Del
aunay
tr
ia
ngul
ation,
”
I
nf.
Proce
ss
.
Let
t.
,
v
ol.
81
,
no
.
5
,
pp
.
271
–
276,
2002
.
[
9
]
A.
Kahng,
I.
Ma
ndoiu,
and
A.
Z
el
ikovsk
y
,
“
Highl
y
sca
la
bl
e
al
g
orit
hm
s
for
re
ct
i
li
ne
ar
and
oc
ti
l
i
nea
r
St
ei
ne
r
tr
ees
,
”
in
Proc
.
Asian
S
outh
Pa
ci
f
ic Des.
Au
tom.
Con
f
.
,
p
p.
827
–
833
,
200
3.
[
1
0
]
H.
Chen,
C.
Qia
o,
F.
Zhou,
and
C.
-
K.
Cheng,
“
Refi
ned
singl
e
t
runk
tre
e:
A
recti
li
n
ea
r
Ste
ine
r
t
ree
generat
or
fo
r
int
er
conne
c
t
pr
e
dic
ti
on
,
”
in
Proc
.
ACM
Int
.
Work
shop Sy
st.
Level Interconnect
Pre
dic
ti
on
,
pp
.
85
–
8
9,
2002
.
[
1
1
]
C.
Chu,
“
FLUTE:
Fast
lookup
t
abl
e
ba
sed
wire
l
engt
h
esti
m
at
ion
technique,”
In
Proc.
I
EEE/A
C
M
Intl.
Con
f.
o
n
Computer
-
Ai
ded
Design
,
pp.
696
–
701,
2004
.
[
1
2
]
C.
Chu
and
Y.
-
C.
W
ong,
“
Fast
and
a
cc
ur
at
e
re
c
ti
li
n
ea
r
Stei
n
er
m
ini
m
al
tree
a
lg
orit
hm
for
VLSI
design,”
in
Pro
c.
Int.
S
ymp.
Phy
s
,
pp.
28
–
35
,
Des
2
005
.
[
1
3
]
Y
-
C.
W
ong
and
C
.
Chu,
“
A
sc
al
ab
le
and
a
cc
ur
at
e
r
ectilinea
r
Ste
in
er
m
ini
m
al
t
ree
a
lgorithm
,”
IE
E
E
Inter
n
a
tio
n
a
l
S
ymp
o
siu
m on
V
LS
I
Desig
n
,
Auto
ma
tio
n
an
d
Test (
VLSI
-
D
AT)
,
pp.
29
-
3
4,
2008
.
[
1
4
]
C.
Chu
and
Yiu
-
Chung
W
ong
,
“
FLUTE:
Fast
lo
okup
ta
bl
e
b
ase
d
recti
l
ine
ar
S
te
in
er
m
ini
m
al
tre
e
al
gorit
hm
for
VLSI
design,
”
IE
EE
Tra
n
s
a
ctio
n
s
o
n
Co
mp
u
ter
-
Aided
Desig
n
o
f
In
teg
ra
ted
Cir
cu
it
s
a
n
d
S
ystems
,
vol.
27
,
no.
1,
pp.
70
-
83
,
2008
.
[
1
5
]
H
.
Zha
nga
,
D
-
Y.
Yea
,
W
-
Z.
Guo
,
“
A
heur
isti
c
for
construc
ti
ng
a
r
ec
t
il
in
ea
r
Stei
n
er
tre
e
b
y
reu
sing r
outi
ng
resourc
e
s
over
obsta
cles
,
”
Inte
gration
,
vol
.
55,
pp
.
162
–
175
,
2016.
[
1
6
]
P.
P.
Saha
,
S.
S
aha
and
T
.
Sam
ant
a
,
“
An
eff
i
cient
in
te
rse
ct
ion
avoi
ding
r
ectilin
ea
r
rou
ti
ng
te
ch
nique
in
VLSI,
”
Inte
rnational
C
onfe
renc
e
on
A
dvanc
es
in
Co
mputing,
Comm
unic
ati
ons
and
Informatic
s
(
ICACCI)
,
M
y
sor
e,
pp.
559
-
562
,
20
13
.
[
1
7
]
K.
Ma,
Q.
Zhou
,
Y.
Cai
,
C.
Zh
a
ng
,
and
Z
.
Qi,
“
A
Stei
ner
tr
ee
c
onstruct
ion
m
ethod
for
fle
xibilit
y
and
conge
stio
n
opti
m
iz
ation,
”
Inte
rnational
C
onfe
renc
e
on
Comm
unic
ati
ons,
Circui
ts
and
Syste
ms
(
ICC
C
AS)
,
Chengdu,
pp.
519
-
523
,
20
13
.
[
1
8
]
T.
H.
W
u,
A.
Davoodi
,
and
J.
T.
Li
nder
o
th,
“
GRIP
:
Global
r
outi
n
g
via
int
eger
progra
m
m
ing
,
”
in
IEE
E
Tr
ansacti
o
n
s
on
Computer
-
Aided
Design
of
In
te
grated
Circuits and
Syst
ems
,
vo
l.
30
,
no
.
1
,
pp
.
7
2
-
84,
Jan
2011.
[
1
9
]
W
.
W
.
Kai,
N.
Ahm
ad,
M.
H.
J
abba
r,
“
Vari
abl
e
bod
y
bia
sing
(
VBB)
base
d
VLSI
design
appr
oac
h
to
red
u
ce
st
a
tic
power,
”
Inte
rna
ti
onal
Journal
of
El
ectric
a
l
and
Computer
Engi
nee
ring
(
IJE
C
E)
,
vol.
7,
no.
6,
pp.
3010
-
3019,
Dec
2017
.
[
2
0
]
U
.
F.
Siddiqi
,
S
.
M.
Sait
,
and
Y
.
Shirai
shi,
“
A
g
ame
the
or
y
-
base
d
heur
isti
c
for
t
he
two
-
dimensional
VLSI
global
routi
ng
prob
le
m
,
”
Journal
o
f
Cir
cui
ts S
yste
ms
a
n
d
Computers
,
vo
l.
24
,
no
.
6
,
pp
.
1
550082:1
-
1550082:19,
2015
.
[
2
1
]
U
.
F.
Siddiq
i
an
d
S
.
M.
Sait,
“
A
game
th
eor
y
b
a
sed
post
-
proc
ess
ing
m
et
hod
to
e
nhanc
e
VLSI
gl
obal
rou
t
ers,”
IE
EE
Ac
c
ess
,
vol
.
5
,
p
p.
1328
–
1339
,
2
017.
[
2
2
]
K.
V
.
Ra
jkumar,
A
.
Yesubabu
,
and
K.
Subrah
m
an
y
am,
“
Fuzz
y
cl
uster
ing
and
f
uzzy
C
-
m
e
ans
par
tition
cl
ust
e
r
ana
l
y
sis
and
va
lidati
on
studi
es
on
a
subs
et
of
Cit
eScor
edata
set
,
”
Inte
rnational
Jo
urnal
of
El
e
ct
ric
al
and
Compute
r
Engi
ne
ering
(
IJ
ECE
)
, v
ol
.
9
,
n
o.
4,
pp.
2760
-
277
0,
Au
g
2019
[
2
3
]
J.
Seward
and
N.
Nethe
r
cot
e
,
“
Us
ing
v
al
grind
to
detec
t
undef
ine
d
va
lue
err
or
s
with
bit
-
pre
ci
s
ion,
”
in
Proc
.
o
f
the
USENI
X Ann
ual
Techn
ic
al
C
onfe
renc
e
,
pp.
2
–
2,
2005
.
[
2
4
]
N.
Nethe
rco
te,
R.
W
al
sh
,
and
J.
Fitz
har
ding
e,
“
Buil
ding
workload
cha
r
acte
ri
za
t
ion
tool
s
wit
h
val
grind
,”
IE
EE
Inte
rnational
Sy
mpos
ium
on
Workload
Charact
e
rization
,
San
Jos
e,
CA
,
pp
.
2
-
2
,
2
006.
[
2
5
]
C.
J.
Alper
t,
“
T
he
ISP
D98
ci
rcu
it
benc
hm
ark
suite,”
in
Proc
.
Int.
Symp.
Ph
ys.
,
pp.
80
–
85
,
Des
1998
.
[Online
]
.
Avail
ab
le
:
htt
p
:/
/
vlsic
ad
.
ucsd.
edu
/UCLAW
eb/
cheese/
ispd98.h
tml
[
2
6
]
Y.
Han,
K.
Chakra
bort
y
,
and
S.
Ro
y
,
“
A
globa
l
route
r
on
GP
U
a
rch
itect
ur
e,”
in
IEE
E
Int
ernati
on
al
Confe
renc
e
on
Computer
Desig
n
(
ICCD
)
,
pp.
1
–
6,
2013
.
[
2
7
]
H.
Shojaei,
A
.
Davoodi,
and
J.
Li
nder
o
th,
“
Congesti
on
a
n
aly
si
s
for
globa
l
rou
ti
ng
vi
a
in
te
g
er
progra
m
m
ing,
”
i
n
IEE
E
Inte
rnat
io
nal
Conf
ere
nce
on
Computer
-
Aided
Design
(
ICC
AD)
,
pp.
256
–
26
2,
2011
.
[
2
8
]
G.
Bosilc
a
,
A.
Boute
iller
,
A.
Dana
li
s,
M.
Faver
ge,
T.
H
e
rau
lt,
and
J.
J
.
Dongarra
,
“
Pa
RS
EC:
Expl
oi
ting
het
ero
g
e
neit
y
fo
r
enha
n
ci
ng
sca
l
abi
lit
y
,
”
Comput
ing
in
Scienc
e
&
Engi
n
ee
ring
,
vo
l.
1
5
,
no
.
6
,
pp
.
36
–
45,
2013
.
[
2
9
]
E.
Agullo
,
P.
R
.
Am
esto
y
,
A.
Butt
ari,
A.
Gue
rm
ouche
,
J.
L’
Exc
e
ll
en
t,
and
F.
Rouet
.
,
“
Robust
m
emory
-
awa
r
e
m
appi
ngs for
pa
ral
l
el
m
ultifront
a
l
fa
ct
ori
zations,”
SIAM
J. Scie
nt
ific
Comput
ing
,
v
ol.
38
,
no
.
3
,
201
6.
[
3
0
]
G.
Au
p
y
,
C
.
B
rasseur,
and
L
.
Marc
ha
l,
“
D
y
namic
m
emor
y
-
awa
re
ta
sk
-
tr
e
e
sche
dul
ing,”
I
n
Proceedi
ngs
of
the
In
te
rnationa
l
Parallel
and
Di
stribute
d
Proce
s
sing S
ymposium
(
IPDP
S)
,
IEE
E,
pp.
758
–
767
,
20
17.
[
3
1
]
M.
Ja
cque
li
n
,
L
.
Marc
ha
l,
Y.
R
ober
t,
and
B.
U
ça
r,
“
On
opti
m
al
tre
e
tra
v
ersa
ls
for
sparse
m
at
rix
fac
to
r
iz
a
ti
on
,
”
In
Parallel
&
Di
stribute
d
Proce
s
sing S
ymposium
(
IPDP
S)
,
2011
IEE
E
Inte
rnat
ion
al
,
I
EEE,
pp.
55
6
–
567,
2011
.
[
3
2
]
M.
Serge
nt,
D.
Gou
din,
S.
Thi
baul
t
,
and
O.
Aum
age
,
“
Co
ntrol
li
ng
th
e
m
emor
y
subs
cri
pt
ion
of
distri
but
ed
appl
i
ca
t
ions
with
a
ta
sk
-
base
d
runti
m
e
s
y
stem,
”
In
Proce
ed
in
gs
of
the
Inte
rnational
Parallel
and
Distribute
d
Proce
ss
ing
Sym
posiumWor
ksho
ps
,
page
s
318
–
3
27.
IE
EE,
2016
.
[
3
3
]
K.
Ma,
Q.
Zhou,
Y.
Cai
,
C.
Zh
a
ng
and
Z.
Qi,
"A
Stei
ner
tre
e
c
onstruct
ion
m
ethod
for
fle
xibi
l
i
t
y
and
conge
stio
n
opti
m
iz
ation,
"
2
013
Inte
rnation
al
Confe
renc
e
on
Comm
unic
ati
ons,
Circui
ts
a
nd
Syste
ms
(
IC
CCAS)
,
Chengdu,
pp.
519
-
523
,
20
13.
[
3
4
]
Kasnec
i,
G.
,
R
amana
th,
M.
,
S
ozi
o,
M.,
Such
ane
k
,
F.M.
,
W
e
ikum,
G.,
“
STAR:
Stei
n
er
-
tree
appr
o
x
imati
on
in
rel
a
ti
onship
gr
a
phs,”
In:
Proc.
of
IEEE
Int
ernati
onal
Con
fe
ren
ce
on
Data
Eng
ine
ering
,
IE
EE
,
W
ashingt
on
DC,
US
A,
pp.
868
-
8
79,
2009
.
Evaluation Warning : The document was created with Spire.PDF for Python.
IS
S
N
:
2088
-
8708
In
t J
Elec
&
C
om
p
En
g,
V
ol.
10
, No
.
3
,
J
une
2020 :
26
5
9
-
296
8
2968
BIOGR
AP
H
I
ES
OF
A
UTH
ORS
Latha
N.
R.
is
a
n
As
sistant
Profess
or
in
th
e
Dep
art
m
ent
of
Com
pute
r
Sci
ence
an
d
Engi
ne
eri
ng
,
B.
M.S.
Coll
eg
e
of
Engi
nee
r
ing,
Banga
lor
e.
She
rec
e
ive
d
B.
E
deg
ree
in
Inform
at
i
on
Scie
nce
and
Engi
ne
eri
ng
fro
m
Visvesvara
y
a
Te
chnol
og
ical
Univer
sit
y
in
2005
and
M.T
ec
h
degr
ee
in
Com
pute
r
Scie
n
ce
and Engi
ne
ering from VTU i
n
2009.
She
is c
urr
ent
l
y
pursuing
P
h.
D.
d
egr
ee in
VTU i
n
th
e area of Para
l
le
l
Com
puti
ng.
Dr.
Pr
asad
G
R
is
a
Profes
sor
in
Depa
rtment
of
Com
pute
r
Sc
ie
nc
e
&
Engi
ne
eri
ng,
BMS
CE
,
Banga
lor
e.
He
holds
a
Ph.D
f
rom
Nati
onal
I
nstit
ute
of
Te
c
hnolog
y
,
Karn
ataka
,
Surathk
al,
IND
IA.
He
rec
ei
ved
his
M.T
ec
h
degr
ee
in
Com
pute
r
Scie
n
ce
&
Engi
nee
ring
fr
om
Banga
lore
Univer
sit
y
in
1
999
and
B.
E
Degre
e
in
Com
pute
r
Scie
n
ce
&
Engi
nee
r
ing
from
Banga
lore
Univer
sit
y
in
1
995.
His
r
ese
ar
ch
int
er
ests
include
Rec
onf
igu
rab
le
computing,
Com
puti
ng
Acc
elera
tors.
Evaluation Warning : The document was created with Spire.PDF for Python.