collective operation
≈ 4 min read
Names in other languages
- Deutschkollektive Operationen
- Englishcollective operation
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
Collective operations are building blocks for interaction patterns, that are often used in SPMD algorithms in the parallel programming context. Hence, there is an interest in efficient realizations of these operations. A realization of the collective operations is provided by the Message Passing Interface (MPI).
Background
Collective operations are building blocks for interaction patterns, that are often used in SPMD algorithms in the parallel programming context. Hence, there is an interest in efficient realizations of these operations. A realization of the collective operations is provided by the Message Passing Interface (MPI). If we do not have an equal distribution, i.e. node p_i has a message of size n_i , we get an upper bound for the runtime by setting n = \max(n_0, n_1, \dots, n_{p-1}) . A distributed memory model is assumed.
Evidence and sources
The concepts are similar for the shared memory model. However, shared memory systems can provide hardware support for some operations like broadcast ( ) for example, which allows convenient concurrent read. Thus, new algorithmic possibilities can become available. The prefix-sum or scan operation is used to collect data or partial results from different processing units and to compute intermediate results by an operator, which are stored on those processing units. It can be seen as a generalization of the reduce operation ( ).
Given p processing units, message m_i is on processing unit p_i . The operator \otimes must be at least associative, whereas some algorithms require also a commutative operator and a neutral element. Common operators are sum , min and max . Eventually processing unit p_i stores the prefix sum \otimes_{i' m_{i'} . In the case of the so-called exclusive prefix sum, processing unit p_i stores the prefix sum \otimes_{i' m_{i'} . Some algorithms require to store the overall sum at each processing unit in addition to the prefix sums.
For short messages, this can be achieved with a hypercube topology if p is a power of two. For long messages, the hypercube ( , ) topology is not suitable, since all processing units are active in every step and therefore pipelining can't be used. A binary tree topology is better suited for arbitrary p and long messages ( ). Prefix-sum on a binary tree can be implemented with an upward and downward phase.
In the upward phase reduction is performed, while the downward phase is similar to broadcast, where the prefix sums are computed by sending different data to the left and right children. With this approach pipelining is possible, because the operations are equal to reduction ( ) and broadcast ( ). Pipelined prefix sum on a binary tree is possible in \mathcal{O}(\alpha \log p + \beta n) . Given p processing units p_i , a fixed processing unit p_j that holds the message m = m_1 \cdot m_2 \cdot \ldots \cdot m_p .
How it works
We want to transport the message m_i onto p_i . The same implementation concerns as for gather ( ) apply. This leads to an optimal runtime in \mathcal{O}(\alpha \log p + \beta p n) . All-to-all is the most general communication pattern. For 0 \leq i, j , message m_{i, j} is the message that is initially stored on node i and has to be delivered to node j . We can express all communication primitives that do not use operators through all-to-all.
For example, broadcast of message m from node p_k is emulated by setting m_{i, j} = m for i = k and setting m_{l, j} empty for l \neq k . Assuming we have a fully connected network, the best possible runtime for all-to-all is in \mathcal{O}(p (\alpha + \beta n)) . This is achieved through p rounds of direct message exchange. For p power of 2, in communication round k , node p_i exchanges messages with node p_j, j = i \oplus k .
If the message size is small and latency dominates the communication, a hypercube algorithm can be used to distribute the messages in time \mathcal{O}(\log p (\alpha + \beta p n)) .
Text derived from https://en.wikipedia.org/w/index.php?oldid=1369325659 under CC BY-SA 4.0; modifications have been made.