Abstract:
We analyze the sensitivity to parameters and the general applicability of genetic algorithms and simulated annealing algorithms for mapping data to distributed-memory
multicomputers, using the loosely synchronous computation model. The analysis includes sensitivity to user parameters, fault tolerance capability, and applicability to
different multicomputer topologies. The user parameters are either objective function dependent or algorithm dependent. The fault tolerance capability is demonstrated by
using the mapping algorithms for mapping data to a multicomputer that has some failed processors. We assume a hypercube multicomputer architecture in most
experiments. However, comparative results for mesh, array, ring, tree, star graph, and
fully connected topologies are presented. The mapping algorithms used are sequential
hybrid genetic algorithm, versions of a distributed genetic algorithm, sequential simulated annealing algorithm, and a simulated parallel simulated annealing algorithm. The experimental results verifY that these algorithms are insensitive to user parameters
in wide ranges, completely fault tolerant, and unbiased towards particular
multicomputer topologies. These results support the conjecture that physical optimization algorithms are flexible and have general applicability, where these properties are necessary for the automation of the mapping process.
