关键词: 流控, k-ary n-cube, 关键气泡机制, 死锁, 虚跨步

Abstract: Bubble flow control is an efficient and buffer occupancy-based technique to avoid deadlock in torus networks. Critical bubble scheme can avoid intra-dimension deadlock with just one packet buffer by marking and tracking as “critical” a certain number of free packet-sized buffers, but has a risk of blocking. A false packet protocol and the design of a non-blocking moveable bubble scheme are presented to solve the block induced by critical bubble. False packet protocol adopts simple request-acknowledge, and the whole scheme is implemented on typical credit flows, and no other special requirement is needed. Unlike the typical bubble scheme, which is locally aware, this scheme is also an efficient implementation of a globally-aware flow control mechanism. Combing an escape channel based on moveable bubble scheme and a fully adaptive channel brings a fully adaptive router with minimal two virtual channels, with one packet buffer per virtual channel. To show the advantage of this scheme, the performance of various bubble-based schemes is compared. Network simulation results show that the moveable bubble scheme outperforms traditional bubble scheme, whereas adaptive scheme performs apparently better than the other non-adaptive methods. It avoids blocking, leads to much lower average packet latency, and displays a throughput improvement of more than 20%, maximally up to 100%.

Key words: flow control, k-ary n-cube, critical bubble scheme, deadlock, virtual cut-through