Spectral methods for efficient load balancing strategies

Abstract

Die gleichmäßige Verteilung der auftretenden Rechenlast bei gleichzeitiger Minimierung der Kommunikation ist von entscheidender Bedeutung für die effiziente Auslastung der Ressourcen eines parallelen Systems. Eine große Zahl von Lastverteilungsverfahren wurde entwickelt und durch theoretische Analyse, durch Experimente und durch Integration in Anwendungen untersucht. Unter diesen Verfahren spielen die k-Partitionierungsverfahren und die Diffusionsverfahren eine prominente Rolle. Diese Arbeit stellt eine Zusammenfassung meiner Dissertation dar, und beschäftigt sich einerseits mit der Konstruktion und Analyse neuer spektraler Schranken für die k-Sektionsweite von Graphen und andererseits mit der Entwicklung verbesserter diffusionsbasierter Lastbalancierungsverfahren für verschiedene Graphklassen und Netzwerktopologien. Zudem wird gezeigt, dass die bekannten Diffusionsverfahren auf heterogene Netze übertragen werden können, wobei die Konvergenzgeschwindigkeit von der Konditionszahl einer zugehörigen gewichteteten Laplacematrix abhängt.