Funktion/Algorithmus, um Daten gleichmäßig zwischen Prozessen zu verteilen

Question

Ich habe ein globales Array, A, dessen Elemente ungleichmäßig über mehrere Prozesse in einem MPI-Programm verteilt sind. Im Interesse des Lastenausgleichs möchte ich die Elemente von A neu verteilen, so dass jeder Prozess ungefähr die gleiche Anzahl von Elementen enthält. Es gibt eine große Freiheit in der Umordnung, weil die Reihenfolge der Elemente von A unwichtig ist - es geht mir nicht darum, welche Elemente von A in welchem ​​Prozess enden. Ich würde natürlich gerne den Transfer so schnell wie möglich erreichen.

Gibt es einen kanonischen Namen für dieses Problem, eine Standardlösung oder eine MPI-Funktion, die es für mich lösen kann?

Answer 1

Normalerweise wird dies als "Load Balancing" bezeichnet, wie Sie bereits gesagt haben.

Es gibt keine direkte MPI-Funktion, Sie müssen einige arithmetische Berechnungen durchführen und selbst senden/empfangen. Es gibt jedoch einige Bibliotheken, die gut partitionierte Domains und ähnliches ergeben. Metis ist sehr beliebt für Mesh oder Graph-basierte Partitoned.

In Ihrem Fall ergibt sich die Schwierigkeit aus der Tatsache, dass alle Ränge müssen nur Teile ihrer Daten zu (von) unterschiedlichen Anzahl von Rängen senden (und erhalten). Wenn Sie die Möglichkeit haben, das komplette globale A zuerst auf einen Rang zu bringen, können Sie es einfach mit MPI_Scatter streuen. Andernfalls müssen Sie einige Berechnung tun:

• Ersten send (MPI_Allgather) das Element Anzahl aller Reihen zu jedem Rang
• zählt, wie viele Elemente jeder Rang sollten senden (empfangen) und (von) wem.
• Senden/Empfangen oder einseitige Kommunikation verwenden.