Ghost packets: a deadlock-free solution for k-ary n-cube networks
Carmen Carrión, Cruz Izu, J.A. Gregorio, Fernando Vallejo, Ramón Beivide · 2002
Improving interconnection subsystems is crucial for the overall performance of a multicomputer system. Hence, a theoretical presentation of a new deadlockfree message flow model for k-ary n-cube networks is developed in this paper. The key idea of this flow control mechanism is to preserve enough free resources for each possible routing dependency cycle, so that packet progress will be guaranteed. Based on this algorithm, we have proposed a simple router structure for a 2-ary n-cube topology with dimensional order routing. Edge or shared buffering can be used, requiring a minimum capacity of one packet per channel. Virtual channels are eliminated, reducing router complexity and, consequently, decreasing network latency at lour loads. In fact, the performance evaluation for the 2-ary n-cube with different loads shows an improvement in the latency parameter of about 20% with respect to a deterministic routing with two virtual channels.