3.5 PRAMs: Varianten und Simulationen

PRAM-Modelle

1. EREW PRAM (Exclusive Read Exclusive Write). Dies ist das restriktivste Modell von allen. In keinem Schritt dürfen zwei Prozessoren auf die gleiche Zelle zugreifen, weder lesend noch schreibend.
2. CREW PRAM (Concurrent Read Exclusive Write). Das ist das übliche Modell, das wir bisher verwendet haben. Es ist erlaubt, dass mehrere Prozessoren gleichzeitig die gleiche Speicherzelle lesen. Wenn allerdings ein Prozessor in eine Zelle schreiben will, so darf in diesem Schritt kein anderer Prozessor auf diese Zelle zugreifen.
   Vorsicht. Der Algorithmus muss garantieren, dass es nie zu unerlaubten Konflikten kommt. Falls also z.B. manchmal zwei Prozessoren auf die gleiche Zelle schreiben wollen, dann gilt dieser Algorithmus als inkorrekt für eine CREW PRAM. Selbst wenn das Ergebnis nicht vom Ausgang dieser konfligierenden Schreibsituation abhängt.

   Übungsaufgabe 3.5.1 Zeigen Sie, wie EREW PRAMs und CREW PRAMs mit Schaltkreisen zusammenhängen.

   1. Zeigen Sie, dass ein Schaltkreis (mit beliebig Gates wie Max oder Minmax oder Summe, nicht nur Booleschen) mit $m$ Gates simuliert werden kann durch eine CREW PRAM mit $m$ Prozessoren. Gehen Sie dabei aus, dass man für ein Gate $i$ sehr leicht berechnen kann, woher die Input-Kabel kommen.
   2. Welche Bedingung sollte ein Schaltkreis erfüllen, so dass Sie ihn ohne Probleme durch eine EREW PRAM simulieren können?

   Übungsaufgabe 3.5.2 Überlegen Sie sich, wie man eine CREW PRAM auf einer EREW PRAM simuliert. Gehen Sie wie folgt vor:

   1. Betrachten Sie das Szenario, dass alle $n$ Prozessoren in diesem Schritt die gleiche Speicherzelle lesen wollen. Zeigen Sie, wie Sie dies mit $O(\log n)$ EREW-Schritten ohne Lesekonflikte simulieren können.
   2. Betrachten Sie nun den allgemeinen Fall. Es gibt $m$ Speicherzellen, und jeder Prozessor will eine davon lesen. Wie lösen Sie die Lesekonflikte auf? Seien Sie verschwenderisch mit Speicherplatz und gönnen sich für Ihren EREW-Algorithmus $O(nm)$ Speicherplatz!
3. CRCW PRAM (Concurrent Read Concurrent Write). Dies ist das stärkste Modell. Wir erlauben, dass mehrere Prozessoren gleichzeitig lesend sowie schreibend auf eine Zelle zugreifen. In diesem Falle müssen wir spezifizieren, was in so einem Falle geschieht, wie also der Konflikt gelöst wird. Dies führt zu einer Vielzahl möglicher Untermodelle:
   1. Common. Gleichzeitige Schreiboperationen auf der gleichen Zelle sind nur erlaubt, wenn alle Prozessoren den gleichen Wert schreiben wollen. Der Algorithmus muss dies garantieren, ansonsten gilt er als inkorrekt.
   2. Arbitrary. Wenn mehrere Prozessoren in eine Zelle schreiben wollen, dann wird der "Sieger" beliebig bestimmt. Um als korrekt zu gelten, muss der Algorithmus für jede beliebige (auch gegnerische) Siegerbestimmungsstrategie erfolgreich sein.
   3. Priority. Wenn mehrere Prozessoren in eine Zelle schreiben wollen, dann gewinnt der Prozessor mit dem größten Index.

   Übungsaufgabe 3.5.3 Überlegen Sie sich, wie man eine Priority CRCW PRAM (also das bisher stärkste Modell) auf einer EREW PRAM simuliert. Nehmen Sie sich $O(nm)$ Platz und gehen dabei vor wie in Übungsaufgabe 3.5.2.

   Übungsaufgabe 3.5.4 Simulieren Sie eine Priority CRCW PRAM mit $n$ Prozessoren und $m$ Speicher auf einer CREW PRAM mit $n$ Prozessoren und $m+O(n)$ Speicherplatz, so dass jeder Schritt der Priority CRCW PRAM mit $O(\log n)$ EREW-Schritten simuliert wird!

   Tip: Verwenden Sie Coles Mergesort-Algorithmus!

   Übungsaufgabe 3.5.5 Gehen Sie nochmal Valiants $O(\log \log n)$-Algorithmus für Max durch (Kapitel 3.3). Zeigen Sie, wie man ihn auf einer Common CRCW PRAM in $O(\log \log n)$ Zeit implementieren kann.

   Dies sind die drei geläufigsten CRCW-PRAM-Modelle. Wir werden gleich weitere, "esoterischere" Modelle kennenlernen.
   4. Robust. No assumption is being made. Arbitrary value? No change? Special symbol? Some completely different garbage symbol? Algorithm must work for all possibilities.
   5. Tolerant. If more than one processor attempts to write, nothing is written. Gil and Matias do not mention whether the processors "see" that their attempt has been unsuccessful.
   6. Collision. If more than one processor attempts to write, a special collision symbol # is written.
   7. Collision+. Like Collision, but if all attempts are unanimous (same value), then that same value is being written into the cell.

Maximum und Minimum in $O(1)$ auf einer Arbitrary CRCW PRAM

Valiants Algorithmus aus Kapitel 3.3 braucht $O(\log \log n)$ Schritte, um mit $n$ Prozessoren das Maximum eines Arrays der Länge $n$ zu finden - wenn man nur die Schritte zählt, in denen Vergleichsoperationen ausgeführt werden. Wenn wir alle Operationen zählen, so braucht er dann doch mehr. Auf gewissen PRAM-Modellen können wir ihn jedoch tatsächlich in $O(\log \log n)$ implementieren.

Im folgenden betrachten wir das Modell Collision. Sie können sich auch Arbitrary vorstellen, aber Collision ist etwas schwächer.

Gil and Matias do not require the ${\mathrm{\Phi }}_i$ to be disjoint (at least they don't state it). If we assume that they are disjoint, I think we can view it as follows: every processor is given a color $\text{col}(P)$ and a value $\text{val}(P)$. We want to determine the "winner" for each color, i.e., compute $\mathrm{W}\mathrm{i}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{r}(c)$ for each color $c$ such that

If no processor has color $c$ then we set $\mathrm{W}\mathrm{i}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{r}(c)=\mathrm{\perp }$. Note that $m$ (the number of colors) corresponds to the size of the memory. $\text{col}(P)=c,\text{val}(P)=v$ means that $P$ wants to write value $v$ into cell $c$. The memory might be much larger than the number of processors, so we cannot afford a processor for each color!