Mapping arbitrary logic functions onto carry chains in FPGAs

  Ci a ion: Senhadji-Na a o, R.; Ga cia-Va gas, I. Mapping A bi a y Logic Func ions on o Ca y Chains in FPGAs. Elec onics 2022,11, 27. h ps://doi.o g/10.3390/ elec onics11010027 Academic Edi o : Akash Kuma Recei ed: 8 Decembe 2021 Accep ed: 20 Decembe 2021 Published: 22 Decembe 2021 Publishe ’s No e: MDPI s ays neu al wi h ega d o ju isdic ional claims in published maps and ins i u ional a il- ia ions. Copy igh : © 2021 by he au ho s. Licensee MDPI, Basel, Swi ze land. This a icle is an open access a icle dis ibu ed unde he e ms and condi 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/). elec onics A icle Mapping A bi a y Logic Func ions on o Ca y Chains in FPGAs Raou Senhadji-Na a o *,† and Ignacio Ga cia-Va gas † Depa men o Compu e A chi ec u e and Technology, Uni e si y o Se ille, 41012 Se ille, Spain; [email p o ec ed] *Co espondence: [email p o ec ed] † These au ho s con ibu ed equally o his wo k. Abs ac : Cu en Field P og ammable Ga e A ays (FPGAs) p o ide as ou ing links and special logic o pe o m ca y ope a ions; howe e , hese esou ces can also be used o implemen non- a i hme ic ci cui s. In his pape , a new app oach o mapping logic unc ions on o ca y chains is p esen ed. Unlike o he app oaches, he p oposed echnique can be applied o any logic unc ion. The p esen ed echnique includes: (1) an a chi ec u e ha is composed o blocks ha implemen AND and OR unc ions (called CANDs and CORs, espec i ely) by means o Look-Up-Tables (LUTs) and ca y-chain esou ces; and (2) a mapping algo i hm o educe bo h he delay o he c i ical pa h and he numbe o used FPGA esou ces. The algo i hm uses a heu is ic o in e connec CORs and CANDs in o de o educe he delay. The p oblem o mapping he max e ms (o min e ms) o a unc ion o LUTs has been modelled as a Se Bin Packing (SBP) p oblem. Since SBP is NP-Ha d, a g eedy algo i hm has been p oposed, which is based on he Fi s Fi Dec easing (FFD) heu is ic. The esul s ob ained ha e been compa ed wi h he con en ional echnique using bo h speed and a ea op imiza ion. Fo his pu pose, a la ge syn he ic se o es cases has been gene a ed. The p oposed echnique imp o es bo h he speed and a ea esul s o he as majo i y o unc ions whose con en ional implemen a ion equi es mo e han ou logic le els. I is impo an o highligh ha he imp o emen o one pa ame e (speed o a ea) is no achie ed a he expense o he o he . Keywo ds: ca y chain; logic syn hesis; FPGA; echnology mapping 1. In oduc ion Field P og ammable Ga e A ays (FPGAs) ha e es ablished hemsel es as one o he p e e ed digi al implemen a ion pla o ms in a ple ho a o cu en indus ial appli- ca ions [ 1 ]. FPGAs ha e e ol ed om a simple de ice o in eg a ing glue-logic o he cu en complex de ices, which includes mo e han 5 million logic cells wi h a hos o o he ea u es such as embedded p ocesso s, DSP blocks o embedded memo y blocks [ 2 , 3 ]. These cha ac e is ics make hese de ices ideal as econ igu able compu ing pla o ms o eal applica ions, allowing he mapping o complex algo i hms on o ha dwa e o achie e he demanding pe o mance o cu en applica ions. I is usual ha designe s y o use FPGA esou ces o a di e en pu pose han o which hey we e included. Following he p inciple called “use i o lose i ”, di e en wo ks in he li e a u e ha e p oposed an uncon en ional use o FPGA esou ces; a ypical example is he use o embedded memo y blocks o implemen ini e s a e machines [4–10]. Op imizing he c i ical pa h o a ci cui is essen ial o achie ing a high pe o mance; in many cases, his is accomplished by including special esou ces in FPGAs. In mos da apa h ci cui s, he c i ical pa h includes he ca y chain used o a i hme ic ope a ions [ 11 ]. In adde s and sub ac o s, his chain gene a es he ca y be ween consecu i e bi s. In ci cui s such as pa i y gene a o s o compa a o s, he chain communica es he cumula i e in o ma ion needed o pe o m hese compu a ions [ 11 ]. Fo his eason, cu en FPGAs p o ide as ou ing links and special logic o pe o m ca y ope a ions. Fo example, in Xilinx FPGA de ices, ca y chains a e composed o dedica ed mul iplexe s and XOR ga es o adding/sub ac ing he ope ands wi h he selec ed ca y bi s [12]. Elec onics 2022,11, 27. h ps://doi.o g/10.3390/elec onics11010027 h ps://www.mdpi.com/jou nal/elec onics Elec onics 2022,11, 27 2 o 13 Al hough ca y chains a e included in FPGAs o implemen a i hme ic ci cui s, hey can also be used o implemen some pa icula logic unc ions, such as AND o OR op- e a ions [ 13 – 15 ]. In his pape , a echnique o mapping a bi a y logic unc ions on o ca y-chains is p oposed. This echnique includes: (1) an a chi ec u e, which is composed o blocks ha implemen AND o OR unc ions by means o Look-Up-Tables (LUTs) and ca y-chain esou ces; and (2) a mapping algo i hm o educe he delay o he c i ical pa h and he numbe o used FPGA esou ces. The emainde o his a icle is o ganized as ollows. In Sec ion 2, we e iew he exis ing li e a u e on he use o ca y chains in non-a i hme ic ci cui s. In Sec ion 3, a backg ound abou he use o ca y chains o implemen ing basic logic unc ions is p e- sen ed. Sec ion 4desc ibes he p oposed a chi ec u e and algo i hm in de ail. Sec ion 5 p esen s he expe imen al esul s. Finally, in Sec ion 6, some conclusions and u u e wo ks a e discussed. 2. Rela ed Wo ks In he li e a u e, he e a e ew wo ks in which ca y chains a e used o imp o e he pe o mance o non-a i hme ic ci cui s. In [ 16 ], a echnique o iden i y logic chains in a ne lis and o map hem on o ca y chains is p esen ed. Howe e , his echnique canno be applied in cu en FPGAs because hey do no include he esou ces equi ed by he p oposed app oach (which is only compa ible wi h he dep eca ed Al e a S a ix and Cyclone de ices [ 17 , 18 ]). In [ 19 ], P eusse e al. p esen an LUT ex ension based on he esou ces o he logic cell o p opaga e he ca y. This ex ension allows he implemen a ion o some (k+ 1 ) -inpu logic unc ions using a unique k -LUT along wi h ca y-chain esou ces; howe e , no all (k+ 1 ) -inpu unc ions gene a ed by he syn hesis ool can be implemen ed in he p oposed LUT ex ension. In addi ion, he applica ion o he p oposed echnique equi es he use o i s own cu -based app oach, which does no acili a e i s in eg a ion in o he design low o comme cial ools. The au ho s claim ha he combina ional delay is educed by abou 20%; howe e , hese esul s ha e been es ima ed using an a chi ec u e simila o Vi ex-5 ins ead o a eal de ice. In addi ion, hey ha e been ob ained wi hou ca ied ou he placemen -and- ou ing. So, ou ing o e head is no aken in o accoun , and he e o e he pe o mance imp o emen is unclea . In [ 20 ], he p oposed echnique eplaces he in e connec ion wi es be ween logic blocks by ca y chains in a pos -syn hesis s age. Al hough no all logic chains can be mapped on o ca y chains, he esul s show ha 9% o ou ing wi es can be sa ed. Chu e al. [ 21 ] p opose a syn hesis me hod ha exploi s ca y chains o mapping gene al logic. The p oposed echnology mapping is based on majo i y-in e e g aphs (MIGs). The MIG ne wo k is pa i ioned in o wo pa s. The ex ac ed ca y-chain logic is implemen ed on ca y chains while he es is mapped on o LUTs as usual. The ex ac ed ca y-chain logic by he Cu Map algo i hm [ 22 ] mus sa is y some cons ain s o be mappable on o LUTs; none heless, inal mapping shows an a e age delay imp o emen o 8% wi h a 10% inc ease in he numbe o LUTs. In [ 23 ], he au ho s p opose he use o he ca y chain o implemen gene al logic as a means o educing he c i ical pa h delay in a pos -syn hesis s age. The echnique selec s a pa h in he MIG o map i on o he ca y chain by es ima ing he po en ial imp o emen p io o LUT mapping. Once MIG nodes a e selec ed o he ca y chain, he es o he ci cui is mapped in ABC [ 24 ] as an and-in e e g aph (ins ead o a MIG). The esul s show ha he echnique allows o map he majo i y o he c i ical LUTs. On a e age, he pe cen age o mapped c i ical LUTs a e 86% and 78% in a ea and speed op imiza ion, espec i ely. This esul s on an a e age inc emen o he a ea-delay p oduc o 9%. The main di e ence be ween his wo k and ha p esen ed in [ 21 ] is ha , in he o me , he echnique is applied be o e he syn hesis p ocess while in he la e i is a pos echnology mapping app oach. Unlike he men ioned echniques, ou app oach does no equi e a p e ious syn hesis p ocess because i does no wo k a he ne lis le el. The e o e, he VHDL desc ip ion gene a ed by ou ool can be syn hesized and implemen ed wi hin he design low o Elec onics 2022,11, 27 3 o 13 comme cial FPGA ools. This is an impo an issue because i g ea ly acili a es he use o he echnique by in eg a ing i in he design low o ools. Ano he impo an di e ence is ha ou app oach can be applied o he logic unc- ion as a whole, and no only o a de e mined subse o he sub unc ions o which i is composed. This is possible because any logic unc ion can be exp essed as sum o min e ms o p oduc o max e ms, which only equi e AND and OR ope a ions. Since he p oposed echnique maps hese ope a ions on o ca y chains, any logic unc ion can be implemen ed. By con as , he o he echniques only map he subse o sub unc ions ha sa is y ce ain cons ain s. 3. Backg ound Some basic logic unc ions can be implemen ed using ca y-chains [ 13 – 15 ]. Since ca y chains a e cascadable o o m wide add/sub ac logic, mapping logic unc ions on o ca y chains is pa icula ly in e es ing o implemen ing wide logic unc ions (i.e., logic unc ions wi h a la ge numbe o inpu s). In he case o he AND unc ion, i can be i ially mapped on o ca y-chain esou ces by means o a beha io al desc ip ion o an adde (see Figu e 1). This is possible because i a numbe is inc eased by one, he ob ained ca y bi is one only i all bi s o he numbe a e ones. This allows o exploi he ca y-chain esou ces e en when he syn hesis ool does no suppo he mapping wide logic unc ions on o ca y chains. Bo h Xilinx and Al e a/In el p o ide a chi ec u al componen s o ins an ia e ca y- chain esou ces, called p imi i es and Lib a y o Pa ame e ized Modules (LPM) unc ions, espec i ely. In Xilinx FPGA de ices [ 12 ], he ca y logic is composed o dedica ed 2:1 mul iplexe s (called MUXCYs), dedica ed XOR ga es o adding/sub ac ing he ope ands wi h he selec ed ca y bi s [ 12 ], and dedica ed connec ions ha a e independen o he gene al-pu pose logic esou ces. In o de o illus a e he use o hese esou ces, Figu e 2 shows a 3-bi ull adde implemen ed in a Xilinx de ice. MUXCYs can be combined wi h LUTs o implemen basic unc ions, such as AND, OR, NAND o NOR ope a ions. As an example, Figu e 3a,b shows he implemen a ion o 24-bi AND and OR unc ions using ca y chains, espec i ely. NAND and NOR unc ions can be implemen ed by changing he cons an alues o MUXCYs o he AND and OR implemen a ions, espec i ely. lib a y IEEE; use IEEE . STD_LOGIC_1164 . ALL; use IEEE . STD_LOGIC_ARITH . ALL; en i y wide_and is po ( inpu : in s d_logic_ ec o (23 down o 0); ou pu : ou s d_logic ); end wide_and; a chi ec u e a ch o wide_and is signal esul : unsigned (24 down o 0); begin -- a ge and sou ce mus ha e he same size esul <= unsigned (’0’ & inpu ) + 1; ou pu <= esul (24); end a ch; Figu e 1. Example o VHDL code o implemen ing 24-inpu AND unc ion using ca y chains. Elec onics 2022,11, 27 4 o 13 Figu e 2. A 3-bi ull adde implemen ed in a Xilinx FPGA de ice using ca y chains. (a) (b) Figu e 3. Examples o he implemen a ion o wide inpu unc ions using ca y chains: ( a ) 24-inpu AND and (b) 24-inpu OR. Xilinx ISE Design Sui e au oma ically maps AND, OR, NOR o NAND unc ions o LUTs along wi h ca y-chain esou ces when he numbe o inpu s is la ge enough [ 25 ]. This p ocess is con olled by means o he ollowing p ope ies: wide_ga e_ex ac ,wide_ga e_min_size and wide_ga e_max_size. The i s p ope y allows o enable o disable he in e ence o ca y- chain esou ces o wide logic unc ions. The wide_ga e_min_size and wide_ga e_max_size p ope ies speci y he minimum and he maximum o he numbe o inpu s equi ed o apply ca y-chain mapping ( hei de aul alues a e 36 and 500). Un o una ely, his mapping is limi ed o he basic unc ions men ioned abo e, and i is no suppo ed by he cu en Xilinx Vi ado Design Sui e. Figu e 4shows he gene al a chi ec u e o implemen ing wide logic unc ions using ca y-chain esou ces (which will be e e ed o as CFUN). CFUN is composed o a chain o qcomponen s, each one including one LUT and one MUXCY. The i h componen is he one loca ed in he posi ion i s a ing wi h he componen closes o he ou pu o he CFUN (simila ly, we will say i h MUXCY o i h LUT). We e e o he numbe o componen s o CFUN as i s leng h. A CFUN o leng h q allows he implemen a ion o a logic unc ion o up o q×k inpu s, whe e k ep esen s he numbe o inpu s o an LUT. Depending on he cons an alues A and B connec ed o MUXCYs and on he sub unc ion implemen ed in he LUTs, di e en logic unc ions can be ob ained. Fo ins ance, CFUN implemen s he AND unc ion i each LUT is con igu ed as an AND, A= 0, and B= 1 (we will e e o i as CAND). Simila ly, CFUN implemen s he OR unc ion i each LUT is con igu ed as a NOR, A=1, and B=0 (we will e e o i as COR). Elec onics 2022,11, 27 5 o 13 In CFUN, he la ges pa h be ween an inpu and he ou pu (i.e., he c i ical pa h) is composed o he las LUT and all MUXCYs (see Figu e 4). The numbe o MUXCYs g ows wi h he numbe o inpu s o he unc ion. Howe e , only he las LUT is in he c i ical pa h. The delay o a MUXCY is much sho e han ha o a LUT; he e o e, CFUN is highly scalable. As a consequence, i he numbe o inpu s is la ge enough, CFUN is as e han he con en ional LUT-based implemen a ions (i.e., hose ha do no use ca y chains). Figu e 4. CFUN a chi ec u e o implemen basic wide logic unc ions using ca y chains. 4. Implemen a ion o A bi a y Logic Func ions Using Ca y Chains Le us suppose an FPGA based on k -inpu LUTs. An a bi a y logic unc ion can be exp essed as a p oduc o max e ms (POM) o a sum o min e ms (SOM). Fo POM, he p oposed implemen a ion (called CPOM) is composed o one CAND and ze o o mo e CORs. The max e ms wi h less han k a iables a e implemen ed in he LUTs o he CAND while each max e m wi h mo e han k a iables is implemen ed using a COR whose ou pu is connec ed o he CAND. Simila ly, o SOM, he p oposed implemen a ion (called CSOM) is composed o one COR and ze o o mo e CANDs ha implemen min e ms wi h mo e han k a iables. Wi hou loss o gene ali y, we assume ha logic unc ions a e exp essed as POM in his wo k. The oy example shown in Figu e 5is used o illus a e he p oposed echnique (he e, we conside ha k = 6). Figu e 5a shows he gi en logic unc ion, which includes eigh max e ms. Two o hem ha e mo e han 6 a iables. The e o e, wo CORs a e equi ed, whose ou pu s a e connec ed o LUTs o he CAND. In his way, each LUT o he CAND implemen s one max e m wi h no mo e han k a iables o he p oduc o se e al max e ms whene e hey in ol e a o al numbe o signals no g ea e han k ( hese signals can be a iables o COR ou pu s). Depending on he numbe o a iables, each max e m o he p oduc is implemen ed in he own LUT o in a COR. Fo example, in Figu e 5b, he las LUT o he CAND (whose ou pu is y0 ) implemen s he p oduc o he max e ms (x9+x10) and (x9+x11) ; he e o e, he LUT has he ollowing inpu signals: x9 , x10 and x11 (no e ha he numbe o a iables is only h ee e en hough he o al numbe o li e als is ou ). The i s LUT o he CAND implemen s he p oduc o he max e m (x2+x6+x7+x8) and he wo max e ms wi h mo e han six a iables (which a e implemen ed using CORs); he e o e, he LUT has he ollowing inpu signals: x2,x6,x7,x8,y8, and y9. The c i ical pa h o a CPOM includes ei he (1) only he CAND o (2) one COR and pa o (o all) he CAND, so he c i ical pa h delay is he maximum o he delays o hese pa hs. In he i s case, he pa h includes he las LUT o he CAND and all i s MUXCYs; he e o e, he delay depends di ec ly on he leng h o he CAND. In Figu e 5b, he pa h o he CAND includes one LUT and h ee MUXCYs. In he second case, he delay o a pa h ha includes a COR depends on bo h he leng h o he COR and he posi ion o he LUT o he CAND o which i is connec ed. This pa h includes he las LUT o he COR and all i s MUXCYs, he LUT o he CAND o which he COR is connec ed, and all MUXCYs be ween ha LUT and he CAND ou pu . The e o e, he pa h includes wo LUTs. We de ine he dep h o he COR as he sum o he leng h o he COR and he posi ion q o he LUT o he CAND o which i is connec ed (see he q h elemen s o Figu e 4). The delay imposed by a COR depends di ec ly on i s dep h. In Figu e 5b, he COR whose ou pu is y8has a dep h equal o ou , and i s pa h includes wo LUTs and ou MUXCYs. Elec onics 2022,11, 27 6 o 13 y=x4·(x0+x1+x2+x3+x4+x5)·(x0+x1+x2)·(x2+x6+x7+x8)·(x9+x10)· (x9+x11)·(x10 +x11 +x12 +x13 +x4+x8+x9+x1+x19 +x6+x15 +x3+x14 +x0+ x16 +x18 +x17 +x5)·(x8+x6+x3+x7+x14 +x10 +x19 +x2+x17 +x12 +x0+x5) (a) (b) y0= (x9+x10)·(x9+x11) y1=x0+x1+x2+x3+x4+x5 y2=x2+x6+x7+x8 y3=x10 +x11 +x12 +x13 +x4+x8 y4=x9+x1+x19 +x6+x15 +x3 y5=x14 +x0+x16 +x18 +x17 +x5 y6=x8+x6+x3+x7+x14 +x10 y7=x19 +x2+x17 +x12 +x0+x5 y8=y3+y4+y5 y9=y6+y7. (c) Figu e 5. Example o CPOM implemen a ion in a 6-LUT-based FPGA: ( a ) logic unc ion, ( b ) imple- men a ion and (c) sub unc ions implemen ed by he LUTs. Elec onics 2022,11, 27 7 o 13 In a MUXCY, he e exis wo di e en kind o delays: he delay o he pa h be ween an inpu da a signal and he ou pu signal (which will be called da a delay), and he delay o he pa h be ween he inpu con ol signal and he ou pu signal (which will be called con ol delay). The c i ical pa h delay o a POM can be exp essed as: d=max(dA,dO) dA=dL+dC M+dD M(lA−1) dO=2(dL+dC M) + dD M(pO−2), whe e dL is he delay o a LUT; dD M , he da a delay o a MUXCY; dC M , he con ol delay o a MUXCY; lA , he leng h o he CAND; and pO , he maximum dep h o he CORs. The delay imposed by he CORs ( dO ) can be educed by minimizing he maximum dep h o he CORs ( pO ). This can be achie ed by connec ing he CORs o he CAND in dec easing o de o i s leng h s a ing om he i s LUT o he CAND. This pape p oposes a mapping algo i hm (see Algo i hm 1) wi h he aim o educing bo h he numbe o used esou ces and he delay o he c i ical pa h. The algo i hm ies o educe he numbe o equi ed elemen by he CAND by packing mo e han one max e m in o each LUT, which allows o educe he numbe o used LUTs and MUXCYs. This can also impac he delay when he c i ical pa h include only he CAND. In addi ion, he connec ions be ween he CORs and he CAND is ca ied ou aken in o accoun he leng h o he CORs in o de o educe he maximum dep h o he CORs. Wi hou loss o gene ali y, we assume ha he logic unc ion is exp essed as a POM, hus Algo i hm 1maps unc ions exp essed as POM o he co esponding CPOM imple- men a ion. In he case o a SOM, he co esponding mapping algo i hm would be he same, bu exchanging he CANDs by he CORs and eplacing he AND ope a ions by NOR ope a ions. Le us suppose ha k is he numbe o inpu s o an LUT. The algo i hm consis s o wo s eps. The i s one c ea es one COR o each max e m wi h mo e han k a iables (see lines om wo o en). To educe he delay o he c i ical pa h, CORs a e connec ed o he LUTs o he CAND in dec easing o de o hei leng hs s a ing om he i s LUT. The second s ep maps he max e ms o up o k a iables on o LUTs (see lines om 11 o 21). This p oblem can be modelled as a Se Bin Packing (SBP) p oblem [ 26 ], which is a a ian o he classical Bin Packing (BP) p oblem [ 27 ]. In BP, i ems wi h di e en sizes mus be packed in o bins o a ixed gi en capaci y in a way ha minimizes he numbe o used bins. In SBP, e e y i em is a se , and a bin can con ain i ems whene e he ca dinali y o he union o he i ems is less han o equal o he capaci y o he bin. In ou case, i ems ep esen max e ms (i.e., he se o a iables o each max e m) and LUTs ep esen bins whose capaci y is k . Since SBP is NP-Ha d [ 26 ], he p oposed algo i hm uses a g eedy s a egy, which is based on he Fi s Fi Dec easing (FFD) heu is ic [ 27 ]. In his heu is ic, he i ems a e so ed in dec easing o de o hei sizes. Fo he i s bin, i ems a e packed in o i ollowing he conside ed o de un il no mo e i ems can be packed. Then, a new bin is c ea ed and he p ocess s a s wi h he emaining i ems. The p ocedu e inishes when all i ems a e packed. In he i s i e a ion o he while loop o Algo i hm 1, L can con ain some COR ou pu s no assigned o any LUT ye (i.e., L can be non-emp y). These ou pu s a e connec ed o he LUT c ea ed in he i s i e a ion (whene e possible, along wi h o he max e ms). The mapping algo i hm educes he numbe o LUTs and MUXCYs o he CAND and, he e o e, he delay imposed by hem. As a consequence, he algo i hm can also inc ease he speed. In o de o illus a e he ope a ion o Algo i hm 1, we ha e applied i o he unc ion shown in Figu e 5a. In he i s loop, he CORs wi h ou pu y8 and y9 a e c ea ed and connec ed o he i s LUT o he CAND. The algo i hm packs (x2+x6+x7+x8) in o he i s LUT because i is he la ges max e m ha can be packed in o ha LUT (no e ha only ou inpu s a e a ailable). Since no o he max e m can be packed in he i s LUT, he algo i hm execu es a new i e a ion o he second loop. In his case, he la ges max e m is (x0+x1+x2+x3+x4+x5) , which is packed in o he second LUT. Then, x4 is also packed Elec onics 2022,11, 27 8 o 13 in o he second LUT al hough he LUT al eady ha e six inpu s. Finally, he max e ms (x9+x10)and (x9+x11)a e packed in o he hi d LUT. When unc ions only ha e max e ms wi h no mo e han k a iables, he p oposed echnique gene a es implemen a ions composed only o one CAND. As men ioned in Sec ion 3, Xilinx ISE Design Sui e can only map basic logic unc ions (AND, OR, NOR and NAND) on o ca y-chains, and he e o e i canno map a POM e en i i has no max e m wi h mo e han k a iables. In hese cases, he ad an age o he p oposed echnique is ha c i ical pa h only includes one LUT and he MUXCYs. Algo i hm 1 Mapping POM o CPOM. Inpu : Mis he se o max e ms, kis he numbe o inpu s o a LUT Ou pu : Ais he CPOM 1: A←emp y CAND 2: L←∅ 3: Le S⊆Mbe he se o max e ms whose numbe o a iables is g ea e han k 4: o each m∈Sin dec easing o de o i s numbe o a iables do 5: C ea e a COR o mand add i s ou pu o L 6: i |L|=k hen 7: Add a LUT ha implemen s he AND o he signals o La e he las LUT o A 8: L←∅ 9: end i 10: end o 11: S←M S 12: while S6=∅o L6=∅do 13: o each m∈Sin dec easing o de o i s numbe o a iables do 14: i he numbe o a iables o L∪ {m}is less han o equal o k hen 15: L←L∪ {m} 16: end i 17: end o 18: Add a LUT ha implemen s he AND o he signals o La e he las LUT o A 19: S←S L 20: L←∅ 21: end while 5. Expe imen al Resul s The p oposed echnique has been e alua ed wi h a la ge se o syn he ic es cases, which a e single-ou pu logic unc ions exp essed as POM. Each es case has been gen- e a ed using di e en andom alues pe each o he ollowing pa ame e s: numbe o a iables (#Va iables), numbe o max e ms (#Max e ms), minimum numbe o a iables pe max e m (MinVa ) and maximum numbe o a iables pe max e m (MaxVa ). The numbe o a iables o each max e m has been de e mined by a andom alue be ween he minimum and maximum assigned o he es case. The a iables a e nega ed wi h a p obabili y o 50%. Table 1shows some s a is ics ( he mean, he s anda d de ia ion, he minimum alue, he qua iles, he maximum alue) o he pa ame e s o he es cases. A gVa ep esen s he a e age numbe o a iables pe max e m. We ha e used Xilinx Vi ado Design Sui e 2019.2 o syn hesize and implemen he es cases, so he esul s include he delay o he placemen -and- ou ing s age. The a ge de ice is xc7a200 g1156-3 (i.e., a Xilinx A ix-7 FPGA). Fo each es case, a VHDL s uc u al desc ip ion has been gene a ed a e applying Algo i hm 1. These desc ip ions use Xilinx p imi i es o ins an ia e LUTs and MUXCYs; he e o e, he ool does no de e mine he FPGA componen s used in he implemen a ions (we will e e o hese implemen a ions as CARRY-MAP). Elec onics 2022,11, 27 9 o 13 Table 1. S a is ics o es cases. Mean SD Min. Q1 Q2 Q3 Max. #Va iables 47.4 35.1 9.0 21.2 32.5 74.0 161.0 #Max e ms 159.9 146.5 8.0 45.2 88.0 276.0 586.0 MinVa 3.9 2.5 1.0 2.2 4.0 5.0 15.0 MaxVa 35.4 31.4 7.0 13.0 20.0 53.0 128.0 A gVa 19.2 15.9 4.1 7.8 11.8 29.3 70.5 The esul s o CARRY-MAP ha e been compa ed o he con en ional LUT-based implemen a ions gene a ed by Vi ado (he eina e e e ed o as VIV-MAP), which do no use ca y chains. VIV-MAP implemen a ions ha e been gene a ed om canonical POM desc ip ions o he logic unc ions using a VHDL beha io al s yle. The complexi y o each logic unc ion has been measu ed as he numbe o logic le els in he c i ical pa h o he VIV-MAP. In o de o p o ide an homogeneous sample in e ms o complexi y, a se o andom es cases ha e been gene a ed, and 30 cases ha e been andomly chosen o each logic le el o s udy ( om h ee o se en); so, a o al numbe o 150 es cases ha e been used. In o de o e alua e he impac o he p oposed echnique in bo h speed and a ea, we ha e selec ed he ollowing p econ igu ed s a egies: Flow_Pe Op imized_high and Pe o mance_Ex aTimingOp o speed op imiza ion in syn hesis and implemen a ion, e- spec i ely, and Flow_A eaOp imized_high and A ea_Explo eWi hRemap o a ea op imiza ion in syn hesis and implemen a ion, espec i ely. The same s a egies ha e been used o VIV-MAP and CARRY-MAP. Rega ding speed op imiza ion, Tables 2and 3summa ize he speed inc emen and a ea educ ion, espec i ely, ob ained by CARRY-MAP espec o VIV-MAP. Bo h ables show he s a is ical measu es men ioned be o e and he hi a e (i.e., he pe cen age o he cases in which he p oposed echnique is be e ). CARRY-MAP is as e han VIV-MAP in 57% o cases, bu he a e age speed inc emen is ze o. Howe e , he a e age speed inc emen inc eases o 14% when only he success cases a e aken in o accoun . The analysis o he esul s by le els o logic shows ha he success o he p oposed echnique depends la gely on he complexi y o he logic unc ions. I is obse ed ha he e is a clea inc easing end in bo h he speed inc emen and hi a e wi h he numbe o logic le els. Fo he cases wi h mo e han ou le els, he hi a e and he a e age speed inc emen a e 89% and 12% ( o mo e han i e le els, hese alues inc ease up o 97% and 17%, espec i ely). Rega ding a ea esul s when speed op imiza ion is used (see Table 3), CARRY-MAP uses less numbe o LUTs han VIV-MAP in 72% o cases. Wi h he excep ion o he unc ions wi h 3 logic le els, he hi a es a e g ea e han o equal o 70%. In addi ion, he a e age educ ion is equal o o g ea e han 7% o he cases wi h mo e han 4 le els. The e o e, i is impo an o highligh ha he signi ican imp o emen o he speed is no achie ed a he expense o using mo e esou ces. This is e idenced in he s a is ics shown in Table 4, which ela es he speed esul s o he a ea esul s. The hi a e ep esen s he pe cen age o cases in which CARRY-MAP is be e han VIV-MAP aking in o accoun bo h he speed and a ea esul s; ha is, he cases in which CARRY-MAP imp o es he speed and/o a ea wi hou wo sening he o he pa ame e . Simila ly, he miss a e ep esen s he cases in which CARRY-MAP wo se he speed and/o a ea wi hou imp o ing he o he pa ame e . These esul s clea ly show ha he p oposed echnique is he be e design op ion aken in o accoun bo h speed and a ea o unc ions wi h mo e han 4 le els when speed op imiza ion is used. Tables 5–7show he esul s o a ea op imiza ion. Fo le els g ea e han 3, CARRY- MAP uses a less numbe o LUTs han VIV-MAP in a leas 53% o cases (see Table 5 ); howe e , he a e age a ea educ ion p esen s posi i e alues only o le els g ea e han 4. The a ea op imiza ion echniques o VIV-MAP a e pa icula ly use ul in complex unc ions wi h many edundan sub unc ions. Howe e , hey canno be applied o CARRY-MAP