On Bipartite Circulant Graph Decompositions Based on Cartesian and Tensor Products with Novel Topologies and Deadlock-Free Routing

Algorithms. 2023. Vol. 16. No. 1. Article 10.

El-Mesady A., Romanov A., Amerikanov A., Ivannikov A.

Recent developments in commutative algebra, linear algebra, and graph theory allow us to approach various issues in several fields. Circulant graphs now have a wider range of practical uses, including as the foundation for optical networks, discrete cellular neural networks, small-world networks, models of chemical reactions, supercomputing and multiprocessor systems. Herein, we are concerned with the decompositions of the bipartite circulant graphs. We propose the Cartesian and tensor product approaches as helping tools for the decompositions. The proposed approaches enable us to decompose the bipartite circulant graphs into many categories of graphs. We consider the use cases of applying the described theory of bipartite circulant graph decomposition to the problems of finding new topologies and deadlock-free routing in them when building supercomputers and networks-on-chip.

Keywords: supercomputing, сеть на кристалле, network-on-chip, adaptive routing algorithm, tensor product, Cartesian product, graph decomposition, circulant graph, циркулянтный граф

Publication based on the results of: Research of new promising topologies and routing methods for use in networks-on-сhip (2022)