Optimisation of irregular multiprocessor computer architectures using geneticalgorithms

Many problems today need the computing power that is only available by using large‐scaleparallel processing. For a significant number of these problems, the density of theglobal communications between the individual processors dominates the performance ofthe whole parallel implementation on a distributed memory multiprocessor system. In thesecases, the design of the interconnection network for the processors is known to play asignificant part in the efficient implementation of real problems. Important criteria to optimisethe efficiency of a configuration are the maximum and average distance a message hasto travel between processors. Minimum path systems are irregular multiprocessor computerarchitectures which optimise these criteria. These architectures provide an efficient alternativeto the more common regular topologies for solving real applications in parallel. Thispaper presents new results for two combinatorial problems that occur during the generationof these optimal irregular configurations. These are: (1) The design of the optimum interconnection network between the processors for configurationscontaining up to 128 processors. (2) The design of the routing tables to provide the optimal routing of messages withinthese irregular networks. The paper shows how these combinatorial problems have been solved, using genetic algorithmsfor the first problem and a random local search procedure for the second. It alsoincludes a comparison with the results obtained for regular topologies, for example: hypercubes,tori, and rings. Copyright Kluwer Academic Publishers 1999