News: Optimierte Prozessor-Netzwerke für Parallelrechner
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.
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.