Future vector microprocessor extensions for data aggregations

Fu u e Vec o Mic op ocesso Ex ensions o Da a Agg ega ions Timo hy Hayes∗†, Osca Paloma ∗†, Osman Unsal∗, Ad ian C is al∗†‡ and Ma eo Vale o∗† ∗Ba celona Supe compu ing Cen e †Uni e si a Poli ` ecnica de Ca alunya ‡Consejo Supe io de In es igaciones Cien ´ ı icas (IIIA-CSIC) { i s }.{las }@bsc.es Abs ac —As he a e o annual da a gene a ion g ows exponen ially, he e is a demand o agg ega e and summa ise as amoun s o in o ma ion quickly. In he pas , equency scaling was elied upon o push applica ion h oughpu . Today, Denna d scaling has ceased and u he pe o mance mus come om exploi ing pa allelism. Single ins uc ion-mul iple da a (SIMD) ins uc ion se s o e a highly e icien and scalable way o exploi ing da a-le el pa allelism (DLP). While mic op ocesso s o iginally o e ed e y simple SIMD suppo a ge ed a mul imedia applica ions, hese ex ensions ha e been g owing bo h in wid h and unc ionali y. Obse ing his end, we use a simula ion amewo k o model u u e SIMD suppo and hen p opose and e alua e i e di e en ways o ec o ising da a agg ega ion. We ind ha al hough da a agg ega ion is abundan in DLP, i is o en oo i egula o be exp essed e icien ly using ypical SIMD ins uc ions. Based on his obse a ion, we p opose a se o no el algo i hms and SIMD ins uc ions o be e cap u e his i egula DLP. Fu he mo e, we disco e ha he bes algo i hm is highly dependen on he cha ac e is ics o he inpu . Ou p oposed solu ion can dynamically choose he op imal algo i hm in he majo i y o cases and achie es speedups be ween 2.7×and 7.6× o e a scala baseline. I. INTRODUCTION The a e o da a gene a ion is g owing exponen ially each yea [1]. Since his has led o eno mous olumes o da a o manage and que y, he e is p essu e on bo h so wa e and ha dwa e de elope s o c ea e solu ions ha can cope wi h he inc easing equi emen s. Agg ega ion is a e y use ul ope a ion when summa ising conside able amoun s o da a and is a co ne s one o impo an echnologies such as SQL, MapReduce, OLAP cubes, pi o ables and s a is- ical languages. In he TPC-H decision suppo benchma k, agg ega ions can domina e eigh o he wen y- wo que ies [2]. A simple agg ega ion is shown in Figu e 1; ea nings pe pe sons a e g ouped oge he and a e aged by age. A summa y like his may help he use unco e ends no immedia ely appa en om he aw da a, e.g. i he e is a co ela ion be ween ea nings and age. Fo many yea s, equency scaling was elied upon o achie e be e pe o mance and highe h oughpu in ap- plica ions. This echnique was gene ally anspa en o he p og amme and algo i hms we e expec ed o execu e as e wi h e e y new gene a ion o mic op ocesso . Due o he mal and powe issues, equency scaling came o an end and name age ea nings Hend y 46 €24,000 O'Sulli an 39 €11,000 Da is 58 €24,000 Higgins 40 €10,000 Whi e 53 €15,000 Williams 40 €8,000 Pa o 51 €9,000 Dohe y 45 €6,000 age ea nings (a g) 30-39 €11,000 40-49 €12,000 50-59 €16,000 Figu e 1. Example o an agg ega ion ope a ion. The inpu able on he le is summa ised on he igh . Ea nings a e g ouped by age ange and a e aged. applica ion pe o mance became some hing mo e explici o he p og amme [3]. The clea es way o ackle his is o exploi a ious o ms o pa allelism o gain u he speedups. Recen de elopmen s in mic op ocesso a chi ec u es ha e pushed a ocus on mul i-co e accele a ion. While his is an e ec i e echnique o exploi h ead-le el pa allelism (TLP), single ins uc ion-mul iple da a (SIMD) ins uc ion se s o e a way o accele a e da a-le el pa allelism (DLP), a mo e e icien o m o pa allelism [4], [5]. The e has ypically been some le el o suppo o SIMD ins uc ions in gene al-pu pose mic op oces- so s—commonly dubbed mul imedia ex ensions, e.g. MAX- 1, Al i ec and SSE. Al hough hese ISA ex ensions s a ed ou ela i ely simple, successi e gene a ions ha e become mo e sophis ica ed and o e wide SIMD egis e s o p o- cess mo e elemen s pe ins uc ion as well as mo e in ica e ins uc ions o ope a e on hem. Fo example, In el’s AVX- 512 [6] inc eases he wid h o he egis e s o 512 bi s and includes mask egis e s, ull ga he /sca e suppo and many non- i ial SIMD ins uc ions. This end is an icipa ed o con inue in he u u e, and he SIMD egis e wid h and ins uc ion se s a e expec ed o g ow u he . We p edic ha he SIMD suppo ound in commodi y mic op ocesso s will e en ually esemble he ins uc ion se s o classic ec o a chi ec u es adi ionally ound in supe compu e s [7]. As cu en SIMD suppo is s ill qui e es ic i e, and he ans o ma ion om mul imedia ex ensions o ue ec o suppo is s ill incomple e, he exac po en ial o exploi ing he DLP ound in da a agg ega ions is hi he o unknown. This wo k makes h ee p incipal con ibu ions. (1) We p opose and implemen se e al ec o ised algo i hms o © 2016 IEEE. Pe sonal use o his ma e ial is pe mi ed. Pe mission om IEEE mus be ob ained o all o he uses, in any cu en o u u e media, including ep in ing/ epublishing his ma e ial o ad e ising o p omo ional pu poses,c ea ing new collec i e wo ks, o esale o edis ibu ion o se e s o lis s, o euse o any copy igh ed componen o his wo k in o he wo ks. da a agg ega ion using common ec o SIMD ins uc ions and e alua e hem using a cycle-accu a e simula ion ame- wo k wi h ue ec o suppo . (2) In o de o de e mine he sensi i i y o he inpu o pe o mance, we assess he beha iou o hese algo i hms o a ange o da a dis ibu- ions and ca dinali ies. (3) Le e aging a ecen p oposal o i egula DLP [8], we augmen he simula ion amewo k wi h new ec o ins uc ions and ha dwa e hen assess hei con ibu ion o da a agg ega ion. We hen ex end his ha dwa e wi h minimal addi ions o c ea e new ins uc ions use ul o da a agg ega ions. The e a e se e al no able ou comes o his wo k. Fi s ly, we ind ha he pe o mance o ec o ised da a agg ega ion is immensely dependen on he dis ibu ion and ca dinali y o he inpu . As a consequence, he e is no a single ec o ised algo i hm ha p o ides he bes pe o mance in e e y case. Secondly, we disco e ha ec o ising he algo i hms is no i ial due he i egula i y o he DLP. We p opose wo dis inc ly di e en ypes o solu ions— he i s , e asion, a emp s o a oid his i egula i y h ough ans o ma ion whe eas he second, con on a ion, ackles i head on. The e asion echniques— elying on ypical ec o SIMD ins uc ions—yield speedups only in a subse o he ca dinali ies/dis ibu ions wi h signi ican slowdowns o e he scala baseline in o he cases. On he o he hand, he con on a ion echniques—emb acing he i egula i y wi h new SIMD ins uc ions—achie e speedup o all ca dinal- i ies/dis ibu ions, e en when in some cases esul s a e su passed by an e asion echnique. Finally, since ca dinali y can be de e mined a un ime, we in oduce an adap i e nea - op imal implemen a ion ha selec s he mos app op ia e algo i hm. Ou p oposed ec o implemen a ions exhibi speedups be ween 2.7×and 7.6×o e a scala baseline o a maximum ec o leng h o 64 and ou locks epped lanes. Sec ion II in oduces ou cus om simula ion amewo k. Sec ion III ou lines ou expe imen al se up, he scala base- line and discusses he obs acles ela ed o ec o ising da a agg ega ions. We p opose and e alua e ec o ised e asion echniques in Sec ion IV and ec o ised con on a ion ech- niques in Sec ion V. Rela ed wo k is discussed in Sec ion VI and Sec ion VII concludes he a icle. II. SIMULATION FRAMEWORK Ou goals a e o look a he pe o mance cha ac e is ics o ec o ised agg ega ion algo i hms unning on mic oa chi- ec u es wi h ue ec o suppo as well as p oposing new ins uc ions and ha dwa e o acili a e inno a i e algo i hms. Achie ing hese goals would be impossible i using only exis ing a chi ec u es. Acco dingly, we ha e c ea ed a sim- ula ion en i onmen o conduc he necessa y expe imen s. A i s hea we use PTLsim [9]—a cycle-accu a e x86-64 simula o . PTLsim models many ea u es o mode n ou - o -o de supe scala p ocesso s including µop ansla ion, mul is age pipelines, specula ion and eco e y, and a mul i- ie ed cache hie a chy. We ha e con igu ed he simula o o beha e as close as possible o In el’s Wes me e mic oa - chi ec u e [10]. Table I con ains a ious mic oa chi ec u al pa ame e s used in ou se up. The e a e six execu ion uni clus e s in o al—a load add ess gene a ion clus e ; a s o e add ess gene a ion clus e ; a s o e da a clus e ; and h ee a i hme ic (non-memo y) clus e s. Table I MICROARCHITECTURE PARAMETERS supe scala and ou o o de pa ame e alue pa ame e alue e ch wid h 4 e ch queue 28 on end wid h 4 on end s ages 17 dispa ch wid h 4 w i eback wid h 4 commi wid h 4 eo de bu e 128 issue wid h pe clus e 1 o al issue wid h 6 issue queue pe clus e 8 o al issue queue 48 load queue 48 s o e queue 32 L1-d misses 10 L2 misses 16 cache hie a chy le el size la ency line size ways se s L1-i 32 KB 1 64 4 128 L1-d 32 KB 4 64 8 64 L2 256 KB 10 64 8 512 By de aul , PTLsim uses a ixed la ency memo y sys em ha does no model bandwid h and con en ion issues. Recen wo k on ec o p ocesso s [11] has shown ha hey ha e he abili y o sa u a e a sys em’s a ailable bandwid h, hus making i c ucial o model he memo y sys em accu a ely when execu ing ec o ised algo i hms, o he wise he esul s may be inaccu a e and misleading. Fo his eason, we ha e in eg a ed DRAMSim2 [12]—a cycle-accu a e memo y sys em simula o —in o PTLsim and eplaced he de aul memo y model. Ha ing an accu a e memo y model allows he ec o ised algo i hms o wo k wi hin a ealis ic band- wid h en elope and hus en o ces a ai e compa ison o non- ec o ised algo i hms. Table II shows a ious memo y sys em pa ame e s used in ou se up. The simula ed p o- cesso has a equency o 2.67 GHz so—as a esul — he memo y con olle is clocked e e y ou p ocesso cycles. Addi ionally, he ollowing add ess layou scheme is used as i was ound o wo k well wi h all o ou expe imen s: ow: ank:bank:column:bu s . Table II MEMORY SYSTEM PARAMETERS pa ame e alue pa ame e alue ype DDR3-1333 ansac ion queue 64 clock 1.5 ns command queue 256 policy open page ow accesses 8 queue pe ank pe bank banks 8 scheduling ank hen bank anks 4 ows 32,768 columns 2,048 bu s leng h 64 by es de ice wid h 4 A. Vec o SIMD Suppo We ha e modi ied he simula ion amewo k subs an ially o gi e i ex ensi e ec o SIMD suppo . Fo b e i y, we p o ide a high-le el o e iew ha cap u es he mos impo an ea u es o hese addi ions. We ha e ex ended he x86-64 ISA wi h six een logi- cal ec o egis e s and ou logical mask egis e s. The wid h o hese egis e s is a con igu able pa ame e o he simula o in o de o expe imen wi h di e en maximum ec o leng hs (MVL). As he baseline mic oa chi ec u e uses egis e enaming, we also apply his echnique o he new ec o egis e s. I has been shown ha enaming ec o egis e s is bene icial when he numbe o physical egis e s is double he numbe o logical egis e s [13] hence we p o ide hi y- wo physical ec o egis e s and eigh physical mask egis e s. The e is also an addi ional ec o leng h egis e ha con ols he numbe o elemen s ope a ed on by any gi en ec o ins uc ion. We manage his egis e explici ly using ge /se ins uc ions. The ec o capabili ies a e igh ly in eg a ed in o he mic oa chi ec u e. We ha e added wo new clus e s—one o pe o m he add ess gene a ion o ec o memo y ins uc- ions and ano he o execu e non-memo y ec o ins uc ions. The la e con ains wo unc ional uni s which can execu e independen non-memo y ec o ins uc ions in pa allel. We ha e de ined and implemen ed h ee classes o ec o memo y ins uc ions. Each class co esponds o an access pa e n and suppo s load,s o e and p e e ch ins uc ions. (1) uni -s ide: memo y is accessed con iguously. This is he mos e icien access pa e n due o he spa ial locali y o he elemen s accessed. (2) s ided: memo y ins uc ions use a base add ess and a pa ame e ha e e s o he inc emen in memo y be ween elemen s. (3) indexed: also known as ga he /sca e , hese ins uc ions use a base add ess and an addi ional ec o egis e o o se s. Uni -s ide and s ided ins uc ions calcula e hei ad- d esses o mulaically. The numbe o cycles spen pe o m- ing he add ess gene a ion depends on he numbe o cache lines needed o ul il he eques , e.g. ou cache lines accessed would equi e ou cycles in he unc ional uni . Indexed memo y ins uc ions equi e adding an o se o a base add ess and need V L lanes cycles o pe o m add ess gen- e a ion whe e V L is he ec o leng h o he ins uc ion. The numbe o cycles needed o comple e a memo y ins uc ion depends on how many indi idual cache lines a e eques ed and whe he o no hese a e al eady esiden in he cache hie a chy. Bulding upon an exis ing echnique [14], [15], we con- igu e he ec o egis e ile o bypass he L1-d cache and go di ec ly o he L2 cache. This way mo e bandwid h can be p o ided a he expense o highe la ency. I has been shown in he ci ed wo k ha his ex a la ency is easily amo ised due he high numbe o elemen s ope a ed on pe indi idual ins uc ion. We in e lea e he L2 cache se s using a simple mapping scheme based on i educible polynomials sugges ed in [16], [17]. This scheme elimina es pa hological beha iou whe e a pa icula s ided memo y access uses he same cache se o all i s eques s. To ope a e on he ec o egis e s, we ha e added a sui e o non-memo y ec o ins uc ions which is summa ised in Table III. Mask ins uc ions equi e jus one cycle o comple e. Mos ec o ins uc ions equi e V L lanes cycles o pass h ough a unc ional uni . Reduc ion ins uc ions a e calcula ed sligh ly di e en ly; he e is a pa ial educ- ion local o each lane equi ing V L lanes −1cycles and hen log2lanes addi ional cycles needed o in e lane educ ion. Compa ison ins uc ions p oduce a esul o a mask egis e . The pe mu a i e ins uc ions—which ea ange he o de o he inpu ec o ’s elemen s— equi e a mask ope and, whe eas mos o he ins uc ions can use masks op ionally. io a is an ins uc ion ound in he CRAY-1. Table III NON-MEMORY VECTOR INSTRUCTIONS class ins uc ions ini ialisa ion se all, clea all, io a a i hme ic maximum, add, sub ac , mul iply bi wise logical and, shi le , shi igh compa ison no equal, no equal o ze o mask popcoun pe mu a i e comp ess, expand educ ion maximum, minimum, sum o he ge /se elemen , ge /se len III. EXPERIMENTAL SETUP He e we desc ibe he expe imen al se up. Ou goal is o de ine a ep esen a i e da a-in ensi e agg ega ion que y, implemen i in a a ie y o ways and e alua e he imple- men a ions wi h a di e se ange o pa ame e s. This will help expose he s eng hs and weaknesses o di e en algo i hm designs. Addi ionally, we p esen a scala agg ega ion algo- i hm which we use as a common baseline in subsequen expe imen s. Finally, we discuss he obs acles o ec o ising da a agg ega ion and p opose wo possible solu ion pa hs. A. Que y and Inpu Da a In ou expe imen s, we e alua e he SQL que y in Figu e 2. This ype o que y has been success ully used in p io wo k o e alua e da a agg ega ions [18]–[20]; i s pe o - mance depends highly bo h on he unde lying implemen- a ion as well as he cha ac e is ics o he inpu da a. is a wo-column able wi h n ows consis ing o a 32-bi in ege g oup key gand a 32-bi in ege alue . The esul is a h ee-column ou pu able whe e each ow con ains a g oup, he equency o ha g oup coun and he sum o all alues co esponding o ha g oup sum. We emula e he beha iou o a column-o ien ed da abase managemen sys em (DBMS) in which columns a e s o ed con iguously as a ays in memo y. These ypes o DBMS a e becoming p e alen in la ge da acen es used o online analy ical p ocessing [21]. 1: SELECT g, COUNT(*), SUM( ) 2: FROM GROUP BY g Figu e 2. SQL code used in expe imen s In all he expe imen s, we ix he numbe o inpu ows n a 10,000,000. This alue is su icien o ep esen beha iou indica i e o non-cache esiden da ase s while also being small enough o simula e o comple ion in a easonable ime ame. The alue column is a uni o m dis ibu ion in he in e al [0,9]; since his column does no di ec ly a ec he pe o mance o he di e en algo i hms, i emains cons an in all expe imen s. We gene a e 110 a ia ions o he g oup column gby a ying he dis ibu ion and ca dinali y co he da a. We use i e unique da a dis ibu ions simila o he ones used by Cieslewicz e al. [18]. (1) uni o m: a pseudo- andom selec ion in he in e al [0, c)wi h equal p obabili y. (2) so ed: a p eso ed uni o m dis ibu ion. (3) sequen ial: a epea - ing sequence {0,1,2, ..., c −1}. (4) hhi e : simila o uni o m howe e 50% o he da a is a single hea y hi ing alue. (5) zip : a pseudo- andom selec ion in he in e al [0, c)wi h a Zip ian p obabili y. The e a e 22 possible ca dinali ies c∈ {10,000,000, 5,000,000,2,500,000,...,38,19,9,4}. Due o he na- u e o each dis ibu ion, c ep esen s a maximum possible ca dinali y a he han a gua an eed ca dinali y. Fo example, i is no always possible o gene a e a Zip ian dis ibu ion whe e |g|=c, he e o e— o zip —c ep esen s he uppe bound o he domain in which we sample om a he han a s ic ca dinali y. sequen ial is he only dis ibu ion whe e cgua an ees bo h a maximum and an ac ual ca dinali y in e e y case. Unless o he wise s a ed, ca dinali y e e s o his uppe bound. Fo he sake o discussion, we g oup he ca dinali ies in o ou di isions. (1) low ca dinali ies [4,...,152], e.g. gende o a pe son. (2) low-no mal ca dinali ies [305,...,9,765], e.g. da e o bi h o a clien . (3) high-no mal ca dinali ies [19,531,...,312,500], e.g. a zip o pos al code. (4) high ca dinali ies [625,000,...,10,000,000], e.g. a passpo numbe . We assume ha he applica ion has a p io i knowledge ha he so ed da ase s a e al eady o de ed and hus a oids he o e head o eso ing. This is no mal in DBMSs in which simila me ada a is used o choose be ween al e na i e algo i hms and make op imisa ions. This assump ion also helps iden i y pe o mance ends independen o a so ing phase. In some agg ega ion echniques, i is use ul o de ec he maximum g oup key and use i o imp o e he algo i hm’s un ime beha iou . In algo i hms wi h a so ing phase—o i he inpu is p eso ed— he maximum g oup key is simply he las alue in he a ay. In algo i hms wi hou a so ing phase—excluding p eso ed inpu —we loca e an exac max- imum g oup key by scanning he en i e a ay g. We ind ha his adds li le o e head compa ed o he agg ega ion i sel , howe e , i could be eplaced wi h sampling and some addi ional checks. Since we a e al eady looking a many a iables, we ix he ec o pa ame e s a MV L = 64 and lanes = 4. These pa ame e s we e shown o be easonable in ecen ec o wo k [8], [11]. They also ep esen a con igu a ion ha we an icipa e could e en ually appea on he ma ke gi en cu en ends. We epo all ou esul s using cycles pe uple (CPT)— he o al numbe o cycles needed o execu e he algo i hm di ided by he o al numbe o inpu uples n. B. Scala Baseline He e we in oduce he baseline algo i hm scala , designed wi hou any ec o SIMD ins uc ions. We di ide i s imple- men a ion in o ou s eps. (1) Find he highes alue, maxg, s o ed in he a ay g. (2) Clea maxg +1 cells o he ou pu ables coun and sum. (3) Agg ega e he inpu a ays g and o ou pu ables coun and sum. Pseudocode o his s ep is shown in Figu e 3. (4) Comp ess he uples o emo e absen g oups wi h NULL esul s. 1: o each i in n do 2: coun [g[i]]++; 3: sum[g[i]] += [i]; 4: end o Figu e 3. Pseudocode o s ep 3 o scala The esul s a e shown in Figu e 4. Fo all da ase s, he pe o mance is simila in low and low-no mal bu hen changes d as ically en e ing high-no mal. When c= 9,765, he L1-d cache capaci y o 32 KB is exceeded. A his poin hhi e ,uni o m and zip inc ease hei CPT in ensely; uni o m alone exhibi s a d ama ic 8×inc ease in CPT. This beha iou is no su p ising as a uni o m dis ibu ion exhibi s poo locali y when he bookkeeping s uc u es exceed he cache size. In con as , so ed does no ake any signi ican hi in pe o mance in high-no mal as ha ing he uples p eso ed in oduces a lo mo e locali y. This e ec wea s o in high and so ed expe iences a s eep slope in i s CPT as well. sequen ial ollows a simila pa e n o so ed al hough sligh ly inc eases i s CPT in high-no mal. A e p ocessing he i s 9,765 uples ou o n, he L1-d cache will be illed and p ocessing subsequen uples causes di y line e ic ions hus educing he memo y sys em’s pe o mance. These e ic ions can occu wi h so ed as well, bu unlike sequen ial, he e will be epea ed alues s o ed adjacen ly causing mo e locali y. This beha iou would sugges ha so ing all he da ase s will lead o be e pe o mance, howe e , he cos o doing his wi h a scala ISA would be e y high—especially o a la ge n. 0 15 30 45 60 75 90 105 120 135 4 9 19 38 76 152 305 610 1,220 2,441 4,882 9,765 19,531 39,062 78,125 156,250 312,500 625,000 1,250,000 2,500,000 5,000,000 10,000,000 low low-no mal high-no mal high cycles pe uple hhi e sequen ial so ed uni o m zip Figu e 4. Resul s o scala baseline C. DLP and Vec o isa ion Da a-le el pa allelism (DLP) is accomplished when he same ope a ions a e applied o mul iple elemen s o homo- geneous da a, i.e. a ec o o da a. DLP can be achie ed by le e aging a ec o SIMD ins uc ion se such as he one desc ibed in Sec ion II-A. We u he ca ego ise DLP as ei he egula o i egula . Regula DLP is a o m o DLP in which esul io a ec o p ocedu e depends only on elemen io i s inpu ec o s’ ope ands, i.e. e e y elemen is independen . A ypical ec o SIMD ins uc ion se is gene ally gea ed owa ds egula DLP. I egula DLP can be de ined as DLP whe e esul io a ec o p ocedu e depends on elemen io i s inpu ec o s’ ope ands and may addi ionally depend on o he esul s o he ec o p ocedu e. I is s ill DLP as he same ope a ions a e applied uni o mly on all da a, howe e , he esul o one ac ion may depend on he ou come o ano he ac ion wi hin he same uni o wo k, e.g. SIMD ins uc ion. Ou e e ence scala baseline is a ela i ely s aigh o - wa d algo i hm ha makes use o ables. Ne e heless—due o he i egula i y o he DLP— he e a e nume ous obs acles when ec o ising he code. Upda ing a able is accomplished by—(a) an indexed load o he able (b) modi ying he alue (c) an indexed s o e o he able. In a SIMD model o compu a ion, his ansla es o—(a) ga he ing mul iple able en ies o a ec o egis e (b) modi ying he ec o o loaded alues (c) sca e ing he modi ied alues back o he able. I he indices used in he ga he /sca e ope a ions a e no unique, i.e. con lic ing, he beha iou is unde ined and upda es can be los causing e oneous ou pu . We e e o his as a ga he -modi y-sca e (GMS) con lic . The e a e wo possible ways o ackle his. One is o e ade he i egula i y by ans o ming he p oblem in o some hing mo e egula and hen ec o ising i . The o he is o con on he i egula i y di ec ly h ough he use o no el ins uc ions. In Sec ion IV we e alua e ou e asion solu ions and in Sec ion V we e alua e ou con on a ion solu ions. IV. EVASION TECHNIQUES In his sec ion, we p opose and e alua e wo al e na i e ec o isable solu ions using ypical ec o SIMD ins uc- ions. A. S anda d So ed Reduce His o ically, ec o a chi ec u es ha e o e ed some sup- po o agg ega ing ec o s o scala s in he o m o educ- ion ins uc ions [22]. A educ ion ins uc ion akes a single ec o egis e as inpu , applies an associa i e/commu a i e ope a ion o all i s elemen s, and ou pu s a single educed scala alue. Figu e 5 shows an example o a sum e- duc ion ope a ion pe o med on a ec o egis e o eigh elemen s. The e a e wo pa allel locks epped lanes ha each p ocesses ou elemen s in h ee cycles ollowed by one ex a (log2lanes) cycle o in e lane educ ion. We classi y educ ions as semi- egula DLP ins uc ions. They a e no comple ely egula because he ou pu elemen depends on mo e han inpu elemen i, ye , hey a e no i egula ei he as he e is a single ou pu alue and, he e o e, ou pu elemen idoes no depend on any o he ou pu elemen . 1 5 10 26 2 3 4 6 7 8 + + + + + + 36 + Figu e 5. Sum educ ion when V L = 8 and lanes = 2 We e alua e he bene i o using hese ypes o ins uc ions in da a agg ega ion. I he inpu is so ed, ec o educ ion ins uc ions can be used di ec ly. I no , he inpu mus be so ed i s . Ou algo i hm is as ollows. (1) I no al eady so ed, gis so ed using as he associa ed payload. (2) The so ed gis scanned o uns o epea ed keys. Runs can be ound by i s compa ing g[i] wi h g[i+1] o gene a e ec o masks. The dis ance be ween se bi s in hese ec o masks co esponds o he leng h o a un. These leng hs also co espond o he elemen s o he ou pu column coun . (3) The un leng hs a e used o load and educe segmen s o . Run leng hs ha exceed he MVL a e s ipmined. To so he inpu a ays in s ep 1 we choose adix so [23]. I is a good ma ch o his algo i hm o se e al easons. Fi s ly, i is ec o isable using ypical ec o SIMD ins uc ions. Secondly, ecen wo k [8] demons a ed ha i ou pe o ms quickso and bi onic me geso when MV L = 64 and lanes = 4— he same con igu a ion used in his wo k. Thi dly, i has an equal CPT o any inpu size n, hence making i scalable o la ge da ase s. Finally, i can be op imised o a pa icula maximum g oup key he eby educing he cos o so ing any pa icula ca dinali y. The esul s o s anda d so ed educe e alua ed wi h all da a dis ibu ions and ca dinali ies a e shown in Figu e 6. To make compa isons easie , we keep he scale o he y-axis he same as he scala baseline o all ec o expe imen s. In Table IV, a summa y is gi en o he o e all pe o mance by aking he a e age speedup (and s anda d de ia ion) o e scala o each ca dinali y di ision. Highligh ed cells indica e ha his is he bes a e age pe o mance so a o ha pa icula combina ion o da ase and ca dinali y di ision. so ed is he only da ase ha does no cause addi ional so ing o e head, as such, we see he cos o he agg ega ion s ep i sel . I s pe o mance is consis en o low,low-no mal and high-no mal bu hen diminishes in high. The inc easing ca dinali y causes he a e age un leng h o dec ease and se ialises he algo i hm he eby unde u ilising he ec o uni . In mos cases, i can be seen ha hhi e ,sequen ial, uni o m and zip show slowdowns o e scala ; only uni o m exhibi s a 1.1×a e age speedup o high. These slowdowns a e due o he o e head o so ing he inpu which o en exceeds he o al cos o scala . Al hough being he mos e icien SIMD so ing algo- i hm, adix so mus unde go signi ican ans o ma ions o be ec o ised. The ec o ised algo i hm su e s om wo majo bo lenecks. (1) In o de o a oid GMS con lic s, i s in e nal bookkeeping s uc u es need o be eplica ed by he numbe o elemen s in a ec o egis e . (2) To ensu e so ing s abili y, each elemen o a ec o egis e mus p ocess a con iguous po ion o he inpu . To achie e his e ec , he inpu mus be loaded in o a ec o egis e using a s ided memo y access pa e n in lieu o a uni -s ide one. 0 15 30 45 60 75 90 105 120 135 4 9 19 38 76 152 305 610 1,220 2,441 4,882 9,765 19,531 39,062 78,125 156,250 312,500 625,000 1,250,000 2,500,000 5,000,000 10,000,000 low low-no mal high-no mal high cycles pe uple hhi e sequen ial so ed uni o m zip Figu e 6. Resul s o s anda d so ed educe Table IV AVERAGE SPEEDUPS (STDEV)OF s anda d so ed educe OVER BASELINE. HIGHLIGHTED CELLS MARK BEST RESULT SO FAR. low low-no mal high-no mal high hhi e 0.7×(0.1) 0.3×(0) 0.6×(0.2) 0.8×(0.1) sequen ial 0.6×(0.1) 0.3×(0) 0.4×(0.1) 0.3×(0) so ed 5.1×(0) 5.1×(0) 5.2×(0.1) 2.7×(1) uni o m 0.6×(0.1) 0.3×(0) 0.8×(0.4) 1.1×(0.1) zip 0.6×(0.1) 0.3×(0) 0.5×(0.1) 0.7×(0.1) B. Poly able I is also possible o make a ec o ised ansla ion o scala using ec o SIMD ins uc ions. S eps 1, 2 and 4 can be ec o ised di ec ly using ypical SIMD ins uc ions, howe e , in a simila ein o adix so , he hi d s ep equi es ans o ma ion. To ci cum en GMS con lic s, we mus eplica e he ou pu ables coun and sum o e e y elemen o a ec o egis e , i.e. he e a e MV L independen e sions o each able. Figu e 7 shows he p ocess o inc emen ing he coun able when MV L = 4. In he igu e, inpu a ay g is a anged in blocks o consecu i e MV L elemen s. The elemen s wi h do ed pa e ns ha e al eady been p ocessed. The highligh ed alues a e cu en ly being used o upda e he able. In his case i can be seen ha he e a e mul iple ins ances o he alue 3 in he ec o egis e ( eg). This duplica ion would cause a GMS con lic i a single able we e used, howe e , since each ec o elemen accesses a local copy, we a oid con lic s en i ely. 1 3 3 0 0 5 2 4 inpu : g 1 3 3 0 eg 1 0 0 0 1 0 0 0 0 0 2 0 0 0 0 1 coun copy g oup key 1 4 2 3 0 1 3 2 0 1 32 0 1 0 1 4 0 1 0 0 5 +1 +1 +1 +1 Figu e 7. Table eplica ion used o a oid GMS con lic s A e he inpu has been p ocessed, he local copies o coun and sum mus be educed o singula global ables. MV L consecu i e elemen s—which o m a single g oup—a e loaded in o he ec o egis e ( eg) ha is hen summed oge he using a educ ion ins uc ion. This local o global educ ion is illus a ed in Figu e 8. 1 0 0 1 2 0 0 0 0 0 2 0 0 1 1 1 0 1 0 1 0 1 0 0 2 2 2 3 2 0 1 0 1 + g oup key 0 1 3 2 4 5 coun copy 0 1 32 eg coun 0 1 3 2 4 5 Figu e 8. Local ables a e educed o a single global able The esul s o poly able a e shown in Figu e 9 and Table V. Fo low, all da ase s exhibi a posi i e speedup. Due o he a angemen o he able s uc u es, so ed shows he bigges imp o emen and sequen ial exhibi s he leas imp o emen . This is due o he layou o he MV L able copies. Replica ions a e s o ed con iguously in memo y, i.e. he cell o g oup k’s local copy iis adjacen in memo y o copy i+1. Since so ed con ains long uns o he same g oup, he numbe o cache lines accessed is minimal. In con as , sequen ial has he opposi e beha iou . The da ase s ha e uns o ascending g oups which causes a s ided memo y access pa e n whe e he s ide is MV L+1 elemen s, i.e. a diagonal access h ough he s uc u e. Since he MV L is la ge han he numbe o elemen s in a cache line, MV L cache lines will be accessed wi h e e y memo y ins uc ion. All o he da ase s exhibi pe o mance be ween hese wo ex emes. A e low, he pe o mance begins o dec ease. Simila o he scala baseline, he ables g ow la ge han wha he cache can accommoda e and pe o mance d ops. In his case, eplica ing he ables causes he de e io a ion o happen soone . In he scala baseline, his ansi ion occu s when c= 9,765 whe eas he e i happens when c= 152 which is six y- ou — he MVL— imes smalle han he o me . Fo hhi e ,sequen ial,uni o m and zip he esul s a e always wo se han scala .so ed con inues o ou pe o m scala in low-no mal and high-no mal due o he spa ial locali y o i s accesses, howe e , in high, i de e io a es and becomes wo se han scala . A sligh ly su p ising esul he e is ha o so ed,low and low-no mal ou pe o m hei coun e pa s in s anda d so ed educe. This due o an unigno able o e head incu ed when scanning he inpu o build he a ay o un leng hs. 0 15 30 45 60 75 90 105 120 135 4 9 19 38 76 152 305 610 1,220 2,441 4,882 9,765 19,531 39,062 78,125 156,250 312,500 625,000 1,250,000 2,500,000 5,000,000 10,000,000 low low-no mal high-no mal high cycles pe uple hhi e sequen ial so ed uni o m zip Figu e 9. Resul s o poly able Table V AVERAGE SPEEDUPS (STDEV)OF poly able OVER BASELINE. HIGHLIGHTED CELLS MARK BEST RESULT SO FAR. low low-no mal high-no mal high hhi e 3.7×(0.4) 0.9×(1) 0.8×(0.2) 0.5×(0.2) sequen ial 2.9×(0.4) 0.8×(1) 0.3×(0) 0.2×(0.1) so ed 7.6×(0) 7×(0.6) 2.9×(1.6) 0.4×(0.2) uni o m 3×(0.6) 0.7×(0.9) 0.6×(0.3) 0.6×(0.2) zip 3.3×(0.6) 0.9×(0.7) 0.5×(0.1) 0.4×(0.2) C. Summa y We ha e e alua ed wo dis inc echniques ha ec o ise da a agg ega ions h ough algo i hm ans o ma ion. I he inpu is al eady so ed, he e a e posi i e speedups o be gained using poly able o lowe ca dinali ies and s anda d so ed educe o highe ca dinali ies. Fo non-so ed da a dis ibu ions, i is bene icial o use poly able i he ca dinali y is e y low. Fo o he combina ions o dis ibu ion and ca di- nali y, nei he o hese echniques su ice. These limi a ions a ise due o he ans o ma ions necessa y o ec o ise da a agg ega ion using a ypical ec o SIMD ISA. These indings mo i a e us o explo e o he echniques using no el ec o SIMD ins uc ions which will allow us o ec o ise he algo i hms wi hou hese de imen al ans o ma ions. V. CONFRONTATION TECHNIQUES In his sec ion we look a al e na i e solu ions ha a emp o con on he i egula DLP head on a he han e ade i . A. Ad anced So ed Reduce The ec o ised adix so used in Sec ion IV-A su e s om pe o mance bo lenecks caused by algo i hm ans- o ma ion. Recen wo k on ec o ised so ing algo i hms p oposed VSR so [8]. VSR so is a no el ec o ised im- plemen a ion o adix so ha a oids eplica ing i s in e nal able s uc u es and p ocesses he inpu a ays sequen ially. Con iguous po ions o he inpu a e ead in o ec o egis- e s using an e icien uni -s ide memo y access pa e n; he algo i hm hen sea ches o elemen s ha may cause GMS con lic s and co ec s hem acco dingly be o e accessing he bookkeeping s uc u es. To enable his new algo i hm in a ec o SIMD a chi ec u e, wo new ins uc ions a e equi ed—VPI and VLU. A de ailed explana ion o he VSR so algo i hm is beyond he scope o his a icle, howe e , we p o ide an o e iew o he new ins uc ion and hei ha dwa e implemen a ion as hese pe ain o la e sec ions. 7 5 5 5 11 9 9 11 00120011 1 2 1 1 inou (a) Vec o P io Ins ance (VPI) 7 5 5 5 11 9 9 11 10010011 inou (b) Vec o Las Unique (VLU) Figu e 10. New ins uc ions o VSR So Vec o P io Ins ances (VPI) uses a single ec o egis e as inpu , p ocesses i se ially, and ou pu s ano he ec o egis e as a esul . Each elemen o he ou pu asse s exac ly how many ins ances o a alue in he co esponding elemen o he inpu egis e ha e been seen be o e in he egis e . An example is gi en in Figu e 10a (elemen s a e p ocessed om le o igh ). In each pass o VSR so , a his og am o he inpu is i s c ea ed. Using he alues o he his og am as o se s, he inpu is sca e ed o an auxilia y a ay whe e i s o de becomes pa ially o ully so ed depending on he pass. Since i is possible ha mul iple inpu alues wi hin a SIMD ope a ion may co espond o he same his og am bin, sca e ing hese alues would go o he same loca ion in he auxilia y a ay. To ci cum en his, VPI is used o co ec he o se s going o con lic ing loca ions by ans o ming hem o adjacen loca ions ins ead. Vec o Las Unique (VLU) also uses a single ec o egis e as inpu bu p oduces a ec o mask as a esul . The idea is o ma k he las ins ance o any pa icula alue ound. An example is gi en in Figu e 10b (elemen s a e p ocessed om le o igh ). A bi in he ou pu mask egis e is se i he co esponding alue in he inpu ec o is no seen a e wa ds. In VSR so , VLU is used o selec a non-con lic ing subse o indices o he his og am and inc emen hem based on he numbe o co ec ions made by VPI. Thus, VPI and VLU oge he can be used o inc emen a his og am s uc u e wi hou GMS con lic s. VPI and VLU a e implemen ed using a CAM s uc u e wi h MV L en ies. Figu e 11 illus a es such a se up whe e MV L = 8. An inpu ec o egis e is p ocessed om he leas signi ican elemen (idx = 0) o he mos signi ican elemen (idx = 7). The diag am shows ha six o he eigh elemen s ha e al eady been p ocessed wi h he se en h in p og ess. P ocessing each inpu elemen equi es wo cycles; ac i i y in he i s cycle is shown wi h solid lines and ac i i y in he second is shown wi h b oken lines. In he i s cycle, he inpu alue 9 is used as a key and a alid en y in he CAM is ound. The coun ield o he CAM en y is copied o he co esponding elemen o he ou pu ec o and also ou ed o an inc emen uni . In he second cycle, he esul o he inc emen is w i en back o he coun ield. Simul aneously, he las idx ield o he CAM en y is upda ed wi h he alue 6— he index o he inpu /ou pu en y being p ocessed a ha momen . When all inpu elemen s ha e been p ocessed, he ou pu ec o will con ain he esul s o VPI whe eas VLU can be gene a ed by con e ing he las idx ield o all alid CAM en ies o a bi mask. To educe ins uc ion la ency, he CAM is gi en ppo s. The CAM s uc u e can be upda ed in pa allel p o ided ha a slice o padjacen elemen s o he inpu ec o has no con lic s. Fo mo e de ails he eade is e e ed o [8]. key 7 5 11 9 x x x x las idx 0 3 4 5 x x x x coun 1 3 1 1 0 0 0 0 +1 = = = = = = = = ec o elemen idx 0 1 2 3 4 5 6 7 alid Y Y Y Y N N N N 7 5 5 5 11 9 9 11 in 0 0 1 2 0 0 x x ou Figu e 11. Ha dwa e implemen a ion o VPI and VLU We now e alua e he same algo i hm used in s anda d so ed educe bu eplace adix so wi h VSR so while keeping all o he s eps equal. The esul s a e shown in Figu e 12 and Table VI. Since he so ed da ase can skip he so ing s ep, i s beha iou and pe o mance emain equal o s anda d so ed educe; hese cases a e ma ked wi h a Ξ symbol. Fo hhi e ,sequen ial,uni o m and zip he esul s a e always be e han s anda d so ed educe. The e a e s ill some slowdowns o e scala o low and low-no mal. Despi e he pe o mance o VSR so being be e han adix so , he o e head is s ill oo high o su pass he CPT o scala o lowe ca dinali ies. Fo high-no mal, his o e head becomes less signi ican and we achie e speedups in all cases. Fo high,hhi e ,uni o m and zip con inue o exhibi speedups whe eas sequen ial shows a slowdown. The eason o his is wo old: (1) sequen ial exhibi s good locali y in high o scala he eby ha ing be e pe o mance ela i e o he o he h ee da ase s. (2) The a e age ec o leng h is educed o alues below he MVL in high. Fo example, when c= 10,000,000 he ec o leng h o e e y educ ion is 1 and his educes pe o mance conside ably. This second poin also a ec s hhi e ,uni o m and zip o high, bu o a lesse ex eme han sequen ial. 0 15 30 45 60 75 90 105 120 135 4 9 19 38 76 152 305 610 1,220 2,441 4,882 9,765 19,531 39,062 78,125 156,250 312,500 625,000 1,250,000 2,500,000 5,000,000 10,000,000 low low-no mal high-no mal high cycles pe uple hhi e sequen ial so ed uni o m zip Figu e 12. Resul s o ad anced so ed educe Table VI AVERAGE SPEEDUPS (STDEV)OF ad anced so ed educe OVER BASELINE. HIGHLIGHTED CELLS MARK BEST RESULT SO FAR. low low-no mal high-no mal high hhi e 1×(0) 0.9×(0) 2×(0.7) 1.8×(0.4) sequen ial 1×(0) 0.9×(0.1) 1.2×(0.1) 0.7×(0.2) so ed 5.1×(0) Ξ 5.1×(0) Ξ 5.2×(0.1) Ξ 2.7×(1) Ξ uni o m 0.9×(0.1) 0.8×(0) 2.7×(1.4) 2.7×(0.7) zip 1×(0.1) 0.8×(0) 1.5×(0.4) 1.6×(0.2) B. Mono able One p oblem wi h he poly able app oach o Sec ion IV-B is ha he able eplica ion des oys any locali y ha may o he wise be p esen in he scala baseline. He e we p opose an al e na i e implemen a ion called mono able ha d aws om he no el ins uc ions used in ad anced so ed educe. VPI and VLU use a ha dwa e implemen a ion based on a CAM and adde . We p opose eusing his ha dwa e s uc u e and building new unc ionali y on op. We de ine a new se o ins uc ions called Vec o G oup Agg ega e (VGAx) ha can aid us u he when ec o ising da a agg ega ion. The e a e h ee ope a ions suppo ed which o m new ins uc ions: sum (VGAsum), minimum (VGAmin) and maximum (VGAmax). Each VGAx ins uc ion uses wo egis e s as inpu —a ec o o g oups ing and a ec o o alues in . The ins uc ions p oduce a ec o ou o unning pa ial agg ega es among alues o he same g oup. We can implemen hese ins uc ions wi h ela i ely mino addi ions o he ha dwa e al eady in place o VPI and VLU. As an example, we desc ibe VGAsum. The seman ics a e illus a ed in Figu e 13 and he implemen a ion is shown in Figu e 14. Fo each inpu elemen , ins ead o inc emen ing i s CAM en y by one as would be done wi h VPI, he en y is summed wi h he co esponding alue in in . The seman ics esemble VPI whe e i s alues would be a ec o o 1s, howe e , an impo an di e ence is ha he ou pu o VPI comes om he CAM en y’s alue be o e he inc emen whe eas he ou pu o VGAsum is aken a e he inc emen . 6 3 4 9 15 2 3 4 6 3 7 16 15 2 5 19 3 7 2 15 in ou ing 7 5 5 5 11 9 9 11 Figu e 13. Seman ics o he VGAsum ins uc ion key 7 5 11 9 x x x x las idx 0 3 4 5 x x x x sum 616 15 2 0 0 0 0 + = = = = = = = = ec o elemen idx 0 1 2 3 4 5 6 7 alid Y Y Y Y N N N N 6 3 4 9 15 2 3 4 in 6 3 7 16 15 2 x x ou 7 5 5 5 11 9 9 11 ing Figu e 14. Ha dwa e implemen a ion o VGAsum We use VGAsum o build a ec o ised e sion o scala using non- eplica ed ables wi h no GMS con lic s. Combin- ing VGAsum wi h VLU allows us o upda e a single able in pa allel. Figu e 15 shows he pseudocode o his s ep. The masked sca e ins uc ion could op ionally be eplaced wi h a comp ess ollowed by a non-masked sca e . 1: ~ 2← gasum( ~ 0,~ 1).g oups in ~ 0& alues in ~ 1 2: m0← lu( ~ 0) 3: ~ 3←ga he (base= able,idx=~ 0,mask=m0) 4: ~ 4← add( ~ 2,~ 3) 5: sca e (base= able,idx=~ 0, als=~ 4,mask=m0) Figu e 15. Pseudocode o upda ing a able using VGAsum Figu e 16 and Table VII show he esul s o mono able. The g aph esembles he ends ound in scala (see Figu e 4) bu wi h lowe CPTs. Fo low,mono able exhibi s good pe o mance o hhi e ,sequen ial,uni o m and zip and ou pe - o ms poly able— he only e asion me hod ha was use ul o his ca dinali y di ision. so ed is no as as as poly able o low and low no mal, which is unde s andable since he majo i y o he VGAsum ins uc ion’s inpu will cause CAM po con lic s and, he e o e, pay he maximum la ency. In con as , mono able ou pe o ms poly able in all cases o so ed in high-no mal and high. I can be seen ha mono able has consis en pe o mance o lowe ca dinali ies, bu o highe ca dinali ies hhi e , sequen ial and uni o m become wo se whe eas sequen ial and so ed emain ela i ely s able. This beha iou is ela ed o he locali y o memo y accesses. When c≤9,765, he da a s uc u es can eside ully in he L2 cache. When his ca dinali y is exceeded—depending on he dis ibu ion o he da a—i may des oy he locali y. Despi e his be- ha iou , all he da ase s in he highe ca dinali ies exhibi a posi i e speedup and bea he poly able me hod in e e y case. Compa ed wi h ad anced so ed educe, some imes he pe o mance is be e and some imes wo se. 0 15 30 45 60 75 90 105 120 135 4 9 19 38 76 152 305 610 1,220 2,441 4,882 9,765 19,531 39,062 78,125 156,250 312,500 625,000 1,250,000 2,500,000 5,000,000 10,000,000 low low-no mal high-no mal high cycles pe uple hhi e sequen ial so ed uni o m zip Figu e 16. Resul s o mono able C. Pa ially So ed Mono able We obse e ha mono able wo ks pa icula ly well o he lowe ca dinali ies. Fo highe ca dinali ies, some o he da ase s lose hei cache locali y and exhibi apid inc eases in CPT. so ed and sequen ial— he da ase s ha do no lose hei locali y—main ain mo e consis en beha iou . We es ima e ha o achie e he op imal beha iou o mono able,