Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://www.arcetri.astro.it/science/plasmi/docs/mpi/simularcetri2003.pdf Äàòà èçìåíåíèÿ: Fri Jun 18 14:55:14 2004 Äàòà èíäåêñèðîâàíèÿ: Sat Dec 22 11:22:19 2007 Êîäèðîâêà: Ïîèñêîâûå ñëîâà: trees

Applicazioni di Calcolo Parallelo in Astrofisica

Claudio Gheller CINECA c.gheller@cineca.it

Firenze, 10-11 Giugno 2003, C. Gheller


Astronomia e Computer: un legame molto stretto.
DALLE OSSERVAZIONI ALLA TEORIA

L'uso del calcolatore Õ indispensabile in ogni passo della ricerca astronomica: · Sviluppo e progettazione di nuovi strumenti di osservazione · Controllo e gestione delle strumentazioni (telescopi, satelliti) · Acquisizione dei dati, telemetria · Data management e compressione · Riduzione e analisi dei dati · Elaborazione dei risultati · Realizzazione di modelli teorici · Confronto tra osservazioni e modelli teorici
Firenze, 10-11 Giugno 2003, C. Gheller


Simulazioni Numeriche

Le simulazioni numeriche, sono la realizzazione dei modelli teorici · · · Descrizione del modello Condizioni iniziali Equazioni evolutive
· · ·

Rappresentazione dello spazio Approssimazione del modello Algoritmi di soluzione delle equazioni
· ·

Ricostruzione degli osservabili Confronto con le osservazioni
Firenze, 10-11 Giugno 2003, C. Gheller


Simulazioni numeriche in astrofisica
I campi applicativi sono innumerevoli: Il sistema solare
Il sole, nascita ed evoluzione dei pianeti...

Le stelle
Struttura, evoluzione, ammassi...

Le galassie
Nascita, evoluzione...

La cosmologia
ProprietÞ ed evoluzione dell'Universo

Firenze, 10-11 Giugno 2003, C. Gheller


Cosmological Simulations Cosmological simulations are challenging applications since:
There are no special symmetries. Full 3-D simulations (periodic boundary conditions); No special shapes of the forming structures. Dar k M at t er Bar yons N-Body; Hydr odynami cs. What is a Cosmological Simulation ??? A cosmological simulation has the object of describing the birth and the evolution of the cosmological structures (galaxies, galaxy clusters, filaments) following th e dynamics of all the components: baryons (typically fluid description), dark matter and stars (Nbody)...

Tw o di f f er ent ki nd of mat t er t o be t r eat ed ( di f f er ent model s ­ di f f er ent al ghor i t ms) . Must describe a representative fraction of the universe. Cosmol ogi cal st r uct ur es ar e i nf l uenced by phenomena on a n enor mous r ange of scal es DYNAMICAL RANGE = 109 !!!

10 ­ 100 Mpc; i.e. 1020 ­ 1021 km. St ar f or mi ng r egi ons ( 1 pc) ; Gal axi es ( 10 kpc) ; Cl ust er s of gal axi es ( 1 M pc) ; Pr essur e f or ces ( 10 Mpc) ; Gr avi t y ( 100 M pc) .

Firenze, 10-11 Giugno 2003, C. Gheller


Applicazioni Cosmologiche
Viene simulato un volume di dimensioni confrontabili all'intero universo (1/100) Cosa possiamo imparare ???

Fisica fondamentale e universo primordiale
Interazioni fondamentali, Big Bang, Inflazione, transizioni di fase...

COBE mi ssi on: map of t he i nf r ar ed sky
Di pol e map

Di pol e subt r act ed map

La piÛ recente immagine del Big Bang (MAP)

Mi l ky w ay subt r act ed map T= 2.73 K, dT/ T = 10-5 Resol ut i on 10°

Firenze, 10-11 Giugno 2003, C. Gheller


Cosa possiamo imparare??? Struttura e proprietÞ delle galassie e degli ammassi di galassie
X-r ay i mage of t he Vi r go Cl ust er
16 Mpc* f ar aw ay 2.5° r adi us ( compar e t o moon 0,25°)

