Optimization of diffusive load-balancing for short-range molecular dynamics

Abstract

In recent years, multi-core processors have become more and more important for manufacturers, which means that developers now have to think more about how to distribute a single application sensibly over several processes. This is where load balancing comes in, allowing us to move load from an overloaded process to an underloaded process. One way of load balancing is diffusive load balancing, which is a method of moving load in the local neighborhood and therefore no global communication is needed. The advantage of this is that processes that have completed the local communication and thus the load-balancing process can continue with the next calculations. This form of load balancing is found in librepa, a library that deals with the balancing of linked-cell grids and can be used in the simulation software ESPResSo. In the course of this thesis the library has been extended with the First and Second Order Diffusion. Furthermore, a feature was added that allows to keep the initial structure of the grid constant, which means that the neighborhood of each process does not change. This feature is necessary for the Second Order Diffusion. A comparison between the methods shows that both First and Second Order Diffusion distribute the load better in the system than librepa's default and prior to this work only diffusive variant. Furthermore, we show that there is no significant overhead in using the Preserving Structure Diffusion. With the use of flow iteration the imbalance values of First and Second Order Diffusion can be improved even further.

In den letzten Jahren haben Mehrkernprozessoren für Hersteller immer mehr an Bedeutung gewonnen, was bedeutet, dass Entwickler nun mehr darüber nachdenken müssen, wie eine einzelne Anwendung sinnvoll auf mehrere Prozesse verteilt werden kann. An dieser Stelle kommt die Lastbalancierung ins Spiel, die es uns ermöglicht, die Last von einem überlasteten Prozess auf einen unterlasteten Prozess zu verlagern. Eine Möglichkeit der Lastbalancierung ist die diffusive Lastbalancierung, eine Methode, bei der die Last in der lokalen Nachbarschaft bewegt wird und daher keine globale Kommunikation erforderlich ist. Dies hat den Vorteil, dass Prozesse, die die lokale Kommunikation und damit den Lastbalancierungsprozess abgeschlossen haben, mit der nächsten Berechnung fortfahren können. Diese Form des Lastausgleichs findet sich in librepa, eine Bibliothek, die sich mit dem Ausgleich von Linked-Cell-Grids beschäftigt und in der Simulationssoftware ESPResSo eingesetzt werden kann. Im Zuge dieser Arbeit wurde die Bibliothek um die First und Second Order Diffusion erweitert. Darüber hinaus wurde eine Funktion hinzugefügt, die es erlaubt, die anfängliche Struktur des Gitters konstant zu halten, was bedeutet, dass sich die Nachbarschaft der einzelnen Prozesse nicht ändert. Dieses Feature ist für die Second Order Diffusion notwendig. Ein Vergleich zwischen den Methoden zeigt, dass sowohl die First Order Diffusion als auch die Second Order Diffusion die Last im System besser verteilt als die Standardvariante und vor dieser Arbeit die einzige diffusive Variante von librepa. Außerdem zeigen wir, dass es keinen signifikanten Overhead bei der Verwendung der Strukturerhaltenden Diffusion gibt. Mit dem Einsatz von flow Iterationen können die Imbalancewerte der First und Second Order Diffusion noch weiter verbessert werden.