This paper proposes a new algorithmic paradigm - k-level asynchronous (KLA) - that bridges level-synchronous and asynchronous paradigms for processing graphs. The KLA paradigm enables the level of asynchrony in parall...
详细信息
ISBN:
(纸本)9781450328098
This paper proposes a new algorithmic paradigm - k-level asynchronous (KLA) - that bridges level-synchronous and asynchronous paradigms for processing graphs. The KLA paradigm enables the level of asynchrony in parallel graphalgorithms to be parametrically varied from none (levelsynchronous) to full (asynchronous). The motivation is to improve execution times through an appropriate trade-off between the use of fewer, but more expensive global synchronizations, as in level-synchronous algorithms, and more, but less expensive local synchronizations (and perhaps also redundant work), as in asynchronousalgorithms. We show how common patterns in graphalgorithms can be expressed in the KLA pardigm and provide techniques for determining k, the number of asynchronous steps allowed between global synchronizations. Results of an implementation of KLA in the stapl graph Library show excellent scalability on up to 96K cores and improvements of 10x or more over levelsynchronous and asynchronous versions for graphalgorithms such as breadth-first search, PageRank, k-core decomposition and others on certain classes of real-world graphs.
暂无评论