  Network-on-chips (NoCs) are currently a widely used approach for achieving
scalability of multi-cores to many-cores, as well as for interconnecting other
vital system-on-chip (SoC) components. Each entity in 2D mesh-based NoCs has a
router responsible for forwarding packets between the dimensions as well as the
entity itself, and it is essentially a 5-port switch. With respect to the
routing algorithm, there are important trade-offs between routing performance
and the efficiency of overcoming potential deadlocks. Common deadlock avoidance
techniques including the turn model usually involve restrictions of certain
paths a packet can take at the cost of a higher probability for network
congestion. In contrast, deadlock resolution techniques, as well as some
avoidance schemes, provide more path flexibility at the expense of hardware
complexity, such as by incorporating (or assuming) dedicated buffers.
  This paper provides a deadlock avoidance algorithm for NoC routers based on
output-queues (OQs) or virtual-output queues (VOQs), with a focus on their use
on field-programmable gate-arrays (FPGAs). The proposed approach features fewer
path restrictions than common techniques, and can be based on existing routing
algorithms as a baseline, deadlock-free or not. This requires no modification
to the queueing topology, and the required logic is minimal. Our algorithm
approaches the performance of fully-adaptive algorithms, while maintaining
deadlock freedom.
