Data allocation, data partitioning, genetic algorithms, load balancing, loosely synchronous algorithms, neural networks, physical optimization methods, recursive bisection, simulated annealing, task allocation.
Three physical optimization methods are considered in this paper for load balancing parallel computations. These are simulated annealing, genetic algorithms, and neural networks. Some design choices and the inclusion of additional steps lead to new versions of the algorithms with different solution qualities and execution times. The performances of these versions are critically evaluated and compared for test cases with different topologies and sizes. Orthogonal recursive coordinate bisection is also included in the comparison as a typical simple deterministic method. Simulation results show that the algorithms have diverse properties. Hence, different algorithms can be applied to different problems and requirements. For example, the annealing and genetic algorithms produce better solutions and do not show a bias towards particular problem structures. But, they are slower than the neural network and recursive bisection. Preprocessing graph contraction is one of the additional steps suggested for the physical methods. It produces a significant reduction in execution time, which is necessary for their applicability to large-scale problems.
Mansouri, N. and Fox, Geoffrey C., "A Comparison of Load Balancing Algorithms for Parallel Computations" (1991). Electrical Engineering and Computer Science Technical Reports. 129.
Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.