New Methods of Synthesis of Optimal Circulant Graphs for Network-on-Chip Design

Circulant graphs is a promising topology for network applications. This paper is devoted to the development of new software for searching optimal circulant graphs by the criteria of minimizing the average length of shortest paths and diameter. A new version of the algorithm for searching optimal circulant graphs with low time complexity is proposed. New data arrays (datasets) of optimal circulant graphs using the newly developed software are obtained. Based on the newly obtained datasets, the target parameters of circulant graphs are investigated. An analytical formula for computing the bisection width for a subclass of circulant graphs is proposed. Analytical relations transforming the problem of finding optimal circulants of degree eight to a problem of constant time complexity are found.