Store-and-Forward

Im Ring sendet jeder Prozessor zunächst seine Nachricht an seinen rechten Nachbarn und reicht danach von links erhaltene Nachrichten weiter.

Die Gesamtzeit beträgt

T_{all - to - all} = (t_s + t_h + t_w · m) · (p - 1)

Im Gitter erhält zunächst jeder Prozessor einer Zeile mit Hilfe von All-to-All im Ring die gesamte Zeileninformation. Danach werden innerhalb der Spalten diese angesammelten Informationen herumgeschickt. Die erste Phase dauert

(t_s + t_h + t_w · m) · ($$\sqrt{p}$$ - 1) .

Die zweite Phase benötigt wegen der bereits angesammelten Daten

(t_s + t_h + t_w · m · $$\sqrt{p}$$) · ($$\sqrt{p}$$ - 1) .

Daraus ergibt sich

T_{all - to - all} = 2 · (t_s + t_h) · ($$\sqrt{p}$$ - 1) + t_w · m(p - 1) .

Im Hypercube vereinigen im i -ten Durchlauf die Prozessoren, die sich im i -ten Bit unterscheiden, ihre Informationen (siehe Bild 4.1).

     result := my_msg;
     for i := 0 to d-1 do
         partner := my_id XOR 2ⁱ;
         send result to partner;
         receive msg from partner;
         result := result $\cup$ msg;
     end;
end

In der i -ten Phase ist die Nachrichtengröße m · 2ⁱ. Ein Austausch dauert t_s + t_h + 2^{i - 1}. Also beträgt die Gesamtzeit

T_{all - to - all} = $$\sum_{i = 1}^{\log p-1}$$(t_s + t_h + 2ⁱ · t_w · m)

= (t_s + t_h) · logp + t_w · m · (p - 1) .

Wird statt einer Vereinigung von Daten eine Verknüpfung durchgeführt, so entsteht aus All-to-All eine Reduktion, bei der die Informationsmenge in jedem Schritt gleich bleibt. Für die Summenbildung ist m = 1 , und es folgt

T_reduktion = (t_s + t_h + t_w) · logp .

All-to-All im Hypercube