OpenMP, skrive til delte arrays

[kyrsjo]

Hei!

 

Jeg har et program som (bla annet) simulerer diffusjon i plasma ved å kollidere partikler. Dette gjøres ca. som følger:

 

1. Del opp partiklene på en grid, ca 120 x 200 celler.

2. Velg tilfeldige par innenfor hver grid

3. Kollider disse parrene ved å la de endre retning

 

Jeg ønsker å paralellisere 2. og 3. ved å splitte grid'en over flere CPU'er, altså at CPU #0 tar celle 0...1000, CPU #1 celle 1001-3005, osv. Jeg har allerede skrevet en load-balancer som fordeler ca. like mange partikler til hver CPU (altså IKKE like mange celler), og bruker én CPU dersom det er for få partikler for å unngå overhead ved split/merge. Partiklene er allerede sortert på grid'en. Jeg vet i prinsippet hvordan jeg skal gjøre dette, men etter å ha lest

The minimum size at which memory accesses by multiple threads without synchronization, either to the same variable or to different variables that are part of the same variable (as array or structure elements), are atomic with respect to each other, is implementation defined. Any additional atomicity restrictions, such as alignment, are implementation defined.

i OpenMP 3.0 sin spesifikasjon, så lurer jeg: Er planen min egentlig trygg?

 

Dataene er lagret som ett flatt array, la oss kalle det "particles", hvor hvert element er en struct som inneholder info'en til partikkelen. Videre så hører det med et ekstra array av array-indexer, la oss kalle det "ordcount", hvor element #0 er antall partikkler i celle #0, #1 = partikler i celle #1 osv, slik at partiklene til celle #N ligger i particles #M1 - #M2, hvor M1 = sum(ordcount #0 ... #(N-1)), M2 = M1 + ordcount #N.

 

Det jeg dermed er redd for, er at når jeg tukler med de siste partiklene for celle #N, så skriver jeg over de første partiklene for celle #N+1 med potensielt utdaterte data - og omvendt.

 

Spørsmålet er derfor:

- Leser jeg spesifikasjonen riktig, og dette er noe jeg bør være redd for?

- Hva kan jeg gjøre for å unngå problemet?

- Hva kan jeg gjøre for å unngå problemet *på en rask måte*?

[kyrsjo]

For å si det på en enklere måte: Dersom tråd #1 leser og skriver til element #n, og tråd #2 leser og skriver til element #(n+1), er jeg da trygg? Eller risikerer jeg at #1 laster inn mange elementer til sin cache - både #n og #n+1 - og oppdaterer element #1 der, for så å skrive både #n og #n+1 tilbake til hovedminnet, men i mellomtiden så har tråd #2 lastet de to uendrede elementene, opptatert #n+1, og så skrevet tilbake både #n OG #n+1, og på denne måten overskrevet endringene i #n fra tråd 1 med den uendrede versjonen? Eller vil den bare skrive tilbake det som har blitt endret?

[kyrsjo]

Etter å ha googla litt mer, så ser det ut til at det jeg er redd for har et navn: "False sharing" (jeg har forøvrig hørt om dette tidligere). Det ser også ut til at dette er et potensielt problem for ytelse, ikke resultatets korrekthet slik som jeg fryktet.

 

Og det er godt - for jeg klarer ikke se at det kan bli et særlig stort problem for ytelsen (med midre cache-linjene er mange kb store - på sandy bridge = Intel i7 som vi stort sett bruker, så er størrelsen 64 bytes => null stress), hver CPU spiser array-indexer med start-punkt mange ti-tusen unna hverandre. Altså er eneste mulighet for å få en ytelsesdrepende krasj er dersom én tråd skulle bli "sittende fast" pga. bakgrunnsaktivitet på maskinen, eller dersom jeg har gjort en real tabbe i scheduler'n min, eller dersom brukeren har bedt om noen titalls tusen tråder...

 

Så, takk kjære forum for å gi meg en tavle å kaste tankene mine mot fram til én satt fast - og pliiis si i fra dersom du ser en bug i resonementet mitt

 

PS: Om DU vil prøve deg på litt enkel parallelisering, så er OpenMP et fint sted å starte. Og det krever ofte ikke at programmet er skrevet for det fra starten av, man kan fint slenge en "#pragma omp for" rundt en løkke, slenge på "-fopenmp" til kompilatoren, og vips så er man på kjøret

 

// Kyrre, prøver å redusere kjøretid fra ~1½ måned til et par uker

[Lycantrophe]

Det BØR være trygt siden det strengt tatt ikke jobber på samme minne.