Turn Prohibition Routing Investigation for Irregular, 2D-Mesh and 3D-Mesh Based Network on Chip
Naveen Choudhary, Department of Computer Science and Engineering, College of Technology and Engineering, Maharana Pratap University of Agriculture and Technology, Udaipur, Rajasthan, India.
Manuscript received on April 05, 2013. | Revised Manuscript received on April 28, 2013. | Manuscript published on May 05, 2013. | PP: 195-198 | Volume-3, Issue-2, May 2013. | Retrieval Number: B1496053213/2013©BEIESP
Open Access | Ethics and Policies | Cite
© The Authors. Published By: Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: Network on Chip (NoC) has established itself as an alternative to the on chip bus to meet the increasing requirements of complex communication needs of system on Chip (SoC). A popular choice of topology for generic Network on Chip has been 2D Meshes. Similarly for application specific Network on Chip irregular topologies customized to application needs is preferred. However as the feature size continue to shrink and integration densities continue to increase, the interconnect delay is emerging as the critical bottleneck for the performance of 2D NoC. The advances in technology such as over the cell routing and Through-Silicon-Vias (TSV) has made possible performance conscious and scalable Network on Chip with more than 2 dimension. As was the case with 2D Mesh NoC, the 3D Mesh NoC is proving to be a preferred choice for the NoC designers due to its simple and scalable design. The communication over the Network on Chip is required to be deadlock and livelock free. Turn prohibition based routing function are a popular choice for NoC communication as it provides deadlock free communication over the NoC without the requirement of additional physical or virtual channels. Moreover turn prohibition based routing is capable of providing deadlock free, livelock free, minimal or nonminimal and maximally adaptive communication over NoCs. Turn prohibition routing is based on analyzing the directions in which packets can turn in the network and the cycles that the turns can form. Prohibiting just enough turns to break all the resource dependence cycles in the network can help researchers design an effective and efficient deadlock and livelock free routing functions for the NoCs. This paper presents an investigation of the various popular turn prohibition based routing algorithms presented in the NoC research literature for 2D mesh, 3D mesh and irregular topology based on chip networks.
Keywords: Turn Model, Routing, Network-on-Chip, Livelock, Deadlock.