Keywords: deadlock, routing algorithms, wormhole routing, fault tolerance, mesh networks, networks on chip
Received May 13, 2005; revised February 24 & June 12, 2006 & January 22, 2007; accepted May 15, 2007.
Communicated by David H. C. Du.
| Previous | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
¡@
Rickard Holsmark and Shashi Kumar
Department of Computer and Electrical Engineering
School of Engineering
Jonkoping University
SE-551 11, Jonkoping, Sweden
Chen and Chiu published a fault tolerant routing algorithm for mesh topology networks
[1] which they claimed was deadlock free in the presence of multiple faults. In
this paper we give a counter-example to show that their Message-Route algorithm [1]
fails to provide deadlock free routing in a 2 dimensional mesh network. We also point
out certain cases where the algorithm fails to route messages to their destinations. We
identify an error in the proof of the main theorem in their paper [1] which was used for
proving the property of deadlock freeness. Changes to their algorithm are proposed to
make it deadlock free and complete. We also discuss a new application of fault tolerant
routing algorithms for non-homogeneous 2-dimensional mesh topology networks for
on-chip communication.
Received May 13, 2005; revised February 24 & June 12, 2006 & January 22, 2007; accepted May 15, 2007.
Communicated by David H. C. Du.