Genetic Algorithms for Generating Minimum Path Configurations

this paper we will restrict attention to systems that support a maximum of four links per processor, but the principles described are equally applicable to any number of links per processor. The distance between any two processors may be measured as the number of links a message has to traverse between its source processor and the destination processor. This increase in maximum distance between any two processors is a function of the underlying interconnection strategy. The philosophy underlying the construction of a minimum path (AMP) configuration is to minimize the diameter, d max , of the interconnection network; that is, to minimize the maximum number of links a message has to travel between any source processor and any other destination processor within the configuration. This principle is maintained even at the expense of the loss of regularity in a system. Due to their irregular nature, the problem of finding optimum AMP configurations is a large one and is a formidable task even for traditional heuristic depth-first search strategies [4], prompting Steve Gregory's quote given above. For example, from the initial spanning tree of a 32 processor AMP (see section 2.1), there are 66 links that need to be connected givin