FPGA accelerator for gradient boosting decision trees

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