Fachbereich Informatik  Abteilung
Betriebssysteme und Verteilte Systeme 		Universität Oldenburg   

Publications: Details

Document Description

Author: Holger Buck
Title: Parallelisierung von Algorithmen zur Zusammenhangsstruktur von Graphen
Kind of Publication: Diplomarbeit
Supervisor: Prof. Stiege
Date: October 1997
Institution: Universität Hildesheim, Institut für Betriebssysteme und Rechnerverbund
Pages, Language 155, German
Keywords: parallel algorithms, connectivity of graphs
CR Classification: E.1[Data]:Data Structures - graphs and networks;
F.1.2[Computation by Abstract Devices]: Modes of Computation - parallelism and concurrency;
G.2.2 [Discrete Mathematics]: Graph Theory - Graph algorithms;
General Terms (ACM): Algorithms
up

Abstract

The aim of this work is to examine the suitability of graph algorithms for parallelism and to look for possible problems. For this purpose, a sequential graph algorithm was parallelised and the corrsponding performance change was rated. Further, the course of events of the parallel program were presented by an existing system for visualization. The algorithm to parallelise is implemented in a program of the Institute for Operating Systems and Computer networks of the University of Hildesheim. The program searches the components and periodicity classes of digraphs. The change in Performance obtained by parallelism measured with the help of extensive and adequate systematic test material. As parallel computer, the KSR1 of the Gesellschaft für wissenschaftliche Datenverarbeitung Göttingen was used.

Kurzfassung

Das Ziel dieser Arbeit ist es, zu untersuchen, wie sich Graphalgorithmen für die Parallelisierung eignen und wo mögliche Probleme liegen könnten. Zu diesem Zweck wurde ein sequentieller Graphalgorithmus parallelisiert und die hierdurch bedingte Leistungsänderung bewertet. Ferner wurden die Abläufe der Parallelisierung unter Benutzung eines existierenden Visualisierungssystems dargestellt. Der zu parallelisierende Algorithmus ist im Programm zur Gewinnung der starken Zusammenhangskomponenten und Periodizitätsklassen in Digraphen, das am Institut für Betriebssysteme und Rechnerverbund der Universität Hildesheim vorhanden ist, implementiert. Die Leistungsänderung durch die Parallelisierung wurde anhand von umfangreichem und hinreichend variablem Testmaterial systematisch gemessen. Als Parallelrechner diente die KSR1 der Gesellschaft für wissenschaftliche Datenverarbeitung Göttingen.
up

Download full text

up

Remarks

up


Last change: Apr 3 1999 Stiege