X-r ay i mage of t he Coma Cl ust er
100 Mpc f ar aw ay Mor e t han 1000 gal axi es

*1 Mpc = 1019 km

X-r ay i mage of a Si mul at ed Cl ust er
St andar d CDM model 2563 si mul at i on

Temper at ur e of i nf al l i ng mat t er
Tem per at ur es r ange f r om 0 t o 108 K

... e cosË via...

Firenze, 10-11 Giugno 2003, C. Gheller


Quanto costa una simulazione ???
le strutture cosmologiche sono influenzate da processi che si sviluppano su un range di scale enorme; alcuni esempi:
·l

e stelle si formano su scale ~ 1 parsec (1016km) ·le galassie sono su scale ~10 kparsec ·le forze di pressione influenzano scale ~ 10 Mparsec ·la gravitÞ agisce sino a scale comparabili con quella dell' niverso, ~ 1000 u Mparsec Il range dinamico ideale sarebbe quindi di 109 !!!!!!!! Vediamo cosa significa questo in termini di memoria del calcolatore: 1283 5123 1024
3

Min. 170 Mbyte Qualche ora/giorno Min. 10 Gbyte Qualche settimana Min. 80 Gbyte Qualche mese

PC Server multiprocessore Supercomputer

Firenze, 10-11 Giugno 2003, C. Gheller


Descrizione del problema

Le osservazioni ci dicono che l' niverso e' ostituito da 3 componenti fondamentali: u c la materia barionica: protoni, neutroni - costituisce tutto cio' he emette "luce" ; c la radiazione: prodotta dai corpi celesti e residuo del Big Bang (radiazione di fondo) - la sua densita' i energia e' olto minore di quella della materia; d m la materia oscura: natura ignota (neutrini massivi, altre particelle elmentari, pianeti ???...) - scoperta nelle galassie confrontando le curve di rotazione delle stelle (indice della ( distribuzione di massa totale) con le curve di luminosita' indice della distribuzione di barioni). Confermata poi da innumerevoli altre osservazioni

Firenze, 10-11 Giugno 2003, C. Gheller


Soluzione del Problema

Focalizziamoci sulle due componenti materiali: la materia oscura ha solo interazioni a lungo raggio (gravita'. Per essa e' deguato ) a un approccio numerico tipo N-Body: la materia e' rappresentata come un insieme di particelle il cui comportamento e' descritto dalla soluzione delle relative equazioni del moto la materia barionica risente anche di interazioni a corto raggio: essa quindi puo' venire piu' adeguatamente descritta come un fluido, la cui evoluzione viene caratterizzata dalla soluzione di un sistema di equazioni che stabiliscono la conservazione di ·materia ·quantita' di moto ·energia Infine e' necessario calcolare il campo gravitazionale che accoppia le due componenti.

Firenze, 10-11 Giugno 2003, C. Gheller


Equazioni del modello Materia oscura: equazioni del moto.

Materia Barionica: equazioni di conservazione.

+ equazione di stato

Campo e Forze Gravitazionali: equazione di Poisson.
Firenze, 10-11 Giugno 2003, C. Gheller


L'algoritmo Fl idodinamico alle Differenze Finite

Con l' pproccio alle differenze finite spazio e tempo engono rappresentati in a modo discreto, come griglia comp tazionale m ltidimensionale. S q esta griglia le engono definite le q antitÞ caratteristiche del sistema. Q este possono enire interpretate come:
· ·

alori medi s lle cella della griglia, alori p nt ali s i nodi della griglia.

S lla griglia spazio-temporale, engono riscritte in modo approssimato le eq azioni che caratterizzano la dinamica del sistema, in modo che esse dipendano dai alori delle q antitÞ caratteristiche approssimati s lla griglia stessa.

Firenze, 10-11 Gi gno 2003, C. Gheller


L'algoritmo Fl idodinamico alle Differenze Finite Con l' pproccio alle differenze finite spazio a modo discreto, come griglia comp taziona L' ea base del modello n merico e'a seg id l La materia barionica iene descritta come
·il

