Optimisation of irregular multiprocessor computer architectures using genetic algorithms

Many problems today need the computing power that is only available by usin g large-scale parallel processing. For a significant number of these proble ms, the density of the global communications between the individual process ors dominates the performance of the whole parallel implementation on a dis tributed memory multiprocessor system. In these cases, the design of the in terconnection network for the processors is known to play a significant par t in the efficient implementation of real problems. Important criteria to o ptimise the efficiency of a configuration are the maximum and average dista nce a message has to travel between processors. Minimum path systems are ir regular multiprocessor computer architectures which optimise these criteria . These architectures provide an efficient alternative to the more common r egular topologies for solving real applications in parallel. This paper pre sents new results for two combinatorial problems that occur during the gene ration of these optimal irregular configurations. These are: (1) The design of the optimum interconnection network between the processor s for configurations containing up to 128 processors. (2) The design of the routing tables to provide the optimal routing of mess ages within these irregular networks. The paper shows how these combinatorial problems have been solved, using ge netic 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.