elec onics
A icle
FPGA Accele a o o G adien Boos ing Decision T ees
Ad ián Alcolea 1,* and Ja ie Resano 2


Ci a ion: Alcolea, A.; Resano, J. FPGA
Accele a o o G adien Boos ing
Decision T ees. Elec onics 2021,10,
314. h ps://doi.o g/10.3390/
elec onics10030314
Academic Edi o : Joo-Young Kim
Recei ed: 31 Decembe 2020
Accep ed: 26 Janua y 2021
Published: 29 Janua y 2021
Publishe ’s No e: MDPI s ays neu-
al wi h ega d o ju isdic ional clai-
ms in published maps and ins i u io-
nal a ilia ions.
Copy igh : © 2021 by he au ho s. Li-
censee MDPI, Basel, Swi ze land.
This a icle is an open access a icle
dis ibu ed unde he e ms and con-
di ions o he C ea i e Commons A -
ibu ion (CC BY) license (h ps://
c ea i ecommons.o g/licenses/by/
4.0/).
1Depa men o Compu e Science and Sys ems Enginee ing (DIIS), Uni e si y o Za agoza, c/Ma ia de
Luna 1, 50018 Za agoza, Spain
2Enginee ing Resea ch Ins i u e o A agon (I3A), Uni e si y o Za agoza, c/Ma iano Esquillo SN,
50018 Za agoza, Spain; j esano@uniza .es
*Co espondence: alcolea@uniza .es
Abs ac :
A decision ee is a well-known machine lea ning echnique. Recen ly hei popula i y
has inc eased due o he powe ul G adien Boos ing ensemble me hod ha allows o g adually
inc easing accu acy a he cos o execu ing a la ge numbe o decision ees. In his pape we
p esen an accele a o designed o op imize he execu ion o hese ees while educing he ene gy
consump ion. We ha e implemen ed i in an FPGA o embedded sys ems, and we ha e es ed i
wi h a ele an case-s udy: pixel classi ica ion o hype spec al images. In ou expe imen s wi h
di e en images ou accele a o can p ocess he hype spec al images a he same speed a which
hey a e gene a ed by he hype spec al senso s. Compa ed o a high-pe o mance p ocesso unning
op imized so wa e, on a e age ou design is wice as as and consumes 72 imes less ene gy.
Compa ed o an embedded p ocesso , i is 30 imes as e and consumes 23 imes less ene gy.
Keywo ds: decision ees; GBDT; FPGA; ene gy e iciency
1. In oduc ion
Decision ees a e a ligh and e icien machine lea ning echnique ha ha e p o ed
hei e ec i eness in se e al classi ica ion p oblems. In he con ex o embedded sys ems,
ene gy e iciency is as much impo an as accu acy, so i is necessa y o sea ch o e icien
algo i hms liable o be accele a ed. This makes he decision ees a pe ec a ge o de elop
an FPGA accele a o .
A single decision ee is equen ly no e y accu a e o complica ed asks bu , hanks
o ensemble me hods, i is possible o combine se e al ees in o de o deal wi h complex
p oblems. G adien Boos ing Decision T ees (GBDT) [
1
] is an ensemble me hod ha
allows o imp o e he accu acy g adually adding new ees in each i e a ion ha imp o e
he esul o he p e ious ones. Con en ional implemen a ions o GBDT su e om
poo scaling o la ge da ase s o a la ge numbe o ea u es, bu ecen ly some e icien
implemen a ions ha e o e come his d awback such as XCGBoos [
2
], Ca Boos [
3
], o
Ligh GBM [
4
]. Fo ins ance, Ligh GBM is a highly e icien open-sou ce GBDT-based
amewo k ha o e s up o 20 imes highe pe o mance o e con en ional GBDT. Wi h
he suppo o Ligh GBM, GBDTs a e cu en ly conside ed one o he mos powe ul
machine lea ning models due o i s e iciency and accu acy. Fo example, ecen ly hey
ha e been used o many winning solu ions in se e al machine lea ning compe i ions [
5
].
They can be used o e y di e en p oblems. Fo ins ance, hey ha e been success ully
used o p oduce accu a e o ecas s o he COVID-19 e olu ion, and o iden i y ac o s
ha in luence i s ansmission a e [
6
]; o de ec aud om cus ome ansac ions [
7
]; o
es ima e majo ai pollu an s isks o human heal h [
8
] using sa elli e-based ae osol op ical
dep h; o o classi y he GPS signal ecep ion in o de o imp o e i s accu acy [
9
]. Mo eo e ,
a ecen publica ion [
10
] analyzed di e en machine lea ning me hods o image p ocessing
in emo e sys ems, ocusing on on-boa d p ocessing, which equi es bo h pe o mance and
low-powe . In his wo k he au ho s iden i ied ha GBDTs p esen a e y in e es ing ade-
o be ween he use o compu a ional and ha dwa e esou ces and he ob ained accu acy.
Elec onics 2021,10, 314. h ps://doi.o g/10.3390/elec onics10030314 h ps://www.mdpi.com/jou nal/elec onics
Elec onics 2021,10, 314 2 o 15
Thei accu acy esul s we e close o hose ob ained wi h con olu ional neu al ne wo ks,
which cu en ly is he mos accu a e me hod, while ca ying ou one o de o magni ude
less compu a ional ope a ions. Mo eo e , mos o hei ope a ions du ing in e ence a e
in ege compa isons, which can be e icien ly calcula ed e en by e y simple low-powe
p ocesso s, and can be easily accele a ed by FPGAs. Fo ha eason hey ep esen a good
op ion o embedded sys em.
In his pape we p esen an accele a o o G adien Boos ing Decision T ees (GBDT)
ha can execu e he GBDT ained wi h Ligh GBM. We ha e c ea ed a eposi o y in
which we include he GBDT models used, and ou sou ce codes [
11
]. Ou accele a o
has been designed o embedded sys ems, whe e ha dwa e esou ces and powe budge
a e e y limi ed. Hence, ou p ima y goal is e iciency. The egis e - ans e le el (RTL)
design o ou accele a o has been w i en in VHDL , and, o demons a e i s po en ial,
we ha e implemen ed i in a low-cos FPGA e alua ion boa d (ZedBoa d) [
12
], which
includes an FPGA o embedded sys ems, and we ha e used ou implemen a ion o he
ele an case s udy analyzed in [
10
]: pixel classi ica ion o hype spec al images wi h
he objec i e o p ocessing he da a a un- ime. We ha e measu ed he execu ion ime
and powe consump ion o ou accele a o and we ha e iden i ied ha ou design can
be used o p ocess complex GBDT models e en when using a small FPGA. In ou case
s udy, ou accele a o can p ocess he hype spec al in o ma ion a he same speed a which
he hype spec al senso s gene a e i , and he dynamic ene gy consump ion due o he
execu ion is an o de o magni ude less in bo h cases, compa ed o a high pe o mance
CPU and compa ed o an embedded sys em CPU. Hence i could be used o on-boa d
p ocessing in emo e sensing de ices.
2. Rela ed Wo k
Se e al p e ious wo ks ha e a ge ed FPGA accele a ion o Decision T ees. Re e -
ence [
13
] ocuses on he aining p ocesses. In ou case we assume ha aining is ca ied
ou o line and we wan o ocus on in e ence, which will be compu ed online. Re e -
ence [
14
] p esen ed a cus om pipeline a chi ec u e which demons a ed he po en ial o
an accele a o o decision ees. Howe e hey do no suppo GBDT and hey apply
hei echniques only o simple case s udies. Re e ence [
15
] p oposes o use a high-le el
syn hesis app oach o design an FPGA accele a o . They ocus on Random Fo es , which
is an ensemble echnique ha calcula es he a e age alue o se e al ees ained wi h
di e en inpu da a o gene a e a mo e accu a e and obus inal ou pu . We ha e decided
o ocus on GBDT ins ead o Random Fo es since ecen ly GBDT ha e demons a ed an
eno mous po en ial [
5
]. Mo eo e , [
10
] compa ed he esul s o Random Fo es and GBDT
and he esul s show ha GBDT p o ided be e accu acy while using smalle models,
hence we belie e ha i is a be e app oach o embedded sys ems. Ano he di e ence
is ha we ha e designed a cus om egis e - ans e le el (RTL) a chi ec u e ins ead o
using a high-le el syn hesis ha will au oma ically gene a e he RTL design om a C-code.
High-le el syn hesis is e y in e es ing o po abili y, and o educe he design cycle,
bu wi h ou RTL design we can ully design he inal a chi ec u e and explo e se e al
ad anced op imiza ion op ions. Re e ence [
16
] is ano he wo k ha analyzes he bene i s
o implemen ing Random Fo es on FPGAs. They compa e he e ec i eness o FPGAs,
GP-GPUs, and mul i-co e CPUs o andom o es classi ie s. They conclude ha FPGAs
p o ide he highes pe o mance solu ion, bu hey do no scale due o he size o he
o es . In his sense, as explained be o e, GBDT models equi e ewe ees o ob ain he
same accu acy, so i is a mo e sui able model o FPGAs. Re e ence [
17
] p oposes o use
FPGAs o accele a e he execu ion o decision ees used in he Mic oso Kinec ision
pipeline o ecognize human body pa s and ges u es. They use a high pe o mance FPGA,
and ob ain e y good esul s o decision ess o ganized as andom o es . Howe e ,
hey iden i y ha hei design canno be used in low-powe FPGAs due o i s memo y
equi emen s. Re e ence [
18
] is a e y ecen wo k ha p esen s an algo i hm ha p o-
duces compac and almos equi alen ep esen a ions o he o iginal inpu decision ees
Elec onics 2021,10, 314 3 o 15
by h eshold compac ion. The main idea is o me ge simila h esholds o educe he
numbe o di e en h esholds needed, and s o e hose alues as ha d-wi ed logic. Wi h
his app oach he size o he ees can be educed. This echnique is o hogonal o ou
app oach and can be bene icial o ou design since i educes he size o he ees, which
simpli ies i s s o age in embedded sys ems. Re e ence [
19
] is ano he ecen wo k ha
analyzes he bene i s o FPGA accele a ion o G adien -boos ed decision ees. In his
case hey e alua e he se ices p o ided by Amazon cloud, which include he access o
high-pe o mance FPGAs ha can be used h ough high-le el in e aces. The e o e, his
wo k is complemen a y o ou s, as i ocuses on high-pe o mance cloud se e s while we
ocus on embedded sys ems.
In summa y, he p e ious wo ks indica e he po en ial o FPGAs o he execu ion
o decision ees. Mos o hese wo ks ocus on Random Fo es , and hey ei he only
implemen small sys ems, o hey need o use high pe o mance FPGAs. The e o e, i is
necessa y o imp o e he scalabili y o hese solu ions in o de o use hem in embedded
sys ems. In his pape we p esen a GBDT-based accele a o capable o sol ing e y
complex models e en in a ela i ely small FPGA. GBDTs ha e achie ed excellen esul s
in a ious machine lea ning p oblems, and hei cha ac e is ics a e e y in e es ing o
embedded sys ems. The e o e, we ha e designed a ha dwa e accele a o o FPGAs wi h
he objec i e o unning complex models based on GBDT in low-cos and low-ene gy
consump ion sys ems. To demons a e he po en ial o ou design we ha e implemen ed
an equi alen solu ion o he mos complex GBDT model p oposed in [
10
], which used
GPUs o execu e he models, on a Xilinx Zedboa d FPGA which is a small model o ien ed
o embedded sys ems.
3. G adien Boos ing Decision T ees
A Decision T ee is a decision algo i hm ha uses a ee-like model o gene a e i s
ou pu . I can be seen as a way o display an algo i hm ha only con ains condi ional
con ol s a emen s. In each ee he decision is based on a se ies o compa isons connec ed
be ween hem as in a bina y ee s uc u e. Each in e nal node ep esen s a compa ison used
o decide he ollowing node, and each lea node con ains he esul o he p edic ion [
20
].
When decision ees a e used o classi ica ion p oblems each lea o he ee is labeled wi h
he p edic ed class o wi h a p obabili y o a gi en class o a p obabili y dis ibu ion o e
all he classes. Figu e 1shows he ope a ion o a Decision T ee on a se ies o ea u e inpu s
wi h a oy example. In he i s place, his ee akes ea u e 4 o he inpu and compa es i s
alue wi h 20; as he inpu alue is lowe i con inues on he le child, and keeps wi h he
same p ocedu e un il i eaches he lea wi h 0.3 as ou pu alue.
Fea u e: 4
Cmp. alue: 20
Fea u e: 0
Cmp. alue: 10 0.7
0.3
<=
<=
>
>
Fea u e: 3
Cmp. alue: 15
0.3 0.5
<= >
25
30
15
10
15
25
0
1
2
3
4
5
Pixel:
In e ence s eps:
Pixel(4) = 15 <= 20 --> le child
Pixel(0) = 25 > 10 --> igh child
Pixel(3) = 10 <= 15 --> le child
Figu e 1. Decision T ee example.
One o he bene i s o using Decision T ees o e o he echniques is ha hey do
no need any inpu p ep ocessing such as da a no maliza ion, scaling o cen e ing. They
wo k wi h he inpu da a as i is [
20
]. The eason is ha ea u es a e ne e mixed. As
Elec onics 2021,10, 314 4 o 15
can be seen in Figu e 1, in each compa ison he ees compa e he alue o an inpu
ea u e wi h ano he alue o he same ea u e. Hence, se e al ea u es can ha e di e en
scales. In o he Machine Lea ning models, ea u es a e mixed o gene a e a single alue,
he e o e, i hei alues belong o di e en o de s o magni ude, some ea u es will ini ially
domina e he esul . This can be compensa ed du ing he aining p ocess, bu in gene al
no maliza ion will be needed o speed up aining and imp o e he esul s. A oiding
no maliza ion educes he un- ime compu a ions needed, hence i is a e y in e es ing
ea u e o embedded sys ems.
Besides, he size o he inpu da a does no di ec ly a ec he size o he model, o i s
compu a ions. Hence, dimensionali y educ ion echniques such as P incipal Componen
Analysis a e no needed o educe he model size. Again, his is e y in e es ing o
embedded sys ems since i subs an ially educes he amoun o calcula ion needed a
in e ence. Du ing aining he mos meaning ul ea u es a e selec ed and used o he
compa isons in he ee. Hence he ea u es ha con ain mo e in o ma ion will be used
mo e equen ly o he compa ison, whe he hose ha do no p o ide use ul in o ma ion
o he classi ica ion p oblem will simply be igno ed. This is an in e es ing p ope y o his
algo i hm since, based on he same decisions made du ing aining o choose ea u es, we
can easily de e mine he ea u e impo ance. This means ha Decision T ees can be used
o ind ou which ea u es p o ide mo e meaning ul in o ma ion, and his can be used o
ain e en smalle models keeping mos o he in o ma ion wi h less memo y impac .
Ne e heless, a single Decision T ee does no p o ide accu a e esul s o complex
classi ica ion asks. The solu ion is o use an ensemble me hod ha combines he esul s o
se e al ees in o de o imp o e he accu acy le els. G adien Boos ing is an ensemble
me hod ha combines he esul s o di e en p edic o s in such a way ha each ee
a emp s o imp o e he esul s o he p e ious ones. Speci ically, he g adien boos ing
me hod consis s in aining p edic o s sequen ially so each new i e a ion y o co ec he
esidual e o gene a ed in he p e ious one. Tha is, each p edic o is ained o co ec he
esidual e o o i s p edecesso . Once he ees a e ained, hey can be used o p edic ion
by simply adding he esul s o all he ees [20].
The GBDT model also allows designe s o ade o accu acy o compu a ion and
model size. Fo example, i a GBDT is ained o 100 i e a ions, i will gene a e 100 ees
o each class. A e wa ds, he designe can decide whe he o use all o hem, o o disca d
he inal ones. I is possible o ind simila ade-o s wi h o he ML models, o ins ance
educing he numbe o con olu ional laye s in a con olu ional neu al ne wo k (CNN).
Howe e , in ha case, each possible design mus be ained again, whe eas in GBDT only
one ain is needed, and a e wa ds he designe can simply e alua e he esul s using
di e en numbe o ees and gene a e a Pa e o cu e wi h he di e en ade-o s. Again,
his is e y sui able o embedded sys ems, as we can adjus he model size acco ding o
he a ailable memo y esou ces, o he execu ion ime and powe consump ion es ic ions.
In e ms o compu a ion, mos o he machine lea ning algo i hms need a signi ican
amoun o loa ing poin ope a ions o he in e ence p ocess. Fo ins ance, CNNs and
mul ilaye pe cep ons (MLPs) a e based on loa ing-poin mul iply-accumula e ope a ions.
By con as , calcula ing he ou pu o a ee only in ol es ca ying ou some compa isons. I
he inpu da a a e in ege s, as is he case wi h he pixels in an image, all hese compa isons
will only use in ege s, which g ea ly educes he compu a ional load. The only loa ing
poin ope a ion will be he accumula ion o he ou pu s o each ee, in hose cases whe e
he inal ou pu is a p obabili y ep esen ed in loa ing poin . Hence, he e will be a single
loa ing poin -addi ion o each ee. In embedded sys ems hese addi ions can be eplaced
by ope a ions in ixed p ecision and he whole model can be execu ed e en in sys ems ha
do no ha e loa ing poin uni s.
4. Design A chi ec u e
Ligh GBM ollows a one- s-all s a egy o classi ica ion p oblems ha consis s in
aining a di e en es ima o (i.e., a se o ees) o each class, so each one o hem p edic s
Elec onics 2021,10, 314 5 o 15
he p obabili y o belonging o ha class. Wi h his app oach each class has hei own
p i a e ees, and he p obabili y o belonging o a gi en class is ob ained by adding he
esul s o i s ees, as shown in Figu e 2.
... ...
+ +
T ees o Class 0 T ees o Class N
Class 0 pe cen age Class N pe cen age
...
Figu e 2. G adien Boos ing Decision T ees (GBDT) esul s accumula ion wi h one- s-all app oach.
Hence, du ing in e ence, each class is independen om he o he s, and he ees o
each class can be analyzed in pa allel. Ou accele a o akes ad an age o his pa allelism
by including one speci ic module o each class.
To design an e icien accele a o , i is essen ial o op imize memo y esou ces. Ou
goal is o s o e he ees in he on-chip memo y esou ces o he FPGA o minimize da a
ans e s wi h he ex e nal memo y. Howe e hose esou ces a e e y limi ed, so a key
poin o he design is o op imize he o ma used o s o e he ees in o de o educe hei
memo y equi emen s.
All he ees o a class a e mapped in o i s ees_nodes RAM memo y, which is local o
he class module. Figu e 3p esen he ep esen a ion ha we ha e selec ed o s o e he ee
s uc u e on his memo y. Ou objec i e is o include all he in o ma ion o each node in a
32-bi wo d. Since we use gene ic pa ame e s in ou code, his wo d size can be enla ged o
educed as needed. Bu in ou expe imen s we ha e obse ed ha 32 bi s p o ides a good
ade-o be ween he accu acy o ep esen he ees and he s o age equi emen s. These
32 bi s ollow wo di e en o ma s aking in o accoun whe he hey a e lea nodes o no .
The o ma o non-lea includes ou ields. The i s and he second ield s o e he
in o ma ion needed o ca y ou he compa ison, ha is, which inpu will be used (8 bi ),
and wi h which alue i will be compa ed (16 bi ). Then we need o s o e he add esses o
he child nodes. As we only ha e 8 bi s emaining, i is no possible o s o e i s absolu e
add esses. In ac , wi h he size o he memo ies ha we a e using, we would need almos
all o he 32-bi s o s o e ha in o ma ion. We ha e sol ed his issue wi h wo solu ions.
Fi s , in he ees_nodes memo y, nodes a e s o ed using he p e-o de a e sal me hod,
ha is, he le child o a non-lea node is always alloca ed in he ollowing memo y posi ion.
Wi h his app oach he add ess o he le child does no need o be s o ed, since i can be
ob ained adding one o he cu en add ess. Hence, we only ha e o s o e he add ess o
he igh child. Second, ins ead o s o ing he absolu e add ess o he igh child, we s o e a
ela i e add ess ha indica es i s dis ance wi h he cu en add ess. This ela i e dis ance
is s o ed in a 7-bi ield. Wi h his app oach he maximum dep h o a ee is 128. This is
mo e han enough o all he ees ha we ha e analyzed, since GBDT does no ely on
e y la ge ees, bu in using many o hem. Finally, we ha e included a lag in he less
signi ican bi o each node: This lag de e mines whe he i is a lea node o no .
In he case o he lea nodes, he 32-bi s memo y wo d includes ou ields. A 16-bi s
ield s o es he ou pu o he h ee. The nex 14-bi s a e used o s o e he add ess o he nex

