Compe i i e cos -e ec i e memo y access p edic o h ough sho - e m
online SVM and dynamic ocabula ies
Pablo Sanchez-Cue as a,b,∗,Fe nando Diaz-del-Rio a,b,c,Daniel Casanue a-Mo a o a,b,
An onio Rios-Na a o a,b,c
aRobo ics and Technology o Compu e s Lab, Uni e sidad de Se illa. A enida Reina Me cedes s/n, 41012 Se illa, Spain
bSma Compu e Sys ems Resea ch and Enginee ing Lab (SCORE), Uni e sidad de Se illa. A enida Reina Me cedes s/n, 41012 Se illa, Spain
cResea ch Ins i u e o Compu e Enginee ing (I3US), Uni e sidad de Se illa. A enida Reina Me cedes s/n, 41012 Se illa, Spain
A R T I C L E I N F O
Keywo ds:
Add ess p edic ion
Suppo ec o machines
Memo y access
Supe scala p ocesso s
Machine lea ning
A B S T R A C T
In ecen yea s, he e has been a signi ican inc ease in he p ocessing o massi e amoun s o da a, d i en by
he g owing demands o mobile sys ems, pa allel and dis ibu ed a chi ec u es, and eal- ime sys ems. This
applies o a ious ypes o pla o ms, bo h speci ic and gene al-pu pose. Despi e nume ous ad ancemen s in
Compu e Sys ems, a c i ical challenge emains: he e iciency and speed o memo y access. This bo leneck is
being add essed h ough cache p e e ching, ha is, by p edic ing he nex memo y add ess o be accessed and
hen by ha ing always p e e ched in he cache sys em hose da a o be used sho ly by he p ocesso . This pape
explo es es ablished in elligen echniques o add ess p edic ion, examining hei limi a ions and analyzing
he memo y access pa e ns o popula so wa e applica ions. Building on he successes o p e ious in elligen
p edic o s based on Machine and Deep Lea ning models, we in oduce a new p edic o , SVM4AP (Suppo
Vec o Machine Fo Add ess P edic ion), designed o o e come he iden i ied d awbacks o i s p edecesso s.
The a chi ec u e o SVM4AP imp o es he ade-o be ween pe o mance and cos , compa ed o hose p e ious
p oposals in he li e a u e, achie ing high accu acy h ough sho - e m lea ning. Compa isons a e made wi h
wo p ominen p edic o s om he li e a u e: he classical DFCM (Di e en ial Fini e Con ex Me hod) and
he con empo a y Deep Lea ning-based DCLSTM (Doubly Comp essed Long-Sho Te m Memo y). The esul s
demons a e ha SVM4AP achie es supe io cos -e ec i eness ac oss a ious con igu a ions. Simula ions e eal
ha SVM4AP con igu a ions domina e bo h DFCM and DCLSTM coun e pa s, o ming he majo i y o he i s
Pa e o on . Pa icula ly no ewo hy is he signi ican ad an age o ou p oposal o small-size p edic o s.
Fu he mo e, we elease an open-sou ce ool enabling he scien i ic communi y o ep oduce he esul s
p esen ed in his pape using a se o benchma k aces.
1. In oduc ion
Today’s socie y is inc easingly dependen on compu ing o pe o m
a ious ac i i ies and sol e p oblems, bu a he same ime, compu ing
has become mo e di icul o suppo and manage due o i s di e si y
and sophis ica ion. The aim is o expand he eno mous se o se ices
p o ided by la ge in as uc u es such as he In e ne , in addi ion
o in eg a e A i icial In elligence unc ionali ies: op imiza ion o p o-
cesses and esou ces, compu e ision, pa e n ecogni ion, in elligen
gene a ion o mul imedia con en , e c. Mo eo e , he aim is o apply
hese equi emen s in all kinds o scena ios, p o ided no only by
gene al-pu pose compu e s bu also by speci ic-pu pose sys ems wi h
signi ican cons ain s.
∗Co esponding au ho .
Compu e a chi ec s undoub edly ace g ea challenges and g ea
oppo uni ies in his con ex . In esponse o compu a ional demand,
many new a chi ec u es ha e been p oposed ha exploi all le els
o pa allelism and imp o e e iciency. Examples in ecen yea s in-
clude SoCs (Sys em on Chip), TPUs (Tenso P ocessing Uni s), and IoT
(In e ne o Things) ne wo ks, among o he s.
Ano he on o e olu ion has been mic oa chi ec u e. Among o he
issues, memo y access emains one o he bigges bo lenecks [1].
His o ically, memo y hie a chies, in gene al, and cache sys ems, in
pa icula , ha e alle ia ed his p oblem bo h o he CPU and o
o he sys ems and de ices, e.g., in he case o non- ola ile s o age [2].
E en so, echniques such as p e e ching, which consis s o p eloading
E-mail add esses: [email p o ec ed] (P. Sanchez-Cue as), [email p o ec ed] (F. Diaz-del-Rio), [email p o ec ed] (D. Casanue a-Mo a o), [email p o ec ed]
(A. Rios-Na a o).
h ps://doi.o g/10.1016/j. u u e.2024.107592
Recei ed 30 Janua y 2024; Recei ed in e ised o m 3 July 2024; Accep ed 30 Sep embe 2024
P. Sanchez-Cue as e al.
he mos likely da a o be used by he p ocesso a pos e io i, ha e
been in eg a ed o op imize hese sys ems [3]. Howe e , gi en he de-
mand o massi e da a compu a ion, his bo leneck equi es addi ional
op imiza ions.
Following he success o b anch p edic o s, e.g., TAGE [4], alue
p edic o s suppose an op imiza ion o memo y usage, which allows
p edic ing he inal alue o a memo y ead ins uc ion [5]. Thanks o
hese p edic o s, ins uc ions can be execu ed specula i ely, a oiding
he wai ing ime o a p io memo y access ins uc ion. A a ian o
such alue p edic o s is access p edic ion, which aims a p edic ing he
memo y add ess used by a memo y ead o w i e ins uc ion.
The la e echnique is now widely used o a much mo e e ec i e
and accu a e p e e ching, since memo y access pa e ns hold a high
s a is ical au o-co ela ion in mos p og ams and algo i hms [6]. In
pa icula , he aim is o always ha e p e e ched in he cache sys em all
he da a o be used by he p ocesso . In addi ion, his would allow us o
inse (specula i ely) he p e e ched da a di ec ly in o he p ocesso ’s
execu ion engine, hus being able o apply alue specula ion [7].
Due o he impo ance o access p edic ion, in his pape , we p o-
pose a no el p edic ion model called Suppo Vec o Machine Fo
Add ess P edic ion (SVM4AP), which esul s in a subs an ial imp o e-
men in cos -e ec i eness compa ed o he classical Di e en ial Fini e
Con ex Me hod (DFCM) p edic o and he ecen Doubly Comp essed
Long-Sho Te m Memo y (DCLSTM). The main ac o s ha suppo his
di e ence a e he use o a high lea ning a e SVM model, he mapping
o add ess del as in a dynamic dic iona y, and he lowe capaci y
equi ed o SVM4AP’s modules, esul ing in a p edic o ha achie es
high p ecision based on he sho - e m lea ning o access pa e ns.
Indeed, bo h simple and complex access pa e ns a e cap u ed by he
lea ning model ( he SVM) easily by p edic ing, no o e he p e ious
del as, bu a he o e he dic iona y classes hese a e mapped.
In summa y, he main con ibu ions o ou p oposal a e as ollows.
•We p opose he SVM4AP p edic o based on h ee main compo-
nen s: (1) an inpu bu e ha eco ds he con ex o each memo y
access ins uc ion; (2) a linea SVM ha , gi en he access his o y,
p edic s he nex add ess del a as a dic iona y class; and (3) a iny
dic iona y ha indexes each class o a del a.
•We success ully ackle ull-dynamism by designing ou p oposal
whe e, in con as o o he Machine and Deep Lea ning s a e-
o - he-a coun e pa s, he SVM pe o ms online lea ning, plus
he non-s a ic dic iona y is main ained ia an LFU eplacemen
policy.
•We pe o m quan i a i e compa isons wi h he s a e-o - he-a
DFCM and DCLSTM p edic o s, showing in bo h cases a clea
imp o emen in e ms o cos -e ec i eness.
•We elease an open-sou ce implemen a ion o he p esen ed ex-
pe imen s, om which he scien i ic communi y can ep oduce
he esul s and/o de elop hei own add ess p edic o s.
In Sec ion 2, he cha ac e is ics o bo h classical and no el p e-
dic o s a e explo ed. In Sec ion 3 he cha ac e is ics o he usual
memo y access pa e ns and hei ela ions wi h he p edic o s a e
desc ibed. In Sec ion 4design imp o emen s conce ning p edic o s
om he li e a u e a e discussed, leading o he design p oposed in
Sec ion 5. Sec ion 6speci ies he es sui e o e alua e he pe o mance
o SVM4AP conce ning DFCM and DCLSTM. Finally, he conclusions
and ideas o u u e wo k a e summa ized in Sec ion 7.
2. Rela ed wo ks
Mos o he classical me hods pe o m add ess p edic ion by im-
plemen ing a able-based alue p edic o : he in e media y o inal
p edic ion alues a e s o ed in di e en ables and a e indexed by a
ea u e associa ed wi h he co esponding memo y access ins uc ion.
The Las Value P edic o (LVP, Gabbay and Mendelson [8]) is one
o hese cases, o which a single able is implemen ed and e u ns a
p edic ed add ess gi en he P og am Coun e (PC) o a memo y access
ins uc ion.
Ano he p edic o o in e es is he DFCM [9], which is o be used
as a baseline o compa isons in his wo k.
The DFCM p esen s wo sepa a e ables: a i s one (called Value
His o y Table o VHT) accessed by he PC o he memo y ead/w i e
ins uc ion ha e u ns a hash alue and he add ess o he p e ious ac-
cess o he same ins uc ion; and a second one (called Value P edic ion
Table o VPT) accessed by he hash alue ob ained om he i s able
and e u ns he s ide o del a (di e ence be ween wo consecu i e
accessed add esses) ha is summed wi h he add ess o he p e ious
access, esul ing in he p edic ed add ess.
A inal example o a able-based p edic o o ele ance is he Value
TAgged GEome ic [10], which was de eloped om he TAGE b anch
p edic o [4]. I ea u es a global b anch his o y ha is hashed wi h
he PC o he memo y access ins uc ion in o de o index a sequence
o ables, each s o ing alue p edic ions. Among he p edic ions gi en
by he ables, he one indexed by he highes numbe o global b anch
his o y bi s is selec ed.
These classical p edic o s ha e he ad an age o being simple and
ha ing low ha dwa e cos , incu ing a la ency equal o he ime
equi ed o ob ain he inal esul s om he ables. Howe e , his
memo y-based mapping comes wi h a pe o mance ha is highly de-
penden on hose mos possible access con ex s ha a e s o ed in a able
o limi ed capaci y. The e o e, he pe o mance o classical p edic o s
is highly dependen on memo y cos and complexi y and dispa i y o
he access con ex s o a gi en p og am [11].
No el me hods y o o e come such es ic ions by implemen ing
he mapping unc ion using a Machine Lea ning model. This ollows a
ema kable e olu ion in Compu e A chi ec u e o mechanisms such as
b anch p edic ion [12], cache euse p edic ion [13], cache eplacemen
policy [14], and e en mic oa chi ec u al malwa e de ec ion [15]. As
hese wo ks s a e, he applica ion o a Machine Lea ning model allows
a conside able imp o emen due o i s high p ecision in ecognizing
linea and nonlinea pa e ns, which usually su pass he pe o mance
o classical me hods.
Cache p e e ching, closely ela ed o memo y add ess p edic ion,
has also le e aged he po en ial o Machine Lea ning. In he las
yea s, some Rein o cemen Lea ning-based p e e che s o ele ance
ha e eme ged, like Be a e al. [16], Ge ogiannis and To ellas [17],
Yang e al. [18] and Huang and Wang [19]. These p e e che s can
il e and egula e p e e ching h ough hei ewa d sys em, which
is dependen on measu ing eal- ime, pe o mance-wise in o ma ion
such as memo y bandwid h o p e e ching imeliness. This app oach
imp o es p e ious s a e-o - he-a con idence mechanisms.
Wi h espec o add ess p edic ion, he e is a majo end in wo ks
ha p opose Recu en Neu al Ne wo ks (RNNs) o empo al locali y-
based p e e ching by le e aging p edic ing cache accesses o cache
misses. Speci ically, many Long Sho Te m Memo y (LSTM)-based
p oposals ha e been in oduced in he las yea s, such as Zeng and Guo
[20], Shi e al. [21], B aun and Li z [22], Gan u e e al. [23]. Some
pa icula examples o in e es o his pape a e Hashemi e al. [24],
S i as a a e al. [25] and Zhang e al. [26], which p opose an LSTM-
based RNN as he classi ica ion model, and whe e each add ess del a is
p edic ed as a alue associa ed o a wo d (class e u ned by he classi-
ie ) and s o ed in a s a ically, o line i ed ocabula y/dic iona y. This
allows his model o conside ably educe i s ou pu space. The DCLSTM
is one o he main con ibu ions in his ega d, which is o med by
one Embedding laye , one LSTM laye , and one o wo ully connec ed
laye s. In o de o sa e up a signi ican amoun o ne wo k size, bo h
inpu and ou pu a e dic iona y wo ds ha a e no one-ho encoded bu
a he encoded in bina y numbe s.
A complex model, like he LSTM-based RNN, enables he p edic o
o lea n all so s o access pa e ns, minimizing he possible impac
o acing complex con ex s, in con as o he able-based p edic o
coun e pa . Howe e , his comes a he p ice o ha ing conside able
Fu u e Gene a ion Compu e Sys ems 164 (2025) 107592
2
P. Sanchez-Cue as e al.
ha dwa e cos s bo h on he weigh s ma ix ha hese models usually
include and on he se o linea and non-linea ope a ions ( equi ed o
p ocess con ex ea u es and in e media e esul s).
O he wo ks, such as Peled e al. [27], app oach p edic ion as a
eg ession p oblem om con ex ual p og am in o ma ion [28] oge he
wi h adi ional a chi ec u al memo y in o ma ion (PC, miss his o y,
and b anch his o y). They use his da a o ain a neu al ne wo k o
lea n he pa e ns o memo y accesses. Howe e , his is an ine icien
p edic o in e ms o bo h esou ce and ene gy consump ion [29] due
o he a ea and powe equi emen s implici in he p oposed neu al
ne wo ks.
Mo eo e , whe eas applying success ul o line lea ning o his kind
o model allows he implemen a ion o a p e- i ed p edic o , addi ional
online lea ning is necessa y o adap he p edic o o he local con ex
o a gi en applica ion and i s inpu da a. He e, a disad an age appea s
when applying online lea ning: he mo e complex a Machine Lea ning
model is (like he case o Deep Lea ning models), he mo e di icul and
unsuccess ul i s i ing [30].
The e a e addi ional p oposals ha do no p opose a p edic o , bu
a he neu al ne wo ks ha suppo he cu en al e na i es. Wo ks
such as Bha ia e al. [31], which p oposes a neu al ne wo k in cha ge o
il e ing he esul s o he p edic o o imp o e i s accu acy, o Rahman
e al. [32], which p oposes a Machine Lea ning echnique ha , based
on he ea u es o he code o be execu ed, sea ches o he op imal
con igu a ion o he p edic o .
In summa y, al hough RNN-based p oposals may achie e high accu-
acy, hey a e no cu en ly easible ha dwa e solu ions o p edic o s
due o hei la ge memo y consump ion, hei ele a ed la ency imes,
and hei need o bo h in ense o line and online aining o main ain
hei dynamic lea ning models [29] wi h high p edic ion a es. To
coun e ac hese issues, some e y ecen s udies om he ield o
Neu omo phic Enginee ing ha e p esen ed bio-inspi ed coun e pa s
o he p e iously men ioned RNN-based wo ks, like in [33,34], whe e
Spiking Neu al Ne wo ks (SNN) wi h Hebbian lea ning ules we e used
o memo y p e e ching. Due o he in e es ing ea u es o his kind
o bio-inspi ed models, which ensu e lowe la ency, memo y cos and
powe consump ion [35], i is expec ed ha mo e s udies on his no el
me hodology appea in he s a e-o - he-a [36].
F om he e iewed ela ed wo ks, we conclude ha DFCM and
DCLSTM models pu sui he same aim ha ou p oposal, so hey ha e
been selec ed o compa ison wi h ou s in Sec ion 6. No e he ele ance
o DCLSTM since i is he la es con ibu ion in e ms o gene al-
pu pose access p edic ion, whe eas he es o he mos ecen wo ks
do no p opose memo y access p edic o s as such, bu a he memo y
p e e che s. Fo ins ance, while DCLSTM is a gene al-pu pose p edic o
wi h he capabili y o p edic ing a wide ange o del as, Pa h inde [34]
only uses del as be ween −63 and +63 o block p edic ion inside a
memo y page. Due o he use o dynamic bu e s ( he inpu bu e and
he dic iona y), ou model, he SVM4AP, is able o pe o m gene al-
pu pose add ess p edic ion and can be di ec ly compa ed o he DFCM
and DCLSTM p edic o s.
3. Memo y access pa e ns
As commen ed in p e ious sec ions, p edic ing memo y access ad-
d esses is highly ela ed o alue p edic ion. Howe e , i gains a s ong
di e en ia ion when he pa e ns on which each echnique ocuses a e
analyzed. In ac , i can be said ha no only is access p edic ion one
pa icula case o alue p edic ion (in ac , he same p edic o s can be
applied o bo h asks), bu i also exploi s a ange o pa e ns ha make
he implemen a ion o access p edic ion easie [7].
Fo ins ance, conside a simple p og am whose main compu a ion
is a simple loop which i e a es h ough wo ec o s, pe o ming wo
memo y eads and one memo y w i e, like in he case o he well-
known SAXPY loop o in gene al hose benchma ks ha sol e scien i ic
nume ical equa ions o e a su ace o space, like SPEC applica ions
oms and cac uBSSN (see Table 2). Al hough he da a loaded om
memo y in each access is a bi a y and can ake any alue wi h nei he
a clea no a p edic able pa e n, a a he di e en si ua ion occu s o
hei memo y add esses because hey ha e no memo y space gaps. On
he whole, o scan pa e ns o simila , he p edic ion o he accessed
add esses is i ial. Mo eo e , he p og am sec ions ha ollow his
end a e o en he bo leneck o many o he algo i hms execu ed
nowadays, and especially in hose o scien i ic and mul imedia applica-
ions whe e ec o and ma ix ope a ions a e p e alen . In such cases,
a p edic o would achie e op imal pe o mance when he di e ences
be ween consecu i e accessed add esses (called del as o s ides) belong
o a small se o possible alues.
In con as , memo y access pa e ns ake he opposi e beha io o
algo i hms whose da a is no placed in memo y in a con inuous manne
bu a he andomly dis ibu ed. Such is he case o s uc u es like
linked lis s o g aphs among o he s (see o example SPEC benchma ks
mc o omne pp in Table 2), whose elemen s a e dynamically alloca ed
by he ope a i e sys em and, hence, a e loca ed ac oss memo y space
wi h andom gaps. Fu he mo e, in such algo i hms, he accesses o
he di e en elemen s o hese s uc u es a e no usually ixed by
he code bu a he dependen ei he on a condi ion which con ols
one o mo e b anches, o on an inpu o in e media y alue. These
kinds o algo i hms p esen he mos di icul scena io o p edic access
add esses.
Fo any o he wo main cases he e desc ibed, one majo ac o
needs o be conside ed: access space, which is he se o all possible
add esses ha a p og am can access, may ange om 0 o (264 − 1) in
64-bi a chi ec u es. The e o e, bo h he inpu and ou pu space ha
he p edic o mus handle is huge, e en o del a/s ide p edic o s.
These and o he issues a e ackled by ou p edic o p oposal as de-
sc ibed in Sec ion 5, and i s inal pe o mance is alida ed in Sec ion 6.
4. Ou lining a new model
Ou p edic o p oposal comes om a se o design decisions ha a e
mean o o e come he de ec ed d awbacks o o he p edic o s. The i s
o hese choices was o p e en he use o able-based indexing unc-
ions (e.g., simila o hose encoun e ed in he DFCM p edic o , Goeman
e al. [9]) by subs i u ing hem wi h a Machine Lea ning block.
Wi h espec o he memo y pa e n p edic o and lea ning blocks,
i can be obse ed ha only he weigh ma ix o RNNs incu s a high
memo y cos (e.g., hose om [11,25,26]), in addi ion o a conside able
la ency on bo h in e ence and e aining. The e o e, a solu ion based on
a linea Suppo Vec o Machine (SVM) was chosen since i ea u es
a much lowe cos bo h in memo y and la ency, and i s esul s a e
excellen , as shown in he ollowing sec ions.
One majo poin in he p e iously e e enced Deep Lea ning-based
me hods was p edic ing del as (di e ences be ween consecu i e access
add esses) by classi ying hem wi h a s a ically i ed dic iona y, whe e
each class/wo d is associa ed wi h a del a. Al hough i enables a much
mo e e icien RNN model due o educing he ou pu space om
any possible del a alue o only a ew hund ed o classes/wo ds, i
makes he p edic o less dynamic and mo e cons ained by he p o-
g ams (whose memo y accesses a e eco ded as a da ase ) selec ed
o he s a ic model aining. Based on his, a dic iona y has also
been inco po a ed in ou p oposal; bu wi h he pa icula ea u e o
being 100% dynamic: all classes/wo ds a e dynamically s o ed du ing
execu ion, ollowing a Leas F equen ly Used (LFU) e ic ion policy.
One ema kable ad an age is also achie ed: his app oach enables a
dic iona y o much smalle size, ocusing on only a ew possible del as
ha appea du ing each code zone o he execu ion. This dic iona y
plays a simila ole o ha o he DCFM second able; howe e , i s size
can be e y much smalle , as shown in Sec ion 6.
Ano he c ucial choice o ou p oposal is ha p edic ions a e pe -
o med on local his o y access aces ( ha is, he sequence o accesses
associa ed wi h he ins uc ion P og am Coun e ) ins ead o a global
Fu u e Gene a ion Compu e Sys ems 164 (2025) 107592
3
P. Sanchez-Cue as e al.
one. I s main ad an age is ha his app oach does no mix accesses o
di e en ins uc ions so ha he p edic o would lea n e e y sequence
as a pa e n a ached sepa a ely o each ins uc ion. This would esul
in a mo e p ecise p edic ion. Howe e , a li le complica ion is he need
o a cache o s o e he his o y (i.e., he access sequences) and he
las accessed add ess o each memo y ead/w i e ins uc ion: he he e-
called inpu bu e . This componen is simila o he i s able o he
DFCM p edic o since i is also indexed by ins uc ion PC and i ou pu s
a ce ain ea u e o he la e add ess p edic ion.
In o de o alle ia e he memo y cos o he inpu bu e and, mo e
impo an ly, o imp o e he p edic o ’s p ecision, one inal decision has
been aken: ins ead o s o ing access sequences as del as be ween con-
secu i e add esses, sequences o classes (ex ac ed om he dic iona y)
ha co espond o each o he del as a e being s o ed. In consequence,
SVM p edic ions would be (del a) classes om he his o y sequence o
classes o e e y ins uc ion. Thanks o his design choice, he inpu
space o he SVM model has been signi ican ly educed in compa ison
o hose o he e e enced RNN p oposals.
In summa y, he p io decisions esul in a model ha p edic s
he nex del a om a small bu cu en ly ele an se (s o ed in he
dic iona y), gi en he sequence o accesses (encoded as classes) o he
execu ed load o s o e ins uc ion. Using a linea SVM allows a mo e
s aigh o wa d i ing o he dynamic inpu s and ou pu s while gi ing
up some longe - e m pa e ns. Thus, ou p oposal le e ages sho - e m
lea ning, achie ing g ea e cos -e ec i eness han he DCLSTM p edic-
o , as depic ed in Sec ion 6. The nex sec ion de ails he a chi ec u e
o he new add ess p edic o , called SVM4AP.
5. P oposed model: SVM4AP
In his wo k, we p opose a p edic o model ha can be conside ed
as a hyb id be ween he DFCM and an RNN: he SVM4AP p edic o .
Speci ically, i s eps o wa d om he DFCM [9] since he del a/s ide
indexa ion ia hash codes ge s eplaced by a SVM. I s componen s a e
desc ibed as ollows (see no a ion in Table 1):
1. Inpu bu e . A memo y able ha s o es an en y o each
memo y ead/w i e ins uc ion con aining: (1) he las accessed
memo y add ess 𝑎𝑝; and (2) he sequence 𝑞𝑝o del a classes
(a.k.a. wo ds) o he las 𝑛𝑞accesses o he ins uc ion. The
able is indexed by he P og am Coun e (PC) 𝑝o he gi en
memo y access ins uc ion. I can be implemen ed as a𝑛𝑤-
way se associa i e cache memo y wi h 𝑛𝑠se s in o al, whe e
he objec i e is o alloca e he en ies o he mos commonly
execu ed memo y access ins uc ions, also making use o a Leas
Recen ly Used (LRU) e ic ion policy.
2. SVM. A linea Suppo Vec o Machine [37] which akes as inpu
a sequence 𝑞o 𝑛𝑞classes and e u ns as ou pu a p edic ed class
𝑐𝑝among he conside ed, possible 𝑛𝑐classes.
The p oposed implemen a ion ea u es as many hype planes as
𝑛𝑐ou pu classes ollowing aone- o-all classi ica ion, and he
p edic ion unc ion o each hype plane is exp essed as:
𝑓(𝑞 , 𝑐) =𝑤𝑐⋅𝑞−𝑏𝑐(1)
𝑝𝑟𝑒𝑑(𝑞 , 𝑐) ={+1 i 𝑓(𝑞 , 𝑐)≥0,
−1 o he wise (2)
whe e 𝑤𝑐and 𝑏𝑐a e he no mal weigh ec o and he in e cep
o he 𝑐 h hype plane, espec i ely. Fo i ing each hype plane,
gi en a sample o 𝑞′as inpu and 𝑦′
𝑐(which is equal o −1 i 𝑞′
is o class 𝑐o +1 o he wise) as ou pu , a g adien descen can
be implemen ed by he ollowing exp essions:
𝑑(𝑞′, 𝑦′
𝑐, 𝑐) = 1 −𝑦′
𝑐
⋅𝑓(𝑞′, 𝑐)(3)
∇𝑤𝑐={0i 𝑑(𝑞′, 𝑦′
𝑐, 𝑐)≤0,
−𝑦′
𝑐
⋅𝑞′o he wise (4)
Fig. 1. P edic ion (a) and i ing (b) phases un by he SVM4AP p edic o . Ope a ions
pe o med by each componen and hei inpu s and ou pu s a e also shown, ollowing
he sho de ini ions o Table 1.
Table 1
Glossa y o he main e ms o he SVM4AP model.
Symbol De ini ion
𝑝Memo y access ins uc ion PC
𝑎𝑝Las accessed add ess o ins . 𝑝
𝑞𝑝His o y o las del as om ins . 𝑝encoded as dic iona y classes
𝑐𝑝P edic ed class o del a o ins . 𝑝
𝑑𝑝P edic ed del a o ins . 𝑝
𝑎𝑝P edic ed memo y add ess o ins . 𝑝
𝑎𝑝
′New memo y add ess o ins . 𝑝
𝑞𝑝
′New his o y o las del as om ins . 𝑝encoded as dic iona y classes
𝑐𝑝
′Class o new del a o ins . 𝑝
𝑑𝑝
′New del a o ins . 𝑝
∇𝑏𝑐={0i 𝑑(𝑞′, 𝑦′
𝑐, 𝑐)≤0,
𝑦′
𝑐o he wise (5)
𝑤′
𝑐=𝑤𝑐+𝜂⋅∇𝑤𝑐(6)
𝑏′
𝑐=𝑏𝑐+𝜂⋅∇𝑏𝑐(7)
whe e ∇𝑤𝑐and ∇𝑏𝑐a e he g adien s o he no mal ec o and
he in e cep o he 𝑐- h hype plane, espec i ely, which a e
mul iplied by he lea ning a e 𝜂in o de o ob ain he new
no mal ec o 𝑤′
𝑐and in e cep 𝑏′
𝑐.
3. Dic iona y. Ano he memo y able ha in his case s o es 𝑛𝑐
en ies, whe e 𝑛𝑐is he numbe o classes ha a e used in he
p edic o . Each en y holds (1) a del a 𝑑, which is a s ide o
di e ence be ween wo consecu i e memo y access add esses,
and (2) a con idence alue 𝑘. Such a able can be implemen ed
wi h a pa icula ully associa i e cache memo y o 𝑛𝑐ways,
whe e an en y is accessed ei he by indexing di ec ly wi h a
gi en class o by que ying he en y (and i s co esponding class)
which s o es he gi en del a. A Leas F equen ly Used (LFU)
e ic ion policy is applied by making use o he con idence 𝑘
o each en y, which is inc emen ed on e ching he en y and
dec emen ed on e ching ano he en y.
The p ecise unc ioning o he p edic o and how he componen s
communica e wi h each o he is explained in wo phases: he p edic ion
pipeline and he i ing pipeline, as po ayed in Fig. 1. These wo pa s
a e desc ibed below:
(a) The p edic ion phase ecei es a new PC 𝑝o a memo y access
ins uc ion as inpu o he p edic o . This PC is employed as
Fu u e Gene a ion Compu e Sys ems 164 (2025) 107592
4
P. Sanchez-Cue as e al.
an index o he inpu bu e , om which bo h a base add ess
𝑎𝑝(indeed, he las accessed memo y add ess) and he class
sequence 𝑞𝑝= [𝑞𝑝(0),…, 𝑞𝑝(𝑛𝑞− 1)] a e ead. The sequence is
inpu ed in he linea SVM, which ou pu s a p edic ed class 𝑐𝑝.
This class is hen used o index he dic iona y om which he
esul ing del a
𝑑𝑝is ead. The inal p edic ed memo y add ess
equals he sum o he base add ess and he del a: 𝑎𝑝=𝑎𝑝+
𝑑𝑝.
I he e was a miss du ing he e ch o he inpu bu e en y, no
p edic ion is pe o med.
(b) The i ing phase esponds o an opposi e si ua ion: he cu en ly
accessed memo y add ess 𝑎𝑝′is gi en by he p ocesso in ad-
di ion o i s co esponding PC 𝑝. The e o e, he inpu bu e is
accessed using 𝑝as an index. Two cases appea : (1) I he en y
is s o ed in he inpu bu e (hi ), a new del a is compu ed as
he di e ence be ween he cu en memo y add ess and he las
one s o ed in his en y: 𝑑𝑝′=𝑎𝑝′−𝑎𝑝; (2) I he en y canno
be e ched om he inpu bu e (miss), he new del a will be
𝑑𝑝′= 0.
Thus, o any o he wo cases, he new del a is used o e ching
(by que y) he dic iona y, om which he o he wo cases ap-
pea : (1) I he e ch hi s he dic iona y, ha ing 𝑐𝑝′as he class o
he e ched en y, i s con idence is summed by a con idence jump
alue (which can be seen as a ewa d): 𝑘(𝑐𝑝′)←𝑘(𝑐𝑝′) +𝐽; (2)
I he e ch misses, a new en y 𝑑𝑝′is w i en in he dic iona y,
which is assigned a class alue 𝑐𝑝′and an ini ial con idence alue
equal o hal o he maximum 1
2𝑘𝑚𝑎𝑥. The con idence o he es
o he en ies is dec emen ed by one.
Once he class 𝑐𝑝′has been mapped o he cu en new del a
𝑑𝑝′, a new class sequence can be o med and s o ed in he inpu
bu e . Speci ically, in he case whe e he e was a hi p e iously
in he inpu bu e , he new class ge s pushed in o he p e ious
class sequence, which is hen s o ed in he co esponding en y
o he inpu bu e , he new sequence being equal o 𝑞𝑝′=
[𝑞𝑝(1),…, 𝑞𝑝(𝑛𝑞− 1), 𝑐𝑝′]. On he con a y, on a p e ious inpu
bu e miss, a new en y needs o be alloca ed in he inpu bu e ,
whe e he sequence is se o 𝑞𝑝′= [𝑛𝑐,…, 𝑛𝑐, 𝑐𝑝′]. Addi ionally,
ei he on an inpu bu e hi o a miss, he cu en add ess 𝑎𝑝′is
w i en as he las accessed add ess.
Finally, i he p edic ion o PC 𝑝p io o his i ing phase
missed, i.e. compu ed an add ess 𝑎𝑝di e en om he ue a ge
one 𝑎𝑝′, a i is pe o med in he SVM. The model is adjus ed wi h
one sample whe e he inpu is equal o he old class sequence 𝑞𝑝
and he ou pu is ac ually he new dic iona y class 𝑐𝑝′.
In summa y, ou p oposal can be iewed as a mix be ween e -
e enced DFCM and Machine Lea ning-based p edic o s, including a
whole se o op imiza ions wi h he objec i e o minimizing cos s and
maximizing p ecision. In ac , hese modi ica ions aim o ocus he
SVM4AP on local-con ex , high lea ning a e i ings in which he
p edic o g eedily lea ns pa e ns ha will apidly be e ic ed by o he
pa e ns, in line wi h he dynamic na u e o he memo y access pa e ns
o a p og am. Indeed, his app oach has inally been success ul, as he
esul s discussed in Sec ion 6show.
6. Expe imen a ion
In his sec ion, expe imen al esul s a e p esen ed and hei discus-
sion is included. The e ec i eness o he SVM4AP model is alida ed
o he p edic ion o memo y add esses accessed in eal applica ions
o he SPEC benchma k [38], showing de ailed compa isons be ween
baseline p edic o s and he p oposed implemen a ion.
6.1. Expe imen al se up
The expe imen a ion p ocess consis s o a wo-s ep pipeline: i s ,
memo y access add esses a e eco ded by ins umen ing a g oup o
applica ions, and hen he eco ded accesses a e used as a da ase o
he p edic o models.
The i s s ep is accomplished using In el Pin [39] o ins umen he
execu ion o he SPEC 2017 benchma ks. The p og am coun e (PC) and
he memo y add ess o each memo y access ins uc ion execu ed in a
eal CPU a e eco ded. The ou pu o his p ocess will depend on he
i ual memo y mapping assigned by he ope a ing sys em. In ou case,
his s ep is ca ied ou on an In el Co e i7-10750H lap op (2.60 GHz,
6 co es, 6×32 kB da a caches, Le el 2 cache size 6×256 kB, Le el 3
cache size 12 MB) using Ubun u 18.04.
The second s ep is p og ammed as a C++ p ojec and uploaded o
Gi Hub1in o de o publish an ea ly, s andalone expe imen a ion ool
which can be expanded o u u e models and benchma ks. The so -
wa e encapsula es all p edic o models (wi h he excep ion o DCLSTM,
whose sou ce code comes om i s o iginal eposi o y2) and simula ion
asks ha emula e he beha io o eal p edic o s. The ou pu o hese
asks is no hos -dependen , and hus no en i onmen al in o ma ion is
ele an o i .
6.2. Da ase building me hod
A close look a he i s s ep o he expe imen a ion p ocess e-
eals ha his ask is no compu a ionally i ial because o he huge
amoun o memo y access ins uc ions ha a e execu ed du ing he
un o a SPEC applica ion. Table 2shows he applica ions selec ed
o expe imen a ion in his wo k, hei SPEC ype classi ied be ween
in ege (INT) o loa ing poin (FP), and hei co esponding numbe o
memo y accesses. This numbe anges om 5.40 × 109 o 1.974 × 1012
ins uc ions, co e ing a o al amoun o 7.72 × 1012 accesses.
Building such a da ase o 7.7 × 1012 accesses is no p ac ical in
bo h s o age and subsequen p ocessing ime. To ackle his majo
es ic ion, we ha e implemen ed an easy bu ai wo kload selec ion
model in o de o bo h educe signi ican ly he numbe o accesses and
o co e uni o mly he o iginal eno mous wo kload. No e ha we e e
o wo kload as he amoun o memo y accesses ha a e sampled om
an ins umen a ion ool o he co esponding p og ams.
Fo each SPEC applica ion, ins umen a ion is pe o med and a ace
o 𝑀= 109accesses in o al is ex ac ed, and o each access (1)
he ins uc ion PC, (2) a bi indica ing whe he he access has been
a ead o a w i e, and (3) he i ual memo y add ess a e s o ed.
Such an amoun o samples esul s in a ace ile o nea ly 30 GB. To
e enly ep esen he o e all access pa e ns o each a ge applica ion, a
uni o m dis ibu ion has been chosen, ha is, a o al o 𝑔= 1000 g oups
ha e been eco ded, each con aining 𝑚= 106accesses. These g oups
a e sepa a ed be ween hem by a dis ance o 𝐷accesses. Addi ionally,
bo h a he s a and a he end o he comple e ace, a sequence o 𝑃
accesses is le un eco ded, conside ed as padding. Fo a p og am ha
has a o al sequence o 𝑁accesses, hese las wo dis ances 𝐷and 𝑃
can be calcula ed using he ollowing equa ions:
𝐷=⌊𝑁−𝑀
𝑔+ 1⌋,(8)
𝑃=⌊(𝑁−𝑀) −𝐷× (𝑔− 1)
2⌋(9)
A simple example o a dis ibu ion ollowing his model o a
p og am execu ion wi h 𝑁= 1000 memo y accesses in o al, 𝑀= 300
accesses pe g oup, and 𝑔= 5g oups can be seen in Fig. 2. No e ha
his me hod is no a andom sampling bu a pa i ion o he memo y
access ace ollowing he execu ion o de .
One in e es ing aspec o ha ing accesses in sepa a ed ace g oups
is ha i can oughly ep oduce he beha io o CPU p ocess con ex
1h ps://gi hub.com/Hema ies/P edicMem23.
2h ps://gi hub.com/MemMAP/MemMAP.
Fu u e Gene a ion Compu e Sys ems 164 (2025) 107592
5
P. Sanchez-Cue as e al.
Table 2
Memo y access s a is ics.
SPEC applica ion Type Applica ion a ea Memo y access
ins uc ions’ coun (109ins .)
pe lbench INT Pe l in e p e e 300.2
gcc INT GNU C compile 229.6
mc INT Rou e planning and scheduling 623.9
lbm FP Fluid dynamics 1974.0
omne pp INT Disc e e E en simula ion 451.5
xalancbmk INT XML o HTML con e sion 490.7
x264 INT Video comp ession 482.5
deepsjeng INT Alpha–be a ee sea ch (Chess) 732.6
exchange2 INT Recu si e solu ion gene a o (Sudoku) 1393.3
leela INT Mon e Ca lo ee sea ch (Go) 623.4
oms FP Regional ocean modeling 5.4
cac uBSSN FP Physics: ela i i y 387.5
Fig. 2. Example o access dis ibu ion o a p og am wi h 𝑁= 1000 accesses in
o al. The access g oups, he sepa a ion be ween hem and he bounda y paddings
a e po ayed in blue, black and g ay blocks esp.
swi ching. Tha is, each sequence o 𝑚accesses may be pe cei ed as
he memo y accesses ha ake place be ween he p ocess alloca ion
on he CPU and i s subsequen e ic ion, which a e pe o med by he
ope a ing sys em schedule . This conside a ion will be signi ican in he
nex subsec ion since his beha io is assumed o happen, and hus he
p edic o and i s online pa ame e s will be ese in each ace g oup
change.
Whe eas his da ase eco ding me hod allows a much less expen-
si e app oxima ion o he ace ex ac ion bo h in ime and s o age
cos s, i mus be cla i ied ha he whole p ocess s ill equi es many
hou s o execu ion and e u ns hund eds o gigaby es o da a. While
ou me hod is ai and simula es p ocess swi ches, he e a e o he
al e na i e da ase -building me hods in he cu en li e a u e [40–42]
ha alle ia e he cos . Fo example, each SPEC applica ion ace can
be sampled ollowing p e iously uned checkpoin s [43]. Then, o
each checkpoin , a weigh can be p o ided as a signi icance me ic:
he highe he alue, he mo e impo ance is gi en o he sequence o
accesses p esen in he checkpoin . Ano he in e es ing and he e odox
p ocedu e is desc ibed in [6], whe e he ace is gene a ed based on
s a is ical me ics in o de o accu a ely cha ac e ize he bu s iness o
memo y access beha io s. Due o expe imen a ion cos s, a ull compa -
ison be ween ou ai me hod and he p e iously men ioned ones is le
o u u e wo k.
6.3. Sea ch o easible SVM4AP p edic o s
Al hough he p oposed SVM4AP can almos each he bes -known
pe o mance whe e memo y is conside ed o be in ini e (see Sec-
ion 6.4), p edic o s should ely a he on op imizing cos -e ec i eness
in ealis ic scena ios.
Since he wo ables o he SVM4AP p edic o play a signi ican
ole in he inal hi a e, he e we explo e and es di e en , ealiz-
able con igu a ions o hese ables. The inpu bu e is implemen ed
(see Sec ion 5) as an 𝑛𝑤-way se associa i e memo y cache accessed
ia ins uc ion PC ha e u ns an en y wi h he co esponding las
memo y add ess and a𝑛𝑞-leng h class/wo d sequence. In addi ion, he
dic iona y consis s o a memo y o 𝑛𝑐classes, each co esponding o an
Table 3
Inpu bu e memo y cos o di e en con igu a ions (in by es).
4-leng h seq. 8-leng h seq.
2 ways 4 ways 2 ways 4 ways
4 classes
128 se s 4288 8576 4672 9344
256 se s 8512 17 024 9280 18 560
1024 se s 33 536 67 072 36 608 73 216
8 classes
128 se s 4416 8832 4928 9856
256 se s 8768 17 536 9792 19 584
1024 se s 34 560 69 120 38 656 77 312
Table 4
Inpu bu e miss a e o di e en con igu a ions and benchma ks.
cac uBSSN mc pe lbench
2 ways 4 ways 2 ways 4 ways 2 ways 4 ways
128 se s 0.9101 0.8705 0.0150 0.0017 0.7124 0.3812
256 se s 0.8640 0.7489 0.0036 0.0004 0.4481 0.1360
1024 se s 0.5299 0.1832 0.0004 0.0003 0.0807 0.0159
en y ha s o es he co esponding del a o s ide. This dic iona y can
be indexed by a class alue o que ied by a del a alue (see Sec ion 5).
A comple e sea ch on he con igu a ion space would equi e a e y
long expe imen a ion un ime because a o al o 109accesses mus
be simula ed o each p edic o con igu a ion pe each selec ed SPEC
applica ion. Thus, only a small bu ep esen a i e subse o alues was
chosen o he explo a ion o he di e en SVM4AP esul s acco ding
o a double c i e ion: co e ing alues ha p oduce ealizable ha dwa e
implemen a ions and spanning a b oad dissimila i y be ween hem. The
selec ed con igu a ion alues a e he ollowing:
𝑛𝑠∈ {128,256,1024}, 𝑛𝑤∈ {2,4}, 𝑛𝑞∈ {4,8}, 𝑛𝑐∈ {4,8}
whe e 𝑛𝑠and 𝑛𝑤a e he numbe o se s and ways o he inpu bu e
espec i ely, and 𝑛𝑞and 𝑛𝑐a e he numbe o classes/wo ds in each
inpu sequence and he dic iona y espec i ely.
A simila heu is ic o ying o minimize expe imen a ion cos while
maximizing dissimila i y was ollowed when selec ing he es ed ap-
plica ions. Thus, h ee applica ions ep esen ing he bes , wo s and
middle case scena ios we e chosen: cac uBSSN,mc and pe lbench.
Resul s a e o ganized in o h ee se s o ables:
•Inpu bu e . Table 3shows he memo y cos s o each o he
explo ed inpu bu e con igu a ions, while Table 4lis s he inpu
bu e miss a es o hem and o he h ee selec ed applica ions.
•Dic iona y. Table 5includes he dic iona y miss a es o he wo
p oposed numbe s o classes and he selec ed applica ions wi h
he co esponding memo y cos o each con igu a ion.
Fu u e Gene a ion Compu e Sys ems 164 (2025) 107592
6
P. Sanchez-Cue as e al.
Table 5
Dic iona y miss a e o di e en con igu a ions ( i s 3 columns), and hei co espond-
ing memo y cos in by es (las column).
cac uBSSN mc pe lbench
4 classes 0.0027 ± 0.0004 0.269 ± 0.004 0.074 ± 0.008 37 by es
8 classes 0.0022 ± 0.0004 0.199 ± 0.003 0.067 ± 0.006 75 by es
Table 6
SVM memo y capaci y o di e en con igu a ions (in by es).
4 classes 8 classes
4-leng h seq. 80 160
8-leng h seq. 144 288
•SVM model. Table 6shows he memo y cos s o he model weigh
ma ix o each o he con igu a ions explo ed, whe eas Table 7
summa izes he model p ecision o he di e en con igu a ions
and o he h ee selec ed applica ions.
No ice ha he dic iona y’s hi a e is compu ed as he hi a e o
ha componen jus when he inpu bu e hi s. In he same di ec ion,
he model’s hi a e is compu ed as he hi a e when bo h he inpu
bu e and he dic iona y hi . The e o e, he p edic o ’s inal hi a e is
equal o he p oduc o he h ee hi a es.
I is wo h no ing ha he inpu bu e ep esen s he c i ical com-
ponen in e ms o memo y because he memo y size o he model
implemen a ion and he dic iona y a e negligible (see Tables 3,5and
6).
Thus, he memo y capaci y o he p edic o should be i ed
s aigh ly h ough he inpu bu e . Fu he mo e, in u n, he inpu
bu e is con igu ed o mee one objec i e: minimizing i s own miss a e
by uning i s cache con igu a ion. Ne e heless, i has o be ema ked
ha he i ing o bo h he dic iona y and he SVM model a ec s he
inpu bu e ’s memo y cos indi ec ly ia wo pa ame e s: he sequence
leng h and he numbe o classes. Hence, his in e dependence among
he componen s o he sys em en ails a ade-o be ween he memo y
cos and hi a e o he p edic o .
The inpu bu e miss a e is highly dependen on he o al numbe
o inpu bu e en ies o wo o he analyzed benchma ks (cac uBSSN
and pe lbench). Speci ically, doubling he numbe o ways p oduces
a conside able imp o emen in he inpu bu e hi a e. This e ec
indica es ha memo y accesses o ins uc ion PCs end o collide in he
same cache se s, which can be due o access spa si y o non-alignmen .
The dic iona y miss a e supposes an impo an ac o only o
he mc applica ion, mainly because i s g aph compu a ion in ol es
dispe sed accesses ac oss i s memo y space. Doubling he size o he
dic iona y (by doubling he numbe o classes) pa ially alle ia es his
e ec .
Finally, he p ecision o he SVM model when bo h he inpu bu e
and he dic iona y hi ends o be maximum when 4 classes a e im-
plemen ed. Howe e , his p ecision is adjus ed o hose cases whe e
bo h he inpu bu e and he dic iona y hi . As po ayed in Table 5,
implemen ing 4 classes leads o a smalle dic iona y ha esul s in a
lowe hi a e. This ade-o is e iewed la e in Sec ion 6.4. On he
o he hand, excep o he case o mc , no clea di e ence in he SVM
hi a e is d awn when compa ing sequence leng hs o 4 o 8.
Ha ing e alua ed he esul s o he explo a ion o he con igu a ions
space, wo con igu a ions o he SVM4AP 𝑛𝑞-𝑛𝑐a e highligh ed among
he es : SVM4AP 4-4 and SVM4AP 8-8. Speci ically and acco ding o
he p e ious discussion, he SVM4AP candida es a e composed o : (1)
a 4-way associa i e inpu bu e which s o es 1024 se s wi h en ies
con aining class sequences o leng h 4 and 8 espec i ely, and (2) a
dic iona y o 4 and 8 classes in o al espec i ely, each ha ing o al
con idence o 256 and con idence jumps o 8. The decision o ocus
on zipping he sequence leng h and he numbe o dic iona y classes as
𝑛𝑞=𝑛𝑐allows he building o a con igu a ion space whe e he scale o
complexi y o he SVM model can be easily uned and analyzed.
The p io explo a ion o he con igu a ion space deli e ed insigh s
in o he SVM4AP’s beha io , i s ela ion wi h ea u es such as inpu
bu e size, and wo a p io i p oposed app op ia e solu ions. In Sec-
ion 6.4 a inal con igu a ion space is co e ed o es di e en locally
op imal SVM4AP con igu a ions, o ming an ex ension o he p e iously
co e ed con igu a ions while selec ing he pa ame e s pa e ns ha
yield be e esul s.
6.4. Resul s and discussion
Following a quan i a i e measu e o he o e all pe o mance and
cos -e ec i eness o he p esen ed SVM4AP, he use o s a e-o - he-a
p edic o s o compa ison is p oposed. Speci ically, he DFCM and he
DCLSTM we e selec ed.
In he case o he DFCM, implemen a ions ha e been ca ied ou o
wo di e en a ian s desc ibed in de ail in [44,45], which a e labeled
he e as ollows:
•HashOnHash: The new hash alue is compu ed as he hash as a
combina ion o he p e ious hash alue and he esul ing del a
( he di e ence be ween he cu en add ess and he p e ious
one).
•K-O de : The esul ing del a is pushed in o a sequence o 𝐾del as
s o ed in he accessed en y o he i s able. Then, he hash alue
is compu ed as he hash o he 𝐾del as s o ed in his en y.
DFCM, like o he able-based p edic o s, achie es be e p ecision
he g ea e he capaci y o i s wo ables. Indeed, in a simula ion
en i onmen , an ideal DFCM p edic o whose ables con ain an in ini e
numbe o en ies ( ia an implemen a ion using dynamic memo y wi h
hash-maps, o example) can be e alua ed. Fu he mo e, in his case,
ha ing limi less ables gains ele ance since i s p edic ions a e based
on s o ing all possible p edic ion solu ions o all possible con ex s.
He e, an analog app oach is b ough o he o e when implemen ing
he SVM4AP: i s con igu a ion space allows mul iple implemen a ions
wi h di e en ou comes in he ange o cos -e ec i eness. Fo example,
as seen in Sec ion 6.3, he p edic ion hi a e is highly dependen on he
hi a e achie ed by bo h he inpu bu e and he dic iona y, which in
u n is di ec ly a ec ed by he size o hose ables.
An ideal SVM4AP p edic o can be implemen ed by ha ing an in i-
ni e inpu bu e while, in con as o he DFCM, he es o he elemen s
( he SVM model and he dic iona y) emain wi h a ixed size. This is
due o he s a ic na u e o an SVM model, whose inpu and ou pu sizes,
o cou se, canno a y dynamically. The e o e, he pe o mance o
SVM4AP wi h Ma ching Lea ning in e ence is mo e limi ed o ealis ic
con igu a ions han a able-based b u e o ce mapping DFCM p edic o
ha can be ex ended o an ideal scena io wi h be e esul s, as shown
in Sec ion 6.4.4.
In he case o DCLSTM, we ha e di ec ly ep oduced he ideal
expe imen al p ocedu e o he model om [25]: aining and es ing
a di e en DCLSTM p edic o o each ace. Tha is, o each SPEC
applica ion, a p edic o is se o lea n only he memo y access pa e ns
in insic o i . No e ha his es ing mode g ea ly bene i s his p edic o .
I is no ewo hy ha he DCLSTM’s esul s a e ob ained a e a da a spli
be ween aining and es se s (as common in Deep Lea ning pipelines),
which also lea es mo e skew owa ds he DCLSTM model. Con e sely,
SVM4AP’s esul s come om he on-line lea ning ac oss he whole
ace wi hou any es ing phase no spli selec ion. The goal o his
expe imen a ion heu is ic is o gi e a s aigh compa ison be ween a
bes -case, Deep Lea ning implemen a ion and ou Machine Lea ning
p oposal. Besides, he e a e o he mo e ealis ic and p ac ical NN
implemen a ions (using a me a-model buil upon di e en specialized
DCLSTMs and i ed ia online e aining, see [46]), which would
deli e e en wo se esul s han he specialized, ained models used
he e.
Fu u e Gene a ion Compu e Sys ems 164 (2025) 107592
7
P. Sanchez-Cue as e al.
Table 7
SVM’s hi a e o di e en inpu and ou pu sizes.
cac uBSSN mc pe lbench
4 classes 8 classes 4 classes 8 classes 4 classes 8 classes
4-leng h seq. 0.962 ± 0.025 0.953 ± 0.033 0.802 ± 0.004 0.773 ± 0.002 0.861 ± 0.105 0.860 ± 0.109
8-leng h seq. 0.962 ± 0.026 0.953 ± 0.034 0.818 ± 0.005 0.777 ± 0.004 0.858 ± 0.106 0.856 ± 0.111
O e all, he di e en easible con igu a ions shown in Tables 8,
9,10 and desc ibed in Sec ion 6.4.2 ( he la e speci ically o he
DCLSTM) a e simula ed, gi en he SPEC aces collec ed by ou ex-
ac ion model om Sec ion 6.2. No e ha he con igu a ions aken
o SVM4AP is an expanded se om he con igu a ion heu is ic e-
iewed in Sec ion 6.3. The p edic ion esul s and memo y cos s a e also
summa ized in hose ables.
To illus a e accu a ely he cha ac e is ics o he esul s gi en by
such amoun o implemen a ions, we di ide he discussion in o ou
subsec ions ea u ing (1) hose esul s gi en by HashOnHash and K-
O de p edic o s, (2) he esul s e u ned by he DCLSTM p edic o , (3)
he ones gi en by he SVM4AP p edic o , and (4) he inal compa ison
among he all o hem.
6.4.1. DFCM esul s
The con igu a ions o bo h HashOnHash and K-O de a ian s ha e
been selec ed i s acco ding o he DFCM’s i s able (i.e. VHT). Since
i s unc ionali y is almos he same as he inpu bu e o SVM4AP,
i s con igu a ion space ollows a simila pa e n. Con e sely, DFCM’s
second able (i.e. VPT), which s o es del as by indexing hash alues,
is se inside a small con igu a ion subse since inal p edic ion hi a e
does no a y much when inc easing i s size. In he pa icula case o
K-o de DFCM, he sequence leng h 𝐾has been adjus ed o jus wo
di e en sequences, one sho and one long. As such, DFCM ables ha e
been simula ed as cache memo ies and he alues belonging o hei
con igu a ion se a e:
𝑛𝑠,1∈ {128,256,512,1024}, 𝑛𝑤,1∈ {6},
𝑛𝑠,2∈ {128,256}, 𝑛𝑤,2∈ {2,4}, 𝐾∈ {4,8},
whe e 𝑛𝑠,1,𝑛𝑠,2a e he numbe o se s con ained in he i s and second
ables espec i ely, 𝑛𝑤,1and 𝑛𝑤,2a e he numbe o ways con ained in
he i s and second ables espec i ely, and 𝐾is he sequence leng h
o del as in he case o aK-O de DFCM.
The DFCM p edic o s a e labeled as he ollowing manne :
•‘‘DFCM HoH 𝑏1-𝑛𝑤,1-𝑏2-𝑛𝑤,2’’, which s ands o aHashOnHash
DFCM whose i s able con ains 𝑛𝑠,1= 2𝑏1se s and 𝑛𝑤,1ways,
and whose second able con ains 𝑛𝑠,2= 2𝑏2se s and 𝑛𝑤,2ways,
espec i ely. 𝑏1and 𝑏2a e he index bi s o each able.
•‘‘DFCM K-o de 𝐾-𝑏1-𝑛𝑤,1-𝑏2-𝑛𝑤,2’’, which s ands o a K-o de
DFCM ha s o es sequences o 𝐾del as, and he same able se s
and ways con igu a ion as explained o he ‘‘DFCM HoH’’.
The mean hi a es and s anda d de ia ions among all SPEC applica-
ions o he HashOnHash and K-O de p edic o s a e shown in Tables 8,
9, in addi ion o he memo y capaci y needed o such implemen a ions.
The a o emen ioned di ec ela ion be ween pe o mance and mem-
o y cos can be obse ed, as la ge p edic o s deli e be e p edic ion
esul s o bo h DFCM a ian s. O cou se, an ideal DFCM wi h ables
o in ini e size deli e s he bes possible hi a e.
Mo eo e , HashOnHash is clea ly be e in cos -e ec i eness han
i s coun e pa , which deli e s poo e esul s while equi ing a la ge
memo y budge . Fo example, he bes hi a e achie ed by K-O de
eaches 74.5 ± 14.6%, and equi es a o al o 432.06 kB, while he bes
hi a e o aHashOnHash p edic o is 82.1 ± 9.7% occupying 151.5 kB.
Rega ding he beha io o he bes HashOnHash ( he ‘‘DCFM HoH
10-6-8-4’’) and he bes K-O de (‘‘DCFM K-O de 8-10-6-7-4’’) in e ms
o hi a e wi h espec o he di e en SPEC applica ions, Figs. 3and
Fig. 3. Hi a e o he bes explo ed con igu a ion o he HashOnHash DFCM wi h
espec o he SPEC applica ions.
Fig. 4. Hi a e o he bes explo ed con igu a ion o he K-O de DFCM wi h espec
o he SPEC applica ions.
4decompose he hi a es o he wo ables plus he inal p edic ion
hi a e. I can be obse ed how he i s able wi h such con igu a ions
is able o a oid almos all misses, and hence he p edic o ’s p ecision
is highly dependen only on he second able’s hi a e and he o e all
ma ch be ween he co ec memo y add esses and he ones which a e
compu ed om he s o ed del as. This is he poin o di e ence be ween
he wo a ian s: bo h p esen good second able’s hi a es, bu while
inal hi a es o he HashOnHash app oach ha o he second able’s
hi a e, he inal p edic ion s o ed by he K-O de ma ches in ewe
occasions wi h he co ec memo y add ess. Such a esul is due o
he mapping unc ion om he K-O de a ian , less able o compu e
con ex s ela ed o co ec del as in he second able.
Focusing on he esul s o he bes HashOnHash, i can be no ed how
disc e e compu a ion applica ions such as mc , o omne pp suppose da a-
dependen memo y add ess pa e ns, whe e add ess del as appea so
dispe sed ha hei con ex s (encoded as hash alues) do no usually
hi when accessing he second able.
Fu u e Gene a ion Compu e Sys ems 164 (2025) 107592
8
P. Sanchez-Cue as e al.
Table 8
Con igu a ions o he DFCM HashOnHash p edic o wi h hei hi a e and o al memo y cos .
Label Fi s able Second able Summa y
𝑛𝑠,1𝑛𝑤,1𝑛𝑠,2𝑛𝑤,2Hi a e Memo y cos
DFCM HoH 7-6-7-4 128 6 128 4 0.632 ± 0.208 24.91 kB
DFCM HoH 8-6-7-2 256 ... 128 2 0.688 ± 0.183 38.28 kB
DFCM HoH 8-6-7-4 256 128 4 0.704 ± 0.180 42.06 kB
DFCM HoH 8-6-8-4 256 256 4 0.712 ± 0.180 49.5kB
DFCM HoH 9-6-7-2 512 128 2 0.754 ± 0.125 72.41 kB
DFCM HoH 9-6-7-4 512 128 4 0.771 ± 0.118 76.19 kB
DFCM HoH 9-6-8-4 512 256 4 0.779 ± 0.115 83.63 kB
DFCM HoH 10-6-7-2 1024 128 2 0.799 ± 0.106 140.28 kB
DFCM HoH 10-6-7-4 1024 ... 128 4 0.814 ± 0.099 144.06 kB
DFCM HoH 10-6-8-4 1024 6 256 4 0.821 ± 0.097 151.5kB
In ini e DFCM HoH ∞1∞10.851 ± 0.092 ∞
Table 9
Con igu a ions o he K-O de p edic o wi h hei hi a e and o al memo y cos .
Label Fi s able Second able Summa y
𝑛𝑠,1𝑛𝑤,1𝐾 𝑛𝑠,2𝑛𝑤,2Hi a e Memo y cos
DFCM K-O de 4-7-6-7-2 128 6 4 128 2 0.599 ± 0.210 33.13 kB
DFCM K-O de 4-7-6-7-4 128 ... 4 ... 4 0.605 ± 0.209 36.91 kB
DFCM K-O de 8-7-6-7-2 128 8 2 0.589 ± 0.226 57.13 kB
DFCM K-O de 8-7-6-7-4 128 8 4 0.598 ± 0.224 60.91 kB
DFCM K-O de 4-8-6-7-2 256 4 2 0.659 ± 0.191 62.28 kB
DFCM K-O de 4-8-6-7-4 256 4 4 0.664 ± 0.191 66.06 kB
DFCM K-O de 8-8-6-7-2 256 8 2 0.653 ± 0.206 110.28 kB
DFCM K-O de 8-8-6-7-4 256 8 4 0.661 ± 0.204 114.06 kB
DFCM K-O de 4-9-6-7-2 512 4 2 0.707 ± 0.153 120.41 kB
DFCM K-O de 4-9-6-7-4 512 4 4 0.713 ± 0.152 124.19 kB
DFCM K-O de 8-9-6-7-2 512 8 2 0.705 ± 0.163 216.41 kB
DFCM K-O de 8-9-6-7-4 512 8 4 0.713 ± 0.161 220.19 kB
DFCM K-O de 4-10-6-7-2 1024 4 2 0.735 ± 0.142 236.28 kB
DFCM K-O de 4-10-6-7-4 1024 4 4 0.741 ± 0.141 240.06 kB
DFCM K-O de 8-10-6-7-2 1024 ... 8 ... 2 0.737 ± 0.148 428.28 kB
DFCM K-O de 8-10-6-7-4 1024 6 8 128 4 0.745 ± 0.146 432.06 kB
Fig. 5. DCLSTM and selec ed SVM4AP hi a es o he aining and es spli s (50/50%)
o he i s 5⋅106 ace accesses.
6.4.2. DCLSTM esul s
Wi h he objec i e o es ing he DCLSTM p edic o model, a subse
o ou ob ained SPEC aces ( om Sec ion 6.2) is he e employed as
da ase . The expe imen comp ehends he i s 5⋅106memo y accesses
o each collec ed ace, an amoun ha has been shown o be enough
o aining and es ing (see [25]).
He e, o each ace, an ins ance o he DCLSTM model is ained
using he i s 50% accesses and la e es ed wi h he las 50% chunk
o he ace. Simila ly o S i as a a e al. [25], he aining comp ises
20 epochs and a ba ch size o 256, whe e he inpu is a sequence o
he las h ee del as. These del as, none heless, a e encoded in bina y
as classes/wo ds inside a216-size dic iona y, which is i ed o line by
selec ing he op equen del as in he ace. Conce ning he ne wo k
s uc u e o he DCLSTM, i includes: (1) an embedding laye wi h an
ou pu size o 10, (2) a LSTM laye wi h 50 uni s, (3) a 10% d opou ,
and (4) a 16-wid h dense laye using he sigmoid ac i a ion unc ion.
The loss unc ion applied is bina y c oss-en opy.
T aining and es ing hi a es a e illus a ed in Fig. 5. Fo a clea e
compa ison, his igu e also displays he co esponding ou comes o
he SVM4AP wi h online lea ning sepa a ely o he same wo ace
spli s. To es ablish his SVM4AP as a e e ence o compa ison as
baseline, i is con igu ed as one o he locally op imal implemen a ions
ou lined in Sec ion 6.3, ea u ing an inpu bu e o 1024 se s and 4
ways, 8-leng h inpu sequences, and a dic iona y wi h 8 classes.
As depic ed in Fig. 5, DCLSTM hi a es a e signi ican ly lowe
han hose o i s SVM4AP coun e pa on all aces, encompassing bo h
aining and es ing spli s, wi h he sole excep ion o he deepsjeng ace.
The la e case is a ibu ed o i s i ial accesses, which a e eques ed
om he same memo y ins uc ion wi h a cons an del a o 1 in almos
mos cases. In addi ion o his, he e is a clea con as , highligh ed by
he mean hi a es o he wo models: 0.485 ± 0.216% and 0.476 ± 0.210%
o DCLSTM in he aining and es spli s, espec i ely; agains a much
supe io 0.784 ± 0.195% and 0.786 ± 0.194% o SVM4AP (also o he
aining and es spli s, espec i ely).
Al hough a complex model such as an RNN should ha e he means
o lea n a wide ange o memo y add ess pa e ns, he design app oach
and hypo hesis de ined in Sec ion 4 o ou simple p oposal a e
alida ed, including he ocus on sho - e m lea ning as opposed o he
long- e m lea ning ha LSTM-based models a e able o accomplish. The
SVM4AP exploi s cha ac e is ics ha suppose a p ope imp o emen
om s a e-o - he-a , Deep Lea ning-based p edic ion models in e ms
o p ecision.
Fu he mo e, he DCLSTM p edic o and ela ed models in oduce
a signi ican cons ain : memo y cos . DCLSTM has a ela i ely modes
Fu u e Gene a ion Compu e Sys ems 164 (2025) 107592
9