e tempo engono rappresentati in le m ltidimensionale. ente: n fl ido;

fl ido e' escritto attra erso la s a densita'la s a pressione, la s a elocita' d , ; ·lo spazio iene rappresentato da na griglia di NxNxN elementi; ·le ariabili del fl ido engono calcolate s lle celle della griglia; ·i alori calcolati sono i alori medi della ariabili s lle celle; ·q esti alori sono calcolati risol endo con na q alche approssimazione n merica le eq azioni di conser azione:

...ad esempio, al primo ordine (scarsa acc ratezza), in na dimensione, l' q azione di e conser azione della massa si p Ð approssimare alle differenze finite come:

Firenze, 10-11 Gi gno 2003, C. Gheller


Parallelizzazione di algoritmi fl idodinamici alle differenze finite

A(i , j)

E' n problema "semplice". Per loro intrinseca nat ra le eq azioni fl idodinamiche sono locali. Pertanto la parallelizzazione del codice si p Ð ottenere in modo efficiente attra erso na s ddi isione a blocchi del dominio, tipo q ella presentata per l'analisi delle immagini. Il codice ris ltante scala molto bene ed e' molto ben bilanciato. Algoritmi di q esto tipo si prestano molto bene alla parallelizzazione !!!

Firenze, 10-11 Gi gno 2003, C. Gheller


Esempio: Data la localitÞ sol zione il processo bisogno di conoscere la prima riga di da processi N-1 e N+1 della N ha SOLO ti dei

Si p Ð di idere il dominio comp tazionale a "bande".

PE N+1
Ghost Region

PE N
Ghost Region

PE N-1

L' array contenente la ariabile iene definito con 2 righe in piÛ, contenenti le "Ghost Regions". La com nicazione coin olge escl si amente le ghost regions e i bordi. Il resto del calcolo Õ completamente locale.
Firenze, 10-11 Gi gno 2003, C. Gheller


L'algoritmo N-Body

Nel caso di sim lazioni cosmologiche di sola materia osc ra, si considera la sola massa, q indi le sole interazioni gra itazionali. In generale com nq e la proced ra p o' ssere generalizzata a casi piÛ articolati e complessi: e
·ogn ·la

i particella ha massa M data;

elocitÞ di ogni particella iene calcolata in istanti di tempo s ccessi i (discretizzazione del tempo) risol endo le eq azioni del moto con opport ne tecniche alle differenze finite.

forza gra itazionale che agisce s ciasc na particella iene calcolata attra erso n' pport na approssimazione n merica. o

·La

Firenze, 10-11 Gi gno 2003, C. Gheller


Dinamica delle Particelle Eq azioni del moto Approx. del primo ordine

Approx. del secondo ordine: Leapfrog

Approx. del secondo ordine: Lax Wendroff (two steps)

Firenze, 10-11 Gi gno 2003, C. Gheller


Calcolo delle Forze

Approx. del primo ordine

Metodo Particle Particle (PP): la forza s na particella Õ la ris ltante di t tte le interazioni con le altre particelle

Vantaggi - acc ratezza, risol zione Limiti - n mero di particelle (scala con N2)

Metodi Tree: la forza Õ lo s il ppo di m ltipolo do distrib zione delle particelle

to alla

Vantaggi - risol zione, scalabilitÞ (N log(N)) Limiti - complessitÞ della costr zione dell' lbero a

Firenze, 10-11 Gi gno 2003, C. Gheller


Metodo Particle Mesh la forza iene calcolata attra erso na doppia trasformata di Fo rier s l campo di densitÞ associato alla distrib zione di particelle ... Vantaggi - scalabilitÞ, rapiditÞ, semplicitÞ dell' lgoritmo a Limiti - Risol zione spaziale
1)

2)

3)

4)

