Allocating data to multicomputer nodes by physical optimization algorithms for loosely synchronous computations

Abstract

Three optimization methods derived from natural sciences are considered for allocating data to multicomputer nodes. These are simulated annealing, genetic algorithms and neural networks. A number of design choices and the addition of preprocessing and postprocessing steps lead to versions of the algorithms which differ in solution qualities and execution times. In this paper the performances of these versions are critically evaluated and compared for test cases with different features. The performance criteria are solution quality, execution time, robustness, bias and parallelizability. Experimental results show that the physical algorithms produce better solutions than those of recursive bisection methods and that they have diverse properties. Hence, different algorithms would be suitable for different applications. 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 algorithms. 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 problems.