SYNCHRONIZED ACCESS TO STREAMS IN
MULTIPROCESSORS
Mon se Pei on, Ma eo Vale o, Edua d Ayguadé and Tomás Lang∗
Depa amen d’A qui ec u a de Compu ado s, Uni e si a Poli ècnica de Ca alunya
G an Capi à s/n, Mòdul D4, 08034 - Ba celona (Spain)
Phone: + 34 - 3 - 401 71 88, Fax: + 34 - 3 - 401 70 55
email: [email p o ec ed]
∗Depa men o Elec ical and Compu e Enginee ing, Uni e si y o Cali o nia a I ine
Abs ac
The synch onized and simul aneous access o se e al
ec o s ha o m a single s eam occu s in SIMD ec o
mul ip ocesso s as well as in MIMD supe scala
mul ip ocesso s wi h decoupled access. In his pape we
p opose a block-in e lea ed s o age scheme and an ou -o -
o de access mechanism ha allows con lic - ee access o
s eams wi h an a bi a y ini ial add ess and cons an s ide
be ween elemen s. A maximal numbe o con lic - ee
amilies including he mos commonly used s ides can be
ob ained. We conside he use o a c ossba in e connec ion
ne wo k, al hough he me hod applies also o he case o a
mul is age in e connec ion ne wo k.
Keywo ds
SIMD Vec o mul ip ocesso s, Mul i-module memo ies,
Vec o s wi h cons an s ide, Con lic - ee access.
1.- In oduc ion
To ha e a su icien memo y bandwid h, he memo y o
ec o p ocesso s is o ganized as se e al modules ha can
be accessed simul aneously. Fo a sys em wi h P po s, o
achie e he maximum h oughpu o P accesses pe
p ocesso cycle i is necessa y o ha e a leas P.T memo y
modules, being T he la ency o each memo y module (o
he a io be ween he memo y cycle and he p ocesso
cycle). In his con ex , a memo y sys em is ma ched when
i is composed o exac ly M = P.T memo y modules and
unma ched when M > P.T.
To achie e his maximum h oughpu he s eam access has
o be pe o med so ha no memo y con lic s occu . This
has been ex ensi ely s udied o ec o unip ocesso
sys ems wi h a single memo y po (P = 1). As summa ized
in [1], s o age schemes ha e been p oposed o p oduce
ei he con lic - ee access o ec o s wi h some s ides o
minimum a e age la ency o uni o m dis ibu ion o
s ides. In his la e case, bu e s can be added o achie e
high h oughpu o long ec o s. O pa icula in e es o
his pape is he scheme p oposed in [2], which inc eases
he numbe o con lic - ee s ides by accessing he ec o
elemen s ou o o de .
In his wo k we a e conce ned wi h an ex ension o he
p e ious esul s o he case in which he e a e P po s (P
p ocesso s wi h one po each o ewe p ocesso s wi h
se e al po s pe p ocesso ). We conside he special case
in which a single s eam is di ided equally among he po s
and he accesses o hese po s is sinch onized, so ha each
po eques s one elemen pe cycle. This mode o
ope a ion is easonable in SIMD ec o mul ip ocesso s o
in MIMD sys ems wi h decoupled access, in which he da a
can be accessed in his egula and synch onized manne ,
bu hen used di e en ly ( o example in a scala o m). In
[3] a s o age scheme called In e lea ed Pa allel Scheme
(IPS) is p oposed, as well as an ou -o -o de access. This
allows a con lic - ee access o s eams wi h he mos -
equen ly used s ides [4] when he in e connec ion
ne wo k is a uni e sal mul is age ne wo k (a Benes
Ne wo k). Each p ocesso needs o p ecalcula e he
add esses o all i s ec o elemen s and hen he p ocesso s
send hei eques s in a synch onized manne .
We p esen he e an al e na i e solu ion o his p oblem,
based on he echniques de elopped in [2]. We conside he
use o a c ossba in e connec ion ne wo k, al hough he
me hod applies also o he case o a mul is age
in e connec ion ne wo k [5].This echnique allows
con lic - ee access o he same numbe o s ides as in [3].
Howe e , i does no equi e he p ecalcula ion o he
add esses o he s eam no he use o a Benes
in e connec ion ne wo k. We p esen he ma ched-memo y
case, an ex ension o he unma ched memo y case being
discussed in [5]. The echnique is p esen ed using a block-
in e lea ing s o age scheme, bu he same esul s a e
ob ained using ei he skewing o a linea ans o ma ion.
The me hod equi es wo add ess gene a o s o ad ance he
calcula ion o a ew add esses. We es ima e ha he
addi ional ha dwa e has a cos ha is only a small ac ion
o he cos o he p ocesso and he memo y sys em.
2.- A chi ec u al model and condi ions o a
con lic - ee access.
We s udy he beha io o memo y accesses in a
mul ip ocesso sys em wi h he s uc u e shown in Figu e
1. I is composed o P = 2s po s and M = 2m memo y
modules g ouped in 2s sec ions, so he e a e 2m-s modules
pe sec ion; he la ency o he memo y modules is T = 2 .
The memo y sys em is ma ched, i.e., m = s+ .
Figu e 1: S uc u e o he sys em.
Po s a e connec ed o sec ions h ough a 2s-inpu , 2s-
ou pu c ossba in e connec ion ne wo k, and modules in a
sec ion a e connec ed by a single bus. This o ganiza ion
allows he ini ia ion each p ocesso cycle o one access pe
sec ion, as long as he eques ed module is no busy wi h a
p e ious eques . The maximum achie able h oughpu is
hen P accesses pe p ocesso cycle a e he ini ial
ansien s a e.
The po s a e con olled by ec o load/s o e ins uc ions
and in e ace wi h he p ocesso s h ough ec o egis e s
o leng h L = 2λ.
As shown in Figu e 2, po i accesses ec o Vi composed
o L consecu i e elemen s o he s eam. The s ide o he
s eam is S and he ini ial add ess is A0. As done in [6], we
classi y he s ides in o amilies, whe e he amily de ined
by x is he se o s ides S = σ⋅2x wi h σ odd.
Figu e 2: Vec o s in a s eam.
The elemen s o a s eam a e dis ibu ed among he
memo y modules in a way ha depends on he s o age
...
...
sec ion 0
sec ion 2s-1
po 0
po 2s-1
2sx2s
In e con.
Ne wo k
0T-1
0T-1
... ...
2λ
V0V1ViV2s-1
el. i.2λ; add ess = A0 + i.2λ.S
elemen 0; add ess = A0
2λ1
scheme used; we say ha he s o age scheme de ines he
spa ial dis ibu ion o a s eam [2]. The e m empo al
dis ibu ion o a s eam e e s o he o de in which i s
elemen s a e eques ed.
We now de e mine necessa y condi ions on he spa ial
dis ibu ion o allow con lic - ee access o he s eam.
In he mul ip ocesso a chi ec u al model desc ibed abo e,
he ollowing wo ypes o con lic s p e en con lic - ee
access:
a) memo y module con lic s. These occu when a eques
a i es o a module while i is busy.
b) sec ion con lic s, which occu when wo simul aneous
eques s a e o he same sec ion.
A necessa y condi ion o a oid memo y module con lic s is
ha each module does no con ain mo e han L/P.T
elemen s o he s eam. This is e iden because o con lic -
ee access L/P.T memo y cycles a e equi ed, which is no
possible i a module has addi ional elemen s.
Simila ly, o a oid sec ion con lic s, each sec ion has o
con ain he same numbe o s eam elemen s.
When a spa ial dis ibu ion sa is ies hese wo condi ions,
we say ha i is balanced. Consequen ly, ou app oach is o
use a s o age scheme ha p oduces balanced spa ial
dis ibu ions o a la ge numbe o s ides, including he
mos equen . Then, we look o con lic - ee empo al
dis ibu ions o hese cases.
3.- Add ess mapping and balanced s eams
Since he memo y is o ganized in se e al sec ions and each
sec ion in se e al modules, an add ess mapping is equi ed
which ans o ms he physical add ess A wi h bina y
ep esen a ion an-1,...,a0 in o a uple (sec ion, supe module,
displacemen ) ( he e m supe module e e s o he module
numbe wi hin a sec ion).
Figu e 3: S o age scheme used in his pape .
We use a block-in e lea ed s o age scheme as add ess
mapping, as illus a ed in Figu e 3. Fo he mapping
pu poses, he add ess is di ided in o h ee ields as ollows:
- he S- ield o s bi s, speci ying he sec ion;
- he M- ield o bi s, speci ying he supe module;
- he es o he bi s o he add ess speci y he
displacemen inside he module.
c1
...
supe module numbe sec ion numbe
A: c1+s ... c0
an-1
s
a0
...
S- ield M- ield
The wo ields a e loca ed as shown in Figu e 3. No e ha
he M- ield and he S- ield should no in e sec (i hey do
in e sec , some modules will ne e be isi ed), so c1≥c0+ .
The pe iod o his ans o ma ion is 2c1+s.
Lemma
Fo he add ess mapping conside ed, a s eam wi h ini ial
add ess A0, leng h L1 = 2λ1 and s ide S = σ.2x is balanced
i x ≤c0 and λ1 ≥ c1+s-x (see [5] o he p oo ).
Since a balanced spa ial dis ibu ion is a necessa y
condi ion o con lic - ee access we wan an add ess
mapping ha sa is ies his condi ion o he maximum
numbe o amilies o s ides. Mo eo e , since s ide 1 is
e y equen , we include his s ide and use he add ess
mapping o Figu e 4, which p oduces balanced s eams o
s ides o he amilies x = 0, 1, ..., c0.
Figu e 4: S o age scheme o a con lic - ee access o amilies
0, 1, ..., c0.
c1
...
A:
c1+s a0
an-1
s
λ
c0...
S- ield M- ield
4.- Con lic - ee empo al dis ibu ion
Fo he balanced s eams ob ained, we now ind con lic -
ee empo al dis ibu ions. Two condi ions ha e o be
sa is ied:
C1.-The P simul aneous eques s mus no ha e sec ion
con lic s.
C2.-Consecu i e accesses o a memo y module ha e o
be sepa a ed by T cycles.
One s eam may ha e many con lic - ee empo al
dis ibu ions; he access o de ings ha we p opose sa is y
he ollowing p ope ies:
P1) Simul aneous accesses go o di e en sec ions ( his is
necessa y, and equi alen o C1).
P2) Simul aneous accesses go o he same supe module.
P3) T consecu i e accesses go o di e en supe modules.
P2 and P3 a e a pa icula way o sa is ying condi ion C2
and esul in a simple ha dwa e o add ess calcula ion [5].
We now de e mine an ou -o -o de accessing scheme ha
sa is ies hese condi ions o he balanced amilies o he
add ess mapping o Figu e 4.
Figu e 5: (a) S o age scheme. (b) Add ess mapping. (c) Mapping o he elemen s o a s eam wi h A0 = 4 and S = 4
sec ion 0 1 2 3
supe module 0123012301230123
0 8 16 24 32 40 48 56 64 72 80 88 96 104 112 120
1 9
7 15 23 31 39 47 55 63 71 79 87 95 103 111 119 127
128 136 144 152 160 168 176 284 192 200 208 216 224 232 240 248
one pe iod
...
...
...
...
sec ion 0 1 2 3
supe module 0123012301230123
8 16 24 32 40 48 56 64 72 80 88 96 104 112 120
4 12 20 28 36 44 52 60 68 76 84 92 100 108 116 124
128 136 144 152 160 168 176 184 192 200 208 216 224 232 240 248
132 140 148 156 164 172 180 188 196 204 212 220 228 236 244 252
256 264 272 280 288 296 304 312 320 328 336 344 352 360 368 376
260 268 276 284 292 300 308 316 324 332 340 348 356 364 372 380
384 392 400 408 416 424 432 440 448 456 464 472 480 488 496 504
388 396 404 412 420 428 436 444 452 460 468 476 484 492 500 508
512
λ
x(a)
V0
V1
V2
V3
Pe iod o he s o age scheme: 128
(b)
(c)
No e ha access in o de p oduces con lic - ee access only
o he pa icula case o λ = . Conside , o ins ance, s =
= 2 and λ = 5; his esul s in c1 = 4 and c0 = 2 (Figu e 5.a);
Figu e 5.b shows one pe iod o he add ess mapping. The
elemen s o a s eam wi h A0=4 and S=4 (σ =1 and x=2) a e
mapped as shown in Figu e 5.c; we show he elemen s
belonging o each ec o Vi as well. Obse e ha , o
ins ance, he elemen s k and (k+1) wi h k odd o each
ec o a e in he same memo y module, so hey canno be
eques ed in successi e cycles.
So, he goal is o eo de he access o he elemen s o he
s eam o ob ain a con lic - ee empo al dis ibu ion. To
achie e his we do he ollowing:
1.Di ide each ec o in o sequences o T elemen s ( he
elemen s o a sequence a e in gene al no consecu i e
ec o elemen s). The elemen s o he s eam a e
iden i ied by he iple: ec o numbe i (0 ≤ i≤ P-1),
sequence numbe j (0 ≤ j ≤ L/T-1), and elemen numbe
k (0 ≤k≤T-1).
2.The access is pe o med pe sequence, i.e.,
o j ;sequences
o k ;elemen s o a sequence
access elemen (j,k) o all i simul aneously
To achie e con lic - ee access o each sequence we de ine
he mapping o elemen s o he ec o s in o sequences as
desc ibed by Figu e 6. No e ha he di ision depends on
he s ide amily, and ha sequences a e iden i ied by he
alues o ju and jd.
Because o he limi ed space we conside only he case in
which x ≥ s (see [5] o he case x < s).
Figu e 6: Elemen k o sequence j o ec o Vi.
Po Pi accesses ec o Vi in he ollowing o de :
o ju = i o (i+2x-1) mod 2x
o jd=0 o 2c0-x-1
o k=0 o T-1
access elemen (j,k)
In he example o Figu e 5, he sequences a e buil as
shown in Figu e 7.
In his way, he simul aneously eques ed elemen s ha e
add esses
o some α = 0...2x-1 and β = 0...2c0-x-1.
These P add esses a e mapped in sec ion
Aijk / 2c1 mod 2s =
This exp ession akes di e en alues o he P alues o i,
so p ope y P1 is sa is ied. Mo eo e , hese add esses a e
mapped in o he supe module
jd
i
λ
λ1
jukc0-x
x
Ai,j,k = A0 + (i.2λ + k.2c0-x + j).σ.2x(j = ju.2c1-x + jd)
k
c1
... a0
an-1
λc0...
sx
( i β ).σ + A0
(i+α)mod2x
Aijk:
A0kσ2c0 βσ2x
+ +
2c1
------------------------------------------------- iα+( ) mod2xσ⋅+
 
 
 
 mod2s