discretizzo lo spazio con na griglia c bica si lato L, n mero di p nti per dimensione N e (q indi) risol zione spaziale dx=L/N. calcolo il campo di densitÞ associato alla distrib zione di particelle distrib endo la massa di ciasc na particella s i p nti griglia. risol o l' q azione di Poisson (che lega la e densitÞ al potenziale gra itazionale) attra erso na proced ra FFT. In q esto modo calcolo il campo gra itazionale s lla griglia. calcolo la forza differenziando il potenziale e stimo la forza che agisce s lla particella con na proced ra analoga alla 2).

Firenze, 10-11 Gi gno 2003, C. Gheller


Particle Mesh: distrib zione dei dati Distib zione dei dati tra i processori: In q esto caso esistono d e tipi di ettori ·q elli che descri ono le particelle (posizione, elocita' ); ·q elli che descri ono i campi s lla griglia (potenziale gra itazionale, densita' ). q esti ltimi engono distrib iti a piani paralleli. Le particelle engono s ddi ise tra i processori: NB: non c' ' orrelazione tra la posizione delle ec particelle locali ad n processore, l' del id processore, e il piano della griglia locale a q el processore

Q esto Õ n problema essenziale per la parallelizzazione !!!

Firenze, 10-11 Gi gno 2003, C. Gheller


Firenze, 10-11 Gi gno 2003, C. Gheller


Firenze, 10-11 Gi gno 2003, C. Gheller


Firenze, 10-11 Gi gno 2003, C. Gheller


Particle Mesh: considerazioni.

1)

in generale na particella sarÞ locale ad n processore di erso da q ello che possiede i dati s griglia necessari a calcolarne la dinamica. il n mero di particelle che "migrano" cambia contin amente e in modo disomogeneo man mano che la sim lazione procede.

2)

q esto porta ad n algoritmo che in generale richiede molta com nicazione e forti sbilanciamenti nel carico di la oro che ogni processore de e realizzare !!!

Firenze, 10-11 Gi gno 2003, C. Gheller


Particle Mesh: distrib zione del la oro. La scelta delle modalitÞ di distrib zione del la oro Õ q indi particolarmente delicata per l' fficienza del codice. e Nel caso piÛ semplice, si p Ð decidere se far s olgere il la oro al processore che ha locale la particella o q ello che ha locali i dati s griglia. Se lo s olge il PE che "possiede" la particella de o fargli a ere t tti i dati delle celle icine: gli algoritmi standard di distrib zione della massa o di calcolo delle forze richiedono da 8 a 27 celle. In q esto modo com nq e ogni processore calcola la dinamica di NPART_TOT/NPES particelle (perfetto bilanciamento). Se il la oro lo s olge il PE che "possiede" le celle q esto de e richiedere soltanto 6 informazioni (la posizione e la elocita' della particella. ) T tta ia si potrebbe erificare che n solo PE eseg e t tto il la oro mentre gli altri attendono inoperosi. La scelta q indi dipende dal bilancio tra q este d e opposte esigenze: assic rare che la com nicazione sia minima e garantire n b on bilanciamento del carico di la oro.
Firenze, 10-11 Gi gno 2003, C. Gheller


Particle Mesh: distrib zione del la oro. Implementazione MPI Nel esempio che seg e, abbiamo in ece implementato la seconda strada, che p Ð portare a forti sbilanciamenti, ma ottimizza la com nicazione. L' plementazione Õ basata s im MPI. Consta dei seg enti step:
·In

di id azione della posizione della particella s lla griglia ·Creazione di liste di particelle associate ai ari processori ·Com nicazione dei dati delle particelle tra i ari processori ·Calcolo della densita' ·Calcolo del potenziale ·Calcolo della forza ·Integrazione delle eq azioni del moto La strategia Õ q indi processori di ersi da informazioni, in n competenza che a completamente local q q n q e ella di sapere in anticipo q elli a c i appartengono e ico processo di com nica esto p nto possono eseg ali particelle cadono in com nicare le relati e zione, ai processori di ire il calcolo in modo

Firenze, 10-11 Gi gno 2003, C. Gheller


