Matrix-Star Graphs: A New Interconnection Network Based on Matrix Operations

In this paper, we introduce new interconnection networks

matrix-star graphs

MTS

n

1,...,

nk

where a node is represented by

n

1

× ... ×

n

k

matrix and an edge is defined by using matrix operations. A matrix-star graph

MTS

2,n

can be viewed as a generalization of the well-known star graph such as degree, connectivity, scalability, routing, diameter, and broadcasting. Next, we generalize

MTS

2,n

to 2-dimensional and 3-dimensional matrix-star graphs

MTS

k

,

n

,

MTS

k

,

n

,

p

. One of important desirable properties of interconnection networks is network cost which is defined by degree

times

diameter. The star graph, which is one of popular interconnection topologies, has smaller network cost than other networks. Recently introduced network, the macro-star graph has smaller network cost than the star graph. We further improve network cost of the macro-star graph: Comparing a matrix-star graph

$MTS_{k,k,k}(k = \sqrt[3]{n^{2}})$

with

n

2

! nodes to a macro-star graph

MS

(

n

–1,

n

–1) with ((

n

–1)

2

+1)! nodes, network cost of

MTS

k

,

k

,

k

is

O

(

n

2.7

) and that of

MS

(

n

–1,

n

–1) is

O

(

n

3

). It means that a matrix-star graph is better than a star graph and a macro-star graph in terms of network cost.