Internati
o
nal
Journal of Ele
c
trical
and Computer
Engineering
(IJE
CE)
Vol.
4, No. 6, Decem
ber
2014, pp. 989~
998
I
S
SN
: 208
8-8
7
0
8
9
89
Jo
urn
a
l
h
o
me
pa
ge
: h
ttp
://iaesjo
u
r
na
l.com/
o
n
lin
e/ind
e
x.ph
p
/
IJECE
An Area-Optimized Chip of Ant
Colon
y
Al
gorithm Desi
gn i
n
Hardware Platform Using th
e Ad
dress
-
Based M
e
t
h
od
E. Sh
afi
g
h
Fard
1
, K
.
Monf
ar
edi
2
, M
.
H
.
N
a
dimi
3
1
Faculty
of Computer
Engineerin
g, Najafab
a
d br
anc
h
,
Isla
mi
c
Az
ad Uni
v
ersity
, Isf
a
han, Iran
2
Engineering Faculty
,
Depar
t
ment of
El
ectr
i
ca
l
a
nd El
ectron
i
c
En
gineer
ing,
Azarb
a
ij
an S
h
ahid
M
a
dani Univ
ers
i
t
y
,
T
a
br
iz, Ir
an
3
Faculty
of Computer
Engineerin
g, Najafab
a
d br
anc
h
,
Isla
mi
c
Az
ad Uni
v
ersity
, Isf
a
han, Iran
Article Info
A
B
STRAC
T
Article histo
r
y:
Received Aug 29, 2014
Rev
i
sed
O
c
t 17
, 20
14
Accepte
d Nov 5, 2014
The ant colon
y
algorithm
is a nature
-inspir
e
d
algorithm highly
used for
solving man
y
co
mplex problems and fi
nding
optimal solutions; h
o
wever,
th
e
algorithm has a
major flaw and that is
the v
a
st amount of calculations and if
the proper
correction algorithm
and arch
ite
ctur
al design are not
provided,
it
will l
ead
to
the
i
n
creasing
use of
hardwar
e
pl
atfo
rm
due to
the
hi
gh volum
e
of operations;
and perhaps
at h
i
gher scal
es
, i
t
caus
e
s
th
e ch
ip
are
a
not
to
work becaus
e
o
f
the high num
ber of problem
s
;
hence
,
the pur
pos
e of this
paper is to save the hardwar
e
platform
as far as p
o
ssible and use it optimally
through providing a p
a
rticular
algorithm
runn
ing on a
reconf
igurable chip
driven b
y
the address-based method,
so that the comparison of s
y
nthesis
operations with the similar works show
s significant
impr
ovements as much
as 1/3
times greater
than
the oth
e
r
similar h
a
rdwar
e
methods.
Keyword:
An
t co
lon
y
Ch
ip
area
Nature-inspir
e
d algorithm
Reconfigura
b
l
e
chip
Copyright ©
201
4 Institut
e
o
f
Ad
vanced
Engin
eer
ing and S
c
i
e
nce.
All rights re
se
rve
d
.
Co
rresp
ond
i
ng
Autho
r
:
E. S
h
afi
g
h Fa
r
d
,
Facul
t
y
o
f
C
o
m
put
er En
gi
ne
eri
n
g,
Na
jafa
b
a
d B
r
a
n
c
h
,
Islamic
Azad Uni
v
ersity, Isfahan, Ira
n.
Em
a
il: sh
afig
hfard
@
azarun
i
v.edu
1.
INTRODUCTION
Im
it
at
i
ng t
h
e nat
u
re an
d i
t
s
expe
ri
ences i
s
one
of t
h
e
m
o
st
co
m
m
on
m
e
t
hods u
s
ed
i
n
art
i
f
i
c
i
a
l
intelligence. Algorithm
s
and evol
utiona
ry c
o
m
putations
re
fer t
o
a set
of
m
e
thods
whos
e problem
s
have
been
so
lv
ed
b
e
i
n
g
insp
ired
b
y
th
e ev
o
l
u
tio
n
o
f
an
imals, p
l
an
ts, an
d
insects in
natu
re. Th
is typ
e
o
f
algo
rith
m
s
wh
ich
i
s
used
t
o
fi
nd
t
h
e o
p
t
i
m
al
sol
u
t
i
on i
n
cl
u
d
e c
o
m
p
l
e
x an
d t
i
m
e-cons
um
i
ng cal
cul
a
t
i
ons c
a
usi
n
g t
h
es
e t
y
pes
of
p
r
ob
lem
s
to
b
e
r
e
m
a
in
ed
un
an
sw
er
ed
in
t
h
e
p
a
st; bu
t sin
c
e th
e ear
ly
1
990s, th
e sp
eed
o
f
an
t co
l
o
n
y
al
go
r
ith
m
bega
n
t
o
i
m
prove usi
n
g para
l
l
e
l
soft
ware m
e
t
hods [1
,
2,
3]
. B
y
20
02
, al
l
m
e
t
hod
s w
e
re so
ft
wa
re-
b
ased a
n
d
m
o
st
ly
al
ong
wi
t
h
t
h
e
paral
l
el
pr
ocessi
n
g
t
echni
que
[
4
,
5]
and i
n
a fe
w c
a
ses we
re r
un i
n
pa
ral
l
e
l
on a
gra
p
hi
c
process
o
r com
pos
ed
of m
u
ltiple core
s [6]. From
the
2000s onwa
rds
,
m
e
thods
for reconfigura
b
le on-c
hip
har
d
ware i
m
pl
em
ent
a
t
i
on be
gan
t
o
be
use
d
by
D
r
.
Sc
he
uerm
ann’
s w
o
rk
gr
o
u
p
[
7
]
an
d l
a
t
e
r, a
w
o
r
k
was
prese
n
t
e
d
usi
n
g t
h
e i
m
pl
em
ent
a
t
i
on b
a
sed
o
n
C
M
OS t
ec
h
n
o
l
o
gy
[8]
as w
e
l
l
as 2 wor
k
s
were
prese
n
t
e
d
based
on t
h
e rec
o
n
f
i
g
u
r
a
b
l
e
chi
p
wi
t
h
t
h
e c
o
m
p
rehe
nsi
v
e
use
of al
l
o
n
-c
hi
p
IPs a
nd c
o
res
[9
, 1
0
]
and i
n
20
1
2
, a
wo
rk
w
h
i
c
h ca
n
be c
onsi
d
ere
d
as a
c
o
m
p
ro
m
i
se of
har
d
w
a
re a
n
d
so
ft
wa
re w
a
s
prese
n
t
e
d i
n
w
h
i
c
h
be
si
des t
h
e
flex
ib
ility o
f
so
ft
ware, t
h
e h
a
rdware sp
eed
has b
een
also
add
e
d
[11
]
. In
the fo
llowing
, sectio
n
s
2-4
h
a
ve b
e
en
p
r
ov
id
ed
as follo
ws: In sectio
n 1, t
h
e ev
o
l
u
tio
n
a
ry
algorith
m
s
, p
a
rticu
l
arly th
e
an
t co
lo
n
y
al
g
o
rith
m are
introduced; in section 2, the
m
e
thod
pres
ented
by this pape
r will be
di
scuss
e
d; sect
ion
3 is de
vot
ed to
eval
uat
i
o
n,
si
m
u
l
a
t
i
on,
a
n
d
co
m
p
ari
s
on
wi
t
h
pre
v
i
o
us m
e
t
hods;
an
d sect
i
o
n
4 i
n
cl
u
d
es c
o
ncl
u
si
ons
an
d
f
u
t
u
re
wo
rk
s.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
IJECE Vol. 4, No. 6, D
ecem
ber 2014
:
989 – 998
99
0
2.
THE ANT COLONY
ALGORITHM
In a gr
o
u
p
col
l
ect
i
v
e beha
vi
o
r
m
odel
,
a gr
o
up
of pe
o
p
l
e
are wor
k
i
n
g t
o
ge
t
h
er t
o
achi
e
ve
t
h
e ul
t
i
m
a
t
e
goal
.
Thi
s
m
e
tho
d
i
s
m
u
ch m
o
re
be
ne
ficial than
when t
h
ey act indepe
nd
en
tly. Th
e an
t co
lon
y
can
b
e
defin
e
d
as an
o
r
g
a
ni
ze
d set
of
or
gani
sm
s whi
c
h c
o
l
l
abo
r
at
e wi
t
h
e
ach
ot
he
r
usi
n
g
phe
r
o
m
ones
and
t
h
e
i
n
f
o
rm
at
i
on
ex
ch
ang
e
d b
y
u
p
d
a
ting
p
h
e
ro
m
o
n
e
s [12
]
.
In
co
m
p
u
t
ation
a
l co
llectiv
e
in
tellig
en
ce, creatu
r
es su
ch
as an
ts,
t
e
rm
i
t
e
s, bees,
fi
sh,
an
d
bi
r
d
s
gr
o
ups
are m
odel
e
d.
I
n
t
h
i
s
t
y
pe o
f
st
r
u
ct
u
r
es, eve
r
y
l
i
v
i
n
g t
h
i
n
g
i
s
d
o
i
n
g a
ver
y
sim
p
le task, but their coope
ration
with each othe
r shows com
p
lex beha
viors [13]. T
h
e overall non-linea
r
beha
vi
o
r
o
f
a
com
m
uni
t
y
i
s
obt
ai
ne
d
f
r
om
com
b
i
n
i
n
g i
n
di
vi
d
u
al
be
hav
i
ors
o
f
t
h
at
co
m
m
uni
t
y
;
i
n
o
t
her
wo
rd
s, t
h
ere i
s
a ve
ry
com
p
l
e
x rel
a
t
i
o
ns
hi
p
bet
w
ee
n t
h
e
co
l
l
ect
i
v
e and i
n
di
vi
d
u
al
beha
v
i
ors
of
a c
o
m
m
uni
t
y
.
Th
e co
llectiv
e
b
e
h
a
v
i
or also
d
e
p
e
nd
s on
th
e in
teractio
n
b
e
tween
i
n
d
i
v
i
duals, so
th
at in
teractio
n
s
enh
a
nce th
e
expe
ri
ences
of
i
n
di
vi
dual
s
a
n
d t
h
ere
b
y
caus
e
t
h
e
pr
o
g
ress
of
t
h
e
c
o
m
m
u
n
i
t
y
.
Whe
n
an
ant
i
n
ci
t
y
wa
nts
t
o
g
o
to th
e nex
t
city, e.g
.
city
, t
h
e
p
r
ob
ab
ility
d
i
stribu
tio
n is
u
s
ed
b
y
th
e an
t to select th
e nex
t
city [M. Do
ri
g
o
,
G. Di
Car
o
,
L.
Gam
b
ardella, 19
9
9
]
.
,
,
∑
,
,
(1
)
Howev
e
r, in
t
h
e
p
r
o
b
a
b
ility d
i
stribu
tio
n (eq
u
a
tion
1
)
, th
ere sh
ou
ld
b
e
a lin
k
b
e
tween
and
, so
it
can be
sai
d
t
h
a
t
no
de
is th
e neig
hb
or
o
f
no
de
. As t
h
e eq
uat
i
on i
m
pl
i
e
s, t
h
e st
udi
e
d
s sh
ou
ld
b
e
long
to
t
h
e
set
N co
nt
ai
ni
ng t
h
e
no
des t
h
at
ha
ve
not
b
een
pre
v
i
o
usl
y
sel
ect
ed,
beca
use
s w
h
i
c
h
h
a
ve
been al
rea
dy
selected are as
sum
e
d to be ze
ro. After calc
u
lating the
s which
m
u
st b
e
calcu
lated
,
in
the in
terv
al
0,1
is a rand
o
m
v
a
riab
le co
m
p
ared
with
q
wh
ich
is a
p
a
ram
e
t
e
r
o
f
th
e an
t co
lon
y
algo
rithm
,
so
th
at to go
fro
m
no
de
t
o
n
ode
usi
n
g t
h
e
pat
h
;
If
,
If s is
n
o
t
am
o
n
g
th
e
rem
a
in
i
n
g cities
If s is
o
n
e
of t
h
e rem
a
in
in
g
cities
(2
)
If
,
If t
h
e
best m
o
de is selected
If t
h
e
next m
o
de is selected
(3
)
After search
ing
for a so
lu
tion and
co
m
p
letin
g
th
e iteratio
n,
ant
s
pe
rf
o
r
m
t
h
e fi
nal
up
dat
e
ope
rat
i
o
ns t
e
r
m
ed as
th
e g
l
ob
al u
pdate. Here, th
e an
t th
at h
a
s
m
a
d
e
th
e sho
r
test to
ur is allo
wed to
m
o
d
i
fy th
e p
h
e
ro
m
o
n
e
o
f
ed
g
e
s
b
e
lon
g
i
n
g
to
it
s tou
r
; th
is in
crease in
t
h
e
p
h
e
ro
m
o
n
e
is accord
i
n
g
to
equ
a
tio
n 4.
1
(4
)
B
a
sed o
n
t
h
e g
l
obal
u
pdat
e
,
o
n
l
y
t
h
e phe
ro
m
one of edg
e
s
bel
o
n
g
i
n
g t
o
t
h
e sh
ort
e
st
pat
h
i
s
chan
ge
d and t
h
e
h
i
gh
est
v
a
lu
e
of
p
h
e
ro
m
o
n
e
is assign
ed to
edg
e
s
with
t
h
e sho
r
test leng
t
h
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
An
Area-Op
timized
Ch
i
p
o
f
An
t Co
l
o
n
y
Algorith
m
Design
i
n
Ha
rd
w
a
re Pl
a
tfo
rm Using
…
(
E
. S
haf
i
g
h
Far
d
)
99
1
3.
THE PROPOSED
METHOD
In
t
h
i
s
sect
i
o
n,
a f
r
am
ewor
k i
s
p
r
ese
n
t
e
d
f
o
r
m
odel
i
ng a
n
t
col
o
ny
al
g
o
ri
t
h
m
,
whi
c
h t
a
kes
ad
vant
a
g
e
o
f
th
e hard
w
a
r
e
d
e
sign
b
a
sed
on
th
e p
r
og
r
a
mm
ab
le sy
ste
m
-
o
n-
ch
i
p
(PSo
C
)
to
cover
a w
i
d
e
r
a
ng
e o
f
ap
p
lication
s
. Th
e resu
lts of all so
ftware on th
e d
e
sk
t
o
p p
r
oces
so
r ha
ve
been c
o
m
p
are
d
wi
t
h
t
h
e m
odel
i
ng
r
e
su
lts of
th
e ad
dr
ess-or
iented
architecture based
on the programm
ab
le syste
m
-on-c
h
ip. T
h
e pres
ented
m
e
t
hod i
s
ai
m
e
d at
red
u
ci
n
g
t
h
e
pr
ocessi
n
g
t
i
m
e of t
h
e a
l
go
ri
t
h
m
.
The
pr
o
pose
d
a
r
c
h
i
t
ect
ure i
s
c
o
m
p
l
e
t
e
l
y
har
d
ware
-o
ri
en
t
e
d w
h
i
c
h
ha
s
bee
n
i
m
pl
em
ent
e
d
usi
n
g
t
h
e ad
dres
s-
base
d m
e
t
hod.
T
h
e effi
ci
en
cy
o
f
t
h
e
prese
n
t
e
d
arc
h
i
t
ect
ure has
b
een ev
al
uat
e
d
by
seve
ral
b
e
nchm
ark
pr
o
b
l
e
m
s
. I
m
pl
em
ent
a
t
i
ons ha
ve bee
n
per
f
o
r
m
e
d usi
n
g va
ri
o
u
s
desi
g
n
t
o
ol
s suc
h
as
Xi
l
i
nx
ISE a
n
d M
a
xPl
u
sI
I as
wel
l
as VH
D
L
(V
HS
IC
ha
r
d
wa
re
d
e
scri
p
tio
n lang
u
a
g
e
); and
t
h
e co
m
p
letely s
o
ft
ware cases
h
a
v
e
b
e
en
simu
lated
in Matlab
.
3
.
1
Pa
ra
lle
l An
t
C
o
lo
ny
A
l
go
r
i
t
h
m in
Ha
rd
wa
r
e
P
l
a
t
f
o
rm
Here, th
e an
ts’ p
e
rfo
r
m
a
n
ce in
th
e recon
f
igu
r
ab
le ch
ip
p
l
atfo
rm
is d
e
scrib
e
d in
accord
a
n
ce
with
the
propose
d
i
d
ea. The following flowcha
r
t
(F
i
g
ure
1
)
s
h
ows
t
h
e ant
s
’
pe
rf
o
r
m
a
nce.
Fig
u
re
1
.
Th
e flo
w
ch
art
o
f
th
e propo
sed an
t co
lon
y
algo
rithm
in
th
e
h
a
rdware
p
l
atform
As ob
serv
ed
in Fig
u
re 2, first
l
y, 2
RAM b
l
ock
s
are in
itialized
; on
e of th
ese RAMs is u
s
ed
to
store
t
h
e i
n
f
o
rm
ati
on o
f
phe
r
o
m
one bet
w
ee
n t
w
o
no
des a
n
d t
h
e
ot
he
r o
n
e,
des
p
i
t
e
bei
ng st
ore
d
i
n
a R
A
M
bl
ock
,
i
s
in the application
of R
O
M,
because it hol
ds he
uristic
coefficients to
prevent a
n
y cha
nge
s in the
di
stance
bet
w
ee
n t
w
o
n
ode
s du
ri
n
g
t
h
e execut
i
o
n of
t
h
e pr
og
ram
;
and m
o
st
im
port
a
nt
l
y
, R
e
sul
t
RAM
whi
c
h i
s
used as
t
h
e c
ont
r
o
l
of
no
des
sel
ect
o
r
desel
ect
has
a
s
m
a
ny
one
-bi
t
u
n
i
t
s
as t
h
e
n
u
m
ber of
n
o
d
es
t
h
at
al
l
are
fi
rs
t
l
y
set
t
o
zer
o;
nam
e
ly
, no
n
o
d
e has
been
se
lected
and t
h
e fiel
d re
lated to a nod
e
becom
e
s 1 wit
h
eac
h choice.
In all
ant colony algorithm
s
that are im
ple
m
ent
e
d i
n
t
h
e har
d
war
e
pl
at
fo
rm
pherom
one val
u
es
st
ore
d
i
n
t
h
e m
e
m
o
ry
are c
onsi
d
ere
d
as an n*n m
a
trix like
Figure
.
In
t
h
e ph
ero
m
o
n
e
m
a
trix
, th
e v
a
lu
es
of
,
m
a
kes up col
u
m
n
s and
rows
of the
m
a
trix and e
ach a
n
t is
assi
gne
d
t
o
a
r
o
w;
i
n
t
h
e m
e
nt
i
one
d
fl
owc
h
art
,
ant
n
u
m
b
er
1,
i
n
t
h
e
be
gi
n
n
i
n
g,
i
s
ass
i
gne
d t
o
t
h
e z
e
ro
-
col
u
m
n
an
d r
o
w an
d
be
gi
ns i
t
s search
o
p
era
t
i
ons a
nd
re
a
d
s
the pherom
one and he
uris
tic
coefficient val
u
es
of
cell
,
from
the related m
e
m
o
ries and carries
out
opera
tions in
accorda
n
ce with
th
e flowc
h
art;
selecting each
n
o
d
e
cau
ses the v
a
l
u
e
o
f
M,
wh
ich
h
a
s
b
e
en
in
itially set
to
zero, t
o
b
e
i
n
crem
en
ted
on
e un
it, an
d th
e ad
dress
associated wit
h
the selected node is store
d
in a
m
e
m
o
ry c
a
lled
Resu
lt an
d
th
e an
t find
s
its n
e
x
t
row b
a
sed
on
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
IJECE Vol. 4, No. 6, D
ecem
ber 2014
:
989 – 998
99
2
th
e n
o
d
e
curren
tly fo
un
d
so
th
at u
s
in
g
left-sh
i
ft op
erations wh
ich
is a k
i
n
d
of sub
s
titute fo
r m
u
ltip
li
catio
n
o
p
e
ration
s
to l
o
wer
th
e
po
wer
co
n
s
u
m
p
tio
n
,
it g
o
e
s fro
m
o
n
e
row t
o
an
o
t
h
e
r in
each
t
r
an
sitio
n.
Fi
gu
re
2.
The
m
ovem
e
nt
of a
n
t
s
i
n
t
h
e
p
h
er
om
one m
a
t
r
i
x
Ho
we
ver
,
i
f
an
y
node
d
o
s n
o
t
m
eet
t
h
e condi
t
i
on o
f
bei
n
g
g
r
eat
er t
h
a
n
t
h
e ran
d
o
m
nu
m
b
er ge
nerat
e
d
b
y
LFSR
m
e
th
o
d
[1
4
]
, th
e ant j
u
st tries to alter th
e co
lu
mn
fro
n
t
ward
and
stays in th
e
sam
e
ro
w to select a
n
o
d
e
as well as b
y
selecting
a no
d
e
, ch
ecks if th
e co
n
d
ition
M=n is m
e
t
o
r
no
t,
wh
ich
i
t
sh
ows wh
ether all
no
des ha
ve be
en sel
ect
ed or
not
. I
f
M
=
n, t
h
e proc
ess o
f
cr
eat
i
ng a sol
u
t
i
on f
o
r t
h
at
i
t
e
rat
i
on i
s
com
p
let
e
d and
the local
updat
e
phase a
n
d then the
phase
of assessing t
h
e
com
p
etence of
ants
begi
ns. By com
p
aring the cost
fun
c
tion
s
o
f
all th
e an
ts, th
e
lo
west co
st
fun
c
tio
n is selected
and
con
s
eq
u
e
n
tly th
e
p
h
ero
m
o
n
e
m
e
mo
ry is
up
dat
e
d;
a
f
t
e
r
t
h
e u
p
d
at
e, as
m
e
nt
i
oned
i
n
t
h
e
pre
v
i
o
us
sectio
n
“fam
i
liarity with
th
e ant co
lon
y
algo
ri
th
m
”
,
t
h
i
s
al
go
ri
t
h
m
can be
re
peat
ed t
o
i
n
fi
ni
t
y
t
i
m
es;
i
t
shoul
d
m
e
nt
i
oned t
h
at
aft
e
r d
o
i
n
g al
l
phas
e
s, at
t
h
e
end
,
t
h
e
iteratio
n
co
nd
i
tio
n
is always ch
eck
e
d
and
if th
e term
in
at
i
on
of
o
p
erat
i
ons
i
s
t
r
ue
, t
h
e pr
ocess
o
f
p
r
o
g
ram
execution ends
up.
3.
2 T
h
e Fra
m
ew
ork o
f
An
t
Col
o
n
y
Op
ti
m
i
z
a
tion Algori
thm Ar
chitec
ture Based
on
the
Pr
ogr
am
mabl
e
Sys
t
em-On
-Chip
Mod
ifica
tio
n
s
o
n
th
e
An
t C
o
lon
y
Al
g
o
r
it
hm:
Som
e
m
odi
fi
cat
i
ons
ha
ve
bee
n
c
o
n
d
u
ct
ed
on
t
h
e
al
go
ri
t
h
m
t
o
reduce
ha
rd
wa
re
cost
s;
f
o
r
exa
m
pl
e, sim
p
l
e
regi
st
er s
h
i
f
t
o
p
e
rat
i
ons
ha
ve
been
use
d
i
n
st
ead
of
m
u
lt
i
p
l
i
cat
i
on ope
rat
i
o
ns as wel
l
as a seri
es of si
m
p
l
e
ch
ange
s ha
ve be
en co
nd
uct
e
d i
n
t
h
e u
pdat
e
p
r
oces
s
with
ou
t
d
e
fecti
n
g th
e m
a
in
pro
g
ram
to
p
r
ev
en
t
n
u
m
b
ers
fr
o
m
bei
ng di
s
p
l
a
y
e
d as
deci
m
a
l o
n
es.
The architectural str
u
cture
:
The f
r
am
ewo
r
k
desi
g
n
e
d
f
o
r t
h
e al
g
o
ri
t
h
m
has consi
s
t
e
d o
f
a
reco
nfi
g
u
r
a
b
l
e
chi
p
s
o
t
h
at
t
h
e ant
col
ony
p
a
ram
e
t
e
rs are
defi
ned i
n
t
w
o
bl
oc
ks o
f
m
e
mory
o
n
rec
o
n
f
i
g
u
r
a
b
l
e
chi
p
an
d al
l
a
r
i
t
h
m
e
t
i
c
operat
i
ons
o
f
t
h
e al
g
o
ri
t
h
m
are
har
d
wa
re m
odel
e
d
on
FP
G
A
l
o
gi
cs.
Fi
g
u
re
3
sho
w
s
t
h
e p
r
esent
e
d f
r
am
ework a
n
d
t
h
e co
nne
ct
i
o
n
s
bet
w
ee
n
di
ff
erent
bl
oc
ks;
a
s
sh
ow
n i
n
t
h
e
fi
g
u
re, t
h
ere a
r
e t
w
o
i
nde
pen
d
e
n
t
m
e
m
o
ri
es i
n
cl
u
d
i
ng m
a
i
n
para
m
e
t
e
rs of t
h
e
al
go
ri
t
h
m
al
ong
wi
t
h
e
v
al
uat
i
on,
u
p
d
at
e, a
n
d ci
t
y
selection units each of
which has
c
o
ns
isted
of a se
ries
of sub-bloc
ks.
Figure
3. The
a
r
chitectural structure
of t
h
e a
n
t
col
ony
al
g
o
r
i
t
h
m
based
o
n
t
h
e
pr
o
g
ram
m
abl
e
sy
st
em
-on-
chi
p
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISS
N
:
2088-8708
An
Area-Op
timized
Ch
i
p
o
f
An
t Co
l
o
n
y
Algorith
m
Design
i
n
Ha
rd
w
a
re Pl
a
tfo
rm Using
…
(
E
. S
haf
i
g
h
Far
d
)
99
3
Inter-c
h
ip m
e
m
o
ries have
been selected a
nd t
h
e
hardwa
re core
of t
h
e
ant col
ony
optim
i
zation
al
go
ri
t
h
m
has
been
m
odel
e
d
on
FP
G
A
l
o
gi
c
s
.
Memories:
T
h
e di
st
ance i
n
f
o
R
A
M
C
o
re (t
he m
e
m
o
ry
of
he
uri
s
t
i
c
i
n
f
o
rm
ati
on)
w
h
i
c
h st
o
r
es t
h
e
in
fo
rm
atio
n
inclu
d
i
ng
a
1
00% en
larg
em
ent of the
distance betwee
n nodes a
nd ca
n
be
m
odeled as
an n*n
matrix
; fo
r n
=
1
6
, it can
b
e
co
n
s
i
d
ered
th
at th
e d
i
am
e
t
er o
f
th
e
m
a
trix
is
e
n
tirely zero, be
cause the dista
n
ce of
a no
de
fr
om
itsel
f i
s
zero
.
T
h
e p
h
e
r
om
one
i
n
f
o
R
A
M
C
o
re
which stores the val
u
e of pherom
one s
ecreted
bet
w
ee
n n
o
d
es
and i
s
di
s
p
l
a
y
e
d as an
n*
n
m
a
t
r
i
x
. B
o
t
h
of m
e
m
o
ri
es
m
e
nt
i
one
d a
b
o
v
e
are of t
h
e R
a
m
bl
ock
typ
e
an
d
in
itialized
with
d
e
fau
lt v
a
lu
es; ho
wev
e
r,
th
e d
i
stan
ce in
fo
RAM Co
re is a BRAM typ
e
in
th
e
appl
i
cat
i
o
n of
R
O
M
.
The m
e
m
o
ry
of t
h
e c
ont
rol
u
n
i
t
whi
c
h has
been si
m
u
l
a
t
e
d as a m
u
lt
i
p
l
e
xer us
es LUTs
distributed in
FPGA platform
;
this N*1 m
u
ltiplexer is
firstly initialized as n 0-
bit
inputs to c
o
nvey the
co
n
c
ep
t of d
e
selectin
g
th
e d
e
sired
city, wh
ich
tak
e
s th
e
flag
with
v
a
lu
e
1
in
th
e m
u
ltip
le
x
e
r after rep
eat
in
g
th
e
o
p
e
ration
and
meetin
g
th
e con
d
ition
of selectin
g
th
e
relevan
t
no
d
e
. Th
e resu
lt m
e
m
o
ry
i
n
clud
ing
th
e
best an
d
m
o
st
o
p
tim
a
l
resu
lts is a R
A
M b
l
o
c
k
which
co
n
t
ains th
e ele
m
en
ts (n
od
es) add
r
esses in
th
e
m
e
mo
ry; for
exam
pl
e, i
t
has
a 1
6
*
8
m
e
m
o
ry
fo
r a
1
6
-
f
ol
d
no
de.
The next city selection block
:
As sh
o
w
n i
n
fi
gu
re 3, t
h
i
s
bl
ock c
onsi
s
t
s
of t
w
o bl
oc
ks as 1- t
h
e
cont
rol
uni
t
a
n
d
2- t
h
e ari
t
h
m
e
t
i
c
uni
t
i
n
cl
u
d
i
ng s
u
b-
bl
oc
ks
fo
r
gene
rat
i
n
g
ran
d
o
m
num
bers, c
o
m
p
ari
s
o
n
, a
n
d
a series
of arith
m
e
t
i
c o
p
e
ratio
n
s
b
a
sed
o
n
th
e R
o
u
l
ette
Wh
eel law.
In th
e
fo
llowing
,
th
e
b
l
o
c
k
s
and th
eir
fu
nct
i
o
ns a
r
e
d
i
scusse
d i
n
det
a
i
l
.
Th
e con
t
ro
l
unit:
As m
e
n
tio
ned
in section
2, an
ts resp
ectiv
el
y
and
n
ode
t
o
no
de ca
rry
o
u
t
t
r
a
v
ersal
ope
rations from
the
nest based on
the
laws of
proba
b
ility t
o
reach the
food; howev
e
r
, to
pre
v
e
n
t the
re
petitive
sel
ect
i
on o
f
a
no
de i
n
t
h
e p
a
t
h
, i
t
sh
oul
d b
e
cont
rol
l
e
d t
h
at
t
h
e t
r
ave
r
se
d n
o
d
es are
se
parat
e
d f
r
om
the o
n
es
not
t
r
ave
r
se
d.
So as
s
h
o
w
n i
n
fi
g
u
re
4
,
a l
o
g
i
c ci
rcui
t
i
s
use
d
, i
n
whi
c
h a
f
l
ag i
s
se
que
nt
i
a
l
l
y
defi
ne
d
fo
r eac
h
n
o
d
e
. Th
e flag
is sto
r
ed
i
n
a
16
-b
it array wh
i
c
h
o
p
e
rates in th
e form
o
f
a
16
*1
m
u
ltip
lex
e
r; and
each
an
t
starts
the searc
h
from
the cell arra
y 1
(the cell a
r
ray 0 is
related t
o
the
s
o
urce a
n
d
has
bee
n
alre
ady selected).
Fi
gu
re
4.
The
bl
oc
k
di
ag
ram
of
t
h
e c
o
nt
rol
u
n
i
t
If t
h
e
flag is 0, it m
eans that the
releva
nt
node
ha
s
been s
e
lected; and if it is 1, the
node ca
n
be
a
candi
dat
e
f
o
r
b
e
i
ng el
ect
e
d
as
t
h
e
next
ci
t
y
;
hence
,
us
i
n
g t
h
i
s
m
e
t
hod
, t
h
e
num
ber
of
co
m
p
ari
s
ons i
s
re
duce
d
,
because the
r
e is no nee
d
to c
h
eck
whethe
r
a node
has
bee
n
alrea
d
y selected or no
t. The
furthe
r explanation
t
h
at
can be gi
v
e
n fo
r t
h
e co
nt
rol
u
n
i
t
i
s
t
h
at
whe
n
a fl
ag re
l
a
t
e
d t
o
a node
i
s
checked t
o
ens
u
re t
h
e sel
ect
or
d
e
select o
f
th
e n
o
d
e
, if th
e flag
h
a
s no
t b
e
en
alread
y selected
; n
a
m
e
ly,
th
e flag
is 0
,
th
e syste
m
will g
o
to
ward
s BRAM to
fin
d
th
e
p
a
ram
e
ters related
to
th
e relev
a
n
t
nod
e. Acco
rd
ing
to
th
e ru
les p
r
ev
iou
s
ly
stated
,
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
IJECE Vol. 4, No. 6, D
ecem
ber 2014
:
989 – 998
99
4
th
e d
e
sired nod
e m
eets th
e co
nd
itio
ns an
d
b
een selected
,
th
e v
a
l
u
e
ob
tain
ed fro
m
th
e co
m
p
arato
r
h
a
s
b
eco
m
e
1 (act
i
v
e
hi
g
h
);
and si
nce t
h
e i
d
ea p
r
o
p
o
se
d b
y
t
h
i
s
paper i
s
add
r
ess
-
ba
sed
,
t
h
e ad
dress
of
desi
re
d n
o
d
e st
or
e
d
in a re
gister is
m
u
ltiplied by
10 He
x or 16 bina
ries, because
it
has been
designe
d
in t
h
e m
e
m
o
ry so that for
ex
am
p
l
e, th
e a
d
dr
esses
H
”
000
0
”
to
H
”
000
1” an
d
H
”
00
10
” to
H
”
00
11
” are r
e
sp
ectiv
ely assig
n
e
d
to
nod
es
0
and
1, a
nd s
o
fo
rt
h.
As o
b
s
e
rve
d
i
n
fi
gu
re
4, w
h
e
n
a n
o
d
e i
s
sel
ect
ed,
t
h
e val
u
e
of a
d
d
r
ess i
n
t
h
e
r
e
gi
st
er
wh
ich
shou
ld
b
e
read
fro
m
BRAM is reset an
d
m
u
ltip
lie
d
b
y
th
e m
u
lti
p
l
ex
er wh
ose selecto
r
v
a
l
u
e is 1
;
and
th
e lin
e
1
of mu
ltip
lex
e
r en
tered
th
e
add
r
ess
reg
i
ster
wh
ic
h
is an
ad
dress co
un
ter is
no
t selected
, b
ecau
s
e the
selecto
r
is zero
; on
t
h
e
o
t
h
e
r
h
a
nd
, th
e sel
ecto
r
o
f
m
u
lti
p
l
ex
er
1
6*1
selects lin
e 1
t
h
ro
ugh
th
e selecto
r
; in
o
t
h
e
r wo
rd
s, an
ov
erall reset
is co
n
d
u
c
ted
in
m
u
ltip
lex
e
r 1
6*1
and
ch
eck
i
ng
th
e flag
s
is restarted
from th
e
source
node to the node
ne
wly selected; but if we co
nsider
the
case when
the desire
d
node has not been
selected
and
the sig
n
a
l
ou
tpu
t
fro
m
th
e co
mp
arat
o
r
is
0
,
al
l ch
eck
s will be p
e
rfo
rm
ed
in th
e sam
e
seq
u
en
tial
manner a
nd
no
m
u
tation will
take place, bec
a
use no reset
has been
occurred in re
gi
sters through
the signal
0
resu
lted fro
m
th
e co
m
p
arato
r
;
and
selecting
lin
e 1 of
b
o
t
h
m
u
l
tip
lex
e
rs,
wh
et
h
e
r m
u
ltip
lex
e
r
16
*1
o
r
8*
1, the
regi
st
er
o
f
i
n
c
r
em
ent
a
l
count
er i
s
sel
ect
ed
a
n
d
o
p
e
r
at
i
ons
are se
que
nt
i
a
l
l
y
per
f
o
r
m
e
d. It
sh
o
u
l
d
be al
s
o
n
o
t
e
d
that there
m
u
st be a
se
parate c
ont
rol
unit for
each a
n
t.
Th
e ca
lcu
l
a
tion
s
a
n
d
log
i
c
un
it (th
e
an
t co
l
o
n
y
l
a
ws
o
f
p
r
o
bab
ility
)
:
Mo
st r
u
les an
d oper
a
tio
n
s
of
th
e
an
t co
lon
y
algo
rith
m
n
eed
ed
to
fi
n
d
th
e n
e
x
t
no
d
e
is
p
e
rfo
rmed
in
t
h
is
b
l
ock
.
As sh
own i
n
figu
re 5, two m
a
i
n
param
e
t
e
rs (t
h
e
p
h
er
om
one
and
he
uri
s
t
i
c
coef
fi
cient) a
r
e res
p
ectively taken
from
BRAM and
ROM
according t
o
the releva
nt a
d
dress.
Fi
gu
re 5.
The
uni
t
of
cal
cul
a
t
i
ons
bl
ock
Aft
e
r
t
h
e c
o
nt
rol
bl
oc
k
whi
c
h i
s
resp
o
n
si
bl
e f
o
r
det
ect
i
n
g
w
h
et
he
r a
n
y
no
de
has
b
een al
rea
d
y
selected or
which a
d
dress
shoul
d
be s
e
lected, it’s tim
e
to sta
r
t the
calculations
stage
to select t
h
e
node
.
Accord
ing
to
fig
u
re 5
,
th
ere sh
ou
ld
b
e
a calcu
latio
n
s
u
n
it fo
r each
an
t so
th
at th
e n
o
d
e
s
selectio
n
op
eratio
n
s
are pe
rform
e
d in parallel with each
othe
r.
After
receivi
ng the desi
red
param
e
ters, the search a
n
d qua
lifying
ope
rat
i
o
ns m
a
inl
y
begi
ns
by
m
u
lt
i
p
l
y
i
ng t
h
e heu
r
i
s
t
i
c
val
u
e by
t
h
e am
ount
o
f
p
h
er
om
one bet
w
een t
h
e
cur
r
ent
n
o
d
e
an
d
t
h
e
o
t
h
e
r no
de which
is b
e
ing
ch
eck
ed
in
term
s
o
f
b
e
co
m
i
n
g
a cand
id
ate. After m
u
ltip
l
y
in
g
th
e
p
h
e
ro
m
o
n
e
b
y
th
e h
e
u
r
istic co
efficien
t, th
e
resu
lting
v
a
l
u
e is co
m
p
ared
with
th
e p
a
rameter o
b
t
ain
e
d
fro
m
th
e
ran
d
o
m
nu
m
b
er ge
nerat
i
n
g u
n
i
t
(whi
ch i
s
c
o
nsi
d
e
r
ed as
a s
e
parat
e
m
odul
e and at
t
e
m
p
t
s
t
o
ge
nerat
e
a r
a
nd
om
num
ber i
n
t
h
e
speci
fi
ed i
n
t
e
rval
by
c
h
an
g
i
ng eac
h cl
oc
k. T
h
e res
u
l
t
i
ng
val
u
e i
s
o
f
ut
m
o
st
im
port
a
nce,
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
An
Area-Op
timized
Ch
i
p
o
f
An
t Co
l
o
n
y
Algorith
m
Design
i
n
Ha
rd
w
a
re Pl
a
tfo
rm Using
…
(
E
. S
haf
i
g
h
Far
d
)
99
5
because the
c
o
m
p
arison si
gnals, 1 or
0, are re
ferred to
t
h
e c
o
ntrol
unit so that t
h
e c
o
ntrol unit func
tion is
base
d
on
t
h
e c
o
m
p
ari
s
on
si
g
n
a
l
(Tabl
e
1
)
.
Tabl
e 1.
T
h
e
c
ont
rol
u
n
i
t
fu
n
c
t
i
on base
d on
t
h
e
com
p
ari
s
on
si
g
n
al
Co
m
p
ar
ison Signal Status
How the next ad
dress is select
ed
in the
m
e
m
o
r
y
block
How the next
node is
selected in th
e
m
u
ltiplexe
r (the
control unit)
0; the value of r
a
ndo
m
nu
m
b
er is higher
.
The checked node
is not
selected a
nd the
count oper
a
tion is
occur
r
e
d and no r
e
set is
per
f
orm
e
d in the runnin
g
r
e
gister
s.
T
h
e count oper
a
tion is occur
r
e
d to check the
next node.
1; the value of r
a
ndo
m
nu
m
b
er is lower.
T
h
e cur
r
e
nt node is selected; and to select
the
next node,
the
shift oper
a
tion fr
o
m
the
cur
r
e
nt addr
ess is per
f
orm
e
d as
m
a
ny
as
the nu
m
b
er
of L
OG (
N
)
;
and the r
e
set
oper
a
tion is occur
r
ed in r
unning r
e
gis
t
er
s.
The overall reset is occurred in the
m
u
ltiplexe
r, and the selector starts to chec
k
node 0.
To i
d
entify a
n
d clari
f
y the
perfor
m
a
n
ce of calcu
latio
ns
un
it and
t
h
e
way o
f
d
e
term
in
i
n
g th
e cost
fu
nct
i
o
n, fi
g
u
r
e 4 has bee
n
m
a
gni
fi
ed t
o
s
h
o
w
cl
earl
y
ho
w o
n
e of t
h
e R
oul
et
t
e
Wheel
ope
rat
i
o
ns o
r
t
h
e cost
fu
nct
i
o
n i
s
pe
r
f
o
r
m
e
d an
d
se
l
ect
ed.
As
sh
o
w
n
i
n
t
h
e
f
o
ll
o
w
i
n
g fi
gu
re (figu
r
e
6
)
, after th
e co
m
p
arison
was
per
f
o
r
m
e
d o
n
c
e
an
d t
h
e
com
p
arat
or
p
r
o
d
u
c
e
d t
h
e
res
u
l
t
a
s
signal 1 (which m
eans the
selection
of c
u
rre
nt
n
o
d
e
), lin
es 1
are selected.
Wh
en
t
h
e m
u
ltip
lex
e
r lin
es
b
e
co
m
e
1
,
th
e cost o
f
selected
no
d
e
is
p
r
o
cessed
along
with the pre
v
ious c
o
sts as the curren
t
fi
nal
cost
an
d i
f
t
h
e out
put
si
g
n
al
of com
p
arator is 0, the lines
0 of
m
u
l
tip
lex
e
rs are selected
an
d
a p
a
rt o
f
th
e R
o
u
l
ette
W
h
eel o
p
e
ration
will b
e
read
y for the n
e
x
t
clo
c
k
;
in
th
is
way
t
h
at
by
s
e
l
ect
i
ng ze
ro
l
i
nes, t
h
e
val
u
e
s
o
f
∑
,
are
cal
cul
a
t
e
d t
o
be
use
d
i
n
t
h
e
pr
oce
ss
of
sel
ect
i
ng t
h
e
n
e
xt
n
o
d
e i
n
t
h
e
ne
xt
cl
oc
ks.
Fig
u
re
6
.
Magn
ificatio
n of t
h
e calcu
latio
n
s
u
n
it
The competenc
e
evaluation
unit
:
At th
is stag
e, after sev
e
ral iteratio
n
s
(d
ep
end
i
ng
on
th
e co
nd
itio
n
o
f
com
p
letion of
the algorithm
)
, the syst
e
m
en
ters the phase
of c
o
m
p
etence ev
aluation. At
this stage, each ant
ent
e
rs t
h
e eval
uat
i
on
phas
e
w
h
i
l
e
i
t
has a co
st
funct
i
o
n l
o
c
a
t
e
d i
n
an n-
bi
t
regi
st
er (
d
epe
ndi
ng
on t
h
e n
u
m
b
er
o
f
nod
es) an
d a
∗
/
2
m
e
m
o
r
y
co
n
t
ain
i
n
g
th
e add
r
esses of selected
nodes. Fi
r
s
tly, thr
oug
h th
e
co
m
p
ariso
n
o
f
an
ts’ co
sts fu
nctio
n
s
, th
e m
i
n
i
m
a
l v
a
lu
e is s
e
lected
; an
d
b
y
selectin
g
th
e lo
west co
st fu
nction,
th
e so
lu
tion
related
to
t
h
e
d
e
si
red an
t en
ters th
e
u
p
d
a
te
p
h
a
se.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
IJECE Vol. 4, No. 6, D
ecem
ber 2014
:
989 – 998
99
6
Fi
gu
re
7.
The
e
v
al
uat
i
o
n
u
n
i
t
Th
e g
l
oba
l
upd
a
t
e un
it:
In
this b
l
o
c
k
,
after
th
e so
l
u
tio
ns av
ailab
l
e in
R
A
M (figu
re 6) are co
m
p
ared
with each
othe
r in term
s of the cost
function, the addresse
s
of the
best
sol
u
tion
(consi
dering the
performance
of t
h
e
best
ant
)
are
sent
t
o
B
r
am
whi
c
h i
n
cl
u
d
es t
h
e p
h
e
rom
one
para
m
e
t
e
r t
o
pe
rf
o
r
m
t
h
e gl
obal
up
dat
e
ope
rat
i
o
ns
on
t
h
e m
e
m
o
ry
usi
n
g
t
h
e
p
h
er
om
one
pa
ram
e
t
e
rs.
4.
EVAL
UATI
O
N
AN
D
A
N
A
L
YSIS
OF T
H
E RES
U
LT
S
In orde
r
t
o
determine
the efficiency of
the
sy
st
em
pro
pos
ed
base
d
o
n
t
h
e
S
O
PC
,
i
t
has
bee
n
sim
u
l
a
t
e
d an
d
sy
nt
hesi
zed
o
n
t
h
e
Vi
rt
ex
7ch
i
p, f
r
o
m
Xi
l
i
nx se
ri
es.
Al
l
p
r
i
v
at
e a
nd
p
u
b
l
i
c
bl
ock
s
ha
v
e
bee
n
written
b
y
VHDL
(VHSIC hardware d
e
sc
ri
p
tio
n
lang
u
a
g
e
). Fo
r t
h
e syn
t
h
e
sis op
eratio
ns, th
e ISE Simu
lato
r
t
ool
avai
l
a
bl
e i
n
t
h
e ISE
Xi
l
i
nx s
o
ft
ware h
a
s been u
s
ed
. H
e
re, t
h
e res
u
l
t
s
of res
o
u
r
ce co
nsum
pt
i
on
obt
ai
ned
fr
om
sy
nt
hesi
zi
ng t
h
e p
r
ese
n
t
e
d m
e
t
hod ar
e st
at
ed. Si
nce t
h
e num
ber of
no
des (
w
i
t
h
res
p
e
c
t
t
o
t
h
e occup
a
ncy
o
f
b
it v
ect
o
r
) an
d
th
e
n
u
m
b
e
r o
f
an
ts (du
e
to
th
e creation
o
f
so
lu
tion
s
p
i
p
e
lin
e)
p
l
ay an
essen
tial ro
le in
th
e
occu
pat
i
o
n a
n
d
use
of
o
n
-c
hi
p
res
o
u
r
ces,
sev
e
ral
t
e
st
s ha
ve been
co
n
duct
e
d by
al
t
e
ri
ng
t
h
e num
ber of no
de
s
(n
) an
d n
u
m
b
er o
f
ants (m
) to sh
o
w
their c
h
an
ges e
ff
ects
on t
h
e increa
se
and
decrea
se of
on-c
hip res
o
urces
con
s
um
pt
i
on.
For t
h
i
s
p
u
r
p
o
s
e, t
h
e sy
nt
hes
i
s operat
i
o
ns h
a
ve bee
n
co
nd
uct
e
d i
n
a fi
xe
d n
u
m
b
er of 6
4
n
ode
s
wi
t
h
t
h
ree di
f
f
e
rent
pi
pel
i
n
e
s
.
Fi
g
u
r
es 8-
1
0
sho
w
t
h
e re
su
lts ob
tain
ed from
th
e reg
r
essi
o
n
fun
c
tio
n. Tab
l
e 2
sh
ow
s a co
m
p
ar
ison
b
e
tw
een th
e r
e
su
lts o
b
t
ain
e
d
fr
o
m
th
e p
r
esen
ted
m
e
t
h
od
and
a si
m
i
lar
w
o
r
k
condu
cted
by
Dr
. Sc
heue
r
m
ann’s
w
o
r
k
gr
ou
p;
an
d Ta
bl
e
3 sh
o
w
s t
h
e c
o
m
p
ari
s
on
o
f
r
e
so
urces
nee
d
e
d
by
t
h
e m
e
t
h
o
d
o
f
syste
m
-o
n
-
ch
i
p
with
ex
tern
al m
e
m
o
ry an
d
24
-b
it v
ect
o
r
fo
r th
e
h
e
uristic co
efficien
t
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
An
Area-Op
timized
Ch
i
p
o
f
An
t Co
l
o
n
y
Algorith
m
Design
i
n
Ha
rd
w
a
re Pl
a
tfo
rm Using
…
(
E
. S
haf
i
g
h
Far
d
)
99
7
Fi
gu
re 8.
The
r
e
sul
t
s
o
f
reg
r
es
si
on
f
unct
i
o
n
f
o
r
est
i
m
a
t
i
ng t
h
e
num
ber
of
r
e
gi
st
ers i
n
6
4
Fi
gu
re
9.
The
r
e
sul
t
s
o
f
reg
r
es
si
on
f
unct
i
o
n
f
o
r
est
i
m
a
t
i
ng t
h
e
num
ber
of
LUT i
n
6
4
Fi
gu
re
1
0
. T
h
e
res
u
l
t
s
o
f
reg
r
essi
on
f
u
nct
i
o
n
f
o
r e
s
t
i
m
a
t
i
ng t
h
e n
u
m
b
er
of
m
e
m
o
ry
bl
oc
k
s
i
n
6
4
y
=
374.32x
+
855.5
R²
=
0.97
0
2000
4000
6000
05
1
0
Numbers
of
LUTs
Numvers
of
Ants
changing
of
lUT
s
with
changing
number
of
An
ts
Series1
y
=
‐
0.3571x
+
4
R²
=
0.8929
0
1
2
3
4
02468
1
0
Numbers
of
Brams
Numbers
of
Ants
changing
of
Br
am
with
changing
Number
s
of
An
ts
Series1
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
IJECE Vol. 4, No. 6, D
ecem
ber 2014
:
989 – 998
99
8
Tabl
e
2. T
h
e
c
o
m
p
ari
s
on
o
f
r
e
so
urces
use
d
by
t
h
e
p
r
esent
e
d m
e
t
hod a
n
d t
h
e
one
s
by
D
r
.
Sche
uerm
ann’
s
w
o
r
kgr
oup
Bit
Vector
T
h
e nu
m
b
er
of BRAM
s
with n=64
m=
t
h
e
n
u
mb
e
r
o
f
a
n
t
s
T
h
e nu
m
b
er
of L
U
T
with n=64
m=
t
h
e
n
u
mb
e
r
o
f
a
n
t
s
T
h
e nu
m
b
er
of r
e
g
i
ster
s with
n=64
m=
t
h
e
n
u
mb
e
r
o
f
a
n
t
s
Resour
ces
T
h
e m
e
thod
6-
bit BRAM
s
=2.
4802
m
+
1.
5297
L
U
T
s
=1516.m
+
97.
2749
RE
Gs=542.
244
m
+
244.
76
4
Population based o
n
the ant colony
optim
ization on
FPGA.
8-
bit
BRAM
s
= -
0
.
3571
m
+
4
L
U
T
s
=
374.
32
m
+
855.
5
RE
Gs=178.
29
m
+ 349
T
h
e
pr
oposed
wor
k
Tabl
e
3. T
h
e
c
o
m
p
ari
s
on
o
f
r
e
so
urces
nee
d
e
d
by
t
h
e m
e
t
h
o
d
of
sy
st
em
-on-chi
p
wi
t
h
e
x
t
e
rnal
m
e
m
o
ry
and
2
4
-b
it v
ector
fo
r th
e
he
uristic coe
fficient
IO
Th
e n
u
m
b
e
r
o
f
LU
T
M=1
T
h
e nu
m
b
er
of r
e
g
i
ster
s
M=1
Resour
ces
T
h
e m
e
thod
26
4511
434
Ar
chitect for
high
speed ant colony
optim
ization.
25
452
150
T
h
e pr
oposed wor
k
5.
CO
NCL
USI
O
N
AN
D F
U
T
U
RE W
O
R
K
S
In t
h
i
s
pa
per
,
t
o
real
i
ze t
h
e ant
col
o
ny
opt
i
m
i
zat
i
on al
gori
t
hm
, a
m
odel
i
ng
based
on t
h
e sy
st
em
-on-
ch
ip
with
address o
r
ien
t
atio
n was pro
p
o
s
ed, wh
ich
is
applicable as a real-tim
e optim
izer. T
h
is arc
h
itecture
u
s
es a set
o
f
parallel stru
ctures and
p
i
p
e
lin
es th
at en
ab
le it to
fu
lfill th
e op
ti
m
i
zatio
n
o
f
v
a
ri
o
u
s
prob
lem
s
b
y
th
e an
t co
lon
y
alg
o
rith
m
.
Th
e p
r
esen
ted
meth
od
is en
tirely hardwa
re a
nd t
h
e a
r
ea us
ed
by the c
h
ip shows
si
gni
fi
ca
nt
im
pro
v
em
ent
s
as
m
u
ch as 1.3 t
i
m
es great
er t
h
a
n
t
h
e ot
he
r si
m
i
l
a
r hard
wa
re m
e
t
hods
. As t
h
e fut
u
re
wo
rk
s, i
t
can b
e
poi
nt
e
d
t
o
m
a
ki
n
g
t
h
e m
e
t
h
od scal
a
b
l
e
wh
i
c
h can be c
o
n
duct
e
d usi
ng t
h
e net
w
o
r
k
-
on
-ch
i
p
t
echn
o
l
o
gy
. Th
e ot
her i
n
t
e
re
st
i
ng w
o
r
k
can
b
e
pro
v
i
d
i
n
g a har
d
ware
-so
f
t
w
are c
o
m
b
i
n
at
i
on m
e
t
hod ba
sed o
n
th
e pro
p
o
s
ed
hardware core t
o
p
r
eserv
e
th
e
flex
ib
ility o
f
the alg
o
rith
m
m
o
re.
REFERE
NC
ES
[1]
Dori
go M.
Optimi
z
a
t
i
o
n,
L
e
a
r
ning a
nd na
t
u
ra
l
a
l
gori
t
h
ms,
Phd,
thesis
, Politecb
ico di Milano
,
Italy
1992.
[2]
Dorigo M.
Parallel ant s
y
stem: an e
xper
i
mental s
t
ud
y
,
unpub
lished manuscript,
cited by M. Dorigo
1993.
[3]
Dorigo M,
Di Caro.
G
a
mbardella,
Ant
a
l
gorithm
s
for discr
e
te
opt
im
ization
,
Artif
i
c
ial
Life
5 (2)
,
1
999. 137–172
[4]
Pe
de
monte
M,
Ne
sma
c
hnow S,
Ca
nc
e
l
a
H.
“Survey
on pa
ra
lle
l
a
n
t c
o
lony
optimiz
a
tion”
,
App
l
ied Soft computing
journal 2011
.
[5]
D
e
l
i
s
l
e
P
,
G
r
a
v
e
l
M
,
K
r
a
j
e
c
k
i
M
,
G
a
g
n
é
C
,
P
r
i
c
e
W
.
“Comparing parallelization
of
an ACO: message passing vs.
s
h
ared m
e
m
o
ry”
,
in:
Proceeding
s of the 2nd International
Workshop on Hybrid
Metaheuristics,
Lecture Notes in
Computer Scien
ce vo
l. 3636, 20
05. 1–11
.
[6]
Fu J, LEI L, Zh
ou G. “Parallel
ant co
lon
y
optimizati
on
algorithm with gpu accelerati
on based
on all-
in-roulette
selec
tion”
,
in
Pr
oceed
ings
of the
3
rd
internationa
l workshop on advan
ced computational
in
tellig
ence
, 2010
, pp 26
0-
264
[7]
Scheuermann B
,
Janson S, Mi
ddendorf M. “
H
ardware-oriented
ant
colon
y
optim
izat
ion”
,
Journal of Systems
Ar
chit
ectur
e
53
(7) 2007. 386–4
02.
[8]
Ghey
sar
i
K, Kho
e
i A, Mashoufi
B. “High speed
ant co
lon
y
optim
ization CMOS Chip”,
in
Journal
of Exp
e
rt Systems
with App
l
i
c
ation
s
, Elsev
i
er
scien
ce, Spring 2011
.
[9]
Yos
h
ikawa M
,
T
e
rai
H. “
A
rc
hitecture
for
high
–speed ant colon
y
optimization .
pr
oceed
ings
”
,
of I
EEE In
ter
nat
ion
a
l
Conference on
information Reuse and
integratio
n
,las Vegas
,
NV,2007. 1-5
.
[10]
Yos
h
ikawa M
and
Tera
i H
,
Hardwar
e
-ori
ented
ant
co
lo
n
y
op
tim
iz
atio
n consider
ing
intensifi
c
a
tion
an
d
diversification in
:
Bednor
z, W.
ed
itor.
Ad
vances
in
greedy algorith
m
s
, I-Tech, 2008
. 359-68
.
[11]
Merkle D,
Mid
d
endorf M.
“
F
ast ant
colon
y
o
p
tim
izat
ion on
r
untime reconfig
ur
able processor array
s
”,
Ge
ne
tic
Programming and Evo
l
vable M
a
chines
3
(4) 20
02. 345–361
[12]
Bai H, OuYang D, Li X, He
L,
Yu H. “Max-
m
in ant s
y
stem on gpu with cuda”,
in:
Proceedings
of the 2009 Fou
r
th
International C
onference on
In
novative Compu
ting
, Informatio
n and Con
t
rol, I
EEE Computer
Society
,
2009
. p
p
.
801–804.
[13]
Duan H,
Yaxiang Yu,
Jie Zou,
Xing Feng. “Ant Colon
y
Optimiza
tion
algorithm desig
n
and its FPGA
implementation”,
IEEE International Sy
mposium
on Intelligen
t Signal Proc
ess and Communicatio
n Systems 2012
.
[14]
Martin P,”an an
aly
s
is of rando
m numbe
r generators for a hard
ware implem
entation of g
e
netic
programming using
FPGA and Handek-C”, IN Proc.Geet
ic
and Evo
l
utionar
y
Computation
Conf, July
2002, pp
. 837-8
44
Evaluation Warning : The document was created with Spire.PDF for Python.