MPI: C++ Datastructuren verdelen

[Verwijderd]

Ben bezig met een grote simulatie een Cray, is een soort supercomputer. Programmeer taal is C++, met MPI om het rekenwerk te parralleliseren. Heb nu het programma werkend zonder MPI, ben nu aan het twijfelen over hoe ik het verder ga aanpakken.

Heb een grote driedimensionale matrix, wordt steeds rekenwerk op uitgevoerd. Nu zou ik elke node steeds een stuk van de matrix kunnen geven en laten bewerken. De matrix is op dit moment een globale variabele. Als elke node na een berekening steeds een heel stuk matrix rond zou zenden naar de andere nodes krijg je nogal wat overhead, en da's niet de bedoeling.
De nodes moeten steeds de hele matrix kennen om de volgende berekenig uit te voeren, dus gewoon splitten is geen optie


Iemand die een geniale ingeving heeft hoe ik dit het beste kan aanpakken?


Groeten RuleKinG

[ACM]

Weet je zeker dat ze de _hele_ matrix moeten kennen?

Of toch eigenlijk alleen de randen met de buren (na wat gekunstel met de algoritme's evt)?
Als je dat laatste voor elkaar krijgt hoef je alleen elke iteratie de rande te updaten wat natuurlijk enorm veel scheelt.

Als het echt zo is dat ze de hele matrix moeten kennen weet ik niet precies hoe je dat kan optimaliseren, maar ook daar zijn in de literatuur vele oplossingen voor

Btw, het grootste deel van de optimalisaties die mogelijk zijn, zijn zo algoritme specifiek dat er nu werkelijk weinig hulp te bieden is.

[Exirion]

Op woensdag 03 juli 2002 14:56 schreef RuleKinG het volgende:
Iemand die een geniale ingeving heeft hoe ik dit het beste kan aanpakken?

Als alle data werkelijk overal bekend moet zijn dan heb je aardig wat communicatie overhead, en als alle stappen afhankelijk van elkaar zijn dan heb je wellicht ook synchronization overhead omdat ze op elkaar moeten wachten.

Wat ACM zegt, als je meer info geeft over het te implementeren algoritme dan zijn er misschien wat optimalisaties te bedenken. Nu kunnen we alleen wat algemene zaken noemen.

Als er in het algoritme dingen zijn te bedenken waardoor je:
1. de communicatie per stap kan beperken
2. de stappen onafhankelijk kunt maken
dan los je veel problemen op, en heb je performance winst.

[RickN]

Dat elke node elke iteratie de hele matrix moet kennen klink me eerlijk gezegd een beetje ongeloofwaardig in de oren. Ik krijg het idee dat je op een verkeerde manier parallellisme probeert te introduceren. Vertel idd eens iets meer over het algoritme, want zo kan eigenlijk niemand je helpen...

[toraq]

Het lijkt me raar als die matrixbewerkingen niet in deelbewerkingen opgedeeld kunnen worden. Een matrixbewerking is namelijk van zichzelf al een samengestelde bewerking. Je moet trouwens wat meer vertellen over je algoritme, zoals de anderen ook al aangeven.

[Verwijderd]

Ok, is gelukt om algoritme op te delen. Moet nog steeds veel data senden, maar moet zo lukken.
Dacht dat er misschien systeem was om data-structuur soort van MPI globaal te maken.
Bijvoorbeel eerste node kent de hele matrix, elke keer als andere nodes deel van de matrix aanspreken wordt dit door automatisch doorgestuurd en later weer opgeslagen. Zou handig zijn.

Doe het wel handmatig per geval.

Toch bedankt voor feedback.

[ACM]

Je kan ook wel een client/server arch maken waarbij de root-node de hele matrix kent en verder niets doet.
En de clients alles uitrekenen.

Maar het hangt van je algoritme af etc etc of dat het handigst is...

[MSalters]

Op woensdag 03 juli 2002 22:34 schreef ACM het volgende:
Je kan ook wel een client/server arch maken waarbij de root-node de hele matrix kent en verder niets doet.
En de clients alles uitrekenen.

Meestal niet; IIRC hebben alle nodes evenveel bandbreedte. Het gevolg zou zijn dat je "server" node volledig overbelast raakt.

Een van de essentiele dingen in parallel rekenen is het vinden van een goede mapping van datastructuur op nodes. De data access patronen van een algoritme bepalen welke mapping het beste is; zonder dat algoritme kunnen we geen datastructuur voorstellen.