Store-And-Forward

Im Ring wird, ausgehend vom Master, die Nachricht in zwei Richtungen propagiert.

Die Zeit beträgt

T_{one - to - all} = (t_s + t_h + t_w · m) · $$\lceil$$$${\frac{p}{2}}$$$$\rceil$$

Im 2-dimensionalen Gitter wird zunächst eine Zeile als Ring mit der Nachricht versorgt, danach werden alle Spalten gleichzeitig wie Ringe versorgt.

Store-and Forward im MC ²

Da eine Zeile bzw. Spalte $\sqrt{p}$ Prozessoren aufweist, beträgt die Zeit

T_{one - to - all} = 2 · (t_s + t_h + t_w · m) · $$\lceil$$$${\frac{\sqrt{p}}{2}}$$$$\rceil$$

Für ein dreidimensionales Gitter ergibt sich

T_{one - to - all} = 3 · (t_s + t_h + t_w · m) · $$\lceil$$$${\frac{\sqrt[3]{p}}{2}}$$$$\rceil$$

Im Hypercube sendet nacheinander für jede Dimension d - 1,d - 2,...,0 der Prozessor mit d -tem Bit = 0 an den Prozessor mit d -tem Bit = 1 . Dabei sind nur solche Prozessoren aktiv, bis zu denen die Nachricht schon vorgedrungen ist.

procedure ONE_TO_ALL_BC(d, my_id, X) /* Broadcast X from 0 to all */
     mask := 2^d - 1;                     /* Set lower d bits of mask to 1 */
     for i := d - 1 downto 0 do                     /* Outer loop */
         mask := mask XOR 2ⁱ;                /* Set bit i of mask 0 */
         if (my_id AND mask) = 0 then
         /* if the lower i bits of my_id are 0 */
             if (my_id AND 2ⁱ) = 0 then
                 msg_destination := my_id XOR 2ⁱ;
                 send X to msg_destination;
             else
                 msg_source := my_id XOR 2ⁱ;
                 receive X from msg_source;
         end
     end
end

Die Gesamtdauer beträgt

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

One-to-All im Hypercube, zeitlicher Verlauf gestrichelt

In abgewandelter Form kann die Prozedur ONE_TO_ALL_BC auch zum Einsammeln von Nachrichten verwendet werden. Es sendet nacheinander für Dimension d - 1,d - 2,...,0 der Prozessor mit d -tem Bit = 0 an den Prozessor mit d -tem Bit = 1 , wo anschließend die Verknüpfung stattfindet. Dabei werden solche Prozessoren passiv, die ihren Beitrag bereits abgeschickt haben.