=
Figu e 7: Sequences in a s eam wi h A0=4 and S=4 wi h L=32, P=4 and T=4.
sec ion 0 1 2 3
supe module 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3
8 16 24 32 40 48 56 64 72 80 88 96 104 112 120
4 12 20 28 36 44 52 60 68 76 84 92 100 108 116 124
128 136 144 152 160 168 176 184 192 200 208 216 224 232 240 248
132 140 148 156 164 172 180 188 196 204 212 220 228 236 244 252
256 264 272 280 288 296 304 312 320 328 336 344 352 360 368 376
260 268 276 284 292 300 308 316 324 332 340 348 356 364 372 380
384 392 400 408 416 424 432 440 448 456 464 472 480 488 496 504
388 396 404 412 420 428 436 444 452 460 468 476 484 492 500 508
512
V0
V1
V2
V3
: i s sequences : second sequences : hi d sequences
This exp ession is independen om i, so P2 is also
ul illed. Accessing consecu i e elemen s o he sequences
means gi ing T consecu i e alues o k in he abo e
exp ession; since he esul ing alues a e di e en , P3 is
also sa is ied and access o one sequence is con lic - ee.
Al hough each sequence is accessed wi hou con lic s, he
access o consecu i e sequences migh lead o con lic s in
he memo y modules. In Figu e 7, o ins ance,
supe modules a e isi ed in he o de <0,1,2,3> by he i s
sequences and in he o de <1,2,3,0> by he second ones;
all he eques made in he i h cycle collide wi h hose
made in he second cycle.
To sol e hese in e sequence con lic s, we use wo add ess
gene a o s, as shown in Figu e 8. Du ing he i s T cycles,
he add esses o he i s sequence a e calcula ed and used
o memo y access; in addi ion, i s supe module o de is
s o ed in a ci cula shi egis e . Meanwhile, he add esses
o he second sequence a e calcula ed and s o ed in a se o
bu e s. A e ha , o each sequence, he add esses o
access a e ob ained om he bu e s unde he con ol o
he shi egis e , and new add esses a e calcula ed o s o e
(so, he second add ess gene a o wo ks only du ing he
i s T cycles).
The addi ional ha dwa e equi ed is one add ess gene a o ,
a ci cula shi egis e and 2.T bu e s.
Figu e 8: Ha dwa e equi ed o sequence eo de ing.
Aijk
2c0
---------- mod2 =A0βσ2x
+
2c0
-------------------------- kσ+
 
 
 mod2
