Hypercube (communication pattern): Difference between revisions

Revision as of 18:38, 31 March 2019

Revision as of 18:43, 31 March 2019

Line 42:

[[File:Hypergraph Communication Steps for Prefix Sum.png|thumb|Example for a prefix sum calculation. Upper number: number <math>m_i</math> that each processing element contributes to the prefix sum. Lower number: prefix sum (at the end of the computation).]]

=== Gossip All-Gather/ All-Reduce ===

'''GossipAll-Gather''' operations start with each processing element having a message <math>m_i</math>. After the operation is finished each processing unit knows the messages of all other processing elements, with message <math>x := m_0 \cdot m_1 \dots m_p</math>. The operation can be implemented following the algorithm template.

'''Input''': message <math>x := m_i</math> at processing unit<math>i</math>.

Line 57:

With each iteration the transferred message doubles in length. This leads to a run-time of <math>T(n,p) \approx \sum_{j=0}^{d-1}(T_\text{start} + n \cdot 2^jT_\text{byte})= \log(p) T_\text{start} + (p-1)nT_\text{byte}</math>.

The same principle can be applied to the '''All-Reduce''' operations, but instead of concatenating the messages, it performs an operation on the two messages. So it is a '''Reduce''' operation, where all processing units know the result. In Hypercubes a modified '''GossipAll-Gather''' reduces the number of communications compared to Reduce and Broadcast.

=== All-to-All ===