Allreduce is a fundamental collective used in parallel computing and distributed training of machine learning models, and can become a performance bottleneck on large systems. In-network computing improves Allreduce performance by reducing packets on the fly using network routers. However, the throughput of current innetwork solutions is limited to a single link bandwidth. We develop, compare and contrast two different sets of Allreduce ...

We present the first parallel depth-first search algorithm for undirected graphs that has near-linear work and sublinear depth. Concretely, in any n-node m-edge undirected graph, our algorithm computes a DFS in Õ(g√n) depth and using Õ (m + n) work. All prior work either required ω(n) depth, and thus were essentially sequential, or needed a high poly(n) work and thus were far from being work-efficient.