Parallele
Algorithmen
zur Lösung
kombinatorischer
Optimierungsprobleme")?>

Die stetige Verbesserung der Rechenleistung von Prozessoren und Hochgeschwindigkeitscomputern erschliesst neue und immer anspruchsvollere Arbeitsgebiete für Programmierer und Systementwickler. Computer können heute für nahezu alle komplexen Aufgabenstellungen eingesetzt werden. Die natürliche Grenze des rasanten technischen Entwicklungsprozesses liegt in der Lichtgeschwindigkeit als maximales Übertragungstempo von Daten. Eine Steigerung der Verarbeitungsgeschwindigkeit scheint dann nur noch möglich durch Aufteilung eines Prozesses in separate Routinen, die unabhängig voneinander zur gleichen Zeit abgearbeitet werden können. Voraussetzung hierfür ist natürlich, dass die Art der Aufgabenstellung dies grundsätzlich zulässt und dass eine effiziente Steuerung des zerlegten Prozesses vorbereitet wurde.

Die Entwicklung von parallel arbeitenden Computerarchitekturen ist inzwischen weit verbreitet. Schon die erste Version des Pentium-Chips erzielte ihre Leistungsverbesserung durch die Parallelschaltung mehrerer Prozessoren ihrer Vorgängerversion 486DX. Pentium Pro Prozessoren sind zusätzlich für einen Einsatz im Verbund eingerichtet. Die Nutzung dieser neuen Möglichkeiten durch intelligente Software-Lösungen steht jedoch hinter der gerätetechnischen Entwicklung zurück. Trotz der Unterstützung durch das gleichzeitige Bemühen um den Aufbau von Multi-Tasking-Systemen werden die Rechenressourcen von Parallelrechnern programmtechnisch kaum genutzt. Die Programmier- und Compilertechnik für sequentielle Vektorrechner ist heutzutage sehr weit entwickelt. Die theoretisch erreichbare Rechenleistung der Systeme kann in vielen Fällen voll ausgeschöpft werden. Hierzu tragen zum Beispiel besonders lange Vektoroperationen bei, die die Recheneinheiten (Pipelines) der Prozessoren immer vollständig auslasten. Trotzdem sind die Kapazitäten der Vektorrechner für viele physikalische Fragestellungen nicht ausreichend.\ Ganz anders sieht dies bei den meist auf RISC-Prozessoren basierenden parallelen und massiv-parallelen Computern aus, die bereits in vielen Rechenzentren zur Verfügung stehen. Zu dem Problem der effektiven Programmierung einzelner RISC-Rechner in bezug auf die Nutzung des Caches und anderer Optimierungsmöglichkeiten tritt hier die Frage nach der richtigen Vorgehensweise bei der Verteilung der Aufgaben auf die einzelnen Prozessoren. In Abhängigkeit von dem zu bearbeitenden Problem spielt dabei die gleichmäßige Auslastung der Prozessoren ebenso eine Rolle wie das richtige Verhältnis zwischen Kommunikations- und Rechenzeit.

Die Entwicklung von geeigneten Algorithmen für die unterschiedlichsten Aufgaben aus dem Bereich der Numerik, der Kombinatorik und Informatik stand im Laufe der 80er und in den frühen 90er Jahren im Mittelpunkt des Interesses vieler wissenschaftlicher Einrichtungen. Im Bereich der Numerik wurden unter anderem parallelisierte Varianten der meisten Matrix- und Vektoroperationen, der verschiedensten Gleichungslöser (z.B.LU-, Cholesky- ,CG- oder QMR-Verfahren), der Integrationsmethoden zur Lösung von Differentialgleichungen (z.B.SOR-, Gauss-Seidel- und Multigridverfahren) und, um ein weiteres, in dieser Arbeit aufgegriffenes Problem zu nennen, die unterschiedlichsten Ansätze zur verteilten Berechnung der Fouriertransformation erforscht. Die Kombinatorik beschäftigte sich mit Schedulingmechanismen und Routing-Problemen. Die Informatik steuerte die unterschiedlichsten Varianten von Betriebssystemen, Kommunikationsverfahren, Programmierumgebungen und Programmiersprachen bei.

Erst in den letzten zwei oder drei Jahren hat eine Phase begonnen, in der die Erfahrungen und Ergebnisse aus der Arbeit an vielen Teilproblemen zusammenfließen und es erlauben, auch komplexe Programme auf die Nutzung von Parallelrechnern auszurichten. Es werden Standards entwickelt, die es ermöglichen sollen, parallele Programme in einer übersichtlichen, klar strukturierten und portablen Art zu gestalten. Es wurde ein Prozeß angestoßen, an dessen Ende jeder Programmierer in der Lage sein wird, das hohe Leistungsvermögen paralleler Architekturen voll auszuschöpfen. In dieser Phase ist es notwendig, Erfahrungen bei der Portierung von großen Programmpaketen auf Parallelrechner zu sammeln und gestaltend an dem Prozeß der Standardisierung und Verbreitung von Parallelrechnern sowie dem dazugehörigen Umfeld wie Kommunikationsbibliotheken, Compilern, Debuggern und Betriebssystemen mitzuwirken.

Das Verbundprojekt PARALOR untersuchte mit Unterstützung des Bundesministeriums für Forschung und Technologie (BMBF) wie parallele Algorithmen der kombinatorischen Optimierung zur Lösung grosser Optimierungsprobleme aus der betrieblichen Praxis eingesetzt werden können. Die Untersuchung wurde durchgeführt anhand von Anwendungsbeispielen, die es ermöglichten, Teilprobleme zu identifizieren, deren algorithmische Behandlung für sich bereits sehr aufwendig ist. Der Einsatz herkömmlicher sequentieller Verfahren ist aufgrund der enormen Rechenzeiterfordernisse nur sehr eingeschränkt möglich. Hier bot es sich an, die technischen Möglichkeiten von Parallelrechnern zu nutzen, um die gegebenen Problemgrössen in vertretbarer Zeit bearbeiten zu können. Ziel des Paralor-Projektes ist es daher gewesen, Algorithmen zu entwicklen und zu verbessern, die das Potential solcher parallelen Rechnerstrukturen nutzbar machen.

Im ZPR wurde dies beispielsweise untersucht im Bereich der Flugplanoptimierung in Zusammenarbeit mit der Deutschen Lufthansa AG. Mehrere Untersuchungsansätze fanden sich im Bereich der Tourenplanung für einen Frischwarenlieferanten.

Kontakt:")?> scicomp@zpr.uni-koeln.de