A Generalized Routing Algorithm for a Family of Optimal 2D Circulant Networks Based on Relative Addressing

The problem of the organization of optimal communications in circulant networks is considered. For a family of optimal two-dimensional circulant networks with the minimum diameter and average distance, the relative addressing of nodes of a network is introduced as shortest paths vectors from a fixed node. On its basis, a constant complexity pair routing algorithm using a set of shortest paths is proposed. This algorithm reduces the execution time in comparison with known routing algorithms due to the elimination of division operations and reduces the required memory to few words. The new algorithm is an analytical generalization to any number of nodes in a network of the method proposed for the family of Gaussian networks. This generalization is based on the proposed scheme of transformations on the plane of geometrical patterns of graphs of the family. The routing algorithm can be applied in networks-on-chip with a two-dimensional circulant topology.

I. Introduction

In this paper, we investigate the solution to the problem of organizing efficient routing algorithms in the class of undirected circulant graphs of degree four. Let us give the definition of circulant networks [1] , [2] . An undirected circulant graph C ( N; s ₁ , …, s _k ) has a set of vertices V = Z _N = {0, 1, …, N − 1} and a set edges . Here S = { s ₁ , s ₂ , …, s _k }, 1 ≤ s ₁ < … < s _k < N is a set of generators, N is its order, k is its dimension. The degree of a vertex of the circulant δ = 2 k , if s _k ≠ N /2, or 2 k − 1 otherwise. The diameter of the graph is D = max _{u , v ∈ V} l ( u , v ), where l ( u , v ) is the length of the shortest path between the vertices u and v . Diameter and average distance evaluate structural delays in a network, as well as connectivity and survivability of the network [3] , [4] . According to various criteria functioning the best topologies of multiprocessor systems with an equal number of nodes and communication lines are structures with the minimum diameter and average distance [2] . In this paper, we consider a family of circulants of dimension two and degree four, which have the minimum diameter and average distance for any number of nodes. Circulant graphs of dimension two are known as topologies for some multiprocessor systems, including the promising networks-on-chip (NoCs) topologies [5] – [8] . Compared to popular NoC topologies such as mesh and 2D tori [9] , they have a smaller diameter and lower average distance for the same number of nodes in the network. Networks on a chip require structures that support effective communications between processors. In this paper the problem of organization of optimal communications in circulant networks is considered. Some optimal routing algorithms were proposed for circulant graphs of degree 4, some of which were implemented in NoCs, see for example [5] – [8] , [10] – [13] . In this article, we have introduced for circulants a new node labeling by their vectors of shortest paths. Based on this labeling (relative addressing of nodes) we have proposed an optimal routing algorithm for a family of two-dimensional circulant networks. This algorithm reduces the execution time in comparison with known routing algorithms due to the elimination of division operations and reduces the required memory to few words.