TY - GEN
T1 - Adaptive routing on the recursive diagonal torus
AU - Funahashi, Akira
AU - Hanawa, T.
AU - Kudoh, T.
AU - Amano, Hideharu
PY - 1997
Y1 - 1997
N2 - Recnrsive Diagonal Torus, or RDT consisting of recursively structured tori is an interconnection network tbr massively parMlel computers. By adding remote links to the diagonal directions of the torus network recursively, the diameter can be reduced within log2N with smaller number of links than that of hypercube. For an interconnection network for massively parallel computers, a routing algorithm which can bypass a faulty or congested node are essential. Although the conventional vector routing is a simple and near-optimM method, it can only use a deterministic path. In this paper, adaptive routing algorithms on RDT are proposed and discussed. The first algorithm is based on Duato's necessary and sufficient condition. With this method virtual channels are effectively used while paths with redundant routing steps are prohibited. Another algorithm based on the turn model is proposed. By prohibiting certain turns on RDT, it permits paths with additional hops. Both algorithms are proved to be deadlock free.
AB - Recnrsive Diagonal Torus, or RDT consisting of recursively structured tori is an interconnection network tbr massively parMlel computers. By adding remote links to the diagonal directions of the torus network recursively, the diameter can be reduced within log2N with smaller number of links than that of hypercube. For an interconnection network for massively parallel computers, a routing algorithm which can bypass a faulty or congested node are essential. Although the conventional vector routing is a simple and near-optimM method, it can only use a deterministic path. In this paper, adaptive routing algorithms on RDT are proposed and discussed. The first algorithm is based on Duato's necessary and sufficient condition. With this method virtual channels are effectively used while paths with redundant routing steps are prohibited. Another algorithm based on the turn model is proposed. By prohibiting certain turns on RDT, it permits paths with additional hops. Both algorithms are proved to be deadlock free.
UR - http://www.scopus.com/inward/record.url?scp=84958608673&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958608673&partnerID=8YFLogxK
U2 - 10.1007/BFb0024214
DO - 10.1007/BFb0024214
M3 - Conference contribution
AN - SCOPUS:84958608673
SN - 3540637664
SN - 9783540637660
VL - 1336
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 171
EP - 182
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PB - Springer Verlag
T2 - International Symposium on High Performance Computing, ISHPC 1997
Y2 - 4 November 1997 through 6 November 1997
ER -