Refine
Document Type
- Article (1)
- Master's Thesis (1)
Has Fulltext
- yes (2)
Keywords
- distributed computing (2) (remove)
Faculty / Organisational entity
Load balancing is one of the central problems that have to be solved in parallel computation. Here, the problem of distributed, dynamic load balancing for massive parallelism is addressed. A new local method, which realizes a physical analogy to equilibrating liquids in multi-dimensional tori or hypercubes, is presented. It is especially suited for communication mechanisms with low set-up to transfer ratio occurring in tightly-coupled or SIMD systems. By successive shifting single load elements to the direct neighbors, the load is automatically transferred to lightly loaded processors. Compared to former methods, the proposed Liquid model has two main advantages. First, the task of load sharing is combined with the task of load balancing, where the former has priority. This property is valuable in many applications and important for highly dynamic load distribution. Second, the Liquid model has high efficiency. Asymptotically, it needs O(D . K . Ldiff ) load transfers to reach the balanced state in a D-dimensional torus with K processors per dimension and a maximum initial load difference of Ldiff . The Liquid model clearly outperforms an earlier load balancing approach, the nearest-neighbor-averaging. Besides a survey of related research, analytical results within a formal framework are derived. These results are validated by worst-case simulations in one-and two-dimensional tori with up to two thousand processors.
Das Ziel dieser Arbeit ist es, ein Framework und einen funktionsfähigen Prototypen für eine Middleware zu entwickeln, die es ermöglicht, Berechnungen verteilt in einem Peer-to-Peer-Netz auszuführen. Dabei sollen verschiedene Arten der Berechnung unterstützt werden. Eine Art der Berechnung sind Aufträge, die massiv parallel berechnet werden können, d.h. solche, die in unabhängige Teilaufträge zerlegt werden können und ohne gegenseitige Kommunikation auskommen. Diese Aufträge können entweder so parametrisiert sein, dass jeder Teilauftrag einen anderen Satz Parameter erhält (z.B. Fraktalberechnung), oder zufallsbasiert, so dass jeder Teilauftrag mit den gleichen Ausgangswerten berechnet wird und unterschiedliche Ergebnisse resultieren. Eine andere Art der Berechnung setzt voraus, dass Knoten, die am gleichen Auftrag arbeiten, auch miteinander kooperieren und durch Nachrichten beispielsweise Teillösungen austauschen (z.B. verteilte evolutionäre Algorithmen). Alle Knoten in diesem Netz sollen gleichberechtigt sein, d.h. jedem Knoten soll es möglich sein, eigene Anwendungen und Aufgaben im Netz zu verteilen. Den verteilten Anwendungen soll zudem die Möglichkeit gegeben werden, mit anderen Knoten, die an der gleichen Aufgabe arbeiten, kommunizieren zu können. Alle benötigten Informationen zur Berechnung eines Auftrags (d.h. Parameter, ausführbarer Code der Anwendung, Anzahl der zu berechnenden Fälle) sollen den rechnenden Knoten durch Middlewarefunktionen zur Verfügung gestellt werden, ebenso soll der Rücktransport der Ergebnisse zum Initiator durch die Middleware erfolgen. Der Nutzer soll also an seinem Arbeitsplatz seine verteilte Anwendung starten können und die Ergebnisse schließlich wieder auf seinem Rechner vorfinden. Die Implementierung soll möglichst modular angelegt sein und nicht auf ein konkretes P2P-Protokoll beschränkt sein, sondern einen leichten Austausch bzw. eine nutzergesteuerte Auswahl von verschiedenen Protokollen ermöglichen. Im Rahmen dieses Prototypen soll ein epidemisches P2P-Protokoll realisiert werden.