Cyclades: Conflict-free Asynchronous Machine Learning
Xinghao Pan, Maximilian Lam, Stephen Tu, Dimitris Papailiopoulos, Ce Zhang, Michael I Jordan, Kannan Ramchandran, Christopher Ré
Abstract
We present Cyclades, a general framework for parallelizing stochastic optimization algorithms in a shared memory setting. Cyclades is asynchronous during model updates, and requires no memory locking mechanisms, similar to Hogwild!-type algorithms. Unlike Hogwild!, Cyclades introduces no conflicts during parallel execution, and offers a black-box analysis for provable speedups across a large family of algorithms. Due to its inherent cache locality and conflict-free nature, our multi-core implementation of Cyclades consistently outperforms Hogwild!-type algorithms on sufficiently sparse datasets, leading to up to 40% speedup gains compared to Hogwild!, and up to 5\times gains over asynchronous implementations of variance reduction algorithms.
BibTeX
@inproceedings{NIPS2016_28e209b6,
author = {Pan, Xinghao and Lam, Maximilian and Tu, Stephen and Papailiopoulos, Dimitris and Zhang, Ce and Jordan, Michael I and Ramchandran, Kannan and R\'{e}, Christopher},
booktitle = {Advances in Neural Information Processing Systems},
editor = {D. Lee and M. Sugiyama and U. Luxburg and I. Guyon and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Cyclades: Conflict-free Asynchronous Machine Learning},
url = {https://proceedings.neurips.cc/paper_files/paper/2016/file/28e209b61a52482a0ae1cb9f5959c792-Paper.pdf},
volume = {29},
year = {2016}
}