Hypercube (communication pattern): Difference between revisions

Revision as of 17:14, 31 March 2019

Revision as of 17:20, 31 March 2019

Line 59:

=== Gossip / All-Reduce ===

'''Gossip''' 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 algorithmnalgorithm template.

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

Line 67:

<math>y := i \text{ XOR } 2^k</math>

'''Send''' <math>x</math> '''to''' <math>y</math>

'''RecieveReceive''' <math>x'</math> '''from''' <math>y</math>

<math>x := x \cdot x'</math>

'''endfor'''

With each iteration the transferedtransferred 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 concancatingconcatenating 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 '''Gossip''' reduces the number of communications compared to Reduce and Broadcast.

=== All-to-All ===