Autor: Georg Pirker
[ < ]
[ globale Übersicht ]
[ Kapitelübersicht ]
[ Stichwortsuche ]
[ > ]
4.5.1 Abstrakte Computermodelle
Abstrakte Computermodelle dienen dazu, unabhängig von Hardware-Details
zu beschreiben, welche
grundsätzlichen Aktionen in einem Berechnungsschritt ausgeführt werden
können und auf welche Art auf Daten zugegriffen wird (Almasi,
Gottlieb [85], Mayr [298], Blelloch).
Solche Modelle bilden einen Rahmen, der festlegt,
welche Algorithmen überhaupt realisierbar sind. Außerdem ermöglichen sie
Komplexitätsanalysen von Algorithmen, die unabhängig von den
Eigenheiten spezieller Computersysteme sind.
RAM-Modell
Das Standardmodell für konventionelle Computer (Einprozessorsysteme) ist
die sogenannte Random Access Machine1
(RAM). Ein RAM-Modell besteht aus folgenden Komponenten:
- einer zentralen Recheneinheit samt einem Akkumulator, der vor der
Ausführung einer Operation die Operanden aufnimmt und in dem nach
der Ausführung des Befehls Zwischenergebnisse gespeichert werden,
- einem unbeschränkten Speicher, der beliebig viele
Speicherzellen besitzt, die unbeschränkt große und kleine Zahlen
enthalten können,
- einem Programm und
- einer Ein- und einer Ausgabevorrichtung.
Das Programm besteht aus Instruktionen (z.B. Addition einer
Zahl zum aktuellen Wert des Akkumulators, übertragen des Akkumulatorinhalts
in den Speicher, Laden einer Zahl aus dem Speicher in den Akkumulator etc.).
Während eines Berechnungsschrittes wird von einer RAM genau eine Instruktion
ihres Programms ausgeführt.
Dabei wird die Annahme getroffen, daß alle Instruktionen gleich
lange dauern, unabhängig von Art und Größe der Operanden.
Das Programm wird sequentiell abgearbeitet. Nur im Fall einer Verzweigung
(bedingter oder unbedingter Sprung) wird die sequentielle
Abarbeitungsreihenfolge durchbrochen.
Beispiel (Summation)
Die Summation von n Zahlen nach dem simplen Schema
|
s := 0;
| |
s := s+x1,
| |
s := s+x2,
... ,
s := s+xn
|
erfordert offensichtlich n RAM-Rechenschritte (wenn man die Initialisierung
vernachlässigt, sonst n+1 Schritte).
PRAM-Modell
Das RAM-Modell als Abstraktion eines
Einprozessorsystems kann man zu einem Modell eines Mehrprozessorsystems
(Parallelrechners) mit gemeinsamem Speicher erweitern. Man erhält eine
Parallel Random Access Machine (PRAM) der Größe p, indem man p
RAMs und einen gemeinsamen Speicher in einem Modell zusammenfaßt.
Die gravierendste Vereinfachung beim PRAM-Modell ist die Annahme, daß die
für die Bearbeitung benötigte Zeitdauer für alle Instruktionen und speziell
auch für alle Speicherzugriffe unabhängig von der Größe p der PRAM ist;
es wird angenommen, daß der Inhalt jeder Speicherzelle von jedem Programm in
einem Zeitschritt erreicht werden kann.
Beispiel (Summation)
Die Summation von n Zahlen erfordert nur
log2 n
Rechenschritte einer PRAM, sofern
p >=
n/log2 n
ist. Ein Rechenschritt besteht hier aus der paarweisen Summation, bei der die
Nachbarelemente
(x1,x2), (x3,x4), ...
jeweils gleichzeitig zueinander addiert werden. So wird die Anzahl der
Summanden wiederholt halbiert2,
bis nur mehr einer übrigbleibt, der dann die Gesamtsumme ist.
MPRAM-Modell
Als Modell von Parallelrechnern mit verteiltem Speicher verwendet man die
Message Passing Random Access Machine (MPRAM).
Sie setzt sich wie die PRAM aus mehreren RAMs zusammen, wobei jetzt aber
auch die Speicher vervielfacht werden, sodaß jede einzelne RAM nur auf
ihren eigenen Speicher Zugriff hat.
Kommunikation zwischen den p RAMs ist möglich; welche RAMs kommunizieren
können, wird durch einen Verbindungsgraphen ausgedrückt.
VRAM-Modell
Eine Vector Random Access Machine (VRAM) enthält zusätzlich zu den
RAM-Komponenten einen unbeschränkten Vektorspeicher, Möglichkeiten der
Ein- und Ausgabe von Vektoren und spezielle Vektorinstruktionen.
Eine VRAM kann in einem Zeitschritt Instruktionen auf einer festen Anzahl
von Vektoren aus dem Vektorspeicher und Skalaren aus dem Skalarspeicher
ausführen, wie z.B. die elementweise Summation von zwei Vektoren oder
die Multiplikation eines Vektors mit einem Skalar.
Im Gegensatz zur PRAM, wo die sequentiellen Instruktionen der RAM
parallel ausgeführt werden, kommen bei einer VRAM
neue, parallele Instruktionen (Vektorinstruktionen) dazu, die
sequentiell ausgeführt werden.
Fußnoten
1deutsch: Maschine mit wahlfreiem Zugriff auf die Speicherzellen;
man spricht auch von verallgemeinerten Registermaschinen.
2Im Fall einer ungeraden Anzahl von Summanden wird der übrig
bleibende Summand unverändert in den nächsten Schritt
übernommen.
[ < ]
[ globale Übersicht ]
[ Kapitelübersicht ]
[ Stichwortsuche ]
[ > ]