Multiplicative circulant networks topological properties and communication algorithms Original Research Article

In this paper we study an interconnection network topology based on the radix representation of integers and modulo arithmetic. The multiplicative circulant graph MC(r, k) consists of n = rk vertices. Two vertices x and y are connected by an edge if and only if ¦x − y¦= ri mod n for some integer i, 0 ⩽ i ⩽ k − 1. Multiplicative circulant graphs can be considered as a kind of “twisted” torus graphs. We prove that for even r > 2 the diameter of the MC(r, k) network is kr2 − ⌊K2⌋ which is smaller than the diameter of the corresponding torus. We also determine the average distance in the MC(r, k) graphs. The multiplicative circulant graphs are vertex symmetric and have Hamiltonian cycles, one of them being 0, 1, …, n − 1. The MC(r, k) graph can be recursively decomposed into r MC(r, k − 1) graphs and the later Hamiltonian cycle. Hypercubes and complete binary trees are embedded in MC(2, k) graphs with dilation and expansion 1. A (pk)-dimensional hypercube can be embedded into MC(2p, k) graph with expansion 1 and dilation 2p-1. Multiplicative circulant graphs have simple optimal routing and broadcasting algorithms. These algorithms are deadlock free for r = 2 and r = 3. A simple parallel semigroup and prefix computation algorithm for the multiplicative circulant networks are described.