Der Monoprozessor ist out. Mehr denn je wird heute an Computer-Architekturen gearbeitet, bei denen mehrere Prozessoren in einem parallelen Modus rechnen.

Nicht auf herkömmliche SIMD-Mehrrechnersysteme (Single Instruction Multiple Data), wie etwa die "Cray" oder die Maschinen von Floating Point Systems (FPS), die ein- und dieselbe Instruktion auf mehrere Daten gleichzeitig anwenden zielte der Vortrag von Dr. Burkhard Schulz auf einer Perkin-Elmer-Tagung ab. Schulz meinte die MIMD-Rechner (Multiple Instructions Mutiple Data), die parallel mehrere (verschiedene) Instruktionen auf mehrere Datenströme anwenden.

Prozessor begrenzt Rechentempo

In herkömmlichen Computern ist die Zentraleinheit das "knappste" Betriebsmittel, denn Speicher und Peripherie lassen sich bekanntermaßen ziemlich frei ausbauen. Der Prozessor begrenzt also letztlich das Tempo, in dem gerechnet werden kann. Wollen mehrere Benutzer gleichzeitig mit dem Computer arbeiten, müssen sich alle "zeitscheibenweise" die Leistung dieser einen CPU teilen.

Will man höhere Rechenleistungen erhalten, so ist es laut Schulz ratsam, auf Mehrrechnersysteme des MIMD-Typs überzugehen, da "bei konventionellen Strukturen sowohl die physikalische als auch die wirtschaftliche Grenze erreicht ist". Ein Multiprozessor-System, das ja auch aus standardisierten und in größeren Serien gefertigten Baugruppen aufgebaut werde, könne hingegen kostengünstiger hergestellt werden als ein vergleichbar leistungsstarker Uniprozessor: Auch eigne es sich besser für "Probleme, die an und für sich parallel sind wie etwa Simulationsabläufe". Damit ließen sich auch Echtzeitaufgaben gut bewältigen. Außerdem könne solch ein System Probleme behandeln, die "für serielle Rechner zu komplex sind", also etwa bei seismischen Berechnungen.

Wie sich solche Systeme einsetzen lassen und was man von ihnen heutzutage erwarten darf, schilderte Schulz am Beispiel eines Konzeptes, bei dem ein Zentralprozessor mit maximal neun Zusatzprozessoren zu einem schnellen 32-Bit-System mit maximal 16 MB gemeinsamen Hauptspeichers gekoppelt werden kann (PE 3200 MPS). Der zweimal 32 Bit breite Speicherbus leistet 64 MB pro Sekunde, jeder Prozessor hat einen eigenen Gleitkommaprozessor und die Ein-/Ausgabeleistung zur Peripherie liegt bei 40 MB pro Sekunde.

Diese Konfiguration wird von einem Echtzeit-Betriebssystem gesteuert, von dem nur eine einzige Kopie in der Zentraleinheit läuft. Alle Zusatzprozessoren sind für das Betriebssystem daher periphere Einheiten, die nur eine Aufgabe haben: Sie müssen einen geladenen Prozeß (Task) abarbeiten - und zwar parallel zu den anderen Prozessoren. Jede Zusatzeinheit besitzt eine eigene Warteschlange für die nächsten zu bearbeitenden Prozesse. Dabei erfordert die Behandlung dieser Warteschlangen laut Schulz keinen Betriebssystemaufwand.

Alle Betriebssystemdienste erledigt die Zentraleinheit, wobei sie dazu gegebenenfalls einen Prozeß, der eine Betriebssystemanforderung beinhaltet, kurz von einer Zusatzeinheit übernimmt und später wieder an sie zurückgibt. Ferner besorgt die Zentraleinheit die Ein- und Ausgaben und bearbeitet, soweit sie noch freie Kapazität besitzt, auch selber Prozesse. Die Rechnerkopplung ist so gestaltet, daß auf Hardware-Ebene automatische Last-Verteilung erfolgt.

Speicherbus steigert Leistung des Multiprozessor-Systems

