Direkt zum Inhalt

News: Optimierte Prozessor-Netzwerke für Parallelrechner

Ein Verfahren, das die gegenwärtigen Bauweisen von Hoch- und Höchstleistungscomputern durch verbesserte Vernetzung der einzelnen Prozessoren revolutionieren könnte, hat der Informatiker Dr. Michael Sampels in seiner Doktorarbeit am Fachbereich Informatik der Universität Oldenburg entwickelt. In seiner Arbeit mit dem, wie er einräumt, auf den ersten Blick recht abschreckenden Titel 'Algebraische Konstruktion von Verbindungsnetzwerken' beschreibt der erst 29jährige Sampels Rechnerarchitekturen, die den bisher verwendeten weit überlegen sind.
Die praktische Bedeutung von Sampels' Ergebnissen beruht darauf, daß die Leistungsfähigkeit eines modernen Hochleistungsrechners stark von der Art der Vernetzung seiner Prozessoren, dem Verbindungsnetzwerk, abhängt. Parallelrechner, wie sie zum Beispiel für die Wettervorhersage benutzt werden, arbeiten nicht wie PCs mit einem, sondern parallel mit bis zu 30 000 Prozessoren, die sich die Rechenarbeit untereinander teilen und deshalb miteinander kommunizieren müssen. Damit jeder Prozessor mit jedem anderen kommunizieren kann, sind sie über ein Netzwerk zusammengeschlossen.

Sampels ist es gelungen, einen neuen Ansatz für die Konstruktion solcher Prozessornetzwerke zu entwickeln: Er kombiniert eine mathematische Darstellungsmethode der Graphentheorie für die verwendeten Netzwerke, sogenannte Cayley-Graphen, mit einer auf der Evolutionstheorie basierenden Optimierungsmethode, den "genetischen Algorithmen". Nach Darwin paßt sich durch das Prinzip survival of the fittest eine Spezies im Laufe der Generationen immer besser an ihre Umweltbedingungen an. Sampels benutzt dieses Prinzip, um seine Cayley-Graphen und damit seine Netzwerke zu optimieren: Er beginnt mit einer zufälligen Start"population" von Graphen, kombiniert diese Graphen miteinander, so daß eine neue Graphen-"Generation" entsteht, und wählt davon die besten aus. Diese benutzt er als neue Startpopulation und wiederholt den Vorgang so oft, bis sich keine weiteren Verbesserungen mehr ergeben. Außerdem benutzt er "Mutationen", zufällige Veränderungen, um zu neuen Graphen zu kommen. Qualitätskriterien für die Auswahl der besten Graphen sind dabei verbesserte Kommunikationseigenschaften der entsprechenden Netzwerke.

Mit diesem Verfahren fand Sampels zahlreiche Graphen, die hinsichtlich der untersuchten theoretischen Größen Verbesserungen bisheriger Resultate aus der Graphentheorie darstellten. In Simulationsexperimenten stellte sich überdies heraus, daß sich wesentliche Verbesserungen gegenüber den in der Konstruktion von Parallelcomputern bisher üblichen "Torus"- und "Hypercube"-Architekturen nicht nur in der Theorie, sondern auch in der Praxis ergeben.

Eine Arbeitsgruppe in Los Alamos (USA) hat Sampels' Ideen bereits aufgegriffen und erprobt sie gegenwärtig in einem Hardware-Experiment. Ergebnisse stehen jedoch noch aus. Auch Sampels beschäftigt sich weiter mit dem Thema, seit seiner Promotion allerdings nicht mehr an der Universität Oldenburg, sondern an der Universität-Gesamthochschule Essen, wo er als Assistent am dortigen Fachbereich Informatik tätig ist.

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.