D-iteration: Evaluation of a Dynamic Partition Strategy
This work addresses load balancing in distributed linear equation solving, but the improvements are incremental over existing static partition results.
The paper evaluates a dynamic partition strategy for the D-iteration method, showing that it improves load balancing and scalability compared to static partitioning, with near-linear speedup and reduced memory per virtual machine.
The aim of this paper is to present a first evaluation of a dynamic partition strategy associated to the recently proposed asynchronous distributed computation scheme based on the D-iteration approach. The D-iteration is a fluid diffusion point of view based iteration method to solve numerically linear equations. Using a simple static partition strategy, it has been shown that, when the computation is distributed over K virtual machines (PIDs), the memory size to be handled by each virtual machine decreases linearly with K and the computation speed increases almost linearly with K with a slope becoming closer to one when the number N of linear equations to be solved increases. Here, we want to evaluate how further those results can be improved when a simple dynamic partition strategy is deployed and to show that the dynamic partition strategy allows one to control and equalize the computation load between PIDs without any deep analysis of the matrix or of the underlying graph structure.