A Recursive Deterministic Routing Algorithm for Two Dimensional Mesh Network

Network performance in parallel systems, actually, depends on network topology and the used routing algorithm. Routing can be classified as centralized, distributed, deterministic or adaptive. Two Dimensional 2D Mesh is one of the popular general purpose networks due to its node degree is fixed and does not increase as the network size increases, symmetry, embedding of other networks, recursive structure, and excellent scalability. In this paper, we developed an optimal deterministic recursive routing algorithm for 2D Mesh network without wraparound link and enhanced it for 2D Mesh network with wraparound link (Torus). To measure the efficiency of the algorithms, they are applied on 4*7 2D Mesh network, and on 4*7 Torus, respectively. As a result, these routing algorithms are optimal in terms of time and space.