2.5 PRAM

Einen SIMD-Rechner mit variabler Prozessorzahl und shared memory bezeichnet man als PRAM (Parallel Random Access Machine). Man unterscheidet vier Varianten bzgl. der Gleichzeitigkeit von Lese- und Schreiboperationen:

EREW: exclusive read, exclusive write

CREW: concurrent read, exclusive write

ERCW: exclusive read, concurrent write

CRCW: concurrent read, concurrent write

Bei gleichzeitigem Schreiben muß die Semantik festgelegt werden,

z.B. Prozessor mit größter ID setzt sich durch.

z.B. ein zufällig gewählter Prozessor setzt sich durch.

z.B. nur erlaubt, wenn alle dasselbe schreiben.

Beispiel:

Gegeben: VAR a: ARRAY[0..n-1] OF INTEGER;

Gesucht: antwort := Maximum der n Zahlen

Zur Vereinfachung sei angenommen, daß alle Zahlen verschieden sind. Offenbar beträgt die Sequentialzeit O(n) .

EREW PRAM zur Maximumsuche auf n Zahlen
Verwendet werden n/2 Prozessoren P₀,P₁,...,P_{n/2 - 1}

d := n;
REPEAT
     d := d DIV 2;
     FOR ALL 0 $\leq$ i $\leq$ d - 1 DO IN PARALLEL
         P_i : a[i] := maximum( a[2 * i], a[2 * i + 1] )
     END
UNTIL d = 1;
antwort := a[0];

Bemerkung: Statt des Maximums kann mit dieser Methode auch die Summe gebildet werden.

Zugriffspfade im ersten Schleifendurchlauf

Parallelzeit: O(log n)

Kosten: O(n · log n)

Speedup: O(n/log n)

Effizienz: O(n/(n · logn)) = O(1/log n)

Effizienz (asymptotisch) bei Maximumsuche mit EREW PRAM

CRCW PRAM zur Maximumsuche auf n Zahlen
Verwendet werden n ² Prozessoren P₀₀,P₀₁,P₀₂,...,P_{n - 1n - 1} .
Beim gleichzeitigen Schreiben sei nur ein einziger Wert erlaubt!

VAR sieger : ARRAY [0..n-1] OF BOOLEAN;

FOR ALL 0 $\leq$ i $\leq$ n - 1 DO IN PARALLEL
     P_0i : sieger[i] := TRUE
END;

FOR ALL 0 $\leq$ i, j $\leq$ n - 1 DO IN PARALLEL
     P_ij : IF a[i] < a [j] THEN sieger[i] := FALSE END
END;

FOR ALL 0 $\leq$ i $\leq$ n - 1 DO IN PARALLEL
     P_0i : IF sieger[i] THEN antwort := a[i] END
END;

Parallelzeit: O(1)

Kosten: O(n ²)

Speedup: O(n)

Effizienz: O(n/n ²) = O(1/n)

Effizienz (asymptotisch) bei Maximumsuche mit CRCW PRAM

CREW PRAM zur Matrizenmultiplikation
Verwendet werden n ³ Prozessoren P₀₀₀,P₀₀₁,...,P_{n - 1,n - 1,n - 1} .

Gegeben: zwei n × n -Matrizen a,b .

Gesucht: ihr Matrizenprodukt c mit

c_ij = $$\sum_{k=0}^{n - 1}$$a_ik · b_kj

VAR a,b : ARRAY [0..n-1] [0..n-1] OF REAL;

FOR ALL 0 $\leq$ i, j, k $\leq$ n - 1 DO IN PARALLEL
     P_ijk : tmp[i, j, k] := a[i, k] * b[k, j]
END
(* nun wird mit n ³/2 Prozessoren *)
(* das Array tmp [i, j, *] aufaddiert *)

d := n;
REPEAT
     d := d DIV 2;
     FOR ALL 0 $\leq$ k $\leq$ d - 1 DO IN PARALLEL
     P_ijk : tmp[i, j, k] := tmp[i, j, 2 * k] + tmp[i, j, 2 * k + 1]
     END
UNTIL d = 1;

Das Ergebnis c_ij befindet sich in tmp[i, j, 0].

Sequentialzeit: O(n ³)

Parallelzeit: O(log n)

Speedup: O(n ³/log n)

Effizienz: O(n ³/n ³ · logn) = O(1/log n)