Was leistet nun ein derartiges System? Bezieht man sich auf den bekannten Whetstone-Benchmark-Test, so leistet die Zentraleinheit pro Sekunde drei und jede Zusatzeinheit zwei Whetstones. Was rein theoretisch bedeuten würde, ein voll ausgebautes System könnte 21 Whetstones pro Sekunde leisten. Es geht jedoch Leistung verloren, weil die Rechner ja kooperieren müssen.

Der Schlüssel zu einer dennoch hohen Netto-Leistung eines Viel-Prozessoren-Systems ist laut Schulz nun ein leistungsstarker zentraler Speicherbus, da dieser "in jeder MIMD-Architektur das am stärksten belastete Bauteil ist". Mit den erwähnten zwei asynchron arbeitenden Bussen für Lese- und Schreiboperationen ist es aber möglich, eine effektive Rechenleistung zu erzielen, die nur um 6,7 Prozent unter den theoretisch erreichbaren 100 Prozent (21 W/s) liegt - selbst unter der erschwerenden Bedingung, daß alle Prozessoren simultan am gleichen Code und mit denselben Daten arbeiten.

Es trifft also nicht unbedingt zu, daß Multiprozessorsysteme schon ab fünf oder sechs Prozessoren "kaum mehr weitere Nettoleistung" erbringen, wie man oft hören oder lesen kann. Das gilt, betonte Schulz, auch für den Fall, daß zusätzlich viel Ein-/Ausgabeverkehr anfällt: Selbst wenn man die maximale Zahl von zehn gleichzeitig transferierenden Plattenspeichern annimmt, und demzufolge mit 39 MB Ein-/Ausgabelast rechnet, sinkt die nutzbare Rechenleistung noch immer nicht unter 70 Prozent.

Soll die volle Leistung solch eines Multiprozessorsystems genutzt werden, bieten sich zwei Möglichkeiten an. Einmal kann man auf ihm verschiedene, voneinander unabhängige Programme gleichzeitig laufen lassen, was, so Schulz, ohne jegliches Problem zur hundertprozentigen Auslastung des Systems führt. Soll andererseits nur ein einziges Programm arbeiten, muß der Anwender in eigener Regie die von der Logik des Programms her gebotene Parallelität voll für das System nutzbar machen. Denn in diesem Fall ist es nicht mehr damit getan, qua Betriebssystem für eine gleichmäßige Lastverteilung zu sorgen.

Welcher Gewinn an Geschwindigkeit ist theoretisch erzielbar, werden mehrere Prozessoren eingesetzt Bezeichnet man den Quotienten er sich aus der Rechenzeit pro Einzelprozessor geteilt durch die Zeit bei Verwendung von N Prozessoren ergibt, mit "S", so beträgt dieses S im Falle von Matixrechnungen und Diskretisierungen S = K mal N. Dabei ist K eine maschinenabhängige Zahl zwischen 0,80 und 0,99. Bei Compiler-Prozessen ist S = K mal x (log2 N); bei Polygonauswertungen, linearen Rekursionen, Sortierproblemen und dergleichen schließlich wird S = K mal N/ (log2N).

Anwenderpriorität bestimmt Prozessorenanzahl

Der Nutzen des parallelen Arbeitens ist somit stark vom gegebenen Problem sowie oft auch von der Qualität der vorhandenen Algorithmen abhängig. Je besser diese ein Problem parallelrechnergerecht aufbereiten, desto effizienter arbeitet ein MIMD-Rechner.

Hochgradig iterative, kontinuierliche Feldprobleme wie Aufgaben der Wettervorhersage, der Seismik oder Strömungs- und FEM-Probleme, bedürfen einer guten Vorbereitung, während MIMD-Rechner für Probleme, die zum Beispiel in der Echtzeit-Bildverarbeitung auftreten, laut Schulz "das natürliche Hilfsmittel" sind.

Wie stark ein gegebenes Programm parallelisiert werden kann, wird mit Petri-Netzen erarbeitet (siehe Abbildung). Dabei soll die zu bearbeitende Datenstruktur beim Start des Programms im Zustand 0 sein, bei dessen Beendigung dann im Zustand Z. Die Pfeile geben die einzelnen Zustandsänderungen an, die Zahlen die für die Änderung jeweils benötigten Zeiteinheiten.

