Cut-Through-Routing

Im Ring läßt sich die Kommunikationszeit durch CT-Routing verbessern. In jeder Iteration findet eine Kommunikation zwischen Partnern wie im ONE_TO_ALL_BC-Algorithmus für den Hypercube statt. D.h., bei 8 Prozessoren sendet zuerst 000 nach 100, dann gleichzeitig 000 nach 010 und 100 nach 110, dann gleichzeitig 000 nach 001, 010 nach 011, 100 nach 101 und 110 nach 111.

One-to-All mit CT im Ring

In der i -ten Iteration dauert die Kommunikation

t_s + t_w · m + t_h · $${\frac{p}{2^i}}$$

Die Gesamtzeit lautet daher

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

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

Für große m und kleine t_s,t_h bedeutet dies gegenüber SF-Routing eine Beschleunigung um den Faktor ${\frac{p}{2 \cdot \log p}}$ .

Im Gitter läßt sich dieselbe Idee zunächst zum Versorgen einer Zeile anwenden, danach werden analog alle Spalten bearbeitet. Jede dieser beiden Phasen dauert

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

Daraus ergibt sich

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

One-to-all mit Cut-Through-Routing im Gitter