An efficient algorithm for solving the token distribution problem on k-ary d-cube networks
Claude Diderich, Marc Gengler, Stéphane Ubéda · Proceedings of the ... International Symposium on Parallel Architectures, Algorithms, and Networks (ISPAN) · 2002
In parallel programs where the problem data is dynamically generated, it is very useful to be able to rely on an efficient load balancing algorithm. The token distribution problem (TDP) is a generalization of the static load balancing problem. The paper describes a novel algorithm for solving the TDP for k-ary d-cube topology networks. Compared to other algorithms, our method is more general and does not rely on every processor knowing the exact number of tokens associated to each processor. The correctness of the algorithm is proved and its complexity is informally studied.>