The optimization 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 signi#cantnumber 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 signi#cant part in the e#cient implementation of real problems. Important criteria to optimise the e#ciency of a con#guration 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 e#cient 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 con#gurations. These are: 1. The design of the optimum interconnection network between the processors for con#gurations containing up to several hundred 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, and includes details of the representation of the problems, the genetic operators applied and the #tness functions used. It also includes a comparison with the results obtained for regular topologies, for example: hypercubes, tori, and rings.