Ich versuche herauszufinden, was ist die beste Praxis beim Entwerfen von parallelen Algorithmus für Modell der Datenverteilung. Was könnte Vor- und Nachteile gegen Blockverteilung vs zyklische Verteilung von Daten im Speicher sein. Jede Hilfe wäre willkommen.Parallele Algorithmus Design
Quinns "Parallele Programmierung in C mit MPI und OpenMP" bietet viele Beispiele für verschiedene Möglichkeiten, Daten in paralleler Programmierung zu verteilen. Es gibt sogar einen Entscheidungsbaum, der Ihnen dabei hilft herauszufinden, welcher Ansatz am bequemsten ist, abhängig von Ihren Bedürfnissen.
Die Blockverteilung im Shared Memory eignet sich am besten für Algorithmen, die ihre Arbeit in Blöcke aufteilen, die nur wenig (oder keine) Synchronisation benötigen, während der Algorithmus läuft.
Der parallele Algorithmusentwurf sollte sich darauf konzentrieren, Synchronisationsengpässe zwischen Prozessen zu minimieren. Ein Beispiel wäre ein Gauß-Seidel-Relaxationsverfahren auf einem 2-D-Gitter, bei dem das Gitter in Streifen aufgeteilt wird (1 pro Prozessor) und keine Synchronisation durchgeführt wird. Jeder Prozessor berechnet einen unabhängigen Konvergenzwert und endet, wenn diese Zahl erreicht ist.
Sie sollten auch die Datenlokalität der Referenz berücksichtigen, die einen deutlichen Effekt auf parallele und sequenzielle Algorithmen haben kann.
"Blockverteilung im Shared Memory ist am besten für Algorithmen geeignet, die ihre Arbeit in Blöcke aufteilen, die nur wenig (oder gar keine) Synchronisation benötigen, während der Algorithmus läuft." - Diese Aussage ist nicht unbedingt notwendig, da ich eine zyklische Zerlegung finden kann, die mir eine Reihe von unabhängigen Aufgaben gibt, während ich im Block dazu nicht in der Lage bin. –
@ Artem Barger: Sie haben Recht. Ich hätte die zugrundeliegende Topologie, d. H. Gitter, Torus, usw. erwähnen sollen ... –
Gauss-Seidel ist ein fast pathologisch schlechter Algorithmus, um parallel zu "tun". Was Sie vorschlagen, ist Linie-Jacobi mit Gauß-Seidel innerhalb jedes Streifens, ein Algorithmus, der extrem langsam konvergiert (im Vergleich zu richtigem Gauss-Seidel, das bereits schrecklich ist). – Jed