Keywords: multicomputer, wormhole routing, deadlock detection, deadlock recovery, adaptive routing
Received June 7, 2007; revised May 14, 2008; accepted July 3, 2008.
Communicated by Chung-Ta King.
| Previous | [ 1] | [ 2] | [ 3] | [ 4] | [ 5] | [ 6] | [ 7] | [ 8] | [ 9] | [ 10] | [ 11] | [ 12] | [ 13] | [ 14] | [ 15] | [ 16] | [ 17] | [ 18] | [ 19] | [ 20] |
¡@
Soojung Lee
Department of Computer Education
Gyeongin National University of Education
Anyang, Kyunggi-do, 430-804 Korea
Deadlock detection and recovery-based routing schemes for wormhole networks
have gained attraction because unlike deadlock avoidance-based schemes, they do not
restrict routing adaptability. In order to alleviate the overhead of running a recovery procedure,
the studies on deadlock detection have focused on the accuracy of deadlock detection,
trying to reduce the number of false detections. This paper proposes both deadlock
detection and recovery schemes. The proposed detection scheme is based on the
turn model and designed to declare only one packet per simple cycle of blocked packets
as deadlocked. Our recovery scheme adjusts the time-out value flexibly according to the
utilization rate of the recovery resources, rather than fixing a single time-out value as in
previous schemes. As a consequence, it not only prevents saturation of the recovery resources
by deadlocked packets but also reduces congestion of normal buffers at heavy
loads. Simulation experiments show that the proposed deadlock detection scheme significantly
reduces the number of false deadlock detections over previous schemes for
low to moderate time-out thresholds. It is also found that the proposed recovery scheme
prevents overloading of the recovery resources, yielding better network performance.
Received June 7, 2007; revised May 14, 2008; accepted July 3, 2008.
Communicated by Chung-Ta King.