A novel non-minimal/minimal turn model for highly adaptive routing in 2D NoCs

Networks-on-Chip (NoCs) are emerging as a promising communication paradigm to overcome bottleneck of traditional bus-based interconnects for current micro-architectures (MCSoC and CMP). One of the current issues in NoC routing is the use of acyclic Channel Dependency Graph (CDG) for deadlock freedom. This requirement forces certain routing turns to be prohibited, thus, reducing the degree of adaptiveness. In this paper, we propose a novel non-minimal turn model which allows cycles in CDG provided that Extended Channel Dependency Graph (ECDG) remains acyclic. The proposed turn model reduces number of restrictions on routing turns, hence able to provide path diversity through additional minimal and non-minimal routes between source and destination.