Engineering Diffusive Load Balancing Algorithms Using Experiments

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