Efficient Cross-Cloud Partial Reduce With CREW

By allowing <inline-formula><tex-math notation="LaTeX">$p$</tex-math></inline-formula> out of <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> workers to conduct <i>all reduce</i> operations among them for a round of synchronization, <i>partial reduce</i>, a promising partially-asynchronous variant of <i>all reduce</i>, has shown its power in alleviating the impacts of stragglers for iterative distributed machine learning (DML). Current <i>partial reduce</i> solutions are mainly designed for intra-cluster DML, in which workers are networked with high-bandwidth LAN links. Yet no prior work has looked into the problem of how to achieve efficient <i>partial reduce</i> for cross-cloud DML, where inter-worker connections are with scarcely-available capacities. To fill the gap, in this paper, we propose <small>CREW</small>, a flexible and efficient implementation of <i>partial reduce</i> for cross-cloud DML. At the high level, <small>CREW</small> is built upon the novel design of employing all active workers along with their internal connection capacities to execute the involved communication and computation tasks; and at the low level, <small>CREW</small> employs a suite of algorithms to distribute the tasks among workers in a load-balanced way, and deal with possible outages of workers/connections, and bandwidth contention. Detailed performance studies confirm that, <small>CREW</small> not only shortens the execution of each <i>partial reduce</i> operation, outperforming existing communication schemes such as PS, Ring, <small>TopoAdopt</small>, and BLINK greatly, but also significantly accelerates the training of large models, up to <inline-formula><tex-math notation="LaTeX">$15\times$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$9\times$</tex-math></inline-formula>, respectively, when compared with the all-to-all direct communication scheme and <i>original partial reduce</i> design.