Elec onics 2021,10, 314 6 o 15
ee. In ou expe imen s 14 bi s we e enough o he absolu e add esses. The o iginal ou pu
o he Ligh GBM GBDTs is a 32-bi loa ing poin . Howe e , using a 16-bi s ixed-poin
ep esen a ion we ob ain simila accu acy in ou expe imen s. In any case, i needed, i is
possible o use mo e bi s o he ou pu wi hou inc easing he size o he memo y wo d
by using ela i e add esses o he @nex _ ee ield ins ead o absolu e add esses. The las
wo bi s a e wo lags ha iden i y whe he his is he las ee in he class, and whe he he
node is a lea o no .
31
31
24 23 8 7 1 0
01216 15- -
- - -
@_ ea u e cmp_ alue el@_ igh _child
lea _ alue @_nex _ ee
is_lea
is_las _ ee
is_lea
Lea node ep esen a ion
Non-lea node ep esen a ion
Figu e 3. Node ep esen a ion.
Figu e 4p esen s a simple example in which wo ees o a class a e s o ed. As can be
seen in he igu e, he oo node o he i s ee is s o ed in add ess 0. Then, he en i e ee
s uc u e co esponding o i s le child is s o ed, ollowing hese same ules ecu si ely, and
inally he igh child is s o ed in he las place. The bi s co esponding o el@_ igh _child
ield s o e he ela i e jump o i s igh child. All he lea nodes o he i s ee indica e
ha he nex ee begins in add ess 5. Finally, he lea nodes o he second ee indica e ha
he e a e no mo e ees o p ocess. This simple example includes 8 nodes. I we execu e i
in ou a chi ec u e we will isi ou o i e o hese nodes, i depends on he esul o he
i s compa ison, and we will need app oxima ely one clock cycle o p ocess each node.
In la ge ees, he numbe o isi ed nodes will be much lowe han he numbe o o al
nodes, and he execu ion ime will emain app oxima ely one cycle pe isi ed node.
Fea u e: 2
Cmp. alue: 85
Fea u e: 106
Cmp. alue: 42
Fea u e: 15
Cmp. alue: 34
0.7
0.3 0.5
0.05 -0.05
<=
<=
<=
>
>
>
0
2
85
4
0
1
106
42 2
0
2
0.3
5
0
1
3
0.5
5
0
1
4
0.7
5
0
1
5
15
34
2
0
6
0.05
- 1 1
7
-0.05
- 1 1
@
31 - 24
23 - 16
15 - 8
7 - 2
1
0
Figu e 4. T ees ep esen a ion example.
Figu e 5depic s he in e nal design o one o he modules ha execu e he ees o a
class. The design includes he p e iously desc ibed ees_nodes RAM memo y, a egis e ,
Elec onics 2021,10, 314 7 o 15
@_las _node, ha is used o s o e he add ess o he las isi ed node, and he logic ha
ca ies ou he compa isons, compu e he nex node o isi , and accumula e he esul s o
he ees.
node
ees_nodes
@_las _node
el@_ igh _child
@_ ea u e
cmp_ alue
@_nex _ ee
@_node
+
1
FEATURES ea u e
<=
+ esul RESULT
lea _ alue
is_las _ ee
is_lea
REG
REG
RAM
FINISH
6b
16b
8b
16b
14b
16b
14b
...
32b
32b
Figu e 5. Class diag am.
In his design he @_ ea u e ield o non-lea nodes is used o selec one ea u e among
all he inpu ea u es o he sys em. The selec ed ea u e is compa ed wi h he cmp_ alue
ield. I he alue o he ea u e is less o equal han he cmp_ alue, he le child o he
non-lea node is selec ed. To his end, we add 1 o he @_las _node. O he wise, we add
he el@_ igh _child o selec he igh child. This will gene a e he @_node ha will be
used o add ess he ees_nodes RAM memo y in case ha he cu en node is a non-lea
(is_lea alue is 0). I he cu en node is a lea (is_lea alue is 1), and his is no he las
ee (is_las _ ee alue is 0), he selec ed alue o add ess he ees_nodes RAM memo y
will be he @_nex _ ee ield o he lea node. On e e y lea node, he esul egis e will
accumula e he lea _ alue ield o he p e ious esul alue.
Acco ding o he selec ed memo y ep esen a ion o he nodes, he maximum size
o he ees_nodes RAM will be 2
14
wo ds, as we dedica e 14 bi s o he @_nex _ ee, and
he heo e ical maximum numbe o nodes o he same ee will be 2
6
due o he size o
he ela i e jump el@_ igh _child. Rega ding he size o he RAM, we could add ess any
numbe o ees jus making he @_nex _ ee a ela i e add ess om he cu en node by
adding i o @_las _node, ne e heless he cu en size is e en bigge han ou needs. In
ou design we dedica e 8 BRAMs o 32 Kb o he ees o each class, which is 8192 wo ds o
32 bi s, so we a e ac ually using he 13 less signi ican o he 14 bi s a ailable o add ess he
ees_nodes RAM. Rega ding he numbe o nodes o each ee, his is only a heo e ical
limi due o he ela i e jump, which ac ually a ec s only he le side o each node, ha
is, he le side o each node o he ee can only ha e 63 nodes, so we could each he
igh child in a p e-o de a e sal. In any case, he maximum numbe o nodes o ou
ees is 61 and he a e age is be ween 7 and 22 depending on he da ase , so his is no a
p oblem ei he .
Once we ecei e he ea u es o one pixel, we only need o wai un il e e y class
module has inished and hen check he ou pu o he a gmax module, which selec s he
Elec onics 2021,10, 314 8 o 15
numbe o he class wi h he highe esul . Figu e 6depic s a simpli ied design o he
accele a o showing his beha io , whe e we omi ed he con ol lines and he managemen
o he communica ions.
 FINISH ea u es
