Engineering diffusive load balancing algorithms using experiments

We study a distributed load balancing problem on arbitrary graphs. First Order (F0) and Second Order (SD) schemes are popular local diffusive schedules for this problem. To use them, several parameters have to be chosen carefully. Determining the "optimal" parameters analytically is difficult, and on a practical level, despite the widespread use of these schemes, little is known on how relevant parameters must be set. We employ systematic experiments to engineer the choice of relevant parameters in first and second order schemes. We present a centralized polynomial time algorithm for choosing the "optimal" F0 scheme based on sere[definite programming. Based on the empirical evidence from our implementation of this algorithm, we pose conjectures on the closed-form solution of optimal F0 schemes for various graphs. We also present a heuristic algorithm to locally estimate relevant parameters in the F0 and S0 schemes; our estimates are fairly accurate compared to those based on expensive global communication. Finally, we show that the F0 and S0 schemes that use approximate values rather than the optimal parameters, can be improved using a new iterative scheme that we introduce here; this scheme is of independent interest. The software we have developed for our implementations is available freely, and can serve as a platform for experimental research in this area. Our methods are being included in Paderborn, the Paderborn Finite Element Library [1].