Routing Algorithms in Optimal Degree Four Circulant Networks Based on Relative Addressing: Comparative Analysis for Networks-on-Chip

The solution of the problem of organizing optimal communications in circulant networks of degree four is considered. For a family of optimal circulant networks with the minimum diameter and average distance for any number of nodes in a graph, we propose an optimal pair routing algorithm of constant complexity based on using the relative addressing of nodes in a network. The new algorithm is an analytical extension to any number of nodes in the network of the routing method proposed for dense Gaussian networks, and it does not use division operations, which are very expensive to implement in fixed-point format. This extension is based on the proposed scheme of transformations on the plane of geometrical patterns of optimal circulant networks. The developed routing algorithm is the basis for generating the series of routing algorithms for different subfamilies of the optimal two-dimensional circulants. The general routing algorithm and its modification for a separate subclass of circulants are implemented in the HDL NoC model with circulant topology. All the algorithm parameters important for networks-on-chip, including the consumption of memory, logical resources, and execution time are comprehensively investigated. The results of a comparative analysis of the new algorithms with other routing algorithms, previously implemented in the networks-on-chip, are presented.

I. Introduction

IN THIS paper, we investigate the solution to the problem of organizing efficient routing algorithms in networks-on-chip (NoCs) [1], [2], [3], [4], [5] with a topology of the class of undirected degree four circulant networks. Circulant networks (graphs) (see the surveys [6], [7], [8], [9]) are a class of regular graphs well-known both in applied practical solutions and in theoretical research (see, for instance, [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22]).