class 0
class N - 1
finish
finish ...
...
a gmax
... ...
REG
 PRED
esul
esul
Figu e 6. Accele a o design.
This design can p ocess a node pe class in each clock cycle. Howe e , in ou expe -
imen s, i we implemen a sys em ha uses mos o he on-chip memo y esou ces, he
place& ou ing p ocess becomes complex and he clock equency is jus 55 MHz. This
can be sol ed by using a mo e mode n FPGA, wi h mo e capaci y, and be e in eg a ion
echnology, bu i can also be imp o ed by applying some compu e a chi ec u e op imiza-
ions simila o hose ha ha e been used o op imize he execu ion o gene al pu pose
p ocesso s. We will illus a e his wi h he ollowing igu es. In Figu e 7a we p esen he
execu ion o he p e iously desc ibed e sion (single-cycle implemen a ion). The igu e
depic s he execu ion o he nodes in one o he classes. I we ha e N classes all o hem
will be execu ed in pa allel. In he igu e h ee nodes a e execu ed in h ee clock cycles.
Howe e , as explained be o e, he clock pe iod is long and he sys em uns slow.
Node i
Node j
Node k
Clk
Node i
Node j
Node k
Clk
a) Single-cycle execu ion
b) Mul i-cycle execu ion
Figu e 7. (a) Single-cycle execu ion scheme. (b) Mul i-cycle execu ion scheme.
Elec onics 2021,10, 314 9 o 15
Ou goal is o imp o e he speed, while ying o keep p ocessing one node pe
cycle. To educe he clock cycle we ha e designed a mul i-cycle implemen a ion. We
ha e explo ed h ee di e en op ions: wo, h ee and ou clock cycles. In hese e sions,
addi ional egis e s ha e been added o he a chi ec u e in o de o spli he longes
combina ional pa hs. F om ha analysis we selec ed he op ion ha execu es he nodes in
h ee cycles, because i achie es an impo an clock-pe iod educ ion and a he same ime
p o ides a clea a chi ec u e, in which i is easy o iden i y he ac ions ha a e ca ied ou
in each cycle. Wi h ou cycles, he bene i s we e e y small, and he esul ing execu ion
scheme was no in ui i e. Figu e 7b p esen s he esul s a e his s ep. AS can be seen in
he igu e, he clock equency has been imp o ed, bu he sys em is slowe han be o e,
since we need h ee clock cycles o each node. Howe e , since we ha e pa i ioned he
design ollowing a clea scheme, we could y o use a pipeline app oach. As p esen ed
in Figu e 8a we ha e h ee di e en pipeline s ages, and each one o hem uses di e en
ha dwa e esou ces. Hence, we can s a execu ing a second node, as soon as he i s one
has inished he i s s age. In ou design he i s s ep is used o ead he node ( e ch), he
second s ep is used o iden i y he ype o he node and ead he needed ea u e (decode),
and he las s ep is used o compa e i wi h he compa ison alue, and iden i y he nex
node o execu e (execu ion). The p oblem o his scheme is ha we do no know he nex
node un il he p e ious node has inished i s execu ion s age. Hence we canno e ch
i in ad ance. Hence, a simple pipeline will no p o ide any bene i . This is he same
p oblem ha con en ional p ocesso s ha e when dealing wi h ins uc ions ha include
condi ional b anches. High-pe o mance p ocesso s alle ia e his p oblem by including
complex suppo o specula i e execu ion, bu i is no an e icien solu ion o embedded
sys ems, since i in oduces impo an ene gy o e heads, and i will no achie e good
esul s, unless i is possible o iden i y clea pa e ns o b anch p edic ions. Hence, he e is
no s aigh o wa d way o ake ad an age o he pipeline a chi ec u e.
Node i
Node s
Node w
Clk
b) Mul i- h eaded pipeline execu ion
Node i
Node j
Node k
Clk
a) Pipeline execu ion
Node j
T ee n
T ee m
T ee l
T ee n
Fe ch Decode Exec.
Fe ch? Fe ch? Fe ch Decode Exec.
Fe ch? Fe ch? Fe ch Decode Exec.
Fe ch Decode Exec.
Fe ch Decode Exec.
Fe ch Decode Exec.
Fe ch Decode Exec.
Figu e 8. (a) Pipeline execu ion scheme. (b) Mul i- h eaded pipeline execu ion scheme.
Howe e , his p oblem can be sol ed by combining he pipeline wi h a mul i- h eading
app oach. The idea is o include suppo o in e lea e he execu ion o h ee di e en ees.
This can be done by including h ee @_las _node egis e s ( ha is he same as ha ing h ee
p og am coun e s in a p ocesso ). The ees in a class a e di ided in h ee se s, and each
coun e manages he execu ion o one o hese se s. Figu e 8b depic s how he execu ions
o he h ee ees a e in e lea ed. In his example h ee di e en ees (n, m and l) a e