Aus der Darstellung ergibt sich unmittelbar, daß bis zu fünf parallel laufende Teilgraphen vorhanden sind und sich daher bis zu fünf Prozessoren sinnvoll einsetzen lassen. Dann kommt man übrigens mit nur 19 Zeiteinheiten aus, denn allein der "kritische Pfad" (O - A - D - F - H - Z) muß rein seriell durchlaufen werden. Mit nur einem Prozessor hingegen würde die Durchlaufzeit der Summe aller Pfade entsprechen, also mit 62 Zeiteinheiten mehr als dreimal so lang sein.

Allerdings, so bemerkte Schulz, sinkt beim Einsatz von immer mehr Prozessoren neben der Durchlaufzeit auch die Auslastung des einzelnen Prozessors, doch könnten die frei bleibenden Rechner-Ressourcen zwischenzeitlich wiederum von anderen Programmen genutzt werden.

In der Praxis muß oft entschieden werden, wie viele Prozessoren einzusetzen sich wirklich lohnt. Das hängt von den Prioritäten des Anwenders ab: Will er minimale Durchlaufzeiten erzielen, so wird er so viele Prozessoren einsetzen, wie der Programmgraph Parallelzweige aufweist. Will er die Auslastung maximieren, so muß er etwa so viele Prozessoren einsetzen, wie sich aus der Multiplikation der Zahl paralleler Wege mit 0,5 bis 0,7 ergibt.

Erste Zusatzeinheit bringt größten Nutzen

Gerade die "ersten" zusätzlichen Prozessoren neben der Zentraleinheit werfen am meisten zusätzlichen Nutzen ab. Allein durch die erste Zusatzeinheit wird die Durchlaufzeit im obigen Beispiel nahezu halbiert (im Vergleich zur Leistung des Einzelprozessors). Die vierte Zusatzeinheit hingegen bringt nur noch fünf Prozent Zeitersparnis.

Die Programmierung eines solchen Master-Slave-Multiprozessorsystems läuft folgendermaßen ab: Der Benutzer des Programms startet an seinem Terminal die zum Gesamtprogramm

gehörende Monitor-Task auf der Zentraleinheit. Diese Task hat unter anderem die Aufgabe, an sogenannten "Simultanpunkten" die auf den Zusatzprozessoren laufenden Sub-Tasks zu starten. Nun wird so lange parallel gearbeitet, bis ein Simultanabschnitt beendet ist. Danach muß eine "Zustandssynchronisation" erfolgen. Das bedeutet, daß an bestimmten Synchronisationspunkten ein Gleichlauf der Prozessoren erzwungen wird; sie müssen also aufeinander warten.

Synchronisationsvariablen nur durch eine Task manipulierbar

Hierbei unterscheiden Fachleute zwischen kurzen und langen Warte-Intervallen, wobei die ersteren kürzer als 100 Millisekunden sind. Sie werden in der Form abgewartet, daß die zuerst am Synchronisationspunkt eintreffende Task solange eine unendliche Schleife durchläuft, bis eine Synchronisationsvariable durch eine andere Task in ihrem Wert geändert wird. Lange Intervalle hingegen werden grundsätzlich über programmgesteuerte Interrupts ausgeführt.

Der Witz an dieser Unterscheidung ist, daß der Prozessor während kurzer Warte-Intervalle belegt bleibt, während er bei langen Intervallen von anderen Tasks benutzt werden kann; nämlich von jenen, die in der Warteschlange als nächste anstehen und ausführungsbereit sind.

Die erwähnten Synchronisationsvariablen liegen in einem Speicherbereich, zu dem alle Prozessoren Zugang haben. Damit gemeinsame Zugriffe mehrerer Tasks nun nicht etwa zu unsicheren Prozeßzuständen führen können, ist dafür gesorgt, daß in diesem kritischen Bereich des Speichers zur Zeit X jeweils immer nur eine einzige Task die Variablen manipulieren darf. Die entsprechenden Sperr- und Entsperrfunktionen werden dabei vom Anwenderprogramm vorgenommen.

