Shortest Path Search Algorithm in Optimal Two-Dimensional Circulant Networks: Implementation for Networks-on-Chip

Abstract

For a family of optimal two-dimensional circulant networks with an analytical description, two new improved versions of the shortest path search algorithm with a constant complexity estimate are obtained. A simple, based on the geometric model of circulant graphs, proof of the formulas used for the shortest path search algorithm is given. Pair exchange algorithms are presented, and their estimates are given for networks-on-chip (NoCs) with a topology in the form of the considered graphs. New versions of the algorithm improve the previously proposed shortest path search algorithm for optimal generalized Petersen graphs with an analytical description. The new proposed algorithm is a promising solution for the use in NoCs which was confirmed by an experimental study while synthesizing NoC communication subsystems and comparing the consumed hardware resources with those when other previously developed routing algorithms.

Keywords

• Two-dimensional circulant graphs
• diameter
• shortest path
• optimal generalized Petersen graphs
• networks-on-chip