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,