Aus dem bisher Gesagten ergibt sich, daß eine Ausführungszeit eines parallel abzuarbeitenden Programms bei vereinfachter Betrachtung aus folgenden vier Komponenten zusammengesetzt ist:

- der Zeit zur Ausführung arithmetischer Operationen,

- der Kommunikationszeit zwischen den Prozessoren,

- der Synchronisationszeit und

- der Wartezeit.

Die Ausführungszeit der arithmetischen Operationen läßt sich laut Schulz vor allem durch Einsatz eines guten Fortran-Compilers minimieren. Muß es aber einmal noch schneller gehen, kann man noch knapp ein Drittel der Zeit sparen, indem man mit einem Mikro-Assembler arbeitet und damit den Mikroprogrammspeicher modifiziert.

Die Synchronisationszeit läßt sich verkürzen, indem das Programm in möglichst lang laufende, parallel ausführbare, große Blöcke gegliedert und, die nur noch selten synchronisiert werden müssen. Die Dauer eines Synchronisationsvorgangs kann durch die Entwicklung eines mikroprogrammierten Synchronisationsmechanismus verringert werden. Schließlich läßt sich die Wartezeit, also die Leerzeit der einzelnen Prozessoren, dadurch verkürzen, daß man das Programm speziell mit dem Ziel gestaltet, möglichst viel Parallelität zu erreichen, und zwar über die gesamte Programmlaufzeit hinweg.

Verwaltung von Task-Warteschlangen

Abschließend noch ein paar Worte zu der Art und Weise, wie ein Multiprozessorsystem seine Task-Warteschlangen verwaltet. Es gibt dabei zum einen sogenannte CPU-Tasks (Prozesse), die nur auf der Zentraleinheit ablaufen und eine gesonderte Warteschlange bilden. Zum anderen existieren "private" Warteschlangen für die einzelnen Zusatzprozessoren. In ihnen sammeln sich jene Prozesse, die auf keinem anderen Zusatzprozessor laufen sollen. Eine gemeinsame Warteschlange wiederum umfaßt Prozesse, die auf mehreren zuvor festgelegten beziehungsweise auf allen Zusatzprogrammen laufen dürfen. Ein letzter Warteschlangen-Typ schließlich bedient neben einigen Zusatzprozessoren auch die Zentraleinheit.

Es ist möglich, die einmal eingestellten Zuordnungen von Warteschlangen zu Prozessoren vom Bediener des Rechners oder auch per Programm jederzeit zu ändern. Dadurch gewinnt das Konzept des modular erweiterbaren Multiprozessor-Systems zumindest in den Anwendungsfällen an Attraktivität, in denen sich das Potential an Parallelität wirklich nutzen läßt und nicht vom Problem her eine streng oder überwiegend sequentielle Bearbeitung nötig ist. Denn da dominiert dann doch wieder der auf höchstes Tempo gezüchtete schnelle Monoprozessor.

Parallelverarbeitung

Zu den Themen die in EDV-Fachkreisen in letzter Zeit mehr und mehr Interesse gefunden haben, gehört auch die parallele Datenverarbeitung also die Abkehr vom herkömmlichen Uni-Prozessor. Sie tritt, in zahlreichen Konzepten und Produkten. in höchst vielseitiger Form zutage und wird auch von Wissenschaftlern mit zu den interessantesten Forschungsbereichen der modernen Informatik gezählt.

Die CW wird das Gebiet "Parallelverarbeitung" in einer losen Folge themengerichteter Beiträge von mehreren Seiten beleuchten, ohne aber wissenschaftliche Systematik oder enzyklopädische Vollständigkeit anzustreben. Dabei wird der Bogen der Texte, die die wichtigsten Aspekte des Parallel-Processing abdecken sollen. von der reinen Theorie bis zu praktisch nutzbaren Produkten der einschlägigen Industrie gespannt.

Bisher ist erschienen: "Datenverarbeitung im Gänsemarsch stößt an ihre Grenzen" (CW 20, Seite 58).