Parallele Computerplattformen und Parallelrechnen

Eine Methode, um sehr rechenaufwendige Probleme auf Computern praktikabler lösen zu können, ist die Parallelisierung.

Hierbei wird versucht, das gesamte Problem in viele kleine Teilprobleme aufzuspalten und diese einzeln, parallel zueinander zu lösen. Die zu bewältigende Arbeit wird hierbei von einem auf viele Computer bzw. Prozessoren, im allgemeinen Knoten genannt, verteilt. Diese Methode ähnelt dem Devide-and-Conquer-Prinzip , das unter anderem in Sortierverfahren Anwendung findet (Cormen et al., 1990; Ottmann and Widmayer, 1993).

Zur Parallelisierung stehen verschiedene Parallelrechnerkonzepte und Parallelrechnerplattformen zur Verfügung. In erster Linie handelt es sich dabei um drei verschiedene Plattformen. (Burkhardt, 1993)

Zum einen sind dies die shared-memory-Systeme, die aus einer unterschiedlichen Anzahl einzelner Prozessoren bestehen, die über den Zugriff auf einen gemeinsamen Speicher miteinander verbunden sind (z.B. shared-memory-Systeme von Silicon Graphics). Hierbei können die einzelnen Prozessoren auch noch zusätzlich eigenen Speicher besitzen.

Zum anderen gibt es Parallelrechner, die aus mehr oder weniger eigenständigen Recheneinheiten mit eigenem Prozessor und Speicher bestehen. Die Recheneinheiten sind durch ein schnelles Verbindungsnetzwerk mit fester oder variabler Topologie miteinander verbunden (z.B. der Parallelrechner SP2 von IBM, der in dieser Arbeit verwendet wurde).

Beim dritten Typ handelt es sich um verteilte Rechnersysteme mit LAN-Kopplung. Dies sind im allgemeinen Workstations, die über Netzwerksysteme wie Ethernet, FDDI oder Tokenring miteinander verbunden sind. Solche verteilten Rechnersysteme können überall dort eingerichtet werden, wo Workstations in homogener oder heterogener Form miteinander vernetzt sind. Da dies in vielen Institutionen der Fall ist und beispielsweise Arbeitsplatzrechner nachts zumeist nicht benutzt werden, bietet sich die Möglichkeit, solche Rechenkapazitäten zu entsprechenden Zeiten zu Parallelplattformen zusammenzuschalten.

Da in den letzten Jahren der Zugriff auch auf echte parallele Computersysteme immer einfacher geworden ist, bietet es sich an, größere Probleme auf solche parallelen Rechnersysteme zu überführen, um die Einschränkungen durch die immensen Rechenzeiten zu mildern.

Die Methode der Parallelisierung findet auch in der Biologie, vor allem in der Molekularbiologie, immer stärkere Anwendung. So wurden z.B. das Programm BLAST zur Homologiesuche in genetischen Datenbanken (Jülich, 1995) oder Programme zur Sekundärstrukturvorhersage von RNA (Nakaya et al., 1995) auf parallelen Rechnerplattformen implementiert.

Auch das Programm fastDNAml von Olsen et al. (1994a), das auf dem Programm dnaml Version 3.3 von Felsenstein (1981) basiert, wurde schon einmal parallelisiert (, )[unveröffentlicht]matsuda94. Die damals der Parallelisierung zugrunde liegende Software wird aber seit einiger Zeit nicht mehr weiterentwickelt und daher nicht mehr an neue Rechnersysteme angepaßt.

Wichtig bei solchen Parallelimplementierungen ist allerdings, die Portabilität für eine möglichst große Anzahl von Plattformen zu ermöglichen, um späteren Weiterentwicklungen der Computer ohne allzu großen Aufwand auf Softwareseite Rechnung tragen zu können und vielen Benutzern die Anwendung zu ermöglichen.

Daher soll in dieser Diplomarbeit die sequentielle Version von fastDNAml erneut parallelisiert werden, unter besonderer Berücksichtung einer einfachen Portierbarkeit für unterschiedliche parallele Rechnersysteme.