Skip to main content

The Optimisation of Irregular Multiprocessor Computer Architectures using Genetic Algorithms

C. J. Burgess, A. G. Chalmers, The Optimisation of Irregular Multiprocessor Computer Architectures using Genetic Algorithms. CSTR-96-006, Department of Computer Science, University of Bristol. March 1996. PDF, 141 Kbytes.


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 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 fitness functions used. It also includes a comparison with the results obtained for regular topologies, for example: hypercubes, tori, and rings. This work was presented at the Symposium on Combinatorial Optimisation, Imperial College, London, March 1996.

Bibtex entry.

Contact details

Publication Admin