ASPIRE: exploiting asynchronous parallelism in iterative algorithms using a relaxed consistency based DSM

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