ini ial @ o ViS
(s, sm, d)
1 2
mux
. . . .
2T bu e s o de
add ess
gene a o s
a bi e
sequence1 o he sequences
o he memo y sys em
supe module
5.- Conclusions
We ha e p esen ed a scheme o access in a con lic - ee
manne a s eam ha is di ided among P p ocesso po s.
The basis o he scheme is o pe o m a synch onized and
ou -o -o de access. In his manne , con lic - ee access is
achie ed o a window o amilies o s ides. Unlike a
p e iously p oposed me hod, his scheme does no equi e
he p ecompu a ion o he add esses, bu compu es hem
easily on- he- ly. The me hod has been p esen ed o a
ma ched memo y sys em and a c ossba in e connec ion
ne wo k. Howe e , i has been ex ended o he unma ched
case and o he use o mul is age ne wo ks.
This wo k has been suppo ed by he Minis y o Educa ion o
Spain unde con ac TIC-880/92, by he ESPRIT Basic Resea ch
Ac ion 6634 APPARC and by he CEPBA (Eu opean Cen e o
Pa allelism o Ba celona).
Re e ences
1. D.T. Ha pe III, "Add ess T ans o ma ions o Inc ease
Memo y Pe o mance", In . Con . on Pa allel
P ocessing, pp. 237-241, 1989.
2. M. Vale o, T. Lang, J.M. Llabe ia, M. Pei on, E.
Ayguade and J.J. Na a o, "Inc easing he Numbe o
S ides o Con lic -F ee Vec o Access", In . Symp. on
Compu e A chi ec u e, pp. 372-381, 1992.
3. A. Seznec and J. Len an , “In e lea ed Pa allel
Schemes: Imp o ing Memo y Th oughpu on
Supe compu e s”, In . Symp. on Compu e
A chi ec u e, pp. 246-255, 1992.
4. H. Tamu a, Y. Shinkai and F. Isobe, “The
Supe compu e FACOM VP Sys em”, Fuji su Techical
Jou nal, 1985.
5. M. Pei on, M. Vale o, E. Ayguadé and T. Lang,
"Synch onized Access o S eams in SIMD Vec o
Mul ip ocesso s", Resea ch Repo DAC 93/05, 1993.
6. D.T. Ha pe III and D. A. Lineba ge , "Con lic -F ee
Vec o Access Using a Dynamic S o age Scheme",
IEEE T ans. on Compu e s, ol. 40, no. 3, pp. 276-283,
1991.