SPLASH 2014
Mon 20 - Fri 24 October 2014 Portland, Oregon, United States
Fri 24 Oct 2014 13:30 - 13:52 at Salon F - Distributed Computing Chair(s): Madan Musuvathi

Many vertex-centric graph algorithms can be expressed via asynchronous parallelism by relaxing certain read-after-write data dependences and thus allowing threads to compute vertex values using stale (i.e., not the most recent) values of their neighboring vertices. We observe that on distributed shared memory systems, by converting synchronous algorithms into their asynchronous counterparts, algorithms can be made tolerant to high inter-node communication latency. However, high inter-node communication latency can lead to excessive use of stale values causing an increase in the number of iterations required by the algorithm to converge. In this paper we design a relaxed memory consistency model and consistency protocol that simultaneously tolerate communication latency and minimize the use of stale values. We demonstrate that for a range of asynchronous graph algorithms, on an average, our approach outperforms algorithms based upon: prior relaxed memory models that allow stale values by at least 2.27x; and Bulk Synchronous Parallel (BSP) model by 4.2x. We also show that our approach performs well in comparison to GraphLab, a popular distributed graph processing framework.

ASPIRE: Exploiting Asynchronous Parallelism in Iterative Algorithms using a Relaxed Consistency based DSM (oopsla2014-vora.pdf)1.83MiB

Fri 24 Oct

oopsla2014
13:30 - 15:00: OOPSLA - Distributed Computing at Salon F
Chair(s): Madan MusuvathiMicrosoft Research
oopsla2014141415020000013:30 - 13:52
Talk
Keval VoraUniversity of California, Riverside, Sai Charan KoduruUniversity of California, Riverside, Rajiv GuptaUC Riverside
Link to publication Media Attached File Attached
oopsla2014141415155000013:52 - 14:15
Talk
Brandon HoltUniversity of Washington, Preston BriggsUniversity of Washington, Luis CezeUniversity of Washington, Mark OskinUniversity of Washington
Link to publication Media Attached File Attached
oopsla2014141415290000014:15 - 14:37
Talk
Tian XiaoTsinghua University / Microsoft Research, Zhenyu GuoMicrosoft Research, Hucheng ZhouMicrosoft Research, Jiaxing ZhangMicrosoft Research, Xu ZhaoUniversity of Toronto, Chencheng YeHuazhong University of Science and Technology, Xi WangMIT CSAIL, Wei LinMicrosoft Bing, Wenguang ChenTsinghua University, Lidong ZhouMicrosoft Research
Link to publication Media Attached
oopsla2014141415425000014:37 - 15:00
Talk
Cosmin RadoiUniversity of Illinois, Stephen J FinkIBM, Rodric RabbahIBM Research, Manu SridharanSamsung Research America
Link to publication Media Attached