CONSTRUCTING MINIMUM PATH CONFIGURATIONS FOR MULTIPROCESSOR SYSTEMS

The performance of a system of distributed memory multiprocessors depends largely on the efficiency of the message transfer system that connects the co-operating processors, in particular, the processor interconnection strategy. For complex science and engineering applications, frequent global communication is required between a processor and every other processor, so it is desirable to minimize the distance between any two processors in the system. Minimum path (AMP) configurations have been proposed as an interconnection strategy to achieve this, and have been shown to provide smaller interprocessor distances than other popular configurations. A disadvantage of AMP configurations is that they are irregular in nature and so their construction is not trivial. In this paper we present an algorithm which uses search techniques to generate AMP configurations for any specified number of processors. It features several optimizations that reduce the search space and direct the search in order that a good solution (i.e. with small interprocessor distances) may be found in a reasonable time. The algorithm has been implemented in Prolog and the program is in regular use to construct AMP configurations which are used to interconnect networks of transputers for the solution of engineering problems.