AsyIter: tolerating computational skew of synchronous iterative applications via computing decomposition

摘要

Iterative computing is pervasive in web applications, data mining and scientific computing. Many parallel algorithms for such applications are synchronous algorithms which need strict synchronization between iterations to ensure their correctness, making the performance sensitive to computational skews in each iteration. Current load balancing approaches may alleviate the effect of computational skew, but cannot completely solve the problem. As a result, for many applications, the skews in each iteration still exist and they are accumulated, seriously affecting the completion time of these applications. In this paper, we propose an effective approach to make synchronous iterative computing applications themselves have the ability to tolerate the negative effects of unresolved computational skews. This approach divides a large computational task in a computing node or worker into a number of sub-tasks which only depend on the states of a few objects from the previous iteration. This allows the sub-tasks in subsequent iterations to proceed in advance whenever the states of related data objects are available. Consequently, the idle time caused by strict synchronization is reduced and the overall performance is thus enhanced. Experimental results show that this approach can improve the overall performance by up to \(2.45\times \) in comparison with the state-of-the-art approaches.