Optimisation of irregular multiprocessor computer architectures using genetic algorithms

Many problems today need the computing power that is only available by using large-scale parallel processing. For a significant number of these problems, the density of the global communications between the individual processors dominates the performance of the whole parallel implementation on a distributed memory multiprocessor system. In these cases, the design of the interconnection network for the processors is known to play a significant part in the efficient implementation of real problems. Important criteria to optimise the efficiency of a configuration are the maximum and average distance a message has to travel between processors. Minimum path systems are irregular multiprocessor computer architectures which optimise these criteria. These architectures provide an efficient alternative to the more common regular topologies for solving real applications in parallel. This paper presents new results for two combinatorial problems that occur during the generation of these optimal irregular configurations. These are: (1) The design of the optimum interconnection network between the processors for configurations containing up to 128 processors; (2) The design of the routing tables to provide the optimal routing of messages within these irregular networks. The paper shows how these combinatorial problems have been solved, using genetic algorithms for the first problem and a random local search procedure for the second. It also includes a comparison with the results obtained for regular topologies, for example: hypercubes, tori, and rings.