Particle Mesh: distrib zione del la oro. Implementazione MPI Q esto tipo di implementazione consente il controllo completo della com nicazione ma necessita di sostanziali modifiche rispetto alla ersione seq enziale. Step 1: creo alc ni array per lo scambio di informazioni "generali" tra i processori
all all co co oc oc nt nt ate ate _pe _pe ( ( _s _r co nt_pe_s(npes),STAT=error) co nt_pe_r(npes),STAT=error) =0 =0 Ogni posizione in q esti array contiene il n mero di particelle che do ranno essere in iate/rice te a / da n processore remoto.

! ! find how many particles fall in each processor ! n_tot_s=0 do ipart=1,nparmax In q esto loop l' array i3=int(x3(ipart)+0.5) effetti amente riempito. if(i3.eq.0)i3=npes*nz ipe3=(i3-1)/nz if(ipe3.ne.mype)then co nt_pe_s(ipe3+1)=co nt_pe_s(ipe3+1)+1 n_tot_s=n_tot_s+1 Conto q ante particelle in totale ogni processore in ia endif enddo

iene

Firenze, 10-11 Gi gno 2003, C. Gheller


Particle Mesh: distrib zione del la oro. Implementazione MPI

Step 2: com nico il n mero di particelle che i ari processori si scambiano.
CALL MPI_Alltoall ( co nt_pe_s, 1, MPI_INTEGER, co nt_pe_r, 1, MPI_INTEGER, MPI_COMM_WORLD, ierr )
... or, sing send end rec ...

do i=1,npes i t f C

e.mype)then 1 i-1 _ISend(co nt_pe_s(i),1,,to_pe,10,& MPI_COMM_WORLD,ierr) CALL MPI_IRec ( (i),1,,& from_pe,10,,stat s,ierr) endif

f o r A

( _ o L

ipe m_ L

1 = p M

. i e P

n = I

enddo

Firenze, 10-11 Gi gno 2003, C. Gheller


Particle Mesh: distrib zione del la oro. Implementazione MPI Step 3: Sapendo q ante particelle de ono enire com nicate, preparo i b ffer con c i com nicare le rispetti e posizioni e elocitÞ.
all all all all all all oc oc oc oc oc oc ate ate ate ate ate ate ( ( ( ( ( ( x1_ x2_ x3_ 1_ 2_ 3_ a a a a a a x_s x_s x_s x_s x_s x_s (n (n (n (n (n (n _to _to _to _to _to _to t_ t_ t_ t_ t_ t_ s+1 s+1 s+1 s+1 s+1 s+1 ), ), ), ), ), ), STA STA STA STA STA STA T=error) T=error) T=error) T=error) T=error) T=error) do ipart=1,nparmax i3=int(x3(ipart)+0.5) if(i3.eq.0)i3=npes*nz ipe3=(i3-1)/nz if(ipe3.ne.mype)then index0=point_pe_a x x1_a x_s(index0)=x1 x2_a x_s(index0)=x2 x3_a x_s(index0)=x3 1_a x_s(index0)= 1 2_a x_s(index0)= 2 3_a x_s(index0)= 3 n_pepe(index0)=ipar point_pe_a x(ipe3+1 endif enddo

Step 4: Riempio i b ffer

(i (i (i (i (i (i (i t )=

pe3 par par par par par par

+1) t) t) t) t) t) t)

point_pe_a x(ipe3+1)+1

Firenze, 10-11 Gi gno 2003, C. Gheller


Particle Mesh: distrib zione del la oro. Implementazione MPI Step 5: Allo stesso modo alloco i ettori che do ranno rice ere i dati.
all all all all all all oc oc oc oc oc oc ate ate ate ate ate ate ( ( ( ( ( ( x1_ x2_ x3_ 1_ 2_ 3_ a a a a a a x_r x_r x_r x_r x_r x_r (n (n (n (n (n (n _to _to _to _to _to _to t+ t+ t+ t+ t+ t+ 1), 1), 1), 1), 1), 1), ST ST ST ST ST ST AT= AT= AT= AT= AT= AT= er er er er er er ror ror ror ror ror ror ) ) ) ) ) )

do i=1,n if((ito_p from inde inde stri stri

pe 1) e= _p x0 x1 de de

s .ne i-1 e=i =po =po 0=c 1=c

.mype)then -1 in in o o

t_p t_p nt_ nt_

e( e_ pe pe

i) r(i) _s(i) _r(i) x_r(index1),stride1,MPI_DOUBLE_PRECISION,& pe,20,MPI_COMM_WORLD,req(1),ierr) x_s(index0),stride0,MPI_DOUBLE_PRECISION,& ,20,MPI_COMM_WORLD,req(2),ierr)

