Synchronized access to streams in multiprocessors

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.