Browse Prior Art Database

Connection topologies for multiprocessors using digraphs Disclosure Number: IPCOM000032500D
Original Publication Date: 2004-Nov-08
Included in the Prior Art Database: 2004-Nov-08

Publishing Venue



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.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 18% of the total text.

Page 1 of 11

Connection topologies for multiprocessors using digraphs

Disclosed are some directed graphs of low diameter or round-trip diameter which can be used to make multiprocessor networks. The concept of round-trip diameter is explained here, together with a search technique for finding these graphs and some generalised constructions of these graphs.

    Multiprocessor systems are often built from processors with point to point links for data transmission. If the links are unidirectional then we can describe the connections as a directed graph, also known as a digraph. Digraphs are characterised by: vertices - also known as nodes and for example are the processors order - the number of vertices arcs - which link the vertices the degree, d, the maximum number of vertices directly connected to a vertex (in-degree), or from a vertex (out-degree). This is the same as the number of arcs entering or leaving a vertex distance - the minimum number of arcs needed to be traversed to get between a given pair of vertices diameter, D, - the maximum distance between any pair of vertices

    It is useful to minimise the number of arcs needed to be traversed to get between two vertices.

    A number of digraph constructions are given by Dinneen[1], including one by Imase and Itoh[2].

    Here is disclosed the following digraph of degree d=2 and diameter D=3 which is a little more efficient that the standard digraph given by Imase and Itoh. Imase and Itoh suggest connections as j = -id - q (mod n), q = 1, 2, ... d

The following connection matrix was found by a search process - see below.

If the processors are connected as in Fig. 1. using one way point to point links then any processor is only a maximum of 3 hops or arcs from another processor, i.e. the diameter is 3.

E.g. to get from processor 0 to processor 1 go via 10 then to 4

From/ to

0 1 2 3 4 5 6 7 8 9 10 11

0 X X

1 X X

2 X X

3 X X

4 X X

5 X X

Page 2 of 11

6 X X

7 X X

8 X X

9 X X

10 X X

11 X X

Figure 1

    The Wiener index of a graph is defined to be the sum of distances over all pairs of vertices.

The total number of hops to get from each processor to every other processor is 300, the minimum possible. This is calculated as: 12 nodes * 2 destinations, 1 hop = 24 12 nodes * 2*2 destinations, 2 hops, = 96 12 nodes, 12-1-2-2*2 = 5 remaining destinations, 3 hops = 180 total = 24+96+180=300 hops in total

    The total number of hops can then be used to calculated the average distance by dividing by the number of pairs of nodes, n.(n-1). For this case the average distance is 300/(12*11) = 25/11 = 2.727272...

    An efficient network of order N has a total number of hops as follows: T = N.(0.1 + 1.d + 2.d2 + 3.d3 + ... D.(N - dD+1 ) where each node is connected to a maximally branching tree of nodes.

    A perfectly efficient network of diameter D would have order N where N = 1 + d + d2 + d3 + ... dD = (dD+1 - 1)/(d - 1)

This is the directed Moore bound.

    Connectivity matrix showing number of hops to get to each destination from each...