...
CALL MPI_Irec (x1_a from_ CALL MPI_Isend(x1_a to_pe

...
CALL MPI_WAITALL(12,req,stat s_array,ierr) endif Firen enddo

ze, 10-11 Gi gno 2003, C. Gheller


Particle Mesh: distrib zione del la oro. Implementazione MPI Step 6: gli array di send non ser ono piÛ. Per risparmiare spazio li elimino...
dea dea dea dea dea dea ll ll ll ll ll ll oca oca oca oca oca oca te te te te te te (x (x (x ( ( ( 1_ 2_ 3_ 1_ 2_ 3_ a a a a a a x x x x x x _s _s _s _s _s _s ) ) ) ) ) )

Step 7: t tti i dati sono ora locali ai processori. Posso procedere con il calcolo come se fosse seq enziale.
call density(x1_a x_r,x2_a x_r,x3_a x_r,n_tot) Calcolo il campo gra itazionale call fields Calcolo le forze gra itazionali call gra ity call nbody(n_tot,x1_a x_r,x2_a x_r,x3_a x_r,& 1_a x_r, 2_a x_r, 3_a x_r) Calcolo la densitÞ a partire dalle particelle

Sposto le particelle

Firenze, 10-11 Gi gno 2003, C. Gheller


Particle Mesh: distrib zione del la oro. Implementazione MPI

Step 8: ripeto al contrario q anto fatto in precedenza, riportando le informazioni s posizioni e elocitÞ delle particelle com nicate ai processori originari.

Step 9: dealloco t tti gli array a s operazione Õ tile a risparmiare q anto il n mero di particelle da array, cambiano ad ogni step e ol

iliari necessari alla com nicazione. Q esta memoria ma, sopratt tto, Õ necessaria in com nicare e q indi la dimensione degli ti o.

Firenze, 10-11 Gi gno 2003, C. Gheller


Particle Mesh: distrib zione del la oro. Implementazione MPI 2 MPI 1 non consentendo accessi asincroni (one-side comm nication) alla memoria, necessita, in q esto caso, di na " infrastr tt ra" pi ttosto complessa. Con MPI 2 si p Ð in ece ottenere n' implementazione molto piÛ snella, simile a q ella Open MP - shared memory ista in precedenza.
call MPI_FENCE(...) call MPI_WIN_CREATE(phi,8*N**3,MPI_DOUBLE_PRECISION,...) call MPI_FENCE(...) do j=1,npart ip=nint(x1(j)) jp=nint(x2(j)) kp=nint(x3(j)) If(la particella Õ "locale")then forza_media=... else call MPI_LOCK(MPI_LOCK_SHARED,...) call MPI_GET(dati necessari per il calcolo della forza) call MPI_UNLOCK(...) forza_media=... endif _new = _old + forza_media * dt aggiorno la elocita' x_new = x+old + _new *dt enddo call MPI_WIN_FREE(...)
Firenze, 10-11 Gi gno 2003, C. Gheller

tro o la posizione della particella s lla griglia

aggiorno la posizione


Tree Code In q esto caso NON iene introdotta alc na griglia comp tazionale... La forza s lla particella i-esima iene approssimata come somma dei contrib ti delle particelle " icine":

... e di q ell lontane, attra erso n' pprossimazione di m ltipolo del potenziale a gra itazionale:

o e con il pedice cm iene indicato il centro di massa dell' tero set di in particelle e con M la massa totale. Tipicamente si blocca lo s il ppo in serie all' rdine di q adr polo o

Firenze, 10-11 Gi gno 2003, C. Gheller


Tree Code

Q ali i antaggi ??? Il m ltipolo iene calcolato non s lle particelle, ma s n sottoinsieme di celle. Le celle engono calcolate secondo na proced ra ad albero: step 1: definisco n angolo critico A step 2: di ido il box comp tazionale in 8 celle ciasc na di dimensione l. Calcolo il centro di massa di ciasc na cella e calcolo la distanza d tra la particella e il centro di massa. Se l/d > A la cella Õ lontana e di essa si calcola il q adr polo, se l/d < A s ddi ido lteriormente la cella step 3: ripeto la proced ra fino a q ando rimango con cellette contenenti n' nica particella. A q este applico la legge di Newton. ot e o

Firenze, 10-11 Gi gno 2003, C. Gheller


Tree Code: implementazione parallela Viene attrib ito lo stesso n mero di particelle ad ogni processore. Utilizzando l' lbero le particelle a engono redistrib ite dinamicamente tra i processori d rante l' ol zione in e modo che particelle fisicamente icine siano anche nello stesso processore) Le celle dell' lbero engono n merate a progressi amente dalla piÛ grande alle piÛ piccole. I li elli piÛ grossolani engono distrib iti in modo ciclico, in modo da e itare il problema di accesso a risorse critiche: se i li elli piÛ grossolani fossero t tti s llo stesso processore t tti andrebbero ad accedere alla memoria di q el processore. I li elli piÛ fini sono in ece locali al processore che possiede il "padre".
Firenze, 10-11 Gi gno 2003, C. Gheller

D e tipi di ettori fondamentali:
·Par

ticelle (posizione, elocitÞ, e massa) ·Tree (posizione, massa del baricentro) La distrib zione dei dati Õ fatta in modo da garantire na distrib zione omogenea della memoria. Il la oro Õ distrib ito eq amente tra le particelle (load balancing)


Tree Code: implementazione parallela

Problema fondamentale del tree code. Calcolo della forza: ogni particella de e rec perare i dati remoti particelle " icine" che non stanno nello stesso processore t tti i q delle celle "lontane" Calcolo del tree: per calcolare la componenente di q adr polo cella p Ð essere necessario accedere a particelle "remote" (nel s della memoria) La com nicazione Õ estremamente pesante

di t tte le adr poli della e n so

engono tilizzate one side com nication (latenza minima) basate s : shmem T3E Origin 3000 LAPI SP3 Implementazione MPI 2 Õ in corso

Firenze, 10-11 Gi gno 2003, C. Gheller


Tree Code: ottimizzazione

1 Gro ping Particelle molto icine possono risentire approssimati amente della stessa interazione di q adr polo da celle lontane. Pertanto Õ in tile ricalcolarla per ogni na di q este particelle. E' ossibile q indi: p
·de

finire d e distanze caratteristiche R e D; rtendo da posizioni opport ne (zone particolarmente dense)

·pa

raggr ppare le particelle che stanno in na sfera di raggio R;
·ca

lcolare la forza s q este particelle come:
near

Ftot = F Fne
ar

+ Ffar, o e:

iene calcolata in modo "standard" per particelle e celle che distano

meno di D, Ffar iene calcolata na olta per t tte per particelle che distano piÛ di D.

Firenze, 10-11 Gi gno 2003, C. Gheller


Tree Code: ottimizzazione 2 Dynamic Load Balancing A ca sa dei di ersi tempi di calcolo delle forze per ciasc na particella, n processore p Ð terminare prima degli altri. In q esto caso (grazie alle one-side com nications, che non pres mono com nicazione) p Ð "ai tare" n' ltro processore a completare il s o a carico di la oro. 3 Data B ffering Spesso gli stessi dati, relati i a particelle o celle remote, ser ono per il calcolo delle forza che agisce s particelle di erse. Pertanto Õ stato implementato n meccanismo di "cache". La memoria del processore non allocata, iene riempita (per q anto possibile) con dati prele ati in precedenza s altri processori, che a q el p nto di engono locali.

Firenze, 10-11 Gi gno 2003, C. Gheller