Connection topologies for multiprocessors using digraphs
Original Publication Date: 2004-Nov-08
Included in the Prior Art Database: 2004-Nov-08
The use of directed graphs or digraphs to represent multiprocessor computer networks is growing in importance. This article introduces the concepts of the round-trip distance between two nodes in a digraph and the round-trip diameter for the digraph as being an important metric as many messages sent across a network require responses to be returned. Various graphs of small order with low round-trip diameters and low average diameters are given, together with a local search technique used to find them.