Deutsch

Ziel von Loadbalancing-Verfahren auf Parallelrechnern ist es, eine gegebene Lastverteilung iterativ auszugleichen, wobei auf jedem Prozessor zunächst ein anderer Lastwert vorliegt. Betrachtet werden ausschließlich Nächste-Nachbar-Verfahren: In jedem Schritt kommuniziert ein Prozessor nur mit seinen direkten Nachbarn. Loadbalancing-Verfahren lassen sich im Wesentlichen in zwei Klassen aufteilen: Diffusions- und Dimension-Exchange-Verfahren. Während erstere für das All-Port-Modell konzipiert sind, bei dem ein Prozessor an alle Nachbarn gleichzeitig Lasten versenden kann, sind letztere an das One-Port-Modell angepasst, bei dem zu jedem Zeitpunkt mit nur einem Nachbarn kommuniziert wird. Beide Arten können als Verfahren zur Lösung bestimmter singulärer Gleichungssysteme angesehen werden. In den letzten Jahren sind endliche Diffusionsverfahren entwickelt worden, für die gezeigt werden konnte, dass sie l₂-minimale Flüsse erzeugen. In der vorliegenden Arbeit werden neue endliche Dimension-Exchange-Verfahren entwickelt, die auf einer Kantenfärbung des zu Grunde liegenden Graphen beruhen. Diese sind oftmals schneller und numerisch stabiler als entsprechende Diffusionsverfahren. Die von den neuen Verfahren berechneten Flüsse sind nicht minimal, aber es wird gezeigt, dass sie beschränkt sind. Für einige spezielle Graphen können diese Schranken mit Hilfe von Graphmatrizen exakt bestimmt werden. Außerdem werden spezielle Verfahren für Produktgraphen vorgestellt sowie ein Scheduling-Verfahren, das auf der Einfärbung des Graphen basiert.

English

Load balancing on parallel computers aims at equilibrating some initial load which is different from one processor to another. Only nearest neighbour algorithms are considered: in each step a processor communicates only with its direct neighbours. Load balancing algorithms can be divided basically into two classes: diffusion and dimension exchange. Whereas the first is appropriate for the so-called all-port-model where a processor can send tokens to all its neighbours at a time, the latter relies on the one-port-model. Both kinds of algorithms can be viewed as methods for solving certain singular linear systems. In the last few years finite diffusion algorithms have been developed and it has been proven that they compute l₂-minimal flows. In the present thesis new finite dimension exchange methods are presented that are based on edge-colourings of the underlying graph. These are often faster and numerically more stable than their diffusion counterparts. The flows computed by the new methods are not minimal but it can be shown that they are bounded. For some special graphs these bounds can be explicitly determined by an analysis of the matrices representing the graph. Additionally special algorithms for product graphs are presented as well as a scheduling technique based on the colouring of the graph.