Search Results

Collective communication primitives are used as building blocks in distributed and parallel programming algorithms: they include Broadcast, AllReduce, Gather, and more. These primitives encapsulate aggregation and dissemination tasks, where each host has a data buffer storing a long vector of inputs, and the goal is to aggregate and/or disseminate these inputs in a pointwise manner. Typically, network protocols computing collective communication primitives are implemented over communication networks that use switches to forward messages, and recently also over programmable switches, which may also carry out limited computation. In this work we study the asymptotic rate of several collective communication primitives: assuming that the capacity of each host-to-switch link suffices to send one input per second, how many instances can we solve per second? We show that in any k-host network that supports both permutation traffic matrices and pipelined serial traffic, the asymptotic rate of the Gather, Scatter, AllGather and AllToAll primitives is ≈ 1/(k-1), while Broadcast and PrefixSum have asymptotic rate ≈ 1. This holds for both forwarding-only and programmable switches. In contrast, for the AllReduce primitive, we show that the rate of computing associative reduction operators in networks with programmable switches is close to 1, while the rate in networks with forwarding-only switches depends on the reduction operator and on the scenario. In particular, for the maximum operator, the rate is close to 1, but the rate of computing integer sums and sums over finite Abelian groups is close to 1/2, even when protocols are allowed randomization, with vanishing {worst-case} error. Moreover, we show that depending on the parameters of the problem, with vanishing distributional error the rate of computing AllReduce of integer sums over forwarding-only switches can be as bad as half the rate afforded by programmable switches, match the rate, or be anywhere in between. To prove these results we give for the first time sharp general communication-complexity lower bounds for these primitives, using information-theoretic techniques. Prior work on the communication cost of collective communication primitives considered only highly restricted protocols where hosts can only apply reduction operators "as a black box’’; to complement our work, we show this restriction can actually lead to suboptimal throughput - for example, when computing AllReduce with the maximum operator.

We consider a multiparty setting where k parties have private inputs X_1,…,X_k ⊆ [n] and wish to compute the intersection ⋂_{𝓁 =1}^k X_𝓁 of their sets, using as little communication as possible. This task generalizes the well-known problem of set disjointness, where the parties are required only to determine whether the intersection is empty or not. In the worst-case, it is known that the communication complexity of finding the intersection is the same as that of solving set disjointness, regardless of the size of the intersection: the cost of both problems is Ω(n log k + k) bits in the shared blackboard model, and Ω (nk) bits in the coordinator model. In this work we consider a realistic setting where the parties' inputs are independent of one another, that is, the input is drawn from a product distribution. We show that this makes finding the intersection significantly easier than in the worst-case: only Θ̃((n^{1-1/k} (H(S) + 1)^{1/k}) + k) bits of communication are required, where {H}(S) is the Shannon entropy of the intersection S. We also show that the parties do not need to know the exact underlying input distribution; if we are given in advance O(n^{1/k}) samples from the underlying distribution μ, we can learn enough about μ to allow us to compute the intersection of an input drawn from μ using expected communication Θ̃((n^{1-1/k}𝔼[|S|]^{1/k}) + k), where |S| is the size of the intersection.