Hypercube (communication pattern): Difference between revisions

Revision as of 19:00, 31 March 2019

Revision as of 19:03, 31 March 2019

Line 43:

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

'''All-Gather''' operations start with each processing element having a message <math>m_i</math>. AfterThe goal of the operation is finishedfor each processing unitelement knowsto know the messages of all other processing elements, with messagei.e. <math>x := m_0 \cdot m_1 \dots m_p</math> where <math>\cdot</math> is concatenation. The operation can be implemented following the algorithm template.

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

Line 55:

'''endfor'''

With each iteration, the transferred message doubles in length. This leads to a run-timeruntime 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 '''All-Gather''' reduces the number of communications compared to Reduce and Broadcast.