Dealing with deadlock has always been a crucial issue for any routing algorithms proposed for wormhole-switched networks. Adaptive routing algorithms, based on deadlock avoidance strategies, usually dedicate resources specifically to ensure deadlock freedom. However, a number of recent studies have demonstrated that deadlocks are quite rare in the network. This fact has motivated researchers to introduce adaptive routing algorithms based on deadlock recovery strategies. In an effort to gain a deep understanding of the factors that affect routing performance, a comparison of the performance merits of deadlock recovery against deadlock avoidance routing algorithms is performed. While most existing network evaluation studies have been based on software simulation, the present study is the first to use the analytical modelling approach to conduct the comparative analysis. The results reveal that in most cases deadlock recovery routing algorithms exhibit superior performance characteristics over their deadlock avoidance counterparts.
References
-
-
1)
-
H. Sarbazi-Azad ,
M. Ould-Khaoua ,
L.M. Mackenzie
.
An accurate analytical model of adaptive wormhole routing in k-ary n-cube interconnection networks.
Perform. Eval.
,
165 -
179
-
2)
-
Anderson, E., Brooks, J., Grassl, C., Scott, S.: `Performance of the Cray T3E multiprocessor', Proc. ACM/IEEE Supercomputing Conf., 15–21 November 1997, San Jose, CA, p. 19–26.
-
3)
-
A. Agarwal
.
Limits on interconnection network performance.
IEEE Trans. Parallel Distrib. Syst.
,
398 -
412
-
4)
-
J.T. Draper ,
J. Ghosh
.
A comprehensive analytical model for wormhole routing in multicomputer systems.
J. Parallel Distrib. Comput.
,
212 -
214
-
5)
-
Anjan, K.V., Pinkston, T.M., Duato, J.: `Generalised theory for deadlock-free adaptive wormhole routing and its application to DISHA concurrent', Proc. 10th ACM/IEEE Int. Parallel processing Symp., 15–19 April 1996, Honolulu, Hawaii, p. 815–821.
-
6)
-
W.J. Dally
.
Performance analysis of k-ary n-cubes interconnection networks.
IEEE Trans. Comput.
,
6 ,
775 -
785
-
7)
-
Khonsari, A., Ould-Khaoua, M.: `Message latency of the compressionless adaptive routing algorithm', Proc. Int. Symp. on Performance evaluation of computer and telecommunication systems (SPECTS' 2001), 15–19 July 2001, Orlando, FL, p. 97–104.
-
8)
-
J. Kim ,
C.R. Das
.
Hypercube, communication delay with wormhole routing.
IEEE Trans. Comput.
,
7 ,
806 -
814
-
9)
-
X. Lin ,
P.K. McKinley ,
L.M. Ni
.
The message flow model for routing in wormhole-routed networks.
IEEE Trans. Parallel Distrib. Syst.
,
7 ,
755 -
760
-
10)
-
B. Ciciani ,
M. Colajanni ,
C. Paolucci
.
Performance evaluation of deterministic wormhole routing in k-ary n-cubes.
Parallel Comput.
,
14 ,
2153 -
2175
-
11)
-
J. Duato ,
S. Yalamanchili ,
L.M. Ni
.
(2003)
Interconnection networks: an engineering approach.
-
12)
-
W.J. Dally
.
Virtual channel flow control.
IEEE Trans. Parallel Distrib. Syst.
,
2 ,
194 -
205
-
13)
-
J.H. Kim ,
Z. Liu ,
A.A. Chen
.
Compressionless routing: A framework for adaptive and fault-tolerant routing.
IEEE Trans. Parallel Distrib. Syst.
,
3 ,
229 -
244
-
14)
-
Laudon, J., Lenoski, D.: `The SGI origin: a ccNUMA highly scalable server', Proc. ACM/IEEE 24th Int. Symp. on Computer architecture, 2–4 June 1997, Denver, CO, p. 241–251.
-
15)
-
Anjan, K.V., Pinkston, T.M.: `An efficient fully adaptive deadlock recovery scheme: DISHA', Proc. 22nd Int. Symp. on Computer architecture, 22–24 June 1996, Santa Margherita Ligure, Italy, p. 201–210.
-
16)
-
Boura, Y., Das, C.R., Jacob, T.M.: `A performance model for adaptive routing in hypercubes', Proc. Int. Workshop Parallel processing, 22–25 January 1994, North Carolina State University, NC, p. 11–16.
-
17)
-
Kessler, R.E., Schwarzmeier, J.L.: `CRAY T3D: a new dimension for Cray Research', Proceedings of CompCon, February 1993, San Francisco, CA, p. 176–182.
-
18)
-
Khonsari, A., Shahrabi, A., Ould-Khaoua, M.: `A performance model of true fully adaptive wormhole routing with deadlock recovery in ', Proc. IEEE 10th Int. Symp. on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS2002), 12–16 October 2002, Fort Worth, TX, IEEE Computer Society Press, 2002.
-
19)
-
W.J. Dally ,
C.L. Seitz
.
Deadlock-free message routing in multiprocessor interconnection networks.
IEEE Trans. Comput.
,
5 ,
547 -
555
-
20)
-
Su, C., Shin, K.G.: `Adaptive deadlock-free routing in multicomputers using one extra channel', Proc. Int. Conf. on Parallel Processing, 14 August 1993, St. Charles, IL, 1, p. 175–182.
-
21)
-
A. Khonsari ,
H. Sarbazi-Azad ,
M. Ould-Khaoua
.
Analysis of true fully adaptive routing with Software-based deadlock recovery.
J. Syst. Softw.
-
22)
-
Vanvoorst, B., Seidel, S., Barscz, E.: `Workload of an iPSC/860', Proc. Scalable high-performance computing Conf., 23–25 May 1994, Knoxville, TN, p. 221–228.
-
23)
-
J. Duato
.
A new theory of deadlock-free adaptive routing in wormhole routing networks.
IEEE Trans. Parallel Distrib. Syst.
,
12 ,
1321 -
1331
-
24)
-
W.J. Dally ,
H. Aoki
.
Deadlock-free adaptive routing in multicomputer networks using virtual channels.
IEEE Trans. Parallel Distrib. Syst.
,
4 ,
466 -
475
-
25)
-
H. Sarbazi-Azad ,
A. Khonsari ,
M. Ould-Khaoua
.
Analysis of deterministic routing in k-ary n-cubes with virtual channels.
J. Interconnect. Netw.
,
85 -
101
-
26)
-
Martinez, J.M., Lopez, P., Duato, J., Pinkston, T.M.: `Software-based deadlock recovery techniques for true fully adaptive routing in wormhole networks', Proc. Int. Conf. on Parallel Processing (ICPP'97), 11–15 August 1997, Bloomingdale, IL, p. 182–189.
-
27)
-
M. Ould-Khaoua
.
A performance model for Duato's fully adaptive routing algorithm in k-ary n-cubes.
IEEE Trans. Comput.
,
12 ,
1 -
8
-
28)
-
Boura, Y., Das, C.R.: `Modelling virtual channel flow control in hypercube', Proc. Int. Symp. on High-performance computer architecture, 22–25 January 1995, Raleigh, CA, p. 166–175.
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-cdt_20030279
Related content
content/journals/10.1049/ip-cdt_20030279
pub_keyword,iet_inspecKeyword,pub_concept
6
6