A flow control mechanism to avoid message deadlock in k-ary n-cubenetworks

摘要

We propose a flow control algorithm for k-ary n-cube networkswhich avoids the deadlock problems without using virtual channels. Somebasic definitions and theorems are proposed in order to establish thenecessary and sufficient conditions to verify that an algorithm isdeadlock-free. Our proposal is based on a restriction of the virtualcut-through flow control rather than of the routing algorithm and it canbe applied both over central buffers or edge buffers. A minimum freebuffer space of two packets is required. The implementation complexityof the router according to Chien's (1993) model, is much easier andfaster than using virtual channels. Network simulations considering therouter complexity show the performance achieved by this new algorithm.The results display a latency improvement of 20% to 35% compared withthe use of virtual channels depending on the load of the network