Th ee-Dimensional Memo y Vec o iza ion o High Bandwid h Media Memo y
Sys ems
Jesus Co bal, Roge Espasa and Ma eo Vale o
Depa amen díA qui ec u a de Compu ado s,
Uni e si a Poli `ecnica de Ca alunyañBa celona, Spain

e-mail:
jco bal, oge ,ma eo
g
@ac.upc.es
Abs ac
Vec o p ocesso s ha e good pe o mance, cos and
adap abili y when a ge ing mul imedia applica ions. How-
e e , o a signi ican numbe o media p og ams, con en-
ional memo y con igu a ions ail o deli e enoughmemo y
e e ences pe cycle o eed he SIMD unc ional uni s. This
pape add esses he p oblem o he memo y bandwid h.
We p opose a no el mechanism sui able o 2-
dimensional ec o a chi ec u es and a ge ed a p o iding
high e ec i e bandwid h o SIMD memo y ins uc ions.
The basis o his mechanism is he ex ension o he scope
o ec o iza ion a he memo y le el, so ha 3-dimensional
memo y pa e ns can be e ched in o a second-le el egis e
ile.
By e ching long blocks o da a and by eusing 2-
dimensional memo y s eams a his second-le el egis e
ile, we ob ain a signi ican inc ease in he e ec i e memo y
bandwid h. As side bene i s, he new 3-dimensional load in-
s uc ions p o ide a high obus ness o memo y la ency and
a signi ican educ ion o he cache ac i i y, hus educing
powe and ene gy equi emen s. A he in es men o a 50%
mo e a ea han a egula SIMD egis e ile, we ha e mea-
su ed and a e age speed-up o 13% and he po en ial o
powe sa ings in he L2 cache o a 30%.
1 In oduc ion
Mul imedia applica ions ha e become one o he mos
impo an ypes o wo kloads in cu en mic op ocesso de-
sign [1]. Mos new gene al pu pose and embedded p oces-
so s include SIMD ISA ex ensions o inc ease he pe o -
manceo u u emedia p o ocolsand kille applica ionssuch
as MPEG-4 [2]. These new ins uc ion ex ensions ocus on
exploi ingda a-le el pa allelism o e small da a- ypes ( hus
some imes called

-SIMD pa allelism) inside a single eg-
is e (64-128bi s ypically). Examples o hese new ISA ex-
ensions a e INTELís MMX [3] and SSE[4], SUNís VIS[5],

This wo k has been suppo ed by he Minis y o Science and Technol-
ogy o Spain unde con ac TIC-2001-0995 and by he CEPBA
AMDís 3DNow! [6], MIPSís MDMX [7] and Mo o olaís
Al iVec [8].
Rangana han e .al. [9] p esen ed an in-dep h s udy o
he cha ac e is ics o

-SIMD enhanced applica ions. They
showed ha a e including so wa e p e e ching, mos me-
dia applica ions we e compu e bound. Pe o mance was,
hen, ul ima ely limi ed by e ch and issue bandwid h. In o -
de o add ess his p oblem, se e al au ho s ha e p oposed
2-dimensional ec o a chi ec u es [10, 11, 12]. These a -
chi ec u es adap o ypical mul imedia memo y pa e ns by
ex ending he scope o ec o iza ion o wo dimensions (o
pa allel loops). The main ad an age o hese 2-dimensional
ec o a chi ec u es is ha hey a e able o signiÝcan ly in-
c ease he numbe o ope a ions pe ins uc ion, hus, b eak-
ing he e ch/issue ba ie o mos media p og ams.
In his pape , we s udy he beha io o se e al media ap-
plica ions using one o hese 2D media ex ensions. We will
show ha se e al applica ions expe ience a signiÝcan pe -
o mance deg ada iondue o he he memo y sys em. While
da acachesshowan ex emelyhighhi a e (asal eadyhigh-
ligh ed by Slinge lande .al. [13]), hey a e, howe e , unable
o deli e enough memo y bandwid h o he ec o unc-
ional uni s.
The design o high bandwid h cache memo y sys ems
is no i ial due o he complex memo y layou s ypically
ound in mos media applica ions. In o de o add ess his
p oblem, we came o he obse a ion ha high amoun s o
spa ial and empo al locali y exis a ex a dimensions o he
memo ypa e nlayou ,e en hough he e a ecompu a ional
dependences ha do no allow s aigh - o wa d ec o iza-
ion. This locali y, i p ope ly exploi ed, may enable high
memo y bandwid h wi h a easible cache hie a chy based
on widening he cache memo y po s.
We p opose a new ex ension o a 2D ec o a chi ec u e
a ge ed a implemen ing high bandwid h ec o memo y
sys ems. The basis o his mechanism is a second-le el ec-
o egis e Ýle whe e 3-dimensional memo y pa e ns can
be e ched om he memo y hanks o a new 3D ec o
load ins uc ion. By doing his, we ake ad an age o highe
amoun s o spa ial and empo al locali y ha ansla e in o
highe e ec i e bandwid h and egis e euse.
P oceedings o he 35 h Annual IEEE/ACM In e na ional Symposium on Mic oa chi ec u e (MICRO-35)
1072-4451/02 $17.00 © 2002 IEEE
a
0,0
a
0,1
a
0,2
a
0,3
a
0,4
a
0,5
a
0,6
a
0,7
64 bi s
dimension i: 8 elemen s x 8 bi s
a
0,0
a
0,1
a
0,2
a
0,3
a
0,4
a
0,5
a
0,6
a
0,7
a
1,0
a
1,1
a
1,2
a
1,3
a
1,4
a
1,5
a
1,6
a
1,7
a
2,0
a
2,1
a
2,2
a
2,3
a
2,4
a
2,5
a
2,6
a
2,7
a
3,0
a
3,1
a
3,2
a
3,3
a
3,4
a
3,5
a
3,6
a
3,7
a
4,0
a
4,1
a
4,2
a
4,3
a
4,4
a
4,5
a
4,6
a
4,7
a
5,0
a
5,1
a
5,2
a
5,3
a
5,4
a
5,5
a
5,6
a
5,7
a
6,0
a
6,1
a
6,2
a
6,3
a
6,4
a
6,5
a
6,6
a
6,7
a
7,0
a
7,1
a
7,2
a
7,3
a
7,4
a
7,5
a
7,6
a
7,7
64 bi s
dimension i: 8 elemen s x 8 bi s
dimension j: 8 elemen s x 64-bi (MMX)
8
MOM
MMX
in ullsea ch(blk1, blk2, leng h, i0, j0, in win)
unsigned cha *blk, *blk2;
in leng h, i0, j0, win;
{
in l, d, i, j, k, min, pos;
unsigned cha *a,*b;
...
...
o (k=0; k<l; k++) {
a = blk1 + k;
b = blk2;
d = 0;
o (j=0; j<8; j++) {
o (i=0; i<8; i++) {
d += abs(a[i]-b[i]);
}
a += leng h;
b += leng h;
}
i (d<dmin) {
min=d;
pos = k; ;
}
}
...
...
}
Figu e 1. Compa ison be ween (a) a con en ional MMX-like

-SIMD ins uc ion and (b) a Ma ix (MOM-
like) 2D SIMD ins uc ion.
We will show ha ou p oposed mechanism is able
o p o ide high pe o mance gains o hose applica ions
whe e memo y bandwid h is he main bo leneck. E en o
he es o he benchma ks,ou p oposalp o ides wosigni -
ican side beneÝ s: a sensible educ ion o he cache ac i i y
and a p e e ching e ec . The o me ansla es in o lowe
powe /ene gyconsump ionin hememo ysub-sys emwhile
he la e p o ides high obus ness o he la ency when he
memo y is a away.
2 A b ie o e iew o a 2D ec o ISA
In his pape , we a e going o use MOM [10] as ou base-
line 2D ec o ISA. MOM s ands o Ma ix O ien ed Mul i-
media ex ensionand is a hyb id be ween a adi ional ec o
anda

-SIMD ISA. MOM is able o exploi up o wo di e -
en dimensions o pa allelism by using a di e en pa adigm
(ei he ec o o

-SIMD ) o ec o ize one o wo a ailable
pa allel nes ed loops.
MOM can be iewed as a con en ional ec o ISA whe e
each o i s compu a ion ope a ions a e

-SIMD MMX-like
ins uc ions. The execu ion o a MOM ins uc ion is dic-
a ed by wo di e en pa ame e s. The Vec o Leng h de e -
mines how many 64-bi elemen s o he MOM egis e a e
ope a ed (ou o 16). The Vec o S ide de e mines he dis-
ance be ween wo consecu i e MOM ec o elemen s when
pe o ming memo y ope a ions.
In o de o help unde s and he di e ences be ween a
con en ional

-SIMD app oach and a 2D app oach such as
MOM, Ýgu e 1 shows a simpliÝed agmen o code ex-
ac ed om a MPEG-2 encode . The algo i hm shown is
doing he mo ion es ima ion s age o he encoding, which
de ec s mo emen o objec s along di e en ideo ames.
In o de o do so, i sea ches ac oss he e e ence image o
he image block which ma ches be e wi h he block being
comp essed. This is accomplished by Ýnding he minimal
sum o absolu e di e ences be ween he pixels o he wo
blocks. This sea ch is pe o med, in he code, o e se e al
ma ices laid ou on he image x-axis. No e ha leng h
may be a bi a ily long, as i s ands o he ho izon al size o
he ame.
Analyzing he code shown in he Ýgu e we can see ha
he e a e up o wo di e en dimensions o da a-le el pa al-
lelism o be exploi ed: nes ed loops
i
and
j
. The calcula ion
o he sum o absolu e di e ences be ween pai s o pixels
(
i j
)
can be done in pa allel ai ly easily. No e, howe e ,
ha loop
k
does no show he same p ope y, as we ha e
da a and con ol dependencies in he
i
clause (clause ha
de e mines i we ha e ound a local minimum) which a oid
ec o iza ion.
As shown in Ýgu e 1, MOM is able o ake ad an age o
he pa allelism implici in bo h loops
i
and
j
. Fi s , i gen-
e a es a MMX-like ins uc ion o loop
i
, and hen ex ends
an addi ional ec o iza ion o his ins uc ion, eplica ing i
ac oss loop
j
. As a esul , each pa e n
a
and
b
a e loaded
in o a single MOM egis e . In o he wo ds, each MOM
egis e elemen (a 64-bi

-SIMD egis e ) co esponds o
a ow o a ma ix.
P oceedings o he 35 h Annual IEEE/ACM In e na ional Symposium on Mic oa chi ec u e (MICRO-35)
1072-4451/02 $17.00 © 2002 IEEE
P ocesso
Co e
P ocesso
Co e
bank 0 bank 1 bank n-1
Shi & Mask
In e change
Ini ial Add ess
Final Add ess
P ocesso
Co e
P ocesso
Co e
(b)(a)
...
C ossba
...
...
11
1 x B
11
B
1
B x 1
Figu e 2. Cache designs o SIMD memo y
po s: (a) Mul i-banking, (b) Po Widening.
3 Ra ionale o 3-dimensional ec o iza ion
In his sec ion we will show ha 2D SIMD media p o-
g ams can expe ience se e e pe o mance deg ada ions due
o he bandwid h cons ain s o ealis ic cache implemen a-
ions. In o de o add ess he p oblem, we will in oduce
wo new ins uc ions o pe o m 3D memo y accesses and
will discuss why hey allow exploi ing a highe amoun o
empo al and spa ial locali y.
3.1 The p oblem o he bandwid h
A adi ionalp oblemo SIMDa chi ec u esis hedesign
o a memo y sys em able o p o ide enough memo y e e -
ences pe cycle o keep he SIMD unc ional uni s busy. As
shown by Toni Juan e . al. [14], ue mul i-po ed caches
a e no easible due o hei high cos . Al e na i e cache de-
signs o ue mul i-po ed caches a e se e al, each wi h i s
d awbacks: ime-mul iplexing(as in he Alpha 21264 [15]),
mul i-banking, po widening, e c.
Mul i-bankingconsis so implemen ing
B
memo ypo s
connec ed wi h a se o cache memo y banks by means o a
c ossba (see Ýgu e 2-a). A ec o memo y ins uc ion can
dis ibu e i s di e en memo y e e ences among all a ail-
able memo y po s. While his conÝgu a ion p esen s he
ad an age o pe o ming well o di e en s ides, scalabil-
i y is comp omised because o bank con en ion and imple-
men a ion issues o he c ossba o an ele a ed numbe o
memo y po s.
Po widening is a mo e es ic i e (bu cheape ) al e na-
i e, based on inc easing he g anula i y o he memo y ac-
cesses. Gi en a ec o memo y ins uc ion whose elemen s
a e consecu i ely a anged in memo y, we can e ch se e al
elemen s in a single access p o ided ha hey a e loca ed
jpeg encode jpeg decode mpeg2 decode mpeg2 encode gsm encode
1.0
1.2
1.4
1.6
Pe o mance slowdown
MOM mul i-banked cache
MOM ec o cache
Figu e 3. Pe o mance slowdown o ealis ic
memo y sys em con igu a ions.
in he same cache line. The ec o cache [16] is a s aigh -
o wa d implemen a ion o his concep . As shown in Ýg-
u e 2-b, he ec o cache is based on loading wo whole
cache lines (one pe in e lea ed bank) ins ead o indi idu-
ally loading each ec o elemen . Addi ional logic (an in e -
change swi ch, a shi e and a mask logic)allows selec ing a
chunk o up o
B
consecu i e wo ds, being he uppe bound
o
B
he size o a single cache line. I s main d awbacks a e:
Ý s , i may add ex a la ency due o he shi &mask logic,
and second, i is no able o p o idemo e han one e e ence
pe cycle when he ec o s ide in di e en han one.
In o de o e alua e he e Ýciency o he wo di e en
cache designs, we ha e measu ed he pe o mancedeg ada-
ion o a 8-way issue p ocesso able o execu e MOM in-
s uc ions, o a se o benchma ks om Mediabench [17].
Figu e 3 shows he p ocesso pe o mance slowdown o
wo di e en cache designs: (a) a 4-po mul i-bankedcache
(wi h 8 memo y banks), and (b) a ec o cache wi h one
single po o wid h 4

64 bi s. Pe o mance deg ada ion
is gi en ela i e o pe o mance o an idealis ic memo y
sys em (pe ec cache, 1-cycle o la ency, unbounded band-
wid h). De ails abou he a chi ec u e conÝgu a ion can be
ound in sec ion 5.3.
Resul s show ha some o he benchma ks ha e signi -
ican pe o mance deg ada ions when aking in o accoun
a ealis ic memo y implemen a ion ( anging om 8% o
58%). As he cache hi a es a e ela i ely high ( om 90%
o 99%), he eason ha explains such dec eases in pe o -
mance is no o he han he e ec i e bandwid h p o ided by
he memo y po s. Resul s also show ha he ec o cache
ob ains slowdowns easonably simila o hose o he mul i-
banked conÝgu a ion, while being much easie o imple-
men .
3.2 Iden i ying he po en ial o a hi d dimension
As seen in he p e ious subsec ion, some media bench-
ma ks ha e se e e pe o mance sho comings due o he
P oceedings o he 35 h Annual IEEE/ACM In e na ional Symposium on Mic oa chi ec u e (MICRO-35)
1072-4451/02 $17.00 © 2002 IEEE
k
i
j
l
MMX memo y pa e n
MOM (2D) memo y pa e n
3D memo y pa e n
i
i
j
in ullsea ch(blk1, blk2, leng h, i0, j0, in win)
unsigned cha *blk, *blk2;
in leng h, i0, j0, win;
{
in l, d, i, j, k, min, pos;
unsigned cha *a,*b;
...
...
o (k=0; k<l; k++) {
a = blk1 + k;
b = blk2;
d = 0;
o (j=0; j<8; j++) {
o (i=0; i<8; i++) {
d += abs(a[i]-b[i]);
}
a += leng h;
b += leng h;
}
i (d<dmin) {
min = d;
pos = k;
}
}
...
...
}
Figu e 4. N-dimensional memo y pa e ns in a MPEG2 ke nel.
inabili y o any o he p oposed ec o memo y sys ems
o p o ide he equi ed bandwid h. A way o iden i y he
sou ces o he p oblem may come om a close obse a ion
o MOM 2-dimensional memo y pa e n cha ac e is ics.
I we u n back a he exampleshown i Ýgu e 1, we eal-
ize ha he e is a long dis ance be ween consecu i e MOM
elemen s (as he s ide be ween wo di e en MOM egis-
e elemen s co esponds o he ho izon al size o he im-
age). The e o e, a ec o memo y sys em such as he ec o
cache is unable o e ch mo e han one MOM egis e ele-
men pe cycle, as wo consecu i e elemen s a e placed in
non-consecu i ecache lines
Indeed, as al eady shown in [10, 11], s ided ma ices a e
a e y common da a s uc u e in mul imedia. These ma i-
ces a e laid ou in memo y in such a way ha , while he
elemen s in a single ow o one ma ix a e consecu i ely
a anged in memo y, elemen s beyond he Ý s dimension
a e dis ibu ed ac oss a away cache lines. F om he se o
benchma ks, only jpeg decode and gsm encode own
memo y pa e ns cha ac e ized o wide blocks o consecu-
i e da a along a single dimension. To sol e his p oblem,
some au ho s p opose simply ea anging he da a o Ý a
be e layou . We ha e ound ha mos o he imes is ei he
no possible (due o he way he benchma ks a e w i en) o
coun e p oduc i e (since i may p oduce e en wo se mem-
o y beha io in o he s ages o he applica ions).
Ou claim is ha he solu ion o his p oblem may eside
in he exploi a ion o mo e dimensions o he media mem-
o y layou han hose al eady exploi ed by 2D ec o s ISAs.
Mo e dimensions b ing mo e oppo uni ies o Ýnd longe
se s o da a consecu i ely a anged in memo y, and hence,
mo e oppo uni ies o ully exploi he peak bandwid h o a
wide memo y po .
I we look u he in o he n-dimensionals uc u e o me-
dia da a, we can ealize ha a se o MOM 2-dimensional
s eams as a whole shows a highe le el o spa ial and em-
po al locali y han e e y s eam in isola ion. I we eo de
he way we access he s eams, we can ake ad an age o
he exis ence o longe chunks o da a and om he edun-
dancyin insic o he o e lappingo di e en 2-dimensional
s eams.
In he p e ious example (see Ýgu e 4), he ow elemen s
o ma ices
a
and
b
a e ex emely spa se. The e o e, i we
use a ec o cache, we a e only able o ga he he eigh 8-bi
elemen s o one ow wi h a single access.
Ne e heless, when looking a he hi d dimension o
he algo i hm (co esponding o loop
k
), we can obse e
a 3-dimensional memo y pa e n composed o a se o 2-
dimensional ma ices. These 2D ma ices a e laid ou on he
x-axis o he image ( he loop
i
) wi h an add ess o se (o
s ide) o one single by e. The o e all s uc u e is a ec an-
gula ma ix o leng h
(8 +
l
;
1)

8
. The in e es ing poin
o his s uc u e is ha i exposes se e al elemen s consec-
u i ely a anged in memo y and ha i de e mines a high
amoun o po en ial MOM 2D memo y s eams inside, as
he e is a high amoun o o e lapping be ween hem.
The main poin is ha , e en hough
k
loop canno be
ully ec o ized,we can ec o ize he memo y access o his
3-dimensional memo y pa e n, as he e a e no memo y de-
pendences be ween he ma ices o e e y ins ance o loop
k
.
P oceedings o he 35 h Annual IEEE/ACM In e na ional Symposium on Mic oa chi ec u e (MICRO-35)
1072-4451/02 $17.00 © 2002 IEEE
By doing so, we a e able o inc ease he e ec i e memo y
bandwid h (as we a e exposing longe chunks o da a), and
we a e able o educe he memo y a Ýc (as we can a oid
e ching epea edly edundan da a when s eams o e lap).
4 3D memo y ec o iza ion
We p opose a no el ec o memo y access echnique
based on implemen ing a new se o 3D ec o egis e s.
These 3D ec o egis e s will be used as empo al s o age
o 3D memo y s eams e ched om memo y. By doing
sequen ial accesses o hese second-le el egis e s, we will
be able o con enien ly ea ange he 3D memo y pa e n o
accommoda e 2D MOM memo y accesses.
A 3D ec o egis e is basically a widened e sion o a
common MOM egis e . A 3D ec o load ins uc ion al-
lows o ans e mul iple cache lines inside he di e en ele-
men s o a single 3D ec o egis e . A e wa ds, he da a in
he 3D egis e Ýle can be ans e ed o he MOM egis e
Ýle using a 3D ec o mo e ins uc ion. In he same ein
ha he MOM egis e Ýle, he 3D egis e Ýle is o ganized
in lanes (o clus e s). This o ganiza ion enables e y high
bandwid h ans e s wi h low ha dwa e complexi y.
I is e y impo an o no e ha om a com-
pile /p og amme poin o iew, 3D memo y ins uc ions
can be used e en i he hi d ou e loop is no s ic ly ec o -
izable. We a e using hese ins uc ions o s ic ly e ch da a
om memo y and o ea ange he da a la e on. The e o e,
hose compu a ional dependences no ela ed o ead/w i e
conÐic s be ween he 2D memo y s eams can be igno ed.
Ou p oposed 3-dimensional memo y ec o iza ion ech-
nique p o ides h ee signiÝcan ad an ages:

longe chunks o da a accessed e e y cycle

educ ion o cache a Ýc by means o egis e euse

mo e elemen s packed pe ec o memo y ins uc ion
In his pape , we will quan i y how well he 3D memo y
ins uc ions do imp o e he leng h o he chunks o da a o
be accessed, educe he cache a Ýc and inc ease he num-
be o elemen s packed pe memo y ins uc ion. Finally, we
will e alua e he impac o hese ac o o e pe o mance,
powe and obus ness o he la ency.
4.1 Seman ics o he 3D memo y ins uc ions
We ha eused he MOMIns uc ionSe A chi ec u e [18]
as a ep esen a i e example o a 2D media ec o ISA. Ou
objec i e is o e alua e he po en ial o ex ending a 2D
ins uc ion epe oi e wi h 3D memo y ins uc ions. The
MOM Ins uc ion Se A chi ec u e con ains 121 ins uc ions
and 16 logical 2D ec o egis e s. Each 2D ec o egis e
is composed o 16 MMX-like elemen s o 64-bi each. The
ISA includes a Vec o Leng h egis e ha keeps ack o
he numbe o MOM elemen s o be ope a ed. Addi ionally,
MOM memo yins uc ions includean ex aÝeld con aining
he Vec o S ide o con ol he load and s o e o 2D memo y
pa e ns.
We ha e made wo modiÝca ions o he basic MOM a -
chi ec u e: he se o logical egis e s has been expanded
wi h he inclusion o wo 3D ec o egis e s, and he in-
s uc ion epe oi e includes wo new ins uc ions designed
o ans e da a o/ om hese new egis e s.
A3D ec o egis e is a widened e sion o a egula
MOM egis e (see Ýgu e 5 o a compa ison o bo h kinds
o egis e s). Ins ead o 16 elemen s o 8 by es, a 3D ec-
o egis e con ains 16 elemen s o 128 by es (16 x 64 bi s),
enough o Ý a ypical L2 cache line. E e y 3D ec o eg-
is e has also a 7-bi poin e egis e , which main ains he
cu en o se wi hin he 3D ec o egis e . This o se de-
e mines which slice o da a is going o be ans e ed o a
2D MOM ec o egis e .
The wo new ins uc ions ha e he ollowing syn ax and
seman ics:
3D Vec o Load. This ins uc ion has he o m
D load
3
DR
i
<
=
R
j
,
R
k
,W,b.
3
DR
i
is one o he wo 3D logical
ec o egis e s.
R
j
is he base add esswhe e he loads a s.
R
k
is he ec o s ide.
W
is an 4-bi immedia e alue which
indica es he wid h o each 3D- egis e elemen . Finally,
b
is a Ðag ha indica es he ini ial alue o he 3D- egis e
poin e .
The seman ics o he ins uc ion a e as ollows (see Ýg-
u e 5-a): s a ing a add ess
R
j
, loada block o
W

64
;
bi
in o he Ý s posi ion o 3D egis e
i
. Repea he p ocess,
adding he s ide egis e
R
k
o he cu en base add ess, o
he nex
VL
;
1
elemen s o he 3D egis e (being
VL
he
con en s o he Vec o Leng h egis e ). The alue o he
egis e poin e is ei he he beginningo he end o he eg-
is e , acco ding o he alue o he Ðag
b
( his allows o mo e
along he wo ways o he hi d dimension).
3D Vec o Mo e. This ins uc ion allows o mo e one
subse o he 3D logical ec o egis e in o a 2D MOM eg-
is e and has he o m 3d mo
MR
i
<
=3
DR
j
,
P
s
.
MR
i
s ands o
he MOM des ina ion egis e .
3
DR
j
is he 3D logical ec-
o egis e om whe e he da a is going o be ans e ed.
P
s
is he poin e s ide.
The seman ics o he ins uc ion a e as ollows (see Ýg-
u e 5-b): s a ing a
o se
(
o se
being he con en s, in
by es, o he poin e egis e associa ed wi h
3
DR
j
), mo e
a 64-bi sub-block om 3D- egis e
j
o he MOM egis-
e Ýle
i
. This p ocess is epea ed
VL
imes (
VL
being he
con en s o he Vec o Leng h egis e ). Finally, upda e he
cu en alue o he 3D egis e poin e by adding
P
s
.
5 E alua ion backg ound
In his sec ion we p esen he me hodology we ha e ol-
lowed o e alua e he beneÝ s o he 3D memo y ec o ex-
ensions o he MOM ISA, and we quan i y he imp o e-
P oceedings o he 35 h Annual IEEE/ACM In e na ional Symposium on Mic oa chi ec u e (MICRO-35)
1072-4451/02 $17.00 © 2002 IEEE

...
...
16
16 x 64 bi s
(a)
by e
by e
...
...
3D poin e
Shi & Mask
W
VL
64 bi s
64 bi s
(b)
16
16 x 64 bi s
by e
64 bi s
VL
3D egis e
W
13D egis e
2D (MOM) egis e
VL
16
Figu e 5. 3D ec o memo y ins uc ions (a) 3D ec o load ( om he ec o cache o one 3D egis e )
(b) 3D ec o mo e ( om one 3D egis e o one MOM egis e ).
men s o he new 3D memo y ins uc ions compa ed wi h
he o iginal 2D memo y ins uc ions.
5.1 Benchma ks and Code Gene a ion
We ha e used he se o modiÝed benchma ks desc ibed
in [10]. F om he Mediabench sui e [17], he au ho s
ew o e a se o ep esen a i e examples o ideo, image
and audio applica ions, using wo e sions o media ISA
ex ensions: a 1D

-SIMD ISA (simila o MMX) and
MOM. We ha e selec ed hose wi h he highes ec o -
iza ion pe cen age: mpeg2 encode,mpeg2 decode,
jpeg encode,jpeg decode and gsm encode. The
benchma ks show a wide selec ion o ypes o media mem-
o y s eams, hus beingsui able o e alua ing he gene ali y
o ou 3D memo y ins uc ions.
We ha e modiÝed he emula ion lib a ies and aces ob-
ained using ATOM [19], so ha we a e able o include 3D
memo y ins uc ions o he MOM e sions o he bench-
ma ks. The 3D memo y ins uc ions we e added o hose
loops ha ulÝlled ei he o he ollowing condi ions: (a)
he e was po en ial o e ch mo e ha one MOM s eam
by loading a whole cache line, and (b) he e was po en ial
o euse a he 3D egis e Ýle le el due o o e lapping be-
ween wo o mo e MOM memo y s eams. F om he se o
benchma ks, only jpeg decode did no ha e sui able 3-
dimensional memo y pa e ns o be exploi ed wi h ou ech-
nique.
Fo ou ini ial e alua ion, he 3Denhancedcode has been
hand-w i en a e a ca e ul s udy o he algo i hms. We be-
lie e,howe e , ha hecompile suppo needed o gene a -
ing such ins uc ions is ela i ely easible o implemen , due
o he na u e o he analysis. Since we a e only ec o izing
memo y e e ences, we do no need o check dependences
beyond hose ela ed o conÐic ing eading and w i ing 2D
memo y s eams. As media ke nels usually ha e lo s o 2D
loads and no 2D s o es, he analysis is commonly i ial (de-
ec ing he s ide be ween he 2D load ins uc ions o pack
hem oge he in o a single 3D load and eplacing he o igi-
nal 2D load ins uc ions wi h 3D ec o mo es).
5.2 Cha ac e is ics o he new ins uc ions
In he p e ious sec ion, we claimed ha he pe o mance
beneÝ s om he new 3D memo y ins uc ions would come
om h ee main ac o s. In his sec ion we will b ieÐy quan-
i y hem and discuss hei beneÝcial impac o e he a chi-
ec u e.
A. Longe da a chunks accessed pe cycle. Ou 3D
memo y ins uc ions ocus on e ching wide blocks o da a
o cap u e slices om di e en MOM memo y s eams. As
a esul , hey exhibi he po en ial o ob ain mo e e ec i e
P oceedings o he 35 h Annual IEEE/ACM In e na ional Symposium on Mic oa chi ec u e (MICRO-35)
1072-4451/02 $17.00 © 2002 IEEE
jpeg encode jpeg decode mpeg2 decode mpeg2 encode gsm encode
0
2
4
6
e ec i e bandwid h (wo ds/access)
MOM mul i-banked cache
MOM ec o cache
MOM+3D ec o cache
Figu e 6. E ec i e memo y bandwid h (in
wo ds ans e ed pe access) o he di e -
en memo y sys ems and ISA enhancemen s.
bandwid h om a ec o cache conÝgu a ion, ha is able o
access as many elemen s as he wid h o a cache line. To
show his p ope y, Ýgu e 6 shows he e ec i e bandwid h
o di e en cache implemen a ions wi h and wi hou 3D in-
s uc ions. We conside he e ec i e bandwid h o be he
a e age numbe o wo ds ha can be ob ained wi h a single
access o he cache (o o se e al banks concu en ly in he
case o he mul i-banked cache).
As shown in he Ýgu e, 3D memo y ec o iza ion makes
e y good use o he simple ec o cache implemen a-
ion, inc easing he e ec i e memo y bandwid h o se e al
benchma ksand being e en be e han he expensi emul i-
banked conÝgu a ion.
Ha ing longe consecu i e se s o da a o access each cy-
cle will ansla e in o wo main beneÝ s. Fi s , we will in-
c ease he e ec i e bandwid h o he ec o memo y sys-
em, hus educingpe o manceslowdown. Second, we will
ga he mo e da a e e y ime we access he cache, hus e-
ducing he cache ac i i y (and as a di ec consequence, he
powe consump ion).
B. Reduc ion o he cache a ic. As we ha e a second-
le el egis e Ýle ha is awa e o he beha io o he memo y
e e ences a he hi d dimension, we ha e oppo uni ies o
educe he a Ýc o he cache bymeans o eusing ( o allyo
pa ially) s eams a he 3D egis e Ýle le el. Fo ins ance,
we may ha e 2D s eams wi h da a o e lapping (as in he
example o sec ion 2), o se s o 2D s eams ha become
in a ian a he hi d dimension o he nes ed loops.
In o de o ealize he impac o egis e euse o e a Ýc
educ ion, we may look a Ýgu e 7. In he Ýgu e, we p esen
he ec o cache a Ýc educ ion when including a 3D ec-
o egis e Ýle, measu ed as he educ ion o 64-bi wo ds
ans e ed om o o he ec o cache sub-sys em.
Reusing da a a he egis e Ýle le el has a clea impac
on he powe consump ion o he sys em (as he accesses o
he 3D egis e Ýle a e cheape , in ene gy e ms, han he
accesses o he cache banks). Addi ionally, he la ency o
jpeg encode jpeg decode mpeg2 decode mpeg2 encode gsm encode
0
20
40
60
80
100
Cache a ic educ ion (%)
Figu e 7. Vec o cache a ic educ ion when
using 3D ec o iza ion (in 64-bi wo ds ans-
e ed).
MOM MOM + 3D
1s 2nd 3 d 1s 2nd 3 d (max)
mpeg2encode 7.2 10.1 ñ 7.2 9.3 1.5 (5)
mpeg2decode 4.2 7.4 ñ 4.2 6.2 1.7 (3)
jpeg encode 4.1 8.2 ñ 4.1 7.8 1.9 (16)
jpeg decode 5.5 15.9 ñ 5.5 15.9 ñ
gsm 4.0 10.0 ñ 4.0 10.0 7.7 (16)
Table 1. Memo y ins uc ion ec o leng h o
each o he h ee dimensions.
he 3D egis e Ýle is much sho e han he cache, hus p o-
iding a way o alle ia e he p ocesso -memo y speed gap
impac .
C. Longe ec o memo y ins uc ions. I is widely
known ha he longe he ec o so a gi ena chi ec u e, he
be e he abili y o ole a e memo y la ency. Ou 3D mem-
o y a chi ec u e ex ension p o ides wo main beneÝ s ha
ha e he po en ial o be e ole a e inc eases in he la ency
o he memo y ins uc ions. Fi s , we a e ac ually doing a
so o so wa e p e e ching, as a 3D memo y ins uc ion
igge s he e ching o s eams o da a se e al cycles be o e
hey will be eally needed. Second, we pack mo e elemen s
pe memo y ins uc ion, hus aking ad an age o he ela-
ion be ween he ec o leng h and he ole ance o memo y
la ency.
Table 1 p esen s he a e age ec o leng h along each di-
mension in e e y memo y ins uc ion ( wo dimensions o
plain MOM memo y ins uc ions, h ee dimensions when
including 3D memo y ins uc ions). Taking in o accoun
ha he 3D memo y ins uc ions a e ypically less p edomi-
nan han he 2D memo y ins uc ions (as hey a e a ound 4
imes longe , and hence, ewe 3D loads a e equi ed when
aking ad an age o he 3D egis e euse), we may ealize
how he hi d dimension is con ibu ing o he amoun o
da a ead by each ins uc ion.
P oceedings o he 35 h Annual IEEE/ACM In e na ional Symposium on Mic oa chi ec u e (MICRO-35)
1072-4451/02 $17.00 © 2002 IEEE
MMX MOM
Fe ch a e 8 8
g adua ion window 128 128
Load/S o e queue 32 32
INTEGER issue 4 4
INTEGER FUs 4 4
SIMD issue 4 1
SIMD FUs 4 1x4
memo y issue 4 2
L1 memo y po s 4 2
L2 ec o memo y po s n/a 1x4
Table 2. P ocesso con igu a ions.
5.3 Modeled a chi ec u e
We ha e used he Jinks simula o [10] o model an ag-
g essi e 8-way ou -o -o de supe scala p ocesso . The p o-
cesso is enhanced wi h i s own independen mul imedia
pipeline and SIMD egis e Ýle. We ha e wo e sions o
he same model, able o execu eei he MMX-s yle o MOM
ins uc ions. A chi ec u al pa ame e s a e summa ized in
able 2. As seen, he MMX conÝgu a ion is agg essi e in
numbe o egis e s and unc ional uni s o a oid an un ai
compa ison wi h MOM.
No e ha he MOM p ocesso has one SIMD unc ional
uni wi h ou lanes o clus e s. E e y clus e is able o pe -
o m one MOM ope a ion/cycle om he same MOM in-
s uc ion, hus p o iding o e all he same FU bandwid h
han he MMX p ocesso (Ýgu e 8-b illus a es he MOM
lane conÝgu a ion).
In o de o implemen he combined 2D/3D memo y
mechanism in he MOM a chi ec u e, we need o include
wo new egis e Ýles: he3D Vec o Regis e File, ha con-
ains 4 physical 3D ec o egis e s and he 3D Poin e Reg-
is e File which keeps he cohe en alues o he poin e s
o each logical 3D ec o egis e . No e ha he enaming
p ocess o he 3D physical ec o egis e s and he physical
poin e egis e s is no he same. Fo ins ance, a 3d mo
ope a ion (which mo es a slice om a 3D ec o egis e o
a MOM egis e ) causes he poin e egis e o be enamed,
as i s alue is upda ed using he poin e s ide. Table 3 sum-
ma izes he di e en egis e Ýle conÝgu a ions. We ha e
assumed 3 cycles o la ency o he 3D ec o egis e Ýle
(bu 1 cycle pe ans e ).
We ha e es ima ed he a ea cos o he di e en egis e
Ýles using he models desc ibed in [20]. Es ima ed egis-
e Ýle a eas (in squa e wi e acks) and o e all no malized
a eas ( ela i e o he MMX-like p ocesso ) a e included in
able 3.
Figu e 8 shows he ec o memo y sub-sys em imple-
men a ion. Ou basic cache hie a chy model is simila o
he Alpha 21364 [21] one, whe e bo h L1 and L2 caches
a e loca ed on-chip. The L1 cache is a 64 KB, 2-way se
associa i e, w i e- h ough cache wi h 32-by e lines. The
L2 cache is a 2MB, 4-way se associa i e, w i e-back cache
MMX MOM MOM+3D
MMX/MOM Regis e File
egis e size 64 b 16x64b 16x64b
logical/physical egis e s 32/80 16/36 16/36
ead po s (pe lane) 12 3 3
w i e po s (pe lane) 8 2 2
max memo y bandwid h 4 4 4
es ima ed a ea (
w
2
) 2,826,240 2,654,208 2,654,208
cache buses (
w
2
) 262,144 262,144 n/a
Accumula o Regis e File
egis e size n/a 192b 192b
logical/physical egis e s n/a 2/4 2/4
ead po s n/a 1 1
w i e po s n/a 1 1
es ima ed a ea (
w
2
) n/a 23,040 23,040
3D Vec o Regis e File
egis e size n/a n/a 16x16x64b
logical/physical egis e s n/a n/a 2/4
ead po s (pe lane) n/a n/a 1
w i e po s (pe lane) n/a n/a 1
max memo y bandwid h n/a n/a 16
es ima ed a ea (
w
2
) n/a n/a 1,966,080
3D Poin e Regis e File
egis e size n/a n/a 7b
logical/physical egis e s n/a n/a 2/8
ead po s n/a n/a 2
w i e po s n/a n/a 2
es ima ed a ea (
w
2
) n/a n/a 3,136
Es ima ed RF a ea 3,088,384 2,939,392 4,646,464
O e all no malized a ea 1.00 0.95 1.50
Table 3. Mul imedia egis e ile con igu a-
ions.
wi h 128-by e lines. L1 da a cache la ency is 1 cycle while
L2 cache la ency is 20 cycles. The ins uc ion cache has
no been simula ed gi en he ex emely low ins uc ion miss
a es measu ed.
We ha e decided o adop he same cache hie a chy con-
Ýgu a ion p oposed o he o iginal MOM a chi ec u e [16,
22]. In his a chi ec u e, he MOM memo y accesses bypass
he L1 cache and go s aigh o he L2 cache. As in e e -
ence be ween ec o and scala da a migh occu , a simple-
cohe ence p o ocol, based on an exclusi e-bi policy, was
p oposed.
Se e al easons explain why is wo h paying he ex a
la ency and implemen ing he ec o memo y sub-sys em
o e he second le el o cache. Fi s , we a oid jeopa dizing
he L1 cycle ime and la ency, hus no comp omising scala
pe o mance,which is pa amoun o he a ge a chi ec u e.
Second, he L2cache has longe cache lines han heL1 da a
cache, hence inc easing he po en ial pe o manceo he al-
eady cos -e Ýcien ec o cache implemen a ion.
Looking a Ýgu e 8-a and 8-b , we can compa e he im-
plemen a ion o a 4-po mul i-banked cache and a ec o
cache o he o iginal MOM a chi ec u e. The in e connec-
ion logic o he ec o cache is signiÝcan ly simple han
i s mul i-bankedcoun e pa . No e, howe e , ha he ec o
cache peak bandwid h is limi ed by he numbe o lanes o
he MOM pipeline (4 o ou conÝgu a ion). E en hough
P oceedings o he 35 h Annual IEEE/ACM In e na ional Symposium on Mic oa chi ec u e (MICRO-35)
1072-4451/02 $17.00 © 2002 IEEE
Shi & Mask
In e change
Ini ial Add ess Final Add ess
VRF0 VRF1 VRF2 VRF3
(a)
Shi & Mask
In e change
Ini ial Add ess Final Add ess
3D
VRF
0
3D
VRF
1
(c)
3D
VRF
2
3D
VRF
3
VRF0 VRF1 VRF2 VRF3
VRF0 VRF1 VRF2 VRF3
bank 0 bank 1 bank 2 bank 3 bank 4 bank 5 bank 6 bank 7
X
(b)
64
64
64 64 64 64
64 64 64 64 64 64 64
64
16x64
64
64
64
64
64
64
64
64
64
64
Figu e 8. Vec o memo y sub-sys em imple-
men a ions: (a) mul i-banked cache, (b) ec-
o cache, and (c) ec o cache and second-
le el 3D ec o egis e ile.
he 4x8 c ossba equi ed o he mul i-banked cache is no
simple, we ha e no conside ed any ex a la ency o he
cache access pipeline.
Figu e 8-cshows he ec o memo ysys em implemen a-
ion, bu his ime o he MOM a chi ec u e wi h 3D mem-
o y ins uc ions. No e ha he 3D ec o egis e Ýle is dis-
ibu ed o e as many lanes as he MOM egis e Ýle. The
di e en widened elemen s o he 3D physical ec o eg-
is e s a e dis ibu ed wi hin hese lanes. All he di e en
3D ec o lanes a e connec ed o he same a ay o bi lines.
So, e e y cycle, a chunk o up o 128 by es o da a can be
e ched om he L2 cacheand can be di ec lyw i en in pa -
allel o one o he 3D ec o egis e Ýle lanes. The e o e,
he e ec i e memo y bandwid h may be as la ge as he size
jpeg encode jpeg decode mpeg2 decode mpeg2 encode gsm encode
1.0
1.2
1.4
1.6
Pe o mance slowdown
MMX-like mul i-banked cache
MMX-like ideal memo y
MOM mul i-banked cache
MOM ec o cache
MOM+3D ec o cache
Figu e 9. Pe o mance slowdown o he di -
e en ISA and memo y sub-sys em con igu-
a ions.
o a whole L2 cache line. While la ge chunks o da a a e
w i en in one o he 3D ec o lanes, one 64-bi elemen
can be ead om each o hese lanes. As a esul , we ha e a
peak ans e a e o ou 64 bi s elemen s pe cycle be ween
he 3D ec o egis e Ýle and he MOM egis e Ýle. No e
ha he 3D egis e Ýle allows by e-aligned accesses. F om
he poin o iew o implemen a ion, we would ypically e-
qui e a mechanism ha e ches wo consecu i e quadwo d-
aligned elemen s and ha is able o use a shi &mask logic
block o ex ac he equi ed 64-bi elemen .
6 Pe o mance and powe bene i s o 3D
memo y ec o iza ion
In his sec ion we will e alua e he beneÝ s p o ided by
3D memo y ec o iza ion in e ms o pe o mance slow-
down ela i e o an idealis ic memo y sys em and will an-
alyze he impac o inc easing he cachela ency. Finally, we
will oughly es ima e he powe sa ings le e aged by he
educ ion o he cache ac i i y.
6.1 Pe o mance slowdown wi h ealis ic memo y
Figu e 9 shows he pe o mance slowdown o di e en
ISA and memo y sub-sys em conÝgu a ions, ela i e o he
pe o mance o a MOM p ocesso wi h an idealis ic mem-
o y sys em (single cycle o la ency, e ec i e bandwid h
equal o he peak bandwid h). The Ýgu e allows us o de-
e mine how well a gi en memo y sys em pe o ms o e a
speciÝc ISA s yle.
Fi s , Ýgu e 9 allows us o see he e ec o a ealis-
ic memo y implemen a ion o e he pe o mance o he
MMX-like conÝgu a ion p ocesso . As seen in he Ýgu e,
so wa e p e e chingcombinedwi h a way o a oiding bank
collisionswouldapp oxima e hepe o manceo heMMX-
like sys em o he one o an idealis ic memo y sys em, bu
i would s ill be a om he pe o mance o he idealis ic
MOMsys em (1.31Xo pe o manceslowdownina e age).
The eason is ha he MMX-s yle p ocesso is limi ed by is-
sue bandwid h and no by memo y bandwid h.
P oceedings o he 35 h Annual IEEE/ACM In e na ional Symposium on Mic oa chi ec u e (MICRO-35)
1072-4451/02 $17.00 © 2002 IEEE