Search

This article considers the usage of circulant topologies as a promising deadlock-free topology for networks-on-chip (NoCs). A new high-level model, Newxim, for the exploration of NoCs with any topology is presented. Two methods for solving the problem of cyclic dependencies in circulant topologies, which limit their applications for NoCs due to the increased possibility of deadlocks, are proposed. The first method of dealing with deadlocks is universal and applicable to any topology; it is based on the idea of bypassing blocked sections of the network on an acyclic subnetwork. The second method—Ring-Split—takes into account the features of circulant topologies. The results of high-level modeling and comparison of the peak throughput of NoCs for circulant and mesh topologies using deadlock-free routing algorithms are presented. It was shown that a new approach for routing in circulants (compared to mesh topology) shows up to 59% better network throughput with a uniform distribution of network load.

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.