Document Type
Report
Date
9-1991
Keywords
Data allocation, data partitioning, genetic algorithms, load balancing, loosely synchronous algorithms, neural networks, physical optimization methods, recursive bisection, simulated annealing, task allocation.
Language
English
Disciplines
Computer Sciences
Description/Abstract
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.
Recommended Citation
Mansouri, N. and Fox, Geoffrey C., "A Comparison of Load Balancing Algorithms for Parallel Computations" (1991). Electrical Engineering and Computer Science - Technical Reports. 129.
https://surface.syr.edu/eecs_techreports/129
Source
local
Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.
Additional Information
School of Computer and Information Science, Syracuse University, SU-CIS-91-47