Schilhard, P. (2007). Distribution of IMUNES system : graph partitioning [Master Thesis, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-18779
Graph partitioning; IMUNES; METIS; Real time job partitioning
en
Abstract:
In meiner Masterarbeit habe ich eine Graph-Partitionierungs Heuristik in IMUNES System implementiert. IMUNES ist ein Programm für Netzwerk Emulation / Simulation. Da die Netzwerk Emulation und Simulation sehr Rechenintensive sind, ist eine Methode für die Aufteilung der Belastung zwischen verteilten Systemen erforderlich. Die Emulation in IMUNES ist als ein Graph dargestellt, so dass das Problem der Aufteilung der Belastung ist als das Problem der Aufteilung von Knoten und Kanten des Graphen ("Graph-Partitionierung") behandelt.<br /> Nach METIS Graph-Partitionierung Algorithmuns, habe ich die Graph-Partitionierung mit drei Phasen implementiert. In der ersten Phase, Vergröberung (Coarsening), eine Hierarchie von Annäherungen an das ursprüngliche Problem wird erzeugt. In der zweiten Phase, wird eine Eingangslösung für das Problem gefunden, die dann iterativ in der dritte Phase verfeinert wird.<br /> In den Hauptteil dieser Masterarbeit beschreibe ich die Implementation der drei Phasen des Multilevel-Partitioning Algorithmus in IMUNES. Das Ziel meiner Masterarbeit war die Implementation des Echtzeit - Job - Partitionierung in IMUNES System. Nach der Implementation habe ich einige Effizienz- und Qalitätsbewertungen durchgeführt. Bewertungsergebnisse am Ende der Arbeit zeigen, dass die Methoden das gleiche Qualitätsniveau von Partitionen erreichen, wie die Partitionen abgeleitet von der METIS Methode, benötigen aber mehr Zeit, wegen den Kompromiss zwischen Geschwindigkeit und Plattformunabhängigkeit durch die Tcl/Tk Skriptsprache anstatt eine kompilierte Programmiersprache.<br />
de
In my master's thesis, I have implemented a graph partitioning heuristic in IMUNES system. IMUNES is a program for network emulation/simulation. Since network emulation and simulation are computationally very intensive, a method for dividing the computational load between distributed processors, in a way that minimizes interprocessor communication, is required. The emulation in IMUNES is represented as graph nodes interconnected with links, so the problem of dividing the computational load between processors is reduced to dividing the nodes and edges of the graph, called graph partitioning.