ELEKTROTEHNI ˇ SKI VESTNIK 89(3): 117–123, 2022 IZVIRNI ZNANSTVENI ˇ CLANEK Energijsko uˇ cinkovito raˇ cunanje s pribliˇ znimi mnoˇ zilniki Ratko Pilipovi´ c, Patricio Buli´ c, Uroˇ s Lotriˇ c Univerza v Ljubljani, Fakulteta za raˇ cunalniˇ stvo in informatiko, Veˇ cna pot 113, 1000 Ljubljana, Slovenija E-poˇ sta: ratko.pilipovic@fri.uni-lj.si Povzetek. Mnoˇ zenje je zelo pogosta aritmetiˇ cna operacija, sreˇ camo jo v najrazliˇ cnejˇ sih aplikacijah, na primer pri obdelavi multimedijskih vsebin in v algoritmih strojnega uˇ cenja. Gre za raˇ cunsko zahtevno in energijsko potratno operacijo, ki jo izvajajo namenska vezja – mnoˇ zilniki. V ˇ stevilnih aplikacijah natanˇ cno raˇ cunanje ni potrebno, zato lahko natanˇ cne mnoˇ zilnike zamenjamo s pribliˇ znimi. Pri naˇ crtovanju pribliˇ znih mnoˇ zilnikov iˇ sˇ cemo reˇ sitev, ki ponuja zadovoljivo natanˇ cnost za aplikacijo in je energijsko ˇ cim bolj uˇ cinkovita. Poznamo logaritemske, nelogaritemske in hibridne pribliˇ zne mnoˇ zilnike, ki se razlikujejo v naˇ cinu raˇ cunanja pribliˇ znega zmnoˇ zka, natanˇ cnosti in porabi energije. V delu predstavimo in primerjamo novejˇ se pribliˇ zne mnoˇ zilnike iz vseh treh skupin. Mnoˇ zilnike smo sintetizirali v tehnologiji Nangate 45 nm CMOS in jih uporabili za obdelavo slik in razvrˇ sˇ canje vzorcev z globokimi nevronskimi mreˇ zami. Rezultati kaˇ zejo, da je za logaritemske pribliˇ zne mnoˇ zilnike znaˇ cilna majhna poraba energije na raˇ cun veˇ cje raˇ cunske napake, za nelogaritemske pribliˇ zne mnoˇ zilnike pa je znaˇ cilna majhna raˇ cunska napaka in zato viˇ sja poraba energije; hibridni mnoˇ zilniki po natanˇ cnosti in energijski porabi sodijo med logaritemske in nelogaritemske reˇ sitve. Kljuˇ cne besede: Pribliˇ zno raˇ cunanje, energijsko uˇ cinkovito raˇ cunanje, aritmetiˇ cna vezja, pribliˇ zni mnoˇ zilniki. Energy-efficient computing with approximate multipliers Multiplication is a crucial and ubiquitous arithmetic operation in various applications, such as multimedia content processing and machine learning algorithms. It is a computationally demanding and energy-consuming operation performed by dedicated circuits, i.e., multipliers. As many applications do not require accurate calculations, the exact multipliers can be replaced with the approximate ones. Therefore, a solution is needed to offer a satisfactory accuracy and to be optimally energy-efficient. There are three types of the approximate multipliers available: logarithmic, non-logarithmic and hybrid. They differ in their product approximation, accuracy and energy consumption. The paper presents and compares the state-of-the-art approximate multipliers of each type. The multipliers are synthesized in the Nangate 45nm CMOS te- chnology and used for image processing and classification with deep neural networks to determine their advantages and weaknesses. The results show that the logarithmic approximate multipliers have a low energy consumption but a higher error, while the non-logarithmic approximate ones have a small error and a higher energy consumption. The hybrid multipliers are somewhere between the logarithmic and non-logarithmic mul- tipliers in terms of their accuracy and energy consumption. We show that the approximate logarithmic multipliers outperform in modelling with neural networks. However, the hybrid and non-logarithmic approximate multipliers offer better results in image processing. Keywords: Approximate computing, energy-efficient compu- ting, arithmetical circuits, approximate multipliers. Prejet 4. april, 2022 Odobren 17. maj, 2022 1 UVOD V zadnjem ˇ casu je postalo pribliˇ zno raˇ cunanje (angl. approximate computing) priljubljen pristop pri naˇ crtovanju energijsko uˇ cinkovitih aritmetiˇ cnih vezij. Veliko raziskav je usmerjenih v naˇ crtovanje pribliˇ znih mnoˇ zilnikov, saj je mnoˇ zenje zahtevna in energij- sko potratna operacija. S pribliˇ znimi mnoˇ zilniki lahko doseˇ zemo obˇ cutno manjˇ so porabo energije na raˇ cun manjˇ se natanˇ cnosti izraˇ cunov, ki pa je ˇ se vedno zadovo- ljiva za ˇ stevilne aplikacije [1]. Med aplikacije, pri katerih lahko veliko pridobimo s pribliˇ znimi mnoˇ zilniki, sodijo ˇ stevilni postopki ob- delave slik in modeliranje z nevronskimi mreˇ zami. Pri obdelavi slik opazovalec teˇ zko opazi majhne spremembe kakovosti slik zaradi napak pri raˇ cunanju. Na ta raˇ cun razliˇ cni algoritmi za obdelavo slik, kot sta rezanje ˇ sivov (angl. seam carving) [2] in izgubna kompresija slik [3], poenostavljajo raˇ cunanje ali zagotavljajo manjˇ so pro- storsko zahtevnost. Globoke nevronske mreˇ ze so zelo priljubljeni modeli stojnega uˇ cenja, ki s prilagajanjem prostih parametrov ali uˇ cenjem poskuˇ sajo povezati vho- dne podatke z izhodnimi. Robustni postopki uˇ cenja nevronskim mreˇ zam omogoˇ cajo, da se do doloˇ cene mere pravilno odzivajo tudi na nepoznane ali ˇ sumne vhodne podatke. Podobno lahko z mnoˇ zico prostih parametrov kompenzirajo tudi raˇ cunske napake. Na omenjenih la- stnostih temelji uporaba tehnik pribliˇ znega raˇ cunanja v nevronskih mreˇ zah, kot je kvantizacija [4]. Pri naˇ stetih in ˇ stevilnih drugih aplikacijah natanˇ cno raˇ cunanje ne 118 PILIPOVI ´ C, BULI ´ C, LOTRI ˇ C prinese oˇ citne izboljˇ save rezultata, temveˇ c predvsem veˇ cjo porabo energije. Poznamo logaritemske, nelogaritemske in hibri- dne pribliˇ zne mnoˇ zilnike, ki se razlikujejo v naˇ cinu raˇ cunanja pribliˇ znega zmnoˇ zka, natanˇ cnosti in porabi energije. Pri logaritemskih mnoˇ zilnikih doloˇ cimo pri- bliˇ zna logaritma obeh faktorjev, ju seˇ stejemo in antilo- garitmiramo. Pri nelogaritemskih mnoˇ zilnikih poenosta- vljamo bodisi raˇ cunanje delnih zmnoˇ zkov bodisi njihovo seˇ stevanje. Hibridni mnoˇ zilniki zdruˇ zujejo elemente lo- garitemskih in nelogaritemskih mnoˇ zilnikov. V nadaljevanju predstavimo nekaj najsodobnejˇ sih pribliˇ znih mnoˇ zilnikov iz vsake skupine. Pribliˇ zne mnoˇ zilnike primerjamo z vidika zakasnitve, porabe pro- stora in energije, raˇ cunske napake in obnaˇ sanja v apli- kacijah. V poglavju 2 predstavimo osnovno idejo ter pregled sodobnih logaritemskih pribliˇ znih mnoˇ zilnikov. V poglavju 3 najprej predstavimo natanˇ cni mnoˇ zilnik, nato pa pregledamo reˇ sitve v sodobnih nelogaritem- skih pribliˇ znih mnoˇ zilnikih. Kratek pregled hibridnih mnoˇ zilnikov je podan v poglavju 4. V poglavju 5 pred- stavimo rezultate sinteze izbranih pribliˇ znih mnoˇ zilnikov ter prikaˇ zemo obnaˇ sanje pribliˇ znih mnoˇ zilnikov pri glajenju slik in razvrˇ sˇ canju z globokimi nevronskimi mreˇ zami. V sklepu povzamemo glavne ugotovitve, ki lahko sluˇ zijo kot osnovno vodilo pri izbiri pribliˇ znega mnoˇ zilnika za izbrano aplikacijo. 2 LOGARITEMSKI PRIBLI ˇ ZNI MNO ˇ ZILNIKI 2.1 Osnovna zgradba Mitchell je ˇ ze leta 1962 predlagal nepredznaˇ ceni logaritemski pribliˇ zni mnoˇ zilnik [5]. b) a) detektor vodilne enice pomikalnik prioritetni kodirnik X log 2 X m X k X log 2 X log 2 Y m P k P + c) pomikalnik P m P 1 k P Slika 1: Zgradba logaritemskih mnoˇ zilnikov: a) logaritemska pretvorba, b) seˇ stevanje logaritmov in c) raˇ cunanje antiloga- ritma. Logaritemski pribliˇ zni mnoˇ zilniki z logaritmiranjem faktorjev mnoˇ zenje nadomestijo s seˇ stevanjem, ki mu sledi antilogaritmiranje. V prvem koraku izraˇ cunamo dvojiˇ ski logaritem obeh faktorjev. Za izraˇ cun logaritma nepredznaˇ cenega ˇ stevila X v bitnem zapisu doloˇ cimo poloˇ zaj vodilne enice, ki nam doloˇ ca eksponent k X , preostali biti na desni pa predstavljajo mantiso m X , X = 2 k X (1+m X ) , (1) V prvem koraku izraˇ cunamo pribliˇ zek logaritma po enaˇ cbi log 2 X =k X +log 2 (1+m X )≈ k X +m X . (2) Slika 1a prikazuje ustrezno vezje. Z detektorjem vodilne enice in prioritetnim kodirnikom dobimo eksponentk X . Mantiso faktorja dobimo s pomikanjem vhodnega ˇ stevila za k X − 1 bitov v levo. Ker je m X vedno manjˇ si od 1, lahko seˇ stevanje v enaˇ cbi (2) nadomestimo s spenjanjem bitov v k X in m X . V drugem koraku seˇ stejemo pribliˇ zna logaritma fak- torjev X in Y . Logaritem zmnoˇ zka P = X· Y lahko zapiˇ semo kot vsoto log 2 P =k P +m P =k X +m X +k Y +m Y , (3) Slika 1b prikazuje seˇ stevalnik. Viˇ sji biti vsote predsta- vljajo eksponent zmnoˇ zka k P , medtem ko preostali biti tvorijo njegovo mantiso m P . V tretjem koraku z antilogaritmiranjem dobimo pri- bliˇ zni zmnoˇ zek P = (1+m P )· 2 k P . (4) Raˇ cunanje antilogaritma v vezju (slika 1c) izvedemo s pomikanjem vrednosti (1+m P ) za k P bitov v levo. 2.2 Pregled Opisani Mitchellov mnoˇ zilnik [5] predstavlja izhodiˇ sˇ ce za naˇ crtovanje logaritemskih pribliˇ znih mnoˇ zilnikov. Mitchellov mnoˇ zilnik ima veliko raˇ cunsko napako, ki naraˇ sˇ ca s ˇ stevilom enic v obeh faktorjih. Za zmanjˇ sanje raˇ cunske napake so Mahalingam in sodelavci [6] uporabili dekompozicijo faktorjev. Babi´ c in sodelavci [7] so predlagali iterativni postopek raˇ cunanja zmnoˇ zka, kjer z veˇ canjem ˇ stevila iteracij postopno izboljˇ sujemo njegovo natanˇ cnost. Z veˇ canjem popularnosti nevronskih mreˇ z in drugih aplikacij, odpornih proti napaki, so se zahteve po na- tanˇ cnem raˇ cunanju zmanjˇ sale. S tem se je poveˇ calo zani- manje za poenostavljenje Mitchellovega mnoˇ zilnika. Liu in sodelavci [8] so v mnoˇ zilniku ALM–SOA uporabili pribliˇ zni seˇ stevalnik. Podobno so Ansari in sodelavci [9] predlagali logaritemski pribliˇ zni mnoˇ zilnik ILM–AA s pribliˇ znim seˇ stevalnikom, ki doseˇ ze manjˇ so raˇ cunsko na- pako. V obeh pristopih uporaba pribliˇ znega seˇ stevalnika za seˇ stevanje logaritmov vodi do manjˇ sega mnoˇ zilnika in s tem do manjˇ se porabe energije. Krajˇ sanje mantise faktorjev predstavlja ˇ se en po- memben pristop pri naˇ crtovanju logaritemskih pribliˇ znih mnoˇ zilnikov. Krajˇ sa mantisa zmanjˇ suje kompleksnost vseh stopenj mnoˇ zilnika, ki pa se odraˇ za v veˇ cji napaki zmnoˇ zka. Kim in sodelavci [10] so predstavili logari- temski mnoˇ zilnik Mitchell–trunc, ki odreˇ ze najmanj po- membne bite mantise. Yin in sodelavci [11] so predlagali ENERGIJSKO U ˇ CINKOVITO RA ˇ CUNANJE S PRIBLI ˇ ZNIMI MNO ˇ ZILNIKI 119 logaritemski pribliˇ zni mnoˇ zilnik DR–ALM z dinamiˇ cnim obsegom, ki ohranja le najpomembnejˇ se bite mantise, pri ˇ cemer za kompenzacijo negativne napake nastavi zadnji bit okrajˇ sane mantise na 1. Pilipovi´ c in sodelavci [12] so predstavili uˇ cinkovit logaritemski mnoˇ zilnik TL, ki temelji na dvojnem rezanju faktorjev – v prvem koraku skrajˇ sa sam faktor, v drugem koraku pa odreˇ ze ˇ se najniˇ zje bite v mantisi. 3 NELOGARITEMSKI PRIBLI ˇ ZNI MNO ˇ ZILNIKI 3.1 Natanˇ cni Boothov mnoˇ zilnik Natanˇ cni mnoˇ zilnik z Boothovim kodiranjem vkljuˇ cuje raˇ cunanje delnih produktov ter njihovo seˇ stevanje. Leta 1950 je Booth predlagal algoritem za kodiranje v bazi 4 [13]. Algoritem predpostavlja, da je n-bitno predznaˇ ceno ˇ stevilo X predstavljeno v dvojiˇ skem komplementu, X =− b X,n − 1 2 n− 1 + n− 2 X i=0 b X,i 2 i . (5) Boothovo kodiranje iz trojic bitov (slika 3.1) doloˇ ci vrednosti ˆb R4 i =− 2b X, 2i+1 +b X, 2i +b X, 2i− 1 in tako zmanjˇ sa ˇ stevilo delnih zmnoˇ zkov P =X· Y = n/ 2− 1 X i=0 ( ˆb R4 i · Y)4 i . (6) Ker velja ˆb R4 i ∈{ 0,± 1,± 2} , lahko delne zmnoˇ zke ˆb R4 i · Y tvorimo z enostavnimi operacijami, kot sta pomik v levo in negacija. ˆb R4 7 z }| { b 15 b 14 | {z } ˆb R4 6 b 13 b 12 ˆb R4 5 z }| { b 11 b 10 |{z} ˆb R4 4 b 9 b 8 ˆb R4 3 z}|{ b 7 b 6 |{z} ˆb R4 2 b 5 b 4 ˆb R4 1 z}|{ b 3 b 2 |{z} ˆb R4 0 b 1 b 0 0 (7) Slika 2: Kodiranje vrednosti ˆ b R4 i pri Boothovem mnoˇ zenju 16- bitnih operandov v bazi 4. Za hitrejˇ se seˇ stevanje delnih zmnoˇ zkov se obiˇ cajno uporabljajo drevesa seˇ stevalnikov (npr. Wallaceovo drevo). To so kombinacijska vezja, ki omogoˇ cajo hkra- tno seˇ stevanje veˇ c delnih zmnoˇ zkov. Ta drevesa namesto polnih seˇ stevalnikov, ki seˇ stejejo le dva bita, upora- bljajo 4-2 paralelne ˇ stevnike (angl. 4-2 compressor) za seˇ stevanje ˇ stirih bitov naenkrat. 3.2 Pregled Nelogaritemski pribliˇ zni mnoˇ zilniki poenostavljajo raˇ cunanje delnih zmnoˇ zkov ali pa njihovo seˇ stevanje. Poenostavitev raˇ cunanja delnih zmnoˇ zkov daje veˇ cje prihranke prostora in energije kot seˇ stevanje. Zaradi tega se v pregledu osredotoˇ cimo na tovrstne pristope. Jiang in sodelavci [14] so predlagali pribliˇ zni mnoˇ zilnik z Boothovim kodiranjem v bazi 8, ki pribliˇ zno raˇ cuna delne zmnoˇ zke za vrednosti ˆb R8 i ∈ ± 3. Liu in sodelavci [15] so poenostavili vezje za pribliˇ zno raˇ cunanje Boothovega kodiranja v bazi 4. Da so ome- jili napako, so pribliˇ zno kodiranje uporabili samo za nekaj spodnjih delnih zmnoˇ zkov. V [16] so predlagali pribliˇ zni mnoˇ zilnik RAD1024 z Boothovim kodiranjem, pri katerem je en faktor razdeljen na viˇ sji in niˇ zji del. Bite iz viˇ sjega dela operanda kodirajo natanˇ cno v bazi 4, medtem ko bite iz niˇ zjega dela kodirajo pribliˇ zno v bazi 1024. Podobno so Waris in sodelavci [17] predlagali pribliˇ zni Boothov mnoˇ zilnik HLR–BM2, ki za viˇ sje bite uporablja natanˇ cno Boothovo kodiranje v bazi 4, za niˇ zje pa pribliˇ zno kodiranje v bazi 8. 4 HIBRIDNI PRIBLI ˇ ZNI MNO ˇ ZILNIKI Hibridni mnoˇ zilniki predstavljajo najmlajˇ so skupino pri- bliˇ znih mnoˇ zilnikov. Nastali so v ˇ zelji po zmanjˇ sanju raˇ cunske napake logaritemskih pribliˇ znih mnoˇ zilnikov. Kljub temu, da so logaritemski pribliˇ zni mnoˇ zilniki majhna in energijsko uˇ cinkovita vezja, lahko pre- cejˇ snja raˇ cunska napaka omeji njihovo uporabnost. Z vkljuˇ cevanjem Boothovega kodiranja v bazi 4 v loga- ritemske pribliˇ zne mnoˇ zilnike dobimo natanˇ cnejˇ sa in energijsko nekoliko bolj potratna vezja. Slika 3 prikazuje prvi hibridni pribliˇ zni mnoˇ zilnik LOBO [18]. Mnoˇ zilnik zdruˇ zuje natanˇ cno Boothovo ko- diranje v bazi 4 in logaritemsko kodiranje. Podobno kot nelogaritemski pribliˇ zni mnoˇ zilniki poskuˇ sa mnoˇ zilnik LOBO narediti ˇ cim manj delnih zmnoˇ zkov. Zato za bolj pomembne bite v faktorju X uporablja natanˇ cno Boo- thovo kodiranje v bazi 4, z logaritemskim mnoˇ zilnikom, ki je predstavljen v [7] pa zmnoˇ zi manj pomembne bite faktorja X s faktorjem Y . Dodatno je z zmanjˇ sevanjem ˇ sirine podatkovnih poti mnoˇ zilnik LOBO malenkost manj natanˇ cen, vendar zato energijsko bolj uˇ cinkovit. Y X 15 X 14 X 13 X 12 X 11 X 10 X 9 X 8 X 1 X 0 Boothovo kodiranje v bazi 4 logaritemski približek zmnožka Seštevanje delnih zmnožkov P PP 3 PP 2 PP 1 PP 02 PP 01 Slika 3: Zgradba mnoˇ zilnika LOBO. Hibridni pribliˇ zni mnoˇ zilnik HRALM [19] je zasnovan na podobni ideji, vendar ponuja enostavnejˇ si dizajn. Mnoˇ zilnik z Boothovim kodiranjem v bazi 4 ustvari le dva delna zmnoˇ zka, zaradi ˇ cesar lahko kompleksne drevesne sheme nadomesti z enim samim seˇ stevalnikom. Vse preostale delne zmnoˇ zke oceni z logaritemskim 120 PILIPOVI ´ C, BULI ´ C, LOTRI ˇ C pribliˇ zkom, ki vkljuˇ cuje tudi rezanje manj pomembnih bitov v mantisi. 5 REZULTATI 5.1 Sinteza mnoˇ zilnikov in ocena napake Pri izbiranju najustreznejˇ sega mnoˇ zilnika za izbrano aplikacijo so pomembne strojne znaˇ cilnosti vezja in napaka. Med prvimi bomo opazovali zakasnitev signala skozi vezje, velikosti vezja, dinamiˇ cno moˇ c in porabo energije z mero PDP (angl. Power-Delay-Product). Za oceno napake bomo uporabili normalizirano povpreˇ cno razdaljo NMED (angl. Normalized Mean Error Dis- tance), ki jo povpreˇ cimo preko vseh moˇ znih faktorjev in normaliziramo z najveˇ cjim zmnoˇ zkom natanˇ cnega mnoˇ zilnika. V primerjavo smo vkljuˇ cili pribliˇ zne mnoˇ zilnike, predstavljene v predhodnih poglavjih: logaritemske ALM–SOA11 [8], ILM–AA [9], Mitchell–trunc6 [10], DR–ALM5 [11] in TL16–8/4 [12], nelogaritem- ske RAD1024 [16] in HLR–BM2 [17] ter hibridne LOBO12–12/8 [18] in HRALM3 [19]. Vse pribliˇ zne mnoˇ zilnike smo opisali v jeziku Verilog in jih po potrebi prilagodili za raˇ cunanje s predznaˇ cenimi ˇ stevili. Za sin- tezo smo uporabili odprtokodno orodje OpenROAD [20] s knjiˇ znico Nangate 45 nm CMOS. Za oceno napake z mero NMED smo mnoˇ zilnike simulirali v programskem jeziku C. Lastnosti mnoˇ zilnikov so zbrane v tabeli 1 in po- nazorjene na sliki 4. Logaritemski pribliˇ zni mnoˇ zilniki se odlikujejo v fizikalnih lastnostih: so manjˇ sa vezja, s krajˇ simi zakasnitvami in manjˇ so porabo energije, nji- hova raˇ cunska napaka pa je veˇ cja kot pri preostalih pribliˇ znih mnoˇ zilnikih. Kot taki so odliˇ cni za aplika- cije, kjer je nizka poraba pomembnejˇ sa od natanˇ cnosti raˇ cunanja. Nelogaritemska mnoˇ zilnika se odlikujeta z nizkim NMED in zato z bistveno veˇ cjo natanˇ cnostjo od logaritemskih. Veˇ cja natanˇ cnost pa se odraˇ za v slabˇ sih fizikalnih lastnostih in manjˇ sih prihrankih v primerjavi Tabela 1: Primerjava 16 bitnih mnoˇ zilnikov. Znak ∗ oznaˇ cuje mnoˇ zilnike, prilagojene za raˇ cunanje s predznaˇ cenimi ˇ stevili. Mnoˇ zilnik Zakasnitev [ns] Moˇ c [µ W] Velikost [µ m 2 ] PDP [fJ] NMED [10 − 3 ] Natanˇ cni 1,74 69,20 1.576,58 120,41 0 Logaritemski ALM–SOA11 ∗ [8] 1,47 36,70 952,01 53,95 8,06 ILM–AA ∗ [9] 1,51 27,80 780,18 41,98 7,20 Mitchell–trunc6 [10] 1,44 32,30 840,83 46,51 14,43 DR–ALM5 [11] 1,31 32,70 831,78 42,80 5,27 TL16–8/4 [12] 1,13 25,40 702,24 28,70 11,84 Nelogaritemski RAD1024 [16] 1,50 41,00 1.008,67 61,50 0,44 HLR–BM2 [17] 1,76 60,90 1.312,18 107,18 0,01 Hibridni LOBO12–12/8 [18] 1,71 36,10 904,93 61,73 1,85 HRALM3 [19] 1,70 32,40 842,42 55,08 4,28 z natanˇ cnim mnoˇ zilnikom – vezja so veˇ cja, zato tudi zakasnitve in poraba energije. Zaradi majhne napake so nelogaritemski mnoˇ zilniki izvrstni kandidati za aplika- cije, ki dovoljujejo pribliˇ zno raˇ cunanje, vendar preve- lika nenatanˇ cnost pri raˇ cunanju pomembno vpliva na kakovost rezultata. Hibridna mnoˇ zilnika se po fizikalnih lastnostih in napaki uvrˇ sˇ cata med obe skupini in sta primerna za aplikacije, ki zahtevajo energijsko varˇ cna vezja, vendar ne prenesejo precejˇ snje raˇ cunske napake logaritemskih pribliˇ znih mnoˇ zilnikov. Slika 4: Povezava med napako NMED in porabo energije PDP za izbrane pribliˇ zne mnoˇ zilnike. 5.2 Ocena uporabnosti mnoˇ zilnikov v aplikacijah V predhodnih raziskavah [18], [19], [12] smo ocenili uporabnost sodobnih pribliˇ znih mnoˇ zilnikov v razliˇ cnih aplikacijah, na primer pri obdelavi slik in razvrˇ sˇ canju z globokimi nevronskimi mreˇ zami. V tem prispevku pov- zemamo glavne rezultate in razpravljamo o uporabnosti izbranih pribliˇ znih mnoˇ zilnikov. 5.2.1 Glajenje slik: Glajenje je eden od osnovnih postopkov pri obdelavi slik. Gre za postopek, pri ka- terem z rahlo prerazporeditvijo barv v sliki zgladimo ostre prehode in fine detajle [21]. Jedro algoritma pred- stavlja konvolucija vhodne slike s konvolucijsko masko velikosti 3× 3. Slike, zglajene z razliˇ cnimi pribliˇ znimi mnoˇ zilniki, primerjamo s sliko, zglajeno z natanˇ cnim mnoˇ zilnikom. Razliko med slikama ovrednotimo s stan- dardnima merama MSSIM (angl. Mean Structural Sim- milarity Index) in PSNR (angl. Peak Signal to Noise Ratio). Tabela 2 prikazuje rezultate glajenja na izbranih slikah iz slikovne baze TESTIMAGES [22]: building, cards, flowers, snails in wood game. Mnoˇ zilniki z izjemo DR– ALM5 se odlikujejo z visoko vrednostjo mere MS- SIM, ki ocenjuje subjektivno kakovost slike. Do veˇ cjih ENERGIJSKO U ˇ CINKOVITO RA ˇ CUNANJE S PRIBLI ˇ ZNIMI MNO ˇ ZILNIKI 121 Tabela 2: Meri MSSIM in PSNR za glajenje slik. Pribliˇ zni mnoˇ zilnik building cards flowers snails wood game MSSIM PSNR[dB] MSSIM PSNR[dB] MSSIM PSNR[dB] MSSIM PSNR[dB] MSSIM PSNR[dB] Logaritemski ALM–SOA11 [8] 0,99 39,56 0,99 39,17 0,99 39,78 0,99 39,78 0,99 39,45 ILM–AA [9] 0,99 39,75 1,00 39,24 0,99 40,08 0,99 40,08 1,00 40,04 Mitchell–trunc6 [10] 0,99 36,63 1,00 35,30 0,99 36,90 0,99 36,90 0,99 36,32 DR–ALM5 [11] 0,94 36,25 0,97 34,31 0,94 33,75 0,94 32,45 0,96 34,15 TL16–8/4 [12] 0,98 37,44 0,98 36,55 0,99 38,02 0,98 37,52 0,98 36,35 Nelogaritemski RAD1024 [16] 1,00 40,70 1,00 40,65 0,99 40,71 0,99 40,71 1,00 40,63 HLR–BM2 [17] 1,00 54,62 1,00 53,06 1,00 56,38 1,00 54,54 1,00 51,19 Hibridni LOBO12–12/8 [18] 0,99 40,69 0,99 40,42 0,99 40,99 0,99 40,67 0,99 40,38 HRALM3 [19] 1,00 41,15 1,00 41,27 1,00 41,41 1,00 41,34 1,00 41,28 a) Natančni c) HLR-BM2 b) DR-ALM5 d) HRALM3 Slika 5: Rezultati glajenja slike building z izbranimi mnoˇ zilniki. Na sliki b), ki smo jo zgladili z logaritemskim pribliˇ znim mnoˇ zilnikom DR–ALM5, opazimo posterizacijo v okolici stropne luˇ ci. razlik prihaja pri meri PSNR. Logaritemski mnoˇ zilniki zaradi velike napake NMED dosegajo nizko razmerje med signalom in ˇ sumom. Nasprotno pa nelogaritemska mnoˇ zilnika z majhno napako NMED dosegata zelo visok PSNR. Oba hibridna mnoˇ zilnika dajeta podobne rezul- tate kot nelogaritemski pribliˇ zni mnoˇ zilnik RAD1024, predvsem mnoˇ zilnik HRALM3 s precej manjˇ sim in energijsko uˇ cinkovitejˇ sim vezjem. Na sliki 5 je pri glajenju z logaritemskim mnoˇ zilnikom DR–ALM5 opa- zna posterizacija, do katere pa ne pride pri glajenju z nelogaritemskim pribliˇ znim mnoˇ zilnikom HLR–BM2 in hibridnim pribliˇ znim mnoˇ zilnikom HRALM3. 5.2.2 Razvrˇ sˇ canje s konvolucijskimi nevronskimi mreˇ zami: Konvolucijske nevronske mreˇ ze so globoke nevronske mreˇ ze, ki so primerne za razvrˇ sˇ canje slik [23]. Nevronske mreˇ ze so raˇ cunsko zahtevni modeli, ki so sposobni tolerirati napake v vhodnih podatkih in se prila- goditi tudi napaki pri raˇ cunanju. Kovolucijske nevronske mreˇ ze vkljuˇ cujejo mnoˇ zico mnoˇ zenj in so zato zelo primerne za testiranje pribliˇ znih mnoˇ zilnikov. V poskusih smo uporabili globoko nevronsko mreˇ zo ResNet-20 [24] in podatkovno bazo CIFAR10 [25]. Delali smo s knjiˇ znico Caffe [26], v kateri smo med izvajanjem modela natanˇ cna mnoˇ zenja nadomestili s pribliˇ znimi. Za vsak pribliˇ zni mnoˇ zilnik smo nevron- sko mreˇ zo uˇ cili desetkrat, vsakiˇ c z nakljuˇ cno zaˇ cetno nastavitvijo uteˇ zi in z vnaprej doloˇ ceno uˇ cno in testno mnoˇ zico [12]. Pri izvajanju modela smo uporabljali pribliˇ zno mnoˇ zenje, pri uˇ cenju pa natanˇ cno mnoˇ zenje v fiksni vejici. Slika 6 predstavlja povpreˇ cno toˇ cnost razvrˇ sˇ canja slik iz podatkovne zbirke CIFAR10 s konvolucijsko nevron- sko mreˇ zo ResNet-20. Veˇ cina pribliˇ znih mnoˇ zilnikov, ne glede na napako NMED, pri razvrˇ sˇ canju slik do- sega toˇ cnost, ki je primerljiva s toˇ cnostjo natanˇ cnega mnoˇ zilnika. Slabˇ si rezultat pri nekaterih mnoˇ zilnikih lahko pripiˇ semo njihovi zasnovi, ki jim zaradi velike napake pri mnoˇ zenju majhnih ˇ stevil ne uspe zaznati manjˇ sih razlik v vhodnih podatkih. Nevronski mreˇ zi z njeno robustno arhitekturo uspe kompenzirati veˇ cjo na- pako logaritemskih mnoˇ zilnikov. Ti so zaradi majhnosti in energijske uˇ cinkovitosti odliˇ cna izbira pri modeliranju z nevronskimi mreˇ zami. 6 SKLEP V prispevku smo predstavili najsodobnejˇ se pribliˇ zne mnoˇ zilnike. Logaritemski pribliˇ zni mnoˇ zilniki so majhni in energijsko uˇ cinkoviti, vendar pri mnoˇ zenju lahko na- redijo precejˇ snjo raˇ cunsko napako. Nelogaritemski pri- bliˇ zni mnoˇ zilniki so veliko veˇ cji in energijsko bolj potra- tni, vendar naredijo veliko manjˇ so napako pri mnoˇ zenju. Naˇ crtovanje hibridnih pribliˇ znih mnoˇ zilnikov sloni na idejah nelogaritemskih in logaritemskih mnoˇ zilnikov, zato tudi po fizikalnih lastnostih in raˇ cunski napaki za- sedajo prostor med nelogaritemskimi in logaritemskimi 122 PILIPOVI ´ C, BULI ´ C, LOTRI ˇ C Natanˇ cni mnoˇ zilnik ALM–SOA11 ILM–AA Mitchell–trunc6 DR–ALM5 TL16–8/4 RAD1024 HLR–BM2 LOBO12–12/8 HRALM3 86,00 88,00 90,00 92,00 Toˇ cnost razvrˇ sˇ canja [%] Slika 6: Toˇ cnost razvrˇ sˇ canja slik iz podatkovne mnoˇ zice CIFAR10 z nevronsko mreˇ zo ResNet-20 in pribliˇ znimi mnoˇ zilniki. mnoˇ zilniki. Pokazali smo, da so logaritemski pribliˇ zni mnoˇ zilniki odliˇ cna izbira za modeliranje z nevronskimi mreˇ zami, ki uspeˇ sno kompenzirajo njihovo veˇ cjo raˇ cunsko napako. Nelogaritemski in hibridni pribliˇ zni mnoˇ zilniki ponujajo boljˇ se rezultate od logaritemskih pribliˇ znih mnoˇ zilnikov pri obdelavi slik, kjer so sprejemljive le manjˇ se napake pri raˇ cunanju. Pribliˇ zni mnoˇ zilniki so manjˇ si, hitrejˇ si in energijsko uˇ cinkovitejˇ si od natanˇ cnih mnoˇ zilnikov. Zaradi ener- gijske uˇ cinkovitosti so po eni strani odliˇ cna izbira za aplikacije, ki zahtevajo dolgo avtonomijo, po drugi strani pa njihovo hitrost in majhnost lahko izkori- stimo za poveˇ canje raˇ cunskih kapacitet visokozmogljivih raˇ cunalniˇ skih sistemov. Pri izbiranju najprimernejˇ sega pribliˇ znega mnoˇ zilnika je treba upoˇ stevati zahteve apli- kacije. Obiˇ cajno ˇ zelimo najmanjˇ si, najhitrejˇ si ali ener- gijsko najuˇ cinkovitejˇ si mnoˇ zilnik, ki ima za pravilno delovanje aplikacije ˇ se sprejemljivo raˇ cunsko napako. Pribliˇ zni mnoˇ zilniki so velik potencial za energijsko uˇ cinkovito raˇ cunanje, ki je vedno bolj aktualno na naj- razliˇ cnejˇ sih podroˇ cjih. Glede na trenutni trend porasta aplikacij, primernih za pribliˇ zne mnoˇ zilnike, verjamemo, da bodo pribliˇ zni mnoˇ zilniki postali nenadomestljivi elementi modernih raˇ cunalniˇ skih sistemov. ZAHVALA Raziskavo je omogoˇ cilo Ministrstvo za visoko ˇ solstvo, znanost in tehnologijo Republike Slovenije v okviru programa P2-0359 - Vseprisotno raˇ cunalniˇ stvo in P2- 0241 Sinergetika kompleksnih sistemov in procesov. Hvala Tijani Milakovi´ c za vloˇ zeni trud pri lektoriranju prve razliˇ cice prispevka. LITERATURA [1] W. Liu, F. Lombardi, and M. Schulte, “Approximate computing: From circuits to applications [scanning the issue],” Proceedings of the IEEE, vol. 108, no. 12, pp. 2103–2107, 2020. [2] S. Avidan and A. Shamir, “Seam carving for content-aware image resizing,” in ACM SIGGRAPH 2007 Papers, ser. SIGGRAPH ’07. New York, NY , USA: Association for Computing Machinery, 2007, p. 10–es. [Online]. Available: https://doi.org/10.1145/1275808.1276390 [3] G. K. Wallace, “The jpeg still picture compression standard,” IEEE Transactions on Consumer Electronics, vol. 38, no. 1, pp. xviii–xxxiv, 1992. [4] V . Sze, Y . Chen, T. Yang, and J. S. Emer, “Efficient processing of deep neural networks: A tutorial and survey,” Proceedings of the IEEE, vol. 105, no. 12, pp. 2295–2329, 2017. [5] J. N. Mitchell, “Computer multiplication and division using binary logarithms,” IRE Transactions on Electronic Computers, vol. EC-11, no. 4, pp. 512–517, Aug. 1962. [6] V . Mahalingam and N. Ranganathan, “Improving accuracy in mitchell’s logarithmic multiplication using operand decompo- sition,” IEEE Transactions on Computers, vol. 55, no. 12, pp. 1523–1535, Dec. 2006. [7] Z. Babi´ c, A. Avramovi´ c, and P. Buli´ c, “An iterative logarithmic multiplier,” Microprocessors and Microsystems, vol. 35, no. 1, pp. 23 – 33, Jul. 2011. [8] W. Liu, J. Xu, D. Wang, C. Wang, P. Montuschi, and F. Lom- bardi, “Design and evaluation of approximate logarithmic multi- pliers for low power error-tolerant applications,” IEEE Transac- tions on Circuits and Systems I: Regular Papers, vol. 65, no. 9, pp. 2856–2868, Sep. 2018. [9] M. S. Ansari, B. F. Cockburn, and J. Han, “An improved logarithmic multiplier for energy-efficient neural computing,” IEEE Transactions on Computers, pp. 1–1, 2020. [10] M. S. Kim, A. A. D. Barrio, L. T. Oliveira, R. Hermida, and N. Bagherzadeh, “Efficient mitchell’s approximate log multipli- ers for convolutional neural networks,” IEEE Transactions on Computers, vol. 68, no. 5, pp. 660–675, Dec. 2019. [11] P. Yin, C. Wang, H. Waris, W. Liu, Y . Han, and F. Lom- bardi, “Design and analysis of energy-efficient dynamic range approximate logarithmic multipliers for machine learning,” IEEE Transactions on Sustainable Computing, vol. Early access, pp. 1–1, Jun. 2020. [12] R. Pilipovi´ c, P. Buli´ c, and U. Lotriˇ c, “A two-stage operand trim- ming approximate logarithmic multiplier,” IEEE Transactions on Circuits and Systems I: Regular Papers, pp. 1–11, 2021. [13] A. D. Booth, “A signed binary multiplication technique,” The Quarterly Journal of Mechanics and Applied Mathematics, vol. 4, no. 2, pp. 236–240, 1951. [14] H. Jiang, J. Han, F. Qiao, and F. Lombardi, “Approximate radix-8 booth multipliers for low-power and high-performance ENERGIJSKO U ˇ CINKOVITO RA ˇ CUNANJE S PRIBLI ˇ ZNIMI MNO ˇ ZILNIKI 123 operation,” IEEE Transactions on Computers, vol. 65, no. 8, pp. 2638–2644, Aug. 2016. [15] W. Liu, L. Qian, C. Wang, H. Jiang, J. Han, and F. Lombardi, “Design of approximate radix-4 booth multipliers for error- tolerant computing,” IEEE Transactions on Computers, vol. 66, no. 8, pp. 1435–1441, Aug. 2017. [16] V . Leon, G. Zervakis, D. Soudris, and K. Pekmestzi, “Appro- ximate hybrid high radix encoding for energy-efficient inexact multipliers,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 26, no. 3, pp. 421–430, Nov. 2018. [17] H. Waris, C. Wang, and W. Liu, “Hybrid low radix encoding- based approximate booth multipliers,” IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 67, no. 12, pp. 3367–3371, Feb. 2020. [18] R. Pilipovi´ c and P. Buli´ c, “On the design of logarithmic mul- tiplier using radix-4 booth encoding,” IEEE Access, vol. 8, pp. 64 578–64 590, Apr. 2020. [19] U. Lotriˇ c, R. Pilipovi´ c, and P. Buli´ c, “A hybrid radix-4 and approximate logarithmic multiplier for energy efficient image processing,” Electronics, vol. 10, no. 10, 2021. [Online]. Available: https://www.mdpi.com/2079-9292/10/10/1175 [20] S. Reda, “Overview of the openroad digital design flow from rtl to gds,” in 2020 International Symposium on VLSI Design, Automation and Test (VLSI-DAT), 2020, pp. 1–1. [21] R. C. Gonzalez and R. E. Woods, Digital Image Processing (3rd Edition). USA: Prentice-Hall, Inc., 2006. [22] N. Asuni and A. Giachetti, “TESTIMAGES: A large data archive for display and algorithm testing,” Journal of Graphics Tools, vol. 17, no. 4, pp. 113–125, Feb. 2013. [Online]. Available: https://doi.org/10.1080/2165347X.2015.1024298 [23] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classi- fication with deep convolutional neural networks,” in Advances in Neural Information Processing Systems, F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, Eds., vol. 25. Lake Tahoe, NV , USA: Curran Associates, Inc., Dec. 2012, pp. 1097– 1105. [24] Y . He, X. Zhang, and J. Sun, “Channel pruning for accelerating very deep neural networks,” in 2017 IEEE International Confe- rence on Computer Vision (ICCV), Oct. 2017, pp. 1398–1406. [25] A. Krizhevsky, “Learning multiple layers of features from tiny images,” University of Toronto, Toronto, Tech. Rep., Apr. 2009. [26] Y . Jia, E. Shelhamer, J. Donahue, S. Karayev, J. Long, R. Girshick, S. Guadarrama, and T. Darrell, “Caffe: Convolutional architecture for fast feature embedding,” in Proceedings of the 22nd ACM International Conference on Multimedia, ser. MM ’14. New York, NY , USA: Association for Computing Machinery, 2014, p. 675–678. [Online]. Available: https://doi.org/10.1145/2647868.2654889 Ratko Pilipovi´ c je leta 2021 doktoriral s podroˇ cja raˇ cunalniˇ stva in informatike na Univerzi v Ljubljani. Je asistent na Fakulteti za raˇ cunalniˇ stvo in informatiko. Njegovo podroˇ cje raziskovanja obsega naˇ crtovanje aritmetiˇ cnih vezij za pribliˇ zno raˇ cunanje, strojno uˇ cenje in vgrajene sisteme. Patricio Buli´ c je diplomiral na Fakulteti za elektrotehniko Univerze v Ljubljani ter magistriral in doktoriral na Fakulteti za raˇ cunalniˇ stvo in informatiko Univerze v Ljubljani, kjer pouˇ cuje veˇ c predmetov s podroˇ cja raˇ cunalniˇ skih sistemov. Uroˇ s Lotriˇ c je izredni profesor na Fakulteti za raˇ cunalniˇ stvo in informatiko Univerze v Ljubljani. Raziskovalno dela na podroˇ cju in- formacijske teorije in visokozmogljivega raˇ cunanja. Omenjeni podroˇ cji pokriva tudi v pedagoˇ skem procesu.